Re: SymbolicPolynomialMod
- To: mathgroup at smc.vnet.net
- Subject: [mg106580] Re: [mg106564] SymbolicPolynomialMod
- From: danl at wolfram.com
- Date: Sun, 17 Jan 2010 07:10:42 -0500 (EST)
- References: <201001141046.FAA19729@smc.vnet.net>
> Dear Mathematica Gurus!
>
> Who know how to execute SymbolicPolynomialMod
> PolynomialMod working only on numbers (not for symbols)
>
> If we know that a,b,c,d,f are five roots of general quintic polynomial
> X^5+t X^4+p X^3+q X^2+r X+s==0
>
> Then we can do SymbolicPolynomialMod of g (manually not by Mathemathica
> unfortunatelly)
>
> g=(a^6 b^7 c^5 d^2 + a^7 b^5 c^6 d^2 + a^5 b^6 c^7 d^2 +
> a^7 b^6 c^2 d^5 + a^2 b^7 c^6 d^5 + a^6 b^2 c^7 d^5 +
> a^5 b^7 c^2 d^6 + a^7 b^2 c^5 d^6 + a^2 b^5 c^7 d^6 +
> a^6 b^5 c^2 d^7 + a^2 b^6 c^5 d^7 + a^5 b^2 c^6 d^7 -
> a^6 b^8 c^3 d^2 f - a^8 b^3 c^6 d^2 f - a^3 b^6 c^8 d^2 f -
> a^8 b^6 c^2 d^3 f - a^2 b^8 c^6 d^3 f - a^6 b^2 c^8 d^3 f -
> a^3 b^8 c^2 d^6 f - a^8 b^2 c^3 d^6 f - a^2 b^3 c^8 d^6 f -
> a^6 b^3 c^2 d^8 f - a^2 b^6 c^3 d^8 f - a^3 b^2 c^6 d^8 f +
> a^7 b^6 c^5 f^2 + a^5 b^7 c^6 f^2 + a^6 b^5 c^7 f^2 -
> a^8 b^6 c^3 d f^2 - a^3 b^8 c^6 d f^2 - a^6 b^3 c^8 d f^2 -
> a^6 b^8 c d^3 f^2 - a^8 b c^6 d^3 f^2 - a b^6 c^8 d^3 f^2 +
> a^6 b^7 d^5 f^2 + a^7 c^6 d^5 f^2 + b^6 c^7 d^5 f^2 +
> a^7 b^5 d^6 f^2 - a^8 b^3 c d^6 f^2 - a b^8 c^3 d^6 f^2 +
> b^7 c^5 d^6 f^2 + a^5 c^7 d^6 f^2 - a^3 b c^8 d^6 f^2 +
> a^5 b^6 d^7 f^2 + a^6 c^5 d^7 f^2 + b^5 c^6 d^7 f^2 -
> a^3 b^6 c d^8 f^2 - a^6 b c^3 d^8 f^2 - a b^3 c^6 d^8 f^2 -
> a^6 b^8 c^2 d f^3 - a^8 b^2 c^6 d f^3 - a^2 b^6 c^8 d f^3 -
> a^8 b^6 c d^2 f^3 - a b^8 c^6 d^2 f^3 - a^6 b c^8 d^2 f^3 -
> a^2 b^8 c d^6 f^3 - a^8 b c^2 d^6 f^3 - a b^2 c^8 d^6 f^3 -
> a^6 b^2 c d^8 f^3 - a b^6 c^2 d^8 f^3 - a^2 b c^6 d^8 f^3 +
> a^6 b^7 c^2 f^5 + a^7 b^2 c^6 f^5 + a^2 b^6 c^7 f^5 +
> a^7 b^6 d^2 f^5 + b^7 c^6 d^2 f^5 + a^6 c^7 d^2 f^5 +
> a^2 b^7 d^6 f^5 + a^7 c^2 d^6 f^5 + b^2 c^7 d^6 f^5 +
> a^6 b^2 d^7 f^5 + b^6 c^2 d^7 f^5 + a^2 c^6 d^7 f^5 +
> a^7 b^5 c^2 f^6 + a^2 b^7 c^5 f^6 + a^5 b^2 c^7 f^6 -
> a^8 b^3 c^2 d f^6 - a^2 b^8 c^3 d f^6 - a^3 b^2 c^8 d f^6 +
> a^5 b^7 d^2 f^6 - a^3 b^8 c d^2 f^6 - a^8 b c^3 d^2 f^6 +
> a^7 c^5 d^2 f^6 + b^5 c^7 d^2 f^6 - a b^3 c^8 d^2 f^6 -
> a^8 b^2 c d^3 f^6 - a b^8 c^2 d^3 f^6 - a^2 b c^8 d^3 f^6 +
> a^7 b^2 d^5 f^6 + b^7 c^2 d^5 f^6 + a^2 c^7 d^5 f^6 +
> a^2 b^5 d^7 f^6 + a^5 c^2 d^7 f^6 + b^2 c^5 d^7 f^6 -
> a^2 b^3 c d^8 f^6 - a^3 b c^2 d^8 f^6 - a b^2 c^3 d^8 f^6 +
> a^5 b^6 c^2 f^7 + a^6 b^2 c^5 f^7 + a^2 b^5 c^6 f^7 +
> a^6 b^5 d^2 f^7 + b^6 c^5 d^2 f^7 + a^5 c^6 d^2 f^7 +
> a^2 b^6 d^5 f^7 + a^6 c^2 d^5 f^7 + b^2 c^6 d^5 f^7 +
> a^5 b^2 d^6 f^7 + b^5 c^2 d^6 f^7 + a^2 c^5 d^6 f^7 -
> a^3 b^6 c^2 d f^8 - a^6 b^2 c^3 d f^8 - a^2 b^3 c^6 d f^8 -
> a^6 b^3 c d^2 f^8 - a b^6 c^3 d^2 f^8 - a^3 b c^6 d^2 f^8 -
> a^2 b^6 c d^3 f^8 - a^6 b c^2 d^3 f^8 - a b^2 c^6 d^3 f^8 -
> a^3 b^2 c d^6 f^8 - a b^3 c^2 d^6 f^8 - a^2 b c^3 d^6 f^8)
>
> by substitutions g/. {a^5->-t a^4-p a^3-q a^2-r a-s,b^5->-t b^4-p b^3-q
> b^2-r b-s,
> c^5->-t c^4-p c^3-q c^2-r c-s,d^5->-t d^4-p d^3-q d^2-r d-s,f^5->-t
> f^4-p f^3-q f^2-r f-s}
>
> etc.
>
> How we can do full SymbolicPolynomialMod on the form g after such
> procedure will be not higher degree as 4 for a,b,c,d,f ?
>
> Best wishes
> Artur
You will want to use PolynomialReduce in one way or another. You could
simply reduce by what amounts to the rules you indicate above. That does
not really do anything to enforce that the roots are distinct, because
those defining polynomials alone do not enforce distinctness. For that,
one can use the set of relations between roots and coefficients. I'll show
this approach. I use Array to get indexed coefficients and roots, so will
translate your polynomial accordingly.
In[19]:= deg = 5;
coeffs = Array[c, deg, 0];
poly = x^deg + coeffs.x^Range[0, deg - 1];
rts = Array[z, deg];
clist = CoefficientList[Apply[Times, x - rts] - poly, x]
Out[52]= {-c[0] - z[1] z[2] z[3] z[4] z[5], -c[1] +
z[1] z[2] z[3] z[4] + z[1] z[2] z[3] z[5] + z[1] z[2] z[4] z[5] +
z[1] z[3] z[4] z[5] + z[2] z[3] z[4] z[5], -c[2] - z[1] z[2] z[3] -
z[1] z[2] z[4] - z[1] z[3] z[4] - z[2] z[3] z[4] - z[1] z[2] z[5] -
z[1] z[3] z[5] - z[2] z[3] z[5] - z[1] z[4] z[5] - z[2] z[4] z[5] -
z[3] z[4] z[5], -c[3] + z[1] z[2] + z[1] z[3] + z[2] z[3] +
z[1] z[4] + z[2] z[4] + z[3] z[4] + z[1] z[5] + z[2] z[5] +
z[3] z[5] + z[4] z[5], -c[4] - z[1] - z[2] - z[3] - z[4] - z[5]}
That gives the set of defining relations between roots and coefficients.
I'll form a Groebner basis for use in later reduction.
In[25]:= Timing[
gb = GroebnerBasis[clist, rts,
MonomialOrder -> DegreeReverseLexicographic,
CoefficientDomain -> RationalFunctions];]
Out[25]= {0.016, Null}
Fast. Turns out it is the reduction that is slow. Next we translate from
your notation to mine.
g2 = g /. Thread[{a, b, c, d, f} -> rts];
In[30]:= LeafCount[g2]
Out[30]= 2221
We now do the reduction, using the same term ordering as before. Might
want to get a cup of coffee...
In[42]:= Timing[{mults2, red2} =
PolynomialReduce[g2, gb, rts,
MonomialOrder -> DegreeReverseLexicographic,
CoefficientDomain -> RationalFunctions];]
Out[42]= {375.339, Null}
In[43]:= LeafCount[red2]
Out[43]= 22638
That's far bigger than I want to look at, let alone put in email.
Daniel Lichtblau
Wolfram Research
- References:
- Trouble with coupled quadratic equations where the solutions are degenerate/symmetric
- From: Robert Hoy <robert.hoy@yale.edu>
- Trouble with coupled quadratic equations where the solutions are degenerate/symmetric