Difference between revisions of "Cyclotomic polynomials"
(Importing text file) |
Ulf Rehmann (talk | contribs) m (tex encoded by computer) |
||
Line 1: | Line 1: | ||
+ | <!-- | ||
+ | c0275801.png | ||
+ | $#A+1 = 56 n = 0 | ||
+ | $#C+1 = 56 : ~/encyclopedia/old_files/data/C027/C.0207580 Cyclotomic polynomials, | ||
+ | Automatically converted into TeX, above some diagnostics. | ||
+ | Please remove this comment and the {{TEX|auto}} line below, | ||
+ | if TeX found to be correct. | ||
+ | --> | ||
+ | |||
+ | {{TEX|auto}} | ||
+ | {{TEX|done}} | ||
+ | |||
''circular polynomials'' | ''circular polynomials'' | ||
− | The polynomials | + | The polynomials $ \Phi _ {1} , \Phi _ {2} \dots $ |
+ | that satisfy the relation | ||
− | + | $$ | |
+ | x ^ {n} - 1 = \prod _ {d \mid n } \Phi _ {d} ( x), | ||
+ | $$ | ||
− | where the product is taken over all positive divisors | + | where the product is taken over all positive divisors $ d $ |
+ | of the number $ n $, | ||
+ | including $ n $ | ||
+ | itself. Over the field of complex numbers one has | ||
− | + | $$ | |
+ | \Phi _ {n} ( x) = \ | ||
+ | \prod _ \zeta ( x - \zeta ), | ||
+ | $$ | ||
− | where | + | where $ \zeta $ |
+ | ranges over the primitive $ n $- | ||
+ | th roots of unity (cf. [[Primitive root|Primitive root]]). The degree of $ \Phi _ {n} ( x) $ | ||
+ | is the number of integers $ k $ | ||
+ | among $ 1 \dots n $ | ||
+ | that are relatively prime with $ n $. | ||
+ | The polynomials $ \Phi _ {n} ( x) $ | ||
+ | can be computed recursively by dividing the polynomial $ x ^ {n} - 1 $ | ||
+ | by the product of all $ \Phi _ {d} ( x) $, | ||
+ | $ d < n $, | ||
+ | $ d \mid n $. | ||
+ | The coefficients lie in the prime field $ \mathbf Q $; | ||
+ | in case of characteristic zero, they are integers. Thus, | ||
− | + | $$ | |
+ | \Phi _ {1} ( x) = x - 1 ,\ \Phi _ {2} ( x) = x + 1 ,\ \ | ||
+ | \Phi _ {3} ( x) = x ^ {2} + x + 1 . | ||
+ | $$ | ||
− | If, moreover, | + | If, moreover, $ n= p $ |
+ | is prime, then | ||
− | + | $$ | |
+ | \Phi _ {p} ( x) = | ||
+ | \frac{x ^ {p} - 1 }{x - 1 } | ||
+ | = x ^ {p - 1 } | ||
+ | + \dots + x + 1 . | ||
+ | $$ | ||
− | The polynomial | + | The polynomial $ \Phi _ {n} ( x) $ |
+ | can be explicitly expressed using the [[Möbius function|Möbius function]] $ \mu $: | ||
− | + | $$ | |
+ | \Phi _ {n} ( x) = \prod _ {d \mid n } | ||
+ | ( x ^ {d} - 1 ) ^ {\mu ( n / d ) } . | ||
+ | $$ | ||
For example, | For example, | ||
− | + | $$ | |
+ | \Phi _ {12} ( x) = | ||
+ | $$ | ||
− | + | $$ | |
+ | = \ | ||
+ | ( x ^ {12} - 1) ( x ^ {6} - 1) ^ {-} 1 ( x ^ {4} - 1) ^ {-} 1 ( x ^ {3} - 1) ^ {0} ( x ^ {2} - 1) ( x - 1) ^ {0\ } = | ||
+ | $$ | ||
− | + | $$ | |
+ | = \ | ||
− | + | \frac{x ^ {6} + 1 }{x ^ {2} + 1 } | |
+ | = x ^ {4} - x ^ {2} + 1 . | ||
+ | $$ | ||
− | + | All the polynomials $ \Phi _ {n} ( x) $ | |
+ | are irreducible over the field of rational numbers, but they may be reducible over finite prime fields. Thus, the relation | ||
+ | |||
+ | $$ | ||
+ | \Phi _ {12} ( x) = x ^ {4} - x ^ {2} + 1 = ( x ^ {2} + 5x + 1 ) | ||
+ | ( x ^ {2} - 5x + 1 ) | ||
+ | $$ | ||
is valid over the field of residues modulo 11. | is valid over the field of residues modulo 11. | ||
− | The equation | + | The equation $ \Phi _ {n} ( x) = 0 $, |
+ | which gives all primitive $ n $- | ||
+ | th roots of unity, is known as the equation of division of the circle. The solution of this equation in trigonometric form is | ||
− | + | $$ | |
+ | r _ {k} = \cos | ||
+ | \frac{2 k \pi }{n} | ||
+ | + i \sin | ||
+ | \frac{2 k \pi }{n} | ||
+ | = \ | ||
+ | e ^ {2 k \pi i /n } , | ||
+ | $$ | ||
− | where the fraction | + | where the fraction $ k / n $ |
+ | is irreducible, i.e. $ k $ | ||
+ | and $ n $ | ||
+ | are relatively prime. The solution of the equation of division of the circle by radicals is closely connected with the problem of constructing a regular $ n $- | ||
+ | gon, or with the equivalent problem of subdividing the circle into $ n $ | ||
+ | equal parts; the latter problem can be solved using a straightedge and a pair of compasses if and only if the equation $ \Phi _ {n} ( x) = 0 $ | ||
+ | is solvable in quadratic radicals. It was shown by C.F. Gauss in 1801 that this condition is satisfied if and only if | ||
− | + | $$ | |
+ | n = 2 ^ {m} p _ {1} \dots p _ {s} , | ||
+ | $$ | ||
− | where | + | where $ m $ |
+ | is a non-negative integer and $ p _ {1} \dots p _ {s} $ | ||
+ | are pairwise different prime numbers of the form $ 2 ^ {2 ^ {k} } + 1 $, | ||
+ | where $ k $ | ||
+ | is a non-negative integer. | ||
====References==== | ====References==== | ||
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> B.L. van der Waerden, "Algebra" , '''1–2''' , Springer (1967–1971) (Translated from German)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> A.K. Sushkevich, "Foundations of higher algebra" , Moscow-Leningrad (1941) (In Russian)</TD></TR></table> | <table><TR><TD valign="top">[1]</TD> <TD valign="top"> B.L. van der Waerden, "Algebra" , '''1–2''' , Springer (1967–1971) (Translated from German)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> A.K. Sushkevich, "Foundations of higher algebra" , Moscow-Leningrad (1941) (In Russian)</TD></TR></table> | ||
− | |||
− | |||
====Comments==== | ====Comments==== | ||
− | The degree of | + | The degree of $ \Phi _ {n} ( x) $ |
+ | is equal to $ \phi ( n) $, | ||
+ | the value (at $ n $) | ||
+ | of the Euler $ \phi $- | ||
+ | function (cf. [[Euler function|Euler function]]). | ||
− | Prime numbers of the form | + | Prime numbers of the form $ 2 ^ {2 ^ {k} } + 1 $ |
+ | with $ k $ | ||
+ | a non-negative integer are called Fermat primes, these numbers are related to a problem of Fermat: When is the number $ F _ {k} = 2 ^ {2 ^ {k} } + 1 $, | ||
+ | with $ k $ | ||
+ | as before, prime? The only small Fermat primes are $ F _ {0} $, | ||
+ | $ F _ {1} $, | ||
+ | $ F _ {2} $, | ||
+ | $ F _ {3} $, | ||
+ | $ F _ {4} $( | ||
+ | cf. [[#References|[a1]]], pp. 183-185). | ||
====References==== | ====References==== | ||
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> I. Stewart, "Galois theory" , Chapman & Hall (1973)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> H. Davenport, "Multiplicative number theory" , Springer (1980)</TD></TR></table> | <table><TR><TD valign="top">[a1]</TD> <TD valign="top"> I. Stewart, "Galois theory" , Chapman & Hall (1973)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> H. Davenport, "Multiplicative number theory" , Springer (1980)</TD></TR></table> |
Revision as of 17:32, 5 June 2020
circular polynomials
The polynomials $ \Phi _ {1} , \Phi _ {2} \dots $ that satisfy the relation
$$ x ^ {n} - 1 = \prod _ {d \mid n } \Phi _ {d} ( x), $$
where the product is taken over all positive divisors $ d $ of the number $ n $, including $ n $ itself. Over the field of complex numbers one has
$$ \Phi _ {n} ( x) = \ \prod _ \zeta ( x - \zeta ), $$
where $ \zeta $ ranges over the primitive $ n $- th roots of unity (cf. Primitive root). The degree of $ \Phi _ {n} ( x) $ is the number of integers $ k $ among $ 1 \dots n $ that are relatively prime with $ n $. The polynomials $ \Phi _ {n} ( x) $ can be computed recursively by dividing the polynomial $ x ^ {n} - 1 $ by the product of all $ \Phi _ {d} ( x) $, $ d < n $, $ d \mid n $. The coefficients lie in the prime field $ \mathbf Q $; in case of characteristic zero, they are integers. Thus,
$$ \Phi _ {1} ( x) = x - 1 ,\ \Phi _ {2} ( x) = x + 1 ,\ \ \Phi _ {3} ( x) = x ^ {2} + x + 1 . $$
If, moreover, $ n= p $ is prime, then
$$ \Phi _ {p} ( x) = \frac{x ^ {p} - 1 }{x - 1 } = x ^ {p - 1 } + \dots + x + 1 . $$
The polynomial $ \Phi _ {n} ( x) $ can be explicitly expressed using the Möbius function $ \mu $:
$$ \Phi _ {n} ( x) = \prod _ {d \mid n } ( x ^ {d} - 1 ) ^ {\mu ( n / d ) } . $$
For example,
$$ \Phi _ {12} ( x) = $$
$$ = \ ( x ^ {12} - 1) ( x ^ {6} - 1) ^ {-} 1 ( x ^ {4} - 1) ^ {-} 1 ( x ^ {3} - 1) ^ {0} ( x ^ {2} - 1) ( x - 1) ^ {0\ } = $$
$$ = \ \frac{x ^ {6} + 1 }{x ^ {2} + 1 } = x ^ {4} - x ^ {2} + 1 . $$
All the polynomials $ \Phi _ {n} ( x) $ are irreducible over the field of rational numbers, but they may be reducible over finite prime fields. Thus, the relation
$$ \Phi _ {12} ( x) = x ^ {4} - x ^ {2} + 1 = ( x ^ {2} + 5x + 1 ) ( x ^ {2} - 5x + 1 ) $$
is valid over the field of residues modulo 11.
The equation $ \Phi _ {n} ( x) = 0 $, which gives all primitive $ n $- th roots of unity, is known as the equation of division of the circle. The solution of this equation in trigonometric form is
$$ r _ {k} = \cos \frac{2 k \pi }{n} + i \sin \frac{2 k \pi }{n} = \ e ^ {2 k \pi i /n } , $$
where the fraction $ k / n $ is irreducible, i.e. $ k $ and $ n $ are relatively prime. The solution of the equation of division of the circle by radicals is closely connected with the problem of constructing a regular $ n $- gon, or with the equivalent problem of subdividing the circle into $ n $ equal parts; the latter problem can be solved using a straightedge and a pair of compasses if and only if the equation $ \Phi _ {n} ( x) = 0 $ is solvable in quadratic radicals. It was shown by C.F. Gauss in 1801 that this condition is satisfied if and only if
$$ n = 2 ^ {m} p _ {1} \dots p _ {s} , $$
where $ m $ is a non-negative integer and $ p _ {1} \dots p _ {s} $ are pairwise different prime numbers of the form $ 2 ^ {2 ^ {k} } + 1 $, where $ k $ is a non-negative integer.
References
[1] | B.L. van der Waerden, "Algebra" , 1–2 , Springer (1967–1971) (Translated from German) |
[2] | A.K. Sushkevich, "Foundations of higher algebra" , Moscow-Leningrad (1941) (In Russian) |
Comments
The degree of $ \Phi _ {n} ( x) $ is equal to $ \phi ( n) $, the value (at $ n $) of the Euler $ \phi $- function (cf. Euler function).
Prime numbers of the form $ 2 ^ {2 ^ {k} } + 1 $ with $ k $ a non-negative integer are called Fermat primes, these numbers are related to a problem of Fermat: When is the number $ F _ {k} = 2 ^ {2 ^ {k} } + 1 $, with $ k $ as before, prime? The only small Fermat primes are $ F _ {0} $, $ F _ {1} $, $ F _ {2} $, $ F _ {3} $, $ F _ {4} $( cf. [a1], pp. 183-185).
References
[a1] | I. Stewart, "Galois theory" , Chapman & Hall (1973) |
[a2] | H. Davenport, "Multiplicative number theory" , Springer (1980) |
Cyclotomic polynomials. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Cyclotomic_polynomials&oldid=46572