19
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ “If a word has a square, it has a three-halves pattern” — really? Aren’t AA, or less trivially AABC and ABCABC, counterexamples? Or am I misunderstanding something? $\endgroup$ Apr 5, 2015 at 11:29
  • 9
    $\begingroup$ Check out Zimin words. $\endgroup$ Apr 5, 2015 at 14:45
  • 3
    $\begingroup$ @TheMaskedAvenger: Thanks! I see that $ABA$ (the second Zimin word) is unavoidable, but the difference in my case is that $|A|=|B|$. $\endgroup$ Apr 5, 2015 at 18:19
  • 2
    $\begingroup$ Good point. I know of literature that talks about a/b words for some value of a/b at least 5/2. Any literature that might address your problem should have Zimin in the bibliography if not in the text. $\endgroup$ Apr 5, 2015 at 18:37
  • 2
    $\begingroup$ Not that it's very much related, but such $3/2$-words remind me of writing the longest element in a finite Coxeter system as $w_\circ = (c_L c_R)^{h/2}$ where $S = L \sqcup R$ is a bipartition of the simple generators $S$ into pairwise commuting elements, $c_L c_R$ is a bipartite Coxeter element, and $(c_L c_R)^{h/2}$ for odd Coxeter number $h$ is meant to be $(c_L c_R)^{(h-1)/2}c_L$. $\endgroup$ Apr 6, 2015 at 8:21

5 Answers 5

11
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ Elsevier link for the Ollagnier paper: link here. Here is his definition of exponent: "The exponent of the repetition $(p, e)$ is the ratio $|pe|/|p|$ of the lengths of $w-pe$ and $p$." $\endgroup$ Apr 9, 2015 at 17:11
  • $\begingroup$ Why is this answer accepted? As far as I can tell, this only discusses four-letter alphabets. $\endgroup$
    – aorq
    Apr 11, 2015 at 15:52
  • 3
    $\begingroup$ $w$, the word defined by Pansiot, is on a 4-letter alphabet. But $h(w)$ is a word on $\{a,b,c\}$. $\endgroup$
    – user38477
    Apr 12, 2015 at 19:38
  • 1
    $\begingroup$ Excellent! Thanks for addressing my question, and please forgive my failure to read carefully. $\endgroup$
    – aorq
    Apr 13, 2015 at 5:43
12
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ How is that property stronger? Doesn't Konig's tree lemma tell us that for a finite-alphabet, the property you state is equivalent to Joseph's? [I also read the paper, and was a bit confused by their argument in the three-letter alphabet case.] $\endgroup$ Apr 7, 2015 at 14:49
  • 2
    $\begingroup$ @PaceNielsen I don't quite see this. Konig's tree lemma says that it is sufficient to construct arbitrarily long words with a property to get an infinite word with the same property, but as far as I can see this property is stronger than Joseph's. That is, this property does not even allow occurrences of $XYX$ where $Y$ is short compared to $X$, while Joseph's property does. $\endgroup$
    – Tony Huynh
    Apr 7, 2015 at 15:11
  • 1
    $\begingroup$ Oh, I see now! That was silly of me to miss that. $\endgroup$ Apr 7, 2015 at 15:33
  • $\begingroup$ Very nice, Tony! Am I correct that their result has no direct implication for three-symbol alphabets? $\endgroup$ Apr 8, 2015 at 23:59
  • 2
    $\begingroup$ Thanks Joseph! Yes, you are correct that their result does not answer your question. The only implication is that one should not try to construct an infinite word over a three-letter alphabet with this stronger property. So if the answer is yes to your question, there will necessarily be occurrences of $X$ which are less than $|X|$ letters apart. $\endgroup$
    – Tony Huynh
    Apr 9, 2015 at 0:05
11
$\begingroup$

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:

Length vs. the number of square-free and sandwich-free words of that length over a 3-letter alphabet

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:

Length vs. the number of sandwich-free words, non-extensible sandwich-free words, and 1-extensible sandwich-free words, of that length over a 3-letter alphabet

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

$\endgroup$
9
  • 5
    $\begingroup$ Is there some obvious pattern among the lex-largest elements in these sets? $\endgroup$ Apr 5, 2015 at 23:02
  • $\begingroup$ Very cool that you used Prolog! Thanks for the phrase "sandwich-free"! I still prefer $3/2$'s-free, but your suggestion may win out. :-) $\endgroup$ Apr 5, 2015 at 23:45
  • 1
    $\begingroup$ I also played around a little with some code (in Haskell), and came to a similar conclusion. Indeed, I didn’t even manage to find a non-extendable sandwich-free word, i.e. a sandwich-free word with no sandwich-free extension, though my search was not exhaustive even for small lengths. Did you find any such? $\endgroup$ Apr 6, 2015 at 4:21
  • $\begingroup$ @PeterLeFanuLumsdaine Great question! The code is updated to include sandwich_free_not_extensible_peano and sandwich_free_not_extensible. According to the query ?- sandwich_free_not_extensible_peano(L,[x,y,z],_)., the smallest non-extensible sandwich-free word over x,y,z is 14 letters long; an example is [y, y, x, x, y, z, z, x, x, z, y, y, x, x]. $\endgroup$ Apr 6, 2015 at 7:30
  • $\begingroup$ @echinodermata: Surely that word remains sandwich-free if extended by z? Is there a typo, or am I missing something? $\endgroup$ Apr 6, 2015 at 9:25
10
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ "meaty sandwich" :-). $\endgroup$ Apr 6, 2015 at 11:19
  • $\begingroup$ Yes, but would "bread, spread, and filling" be $XYZX$, or $XYZYX$? $\endgroup$ Apr 7, 2015 at 6:59
8
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.