13
$\begingroup$

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?

$\endgroup$
0

6 Answers 6

9
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Portland
    Oct 13, 2010 at 18:39
  • $\begingroup$ 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. $\endgroup$ Oct 13, 2010 at 20:20
  • $\begingroup$ ...although, trying a couple of plots with randomly chosen $\theta$, $S_n$ appears to be bounded, but is probably growing very slowly. $\endgroup$ Oct 13, 2010 at 20:52
  • $\begingroup$ 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$. $\endgroup$ Oct 14, 2010 at 2:31
  • $\begingroup$ @GeorgeLowther Is there a standard reference for the case when we know the irrationality measure of θ? $\endgroup$
    – Charles
    Oct 14, 2016 at 18:58
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
6
  • 3
    $\begingroup$ I don't think tosses of a fair coin is a good model for fractional part of multiples of an irrational. $\endgroup$ Oct 13, 2010 at 5:08
  • $\begingroup$ You're right, it isn't---I was confusing equidistributed with pseudo-random. $\endgroup$ Oct 13, 2010 at 6:52
  • $\begingroup$ @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. $\endgroup$ Oct 13, 2010 at 6:53
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 13, 2010 at 7:17
  • $\begingroup$ I think it's bounded if the partial quotients of the irrational are bounded (as is the case for any quadratic irrational, for example). $\endgroup$ Oct 13, 2010 at 12:16
0
$\begingroup$

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.

$\endgroup$

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.