ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 18 Jan 2020 11:54:14 -0600Testing whether polynomial is in algebra of other polynomialshttps://ask.sagemath.org/question/49592/testing-whether-polynomial-is-in-algebra-of-other-polynomials/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.Sat, 18 Jan 2020 04:06:01 -0600https://ask.sagemath.org/question/49592/testing-whether-polynomial-is-in-algebra-of-other-polynomials/Answer by rburing for <p>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$.</p>
<p>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$.</p>
<p><strong>Example</strong>: 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$$ </p>
<p>I'd appreciate any help.</p>
https://ask.sagemath.org/question/49592/testing-whether-polynomial-is-in-algebra-of-other-polynomials/?answer=49594#post-id-49594My 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](https://ask.sagemath.org/question/8509/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](https://www.singular.uni-kl.de/Manual/4-1-2/sing_1421.htm).
(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](https://www.sciencedirect.com/science/article/pii/S0304397515000924) discusses an implementation of SAGBI in SAGE 4.2.1, but I didn't manage to find the code.
Sat, 18 Jan 2020 07:29:38 -0600https://ask.sagemath.org/question/49592/testing-whether-polynomial-is-in-algebra-of-other-polynomials/?answer=49594#post-id-49594Comment by rburing for <p>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: <em>SAGBI: Subalgebra Analogue to Gröbner Bases for Ideals</em>. We can use an implementation in Singular, as discussed in the old question <a href="https://ask.sagemath.org/question/8509/basis-of-invariant-polynomial-system/">Basis of invariant polynomial system</a>. I think you can use it as follows:</p>
<pre><code>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())
</code></pre>
<p>Output:</p>
<pre><code>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
</code></pre>
<p>See the Singular manual of <a href="https://www.singular.uni-kl.de/Manual/4-1-2/sing_1421.htm">sagbi_lib</a>.</p>
<p>(I tried calling <code>sagbiReduce</code> with just <code>A</code> instead of <code>sagbi(A)</code>, but it didn't manage to do the reduction to <code>0</code>.)</p>
<p>For $n=4$ the computation of <code>sagbi(A)</code> already takes more than half an hour (I'll update this post when/if it finishes).</p>
<p>Maybe there exist faster implementations?</p>
<p>P.S. The paper <a href="https://www.sciencedirect.com/science/article/pii/S0304397515000924">$F_4$-invariant algorithm for computing SAGBI-Gröbner bases</a> discusses an implementation of SAGBI in SAGE 4.2.1, but I didn't manage to find the code.</p>
https://ask.sagemath.org/question/49592/testing-whether-polynomial-is-in-algebra-of-other-polynomials/?comment=49599#post-id-49599I 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.Sat, 18 Jan 2020 11:54:14 -0600https://ask.sagemath.org/question/49592/testing-whether-polynomial-is-in-algebra-of-other-polynomials/?comment=49599#post-id-49599Comment by mathworker21 for <p>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: <em>SAGBI: Subalgebra Analogue to Gröbner Bases for Ideals</em>. We can use an implementation in Singular, as discussed in the old question <a href="https://ask.sagemath.org/question/8509/basis-of-invariant-polynomial-system/">Basis of invariant polynomial system</a>. I think you can use it as follows:</p>
<pre><code>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())
</code></pre>
<p>Output:</p>
<pre><code>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
</code></pre>
<p>See the Singular manual of <a href="https://www.singular.uni-kl.de/Manual/4-1-2/sing_1421.htm">sagbi_lib</a>.</p>
<p>(I tried calling <code>sagbiReduce</code> with just <code>A</code> instead of <code>sagbi(A)</code>, but it didn't manage to do the reduction to <code>0</code>.)</p>
<p>For $n=4$ the computation of <code>sagbi(A)</code> already takes more than half an hour (I'll update this post when/if it finishes).</p>
<p>Maybe there exist faster implementations?</p>
<p>P.S. The paper <a href="https://www.sciencedirect.com/science/article/pii/S0304397515000924">$F_4$-invariant algorithm for computing SAGBI-Gröbner bases</a> discusses an implementation of SAGBI in SAGE 4.2.1, but I didn't manage to find the code.</p>
https://ask.sagemath.org/question/49592/testing-whether-polynomial-is-in-algebra-of-other-polynomials/?comment=49598#post-id-49598Hey. 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$?Sat, 18 Jan 2020 10:04:03 -0600https://ask.sagemath.org/question/49592/testing-whether-polynomial-is-in-algebra-of-other-polynomials/?comment=49598#post-id-49598