Return to Answer

No, you cannot put any better bound than S_N = o(N). There is a general technique, using the Baire category theorem of proving the existence of counterexamples to problems like this (which I discovered while trying to find a counterexample to a question by David Speyer, link). I see that Helge's answer is also pointing towards the same result.

First, for θ irrational, $$ S_N/N=\frac{1}{N}\sum_{n=1}^N1_{\{0< n\theta/2 <1/2{\rm\ (mod\ 1)}\}}-\frac{1}{N}\sum_{n=1}^N1_{\{1/2< n\theta/2 <1{\rm\ (mod\ 1)}\}} $$ By Weyl's equidistribution theorem, both sides on the right hand side tend to 1/2 and S_N / N → 0, so S_N = o(N).

The further question was asked in the comment: are there any irrational θ for which S_N = O(N^x) for x < 1. The answer is yes. In fact this holds for almost every θ and every x > 1/2.

$$ \begin{array} \displaystyle \vert S_N(\theta)\vert &\displaystyle \le a +\sum_{n=1}^N1_{\{-2/q\le n\theta\le 2/q{\rm\ (mod\ 1)}\}}\\\\ &\displaystyle\le 2q +\sum_{n=0}^{\lfloor N/q\rfloor}\sum_{m=1}^q1_{\{-2/q\le nq\theta+m\theta\le 2/q{\rm\ (mod\ 1}\}}\\\\ &\displaystyle\le 2q+\sum_{n=0}^{\lfloor N/q\rfloor}\sum_{m=1}^q1_{\{-4/q\le nq\theta+2mp/q\le 4/q{\rm\ (mod\ 1)}\}} \end{array} $$ The points 2mp/q (mod 1) are equally spaced. If q is odd then they have spacing 1/q and no more than 9 of them can lie in an interval of length 8/q. If q is even then the spacing is 2/q and no more than 5 can lie in such an interval. In either case, the final sum over m above is bounded by 10=5*2. $$ \vert S_N(\theta)\vert\le 2q+10N/q. $$ If θ has irrationality measure less than α then, for large enough N, the rational approximation p/q can be chosen such that N^1/2 ≤ q ≤N^(α-1)/2, $$ \vert S_N(\theta)\vert\le 2N^{(\alpha-1)/2}+10N^{1/2}. $$ In particular, if θ has irrationality measure 2 then $S_N=O(N^x)$ for every $x>1/2$. But, almost every real number has irrationality measure 2.

No, you cannot put any better bound than S_N = o(N). There is a general technique, using the Baire category theorem of proving the existence of counterexamples to problems like this (which I discovered while trying to find a counterexample to a question by David Speyer, link). I see that Helge's answer is also pointing towards the same result.

First, for θ irrational, $$ S_N/N=\frac{1}{N}\sum_{n=1}^N1_{\{0< n\theta/2 <1/2{\rm\ (mod\ 1)}\}}-\frac{1}{N}\sum_{n=1}^N1_{\{1/2< n\theta/2 <1{\rm\ (mod\ 1)}\}} $$ By Weyl's equidistribution theorem, both sides on the right hand side tend to 1/2 and S_N / N → 0, so S_N = o(N).

The further question was asked in the comment: are there any irrational θ for which S_N = O(N^x) for x < 1. The answer is yes. In fact this holds for almost every θ and every x > 1/2.

$$ \begin{array} \displaystyle \vert S_N(\theta)\vert &\displaystyle \le a +\sum_{n=1}^N1_{\{-2/q\le n\theta\le 2/q{\rm\ (mod\ 1)}\}}\\\\ &\displaystyle\le 2q +\sum_{n=0}^{\lfloor N/q\rfloor}\sum_{m=1}^q1_{\{-2/q\le nq\theta+m\theta\le 2/q{\rm\ (mod\ 1}\}}\\\\ &\displaystyle\le 2q+\sum_{n=0}^{\lfloor N/q\rfloor}\sum_{m=1}^q1_{\{-4/q\le nq\theta+2mp/q\le 4/q{\rm\ (mod\ 1)}\}} \end{array} $$ The points 2mp/q (mod 1) are equally spaced. If q is odd then they have spacing 1/q and no more than 9 of them can lie in an interval of length 8/q. If q is even then the spacing is 2/q and no more than 5 can lie in such an interval. In either case, the final sum over m above is bounded by 10=5*2. $$ \vert S_N(\theta)\vert\le 2q+10N/q. $$ If θ has irrationality measure less than α then, for large enough N, the rational approximation p/q can be chosen such that N^1/2 ≤ q ≤N^(α-1)/2, $$ \vert S_N(\theta)\vert\le 2N^{(\alpha-1)/2}+10N^{1/2}. $$ In particular, if θ has irrationality measure 2 then $S_N=O(N^x)$ for every $x>1/2$. But, almost every real number has irrationality measure 2.

No, you cannot put any better bound than S_N = o(N). There is a general technique, using the Baire category theorem of proving the existence of counterexamples to problems like this (which I discovered while trying to find a counterexample to a question by David Speyer, link). I see that Helge's answer is also pointing towards the same result.

No, you cannot put any better bound than S_N = o(N). There is a general technique, using the Baire category theorem of proving the existence of counterexamples to problems like this (which I discovered while trying to find a counterexample to a question by David Speyer, link). I see that Helge's answer is also pointing towards the same result.

The further question was asked in the comment: are there any irrational θ for which S_N = O(N^x) for x < 1. The answer is yes. In fact this holds for almost every θ and every x > 1/2.

The idea is to consider rational approximations to θ, |θ/2 - p/q| ≤ q^-2. Then, there will be an integer 1 ≤ a < q such that |1/2 - [ap/q]| ≤ 1/(2q). So, |1/2-[aθ/2]| ≤ 1/q. With u() as above, it follows that u(nθ) + u((n+a)θ) = 0 unless -2/q ≤ nθ ≤ 2/q (mod 1). So, there is a lot of cancellation in S_N(θ),

$$ \begin{array} \displaystyle \vert S_N(\theta)\vert &\displaystyle \le a +\sum_{n=1}^N1_{\{-2/q\le n\theta\le 2/q{\rm\ (mod\ 1)}\}}\\\\ &\displaystyle\le 2q +\sum_{n=0}^{\lfloor N/q\rfloor}\sum_{m=1}^q1_{\{-2/q\le nq\theta+m\theta\le 2/q{\rm\ (mod\ 1}\}}\\\\ &\displaystyle\le 2q+\sum_{n=0}^{\lfloor N/q\rfloor}\sum_{m=1}^q1_{\{-4/q\le nq\theta+2mp/q\le 4/q{\rm\ (mod\ 1)}\}} \end{array} $$ The points 2mp/q (mod 1) are equally spaced. If q is odd then they have spacing 1/q and no more than 9 of them can lie in an interval of length 8/q. If q is even then the spacing is 2/q and no more than 5 can lie in such an interval. In either case, the final sum over m above is bounded by 10=5*2. $$ \vert S_N(\theta)\vert\le 2q+10N/q. $$ If θ has irrationality measure less than α then, for large enough N, the rational approximation p/q can be chosen such that N^1/2 ≤ q ≤N^(α-1)/2, $$ \vert S_N(\theta)\vert\le 2N^{(\alpha-1)/2}+10N^{1/2}. $$ In particular, if θ has irrationality measure 2 then $S_N=O(N^x)$ for every $x>1/2$. But, almost every real number has irrationality measure 2.