Testing whether polynomial is in algebra of other polynomials

algebra

A collection $\Sigma$ of polynomials is an algebra if: (1) $\lambda f + \eta g \in \Sigma$ for any $f,g \in \Sigma, \lambda,\eta \in \mathbb{R}$ and (2) $f,g \in \Sigma$ implies $fg \in \Sigma$ . We say that $P$ is in the algebra of ${P_1,\dots,P_n}$ if $P$ is in the smallest algebra containing $P_1,\dots,P_n$ .

I was wondering if there was a way to check whether a given $P$ as in the algebra of a given collection $P_1,\dots,P_n$ .

Example: take $n \ge 1$ and let $P_1 = x_1+\dots+x_n, P_2 = x_1^2+\dots+x_n^2,\dots P_n = x_1^n+\dots+x_n^n$ . Then all $n$ of the following symmetric functions are in the algebra generated by $P_1,\dots,P_n$ : $x_1+\dots+x_n$ $x_1x_2+\dots+x_{n-1}x_n$ $x_1x_2x_3+\dots+x_{n-2}x_{n-1}x_n$ $\dots$ $x_1\dots x_n$

I'd appreciate any help.

add a comment

answered 5 years ago

rburing

10964 ●4 ●80 ●219 https://www.rburing.nl/

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.

link

Comments

Hey. Thanks a lot for your answer! I still need to play around with it some more. In the meantime, do you think there's any way to also spit out how, for example, $x_0x_1+x_0x_2+x_1x_2$ came from the given algebra, i.e. what combination of stuff in our algebra yields $x_0x_1+x_0x_2+x_1x_2$ ?

mathworker21 ( 5 years ago )

I think once you have the SAGBI basis (which seems to be not so easy), the reduction step is very easy. In theory you can keep track of the expressions in terms of the original generators, but that is not done in this implementation. You would have to modify this implementation, or find/write another that does it.

rburing ( 5 years ago )

add a comment

Testing whether polynomial is in algebra of other polynomials

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Testing whether polynomial is in algebra of other polynomials savecancel

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Testing whether polynomial is in algebra of other polynomials