Arithmetic Properties of Apollonian Gaskets

Abstract

Definition of Apollonian gasket. Sphere packing, uniqueness of Apollonian gasket, examples of unbounded Apollonian tilings. Integral solutions to Descartes’s equation, groups freely generated by reflections.

Here we study some arithmetic questions arising when we consider the curvatures of disks which constitute an Apollonian gasket.

1 The Structure of $\overline{\mathbb{Q}}$

Here we want to investigate the set ${P}^{1}(\mathbb{Q}) = \overline{\mathbb{Q}}$ of rational numbers including the infinite point ∞. It can be called a rational circle.

First, think about how to parameterize $\overline{\mathbb{Q}}$. Every number $r \in \overline{\mathbb{Q}}$ can be written in the form $\frac{p} {q}$, where $p,\,q \in \mathbb{Z}$. But the map $\alpha :\, \mathbb{Z} \times \mathbb{Z}\rightarrow \overline{\mathbb{Q}},\alpha (p,\,q) = \frac{p} {q}$, is surjective but by no means injective.

We can impose the condition $\gcd (p,\,q) = 1$, that is, that p and q be relatively prime, or in other words, that the fraction $\frac{p} {q}$ be in lowest terms. Note, however, that the set X of relatively prime pairs (p, q) is itself a rather complicated object. The map $\alpha$, restricted to X, will be “two-to-one”: ${\alpha }^{-1}(r) = \pm (p,\,q)$. And there is no natural way to choose exactly one representative from every pair $\{(p,\,q),\;(-p,\,-q)\}$. However, for all $r = \frac{p} {q} \in \mathbb{Q}$, we can assume q > 0. But for q = 0, there is no preference between $p = \pm 1$.

Remark 6.1.

For the analytically minded reader, we can say that the construction here is similar to the Riemann surface of the function $f(w) = \sqrt{w}$. The map $z\mapsto w = {z}^{2}$ has two preimages for each $w \in {\mathbb{C}}^{\times }$, but this double-valued function does not admit an analytic (or even continuous) single-valued branch.

♡

Remark 6.2.

A remarkable way to label all positive rational numbers was discovered recently by Neil Calkin and Herbert Wilf (“Recounting the Rationals,” American Mathematical Monthly 107 (2000), pp. 360–363). Let $\mathbf{b}(n)$ be the number of partitions of an integer $n \geq 0$ into powers of 2, no power of 2 being used more than twice. Than the ratio $r_{n} = \frac{\mathbf{b}(n)} {\mathbf{b}(n+1)}$ takes every positive rational value exactly once! The initial piece of this numeration is given in the following table:

It is of interest to compare this numeration with the one given by Farey series (see below).

♡

Table 1

Table 2

Our next step in the study of $\overline{\mathbb{Q}}$ is the introduction of a natural distance between points. In the following, we tacitly assume that all rational numbers are written in lowest terms.

Let us call two numbers $r_{i} = \frac{p_{i}} {q_{i}}$, i = 1, 2, from $\overline{\mathbb{Q}}$ friendly if the following equivalent conditions are satisfied:

$$(a) \vert p_{1}q_{2} - p_{2}q_{1}\vert = 1,\qquad (b) \vert r_{1} - r_{2}\vert = \frac{1} {\vert q_{1}q_{2}\vert }.$$

(6.1.1)

It is worth mentioning that the friendship relation is not an equivalence relation:¹ every integer k is friendly to $\infty$, but only neighboring integers are friendly to each other.

Note that the group $\mathrm{PGL}(2,\, \mathbb{Z})$ acts on $\overline{\mathbb{Q}}$ by fractional linear transformations and that this action preserves the friendship relation. We can often use this fact in our study.

Lemma 6.1.

The group $\mathrm{PSL}(2,\, \mathbb{Z})$ acts simply transitively on the set of all ordered pairs of friendly numbers from $\overline{\mathbb{Q}}$ . The group $\mathrm{PGL}(2,\, \mathbb{Z})$ acts transitively but with a nontrivial stabilizer isomorphic to $\mathbb{Z}_{2}$.

Proof. Let $r_{i} = \frac{p_{i}} {q_{i}}$, i = 1, 2, be a pair of friendly numbers. Assume for definiteness that $p_{1}q_{2} - p_{2}q_{1} = 1$. We have to show that there is a unique element $\gamma$ of $\mathrm{PSL}(2,\, \mathbb{Z})$ that sends the standard friendly pair $(\infty,\,0)$ to the given pair $(r_{1},\,r_{2})$. Let $g = \left (\begin{array}{*{10}c} a&b\\ c &d\end{array} \right )$ be a representative of $\gamma$ in $\mathrm{SL}(2,\, \mathbb{Z})$. Then we have $\gamma (0) = \frac{b} {d},\quad \gamma (\infty ) = \frac{a} {c}$.

The conditions $\gamma (\infty ) = r_{1},\,\gamma (0) = r_{2}$ imply $(a,\,c) = k_{1} \cdot (p_{1},\,q_{1})$, $(b,\,d) = k_{2} \cdot (p_{2},\,q_{2})$. Therefore, $1 =\det g = ad - bc = k_{1}k_{2} \cdot {(p_{1}q_{2} - p_{2}q_{1})}^{-1} = k_{1}k_{2}$ and $k_{1} = k_{2} = \pm 1$. Hence $g = \pm \left (\begin{array}{*{10}c} p_{1} & p_{2} \\ q_{1} & q_{2} \end{array} \right )$ is determined up to sign and defines the unique element of $\mathrm{PSL}(2,\, \mathbb{Z})$.

The stabilizer of the pair $(0,\,\infty )$ in $\mathrm{PGL}(2,\, \mathbb{Z})$ consists of classes of matrices $\left (\begin{array}{*{10}c} 1& 0\\ 0 &\pm 1 \end{array} \right )$.

Exercise 6.1.

Describe all numbers that are (a) friendly to 0; (b) friendly to $\infty$; (c) friendly to 1.

We define a distance in the set $\overline{\mathbb{Q}}$ in the following way. Given two numbers r′ and r′, denote by $d(r^{\prime},\,r^{\prime\prime})$ the minimal $n \in \mathbb{Z}_{+}$ for which there exists a chain $r^{\prime} = r_{0},\,r_{1},\,\ldots,\,r_{n-1},\,r_{n} = r^{\prime\prime}$ such that for all k, the number r _k is friendly to $r_{k\pm 1}$ for $1 \leq k \leq n - 1$.

Exercise 6.2.

• (a) Show that $(\overline{\mathbb{Q}},\,d)$ is a discrete metric space on which the group $\mathrm{PGL}(2,\, \mathbb{Z})$ acts by isometries.

• (b) Find the stabilizer of the point $\infty$.

Answer.

(b) The group ${\rm Aff} (1,\, \mathbb{Z})$ of transformations $r\mapsto ar + b$, $a = \pm 1$, $b \in \mathbb{Z}$.

Exercise 6.3.

Compute the distances (a) $d(\infty,\,n);$ (b) d(0, n); (c) $d(0,\, \frac{5} {8})$.

Answer.

(a) 1; (b) 0 for n = 0, 1 for $n = \pm 1,$ 2 for | n |  > 1; (c) 4.

Exercise 6.4.

• (a) Show that for every $r^{\prime},\,r^{\prime\prime} \in \overline{\mathbb{Q}}$, the distance d(r′, r′) is finite.

• (b) Is the metric space $\overline{\mathbb{Q}}$ bounded?

Answer.

(a) See Theorem 6.1 below; (c) No.

Rather interesting and nontrivial problems arise when we consider the geometry of balls and spheres in $\overline{\mathbb{Q}}$. As usual, we define a ball with center a and radius r as the set $B_{r}(a) =\{ b \in \overline{\mathbb{Q}}\bigm |d(a,\,b) \leq r\}$. Analogously, a sphere is the set $S_{r}(a) =\{ b \in \overline{\mathbb{Q}}\bigm |d(a,\,b) = r\}$.

Theorem 6.1.

The ball $B_{n}(\infty )$ consists of all rational numbers that can be written as a continued fraction of length n, i.e., as

$$r=k_1+\cfrac{1}{k_2+\cfrac{1}{k_3+\cfrac{1}{\ddots k_{n-1}+\cfrac{1}{k_n}}}}$$

(6.1.2)

where k _i are arbitrary integers (positive or negative).

proof. First of all, let us show that for every r of the form (6.1.2), the distance $d(\infty,\,r)$ does not exceed n. We shall do this by induction on n.

For n = 1, the result follows from Exercise 6.3. Assume that the theorem is true for all continued fractions of length $\leq n - 1$ and consider a continued fraction of length n given by Eq. (6.1.2). Denote by r′ the number $\frac{1} {r-k_{1}}$. It is clear that r′ is represented by a continued fraction of length n − 1, whence $d(\infty,\,r^{\prime}) \leq n - 1$. Now, from the invariance of the distance with respect to shifts $r\mapsto r + k$, $k \in \mathbb{Z}$, and with respect to the inversion $r\mapsto {r}^{-1}$, we have

$$d(\infty,\,r) = d(\infty,\,r - k_{1}) = d(0,\,r^{\prime}) \leq d(0,\,\infty ) + d(\infty,\,r^{\prime}) \leq 1 + (n - 1) = n.$$

The first sign $\leq$ is just the triangle inequality, and the second follows from Exercise 6.3(a) and from the induction hypothesis.

The structure of spheres is a more delicate question. The “complexity” of a sphere grows with its radius.

For instance, consider $S_{1}(\infty ) = \mathbb{Z}$. It is a homogeneous space with respect to the group ${\rm Aff} (1,\, \mathbb{Z})$, which plays the role of the “group of rotations” around the infinite point; see Exercise 6.3(a).

The sphere $S_{2}(\infty )$ consists of points $k_{1} + \frac{1} {k_{2}}$, where $k_{1},\,k_{2} \in \mathbb{Z}$ and $k_{2}\neq 0,\,\pm 1$. Under the action of ${\rm Aff} (1,\, \mathbb{Z})$, it splits into infinitely many orbits $\Omega _{m}$, enumerated by the number $m = \vert k_{2}\vert \geq 2.$ The stabilizer of the point $k + \frac{1} {m} \in \Omega _{m}$ is trivial for m > 2 and contains one nonunit element $r\mapsto 2k + 1 - r$ for m = 2.

Problem 6.1.

Describe the orbits of ${\rm Aff} (1,\, \mathbb{Z})$ on the sphere $S_{k}(\infty )$ for k > 2.

2 Rational Parameterization of Circles

It is well known that a circle as a real algebraic manifold is rationally equivalent to a real projective line. This means that one can establish a bijection between a circle and a projective line using rational functions with rational coefficients.

For example, the circle x ² + y ² = 1 can be identified with a projective line with parameter t as follows:

$$x = \frac{{t}^{2} - 1} {{t}^{2} + 1},\qquad y = \frac{2t} {{t}^{2} + 1};\qquad t = \frac{y} {1 - x} = \frac{1 + x} {y}.$$

(6.2.1)

In particular, as t runs through all rational numbers (including $\infty$), the corresponding points (x, y) run through all rational points² of the circle.

From this fact one can derive the well-known description of primitive integral solutions to the equation x ² + y ² = z ². Namely, in every primitive solution, exactly one of the numbers x, y is even. Assume that it is y; then there are relatively prime numbers a, b such that

$$x\ =\ {a}^{2} - {b}^{2},\quad y\ =\ 2ab,\,\quad \pm z\ =\ {a}^{2} + {b}^{2}.$$

(6.2.2)

Analogously, the projectivization of the future light cone in ${\mathbb{R}}^{1,3}$ is nothing but the two-dimensional sphere, which is rationally equivalent to a completed two-dimensional plane. Therefore, all future light vectors $(t,\,x,\,y,\,z)$ with integral nonnegative coefficients can be written, up to positive proportionality, in the form

$$t = {k}^{2} + {l}^{2} + {m}^{2},\quad x = 2km,\quad y = 2lm,\quad z = \vert {k}^{2} + {l}^{2} - {m}^{2}\vert.$$

(6.2.3)

I do not know whether any integral solution can be written exactly in the form (6.2.3) for some integers $k,\,l,\,m$ with $\gcd (k,\,l,\,m) = 1$.³

Next, we take into account that on the real projective line $\overline{\mathbb{R}}$, there is a natural orientation. For our goals, it is convenient to define the orientation as a cyclic order for every three distinct points $x_{1},\,x_{2},\,x_{3} \in \overline{\mathbb{R}}$. Geometrically, this order means that going from x ₁ to x ₃ in the positive direction, we pass x ₂ on our way. We shall also use the expression “x ₂ is between x ₁ and x ₃.” Note that in this case, x ₂ is not between x ₃ and x ₁.

Exercise 6.5.

• (a) Show that in the case that all x ₁, x ₂, x ₃ are finite (i.e., $\neq \infty$), the statement “x ₂ is between x ₁ and x ₃” is equivalent to the inequality

  $$(x_{1} - x_{2})(x_{2} - x_{3})(x_{3} - x_{1}) > 0.$$

• (b) Which of the following are true?

• (i) 1 is between 0 and $\infty$;

• (ii) $\infty$ is between 0 and 1;

• (iii)  − 1 is between 0 and $\infty$.

We now introduce a new operation⁴ of “inserting” on $\overline{\mathbb{R}}$. It associates to an ordered pair of rational numbers (r ₁, r ₂) a third number, denoted by $r_{1} \downarrow r_{2}$, such that

$$r_{1} \downarrow r_{2}\, :=\, \frac{p_{1} + p_{2}} {q_{1} + q_{2}},\quad \text{if}\quad r_{1} = \frac{p_{1}} {q_{1}},\ r_{2} = \frac{p_{2}} {q_{2}},$$

(6.2.4)

where the signs of p _i and q _i are chosen such that $r_{1} \downarrow r_{2}$ is between r ₁ and r ₂.

Exercise 6.6.

Compute the following expressions:

(a) $0 \downarrow \infty$; (b) $\infty \downarrow 0$; (c) $\infty \downarrow -2$; (d) $1 \downarrow 2$; (e) $2 \downarrow 1$; (f) $\frac{1} {2} \downarrow -\frac{1} {3}$.

Answer.

(a) 1; (b) − 1; (c) − 3; (d) $\frac{3} {2}$; (e) $\infty$; (f) − 2.

The operation $\downarrow$ has especially nice properties when r ₁ and r ₂ are friendly numbers. In this case, the number $r_{1} \downarrow r_{2}$ is evidently friendly to both r ₁ and r ₂.

Exercise 6.7.

Show that for friendly numbers r ₁, r ₂, the number $r_{1} \downarrow r_{2}$ is the unique rational number between r ₁ and r ₂ (in the sense of the cyclic order described above) that is friendly to both of them.

These considerations lead to the notion of Farey series. The standard Farey series F ⁿ of rank n by definition consists of all rational numbers $0 < \frac{p} {q} < 1$ with $1 \leq q \leq n$ written in increasing order. The number of terms in F ⁿ is equal to $\sum _{k=2}^{n}\varphi (k)$, where $\varphi (k)$ is the Euler totient function, which counts the number of integers between 1 and k that are relatively prime to k. It is given by the formula

$$\varphi (n) = n \cdot \displaystyle\prod _{p\mid n}\left (1 - {p}^{-1}\right ),\quad \text{where p runs through all prime divisors of n}.$$

For example, the Farey series F ⁵ contains $\varphi (2) +\varphi (3) +\varphi (4) +\varphi (5) = 1 + 2 + 2 + 4 = 9$ terms:

$$\quad \frac{1} {5},\quad \frac{1} {4},\quad \frac{1} {3},\quad \frac{2} {5},\quad \frac{1} {2},\quad \frac{3} {5},\quad \frac{2} {3},\quad \frac{3} {4},\quad \frac{4} {5}.$$

We refer to [Nev49] for many known facts about standard Farey series, mentioning only some of them here.

Exercise 6.8.

Show that neighboring terms of Farey series are friendly numbers.

For our goals, we introduce a slightly different definition. Namely, the modified Farey series ${F}^{(n)} \subset \overline{\mathbb{R}}$ is defined as follows: The series ${F}^{(0)}$ consists of three numbers, 0, 1, and $\infty$, with given cyclic order. The series ${F}^{(n+1)}$, $n \geq 1$, is obtained from F ⁽ⁿ⁾ by inserting between every pair of consecutive numbers a, b the number $a \downarrow b$. So the modified Farey series F ⁽ⁿ⁾ consists of $3 \cdot {2}^{n}$ cyclic ordered numbers. We denote by $f_{k}^{(n)}$, $1 - {2}^{n} \leq k \leq {2}^{n+1}$, the kth member of F ⁽ⁿ⁾. In particular, for every $n \geq 0$, we have $f_{0}^{(n)} = 0$, $f_{{2}^{n}}^{(n)} = 1$, $f_{{2}^{n+1}}^{(n)} = \infty$.

The modified Farey series of rank $\leq 4$ are shown below:

$$\begin{array}{llllllllllllllllllllllllllllllll}\scriptstyle k:\quad &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle 0 &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle 1 &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle 2 \\ \scriptstyle f_{k}^{(0)}:\quad &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle \frac{0} {1} &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle \frac{1} {1} &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle \frac{1} {0} \\ \scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle \\ \scriptstyle k:\quad &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle -1 &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle 0 &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle 1 &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle 2 &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle 3 &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle 4 \\ \scriptstyle f_{k}^{(1)}:\quad &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle -\frac{1} {1} &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle \frac{0} {1} &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle \frac{1} {2} &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle \frac{1} {1} &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle \frac{2} {1} &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle \frac{1} {0} \\ \scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle \\ \scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle \\ \scriptstyle k:\quad &\scriptstyle &\scriptstyle -3 &\scriptstyle &\scriptstyle -2 &\scriptstyle &\scriptstyle -1 &\scriptstyle &\scriptstyle 0 &\scriptstyle &\scriptstyle 1 &\scriptstyle &\scriptstyle 2 &\scriptstyle &\scriptstyle 3 &\scriptstyle &\scriptstyle 4 &\scriptstyle &\scriptstyle 5 &\scriptstyle &\scriptstyle 6 &\scriptstyle &\scriptstyle 7 &\scriptstyle &\scriptstyle 8 \\ \scriptstyle f_{k}^{(2)}:\quad &\scriptstyle &\scriptstyle -\frac{2} {1} &\scriptstyle &\scriptstyle -\frac{1} {1} &\scriptstyle &\scriptstyle -\frac{1} {2} &\scriptstyle &\scriptstyle \frac{0} {1} &\scriptstyle &\scriptstyle \frac{1} {3} &\scriptstyle &\scriptstyle \frac{1} {2} &\scriptstyle &\scriptstyle \frac{2} {3} &\scriptstyle &\scriptstyle \frac{1} {1} &\scriptstyle &\scriptstyle \frac{3} {2} &\scriptstyle &\scriptstyle \frac{2} {1} &\scriptstyle &\scriptstyle \frac{3} {1} &\scriptstyle &\scriptstyle \frac{1} {0} \\ \scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle &\scriptstyle \\ \scriptstyle k:\quad &\scriptstyle -7 &\scriptstyle -6 &\scriptstyle -5 &\scriptstyle -4 &\scriptstyle -3 &\scriptstyle -2 &\scriptstyle -1 &\scriptstyle 0 &\scriptstyle 1 &\scriptstyle 2 &\scriptstyle 3 &\scriptstyle 4 &\scriptstyle 5 &\scriptstyle 6 &\scriptstyle 7 &\scriptstyle 8 &\scriptstyle 9 &\scriptstyle 10&\scriptstyle 11&\scriptstyle 12&\scriptstyle 13&\scriptstyle 14&\scriptstyle 15&\scriptstyle 16 \\ \scriptstyle f_{k}^{(3)}:\quad &\scriptstyle -\frac{3} {1} &\scriptstyle -\frac{2} {1} &\scriptstyle -\frac{3} {2} &\scriptstyle -\frac{1} {1} &\scriptstyle -\frac{2} {3} &\scriptstyle -\frac{1} {2} &\scriptstyle -\frac{1} {3} &\scriptstyle \frac{0} {1} &\scriptstyle \frac{1} {4} &\scriptstyle \frac{1} {3} &\scriptstyle \frac{2} {5} &\scriptstyle \frac{1} {2} &\scriptstyle \frac{3} {5} &\scriptstyle \frac{2} {3} &\scriptstyle \frac{3} {4} &\scriptstyle \frac{1} {1} &\scriptstyle \frac{4} {3} &\scriptstyle \frac{3} {2} &\scriptstyle \frac{5} {3} &\scriptstyle \frac{2} {1} &\scriptstyle \frac{5} {2} &\scriptstyle \frac{3} {1} &\scriptstyle \frac{4} {1} &\scriptstyle \frac{1} {0} \end{array}$$

To find an explicit formula for the numbers f _k ⁽ⁿ⁾ is a nontrivial problem. We shall discuss it below.

Exercise 6.9.

Show that $f_{k}^{(n)} = f_{2k}^{(n+1)}$, so that f _k ⁽ⁿ⁾ actually depends only on the dyadic number $r = \frac{k} {{2}^{n}}$. Sometimes, we shall write f _r instead of f _k ⁽ⁿ⁾.

To simplify the exposition, let us consider the part of F ⁽ⁿ⁾ between 0 and 1, i.e., members f _r with r between 0 and 1.

Note that if we change the procedure and insert between any two numbers a, b not $a \downarrow b$, but the arithmetic mean value $\frac{a+b} {2}$, we obtain at the nth step, the arithmetic progression with 2ⁿ + 1 terms starting with 0 and ending by 1. The kth member of this progression is $a_{k}^{(n)} = \frac{k} {{2}^{n}}$, or in the same notation as above, a _r  = r (Fig. 6.1).

Fig. 6.1

Graph of the function

Now we are prepared to define a remarkable function first introduced by Hermann Minkowski. He called it the “question mark function” and denoted it by ?(x); see Info E in Part I.

Theorem (Minkowski’s theorem). 

There exists a unique continuous and strictly increasing function $\boldsymbol{\text{?}} : [0,1] \rightarrow [0,1]$ such that

$$\boldsymbol{\text{?}}(a \downarrow b) = \frac{ {?(a)} + {?(b)}}{2}{for\,all\,friendly\,rational\,numbers}\quad a,b \in [0,1].$$

(6.2.5)

Sketch of proof.  The formula (6.2.5) and induction over n imply that if the desired function exists, it must have the property ? $\big(f_{k}^{(n)}\big) = a_{k}^{(n)}$. It follows that ? $\big(f_{r}\big) = r$ for all $r \in \mathbb{Z}[\frac{1} {2}]\bigcap [0,\,1]$.

On the other hand, we can define ? on $\mathbb{Z}[\frac{1} {2}]$ by the formula ?(f _r ) = r. Since both sets $\{f_{k}^{(n)}\}$ and $\{a_{k}^{(n)}\}$ are dense in [0, 1], the function can be extended uniquely as a monotone function from [0, 1] to [0, 1]. For example, we can put

$$ \boldsymbol{?}(x) =\lim _{n\rightarrow \infty }\boldsymbol{?}(x_{n}),$$

(6.2.6)

where $\{x_{n}\}$ is a monotone sequence of rational numbers converging to x.

The inverse function p to the question mark function solves the problem of computing f _k ⁽ⁿ⁾ posed above, since for every dyadic $r \in [0,\,1]$, we have f _r  = p(r).

On the set $\mathbb{Z}[\frac{1} {2}]\bigcap [0,\,1]$ of binary fractions, the function p(x) can be computed step by step using the property

$$p\left (\frac{2k + 1} {{2}^{n+1}} \right ) = p\left ( \frac{k} {{2}^{n}}\right ) \downarrow \ p\left (\frac{k + 1} {{2}^{n}} \right ),$$

(6.2.7)

which follows immediately from Eq. (6.2.5), and repeating the construction of the modified Farey series.

Theorem 6.2.

The function $p :={ \boldsymbol{\text{ ?}}}^{-1}$ has the following properties:

• 1. $(a)\ p(1 - x) = 1 - p(x);\quad (b)\ p(\frac{x} {2} ) = \frac{p(x)} {1+p(x)};\quad (c)\ p(\frac{1+x} {2} ) = \frac{1} {2-p(x)}.$

• 2. $(p)^{\prime}( \frac{k} {{2}^{n}}) = \infty$ for every n and $0 \leq k \leq {2}^{n}$.

• 3. For every rational nondyadic number $r \in [0,1]$ , the value p(r) is a quadratic irrationality, i.e., has a form $r_{1} + \sqrt{r}_{2}$ for some rational $r_{1},\,r_{2}$.

• 4. We have the following remarkable formula:

$$\displaystyle\begin{array}{rcl} p\left (\underbrace{\mathop0.0\ldots 00}\limits _{k_{1}}\underbrace{\mathop 11\ldots 11}\limits _{l_{1}}\ldots \underbrace{\mathop 00\ldots 00}\limits _{k_{n}}\underbrace{\mathop 11\ldots 11}\limits _{l_{n}}\ldots \right )= \frac{1} {k_{1}+ \frac{1} {l_{1}+ \frac{1} {{\ddots}k_{n}+ \frac{1} {l_{n}+\frac{1} {\ddots} }}}\ldots }& &\end{array}$$

(6.2.8)

where on the left-hand side, the binary system is used, while on the right-hand side, we use a continued fraction. The formula (6.2.8) works also for finite binary fractions. ⁵

Sketch of proof.  The relations 1(a)–(c) can be derived from the following useful fact.

Lemma 6.2.

Let $g = \left (\begin{array}{*{10}c} a&b\\ c &d \end{array} \right ) \in \mathrm{ GL}(2,\, \mathbb{Z})$ . Then the transformation of $\overline{\mathbb{Q}}$ given by

$$r\mapsto g \cdot r := \frac{ar + b} {cr + d}$$

commutes with the insertion operation $\downarrow$ , i.e.,

$$(g \cdot r_{1}) \downarrow (g \cdot r_{2})\ =\ g \cdot (r_{1} \downarrow r_{2}).$$

(6.2.9)

We leave the proof of this claim to the reader and make only two useful remarks, each of which could serve as the basis for a proof.

• 1. The transformations in question send friendly pairs to friendly pairs.

• 2. The group $\mathrm{GL}(2,\, \mathbb{Z})$ is generated by two elements:

$$g_{1} = \left (\begin{array}{*{10}c} 1&1\\ 0 &1 \end{array} \right ),\qquad g_{2} = \left (\begin{array}{*{10}c} 0&1\\ 1 &0 \end{array} \right ).$$

Now we prove relation 1(a). Consider the following diagram:

Relation 1(a) claims that it is commutative. To check this, choose a point $x \in [0,\,1]$ that is a dyadic fraction $r = \frac{k} {{2}^{n}} = a_{r}$. Then the vertical arrow sends this number to p(a _r ) = f _r , and the horizontal arrow sends f _r to f _1 − r (check this, consulting the table above).

On the other hand, the horizontal arrow sends r to 1 − r = a _1 − r , and then the vertical arrow sends a _1 − r to f _1 − r . Thus for every number of the form $\frac{k} {{2}^{n}}$, relation 1(a) holds. By continuity, it holds everywhere.

Consider relation 1(b). It is equivalent to the commutativity of the diagram

Here again we start with an element $r = a_{r} \in [0,\,1]$. The horizontal arrow sends it to a _r ∕ 2, and then the vertical arrow transforms it to f _r ∕ 2.

On the other hand, the vertical arrow sends a _r to f _r , and we have to show that the horizontal arrow transforms it to f _r ∕ 2. That is, we want to check the equality $\frac{f_{r}} {1+f_{r}} = f_{r/2}$. For this, we observe that the transformation $x\mapsto \frac{x} {1+x}$ maps the segment [0, 1] to the segment $[0,\, \frac{1} {2}]$. Since it belongs to $\mathrm{PGL}(2,\, \mathbb{Z})$, it transforms the part of Farey series between f ₀ and f ₁ to the par between f ₀ and f _1 ∕ 2. Then by induction on n, we check that it sends $f_{\frac{2k} {{2}^{n}} }$ to $f_{ \frac{k} {{2}^{n}} }$.

The relation 1(c) can be proved in the same way using the diagram

The point is that affine transformations respect half-sums, while the transformations from $\mathrm{PGL}(2,\, \mathbb{Z})$ respect the insertion operation.

I recommend that the reader formulate and prove some other properties of and p using other diagrams.

It is also useful to extend the definition of and p to the whole set $\overline{\mathbb{R}}$ by the formulas

$$p\left (\frac{1} {x}\right ) = \frac{1} {p(x)};\qquad p(-x) = -p(x).$$

(6.2.13)

We shall verify property 2 only at the point x = 0. The general case $x = \frac{k} {{2}^{n}}$ can be done similarly, or it can be reduced to the case x = 0 by 1(a)–1(c).

We have p(0) = 0, $p( \frac{1} {{2}^{n}}) = \frac{1} {n+1}$. So if $\frac{1} {{2}^{n}} \leq \Delta x \leq \frac{1} {{2}^{n-1}}$, we have $\frac{1} {n+1} \leq$ $\Delta p \leq \frac{1} {n}$.

Therefore, $\frac{{2}^{n-1}} {n+1} \leq \frac{\Delta p} {\Delta x} \leq \frac{{2}^{n}} {n}$ for $\frac{1} {{2}^{n}} \leq \Delta x \leq \frac{1} {{2}^{n-1}}$ and $p^{\prime}(0) = +\infty$.

Statement 3 follows from the formula (6.2.8). As for this formula, it can be proved for finite fractions by induction using the Farey series. Note that in the last section of Part I, we used Eq. (6.2.8) as a definition of the question mark function.

Remark 6.3.

Let us interpret the function $p :={ \text{?}}^{-1}$ as a distribution function for a probability measure $\mu$ on [0, 1]: the measure of an interval [a, b] is equal to p(b) − p(a). This measure is a weak limit⁶ of the sequence of discrete measures $\mu _{n}$, $n \geq 1$, concentrated on the subset ${F}^{(n)}$, so that the point $f_{k}^{(n)}$ has the mass $\frac{1} {{2}^{n}}$ for $1 \leq k \leq {2}^{n}$.

It is clear that the support of $\mu$ is the whole segment [0, 1] (i.e., the measure of every interval $(a,\,b) \subset [0,\,1]$ is positive). While for an ordinary Farey series, the measure defined in a similar way is uniform, in our case it is far from it. The detailed study of this measure is a very promising subject (see, e.g., [de Rha59]). ♡

Exercise 6.10.

Find the values of ?(x) and ′(x) at the point $x = \frac{1} {3}$.

Hint.

Using the relation $\frac{1} {2} -\frac{1} {4} + \frac{1} {8} - \frac{1} {16} + \frac{1} {32} - \frac{1} {64}+\ldots = \frac{1} {3}$, show that

$$?\left (\frac{1} {3} - \frac{1} {3 \cdot {4}^{n}}\right ) = \frac{\Phi _{2n-1}} {\Phi _{2n+1}},\qquad ?\left (\frac{1} {3} + \frac{2} {3 \cdot {4}^{n}}\right ) = \frac{\Phi _{2n}} {\Phi _{2n+2}},$$

where $\Phi _{n}$ is the nth Fibonacci number, given by the formula

$$\Phi _{n} = \frac{{\phi }^{n} - {(-\phi )}^{-n}} {\phi {+\phi }^{-1}},$$

where $\phi = \frac{\sqrt{5}+1} {2} \approx 1.618\ldots$ is the golden ratio.⁷

Answer.

? $\big(\frac{1} {3}\big) = \frac{3-\sqrt{5}} {2} ;\quad \text{?}^{\prime}\big(\frac{1} {3}\big) = 0$.

Problem 6.2.

Is it true that ? ′(x) = 0 for all rational numbers except a _k ⁽ⁿ⁾?

We can sum up the content of this section as follows: there is a monotone parameterization of all rational numbers in [0, 1] by the simpler set of all binary fractions in the same interval.

If we remove the restriction $r \in [0,\,1]$, we get a parameterization of $\overline{\mathbb{Q}}$ by $\overline{\mathbb{Z}[\frac{1} {2}]}$ that preserves the cyclic order on the circle introduced above.

Remark 6.4.

There is an interesting geometric interpretation of the Farey series and of the Minkowski question mark function. It was discovered by George de Rham [de Rha59].

Consider the square $[-1,\,1] \times [-1,\,1] \subset {\mathbb{R}}^{2}$. Let us divide every side into three equal parts and join neighboring division points. We get an octagon with equal angles but unequal sides. Repeat this procedure: divide every side of the octagon into three equal parts and join the neighboring division points. The result will be a convex polygon with 16 sides that is contained in the octagon. Proceeding in this way, we get a nested series of convex polygons $\Pi _{n}$, $n \geq 1$, with 2^n + 1 sides. The intersection of all these polygons is a convex domain D bounded by a C ²-smooth curve C (see Fig. 6.2). Note the following facts:

• (a) The center of each side of every $\Pi _{n}$ belongs to C. Let us enumerate those that belong to the upper half of C by the numbers $r_{k} = \frac{k} {{2}^{n}}$, $-{2}^{n} \leq k \leq {2}^{n}$.

• (b) Let the upper half of C be given by the equation y = f(x), $\vert x\vert \leq 1$. Let x _k be the x-coordinate of r _k . Then f′(x _k ) = f _{r k} , the member of the nth Farey series.

♡

Fig. 6.2

The de Rham curve

3 Nice Parameterizations of Disks Tangent to a Given Disk

Let A be an Apollonian gasket. Choose a disk D ∈ A corresponding to a Hermitian matrix M and consider those disks in A that are tangent to D.

The tangent points form a countable subset $T \subset \partial D$. We shall show later that one can parameterize points of T by rational numbers (including $\infty$) in such a way that the natural cyclic order on T, as a part of $\partial D$, corresponds to the cyclic order on $\overline{\mathbb{Q}}$, as a part of $\overline{\mathbb{R}}$.

Let D _r be the disk tangent to D at the point $t_{r} \in T$ and let M _r be the corresponding Hermitian matrix.

We say that a parameterization $r \rightarrow t_{r}$ of T by $\overline{\mathbb{Q}}$ is nice if it has the following properties:

• 1. If $r = \frac{p} {q}$ in lowest terms, then

  $$M_{r} = A{p}^{2} + 2Bpq + C{q}^{2} - M,\quad \text{where A,B,C are fixed Hermitian matrices.}$$

• 2. The disk D _r is tangent to D _r′ iff $r = \frac{p} {q}$ and $r^{\prime} = \frac{p^{\prime}} {q^{\prime}}$ are friendly, i.e., iff $\vert pq^{\prime} - p^{\prime}q\vert = 1$.

Of course, conditions 1 and 2 are very strong and contain all the information about tangent disks. Therefore, the next result is rather important.

Theorem 6.3.

Nice parameterizations exist and have the following additional property: Let $v_{0},\,v_{1},\,v_{2},\,v_{3}$ be vectors in ${\mathbb{R}}^{1,3}$ corresponding to matrices $A + C,\,B,\,A - C,\,M$ . Then the Gram matrix of their scalar products has the form

$$G =\Vert (v_{i},\,v_{j})\Vert = \left (\begin{array}{*{10}c} 1& 0 & 0 & 0\\ 0 &-1 & 0 & 0 \\ 0& 0 &-1& 0\\ 0 & 0 & 0 &-1 \end{array} \right ).$$

(6.3.1)

First main example: band gasket. :

Let $D =\{ w \in \mathbb{C}\bigm |\text{Im}\ w \leq 0\}$, $D_{\infty } =\{ w \in \mathbb{C}\bigm |\text{Im}\ w \geq 1\}$. Let $D_{0},\,D_{1}$ be the disks of unit diameter, tangent to D at points 0, 1 and to $D_{\infty }$ at points i, i + 1 (Fig. 6.3).

Fig. 6.3

Nice parameterization of a line in the band gasket

Then $\partial D = \overline{\mathbb{R}},\ T = \overline{\mathbb{Q}}$. The tautological parameterization of T is nice, with

$$M = \left (\begin{array}{*{10}c} 0 & i\\ -i &0\end{array} \right ),\ \ M_{\frac{p} {q} } = \left (\begin{array}{*{10}c} 2{p}^{2} & -2pq - i \\ -2pq + i& 2{q}^{2}\end{array} \right ),\ \ D_{\frac{p} {q} } :\ \biggm | w-\frac{2pq + i} {2{q}^{2}} \biggm |\ \leq \, \frac{1} {2{q}^{2}}.$$

Second main example: rectangular gasket. :

Let $D =\{ w \in \mathbb{C}\bigm |\vert w\vert \geq 1\}$ be the complement to the open unit disk, and let D ₀ be given by the condition $\vert w -\frac{1} {2}\vert \leq \frac{1} {2}$, $D_{\infty }$ by the condition $\vert w + \frac{1} {2}\vert \leq \frac{1} {2}$, and D ₁ by the condition $\vert w -\frac{2i} {3} \vert \leq \frac{1} {3}$.

Here $\partial D$ is the unit circle, and a nice parameterization is $t_{r} = \frac{p+iq} {p-iq}$, so that

$$M = \left (\begin{array}{*{10}c} -1&0\\ 0 &1 \end{array} \right ),\qquad M_{r} = \left (\begin{array}{*{10}c} {p}^{2} + {q}^{2} - 1& -{(p + iq)}^{2} \\ -{(p - iq)}^{2} & {p}^{2} + {q}^{2} + 1 \end{array} \right ),$$

$$D_{\frac{p} {q} } :\ \biggm | w - \frac{{(p + iq)}^{2}} {{p}^{2} + {q}^{2} + 1}\biggm |\ \leq \, \frac{1} {{p}^{2} + {q}^{2} + 1}.$$

Proof of Theorem 6.3. Let $D_{0},\,D_{1},\,D_{\infty }$ be any three disks from A that are tangent to D and to each other. We associate the labels 0, 1 and $\infty$ to the corresponding tangent points in $\partial D$ (Fig. 6.4).

Fig. 6.4

Nice parameterization of the outer circle in the rectangular gasket

Then, assuming that the theorem is true and the parameterization is nice, we can compute $A,\,B,\,C$ from the equations

$$M_{\infty } = A - M,\quad M_{0} = C - M,\quad M_{1} = A + 2B + C - M.$$

We get

$$A = M + M_{\infty },\quad C = M + M_{0},\quad B = \frac{1} {2}(M_{1} - M - M_{0} - M_{\infty }).$$

Then, using the property of matrices $M_{0},\,M_{1},\,M_{\infty }$, and M, we can check relation (6.3.1). From there, statement 2 of the theorem follows easily if we define M _r using statement 1.

Practically, a nice parameterization can be defined step by step. Assume that the disks D _r1 and D _r2 corresponding to friendly rational numbers r ₁ and r ₂ are already defined and are tangent to D and to each other. Then we associate to $r = r_{1} \downarrow r_{2}$, the disk tangent to D _r1, D _r2, and D.

In fact, there are two such disks and two possible values of $r = r_{1} \downarrow r_{2}$; the right choice is uniquely determined by the cyclic order.

Corollary.

The boundary curvature of the disk tangent to D at the point $r = \frac{p} {q}$ (in lowest terms) is given by a quadratic polynomial in p, q:

$$c(p,\,q)\ =\ \big (c_{\infty } + c\big) \cdot {p}^{2} +\big (c_{ 1} - c_{0} - c_{\infty }- c\big) \cdot pq +\big (c_{0} + c\big) \cdot {q}^{2} - c,$$

(6.3.2)

where c _i is the boundary curvature of the disk D _i.

In particular, if four mutually tangent disks in an Apollonian gasket A have integral boundary curvatures, then all disks from A have this property.

Exercise 6.11.

For the triangular Apollonian gasket, find the curvatures of the disks tangent to the outer disk.

Answer.

$c(p,q) = \frac{2({p}^{2}-pq+{q}^{2})} {\sqrt{3}} + 1$.

Exercise 6.12.

Describe the canonical parameterization for the outer circle of the triangular gasket.

Hint.

Label by $0,\,1,\,\infty$ the tangent points corresponding to the three maximal inner disks.

4 Integral Apollonian Gaskets

4.1 Basic Quadruples

There are many models of Apollonian gasket for which the curvatures of all circles are integers. We call them integral gaskets. For each such gasket, we can choose the quadruple of disks such that corresponding boundary curvatures form an integral quadruple $(c_{1} \geq c_{2} \geq c_{3} \geq c_{4})$ with minimal c ₁. Call it a basic quadruple.

Lemma 6.3.

For a basic quadruple, we have

$$c_{4} \leq 0,\qquad \vert c_{4}\vert < c_{3} < \left (1 + \frac{2} {\sqrt{3}}\right )\vert c_{4}\vert \approx 2.1547\ldots \cdot \vert c_{4}\vert.$$

Proof. Let D _i , $1 \leq i \leq 4$, be a quadruple of mutually tangent disks with curvatures c _i , $1 \leq i \leq 4$. The first inequality has already been proved (see Remark 4.2).

Consider now Descartes’s equation (4.1.3) as a quadratic equation in c ₁ with given $c_{2},\,c_{3},\,c_{4}$. Then we get

$$c_{1} = c_{2} + c_{3} + c_{4} \pm 2\sqrt{c_{2 } c_{3 } + c_{3 } c_{4 } + c_{4 } c_{2}}.$$

(6.4.1)

Since the initial quadruple is basic, we have to choose the minus sign in Eq. (6.4.1) (otherwise, we could replace c ₁ by a smaller quantity).

The inequality $c_{1} \geq c_{2}$ together with Eq. (6.4.1) gives $c_{3} + c_{4} \geq 2\sqrt{c_{2 } c_{3 } + c_{3 } c_{4 } + c_{4 } c_{2}}$, or ${(c_{3} - c_{4})}^{2} \geq 4c_{2}(c_{3} + c_{4}) \geq {(c_{3} + c_{4})}^{2}$. This can be true only when $c_{4} \leq 0$.

Finally, for nonpositive c ₄, we have ${(c_{3} - c_{4})}^{2} \geq 4c_{2}(c_{3} + c_{4}) \geq 4c_{3}(c_{3} + c_{4})$, or $3c_{3}^{2} + 6c_{3}c_{4} + c_{4}^{2} \leq 4c_{4}^{2}$. This gives $\sqrt{3}(c_{3} + c_{4}) \leq -2c_{4}$, hence $c_{3} \leq \frac{2+\sqrt{3}} {\sqrt{3}} \vert c_{4}\vert$.

Here is a list of basic quadruples of small sizes generating nonisomorphic gaskets in order of increasing | c ₄ | :

$c_{4} = 0\qquad \quad (1,\,1,\,0,\,0);$

$c_{4} = -1\qquad (3,\,2,\,2,\,-1);$

$c_{4} = -2\qquad (7,\,6,\,3,\,-2);$

$c_{4} = -3\qquad (13,\,12,\,4,\,-3),\qquad (8,\,8,\,5,\,-3);$

$c_{4} = -4\qquad (21,\,20,\,5,\,-4),\qquad (9,\,9,\,8,\,-4);$

$c_{4} = -5\qquad (31,\,30,\,6,\,-5),\qquad (18,\,18,\,7,\,-5);$

$c_{4} = -6\qquad (43,\,42,\,7,\,-6),\qquad (15,\,14,\,11,\,-6),\qquad (19,\,15,\,10,\,-6);$

$c_{4} = -7\qquad (57,\,56,\,8,\,-7),\qquad (20,\,17,\,12,\,-7),\qquad (32,\,32,\,9,\,-7);$

$c_{4} = -8\qquad (73,\,72,\,9,\,-8),\qquad (24,\,21,\,13,\,-8),\qquad (25,\,25,\,12,\,-8);$

$c_{4}=-9\quad (91,\,90,\,10,\,-9),\ (50,\,50,\,11,\,-9),\ (22,\,19,\,18,\,-9),$ $(27,\,26,\,14,\,-9);$

$c_{4} = -10$

$(111,\,110,\,11,\,-10),\ (39,\,35,\,14,\,-10),\ (27,\,23,\,18,\,-10);$

$c_{4} = -11$

$(133,\,132,\,12,\,-11),\ (72,\,72,\,13,\,-11),\ (37,\,36,\,16,\,-11),\ (28,\,24,\,21,\,-11)$.

Three general formulas:

$$\displaystyle\begin{array}{rcl} & c_{4} = -km\qquad ({k}^{2} + km + {m}^{2},\,k(k + m),\,m(k + m),\,-km)& \\ & c_{4} = 1 - 2k\qquad (2{k}^{2},\,2{k}^{2},\,2k + 1,\,1 - 2k) & \\ & c_{4} = -4k\qquad \big({(2k + 1)}^{2},\,{(2k + 1)}^{2},\,4(k + 1),\,-4k\big) & \\ \end{array}$$

The reader can find many other interesting facts about integral gaskets in [G03]. However, a description of all basic quadruples is still unknown.

Info I. The Möbius Inversion Formula

In number-theoretic computations, the Möbius inversion formula is frequently used. We explain here how it works.

Suppose we have a partially ordered set X with the property that for every element $x \in X$, there are only finitely many elements that are less than x. Let now f be any real- or complex-valued function on X. Define a new function F by the formula

$$F(x) =\displaystyle\sum _{y\leq x}f(y). $$

(I.1)

Proposition I.1.

There exists a unique function $\tilde{\mu }$ on $X \times X$ with the following properties:

• 1. $\tilde{\mu }(x,\,y) = 0$ unless $y \leq x$.

• 2. $\tilde{\mu }(x,\,x) = 1$.

• 3. If the functions f and F are related by Eq. (I.1), then

  $$f(x) =\displaystyle\sum _{y\leq x}\tilde{\mu }(x,\,y)F(y). $$

  (I.2)

In many applications, the set X is a semigroup of nonnegative elements in some partially ordered abelian group G, and the order relation is translation-invariant: y < x is equivalent to a + y < a + x for every $a \in G$. In this case, $\mu$ is also translation-invariant, $\tilde{\mu }(a + x,\,a + y) =\tilde{\mu } (x,\,y)$, and hence it can be written in the form $\mu (x - y)$, where $\mu$ is a function on G that is zero outside X. The inversion formula takes the form

$$f(x) =\displaystyle\sum _{y\leq x}\mu (x - y)F(y)\qquad \text{(M}\ddot{o}\text{bius inversion formula)}. $$

(I.3)

We leave the proofs for the interested reader and consider only some examples that we need in our book.

Example 1.

Let $G = \mathbb{Z}$ with the standard order. Then the formula (I.1) takes the form $F(n) =\sum _{m\leq n}f(m)$, and the inversion formula is $f(n) = F(n) - F(n - 1)$. We see that in this case, Proposition I.1 is true and the function $\mu$ is given by

$$\mu (n) = \left \{\begin{array}{@{}l@{\quad }l@{}} 1 \quad &\text{if }n = 0, \\ -1\quad &\text{if }n = 1, \\ 0 \quad &\text{otherwise}. \end{array} \right.$$

Example 2.

$G = G_{1} \times G_{2}$, and the order on G is the product of orders on G ₁ and on G ₂, i.e.,

$$(g_{1},\,g_{2}) > (0,\,0)\quad \Leftrightarrow \quad g_{1} > 0\quad \text{and}\quad g_{2} > 0.$$

Here the $\mu$-function for G is simply the product of the $\mu$-functions for G ₁ and G ₂.

Note that if G ₁ and G ₂ are ordered groups, the $G = G_{1} \times G_{2}$ is only partially ordered.

Example 3.

$G = {\mathbb{Q}}^{\times }$ is the multiplicative group of nonzero rational numbers. The partial order is defined as follows: $r_{1} \leq r_{2}$ if the number $\frac{r_{2}} {r_{1}}$ is an integer. So in this case, $X = \mathbb{Z}_{+}$ with the order relation m < n if $m\mid n$ (m is a divisor of n).

It is easy to see that this partially ordered group is the direct sum of a countable number of copies of $\mathbb{Z}$ with the usual order. Indeed, every element of G can be uniquely written in the form $r =\prod _{k\geq 1}p_{k}^{n_{k}}$, where p _k is the kth prime number, $n_{k} \in \mathbb{Z}$, and only finitely many of n _k are nonzero. The number r is an integer iff all n _k are nonnegative.

Therefore, the function $\mu$ is the product of infinitely many functions from Example 1. The exact definition is as follows.

Definition I.1.

$$\mu (n) = \left \{\begin{array}{@{}l@{\quad }l@{}} 1\&\text{if }n = 1,\quad \\ {(-1)}^{k} \quad &\text{if n is a product of k distinct primes,} \\ 0 \quad &\text{otherwise.} \end{array} \right.$$

Equation (I.3) in this case is the classical Möbius inversion formula

$$f(n) =\displaystyle\sum _{d\mid n}\mu (d)F\left (\frac{n} {d}\right ). $$

(I.4)

As an application, we derive here the formula for the Euler $\varphi$-function.

Let us classify the numbers $k \leq n$ according to the value of $d = \text{gcd}(k,\,n)$. It is clear that $\gcd (\frac{k} {d},\, \frac{n} {d}) = 1$. It follows that the number of those k for which $\gcd (k,\,n) = d$ is equal to $\varphi (\frac{n} {d})$. We have obtained the identity

$$n =\displaystyle\sum _{d\mid n}\varphi \left (\frac{n} {d}\right ).$$

Applying the Möbius inversion formula, we get

$$\varphi (n) =\displaystyle\sum _{d\mid n}\mu (d) \cdot \frac{n} {d},\qquad \text{or}\qquad \frac{\varphi (n)} {n} =\displaystyle\sum _{d\mid n}\frac{\mu (d)} {d}. $$

(I.5)

♢

1 Some Computations

A well-known unsolved problem is to compute the Hausdorff dimension of the Apollonian gasket and the Hausdorff measure of its different modifications (e.g., spherical or triangular gaskets). We know the answer to the first question to a high degree of accuracy: in [MC03], it is shown that the Hausdorff dimension of the Apollonian gasket is $d = 1.308535???\ldots$. However, we have no idea about the nature of this number. For example, is it irrational? Can it be expressed in terms of some logarithms as for the Cantor set or Sierpiński gasket? Has it any interesting arithmetic properties?

Another interesting problem is to compute the total area of the disks in some Apollonian gasket that are tangent to a given disk D, e.g., to the outer disk in the rectangular or triangular gasket.

We start, however, with a slightly easier problem. Consider the first main example of the band gasket above. We want to compute the total area of the disks in the band gasket that are tangent to the real axis at the rational points of the segment [0, 1]. A more natural question, one with a simpler answer, is to compute the area of the part of the unit square with vertices 0, 1, 1 + i, i covered by the disks tangent to the lower side of the square.

We know that the diameter of the disk with tangent point $\frac{m} {n} \in [0,\,1]$ is $\frac{1} {{n}^{2}}$. Hence its area is $\frac{\pi }{4{n}^{4}}$. There are $\varphi (n)$ disks of this size. So for the area in question, we have the expression

$$A\quad = \quad \frac{\pi } {4} \cdot \displaystyle\sum _{n\geq 1}\frac{\varphi (n)} {{n}^{4}}.$$

(6.4.2)

This number can be expressed through the values of the Riemann $\zeta$-function at the points 3 and 4.

Let us use the formula for $\varphi (n)$ obtained in Info I. The formula (6.4.2) takes the form

$$A\quad = \quad \frac{\pi } {4} \cdot \displaystyle\sum _{n\geq 1}\displaystyle\sum _{d\mid n} \frac{\mu (d)} {d{n}^{3}}.$$

We denote $\frac{n} {d}$ by m and sum over d and m. We get

$$A\quad = \quad \frac{\pi } {4} \cdot \displaystyle\sum _{d\geq 1}\displaystyle\sum _{m\geq 1} \frac{\mu (d)} {{m}^{3}{d}^{4}}\quad = \quad \frac{\pi } {4} \cdot \displaystyle\sum _{m\geq 1} \frac{1} {{m}^{3}} \cdot \displaystyle\sum _{d\geq 1}\frac{\mu (d)} {{d}^{4}}.$$

The sum $\sum _{m\geq 1} \frac{1} {{m}^{3}}$ is, by definition, the value $\zeta (3)$. On the other hand, the sum $\sum _{d\geq 1}\frac{\mu (d)} {{d}^{4}}$ can be written as

$$\displaystyle\sum _{k\geq 0}\ {(-1)}^{k} \cdot \displaystyle\sum _{ 1\leq i_{1}<i_{2}<\ldots <i_{k}}{(p_{i_{1}}p_{i_{2}}\cdots p_{i_{k}})}^{-4}\ =\ \displaystyle\prod _{ i\geq 1}\left (1 - \frac{1} {p_{i}^{4}}\right ) = \frac{1} {\displaystyle\sum _{n\geq 1} \frac{1} {{n}^{4}} } = \frac{1} {\zeta (4)}.$$

Finally, we get

$$A\ =\ \frac{\pi } {4} \cdot \frac{\zeta (3)} {\zeta (4)}\ =\ \frac{45\zeta (3)} {{2\pi }^{3}} \approx 0.872284.$$

The total area of the disks tangent to the outer disk of the rectangular gasket is equal to

$$\frac{\pi } {2} \cdot \displaystyle\sum _{\gcd (p,q)=1} \frac{1} {{({p}^{2} + {q}^{2} + 1)}^{2}}.$$

It can be expressed in terms of the $\zeta$-function related to the Gaussian field $\mathbb{Q}(i)$.

Exercise 6.13.

Let $\Sigma _{m}$ denote the sum $\sum _{{\mathbb{Z}}^{2}\setminus \{(0,0)\}} \frac{1} {{({k}^{2}+{l}^{2})}^{m}}$. Show that

$$\displaystyle\sum _{\gcd \,(p,q)=1} \frac{1} {{({p}^{2} + {q}^{2})}^{m}} = \frac{\Sigma _{m}} {\zeta (2m)}$$

(6.4.2)

and

$$\displaystyle\sum _{\gcd \,(p,q)=1} \frac{1} {{({p}^{2} + {q}^{2} + 1)}^{2}} =\displaystyle\sum _{ m=1}^{\infty }{(-1)}^{m-1}\frac{m \cdot \Sigma _{m+1}} {\zeta (2m + 2)}.$$

(6.4.3)