[Math] Two questions from combinatorics on words

co.combinatoricscombinatorics-on-wordscomputer sciencediscrete mathematics

Question 1. Assume that an infinite word $u\in\{0,1\}^{\mathbb Z}$ is not balanced. Is it true that there exists a finite 0-1 word $w$ such that $0w01w1$ or $1w10w0$ is a factor of $u$? Is it true that both are? (Perhaps, with different $w$.) – answered in the negative

Question 1 (modified). Assume that an infinite word $u\in\{0,1\}^{\mathbb Z}$ is not balanced. Is it true that there exists a finite (possibly, empty) 0-1 word $w=w_1\dots w_k$ such that $0w_1\dots w_k01w_k\dots w_11$ or $1w_1\dots w_k10w_k\dots w_10$ is a factor of $u$? Is it true that both are? (Perhaps, with different $w$.) – ANSWERED by Wolfgang

Question 2. Assume now that $u\in\{0,1\}^{\mathbb Z}$ is balanced and aperiodic (i.e., Sturmian). Is it true that for any $n\ge1$ there exists a finite 0-1 word $w=w_1\dots w_k$ with $k\ge n$ such that $w_1\dots w_k01w_k\dots w_1$ or $w_1\dots w_k10w_k\dots w_1$ is a factor of $u$? Again, is it true that both are (with different $w$)? – ANSWERED by domotorp

I am familiar with Lothaire's famous monograph "Algebraic Combinatorics on Words" but couldn't find these results there.

EDIT. Here's what is meant by `balanced'. For a finite 0-1 word $w$ let $\delta(w)$ denote the number of 1s in $w$. A 0-1 word $w$ (finite or infinite) is called balanced if for any $n\ge1$ and any two factors $u$ and $v$ of $w$ of length $n$ we have $|\delta(u)-\delta(v)|\le 1$.

For instance, $0100101$ is balanced whilst $101000$ is not, since $\delta(101)=2$ and $\delta(000)=0$.

Best Answer

I think Question 2 is true and the proof is as follows. Every Sturmian word is equivalent to the cutting sequence of an irrational number (except, I think, those that have only one extra digit compared to a rational number, for which your statement is true). If you have a line $ax$ that goes through the origin, then its cutting sequence in both directions is the same, i.e., they are each other's reverse. Similarly, whenever the line goes "very close" to a grid point, the part before it will be the reverse of the part after it for a long time. Close to the grid point, you have the 01 or the 10. From Diophantine approximation, it follows that we can indeed achieve "very close" in both situations.

Related Question