15
$\begingroup$

Apologise in advance if this problem isn't research-level (I'm quite certain it isn't). It's just I found it quite intriguing because it turned out to be much more subtle than it appeared at my first glance. Also, this problem didn't get an answer so far (nor much attention) from MSE, so I decided to post it here in hopes I can get some valuable insights. Cheers!

Here goes the original post from MSE.

Let $b=\dfrac{\sqrt{5}-1}2$ and $a_n:=(-1)^{[nb]\bmod 2}$ where $[\cdot]$ denotes the floor function. Then is $\sum a_n$ bounded?

As far as I know $nb\bmod 2$ is equidistributed in $[0,2]$ and so as $n$ gets large there will be about half of indices in $\{1,2,\cdots,n\}$ that correspond to $1$ and the other half to $-1$. This doesn't help much though because what it says is basically $\sum a_n\in o(n)$. By testing on computer softwares, it seems to be $O(\log n)$ (but of course any such "test" is worthless). But I don't know what else I can do.

Also, is there anything special about $b$ besides being an irrational real number (or, being the golden ratio)? What if I replace it by, say, $\pi$?

PS: A comment suggested a probable connection with the 1D random walk, but I really can't see a possible way to formulate such a connection beyond the intuitive level.

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ A friend also hinted at using continued fractions, saying he proved it is not bounded some time ago but apparently have forgot and lost all the details. $\endgroup$
    – Vim
    Commented Apr 11, 2017 at 15:58
  • 17
    $\begingroup$ You conclude "not much attention" in MSE after only 12 hours? $\endgroup$
    – Gerald Edgar
    Commented Apr 11, 2017 at 16:30
  • 2
    $\begingroup$ To see the computer-suggested bound $\sum_{n\leq X} a_n\ll O(\log{X})$, first write $X$, which we may assume is even (since we only lose $O(1)$ by pulling off the last term) greedily as $2\sum_{i\leq k} F_{n_i}$, with $n_i\not\equiv 0\pmod{3}$ (i.e., all $F_{n_i - 1}$ odd) --- here the $F$'s are Fibonacci numbers in increasing order, and by 'greedily' I mean take the largest one less than $X$ and repeat. Note that in general the largest $F_m\leq X$ with $m\not\equiv 0\pmod{3}$ is $\gg X$, so that $k\ll \log{X}$. $\endgroup$
    – alpoge
    Commented Apr 11, 2017 at 19:35
  • $\begingroup$ Next write $Y_j := \sum_{i\leq j} F_{n_i}$, so that $Y_0 = 0$ and $2Y_k = X$. Note that $Y_i\ll F_{n_i}\leq Y_i$. Now our sum is $\sum_{n\leq X} a_n = \sum_{i\leq k} \sum_{2Y_{i-1} < n\leq 2Y_i} a_n$, so it suffices to show that each of the inner sums is $O(1)$. Note that the $i$-th inner sum is over an interval of length $2F_{n_i}$. So we'll use the approximation $b = \frac{1}{\phi} = \frac{F_{n_i-1}}{F_{n_i}} + O(F_{n_i}^{-2})$, which holds by e.g. Binet. Hence for $2Y_{i-1} < m\leq 2Y_i$, we have that $mb = \frac{m F_{n_i -1}}{F_{n_i}} + O(Y_i^{-1})$, since again $F_{n_i}\asymp Y_i$. $\endgroup$
    – alpoge
    Commented Apr 11, 2017 at 19:37
  • $\begingroup$ It follows that $\lfloor mb\rfloor = \lfloor \frac{m F_{n_i -1}}{F_{n_i}}\rfloor$ except for at most $O(1)$ exceptions in this interval. Indeed, if there is an exception $m$, then any other exception $m'$ must satisfy (on taking differences) $\left\{\frac{(m'-m) F_{n_i - 1}}{F_{n_i}}\right\}\ll F_{n_i}^{-1}$, and so $(m'-m) F_{n_i - 1}$ lies in one of $O(1)$ congruence classes modulo $F_{n_i}$. Since $(F_{n_i - 1}, F_{n_i}) = 1$ it follows that $m'$ must lie in $O(1)$ many congruence classes modulo $F_{n_i}$, and now note that the interval was only of length $2F_{n_i}$ in the first place. $\endgroup$
    – alpoge
    Commented Apr 11, 2017 at 19:37

2 Answers 2

Reset to default
17
$\begingroup$

The sequence $\sum a_n$ is unbounded.

This is a consequence of a general result from Kesten,
On a conjecture of Erdös and Szüsz related to uniform distribution mod 1, Acta Arithmetica (1966). The proof is not very long but quite computational, using properties of continued fractions.

Theorem Let $\xi \in [0,1]$, $0\leq a < b \leq 1$, denote by $N(M, \xi, a,b)$ the number of integers less than $M$ such that $a \leq \{k\xi\} \leq b$. Then $N(M,\xi, a,b) - M(b-a)$ is unbounded if $b-a$ is rational and $\xi$ is irrational.

You are interested in the $1/2$ discrepancy of an irrational rotation of the circle. Note that from the Denjoy-Koksma inequality, there is a sequence $q_n$ such that $\sum_{k= 0}^{q_n-1} a_k$ is bounded by $2$. The sequence exists for any irrational rotation of the circle and is given by the denominators of the partial fraction decomposition of the rotation number. For the golden ratio, these numbers are given by the Fibonacci numbers.

The golden ratio is a bit special because its decomposition in continued fraction is just $[1,1,1...]$ so it is badly approximated by the rational numbers. So the computation of Kesten should be simpler in that case.

EDIT: the theorem is also mentioned shortly in the book of Kuipers and Niederreiter, "uniform distribution of sequences". Some additional references can be found in the notes of chapter 2, section 3 p128.

Improve this answer
$\endgroup$
1
8
$\begingroup$

I've decided to upgrade my comments and make an answer out of them, even though I'm just addressing the (easier) variant suggested by the OP at the end of the post, where we replace the golden ratio by other numbers $b$.

If $b$ can be well approximated by rationals, then it's easy to see that the sum cannot stay bounded: More precisely, suppose there are infinitely many (reduced) fractions with odd denominators $q$ such that $$ \left| \frac{b}{2} - \frac{p}{q} \right| = o(q^{-2}) $$ (the golden ratio is not of this type; I can only get $O(q^{-2})$, and in fact it is usually thought of as the number with the worst rational approximations).

The shift by $p/q$ is periodic with odd period, so gives a bias of at least $1$ to one of the two halves of the circle. Also, if I keep a distance $\gtrsim 1/q$ to the endpoints of the intervals, then a perturbation by $\le \delta/q$ of the initial point will not change anything.

Now I can just wait until $nb$ is close to such an initial point, and the approximation of $b/2$ by $p/q$ will be justified during a time interval of length $kq$, for any $k\ge 1$ (because $kq\cdot o(q^{-2})\ll 1/q$). So I pick up an overall bias of at least $k$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .