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

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.

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)

(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).