13
$\begingroup$

A Farey sequence of order $n$ is a list of the rational numbers between 0 and 1 inclusive whose denominator is less than or equal to $n$.

For example $F_6= \{0,1/6,1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,5/6,1\}$.

The consecutive differences of $F_6$ are $S_6=\{1/6, 1/30, 1/20, 1/12, 1/15, 1/10, 1/10, 1/15, 1/12, 1/20, 1/30, 1/6\}$,

and the sum of squares of the elements of $S_6$, $\displaystyle T_6=\sum_{i\in S_6}i^2 = \frac{19}{180}$.

It appears that the sum of squares $T_n$ shrinks a bit faster than $O(ln(n)/n^2)$ but I cannot see how to prove it. I'd also be interested in considering higher powers than the square, and the differences between every other element, or every third, etc.

  • 0
    Note that you can characterize the differences as all of the form $\frac{1}{ab}$ where $(a,b)=1$ and a+b>n, and each of these values occurs twice.2011-05-28

1 Answers 1

14

Actually, we can do it for higher powers as well. Let $F_k (N)$ denote the sum of the $k^{th}$ powers of the differences in the Farey sequence. Then it is easy to see that $F_0(N)=\sum_{n=1}^N \phi(n)\sim \frac{3N^2}{\pi^2}$ and $F_1(N)=1.$ It seems you are looking for $F_2 (N)$, and, you are correct that the asymptotic is $\frac{\log N}{N^2}$. More precisely we have: $F_{2}(N)=\frac{12}{\pi^{2}N^{2}}\left(\log N+\frac{1}{2}+\gamma-\frac{\zeta'(2)}{\zeta(2)}\right)+O\left(\frac{\log^{2}N}{N^{3}}\right).$

For $k\geq 3$, we the log disappears, and we have $F_{k}(N)=\frac{2\zeta(k-1)}{\zeta(k)N^{k}}+O\left(\frac{\log N}{N^{k+1}}\right).$ (The error can be improved by a log when $k\geq 4$)

Hope that helps,

References:

R.R. Hall's Paper: A Note on Farey Sequences.

Remark: I strongly suggest reading R.R. Hall's paper since it has the complete proofs, and covers other cases such as negative powers.

  • 0
    This is an approximation to an approximation of an answer to$a$question of Jim Propp's (http://jamespropp.org/SeeSlope.nb) on given the nearest integer to $ax+b$ for $x$ from 1 to n and $a$ and $b$ uniform(0,1) R.V.s what is the best expected error for an estimate of $a$. The higher exponents will give higher moments of the estimation error.2011-05-28