Sturmian subword whose reverse is not a subword

Question

Let ${\cal L}_n$ be the set of all subwords of length $n$ of a biinfinite Sturmian sequence, induced by a rotation coding with irrational angle $\theta$.

Take a word $w \in {\cal L}_{2^n}$ and write it as the concatenation of its two halves: $w=w_1w_2$. Say that $w$ is bad if $w_1 \neq w_2$ and $w_2w_1 \in {\cal L}_{2^n}$.

For example there is always a bad word for $n=1$: the word $ab$, because $ab, ba \in {\cal L}_2$.

I want to know whether there is a value of $\theta$ for which there is no bad word for $n \geq 2$.

For example, using a computer, I find:

• for a small $\theta \approx 0.015$ there are some bad words for $n=2$, such as $abbb$;

• for the "golden" case $\theta=1/\phi^2 \approx 0.381966$, I found the first bad word for $n=3$, namely $abbabbab$;

• for $\theta=\sqrt{2}-1 \approx 0.4142136$, the first bad word occurs for $n=7$;

• for $\theta \approx 0.4548312$, I didn't find any bad word until $n=10$.

The smallest $n\geq 2$ for which there is a bad word seems to increase when $\theta$ increases from $0$ to $1/2$.

I have no reason to expect that there is no bad word for some value of $\theta$, but I ask this question because a positive answer would help me to solve a certain problem: I try to prove a property $P_n$ on ${\cal L}_{2^n}$ which satisfies $P_n \implies P_{n+1}$ if there is no bad word.

Update

I just think to a better question. Let $n(\theta)$ the smallest $n \geq 2$ for which there is a bad word in ${\cal L}_{2^n}(\theta)$. Does $n(\theta) \to \infty$ as $\theta \to 1/2$?

Answer 1

It seems that $n(\theta)$ should depend on the occurrence of some relatively long runs of 0s (and perhaps of 1s) in the decimal representation of $\theta$; at least, if there are no such runs, $n(\theta)$ should not exist.

To see this, let $w_k(\alpha)$ be the word of length $k$ defined as the Sturmian word for our $\theta$, but starting at position $\alpha$ of the circle. What does it mean that $w=w_1w_2$ is bad? We have $w_1w_2=w_{2^n}(\alpha)$ and $w_2w_1=w_{2^n}(\beta)$ for some $\alpha,\beta$. We definitely need that $\beta\approx \alpha+2^{n-1}\theta\pmod 1$ and $\alpha\approx \beta+2^{n-1}\theta\pmod 1$, but $\alpha\not\approx \beta\pmod 1$, so that $2^{n-1}\theta\approx 1/2\pmod 1$. This already settles the question about the limit as $\theta\to1/2$ in the affirmative.

Which approximation error suffices for the formulas from the previous paragraph? Consider the numbers $k\theta\mod 1$ for $k=1,\dots,2^{n-1}$. They split the unit circle into seveal arcs, and it is well-known that these arcs have at most 3 distinct lengths $x_n$, $y_n$, and $z_n=x_n+y_n$ ($z_n$ may be absent). Then the error of the approximation should definitely be not greater than $z_n$. So, if $2^{n-1}\theta\mod 1$ is always separated from $1/2$, then $n(\theta)$ should not exist.

To construct such $\theta$, it suffices to write its binary notation using, say, $01$ and $011$ in an aperiodic manner (perhaps, some more careful start is needed).

Sorry for some vagueness; hope it is clear what is happening.

Answer 2

Yes, I think so. If $\theta\approx \frac 12$ (say $\theta=\frac 12-\epsilon$), then a $\theta$-Sturmian word looks like $01010101010\textbf{0}1010101010101010101010101010\textbf{0}101010101010$. The "extra 0's are roughly $1/(2\epsilon)$ apart. If $2^n<1/\epsilon$, then a word of length $2^n$ contains either no extra $\textbf{0}$ (in which case the two halves are the same, so the word does not satisfy the definition of bad) or one extra $\textbf{0}$ (in which case the reversed halves do not form a Sturmian word e.g. $01010101010\textbf{0}1010$ reversed is $10\textbf{0}1010010101010$, which has two extra 0s). So the first "bad" word satisfies $2^{-n}\lesssim \epsilon$.