How can one prove the following equality (for fixed positive integer $a$):


where $\{x\}=x-\lfloor x\rfloor$ denotes the fractional part operator.

  • 1
    $\begingroup$ Might help to notice that $k(6n-1)/(6n^2)=(k/n)-(1/(6n^2))$. This makes it easier to see what the fractional part is --- it's one thing if $k$ is a multiple of $n$, something else if it's not. Where does the problem come from? $\endgroup$ – Gerry Myerson May 4 '14 at 7:32
  • 1
    $\begingroup$ I'm happy to hear that someone is working on Dedekind sums. Can you tell me what Dedekind sums you're trying to evaluate? $\endgroup$ – Gerry Myerson May 4 '14 at 23:43
  • $\begingroup$ Doesn't the reciprocity formula for Dedekind sums help you to evaluate that one? $\endgroup$ – Gerry Myerson May 4 '14 at 23:51
  • 1
    $\begingroup$ $an^2$ reduced modulo $an-1$ is $n$, so reciprocity relates the sum for $(an^2,an-1)$ to the sum for $(an-1,n)$. Then another application gets you to $(-1,n)$. $\endgroup$ – Gerry Myerson May 5 '14 at 0:02
  • 1
    $\begingroup$ Let $a=2$, $n=3$. Then (in the notation of Rademacher and Grosswald, page 3) $$s(5,18)+s(18,5)=-(1/4)+(1/12)((18/5)+(1/90)+(5/18))$$ But $s(18,5)=s(3,5)$, and reciprocity again gives $$s(3,5)+s(5,3)=-(1/4)+(1/12)((5/3)+(1/15)+(3/5))$$ Then $s(5,3)=s(3-1,3)=s(-1,3)=-s(1,3)$ should be easy to evaluate. $\endgroup$ – Gerry Myerson May 5 '14 at 0:21

The Dedekind sum $s(t,u)$ can be defined by $$s(t,u)=\sum_{k=1}^{u-1}{k\over u}\left(\left\{{kt\over u}\right\}-{1\over2}\right)$$ for relatively prime integers $t,u$, where $\{x\}$ denotes the fractional part of $x$. We have $$s(t,u)=-{1\over2u}\sum k+{1\over u}\sum k\left\{{kt\over u}\right\}$$ so if we can evaluate $s(an-1,an^2)$ then we can evaluate $\displaystyle\sum_1^{u-1}k\left\{{(an-1)k\over an^2}\right\}$

The Dedekind sum satisfies these formulas (and many more):

  1. $s(t,u)=s(t',u)$ if $t\equiv t'\pmod u$

  2. $\displaystyle s(1,u)=-{1\over4}+{1\over6u}+{u\over12}$

  3. $s(-t,u)=-s(t,u)$

  4. $\displaystyle s(t,u)+s(u,t)=-{1\over4}+{1\over12}\left({t\over u}+{1\over tu}+{u\over t}\right)$

The last of these is called the reciprocity formula for the Dedekind sum, and is considerably harder to establish than the others.

Reciprocity lets us express $s(an-1,an^2)$ in terms of $s(an^2,an-1)$.

Then the first formula implies $s(an^2,an-1)=s(n,an-1)$.

Then reciprocity gives us $s(n,an-1)$ in terms of $s(an-1,n)$.

Then from the 1st and 3rd formulas we have $s(an-1,n)=s(-1,n)=-s(1,n)$, and the 2nd formula completes the evaluation.


I make it an answer only because I want to include the program code, please don't downvote. the approximation is good, but not exact. As to how to prove it, I have no clue.

for n = 10, the LHS is 1069916.8199999994 and RHS is 1076398 for n = 1000, LHS = 107999963999968.27 and RHS = 107999963999968

maybe you missed something?

In [5]: math.modf(4.5)
Out[5]: (0.5, 4.0)

In [6]: foo = lambda k,n : k*math.modf(1.0*k*(6*n-1) / (6*n**2))[0]

In [9]: bar = lambda n : 12*sum( [foo(k,n) for k in xrange(1,6*n**2)])

In [10]: bar(10) 
Out[10]: 1076397.9999999993

In [11]: 1080000 - 3600 -2 
Out[11]: 1076398

In [12]: g = lambda n : 108*n**4 - 36*n**2 - 2

In [13]: g(10) 
Out[13]: 1076398

In [14]: bar(1000) 
Out[14]: 107999963999968.27

In [15]: g(1000) 
Out[15]: 107999963999998
  • 2
    $\begingroup$ There is approximation and the formula is exact. For $n=10$,$lhs=rhs=1076398$; for $n=100$,$lhs=rhs=10799639998$; for $n=1000$,$lhs=rhs=107999963999998$. Could you take your code and change the $1.0$ to $1$ in $foo$ ? I suppose that $bar$ is computed on reals and that you bump on accuracy limits. Please answer. $\endgroup$ – Claude Leibovici May 4 '14 at 6:43
  • $\begingroup$ hello, Claude, if if change 1.0 to 1 in foo(), the result of modf() is always 0 because in python,the divisions are by default integer divisions. Thanks to your comment, I realize the evaluation is affected by accuracy limit of floating points. Thanks $\endgroup$ – fast tooth May 4 '14 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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