$\sum{x^{(i,n)}}+1$ is irreducible?

Question

A simple calculation using Burnside lemma shows that the number of distinct "necklaces" with $n$ balls of $x$ colors is

$$\frac{F_n(x)}{n} = \frac{\sum_{i=1}^n x^{(i,n)}}{n} = \frac{\sum_{d \mid n} x^d \varphi\left(\frac{n}{d}\right)}{n}.$$

It's natural to ask more about this polynomial $F_n$. A few attemptions shows that $F_n + 1$ might be irreducible over $\mathbb Q$:

$$ F_2(x) + 1 = x^2 + x + 1,\\ F_3(x) + 1 = x^3 + 2x + 1,\\ F_4(x) + 1 = x^4 + x^2 + 2x + 1,\\ \cdots $$

In fact, a computer search up to $F_{2000}$ shows that $F_i$ is irreducible for all $i \le 2000$.

QUESTION. Is $F_n+1$ irreducible over $\mathbb Q$ for all $n \ge 2$?

Answer 1

As Peter mentioned in his comment, $F_n(x)$ has the nice property that $n\mid F_n(x)$ for all integers $x$. We will show that, in fact, for any complete set of conjugate algebraic integers $\{\alpha_1, \ldots, \alpha_d\}$, $F_n$ has the property that $n \mid \sum_{i=1}^d F_n(\alpha_i)$. From this, we can deduce the irreducibility of $F_n(x)+1$ as follows:

Let $\alpha_1, \ldots, \alpha_d$ be the roots of an arbitrary degree-$d$ factor of the degree $n$ polynomial $f(x) := F_n(x)+1$. Then $$ 0 = \sum_{i=1}^d f(\alpha_i) = \left(\sum_{i=1}^d F_n(\alpha_i)\right) + d.$$ The property above then implies that $n\mid d$, so $d=0$ or $d=n$. Since each factor of $f(x)$ has degree $0$ or degree $n$, $f(x)$ is irreducible.

---

To prove this property, fix a prime $p$ that divides $n$, and write $n = p^k\cdot m$ where $p \not\mid m$. By grouping the terms of $F_n(x) = \sum_{d\mid n}x^d \varphi(\frac{n}{d})$ according to the largest power of $p$ that divides $d$, we obtain the following identity:

$$F_n(x) = F_{p^k m}(x) = F_m(x^{p^k}) + (p-1)\sum_{i=1}^k p^i F_m(x^{p^{k-i}}).$$

or equivalently $$F_n(x) = \left[ F_m(x^{p^k})-F_m(x^{p^{k-1}})\right] + p\left[ F_m(x^{p^{k-1}})-F_m(x^{p^{k-2}})\right] +\ldots + p^{k-1}\left[ F_m(x^{p})-F_m(x)\right] + p^kF_m(x).$$

Let $\alpha_1,\ldots, \alpha_d$ be the roots of any monic polynomial with integer coefficients. Our goal is to prove that $\sum_{i=1}^d F_n(\alpha_i) \equiv 0 \pmod{p^k}$ for each $p^k$ dividing $n$. Based on the identity above, it suffices to prove that for each $1\le j \le k$, $$\sum_{i=1}^dF_m(\alpha_i^{p^{j}}) \equiv \sum_{i=1}^dF_m(\alpha_i^{p^{j-1}}) \pmod{p^j}$$ To that end, we have the following lemma:

Lemma. Let $\alpha_1,\ldots, \alpha_d$ be the roots of a monic polynomial in $\mathbb{Z}[x]$, and let $G(x_1,\ldots,x_d)$ be a symmetric polynomial in $\mathbb{Z}[x_1,\ldots,x_d]$. Then for any prime power $p^j$, $$G(\alpha_1^{p^j},\ldots,\alpha_d^{p^j}) \equiv G(\alpha_1^{p^{j-1}},\ldots,\alpha_d^{p^{j-1}}) \pmod{p^j}$$ (as a congruence of two integers).

Taking $G(x_1,\ldots,x_d) = \sum_{i=1}^d F_m(x_d)$ in the lemma completes the proof.

Proof of the Lemma: Inductively, we can find symmetric polynomials $G_0, G_1, \ldots$ such that for each $j$, $$G(x_1^{p^{j}},\ldots,x_d^{p^{j}}) = G_0(x_1, \ldots, x_d)^{p^{j}} + p\cdot G_1(x_1, \ldots, x_d)^{p^{j-1}} + \ldots + p^j\cdot G_j(x_1, \ldots, x_d)$$ For the base case, $G_0 = G$. For the inductive step, substitute in $x_i^p$ for $x_i$. Then looking at each term on the right-hand side, we have (for example) $$ G_0(x_1^p, \ldots, x_d^p) \equiv G_0(x_1, \ldots, x_d)^p \pmod{p},$$ (as a congruence of two polynomials), so the binomial theorem implies that $$ G_0(x_1^p, \ldots, x_d^p)^{p^j} \equiv G_0(x_1, \ldots, x_d)^{p^{j+1}} \pmod{p^{j+1}}.$$ The other terms are similar. This completes the inductive step.

With this identity proven, plug in $\alpha_1, \ldots, \alpha_d$ for $x_1, \ldots, x_d$. Then, since $G_0, G_1, \ldots$ are symmetric polynomials, $G_0(\alpha_1, \ldots, \alpha_d), G_1(\alpha_1, \ldots, \alpha_d), \ldots$ are all integers by the fundamental theorem of symmetric polynomials.

The lemma then follows from the fact that for every integer $a$ and prime power $p^j$, $$a^{p^j} \equiv a^{p^{j-1}} \pmod{p^j}.$$

Answer 2

Supplementing Benjamin Wright's very nice solution, here is a combinatorial proof of the lemma he uses, that if $\alpha_1, \dots \alpha_m$ are a complete set of conjugate algebraic integers then $n \mid \sum F_n(\alpha_i)$. We will do it by counting a slight generalization of necklaces.

Let $X$ be a finite directed multigraph on $m$ vertices with adjacency matrix $A$, which can be any $m \times m$ matrix with non-negative integer coefficients. We're going to count the number of "necklace walks" on this graph of length $n$, by which I mean an orbit of the set of closed walks of length $n$ under the action of the cyclic group $C_n$. If $\alpha_1, \dots \alpha_m$ are the eigenvalues of $A$ then

$$\text{tr}(A^n) = \sum_{i=1}^m \alpha_i^n$$

counts the number of closed walks of length $n$. From here, the same Burnside's lemma calculation as in the OP gives that the number of "necklace walks" of length $n$ is

$$\frac{1}{n} \sum_{d \mid n} \varphi \left( \frac{n}{d} \right) \text{tr}(A^d) = \frac{1}{n} \sum_{i=1}^m F_n(\alpha_i)$$

which implies that $n \mid \sum F_n(\alpha_i)$ if $\alpha_i$ are the eigenvalues of a matrix $A$ with non-negative integer coefficients. To conclude from here, note that to prove divisibility by $n$ we can reduce the matrix $A \bmod n$ and compute $\sum_{d \mid n} \varphi \left( \frac{n}{d} \right) \text{tr}(A^d) \bmod n$, and since the reduction $\bmod n$ map from non-negative integer matrices to matrices $\bmod n$ is surjective, the result is true for arbitrary matrices $\bmod n$ and hence for arbitrary integer matrices. In particular it is true for the companion matrix of any monic polynomial over $\mathbb{Z}$, so the $\alpha_i$ can be any complete set of conjugate algebraic integers as desired.