Ask Your Question

Evaluating polynomials in Z[x] at roots of unity.

asked 2019-03-23 06:26:52 -0500

joakim_uhlin gravatar image

Suppose that I have a polynomial $p(x)$ with integer coeffcients, then I can easily evaluate this at some integer to get an exact answer. That is, I can write something like

sage: p=1+x+2*x^2+x^3+x^4
sage: p(2)

But If I instead want to evaluate this polynomial at a root of unity (I take $w$ to be a primitive $5$:th root of unity in the example below but any root of unity would do), then I may write say

sage: w = e^(2*pi*i/5)
sage: p(w)
1/256*(sqrt(5) + I*sqrt(2*sqrt(5) + 10) - 1)^4 + 1/64*(sqrt(5) + I*sqrt(2*sqrt(5) + 10) - 1)^3 + 1/8*(sqrt(5) + I*sqrt(2*sqrt(5) + 10) - 1)^2 + 1/4*sqrt(5) + 1/4*I*sqrt(2*sqrt(5) + 10) + 3/4

Which is a correct answer but written in a very complicated form. Alternatively, I can write

sage: K.<z> = CyclotomicField(5)
sage: w=CC(z)
sage: p(w)
-0.809016994374947 + 0.587785252292473*I

which is an approximation of the correct answers. In the above case, we actually have $p(w)=w^2$ and I am wondering if there is an easy way to always obtain such an answer. For a general $p(x)$ with integer coefficients and $w$ that is a primitive $n$:th root of unity, we can write $p(w)$ on the form

$$a_0+a_1 w + a_2 w^2 + \dots +a_{n-1} w^{n-1}$$

where the $a_i$:s are integers. Is there a good way to get the $p(w)$ on this form in Sage?

edit retag flag offensive close merge delete



By the way, the degree of $w$ is $\varphi(n)$ in general, so there is an expansion with fewer powers.

rburing gravatar imagerburing ( 2019-03-23 08:21:23 -0500 )edit

2 answers

Sort by ยป oldest newest most voted

answered 2019-03-23 06:49:41 -0500

rburing gravatar image

updated 2019-03-23 06:53:27 -0500

Yes, you can do it like this:

sage: R.<x> = PolynomialRing(ZZ)
sage: p = 1+x+2*x^2+x^3+x^4
sage: K.<w> = CyclotomicField(5)
sage: p(w)

Here it's important that x is the generator of a polynomial ring. It doesn't work when x is symbolic, as you noticed. If you have to start with a symbolic polynomial, then you can convert it first using the polynomial() method:

sage: var('y')
sage: q = 1+y+2*y^2+y^3+y^4
sage: q.polynomial(ZZ)(w)
edit flag offensive delete link more

answered 2019-03-23 09:33:31 -0500

vdelecroix gravatar image

updated 2019-03-23 09:35:24 -0500

Using GAP's universal cyclotomic field under the hood

sage: x = polygen(ZZ)
sage: p = 1+x+2*x^2+x^3+x^4
sage: p(E(5))

In GAP (and Sagemath) E(k) is the primitive k-th root of unity. The advantage of this approach is that you can mix distinct roots of unity and GAP will take care of any simplification

sage: R.<x,y> = PolynomialRing(ZZ)
sage: p = x*y + x^2 - 2*y^3
sage: p(E(3), E(5))
-E(15) + E(15)^4 - E(15)^7 + E(15)^8 - E(15)^13 + 2*E(15)^14
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2019-03-23 06:26:52 -0500

Seen: 55 times

Last updated: Mar 23