Consequence of equidistribution or not? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T04:58:22Z http://mathoverflow.net/feeds/question/41972 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/41972/consequence-of-equidistribution-or-not Consequence of equidistribution or not? Portland 2010-10-13T04:07:39Z 2010-10-14T01:42:59Z <p>Let $\theta \not\in \mathbb{Q}$. We know that $(n\theta)_{n \geq 1}$ is equidistributed modulo 1.</p> <p>Let $\epsilon_n = \mathrm{sign}\bigl(\sin(n\pi \theta)\bigr)$ and $S_N= \sum_{n=1}^N \epsilon_n$.</p> <p>I'm looking for a "good" asymptotic bound for $|S_N|$ (not $|S_N|\leq N$ obviously). </p> <p>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?</p> http://mathoverflow.net/questions/41972/consequence-of-equidistribution-or-not/41976#41976 Answer by Dick Palais for Consequence of equidistribution or not? Dick Palais 2010-10-13T05:05:46Z 2010-10-13T05:05:46Z <p>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 &lt; 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}$.</p> http://mathoverflow.net/questions/41972/consequence-of-equidistribution-or-not/41977#41977 Answer by Gerry Myerson for Consequence of equidistribution or not? Gerry Myerson 2010-10-13T05:07:01Z 2010-10-13T05:07:01Z <p>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. </p> http://mathoverflow.net/questions/41972/consequence-of-equidistribution-or-not/41988#41988 Answer by Aaron Meyerowitz for Consequence of equidistribution or not? Aaron Meyerowitz 2010-10-13T07:21:13Z 2010-10-13T07:21:13Z <p>In the case that $\theta=0.71828...=e-1$ the numbers (for <code>$0&lt;n&lt;1000000$</code> ) range from +9 to -2 with counts 384, 4624, 24764, 78017, 161080, 229363, 230073, 162500, 79028, <strong>25112</strong>, 4672, 384</p> <p>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</p> <p>and for $\theta=0.6180...=\frac{\sqrt{5}-1}{2}$ they range from 10 to -9 with counts</p> <p>1, 20, 196, 1231, 5493, 18331, 47058, 94415, 149350, 187132, <strong>186186</strong>, 147265, 92534, 46012, 17945, 5399, 1217, 195, 20, 1</p> <p>So one would guess that for $\theta$ rational (but not an integer) it is periodic but bounded and for irrational $\theta$ unbounded.</p> http://mathoverflow.net/questions/41972/consequence-of-equidistribution-or-not/41989#41989 Answer by Fedor Petrov for Consequence of equidistribution or not? Fedor Petrov 2010-10-13T07:23:51Z 2010-10-13T07:23:51Z <p>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}$).</p> http://mathoverflow.net/questions/41972/consequence-of-equidistribution-or-not/41991#41991 Answer by Helge for Consequence of equidistribution or not? Helge 2010-10-13T07:30:30Z 2010-10-13T07:30:30Z <p>Continuing the idea from Gerry's answer. The quantity, you are looking for is just</p> <p>$$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 $\#\{ ... \} \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.</p> <p>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$.</p> http://mathoverflow.net/questions/41972/consequence-of-equidistribution-or-not/42011#42011 Answer by George Lowther for Consequence of equidistribution or not? George Lowther 2010-10-13T13:04:15Z 2010-10-14T01:42:59Z <p>No, you cannot put any better bound than S<sub>N</sub>&nbsp;=&nbsp;<em>o</em>(N). There is a general technique, using the <a href="http://en.wikipedia.org/w/index.php?title=Baire_category_theorem&amp;oldid=379733059" rel="nofollow">Baire category theorem</a> 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, <a href="http://mathoverflow.net/questions/35902/does-weyls-inequality-prove-equidistribution/35976#35976" rel="nofollow">link</a>). I see that Helge's answer is also pointing towards the same result.</p> <p>First, for &theta; irrational, $$S_N/N=\frac{1}{N}\sum_{n=1}^N1_{\{0&lt; n\theta/2 &lt;1/2{\rm\ (mod\ 1)}\}}-\frac{1}{N}\sum_{n=1}^N1_{\{1/2&lt; n\theta/2 &lt;1{\rm\ (mod\ 1)}\}}$$ By <a href="http://en.wikipedia.org/wiki/Weyl%2527s_equidistribution_theorem" rel="nofollow">Weyl's equidistribution theorem</a>, both sides on the right hand side tend to 1/2 and S<sub>N</sub>&nbsp;/&nbsp;N&nbsp;&rarr;&nbsp;0, so S<sub>N</sub>&nbsp;=&nbsp;<em>o</em>(N).</p> <p>It is not possible to do better than this. In fact, if f:&nbsp;&#x02115;&nbsp;&rarr;&nbsp;&#x0211D;<sup>+</sup> is any function satisfying liminf&nbsp;f(N)&nbsp;/&nbsp;N&nbsp;=&nbsp;0 then there will be an uncountable dense set of irrational &theta; for which limsup&nbsp;S<sub>N</sub>&nbsp;/&nbsp;f(N)&nbsp;=&nbsp;&infin;. In particular, using f(n)&nbsp;=&nbsp;n<sup>x</sup> for x&nbsp;&lt;&nbsp;1 rules out bounds such as S<sub>n</sub>&nbsp;=&nbsp;<em>O</em>(n<sup>x</sup>). In fact, we can find a set of such &theta; as an intersection of countably many open dense subsets of &#x0211D;, so the Baire category theorem shows the existence of uncountably many counterexamples.</p> <p>Let u(x)&nbsp;=&nbsp;1<sub>{0&le;[x/2]&lt;1/2}</sub>&nbsp;-&nbsp;1<sub>{1/2&le;[x/2]&lt;1}</sub> where [x] is the fractional part of x, and S<sub>N</sub>(&theta;)&nbsp;=&nbsp;&Sigma;<sub>n&le;N</sub>&nbsp;u(n&theta;). Let U<sub>K</sub> 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 &#x0211D;. In fact, if &theta;&nbsp;=&nbsp;2p/q for q odd then, for 1&nbsp;&le;&nbsp;n&nbsp;&lt;&nbsp;q, u((q-n)&theta;)&nbsp;&nbsp;=&nbsp;-u(n&theta;). So, S<sub>q-1</sub>(&theta;)&nbsp;=&nbsp;0 and S<sub>q</sub>(&theta;)&nbsp;=&nbsp;1. Then, by periodicity of [n&theta;/2], S<sub>nq</sub>&nbsp;(&theta;)&nbsp;=&nbsp;n and S<sub>n</sub>(&theta;) increases linearly. So, S<sub>n</sub>(&theta;)&nbsp;&gt;&nbsp;Kf(n) for infinitely many n, and &theta;&nbsp;&isin;&nbsp;U<sub>K</sub>. By right continuity of u, (&theta;,&theta;+&epsilon;)&nbsp;&sube;&nbsp;U<sub>K</sub> for small enough &epsilon;. This shows that (2p/q,2p/q+&epsilon;) is contained in the interior of U<sub>K</sub> and, as such 2p/q are dense, the interior of U<sub>K</sub> is a dense open subset of &#x0211D;. The Baire category theorem implies that $$U\equiv\bigcap_{K=1}^\infty U_K$$ is an uncountable dense subset of &#x0211D; and, by construction, for any &theta;&nbsp;&isin;&nbsp;U, limsup S<sub>n</sub>(&theta;)&nbsp;/&nbsp;f(n)&nbsp;&gt;&nbsp;K for each K.</p> <hr> <p>The further question was asked in the comment: are there <em>any</em> irrational &theta; for which S<sub>N</sub>&nbsp;=&nbsp;<em>O</em>(N<sup>x</sup>) for x&nbsp;&lt;&nbsp;1. The answer is yes. In fact this holds for <a href="http://en.wikipedia.org/wiki/Almost_everywhere" rel="nofollow">almost every</a> &theta; and every x&nbsp;&gt;&nbsp;1/2.</p> <p>The idea is to consider rational approximations to &theta;, |&theta;/2&nbsp;-&nbsp;p/q|&nbsp;&le;&nbsp;q<sup>-2</sup>. Then, there will be an integer 1&nbsp;&le;&nbsp;a&nbsp;&lt;&nbsp;q such that |1/2&nbsp;-&nbsp;[ap/q]|&nbsp;&le;&nbsp;1/(2q). So, |1/2-[a&theta;/2]|&nbsp;&le;&nbsp;1/q. With u() as above, it follows that u(n&theta;)&nbsp;+&nbsp;u((n+a)&theta;)&nbsp;=&nbsp;0 unless -2/q&nbsp;&le;&nbsp;n&theta;&nbsp;&le;&nbsp;2/q (mod 1). So, there is a lot of cancellation in S<sub>N</sub>(&theta;),</p> <p>$$\begin{array} \displaystyle \vert S_N(\theta)\vert &amp;\displaystyle \le a +\sum_{n=1}^N1_{\{-2/q\le n\theta\le 2/q{\rm\ (mod\ 1)}\}}\\ &amp;\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}\}}\\ &amp;\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 &theta; has <a href="http://mathworld.wolfram.com/IrrationalityMeasure.html" rel="nofollow">irrationality measure</a> less than &alpha; then, for large enough N, the rational approximation p/q can be chosen such that N<sup>1/2</sup>&nbsp;&le;&nbsp;q&nbsp;&le;N<sup>(&alpha;-1)/2</sup>, $$\vert S_N(\theta)\vert\le 2N^{(\alpha-1)/2}+10N^{1/2}.$$ In particular, if &theta; has irrationality measure 2 then $S_N=O(N^x)$ for every $x>1/2$. But, almost every real number has irrationality measure 2.</p>