Difference between revisions of "Cyclotomic polynomial"
Aops-student (talk | contribs) |
(This page was absolutely abysmal in the state I found it. I added many well-known results and proofs of all of my conjectures. One could extend this to algebraic number theory and Galois theory, which currently I haven't the time to write about.) |
||
(One intermediate revision by the same user not shown) | |||
Line 1: | Line 1: | ||
− | + | 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 | ||
− | == | + | ===Motivation=== |
− | The | + | The main reason why one even cares about the Cyclotomic polynomials begins with the study of splitting [[field]]s. |
− | + | '''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>. | |
− | + | 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? | |
− | |||
− | The | + | ===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]]. |
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.
Contents
Motivation
The main reason why one even cares about the Cyclotomic polynomials begins with the study of splitting fields.
Definition: The extension of a field is a splitting field for if can be written as the product of irreducible factors in , and does not factor into a product of irreducible factors in any other proper subfield of containing .
To ease any worries, any field is guaranteed an extension , so the existence of such a splitting field is not problematic. An example to consider would be the splitting field of over the field . This, of course, would just be since its roots in are both in . So this raises the question: what is the splitting field of over based on this definition?
The Cyclotomic Field
Recall that over there are distinct solutions of the equation , which are
for . These are known as the th roots of unity. These harken back to the language of generators, since we see that
In fact, the collection of the th roots of unity forms a cyclic group under multiplication, which we will call .
Now we are in the language of groups. Since is cyclic, it certainly has generators, so we shall define them. We call the generators of the primitive th roots of unity, which we denote as . The other primitive roots of unity are of course where where , so it follows that there are primitive roots of unity. This makes sense because if we let then .
Back to the language of fields. As we saw in the case of , we can view this splitting field for over as a field generated over by the field . Specifically, our splitting field is going to be generated by .
Definition: The splitting field of over is called the cyclotomic field of the th roots of unity, which we denote by .
The Cyclotomic Polynomial at First Glance
The Cyclotomic polynomials come into play when we look at . More specifically, over we get the following factorization:
but since for any , we see that must be a root of . This is such a special property that we give this polynomial a special name. The Cyclotomic Polynomials of order are given by
This would just be a mathematical novelty if not for this crucial theorem.
Theorem: The Cyclotomic Polynomial is irreducible over for all .
Proof: The proof is rather iconic. Let be prime. We can write the cyclotomic polynomial in a more helpful form:
Recall by that by the Binomial Theorem we have
where for . By considering we have
and dividing the right hand side by gives
which is irreducible over by eisenstein's criterion. The implication that being irreducible in can easily be seen with , so by Gauss' lemma the result follows.
Since is irreducible over , it follows that is the splitting field for . Hence, . But this is only for . What happens if we generalize this for all ?
The Cyclotomic Polynomials Fully Defined
We define the th cyclotomic polynomial as the polynomial whose roots are the th roots of unity.
Let be a subgroup of of order . By definition we see that
This allows us to compute the Cyclotomic Polynomial of order recursively. However, there is a nicer way that requires less expansion.
Theorem: .
Proof: For context, the Möbius Inversion Formula states that if and are arithmetic functions then
where denotes the Möbius Function. We begin with the following formula that states
We now take the logarithm of both sides of this equation. We see that
Now we apply Möbius. By the formula we see that
and unexponentiating by considering this equation in gives
which is exactly what we wanted to show.
As a corollary to the previous theorem, this implies that 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.