Newton polygons and Galois groups

Issai Schur

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

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.

One thought on “Newton polygons and Galois groups

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s