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 11:16:22 +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]A.P.Sat, 09 May 2020 11:16:22 +0200https://ask.sagemath.org/question/51336/