Cyclotomic Polynomials
By Alan Crowe (Wed Dec 27, 2006 at 01:10:24 PM EST) maths, algebra, polynomials, cyclotomic polynomials, roots of unity (all tags)
I recently had a little success with trying to understand the Möbius transform. I noticed that cyclotomic polynomials have the same technical issue of looking at divisors, so I thought I would have a go at computing one of them, while I was on a roll.

I tried f12, the twelfth cyclotomic polynomial. Let ζ be the primitive twelfth root of unity.
f12 = (x - ζ)(x - ζ5)(x-ζ7)(x-ζ11)
is the definition. However the surprising thing about cyclotomic polynomials is that the coefficients are all rationals (integers infact), none of the surds from taking twelfth roots escape to pollute the polynominal. My book proves this by giving an inductive construction.

Start from x12-1 and divide by all of f1, f2, f3, f4, f6, the point being that 1,2,3,4, and 6 are divisors of 12.

Now I've always believed that ζ has a twelfth degree minimum polynomial and that the field extension [Q(ζ):Q] is twelfth degree. It is "just obvious", I never really thought about it, and I don't spot what is coming.

Starting as I said from x12-1 I divide by x-1 getting

x11+ x10+ x9+ x8+ x7+ x6+ x5+ x4+ x3+ x2+ x+ 1
Next comes division by x+1 leaving
x10+ x8+ x6+ x4+ x2+ 1
Dividing by x2+x+1 requires care, so I get
x8- x7+ x6+ x2- x+ 1
without seeing the danger. Dividing by (x2+1) is an easier calculation but I'm feeling smug that things are going well so I'm not smelling the burning insulation yet. Finally division,by x2-x+1 reveals
x4- x2+1

Oh shit! How the fuck did that happen. ζ is supposed to be a twelfth root, what is it doing satisfying a fourth degree polynomial?

Starting to panic I fire up my trusty REPL and start coding up numerical calculations. Soon it is very clear. The twelfth root of unity does satisfy a fourth degree polynomial. [Q(ζ):Q] = 4 not 12. I don't understand mathematics.

Cyclotomic Polynomials eh? by MisterQueue (2.00 / 0) #1 Wed Dec 27, 2006 at 01:27:16 PM EST
I had one of those once... the doctor had to wrestle it out of my chest with two hands after he cut open my ribcage to remove it.

Said it fought like a bear, but stung like a bee.

It skittered across the floor and down the hall where it started a small family in the rafters of the creaky old Hospital of Guadalupe where I had chosen to have the procedure done (it was cheaper there.)

True story.

-Q
--------------
It shone, pale as bone,
As I stood there alone.

creaky old Hospital of Guadalupe by Alan Crowe (4.00 / 1) #2 Wed Dec 27, 2006 at 01:58:11 PM EST
Do you have the ICBM co-ordinates of the hospital? We need to nuke the site from orbit, it's the only way to be sure.

[ Parent ]
I used to yes, by MisterQueue (4.00 / 1) #3 Wed Dec 27, 2006 at 02:11:02 PM EST
but this cantankerous old man accosted me one day whilst selling my wares on the streets of Pompeii. Needless to say, I was none too happy.

At this point I'm sure it's best we simply accept our fate.

Also, you forgot to carry the two.

-Q
--------------
It shone, pale as bone,
As I stood there alone.

[ Parent ]