A sum of fractional parts.

Question

I am looking to evaluate the sum $$\sum_{1\leq k\leq mn}\left\{ \frac{k}{m}\right\} \left\{ \frac{k}{n}\right\} .$$

Using matlab, and experimenting around, it seems to be $\frac{(m-1)(n-1)}{4}$ when $m,n$ are relatively prime. How can we prove this, and what about the case where they are not relatively prime?

Conjecture: Numerically, it seems that for any $m,n$ we have $$\sum_{1\leq k\leq mn}\left\{ \frac{k}{m}\right\} \left\{ \frac{k}{n}\right\} =\frac{(m-1)(n-1)}{4}+C(\gcd(m,n))$$ where $C(\gcd(m,n))$ is some constant depending only on the $\gcd(m,n)$.

Additionally: Can we sum this even when it is not a complete interval? Suppose that $0<a<b<mn,$ do we have an exact form for $$\sum_{a\leq k\leq b}\left\{ \frac{k}{m}\right\} \left\{ \frac{k}{n}\right\}.$$

Remark: In the one variable case we have $$\sum_{1\leq k\leq n}\left\{ \frac{k}{n}\right\} =\frac{n-1}{2}$$ the sum over an interval $a,b$ has an explicit form.

Answer 1

Let's call your sum $f(m,n)$. The ordinary generating function of $f(\cdot,n)$ appears to be of the form $$g(z,n) = \frac{z^2 p_n(z)}{6 (1-z)(1-z^n)}$$ where $p_n$ is a polynomial of degree $n-1$ (except for $n=2$ where it has degree $0$): $$\eqalign{ p_{{2}}&=3\cr p_{{3}}&=-{z}^{2}+7\,z+3\cr p_{{4}}&=-3\,{z}^{3}+12\,{z}^{2}+3\,z+6\cr p_{{5}}&=-6\,{z}^{4}+18\,{z}^{3}+6\,{z}^{2}+6\,z+6\cr p_{{6}}&=-10\,{z}^{5}+25\,{z}^{4}+6\,{z}^{3}+5\,{z}^{2}+10\,z+9\cr p_{{7}}&=-15\,{z}^{6}+33\,{z}^{5}+9\,{z}^{4}+9\,{z}^{3}+9\,{z}^{2}+9\,z +9\cr p_{{8}}&=-21\,{z}^{7}+42\,{z}^{6}+9\,{z}^{5}+12\,{z}^{4}+3\,{z}^{3}+18 \,{z}^{2}+9\,z+12\cr p_{{9}}&=-28\,{z}^{8}+52\,{z}^{7}+12\,{z}^{6}+8\,{z}^{5}+16\,{z}^{4}+12 \,{z}^{3}+8\,{z}^{2}+16\,z+12\cr p_{{10}}&=-36\,{z}^{9}+63\,{z}^{8}+12\,{z}^{7}+15\,{z}^{6}+12\,{z}^{5}+ 3\,{z}^{4}+24\,{z}^{3}+15\,{z}^{2}+12\,z+15\cr p_{{11}}&=-45\,{z}^{10}+75\,{z}^{9}+15\,{z}^{8}+15\,{z}^{7}+15\,{z}^{6} +15\,{z}^{5}+15\,{z}^{4}+15\,{z}^{3}+15\,{z}^{2}+15\,z+15\cr p_{{12}}&=-55\,{z}^{11}+88\,{z}^{10}+15\,{z}^{9}+14\,{z}^{8}+13\,{z}^{7 }+24\,{z}^{6}-{z}^{5}+34\,{z}^{4}+9\,{z}^{3}+20\,{z}^{2}+19\,z+18\cr}$$

EDIT: This seems to come from the fact that $$f(m+n,n) - f(m,n) =\frac{n^2-n}{4}$$ for all $m$ and $n$.

EDIT: Let $g(m,n) = f(m,n) - \dfrac{(m-1)(n-1)}{4}$. From $f(m+n,n) - f(m,n) = \dfrac{n^2-n}{4}$ we get $g(m+n,n) = g(m,n)$. By following the Euclidean algorithm, we get $$g(m,n) = g(d,d) = \dfrac{(d-1)(2d-1)}{6} - \dfrac{(d-1)^2}{4} = \frac{d^2-1}{12}$$ where $d = \gcd(m,n)$. That is, $$ f(m,n) = \frac{\gcd(m,n)^2-1}{12} + \dfrac{(m-1)(n-1)}{4} $$

Answer 2

The fractional parts depend only on the values modulo $n$ and $m$, respectively.

Since you take $m$ and $n$ relatively prime, you can simply let the two instances of $k$ run through all residue classes modulo $m$ and $n$ independently (Chinese remainder theorem). This reduces your question immediately to the product of the one-variable case for $m$ and $n$.

The one-variable case is a direct consequence of the summation formula for the first $n$ integers.

Edited to add: This means, of course, that an arbitrary interval is not a very good condition on the pair of residues and there is no reason to expect a general closed expression.

Answer 3

For the relatively prime case. Split the summation into classes $k \equiv 0 \mod m$, $k \equiv 1 \mod m$, $k \equiv 2 \mod m$ and so on. For $k \equiv r \mod m$, and $1 \leq k \leq mn$ each $k$ leaves a distinct remainder when divided by $n$ since $m$ and $n$ are relatively prime. Hence, the summation is $$\displaystyle \frac{\sum_{r=0}^{n-1} r}{m} \times \frac{\sum_{r=0}^{m-1} r}{n} = \frac{n(n-1)}{2m} \frac{m(m-1)}{2n}$$

EDIT Consider the class say $k \equiv r \bmod m$. If $(m,n)=1$, then $r,m+r,2m+r,\cdots,(n-1)m+r$ leave different remainders when divided by $n$. If not then $n | (k_1 - k_2)m$ for some $0 \leq k_1,k_2 <n$. Since $(m,n) = 1$, $n|(k_1-k_2)$. Not possible. Hence, summing all the remainders in the class $k \equiv r \bmod m$ gives us $\frac{n(n-1)}{2}$. Hence, the sum of all the fractional parts is $\displaystyle \frac{n(n-1)}{2m}$.