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.

  • $\begingroup$ 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. $\endgroup$ – Thomas Andrews May 28 '11 at 2:16

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,


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.

  • $\begingroup$ @Deinst: I am actually really curious, how did this problem come up? And what did you need the solution for? $\endgroup$ – Eric Naslund May 28 '11 at 1:04
  • $\begingroup$ This is an approximation to an approximation of an answer to a question of Jim Propp's (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. $\endgroup$ – deinst May 28 '11 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.