Newton polygons and Galois groups

Issai Schur

A famous result of David Hilbert asserts that there exist irreducible polynomials of every degree $n$ over ${\mathbf Q}$ having the largest possible Galois group $S_n$ . However, Hilbert’s proof, based on his famous irreducibility theorem, is non-constructive. Issai Schur proved a constructive (and explicit) version of this result: the $n^{\rm th}$ Laguerre polynomial $L_n(x) = \sum_{j=0}^n (-1)^j \binom{n}{j} \frac{x^j}{j!}$ is irreducible and has Galois group $S_n$ over ${\mathbf Q}$ .

In this post, we give a simple proof of Schur’s result using the theory of Newton polygons. The ideas behind this proof are due to Robert Coleman and are taken from his elegant paper On the Galois Groups of the Exponential Taylor Polynomials. (Thanks to Farshid Hajir for pointing out to me that Coleman’s method applies equally well to the Laguerre polynomials.) Before we begin, here is a quote from Ken Ribet taken from the comments section of this post:

Coleman was light years ahead of Steve Jobs: he was the original guy to think different. This was especially true where Newton polygons were concerned. (Steve never got into those.) I remember how obvious it was to Robert how to prove Schur’s theorem concerning the Galois groups of the polynomials obtained by truncating the Taylor series for exp(x). At first, no one could follow Robert’s reasoning. Fortunately, Robert was patient; he was always happy to provide further details.

In order to help the reader understand Coleman’s beautiful ideas, we begin with a quick crash course on valued fields and Newton polygons. A valued field is a field $K$ together with a valuation ${\rm val} : K^\times \to {\mathbf R}$ , which is a function satisfying ${\rm val}(xy)={\rm val}(x) + {\rm val}(y)$ and ${\rm val}(x+y) \geq \min \{ {\rm val}(x), {\rm val}(y) \}$ . A valuation induces a metric on $K$ by the rule $d(x,y) = {\rm exp}(-{\rm val}(x-y))$ , so one can talk about completeness and completions. For example, the completion of ${\mathbf Q}$ with respect to the $p$ -adic valuation ${\rm ord}_p$ is the field ${\mathbf Q}_p$ of $p$ -adic numbers. If $K$ is a complete valued field and $L$ is a finite extension of $K$ , there is a unique valuation on $L$ extending the given one on $K$ , which can be defined by setting ${\rm val}(\alpha) = \frac{1}{[L:K]} {\rm val}({\rm Nm}_{L/K}(\alpha))$ , where ${\rm Nm}_{L/K}(\alpha)$ is the determinant of multiplication by $\alpha$ viewed as an endomorphism of the $K$ -vector space $L$ . In particular, there is a unique extension of the valuation on $K$ to a fixed algebraic closure $\bar{K}$ , and every root of an irreducible polynomial of degree $d$ over $K$ has valuation belonging to $\frac{1}{d} {\rm val}(K^\times)$ . It follows that every root of a polynomial of degree $d$ over $K$ has valuation belonging to $\frac{1}{d'} {\rm val}(K^\times)$ for some $d' \leq d$ .

The theory of Newton polygons asserts that if $f(x)$ is a polynomial with coefficients in a complete valued field $K$ , then the valuations of the roots of $f(x)$ in some fixed algebraic closure $\bar{K}$ of $K$ can be determined in a purely combinatorial way from the valuations of the coefficients of $f(x)$ . More concretely, suppose $f(x) = a_0 + a_1 x + \cdots + a_n x^n \in K[x]$ with $a_0$ and $a_n$ nonzero, and consider the points $(i,{\rm val}(a_i))$ in the Cartesian plane (where we either omit points with $a_i = 0$ or take ${\rm val}(0)=+\infty$ ). The Newton polygon of $f(x)$ is defined to be the lower convex hull of these points. Let $(x_0,y_0), (x_1,y_1)\ldots (x_k,y_k)$ denote the successive vertices of the Newton polygon, and for $i=1,\ldots,k$ let $m_i = \frac{y_i - y_{i-1}}{x_i - x_{i-1}}$ be the slope of the $i^{\rm th}$ segment. The theorem of the Newton Polygon asserts that there are exactly $x_i - x_{i-1}$ roots of $f(x)$ in $\bar{K}$ having valuation $-m_i$ .

The 2-adic Newton polygon of $1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\frac{x^5}{5!}+\frac{x^6}{6!}+\frac{x^7}{7!}$

More vividly, imagine the points $(i,{\rm val}(a_i))$ as nails sticking out from the plane and attach a long piece of string with one end nailed to $(x_0,y_0) = (0,{\rm val}(a_0))$ and the other end free. Rotate the string counter-clockwise until it meets one of the nails; this will be the point $(x_1,y_1)$ . As we continue rotating, the segment of string between $(x_0,y_0)$ and $(x_1,y_1)$ (whose slope is $m_1$ ) will be fixed. Continuing to rotate the string in this manner until the string catches on the point $(x_k,y_k) = (n,{\rm val}(a_n))$ yields the Newton polygon. (Click here for a java applet which draws Newton polygons.)

In the figure above, the vertices of the Newton polygon for the truncated exponential polynomial $E_7(x) = 1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\frac{x^5}{5!}+\frac{x^6}{6!}+\frac{x^7}{7!}$ over ${\mathbf Q}_2$ are $(x_0,y_0)=(0,0),(x_1,y_1)=(4,-3),(x_2,y_2)=(6,-4),(x_3,y_3)=(7,-4)$ , with corresponding slopes $-\frac{3}{4}, -\frac{1}{2}, 0$ . Thus $E_7(x)$ has four roots with valuation $\frac{3}{4}$ , two roots with valuation $\frac{1}{2}$ , and one root with valuation $0$ .

Newton polygons are very useful for proving irreducibility of polynomials; for example, they yield an illuminating proof of Eisenstein’s criterion. Indeed, the Newton polygon of a degree $n$ Eisenstein polynomial $g(x)$ consists of a single segment of slope $-\frac{1}{n}$ connecting $(0,1)$ and $(n,0)$ , hence all roots of $g(x)$ have valuation $\frac{1}{n}$ . However, as mentioned above every root of a polynomial of degree $d$ over a field $K$ with value group ${\mathbf Z}$ has valuation belonging to $\frac{1}{d'} {\mathbf Z}$ for some $d' \leq d$ . Thus $g(x)$ is irreducible over $K$ .

We now prove, following Coleman, that the exponential Taylor polynomials $E_n(x) = 1+x+\frac{x^2}{2!}+\cdots + \frac{x^n}{n!}$ and the Laguerre polynomials $L_n(x) = \sum_{j=0}^n (-1)^j \binom{n}{j} \frac{x^j}{j!}$ are irreducible over ${\mathbf Q}$ for all $n$ . We will then compute their Galois groups using a classical group-theoretic result of Jordan and some elementary number theory.

Fix a prime number $p$ . To compute the $p$ -adic Newton polygons of the above polynomials, one uses the following two well-known facts:

(1) Let $n$ be a positive integer, and write $n$ in base $p$ as $n = b_0 + b_1 p + \cdots + b_s p^s$ with $0 \leq b_i < p$ and let $b = b_0 + b_1 + \cdots + b_s$ be the sum of the base $p$ digits of $n$ . Then ${\rm ord}_p(n!) = \frac{n-b}{p-1}$ .

(2) [Lucas’ Theorem] Let $n,m$ be positive integers with $k < n$ , written in base $p$ as $n = b_0 + b_1 p + \cdots + b_s p^s$ and $m = a_0 + a_1 p + \cdots + a_s p^s$ . (We add extra zeros to the base $p$ expansion of $m$ if necessary so that the two expansions have the same length.) Then $\binom{n}{m} \equiv \binom{b_0}{a_0} \binom{b_1}{a_1} \cdots \binom{b_s}{a_s} \pmod{p}$ .

It is an exercise using (1) to show that if we write $n = b_1 p^{n_1} + b_2 p^{n_2} + \cdots + b_s p^{n_s}$ with $n_1 > n_2 > \cdots > n_s$ and $0 < b_i < p$ , then the vertices of the Newton polygon of $E_n(x)$ are $x_0 = (0,0)$ and $(x_i,-{\rm ord}_p(x_i!))$ for $1 \leq i \leq s$ , where $x_i = b_1 p^{n_1} + \cdots + b_i p^{n_i}$ , and the corresponding slopes of $E_n(x)$ are $m_i = \frac{-(p^{n_i} - 1)}{p^{n_i}(p-1)}$ .

Moreover, using (2) we see that the $p$ -adic Newton polygon for $L_n(x)$ is equal to the Newton polygon for $E_n(x)$ . Indeed, each coefficient of $L_n(x)$ has valuation at least as big as the corresponding coefficient of $E_n(x)$ , and it follows from Lucas’ theorem that $\binom{n}{x_i} \equiv 1 \pmod{p}$ , so in particular ${\rm ord}_p(\binom{n}{x_i})=0$ . (Instead of (2), one could also apply Kummer’s theorem that ${\rm ord}_p(\binom{n}{m})$ is equal to the number of carries when $m$ is added to $n-m$ in base $p$ .)

Let $f(x)$ be any polynomial of degree $n$ with coefficients in ${\mathbf Q}$ having the same Newton polygon as $E_n(x)$ and $L_n(x)$ for all primes $p$ . We draw the following global conclusions from the local considerations above:

(A) $f(x)$ is irreducible over ${\mathbf Q}$ .

Indeed, if $p^m$ divides $n$ then $p^m$ divides the denominator of each $m_i$ in lowest terms, hence the denominator of the valuation of each root of $f(x)$ in lowest terms. This implies that $p^m$ divides the degree of every irreducible factor of $f(x)$ over ${\mathbf Q}_p$ , hence over ${\mathbf Q}$ as well. Thus every irreducible factor of $f(x)$ over ${\mathbf Q}$ has degree divisible by $n = \prod_p p^{{\rm ord}_p(n)}$ .

(B) If $n/2 < p \leq n$ is a prime number, then the Galois group $G$ of $f(x)$ contains a $p$ -cycle.

To see this, first note that $p \leq n$ implies that $n_1 \geq 1$ , and thus $p$ divides the denominator of $m_1$ . As above, this implies that $p$ divides the degree of any extension of ${\mathbf Q}_p$ formed by adjoining a root of $f(x)$ with valuation $-m_1$ . Thus $p$ divides the degree of the splitting field of $f(x)$ over ${\mathbf Q}_p$ , and hence over ${\mathbf Q}$ as well. This means that $p$ divides the order of $G$ , so by Cauchy’s theorem $G$ contains an element of order $p$ . Since $p > n/2$ , the only elements of order $p$ in $S_n$ are $p$ -cycles.

(C) $G$ contains the alternating group $A_n$ for all $n \neq 6,7$ . If $G$ contains a 3-cycle then this holds for $n = 6,7$ as well.

For this, we first observe that by (the proof of) Bertrand’s Postulate, for each integer $n \geq 8$ there is a prime number $p$ with $n/2 < p < n-2$ . On the other hand, a well-known group-theoretic result due to Camille Jordan says that a transitive subgroup of $S_n$ which contains a $p$ -cycle for some prime $p$ with $n/2 < p < n-2$ must contain $A_n$ . Combined with (A) and (B), this proves (C) for $n \geq 8$ . For $n \leq 7$ , we can instead use the fact that a transitive subgroup of $S_n$ which contains a 3-cycle and a $p$ -cycle for some prime $p$ with $n/2 < p$ must contain $A_n$ (cf. Theorem 2.2 here).

(D) (Schur) The Galois group of $L_n(x)$ over ${\mathbf Q}$ is $S_n$ for all $n$ . The Galois group of $E_n(x)$ is $S_n$ if $4 \nmid n$ and $A_n$ if $4 \mid n$ .

First, we can use Dedekind’s theorem (Theorem 4.14 in these notes) to show that the Galois group contains $A_n$ for all $n$ ; this amounts to finding a prime $q$ for $n=6,7$ such that $f(x) \pmod q$ factors into an irreducible cubic times linear factors. (Exercise!) It remains to distinguish between the possibilities $A_n$ and $S_n$ for $G$ , which can be done by looking at the discriminant: the Galois group will be $A_n$ if the discriminant is a square in ${\mathbf Q}$ and $S_n$ otherwise (see Theorem 4.7 here). It so happens that there are beautiful explicit formulas due to Schur for the discriminant of $L_n(x)$ and $E_n(x)$ : the discriminant of $L_n(x)$ is $\prod_{j=1}^n j^{2j-1}$ and the discriminant of $E_n(x)$ is $(-1)^{\binom{n}{2}} (n!)^n$ . (For the latter, see Coleman’s paper referenced above, and for the former see Theorem 6.71 of Szego’s book Orthogonal Polynomials.) It follows easily from these formulas and Bertrand’s postulate that the discriminant of $L_n(x)$ is never a square, and the discriminant of $E_n(x)$ is a square iff $n \mid 4$ .

Concluding Remarks:

1. For more on p-adic numbers, valuations, and local fields, including proofs of many of the assertions made above, see for example Chapter 5 of my course notes on Algebraic Number Theory, these notes by Jack Thorne, or Serre’s book Local Fields. A reference for the theory of Newton polygons is the book An Introduction to G-Functions by Dwork, Gerotto, and Sullivan.

2.Schur’s proof of the irreducibility of exponential Taylor polynomials was quite different from what we’ve presented here; it relies on a stronger version of Bertrand’s postulate and applies to a much larger class of polynomials; see this handout by Keith Conrad.

3. There is a one-parameter family $L_n^\alpha(x)$ of generalized Laguerre polynomials which includes both the classical Laguerre polynomials $L_n(x)$ (when $\alpha = 0$ ) and the exponential Taylor polynomials $E_n(x)$ considered in this post. One can use the Newton polygon method described here to prove that for fixed $\alpha$ , the Galois group of $L_n^\alpha(x)$ contains $A_n$ for all but finitely many $n$ . See this paper and the references therein.

4. Another explicit family of polynomials over ${\mathbf Q}$ having Galois group $S_n$ for all $n$ is given by $f_n(x) = x^n - x - 1$ .

Ernst Selmer

The irreducibility of these polynomials was proved by Ernst Selmer in this paper; the argument is tricky but elementary.

To see that the Galois group is $S_n$ , we follow the exposition of Serre from his book Topics in Galois Theory (p.42). A prime $p$ divides the discriminant of $f_n(x)$ if and only if $f_n(x)$ and its derivative $f_n'(x) = nx^{n-1} - 1$ have a common root modulo $p$ . Substituting $x^{n-1} \equiv 1/n$ into $f(x) \equiv 0$ , we get $x \equiv n/(1-n) \pmod{p}$ . Hence there can be at most one double root modulo $p$ for each prime $p$ which ramifies in a splitting field for $f(x)$ . This implies that the inertia subgroup at $p$ in $G = {\rm Gal}(f)$ is either trivial or of order 2 and generated by a transposition. Since ${\mathbf Q}$ is simply connected (i.e., has no nontrivial unramified extensions), $G$ is generated by its inertia subgroups. By Selmer’s theorem, $G$ is transitive, and we have just shown that $G$ is generated by transpositions. But a transitive subgroup of $S_n$ generated by transpositions must be equal to $S_n$ .

6 thoughts on “Newton polygons and Galois groups”

galoisrepresentations says:

May 26, 2014 at 7:39 am

I hadn’t seen that argument of Serre before — it’s quite slick.

Luis Gómez Sánchez A. says:

June 20, 2015 at 12:20 am

Very nice for me to read this article, both by its content and the portrait of Selmer of whom I studied hard his classic and voluminous paper on cubics for my thesis in Montpellier. But also I saw your link “Effective Chabauty” and felt strong reverence for my excellent teacher of Grenoble who has died since some time ago.

Pingback: p-adic Numbers and Dissections of Squares into Triangles | Matt Baker's Math Blog
mabud says:

November 20, 2018 at 8:11 am

very nice post

Matt Baker says:

September 18, 2020 at 1:32 pm

Keith Conrad has written up a simple algebraic proof of Selmer’s theorem (mentioned in Concluding Remark 4 above) here: https://kconrad.math.uconn.edu/blurbs/ringtheory/irredselmerpoly.pdf

Pingback: How does Schur determine Galois groups of truncated exponential series? – Math Solution

Matt Baker's Math Blog

Thoughts on number theory, graphs, dynamical systems, tropical geometry, pedagogy, puzzles, and the p-adics

Newton polygons and Galois groups

6 thoughts on “Newton polygons and Galois groups”

Leave a Reply Cancel reply

Share this:

Like this:

Related

6 thoughts on “Newton polygons and Galois groups”

Leave a Reply Cancel reply