Testing whether polynomial is in algebra of other polynomials

edit

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.