MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

First, a bit of notation. If we have an arithmetic progression $a, a+k, a+2k, \ldots, a+(n-1)k$ we will call $k$ the distance, and $n$ the length.

While trying to find an example for a paper I'm writing in ring theory, I was led to ask the question: Is there a sequence of 0's and 1's for which if there is an arithmetic progression in the sequence which is constantly 0 (or 1), is there a bound for the length in terms of the distance?

I found that the answer is yes, and the Thue-Morse sequence works. Modifying the ideas of Corollary 2 in "Thue-Morse at multiples of an integer" (available here), we see that the length of a constant arithmetic progression on the Thue-Morse sequence of distance $k$ is bounded by $32k^3$.

So, here are my questions for you experts.

(1) Is there an easier sequence where one can prove this is true (possibly with citation in the literature)?

(2) If not, is there a straightforward citation for this fact for the Thue-Morse sequence? (The reference I gave above works for arithmetic progressions which start near the front of the sequence. But to get an arbitrary arithmetic progression, you need to increase the bound given in the paper a little, and also give a supplementary argument.)

share|cite|improve this question
up vote 6 down vote accepted

How about this? Fix your favourite irrational number $\phi$. I like the golden mean. Let $x_s=[ s\phi ] - [(s-1)\phi]$ ($[t]$ means the integer part of $t$). These sequences are called Sturmian sequences.

Of course $x_s$ is 1 if and only if $s\phi \bmod 1$ lies in $[0,\phi)$.

Now for any $a$ and $k$, you're asking whether $(a+jk)\phi\bmod 1$ lies in $[0,\phi)$ for all $0\le j < n$ or lies in $[\phi,1)$ for all $0\le j < n$.

Provided $S_{k,n}:=\lbrace jk\phi\bmod 1\colon 0\le j < n\rbrace$ is $\delta$-dense in the circle, where $\delta=\min(\phi,1-\phi)$ this cannot happen.

This means you can "compute" the maximum length as a function of $k$, namely $L_{max}(k)=\max\lbrace n\colon S_{k,n}$ is not $\delta$-dense$\rbrace$. In the case of golden mean, $L_{max}(k)$ grows linearly in $k$, but I can't write down the proof of that here (the margin is too small).

Some more stuff as requested by OP

Claim: If $d(k\phi,\mathbb Z/6)=\epsilon$ then $L_{max}(k)<1/\epsilon$.

Proof: Let $k\phi=a/6+\epsilon$, where $|\epsilon|<1/12$. Notice that $\delta<1/3$. If $a=0$, then $1/\epsilon$ steps produces an $\epsilon$-dense subset of the circle. If $a=1$ or 5, then 12 steps produces a $\delta$-dense subset of the circle. If $a=3$, then $1/\epsilon$ steps produces a $2\epsilon$-dense subset of the circle [because $2k\phi$ is $2\epsilon$-close to $\mathbb Z$] and if $a=2$ or 4, then $1/\epsilon$ steps produces a $3\epsilon$-dense subset of the circle.

Next notice $d(k\phi,\mathbb Z/6)\le d(6k\phi,\mathbb Z)$. From Hardy and Wright (5th ed, Theorem 194) plus a simple argument you get $d(k\phi,\mathbb Z)\le 1/(Ak)$ for a suitable $A$.

Combining these ingredients gives the linear growth of $L_{max}$.

share|cite|improve this answer
If the margin is too small, how about giving me a reference? :-) – Pace Nielsen Feb 8 '12 at 19:56

Your Answer


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.