Testing whether polynomial is in algebra of given collection of polynomials A collection $\Sigma$ of polynomials is an algebra if: 


*

*$\lambda f + \eta g \in \Sigma$ for any $f,g \in \Sigma,
    \lambda,\eta \in \mathbb{R}$

*$f,g \in \Sigma$ implies $fg \in \Sigma$. 

*$1 \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, on any computer math software, to check whether a given $P$ is in the algebra of a given collection $P_1,\dots,P_n$. I know Mathematica can check if $P$ is in the ideal generated by $P_1,\dots,P_n$, but I don't know about algebras, or about any software besides Mathematica (which I barely know).
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.
 A: First and foremost, I do not know of any software that solves this. But I do have some ideas that could be helpful.
Your example already includes multi variable polynomials, but let me first focus on single variable polynomials.
The algebra generated by $\{P_1,...,P_n\}$ is the infinite dimensional linear subspace of $\mathbb{R}[X]$ spanned by all monomials w.r.t. these polynomials, such as $P_1^5$ and $P_3^2P_5P_6$, but also $P_1$ and just $1$.
First of all, the case $n=1$ is very easy. All elements of the algebra are of the form $\lambda_0+\lambda_1P_1+\lambda_2P_1^2+...+\lambda_kP_1^k$ with $k=0$ or $\lambda_k\neq0$. Note that the degree of this polynomial is $k\cdot\mbox{deg}(P_1)$. This already shows that the degree of $P$ has to be a multiple of that of $P_1$. If this is the case, then you can figure out what $\lambda_k$ needs to be and subtract $\lambda_kP_1^k$ from $P$ to reduce the degree of $P$. Then simply repeat the process to determine whether $P$ belongs to the algebra generated by $P_1$.
When $n$ gets larger, the problem becomes a lot more difficult. Let us first consider the case where all $P_i$ are monomials $P_i(X)=X^{k_i}$. Then we require for every non-zero coefficient $\lambda_k$ of $P$ that $k$ can be written as a sum of numbers, with repetition allowed, from $\{k_1,...,k_n\}$. Reading up on the Frobenius problem makes me suspect this is already NP-complete with respect to $n$.
The more I think about the general problem, the more I suspect it to be undecidable. But here is an algorithm that should find a solution relatively quickly (see: polynomial in the degrees, but exponential in $n$) if one exists, and will run forever if there is no solution.
Generate all monomials w.r.t. the polynomials $P_1,...,P_n$ in order of their degree. This can be done efficiently with a priority queue. For every monomials you find, add it to the list of monomials so far. This list can be seen as a list of vectors in $\mathbb{R}^d$ with $d$ the maximum degree of the monomials thus far. Then we ask the question whether $P$ is a linear combination of these vectors.
Example: Consider $P(X)=X+2$, $P_1(X)=X+X^2$, $P_2(X)=X+X^3$. We find the following monomials with their corresponding vectors:
\begin{align*}
1&&(1,0,0,0,0,0,0)\\
P_1&&(0,1,1,0,0,0,0)\\
P_2&&(0,1,0,1,0,0,0)\\
P_1^2&&(0,0,1,2,1,0,0)\\
P_1P_2&&(0,0,1,1,1,1,0)\\
P_2^2&&(0,0,1,0,2,0,1)\\
P_1^3&&(0,0,0,1,3,3,1)\\
\end{align*}
At this point, we have $7$ linearly independent vectors in $7$ dimensions, so we can write $P$ as a linear combination of these monomials.
Note that the same algorithm can be used for multi variable polynomials. Although the algorithm will be a lot less efficient.
A: Suppose we want to determine whether $q \in \mathbb{R}[x_1, \ldots, x_r]$ is in the subalgebra generated by $p_1, \ldots, p_n$.  The general theory of Groebner bases allows us to find a Groebner basis of the kernel of the $\mathbb{R}$-algebra homomorphism
$$\mathbb{R}[t_1, \ldots, t_n, s] \to \mathbb{R}[x_1, \ldots, x_r], t_i \mapsto p_i, s \mapsto q.$$
Furthermore, if the monomial order we chose has $s > t_1^{d_1} \cdots t_r^{d_r}$ for all $d_1, \ldots, d_r \ge 0$, then $q$ will be in the subalgebra generated by $p_1, \ldots, p_n$ if and only if one of the elements of this Groebner basis of the kernel is equal to $\lambda s - F(t_1, \ldots, t_n)$ for some $\lambda \in \mathbb{R}^*, F \in \mathbb{R}[x_1, \ldots, x_r]$.
If some specific computer algebra system does not have a builtin function for finding kernels, but it does have a general Groebner basis calculation routine, then you can find the required kernel by calculating a Groebner basis for the ideal $\langle t_i - p_i, s - q \rangle$ of $\mathbb{R}[t_1, \ldots, t_n, s, x_1, \ldots, x_r]$, using an elimination order such that the monomials of $\mathbb{R}[t_1, \ldots, t_n, s]$ are smaller than any monomials containing a positive power of $x_j$.  Then take the elements of the Groebner basis of this ideal which lie in $\mathbb{R}[t_1, \ldots, t_n, s]$, and they will form the desired Groebner basis of the kernel.

This does have the disadvantage of having to do a new Groebner basis calculation for each new $q$, even if $p_1, \ldots, p_n$ are fixed.  However, we can also produce a variant of the algorithm which allows you to perform the Groebner basis calculation once for fixed $p_1, \ldots, p_n$ with $q$ varying: find a Groebner basis of the ideal $I = \langle t_i - p_i \rangle$ of $\mathbb{R}[t_1, \ldots, t_n, x_1, \ldots, x_r]$ which respect to an elimination order where the monomials in $t_1, \ldots, t_n$ are smaller than any monomial with a positive power of some $x_j$.  Now, given $q$, the reduction process of dividing $q$ (or technically $1 \otimes q \in \mathbb{R}[t_1, \ldots, t_n] \otimes_{\mathbb{R}} \mathbb{R}[x_1, \ldots, x_r] \simeq \mathbb{R}[t_1, \ldots, t_n, x_1, \ldots, x_r]$) by elements of the Groebner basis will give either zero or the representative of $(1 \otimes q) + I$ with minimal leading monomial.  Then $q$ is in the subalgebra generated by $p_1, \ldots, p_n$ if and only if that remainder of $(1 \otimes q) \mathop{\mathrm{mod}} I$ is in $\mathbb{R}[t_1, \ldots, t_n]$ (if and only if the leading monomial in the remainder is in $\mathbb{R}[t_1, \ldots, t_n]$).
