# A specific Dedekind-esque sum

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 http://front.math.ucdavis.edu/0501.5497 .

The plot at the bottom of http://www.cs.uml.edu/~jpropp/Phi-short.pdf 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).

-
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

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.