2
$\begingroup$

I'm reading Additive Combinatorics by Tao and Vu and am stuck on a step in a proof they present (attributed to Gauss) that cyclotomic polynomials are irreducible over the integers. The argument proceeds by contradiction. By definition, the $n$th cyclotomic polynomial $\Phi_n(z)$ is $$ \Phi_n(z) = \prod_\omega (z-\omega),$$ where the product runs over all primitive $n$th roots of unity. So if $\Phi_n(z)$ is reducible, then the set of all primitive $n$th roots of unity can be partitioned into two disjoint nonempty subsets $A$ and $B$ such that $$f(x) = \prod_{\omega\in A}(z-\omega) \qquad\text{and}\qquad g(x) = \prod_{\omega\in B}(z-\omega)$$ both have integer coefficients. Since $n$th roots of unity are all powers of one another, there is some $\omega\in A$ and integer $m$ such that $\omega^m \in B$. Now the authors say that we can decompose $m$ into primes and argue by contradiction to show that actually there is some $\omega\in A$ and prime $p$ such that $\omega^p\in B$.

I am a bit stuck on this step. I wrote $m = p_1p_2\cdots p_k$ and assumed, for contradiction, that $\omega^{p_i} \in A$ for all $1\le i\le k$, but I was not sure what contradiction to obtain (I suppose it has to be integrality of the coefficients somehow?). I'm sure the step was skipped in the book because it is pretty trivial, but a nudge in the right direction would be appreciated!

$\endgroup$
1
  • $\begingroup$ Thank you to both answerers! the proof was indeed quite simple, I just didn't see it :(( $\endgroup$
    – marcelgoh
    Oct 12, 2022 at 3:38

2 Answers 2

4
$\begingroup$

The point is that you let $w$ vary. It is not the same $w$ as the one that works with $m.$

Let $w_0=w, w_{i+1}=w_i^{p_{i+1}}.$ Then $w_k=w^m.$

Let $j$ be the first value so that $w_j\in B.$ There is such a $j$ since $w_k\in B.$ $j\neq 0$ since $w_0\in A.$

Then $w_{j-1}\in A,$ and $w_j=w_{j-1}^{p_j}\in B.$ Then $w_{j-1}$ in the value for $w$ in the theorem.

$\endgroup$
1
$\begingroup$

Let $\omega$, $m=p_1\cdot p_2 \cdots p_k$; $p_i$ prime for $i=1,2,\ldots k$; and the sets $A,B$, be as in your proof; $\omega \in A$ and $\omega^m \in B$. Let us then set $\omega_i = \omega^{p_1p_2 \ldots p_i}$, for each $i=1,2, \ldots, k$, and $\omega_0=\omega$, for $i=0$.

  1. Then on the one hand, $\omega_0$ is in $A$, and $\omega_k=\omega^m$ and $\omega^m$ is in $B$.

  2. On the other hand, $\omega_{j+1} = \omega_j^{p_{j+1}}$ for each $j=0,1,2,\ldots, k-1$, where recall $p_{j+1}$ is a prime and $m=p_1\cdot p_2 \cdots p_k$.

So then, let $j$ be the smallest integer in $\{0,1,2,\ldots, k-1\}$ such that $\omega_j$ is in $A$ and $\omega^{j+1}$ is in $B$. As from 1. above, $\omega=\omega_0$ is in $A$ and $\omega_k$ is in $B$, observe that there is indeed such a $j$. But then by 2. above, $\omega_{j+1} = \omega_j^{p_{j+1}}$; $\omega_j \in A$; $\omega_{j+1} \in B$; $p_{j+1}$ prime.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .