Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. – Thomas Andrews May 28 '11 at 2:16
up vote 12 down vote accepted

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.

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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