Gaps between Farey fractions

Consider the rationals (fractions) between $0$ and $1$ with denominator bounded by $Q$ . That is

$\displaystyle \left\{ \frac{a}{q} :\quad (a, q)=1, ~0 \le a \le q \right\}$

These fractions are called Farey fractions of level $Q$ and we denote them by $\mathcal F_Q.$

$\displaystyle \mathcal F_{1}=\left\{\frac{0}{1}, \frac{1}{1}\right\}$
$\displaystyle \mathcal F_{2}=\left\{\frac{0}{1}, \frac{1}{2}, \frac{1}{1}\right\}$
$\displaystyle \mathcal F_{3}=\left\{\frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1}\right\}$
$\displaystyle \mathcal F_{4}=\left\{\frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1}\right\}$
$\displaystyle \mathcal F_{5}=\left\{\frac{0}{1}, \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}, \frac{1}{1}\right\}$
$\displaystyle \mathcal F_{6}=\left\{\frac{0}{1}, \frac{1}{6}, \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}, \frac{5}{6}, \frac{1}{1}\right\}$
$\displaystyle \mathcal F_{7}=\left\{\frac{0}{1}, \frac{1}{7}, \frac{1}{6}, \frac{1}{5}, \frac{1}{4}, \frac{2}{7}, \frac{1}{3}, \frac{2}{5}, \frac{3}{7}, \frac{1}{2}, \frac{4}{7}, \frac{3}{5}, \frac{2}{3}, \frac{5}{7}, \frac{3}{4}, \frac{4}{5}, \frac{5}{6}, \frac{6}{7}, \frac{1}{1}\right\}$
$\displaystyle \mathcal F_{8}=\left\{\frac{0}{1}, \frac{1}{8}, \frac{1}{7}, \frac{1}{6}, \frac{1}{5}, \frac{1}{4}, \frac{2}{7}, \frac{1}{3}, \frac{3}{8}, \frac{2}{5}, \frac{3}{7}, \frac{1}{2}, \frac{4}{7}, \frac{3}{5}, \frac{5}{8}, \frac{2}{3}, \frac{5}{7}, \frac{3}{4}, \frac{4}{5}, \frac{5}{6}, \frac{6}{7}, \frac{7}{8}, \frac{1}{1}\right\}$

The number of fractions is

$\displaystyle \left|\mathcal F_{Q}\right|=1+\sum_{q=1}^{Q} \varphi(q) = \frac{3Q^2}{\pi^2} +O(Q\log Q)$

Neighbours: Any two neighbours $\frac{a}{q}> \frac{a'}{q'}$ have the property that

$\displaystyle aq'-a'q=1 \implies \frac{a}{q} -\frac{a'}{q'} =\frac{1}{qq'}$

In fact, two fractions are adjacent to each other in some Farey sequence $\mathcal F_n$ iff

$\displaystyle aq'-a'q=1$ .

In particular they are adjacent in $\mathcal F_Q$ if and only if we have

$\displaystyle q+q^{\prime}>Q, \text{ } a^{\prime} q-a q^{\prime}=1$

To see these conditions, observe the mediant property

$\displaystyle \frac{a}{b} <\frac{a+c}{b+d} < \frac{c}{d}$ ,

and the fact the we can construct all the Farey fraction starting from $\frac{0}{1}, \frac{1}{1}$ by adding the mediant points successively — We can see this inductively, any fraction $\frac{r}{s}$ between two neighbours $\frac{a}{b} <\frac{c}{d}$ in $\mathcal F_{n-1}$ will have denominator $r$ at least $b+d$ .

$\displaystyle \frac{1}{bd}=\frac{a}{b} -\frac{c}{d} = \frac{a}{b} -\frac{r}{s} + \frac{r}{s} -\frac{c}{d} \ge \frac{1}{bs}+\frac{1}{sd} \implies s\ge b+d$

(We used inductive hypothesis to get $ad-bc=1 .$ )

Therefore the mediant is the first “new” fraction that’s going to be added. We can check that the determinant condition between the neighbours is preserved as we add the mediants,

$\displaystyle ad-bc =1 \implies (b+d)a-b(a+c)=(a+c)d-(b+d)c=1$ .

Finally the condition $q+q'>Q$ for a neighbours in a fixed level because if the sum is smaller, the mediant is in between them and also lies in $\mathcal F_Q$ .

If $\text{ }\frac{a_1}{q_1}<\frac{a_2}{q_2} <\frac{a_3}{q_3}$ are consecutive fractions in a fixed level $Q$ we have the following relation

$\displaystyle q_{3}=\left[\frac{Q+q_{1}}{q_{2}}\right] q_{2}-q_{1}$

This can be rephrased in terms of the variables $\frac{q_i}{Q}$ as

$\displaystyle \left(\frac{q_{j+1}}{Q}, \frac{q_{j+2}}{Q}\right)=T\left(\frac{q_{j}}{Q}, \frac{q_{j+1}}{Q}\right)$

where

$\displaystyle T(x, y)=\left(y,\left[\frac{1+x}{y}\right] y-x\right)$

So by iterating we can write

$\displaystyle \left(\frac{q_{j+1}}{Q}, \frac{q_{j+2}}{Q}\right)=T^{j}\left(\frac{q_{1}}{Q}, \frac{q_{2}}{Q}\right) =T^{j}\left(\frac{1}{Q}, 1\right)$ .

Note that $T$ is a transformation defined on the Farey triangle

$\displaystyle \mathcal{T}=\left\{(x, y) \in \mathbb{R}^{2}: 0\le x \le y \le 1, x+y >1 \right\}$

by the properties of neighbouring fractions.

Distribution/ Statistics:

How is the sequence distributed? What about the gaps and other statistics?

We can see that the minimum gap is

$\displaystyle \frac{1}{Q-1}-\frac{1}{Q}=\frac{1}{Q(Q-1)}$

and the maximum gap is

$\displaystyle \frac{1}{Q}-0 =1-\frac{Q-1}{Q} =\frac{1}{Q}$ .

But the average gap is $\displaystyle \frac{1}{|\mathcal F_Q|} \sim \frac{\pi^2}{3Q^2}$ .

Although the gaps are not the same and there is a lot of variation, the sequence is uniformly distributed as $Q\to \infty$ , that is every interval has approximately proportional number of fractions. That is

$\displaystyle \frac{1}{|F_Q|}\left|\left\{ \frac{a}{q} \in \mathcal F_{Q} : \alpha < \frac{a}{q} <\beta\right\}\right| \sim \beta-\alpha$

To prove this note that that $\alpha < \frac{a}{q} <\beta \iff \alpha q< a<\beta q$ , so count the integer points in the interval $[\alpha q, \beta q]$ which are coprime to $q$ , which amount to approximately

$\displaystyle \frac{\varphi(q)}{q} \cdot q(\beta-\alpha)$

and then summing over $q$ gives $~(\beta-\alpha) \sum_{q=1}^{Q} \varphi(q) ~(\beta-\alpha)|\mathcal F_{Q}|$

The error terms are governed by the Weyl sums $\displaystyle \sum_{r \in \mathcal{F}_{Q}} {e}^{2 \pi i h r}$ , which by Mobius inversion (to remove/detect the condition $(a, q)=1$ ) are given by

$\displaystyle \sum_{r \in \mathcal{F}_{Q}} {e}^{2 \pi h r} =\sum_{q\le Q} \sum_{a=1}^{q}\sum_{d|(a, q)} \mu(d) {e}^{\frac{2 \pi i ah}{q} } = \sum_{d}\mu(d) \sum_{q\le Q, d|q} \sum_{q|d \mid h} \frac{q}{d} =\sum_{d_1|h} d_1 \sum_{d \le Q/d_1} \mu(d)$

Thus the problem of finding the best error terms is related to bounding the Mobius sums $\displaystyle \sum_{d \le Q/d_1 } \mu(d)$ .

Anyway note that equidistribution is a statement about of coarse scale behaviour– we take intervals of fixed size. If we take very small intervals, the error terms may dominate and the interval might have a lot more or lot less fractions. For instance $[(0, \frac{1}{Q}])$ has zero points, but the uniform distribution predicts $(1/Q)|\mathcal F_Q| \sim \frac{3Q}{\pi^2}$ for the count. The smallest scale on which the uniform distribution is valid is related to the error terms and rate of convergence of the above equidistribution statement and as we saw is related to finding cancellation in the Mobius sums- this is extremely hard and basically the Riemann hypothesis problem.

We can ask how the spacings are distributed. In fact, we want to understand the distribution of $(q, q')$ of a the denominators of adjacent fractions. The scaled denominators $\frac{q}{Q}, \frac{q'}{Q}$ are uniformly distributed in the Farey triangle

$\displaystyle \mathcal{T}= \mathcal{T}=\left\{(x, y) \in \mathbb{R}^{2}: 0 \le x \le y \le 1, x+y \ge 1 \right\}$

Thus the spacings $\frac{1}{qq'}$ are distributed according to the distribution of $\frac{1}{xy}$ on the Farey triangle. In general any statistic $f(q/Q, q'/Q)$ can be seen the statistics of $f(x, y)$ on the Farey triangle.

Example: The average gap $\frac{1}{|\mathcal F_Q|}\sum \frac{1}{qq'}= \frac{1}{|\mathcal F_Q|}$ because sum of gaps is the length of the interval $[0, 1]$ , but the uniform distribution implies that the average has to be

$\frac{1}{\text{Area}(\mathcal T)}\int_{\mathcal T}\frac{1}{Q^2xy} dA.$

Computing the integral we get $\frac{\pi^2}{3Q^2}$ and this equals $\frac{1}{|\mathcal F_Q|}$ for large $Q$ .

The expressions for the spacing distribution where computed by Hall. Let $\sigma_Q(t)$ be the fraction of spacings which are at least $\frac{t}{Q^2}$ , then we have

$\displaystyle \sigma_Q(t) \sim \frac{\text{Area} \left\{ (x,y) : \frac{1}{xy}>t \right\}}{\text{Area}(\mathcal T)} =\sigma(t)$

This distribution $\sigma(t)$ is given by density $\Delta(t)$ ,

$\displaystyle \sigma(t) =\int_{t}^{\infty}\Delta(t) ~~dt$ with

$\displaystyle \Delta(t)= \begin{cases}0 & \text { if } t \in\left[0, 1\right], \\ \frac{2}{ t^{2}} \log t & \text { if } t \in\left[1, 4\right] \\ \frac{4}{t^{2}} \log \frac{t}{2}\left(1-\sqrt{1-\frac{4}{t}}\right) & \text { if } t \in\left[4, \infty\right)\end{cases}$

This allows us to see that the most common gap is near $\frac{\sqrt e}{Q^2}.$

If we want distribution of $\frac{q_1}{Q}, \frac{q_2}{Q}, \frac{q_k}{Q}$ for $k$ consecutive fraction, using the transformation $T$ that relates adjacent denominators, the distribution is given by the distribution of $T^{j}(x,y)$ for $(x,y)$ a random point in the Farey triangle. Once we have this we can compute higher level spacing distributions.

Both these properties follow from the uniform distribution, but the error terms have a lot more arithmetic- for instance for $\frac{a}{q} <\frac{a_1}{q_1}$ , we need to understand the distribution of quantities like $\bar q_1 \mod q$ .

Share this:

Related

Leave a comment Cancel reply