Ask Your Question

Testing whether polynomial is in algebra of other polynomials

asked 2020-01-18 11:06:01 +0200

mathworker21 gravatar image

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.

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted

answered 2020-01-18 14:29:38 +0200

rburing gravatar image

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)

S = singular.sagbi(A)
for e in E:
    print(e, '--->', singular.sagbiReduce(e, S).sage())


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.

edit flag offensive delete link more


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 gravatar imagemathworker21 ( 2020-01-18 17:04:03 +0200 )edit

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 gravatar imagerburing ( 2020-01-18 18:54:14 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2020-01-18 11:06:01 +0200

Seen: 277 times

Last updated: Jan 18 '20