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

Let $\tau$ be $(-1+\sqrt{5})/2$, let $f(x)$ be $\lfloor (x+1)\tau \rfloor$, let $s_n$ be $\tau n (n+1) (n+2) / 6$, and let $S_n$ be $$\sum_{k=0}^{n} (n−2k)f(n−k) = n f(n) + (n-2) f(n-1) + (n-4) f(n-2) + \dots - (n-2) f(1) - n f(0).$$

Is $(S_n-s_n)/(n \log n)$ bounded for $n > 1$? (It stays between -0.35 and +0.30 for all $n$ between 2
and $10^6$.)

This is a specific instance of the question Dedekind-esque sums that I posted a few weeks ago. It may be an atypical instance in some ways (since $\tau$ is a pretty atypical real number for Diophantine approximation problems) but it's the one that interests me most right now. An affirmative answer to my question would have implications concerning the "Goldbug machine" described in .

The plot at the bottom of is a histogram of $(S_n - s_n)/n$ for $n$ going from 1 to a million. As you can see, it doesn't stray very far away from 0. So perhaps that $\log n$ in the denominator could be replaced by something smaller, like $\sqrt{\log n}$ or even $\log \log n$ (or maybe even 1, though I doubt it).

share|cite|improve this question
Okay, I'm offering a bounty of 50 reputation points for the first person to give a detailed solution to this problem. (Not just a proof-sketch, but the details too; the sort of thing you'd submit as a solution to a problem published in the American Mathematical Monthly). I'm kind of new to MathOverflow, so I'm unclear whether posting a bounty is something I can just decree informally in a comment like this, or whether there's an official procedure I need to follow. (The FAQ says "You can post a bounty" but it doesn't say how!) – James Propp Jun 2 '10 at 3:50
It appears that the managers of the site kindly put 50 bounty points on this question on my behalf, which I appreciate. Meanwhile, when I reloaded this page, I finally noticed the "add bounty" button (which I could swear wasn't there before!), so I put 50 bounty points on the problem on my own behalf, not realizing that the site managers had already put 50 bounty points on the problem. So now there's 100 bounty points on the problem, which is fine with me, if it'll get this problem more attention. But am I the only one who's having trouble using MathOverflow? – James Propp Jun 3 '10 at 1:44
You say you're new, and no-one else has posted here, so just let me re-assure you: people are reading. You're getting views and upvotes. The reason I have made no post here is that I tried your problem and simply can't get anywhere; perhaps others are in the same boat. – Kevin Buzzard Jun 3 '10 at 5:30
The problem reduces to computing and proving the main terms of sums of the form $\sum_{k=1}^{n} \{\frac{ka}{n+1}\}$ and $\sum_{k=1}^{n} k\{\frac{ka}{n+1}\}$, the former being easy. I have not cracked the second sum. – Dror Speiser Jun 3 '10 at 20:54
up vote 2 down vote accepted

I can't help thinking that the answer ought to come out of a combination of standard techniques. First, indeed, reduce to fractional parts: but with a caveat, that it would be sensible to do some manipulation first. I'm thinking about "summation by parts".

Edit: There is a classic reference: G. H. Hardy & J. E. Littlewood, "Some problems of Diophantine approximation: The lattice points of a right-angled triangle," (1st memoir), Proc. London Math. Soc. (2), v. 20, 1922, pp. 15-36. They consider the modified fractional part sum, with {x} set as x - [x] - 1/2, of the ${k\theta}$ up to n, where to be compatible with their notation $\theta$ would be the reciprocal of $\tau$, not that this matters at all. The bound they get is O(log n) (Hardy's Works vol. I p. 145), which depends only on the continued fraction having bounded partial quotients. The particular case relevant to $\tau$ is worked out in detail over the next few pages. The result is sharp. Off the top of my head this looks enough to get the error term O(nlog n) for the sum as posted, by breaking into at most n sums of this type.

share|cite|improve this answer
If Charles or anyone else ever does the full analysis, please let me know. Thanks to everyone who thought about the problem, whether or not they posted anything! – James Propp Jun 10 '10 at 3:14
Added a reference where I think the whole business is sufficiently clarified. – Charles Matthews Jun 16 '10 at 11:13

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.