The Modular Group

The modular group $\mathrm{PSL}(2,\mathbb{Z})$ is the group of $2×2$ integer matrices of determinant $1$, taken up to overall sign. It acts on the upper half-plane by Möbius transformations $z ↦ \frac{az+b}{cz+d}$, and the quotient is the modular surface — the object that continued fractions, binary quadratic forms, the Farey tree and the $j$-invariant are all secretly about.

What makes it a good fit here is that it is a free product, $\mathbb{Z}/2 * \mathbb{Z}/3$. A free product has no relations to speak of, so every element is a word, and questions about the group become questions about words — which is combinatorics this catalogue already knows how to count.

The payoff at the end of the page: a conjugacy class in this group is a closed orbit of a flow, that orbit is a knot in the complement of a trefoil, and the knot's linking number with that trefoil is something you can read off the word by counting letters.

Two generators, three alphabets

The group is generated by

$$S = \begin{pmatrix} 0 & -1 \\ 1 & 0\end{pmatrix}, \qquad T = \begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix},$$

with $S$ the inversion $z ↦ -1/z$ and $T$ the translation $z ↦ z+1$. In $\mathrm{PSL}$, $S$ has order $2$ and $U = ST$ has order $3$; those two are the free factors.

But there are three useful alphabets, and they name the same elements:

alphabet	letters	what a word is
$S,\ T$	the geometric generators	an alternating product $T^{e_0}ST^{e_1}S\cdots$ — the exponents are a continued fraction
$L,\ R$	$\begin{pmatrix}1&0\\1&1\end{pmatrix}$, $\begin{pmatrix}1&1\\0&1\end{pmatrix}$	a positive word, unique for any matrix with non-negative entries — and it is a path down the Stern–Brocot tree
necklace	$L,R$ up to rotation	a conjugacy class — i.e. a closed geodesic

#A matrix is a word

The peel is the subtractive Euclidean algorithm, so it never has to search.

In$\mathrm{ModularWord}(\mathrm{ModularMatrix}(1, 1, 1, 2))$Out$\text{LR}$In$\mathrm{ModularWord}(\mathrm{ModularMatrix}(5, 3, 3, 2))$Out$\text{RLRL}$In$\mathrm{ModularTrace}(\text{LRLR})$Out$7$In$\mathrm{ModularSTWord}(\mathrm{ModularMatrix}(3, 2, 4, 3))$Out$\bigl\lbrack0, -2, -2, -2, 0\bigr\rbrack$

source · editable

<notatio-cell value="ModularWord(ModularMatrix(1, 1, 1, 2))" data-allow-mismatch="children" /> <notatio-cell value="ModularWord(ModularMatrix(5, 3, 3, 2))" data-allow-mismatch="children" /> <notatio-cell value='ModularTrace("LRLR")' data-allow-mismatch="children" /> <notatio-cell value="ModularSTWord(ModularMatrix(3, 2, 4, 3))" data-allow-mismatch="children" />

Why the peel never needs a search is worth a sentence: $R^{-1}M$ subtracts row 2 from row 1 and $L^{-1}M$ subtracts row 1 from row 2, so $R$ comes off when $a ≥ c$ and $b ≥ d$, and $L$ when $c ≥ a$ and $d ≥ b$. Both conditions at once would force $a=c$ and $b=d$, hence determinant $0$ — impossible. There is never a choice to make.

The trace sorts elements into three kinds, and the trichotomy is the whole geometry: elliptic elements ($|\mathrm{tr}| < 2$) are rotations of finite order, parabolic ones ($=2$) fix a single point on the boundary, and hyperbolic ones ($>2$) translate along a geodesic. Only the last kind has a closed geodesic, and a positive $LR$ word is hyperbolic exactly when it uses both letters.

#The trichotomy

All-L or all-R is parabolic: a word has to turn both ways to close up.

In$\mathrm{ModularKind}(\text{LR})$Out$\text{Hyperbolic}$In$\mathrm{ModularKind}(\mathrm{ModularMatrix}(1, 5, 0, 1))$Out$\text{Parabolic}$In$\mathrm{ModularKind}(\mathrm{ModularMatrix}(0, -1, 1, 0))$Out$\text{Elliptic}$

source · editable

<notatio-cell value='ModularKind("LR")' data-allow-mismatch="children" /> <notatio-cell value="ModularKind(ModularMatrix(1, 5, 0, 1))" data-allow-mismatch="children" /> <notatio-cell value="ModularKind(ModularMatrix(0, -1, 1, 0))" data-allow-mismatch="children" />

Words are continued fractions

The $L$/$R$ word of a positive rational is its path down the Stern–Brocot tree, and the runs of that path are its continued fraction — with the last run one short, because the final step is the arrival rather than a turn. Three objects, one description.

#One object, three names

π's famous convergent: three rights, seven lefts, fifteen rights.

In$\mathrm{ContinuedFraction}(\frac{355}{113})$Out$\bigl\lbrack3, 7, 16\bigr\rbrack$In$\mathrm{SternBrocotPath}(355, 113)$Out$\text{RRRLLLLLLLRRRRRRRRRRRRRRR}$In$\mathrm{FromSternBrocotPath}(\text{RLR})$Out$\frac{5}{3}$In$\mathrm{FromContinuedFraction}(\bigl\lbrack3, 7, 16\bigr\rbrack)$Out$\frac{355}{113}$

source · editable

<notatio-cell value="ContinuedFraction(355 / 113)" data-allow-mismatch="children" /> <notatio-cell value="SternBrocotPath(355, 113)" data-allow-mismatch="children" /> <notatio-cell value='FromSternBrocotPath("RLR")' data-allow-mismatch="children" /> <notatio-cell value="FromContinuedFraction([3, 7, 16])" data-allow-mismatch="children" />

The Fibonacci fractions alternate perfectly — $R L R L R \ldots$ — which is the sense in which the golden ratio is the "most irrational" number: its path never commits to a direction, so no convergent is ever unusually good.

#Farey

Consecutive Farey fractions satisfy ps − qr = ±1 — a determinant, i.e. a group element.

In$\mathrm{FareySequence}(5)$Out$\bigl\lbrack0, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, 1\bigr\rbrack$In$\mathrm{FareyNeighbours}(1, 3, 1, 2)$Out$\mathrm{True}$In$\mathrm{FareyNeighbours}(1, 3, 2, 3)$Out$\mathrm{False}$

source · editable

<notatio-cell value="FareySequence(5)" data-allow-mismatch="children" /> <notatio-cell value="FareyNeighbours(1, 3, 1, 2)" data-allow-mismatch="children" /> <notatio-cell value="FareyNeighbours(1, 3, 2, 3)" data-allow-mismatch="children" />

Closed geodesics are necklaces

Here is the step that turns geometry into counting. Conjugating a positive word by its own first letter rotates it: $x^{-1}(xw)x = wx$. So a conjugacy class of positive words is precisely a word up to cyclic rotation — a binary necklace.

And a hyperbolic conjugacy class is a closed geodesic on the modular surface. So:

closed geodesics of symbolic length $n$ $\;=\;$ binary necklaces of length $n$, less the two constant ones (which are parabolic, not hyperbolic).

That is a closed form, $\frac{1}{n}\sum_{d \mid n} \varphi(d)\,2^{n/d} - 2$, and the primitive geodesics — those not a repeat of a shorter one — are counted by the aperiodic necklaces, the Lyndon words: $\frac{1}{n}\sum_{d \mid n} μ(d)\,2^{n/d}$.

#Every geodesic of a given length

Named by the least rotation, which is the canonical name of a necklace.

In$\mathrm{ModularClasses}(4)$Out$\bigl\lbrack\text{LLLR}, \text{LLRR}, \text{LRLR}, \text{LRRR}\bigr\rbrack$In$\mathrm{ModularClass}(\text{RLL})$Out$\text{LLR}$In$\mathrm{ModularClass}(\text{LRL})$Out$\text{LLR}$In$\mathrm{IsPrimitiveClass}(\text{LRLR})$Out$\mathrm{False}$

source · editable

<notatio-cell value="ModularClasses(4)" data-allow-mismatch="children" /> <notatio-cell value='ModularClass("RLL")' data-allow-mismatch="children" /> <notatio-cell value='ModularClass("LRL")' data-allow-mismatch="children" /> <notatio-cell value='IsPrimitiveClass("LRLR")' data-allow-mismatch="children" />

The word length is the geodesic's symbolic period — how many times it crosses the fundamental domain. Its geometric length is $ℓ = 2\,\mathrm{arccosh}(|\mathrm{tr}|/2)$, so the trace is the real weight, and the two orderings do not agree: $LLLR$ and $LRLR$ have the same word length but traces $5$ and $7$. The shortest closed geodesic on the modular surface is $LR$, with trace $3$; its fixed point is the golden ratio.

The same cycles, as quadratic forms

Gauss got to these cycles from a completely different direction, and it is worth seeing that they are the same ones.

A binary quadratic form is $ax^2 + bxy + cy^2$, carried by its triple $(a,b,c)$, with discriminant $D = b^2 - 4ac$. The modular group acts on forms by substituting $(x,y) ↦ (px+qy,\; rx+sy)$, the discriminant is invariant, and the orbits are the classes — the objects class numbers count.

When $D > 0$ and is not a perfect square the form is indefinite, and the thing that makes it belong here happens: a class does not contain one distinguished reduced form but a whole cycle of them. Step round that cycle with $ρ$ and you are running the continued fraction of the form's root; it closes because that expansion is periodic. So

a class of indefinite forms $=$ a cycle of reduced forms $=$ a periodic continued fraction $=$ a closed geodesic.

#A class is a cycle

The cycle length is always even — ρ flips the sign of the leading coefficient.

In$\mathrm{FormCycle}(\mathrm{QuadraticForm}(1, 1, -1))$Out$\bigl\lbrack\mathrm{QuadraticForm}(1, 1, -1), \mathrm{QuadraticForm}(-1, 1, 1)\bigr\rbrack$In$\mathrm{ReducedForms}(60)$Out$\bigl\lbrack\mathrm{QuadraticForm}(-6, 6, 1), \mathrm{QuadraticForm}(-3, 6, 2), \mathrm{QuadraticForm}(-2, 6, 3), \mathrm{QuadraticForm}(-1, 6, 6), \mathrm{QuadraticForm}(1, 6, -6), \mathrm{QuadraticForm}(2, 6, -3), \mathrm{QuadraticForm}(3, 6, -2), \mathrm{QuadraticForm}(6, 6, -1)\bigr\rbrack$In$\mathrm{FormClassNumber}(60)$Out$4$In$\mathrm{FormClassNumber}(12)$Out$2$

source · editable

<notatio-cell value="FormCycle(QuadraticForm(1, 1, -1))" data-allow-mismatch="children" /> <notatio-cell value="ReducedForms(60)" data-allow-mismatch="children" /> <notatio-cell value="FormClassNumber(60)" data-allow-mismatch="children" /> <notatio-cell value="FormClassNumber(12)" data-allow-mismatch="children" />

The stabiliser of a form is generated by its automorph, built from the fundamental solution of Pell's equation $t^2 - Du^2 = 4$:

$$\begin{pmatrix} (t - bu)/2 & -cu \\ au & (t + bu)/2 \end{pmatrix},$$

whose determinant is $(t^2 - Du^2)/4 = 1$ and whose trace is $t$. Since $t > 2$ that matrix is hyperbolic — so the form's class really is one of the closed geodesics above, and it has an $LR$ word like any other.

#Pell, the automorph, and back to a word

The automorph fixes the form, and its word is the geodesic the class names.

In$\mathrm{PellSolution}(5)$Out$\bigl\lbrack3, 1\bigr\rbrack$In$\mathrm{FormAutomorph}(\mathrm{QuadraticForm}(1, 1, -1))$Out$\mathrm{ModularMatrix}(1, 1, 1, 2)$In$\mathrm{FormAction}(\mathrm{QuadraticForm}(1, 1, -1), \mathrm{FormAutomorph}(\mathrm{QuadraticForm}(1, 1, -1)))$Out$\mathrm{QuadraticForm}(1, 1, -1)$In$\mathrm{ModularWord}(\mathrm{FormAutomorph}(\mathrm{QuadraticForm}(1, 1, -1)))$Out$\text{LR}$

source · editable

<notatio-cell value="PellSolution(5)" data-allow-mismatch="children" /> <notatio-cell value="FormAutomorph(QuadraticForm(1, 1, -1))" data-allow-mismatch="children" /> <notatio-cell value="FormAction(QuadraticForm(1, 1, -1), FormAutomorph(QuadraticForm(1, 1, -1)))" data-allow-mismatch="children" /> <notatio-cell value="ModularWord(FormAutomorph(QuadraticForm(1, 1, -1)))" data-allow-mismatch="children" />

That the $ρ$-cycles really are the equivalence classes is the load-bearing claim, and it is checked against an oracle that never mentions $ρ$: given two forms, a transforming matrix must have a first column $(p,r)$ with $f(p,r) = a'$, and along the resulting family the middle coefficient moves in steps of exactly $2a'$ — so the matrix is solved for rather than searched, and the check is exact.

The knots they draw

Now the geometry. The modular flow is the geodesic flow on the unit tangent bundle of the modular surface, and its closed orbits are exactly the hyperbolic conjugacy classes above. The striking fact is what that unit tangent bundle is:

$$\mathrm{SL}(2,\mathbb{Z}) \backslash \mathrm{SL}(2,\mathbb{R}) \;≅\; S^3 ∖ \text{trefoil}.$$

The space the flow lives in is the complement of a trefoil knot in the $3$-sphere. So every closed orbit is a closed curve in that complement — a modular knot. Étienne Ghys proved that these are precisely the Lorenz knots, the periodic orbits of the Lorenz attractor, and that their linking number with the missing trefoil has a completely elementary description:

$$\mathrm{lk}(k_γ, \text{trefoil}) \;=\; Ψ(γ) \;=\; \#R - \#L .$$

Count the letters. That is the linking number.

#Ghys's theorem, as a calculation

A geodesic that turns equally both ways has linking number zero.

In$\mathrm{LinkingWithTrefoil}(\text{LLRR})$Out$0$In$\mathrm{LinkingWithTrefoil}(\text{LRRRR})$Out$3$In$\mathrm{WordSymbol}(\text{LRRRR})$Out$3$In$\mathrm{LinkingWithTrefoil}(\text{LLLR})$Out$-2$

source · editable

<notatio-cell value='LinkingWithTrefoil("LLRR")' data-allow-mismatch="children" /> <notatio-cell value='LinkingWithTrefoil("LRRRR")' data-allow-mismatch="children" /> <notatio-cell value='WordSymbol("LRRRR")' data-allow-mismatch="children" /> <notatio-cell value='LinkingWithTrefoil("LLLR")' data-allow-mismatch="children" />

Where the arithmetic comes in

Counting letters is one description of that linking number. The other comes from number theory and looks nothing like it. Rademacher's function is

$$Φ\begin{pmatrix} a & b \\ c & d\end{pmatrix} = \frac{a+d}{c} - 12\,\mathrm{sign}(c)\,s(d,|c|), \qquad c ≠ 0,$$

where $s(h,k) = \sum_{j=1}^{k-1} \left(\!\left(\tfrac{j}{k}\right)\!\right)\left(\!\left(\tfrac{hj}{k}\right)\!\right)$ is a Dedekind sum — the same sum that appears in the transformation law of the Dedekind eta function and in the exact formula for the partition numbers. The Rademacher symbol corrects $Φ$ into a class function:

$$Ψ(M) = Φ(M) - 3\,\mathrm{sign}\big(c(a+d)\big).$$

Nothing in that formula mentions words. That $Ψ$ equals $\#R - \#L$ on every hyperbolic element is the theorem, and it is what the package's tests check — one side by brute-force Dedekind sums over the matrix, the other by counting letters in a string.

#The other side of the identity

Φ alone is not conjugation-invariant; only the corrected Ψ is.

In$\mathrm{DedekindSum}(4, 3)$Out$\frac{1}{18}$In$\mathrm{RademacherPhi}(\mathrm{ModularMatrix}(1, 7, 0, 1))$Out$7$In$\mathrm{RademacherPhi}(\text{LLLR})$Out$1$In$\mathrm{RademacherSymbol}(\text{LLLR})$Out$-2$

source · editable

<notatio-cell value="DedekindSum(4, 3)" data-allow-mismatch="children" /> <notatio-cell value="RademacherPhi(ModularMatrix(1, 7, 0, 1))" data-allow-mismatch="children" /> <notatio-cell value='RademacherPhi("LLLR")' data-allow-mismatch="children" /> <notatio-cell value='RademacherSymbol("LLLR")' data-allow-mismatch="children" />

The Dedekind sums are computed straight from the definition and then checked against reciprocity,

$$s(h,k) + s(k,h) = -\tfrac14 + \tfrac{1}{12}\left(\tfrac{h}{k} + \tfrac{k}{h} + \tfrac{1}{hk}\right),$$

which is an independent enough statement to catch any slip in the sawtooth.

Things worth knowing

• The sign in $\mathrm{PSL}$ is real. Rebuilding a matrix from its $S/T$ word can hand back $-M$. That is not a bug; it is the $± I$ the group quotients out, and every comparison here is up to that sign.
• A word has to turn both ways. All-$L$ and all-$R$ words are parabolic — they fix a cusp rather than a geodesic — which is why the necklace count is always two short of the full one.
• Word length is not geodesic length. The symbolic period counts crossings of the fundamental domain; the trace measures the actual length. Sorting geodesics by one does not sort them by the other.
• $Φ$ is a quasimorphism, not a homomorphism. It is only almost additive, and it is only after the $\mathrm{sign}$ correction that it becomes an invariant of the closed orbit. Rotating a positive word cannot show the difference — the correction is constant on the positive cone — but conjugating by $S$ does.

What this connects to

• Numeral systems — the continued fraction here is a numeral system, and the Stern–Brocot path is its digit string.
• Binary necklaces and Lyndon words in the enumeratio catalogue count the closed geodesics exactly.
• Class numbers and Pell's equation — the form cycles above are the arithmetic face of the same objects, and FormClassNumber counts them.
• Lorenz knots and braids are the natural next step: Ghys's theorem says the modular knots are Lorenz knots, which are closures of positive braids, so the braid group is what turns these words into actual knot diagrams and invariants.