ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 21 Mar 2021 08:54:14 +0100Obtaining incidence algebras for GAP via Sagehttps://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/Gap (via its package QPA) can obtain the incidence algebras of a given
connected poset `P` as a quiver algebra `KQ/I` (note that any
incidence algebra is isomorphic to the quiver algebra where `Q`
is the Hasse quiver and the relations I are generated by all
commutativity relations `w1-w2` where the paths `w1` and `w2`
start and end at the same points).
However, sadly GAP is very slow with this and obtaining the quiver algebra
for a poset with 40 or more points can take days or even weeks.
I wonder whether there is a way to use Sage to obtain
two lists of quiver and relations from a given poset
and then use those lists to input them in GAP to directly obtain
the quiver algebra in GAP (so that GAP has to do no computations
for the relations, which seems to be the main problem
although I'm not really sure why it takes so long).
Solving this problem would be very important to deal with
large posets in GAP (and one really needs the incidence algebra
as a quiver algebra in QPA to do homological algebra with it
as Sage has no such functions).
Here is an example, namely the strong Bruhat order of the
symmetric group $S_3$ with quiver and relations.
First here it is in Sage:
Y = posets.SymmetricGroupBruhatOrderPoset(3)
display(Y)
Now quiver and relations for GAP should look as follows:
Quiver(
["x123", "x132", "x213", "x231", "x312", "x321"],
[["x123", "x132", "x123_x132"],
["x123", "x213", "x123_x213"],
["x132", "x231", "x132_x231"],
["x132", "x312", "x132_x312"],
["x213", "x231", "x213_x231"],
["x213", "x312", "x213_x312"],
["x231", "x321", "x231_x321"],
["x312", "x321", "x312_x321"]])
[ x123_x132*x132_x231-x123_x213*x213_x231,
x123_x132*x132_x312-x123_x213*x213_x312,
x132_x231*x231_x321-x132_x312*x312_x321,
x213_x231*x231_x321-x213_x312*x312_x321 ]
Here the first entry is the quiver specified by the points
["x123", "x132", "x213", "x231", "x312", "x321"]
and by the arrows
[["x123", "x132", "x123_x132"],
["x123", "x213", "x123_x213"],
["x132", "x231", "x132_x231"],
["x132", "x312", "x132_x312"],
["x213", "x231", "x213_x231"],
["x213", "x312", "x213_x312"],
["x231", "x321", "x231_x321"],
["x312", "x321", "x312_x321"]]
that specify the Hasse diagram of the poset. Here we see that
a point is called for example `x132` , so we put an `x` before each
name of the point (here the point is named `132` in Sage).
An arrow is named for example `x132_x312` and the list entry
`["x132","x312","x132_x312"]` specifies that the arrow `x132_x312`
starts at the point `x132` and ends at the point `x312`.
The relations are then of the form for example `x123_x132*x132_x231-x123_x213*x213_x231`.
Note that we do not need really all relations of the form `w1-w2` in general
as some of those relations might be implied by some other.
So to make things faster it might be a good idea to find "minimal" relations,
but I am not quite sure how to do that.
As a test, it would be interesting if one can make things fast enough
to obtain for example the strong Bruhat order of $S_5$ (which has 120 points)
as a quiver algebra in GAP within 2 or 3 hours.
At the moment this takes more than a month with GAP.Thu, 18 Mar 2021 18:43:09 +0100https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/Answer by Max Alekseyev for <p>Gap (via its package QPA) can obtain the incidence algebras of a given
connected poset <code>P</code> as a quiver algebra <code>KQ/I</code> (note that any
incidence algebra is isomorphic to the quiver algebra where <code>Q</code>
is the Hasse quiver and the relations I are generated by all
commutativity relations <code>w1-w2</code> where the paths <code>w1</code> and <code>w2</code>
start and end at the same points).</p>
<p>However, sadly GAP is very slow with this and obtaining the quiver algebra
for a poset with 40 or more points can take days or even weeks.</p>
<p>I wonder whether there is a way to use Sage to obtain
two lists of quiver and relations from a given poset
and then use those lists to input them in GAP to directly obtain
the quiver algebra in GAP (so that GAP has to do no computations
for the relations, which seems to be the main problem
although I'm not really sure why it takes so long).</p>
<p>Solving this problem would be very important to deal with
large posets in GAP (and one really needs the incidence algebra
as a quiver algebra in QPA to do homological algebra with it
as Sage has no such functions).</p>
<p>Here is an example, namely the strong Bruhat order of the
symmetric group $S_3$ with quiver and relations.</p>
<p>First here it is in Sage:</p>
<pre><code>Y = posets.SymmetricGroupBruhatOrderPoset(3)
display(Y)
</code></pre>
<p>Now quiver and relations for GAP should look as follows:</p>
<pre><code>Quiver(
["x123", "x132", "x213", "x231", "x312", "x321"],
[["x123", "x132", "x123_x132"],
["x123", "x213", "x123_x213"],
["x132", "x231", "x132_x231"],
["x132", "x312", "x132_x312"],
["x213", "x231", "x213_x231"],
["x213", "x312", "x213_x312"],
["x231", "x321", "x231_x321"],
["x312", "x321", "x312_x321"]])
[ x123_x132*x132_x231-x123_x213*x213_x231,
x123_x132*x132_x312-x123_x213*x213_x312,
x132_x231*x231_x321-x132_x312*x312_x321,
x213_x231*x231_x321-x213_x312*x312_x321 ]
</code></pre>
<p>Here the first entry is the quiver specified by the points</p>
<pre><code>["x123", "x132", "x213", "x231", "x312", "x321"]
</code></pre>
<p>and by the arrows </p>
<pre><code>[["x123", "x132", "x123_x132"],
["x123", "x213", "x123_x213"],
["x132", "x231", "x132_x231"],
["x132", "x312", "x132_x312"],
["x213", "x231", "x213_x231"],
["x213", "x312", "x213_x312"],
["x231", "x321", "x231_x321"],
["x312", "x321", "x312_x321"]]
</code></pre>
<p>that specify the Hasse diagram of the poset. Here we see that
a point is called for example <code>x132</code> , so we put an <code>x</code> before each
name of the point (here the point is named <code>132</code> in Sage).</p>
<p>An arrow is named for example <code>x132_x312</code> and the list entry
<code>["x132","x312","x132_x312"]</code> specifies that the arrow <code>x132_x312</code>
starts at the point <code>x132</code> and ends at the point <code>x312</code>.</p>
<p>The relations are then of the form for example <code>x123_x132*x132_x231-x123_x213*x213_x231</code>.</p>
<p>Note that we do not need really all relations of the form <code>w1-w2</code> in general
as some of those relations might be implied by some other.</p>
<p>So to make things faster it might be a good idea to find "minimal" relations,
but I am not quite sure how to do that.</p>
<p>As a test, it would be interesting if one can make things fast enough
to obtain for example the strong Bruhat order of $S_5$ (which has 120 points)
as a quiver algebra in GAP within 2 or 3 hours.
At the moment this takes more than a month with GAP.</p>
https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?answer=56241#post-id-56241If I got the problem correctly, the following code constructs the relations (excluding some redundant ones):
import json
def xlabel(e):
return 'x%s_x%s' % e
Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',json.dumps(['x'+str(v) for v in H.vertices()]))
print('arrows:',json.dumps([['x'+str(e[0]),'x'+str(e[1]),xlabel(e)] for e in H.edges(labels=False)]))
R = PolynomialRing(QQ,[xlabel(e) for e in H.edges(labels=False)])
rels = []
for u in H.vertices():
for v in set().union(*[set(H.neighbors_out(w)) for w in H.neighbors_out(u)]):
P = list(set(H.neighbors_out(u)) & set(H.neighbors_in(v)))
rels += [R( xlabel((u,P[i]))+'*'+xlabel((P[i],v))+'-'+xlabel((u,P[i+1]))+'*'+xlabel((P[i+1],v)) ) for i in range(len(P)-1)]
print('# rels:',len(rels))
To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).
J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)Fri, 19 Mar 2021 02:47:08 +0100https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?answer=56241#post-id-56241Comment by FrédéricC for <p>If I got the problem correctly, the following code constructs the relations (excluding some redundant ones):</p>
<pre><code>import json
def xlabel(e):
return 'x%s_x%s' % e
Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',json.dumps(['x'+str(v) for v in H.vertices()]))
print('arrows:',json.dumps([['x'+str(e[0]),'x'+str(e[1]),xlabel(e)] for e in H.edges(labels=False)]))
R = PolynomialRing(QQ,[xlabel(e) for e in H.edges(labels=False)])
rels = []
for u in H.vertices():
for v in set().union(*[set(H.neighbors_out(w)) for w in H.neighbors_out(u)]):
P = list(set(H.neighbors_out(u)) & set(H.neighbors_in(v)))
rels += [R( xlabel((u,P[i]))+'*'+xlabel((P[i],v))+'-'+xlabel((u,P[i+1]))+'*'+xlabel((P[i+1],v)) ) for i in range(len(P)-1)]
print('# rels:',len(rels))
</code></pre>
<p>To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).</p>
<pre><code>J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)
</code></pre>
https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56294#post-id-56294See also https://ask.sagemath.org/question/38895/incidence-algebras-in-qpa-via-sage/Sun, 21 Mar 2021 08:54:14 +0100https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56294#post-id-56294Comment by Max Alekseyev for <p>If I got the problem correctly, the following code constructs the relations (excluding some redundant ones):</p>
<pre><code>import json
def xlabel(e):
return 'x%s_x%s' % e
Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',json.dumps(['x'+str(v) for v in H.vertices()]))
print('arrows:',json.dumps([['x'+str(e[0]),'x'+str(e[1]),xlabel(e)] for e in H.edges(labels=False)]))
R = PolynomialRing(QQ,[xlabel(e) for e in H.edges(labels=False)])
rels = []
for u in H.vertices():
for v in set().union(*[set(H.neighbors_out(w)) for w in H.neighbors_out(u)]):
P = list(set(H.neighbors_out(u)) & set(H.neighbors_in(v)))
rels += [R( xlabel((u,P[i]))+'*'+xlabel((P[i],v))+'-'+xlabel((u,P[i+1]))+'*'+xlabel((P[i+1],v)) ) for i in range(len(P)-1)]
print('# rels:',len(rels))
</code></pre>
<p>To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).</p>
<pre><code>J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)
</code></pre>
https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56269#post-id-56269I realized that for dealing with paths of length 2 only, `path_semigroup()` was an overkill. So, I've redesigned the code and simplified it. Hopefully, it is now more error-proof and works fine for all posets. Please check it out.Fri, 19 Mar 2021 19:20:06 +0100https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56269#post-id-56269Comment by FrédéricC for <p>If I got the problem correctly, the following code constructs the relations (excluding some redundant ones):</p>
<pre><code>import json
def xlabel(e):
return 'x%s_x%s' % e
Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',json.dumps(['x'+str(v) for v in H.vertices()]))
print('arrows:',json.dumps([['x'+str(e[0]),'x'+str(e[1]),xlabel(e)] for e in H.edges(labels=False)]))
R = PolynomialRing(QQ,[xlabel(e) for e in H.edges(labels=False)])
rels = []
for u in H.vertices():
for v in set().union(*[set(H.neighbors_out(w)) for w in H.neighbors_out(u)]):
P = list(set(H.neighbors_out(u)) & set(H.neighbors_in(v)))
rels += [R( xlabel((u,P[i]))+'*'+xlabel((P[i],v))+'-'+xlabel((u,P[i+1]))+'*'+xlabel((P[i+1],v)) ) for i in range(len(P)-1)]
print('# rels:',len(rels))
</code></pre>
<p>To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).</p>
<pre><code>J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)
</code></pre>
https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56270#post-id-56270For the weak order and all similar polytopal posets, the relations are given by 2-dim faces of the permutohedra, see https://oeis.org/A019538 for their number in type A.Fri, 19 Mar 2021 19:27:57 +0100https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56270#post-id-56270Comment by klaaa for <p>If I got the problem correctly, the following code constructs the relations (excluding some redundant ones):</p>
<pre><code>import json
def xlabel(e):
return 'x%s_x%s' % e
Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',json.dumps(['x'+str(v) for v in H.vertices()]))
print('arrows:',json.dumps([['x'+str(e[0]),'x'+str(e[1]),xlabel(e)] for e in H.edges(labels=False)]))
R = PolynomialRing(QQ,[xlabel(e) for e in H.edges(labels=False)])
rels = []
for u in H.vertices():
for v in set().union(*[set(H.neighbors_out(w)) for w in H.neighbors_out(u)]):
P = list(set(H.neighbors_out(u)) & set(H.neighbors_in(v)))
rels += [R( xlabel((u,P[i]))+'*'+xlabel((P[i],v))+'-'+xlabel((u,P[i+1]))+'*'+xlabel((P[i+1],v)) ) for i in range(len(P)-1)]
print('# rels:',len(rels))
</code></pre>
<p>To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).</p>
<pre><code>J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)
</code></pre>
https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56268#post-id-56268Thank you very much again! In the example for `W = WeylGroup("B3", prefix="s") P = W.bruhat_poset() Y = P.relabel()` it gives the vertices and arrows but for the relations one obtains the error : `KeyError Traceback (most recent call last)
<ipython-input-1-0d08432e40fd> in <module>
23 rels = []
24 for u,v in Y.relations_iterator(strict=True):
---> 25 P = [p for p in S.all_paths(X2I[u],X2I[v]) if len(p)==Integer(2)]
26 rels += [R( f'{P[i]} - {P[i+1]}' ) for i in range(len(P)-Integer(1))]
27
KeyError: 0`Fri, 19 Mar 2021 18:51:37 +0100https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56268#post-id-56268Comment by Max Alekseyev for <p>If I got the problem correctly, the following code constructs the relations (excluding some redundant ones):</p>
<pre><code>import json
def xlabel(e):
return 'x%s_x%s' % e
Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',json.dumps(['x'+str(v) for v in H.vertices()]))
print('arrows:',json.dumps([['x'+str(e[0]),'x'+str(e[1]),xlabel(e)] for e in H.edges(labels=False)]))
R = PolynomialRing(QQ,[xlabel(e) for e in H.edges(labels=False)])
rels = []
for u in H.vertices():
for v in set().union(*[set(H.neighbors_out(w)) for w in H.neighbors_out(u)]):
P = list(set(H.neighbors_out(u)) & set(H.neighbors_in(v)))
rels += [R( xlabel((u,P[i]))+'*'+xlabel((P[i],v))+'-'+xlabel((u,P[i+1]))+'*'+xlabel((P[i+1],v)) ) for i in range(len(P)-1)]
print('# rels:',len(rels))
</code></pre>
<p>To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).</p>
<pre><code>J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)
</code></pre>
https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56267#post-id-56267It's a matter of vertex labels types in `H`. For $S_5$ they were strings, in your last poset they are not. The issue is fixed by wrapping vertex labels with `str()` while prepending them with `x` - see updated code.Fri, 19 Mar 2021 18:31:51 +0100https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56267#post-id-56267Comment by klaaa for <p>If I got the problem correctly, the following code constructs the relations (excluding some redundant ones):</p>
<pre><code>import json
def xlabel(e):
return 'x%s_x%s' % e
Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',json.dumps(['x'+str(v) for v in H.vertices()]))
print('arrows:',json.dumps([['x'+str(e[0]),'x'+str(e[1]),xlabel(e)] for e in H.edges(labels=False)]))
R = PolynomialRing(QQ,[xlabel(e) for e in H.edges(labels=False)])
rels = []
for u in H.vertices():
for v in set().union(*[set(H.neighbors_out(w)) for w in H.neighbors_out(u)]):
P = list(set(H.neighbors_out(u)) & set(H.neighbors_in(v)))
rels += [R( xlabel((u,P[i]))+'*'+xlabel((P[i],v))+'-'+xlabel((u,P[i+1]))+'*'+xlabel((P[i+1],v)) ) for i in range(len(P)-1)]
print('# rels:',len(rels))
</code></pre>
<p>To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).</p>
<pre><code>J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)
</code></pre>
https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56265#post-id-56265Another question: Does your program also work for other posets besides the symmetric group where the vertices of the elements are labeled by natural numbers (or some other combinations of number to display for examples signed permutations)? For example for the poset `W = WeylGroup("B3", prefix="s")
P = W.bruhat_poset()
Y = P.relabel()` I obtain the error `can only concatenate str (not "FinitePoset_with_category.element_class") to str` when I try to apply your program to Y.Fri, 19 Mar 2021 18:07:44 +0100https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56265#post-id-56265Comment by klaaa for <p>If I got the problem correctly, the following code constructs the relations (excluding some redundant ones):</p>
<pre><code>import json
def xlabel(e):
return 'x%s_x%s' % e
Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',json.dumps(['x'+str(v) for v in H.vertices()]))
print('arrows:',json.dumps([['x'+str(e[0]),'x'+str(e[1]),xlabel(e)] for e in H.edges(labels=False)]))
R = PolynomialRing(QQ,[xlabel(e) for e in H.edges(labels=False)])
rels = []
for u in H.vertices():
for v in set().union(*[set(H.neighbors_out(w)) for w in H.neighbors_out(u)]):
P = list(set(H.neighbors_out(u)) & set(H.neighbors_in(v)))
rels += [R( xlabel((u,P[i]))+'*'+xlabel((P[i],v))+'-'+xlabel((u,P[i+1]))+'*'+xlabel((P[i+1],v)) ) for i in range(len(P)-1)]
print('# rels:',len(rels))
</code></pre>
<p>To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).</p>
<pre><code>J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)
</code></pre>
https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56264#post-id-56264I cant thank you enough. The number of relations for S4 got reduced from over 1000 to just 63. I think there is good hope now that S5 might also finish and GAP can obtain the quiver algebra in a reasonable time. I will update you when the program finishes (together with GAP).Fri, 19 Mar 2021 17:53:50 +0100https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56264#post-id-56264Comment by Max Alekseyev for <p>If I got the problem correctly, the following code constructs the relations (excluding some redundant ones):</p>
<pre><code>import json
def xlabel(e):
return 'x%s_x%s' % e
Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',json.dumps(['x'+str(v) for v in H.vertices()]))
print('arrows:',json.dumps([['x'+str(e[0]),'x'+str(e[1]),xlabel(e)] for e in H.edges(labels=False)]))
R = PolynomialRing(QQ,[xlabel(e) for e in H.edges(labels=False)])
rels = []
for u in H.vertices():
for v in set().union(*[set(H.neighbors_out(w)) for w in H.neighbors_out(u)]):
P = list(set(H.neighbors_out(u)) & set(H.neighbors_in(v)))
rels += [R( xlabel((u,P[i]))+'*'+xlabel((P[i],v))+'-'+xlabel((u,P[i+1]))+'*'+xlabel((P[i+1],v)) ) for i in range(len(P)-1)]
print('# rels:',len(rels))
</code></pre>
<p>To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).</p>
<pre><code>J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)
</code></pre>
https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56263#post-id-56263I've corrected both issues. Check it out. Given a reduced set of relations, it's worth to restart computation for $S_5$.Fri, 19 Mar 2021 17:48:21 +0100https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56263#post-id-56263Comment by klaaa for <p>If I got the problem correctly, the following code constructs the relations (excluding some redundant ones):</p>
<pre><code>import json
def xlabel(e):
return 'x%s_x%s' % e
Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',json.dumps(['x'+str(v) for v in H.vertices()]))
print('arrows:',json.dumps([['x'+str(e[0]),'x'+str(e[1]),xlabel(e)] for e in H.edges(labels=False)]))
R = PolynomialRing(QQ,[xlabel(e) for e in H.edges(labels=False)])
rels = []
for u in H.vertices():
for v in set().union(*[set(H.neighbors_out(w)) for w in H.neighbors_out(u)]):
P = list(set(H.neighbors_out(u)) & set(H.neighbors_in(v)))
rels += [R( xlabel((u,P[i]))+'*'+xlabel((P[i],v))+'-'+xlabel((u,P[i+1]))+'*'+xlabel((P[i+1],v)) ) for i in range(len(P)-1)]
print('# rels:',len(rels))
</code></pre>
<p>To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).</p>
<pre><code>J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)
</code></pre>
https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56258#post-id-56258I noted that your programm generates relations like `x123_x132*x132_x231*x231_x321 - x123_x132*x132_x312*x312_x321,
-x123_x213*x213_x231*x231_x321 + x123_x132*x132_x312*x312_x321,` for S3. But actually the incidence algebra of Sn for general n should be a quadratic algebra, so any relation is of the form a*b-c*d where a,b,c and d are arrows. Im not sure whether there is an easy way to only add relations of the form a*b-c*d so that one omits relations that have terms that are a product of 3 or more arrows or relations that are a sum of 3 or more terms.Fri, 19 Mar 2021 17:16:06 +0100https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56258#post-id-56258Comment by klaaa for <p>If I got the problem correctly, the following code constructs the relations (excluding some redundant ones):</p>
<pre><code>import json
def xlabel(e):
return 'x%s_x%s' % e
Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',json.dumps(['x'+str(v) for v in H.vertices()]))
print('arrows:',json.dumps([['x'+str(e[0]),'x'+str(e[1]),xlabel(e)] for e in H.edges(labels=False)]))
R = PolynomialRing(QQ,[xlabel(e) for e in H.edges(labels=False)])
rels = []
for u in H.vertices():
for v in set().union(*[set(H.neighbors_out(w)) for w in H.neighbors_out(u)]):
P = list(set(H.neighbors_out(u)) & set(H.neighbors_in(v)))
rels += [R( xlabel((u,P[i]))+'*'+xlabel((P[i],v))+'-'+xlabel((u,P[i+1]))+'*'+xlabel((P[i+1],v)) ) for i in range(len(P)-1)]
print('# rels:',len(rels))
</code></pre>
<p>To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).</p>
<pre><code>J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)
</code></pre>
https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56257#post-id-56257Thanks again. The output for the arrows is now `["x123_x132", "x123_x213", "x132_x231", "x132_x312", "x213_x231", "x213_x312", "x231_x321", "x312_x321"]` instead of `[["x123", "x132", "x123_x132"], ["x123", "x213", "x123_x213"], ["x132", "x231", "x132_x231"], ["x132", "x312", "x132_x312"], ["x213", "x231", "x213_x231"], ["x213", "x312", "x213_x312"], ["x231", "x321", "x231_x321"], ["x312", "x321", "x312_x321"]]` , which is needed for GAP to understand where the arrows start and end. Is there an easy fix ? Sorry, but I was not able to directly manipulate your code myself yet so that this is possible. By the way, S_5 still calculates. Since the relations for S3 are 7 and for S4 the number is 1067, I fear that S5 might still be too big for a computer to handle(maybe it has~1000000 relations?)Fri, 19 Mar 2021 17:14:08 +0100https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56257#post-id-56257Comment by Max Alekseyev for <p>If I got the problem correctly, the following code constructs the relations (excluding some redundant ones):</p>
<pre><code>import json
def xlabel(e):
return 'x%s_x%s' % e
Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',json.dumps(['x'+str(v) for v in H.vertices()]))
print('arrows:',json.dumps([['x'+str(e[0]),'x'+str(e[1]),xlabel(e)] for e in H.edges(labels=False)]))
R = PolynomialRing(QQ,[xlabel(e) for e in H.edges(labels=False)])
rels = []
for u in H.vertices():
for v in set().union(*[set(H.neighbors_out(w)) for w in H.neighbors_out(u)]):
P = list(set(H.neighbors_out(u)) & set(H.neighbors_in(v)))
rels += [R( xlabel((u,P[i]))+'*'+xlabel((P[i],v))+'-'+xlabel((u,P[i+1]))+'*'+xlabel((P[i+1],v)) ) for i in range(len(P)-1)]
print('# rels:',len(rels))
</code></pre>
<p>To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).</p>
<pre><code>J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)
</code></pre>
https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56253#post-id-56253The easiest solution is to use `json.dumps()` wrapper - see updated code.Fri, 19 Mar 2021 16:04:45 +0100https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56253#post-id-56253Comment by klaaa for <p>If I got the problem correctly, the following code constructs the relations (excluding some redundant ones):</p>
<pre><code>import json
def xlabel(e):
return 'x%s_x%s' % e
Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',json.dumps(['x'+str(v) for v in H.vertices()]))
print('arrows:',json.dumps([['x'+str(e[0]),'x'+str(e[1]),xlabel(e)] for e in H.edges(labels=False)]))
R = PolynomialRing(QQ,[xlabel(e) for e in H.edges(labels=False)])
rels = []
for u in H.vertices():
for v in set().union(*[set(H.neighbors_out(w)) for w in H.neighbors_out(u)]):
P = list(set(H.neighbors_out(u)) & set(H.neighbors_in(v)))
rels += [R( xlabel((u,P[i]))+'*'+xlabel((P[i],v))+'-'+xlabel((u,P[i+1]))+'*'+xlabel((P[i+1],v)) ) for i in range(len(P)-1)]
print('# rels:',len(rels))
</code></pre>
<p>To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).</p>
<pre><code>J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)
</code></pre>
https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56252#post-id-56252Thank you very much again. The output now for the vertices looks like `['x123', 'x132', 'x213', 'x231', 'x312', 'x321']` but GAP only understands it when it has the form `["x123", "x132", "x213", "x231", "x312", "x321"]` , so that one has " instead of '. I tried to modify your code by using print("vertices:",["x"+v for v in H.vertices()]) instead, but it still doesnt show the symbol " and uses the symbol ' instead. Is there an easy fix to that? Sorry, Im not so experienced with Sage.Fri, 19 Mar 2021 15:51:00 +0100https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56252#post-id-56252Comment by Max Alekseyev for <p>If I got the problem correctly, the following code constructs the relations (excluding some redundant ones):</p>
<pre><code>import json
def xlabel(e):
return 'x%s_x%s' % e
Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',json.dumps(['x'+str(v) for v in H.vertices()]))
print('arrows:',json.dumps([['x'+str(e[0]),'x'+str(e[1]),xlabel(e)] for e in H.edges(labels=False)]))
R = PolynomialRing(QQ,[xlabel(e) for e in H.edges(labels=False)])
rels = []
for u in H.vertices():
for v in set().union(*[set(H.neighbors_out(w)) for w in H.neighbors_out(u)]):
P = list(set(H.neighbors_out(u)) & set(H.neighbors_in(v)))
rels += [R( xlabel((u,P[i]))+'*'+xlabel((P[i],v))+'-'+xlabel((u,P[i+1]))+'*'+xlabel((P[i+1],v)) ) for i in range(len(P)-1)]
print('# rels:',len(rels))
</code></pre>
<p>To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).</p>
<pre><code>J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)
</code></pre>
https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56251#post-id-56251I've slightly updated the code and added printing of vertices and arrows. Let me know if you have any questions.Fri, 19 Mar 2021 15:08:01 +0100https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56251#post-id-56251Comment by klaaa for <p>If I got the problem correctly, the following code constructs the relations (excluding some redundant ones):</p>
<pre><code>import json
def xlabel(e):
return 'x%s_x%s' % e
Y = posets.SymmetricGroupBruhatOrderPoset(3)
H = Y.hasse_diagram()
print('vertices:',json.dumps(['x'+str(v) for v in H.vertices()]))
print('arrows:',json.dumps([['x'+str(e[0]),'x'+str(e[1]),xlabel(e)] for e in H.edges(labels=False)]))
R = PolynomialRing(QQ,[xlabel(e) for e in H.edges(labels=False)])
rels = []
for u in H.vertices():
for v in set().union(*[set(H.neighbors_out(w)) for w in H.neighbors_out(u)]):
P = list(set(H.neighbors_out(u)) & set(H.neighbors_in(v)))
rels += [R( xlabel((u,P[i]))+'*'+xlabel((P[i],v))+'-'+xlabel((u,P[i+1]))+'*'+xlabel((P[i+1],v)) ) for i in range(len(P)-1)]
print('# rels:',len(rels))
</code></pre>
<p>To get a minimal set of relations, we can define the ideal generated by these relations and compute its Groebner basis (although this may be quite computationally expensive).</p>
<pre><code>J = R.ideal(rels)
B = J.groebner_basis()
print("basis:",B)
</code></pre>
https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56247#post-id-56247Thank you very much for this great answer! I tested it for S_3 and it works fine and gives the correct algebra for GAP. I calculate S_5 at the moment but it seems it takes longer, so I will wait some hours. By the way, is there an easy method using your code to obtain the two lists of vertices and arrows in the form `["x123", "x132", "x213", "x231", "x312", "x321"]` (those are the vertices) and `[["x123", "x132", "x123_x132"],
["x123", "x213", "x123_x213"],
["x132", "x231", "x132_x231"],
["x132", "x312", "x132_x312"],
["x213", "x231", "x213_x231"],
["x213", "x312", "x213_x312"],
["x231", "x321", "x231_x321"],
["x312", "x321", "x312_x321"]]` (those are the arrows) so that GAP directly understands the quiver?Fri, 19 Mar 2021 10:42:11 +0100https://ask.sagemath.org/question/56230/obtaining-incidence-algebras-for-gap-via-sage/?comment=56247#post-id-56247