Cyclotomic Polynomials
Cyclotomic polynomials are polynomials whose complex roots are primitive roots of unity. They are important in algebraic number theory (giving explicit minimal polynomials for roots of unity) and Galois theory, where they furnish examples of abelian field extensions, but they also have applications in elementary number theory the proof that there are infinitely many primes congruent to mod as well as geometry (helping answer the question of which regular polygons are constructible with a ruler and compass).
Motivation
The roots of unity lie on the unit circle as the vertices of a regular -gon. If then the roots consist of These are all of the complex roots of the polynomial
The primitive roots of unity are the roots of that are not roots of for any smaller ; that is, is their multiplicative order. Which roots are these?
Let be a primitive root of unity. Then the primitive roots of unity consist of the powers with and . There are of these, where is Euler's totient function.
If and , then . If , then which is impossible, so is a primitive root of . If , then , so is not a primitive root of . This proves the statement.
There are twelve roots of unity, but only of them are primitive, namely . The other are roots of unity for some proper divisor of .
Definition
Let be the polynomial with complex coefficients defined by the formula
where .
The order of any root of unity is a divisor of (by the division algorithm—the argument is the same as the argument for orders mod p), so this definition implies that
which is a formula that will be used later.
How many polynomials with integer coefficients (PICs) divide , in the sense that for some PIC?
Here is some background info for those who have not studied this kind of number theory yet:
For any positive integer , we define the cyclotomic polynomial , where the product is taken over all primitive roots of unity, . We are told that is a PIC and that it cannot be factored into two PICs of positive degree is "irreducible"
Extra-credit question: Explain why the cyclotomic polynomials have integer coefficients.
- , so .
- , so .
- , because and
- and the only other primitive root of is , so .
- An easy shortcut for is this: every root of unity is primitive except for , so .
- For , only and are primitive. So . This could also have been derived via
Already some patterns are emerging. The argument for works for any where is prime, so . It is immediate from the definition and the result in the above section that the degree of is .
More fundamentally, notice that the coefficients of appear to be integers. Slightly more subtle is the fact that seems to be irreducible over the integers (there are no nonconstant polynomial factors of smaller degree with integer coefficients). Both of these statements will be proved in later sections.
Properties of
is a polynomial with integer coefficients, of degree . It is irreducible over the rational numbers that is, it has no nontrivial factors with rational coefficients with smaller degree than so it is the minimal polynomial of .
Show that by induction on . The base case is clear, and now suppose the result holds for all . Then The product in the parentheses is a monic polynomial with integer coefficients, by the inductive hypothesis. Now the result follows from a general divisibility lemma.
Lemma: Suppose in and and are monic polynomials with integer coefficients. Then is a monic polynomial with integer coefficients.
Proof of lemma: There is a division algorithm in that works as long as the divisor is monic. Thus we can write with or , where So and if both sides of the equation are nonzero, then the degree of the left side is clearly strictly greater than the degree of the right side, which is impossible; so both sides are zero, , and .
The proof of irreducibility is left for the final, optional section of the wiki.
Note that the coefficient of in is the negative of the sum of the primitive roots of unity, which is where is the Möbius function (see that wiki for a proof). In general it appears for small examples that the coefficients of are always or . But in fact this is not the case for all ; the smallest for which has a different coefficient is . The coefficient of and is
Formulas for
Applying Möbius inversion to the identity
gives
which is a fairly explicit formula for . It can also be used to prove general facts about relationships between various .
For a positive integer , let be the product of the distinct positive primes dividing . Then
The divisors of such that are precisely the divisors of . So
It is immediate from the theorem that
So the are determined by their values on square-free . The following theorem can be used to compute these values:
If , prime, then
There are two types of divisors of , ones divisible by and ones that are not. The former can be written as , and the latter can be written as . Splitting the product into two products gives
Compute .
By the first theorem, .
Now by the second theorem. This is
so
Applications
Here is one application to the following special case of Dirichlet's theorem on primes in arithmetic progressions. This uses a result about the prime divisors of for integer .
Given a positive integer , there exists a positive integer such that a prime divisor of for some integer is either less than or congruent to mod .
Let . Then and are relatively prime over the complex numbers, hence relatively prime over the rational numbers (by similar arguments as above). So there exist such that . Let be the product of the denominators of the coefficients of and Then clearing denominators gives , where and have integer coefficients.
Now suppose is a prime number dividing . Then , so . Now if also for some smaller positive , then and so , which is impossible. So in fact is the multiplicative order of mod . Then Fermat's little theorem implies , as desired.
For every , there are infinitely many primes congruent to mod .
Suppose there were only finitely many such primes. Let equal the product of those primes and the number where is as in the previous theorem. Now as since it is a monic polynomial, so take large enough so that .
Now for , (exercise), so is relatively prime to (all the other terms but the constant term are divisible by ). This is a contradiction of the previous theorem, since any prime dividing must divide by its construction.
Proof of Irreducibility
There are several proofs of irreducibility; the one given here is due to Schur.
First there is a lemma about products involving roots of unity.
Lemma: Let be a primitive root of unity. Then
where the product runs over pairs of distinct positive integers with .
Proof of lemma: First, where Next, note that for fixed equals times , by factoring out a and using the above identity. So the whole product equals and . This proves the lemma.
Now we show that is irreducible by reducing it to the following result:
If an integer-coefficient polynomial divides and is a root of , then so is for any prime .
Once this result has been proved, the irreducibility of follows, because any integer-coefficient factor of with a root must have all the rest of the primitive roots as well, by repeatedly applying the result.
Proof of result: Suppose is not a root. Then is nonzero, and is a product of differences of roots of unity. So it divides the giant product from the lemma, and thus must divide ; that is, is an algebraic integer.
But mod because the binomial coefficients are all divisible by for so divides because . That is, is an algebraic integer.
Putting these two together, we get is an algebraic integer. But this is a rational number, so it must be an integer. This is a contradiction since .