# Consequence of equidistribution or not?

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?

-

No, you cannot put any better bound than SN = 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 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 θ 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 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.

-
George, this is very nice. "There will be an uncountable dense set of irrational $\theta$ for which we can rule out bounds such as $S_n = O(n^x)$ with $x<1$." But is there any $\theta \in \mathbb{R}\setminus \mathbb{Q}$ s.t. there exists $x<1$ and $S_n = O(n^x)$, or can we rule that out as well? – Portland Oct 13 '10 at 18:39
I expect that $S_n=o(n^x)$ for every x > 1/2 and almost every $\theta$, by thinking of $S_n$ as similar to a random walk. I'll have to think about that a bit more though. – George Lowther Oct 13 '10 at 20:20
...although, trying a couple of plots with randomly chosen $\theta$, $S_n$ appears to be bounded, but is probably growing very slowly. – George Lowther Oct 13 '10 at 20:52
Well, my guess of $S_n=o(n^x)$ for every x > 1/2 and almost every $\theta$ was correct. We can't do much better than this, as Fedor's answer shows that $\limsup_{n\to\infty}|S_n|/n^x=\infty$ for every x < 1/2 and almost every $\theta$. – George Lowther Oct 14 '10 at 2:31

The sine function has little to do with this; you get $\epsilon_n=1$ if $n\theta/2\pmod1$ is in $(0,1/2)$, $-1$ if it's in $(1/2,1)$. Now you can probably apply bounds for the discrepancy of the sequence $n\theta$, but even that may be overkill.

-

Continuing the idea from Gerry's answer. The quantity, you are looking for is just

$$D(N) = 2 \left( \# \{1 \leq n \leq N: \theta n \pmod{1} \in [0,\frac{1}{2}) \}- \frac{N}{2} \right)$$ If $\theta = 1/3$, then this quantity grows like $N$. Since $\#\{\dots\} \sim \frac{2}{3} N$. Something similar happens whenever $\theta = \frac{p}{q}$ with $q$ odd (if I am not mistaken). Of course one cannot achieve a growth of the form $\sim N$ for any irrational number, but one can get arbitrarily close choosing $$\theta = \cfrac{1}{a_1 + \cfrac{1}{a_2 + \dots}}$$ with the sequence $a_k$ growing fast enough.

In summary, the above strategy should show that given $f(N)$ such that $f(N)/N \to 0$, one can find $\theta$ such that $D(N) \geq c f(N)$ for some small enough $c > 0$ and infinitely many $N$.

-

No $x$ less then $1/2$ may satisfy $S_N=o(n^x)$. Indeed, denote $f(x)=\chi_{[0,\pi]}-\chi_{[\pi,2\pi]}$, then we are interested in $|f(\theta)+f(2\theta)+\dots+f(n\theta)|$ for specific value of $\theta$. But $$\int_0^{2\pi} |f(\theta)+f(2\theta)+\dots+f(n\theta)|^2 d\theta$$ is not less then $n$, since $\int f^2(k\theta)=1$, $\int f(k\theta) f(m\theta)\geq 0$ (the latter may be otten elementary or via Fourier series $f(x)=\pi^{-1}\sum \sin (2k+1)x/(2k+1)$, I may be wrong with the constant $\pi^{-1}$).

-

To say that $n \theta$ is equidistributed means in particular that for any open set $O$ of $(0,1)$ that if $N(n)$ is the the number of $k < n$ such that $k \theta (\mod 1) \in O$, then $N(n) /n$ approaches the measure of $O$. It follows easily that the sum $S_N$ is just your expected winnings after $N$ tosses of a fair coin if you win 1 dollar for each head and lose a dollar for each tail (or the distance you are from the origin in a one dimensional random walk after $N$ steps)---in other words, $|S_N|$ is asymptotically equal to $\sqrt {N}$.

-
I don't think tosses of a fair coin is a good model for fractional part of multiples of an irrational. – Gerry Myerson Oct 13 '10 at 5:08
You're right, it isn't---I was confusing equidistributed with pseudo-random. – Dick Palais Oct 13 '10 at 6:52
@Gerry: It probably is adequate model (equidistributed sequences should behave as random sequences, natural to expect from them), but this fact is hard to prove in full generality. – Fedor Petrov Oct 13 '10 at 6:53
I don't think so. For example the sequence 1/2,1/4,3/4,1/8,3/8,5/8, 1/16,3/16,... is equidistributed but not random. You need k-distributed for all (or at least for large k) for approximate pseudorandomness. I decided to test the sum $S_N$ when $\theta = \sqrt 2$ and in fact it seems to oscillate between -2 and 2 up to N = 1000. It never gets near 30. – Dick Palais Oct 13 '10 at 7:17
I think it's bounded if the partial quotients of the irrational are bounded (as is the case for any quadratic irrational, for example). – Gerry Myerson Oct 13 '10 at 12:16

In the case that $\theta=0.71828...=e-1$ the numbers (for $0<n<1000000$ ) range from +9 to -2 with counts 384, 4624, 24764, 78017, 161080, 229363, 230073, 162500, 79028, 25112, 4672, 384

For $\theta=0.414...=\sqrt{2}-1$ they range from +17 to +1 with counts 128, 1152, 5312, 16608, 39240, 74016, 114980, 149784, 165216, 154818, 122949, 82038, 45232, 20016, 6752, 1568, 192

and for $\theta=0.6180...=\frac{\sqrt{5}-1}{2}$ they range from 10 to -9 with counts

1, 20, 196, 1231, 5493, 18331, 47058, 94415, 149350, 187132, 186186, 147265, 92534, 46012, 17945, 5399, 1217, 195, 20, 1

So one would guess that for $\theta$ rational (but not an integer) it is periodic but bounded and for irrational $\theta$ unbounded.

-