Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Question: Let $s(p,q)=\sum_{i=1}^{q-1}((i/q))((pi/q))$ where (p,q)=1 and $((x))=x-[x]-1/2$ for $x\notin Z$. I want to prove that $s(p,q)+s(q,p)=(p/q+\frac{1}{pq}+q/p)/12-1/4$ using at least one of the following four methods.

i. I tried proving Dedekind Reciprocity using Riemann-Stieltjes integration. In his 1982 journal article, ‘Sums involving the greatest integer function and Riemann-Stieltjes integration’ by Bruce C. Berndt, he recommends using Riemann-Stieltjes integration to prove identities involving sums of the greatest integer function where it would be difficult to do so using lattice-point diagrams. You can read it online at http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=GDZPPN002200031. He proves a result by Carlitz using an identity needed to prove Dedekind Reciprocity, but does not prove that identity. I am open to any ideas, but it seemed like Riemann-Stieltjes integration can only be applied in a select few cases.

ii. I tried proving Dedekind Reciprocity using lattice-point diagrams, but it got very messy. Since Berndt did not prove it using Riemann-Stieltjes integration, I doubt it can be done using lattice-points. I welcome any ideas for using lattice-point diagrams in a critical part (if not the main part) of the proof.

iii. I tried proving Dedekind Reciprocity using the Fourier series for the sawtooth-wave function. I actually made some progress with this approach. Since $-((x))=\sum_{n=1}^{\infty}sin(2n{\pi}x)/(n\pi)$ for ALL REAL x, we consider the function $((i/q))((pi/q))$ where (p,q)=1. Since ((i/q)) simplifies to i/q-1/2 for all i in the sum, I can evaluate all sums in the product using elementary methods except for $\sum_{i=1}^{q-1}(i/q)((pi/q))+\sum_{i=1}^{p-1}(i/p)((qi/p))$. Since $i((pi/q))/q=-\sum_{n=1}^{\infty}isin(2n{\pi}i/q)/(qn\pi)$, we start with the finite sum $\sum_{k=1}^{q-1}kx^k=\frac{qx^q}{x-1}-\frac{x(x^q-1)}{(x-1)^2}$. Since $ksin(2n{\pi}kp/q)/(qn\pi)=k((e^{i2n{\pi}p/q})^k-(e^{-i2n{\pi}p/q})^k)/(2qn{\pi}i)$ and $\sum_{n=1}^{\infty}\sum_{k=1}^{q-1}k((e^{i2n{\pi}p/q})^k-(e^{-i2n{\pi}p/q})^k)/(2qn{\pi}i)=\sum_{n=1}^{\infty}(1/2-1/(1-e^{i2n{\pi}p/q}))/(n{\pi}i)$, $\sum_{i=1}^{q-1}(i/q)((pi/q))+\sum_{i=1}^{p-1}(i/p)((qi/p))=-\sum_{n=1}^{\infty}(1-1/(1-e^{i2n{\pi}p/q})-1/(1-e^{i2n{\pi}q/p}))/(n{\pi}i)$. When converting the sum back into trigonometric functions, the sum simplifies to $\sum_{n=1}^{\infty}(cot(n{\pi}p/q)+cot(n{\pi}q/p))/(2n\pi)=\sum_{n=1}^{\infty}\frac{sin(n{\pi}(p/q+q/p))}{2n{\pi}sin(n{\pi}p/q)sin(n{\pi}q/p)}$. How can I evaluate these sums? Can these sums be easily evaluated using Poisson summation or some other analytic method?

iv. I found a decent proof of Dedekind Reciprocity in a 1953 journal article by Carlitz; however, the disadvantage of using it is that I would have to introduce Lagrange polynomials. You can read it online at http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.pjm/1103051326. The first step in the proof requires a proof that $-((r/k))=\frac{1}{2k}+\frac{1}{k}\sum_{s=1}^{k-1}\frac{p^{-rs}}{(1-p^s)}$ where $p=e^{2{\pi}i/k}$ and $r,k\in Z$. The article recommended Mobius inversion, but this relation looks simple enough that I want to prove it by brute force. I am currently working on it and welcome any ideas.

Background: I am writing a subsection on Dedekind Reciprocity for my online book, A Mathematical Analysis of the Greatest Integer Function. The content of my book can be more accurately summarized as a discussion of a variety of integer-intensive topics in number theory and analysis. My objective is to develop a lot of theory on integer functions in the beginning and then use the theory to discuss these integer-intensive topics and prove important results associated with them using a powerful, direct, and unified approach. In summary, I am attempting to devise a proof of Dedekind Reciprocity that uses integer functions in an advanced way and is otherwise elementary. However, if such a proof already exists, then I would be content with inserting it in my work and citing the source.

share|improve this question
Since you don't mention the Rademacher-Grosswald book, Dedekind Sums, I'm not sure whether you have looked at the many proofs given there to see whether any meet your needs. –  Gerry Myerson Sep 21 '12 at 5:43
Thank you, Gerry. I tried to find the book on the internet before, but could not. After your comment, I tried again and found it at maths.ed.ac.uk/~aar/papers/rademacher2.pdf. It starts off with four proofs of Dedekind Reciprocity, some of which are pretty basic and straightforward from the definition (which is what I am looking for). It will take me some time to figure out which proof I want to use and how I want to present it, but I should be able to take it from here. When I am finished, I can read further to decide which arithmetic applications to include in my book. –  Ken Sep 21 '12 at 21:07
add comment

1 Answer 1

In computer science Dedekind sums show up in the study of linear congruential sequences and as a result Donald Knuth discusses Dedekind reciprocity at length in The Art of Computer Programming.

His proof of choice is based on the same Carlitz proof you referred to, but he alludes to another:

The proof we will give, based on the complex roots of unity, is essentially due to Carlitz. There is actually a simpler proof that uses only elementary manipulations of sums (see exercise 7)

(in section 3.3.3 Theoretical Tests, just after Lemma B "Reciprocity Law" for Dedekind sums)

Exercise 7 refers to exercise 1.2.4-45 which in turns refers to exercise 1.2.4-37:

Let $m$ and $n$ be integers, $n>0$. Show that

$$\sum_{0\le k\lt n}{\left \lfloor \frac{mk+x}{n} \right \rfloor}=\frac{(m-1)(n-1)}{2}+\frac{d+1}{2}+d\left \lfloor x/d \right \rfloor, $$

where $d$ is the greatest common divisor of $m$ and $n$, and $x$ is any real number.

(in section 1.2.4 Integer Functions and Elementary Number Theory)

You can see the seeds of reciprocity in the symmetry of the right hand side of this equation with respect to $m$ and $n$.

share|improve this answer
add comment

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.