Skip to content →

Category: number theory

Monstrous dessins 3

A long while ago I promised to take you from the action by the modular group Γ=PSL2(Z) on the lattices at hyperdistance n from the standard orthogonal laatice L1 to the corresponding ‘monstrous’ Grothendieck dessin d’enfant.

Speaking of dessins d’enfant, let me point you to the latest intriguing paper by Yuri I. Manin and Matilde Marcolli, ArXived a few days ago Quantum Statistical Mechanics of the Absolute Galois Group, on how to build a quantum system for the absolute Galois group from dessins d’enfant (more on this, I promise, later).

Where were we?

We’ve seen natural one-to-one correspondences between (a) points on the projective line over Z/nZ, (b) lattices at hyperdistance n from L1, and (c) coset classes of the congruence subgroup Γ0(n) in Γ.

How to get from there to a dessin d’enfant?

The short answer is: it’s all in Ravi S. Kulkarni’s paper, “An arithmetic-geometric method in the study of the subgroups of the modular group”, Amer. J. Math 113 (1991) 1053-1135.

It is a complete mystery to me why Tatitscheff, He and McKay don’t mention Kulkarni’s paper in “Cusps, congruence groups and monstrous dessins”. Because all they do (and much more) is in Kulkarni.

I’ve blogged about Kulkarni’s paper years ago:

– In the Dedekind tessalation it was all about assigning special polygons to subgroups of finite index of Γ.

– In Modular quilts and cuboid tree diagram it did go on assigning (multiple) cuboid trees to a (conjugacy class) of such finite index subgroup.

– In Hyperbolic Mathieu polygons the story continued on a finite-to-one connection between special hyperbolic polygons and cuboid trees.

– In Farey codes it was shown how to encode such polygons by a Farey-sequence.

– In Generators of modular subgroups it was shown how to get generators of the finite index subgroups from this Farey sequence.

The modular group is a free product
Γ=C2C3=s,u | s2=1=u3
with lifts of s and u to SL2(Z) given by the matrices
S=[0110], U=[0111]

As a result, any permutation representation of Γ on a set E can be represented by a 2-coloured graph (with black and white vertices) and edges corresponding to the elements of the set E.

Each white vertex has two (or one) edges connected to it and every black vertex has three (or one). These edges are the elements of E permuted by s (for white vertices) and u (for black ones), the order of the 3-cycle determined by going counterclockwise round the vertex.



Clearly, if there’s just one edge connected to a vertex, it gives a fixed point (or 1-cycle) in the corresponding permutation.

The ‘monstrous dessin’ for the congruence subgroup Γ0(n) is the picture one gets from the permutation Γ-action on the points of P1(Z/nZ), or equivalently, on the coset classes or on the lattices at hyperdistance n.

Kulkarni’s paper (or the blogposts above) tell you how to get at this picture starting from a fundamental domain of Γ0(n) acting on teh upper half-plane by Moebius transformations.

Sage gives a nice image of this fundamental domain via the command


FareySymbol(Gamma0(n)).fundamental_domain()

Here’s the image for n=6:



The boundary points (on the halflines through 0 and 1 and the 4 half-circles need to be identified which is indicaed by matching colours. So the 2 halflines are identified as are the two blue (and green) half-circles (in opposite direction).

To get the dessin from this, let’s first look at the interior points. A white vertex is a point in the interior where two black and two white tiles meet, a black vertex corresponds to an interior points where three black and three white tiles meet.

Points on the boundary where tiles meet are coloured red, and after identification two of these reds give one white or black vertex. Here’s the intermediate picture



The two top red points are identified giving a white vertex as do the two reds on the blue half-circles and the two reds on the green half-circles, because after identification two black and two white tiles meet there.

This then gives us the ‘monstrous’ modular dessin for n=6 of the Tatitscheff, He and McKay paper:



Let’s try a more difficult example: n=12. Sage gives us as fundamental domain



giving us the intermediate picture



and spotting the correct identifications, this gives us the ‘monstrous’ dessin for Γ0(12) from the THM-paper:

In general there are several of these 2-coloured graphs giving the same permutation representation, so the obtained ‘monstrous dessin’ depends on the choice of fundamental domain.

You’ll have noticed that the domain for Γ0(6) was symmetric, whereas the one Sage provides for Γ0(12) is not.

This is caused by Sage using the Farey-code
Misplaced &

One of the nice results from Kulkarni’s paper is that for any n there is a symmetric Farey-code, giving a perfectly symmetric fundamental domain for Γ0(n). For n=12 this symmetric code is

Misplaced &

It would be nice to see whether using these symmetric Farey-codes gives other ‘monstrous dessins’ than in the THM-paper.

Remains to identify the edges in the dessin with the lattices at hyperdistance n from L1.

Using the tricks from the previous post it is quite easy to check that for any n the monstrous dessin for Γ0(n) starts off with the lattices LM,gh=M,gh as below



Let’s do a sample computation showing that the action of s on Ln gives L1n:

Ln.s=[n001][0110]=[0n10]

and then, as last time, to determine the class of the lattice spanned by the rows of this matrix we have to compute

[0110][0n10]=[100n]

which is class L1n. And similarly for the other edges.

2 Comments

Monstrous dessins 2

Let’s try to identify the Ψ(n)=np|n(1+1p) points of P1(Z/nZ) with the lattices LMgh at hyperdistance n from the standard lattice L1 in Conway’s big picture.

Here are all 24=Ψ(12) lattices at hyperdistance 12 from L1 (the boundary lattices):

You can also see the 4=Ψ(3) lattices at hyperdistance 3 (those connected to 1 with a red arrow) as well as the intermediate 12=Ψ(6) lattices at hyperdistance 6.

The vertices of Conway’s Big Picture are the projective classes of integral sublattices of the standard lattice Z2=Ze1Ze2.

Let’s say our sublattice is generated by the integral vectors v=(v1,v2) and w=(w1.w2). How do we determine its class LM,gh where MQ+ is a strictly positive rational number and 0gh<1?

Here’s an example: the sublattice (the thick dots) is spanned by the vectors v=(2,1) and w=(1,4)



Well, we try to find a basechange matrix in SL2(Z) such that the new 2nd base vector is of the form (0,z). To do this take coprime (c,d)Z2 such that cv1+dw1=0 and complete with (a,b) satisfying adbc=1 via Bezout to a matrix in SL2(Z) such that
[abcd][v1v2w1w2]=[xy0z]
then the sublattice is of class Lxz,yz mod 1.

In the example, we have
[0112][2114]=[1407]
so this sublattice is of class L17,47.

Starting from a class LM,gh it is easy to work out its hyperdistance from L1: let d be the smallest natural number making the corresponding matrix integral
d.[Mgh01]=[uv0w]M2(Z)
then LM,gh is at hyperdistance u.w from L1.

Now that we know how to find the lattice class of any sublattice of Z2, let us assign a class to any point [c:d] of P1(Z/nZ).

As gcd(c,d)=1, by Bezout we can find a integral matrix with determinant 1
S[c:d]=[abcd]
But then the matrix
[a.nb.ncd]
has determinant n.

Working backwards we see that the class L[c:d] of the sublattice of Z2 spanned by the vectors (a.n,b.n) and (c,d) is of hyperdistance n from L1.

This is how the correspondence between points of P1(Z/nZ) and classes in Conway’s big picture at hyperdistance n from L1 works.

Let’s do an example. Take the point [7:3]P1(Z/12Z) (see last time), then
[2173]SL2(Z)
so we have to determine the class of the sublattice spanned by (24,12) and (7,3). As before we have to compute
[27724][241273]=[13012]
giving us that the class L[7:3]=L11234 (remember that the second term must be taken mod 1).

If you do this for all points in P1(Z/12Z) (and P1(Z/6Z) and P1(Z/3Z)) you get this version of the picture we started with



You’ll spot that the preimages of a canonical coordinate of P1(Z/mZ) for m|n are the very same coordinate together with ‘new’ canonical coordinates in P1(Z/nZ).

To see that this correspondence is one-to-one and that the index of the congruence subgroup
Γ0(n)={[pqrs] | n|r and psqr=1}
in the full modular group Γ=PSL2(Z) is equal to Ψ(n) it is useful to consider the action of PGL2(Q)+ on the right on the classes of lattices.

The stabilizer of L1 is the full modular group Γ and the stabilizer of any class is a suitable conjugate of Γ. For example, for the class Ln (that is, of the sublattice spanned by (n,0) and (0,1), which is of hyperdistance n from L1) this stabilizer is
Stab(Ln)={[abnc.nd] | adbc=1}
and a very useful observation is that
Stab(L1)Stab(Ln)=Γ0(n)
This is the way Conway likes us to think about the congruence subgroup Γ0(n): it is the joint stabilizer of the classes L1 and Ln (as well as all classes in the ‘thread’ Lm with m|n).

On the other hand, Γ acts by rotations on the big picture: it only fixes L1 and maps a class to another one of the same hyperdistance from L1.The index of Γ0(n) in Γ is then the number of classes at hyperdistance n.

To see that this number is Ψ(n), first check that the classes at hyperdistance pk for p a prime number and for all k for the p+1 free valent tree with root L1, so there are exactly pk1(p+1) classes as hyperdistance pk.

To get from this that the number of hyperdistance n classes is indeed Ψ(n)=p|npvp(n)1(p+1) we have to use the prime- factorisation of the hyperdistance (see this post).

The fundamental domain for the action of Γ0(12) by Moebius tranfos on the upper half plane must then consist of 48=2Ψ(12) black or white hyperbolic triangles



Next time we’ll see how to deduce the ‘monstrous’ Grothendieck dessin d’enfant for Γ0(12) from it



Comments closed

Monstrous dessins 1

Dedekind’s Psi-function Ψ(n)=np|n(1+1p) pops up in a number of topics:

  • Ψ(n) is the index of the congruence subgroup Γ0(n) in the modular group Γ=PSL2(Z),
  • Ψ(n) is the number of points in the projective line P1(Z/nZ),
  • Ψ(n) is the number of classes of 2-dimensional lattices LMgh at hyperdistance n in Conway’s big picture from the standard lattice L1,
  • Ψ(n) is the number of admissible maximal commuting sets of operators in the Pauli group of a single qudit.

The first and third interpretation have obvious connections with Monstrous Moonshine.

Conway’s big picture originated from the desire to better understand the Moonshine groups, and Ogg’s Jack Daniels problem
asks for a conceptual interpretation of the fact that the prime numbers such that Γ0(p)+ is a genus zero group are exactly the prime divisors of the order of the Monster simple group.

Here’s a nice talk by Ken Ono : Can’t you just feel the Moonshine?



For this reason it might be worthwhile to make the connection between these two concepts and the number of points of P1(Z/nZ) as explicit as possible.

Surely all of this is classical, but it is nicely summarised in the paper by Tatitscheff, He and McKay “Cusps, congruence groups and monstrous dessins”.

The ‘monstrous dessins’ from their title refers to the fact that the lattices LMgh at hyperdistance n from L1 are permuted by the action of the modular groups and so determine a Grothendieck’s dessin d’enfant. In this paper they describe the dessins corresponding to the 15 genus zero congruence subgroups Γ0(n), that is when n=1,2,3,4,5,6,7,8,9,10,12,13,16,18 or 25.

Here’s the ‘monstrous dessin’ for Γ0(6)



But, one can compute these dessins for arbitrary n, describing the ripples in Conway’s big picture, and try to figure out whether they are consistent with the Riemann hypothesis.

We will get there eventually, but let’s start at an easy pace and try to describe the points of the projective line P1(Z/nZ).

Over a field k the points of P1(k) correspond to the lines through the origin in the affine plane A2(k) and they can represented by projective coordinates [a:b] which are equivalence classes of couples (a,b)k2{(0,0)} under scalar multiplication with non-zero elements in k, so with points [a:1] for all ak together with the point at infinity [1:0]. When n=p is a prime number we have #P1(Z/pZ)=p+1. Here are the 8 lines through the origin in A2(Z/7Z)



Over an arbitrary (commutative) ring R the points of P1(R) again represent equivalence classes, this time of pairs
(a,b)R2 : aR+bR=R
with respect to scalar multiplication by units in R, that is
(a,b)(c,d)  iff λR : a=λc,b=λd
For P1(Z/nZ) we have to find all pairs of integers (a,b)Z2 with 0a,b<n with gcd(a,b)=1 and use Cremona’s trick to test for equivalence:
(a,b)=(c,d)P1(Z/nZ) iff adbc0 mod n
The problem is to find a canonical representative in each class in an efficient way because this is used a huge number of times in working with modular symbols.

Perhaps the best algorithm, for large n, is sketched in pages 145-146 of Bill Stein’s Modular forms: a computational approach.

For small n the algorithm in §1.3 in the Tatitscheff, He and McKay paper suffices:

  • Consider the action of (Z/nZ) on {0,1,,n1}=Z/nZ and let D be the set of the smallest elements in each orbit,
  • For each dD compute the stabilizer subgroup Gd for this action and let Cd be the set of smallest elements in each Gd-orbit on the set of all elements in Z/nZ coprime with d,
  • Then P1(Z/nZ)={[c:d] | dD,cCd}.

Let’s work this out for n=12 which will be our running example (the smallest non-squarefree non-primepower):

  • (Z/12Z)={1,5,7,11}C2×C2,
  • The orbits on {0,1,,11} are
    {0},{1,5,7,11},{2,10},{3,9},{4,8},{6}
    and D={0,1,2,3,4,6},
  • G0=C2×C2, G1={1}, G2={1,7}, G3={1,5}, G4={1,7} and G6=C2×C2,
  • 1 is the only number coprime with 0, giving us [1:0],
  • {0,1,,11} are all coprime with 1, and we have trivial stabilizer, giving us the points [0:1],[1:1],,[11:1],
  • {1,3,5,7,9,11} are coprime with 2 and under the action of {1,7} they split into the orbits
    {1,7}, {3,9}, {5,11}
    giving us the points [1:2],[3:2] and [5:2],
  • {1,2,4,5,7,8,10,11} are coprime with 3, the action of {1,5} gives us the orbits
    {1,5}, {2,10}, {4,8}, {7,11}
    and additional points [1:3],[2:3],[4:3] and [7:3],
  • {1,3,5,7,9,11} are coprime with 4 and under the action of {1,7} we get orbits
    {1,7}, {3,9}, {5,11}
    and points [1:4],[3:4] and [5,4],
  • Finally, {1,5,7,11} are the only coprimes with 6 and they form a single orbit under C2×C2 giving us just one additional point [1:6].

This gives us all 24=Ψ(12) points of P1(Z/12Z) (strangely, op page 43 of the T-H-M paper they use different representants).

One way to see that #P1(Z/nZ)=Ψ(n) comes from a consequence of the Chinese Remainder Theorem that for the prime factorization n=p1e1pkek we have
P1(Z/nZ)=P1(Z/p1e1Z)××P1(Z/pkekZ)
and for a prime power pk we have canonical representants for P1(Z/pkZ)
[a:1] for a=0,1,,pk1 and[1:b] for b=0,p,2p,3p,,pkp
which shows that #P1(Z/pkZ)=(p+1)pk1=Ψ(pk).

Next time, we’ll connect P1(Z/nZ) to Conway’s big picture and the congruence subgroup Γ0(n).

Comments closed