Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

6 Answers 6

up vote 8 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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}$.

share|improve this answer
3  
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
1  
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
show 1 more comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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