User:Ga ohoyt/Cyclotomic polynomials

Cyclotomic (or "circle dividing") polynomials are the irreducible factors of <math>z^n - 1\!</math> when the polynomial coefficients are restricted to the field of rational numbers. For example

<math> z^6-1 = (z^2-z+1) (z^2+z+1) (z+1) (z-1) </math>.

The cyclotomic polynomials are often written as <math>\Phi_n(z)</math>. The polynomial <math>z^n - 1\!</math> has exactly as many of these factors as there are integer factors of n:

<math> z^6 - 1 = \Phi_6(z)\Phi_3(z)\Phi_2(z)\Phi_1(z) </math>.

Finding cyclotomic polynomials

Recursive method

Cyclotomic polynomials are defined by the equation

<math>z^n - 1 = \prod_{d\,\mid\,n} \Phi_d(z)</math>.

Solving for <math>\Phi_n(z) </math>, one obtains

<math>\Phi_n(z) = \frac {z^n - 1} {\prod_{(d \ne n)\,\mid\,n} \Phi_d(z)} </math>.

One can then construct any polynomial recursively, given that <math> \Phi_1(z) = z - 1</math>:

<math>\Phi_2(z) = \frac {z^2 - 1} {z-1} = z + 1 </math>

<math>\Phi_3(z) = \frac {z^3 - 1} {z-1} = z^2+z+1 </math>

<math>\Phi_6(z) = \frac {z^6 - 1} {(z-1) (z+1) (z^2 + z + 1)} = z^2-z+1 </math>.

Direct method

For larger values of n, it is easier to use the direct formula, based on the Möbius inversion of the above formula:

<math>\Phi_n(z)=\prod_{d\,\mid n}(z^{n/d}-1)^{\mu(d)},</math>

where μ is the Möbius function. For example, one would follow these steps for n = 60:

1. Factor n.

<math> 60 = 2^2*3*5 </math>

2. Determine the square-free divisors of n, and classify them according to whether their number of prime factors are even or odd.

<math> 30 = 2*3*5 </math> (Odd)

<math> 15 = 3*5 </math> (Even)

<math> 10 = 2*5 </math> (Even)

<math> 6 = 2*3 </math> (Even)

<math> 5= 5 </math> (Odd)

<math> 3= 3 </math> (Odd)

<math> 2= 2 </math> (Odd)

<math> 1= 1 </math> (Even, since 1 is not a prime)

3. Form the factors <math> z^{n/d} - 1 </math>, putting the factors from the even class in the numerator and those from the odd class in the denominator.

<math> \Phi_{60}(z) = \frac { (z^{60}-1) (z^{10}-1) (z^6-1) (z^4-1) } { (z^{30}-1) (z^{20}-1) (z^{12}-1) (z^2-1) } </math>

<math> = \frac { (z^{30}+1) (z^2+1) } { (z^{10}+1) (z^6+1) } </math>

<math> = \frac { z^{20}-z^{10}+1 } { z^4-z^2+1 } </math>

<math> = z^{16}+z^{14}-z^{10}-z^8-z^6+z^2+1 </math>.

Construction from complex roots

It is also possible to construct a cyclotomic polynomial from the complex roots of 1:

<math>\Phi_n(z) = \prod_{k=1}^{\varphi(n)}(z-e^{\frac {2\pi k} {n} j})\;</math>

where <math>\phi(n)</math> is Euler's totient function. For example,

<math>\Phi_6(z) = (z-e^{\frac {\pi} {3} j})(z-e^{\frac {5\pi} {3} j}) = z^2-z+1.</math>

Some special cases

When p and q are odd primes,

<math>\Phi_p(z)=\frac{z^p-1}{z-1}=\sum_{k=0}^{p-1} z^k</math>

<math>\Phi_{2p}(z)=\frac{z^p+1}{z+1}=\sum_{k=0}^{p-1} (-z)^k</math>

<math>\Phi_{pq}(z)=\frac{(z^{pq}-1) (z-1)}{(z^p-1) (z^q-1)}=\frac {\sum_{k=0}^{q-1} z^{pk} } {\sum_{k=0}^{q-1} z^k}</math>