Editing Cyclotomic polynomial (section)

==Properties==

===Fundamental tools===

The cyclotomic polynomials are monic polynomials with integer coefficients that are [[irreducible polynomial|irreducible]] over the field of the rational numbers. Except for ''n'' equal to 1 or 2, they are [[Palindromic polynomial|palindrome]]s of even degree.

The degree of <math>\Phi_n</math>, or in other words the number of ''n''th primitive roots of unity, is <math>\varphi (n)</math>, where <math>\varphi</math> is [[Euler's totient function]].

The fact that <math>\Phi_n</math> is an irreducible polynomial of degree <math>\varphi (n)</math> in the [[ring (mathematics)|ring]] <math>\Z[x]</math> is a nontrivial result due to [[Carl Friedrich Gauss|Gauss]].<ref>{{Lang Algebra}}</ref> 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#Cyclotomic polynomials|Eisenstein's criterion]].

A fundamental relation involving cyclotomic polynomials is 

:<math>\begin{align} x^n - 1 
&=\prod_{1\leqslant k\leqslant n} \left(x- e^{2i\pi\frac{k}{n}} \right) \\
&= \prod_{d \mid n} \prod_{1 \leqslant k \leqslant n \atop \gcd(k, n) = d} \left(x- e^{2i\pi\frac{k}{n}} \right) \\
&=\prod_{d \mid n} \Phi_{\frac{n}{d}}(x) =  \prod_{d\mid n} \Phi_d(x).\end{align}</math>

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#Multiplicative notation|Möbius inversion formula]] allows <math>\Phi_n(x)</math> to be expressed as an explicit rational fraction:

:<math>\Phi_n(x)=\prod_{d\mid n}(x^d-1)^{\mu \left (\frac{n}{d} \right )}, </math>

where <math>\mu</math> is the [[Möbius function]].

This provides a [[Recursive definition|recursive formula]] for the cyclotomic polynomial <math>\Phi_{n}(x)</math>, which may be computed by [[Polynomial long division|dividing]] <math>x^n-1</math> by the cyclotomic polynomials <math>\Phi_d(x)</math> for the proper divisors ''d'' dividing ''n'', starting from <math>\Phi_{1}(x)=x-1</math>:

:<math>\Phi_n(x)=\frac{x^{n}-1}{\prod_{\stackrel{d|n}{{}_{d<n}}}\Phi_{d}(x)}.</math>

This gives an algorithm for computing any <math>\Phi_n(x)</math>, provided [[integer factorization]] and [[Euclidean division of polynomials|division of polynomials]] are available. Many [[computer algebra systems]], such as [[SageMath]], [[Maple (software)|Maple]], [[Mathematica]], and [[PARI/GP]], have a built-in function to compute the cyclotomic polynomials.

===Easy cases for computation===
As noted above, if {{math|1=''n'' = ''p''}} is a prime number, then

:<math>\Phi_p(x) = 1+x+x^2+\cdots+x^{p-1}=\sum_{k=0}^{p-1}x^k\;.</math>

If ''n'' is an odd integer greater than one, then 

:<math>\Phi_{2n}(x) = \Phi_n(-x)\;.</math>

In particular, if {{math|1=''n'' = 2''p''}} is twice an odd prime, then (as noted above)

:<math>\Phi_{2p}(x) = 1-x+x^2-\cdots+x^{p-1}=\sum_{k=0}^{p-1}(-x)^k\;.</math>

If {{math|1=''n'' = ''p<sup>m</sup>''}} is a [[prime power]] (where ''p'' is prime), then

:<math>\Phi_{p^m}(x) = \Phi_p(x^{p^{m-1}}) =\sum_{k=0}^{p-1}x^{kp^{m-1}}\;.</math>

More generally, if {{math|1=''n'' = ''p<sup>m</sup>r''}} with {{math|''r''}} [[relatively prime]] to {{math|''p''}}, then 

:<math>\Phi_{p^mr}(x) = \Phi_{pr}(x^{p^{m-1}})\;.</math>

These formulas may be applied repeatedly to get a simple expression for any cyclotomic polynomial <math>\Phi_n(x)</math> in terms of a cyclotomic polynomial of [[square-free number|square free]] index: If {{math|''q''}} is the [[Product (mathematics)|product]] of the prime divisors of {{math|''n''}} (its [[Radical of an integer|radical]]), then<ref>{{citation
 | last = Cox | first = David A. | author-link = David A. Cox  | contribution = Exercise 12  | doi = 10.1002/9781118218457 | edition = 2nd  | isbn = 978-1-118-07205-9 | page = 237 | publisher = John Wiley & Sons  | title = Galois Theory | year = 2012}}.</ref>

:<math>\Phi_n(x) = \Phi_q(x^{n/q})\;.</math>

This allows formulas to be given for the {{math|''n''}}th cyclotomic polynomial when {{math|''n''}} has at most one odd prime factor: If {{math|''p''}} is an odd prime number, and {{tmath|\ell}} and {{math|''m''}} are positive integers, then
:<math>\Phi_{2^m}(x) = x^{2^{m-1}}+1\;,</math>
:<math>\Phi_{p^m}(x) = \sum_{j=0}^{p-1}x^{jp^{m-1}}\;,</math>
:<math>\Phi_{2^\ell p^m}(x) = \sum_{j=0}^{p-1}(-1)^jx^{j2^{\ell-1}p^{m-1}}\;.</math>

For other values of {{math|''n''}}, the computation of the {{math|''n''}}th cyclotomic polynomial is similarly reduced to that of  <math>\Phi_q(x),</math> where {{math|''q''}} is the product of the distinct odd prime divisors of {{math|''n''}}. To deal with this case, one has that, for {{math|''p''}} prime and not dividing {{math|''n''}},<ref name="WolframCyclotomic">{{MathWorld |title=Cyclotomic Polynomial |id=CyclotomicPolynomial|mode=cs2}}</ref>

:<math>\Phi_{np}(x)=\Phi_{n}(x^p)/\Phi_n(x)\;.</math>

===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.<ref name=arXivSanna>{{cite arXiv|eprint=2111.04034 |last1=Sanna |first1=Carlo |title=A Survey on Coefficients of Cyclotomic Polynomials |year=2021 |class=math.NT|mode=cs2 }}</ref>
 
If ''n'' has at most two distinct odd prime factors, then Migotti showed that the coefficients of <math>\Phi_n</math> are all in the set {1, −1, 0}.<ref>{{citation |title=Algebra: A Graduate Course |first=Martin |last=Isaacs |page=310 |isbn=978-0-8218-4799-2 |publisher=AMS Bookstore |year=2009}}</ref>

The first cyclotomic polynomial for a product of three different odd prime factors is <math>\Phi_{105}(x);</math> it has a coefficient −2 (see [[#Examples|above]]). The converse is not true: <math>\Phi_{231}(x)=\Phi_{3\times 7\times 11}(x)</math> only has coefficients in {1, −1, 0}.

If ''n'' is a product of more different odd prime factors, the coefficients may increase to very high values. E.g., <math>\Phi_{15015}(x) =\Phi_{3\times 5\times 7\times 11\times 13}(x)</math> has coefficients running from −22 to 23; also <math>\Phi_{255255}(x)=\Phi_{3\times 5\times 7\times 11\times 13\times 17}(x)</math>, the smallest ''n'' with 6 different odd primes, has coefficients of magnitude up to 532.

Let ''A''(''n'') denote the maximum absolute value of the coefficients of <math>\Phi_{n}(x)</math>.  It is known that for any positive ''k'', the number of ''n'' up to ''x'' with ''A''(''n'') > ''n''<sup>''k''</sup> 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''<sup>ψ(''n'')</sup> for almost all ''n''.<ref name=Mai2008>{{Citation
 | last = Maier
 | first = Helmut
 | chapter = Anatomy of integers and cyclotomic polynomials
 | editor1-last = De Koninck
 | editor1-first = Jean-Marie
 | editor2-last = Granville
 | editor2-first = Andrew
 | editor2-link = Andrew Granville
 | editor3-last = Luca
 | editor3-first = Florian
 | title = Anatomy of integers. Based on the CRM workshop, Montreal, Canada, March 13-17, 2006
 | location = Providence, RI
 | publisher = [[American Mathematical Society]]
 | series = CRM Proceedings and Lecture Notes
 | volume = 46
 | pages = 89–95
 | year = 2008
 | isbn = 978-0-8218-4406-9
 | zbl = 1186.11010
}}</ref>

A combination of theorems of Bateman and Vaughan states that{{r|arXivSanna|p=10}} on the one hand, for every <math>\varepsilon>0</math>, we have
:<math>A(n) < e^{\left(n^{(\log 2+\varepsilon)/(\log\log n)}\right)}</math>
for all sufficiently large positive integers <math>n</math>, and on the other hand, we have
:<math>A(n) > e^{\left(n^{(\log 2)/(\log\log n)}\right)}</math>
for infinitely many positive integers <math>n</math>. This implies in particular that [[univariate polynomial|univariate polynomials]] (concretely <math>x^n-1</math> for infinitely many positive integers <math>n</math>) can have factors (like <math>\Phi_n</math>) whose coefficients are [[Superpolynomial|superpolynomially]] larger than the original coefficients. This is not too far from the general [[Landau-Mignotte bound]].

===Gauss's formula===

Let ''n'' be odd, [[Square-free integer|square-free]], and greater than 3. Then:<ref>Gauss, DA, Articles 356-357</ref><ref name=riesel>{{citation
 | last1 = Riesel  | first1 = Hans
 | title = Prime Numbers and Computer Methods for Factorization
 | edition = 2nd
 | publisher = Birkhäuser
 | location = Boston
 | year = 1994
 | isbn = 0-8176-3743-5
 | pages = 309-316, 436, 443
}}</ref>

:<math>4\Phi_n(z) = A_n^2(z) - (-1)^{\frac{n-1}{2}}nz^2B_n^2(z)</math>

for certain polynomials ''A<sub>n</sub>''(''z'') and ''B<sub>n</sub>''(''z'') with integer coefficients, ''A<sub>n</sub>''(''z'') of degree ''&phi;''(''n'')/2, and ''B<sub>n</sub>''(''z'') of degree ''&phi;''(''n'')/2 − 2. Furthermore, ''A<sub>n</sub>''(''z'') is palindromic when its degree is even; if its degree is odd it is antipalindromic. Similarly, ''B<sub>n</sub>''(''z'') is palindromic unless ''n'' is composite and ''n'' ≡ 3 (mod 4), in which case it is antipalindromic.

The first few cases are

:<math>\begin{align}
4\Phi_5(z) &=4(z^4+z^3+z^2+z+1)\\ 
&= (2z^2+z+2)^2 - 5z^2  \\[6pt]
4\Phi_7(z) &=4(z^6+z^5+z^4+z^3+z^2+z+1)\\ 
&= (2z^3+z^2-z-2)^2+7z^2(z+1)^2 \\ [6pt]
4\Phi_{11}(z)
&=4(z^{10}+z^9+z^8+z^7+z^6+z^5+z^4+z^3+z^2+z+1)\\ 
&= (2z^5+z^4-2z^3+2z^2-z-2)^2+11z^2(z^3+1)^2
\end{align}</math>

===Lucas's formula===

Let ''n'' be odd, square-free and greater than 3. Then{{r|riesel}}

:<math>\Phi_n(z) = U_n^2(z) - (-1)^{\frac{n-1}{2}}nzV_n^2(z)</math>

for certain polynomials ''U<sub>n</sub>''(''z'') and ''V<sub>n</sub>''(''z'') with integer coefficients, ''U<sub>n</sub>''(''z'') of degree ''&phi;''(''n'')/2, and ''V<sub>n</sub>''(''z'') of degree ''&phi;''(''n'')/2 − 1. This can also be written

:<math>\Phi_n \left ((-1)^{\frac{n-1}{2}}z \right ) = C_n^2(z) - nzD_n^2(z).</math>

If ''n'' is even, square-free and greater than 2 (this forces ''n''/2 to be odd),

:<math>\Phi_{\frac{n}{2}} (-z^2) = \Phi_{2n}(z)= C_n^2(z) - nzD_n^2(z)</math>

for ''C<sub>n</sub>''(''z'') and ''D<sub>n</sub>''(''z'') with integer coefficients, ''C<sub>n</sub>''(''z'') of degree ''&phi;''(''n''), and ''D<sub>n</sub>''(''z'') of degree ''&phi;''(''n'') − 1. ''C<sub>n</sub>''(''z'') and ''D<sub>n</sub>''(''z'') are both palindromic.

The first few cases are:

:<math>\begin{align}
\Phi_3(-z) &=\Phi_6(z) =z^2-z+1 \\
&= (z+1)^2 - 3z \\[6pt]
\Phi_5(z) &=z^4+z^3+z^2+z+1 \\
&= (z^2+3z+1)^2 - 5z(z+1)^2 \\[6pt]
\Phi_{6/2}(-z^2) &=\Phi_{12}(z)=z^4-z^2+1 \\
&= (z^2+3z+1)^2 - 6z(z+1)^2
\end{align}</math>

===Sister Beiter conjecture===

The [[Sister Beiter conjecture]] is concerned with the maximal size (in absolute value) <math>A(pqr)</math> of coefficients of ''ternary cyclotomic polynomials'' <math>\Phi_{pqr}(x)</math> where <math>p\leq q\leq r</math> are three odd primes.<ref name=beiter68>{{citation|last=Beiter|first=Marion|author-link=Marion Beiter|title=Magnitude of the Coefficients of the Cyclotomic Polynomial <math>F_{pqr}(x)</math>|journal=[[The American Mathematical Monthly]]|volume=75|issue=4|date=April 1968|pages=370–372|doi=10.2307/2313416 |jstor=2313416}}</ref>