Exercise 6.1.2 (Number and sum of Farey fractions of order $n$)

Proof.

(a)

Let $N$ be the number of Farey fractions $a∕b$ of order $n$ satisfying the inequalities $0\le a∕b\le 1$, and $$A=\{(a,b)\in \mathbb{N}\times \mathbb{N}\mid 0\le a\le b\le n,a\wedge b=1\},$$

so that $N=\mathrm{Card}A$.

We define for every $j\in [[1,n]]$,

$$\begin{array}{llll}\hfill A_j& =\{(a,b)\in \mathbb{N}\times \mathbb{N}\mid 0\le a\le b\le n,a\wedge b=1,b=j\},& \hfill & \\ \hfill B_j& =\{a\in \mathbb{N}\mid 0\le a\le j,a\wedge j=1\}& \hfill & \end{array}$$

Then

$$A=\underset{j=1}{\overset{n}{\bigcup }}{A}_j\text{(disjoint union)},$$

and

$$\phi \{\begin{array}{ccc}\hfill A_j\hfill & \hfill \to \hfill & B_j\hfill \\ \hfill (a,j)\hfill & \hfill \mapsto \hfill & a\hfill \end{array}$$

is bijective, with reciprocal $\psi :B_j\to A_j$ defined by $a\mapsto (a,j)$.

Therefore

$$N=|A|=\underset{j=1}{\overset{n}{\sum }}|B_j|.$$

Since $0\wedge 1=1\wedge 1=1$, then $B_1=\{0,1\}$, thus $B_1=2=1+\varphi (1)$.

If $j\ge 2$, $0\wedge j=j\ne 1$, thus

$$\begin{array}{llll}\hfill B_j& =\{a\in \mathbb{N}\mid 0\le a\le j,a\wedge j=1\}& \hfill & \\ \hfill & =\{a\in \mathbb{N}\mid 1\le a\le j,a\wedge j=1\}& \hfill & \end{array}$$

By definition of $\varphi$,

$$\varphi (j)=\mathrm{Card}\{a\in \mathbb{N}\mid 1\le a\le j,a\wedge j=1\}(j\ge 1),$$

so $|B_j|=\varphi (j)$ if $j\ge 2$.

$$N=1+\underset{j=1}{\overset{n}{\sum }}\varphi (j).$$

The number of Farey fractions $a∕b$ of order $n$ satisfying the inequalities $0\le a∕b\le 1$ is $N=1+{\sum <!--\; FUNCTION\; APPLICATION\; -->}_{j=1}^n\varphi (j)$

(b)

The sum of Farey fractions $a∕b$ of order $n$ satisfying the inequalities $0\le a∕b\le 1$ is $$N^{\prime }=\underset{(a,b)\in A}{\sum }\frac{a}{b}.$$

Consider the map

$$\chi \{\begin{array}{ccc}\hfill A\hfill & \hfill \to \hfill & A\hfill \\ \hfill (a,b)\hfill & \hfill \mapsto \hfill & (b-a,b)\hfill \end{array}$$

For every $(a,b)\in A$, $0\le a\le b\le n$, thus $0\le b-a\le b\le n$, and $(b-a)\wedge b=1$, thus $(b-a,b)\in A$, and $\chi$ is well defined.

Note that $(\chi \circ \chi )(a,b)=\chi (b-a,b)=(b-(b-a),b)=(a,b)$ for every $(a,b)\in A$, thus $\chi \circ \chi =1_A$, so $\chi$ is an involution of $A$. A fortiori, $\chi$ is bijective. (This shows that the Farey sequence is symmetric.)

Therefore the changement of indices $(a,b)\mapsto \chi (a,b)=(b-a,b)$ gives

$$N^{\prime }=\underset{(a,b)\in A}{\sum }\frac{b-a}{b}.$$

Hence

$$\begin{array}{llll}\hfill 2N^{\prime }& =\underset{(a,b)\in A}{\sum }\frac{a}{b}+\underset{(a,b)\in A}{\sum }\frac{b-a}{b}& \hfill & \\ \hfill & =\underset{(a,b)\in A}{\sum }\left(\frac{a}{b}+\frac{b-a}{b}\right)& \hfill & \\ \hfill & =\underset{(a,b)\in A}{\sum }1& \hfill & \\ \hfill & =\mathrm{Card}A& \hfill & \\ \hfill & =1+\underset{j=1}{\overset{n}{\sum }}\varphi (j).& \hfill & \end{array}$$

Therefore

$$N^{\prime }=\frac{1}{2}\left(1+\underset{j=1}{\overset{n}{\sum }}\varphi (j)\right)$$