Namespaces
Variants
Actions

Difference between revisions of "Cyclotomic polynomials"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (fixing dots)
 
(2 intermediate revisions by 2 users not shown)
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c0275801.png" /> that satisfy the relation
+
The polynomials $  \Phi _ {1} , \Phi _ {2}, \dots $
 +
that satisfy the relation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c0275802.png" /></td> </tr></table>
+
$$
 +
x  ^ {n} - = \prod _ {d \mid  n } \Phi _ {d} ( x),
 +
$$
  
where the product is taken over all positive divisors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c0275803.png" /> of the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c0275804.png" />, including <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c0275805.png" /> itself. Over the field of complex numbers one has
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c0275806.png" /></td> </tr></table>
+
$$
 +
\Phi _ {n} ( x)  = \
 +
\prod _  \zeta  ( x - \zeta ),
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c0275807.png" /> ranges over the primitive <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c0275808.png" />-th roots of unity (cf. [[Primitive root|Primitive root]]). The degree of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c0275809.png" /> is the number of integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758010.png" /> among <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758011.png" /> that are relatively prime with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758012.png" />. The polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758013.png" /> can be computed recursively by dividing the polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758014.png" /> by the product of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758015.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758016.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758017.png" />. The coefficients lie in the prime field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758018.png" />; in case of characteristic zero, they are integers. Thus,
+
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,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758019.png" /></td> </tr></table>
+
$$
 +
\Phi _ {1} ( x)  = x - 1 ,\  \Phi _ {2} ( x)  = x + 1 ,\ \
 +
\Phi _ {3} ( x)  = x  ^ {2} + x + 1 .
 +
$$
  
If, moreover, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758020.png" /> is prime, then
+
If, moreover, $  n= p $
 +
is prime, then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758021.png" /></td> </tr></table>
+
$$
 +
\Phi _ {p} ( x)  =
 +
\frac{x  ^ {p} - 1 }{x - 1 }
 +
  = x ^ {p - 1 }
 +
+ \dots + x + 1 .
 +
$$
  
The polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758022.png" /> can be explicitly expressed using the [[Möbius function|Möbius function]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758023.png" />:
+
The polynomial $  \Phi _ {n} ( x) $
 +
can be explicitly expressed using the [[Möbius function|Möbius function]] $  \mu $:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758024.png" /></td> </tr></table>
+
$$
 +
\Phi _ {n} ( x)  = \prod _ {d \mid  n }
 +
( x  ^ {d} - 1 ) ^ {\mu ( n / d ) } .
 +
$$
  
 
For example,
 
For example,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758025.png" /></td> </tr></table>
+
$$
 +
\Phi _ {12} ( x) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758026.png" /></td> </tr></table>
+
$$
 +
= \
 +
( x  ^ {12} - 1) ( x  ^ {6} - 1)  ^ {-1} ( x  ^ {4} - 1)  ^ {-1} ( x  ^ {3} - 1)  ^ {0} ( x  ^ {2} - 1) ( x - 1)  ^ {0 } =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758027.png" /></td> </tr></table>
+
$$
 +
= \
  
All the polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758028.png" /> are irreducible over the field of rational numbers, but they may be reducible over finite prime fields. Thus, the relation
+
\frac{x  ^ {6} + 1 }{x  ^ {2} + 1 }
 +
  = x  ^ {4} - x  ^ {2} + 1 .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758029.png" /></td> </tr></table>
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758030.png" />, which gives all primitive <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758031.png" />-th roots of unity, is known as the equation of division of the circle. The solution of this equation in trigonometric form is
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758032.png" /></td> </tr></table>
+
$$
 +
r _ {k}  = \cos 
 +
\frac{2 k \pi }{n}
 +
+ i  \sin 
 +
\frac{2 k \pi }{n}
 +
  = \
 +
e ^ {2 k \pi i /n } ,
 +
$$
  
where the fraction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758033.png" /> is irreducible, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758034.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758035.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758036.png" />-gon, or with the equivalent problem of subdividing the circle into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758037.png" /> equal parts; the latter problem can be solved using a straightedge and a pair of compasses if and only if the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758038.png" /> is solvable in quadratic radicals. It was shown by C.F. Gauss in 1801 that this condition is satisfied if and only if
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758039.png" /></td> </tr></table>
+
$$
 +
= 2  ^ {m} p _ {1} \cdots p _ {s} ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758040.png" /> is a non-negative integer and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758041.png" /> are pairwise different prime numbers of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758042.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758043.png" /> is a non-negative integer.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758044.png" /> is equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758045.png" />, the value (at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758046.png" />) of the Euler <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758047.png" />-function (cf. [[Euler function|Euler function]]).
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758048.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758049.png" /> a non-negative integer are called Fermat primes, these numbers are related to a problem of Fermat: When is the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758050.png" />, with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758051.png" /> as before, prime? The only small Fermat primes are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758052.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758053.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758054.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758055.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027580/c02758056.png" /> (cf. [[#References|[a1]]], pp. 183-185).
+
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 &amp; 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 &amp; Hall  (1973)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  H. Davenport,  "Multiplicative number theory" , Springer  (1980)</TD></TR></table>

Latest revision as of 05:18, 7 March 2022


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} \cdots 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)
How to Cite This Entry:
Cyclotomic polynomials. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Cyclotomic_polynomials&oldid=16160
This article was adapted from an original article by I.V. Proskuryakov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article