Computational Verification of M_{11} and M_{12} as Galois Groups over Q

Henri Darmon  David Ford
Department of Mathematics  Department of Computer Science
Harvard University  Concordia University
Cambridge, Massachusetts 02138 Montreal, Quebec H3G 1M8
U.S.A.  Canada

1. The Theory

For n = 11 and n = 12 we exhibit f(x) ∈ Z[x] monic, irreducible of degree n, which can be seen by the standard techniques of [1] to have M_{n} ⊆ Gal_{ℚ}f ⊆ A_{n}. We prove Gal_{ℚ}f = M_{n} by demonstrating that Gal_{ℚ}f is not transitive on sets of roots taken n − 6 at a time. The example polynomials are derived from [5].

We assume the prime p has been chosen so that f(x) has n distinct p-adic integer roots. We let α_{1}, …, α_{n} be the roots of f(x) in Z_{p}, β_{1}, …, β_{n} the roots of f(x) in C, and R_{n} a complete set of coset representatives of M_{n} in A_{n}.

We define

F (x_{1}, … x_{n}) = ∑_{θ} ∏_{j∈θ} x_{j},

the subscripts in each term being taken from a distinct (n − 6)-tuple θ of the Steiner system S(n − 7, n − 6, n). By definition, F (x_{1}, … x_{n}) is fixed by any σ ∈ M_{n}. We assume the values of σF (α_{1}, …, α_{n}) are known to be distinct as σ ranges over R_{n}. Then Gal_{ℚ}f ≠ A_{n} if and only if there is a labelling of the roots for which F (α_{1}, …, α_{n}) ∈ Z.

We define

g(x) = ∏_{σ∈R_{n}}(x − σF (α_{1}, …, α_{n})) = ∏_{σ∈R_{n}}(x − σF (β_{1}, …, β_{n})) ∈ Z[x].

It is enough to show that g(v) = 0 for some v ∈ Z. Taking B an upper bound on the absolute values of the conjugates of F (β_{1}, …, β_{n}), h = |R_{n}|, and k sufficiently large, we have

|g(v)| ≤ (|v| + B)^{h} < p^{k}.

If we can produce a labelling of the roots for which

(1)  F (α_{1}, …, α_{n}) ≡ v (mod p^{k})

it will follow that g(v) ≡ 0 (mod p^{k}), so that g(v) = 0, and the proof will be complete.

2. The Method

The value of v is discovered by examination of the values of σF (β_{1}, …, β_{n}), σ ∈ R_{n}, using sufficiently precise approximations of β_{1}, …, β_{n}.

By testing whether f(x) divides x^{p} − x mod p we discover the smallest prime modulus p for which f(x) has n distinct roots. It follows that f(x) has n distinct roots α_{1}, …, α_{n} in Z_{p}.

We confirm that σF (α_{1}, …, α_{n}) assumes distinct values mod p^{2} for σ ∈ R_{n} (the values are not distinct mod p). In the process we discover a “correct” labelling of the roots, so that F (α_{1}, …, α_{n}) ≡ v (mod p^{2}).

When the roots are correctly labelled we apply Hensel lifting to obtain sufficiently precise rational integer approximations of the p-adic integer roots so that (1) can be confirmed.

The search for the splitting prime p and the enumeration of the distinct values of

σF (α_{1}, …, α_{n}) (mod p^{2})

were programmed in PASCAL and VAX MACRO assembler. The Hensel lifting was done by a program in the ALGEB language (see [2]). All computations were performed on a VAX 8550 computer at the Computer Centre of Concordia University.

3. An example for M_{11} The Steiner system S(4, 5, 11) is described in [3], from which we take

f(x) = x^{11} + 101x^{10} + 4151x^{9} + 87851x^{8} + 976826x^{7} + 4621826x^{6}
− 5948674x^{5} − 113111674x^{4} − 12236299x^{3} + 1119536201x^{2}
− 1660753125x − 332150625.

We find:

h = 2520; v = −688814; B = 111000000; p = 37061; k = 4439.

A correct labelling of the p-adic integer roots is given by

α_{1} ≡ 3562 α_{4} ≡ 6490 α_{7} ≡ 9100 α_{10} ≡ 15236
α_{2} ≡ 3891 α_{5} ≡ −17375 α_{8} ≡ −5956 α_{11} ≡ 7030
α_{3} ≡ 4847 α_{6} ≡ −18529 α_{9} ≡ −8397

The Hensel lifting for this example required 7 hours, 32 minutes of CPU time.

4. An example for M_{12} The Steiner system S(5, 6, 12) is described in [4], from which we take

f(x) = x^{12} + 100x^{11} + 4050x^{10} + 83700x^{9} + 888975x^{8} + 3645000x^{7}
− 10570500x^{6} − 107163000x^{5} + 100875375x^{4} + 1131772500x^{3}
− 329614375x^{2} + 1328602500x + 332150625.

We find:

h = 2520; v = −7508700; B = 2843000000; p = 1044479; k = 3959. A correct labelling of the p-adic integer roots is given by

\begin{aligned}α_{1} & ≡ & −480839 & α_{4} & ≡ & −199074 & α_{7} & ≡ & 216720 & α_{10} & ≡ & 394385 \\ α_{2} & ≡ & −319442 & α_{5} & ≡ & −116833 & α_{8} & ≡ & 392842 & α_{11} & ≡ & −100630 \\ α_{3} & ≡ & −292338 & α_{6} & ≡ & −54522 & α_{9} & ≡ & 425417 & α_{12} & ≡ & 134214 \end{aligned}

The Hensel lifting for this example required 14 hours, 12 minutes of CPU time.

References

1. D. W. Erbach, J. Fischer, & J. McKay. Polynomials with PSL(2,7) as Galois Group. Journal of Number Theory 11 (1979), 69–75.

2. D. Ford. On the Computation of the Maximal Order in a Dedekind Domain. Ph.D. Dissertation, Ohio State University (1978).

3. D. Ford & J. McKay. From Polynomials to Galois Groups. Lecture Notes in Computer Science 204 (1985), 535–536. Proc. Eurocal ’85 (Linz).

4. D. Ford & J. McKay. Computation of Galois Groups from Polynomials over the Rationals. In COMPUTER ALGEBRA, D. Chudnovsky & R. Jenks, editors, pp. 145–150. Marcel Dekker, New York (1988).

5. B. H. Matzat & A. Zeh-Marschke. Realisierung der Mathieugruppen M_{11} und M_{12} als Galoisgruppen über Q. Journal of Number Theory 23 (1986), 195–202.