Three-halves-free words (analogous to square-free)

Question

A square-free word is a string of symbols (a "word") that avoids the pattern $XX$, where $X$ is any consecutive sequence of symbols in the string. For alphabets of two symbols, the longest square-free word has length $3$. But for alphabets of three symbols, there are infinitely long square-free words, due to Thue.

Define a three-halves-free word as one that avoids the pattern $XYX$, where $|X|=|Y|$. Another view is that these words avoid $Z(\frac{1}{2}Z)$, i.e., $Z=XY$ with $X$ and $Y$ the same length. So $Z$ has even length, and we want to avoid immediately following with the first half of $Z$.

For an alphabet of two symbols, $0$ & $1$, here are the three-halves-free words of length $5$: \begin{eqnarray*} &(0, 1, 1, 0, 0)\\ &(0, 0, 1, 1, 0)\\ &(1, 1, 0, 0, 1)\\ &(1, 0, 0, 1, 1) \end{eqnarray*} All the $28$ other length-$5$ words fail. E.g., $(0,1,0,1,0)$ fails because $(0,1,0)$ matches with $XYX=010$. But there are no three-halves-free words of length $\ge 6$. For example, extending $(0, 1, 1, 0, 0)$ with $0$ gives $(0, 1, 1, 0, 0, 0)$, matching $XYX=000$, and extending with $1$ gives $(0, 1, 1, 0, 0, 1)$, matching with $X=01$.

Q. Are there infinitely long words in three-letter alphabets that are three-halves-free?

If a word has a square $ZZ$ with $|Z|$ even, then it has a three-halves pattern. If a word is square-free, it may not be three-halves-free. For example, both $(1,0,1)$ and $(0,1,2,1,0,1)$ are square-free. And the square-free infinite word A029883 $$ (1, 0, -1, 1, -1, 0, 1, 0, -1, 0, 1, -1, 1, 0, -1, \ldots ) $$ is not three-halves-free: e.g., $(-1,1,-1)$ and $(-1,0,1,0,-1,0)$ are three-halves patterns.

Answer 1

(Not a real answer, just a conjecture)

Let $w$ be the Pansiot word on $4$ letters defined here :
J.J. Pansiot, A propos d'une conjecture de F. Dejean sur les répétitions dans les mots, Discrete Applied Mathematics Volume 7, Issue 3, March 1984, Pages 297–311
in French, or also in
J. Moulin Ollagnier, Proof of Dejean's conjecture for alphabets with 5, 6, 7, 8, 9, 10 and 11 letters, Theoretical Computer Science, Volume 95, Issue 2, 30 March 1992, Pages 187–205.
This word proves Dejean's Conjecture for $4$ letters, that is:
it avoids fractional repetitions of exponent greater than $7/5$, and so it is also three-halves-free.

$$w=abcdbadcbdacdbcadcbacdabdcadbcdacbadcabdacdbadcbdabcadbacdab...$$

Conjecture Theorem

Let $h(a)=aabbaccabc$, $h(b)=aacbacbacc$, $h(c)=abbaaccbbc$, $h(d)=abcaacbbcc$.

Then $h(w)$ is a three-halves-free word on $3$ letters.

I checked up to size 412030. I do not tried to prove the result, but maybe the proof is simple and "standard" (suppose that the image has a three-halves, then prove that the pre-image has a three-halve).

edit: The proof is easy. $h$ is $10$-uniform and is synchronizing, that is for every $x,y,z\in\{a,b,c,d\}$, $h(x)$ is not a proper infix of $h(yz)$. Thus, if a factor $XYX$ of $h(w)$ is a three-halve, then either $XYX$ is small (of size at most $18\times 3$), or $\vert X \vert = \vert Y \vert$ is a multiple of $10$. There are only a finite number of "small" factors to check.
Now, if we are in the second case, and if $\vert X \vert$ if big (at least $42$), then $XYX$ has a unique de-substitution in $w$, and $w$ has a factor $X'Y'X'$ with $\vert Y' \vert / \vert X' \vert > 2/5$. Thus $w$ has a repetition of exponent greater that $7/5$, and we have a contradiction with the fact that $w$ is a Dejean word (i.e. it is $7/5+$-free).

Answer 2

A stronger property is true for four-letter alphabets. That is, in Words without near-repetitions, Currie and Bendor-Samuel prove that there is an infinite word $\omega$ over a four-letter alphabet such that whenever $XYX$ occurs as a subword of $\omega$, $|Y| > |X|$. They also prove that there is no infinite word over a three-letter alphabet with this stronger property.

Answer 3

Note: This is an extended comment, not a full answer.

I don't know about you, but I didn't start out with any good intuition about the answer to the question. I decided to do some computer experiments/visualization.

I wrote some code in Prolog which generates square-free and three-halves-free words over a given alphabet. I don't usually use Prolog for anything, but this seemed like the sort of problem that it's very well suited to. Source code and an interactive environment is available here. (Please comment if it doesn't work, the link is dead, etc.) Please experiment on your own too!

The query below generates the three-halves-free words of length 5 over the alphabet x,y. In the code I called it "sandwich-free" rather than "three-halves-free".

?- sandwich_free(L,[x,y],5).
L = [x, y, y, x, x] ;
L = [x, x, y, y, x] ;
L = [y, y, x, x, y] ;
L = [y, x, x, y, y] ;
false.

"?-" is the prompt; the next four lines are the results, and "false" indicates that there are no more answers. (The order of the results is lexicographic, if you read each result from right to left.)

If you ask for the sandwich-free words of length 6 over the same alphabet, you get 0 results:

?- sandwich_free(L,[x,y],6).
false.

Here's a sandwich-free word of length 500 over a 3-letter alphabet:

?- sandwich_free(L,[x,y,z],500).
L = [y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, z, x, y, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, y, x, x, z, z, x, y, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, z, x, x, y, y, x, z, y, x, x, y, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x]
...

You can ask for the sandwich-free words of any length over a given alphabet:

?- sandwich_free_peano(L,[x,y],N).
L = [],
N = zero ;
L = [x],
N = s(zero) ;
L = [y],
N = s(zero) ;
L = [x, x],
N = s(s(zero)) ;
L = [y, x],
N = s(s(zero)) ;
L = [x, y],
N = s(s(zero)) ;
L = [y, y],
N = s(s(zero)) ;
L = [y, x, x],
N = s(s(s(zero)))
...

(Technical limitations in Prolog required me to write a separate version of sandwich_free using Peano numerals, when you're passing in a number not already instantiated as a constant.)

You can also use it to check whether a given list is sandwich-free:

?- sandwich_free_peano([x,y,z,z,y],[x,y,z],_).
true ;
false.

(The answer is true; false just indicates no more answers.)

Here's a plot of length vs. the number of square-free and sandwich-free words of that length over a 3-letter alphabet. The growth appears to be exponential:

The query which generated the data points was

?- numlist(0,23,L),maplist(how_many_sandwich_free_alphabet_3,L,XS).

The data points on the graph are:

• Square-free: 1, 3, 6, 12, 18, 30, 42, 60, 78, 108, 144, 204, 264, 342, 456, 618, 798, 1044, 1392, 1830, 2388, 3180, 4146, 5418 (OEIS A006156)
• Sandwich-free: 1, 3, 9, 18, 36, 72, 108, 180, 288, 432, 648, 1008, 1548, 2376, 3636, 5400, 8172, 12276, 17892, 26532, 39492, 58428, 86688, 128592 (not in the OEIS at this time)

I find this compelling evidence that there are arbitrarily long three-halves-free words, indeed exponentially many as a function of length. It also seems very likely that infinitely long three-halves-free words exist.

---

Edit:

Here's some interesting new data: Say that a sandwich-free word is "extensible" if you can add one more letter to the front of it to get another sandwich-free word. Most sandwich-free words are extensible. An example of one that is not:

_, y, y, x, x, y, z, z, x, x, z, y, y, x, x

Try to fill in the blank at the front.

More generally we can talk about "$k$-extensible" sandwich-free words, by which I mean "$k$-extensible but not $(k+1)$-extensible". Now here's a plot of how many non-extensible and 1-extensible words there are of particular lengths:

(Data: 1, 3, 9, 18, 36, 72, 108, 180, 288, 432, 648, 1008, 1548, 2376, 3636, 5400, 8172, 12276, 17892, 26532, 39492, 58428, 86688, 128592, 190512, 282492, 418680, 620208, 919044, 1362456, 2012940; 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 72, 72, 144, 396, 252, 396, 720, 1044, 1440, 2376, 3456, 5040, 7524, 11088, 16272, 26604, 36864; 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 36, 36, 36, 72, 108, 180, 720, 540, 468)

Answer 4

Also not an answer, but may be useful.

A somewhat similar kind of word is mentioned at the end of section 1.5 of Salomaa: Jewels of Formal Language Theory:

There is an infinite word over a 3-letter alphabet such that every "sandwich" $XYX$ (with $X$ nonempty) in the word is fairly meaty, viz., $|Y|\ge\frac13|X|$. Also, $1/3$ is sharp here as a level of meatiness: starting at length 39 every word must contain a sandwich no more meaty than that (which incidentally is anecdotal evidence that we have to look at fairly long words before drawing any conclusions in this area).

So while you're asking whether there is an infinite imbalanced sandwich word ("balanced" meaning that the meat is just as thick as each bun), this shows there is an infinite meaty sandwich word.

Answer 5

This is not an answer, but it may help.

According to A generalization of repetition threshold by Lucian Iliea, Pascal Ochemb, and Jeffrey Shallit (Theoretical Computer Science, Volume 345, Issues 2–3, 22 November 2005, Pages 359–369)

Brandenburg [3] and (implicitly) Dejean [6] considered the problem of determining the repetition threshold; that is, the least exponent $\alpha=\alpha(k)$ such that there exist infinite words over $\Sigma_k$ that avoid $(\alpha+\epsilon)$-powers for all $\epsilon>0$. Dejean proved that $\alpha(3)=\frac74$.

(Dejean's paper is in French, and I can't read French.)

As Bjørn Kjos-Hanssen points out in a comment, the result I cite settles the case of power-free words that avoid all powers greater than or equal to 3/2, but Joseph O'Rourke's question is asking for 3/2-free words. (It is possible for a word to be 3/2-free yet contain powers greater than 3/2, for example, the word $00$ has a square and yet is 3/2-free.)