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

Does anyone know of a way to simplify this sum?

$$S(n)=\sum_{j=1}^{\rho(n)}\sum_{k=1}^\infty\frac{\sin[2\pi k n 2^{-j}]-\sin[2\pi k (n-1) 2^{-j}]}{k}$$

where $\rho(n)=[\log_2(n)]$ (and $[x]$ denotes the greatest integer less than $x$).

Note: This question is a follow-up to a previous question I asked: Greatest power of two dividing an integer

EDIT: After following all the given suggestions, I found that for integer $n$,


This is pretty much what I started with in my previous post, so if anyone knows of a way to take this sum, please let me know. Anyway, I will leave this result here in case anyone ever comes across $S(n)$ in some other context. Thanks to everyone who helped.

share|cite|improve this question
@Alex-Lupsasca, two thumbs up for editing your question based upon the answers and comments received! :) – sleepless in beantown Nov 22 '10 at 6:51
@sleepless: I think I was too hasty; there was a mistake in what I computed :( – Alex Lupsasca Nov 22 '10 at 6:54
@Alex, yikes! You might want to take the "Solved" out of the title. That way, no one will mistakenly skip over this question thinking it's already been solved... Best wishes. I'll contribute something to the answer section if my neurons fire in the appropriate sequence. May I ask – sleepless in beantown Nov 22 '10 at 7:14
Well, using the solution in terms of logarithms and then in terms of arguments (given by Stopple) below, one can obtain (by using arctan(y/x) as argument) a sum with terms of the form arccot(tan x) which finally simplifies to the expression given in the above edit. – Alex Lupsasca Nov 23 '10 at 4:18
There's something peculiar about the 2nd display in the current version. First, I think you want both floor terms to be inside the summation. Second, when $n$ is odd the term outside that summation is 1/0. – Gerry Myerson Nov 23 '10 at 4:23
up vote 2 down vote accepted

Mathematica computes just the sum on k as $$ \frac{1}{2} i \left(\log \left(1-e^{-i 2^{1-j} (n-1) \pi }\right)-\log \left(1-e^{i 2^{1-j} (n-1) \pi }\right)-\log \left(1-e^{-i 2^{1-j} n \pi }\right)+\log \left(1-e^{i 2^{1-j} n \pi }\right)\right) $$ One can then simplify the sum on j of logarithms as the logarithm of a product.

share|cite|improve this answer
This expression is indeterminate for integer n... Can you think of a way around that? – Alex Lupsasca Sep 29 '10 at 21:42
We have two terms of the form $\log(1-z)-\log(1-\bar{z})$. With $\log(1-z)=\ln|1-z|+i\arg(1-z)$, this difference simplifies (for $z$ not on the unit circle) to $2i\arg(1-z)$, which makes sense even on the unit circle. – Stopple Sep 30 '10 at 15:46
Oops, when $n$ has more than $j$ twos dividing it, the argument is undefined - this ties in with you original question. – Stopple Sep 30 '10 at 15:58

The summand is even in k, and $\sin(x)/x$ has a nice Fourier transform, so it is very tempting to symmetrise in k (and throw in k=0, adopting the usual convention that the sinc function $\sin(x)/x$ equals 1 at x=0) and then apply Poisson summation. This should lead to a nice expression for the inner sum that can then be summed in j. (Admittedly there is the issue that the sinc function is not absolutely integrable, but one can still proceed formally for the purposes of getting the right answer, and then go back and make things more rigorous, e.g. by using the theory of distributions, if this becomes necessary. I'm guessing that there is some cancellation between the two terms in the summand that will assist in this task.)

The logarithmic expressions of the form $\log(1 - e^{ix})$ that appeared in the other comments are not as scary as they seem. Observe that the final sum is real, so one only needs the real parts of things like $i\log(1 - e^{ix})$, i.e. the phase of $\log(1-e^{ix})$, but this is basically something like $x/2 \pm \pi/2$ (depending on branch cuts). So there is probably going to be quite a bit of simplification. (But going via the Poisson summation route rather than the logarithmic power series route may be a bit more direct, even if both methods ought to give the same answer at the end.)

share|cite|improve this answer
I tried to apply the Poisson summation but got a function which doesn't match the sum... I must be making a mistake somewhere. One more thing: I thought that sinc(0) is usually defined to be 1? – Alex Lupsasca Sep 30 '10 at 0:15
Sorry, that was a typo (but the k=0 term cancels itself out regardless). – Terry Tao Sep 30 '10 at 5:25
I seem to be getting the same expression that I started with (in my previous post) and was trying to simplify... – Alex Lupsasca Oct 2 '10 at 20:40
I believe that Poisson summation eventually leads back to $[n/2]-[(n-1)/2]+[n/4]-[(n-1)/4]+[n/8]-[(n-1)/8]+\dots$ which is what I started with in the first place and is of little use to me... Thank you for the help nevertheless; this was an instructive experience :) – Alex Lupsasca Nov 22 '10 at 5:29

Please read this as a comment: I had to type it here because it is too long to fit into the comment box.

To get a rough idea, i replaced the sum on $j$ by an integral going up to $\log n$. Mathematica came up with the following (ugly) closed form (after doing a FullSimplify) (please excuse the horrible typesetting).

$\frac{2^{-1-\log(n)}}{\log(2)} \Bigl(-2\pi+\pi\log(4)\log(n))+2^{\log(n)}\Bigl(\pi -\pi \log(2)-i \log(2)$

$\Bigl(2 \text{atanh}\bigl(e^{-i n \pi }\bigr)- 2 \text{atanh}\bigl(e^{i n \pi }\bigr)+\bigl(-\log\bigl(1-e^{-i 2^{1-\log(n)} (-1+n) \pi }\bigr)+\log\bigl(1-e^{i 2^{1-\log(n)} (-1+n) \pi }\bigr)$

$+\log\bigl(1-e^{-i 2^{1-\log(n)} n \pi }\bigr)-\log\bigl(1-e^{i 2^{1-\log(n)} n \pi }\bigr)\Bigr) \log(n)\Bigr)$

So my point is that perhaps your sum might not have a very nice closed form, if at all. Perhaps this integral helps study the asymptotic properties of your $S(n)$?

share|cite|improve this answer

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.