Category: math

Monstrous dessins 2

Published July 24, 2019 by lieven

Let’s try to identify the $Ψ (n) = n \prod_{p | n} (1 + \frac{1}{p})$ points of $P^{1} (Z / n Z)$ with the lattices $L_{M \frac{g}{h}}$ at hyperdistance $n$ from the standard lattice $L_{1}$ in Conway’s big picture.

Here are all $24 = Ψ (12)$ lattices at hyperdistance $12$ from $L_{1}$ (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 $Z^{2} = Z e_{1} \oplus Z e_{2}$ .

Let’s say our sublattice is generated by the integral vectors $v = (v_{1}, v_{2})$ and $w = (w_{1} . w_{2})$ . How do we determine its class $L_{M, \frac{g}{h}}$ where $M \in Q_{+}$ is a strictly positive rational number and $0 \leq \frac{g}{h} < 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 $S L_{2} (Z)$ such that the new 2nd base vector is of the form $(0, z)$ . To do this take coprime $(c, d) \in Z^{2}$ such that $c v_{1} + d w_{1} = 0$ and complete with $(a, b)$ satisfying $a d - b c = 1$ via Bezout to a matrix in $S L_{2} (Z)$ such that
$[\begin{matrix} a & b \\ c & d \end{matrix}] [\begin{matrix} v_{1} & v_{2} \\ w_{1} & w_{2} \end{matrix}] = [\begin{matrix} x & y \\ 0 & z \end{matrix}]$
then the sublattice is of class $L_{\frac{x}{z}, \frac{y}{z} m o d 1}$ .

In the example, we have
$[\begin{matrix} 0 & 1 \\ - 1 & 2 \end{matrix}] [\begin{matrix} 2 & 1 \\ 1 & 4 \end{matrix}] = [\begin{matrix} 1 & 4 \\ 0 & 7 \end{matrix}]$
so this sublattice is of class $L_{\frac{1}{7}, \frac{4}{7}}$ .

Starting from a class $L_{M, \frac{g}{h}}$ it is easy to work out its hyperdistance from $L_{1}$ : let $d$ be the smallest natural number making the corresponding matrix integral
$d . [\begin{matrix} M & \frac{g}{h} \\ 0 & 1 \end{matrix}] = [\begin{matrix} u & v \\ 0 & w \end{matrix}] \in M_{2} (Z)$
then $L_{M, \frac{g}{h}}$ is at hyperdistance $u . w$ from $L_{1}$ .

Now that we know how to find the lattice class of any sublattice of $Z^{2}$ , let us assign a class to any point $[c : d]$ of $P^{1} (Z / n Z)$ .

As $g c d (c, d) = 1$ , by Bezout we can find a integral matrix with determinant $1$
$S_{[c : d]} = [\begin{matrix} a & b \\ c & d \end{matrix}]$
But then the matrix
$[\begin{matrix} a . n & b . n \\ c & d \end{matrix}]$
has determinant $n$ .

Working backwards we see that the class $L_{[c : d]}$ of the sublattice of $Z^{2}$ spanned by the vectors $(a . n, b . n)$ and $(c, d)$ is of hyperdistance $n$ from $L_{1}$ .

This is how the correspondence between points of $P^{1} (Z / n Z)$ and classes in Conway’s big picture at hyperdistance $n$ from $L_{1}$ works.

Let’s do an example. Take the point $[7 : 3] \in P^{1} (Z / 12 Z)$ (see last time), then
$[\begin{matrix} - 2 & - 1 \\ 7 & 3 \end{matrix}] \in S L_{2} (Z)$
so we have to determine the class of the sublattice spanned by $(- 24, - 12)$ and $(7, 3)$ . As before we have to compute
$[\begin{matrix} - 2 & - 7 \\ 7 & 24 \end{matrix}] [\begin{matrix} - 24 & - 12 \\ 7 & 3 \end{matrix}] = [\begin{matrix} - 1 & 3 \\ 0 & - 12 \end{matrix}]$
giving us that the class $L_{[7 : 3]} = L_{\frac{1}{12} \frac{3}{4}}$ (remember that the second term must be taken $m o d 1$ ).

If you do this for all points in $P^{1} (Z / 12 Z)$ (and $P^{1} (Z / 6 Z)$ and $P^{1} (Z / 3 Z)$ ) you get this version of the picture we started with

You’ll spot that the preimages of a canonical coordinate of $P^{1} (Z / m Z)$ for $m | n$ are the very same coordinate together with ‘new’ canonical coordinates in $P^{1} (Z / n Z)$ .

To see that this correspondence is one-to-one and that the index of the congruence subgroup
$Γ_{0} (n) = {[\begin{matrix} p & q \\ r & s \end{matrix}] | n | r and p s - q r = 1}$
in the full modular group $Γ = P S L_{2} (Z)$ is equal to $Ψ (n)$ it is useful to consider the action of $P G L_{2} (Q)^{+}$ on the right on the classes of lattices.

The stabilizer of $L_{1}$ is the full modular group $Γ$ and the stabilizer of any class is a suitable conjugate of $Γ$ . For example, for the class $L_{n}$ (that is, of the sublattice spanned by $(n, 0)$ and $(0, 1)$ , which is of hyperdistance $n$ from $L_{1}$ ) this stabilizer is
$S t a b (L_{n}) = {[\begin{matrix} a & \frac{b}{n} \\ c . n & d \end{matrix}] | a d - b c = 1}$
and a very useful observation is that
$S t a b (L_{1}) \cap S t a b (L_{n}) = Γ_{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 $L_{1}$ and $L_{n}$ (as well as all classes in the ‘thread’ $L_{m}$ with $m | n$ ).

On the other hand, $Γ$ acts by rotations on the big picture: it only fixes $L_{1}$ and maps a class to another one of the same hyperdistance from $L_{1}$ .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 $p^{k}$ for $p$ a prime number and for all $k$ for the $p + 1$ free valent tree with root $L_{1}$ , so there are exactly $p^{k - 1} (p + 1)$ classes as hyperdistance $p^{k}$ .

To get from this that the number of hyperdistance $n$ classes is indeed $Ψ (n) = \prod_{p | n} p^{v_{p} (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

Published July 22, 2019 by lieven

Dedekind’s Psi-function $Ψ (n) = n \prod_{p | n} (1 + \frac{1}{p})$ pops up in a number of topics:

$Ψ (n)$ is the index of the congruence subgroup $Γ_{0} (n)$ in the modular group $Γ = P S L_{2} (Z)$ ,
$Ψ (n)$ is the number of points in the projective line $P^{1} (Z / n Z)$ ,
$Ψ (n)$ is the number of classes of $2$ -dimensional lattices $L_{M \frac{g}{h}}$ at hyperdistance $n$ in Conway’s big picture from the standard lattice $L_{1}$ ,
$Ψ (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 $P^{1} (Z / n Z)$ 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 $L_{M \frac{g}{h}}$ at hyperdistance $n$ from $L_{1}$ 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 $P^{1} (Z / n Z)$ .

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

Over an arbitrary (commutative) ring $R$ the points of $P^{1} (R)$ again represent equivalence classes, this time of pairs
$(a, b) \in R^{2} : a R + b R = R$
with respect to scalar multiplication by units in $R$ , that is
$(a, b) \sim (c, d) iff \exists λ \in R^{*} : a = λ c, b = λ d$
For $P^{1} (Z / n Z)$ we have to find all pairs of integers $(a, b) \in Z^{2}$ with $0 \leq a, b < n$ with $g c d (a, b) = 1$ and use Cremona’s trick to test for equivalence:
$(a, b) = (c, d) \in P^{1} (Z / n Z) iff a d - b c \equiv 0 m o d 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 / n Z)^{*}$ on ${0, 1, \dots, n - 1} = Z / n Z$ and let $D$ be the set of the smallest elements in each orbit,
For each $d \in D$ compute the stabilizer subgroup $G_{d}$ for this action and let $C_{d}$ be the set of smallest elements in each $G_{d}$ -orbit on the set of all elements in $Z / n Z$ coprime with $d$ ,
Then $P^{1} (Z / n Z) = {[c : d] | d \in D, c \in C_{d}}$ .

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

$(Z / 12 Z)^{*} = {1, 5, 7, 11} ≃ C_{2} \times C_{2}$ ,
The orbits on ${0, 1, \dots, 11}$ are
${0}, {1, 5, 7, 11}, {2, 10}, {3, 9}, {4, 8}, {6}$
and $D = {0, 1, 2, 3, 4, 6}$ ,
$G_{0} = C_{2} \times C_{2}$ , $G_{1} = {1}$ , $G_{2} = {1, 7}$ , $G_{3} = {1, 5}$ , $G_{4} = {1, 7}$ and $G_{6} = C_{2} \times C_{2}$ ,
$1$ is the only number coprime with $0$ , giving us $[1 : 0]$ ,
${0, 1, \dots, 11}$ are all coprime with $1$ , and we have trivial stabilizer, giving us the points $[0 : 1], [1 : 1], \dots, [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 $C_{2} \times C_{2}$ giving us just one additional point $[1 : 6]$ .

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

One way to see that $# P^{1} (Z / n Z) = Ψ (n)$ comes from a consequence of the Chinese Remainder Theorem that for the prime factorization $n = p_{1}^{e_{1}} \dots p_{k}^{e_{k}}$ we have
$P^{1} (Z / n Z) = P^{1} (Z / p_{1}^{e_{1}} Z) \times \dots \times P^{1} (Z / p_{k}^{e_{k}} Z)$
and for a prime power $p^{k}$ we have canonical representants for $P^{1} (Z / p^{k} Z)$
$[a : 1] for a = 0, 1, \dots, p^{k} - 1 and [1 : b] for b = 0, p, 2 p, 3 p, \dots, p^{k} - p$
which shows that $# P^{1} (Z / p^{k} Z) = (p + 1) p^{k - 1} = Ψ (p^{k})$ .

Next time, we’ll connect $P^{1} (Z / n Z)$ to Conway’s big picture and the congruence subgroup $Γ_{0} (n)$ .

Comments closed

the Riemann hypothesis and Psi

Published July 14, 2019 by lieven

Last time we revisited Robin’s theorem saying that 5040 being the largest counterexample to the bound
$\frac{σ (n)}{n l o g (l o g (n))} < e^{γ} = 1.78107 . . .$ is equivalent to the Riemann hypothesis.

There’s an industry of similar results using other arithmetic functions. Today, we’ll focus on Dedekind’s Psi function

Ψ (n) = n \prod_{p | n} (1 + \frac{1}{p})

where

p

runs over the prime divisors of

n

. It is series A001615 in the online encyclopedia of integer sequences and it starts off with

1, 3, 4, 6, 6, 12, 8, 12, 12, 18, 12, 24, 14, 24, 24, 24, 18, 36, 20, 36, 32, 36, 24, 48, 30, 42, 36, 48, 30, 72, 32, 48, 48, 54, 48, …

and here’s a plot of its first 1000 values

To understand this behaviour it is best to focus on the ‘slopes’ $\frac{Ψ (n)}{n} = \prod_{p | n} (1 + \frac{1}{p})$ .

So, the red dots of minimal ‘slope’

\approx 1

correspond to the prime numbers, and the ‘outliers’ have a maximal number of distinct small prime divisors. Look at

210 = 2 \times 3 \times 5 \times 7

and its multiples

420, 630

and

840

in the picture.

For this reason the primorial numbers, which are the products of the fist

k

prime numbers, play a special role. This is series A002110 starting off with

1, 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870,…

In Patrick Solé and Michel Planat Extreme values of the Dedekind $Ψ$ function, it is shown that the primorials play a similar role for Dedekind’s Psi as the superabundant numbers play for the sum-of-divisors function $σ (n)$ .

That is, if

N_{k}

is the

k

-th primorial, then for all

n < N_{k}

we have that the 'slope' at

n

is strictly below that of

N_{k}

\frac{Ψ (n)}{n} < \frac{Ψ (N_{k})}{N_{k}}

which follows immediately from the fact that any

n < N_{k}

can have at most

k - 1

distinct prime factors and

p \mapsto 1 + \frac{1}{p}

is a strictly decreasing function.

Another easy, but nice, observation is that for all

n

we have the inequalities

n^{2} > ϕ (n) \times ψ (n) > \frac{n^{2}}{ζ (2)}

where

ϕ (n)

is Euler’s totient function

ϕ (n) = n \prod_{p | n} (1 - \frac{1}{p})

This follows as once from the definitions of

ϕ (n)

and

Ψ (n)

ϕ (n) \times Ψ (n) = n^{2} \prod_{p | n} (1 - \frac{1}{p^{2}}) < n^{2} \prod_{p prime} (1 - \frac{1}{p^{2}}) = \frac{n^{2}}{ζ (2)}

But now it starts getting interesting.

In the proof of his theorem, Guy Robin used a result of his Ph.D. advisor Jean-Louis Nicolas

known as Nicolas’ criterion for the Riemann hypothesis: RH is true if and only if for all $k$ we have the inequality for the $k$ -th primorial number $N_{k}$
$\frac{N_{k}}{ϕ (N_{k}) l o g (l o g (N_{k}))} > e^{γ}$
From the above lower bound on $ϕ (n) \times Ψ (n)$ we have for $n = N_{k}$ that
$\frac{Ψ (N_{k})}{N_{k}} > \frac{N_{k}}{ϕ (N_{k}) ζ (2)}$
and combining this with Nicolas’ criterion we get
$\frac{Ψ (N_{k})}{N_{k} l o g (l o g (N_{k}))} > \frac{N_{k}}{ϕ (N_{k}) l o g (l o g (N_{k})) ζ (2)} > \frac{e^{γ}}{ζ (2)} \approx 1.08 \dots$
In fact, Patrick Solé and Michel Planat prove in their paper Extreme values of the Dedekind $Ψ$ function that RH is equivalent to the lower bound
$\frac{Ψ (N_{k})}{N_{k} l o g (l o g (N_{k}))} > \frac{e^{γ}}{ζ (2)}$
holding for all $k \geq 3$ .

Dedekind’s Psi function pops up in lots of interesting mathematics.

In the theory of modular forms, Dedekind himself used it to describe the index of the congruence subgroup

Γ_{0} (n)

in the full modular group

Γ

In other words, it gives us the number of tiles needed in the Dedekind tessellation to describe the fundamental domain of the action of $Γ_{0} (n)$ on the upper half-plane by Moebius transformations.

When $n = 6$ we have $Ψ (6) = 12$ and we can view its fundamental domain via these Sage commands:

G=Gamma0(6) FareySymbol(G).fundamental_domain()

giving us the 24 back or white tiles (note that these tiles are each fundamental domains of the extended modular group, so we have twice as many of them as for subgroups of the modular group)

But, there are plenty of other, seemingly unrelated, topics where $Ψ (n)$ appears. To name just a few:

The number of points on the projective line $P^{1} (Z / n Z)$ .
The number of lattices at hyperdistance $n$ in Conway’s big picture.
The number of admissible maximal commuting sets of operators in the Pauli group for the $n$ qudit.

and there are explicit natural one-to-one correspondences between all these manifestations of $Ψ (n)$ , tbc.

Comments closed