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.

$\endgroup$
1
  • $\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$ May 28, 2011 at 2:16

1 Answer 1

14
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @Deinst: I am actually really curious, how did this problem come up? And what did you need the solution for? $\endgroup$ May 28, 2011 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, 2011 at 1:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .