ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 09 May 2020 23:15:18 +0200Implicitization by symmetric polynomialshttps://ask.sagemath.org/question/51336/implicitization-by-symmetric-polynomials/Let $p_1,\dotsc,p_m$ be real polynomials (although rational can do as well) in $t$ variables.
> What is the most efficient way to compute the smallest degree $d$ such that $s(p_1,\dotsc,p_m) = 0$ for some rational symmetric polynomial $s$ in $m$ variables?
----------
At the moment I am doing this for $t = 1$ by iterating the following simple algorithm over $d \geq 1$:
1. Create a list `Sc` of the Schur functions corresponding to the partitions of $k \leq d$ with at most $m$ parts, which is a linear basis over $\Bbb{Q}$ for the space of symmetric polynomials in $m$ variables with degree up to $d$.
2. Compute the list `Ps` of the evaluations of each element of `Sc` at $(p_1,\dotsc,p_m)$.
3. Convert the elements of `Ps` into vectors and stop if they are linearly dependent, otherwise increase $d$ by one and repeat from 1.
This works reasonably well when the degrees of $p_1,\dotsc,p_m$ are small, but otherwise iterating over each $d$ involves quite a bit of work and it doesn't scale very well.
I know that the equivalent problem for $s \in \Bbb{Q}[X_1,\dotsc,X_m]$ is "readily" solved through variable elimination via Gröbner bases, but I have yet to find a way to make this work for symmetric polynomials. I also thought that I might compute the relevant ideal and then try to find the subset fixed by the symmetric group in $m$ variables, but I couldn't find any facilities in Sage to compute fixed sets under a group action (which I guess is a hard problem in general).
----------
This is my current code:
S = SymmetricFunctions(QQ).s()
R.<x> = QQ[]
def eval_schur(F, d):
"""
Returns the evaluation at a vector F of the Schur functions of degree n.
"""
m = len(F)
schur_polys = ((l, S(l).expand(m)) for l in Partitions(d) if len(l) <= m)
return ((l, sch(*F)) for (l,sch) in schur_polys)
def poly_vectors(polys):
d = max(p.degree() for p in polys)
return (p.padded_list(d+1) for p in polys)
def order_of_symmetric_dependence(F):
schur = [R(1)]
vectors = [1]
d = 0
while not FreeModule(QQ,1).are_linearly_dependent(vectors):
d += 1
schur.extend((s for (_,s) in eval_schur(F,d)))
vectors = poly_vectors(schur)
return d
And here's a sample output:
In [2]: [order_of_symmetric_dependence([x, x^2, x^(2*k)]) for k in range(1,8)]
Out[2]: [4, 5, 8, 11, 12, 12, 12]Sat, 09 May 2020 11:16:22 +0200https://ask.sagemath.org/question/51336/implicitization-by-symmetric-polynomials/Comment by rburing for <p>Let $p_1,\dotsc,p_m$ be real polynomials (although rational can do as well) in $t$ variables.</p>
<blockquote>
<p>What is the most efficient way to compute the smallest degree $d$ such that $s(p_1,\dotsc,p_m) = 0$ for some rational symmetric polynomial $s$ in $m$ variables?</p>
</blockquote>
<hr>
<p>At the moment I am doing this for $t = 1$ by iterating the following simple algorithm over $d \geq 1$:</p>
<ol>
<li><p>Create a list <code>Sc</code> of the Schur functions corresponding to the partitions of $k \leq d$ with at most $m$ parts, which is a linear basis over $\Bbb{Q}$ for the space of symmetric polynomials in $m$ variables with degree up to $d$.</p></li>
<li><p>Compute the list <code>Ps</code> of the evaluations of each element of <code>Sc</code> at $(p_1,\dotsc,p_m)$.</p></li>
<li><p>Convert the elements of <code>Ps</code> into vectors and stop if they are linearly dependent, otherwise increase $d$ by one and repeat from 1.</p></li>
</ol>
<p>This works reasonably well when the degrees of $p_1,\dotsc,p_m$ are small, but otherwise iterating over each $d$ involves quite a bit of work and it doesn't scale very well.</p>
<p>I know that the equivalent problem for $s \in \Bbb{Q}[X_1,\dotsc,X_m]$ is "readily" solved through variable elimination via Gröbner bases, but I have yet to find a way to make this work for symmetric polynomials. I also thought that I might compute the relevant ideal and then try to find the subset fixed by the symmetric group in $m$ variables, but I couldn't find any facilities in Sage to compute fixed sets under a group action (which I guess is a hard problem in general).</p>
<hr>
<p>This is my current code:</p>
<pre><code>S = SymmetricFunctions(QQ).s()
R.<x> = QQ[]
def eval_schur(F, d):
"""
Returns the evaluation at a vector F of the Schur functions of degree n.
"""
m = len(F)
schur_polys = ((l, S(l).expand(m)) for l in Partitions(d) if len(l) <= m)
return ((l, sch(*F)) for (l,sch) in schur_polys)
def poly_vectors(polys):
d = max(p.degree() for p in polys)
return (p.padded_list(d+1) for p in polys)
def order_of_symmetric_dependence(F):
schur = [R(1)]
vectors = [1]
d = 0
while not FreeModule(QQ,1).are_linearly_dependent(vectors):
d += 1
schur.extend((s for (_,s) in eval_schur(F,d)))
vectors = poly_vectors(schur)
return d
</code></pre>
<p>And here's a sample output:</p>
<pre><code>In [2]: [order_of_symmetric_dependence([x, x^2, x^(2*k)]) for k in range(1,8)]
Out[2]: [4, 5, 8, 11, 12, 12, 12]
</code></pre>
https://ask.sagemath.org/question/51336/implicitization-by-symmetric-polynomials/?comment=51337#post-id-51337Can you add your code and a sample case? Maybe naive idea: eliminate $x_1,\ldots,x_t$ from $\langle y_i - e_i(p_1(x_1,\ldots,x_t),\ldots,p_m(x_1,\ldots,x_t)) \rangle$ where $e_i$ are the elementary symmetric polynomials in $m$ variables.Sat, 09 May 2020 11:53:41 +0200https://ask.sagemath.org/question/51336/implicitization-by-symmetric-polynomials/?comment=51337#post-id-51337Comment by A.P. for <p>Let $p_1,\dotsc,p_m$ be real polynomials (although rational can do as well) in $t$ variables.</p>
<blockquote>
<p>What is the most efficient way to compute the smallest degree $d$ such that $s(p_1,\dotsc,p_m) = 0$ for some rational symmetric polynomial $s$ in $m$ variables?</p>
</blockquote>
<hr>
<p>At the moment I am doing this for $t = 1$ by iterating the following simple algorithm over $d \geq 1$:</p>
<ol>
<li><p>Create a list <code>Sc</code> of the Schur functions corresponding to the partitions of $k \leq d$ with at most $m$ parts, which is a linear basis over $\Bbb{Q}$ for the space of symmetric polynomials in $m$ variables with degree up to $d$.</p></li>
<li><p>Compute the list <code>Ps</code> of the evaluations of each element of <code>Sc</code> at $(p_1,\dotsc,p_m)$.</p></li>
<li><p>Convert the elements of <code>Ps</code> into vectors and stop if they are linearly dependent, otherwise increase $d$ by one and repeat from 1.</p></li>
</ol>
<p>This works reasonably well when the degrees of $p_1,\dotsc,p_m$ are small, but otherwise iterating over each $d$ involves quite a bit of work and it doesn't scale very well.</p>
<p>I know that the equivalent problem for $s \in \Bbb{Q}[X_1,\dotsc,X_m]$ is "readily" solved through variable elimination via Gröbner bases, but I have yet to find a way to make this work for symmetric polynomials. I also thought that I might compute the relevant ideal and then try to find the subset fixed by the symmetric group in $m$ variables, but I couldn't find any facilities in Sage to compute fixed sets under a group action (which I guess is a hard problem in general).</p>
<hr>
<p>This is my current code:</p>
<pre><code>S = SymmetricFunctions(QQ).s()
R.<x> = QQ[]
def eval_schur(F, d):
"""
Returns the evaluation at a vector F of the Schur functions of degree n.
"""
m = len(F)
schur_polys = ((l, S(l).expand(m)) for l in Partitions(d) if len(l) <= m)
return ((l, sch(*F)) for (l,sch) in schur_polys)
def poly_vectors(polys):
d = max(p.degree() for p in polys)
return (p.padded_list(d+1) for p in polys)
def order_of_symmetric_dependence(F):
schur = [R(1)]
vectors = [1]
d = 0
while not FreeModule(QQ,1).are_linearly_dependent(vectors):
d += 1
schur.extend((s for (_,s) in eval_schur(F,d)))
vectors = poly_vectors(schur)
return d
</code></pre>
<p>And here's a sample output:</p>
<pre><code>In [2]: [order_of_symmetric_dependence([x, x^2, x^(2*k)]) for k in range(1,8)]
Out[2]: [4, 5, 8, 11, 12, 12, 12]
</code></pre>
https://ask.sagemath.org/question/51336/implicitization-by-symmetric-polynomials/?comment=51341#post-id-51341@rburing I had to clean up my code a little, but here it is.Sat, 09 May 2020 14:19:23 +0200https://ask.sagemath.org/question/51336/implicitization-by-symmetric-polynomials/?comment=51341#post-id-51341Comment by A.P. for <p>Let $p_1,\dotsc,p_m$ be real polynomials (although rational can do as well) in $t$ variables.</p>
<blockquote>
<p>What is the most efficient way to compute the smallest degree $d$ such that $s(p_1,\dotsc,p_m) = 0$ for some rational symmetric polynomial $s$ in $m$ variables?</p>
</blockquote>
<hr>
<p>At the moment I am doing this for $t = 1$ by iterating the following simple algorithm over $d \geq 1$:</p>
<ol>
<li><p>Create a list <code>Sc</code> of the Schur functions corresponding to the partitions of $k \leq d$ with at most $m$ parts, which is a linear basis over $\Bbb{Q}$ for the space of symmetric polynomials in $m$ variables with degree up to $d$.</p></li>
<li><p>Compute the list <code>Ps</code> of the evaluations of each element of <code>Sc</code> at $(p_1,\dotsc,p_m)$.</p></li>
<li><p>Convert the elements of <code>Ps</code> into vectors and stop if they are linearly dependent, otherwise increase $d$ by one and repeat from 1.</p></li>
</ol>
<p>This works reasonably well when the degrees of $p_1,\dotsc,p_m$ are small, but otherwise iterating over each $d$ involves quite a bit of work and it doesn't scale very well.</p>
<p>I know that the equivalent problem for $s \in \Bbb{Q}[X_1,\dotsc,X_m]$ is "readily" solved through variable elimination via Gröbner bases, but I have yet to find a way to make this work for symmetric polynomials. I also thought that I might compute the relevant ideal and then try to find the subset fixed by the symmetric group in $m$ variables, but I couldn't find any facilities in Sage to compute fixed sets under a group action (which I guess is a hard problem in general).</p>
<hr>
<p>This is my current code:</p>
<pre><code>S = SymmetricFunctions(QQ).s()
R.<x> = QQ[]
def eval_schur(F, d):
"""
Returns the evaluation at a vector F of the Schur functions of degree n.
"""
m = len(F)
schur_polys = ((l, S(l).expand(m)) for l in Partitions(d) if len(l) <= m)
return ((l, sch(*F)) for (l,sch) in schur_polys)
def poly_vectors(polys):
d = max(p.degree() for p in polys)
return (p.padded_list(d+1) for p in polys)
def order_of_symmetric_dependence(F):
schur = [R(1)]
vectors = [1]
d = 0
while not FreeModule(QQ,1).are_linearly_dependent(vectors):
d += 1
schur.extend((s for (_,s) in eval_schur(F,d)))
vectors = poly_vectors(schur)
return d
</code></pre>
<p>And here's a sample output:</p>
<pre><code>In [2]: [order_of_symmetric_dependence([x, x^2, x^(2*k)]) for k in range(1,8)]
Out[2]: [4, 5, 8, 11, 12, 12, 12]
</code></pre>
https://ask.sagemath.org/question/51336/implicitization-by-symmetric-polynomials/?comment=51342#post-id-51342@rburing Unfortunately, your suggestion doesn't seem to work, assuming I understand it correctly:
F = [t,t^2,t^3]
Rt.<t,x1,x2,x3> = QQ[]
I = Rt.ideal([x1 - E[1].expand(3)(F), x2 - E[2].expand(3)(F), x3 - E[3].expand(3)(F)])
gs = I.elimination_ideal(t).gens()
[g(x1 = F[0], x2 = F[1], x3 = F[2]) for g in gs]
outputs
[-t^6 - t^5 + t^4 + t^3,
t^7 - t^6 - 3*t^5 + t^4 + 2*t^3,
t^5 + t^4 - t^3 - t^2,
2*t^10 - 4*t^9 - 9*t^8 + 2*t^7 + 5*t^6]
instead of `[0,0,0,0]`.Sat, 09 May 2020 14:37:08 +0200https://ask.sagemath.org/question/51336/implicitization-by-symmetric-polynomials/?comment=51342#post-id-51342Comment by A.P. for <p>Let $p_1,\dotsc,p_m$ be real polynomials (although rational can do as well) in $t$ variables.</p>
<blockquote>
<p>What is the most efficient way to compute the smallest degree $d$ such that $s(p_1,\dotsc,p_m) = 0$ for some rational symmetric polynomial $s$ in $m$ variables?</p>
</blockquote>
<hr>
<p>At the moment I am doing this for $t = 1$ by iterating the following simple algorithm over $d \geq 1$:</p>
<ol>
<li><p>Create a list <code>Sc</code> of the Schur functions corresponding to the partitions of $k \leq d$ with at most $m$ parts, which is a linear basis over $\Bbb{Q}$ for the space of symmetric polynomials in $m$ variables with degree up to $d$.</p></li>
<li><p>Compute the list <code>Ps</code> of the evaluations of each element of <code>Sc</code> at $(p_1,\dotsc,p_m)$.</p></li>
<li><p>Convert the elements of <code>Ps</code> into vectors and stop if they are linearly dependent, otherwise increase $d$ by one and repeat from 1.</p></li>
</ol>
<p>This works reasonably well when the degrees of $p_1,\dotsc,p_m$ are small, but otherwise iterating over each $d$ involves quite a bit of work and it doesn't scale very well.</p>
<p>I know that the equivalent problem for $s \in \Bbb{Q}[X_1,\dotsc,X_m]$ is "readily" solved through variable elimination via Gröbner bases, but I have yet to find a way to make this work for symmetric polynomials. I also thought that I might compute the relevant ideal and then try to find the subset fixed by the symmetric group in $m$ variables, but I couldn't find any facilities in Sage to compute fixed sets under a group action (which I guess is a hard problem in general).</p>
<hr>
<p>This is my current code:</p>
<pre><code>S = SymmetricFunctions(QQ).s()
R.<x> = QQ[]
def eval_schur(F, d):
"""
Returns the evaluation at a vector F of the Schur functions of degree n.
"""
m = len(F)
schur_polys = ((l, S(l).expand(m)) for l in Partitions(d) if len(l) <= m)
return ((l, sch(*F)) for (l,sch) in schur_polys)
def poly_vectors(polys):
d = max(p.degree() for p in polys)
return (p.padded_list(d+1) for p in polys)
def order_of_symmetric_dependence(F):
schur = [R(1)]
vectors = [1]
d = 0
while not FreeModule(QQ,1).are_linearly_dependent(vectors):
d += 1
schur.extend((s for (_,s) in eval_schur(F,d)))
vectors = poly_vectors(schur)
return d
</code></pre>
<p>And here's a sample output:</p>
<pre><code>In [2]: [order_of_symmetric_dependence([x, x^2, x^(2*k)]) for k in range(1,8)]
Out[2]: [4, 5, 8, 11, 12, 12, 12]
</code></pre>
https://ask.sagemath.org/question/51336/implicitization-by-symmetric-polynomials/?comment=51343#post-id-51343Actually, I made a mistake there. I should have substituted $e_i$ back in after eliminating the variables, and indeed evaluating the elements of
gs = [g(x1 = E[1].expand(3), x2 = E[2].expand(3), x3 = E[3].expand(3)) for g in I.elimination_ideal(t).gens()]
at `F` results in `[0,0,0,0]`. I'll have to do some performance tests, now.Sat, 09 May 2020 14:52:05 +0200https://ask.sagemath.org/question/51336/implicitization-by-symmetric-polynomials/?comment=51343#post-id-51343Answer by rburing for <p>Let $p_1,\dotsc,p_m$ be real polynomials (although rational can do as well) in $t$ variables.</p>
<blockquote>
<p>What is the most efficient way to compute the smallest degree $d$ such that $s(p_1,\dotsc,p_m) = 0$ for some rational symmetric polynomial $s$ in $m$ variables?</p>
</blockquote>
<hr>
<p>At the moment I am doing this for $t = 1$ by iterating the following simple algorithm over $d \geq 1$:</p>
<ol>
<li><p>Create a list <code>Sc</code> of the Schur functions corresponding to the partitions of $k \leq d$ with at most $m$ parts, which is a linear basis over $\Bbb{Q}$ for the space of symmetric polynomials in $m$ variables with degree up to $d$.</p></li>
<li><p>Compute the list <code>Ps</code> of the evaluations of each element of <code>Sc</code> at $(p_1,\dotsc,p_m)$.</p></li>
<li><p>Convert the elements of <code>Ps</code> into vectors and stop if they are linearly dependent, otherwise increase $d$ by one and repeat from 1.</p></li>
</ol>
<p>This works reasonably well when the degrees of $p_1,\dotsc,p_m$ are small, but otherwise iterating over each $d$ involves quite a bit of work and it doesn't scale very well.</p>
<p>I know that the equivalent problem for $s \in \Bbb{Q}[X_1,\dotsc,X_m]$ is "readily" solved through variable elimination via Gröbner bases, but I have yet to find a way to make this work for symmetric polynomials. I also thought that I might compute the relevant ideal and then try to find the subset fixed by the symmetric group in $m$ variables, but I couldn't find any facilities in Sage to compute fixed sets under a group action (which I guess is a hard problem in general).</p>
<hr>
<p>This is my current code:</p>
<pre><code>S = SymmetricFunctions(QQ).s()
R.<x> = QQ[]
def eval_schur(F, d):
"""
Returns the evaluation at a vector F of the Schur functions of degree n.
"""
m = len(F)
schur_polys = ((l, S(l).expand(m)) for l in Partitions(d) if len(l) <= m)
return ((l, sch(*F)) for (l,sch) in schur_polys)
def poly_vectors(polys):
d = max(p.degree() for p in polys)
return (p.padded_list(d+1) for p in polys)
def order_of_symmetric_dependence(F):
schur = [R(1)]
vectors = [1]
d = 0
while not FreeModule(QQ,1).are_linearly_dependent(vectors):
d += 1
schur.extend((s for (_,s) in eval_schur(F,d)))
vectors = poly_vectors(schur)
return d
</code></pre>
<p>And here's a sample output:</p>
<pre><code>In [2]: [order_of_symmetric_dependence([x, x^2, x^(2*k)]) for k in range(1,8)]
Out[2]: [4, 5, 8, 11, 12, 12, 12]
</code></pre>
https://ask.sagemath.org/question/51336/implicitization-by-symmetric-polynomials/?answer=51353#post-id-51353As suggested in my comment: you can eliminate $x_1,…,x_t$ from the ideal $$I = \langle y_i - e_i(p_1(x_1,\ldots,x_t),\ldots,p_m(x_1,\ldots,x_t)) : i = 1,\ldots, m \rangle$$ in the ring $\mathbb{Q}[x_1,\ldots,x_t,y_1,\ldots,y_m]$, where $e_i$ are the elementary symmetric polynomials in m variables.
For efficiency reasons we compute the elimination ideal $I \cap \mathbb{Q}[y_1,\ldots,y_m]$ manually, using a Groebner basis $G$ of $I$ with respect to a block ordering where the $x$'s are the greatest and the $y$'s have a weighted degrevlex ordering where $y_k$ has degree $k$ (simulating the degree of $e_k$), so that substituting $y_i = e_i(x_1,\ldots,x_t)$ into the polynomials in $G \cap \mathbb{Q}[y_1,\ldots,y_m]$ yields symmetric dependencies of minimal degree.
def symmetric_dependencies(p):
R = p[0].parent()
m = len(p)
S = PolynomialRing(R.base_ring(),
names=list(R.gens()) + ['y{}'.format(k+1) for k in range(m)],
order=TermOrder('degrevlex', R.ngens()) + \
TermOrder('wdegrevlex',list(range(1,m+1))))
p = [S(f) for f in p]
X = S.gens()[0:R.ngens()]
Y = S.gens()[R.ngens():]
E = SymmetricFunctions(QQ).elementary()
Es = [E[k+1].expand(m) for k in range(m)]
I = S.ideal([Y[k] - Es[k](p) for k in range(m)])
G = I.groebner_basis()
GY = [g for g in G if all(v in Y for v in g.lt().variables())]
E_subs = {Y[k] : Es[k] for k in range(m)}
dependencies = [f.subs(E_subs) for f in GY]
#assert all(f(p) == 0 for f in dependencies)
return dependencies
Example:
sage: R.<x> = QQ[]
sage: [min(f.degree() for f in symmetric_dependencies([x, x^2, x^(2*k)])) for k in range(1,8)]
[4, 5, 8, 11, 12, 12, 12]
It seems to be slightly faster than your function on this example.Sat, 09 May 2020 19:34:31 +0200https://ask.sagemath.org/question/51336/implicitization-by-symmetric-polynomials/?answer=51353#post-id-51353Comment by A.P. for <p>As suggested in my comment: you can eliminate $x_1,…,x_t$ from the ideal $$I = \langle y_i - e_i(p_1(x_1,\ldots,x_t),\ldots,p_m(x_1,\ldots,x_t)) : i = 1,\ldots, m \rangle$$ in the ring $\mathbb{Q}[x_1,\ldots,x_t,y_1,\ldots,y_m]$, where $e_i$ are the elementary symmetric polynomials in m variables.</p>
<p>For efficiency reasons we compute the elimination ideal $I \cap \mathbb{Q}[y_1,\ldots,y_m]$ manually, using a Groebner basis $G$ of $I$ with respect to a block ordering where the $x$'s are the greatest and the $y$'s have a weighted degrevlex ordering where $y_k$ has degree $k$ (simulating the degree of $e_k$), so that substituting $y_i = e_i(x_1,\ldots,x_t)$ into the polynomials in $G \cap \mathbb{Q}[y_1,\ldots,y_m]$ yields symmetric dependencies of minimal degree.</p>
<pre><code>def symmetric_dependencies(p):
R = p[0].parent()
m = len(p)
S = PolynomialRing(R.base_ring(),
names=list(R.gens()) + ['y{}'.format(k+1) for k in range(m)],
order=TermOrder('degrevlex', R.ngens()) + \
TermOrder('wdegrevlex',list(range(1,m+1))))
p = [S(f) for f in p]
X = S.gens()[0:R.ngens()]
Y = S.gens()[R.ngens():]
E = SymmetricFunctions(QQ).elementary()
Es = [E[k+1].expand(m) for k in range(m)]
I = S.ideal([Y[k] - Es[k](p) for k in range(m)])
G = I.groebner_basis()
GY = [g for g in G if all(v in Y for v in g.lt().variables())]
E_subs = {Y[k] : Es[k] for k in range(m)}
dependencies = [f.subs(E_subs) for f in GY]
#assert all(f(p) == 0 for f in dependencies)
return dependencies
</code></pre>
<p>Example:</p>
<pre><code>sage: R.<x> = QQ[]
sage: [min(f.degree() for f in symmetric_dependencies([x, x^2, x^(2*k)])) for k in range(1,8)]
[4, 5, 8, 11, 12, 12, 12]
</code></pre>
<p>It seems to be slightly faster than your function on this example.</p>
https://ask.sagemath.org/question/51336/implicitization-by-symmetric-polynomials/?comment=51356#post-id-51356Thank you, this is precisely what I was after.Sat, 09 May 2020 23:15:18 +0200https://ask.sagemath.org/question/51336/implicitization-by-symmetric-polynomials/?comment=51356#post-id-51356