Groebner bases for supercommutative polynomial algebras.

[Reimundo Heluani]

Is there an implementation of such a thing as in the title?

I am facing the following design problem, and I'd love to get some pointers. I
have a category of parents that are infinite dimensional super algebras but are
graded with finite dimensional graded pieces. For the sake of clarity think of
a polynomial differential algebra that is QQ[x_1,x_2,x_3,...,y_1,y_2,y_3,....]
where the variables x_i and y_i have degree i. I can work with ideals and
quotients of these guys by computing the quotient degree by degree.

Now the issue is to compute the graded dimension of the quotient as a formal
power series. The way I am implementing this is by computing a basis of the
degree part n of the algebra and then the degree part n of the ideal.

In the particular case of the polynomial algebra above, I have another
implementation: if I only care about the hilbert series up to degree n, then I
work in the quotient by (x_j, y_j) for j>n, this gives me a finite type
polynomial algebra and I can ask for a grobner basis of the ideal before
computing the hilbert series. This is several orders of magnitude faster.

Now my question: in my setup I need some of the x's or y's to be odd,
anticommutative variables. And even worse their weights might be rational
numbers and not only integers. Buchberger's algorithm works with minimal
variations in the super-commutative case. If I disregard the issue of rational
degrees, is there an implementation of these "grobner bases" for super
commutative algebras in Sage?

Best,

R.

[Simon King]

Hi Reimundo,

On 2020-06-17, 'Reimundo Heluani' via sage-support <sage-s...@googlegroups.com> wrote:
> Is there an implementation of such a thing as in the title?

TL;DR: Yes. Singular does have these capabilities. I recall that these
were comfortably wrapped in SageMath, but as it turns out: They aren't.

Note to developers: I think we should have at least two trac tickets
related with Reimundo's question, and we should have these tickets opened
10 years ago already!!!

1. If A is a super-commutative algebra (which exists in Sage), then
singular(A) should create a copy of A in the Singular pexpect
interface, but this is broken.
2. Apparently, for ideals over A, Sage is using a generic implementation
that doesn't know about Gröbner bases. It should of course use an
implementation based on libsingular.

Longer answer:

I suppose "supercommutative" means that you have something
that resembles a polynomial ring, with the difference that some of the
generators anti-commute among each other, whereas some generators
commute with all generators.

> I am facing the following design problem, and I'd love to get some pointers.

Can one not find it by searching in the SageMath documentation? Anyway,
I suppose it is explained in the docs how to create a SCA
(SuperCommutativeAlgebra) with grading, create ideals
over such algebras, and compute Gröbner bases.

This is how one could search during a SageMath session:

sage: search_src('supercommutative')
However, the answers to that search have not really been helpful. So,
perhaps the search in the documentation wasn't successful either. It
points to a lot of places in "sage.categories", but not where I recall
the actual implementation.

Fortunately I recall that supercommutative algebra is abbreviated as
sca. Hence, the following search succeeded:

sage: search_def('sca', whole_word=True)
It tells you that you find it (of course with documentation and
examples) in sage.rings.polynomial.plural

> Now the issue is to compute the graded dimension of the quotient as a formal
> power series.

You talk about Hilbert-Poincaré series? That's already implemented in
SageMath

Actually I need Hilbert-Poincaré series for my computation of modular
cohomology rings of finite groups; these rings are graded-commutative
(for odd prime characteristic at least) and can thus be implemented as
supercommutative algebras.

Here is a non-trivial example from my cohomology computations
(translated to boilerplate singular):

sage: names = '(x1a,x1b,x3a,x3b,y2a,y2b,y2c,y2d,y6)'
sage: Igens = ['x1a*x1b',
'y2b*x1a-y2a*x1b',
'y2c*x1a-y2b*x1b-y2a*x1b',
'y2c*x1b-y2b*x1b-y2a*x1b',
'y2d*x1a-y2b*x1b+y2a*x1b',
'-y2b^2+y2a*y2c-y2a*y2b',
'y2b*y2c-y2b^2-y2a*y2b',
'y2c^2+y2b^2+y2a*y2b',
'y2b^2-y2a*y2d-y2a*y2b+x1a*x3a',
'-y2b*y2d-y2b^2+y2a*y2b+x1b*x3a',
'-y2b*y2d-y2a*y2d+x1a*x3b',
'-y2c*y2d+x1b*x3b',
'y2d*x3a-y2d^2*x1b-y2c*x3a-y2b*x3a+y2a*y2b*x1b-y2a^2*x1b',
'-y2b*x3a+y2a*x3b-y2a*x3a-y2a*y2b*x1b',
'-y2c*x3a+y2b*x3b-y2a^2*x1b',
'y2c*x3b+y2c*x3a-y2a*y2b*x1b-y2a^2*x1b',
'x3a*x3b-y2d*x1b*x3b+y2a*x1b*x3b-y2a*x1a*x3b+y2a*x1a*x3a']

Create the super commutative algebra:

sage: R = singular.ring(3,names,'wp(1,1,3,3,2,2,2,2,6)')
sage: A = singular.superCommutative(4,9)
sage: A.set_ring()

Create an ideal and compute its Hilbert series (note that the quotient
of A by this ideal is isomorphic to the cohomology ring of the Sylow
3-subgroup of U_3(8) with coefficients in GF(3)):

sage: I = singular.ideal(Igens)
sage: from sage.rings.polynomial.hilbert import hilbert_poincare_series
sage: HP = hilbert_poincare_series(I.twostd().lead(), (1,1,3,3,2,2,2,2,6))

Now we can read off the number of standard monomials in each (weighted)
degree. Unfortunately, Singular doesn't have a function to return
standard monomials in WEIGHTED degree. Hence, just as a proof of
concept, I collect the standard monomials in unweighted degree up to 8,
then filter and count by weighted degree.

sage: SM = []
sage: for d in range(1,9):
....: SM.extend(list(I.twostd().kbase(d)))
....:
sage: for d in range(1,9):
....: print(d,len([m for m in SM if m.deg()==d]))
....:
1 2
2 6
3 8
4 7
5 8
6 6
7 6
8 11

And this coincides with what the Hilbert series predicts:

sage: HP
(t^14 + t^13 + 3*t^12 - 3*t^10 - 7*t^9 - 3*t^8 + t^7 + 2*t^6 - 2*t^5 - 5*t^4 - 7*t^3 - 6*t^2 - 2*t - 1)/(t^3 - 1)
sage: PowerSeriesRing(ZZ,'t')(HP)
1 + 2*t + 6*t^2 + 8*t^3 + 7*t^4 + 8*t^5 + 6*t^6 + 6*t^7 + 11*t^8 + 13*t^9 + 9*t^10 + 11*t^11 + 10*t^12 + 8*t^13 + 10*t^14 + 10*t^15 + 8*t^16 + 10*t^17 + 10*t^18 + 8*t^19 + O(t^20)

Note that in princible Singular can compute Hilbert series, too, but
it has an awkward syntax, refuses to work in non-commutative settings,
and occasionally suffers from integer overflows.

Best regards,
Simon

[Reimundo Heluani]

On Nov 29, Simon King wrote:
>Hi Reimundo,
>
>On 2020-06-17, 'Reimundo Heluani' via sage-support <sage-s...@googlegroups.com> wrote:
>> Is there an implementation of such a thing as in the title?
>
>TL;DR: Yes. Singular does have these capabilities. I recall that these
>were comfortably wrapped in SageMath, but as it turns out: They aren't.

Ohh this is very cool, I have a very large ticket #29610 implementing vertex
algebras, and one of the main applications of that ticket is to use Groebner
bases techniques to deal with algebras of functions of arc and jet spaces. I
had to explicitly deal with the super and non-super situation in completely
different ways because of the lack of groebner bases for the former.

Well, in the Noetherian case this works fine. The setup I need is a
non-noetherian algebra: a polynomial differential algebra, that is polynomials
in x_1,...,x_n and all of their formal derivatives. So this is a polynomial
algebra infinitely generated by variables x_i^{(j)} for 1 <= i <= n and 0 <=
j.

I need to compute Hilbert series of differential ideals, that is ideals
generated by some elements of the above plus all of their derivatives.

This works fine in the commutative case, since I can compute grobner bases up
to arbtitrary degree and ask for the hilbert series up to that degree. But I
couldn't get it to work in the super-commutative case.

But now that you mention that this is actually implemented in libsingular,
I'll look forward to the ticket porting this to Sage.

Best,

R.

>--
>You received this message because you are subscribed to the Google Groups "sage-support" group.
>To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
>To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/rq0279%24ev3%241%40ciao.gmane.io.

[Simon King]

Hi Reimundo,

On 2020-11-29, 'Reimundo Heluani' via sage-support <sage-s...@googlegroups.com> wrote:
> Well, in the Noetherian case this works fine. The setup I need is a
> non-noetherian algebra: a polynomial differential algebra, that is polynomials
> in x_1,...,x_n and all of their formal derivatives. So this is a polynomial
> algebra infinitely generated by variables x_i^{(j)} for 1 <= i <= n and 0 <=
> j.

I see. But this probably means that we are talking about two different
notions of supercommutative algebra.

I really mean a finitely generated polynomial algebra in which some
generators anti-commute among each other.

For the non-Noetherian case, I am not so sure if some implementation is
available. What I said about SCA in Singular *is* about Noetherian
algebras.

> I need to compute Hilbert series of differential ideals, that is ideals
> generated by some elements of the above plus all of their derivatives.
>
> This works fine in the commutative case, since I can compute grobner bases up
> to arbtitrary degree and ask for the hilbert series up to that degree. But I
> couldn't get it to work in the super-commutative case.

I associate three things with it -- but I'm not sure if one of them helps.

1. There are differential algebras in Singular, but again they seem to
be finitely generated algebras. See
https://www.singular.uni-kl.de/Manual/latest/sing_2482.htm,
but I haven't been able to turn this into an example using the
pexpect interface.
2. There are several implementations of FreeAlgebra in Sage. One of them
is based on "letterplace", which is provided by Singular. It allows you
to choose non-negative integer weights and can compute Gröbner bases out
to any finite degree, *BUT* it only works for weighted-homogeneous
ideals (and in fact it won't even let you create an element that isn't
weighted homogeneous). No idea if it is possible to formulate your
problem in this very restricted setting.
3. There is a so-called InfinitePolynomialRing in Sage and it can
compute so-called symmetric Gröbner bases. But probably it doesn't
match your needs at all, as it is commutative, and the ideals under
consideration need to be "symmetric" in the sense that your algebra
has indexed series of generators x_1, x_2, x_3, ..., y_1, y_2, y_3, ...,
and when you take any element of your ideal and apply any permutation of
{1,2,3,...} to all indices of the generators, than you again get an
element of your ideal.

But I'm afraid it seems your use case isn't covered.

Best regards,
Simon

[Reimundo Heluani]

On Nov 29, Simon King wrote:

>Hi Reimundo,
>
>On 2020-11-29, 'Reimundo Heluani' via sage-support <sage-s...@googlegroups.com> wrote:
>> Well, in the Noetherian case this works fine. The setup I need is a
>> non-noetherian algebra: a polynomial differential algebra, that is polynomials
>> in x_1,...,x_n and all of their formal derivatives. So this is a polynomial
>> algebra infinitely generated by variables x_i^{(j)} for 1 <= i <= n and 0 <=
>> j.
>
>I see. But this probably means that we are talking about two different
>notions of supercommutative algebra.
>
>I really mean a finitely generated polynomial algebra in which some
>generators anti-commute among each other.
>
>For the non-Noetherian case, I am not so sure if some implementation is
>available. What I said about SCA in Singular *is* about Noetherian
>algebras.
>

We are talking about the same notions, I have my own implementation of the
super or non-super non-Noetherian case. But If I want to compute the Hilbert
series, say up to order n, then I divide by the ideal generated by all
n+1-derivatives. This produces a polynomial algebra that I can feed to
libsingular and ask for a groebner basis. I can do this in the non-super case,
but not in the super case currently.

R.

>--
>You received this message because you are subscribed to the Google Groups "sage-support" group.
>To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.

>To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/rq07f4%24o75%241%40ciao.gmane.io.