Cyclotomic polynomial
In mathematics, more specifically in algebra, the nth cyclotomic polynomial, for any positive integer n, is the unique irreducible polynomial with integer coefficients, which is a divisor of and is not a divisor of for any k < n. Its roots are the nth primitive roots of unity , where k runs over the integers lower than n and coprime to n. In other words, the nth cyclotomic polynomial is equal to
It may also be defined as the monic polynomial with integer coefficients, which is the minimal polynomial over the field of the rational numbers of any primitive nth-root of unity ( is an example of such a root).
Examples
If n is a prime number then
If n=2p where p is an odd prime number then
For n up to 30, the cyclotomic polynomials are:^{[1]}
The case of the 105th cyclotomic polynomial is interesting because 105 is the lowest integer that is the product of three distinct odd prime numbers and this polynomial is the first one that has a coefficient greater than 1:
Properties
Fundamental tools
The cyclotomic polynomials are monic polynomials with integer coefficients that are irreducible over the field of the rational numbers. Except for n equal to 1 or 2, they are palindromic polynomials of even degree.
The degree of , or in other words the number of nth primitive roots of unity, is , where is Euler's totient function.
The fact that is an irreducible polynomial of degree in the ring is a nontrivial result due to Gauss.^{[2]} Depending on the chosen definition, it is either the value of the degree or the irreducibility which is a nontrivial result. The case of prime n is easier to prove than the general case, thanks to Eisenstein's criterion.
A fundamental relation involving cyclotomic polynomials is
which means that each n-th root of unity is a primitive d-th root of unity for a unique d dividing n.
The Möbius inversion formula allows the expression of as an explicit rational fraction:
where is the Möbius function.
The cyclotomic polynomial may be computed by (exactly) dividing by the cyclotomic polynomials of the proper divisors of n previously computed recursively by the same method:
This formula allows to compute on a computer for any n, as soon as integer factorization and division of polynomials are available. Many computer algebra systems have a built in function to compute the cyclotomic polynomials. For example this function is called by typing cyclotomic_polynomial(n,'x')
in Sage, numtheory[cyclotomic](n,x);
in Maple, and Cyclotomic[n,x]
in Mathematica.
Easy cases for the computation
As noted above, if n is a prime number then
If n is an odd integer greater than one, then
In particular, if n=2p is twice an odd prime then (as noted above)
If n=p^{m} is a prime power (where p is prime), then
More generally, if n=q^{m}r with m>1 then
This formula may be iterated to get a simple expression of any cyclotomic polynomial in term of a cyclotomic polynomial of square free index: If q is the product of the prime divisors of n (its radical), then^{[3]}
This allows to give formulas for the nth cyclotomic polynomial when n has at most one odd prime factor: If p is an odd prime number, and h and k are positive integers, then:
For the other values of n, the computation of the nth cyclotomic polynomial is similarly reduced to that of where q is the product of the distinct odd prime divisors of n. To deal with this case, one has that, for p relatively prime to n,^{[4]}
Integers appearing as coefficients
The problem of bounding the magnitude of the coefficients of the cyclotomic polynomials has been the object of a number of research papers.
If n has at most two distinct odd prime factors, then Migotti showed that the coefficients of are all in the set {1, −1, 0}.^{[5]}
The first cyclotomic polynomial for a product of 3 different odd prime factors is it has a coefficient −2 (see its expression above). The converse isn't true: = only has coefficients in {1, −1, 0}.
If n is a product of more odd different prime factors, the coefficients may increase to very high values. E.g., = has coefficients running from −22 to 22, = , the smallest n with 6 different odd primes, has coefficients up to ±532.
Let A(n) denote the maximum absolute value of the coefficients of Φ_{n}. It is known that for any positive k, the number of n up to x with A(n) > n^{k} is at least c(k)⋅x for a positive c(k) depending on k and x sufficiently large. In the opposite direction, for any function ψ(n) tending to infinity with n we have A(n) bounded above by n^{ψ(n)} for almost all n.^{[6]}
Gauss's formula
Let n be odd, square-free, and greater than 3. Then^{[7]}^{[8]}
where both A_{n}(z) and B_{n}(z) have integer coefficients, A_{n}(z) has degree φ(n)/2, and B_{n}(z) has degree φ(n)/2 − 2. Furthermore, A_{n}(z) is palindromic when its degree is even; if its degree is odd it is antipalindromic. Similarly, B_{n}(z) is palindromic unless n is composite and ≡ 3 (mod 4), in which case it is antipalindromic.
The first few cases are
Lucas's formula
Let n be odd, square-free and greater than 3. Then^{[9]}
where both U_{n}(z) and V_{n}(z) have integer coefficients, U_{n}(z) has degree φ(n)/2, and V_{n}(z) has degree φ(n)/2 − 1. This can also be written
If n is even, square-free and greater than 2 (this forces n to be ≡ 2 (mod 4)),
where both C_{n}(z) and D_{n}(z) have integer coefficients, C_{n}(z) has degree φ(n), and D_{n}(z) has degree φ(n) − 1. C_{n}(z) and D_{n}(z) are both palindromic.
The first few cases are:
Prime Cyclotomic numbers
{{ safesubst:#invoke:Unsubst||$N=Unreferenced section |date=__DATE__ |$B= {{ safesubst:#invoke:Unsubst||$N=Unreferenced |date=__DATE__ |$B= {{#invoke:Message box|ambox}} }} }}
The prime numbers of the form (with n, b integers, n > 2, b > 1) are listed in Template:Oeis, or all primes in Template:Oeis.
The list is about the smallest integer b > 1 which is a prime (see Template:Oeis), it is conjectured that such b exists for all positive integer n (See Bunyakovsky conjecture). (For that to allow b = 1, see Template:Oeis. In fact, b = 1 if and only if n is a prime or a prime power, so you can see this sequence for all positive integer n which is neither a prime nor a prime power. For n is a prime, see Template:Oeis).
The list is about all n ≤ 300 (The b-file of A117544 lists all n ≤ 1000, but it lists 1 if and only if n is a prime or prime power)
n | +1 | +2 | +3 | +4 | +5 | +6 | +7 | +8 | +9 | +10 | +11 | +12 | +13 | +14 | +15 | +16 | +17 | +18 | +19 | +20 |
0+ | 3 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 5 | 2 | 2 | 2 | 2 | 2 | 2 | 6 | 2 | 4 |
20+ | 3 | 2 | 10 | 2 | 22 | 2 | 2 | 4 | 6 | 2 | 2 | 2 | 2 | 2 | 14 | 3 | 61 | 2 | 10 | 2 |
40+ | 14 | 2 | 15 | 25 | 11 | 2 | 5 | 5 | 2 | 6 | 30 | 11 | 24 | 7 | 7 | 2 | 5 | 7 | 19 | 3 |
60+ | 2 | 2 | 3 | 30 | 2 | 9 | 46 | 85 | 2 | 3 | 3 | 3 | 11 | 16 | 59 | 7 | 2 | 2 | 22 | 2 |
80+ | 21 | 61 | 41 | 7 | 2 | 2 | 8 | 5 | 2 | 2 | 11 | 4 | 2 | 6 | 44 | 4 | 12 | 2 | 63 | 20 |
100+ | 22 | 13 | 3 | 4 | 7 | 10 | 2 | 3 | 12 | 5 | 12 | 40 | 86 | 14 | 268 | 5 | 24 | 6 | 148 | 2 |
120+ | 43 | 2 | 12 | 6 | 127 | 2 | 2 | 102 | 2 | 3 | 7 | 3 | 2 | 5 | 33 | 56 | 13 | 8 | 11 | 4 |
140+ | 5 | 46 | 3 | 6 | 2 | 18 | 13 | 4 | 5 | 2 | 29 | 9 | 14 | 3 | 62 | 4 | 56 | 2 | 189 | 20 |
160+ | 3 | 93 | 30 | 12 | 2 | 49 | 44 | 18 | 24 | 2 | 22 | 14 | 60 | 2 | 63 | 17 | 47 | 16 | 304 | 35 |
180+ | 5 | 9 | 156 | 2 | 43 | 24 | 41 | 96 | 8 | 40 | 74 | 2 | 118 | 70 | 2 | 10 | 33 | 5 | 156 | 26 |
200+ | 41 | 2 | 294 | 16 | 11 | 5 | 127 | 2 | 103 | 25 | 46 | 41 | 206 | 6 | 167 | 88 | 39 | 12 | 105 | 15 |
220+ | 15 | 14 | 183 | 7 | 77 | 92 | 72 | 15 | 606 | 13 | 66 | 9 | 602 | 2 | 17 | 3 | 46 | 52 | 223 | 28 |
240+ | 115 | 19 | 209 | 61 | 67 | 11 | 15 | 5 | 27 | 25 | 37 | 23 | 69 | 2 | 3 | 120 | 52 | 17 | 69 | 28 |
260+ | 2 | 48 | 104 | 9 | 14 | 20 | 26 | 25 | 41 | 20 | 6 | 55 | 41 | 89 | 17 | 3 | 338 | 30 | 3 | 2 |
280+ | 217 | 34 | 13 | 69 | 112 | 14 | 3 | 5 | 315 | 65 | 15 | 196 | 136 | 22 | 44 | 2 | 56 | 16 | 219 | 4 |
For all positive integers n ≤ 1000, the largest three bs are 2706, 2061, and 2042, when n is 545, 601, and 943, and there are 17 values of n ≤ 1000 such that b > 1000.
In fact, if p is a prime, than is and a repunit number in base b, (111111...111111)_{b}, so the following is a list of the smallest b > 1 which is a prime. (see Template:Oeis)
The list is about the first 100 primes p. (The b-file of A066180 lists the first 200 primes p, up to 1223)
p | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 | 37 | 41 | 43 | 47 | 53 | 59 | 61 | 67 | 71 |
min b | 2 | 2 | 2 | 2 | 5 | 2 | 2 | 2 | 10 | 6 | 2 | 61 | 14 | 15 | 5 | 24 | 19 | 2 | 46 | 3 |
p | 73 | 79 | 83 | 89 | 97 | 101 | 103 | 107 | 109 | 113 | 127 | 131 | 137 | 139 | 149 | 151 | 157 | 163 | 167 | 173 |
min b | 11 | 22 | 41 | 2 | 12 | 22 | 3 | 2 | 12 | 86 | 2 | 7 | 13 | 11 | 5 | 29 | 56 | 30 | 44 | 60 |
p | 179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 | 227 | 229 | 233 | 239 | 241 | 251 | 257 | 263 | 269 | 271 | 277 | 281 |
min b | 304 | 5 | 74 | 118 | 33 | 156 | 46 | 183 | 72 | 606 | 602 | 223 | 115 | 37 | 52 | 104 | 41 | 6 | 338 | 217 |
p | 283 | 293 | 307 | 311 | 313 | 317 | 331 | 337 | 347 | 349 | 353 | 359 | 367 | 373 | 379 | 383 | 389 | 397 | 401 | 409 |
min b | 13 | 136 | 220 | 162 | 35 | 10 | 218 | 19 | 26 | 39 | 12 | 22 | 67 | 120 | 195 | 48 | 54 | 463 | 38 | 41 |
p | 419 | 421 | 431 | 433 | 439 | 443 | 449 | 457 | 461 | 463 | 467 | 479 | 487 | 491 | 499 | 503 | 509 | 521 | 523 | 541 |
min b | 17 | 808 | 404 | 46 | 76 | 793 | 38 | 28 | 215 | 37 | 236 | 59 | 15 | 514 | 260 | 498 | 6 | 2 | 95 | 3 |
Applications
Using , one can give an elementary proof for the infinitude of primes congruent to 1 modulo n,^{[10]} which is a special case of Dirichlet's theorem on arithmetic progressions.
See also
Notes
- ↑ OEIS A013595.
- ↑ Template:Lang Algebra
- ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.
- ↑ Template:Cite web
- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ Meier (2008)
- ↑ Gauss, DA, Articles 356-357
- ↑ Riesel, pp. 315-316, p. 436
- ↑ Riesel, pp. 309-315, p. 443
- ↑ S. Shirali. Number Theory. Orient Blackswan, 2004. p. 67. ISBN 81-7371-454-1
References
Gauss's book Disquisitiones Arithmeticae has been translated from Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.
- {{#invoke:citation/CS1|citation
|CitationClass=book }}
- {{#invoke:citation/CS1|citation
|CitationClass=book }}
- {{#invoke:citation/CS1|citation
|CitationClass=book }}
- {{#invoke:citation/CS1|citation
|CitationClass=citation }}
- {{#invoke:citation/CS1|citation
|CitationClass=book }}
External links
- Weisstein, Eric W., "Cyclotomic polynomial", MathWorld.
- {{#invoke:citation/CS1|citation
|CitationClass=citation }}