MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

As $\alpha$ and $\gamma$ range uniformly over $[0,1]$, what is the typical (e.g. median or root-mean-square) order of magnitude of $C_m (\alpha,\gamma)$ := $\sum_{1 \leq k \leq m} \left( {\rm frac}(k\alpha+\gamma) - \frac12 \right)$ where frac($x$) denotes the fractional part of $x$?

I'd settle for an answer in the case where $\gamma = 0$.

I know there are articles that address the question where $\alpha$ is fixed (going back to Hardy), but they don't immediately answer my question. Perhaps one could cobble together an answer using results about how the magnitude of $C_m (\alpha,\gamma)$ is bounded in terms of the continued fraction convergents for $\alpha$, along with results about how the convergents grow for a generic real number.

share|cite|improve this question
I'm confused by "I'd settle for an answer in the case where $\gamma = 0$ ." That doesn't sound like a "case," but a different (and not obviously easier) question. – David Feldman Feb 8 '11 at 7:07
This might be a very difficult question. $C_m(\alpha,0)$ is continuous, indeed linear with constant slope, except for discontinuities located on a Farey sequence. So the order of magnitude you ask for might be related to the discrepancy of Farey sequences, and versions of that question turn out equivalent to RH. It's not hard to express $C_m(\alpha,0)$ as a Fourier series, but the Fourier coefficients have number theoretic content. – David Feldman Feb 8 '11 at 23:22
David, I've posted a solution, so 1) the question is not all that difficult, or 2) my solution is wrong, or 3) I've settled the Riemann Hypothesis. RH, I think, is equivalent to sharp estimates of Farey discrepancy, but less-than-sharp estimates are not so hard to come by, and can still be useful. – Gerry Myerson Feb 9 '11 at 4:43
up vote 5 down vote accepted

I think I can show that $$\sum_{1 \leq h,k \leq N} \frac{GCD(h,k)^2}{hk}$$ grows linearly. But I get the constant is $$\sum_{ GCD(i,j)=1} \frac{1}{\max(i,j) i j}$$ This constant is incredibly close to $3$. (I am omitting the $1/12$, so my $3$ is your $0.25$.) My intuition is that they can't be equal, but they agree to a lot of digits, so I am not sure. See below for my computations.

UPDATE: This constant is $3$, due to an identity of Euler. See Marty's answer here. I'll leave the numeric work below for those might be curious how to approximate things like this.

Let's group the sum according to $GCD(h,k)$. So we have $$\sum_d \sum_{\substack{1 \leq h,k \leq N \\ GCD(h,k)=d}} \frac{d^2}{hk} = \sum_d \sum_{\substack{1 \leq i,j \leq N/d \\ GCD(i,j)=1}} \frac{d^2}{d^2 ij} = \sum_d \sum_{\substack{1 \leq i,j \leq N/d \\ GCD(i,j)=1}} \frac{1}{ij}$$ where $h=di$ and $k=dj$. Grouping on $(i,j)$, we have $$\sum_{\substack{1 \leq i,j \leq N \\ GCD(i,j)=1}} \frac{\lfloor N/\max(i,j) \rfloor}{ij} = N \sum_{\substack{1 \leq i,j \leq N \\ GCD(i,j)=1}} \frac{1}{\max(i,j) i j} + O \left( \sum_{\substack{1 \leq i,j \leq N \\ GCD(i,j)=1}} \frac{1}{i j} \right)$$ The error term is $O(\log N)^2$, so that's not the dominant term.

Once we check that the sum converges, this will show that your rate of growth is linear with that coefficient. We'll drop the $GCD(i,j)=1$ condition, since that just makes the sum smaller. $$\sum_{i,j} \frac{1}{\max(i,j) i j} = \sum_{n} \frac{1}{n^2} \left( 2 + \frac{2}{2} + \frac{2}{3} + \cdots + \frac{2}{n-1} + \frac{1}{n} \right) = \sum_{n} n^{-2} O(\log n).$$ Here $n=\max(i,j)$. The final sum converges by the integral test, so the original one does as well.

Now, what is the value of this sum? Notice that, if $(i,j) = (g i', g j')$ with $GCD(i', j')=1$, then $\max(i,j)i j = g^3 \max(i',j') i' j'$. So, if we sum over all pairs, instead of just the relatively prime ones, then we multiply by a factor of $\sum g^{-3} = \zeta(3)$. So we want to compute $$\sum_{1 \leq i,j} \frac{1}{\max(i,j) i j}$$ and, in particular, we want to know how it compares to $3 \zeta(3)$. As we showed above, we can simplify this sum to $$\sum_{n} \frac{1}{n^2} \left( 2 + \frac{2}{2} + \frac{2}{3} + \cdots + \frac{2}{n-1} + \frac{1}{n} \right).$$

Now, is this actually the same as $3 \zeta(3)$? I had Mathematica compute the sum of the first $10,000$ terms, using $20$ digit precision for all intermediate computations. If Mathematica can be trusted, the result is $3.6040133$. Now, $2+2/2+2/3+\cdots +2/(n-1) + 1/n = 2 \log n + 2 \gamma + O(1/n)$. So I approximated the rest of the sum by the integral $\int_{10000}^{\infty} 2 (\log t + \gamma) dt/t^2$. (Here $\gamma$ is the Euler gamma constant.) According to Mathematica, this integral is $0.0021575$. The error in approximating a decreasing sum by an integral is bounded by the first term, which is $1.8 \times 10^{-7}$. The error in approximating the harmonic number by a $\log$ should be something like $\int_{10000}^{\infty} dt/t^3 = 5 \times 10^{-9}$; I don't have the energy to turn this into a rigorous bound. So the sum should be $3.6040133 + 0.0021575 \pm 2 \times 10^{-7} = 3.6061708 \pm 2 \times 10^{-7}$. (That error lines up with the last digit given.)

And what is $3 \zeta(3)$? I kid you not, it is $3.6061707$, right in range! So they might be equal, but, if so, I can't see why.

UPDATE: OK, I went back and improved my approximations in two ways: (1) I replaced the Harmonic number $H_n$ by $\log n + \gamma + (1/2) n^{-1} - (1/12) n^{-2} + (1/120) n^{-4}$ and (2) I approximated the sum of the terms past $10000$ by the first few terms of the Euler-Macluarin approximation, up to the $B_4$ term. The result, doing my internal computations with $20$ digits of accuracy: 3.6061707094787828562. The numerical value of $3 \zeta(3)$: Exactly the same!

Something is going on here. If you don't mind, I'll ask a separate question about what.

share|cite|improve this answer

Let $C_m(\alpha)=\sum_{k=1}^m((k\alpha))$ where $((x))$ is $x-[x]-1/2$ if $x$ is not an integer, 0 if $x$ is an integer (so this agrees with your definition away from points where $k\alpha$ is an integer). Then we'll get at the root-mean-square magnitude of $C_m(\alpha)$ by $$\int_0^1C_m(\alpha)^2d\alpha=\int_0^1\left(\sum_1^m((k\alpha))\right)^2d\alpha=\sum_{h,k}\int_0^1((h\alpha))((k\alpha))d\alpha$$ Now go to page 25 of Rademacher and Grosswald, Dedekind Sums, where it is proved that this last integral is given by $c^2/(12hk)$, where $c=\gcd(h,k)$. Well, that should get you started.

UPDATE added by David Speyer: The rest of this answer refers to a different sum. See the comments below where this issue is discussed. Gerry, hope you don't mind me adding this, but it bugs me when there is wrong information in an (otherwise very good) answer.

EDIT: Not really fair to leave you with $\sum_{h,k}{\gcd(h,k)\over12hk}$ to evaluate, so I found a reference that does it.

Olivier Bordelles, Mean values of generalized gcd-sum and lcm-sum functions, J. Integer Seq. 10 (2007), no. 9, Article 07.9.2, 13 pp. (electronic), MR2346091 (2008g:11005), available at finds $$\sum_{n\le x}\sum_{j=1}^n{1\over{\rm lcm}(n,j)}={(\log x)^3\over6\zeta(2)}+C_1(\log x)^2+O(\log x)$$ where $C_1$ is some explicit constant that I can't be bothered to type out. Now $1/{\rm lcm}(h,k)=\gcd(h,k)/hk$, and $$\sum_{h=1}^m\sum_{k=1}^mf(h,k)=2\sum_{h\le m}\sum_{k=1}^hf(h,k)-\sum_{h=1}^mf(h,h)$$ for symmetric functions $f$, and it all comes together.

share|cite|improve this answer
Thanks, Gerry! But I don't see why the sums in your addendum are relevant to the sum from your original posting; $(\gcd(h,k))^2/(hk)$ is $hk / (\lcm(h,k))^2$, not $1 / \lcm(h,k)$. What am I missing? In any case, I used Mathematica to compute $\sum_{1 \leq h,k \leq m} (\gcd(h,k))^2 / (12hk)$ for various values of $m$, and I found that the values grow roughly linearly with $m$; indeed, they come surprisingly close to lying on a straight line. See . – James Propp Feb 9 '11 at 19:52
I screwed up, forgot it was $c^2$ in the numerator, not just $c$. It's worth checking whether the techniques in the Bordelles paper can be applied to the correct sum. – Gerry Myerson Feb 9 '11 at 22:40
It definitely appears from the data that $(\int_0^1 C_m (\alpha)^2 \ d\alpha)/m$ converges to a constant, and this constant appears to be about .25. Might it actually equal 1/4? One can argue heuristically that the integral should be on the order of $m$ since $C_m (\alpha)$ is a sum of $m$ terms that in some sense should be independent, but curiously, this heuristic doesn't give a coefficient at all close to .25! (Unless I'm making a mistake.) – James Propp Feb 10 '11 at 13:31

I looked at the literature just now, and I believe that R.R. Hall may have given a fairly complete answer to these questions. See his 1998 Crelle paper:

Regards, Sinai

share|cite|improve this answer
Thanks, Sinai! Could someone with (on-line or off-line) access to Journal fur die reine und angewandte Mathematik (Crelles Journal) summarize Hall's paper? (I can only view the first page.) – James Propp Feb 11 '11 at 17:22

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.