In [2]:
LoadPackage("francy");
LoadPackage("num");
Out[2]:
Out[2]:
This example draws the Apéry set of a numerical semigrup with respect to its multiplicity. By passing over a node with the mouse, the set of factorizations with respect to the minimal generating system of the numerical semigroup is displayed. Clicking a node produces a message with the same information.
In [3]:
apery:=function(arg)
local ap,c,hasse, s, n, r, graphHasse, aps, es, canvas, i, order, showfacts, message;
# rel is a list of lists with two elements representin a binary relation
# hasse(rel) removes from rel the pairs [x,y] such that there exists
# z with [x,z],[z,y] in rel
hasse:=function(rel)
local dom, out;
dom:=Flat(rel);
out:=Filtered(rel, p-> ForAny(dom, x->([p[1],x] in rel) and ([x,p[2]] in rel)));
return Difference(rel,out);
end;
order:=function(x)
return Maximum(LengthsOfFactorizationsElementWRTNumericalSemigroup(x,s));
end;
showfacts:=function(x)
message := FrancyMessage(Concatenation(String(x), " factors as "),
String(FactorizationsElementWRTNumericalSemigroup(x,s)));
SetFrancyId(message, Concatenation("message-for-", String(x)));
Add(canvas, message);
return Draw(canvas);
end;
if Length(arg)=1 then
s:=arg[1];
n:=MultiplicityOfNumericalSemigroup(s);
fi;
if Length(arg)=2 then
s:=arg[1];
n:=arg[2];
fi;
if Length(arg)>2 then
Error("The number of arguments must be one or two");
fi;
graphHasse := Graph(GraphType.UNDIRECTED);
#SetSimulation(graphHasse,true);
#SetDrag(graphHasse,true);
ap:=AperyList(s,n);
c:=Cartesian([1..n],[1..n]);
c:=Filtered(c, p-> ap[p[2]]<>ap[p[1]]);
c:=Filtered(c, p-> ap[p[1]]-ap[p[2]] in s);
c:=hasse(c);
aps:=[];
for i in [1..n] do
aps[i]:=Shape(ShapeType!.CIRCLE, String(ap[i]));
SetLayer(aps[i],-order(ap[i]));
Add(aps[i],Callback(showfacts,[ap[i]]));
Add(aps[i],FrancyMessage(Concatenation("{",
JoinStringsWithSeparator(List(FactorizationsElementWRTNumericalSemigroup(ap[i],s),
f->Concatenation("(",JoinStringsWithSeparator(f,","),")")),","),")")));
Add(graphHasse,aps[i]);
od;
for r in c do
Add(graphHasse,Link(aps[r[1]],aps[r[2]]));
od;
canvas:=Canvas("Apery");
Add(canvas,graphHasse);
return Draw(canvas);
end;
Out[3]:
In [4]:
apery(NumericalSemigroup(10,51,27,31));
Out[4]:
This example shows how to draw the sons of a numerical semigroup in the tree of numerical semigroups. If we click on a node, then the sets of sons of that node are added to the canvas, and if the node is a leaf, a warning message is displayed.
Passing the mouse over a node shows the set of minimal generators of the node.
In [5]:
sons:=function(s)
local gens, frb, desc, graphHasse, d, shpr, shp, canvas, sonsf, i, gn, lbl;
sonsf:=function(s,n)
local gens, frb, desc, d, shp, i, lbl, gn;
frb:=FrobeniusNumber(s);
gens:=Filtered(MinimalGenerators(s), x-> x>frb);
desc:=List(gens, g->RemoveMinimalGeneratorFromNumericalSemigroup(g,s));
gn:=Genus(s);
i:=0;
for d in desc do
i:=i+1;
lbl:=Concatenation("$\\langle",JoinStringsWithSeparator(MinimalGenerators(d),","),"\\rangle$");
shp:=Shape(ShapeType!.CIRCLE, lbl);
SetFrancyId(shp,lbl);
SetLayer(shp,Genus(d));
SetSize(shp,1);
Add(shp,Callback(sonsf,[d,shp]));
Add(shp,FrancyMessage(String(MinimalGenerators(d))));
Add(graphHasse,shp);
Add(graphHasse,Link(n,shp));
od;
if desc<>[] then
return Draw(canvas);
fi;
Add(canvas, FrancyMessage(FrancyMessageType.WARNING, "This semigroup is a leaf"));
return Draw(canvas);
end;
frb:=FrobeniusNumber(s);
gens:=Filtered(MinimalGenerators(s), x-> x>frb);
desc:=List(gens, g->RemoveMinimalGeneratorFromNumericalSemigroup(g,s));
gn:=Genus(s);
graphHasse := Graph(GraphType.UNDIRECTED);
lbl:=Concatenation("$\\langle",JoinStringsWithSeparator(MinimalGenerators(s),","),"\\rangle$");
shpr:=Shape(ShapeType!.CIRCLE, lbl);
SetSize(shpr,1);
SetFrancyId(shpr,lbl);
Add(shpr,FrancyMessage(String(MinimalGenerators(s))));
SetLayer(shpr,Genus(s));
Add(graphHasse,shpr);
i:=0;
for d in desc do
i:=i+1;
lbl:=Concatenation("$\\langle",JoinStringsWithSeparator(MinimalGenerators(d),","),"\\rangle$");
shp:=Shape(ShapeType!.CIRCLE, lbl);
SetFrancyId(shp,lbl);
SetLayer(shp,Genus(d));
SetSize(shp,1);
Add(shp,Callback(sonsf,[d,shp]));
Add(shp,FrancyMessage(String(MinimalGenerators(d))));
Add(graphHasse,shp);
Add(graphHasse,Link(shpr,shp));
od;
canvas:=Canvas("Sons of a numerical semigroup");
SetTexTypesetting(canvas, true);
Add(canvas,graphHasse);
return Draw(canvas);
end;
Out[5]:
In [6]:
sons(NumericalSemigroup(3,5,7));
Out[6]:
In [7]:
sonstree:=function(s,l,generators)
local gens, frb, desc, graphTreee, d, shpr, shp, canvas, sonsf, lbl;
sonsf:=function(s,n,lv)
local gens, frb, desc, d, shp;
if lv=0 then
return ;
fi;
frb:=FrobeniusNumber(s);
gens:=Filtered(generators(s), x-> x>frb);
desc:=List(gens, g->RemoveMinimalGeneratorFromNumericalSemigroup(g,s));
for d in desc do
lbl:=Concatenation("$\\{",JoinStringsWithSeparator(generators(d),","),"\\}$");
shp:=Shape(ShapeType!.CIRCLE, lbl);
SetSize(shp,5);
Add(graphTreee,shp);
SetParentShape(shp,n);
sonsf(d,shp,lv-1);
od;
if desc<>[] then
return ;
fi;
#Add(canvas, FrancyMessage(FrancyMessageType.WARNING, "This semigroup is a leaf"));
return ;
end;
frb:=FrobeniusNumber(s);
gens:=Filtered(generators(s), x-> x>frb);
desc:=List(gens, g->RemoveMinimalGeneratorFromNumericalSemigroup(g,s));
graphTreee := Graph(GraphType.TREE);
SetCollapsed(graphTreee,false);
shpr:=Shape(ShapeType!.CIRCLE, "S");
SetSize(shpr,5);
Add(shpr,FrancyMessage(String(generators(s))));
Add(graphTreee,shpr);
canvas:=Canvas("Sons of a numerical semigroup");
SetTexTypesetting(canvas, true);
Add(canvas,graphTreee);
sonsf(s,shpr,l);
return Draw(canvas);
end;
Out[7]:
Darker dots correspond either to leaves or to elements with highest genus. Blue nodes can be collapsed by clicking.
In [8]:
sonstree(NumericalSemigroup(1),4,MinimalGenerators);
Out[8]:
And we can get also the tree of Arf numerical semigroups
In [9]:
sonstree(NumericalSemigroup(1),8,ArfCharactersOfArfNumericalSemigroup);
Out[9]:
In [10]:
oversemigroups:=function(s)
local ov, graphHasse, canvas,c,i,r,ovs,n,hasse,lbl;
hasse:=function(rel)
local dom, out;
dom:=Flat(rel);
out:=Filtered(rel, p-> ForAny(dom, x->([p[1],x] in rel) and ([x,p[2]] in rel)));
return Difference(rel,out);
end;
ov:=OverSemigroupsNumericalSemigroup(s);
n:=Length(ov);
graphHasse := Graph(GraphType.UNDIRECTED);
#SetSimulation(graphHasse,true);
#SetDrag(graphHasse,true);
c:=Cartesian([1..n],[1..n]);
c:=Filtered(c, p-> p[2]<>p[1]);
c:=Filtered(c, p-> IsSubset(ov[p[1]],ov[p[2]]));
c:=hasse(c);
ovs:=[];
for i in [1..n] do
lbl:=Concatenation("$\\langle",JoinStringsWithSeparator(MinimalGenerators(ov[i]),","),"\\rangle$");
if IsIrreducible(ov[i]) then
ovs[i]:=Shape(ShapeType!.DIAMOND, lbl);
else
ovs[i]:=Shape(ShapeType!.CIRCLE, lbl);
fi;
SetLayer(ovs[i],Genus(ov[i]));
SetSize(ovs[i],2);
Add(graphHasse,ovs[i]);
od;
for r in c do
Add(graphHasse,Link(ovs[r[1]],ovs[r[2]]));
od;
canvas:=Canvas("Oversemigroups");
SetTexTypesetting(canvas, true);
Add(canvas,graphHasse);
return Draw(canvas);
end;
Out[10]:
A Hasse diagram of the set of oversemigroups of the given numerical semigroup is displayed. Irreducible numerical semigroups are drawn as diamonds.
In [11]:
oversemigroups(NumericalSemigroup(6,7,9,11));
Out[11]:
The Eliahou graph of an element in a numerical semigroup is a graph whose vertices are the factorizations of the element, and to vertices are joined with an edge if they have common support.
In [12]:
DrawEliahouGraph:=function(n,s)
local graph, canvas, f, fs, c, nf, i, p;
f:=FactorizationsElementWRTNumericalSemigroup(n,s);
graph:=Graph(GraphType.UNDIRECTED);
#SetShowNeighbours(graph,true);
#SetSimulation(graph,true);
#SetDrag(graph,true);
nf:=Length(f);
fs:=[];
for i in [1..nf] do
fs[i]:=Shape(ShapeType!.CIRCLE, Concatenation("(",JoinStringsWithSeparator(f[i],","),")"));
SetLayer(fs[i],Sum(f[i]));
SetSize(fs[i],1);
Add(graph,fs[i]);
od;
c:=Cartesian([1..nf],[1..nf]);
c:=Filtered(c,p->p[1]<p[2] and f[p[1]]*f[p[2]]<>0);
for p in c do
Add(graph,Link(fs[p[1]],fs[p[2]]));
od;
canvas:=Canvas("Eliahou graph");
Add(canvas,graph);
return Draw(canvas);
end;
Out[12]:
In [13]:
s:=NumericalSemigroup(5,7,9);
Out[13]:
In [14]:
DrawEliahouGraph(49,s);
Out[14]:
In [15]:
BettiElements(s);
Out[15]:
In [16]:
DrawEliahouGraph(55,s);
Out[16]:
In [17]:
DrawRosalesGraph:=function(n,s)
local graph, canvas, msg, msgs, c, nv, i, p;
msg:=Filtered(MinimalGenerators(s), g->n-g in s);
graph:=Graph(GraphType.UNDIRECTED);
#SetSimulation(graph,true);
#SetDrag(graph,true);
nv:=Length(msg);
msgs:=[];
for i in [1..nv] do
msgs[i]:=Shape(ShapeType!.CIRCLE, String(msg[i]));
SetSize(msgs[i],1);
Add(graph,msgs[i]);
od;
c:=Cartesian([1..nv],[1..nv]);
c:=Filtered(c,p->p[1]<p[2] and n-(msg[p[1]]+msg[p[2]]) in s);
for p in c do
Add(graph,Link(msgs[p[1]],msgs[p[2]]));
od;
canvas:=Canvas("Rosales graph");
Add(canvas,graph);
return Draw(canvas);
end;
Out[17]:
In [18]:
s:=NumericalSemigroup(5,7,9);
Out[18]:
In [19]:
DrawRosalesGraph(49,s);
Out[19]:
In [20]:
DrawRosalesGraph(10,NumericalSemigroup(3,5,7));
Out[20]:
In [21]:
DrawFactorizationGraph:=function(f)
local graph, canvas, fs, c, nf, i, p, ln, distance, Kruskal, tv;
Kruskal := function(V, E)
local trees, needed, v, e, i,j, nv;
trees := List(V, v-> [v]);
needed := [];
nv:=Length(V);
for e in E do
i:=First([1..Length(trees)], k-> e[1] in trees[k]);
j:=First([1..Length(trees)], k-> e[2] in trees[k]);
if i<>j then
trees[i]:=Union(trees[i], trees[j]);
trees[j]:=[];
Add(needed,e);
fi;
if Length(needed)=nv-1 then
break;
fi;
od;
return needed;
end;
distance := function(a,b)
local k, gcd, i;
k := Length(a);
if k <> Length(b) then
Error("The lengths of a and b are different.\n");
fi;
gcd := [];
for i in [1..k] do
Add(gcd, Minimum(a[i],b[i]));
od;
return(Maximum(Sum(a-gcd),Sum(b-gcd)));
end;
graph:=Graph(GraphType.UNDIRECTED);
# SetSimulation(graph,true);
#SetDrag(graph,true);
#SetShowNeighbours(graph,true);
nf:=Length(f);
fs:=[];
for i in [1..nf] do
fs[i]:=Shape(ShapeType!.CIRCLE, Concatenation("(",JoinStringsWithSeparator(f[i],","),")"));
SetLayer(fs[i],Sum(f[i]));
SetSize(fs[i],1);
Add(graph,fs[i]);
od;
c:=Cartesian([1..nf],[1..nf]);
c:=Filtered(c,p->p[1]<p[2] and f[p[1]]*f[p[2]]<>0);
Sort(c,function(e,ee) return distance(f[e[1]],f[e[2]])<distance(f[ee[1]],f[ee[2]]); end);
tv:=Kruskal(f,List(c,p->[f[p[1]],f[p[2]]]));
for p in c do
ln:=Link(fs[p[1]],fs[p[2]]);
#SetWeight(ln, distance(f[p[1]],f[p[2]]));
SetTitle(ln, String(distance(f[p[1]],f[p[2]])));
if [f[p[1]],f[p[2]]] in tv then
SetColor(ln,"red");
fi;
Add(graph,ln);
od;
canvas:=Canvas("Factorizations graph");
Add(canvas,graph);
return Draw(canvas);
end;
Out[21]:
In [22]:
f:=FactorizationsElementWRTNumericalSemigroup(40,NumericalSemigroup(3,5,7));
Out[22]:
In [ ]: