# Two questions from combinatorics on words

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

• Would you mint posting the definition of balanced (or a link if it is very complicated)? Nov 30, 2013 at 20:26
• Daniel, it's done. Hope that helps. Nov 30, 2013 at 21:01
• Sorry, I don't have enough reputation to write a comment so I'm writing it into an answer. About the second question, you can replace "or" with "and", since Sturmian words contain all the reversals of their factors. Dec 5, 2014 at 21:45

## 7 Answers

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.

To produce a counterexample for question 1, you can consider sequences with few $01$ and $10$ subsequences, such as

$...00000.0110000111111110000000000000000111...$

Each $01$ is between a patch of $0$s of length $2^n$ and a patch of $1$s of length $2^{n+1}$. For this to be in the middle of $0w01w1$, either $w$ is all $1$s or it is not. If so, then there would be an isolated $0$ which doesn't happen. If not, then there would be at least $2^{n+1}$ $1$s to the right, but there are fewer than $2^{n}$ $1$s to the left. Similarly, each $10$ is between a subsequence of $1$s of length $2^n$ on the left and $2^{n+1}$ $0$s on the right. For this to be in the middle of $1w10w0$, $w$ can't be all $0$s, but then it must have length at least $2^{n+1}$, and then the first $1$ of $1w10w0$ would be too far to the left.

• Douglas, thanks. I have modified this question replacing $w$ with its reverse $\widetilde w$ - hope there are no counterexamples for this version. Dec 1, 2013 at 0:35

In case of Question 1 (modified), it might happen that both are not factors, e.g., consider the sequence ...1111010000....

• But $111010=1w10\widetilde w0$ is a factor, with $w=1$. Dec 2, 2013 at 22:59
• Yes, I mean that it might happen that we do not have both forms as factors but only one of them. Dec 2, 2013 at 23:12
• Sorry, I misunderstood your answer. Indeed, you are right. As a matter of fact, I can see how your sequence can be used to construct uncountably many counterexamples. Dec 2, 2013 at 23:40

I'll prove that the modified question 1 has an affirmative answer by showing conversely that an infinite word $u\in\{0,1\}^{\mathbb Z}$ which avoids all $0w01\widetilde w1$ and $1w10\widetilde w0$ (call these factors forbidden) is necessarily balanced.

If $u\ne...0101...$, there is wlog a factor 00. (Otherwise, swap all 0's and 1's). For $k\ge1$, define a $k$-patch (or $p_k$ for short) as a 'maximal' run of $k$ consecutive zeros in $u$, i.e. it is preceded and followed by a 1. As 0011 and 1100 are forbidden, these 1's are isolated if $k\ge 2$, so each $10_k1$ (where indices mean repetition) is preceded and followed by patches $p_a$ and $p_b$, and the forbidden factors imply $k-1\le a,b\le k+1$. The same holds trivially for $k=1$. So two 'neighboring' patches have a difference of length of at most 1.
Now suppose that there is a $k\ge 1$ such that $u$ contains a $p_{k-1}$ and a $p_{k+1}$. (It makes sense to define a $0$-patch $p_0$ as the empty set in the middle of a factor 11 forcing those two 1's.) Suppose they are closest possible to each other, i.e. between them there is only a number, say $n$, of $k$-patches (each separated by an isolated 1).

So $u$ has a factor $$10_{k-1}\overbrace{10_k\cdots10_k}^n10_{k+1}1$$ (or the other way round, in which case inverse the whole sequence wlog). Which entries must follow to the right? In fact we must have

$$10_{k-1}\overbrace{10_k\cdots10_k}^n\underbrace{10}_{(x)}0_{k-1} \underbrace{01}_{(y)}\overbrace{\color{red}{0_k1\cdots0_k1}}^{n-1}\color{red}{0_k}$$ because each red 0 is forced by the fact that the string 01 marked by $(y)$ must not be the center of a forbidden factor, and each red 1 is forced by the fact that the string 10 marked by $(x)$ must not be the center of a forbidden factor. But due to the initial 1, the whole string above is a forbidden one with center $(x)$. Contradiction.

So there is a $k$ such that $u$ consists only of patches of lengths $k$ and $k+1$, separated by isolated 1's. It is easy to see that such a $u$ is balanced. qed.

EDIT: this was wrong, but the proof can be rescued by the following completion.

Suppose $u$ is not balanced. Then take the smallest $r$ such that there are two factors $s$ and $t$ of length $r$ where $t$ has 2 more 1's than $s$. So $s$ starts and ends with $0_{k+1}$ and $t$ starts and ends with $10_k1$.

Let $n$ be the number of interior 1's of each $s$ and $t$. Suppose there are $i$ instances of $p_k$ and $j$ instances of $p_{k+1}$ with both $i,j>0$, then the interior of $t$ must have the same numbers of each (note that $s$ and $t$ have the same number of 1's in their interior).

EDIT after the last remark of Harry Altman (the one starting with "Yay") : I have found a way to repare the proof again, making it at the same time more elegant.

We'll now introduce the process of reduction: put $a^0=1,b^0=0$ and $u^0=u$. For $\nu=0,1,...$ proceed as follows: As the $a^\nu$-$b^\nu$-word $u^\nu$ contains no forbidden factors (in terms of $a^\nu$ and $b^\nu$), the boldface statement above about 'neighboring' patches applies also to $u^\nu$, so there must be a $k^\nu$ such that $u^\nu$ is composed either
(1) of runs $a^\nu_{k^\nu}$ and $a^\nu_{k^\nu+1}$, interspearsed by isolated $b^\nu$'s, or
(2) of runs $b^\nu_{k^\nu}$ and $b^\nu_{k^\nu+1}$, interspearsed by isolated $a^\nu$'s.

Then denote in case (1) $a^{\nu+1}:=b^\nu a^\nu_{k^\nu}, b^{\nu+1}:=b^\nu a^\nu_{k^\nu+1}$, and
in case (2) $a^{\nu+1}:=a^\nu b^\nu_{k^\nu}, b^{\nu+1}:=a^\nu b^\nu_{k^\nu+1}$,
further define $u^{\nu+1}$ as the sequence $u$ written as a $a^{\nu+1}$-$b^{\nu+1}$-word. This reduction can be traced back, and it is easy to see that that $u^{\nu+1}$ cannot contain $a^{\nu+1}$-$b^{\nu+1}$-words as forbidden factors. (Looking at the $a^{\nu+1}b^{\nu+1}$ or $b^{\nu+1}a^{\nu+1}$ in the center of a forbidden factor, it is clear that this gives rise to a forbidden factor in $u^\nu$, which is excluded.)

$s^\nu$ and $t^\nu$ can be written as factors of $u^\nu$, one of them starts and ends with $a^\nu$’s, the other one of them starts and ends with $b^\nu$’s. By the minimality of $s$ and $t$ and the fact that they have the same number of letters, it is easy to see that, up to an initial or final isolated letter (like in the $\nu=0$ case : a missing 1 before $s$ and the final 1of $t$), they must factor also in terms of the ‘new letters’ $a^{\nu+1}$’s and $b^{\nu+1}$, and their numbers of occurrences in the interior must again coincide. (To illustrate this, think of $s=bbbabbbabbabbabbb$ and $t=abbabbabbabbbabba$ omitting the $\nu$’s. Here $k=2$, as there are runs in $b$ of lengths 2 and 3.. Then the reduction would be $abbb\to b$ and $abb\to a$ with $s$ (or rather $as$) $\to bbaab$ ant $t$ (or rather $t$ with the final $a$ omitted) $\to aaaba$.)

It is clear that $s^{\nu+1}$ has less letters $a^{\nu+1}$ and $b^{\nu+1}$ than $s^\nu$ has letters $a^\nu$ and $b^\nu$, and that by minimality, one of them starts and ends with $a^{\nu+1}$’s, the other one of them starts and ends with $b^{\nu+1}$’s. Iterating this reduction, we must thus come to a point where (omitting again the $\nu$’s) either $s$ or $t$, say $s$, consists only of letters of the same kind, say $a$. But at that moment, $t$ must have the form $baa\cdots ab$, thus it has a run of two less $a$’s. Contradiction.

We conclude that the initial $s$ and $t$ cannot exist, thus $u$ is balanced. Qed.

• Wolfgang, I like your idea about patches, but I don't see how the fact that 0011 and 1100 are forbidden can lead to this. Take, for instance, the periodic sequence with period 00101101 - it contains both 00 and 11 as factors but neither 0011 nor 1100. Dec 4, 2013 at 14:25
• Also, the last sentence of your comment is somewhat perplexing. Surely, there are plenty of unbalanced words which are concatenations of the blocks $10_k$ and $10_{k+1}$. For instance, the set of all such words has an exponential growth whilst the number of balanced words is known to grow polynomially. Dec 4, 2013 at 14:40
• for your first comment: 00101101 is also forbidden. I have said that the argument 0011 and 1100 only applies for $k\ge 2$, of course. But I realize that you are right with your second comment. Sure enough I missed that e.g. factors 10101 and 00100 might co-occur. What a pity! Dec 5, 2013 at 7:35
• I think I have been able to rescue my proof! Please check. Dec 5, 2013 at 13:42
• @Harry's 2nd comment: Thank you for checking that. You are absolutely right, this is (was) still a flaw. Again it's rescuable, see my last edit. I am quite sure the proof is waterproof now. Dec 6, 2013 at 9:11

Too late, but here's my proof that the answer to Question 1 (modified) is yes.

If $u\in\{0,1\}^\mathbb{Z}$ is not balanced, there exists a palindrome $w$ such that $0w0$ and $1w1$ are factors of $u$ (see Prop. 2.1.3 in Lothaire 2); if $w$ is of minimal length $n$, then $u$ has at most $k+1$ factors of each length $k\leq n+1$ (Prop. 2.1.2). Moreover $\{0w0,1w1\}$ is the only imbalance among factors of length $\leq n+2$ in $u$. It follows that the set of factors of length $n+2$ is contained in $\{0w0,1w1\}\cup [w01]$, where [x] denotes the conjugacy class of $x$ (all of its cyclic shifts). Also, every factor of length $n+1$ except $0w$ and $1w$ are not right special, i.e., they always occur followed by the same letter.

From this we can derive that there exists $m\geq 0$ such that every occurrence of $0w0$ is followed by $(1w0)^m$ and every occurrence of $1w1$ is followed by $(0w1)^m$. If such $m$ is chosen to be maximal, then either $$0w0(1w0)^m1w1(0w1)^m=0(w01)^mw01w(10w)^m1$$ or $$1w1(0w1)^m0w0(1w0)^m=1(w10)^mw10w(01w)^m0$$ is a factor of $u$.

• Even if Wolfgang beat me to it, maybe someone might be interested in my proof. I know it is much denser; I suggest drawing the Rauzy graph for length $n+1$ to see it more clearly. Dec 5, 2013 at 23:38

For Question 1, it seems that the word $\dots 001001001001\,011011011011\dots$ has neither such factor.

• Ilya, thanks - that works. I have modified this question in the spirit of Question 2, this time hoping for the affirmative answer. Nov 30, 2013 at 23:17

For Question 1, I believe the result you are looking for is the following by Dulucq and Gouyou-Beauchamps (1990).

A finite word $w$ over $\{0,1\}$ is not balanced (and so not a factor of a Sturmian word) if and only if it can be written $w = x0u0y1\tilde{u}1z$ or $w = x1u1y0\tilde{u}0z$ for some words $u, x, y, z$ (where $\tilde{u}$ is the reverse of $u$).

• Amy, I am not sure how this helps unless $y$ is the empty word - in which case $0u01\tilde{u}1$ or $1u10\tilde{u}0$ is indeed a factor of $w$. Could you elaborate, please? Dec 4, 2013 at 3:51
• Also, I couldn't find the result in question in the paper you mention. Could you give the exact reference, please? Dec 4, 2013 at 14:36
• The result is implicitly proved in Section 3 of the paper that I mentioned. Alternatively, see Problem 2.1.4 on page 90 of the 2nd Lothaire book "Algebraic Combinatorics on Words". By this result, a (finite or infinite) word over $\{0,1\}$ is not balanced if and only if it contains a factor of the form $0u0y1\tilde{u}1$ or $1u1y0\tilde{u}0$ for some (possibly empty) finite words $u, y$. So it seems to me that the answer to your modified Question 1 is NO, unless you modify it to include the possibility of a non-empty word between the 1 & 0 (or 0 & 1) in the middle ... Dec 4, 2013 at 16:22
• And here's a possible counterexample to your modified Question 1: $\cdots 010101(00100010101)101010\cdots$ which is not balanced because of the "bracketed" factor that takes the form $0u0y1\tilde{u}1$ with $u=010$ and $y=0$, for instance. It also contains the non-balanced factor $00010101$ with $u=0$ and $y=10$. I think you'll find, however, that it does not contain a factor of the form $0u01\tilde{u}1$ or $1u10\tilde{u}0$. Am I right? Dec 4, 2013 at 16:46
• Amy, thanks. I remember I've seen it somewhere, and now I know where. A non-empty word in the middle is not an option, I'm afraid. However, I don't see immediately why their characterization implies the NO answer. I still think the answer is YES, it's just that this particular result doesn't help, that's all. ;) Dec 4, 2013 at 16:48