Connected fundamental domains for congruence subgroups

This paper constructs canonical sets of right coset representatives for the congruence subgroups $\Gamma_0(N)$, $\Gamma_1(N)$, and $\Gamma(N)$ to prove that their corresponding fundamental domains are connected, utilizing a study of the projective line $\mathbb{P}^1(\mathbb{Z}/N\mathbb{Z})$ and a multiplicity function $M$ that is shown to be one less than a more computable function $W$.

The Gist

Imagine you are an architect trying to tile a vast, infinite floor (the "Upper Half Plane") with identical, perfect triangular tiles. This floor represents the world of complex numbers used in advanced mathematics.

The paper you're asking about is essentially a construction manual for a very specific, tricky type of tiling project. The authors, Zhaohu Nie and C. Xavier Parent, have figured out how to lay down these tiles so that they form one single, unbroken, connected shape, rather than a scattered pile of disconnected islands.

Here is the breakdown of their work using simple analogies:

1. The Setting: The Infinite Floor and the Rules

Think of the "Upper Half Plane" as an endless ocean of blue tiles. There is a master set of rules (called $\Gamma(1)$) that tells you how you can slide, flip, or rotate these tiles. If you slide a tile according to these rules, it lands on top of another tile perfectly.

Now, imagine you want to build a fence around a specific area of this ocean. You want to pick a "Fundamental Domain."

• The Goal: Pick a specific shape made of tiles that covers the entire ocean exactly once (no overlaps, no gaps) when you apply the master rules.
• The Problem: Usually, when mathematicians pick these shapes for complex sub-rules (called "Congruence Subgroups"), the resulting shape is a messy, scattered collection of disconnected islands. It's like trying to build a house out of bricks that are floating miles apart. You can't walk from the kitchen to the bedroom without teleporting.

The Authors' Achievement: They found a way to pick the tiles so that the final house is one connected room. You can walk from any point in the shape to any other point without leaving the shape.

2. The "Coset Representatives": The Key to the Door

To build this connected house, you need a list of specific "moves" (matrices) to apply to your starting tile. In math terms, these are called right coset representatives.

Think of it like a dance troupe.

• The "Master Dance" is the full set of moves ($\Gamma(1)$).
• The "Sub-Dance" is the specific group you are studying ($\Gamma_0(N)$, $\Gamma_1(N)$, etc.).
• To cover the whole floor, you need to know exactly which specific moves from the Master Dance are unique to your Sub-Dance.

The authors created a canonical (standard) list of these moves. Before this paper, people had to use computer programs to guess and check which moves worked, hoping the resulting shape would be connected. The authors said, "No, we can write a formula that guarantees the shape will be connected."

3. The Secret Ingredient: The "M" and "W" Functions

The magic trick that makes the shape connected relies on a specific counting function they call $M$.

• The Analogy: Imagine you are walking through a forest of trees (numbers). Some trees are "safe" (units) and some are "blocked" (not units).
• The Function $M$: For a specific spot in the forest, $M$ asks: "How many steps do I need to take before I hit a safe tree?"
• The Function $W$: The authors discovered that $M$ is just a simple math problem away from another function, $W$. They found that $W = M + 1$.
  • Why this matters: $M$ was hard to calculate. $W$ is easy to calculate. By realizing they are just one step apart, the authors could quickly figure out exactly how many tiles to stack up in each direction to ensure the whole structure holds together.

4. The "Graph" Connection

To prove their shape is connected, they drew a map (a graph).

• Nodes: Each tile in their list is a dot on the map.
• Lines: If two tiles touch each other (share an edge), they draw a line between the dots.
• The Proof: They showed that you can draw a path from any dot to any other dot without lifting your pencil. If the map is connected, the physical shape (the fundamental domain) is connected.

5. The Examples: From Simple to Complex

The paper ends with pictures (Figures 1–4) showing their results for different numbers ($N$).

• $N=6$: A relatively simple, connected shape.
• $N=30$: A much more complex, intricate shape. Because 30 has three prime factors (2, 3, 5), the "forest" is denser, and the "steps" ($M$) required to find safe trees get larger. The resulting shape looks like a complex, multi-lobed flower, but crucially, all the petals are still attached to the stem.

Summary: Why Should You Care?

Before this paper, if you wanted to visualize these mathematical shapes, you had to rely on trial-and-error computer programs that gave you a result but didn't explain why it looked that way.

Nie and Parent gave us:

1. A Recipe: A clear, step-by-step list of moves to build the shape.
2. A Guarantee: A mathematical proof that the shape will always be one connected piece.
3. A Shortcut: A simpler way to calculate the necessary steps using their new $W$ function.

In short, they turned a chaotic, scattered puzzle into a neat, connected, and predictable structure, making it much easier for mathematicians to study the hidden patterns of numbers.

Technical Summary

Here is a detailed technical summary of the paper "Connected Fundamental Domains for Congruence Subgroups" by Zhaohu Nie and C. Xavier Parent.

1. Problem Statement

The paper addresses the construction of canonical sets of right coset representatives for the congruence subgroups $\Gamma_0(N)$, $\Gamma_1(N)$, and $\Gamma(N)$ of the modular group $\Gamma(1) = SL_2(\mathbb{Z})$.

The primary objective is to ensure that the union of the images of the standard fundamental domain $D$ (the standard hyperbolic triangle) under these representatives forms a connected fundamental domain for the subgroup.

• Context: While fundamental domains for $\Gamma(1)$ are well-understood, constructing connected fundamental domains for congruence subgroups is non-trivial.
• Gap in Literature: Existing methods (often computer-based, such as Verrill's program) can generate connected domains but lack a structural, conceptual understanding of the representatives used. There was no known canonical list of representatives that guarantees connectedness for general $N$.

2. Methodology

The authors employ a combination of group theory, number theory, and graph theory to solve this problem.

A. Group Theoretic Framework

• Generators: The paper utilizes the standard generators of $\Gamma(1)$: $T = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ and $S = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$.
• Coset Representatives: The strategy involves finding a specific set of matrices $\{\gamma_i\}$ such that the interior of $\bigcup \gamma_i D$ is connected.
• Symmetric Residue Classes: To improve visualization and symmetry, the authors define a symmetric range for residues modulo $N$: $-N_1 \leq x \leq N_2$, where $N_1 = \lfloor \frac{N-1}{2} \rfloor$ and $N_2 = \lfloor \frac{N}{2} \rfloor$.

B. The Projective Line and Multiplicity Function

The core of the construction relies on a bijection between the right cosets of $\Gamma_0(N)$ and the projective line $\mathbb{P}^1(\mathbb{Z}/N\mathbb{Z})$.

• Decomposition: The projective line is split into an "affine part" $A_1$ (where $\gcd(a, N)=1$) and a "hyperplane at infinity" $H$ (where $\gcd(a, N) > 1$).
• The Function $M$: The authors define a function $M: \mathbb{P}^1(\mathbb{Z}/N\mathbb{Z}) \to \mathbb{Z}_{\geq 0}$ for a class $(a:b)$:
  $$M(a:b) = \min \{m \in \mathbb{Z}_{\geq 0} \mid \gcd(ma - b, N) = 1\}$$
  This function determines the "depth" or number of $T$-transitions required to reach a unit in the modular arithmetic context.
• Preferred Representatives: Using $M$, the authors define a map to select "preferred" elements in each coset class, specifically choosing representatives of the form $ST^j ST^m$ where $0 \leq m \leq M_j$.

C. Graph Connectivity

To prove the resulting domain is connected, the authors introduce a graph $G_\Theta$:

• Vertices: The chosen coset representatives.
• Edges: Two vertices $\theta_i, \theta_j$ are connected if $\theta_j = \theta_i S$, $\theta_j = \theta_i T$, or $\theta_j = \theta_i T^{-1}$.
• Lemma 2.8: The domain $\text{Int}(\bigcup \theta_i D)$ is connected if and only if the graph $G_\Theta$ is connected.
• Strategy: The authors explicitly construct a spanning tree for $G_\Theta$ to prove connectivity.

D. The Function $W$

The authors introduce a computationally simpler function $W: \mathbb{Z}/N\mathbb{Z} \to \mathbb{N}$:
$$W_j = \min \{m \in \mathbb{N} \mid mj - 1 \in (\mathbb{Z}/N\mathbb{Z})^*\}$$
They prove the relationship $W_j = M_j + 1$, which significantly speeds up the calculation of the bounds for the representatives.

3. Key Contributions and Results

A. Canonical Lists of Representatives

The paper provides explicit, canonical lists of right coset representatives for the three main congruence subgroups:

1. For $\Gamma_0(N)$:
   The set $\Theta_0$ consists of:

   • $ST^i$ for $-N_1 \leq i \leq N_2$ (covering the affine part).
   • $ST^j ST^m$ for $-N_1 \leq j \leq N_2$ with $\gcd(j, N) > 1$ and $0 \leq m \leq M_j$.

2. For $\Gamma_1(N)$:
   The set $\Theta_1$ extends $\Theta_0$ by multiplying by representatives of $(\pm I)\Gamma_1(N) \backslash \Gamma_0(N)$. This involves terms like $ST^k ST^{k^{-1}} S$ where $k$ is a unit modulo $N$.

3. For $\Gamma(N)$:
   The set is constructed by multiplying the representatives of $\Gamma_1(N)$ by powers of $T$ (specifically $T^\ell$ for $-N_1 \leq \ell \leq N_2$).

B. Proof of Connectedness

The authors rigorously prove that the graphs corresponding to these sets ($G_{\Theta_0}$, $G_{\Theta_1}$, etc.) are connected.

• They demonstrate that every vertex in the graph can be reached from the identity element $S$ (or $I$) via a path of $S$ and $T$ transitions.
• This guarantees that the union of the transformed fundamental domains forms a single connected region in the upper half-plane.

C. Theorem on $M$ and $W$

Theorem 1.12: For any $j \in \mathbb{Z}/N\mathbb{Z}$, $W_j = M_j + 1$.
This result allows for the rapid computation of the bounds $M_j$ required to define the fundamental domains, replacing a more complex minimization problem with a direct check of units.

4. Examples and Visualizations

The paper includes computational examples generated using Maple:

• $\Gamma_0(6)$: Illustrates a case where $M_j$ values are small (0 or 1).
• $\Gamma_1(8)$: Shows the structure when $N$ is a prime power.
• $\Gamma_0(30)$: A complex example with three prime factors ($2, 3, 5$). Here,$M_j$can be greater than 1 (up to 3). The authors provide a detailed table of representatives, cusp widths, and the corresponding cusp representatives, demonstrating how the$M_j + 1$ values relate to the widths of the cusps.

5. Significance

• Conceptual Clarity: The paper moves beyond "brute-force" computer searches to provide a structural, algebraic understanding of how to construct connected fundamental domains.
• Algorithmic Efficiency: The relationship $W_j = M_j + 1$ provides a fast algorithm for determining the necessary representatives for any $N$.
• Canonical Nature: The lists provided are "canonical," meaning they are defined by specific mathematical properties (symmetry and minimality) rather than arbitrary choices, making them reproducible and standard.
• Foundation for Further Study: The explicit construction of these domains and the study of the function $M$ lay the groundwork for future research into the geometry of modular curves and the distribution of cusps.

In summary, Nie and Parent successfully bridge the gap between abstract group theory and geometric visualization by providing a constructive, proven method to generate connected fundamental domains for congruence subgroups, accompanied by a new number-theoretic function that simplifies the underlying calculations.