Let $\theta \not\in \mathbb{Q}$. We know that $(n\theta)\_{n \geq 1}$ is equidistributed modulo 1.


Let $\epsilon\_n = \mathrm{sign}\bigl(\sin(n\pi \theta)\bigr)$ and $S\_N= \sum\_{n=1}^N \epsilon\_n$.


I'm looking for a "good" asymptotic bound for $|S\_N|$ (not $|S\_N|\leq N$ obviously). 


It looks like for any $x>0$, we should have $S\_N =o(n^x)$, or even better, that $(S\_N)$ is bounded, but is it?



Consequence of equidistribution or not?
No, you cannot put any better bound than SN = *o*(N). There is a general technique, using the [Baire category theorem](http://en.wikipedia.org/w/index.php?title=Baire_category_theorem&oldid=379733059) 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](https://mathoverflow.net/questions/35902/does-weyls-inequality-prove-equidistribution/35976#35976)). 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](http://en.wikipedia.org/wiki/Weyl%2527s_equidistribution_theorem), both sides on the right hand side tend to 1/2 and SN / N → 0, so SN = *o*(N).


It is not possible to do better than this. In fact, if f: ℕ → ℝ+ is any function satisfying liminf f(N) / N = 0 then there will be an uncountable dense set of irrational θ for which limsup SN / f(N) = ∞. In particular, using f(n) = nx for x < 1 rules out bounds such as Sn = *O*(nx).
In fact, we can find a set of such θ as an intersection of countably many open dense subsets of ℝ, so the Baire category theorem shows the existence of uncountably many counterexamples.


Let u(x) = 1{0≤[x/2]<1/2} - 1{1/2≤[x/2]<1} where [x] is the fractional part of x, and SN(θ) = Σn≤N u(nθ). Let UK be the set
$$
U\_K=\left\{\theta\in\mathbb{R}\colon S\_n(\theta)>Kf(n){\rm\ for\ some\ }n\ge K\right\}.
$$
This contains a dense open subset of ℝ. In fact, if θ = 2p/q for q odd then, for 1 ≤ n < q, u((q-n)θ)  = -u(nθ). So, Sq-1(θ) = 0 and Sq(θ) = 1. Then, by periodicity of [nθ/2], Snq (θ) = n and Sn(θ) increases linearly. So, Sn(θ) > Kf(n) for infinitely many n, and θ ∈ UK. By right continuity of u, (θ,θ+ε) ⊆ UK for small enough ε. This shows that (2p/q,2p/q+ε) is contained in the interior of UK and, as such 2p/q are dense, the interior of UK is a dense open subset of ℝ. The Baire category theorem implies that
$$
U\equiv\bigcap\_{K=1}^\infty U\_K
$$
is an uncountable dense subset of ℝ and, by construction, for any θ ∈ U, limsup Sn(θ) / f(n) > K for each K.




---


The further question was asked in the comment: are there *any* irrational θ for which SN = *O*(Nx) for x < 1. The answer is yes. In fact this holds for [almost every](http://en.wikipedia.org/wiki/Almost_everywhere) θ 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 SN(θ),


$$
\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](http://mathworld.wolfram.com/IrrationalityMeasure.html) less than α then, for large enough N, the rational approximation p/q can be chosen such that N1/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.


