What's next in this sequence of polynomials?
  • x-1
  • x+1
  • x2+x+1
  • x2+1
  • x4+x3+x2+x+1

These are the first 5 cyclotomic polynomials. The nth cyclotomic polynomial is
cycn(x)=(x-e1)(x-e2)...(x-er)
where e1,e2,...,er are the primitive complex nth roots of unity.

It follows from the definition that the degree of cycn is phi(n), where phi is the Euler Phi function.

In the case of a prime number p we get
cycp(x)=(xp-1)/(x-1)=xp-1+xp-2+...+x+1
(because all the pth roots of unity are primitive except for 1).

The cyclotomic polynomials can be calculated recursively because of the formula
xn-1=product over all d|n of cycd(x)

This formula follows because the roots of xn-1 are exactly the nth roots of unity. By Lagrange's Theorem each nth root of unity is a primitive dth root of unity for some divisor d of n. On the other hand clearly any such primitive dth root of unity is an nth root of unity.

Let's do this for an example, n=6. The divisors of 6 are 1,2,3,6 so the formula tells us
x6-1=cyc1(x)cyc2(x)cyc3(x)cyc6(x)
=(x-1)(x+1)(x2+x+1)cyc6(x)
=(x2-1)(x2+x+1)cyc6(x)
=(x4+x3-x+1)cyc6(x)

We obtain from this that cyc6(x)=x2-x+1.

A couple more interesting properties of cycn(x)

Apparently my amazing "proof" that all coefficients of a cyclotomic polynomial are -1, 0 or 1 is flawed, since the 105th cyclotomic polynomial has this sequence of coefficients (generated using GAP):
[ 1, 1, 1, 0, 0, -1, -1, -2, -1, -1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, -1, 0, -1, 0, -1, 0, -1, 0, -1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, -1, -1, -2, -1, -1, 0, 0, 1, 1, 1 ],
which contains -2. MathWorld explains that this is due to 105 = 3*5*7 being a product of 3 odd primes (clearly it is the first such).

Instead, I give you the following trivial fact about cyclotomic polynomials. Their sequence of coefficients is a palindrome: it reads the same in both directions, possibly changing signs on all coefficients! This is less astounding when you think about it. Here's why the sequence of coefficients of a cyclotomic polynomial is a palindrome...

Log in or registerto write something here or to contact authors.