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.
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.