sums of fractional parts of linear functions of n

Question

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.

Answer 1

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.

Answer 2

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 https://cs.uwaterloo.ca/journals/JIS/VOL10/Bordelles2/bordelles61.pdf 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.

Answer 3

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:

http://www.reference-global.com/doi/abs/10.1515/crll.1998.035

Hall, R. R., Linear Diophantine equations and Franel integrals, J. Reine Angew. Math. 496, 93-105 (1998). ZBL0886.11012.

Regards, Sinai