# Category: groups

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

• $\Psi(n)$ is the index of the congruence subgroup $\Gamma_0(n)$ in the modular group $\Gamma=PSL_2(\mathbb{Z})$,
• $\Psi(n)$ is the number of points in the projective line $\mathbb{P}^1(\mathbb{Z}/n\mathbb{Z})$,
• $\Psi(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$,
• $\Psi(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 $\Gamma_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 $\mathbb{P}^1(\mathbb{Z}/n\mathbb{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 $\Gamma_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 $\Gamma_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 $\mathbb{P}^1(\mathbb{Z}/n \mathbb{Z})$.

Over a field $k$ the points of $\mathbb{P}^1(k)$ correspond to the lines through the origin in the affine plane $\mathbb{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 $\# \mathbb{P}^1(\mathbb{Z}/p\mathbb{Z}) = p+1$. Here are the $8$ lines through the origin in $\mathbb{A}^2(\mathbb{Z}/7\mathbb{Z})$

Over an arbitrary (commutative) ring $R$ the points of $\mathbb{P}^1(R)$ again represent equivalence classes, this time of pairs
$(a,b) \in R^2~:~aR+bR=R$
with respect to scalar multiplication by units in $R$, that is
$(a,b) \sim (c,d)~\quad~\text{iff}~\qquad \exists \lambda \in R^*~:~a=\lambda c, b = \lambda d$
For $\mathbb{P}^1(\mathbb{Z}/n \mathbb{Z})$ we have to find all pairs of integers $(a,b) \in \mathbb{Z}^2$ with $0 \leq a,b < n$ with $gcd(a,b)=1$ and use Cremona’s trick to test for equivalence:
$(a,b) = (c,d) \in \mathbb{P}^1(\mathbb{Z}/n \mathbb{Z})~\quad \text{iff}~\quad ad-bc \equiv 0~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 $\S 1.3$ in the Tatitscheff, He and McKay paper suffices:

• Consider the action of $(\mathbb{Z}/n\mathbb{Z})^*$ on $\{ 0,1,…,n-1 \}=\mathbb{Z}/n\mathbb{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 $\mathbb{Z}/n \mathbb{Z}$ coprime with $d$,
• Then $\mathbb{P}^1(\mathbb{Z}/n\mathbb{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):

• $(\mathbb{Z}/12\mathbb{Z})^* = \{ 1,5,7,11 \} \simeq C_2 \times C_2$,
• 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 \}$,
• $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,…,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 $C_2 \times C_2$ giving us just one additional point $[1:6]$.

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

One way to see that $\# \mathbb{P}^1(\mathbb{Z}/n \mathbb{Z}) = \Psi(n)$ comes from a consequence of the Chinese Remainder Theorem that for the prime factorization $n = p_1^{e_1} … p_k^{e_k}$ we have
$\mathbb{P}^1(\mathbb{Z}/n \mathbb{Z}) = \mathbb{P}^1(\mathbb{Z}/p_1^{e_1} \mathbb{Z}) \times … \times \mathbb{P}^1(\mathbb{Z}/p_k^{e_k} \mathbb{Z})$
and for a prime power $p^k$ we have canonical representants for $\mathbb{P}^1(\mathbb{Z}/p^k \mathbb{Z})$
$[a:1]~\text{for}~a=0,1,…,p^k-1~\quad \text{and} \quad [1:b]~\text{for}~b=0,p,2p,3p,…,p^k-p$
which shows that $\# \mathbb{P}^1(\mathbb{Z}/p^k \mathbb{Z}) = (p+1)p^{k-1}= \Psi(p^k)$.

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

Last time we revisited Robin’s theorem saying that 5040 being the largest counterexample to the bound
$\frac{\sigma(n)}{n~log(log(n))} < e^{\gamma} = 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
$\Psi(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{\Psi(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 $\Psi$ 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 $\sigma(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{\Psi(n)}{n} < \frac{\Psi(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 > \phi(n) \times \psi(n) > \frac{n^2}{\zeta(2)}$
where $\phi(n)$ is Euler’s totient function
$\phi(n) = n \prod_{p | n}(1 – \frac{1}{p})$
This follows as once from the definitions of $\phi(n)$ and $\Psi(n)$
$\phi(n) \times \Psi(n) = n^2 \prod_{p|n}(1 – \frac{1}{p^2}) < n^2 \prod_{p~\text{prime}} (1 - \frac{1}{p^2}) = \frac{n^2}{\zeta(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}{\phi(N_k)~log(log(N_k))} > e^{\gamma}$
From the above lower bound on $\phi(n) \times \Psi(n)$ we have for $n=N_k$ that
$\frac{\Psi(N_k)}{N_k} > \frac{N_k}{\phi(N_k) \zeta(2)}$
and combining this with Nicolas’ criterion we get
$\frac{\Psi(N_k)}{N_k~log(log(N_k))} > \frac{N_k}{\phi(N_k)~log(log(N_k)) \zeta(2)} > \frac{e^{\gamma}}{\zeta(2)} \approx 1.08…$
In fact, Patrick Solé and Michel Planat prove in their paper Extreme values of the Dedekind $\Psi$ function that RH is equivalent to the lower bound
$\frac{\Psi(N_k)}{N_k~log(log(N_k))} > \frac{e^{\gamma}}{\zeta(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 $\Gamma_0(n)$ in the full modular group $\Gamma$.

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

When $n=6$ we have $\Psi(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 $\Psi(n)$ appears. To name just a few:

• The number of points on the projective line $\mathbb{P}^1(\mathbb{Z}/n\mathbb{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 $\Psi(n)$, tbc.

Yesterday, there was an interesting post by John Baez at the n-category cafe: The Riemann Hypothesis Says 5040 is the Last.

The 5040 in the title refers to the largest known counterexample to a bound for the sum-of-divisors function
$\sigma(n) = \sum_{d | n} d = n \sum_{d | n} \frac{1}{n}$

In 1983, the french mathematician Guy Robin proved that the Riemann hypothesis is equivalent to
$\frac{\sigma(n)}{n~log(log(n))} < e^{\gamma} = 1.78107...$ when $n > 5040$.

The other known counterexamples to this bound are the numbers 3,4,5,6,8,9,10,12,16,18,20,24,30,36,48,60,72,84,120,180,240,360,720,840,2520.

In Baez’ post there is a nice graph of this function made by Nicolas Tessore, with 5040 indicated with a grey line towards the right and the other counterexamples jumping over the bound 1.78107…

Robin’s theorem has a remarkable history, starting in 1915 with good old Ramanujan writing a part of this thesis on “highly composite numbers” (numbers divisible by high powers of primes).

His PhD. adviser Hardy liked his result but called them “in the backwaters of mathematics” and most of it was not published at the time of Ramanujan’s degree ceremony in 1916, due to paper shortage in WW1.

When Ramanujan’s paper “Highly Composite Numbers” was first published in 1988 in ‘The lost notebook and other unpublished papers’ it became clear that Ramanujan had already part of Robin’s theorem.

Ramanujan states that if the Riemann hypothesis is true, then for $n_0$ large enough we must have for all $n > n_0$ that
$\frac{\sigma(n)}{n~log(log(n))} < e^{\gamma} = 1.78107...$ When Jean-Louis Nicolas, Robin's PhD. adviser, read Ramanujan's lost notes he noticed that there was a sign error in Ramanujan's formula which prevented him from seeing Robin's theorem.

Nicolas: “Soon after discovering the hidden part, I read it and saw the difference between Ramanujan’s result and Robin’s one. Of course, I would have bet that the error was in Robin’s paper, but after recalculating it several times and asking Robin to check, it turned out that there was an error of sign in what Ramanujan had written.”

If you are interested in the full story, read the paper by Jean-Louis Nicolas and Jonathan Sondow: Ramanujan, Robin, Highly Composite Numbers, and the Riemann Hypothesis.

What’s the latest on Robin’s inequality? An arXiv-search for Robin’s inequality shows a flurry of activity.

For starters, it has been verified for all numbers smaller that $10^{10^{13}}$…

It has been verified, unconditionally, for certain classes of numbers:

• all odd integers $> 9$
• all numbers not divisible by a 25-th power of a prime

Rings a bell? Here’s another hint:

According to Xiaolong Wu in A better method than t-free for Robin’s hypothesis one can replace the condition of ‘not divisible by an N-th power of a prime’ by ‘not divisible by an N-th power of 2’.

Further, he claims to have an (as yet unpublished) argument that Robin’s inequality holds for all numbers not divisible by $2^{42}$.

So, where should we look for counterexamples to the Riemann hypothesis?

What about the orders of huge simple groups?

The order of the Monster group is too small to be a counterexample (yet, it is divisible by $2^{46}$).

The usual argument to show that the group of all orientation-preserving symmetries of the Klein quartic is the simple group $L_2(7)$ of order $168$ goes like this:

There are two families of $7$ truncated cubes on the Klein quartic. The triangles of one of the seven truncated cubes in the first family have as center the dots, all having the same colour. The triangles of one of the truncated cubes in the second family correspond to the squares all having the same colour.

If you compare the two colour schemes, you’ll see that every truncated cube in the first family is disjoint from precisely $3$ truncated cubes in the second family.

That is, we can identify the truncated cubes of the first family with the points in the Fano plane $\mathbb{P}^2(\mathbb{F}_2)$, and those of the second family with the lines in that plane.

The Klein quartic consists of $24$ regular heptagons, so its rotation symmetry group consists of $24 \times 7 = 168$ rotations,each preserving the two families of truncated cubes. This is exactly the same number as there are isomorphisms of the Fano plane, $PGL_3(\mathbb{F}_2) = L_2(7)$. Done!

For more details, check John Baez’ excellent page on the Klein quartic, or the Buckyball curve post.

Here’s another ‘look-and-see’ proof, starting from Klein’s own description of his quartic.

Look at the rotation $g$, counter-clockwise with angle $2\pi / 7$ fixing the center of the central blue heptagon, and a similar rotation $h$ fixing the center of one of the neighbouring red heptagons.

The two vertices of the edge shared by the blue and red heptagon are fixed by $g.h$ and $h.g$, respectively, so these rotations must have order three (there are $3$ heptagons meeting in the vertex).

That is, the rotation symmetry group $G$ of the Klein quartic has order $168$, and contains two elements $g$ and $h$ of order $7$, such that the subgroup generated by them contains elements of order $3$.

This is enough to prove that the $G$ must be simple and therefore isomorphic to $L_2(7)$!

The following elegant proof is often attributed to Igor Dolgachev.

If $G$ isn’t simple there is a maximal normal subgroup $N$ with $G/N$ simple .

The only non-cyclic simple group having less elements that $168$ is $A_5$ but this cannot be $G/N$ as $60$ does not divide $168$.

So, $G/N$ must be cyclic of order $2,3$ or $7$ (the only prime divisors of $168=2^3.3.7$).

Order $2$ is not possible as any group $N$ of order $84=2^2.3.7$ can just have one Sylow $7$-subgroup. Remember that the number of $7$-Sylows of $N$ must divide $2^2.3=12$ and must be equal to $1$ modulo $7$. And $G$ (and therefore $N$) has at least two different cyclic subgroups of order $7$.

Order $3$ is impossible as this would imply that the normal subgroup $N$ of order $2^3.7=56$ must contain all $7$-Sylows of $G$, and thus also an element of order $3$. But, $3$ does not divide $56$.

Order $7$ is a bit more difficult to exclude. This would mean that there is a normal subgroup $N$ of order $2^3.3=24$.

$N$ (being normal) must contain all Sylow $2$-subgroups of $G$ of which there are either $1$ or $3$ (the order of $N$ is $2^3.3=24$).

If there is just one $S$ it should be a normal subgroup with $G/S$ (of order $21$) having a (normal) unique Sylow $7$-subgroup, but then $G$ would have a normal subgroup of index $3$, which we have excluded.

The three $2$-Sylows are conjugated and so the conjugation morphism
$G \rightarrow S_3$
is non-trivial and must have image strictly larger than $C_3$ (otherwise, $G$ would have a normal subgroup of index $3$), so must be surjective.

But, $S_3$ has a normal subgroup of index $2$ and pulling this back, $G$ must also have a normal subgroup of index two, which we have excluded. Done!

David Singmaster‘s “Notes on Rubik’s magic cube” are a collectors item, but it is still possible to buy a copy. I own a fifth edition (august 1980).

These notes capture the Rubik craze of those years really well.

Here’s a Conway story, from Siobhan Roberts’ excellent biography Genius at Play.

The ICM in Helsinki in 1978 was Conway’s last shot to get the Fields medal, but this was the last thing on his mind. He just wanted a Rubik cube (then, iron-curtain times, only sold in Hungary), so he kept chasing Hungarians at the meeting, hoping to obtain one. Siobhan writes (p. 239):

“The Fields Medals went to Pierre Deligne, Charles Fefferman, Grigory Margulis, and Daniel Quillen. The Rubik’s cube went to Conway.”

After his Notes, David Singmaster produced a follow-up newsletter “The Cubic Circular”. Only 5 magazines were published, of which 3 were double issues, between the Autumn of 1981 and the summer of 1985.