Difference between revisions of "Cyclotomic polynomial"

Latest revision as of 13:50, 23 June 2022

The Cyclotomic Polynomials are a family of polynomials that are observed frequently in number theory and algebra. While most sources on the internet introduce them on a preliminary level, there is far more rigor and connections to different disciplines which will all be shared here.

To ease any worries, any field $F$ is guaranteed an extension $K$ , so the existence of such a splitting field is not problematic. An example to consider would be the splitting field of $f(x)=x^2-2$ over the field $\mathbb{Q}$ . This, of course, would just be $\mathbb{Q}(\sqrt{2})$ since its roots in $\mathbb{Q}$ are both in $\mathbb{Q}(\sqrt{2})$ . So this raises the question: what is the splitting field of $x^n-1$ over $\mathbb{Q}$ based on this definition?

The Cyclotomic Field

Recall that over $\mathbb{C}$ there are $n$ distinct solutions of the equation $x^n=1$ , which are

$e^{2\pi i k/n}=\text{cis}\left(\frac{2\pi k}{n}\right)=\cos\left(\frac{2\pi k}{n}\right)+i\sin\left(\frac{2\pi k}{n}\right)$

for $k\in\{0,1,\ldots, n-1\}$ . These are known as the $n$ th roots of unity. These harken back to the language of generators, since we see that

$(e^{2\pi i k/n})^n=e^{n(2\pi i k/n)}=e^{2\pi i k}=1.$

In fact, the collection of the $n$ th roots of unity forms a cyclic group under multiplication, which we will call $\mathbb{U}$ .

Now we are in the language of groups. Since $\mathbb{U}$ is cyclic, it certainly has generators, so we shall define them. We call the generators of $\mathbb{U}$ the primitive $n$ th roots of unity, which we denote as $\zeta_n$ . The other primitive roots of unity are of course $\zeta_n^m$ where $1\le m<n$ where $\gcd(m,n)=1$ , so it follows that there are $\varphi(n)$ primitive roots of unity. This makes sense because if we let $\zeta_n=e^{2\pi i/n}$ then $\zeta_n^k=e^{2\pi i k/n}$ .

Back to the language of fields. As we saw in the case of $\mathbb{U}$ , we can view this splitting field for $x^n-1$ over $\mathbb{Q}$ as a field generated over $\mathbb{Q}$ by the field $\mathbb{C}$ . Specifically, our splitting field is going to be generated by $\zeta_n$ .

Definition: The splitting field of $x^n-1$ over $\mathbb{Q}$ is called the cyclotomic field of the $n$ th roots of unity, which we denote by $\mathbb{Q}(\zeta_n)$ .

The Cyclotomic Polynomial at First Glance

The Cyclotomic polynomials come into play when we look at $n=p$ . More specifically, over $\mathbb{Q}$ we get the following factorization:

$x^{p}-1=(x-1)(x^{p-1}+x^{p-2}+x^{p-3}+\ldots+x+1$

but since $\zeta_p\ne 1$ for any $p$ , we see that $\zeta_p$ must be a root of $x^{p-1}+x^{p-2}+x^{p-3}+\ldots+x+1$ . This is such a special property that we give this polynomial a special name. The Cyclotomic Polynomials of order $p$ are given by

$\Phi_p(x)=x^{p-1}+x^{p-2}+\ldots+x+1.$

This would just be a mathematical novelty if not for this crucial theorem.

Theorem: The Cyclotomic Polynomial $\Phi_p(x)$ is irreducible over $\mathbb{Q}$ for all $p$ .

Proof: The proof is rather iconic. Let $p$ be prime. We can write the cyclotomic polynomial in a more helpful form:

$\Phi_p(x)=x^{p-1}+x^{p-2}+x^{p-3}\cdots x^2+x+1=\frac{x^p-1}{x-1}\implies (x-1)\Phi_p(x)=x^p-1.$

Recall by that by the Binomial Theorem we have

$(x+1)^p=\sum_{n=0}^{p}\binom{p}{n}x^{p-n}$

where $p~|~\binom{p}{n}$ for $0<n<p$ . By considering $\Phi_p(x+1)$ we have

$\begin{align*} x\Phi_p(x+1)&=(x+1)^p-1\\ &=\sum_{n=0}^{p}\binom{p}{n}x^{p-n}-1\\ &=x^p+px^{p-1}+\binom{p}{2}x^{p-2}+\cdots +px \end{align*}$

and dividing the right hand side by $x$ gives

$\Phi_p(x+1)=x^{p-1}+px^{p-2}+\binom{p}{2}x^{p-3}+\cdots +p$

which is irreducible over $\mathbb{Z}$ by eisenstein's criterion. The implication that $\Phi_p(x+1)$ being irreducible in $\mathbb{Z}$ can easily be seen with $\Phi_p(x)$ , so by Gauss' lemma the result follows. $\square$

Since $\Phi_p(x)$ is irreducible over $\mathbb{Q}$ , it follows that $\mathbb{Q}(\zeta_p)$ is the splitting field for $\Phi_p(x)$ . Hence, $[\mathbb{Q}(\zeta_p) : \mathbb{Q}]=p-1$ . But this is only for $n=p$ . What happens if we generalize this for all $n$ ?

The Cyclotomic Polynomials Fully Defined

We define the $n$ th cyclotomic polynomial $\Phi_n(x)$ as the polynomial whose roots are the $n$ th roots of unity.

$\Phi_n(x)=\prod_{\zeta~\text{primitive}~\in\mathbb{U}}(x-\zeta)=\prod_{1\le a<n, \gcd(a,n)=1}(x-\zeta_n^a).$

Let $\mathbb{U}_d$ be a subgroup of $\mathbb{U}$ of order $d$ . By definition we see that

$x^n-1=\prod_{\zeta^n=1}(x-\zeta)\implies x^n-1=\prod_{d|n}\left(\prod_{\zeta~\text{primitive}~\in\mathbb{U}_d}(x-\zeta)\right)=\prod_{d|n}\Phi_d(x).$

This allows us to compute the Cyclotomic Polynomial of order $n$ recursively. However, there is a nicer way that requires less expansion.

Theorem: $\Phi_n(x)=\prod_{d|n}(x^d-1)^{\mu(n/d)}$ .

Proof: For context, the Möbius Inversion Formula states that if $g(n)$ and $f(n)$ are arithmetic functions then

$g(n)=\sum_{d|n}f(d)\implies f(n)=\sum_{d|n}\mu(d)g\left(\frac{n}{d}\right)=\sum_{d|n}\mu\left(\frac{n}{d}\right)g(d)$

where $\mu(n)$ denotes the Möbius Function. We begin with the following formula that states

$x^n-1=\prod_{d|n}\Phi_d(x).$

We now take the logarithm of both sides of this equation. We see that

$\begin{align*} \log(x^n-1)&=\log\left(\prod_{d|n}\Phi_d(x)\right)\\ &=\sum_{d|n}\log(\Phi_d(x)). \end{align*}$

Now we apply Möbius. By the formula we see that

$\begin{align*} \log(x^n-1)&=\sum_{d|n}\log(\Phi_d(x))\\ \log(\Phi_n(x))&=\sum_{d|n}\log(x^d-1)\mu\left(\frac{n}{d}\right) \end{align*}$

and unexponentiating by considering this equation in $\exp(x)$ gives

$\begin{align*} \Phi_n(x)=\prod_{d|n}(x^d-1)^{\mu(n/d)} \end{align*}$

which is exactly what we wanted to show. $\square$

As a corollary to the previous theorem, this implies that $\deg(\Phi_n(x))=\varphi(n)$ rather easily. This helps aid in computation, and once again ties this strange polynomial to number theory. The Cyclotomic Polynomial has some ties to algebraic number theory in particular, and also has some nice results in Galois theory.

@@ Line 1: / Line 1: @@
-==Definition==
+The '''Cyclotomic Polynomials''' are a family of polynomials that are observed frequently in [[number theory]] and [[algebra]].  While most sources on the internet introduce them on a preliminary level, there is far more rigor and connections to different disciplines which will all be shared here.
-The cyclotomic [[polynomials]] are recursively defined as <math>x^n-1=\prod_{d \vert n} \Phi_n (x)</math>, for <math>n \geq 1</math>. All cyclotomic polynomials are [[irreducible polynomial|irreducible]].
-==Roots==
+===Motivation===
-The roots of <math>\Phi_n(x)</math> are <math>e^{\frac{2\pi i d}{n}}</math>, where <math>\gcd(d, n) = 1</math>. For this reason, due to the [[Fundamental Theorem of Algebra]], we have <math>\Phi_n(x) = \prod_{d: \gcd(d, n) = 1} (x - e^{\frac{2\pi i d}{n}})</math>.
+The main reason why one even cares about the Cyclotomic polynomials begins with the study of splitting [[field]]s.
-==Examples==
+'''Definition''': The extension <math>K</math> of a field <math>F</math> is a splitting field for <math>f(x)\in F[x]</math> if <math>f(x)</math> can be written as the product of irreducible factors in <math>K[x]</math>, and <math>f(x)</math> does not factor into a product of irreducible factors in any other proper subfield of <math>K</math> containing <math>F</math>.
-For a prime <math>p</math>, <math>\Phi_p (x)=x^{p-1}+x^{p-2}+ \cdots + 1</math>, because for a prime <math>p</math>, <math>\Phi_p (x) \cdot \Phi_1 (x)=x^p - 1</math> and so we can factorise <math>x^p - 1</math> to obtain the required result.
-The first few cyclotomic polynomials are as shown:
+To ease any worries, any field <math>F</math> is guaranteed an extension <math>K</math>, so the existence of such a splitting field is not problematic.  An example to consider would be the splitting field of <math>f(x)=x^2-2</math> over the field <math>\mathbb{Q}</math>.  This, of course, would just be <math>\mathbb{Q}(\sqrt{2})</math> since its roots in <math>\mathbb{Q}</math> are both in <math>\mathbb{Q}(\sqrt{2})</math>.  So this raises the question: what is the splitting field of <math>x^n-1</math> over <math>\mathbb{Q}</math> based on this definition?
-<cmath>\begin{align*}
-\Phi_1(x)&=x-1 \\
-\Phi_2(x)&=x+1 \\
-\Phi_3(x)&=x^2+x+1 \\
-\Phi_4(x)&=x^2+1 \\
-\Phi_5(x)&=x^4+x^3+x^2+x+1 \\
-\Phi_6(x)&=x^2-x+1 \\
-\Phi_7(x)&=x^6+x^5+\cdots + 1 \\
-\Phi_8(x)&=x^4+1 \\
-\Phi_9(x)&=x^6+x^3+1 \\
-\Phi_10(x)&=x^4-x^3+x^2-x+1\\
-\end{align*}</cmath>
-{{stub}}
+===The Cyclotomic Field===
+Recall that over <math>\mathbb{C}</math> there are <math>n</math> distinct solutions of the equation <math>x^n=1</math>, which are
+<center><cmath>e^{2\pi i k/n}=\text{cis}\left(\frac{2\pi k}{n}\right)=\cos\left(\frac{2\pi k}{n}\right)+i\sin\left(\frac{2\pi k}{n}\right)</cmath></center>
+for <math>k\in\{0,1,\ldots, n-1\}</math>.  These are known as the <math>n</math>th [[roots of unity]].  These harken back to the language of generators, since we see that
+<center><cmath>(e^{2\pi i k/n})^n=e^{n(2\pi i k/n)}=e^{2\pi i k}=1.</cmath></center>
+In fact, the collection of the <math>n</math>th roots of unity forms a cyclic [[group]] under multiplication, which we will call <math>\mathbb{U}</math>.
+Now we are in the language of groups.  Since <math>\mathbb{U}</math> is cyclic, it certainly has generators, so we shall define them.  We call the generators of <math>\mathbb{U}</math> the ''primitive <math>n</math>th roots of unity'', which we denote as <math>\zeta_n</math>.  The other primitive roots of unity are of course <math>\zeta_n^m</math> where <math>1\le m<n</math> where <math>\gcd(m,n)=1</math>, so it follows that there are <math>\varphi(n)</math> primitive roots of unity.  This makes sense because if we let <math>\zeta_n=e^{2\pi i/n}</math> then <math>\zeta_n^k=e^{2\pi i k/n}</math>.
+Back to the language of fields.  As we saw in the case of <math>\mathbb{U}</math>, we can view this splitting field for <math>x^n-1</math> over <math>\mathbb{Q}</math> as a field generated over <math>\mathbb{Q}</math> by the field <math>\mathbb{C}</math>.  Specifically, our splitting field is going to be generated by <math>\zeta_n</math>.
+'''Definition''': The splitting field of <math>x^n-1</math> over <math>\mathbb{Q}</math> is called the cyclotomic field of the <math>n</math>th roots of unity, which we denote by <math>\mathbb{Q}(\zeta_n)</math>.
+===The Cyclotomic Polynomial at First Glance===
+The Cyclotomic polynomials come into play when we look at <math>n=p</math>.  More specifically, over <math>\mathbb{Q}</math> we get the following factorization:
+<center><cmath>x^{p}-1=(x-1)(x^{p-1}+x^{p-2}+x^{p-3}+\ldots+x+1</cmath></center>
+but since <math>\zeta_p\ne 1</math> for any <math>p</math>, we see that <math>\zeta_p</math> must be a root of <math>x^{p-1}+x^{p-2}+x^{p-3}+\ldots+x+1</math>.  This is such a special property that we give this polynomial a special name.  The '''Cyclotomic Polynomials of order <math>p</math>''' are given by
+<center><cmath>\Phi_p(x)=x^{p-1}+x^{p-2}+\ldots+x+1.</cmath></center>
+This would just be a mathematical novelty if not for this crucial theorem.
+'''Theorem''': The Cyclotomic Polynomial <math>\Phi_p(x)</math> is irreducible over <math>\mathbb{Q}</math> for all <math>p</math>.
+''Proof'': The proof is rather iconic.  Let <math>p</math> be prime.  We can write the cyclotomic polynomial in a more helpful form:
+<center><math>\Phi_p(x)=x^{p-1}+x^{p-2}+x^{p-3}\cdots x^2+x+1=\frac{x^p-1}{x-1}\implies  (x-1)\Phi_p(x)=x^p-1. </math></center>
+Recall by that by the Binomial Theorem we have
+<center><math>(x+1)^p=\sum_{n=0}^{p}\binom{p}{n}x^{p-n}</math></center>
+where <math>p~|~\binom{p}{n}</math> for <math>0<n<p</math>.  By considering <math>\Phi_p(x+1)</math> we have
+<center><cmath>\begin{align*}
+x\Phi_p(x+1)&=(x+1)^p-1\\
+&=\sum_{n=0}^{p}\binom{p}{n}x^{p-n}-1\\
+&=x^p+px^{p-1}+\binom{p}{2}x^{p-2}+\cdots +px
+\end{align*}</cmath></center>
+and dividing the right hand side by <math>x</math> gives
+<center><math>\Phi_p(x+1)=x^{p-1}+px^{p-2}+\binom{p}{2}x^{p-3}+\cdots +p</math></center>
+which is irreducible over <math>\mathbb{Z}</math> by [[eisenstein's criterion]].  The implication that <math>\Phi_p(x+1)</math> being irreducible in <math>\mathbb{Z}</math> can easily be seen with <math>\Phi_p(x)</math>, so by Gauss' lemma the result follows. <math>\square</math>
+Since <math>\Phi_p(x)</math> is irreducible over <math>\mathbb{Q}</math>, it follows that <math>\mathbb{Q}(\zeta_p)</math> is the splitting field for <math>\Phi_p(x)</math>.  Hence, <math>[\mathbb{Q}(\zeta_p) : \mathbb{Q}]=p-1</math>.  But this is only for <math>n=p</math>.  What happens if we generalize this for all <math>n</math>?
+===The Cyclotomic Polynomials Fully Defined===
+We define the <math>n</math>th cyclotomic polynomial <math>\Phi_n(x)</math> as the polynomial whose roots are the <math>n</math>th roots of unity.
+<center><cmath>\Phi_n(x)=\prod_{\zeta~\text{primitive}~\in\mathbb{U}}(x-\zeta)=\prod_{1\le a<n, \gcd(a,n)=1}(x-\zeta_n^a).</cmath></center>
+Let <math>\mathbb{U}_d</math> be a subgroup of <math>\mathbb{U}</math> of order <math>d</math>.  By definition we see that
+<center><cmath>x^n-1=\prod_{\zeta^n=1}(x-\zeta)\implies x^n-1=\prod_{d|n}\left(\prod_{\zeta~\text{primitive}~\in\mathbb{U}_d}(x-\zeta)\right)=\prod_{d|n}\Phi_d(x).</cmath></center>
+This allows us to compute the Cyclotomic Polynomial of order <math>n</math> recursively.  However, there is a nicer way that requires less expansion.
+'''Theorem''': <math>\Phi_n(x)=\prod_{d|n}(x^d-1)^{\mu(n/d)}</math>.
+''Proof'': For context, the Möbius Inversion Formula states that if <math>g(n)</math> and <math>f(n)</math> are arithmetic functions then
+<center><cmath>g(n)=\sum_{d|n}f(d)\implies f(n)=\sum_{d|n}\mu(d)g\left(\frac{n}{d}\right)=\sum_{d|n}\mu\left(\frac{n}{d}\right)g(d)</cmath></center>
+where <math>\mu(n)</math> denotes the Möbius Function.  We begin with the following formula that states
+<center><cmath>x^n-1=\prod_{d|n}\Phi_d(x).</cmath></center>
+We now take the logarithm of both sides of this equation.  We see that
+<center><cmath>\begin{align*}
+\log(x^n-1)&=\log\left(\prod_{d|n}\Phi_d(x)\right)\\
+&=\sum_{d|n}\log(\Phi_d(x)).
+\end{align*}</cmath></center>
+Now we apply Möbius.  By the formula we see that
+<center><cmath>\begin{align*}
+\log(x^n-1)&=\sum_{d|n}\log(\Phi_d(x))\\
+ \log(\Phi_n(x))&=\sum_{d|n}\log(x^d-1)\mu\left(\frac{n}{d}\right)
+ \end{align*}</cmath></center>
+and unexponentiating by considering this equation in <math>\exp(x)</math> gives
+<center><cmath>\begin{align*}
+\Phi_n(x)=\prod_{d|n}(x^d-1)^{\mu(n/d)}
+\end{align*}</cmath></center>
+which is exactly what we wanted to show. <math>\square</math>
+As a corollary to the previous theorem, this implies that <math>\deg(\Phi_n(x))=\varphi(n)</math> rather easily.  This helps aid in computation, and once again ties this strange polynomial to [[number theory]].  The Cyclotomic Polynomial has some ties to [[algebraic number theory]] in particular, and also has some nice results in [[Galois theory]].

Page

Toolbox

Search

Difference between revisions of "Cyclotomic polynomial"

Latest revision as of 13:50, 23 June 2022

Contents

Motivation

The Cyclotomic Field

The Cyclotomic Polynomial at First Glance

The Cyclotomic Polynomials Fully Defined