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

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$$?

• Interesting. Maybe an off-topic question : When is $\frac{F_n(x)}{n}$ an integer ? It must be if it is the number of distinct necklaces. Oct 13, 2022 at 15:35
• You can at least prove it easily for certain known structure of divisors of $n$. For example, for $n=p^k$ a prime power $F_n(x)+1=x^{p^k}+(p-1)x^{p^{k-1}}+\dots+(p^k-p^{k-1})x+1$, whose reciprocal polynomial (coefficients in reverse order) is irreducible by Perron's criterion.
– Sil
Oct 14, 2022 at 10:41
• @Sil Can we also prove $F_n(-1)+1\ne 0$ which would show there is never a linear factor. Oct 14, 2022 at 11:03
• @Peter True, I think that follows from this math.stackexchange.com/questions/84283
– Sil
Oct 14, 2022 at 11:30
• @Peter That's Romanian TST 2015 Day 2, P1. Oct 14, 2022 at 12:49

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}.$$

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.

• Excellent combinatorial explanation! Thanks! Nov 21, 2022 at 14:38