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.Thu, 10 May 2018 21:48:45 -0500polynomials with roots of unity as coefficientshttps://ask.sagemath.org/question/42307/polynomials-with-roots-of-unity-as-coefficients/I have three polynomials $(1+x)^L+1$, $(1+\omega x)^L+$ and $(1+\omega^2 x)^L+1$ where $\omega$ is cube root of unity and L is some constant, for example, 2 or 3. I want to find the GCD of these polynomials. How do I define these polynomials in sagemath with coefficients as roots of unity?Thu, 10 May 2018 15:48:58 -0500https://ask.sagemath.org/question/42307/polynomials-with-roots-of-unity-as-coefficients/Answer by tmonteil for <p>I have three polynomials $(1+x)^L+1$, $(1+\omega x)^L+$ and $(1+\omega^2 x)^L+1$ where $\omega$ is cube root of unity and L is some constant, for example, 2 or 3. I want to find the GCD of these polynomials. How do I define these polynomials in sagemath with coefficients as roots of unity?</p>
https://ask.sagemath.org/question/42307/polynomials-with-roots-of-unity-as-coefficients/?answer=42309#post-id-42309I would suggest to work on the polynomial ring with coefficient in the algebraic number field since you will have exact representations and your computations will be reliable:
sage: R.<x> = PolynomialRing(QQbar)
sage: R
Univariate Polynomial Ring in x over Algebraic Field
sage: a = QQbar(1)
sage: w = a.nth_root(3, all=True)[1]
sage: w.parent()
Algebraic Field
sage: L = 3
sage: A = (1+x)^L + 1
sage: B = (1+w*x)^L +1
sage: C = (1+w^2*x)^L +1
sage: A.parent()
Univariate Polynomial Ring in x over Algebraic Field
Apparently, those polynomials are coprime to eachother:
sage: gcd(A,gcd(B,C))
1
**EDIT** regarding the comment, if you want to work in the algebraic closure of the finite field with two elements, you can do:
sage: F = GF(2).algebraic_closure()
sage: R.<x> = PolynomialRing(F) ; R
Univariate Polynomial Ring in x over Algebraic closure of Finite Field of size 2
sage: P = x^3-1
sage: P.roots()
[(z2 + 1, 1), (z2, 1), (1, 1)]
sage: P.roots(multiplicities=False)
[z2 + 1, z2, 1]
sage: L = 3
sage: [(1+w*x)^L +1 for w in P.roots(multiplicities=False)]
sage: polys = [(1+w*x)^L +1 for w in P.roots(multiplicities=False)] ; polys
[x^3 + z2*x^2 + (z2 + 1)*x, x^3 + (z2 + 1)*x^2 + z2*x, x^3 + x^2 + x]
sage: reduce(gcd, polys)
x
sage: L = 2
sage: polys = [(1+w*x)^L +1 for w in P.roots(multiplicities=False)] ; polys
[z2*x^2, (z2 + 1)*x^2, x^2]
sage: reduce(gcd, polys)
x^2Thu, 10 May 2018 16:43:03 -0500https://ask.sagemath.org/question/42307/polynomials-with-roots-of-unity-as-coefficients/?answer=42309#post-id-42309Comment by arpit for <p>I would suggest to work on the polynomial ring with coefficient in the algebraic number field since you will have exact representations and your computations will be reliable:</p>
<pre><code>sage: R.<x> = PolynomialRing(QQbar)
sage: R
Univariate Polynomial Ring in x over Algebraic Field
sage: a = QQbar(1)
sage: w = a.nth_root(3, all=True)[1]
sage: w.parent()
Algebraic Field
sage: L = 3
sage: A = (1+x)^L + 1
sage: B = (1+w*x)^L +1
sage: C = (1+w^2*x)^L +1
sage: A.parent()
Univariate Polynomial Ring in x over Algebraic Field
</code></pre>
<p>Apparently, those polynomials are coprime to eachother:</p>
<pre><code>sage: gcd(A,gcd(B,C))
1
</code></pre>
<p><strong>EDIT</strong> regarding the comment, if you want to work in the algebraic closure of the finite field with two elements, you can do:</p>
<pre><code>sage: F = GF(2).algebraic_closure()
sage: R.<x> = PolynomialRing(F) ; R
Univariate Polynomial Ring in x over Algebraic closure of Finite Field of size 2
sage: P = x^3-1
sage: P.roots()
[(z2 + 1, 1), (z2, 1), (1, 1)]
sage: P.roots(multiplicities=False)
[z2 + 1, z2, 1]
sage: L = 3
sage: [(1+w*x)^L +1 for w in P.roots(multiplicities=False)]
sage: polys = [(1+w*x)^L +1 for w in P.roots(multiplicities=False)] ; polys
[x^3 + z2*x^2 + (z2 + 1)*x, x^3 + (z2 + 1)*x^2 + z2*x, x^3 + x^2 + x]
sage: reduce(gcd, polys)
x
sage: L = 2
sage: polys = [(1+w*x)^L +1 for w in P.roots(multiplicities=False)] ; polys
[z2*x^2, (z2 + 1)*x^2, x^2]
sage: reduce(gcd, polys)
x^2
</code></pre>
https://ask.sagemath.org/question/42307/polynomials-with-roots-of-unity-as-coefficients/?comment=42311#post-id-42311@tmonteil, thanks for the answer. Is it easy to do the same gcd computation in algebraic closure of finite field, $F_2$ for example?Thu, 10 May 2018 21:48:45 -0500https://ask.sagemath.org/question/42307/polynomials-with-roots-of-unity-as-coefficients/?comment=42311#post-id-42311Answer by Emmanuel Charpentier for <p>I have three polynomials $(1+x)^L+1$, $(1+\omega x)^L+$ and $(1+\omega^2 x)^L+1$ where $\omega$ is cube root of unity and L is some constant, for example, 2 or 3. I want to find the GCD of these polynomials. How do I define these polynomials in sagemath with coefficients as roots of unity?</p>
https://ask.sagemath.org/question/42307/polynomials-with-roots-of-unity-as-coefficients/?answer=42308#post-id-42308Brute force works well here : Let's first get these roots of the unity as algebraics :
sage: Rt.<t>=PolynomialRing(QQbar)
sage: Lc=[s[0] for s in (t^3-1).roots()];Lc
[1,
-0.500000000000000? - 0.866025403784439?*I,
-0.500000000000000? + 0.866025403784439?*I]
Use those coefficients to create the needed polynomials :
sage: Rx.<x>=PolynomialRing(QQbar)
sage: L=3
sage: Lp=[(1+c*x)^L for c in Lc];Lp
[x^3 + 3*x^2 + 3*x + 1,
(1.000000000000000? + 0.?e-18*I)*x^3 + (-1.500000000000000? + 2.598076211353316?*I)*x^2 + (-1.500000000000000? - 2.598076211353316?*I)*x + 1,
(1.000000000000000? + 0.?e-18*I)*x^3 + (-1.500000000000000? - 2.598076211353316?*I)*x^2 + (-1.500000000000000? + 2.598076211353316?*I)*x + 1]
But of course :
sage: reduce(lambda a,b:gcd(a,b), Lp)
1
Now, you can also do the same in SR :
sage: var("x")
x
Coefficients :
sage: Lc=[s.rhs() for s in solve(x^3-1,x)]
sage: Lc
[1/2*I*sqrt(3) - 1/2, -1/2*I*sqrt(3) - 1/2, 1]
Polynomials :
sage: Lp=[(1+c*x)^L for c in Lc];Lp
[-1/8*(x*(-I*sqrt(3) + 1) - 2)^3, -1/8*(x*(I*sqrt(3) + 1) - 2)^3, (x + 1)^3]
And again :
sage: reduce(lambda a,b:gcd(a,b), Lp)
1
HTH,
Thu, 10 May 2018 16:35:44 -0500https://ask.sagemath.org/question/42307/polynomials-with-roots-of-unity-as-coefficients/?answer=42308#post-id-42308