Skip to main content
1 of 3
Kevin
  • 539
  • 3
  • 11

Suppose that you can factor $x^{p-1} + x^{p-2} + \cdots + 1$ as $f(x)g(x)$ with $\deg(f)=a,\deg(g) = b$ and $f,g$ having nonnegative coefficients.

Lemma: It must be the case that $f = \sum_{i=0}^a c_i x^i$ and $g = \sum_{i=0}^b d_i x^i$, where $c_i, d_j > 0$ for all $0 \le i \le a$ and $0 \le j \le b$.

Proof: Suppose that some $c_i$ is zero; for concreteness say $c_a = 0$. Now, let's fix the set of $a$ distinct $p$th roots of unity that $f$ vanishes on, say $\omega^{r_1}, \ldots, \omega^{r_a}$ with $\omega$ a primitive root. The set of polynomials satisfying these conditions is the subspace $(c_0, \ldots, c_{a-1})$ such that $M.(c_0, \ldots, c_{a-1}) = (0,\ldots, 0)$, and $M$ is the $a \times a$ matrix whose $i,j$th entry is $\omega^{r_i \cdot j}$. But this is a submatrix of the DFT matrix for $\mathbb{Z}_p$, and hence it is invertible; see Lemma 1.3 of https://arxiv.org/abs/math/0308286 for a reference. Hence $f$ must be identically zero, a contradiction. Note this argument works when we omit any monomial from the support of $f$, not just $x^a$.

Now, note that by rescaling $f$ and $g$ we may assume that $c_0 = 1$, and therefore also $d_0 = 1$. Now consider $c_ad_b$, the coefficient of $x^{p-1}$ in the product. Note that $c_a$ must be strictly less than 1, since the coefficient of $x^a$ in the product equals $c_a \cdot 1$ plus some positive stuff (by the lemma), and this should equal 1. Similarly, $d_b < 1$. So $c_ad_b < 1$, a contradiction.

Kevin
  • 539
  • 3
  • 11