Math 263x is a new “topics class” concentrating on some of the computational tools and techniques that can complement theoretical research in number theory, algebraic geometry, and related fields. We meet Mondays and Wednesdays from 1:00 PM to 2:00 PM in Room 222 of the Science Center.

If you find a mistake, omission, etc., please let me know by e-mail.

September 5: Introduction
September 10: Belyi maps and some of their uses
September 12: Start on computation of Belyi functions
September 17: More on Belyi polynomials etc.
September 19: Resultants
September 24: A cube minus a square
September 28 [sic]: Interlude on sorting and searching
October 1: Using multivariate (and usually p-adic) Newton's method
October 3: Wednesday, Oct. 3: Multivariate p-adic Newton, cont'd
[October 8: No class: University holiday (Columbus Day)]
October 10: positive- [usually 1-]dimensional families
October 15: Curves of genus 0 through 5
October 17: Hyperelliptic curves; curves of genus 1; a Weil-Belyi function on an elliptic curve (and parametrizing 5-torsion etc.)
October 22: Overview of complex reflection groups and their invariant rings (which give rise to highly symmetric curves)
October 24: The Hilbert-Molien series of a group representation; A₄, S₄, A₅ acting on the Riemann sphere
Oct. 29: NO CLASS: Harvard cancelled all classes due to anticipated severe weather
October 31: Covariants of subgroups of GL₂ related to A₄ and S₄
November 5: Covariants of subgroups of GL₂ related to A₅; overview of the exceptional reflection groups of dimension 3 and higher
November 7: Hurwitz quaternions, the W(D₄) lattice, and the W(F₄) invariants; Belyi functions parametrizing trinomials with interesting Galois groups
Nov. 12 and 14: NO CLASS: I'll be in Lausanne, Switzerland
November 19: Introduction to (classical (elliptic)) modular curves
[November 21 is the start of Thanksgiving break]
November 26: Fricke and Atkin-Lehner involutions of X₀(N) and some of their uses
November 28: Non-Atkin-Lehner elements of the normalizer of Γ₀(N)

Trying all x < p^1/2 works in finite time, but not “finite enough” even with the computer (and if/when the computers catch up I can double the number of digits in p…). One proof of the theorem almost yields an efficient algorithm, using an idea attributed to Cornacchia (1908): x/y is a square root of −1 mod p, and conversely given such a root we recover (x,y) in time ≪log^cp by lattice reduction (which in two dimensions is basically the Euclidean algorithm). All the ingredients we used are already implemented in packages such as gp, so the resulting algorithm can be expressed by a one-liner such as

[Victor Miller 1992, transcribed some time later into the new gp syntax]. So for instance

fermat(p) = qflll([lift(sqrt(Mod(-1,p))),p;1,0])[1,]
#
fermat(31415926535897932384626433832795028841)

returns [4223562448517994405, -3684758713859920604] in about  0 ms. (and this would even be feasible, if arduous, to do by hand).

Why did we write that this analysis “almost yields an efficient algorithm”? Well, how do we find the square root mod p? An embarrassment: it's easy to evaluate the Legendre symbol, but if it's +1 we generally don't know how to get a square root in deterministic polynomial time unless we assume the extended Riemann hypothesis for the Legendre character mod p — though we can do it in “random polynomial time”. However, modular square roots of small numbers can be evaluated in polynomial (albeit not practical) time by using the arithmetic of elliptic curves mod p ! That was the application Schoof gave for his algorithm [ = René Schoof: Elliptic Curves over Finite Fields and the Computation of Square Roots mod p, Math. of Computation 44, pages 483–494 (1985)] for counting rational points on an elliptic curve mod p. In our case we count points on the curve Y² = X³ − X, which is relevant because it has complex multiplication by a square root of −1: the count is p+1±2x or p+1±2y, from which we recover the two-square representation in determinstic polynomial time.

See Serre's Topics in Galois Theory (Boston: Jones & Bartlett 1992) for the application to the inverse Galois problem (perhaps the best-known arithmetic application) and other results concerning Belyi functions. In algebraic geometry, such functions might be most famous for the equality case in the Hurwitz bound of 84(g−1) on the number of automorphisms of a Riemann surface (a.k.a. algebraic curve over C) of genus g>1: if C attains this bound, or more generally has more than 12(g−1) automorphisms, then the quotient map C→C/Aut(C) is a Belyi function.

Such functions appear surprisingly often in other contexts; one of these years I might write an article on the ubiquity of Belyi functions. For now, I give references and/or links to some of the places where I've run across Belyi functions over the years:

• ABC implies Mordell, International Math. Research Notices 1991 #7, 99–109 [bound with Duke Math. J. 64 (1991)].
• The Klein Quartic in Number Theory (1998, in the MSRI volume The Eightfold Way on Klein's quartic curve x³y + y³z + z³x = 0)
• “slides” from a 1999 talk at MSRI on “Other Arithmetic Manifestations of Branched Covers”
• Shimura curve computations (1998) [especially the curves associated to groups commensurate with arithmetic triangle groups]
• Rational points near curves and small nonzero |x³−y²| via lattice reduction (2000) [see the start of Section 4, pages 22–25; some of the other material here will figure later in the course]
• Trinomials ax⁷+bx+c and ax⁸+bx+c with Galois Groups of Order 168 and 8·168 (with Nils Bruin), Lecture Notes in Computer Science 2369 (proceedings of ANTS-5, 2002; C.Fieker and D.R.Kohel, eds.), 172–188.
• My HCMR article on “The ABC’s of Number Theory” (2007)

Consider for example the case that n=6 and (a₁, a₂, a₃) = (4,1,1). As we already saw, the coincidence a₂=a₃ lets us simplfy P to the form Cx⁴(x²+ax+b) for some nonzero C and parameters a, b determined up to scaling to λa, λ²b. Even so, we expect two inequivalent solutions [corresponding to the two isomers of cyclohexadiene]. This is one of the simplest cases with a double transposition. Here it turns out that for each solution the Galois group is properly contained in S₆ (though it cannot be the alternating group A₆ or a subgroup of A₆ , because g₀ and g_∞ are odd permutations). When the two “double bonds” are adjacent, we get GL₂(F₅) (a.k.a. the (3-)transitive copy of S₅ in S₆, a.k.a. the image of the points stabilizer in S₆ under an outer automorphism of S₆); when the two “double bonds” are opposite, we have the imprimitive 48-element subgroup of S₆, isomorphic to the symmetrics of the octahedron acting on its six vertices as the stabilizer of the partition into three opposite pairs.

Indeed we find that Q(x) = 6x² + 5ax + 4b, and then that the x³ coefficient of P mod Q² is 144ab − 100a³. Thus either a = 0 or 36b = 25a². The solution a = 0 makes P a polynomial in x², which corresponds to the imprimitive solution. Thus the other case must be the GL₂(F₅) cover. A convenient choice of scaling is (a, b) = (6,25), giving the identity 27x⁴(x²+6x+25) = (3x²−12x+20) (3x²+15x+50)² − 50000.

Exercises:
i) Since we just got a sextic cover with Galois group S₅, there must also be a Belyi map of degree 5 giving the same Galois closure. The cycle structures are 32 / 41 / 221 (corresponding to the S₆ cycle structures 6 / 411 / 2211). Find the Belyi map.
ii) What happens for the Belyi polynomials of degree 7 for which g₁ is a double transposition and g₀ has shape 331 or 421?

POSTSCRIPT on some Belyi polynomials of degree at most 7 for which g₁ is a double transposition: the examples of degree 6 aren't quite the smallest, but we've in effect seen all those of smaller degree, with g₀ and g₁ interchanged (which switches P with 1−P). Thus the only degree-4 possibility is 4 / 211 / 22, where g₀ is a simple transposition, and in degree 5 one of the two possibilities is 5 / 311 / 221, where g₀ is a 3-cycle. This leaves only 5 / 221 / 221, but when g₀ and g₁ are both involutions G must be dihedral and we get a cover equivalent to a Čebyšev polynomial. Here we can calculate directly the identity x (x²+5x+5)² + 4 = (x+4) (x²+3x+1)²; translating x by 2 yields the equivalent form (x−2) (x²+x−1)² + 4 = (x+2) (x²−x−1)²; and then replacing x by 2x and dividing P by 2 yields the fifth Čebyšev polynomial 16x⁵ − 20x³ + 5x which is ramified above ±1, each of which has one simple and two double preimages.
As for degrees 6 and 7…
• In degree 6, besides the cases with cycle structures 6 / 411 / 2211, there's also 6 / 222 / 2211 and 6 / 321 / 2211. The former again has G dihedral (and also imprimitive in this case, since 6 is composite), giving rise to a Čebyšev polynomial. For the latter, there are three solutions, all generating the alternating group A₆: writing P(x) = c x³ (x+1)² (x+w), we compute that w must be one of the three roots of 25w³ − 12w² − 24w − 16, an irreducible polynomial that happens(?) to give the field Q(2^1/3); explicitly w = 2^4/3 / (3−2^1/3). [gp's nfdisc reported that disc(Q(w)/Q) = −108, which sufficed to identify the field with Q(2^1/3); there are various ways then to find w as an element of that cubic field, and then it's known that for any cubic extension K/F any two elements of K\F are related by a unique fractional F-linear transformation that can be found by linear algebra.]
• 7 / 331 / 22111: here G is necessarily the 168-element group; the polynomial is defined over Q((−7)^1/2). The Galois closure is the Klein quartic, and x is a rational coordinate on the quotient of this quartic by one of the two kinds of index-7 subgroups of G (both isomorphic with S₄ and switched by an outer automorphism of G). While the Klein quartic can be defined over Q, its automorphism group cannot. Again I refer to my article on the Klein quartic.
• 7 / 421 / 22111: here P(x) = c x⁴ (x+1)² (x+w) and there are four possibilities for w, but they are not all conjugate: two are the roots of 2w²+w+1, which again generate Q((−7)^1/2), and the others are roots of 27w²−18w−25 and generate Q(21^1/2). Indeed there are two possible Galois groups, G₁₆₈ and the full alternating group A₇; which one corresponds to which pair of w's? [...]
END POSTSCRIPT

Motivation, definition, and properties of resultants of univariate polynomials, which we'll use to eliminate one of two variables when we've brought one of these calculations down to solving two simultaneous nonlinear equations. The Sylvester matrix of P and Q has corank equal the degree of gcd(P, Q), as can be seen by identifying the row kernel with {(A, B) : deg(A) < deg(Q),  deg(B) < deg(P),  AP+BQ = 0}. If ξ is a common zero of P and Q then the column vector (ξⁿ⁻¹, ξⁿ⁻², …, ξ², ξ, 1) (where n = deg(P) + deg(Q) is the matrix size) is in the kernel. This fully accounts for the kernel if gcd(P, Q) has distinct roots. What happens if there are some roots of multiplicity 2 or greater?

Exercise: Use this to find the Belyi polynomials of degree 11 with cycle structures 3³1² and 2⁴1³ (a.k.a. 33311 and 2222111) above 0 and 1. [Start by writing P(x) = C (x³+ax+b)³ (x²+cx+d) ≡ constant mod Q² where Q(x) = P’(x) / (x³+ax+b)².] What's going on?

POSTSCRIPT re degree-11 Belyi polynomials: for 11 / 3³1² / 2⁴1³ there are 10 possibilities, in two Galois orbits of sizes 2 and 8. The larger gives G = A₁₁, but the pair gives functions defined over Q((−11)^1/2) for which G is the simple group of 660 elements, isomorphic with PSL₂(F₁₁). [This is the last of Galois' list of subgroups of index p in PSL₂(F_p), here isomorphic with A₅; we already saw the S₄ and A₄ cases, for p=7 and p=5 respectively. There's also the case of the index-6 subgroup of PSL₂(F₉) ≅ A₆.] Curiously a very similar thing happens if we change the cycle structure of g₀ to 11 / 4²1³ / 2⁴1³, as Andrew Sutherland tried: again 10=2+8 possibilities with the larger orbit giving G = A₁₁, and the smaller orbit defined over Q((−11)^1/2), but here the quadratic orbit gives G = M₁₁, the smallest Mathieu group! Both of these appear in the list of Galois groups of polynomials in Müller's paper: see the first item under (ii) and the second under (iii) in the statement of the main theorem (between pages 3 and 4). The appearance of Q((−11)^1/2) in both cases is no coincidence: it ultimately comes down to the fact that in both PSL₂(F₁₁) and M₁₁ the 11-cycle g_∞ is conjugate with its k-th power iff k is a quadratic residue of 11, even if we consider conjugacy in the normalizer of the group in S₁₁. The quadratic extension Q((−11)^1/2) arises as the subfield of the 11th cyclotomic field Q(μ₁₁) fixed by the squares in Gal(Q(μ₁₁) / Q) = (Z/11Z)^*.
END POSTSCRIPT

We begin our consideration of the important special case where g₀ and g₁ are 3- and 2-cycles with few or no fixed points, corresponding to A + B = C where B and C are nearly a square and nearly a cube (“nearly” = within low-degree factors). Such identities arise in connection with Hurwitz curves (and other highly symmetric Riemann surfaces), and also in connection with Hall's conjecture (which asserts that for integers x, y either x³ = y² or |x³ − y²| ≫_ε x^½−ε). Rather more structurally, because the discriminant of a cubic X³+pX+q is −(4p³+27q²), pairs (P, Q) of polynomials for which P³−Q² has many repeated factors often appear in connection with elliptic and modular curves and elliptic surfaces.(*) Sometimes these connections overlap: the identity (x²+10x+5)³ − 1728x = (x²+4x−1)² (x²+22x+125) yields (via a “Pell equation”) the only known infinite family of solutions of 0 ≤ |x³ − y²| ≤ x^½ [Danilov 1982]; the associated Belyi map, with exponents 51 / 33 / 2211, also gives the cover X₀(5) → X(1) of modular curves (a connection noted in [NDE 1998]: if x = 125(η(5τ) / η(τ))⁶ = w₅(η(τ) / η(5τ))⁶ then j(τ) = (x²+10x+5)³/1728x); and the Galois closure X(5) is the icosahedral Galois cover P¹ → P¹/A₅ ≅ P¹.

(*) Recall that any cubic polynomial X³+aX²+bX+c can be brought into the form X³+pX+q using the change of variable X ← X − a/3, though sometimes another choice of translate is more useful. For example, Hall's identity with deg(P)=8, deg(Q)=12, and deg(P³−Q²)=5 has P(x) = 4(x⁸ − 2x⁷ + 7x⁶ − 6x⁵ + 11x⁴ + 4x³ + 12x + 1) [without the factor of 4 the polynomial Q would not quite be in Z[x]; Hall actually used P(x+1), which has larger coefficients]. Then Q is the truncation of the Laurent expansion of P^3/2 about x = ∞ (the x^−k coefficients in this expansion vanish for 1 ≤ k ≤ 6). But it's much simpler to write the corresponding cubic as X³ + (x⁴−x³+3x²+1) X² − 2(x³−x²+2x) X + (x²−x+1), and this actually reflects a natural approach to finding these P and Q.

A basic problem: given a list x_i (1<i<N), find all coincidences x_i = x_j with i ≠ j. This seems to require (N²−N)/2 pairwise tests, but in fact can be done in time O(N log N) by first sorting the list and then looking for consecutive matches. The key fact that sorting takes time only O(N log N) is nontrivial but has been known for some time (see e.g. the beginning of Volume III of Knuth's The Art of Computer Programming). So is the fact that O(N log N) is optimal if each step can only compare two list elements (because it takes at least log₂(N!) comparisons to distinguish all N! possible orderings; see “bucket sort” and, rather more facetiously, “spaghetti sort” for models of computation that allow for O(N) sorting). This reduction from order N² to N log N makes sorting a powerful computational tool in various contexts, despite the additional space cost (usually all N of the x_i must be stored at once, even when x_i is given by a function of i, when it takes practically no space to test x_i = x_j for each pair {i, j}). A typical application is finding all solutions of f (i) = f (j) with 1≤i<j≤N, or all solutions of f (x)=g(y) with x and y in different sets. Unix utilities such as sort, uniq, and comm can be very helpful here because they implement the relevant algorithms in an efficient and often convenient form; when the files aren't in quite the right format, grep, sed, and (for more complicated tasks) editors like vi and emacs, can provide the needed pre/inter/post-processing. For example, it is easy to find in a wordlist two common words that are the same except that one begins with C and the other with U (and are more familiar and longer than crease/urease). [Here's the solution.]

Besides its application to this kind of wordplay, fast sorting finds use in some computational problems in number theory. A typical example is the search for elliptic curves E/Q with many small integral points (“small” meaning comparable with the coefficients of E; that is, x≪H² and y≪H³ if the coefficients a_i are O(Hⁱ)). In this ANTS-6 (2004) paper with Mark Watkins we did this as a heuristic proxy for large Mordell-Weil rank. The factorization trick to (in essence) find y, y’ and B given x, x’ and A in x³ + Ax + B − y² = x’³ + Ax’ + B − y’² = 0 will recur later this term when/if we reach parametrizations of elliptic surfaces with two sections. Another kind of application is to searching for solutions of Diophantine equations of the form  f (x, y) = g(z, t). When  f  is itself of the form  f (x, y) = f₁(x) + f₂(y), and the same is true of g, there are further nontrivial improvements that reduce the space requirement from the expected order of N² down to N; see for instance Dan Bernstein's sortedsums page. (It still takes N² time, though there's no factor of log N because the lists of f₁, f₂, g₁, g₂ values can be pre-sorted in time only N log N.)

For a paradigm we shall use Hall's identity, already exhibited at the end of last Monday's notes: deg(P³−Q²)=5, where P is the octic P(x) = 4(x⁸ − 2x⁷ + 7x⁶ − 6x⁵ + 11x⁴ + 4x³ + 12x + 1), and Q is the truncation of the Laurent expansion of P^3/2 about x = ∞, whose x^−k coefficients in this expansion vanish for 1 ≤ k ≤ 6. This is the first primitive example of an ABC identity deg(P³−Q²) = m+1 with deg(P) = 2m and deg(Q) = 3m; this can also be seen combinatorially from the structure of permutations g₀, g₁, g_∞ of 6m objects that satisfy g₀g₁g_∞=id and have cycle structures 3^2m, 2^3m, 1^5m+1(5m−1); they correspond to trees on 2m vertices (the 3-cycles), each of degree 1 or 3, embedded in the plane (so each cubic vertex has an orientation, and therefore not quite the same as the azanes N_m−1H_m+1, which do not come with a planar embedding — and much different from boranes, which turn out to be much more complicated than ball-and-stick chemistry would suggest). Hall's example has m=4; see below for m=1,2,3.

For any m, we can normalize P and Q to be monic, and require the Laurent expansion of P^3/2 to match Q to within O(x^1−2m); that is, the x^−k coefficient must vanish for 1 ≤ k ≤ 2m−2. Each coefficient is a polynomial in the 2m non-leading coefficients of P, call them c_i (i = 0, 1, 2, … 2m−1), so it might seem we have 2 equations too few; but in fact there are only 2m−2 parameters for P once we account for the two-dimensional group of affine linear transformations (the “ax+b group”). We can choose a canonical translation by setting the x^2m−1 coefficient of P, and thus also the x^3m−1 coefficient of Q, to zero (these are the next-to-leading coefficients; for m=1 this is the familiar “completing the square”). This leaves one dimension of equivalences, scaling x to ax for some nonzero a; this multiplies each c_i by a^2m−i. We can thus interpret (c_2m−2 : c_2m−3 : c_2m−4 : … : c₁ : c₀) as a point in (2m−2)-dimensional weighted projective space with weights (2, 3, 4, …, 2m−1, 2m), and are looking for a point in the intersection of (2m−2) hypersurfaces, with the vanishing of the x^−k coefficient corresponding to a hypersurface of weighted degree 2m+k.

We encountered such a problem before (see the end of the Sep.12 notes), where the number of solutions was given by Bézout's product formula. But here such a formula would grossly overestimate the number of solutions because there's an (m−2)-dimensional variety of spurious solutions (P, Q) = (R², R³). Indeed it is not immediately obvious that there are non-spurious solutions; their existence follows from the topological construction of Belyi functions, but that still leaves the question of computing the polynomials explicitly. This is easy for the first few m, especially since the first few equations must be linear in the first few coefficients (counting from c₀), which lets us solve for the first m/3+O(1) coefficients as rational functions of the remaining 5m/3 or so. But then we're left with a complicated system of nonlinear equations. m=4 is the first case where resultants fail us: the first equation has weight 13, so is linear in c₀ (weight 8), but the next equation (weight 14) is already quadratic in c₁ (weight 7), and there are still four more dimensions to go. What to do? [Since we're using this example as a paradigm, we pretend that we don't know how to exploit the special “cube minus a square” structure; but even those tricks give out before long, leaving us with even more complicated simultaneous equations in four or more variables.]

We'll exploit our foreknowledge that the solutions must be rational numbers. (We shall soon see how to adapt this method to solutions that are not necessarily rational but still algebraic of small degree.) We do not know in advance how complicated these rational numbers must be (in the present case we at least pretend not to know…), but we hope that they're simple enough that we can approximate them closely enough to guess the numerator and denominator, and then confirm the guess by checking that we have an exact solution of our system of equations. The complexity of a rational number c is measured by its height H(c): if c=r/s in lowest terms then H(c) = max(|r|,|s|). The number of solutions of H(c) ≤ M is asymptotically proportional to H², so we need enough precision to tell at least that many numbers apart, i.e. more than 2 log H(c) digits; equivalently, c must be known to within O(H⁻²). Fortunately that necessary level of accuracy is also enough to recover r and s, and not just in theory but practically, using continued fractions, a.k.a. the Euclidean algorithm. This is a common enough application that it is often implemented as a pre-existing routine, see e.g. bestappr in gp.

If we have an approximation that's close but not good enough for this purpose, we can repeatedly improve it using Newton's method. Suppose we want to find a zero x_* of a differentiable function F on d-dimensional space, and have an approximation x₀ that's within ε of x_*. Then, as in the familiar case d=1, we expect to get a better approximation by setting x₁ = x₀ − (F’(x₀))⁻¹F(x₀). Note that F’ is a matrix-valued function. If this function is continuous, and F’(x_*) is invertible, then x₁ is within O(ε²) of x_* provided that ε was small enough. Iterating then gives us errors of order ε⁴, ε⁸, ε¹⁶, etc., doubling the precision at each step; and soon we reach enough precision to recover the rational coordinates of x_*.

In practice we won't actually compute F’(x_*), because F will typically be quite complicated (in our example there are rational functions of moderately high degree and a square root), making the formulas for its partial derivatives horrendous. Fortunately it's good enough to approximate them by the “difference quotient”: for each unit vector e_j, replace the column F’(x₀) e_j of F’(x₀) by ε⁻¹(F(x₀+e_j)−F(x₀)). This still requires d² function evaluations, but they're usually much simpler functions than the entries of the formal derivative of F, and we're now spared the chore of working out this formal derivative.

But we still don't know how to find a close enough initial approximation x₀ — and indeed it's hard to estimate just how close we must be since we have no handle on how close F’(x_*) and its nearby values F’(x) are to being singular, and how fast F’ changes near x_*. We often circumvent this problem by remembering a ubiquitous slogan of modern number theory: treat all completions of a number field on an equal footing to the extent possible. Here instead of the Archimedean completion R we'll work with a p-adic completion Q_p, where numerical analysis is much simpler thanks to the non-Archimedean norm. Better yet, finding the initial approximation usually reduces to an exhaustive search mod p, which is often feasible past the range of Gröbner-basis methods (though this method too must fail eventually, being exponential in the number of variables). As long as F’(x_*) is not just invertible but invertible mod p, Newton will work starting from (an arbitrary lift to Z_p of) x_* mod p, so that once we've found the solution mod p by exhaustive search, we approximate x_* to p-adic precision 2^N in N Newton steps.

Warning: even though P had quite small coefficients (absolute value at most 12), the weighted projective coordinates (c_2m−2 : c_2m−3 : c_2m−4 : … : c₁ : c₀) are more complicated, e.g. even scaling c_i by 4^m−i leaves us with (84 : 176 : 2366 : 13536 : 26884 : 218864 : 268777); and we cannot solve for individual c_i, only for weight-zero expressions like c₈ / (c₂c₆), which are more complicated yet. Fortunately it's easy to get enough p-adic precision. In hairier settings, we might first recognize a relatively simple weight-zero expression, which would give us a start on choosing a good scaling (in our illustrative example, c₂³ / (c₃²) = 9261/484 = 21³/22² suggests (c₂, c₃) = (21, 22) as a good starting normalization). At the end it can still be something of an art to massage P to a more appealing form (12 vs. 268777).

As promised, here are the polynomials for m=1,2,3. They all have imprimitive Galois groups. In general if the Galois group of a cover C→P¹ is imprimitive then the cover factors as C→C₀→P¹. If the original cover was ramified only above 0, 1, ∞ then the same is true of C₀→P¹, and this Belyi map may be of interest in its own right. In our setting the other map C→C₀ can always be taken to be the squaring or cubing map, which is possible if m+1 a multiple of 2 or 3 respectively.
• For m=1, the permutations generate a subgroup of S₆ that fixes a partition of the six objects into three pairs. On the polynomial side, we can normalize the quadratic P to be monic with no linear coefficient, say P(x) = x² + 2a for some nonzero a. Then Q(x) = x³ + 3ax and P³−Q² = 3a²x² + 8a³. All these solutions are equivalent over C, but the equivalence class over Q depends on a mod (Q^*)². The three pairs permuted by the Galois group are pairs {±x} of roots of P³/Q² = t. Writing P³/Q² in terms of X:=x² yields the degree-3 Belyi function (X+2a)³ / (X (X+2a)²) with cycle structures 3/21/21, equivalent to the cover of modular curves X₀(2) → X(1).
• For m=2, the permutations fix a partition of 12 objects into four triples. Once we normalize the quartic polynomial P by translating x to kill the x³ coefficient, the quadratic and constant coefficients must vanish as well (check this directly!), leaving a polynomial we can write as a multiple of P(x) = x⁴ + 4ax. Then Q(x) = x⁶ + 6ax³ + 6a² and P³−Q² = −(8a³x³ + 36a⁴). All these solutions are cubic twists of each other. Writing P³/Q² as a function of x³ yields a degree-4 Belyi function with cycle structures 31/31/22, equivalent to the cover of modular curves X₀(3) → X(1).
• Finally, for m=3, the group fixes a partition of the 6m=18 objects into nine pairs. The polynomisls were obtained by Birch in 1961: up to twist and scaling, P(x) = 36x⁶ + 24x⁴ + 10x² + 1,   Q(x) = 216x⁹ + 216x⁷ + 126x⁵ + 35x³ + 21x/4, and P³−Q² = 9x⁴/2 + 39x²/16 + 1. Writing P³/Q² as a function of x³ yields a degree-9 Belyi function with cycle structures 22221/333/711; since the corresponding permutations have orders 2, 3, 7, the Galois closure is a Hurwitz curve. It turns out to be the Fricke-Macbeath curve of genus 7, second-smallest after the Klein quartic, with 504 automorphisms that constitute the simple group SL₂(F₈). [While the Fricke-Macbeath curve can be defined over Q, the automorphisms can only be defined over the cyclic cubic extension Q(2 cos(2π/7)); the group Gal(Q(2 cos(2π/7)) / Q) acts on SL₂(F₈) via Aut(F₈), giving a Galois extension of Q(t) with group ΣL₂(F₈) = SL₂(F₈) : Aut(F₈).]

Overview of lattice basis reduction, accomplished in polynomial time by the Lenstra-Lenstra-Lovász algorithm, which for us is a tool for finding integer relations and similar Diophantine-approximation tasks. For us, we need it to recognize an algebraic number c of degree at most d from a good approximation, which is tantamount to finding an integer relation in 1, c, c², …, c^d, or in c and 1, a, a², …, a^d−1 if we already know that c is in the field generated by the algebraic number a of degree d. These algorithms are usually presented over R, but (at least in their incarnation as lattice-reduction techniques) work equally well (i.e. via Euclidean lattices of comparable parameters) over Q_p, and indeed gp's lindep and algdep work for p-adic as well as real (or complex) numbers. If we know approximations to more than one algebraic conjugate of c, say δ conjugates, then we can use them all together, looking for integer relations on vectors of length δ. (The degree d can't be too large, but if it's so large that we cannot find c with a few thousand digits of precision then we usually didn't care much about this c as an algebraic number in the first place…)

Lattice reduction in dimension >2 can give rise to useful practical improvements even for problems that we already know how to solve using 2-dimensional lattice reduction (a.k.a. Euclid). For example, if we're trying to recover a point (c₀ : c₁ : c₂ : … : c_k) of height at most H in (unweighted) projective space P^k(Q), we need to know the point to within about 1 / H² to apply continued fractions to (say) each ratio c_i / c₀, but in fact an H^−(k+1)/k approximation suffices if we use all the c_i together and apply LLL in dimension k+1. [NB halving the necessary precision can gain a factor of about 4 in the computing time. See my ANTS-4 paper for further improvements when we know a proper subvariety of P^k(Q) that contains our point.] Likewise for an element of (say) Q(i), where the real and imaginary parts usually have the same denominator to within a small factor; indeed in this case it's even better to search for a representation (a+bi) / (c+di) with a, b, c, d small.

Finally (and you may have been wondering about this for a while now), how do we know that our solution will have even one conjugate defined over Q_p? Well in general we don't, and can claim only a technique that often works well in practice, not a provably efficient algorithm. (For “provably efficient” we'd also need an upper bound on the height of the solution.) Still, we expect — based first on a naïve probabilistic argument, and then on its corroboration by Čebotarev's density theorem — that for random p the expected number of conjugates defined over Q_p should equal 1, so (barring bad luck) we should find one before p gets so large that we run out of patience or computing time. In any case, once we've found an algebraic solution by hook or by crook we can prove it is correct by simply checking that the desired identity holds — at least if an identity is all we're looking for, with no additional condition like the identification of G when it is not determined uniquely by the cycle structures and other available data.

genus 0: over C it's just the projective line (a.k.a. Riemann sphere), but over a field that's not algebraically closed (nor finite) even genus-zero curves needn't be trivial. Such a curve is always a smooth conic in P² (embedded by the space Γ(−K) of anticanonical sections, which has dimension 3 by Riemann-Roch); thus the curve is rational iff it has a rational point ("if" by the usual slope parametrization, and the converse is trivial). More generally a genus-zero curve is rational iff it has a divisor D of odd degree: "if" because some D+cK has degree 1, and is effective by Riemann-Roch; and again "only if" is trivial. All our genus-zero covers so far came with such a D, indeed a distinguished point, which could be described as the unique multiplicity-m preimage of t for some m≥1 and t in {0,1,∞} (being careful that we're not in a case where we've had to make two or all three branch points algebraic conjugates). But that need not be the case in general. For example, there's a unique action defined over Q of the symmetric group S₄ on a curve of genus zero; but the curve cannot be rational over Q, or even over R, because then (by the usual averaging argument) S₄ would be contained in O₂(R)/{±1}, and thus would contain a cyclic group with index at most 2. [This could also be checked by calculating the Schur indicator of the 2-dimensional irreducible representation of the relevant central extension 2S₄, or indeed of its subgroup isomorphic with the 8-element quaternion group.] So the genus-zero curve must be "pointless"; explicitly it is the conic x²+y²+z²=0, with S₄ acting by signed coordinate permutations. [... quaternion algebras like Hurwitz {2,∞}, Br₂, ...]

genus 1: again, over an algebraically closed field such as C we have a familiar picture, this time an elliptic curve C, since there must be a rational point P₀. More generally, any divisor D of positive degree is still effective by Riemann-Roch, and if deg(D)=1 then D∼(P₀) for some rational point P₀. We can then use the sections of 3P₀ to embed C in P² as a cubic in Weierstrass form y² + a₁xy + a₃y = x³ + a₂x² + a₄x + a₆, calculating the coefficients a_i by comparing Laurent expansions about P₀ as usual. Sometimes (especially when C arises as a modular curve such as X₀(11)) it is more convenient to start from a degree-2 function x on C and a holomorphic differential ω, and then set z = dx/ω, which is anti-invariant under the involution of C satisfying x ι = x and is regular away from the poles of x, and thus satisfies an equation z² = P(x) for some polynomial P of degree 3 or 4 according as x has one double pole or two simple poles. On modular forms, the q-expansions of modular forms often give a convenient handle on rational functions and holomorphic functions. Here we may tell Sage:

ModularForms(11,prec=14).echelon_basis()

[
1 + 12*q^2 + 12*q^3 + 12*q^4 + 12*q^5 + 24*q^6 + 24*q^7 + 36*q^8 + 36*q^9 + 48*q^10 + 72*q^12 + 24*q^13 + O(q^14),
q - 2*q^2 - q^3 + 2*q^4 + q^5 + 2*q^6 - 2*q^7 - 2*q^9 - 2*q^10 + q^11 - 2*q^12 + 4*q^13 + O(q^14)
]

Z=subst(z^2,q,serreverse(1/x)); subst(truncate(Z),q,1/X)

But what if there is no divisor of degree 1? Any genus-1 curve C comes with a divisor D of some positive degree d, and Γ(D) has dimension d, giving a map to P^d−1 that is an embedding as an “elliptic normal curve ” for d≥3 (for d=2 it's a 2:1 map, giving a model of C of the form y² = quartic(x)). As with curves of increasing genus, elliptic normal curves of increasing degree d get increasingly complicated, and are complete intersections only for the smallest few cases; here these are d=3 (a plane cubic) and d=4 (the intersection of two quadrics). Fortunately the d≤4 cases are most if not all the ones we'll encounter. Still even those cases are much more complicated than the plane conics that are as tricky as genus-zero curves get. Two famous examples already for d=3 are x³+py³+p²z³=0 for p prime (no p-adic solution) and 3x³+4y³+5z³=0 (Selmer's example of a cubic with no rational points even though there is no local obstruction). [To be continued Wednesday…]

genus 2: Once g≥1, the curve C is of general type (the canonical divisor is positive). The space of holomorphic differentials gives a map, the canonical map, to P^g−1, which is either an embedding or a 2:1 map. In the latter case C is hyperelliptic, which is the case for all curves of genus 2 but only for special curves once g≥3. At least if g is even (or if the ground field is algebraically closed, or finite, or more generally is a field with trivial Br[2]), a hyperelliptic curve of genus g has the form y² = P(x) where P is a polynomial of degree 2g+2 without repeated roots. For g=2, the degree-2 function x on C is simply the ratio, say ω₁/ω₂, of generators of the 2-dimensional space of holomorphic forms. The hyperelliptic involution ι then takes any (x, y) to (x, −y), and takes each ω_i to −ω_i (as can be seen either from the explicit formulas (ω₁, ω₂) = (x dx/y, dx/y) or by observing that a ι-invariant holomorphic differentials descends to a holomorphic differential on P¹, and is thus zero). Thus we can construct y as dx / ω₂, and then find the hyperelliptic defining equation for C that equates y² with a sextic polynomial in x (or a quintic if there's a rational Weierstrass point and ω₂ was chosen to vanish at that point).

Again we give an example of a modular curve, this time X₁(13), which is the first X₁(N) of genus >1. [For N≤12 the curve is rational, except for N=11 when it is a curve of genus 1 that you should by now know how to compute; we shall see later this term how to describe the elliptic curves with N-torsion points that are parametrized by these curves X₁(N).] This time we need the two-dimensional space of cuspforms for Γ₁(13), which in Sage we can get from

CuspForms(Gamma1(13),prec=14).echelon_basis()

[
q - 4*q^3 - q^4 + 3*q^5 + 6*q^6 - 3*q^8 + q^9 - 6*q^10 - 2*q^12 + 2*q^13 + O(q^14),
q^2 - 2*q^3 - q^4 + 2*q^5 + 2*q^6 - 2*q^8 + q^9 - 3*q^10 + 3*q^13 + O(q^14)
]

genus 3 and higher: Here if C is not hyperelliptic then the holomorphic differentials (= sections of the canonical divisor) embed C as a curve of degree 2g−2 in P^g−1. For g=3,4,5 this curve is a complete intersection, as described at the beginning of today's notes; given generators for the holomorphic differentials, and thus homogeneous coordinates on P^g−1, the defining equations are linear relations in the monomials of appropriate degree, and can be found by linear algebra. [Next time we'll see what to do if C turns out to be hyperelliptic.]

[
q + q^4 - q^5 - 2*q^6 + 2*q^7 - 2*q^8 - 3*q^10 - 2*q^12 + 2*q^14 + 2*q^15 + 3*q^16 - 2*q^17 + 3*q^18 + 2*q^19 + O(q^20),
q^2 - 2*q^4 - q^5 + 3*q^8 + q^9 + q^10 - 2*q^11 - 2*q^12 + 2*q^13 + 2*q^14 - 4*q^16 - 2*q^18 + 2*q^19 + O(q^20),
q^3 - 2*q^4 + q^6 - q^7 + 2*q^8 + 2*q^10 - 3*q^11 - q^12 + 2*q^13 - q^14 - 2*q^15 - 2*q^18 + 3*q^19 + O(q^20)
]

Curiously we can also predict the simple preimage P of the third branch point 1: it must be −2T. This exploits a trick that must have been rediscovered many times, though to my surprise I've found no explicit mention of it earlier than my ABC⇒Mordell paper of 1991. The idea (which applies to branched covers of any positive genus) is that once we know all the ramification of f, we know the divisor of its differential df, and the fact that this divisor is canonical gives us additional information (an extra equation in the Jacobian) on the preimages of the branch points. It is more convenient to work with the logarithmic differential df / f, which has a simple pole at each zero or pole of f, and a zero of multiplicity m−1 wherever f = t has a zero of multiplicity m for some t other than 0 and ∞. Here this means the logarithmic differential has divisor D−(O)−(T), so D ∼ (O)+(T); since also (P)+2D ∼ 5(O), we can eliminate D to find (P)+2(T) ∼ 3(O), whence P = −2T in the group law, as claimed. Thus we can start from any Weil function w with divisor 5(T)−5(O) (i.e. any multiple of f ) and recover f  as w / w(−2T).

The next step is to parametrize pairs (E, T) where E is an elliptic curve and T is a 5-torsion point on E (NB: this is much better than starting from a random E and then choosing one of its 24 nontrivial 5-torsion points). The following procedure for parametrizing elliptic curves with a torsion point of low order goes at least back to Tate (see the formula for a general curve with a 7-torsion point the end of §7 of his paper The Arithmetic of Elliptic Curves (Inventiones Math. 1974)). Suppose E has extended Weierstrass form with coefficients (a₁, a₂, a₃, a₄, a₆), that is

Now it's easy to describe, for small N >3, the pairs (a₁, a) that make T an N-torsion point. We illustrate with the case N=5 that motivated this excursion. We write the condition 5T = 0 as 3T = −2T, which (since T ≠ O) is equivalent to the condition that 2T and 3T have the same x coordinate. [These coordinates can be computed in gp with   ellpow([a1,a,a,0,0], [0,0], 2)   and   ellpow([a1,a,a,0,0], [0,0], 3)   (look, Ma, no ellinit!), though here the group-law computations are simple enough to be done unaided.] We find that 2T = (−a, a₁a−a) and 3T = (1−a₁, a₁−a−1), so 5T = 0 iff a₁ = a+1. Therefore the general 5-torsion point on an elliptic curve is equivalent to the point (0, 0) on the curve with coefficients (a+1, a, a, 0, 0). Exercise: Find the corresponding formulas for 4T = 0, 6T = 0, and (recovering the formula in Tate's paper) 7T = 0.

Next step is to find a Weil function w. Since w is a section of 5(O), it is a linear combination of xy, x², y, x, and 1. There's a one-dimensional space of combinations that vanish to order at least 4 at T, and then the fifth zero is automatically at T as well because T is 5-torsion. One way to find these combinations is to expand y in a Taylor series about x=0 near T; we find y = x² − x³ + x⁴ + (a⁻¹−1) x⁵ + O(x⁶) , so w = x² − y − xy works. An alternative approach, which can be used even for Weil functions of really high degree, is to write w as a product of powers of linear forms. Here the functions x and y on E have divisors (T) + (−T) − 2(O) and 2(T) + (−2T) − 3(O) respectively, so xy² has divisor 5(T) + (−T) + 2(−2T) − 8(O), and we need only divide by the equation of the line through −T and −2T, which is tangent to E at −2T. This gives w = xy² / (x+y+a). Rationalizing the denominator and removing a common factor y simplifies this to (x+1)y − x², same up to sign as our previous answer.

We are finally ready to find the value of a, and thus the curve E, for which f  = w / w(−2T) = (x² − y − xy) / a² is a (5, 5, 221) Belyi function. There are several ways to go about this. A simple one is to locate the x-coordinate of the zeros of of f −1 by computing the resulting with respect of y of f −1 with the defining equation of the curve. This yields a quintic in x, one of whose roots is x(−2T) = −a, and the other four must come in two equal pairs; that is, the quintic must be c (x+a) times the square of a quadratic polynomial, for some constant c. We find that the resultant is −(x+a) (x⁴ − ax³ + a²x² + 3a²x + a²−a³), so the last factor must be a square. As usual we solve for a by comparing with the Laurent expansion of the square root about x = ∞ (which here is x² − ax/2 + 3a²/8 + O(1/x)). We find that a = −8, and check that this indeed makes f a Belyi function with the desired cycle structures.

The standard model of E has coordinates (a₁, a₂, a₃, a₄, a₆) = (1, 1, 1, 22, −9) and can be obtained for instance by telling gp E = [-7,-8,-8,0,0]; R = ellglobalred(ellinit(E)); ellchangecurve(E, R[2]) which also shows that the curve has conductor 50, small enough that it already appears in Tingley's 40-year-old Antwerp Tables (which include all curves of conductor at most 200). I usually advocate against forcing equations into such forms, which can make the equations more unwieldy and hide features such as the point (0, 0); but the ellglobalred form does have the advantage of being a canonical reduced form, which one can use to tell whether two curves are isomorphic or to compile tables for future reference. [Once the genus exceeds 1 it can be much harder to detect and find isomorphisms between two given curves.] Here we learn from the table that E has not just a rational 5-torsion point, but also a rational 3-isogeny; indeed it was already known in 1972 that this curve and the 3-isogenous one with coefficients (1, 1, 1, −3, 1) are the only elliptic curves over Q with both a rational 5-torsion point and a rational 3-isogeny. These curves' appearance here is related with the fact that the Galois closure of our Belyi function is the Bring curve of genus 4 with automorphism group S₅, which has maximal size for a genus-4 curve in characteristic zero; I hope I'll have the time to say more about this in a few weeks.

Part of the original proof (G.C. Shephard and J.A. Todd, “Finite unitary reflection groups”, Canad. J. Math. 6 (1954), 274–304) required obtaining the full list of irreducible reflection group (Table VII on p.301 of the Shephard-Todd paper). A more conceptual proof followed (Chevalley, later extended by Serre), but the classification of complex reflection groups remains a very useful tool and source for highly symmetric algebraic curves and other geometric structures.

There are three infinite families of irreducible complex reflection groups, plus 34 exceptional cases, in dimensions ranging from 2 to 8. Most (19) of the 34 exceptional complex reflection groups are in dimension 2; each is a variation of one of the three special groups A₄, S₄, and A₅ of rotations of the Riemann sphere). The counts in dimensions 3, 4, 5, 6, 7, 8 are respectively 5, 5, 1, 2, 1, 1. We begin with the infinite families, then describe the exceptional reflection groups and their invariant rings.

We have encountered already most of the infinite families. The simplest one (though it happens to be listed third in the Shephard-Todd list) consists of the cyclic groups μ_m in GL₁(C), with the invariant ring generated by Φ₁ = x^m.

The next series (and the first in the Shephard-Todd table) is the symmetric group S_n+1 acting on an n-dimensional space, the zero-sum hyperplane of the permutation representation. [...]

The final infinite series generalizes the group that arises in the symmetries of Fermat curves. For any n>1 and m>1, the μ_m-signed n×n permutation matrices constitute a complex reflection group G(m, 1, n) of order n!mⁿ with invariant degrees m, 2m, …, n m, because the invariant polynomials are symmetric functions in the m-th powers of the coordinate variables (we exclude n=1, which we have seen already, and m=1, which yields the not-quite-irreducible group S_n of permutation matrices). We obtain a homomorphism G→μ_m by mapping each matrix in G to the product of its nonzero elements. For each factor q of m, the preimage of μ_q is again a complex reflection group, which Shephard and Todd call G(m, p, n) where pq=m. This group has order n!mⁿ/p, and (again assuming m>1) acts irreducibly except for G(2,2,2) which is a Klein 4-group. The invariant degrees are m, 2m, …, (n−1)m, and nq. Recall that the invariant polynomials for G(m, 1, n) are the symmetric functions in the m-th powers of the coordinate variables; if we generate these by the elementary symmetric functions, then Φ_n is the m-th power of the product of the variables, and we get generators of the G(m, p, n) invariants by replacing this m-th power by the q-th power of the same product.

The real (a.k.a. Euclidean) reflection groups in these families are: μ₂ = {±1} = A₁ (and trivially μ₁ = {1}) in GL₁(R); the symmetric group S_n+1 = A_n in GL_n(R); the groups G(2, 1, n) = BC_n and G(2, 2, n) = D_n, again in GL_n(R); and less obviously (because this requires a complex change of basis) G(m, m, 2) which is the 2m-element dihedral group in GL₂(R).

It is not quite correct to say the three infinite families plus the 34 exceptional cases fully account for the irreducible complex reflection groups. There's also the missing group G(2,2,2), and several coincidences where the same small group appears more than once on the list. This is already familiar from the classification of simple Lie groups, where in addition to the exceptional groups G₂, F₄, E₆, E₇, E₈ we have the missing D₂ (which is not simple, decomposing as two A₁'s) and the coincidence A₃=D₃. Since Lie groups correspond to Euclidean reflection groups, these irregularities appear in our list: the 34 exceptions include F₄, E₆, E₇, E₈; the reducible D₂ is the reducible G(2,2,2); and A₃=D₃ is the coincidence of S₄ with G(2,2,3). [This last one is related with the exact sequence 1→(Z/2Z)²→S₄→S₃→1; note how the invariant degrees 2,3,4 manage to match up!] There are two further coincidences involving the dihedral groups: G(3,3,2) is also S₃, and G(4,4,2) is also G(2,1,2). These correspond to the Lie groups A₂ and B₂; note that G₂ is not exceptional as a reflection group, because like A₂ and BC₂ it's just one of the dihedral groups (though distinguished by being “crystallographic”).

[In positive characteristic, it is known that a representation of a finite group that has polynomial invariant ring must still be generated by g such that 1−g has rank 1, but there are several new complications. For one, such g could also be a “transvection”, with all eigenvalues 1 but one 2×2 Jordan block. Dickson already gave the example of SL_n(F_q), which has no reflections (why?) but is generated by transvections, and has an invariant polynomial ring with generators of degrees qⁿ − qⁱ for 0 < i < n and (qⁿ − 1) / (q − 1). Dickson also showed that GL_n(F_q) has invariant polynomial ring with degrees qⁿ−qⁱ (0 ≤ i < n). The full list of such groups is known, but this is a more recent result, and here it turns out that not all reflection/transvection groups actually have polynomial invariant rings.]

Recall that if U is a graded vector space with degrees 0, 1, 2, …, and finite-dimensional graded pieces U₀, U₁, U₂, …, then the Hilbert series for U is the generating function Σ_n≥0 dim(U_n) · tⁿ.   If U = (C[V])^G, the algebra of invariants for a finite group G acting on a finite-dimensional space V, then this generating function is called the “(Hilbert-)Molien series” of the representation. If the invariant ring is polynomial with generators of degrees d_i then the series is 1 / Π_i (1 − q^d_i). In characteristic zero, the fixed subspace of any finite-dimensional representation of G has dimension |G|⁻¹ Σ_g∈G tr(g). This yields the formula |G|⁻¹ Σ_g∈G (1 / det(1− t g)) for the Molien series. (This formula figures in one approach to the classification of complex reflection groups, which is one way that the problem becomes much harder in positive characteristic.) For example, if V = C and G = μ_m we get m⁻¹ Σ_ζ^m=1 1 / (1− ζ t), which simplifies to 1 / (1− t^m) as expected; if V = C² and G = {±1}, we get   (1/2) [(1−t)⁻² + (1+t)⁻²] = (1+t²) / (1−t²)², so (as we already knew) the invariant ring is not polynomial, though here it's still a “complete intersection ring”, with three generators x², xy², y² in degree 2 and one relation x²y²=(xy)² in degree 4, corresponding to the factorization (1−t⁴) / (1−t²)³ of the Molien series. [...]

We next work out in some detail the identities related with exceptional finite subgroups of GL₂(C), which give rise to some of beautiful mathematics (mostly classical but with various modern links) that should be [i.e. that I wish were] better known. For starters, suppose G is a finite subgroup (not necessarily a complex reflection group) of GL₂(C), and let D be its normal subgroup of diagonal matrices. Recall that any complex representation of a finite group G fixes a positive-definite Hermitian pairing (obtained by averaging, a simple case of the “unitarian trick”), and thus map G to the unitary group of that pairing. [This is why Shephard and Todd can title their paper “finite unitary reflection groups” and still get a description of all finite complex reflection groups.] So here G is a subgroup of U₂(C). It follows that the induced action of G₀ := G / D on P¹(C) is an injection into PU₂(C), which is the group SO₃(R) of Euclidean rotations of the Riemann sphere P¹(C). Now it is known that a discrete subgroup of SO₃(R) is cyclic, dihedral, or one of the three exceptional groups A₄, S₄, A₅. The cyclic subgroups yield reducible representations, and dihedral cases yield reflection groups G(m, p, 2). We next consider the exceptional cases, in which G₀ is the group of orientation-preserving symmetries of the regular tetrahedron, octahedron (dually: cube), or icosahedron (dually: dodecahedron) inscribed in the Riemann sphere.

For any finite subgroup G₀ of PU₂(C) (or even PGL₂(C)) its preimage in SL₂(C) is in the middle of a short exact sequence 1→{±1}→G₁→G₀→1. When G₀ is one of the three exceptional groups, or more generally any group containing an involution, the short exact sequence cannot split, because in SL₂(C) contains no involution other than the central element −1. We next describe in each case polynomials that are invariant or at least “covariant” under the action of these groups 2A₄, 2S₄, 2A₅. (We say P is “covariant” under an action of G when there's a homomorphism G→C^* such that gP = χ(g)P for all group elements g.) Note that G₁ is never a reflection group, because it contains no reflections (a complex reflection cannot have determinant 1); but for most of our purposes we need only the projective action, and also once we know the covariant polynomials we can easily describe the invariant rings of each of the reflection groups with the same image in PGL₂(C).

A nonzero polynomial P is covariant for G₁ iff its zero divisor (which is just a finite multiset in the Riemann sphere) is invariant under G₀. Now each of our G₀ is the group of rotations of a regular polyhedron with N triangles meeting at each vertex, and acts freely on the Riemann sphere except for the vertices, face centers, and edge centers of the polyhedron, whose stabilizers are cyclic of order N, 3, 2 respectively. Here are the familiar counts:

N	G0	polyhedron	|G0|	V	F	E
3	A4	tetrahedron	12	4	4	6
4	S4	octahedron	24	6	8	12
5	A5	icosahedron	60	12	20	30

Now the Euler relation E = V + F − 2 = (V−1) + (F−1) means that once we know the polynomials of degrees V and F we can obtain the third polynomial as the Jacobian determinant of the first two. (The Jacobian cannot vanish because the polynomials are algebraically independent.) Also, since our polyhedron has triangular faces we have F = 3E/2, which together with Euler's formula implies F = 2(V−2); thus we can get the polynomial of degree F as the Hessian (determinant of the matrix of second partial derivatives) of the degree-V polynomial. So it remains to find the G₀-orbit of smallest size V in the Riemann sphere. In each case there is a linear relation in degree |G₀| between the N-th power, cube, and square of the covariants of degree V, F, E respectively. The ratio of these powers gives the quotient map P¹(C) → P¹(C) / G = P¹(C), with the target P¹(C) arising naturally as a line in P²(C), and intersecting the three coordinate lines of that P²(C) at the three branch points of the target P¹(C). In each case this quotient map can also be identified as the covering of modular curves X(N) → X(1), with the branch points of order 2, 3, and N at j = 1728 = 12³,  j = 0, and j = ∞ respectively.

The μ₄ case (#6) also arises in coding theory; this is the reason I chose χ(g)g rather than χ⁻¹(g)g, which is equivalent and has quartic invariant A rather than the “larger” B. Let K be a linear code of length n a finite field of q elements. [Normally one uses not K but C for Code, but this could get confusing here…] Recall that the (Hamming) weight enumerator W_K(x, y) is the homogeneous polynomial of degree n whose x^n−wy^w coefficient is the number of codewords of weight w (each w in [0,n]). The weight enumerator of any linear code K is related with the weight enumerator of its dual code K^⊥ via the MacWilliams identity W_K^⊥ (x, y) = |K|⁻¹ W_K (x + (q−1) y, x − y).  Suppose now that K is a “Type III code”, i.e. that q = 3 and K is self-dual. The first example with n > 0 is the “tetracode”, generated by (1, 1, 1, 0) and (1, −1, 0, 1), with weight enumerator x⁴ + 8xy³ (all eight nonzero words have weight 3). This looks familiar for good reason! The condition K=K^⊥ implies that |K| = 3^n/2 (in general a self-dual code of length n has dimension n/2) and that every word has weight divisible by 3 (compute the pairing of any word with itself). The former property, together with MacWilliams, implies that the weight enumerator W_K is invariant under (x, y) ↔ 3^−½(x+2y, x−y); the latter, that W_K is invariant under (x, y) → (x, ζy). Therefore W_K is invariant under the subgroup of GL₂(C) generated by these two linear transformations, which is reflection group #6 with center μ₄ = {±1, ±i} (note that the scaling coefficient in the MacWilliams identity is 3^−½, not (−3)^−½). This yields Gleason's theorem for Type III codes: the weight enumerator is a polynomial in B = x⁴ + 8xy³ and C², or equivalently in B and A³ = y³(x³−y³)³. In particular, 4 | n, which was not obvious (though it can be proved by more direct means). Also, any Type III code of length 8 has weight enumerator B², and a Type III code of length 12 with no words of weight 3 must have weight enumerator B³ − 24A³ = x¹² + 264x⁶x⁶ + 440x³x⁹ + 24y¹². It is known that such a code exists, and is unique up to isomorphism, namely the extended ternary Golay code, which is also a natural route to the sporadic Mathieu group M₁₂, and especially its double cover 2.M₁₂; e.g. the 132 pairs of words of weight 6 are supported on the blocks of the (5,6,12) Steiner system, and the 12 pairs of words of maximal weight form the unique Hadamard matrix of order 12.

N=4: We have two natural choices here. One is to note that the edge-centers of a regular tetrahedron are the vertices of a regular octahedron, while the vertices of the tetrahedron and its dual constitute the eight vertices of the octahedron's dual cube. We may thus use the above C and AB = x⁷y + 7x⁴y⁴ − 8xy⁷ as our sextic and octic polynomials with octahedral symmetry. (As we know, we could also construct AB as a multiple of the Hessian of C; as it happens it's the Hessian divided by −3600.) Then D = ∂(C, AB) / ∂(x,y) = x¹² + 88x⁹y³ + 704x³y⁹ − 64y¹² is the covariant dodecic(?), with C⁴ + 256(AB)³ − D² = 0. [What would happen if we instead took the Hessian of AB to get a covariant polynomial of degree 2(8−2)=12?] In this picture the symmetry group S₄ consists of the A₄ and its composition with the involution z ↔ −2/z that switches the roots of A and B. The polynomials AB, C, and D are invariant under 2A₄, but the action of 2S₄ multiplies C by the nontrivial character 2S₄→{±1} coming from the sign character of S₄, while fixing AB and D. This can be seen directly from the action of the determinant-1 lifts of z ↔ −2/z, which are (x, y) ↔ (±2^½x, ∓2^−½y). It follows that if we lift even permutations from S₄ to SL₂(C), but odd permutations to matrices of determinant −1 in GL₂(C), we get another double cover of S₄ that does have a polynomial invariant ring, generated by AB and C; this is Shepard and Todd's complex reflection group #12 (where #8 through #11 are larger groups that contain the to SL₂(C) lift of S₄).

It is often more convenient to start from P = xy (x⁴−y⁴), whose roots z = 0, ∞, ±1, ±i are vertices of an octahedron inscribed in the sphere with obvious fourfold symmetry z → iz (and with the equator restored to |z| = 1). Dividing the Hessian of P by −25 yields Q = x⁸ + 14x⁴y⁴ + y⁸, with roots at the vertices of the cube dual to that octahedron. Dividing the Jacobian derivative ∂(P,Q) / ∂(x,y)  by −8 then yields R = x¹² − 33x⁸y⁴ − 33x⁴y⁸ + y¹², which has its twelve roots at the eight points μ₄(1±2^½) and the four primitive 8th roots of unity 2^−½(±1±i ). The identity relating these covariants is 108P⁴ − Q³ + R² = 0.

Here the symmetry group is generated by z → iz together with the involution z ↔ (z+1) / (z−1), which switches 1 ↔ ∞,  0 ↔ −1, and i ↔ −i. The determinant of the associated linear map (x, y) → (x+y, x−y) is −2, so its lifts to SL₂ are obtained by dividing by the square roots of −2. [...]

By the Riemann-Hurwitz formula, the genus of X₀(N)⁺ can be computed from the genus of X₀(N) together with the number of fixed points of w_N. This number can be expressed in terms of the class numbers of binary quadratic forms of discriminants −N (if that's congruent to 0 or 1 mod 4) and −4N; it is even by Riemann-Hurwitz, and nonzero because τ = i / N^½ is always a fixed point. The total count grows as N^(1/2)±ε. Thus as N→∞ the genus of X₀(N)⁺ is asymptotically half the genus of X₀(N). It's never more than half that genus, and can be substantially less for small (or even some not-so-small) N.  Indeed X₀(N)⁺ has genus 0 for some N as large as 71, famously including all the prime factors of the size of the Monster group (see “Monstrous Moonshine”); each of these curves is thus rational, because X₀(N), and thus any quotient of X₀(N), has at least one rational point, the cusp τ = i ∞ . Also, the genus of X₀(N)⁺ is 1 for some N as large as 131 (and at least when N is prime this elliptic curve has rank 1 over Q, so for each of these N there are infinitely many “Q-curves” over quadratic extensions of Q that are N-isogenous with their Galois conjugates. The largest N for which X₀(N)⁺ has genus 2 (genus 3) is 191 (resp. 239). This and much more information about the genera of these curves and their spaces of holomorphic differentials (a.k.a. weight-2 cuspforms) can be read off tables such as Antwerp Table 5. We have seen already how to use the q-expansions of modular forms on such curves to compute explicit models.

For the seven values of N>1 with (N−1) | 24, for which we constructed an X₀(N) Hauptmodul h as the 24 / (N−1) power of  η(τ) / η(Nτ), the involution w_N takes h ↔ N^{12 / (N−1)} / h.  Note that the constant N^{12 / (N−1)} is integral even for the two values N=9 and N=25 for which the exponent 12 / (N−1) is half-integral. The two fixed points h = ±N^{6 / (N−1)} of w_N give elliptic curves E/C with a cyclic N-isogeny to E itself. Thus E has complex multiplication (CM). This is clear for the fixed point at τ = i / N^½, for which j(E) = j(i N^½) and thus End(E) is the imaginary quadratic order Z[(−N)^½] of discriminant −4N. At this τ, our h is clearly positive, so h = +N^{6 / (N−1)}.  For N = 2, 3, 4, 7, we get the integers h = 64, 27, 16, 7 respectively, and can then use last week's formulas for j as a rational function of h to compute j = 20³, 2·30³, 66³, 255³ respectively. In this case the negative root h = −N^{6 / (N−1)} yields the third cusp of X₀(N) for N=4, and simpler CM values j = 12³, 0, −15³ of discriminant −4, −3, −7 for N = 2, 3, 7 respectively. [If we had known in advance that these “singular moduli” are in Z then we could have just used a few terms of the q-expansions for j, or better yet for E₄ and Δ (easier to bound the coefficients), and then rounded to the nearest integer. But this approach requires developing (or taking on faith) a substantial chunk of the theory of complex multiplication.] If N is one of the remaining three values 5, 9, 25, then the two square roots of N^{12 / (N−1)} yield the two Galois-conjugate j-invariants of curves with CM by Z[(−N)^½].

[Added after class: each of the pairs (X₀(N), w_N) yields several further CM values of j, coming from cyclic N-isogenies φ: E → E with φ* ≠ −φ, coming from pairs of solutions h of j(h) = j(w_N(h)) other than the fixed points of w_N. For N=2 this gives h² + 47h + 2¹² = 0 and j = −15³ which we have already seen, where the endomorphism ring has discriminant −7 and contains the elements (±1±(−7)^½) / 2 of norm 2). For N=3 the new CM values have h² + 46h + 3⁶ = 0 and h² − 10h + 3⁶ = 0; the former repeats the CM value j = 20³ seen already, but the latter gives the new j = −32³ with discriminant −11.   Exercise: Do the analogous computation for N=5, 7, 13; can you identify the CM discriminant of each of the new “singular moduli” found?]

The Fricke involution w_N of X₀(N) generalizes to an Atkin-Lehner involution w_N1 of the same curve X₀(N) for any factorization N = N₁N₂ with gcd(N₁, N₂) = 1; that is, with N₁, N₂ being complementary “unitary divisors” of N. These w_N1 form an abelian group of exponent 2 (assuming N≠1) and rank equal to the number of distinct prime factors of N, the identity element being the trivial “involution” w₁. To construct w_N1, factor the typical isogeny parametrized by X₀(N) in two ways as the product of cyclic isogenies of degrees N₁ and N₂, namely E → E’ → E’’’ and E → E’’ → E’’’ where the isogenies E → E’ and E’’ → E’’’ have degree N₁, and the isogenies E → E’’ and E’ → E’’’ have degree N₂. That is, points P on Y₀(N) parametrize commutative diagrams of cyclic isogenies of degrees N₁ and N₂. Replacing each of the isogenies of degree N₁ by its dual yields another such diagram, which corresponds to another point P’ on Y₀(N); we define w_N1 to be the map that takes P to P’, completed to a map X₀(N) → X₀(N), which again is an involution because φ** = φ. For N₁=N this definition recovers w_N, as it should to justify the notation; and as is true for w_N, the involution w_N1 comes from a matrix with integer entries and determinant N₁ in the normalizer of Γ₀(N) in PGL₂(Q)⁺. The product of two Atkin-Lehner involutions w_N1 and w_N2 is w_N3 where N₃ is the unitary divisor of N determined uniquely by the condition that N₁N₂N₃ be a square. Unlike the special case N₁=N, for general unitary divisors N₁ of N we cannot expect to be able to lift w_N1 to an involution in PGL₂(Q)⁺. It sometimes happens that an involution w_N1 has no fixed points at all; this first happens for (N, N₁) = (14, 2) and (15, 3) When w_N1 does have fixed points, they can again be counted via class numbers of quadratic forms; the general formulas can get annoying to figure out, but fortunately this is not necessary for any N small enough that we might actually compute formulas for X₀(N) or its quotient by some subgroup of the Atkin-Lehner group: by Riemann-Hurwitz, this is equivalent to finding, for each choice of ± signs, the dimension of the (±1, ±1, …, ±1) eigenspace of the action of the w_N1's on the holomorphic differentials on X₀(N), or equivalently on the weight-2 cuspforms for Γ₀(N); and these dimensions have been extensively tabulated (already the fifth Antwerp table contains this information for all N≤300), and computer packages will compute the eigenspaces, and thus a fortiori their dimensions, on the fly.