13
$\begingroup$

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 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).

$\endgroup$
4
  • $\begingroup$ 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!) $\endgroup$ Jun 2, 2010 at 3:50
  • $\begingroup$ 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? $\endgroup$ Jun 3, 2010 at 1:44
  • $\begingroup$ 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. $\endgroup$ Jun 3, 2010 at 5:30
  • $\begingroup$ 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. $\endgroup$ Jun 3, 2010 at 20:54

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$ Jun 10, 2010 at 3:14
  • $\begingroup$ Added a reference where I think the whole business is sufficiently clarified. $\endgroup$ Jun 16, 2010 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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