The Schinzel-Zassenhaus conjecture

In this post we give an account of the following theorem, which answers a conjecture of Schinzel and Zassenhaus

Theorem 1: Let $P \in \mathbb{Z}[X]$ be a monic integer irreducible polynomial of degree $n > 1$. If $P$ is not cyclotomic, then

\[\max_{\substack{\alpha : P(\alpha)=0}} |\alpha| \geq 2^{1/4n}.\]

What's mysterious about this is how uniform it is: given a non-cyclotomic polynomial it has to have a root far enough out from the unit circle, where far enough is in terms of the degree of the polynomial. Said differently, it's difficult to have roots all near the unit circle without having all of them on the unit circle. The proof strategy will be to extract both analytic and mod $p$ information and put that together.

Here's the analytic information we need. Recall the following from a previous post:

Dubinin's theorem: Let $K$ be the union of some intervals of the form $[0,a_j]$, which we call the star $K(a_1, \dots a_n)$, and suppose that capacity of $K$ is $1$. Then $\max_j |a_j|$ takes its minimal value when the star is symmetric: all $|a_j|$ are equal and the angles between adjacent intervals are equal.

By instead allowing the capacity to vary, we get the following equivalent form: the star $K(a_1, \dots a_n)$ has capacity/transfinite diameter at most $(\max|a_i|^n/4)^{\frac{1}{n}}$, with equality iff the $a_i$ form the vertices of a regular $n-$gon centred at the origin.

Mod p input

Lemma 2: Consider $P(X) \in \mathbb{Z}[X]$ an integer monic polynomial, with factorization $P(X) = \prod_{i=1}^{n}(X - \alpha_i)$ over $\mathbb{C}$. Define the auxiliary sequence of integer polynomials $(P_n)_{n \geq 1}$ by

\begin{equation*} P_m(X) = \prod_{i=1}^{n}(X - \alpha_i^m) \in \mathbb{Z}[X]. \end{equation*}

Then the following mod 4 congruence holds:

\begin{equation*}P_1 \equiv P_2 \pmod{4\mathbb{Z}[X]}.\end{equation*}

Proof: First off, we easily see the congruence $\sum_{i=1}^{n} \alpha_i^4 \equiv \sum_{i=1}^{n} \alpha_i^2 \pmod{4}$ for the $X^{n-1}$ terms. For, by the Newton-Girard identities expressing the power sums $s_k = \sum_{i=1}^{n} \alpha_i^k$ as polynomials in the n elementary symmetric functions $e_1, \ldots, e_n \in \mathbb{Z}$ of the roots $\alpha_i$, we have

\begin{align}s_2 &= e_1^2 - 2e_2, \\s_4 &= e_1^4 + 2e_2^2 - 4(e_1^2 e_2 - e_1 e_3 + e_4),\end{align}

which are manifestly congruent mod 4 as $e_1, e_2, e_3, e_4 \in \mathbb{Z}$.

For the general case with the $X^{n-k}$ coefficients, we simply apply the previous to the new polynomial

\begin{equation*}\prod_{I}(X - \alpha_{i_1} \cdots \alpha_{i_k}) \in \mathbb{Z}[X],\end{equation*}

where the product is over all $k$-element sets $I = \{i_1, \ldots, i_k\} \subset \{1, \ldots, n\}$.  $\blacksquare$

The following consequence is the crucial 2-adic integrality property needed for our proof of Theorem 1. It is based on the observation that

\begin{equation*}\sqrt{1 + 4Y} = \sum_{k=0}^{\infty} \binom{1/2}{k} 4^k Y^k \in \mathbb{Z}[[Y]]. \tag{1}\end{equation*}

Proposition 3: Consider a polynomial $Q \in \mathbb{Z}[X]$ such that $Q(0) = 1$ and $Q \bmod 4$ is a perfect square in $(\mathbb{Z}/4)[X]$. Then $\sqrt{Q(X)}$ has an $X = 0$ Taylor expansion in integer coefficients:

\begin{equation*}\sqrt{Q(X)} \in 1 + X\mathbb{Z}[[X]].\end{equation*}

In particular, for every integer polynomial $P \in \mathbb{Z}[X]$ such that $P(0) = 1$, we have

\begin{equation*}\sqrt{P_2(X)P_4(X)} \in \mathbb{Z}[[X]]. \tag{2}\end{equation*}

Proof: By assumption, we can write $Q(X) = U(X)^2 + 4V(X)$, with $U(X), V(X) \in \mathbb{Z}[X]$ and $U(0) = 1, V(0) = 0$. We have

\begin{equation*}\sqrt{Q(X)} = U(X)\sqrt{1 + 4V(X)/U(X)^2} \in \mathbb{Z}[[X]],\end{equation*}

upon applying (1) with $Y := V(X)/U(X)^2 \in X\mathbb{Z}[[X]]$.  $\blacksquare$

Examples: Interesting examples of algebraic or holonomic power series with integer coefficients are often found among the generating functions enumerating certain lattice walks. The simplest, and most celebrated cases are the Catalan, Schröder and Motzkin numbers, of respective generating functions

\[\frac{1 - \sqrt{1 - 4x}}{2x}, \quad \frac{1 + x - \sqrt{1 - 6x + x^2}}{2x}\]

and

\[\frac{1 - x - \sqrt{1 - 2x - 3x^2}}{2x^2}.\]

In the light of Proposition 3, we see a purely algebraic reason that these quadratic algebraic functions happen to have integer coefficients expansions: the expressions under the square root are congruent modulo 4 to a perfect square, respectively $1 - (2x)^2$ and $(1 + x)^2$. 

Next, we figure out the cases that the function~(2) is rational, i.e. that the polynomial $P_2 P_4$ is a perfect square. This is the place in the argument where the cyclotomic cases are recognized and excluded.

Lemma 4: Suppose that $P(X) \in \mathbb{Z}[X]$ is a monic integer irreducible polynomial of deg $P > 1$, such that $P_2(X)$ is not a power of $P(X)$. Then the following are equivalent:

1.  $P$ is a cyclotomic polynomial of an odd level;
2. $P_2 = P_1$;
3. $P_2 P_1$ is a perfect square;
4. the function $\sqrt{P_2 P_1}$ is rational.

Proof: If $P = \Phi_N$ with $N$ odd, squaring the set of $N^{th}$ roots of unity is simply a permutation, so $P_4 = P_2 = \Phi_N$ also, and hence $\sqrt{P_2 P_4} = \Phi_N$. 

Conversely, suppose that $P_2 P_1$ is a perfect square, and take any root $\alpha$ of our irreducible polynomial $P$. Since we assumed the polynomial $P_2 \in \mathbb{Z}[X]$ to be irreducible, $\alpha^2$ has to be among the roots $\sigma(\alpha)^4$ of $P_1$ with $\sigma$ ranging over the Galois group of the splitting field of the polynomial $P$. Letting $k$ be the order of $\sigma$, we get a $k$-fold iteration:

\[\alpha^2 = \sigma(\alpha^2)^2 = \sigma^2(\alpha)^{2^3} = \sigma^2(\alpha^2)^{2^2} = \cdots = \sigma^k(\alpha)^{2^{k+1}} = \alpha^{2^{k+1}}.\]

Hence $\alpha$ is a root of unity. $\blacksquare$

Proof of theorem 1

The main point of the next theorem is, as mentioned, to take Archimedean and non-Archimedean information about the function and piece those together into structural information about the function that we need to apply lemma 4. In what follows the $v$-adic absolute values follow the standard normalization $|\ell|_v = 1/\ell$ for the unique rational prime such that $\ell \mid v$.

Polya-Bertrandias theorem: Let $F$ be a number field and $S \subset M^{\text{fin}}_F$ a finite subset of its non-Archimedean places. Consider a formal power series

\[f(1/X) = \sum_{n\geq 0} a_n X^{-n} \in \mathbb{O}_{F,S}[[1/X]]\]

with $S$-integral coefficients $a_n \in \mathbb{O}_{F,S}$. For every $v \in S$, suppose that $f(1/X)$ is convergent on the $v$-adic disk $|1/X|_v < R_v$. Further, for every field embedding $\sigma : F \hookrightarrow \mathbb{C}$, consider a compact subset $K_\sigma \subset \mathbb{C}$ such that $\widehat{\mathbb{C}} \setminus K_\sigma$ is connected and the power series $f_\sigma(1/X) := \sum \sigma(a_n)X^{-n}$ has analytic continuation to $\widehat{\mathbb{C}} \setminus K_\sigma$. If

\[\prod_{\sigma:F\hookrightarrow\mathbb{C}} d(K_\sigma) < \prod_{v\in S} R_v, \tag{3}\]

then $f \in F(X) \cap F[[1/X]]$ is a rational power series.

The right-hand side of (3) is understood to be $= 1$ in the case $S = \emptyset$ of an empty product (a power series in $\mathbb{O}_F[[1/X]]$).

I have been unable to track down a complete proof in English, but there is, characteristically unhelpfully, one in French. When I figure out what to say about this theorem I will write about it, but for today's purposes the reader may simply take Corollary 5 below (the case $\mathbb{O}_{F,S} = \mathbb{Z}$ in the following) as a blackbox.

Corollary 5: An integer coefficients formal power series $f(1/X) \in \mathbb{Z}[[1/X]]$ as obtained as soon as $[1/X]$ is analytic on a connected complement $\widehat{\mathbb{C}} \setminus K$ of some compact set $K \subset \mathbb{C}$ having transfinite diameter $d(K) < 1$.

Proof of theorem 1: We shall denote $P^*(X) = X^n P(1/X)$ the reciprocal polynomial. It has complex factorization $P^*(X) = \prod_{i=1}^n (1 - \alpha_i X)$ and associated polynomials $P^*_m(X) := \prod_{i=1}^n (1 - \alpha_i^m X) = (P_m)^*$. Our monicity convention for $P$ now translates into the free term condition $P^*(0) = 1$, so that Proposition 3 is applicable to $P^*$. Consider the power series

\[f(1/X) := \sqrt{P^*_2(1/X)P^*_4(1/X)} \in \mathbb{Z}[[1/X]],\]

where the integrality of coefficients comes from Proposition 3. We apply Bertrandias's Theorem (Corollary~5) to this power series $f(1/X)$ and the star

\[K := K(\alpha_i^2, \alpha_i^4 : P(\alpha_i) = 0) = K(\alpha : P^*_2(1/\alpha)P^*_4(1/\alpha) = 0) \subset \mathbb{C}\]

of $2n$ vertices (possibly with overlapping edges) $\alpha_i^2, \alpha_i^4$, where $\alpha_1, \ldots, \alpha_n$ are the complex roots of $P(X)$. By Dubinin's Theorem this star has transfinite diameter bounded above by

\[d(K) \leq \left(\frac{\max_i |\alpha_i|^{4 \cdot 2n}}{4}\right)^{\frac{1}{2n}} \]

Suppose now that $\max_i |\alpha_i| < 2^{\frac{1}{4n}}$. Then $d(K) < 1$, and since the power series $f(1/X)$ has analytic continuation to the connected and simply connected domain $\widehat{\mathbb{C}} \setminus K$ in the Riemann sphere avoiding the branch points of the square root, Bertrandias's Corollary~5 yields the rationality of the power series $f(1/X)$. This means that the polynomial $P_2 P_4$ is a perfect square. If the polynomial $P_2(X) \in \mathbb{Z}[X]$ is irreducible, this is only possible when $P_4 = P_2$; Lemma 4 tells us that this is equivalent to $P$ being a cyclotomic polynomial of an odd level. If to the contrary $P_2$ is reducible, the minimal polynomial $Q(X)$ of $\alpha_1^2$ has degree $\deg Q = \deg P/2 = n/2$, and its roots are at the set $\{\alpha_1^2, \ldots, \alpha_n^2\}$. Upon passing in this way from $P$ to $Q$, Theorem 1 now follows by induction on the degree $n$. $\blacksquare$

In the paper we have been following Dimitrov proves much more: he proves a version for polynomials with coefficients in a much larger field than $\mathbb{Q}$, but the arguments used are generalisations of the results discussed above that require much more number-theoretic input, e.g. the full strength of Polya-Bertrandias is used. The core philosophy of the result is the same though: uniform bounds that depend only on a prime parameter $p$ and the degree $n$ of the polynomial. I find such results quite appealing: it's very surprising how little information is needed to obtain very strong bounds. Naturally, the method given above is good for other things too, and Dimitrov proves a few other things while raising more interesting questions, which the interested reader is encouraged to explore.