Obtaining incidence algebras for GAP via Sage

edit

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.