Ask Your Question

Obtaining incidence algebras for GAP via Sage

asked 2021-03-18 18:43:09 +0200

klaaa gravatar image

updated 2021-03-18 22:10:44 +0200

slelievre gravatar image

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)

Now quiver and relations for GAP should look as follows:

    ["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, 
  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.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2021-03-19 02:47:08 +0200

Max Alekseyev gravatar image

updated 2021-03-19 19:54:57 +0200

If 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()
edit flag offensive delete link more


Thank 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?

klaaa gravatar imageklaaa ( 2021-03-19 10:42:11 +0200 )edit

I've slightly updated the code and added printing of vertices and arrows. Let me know if you have any questions.

Max Alekseyev gravatar imageMax Alekseyev ( 2021-03-19 15:08:01 +0200 )edit

Thank 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.

klaaa gravatar imageklaaa ( 2021-03-19 15:51:00 +0200 )edit

The easiest solution is to use json.dumps() wrapper - see updated code.

Max Alekseyev gravatar imageMax Alekseyev ( 2021-03-19 16:04:45 +0200 )edit

Thanks 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?)

klaaa gravatar imageklaaa ( 2021-03-19 17:14:08 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2021-03-18 18:43:09 +0200

Seen: 97 times

Last updated: Mar 19