1 | initial version |

My first thought was that you want an analogue of a Gröbner basis of an ideal. A web search yields that exactly such a thing has been thought of: *SAGBI: Subalgebra Analogue to Gröbner Bases for Ideals*. We can use an implementation in Singular, as discussed in the old question Basis of invariant polynomial system. I think you can use it as follows:

```
n = 3
R = PolynomialRing(QQ, n, names='x')
x = R.gens()
A = R.ideal([sum(xi^k for xi in x) for k in range(1,n+1)])
print('Algebra:', A.gens())
from itertools import combinations
E = [sum(prod(xi) for xi in combinations(x,k)) for k in range(1,n+1)]
print('Elements to reduce:', E)
singular.LIB("sagbi.lib")
S = singular.sagbi(A)
for e in E:
print(e, '--->', singular.sagbiReduce(e, S).sage())
```

Output:

```
Algebra: [x0 + x1 + x2, x0^2 + x1^2 + x2^2, x0^3 + x1^3 + x2^3]
Elements to reduce: [x0 + x1 + x2, x0*x1 + x0*x2 + x1*x2, x0*x1*x2]
x0 + x1 + x2 ---> 0
x0*x1 + x0*x2 + x1*x2 ---> 0
x0*x1*x2 ---> 0
```

See the Singular manual of sagbi_lib.

(I tried calling `sagbiReduce`

with just `A`

instead of `sagbi(A)`

, but it didn't manage to do the reduction to `0`

.)

For $n=4$ the computation of `sagbi(A)`

already takes more than half an hour (I'll update this post when/if it finishes).

Maybe there exist faster implementations?

P.S. The paper $F_4$-invariant algorithm for computing SAGBI-Gröbner bases discusses an implementation of SAGBI in SAGE 4.2.1, but I didn't manage to find the code.

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.