<figure><img src="image_1.png" /></figure>

HAL
open science

# Doubled patterns with reversal and square-free doubled patterns

Antoine Domenech, Pascal Ochem

<figure><img src="image_2.png" /></figure>

## To cite this version:

Antoine Domenech, Pascal Ochem. Doubled patterns with reversal and square-free doubled patterns. 2023. lirmm-03799694

HAL Id: lirmm-03799694

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03799694

Preprint submitted on 17 Oct 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Doubled patterns with reversal and square-free
doubled patterns

Antoine Domenech

ENS de Lyon, Lyon, France
antoine.domenech@ens-lyon.fr

Pascal Ochem

LIRMM, CNRS, Université de Montpellier
Montpellier, France
ochem@lirmm.fr

March 2, 2022

Abstract

In combinatorics on words, a word $w$ over an alphabet $\Sigma$ is said
to avoid a pattern $p$ over an alphabet $\Delta$ if there is no factor $f$ of $w$
such that $f = h(p)$ where $h : \Delta^* \to \Sigma^*$ is a non-erasing morphism.
A pattern $p$ is said to be $k$-avoidable if there exists an infinite word
over a $k$-letter alphabet that avoids $p$. A pattern is *doubled* if ev-
ery variable occurs at least twice. Doubled patterns are known to be
3-avoidable. Currie, Mol, and Rampersad have considered a gener-
alized notion which allows variable occurrences to be reversed. That
is, $h(V^R)$ is the mirror image of $h(V)$ for every $V \in \Delta$. We show
that doubled patterns with reversal are 3-avoidable. We also conjec-
ture that (classical) doubled patterns that do not contain a square are
2-avoidable. We confirm this conjecture for patterns with at most 4
variables. This implies that for every doubled pattern $p$, the growth
rate of ternary words avoiding $p$ is at least the growth rate of ternary
square-free words. A previous version of this paper containing only
the first result has been presented at WORDS 2021.
# 1 Introduction

The *mirror image* of the word $w = w_1w_2...w_n$ is the word $w^R = w_nw_{n-1}...w_1$.
A pattern with reversal *p* is a non-empty word over an alphabet
$Δ = \{A, A^R, B, B^R, C, C^R, ...\}$ such that $\{A, B, C, ...
\}$ are the *variables* of
*p*. An *occurrence* of *p* in a word *w* is a non-erasing morphism
$h: Δ^* → Σ^*$
satisfying $h(X^R) = (h(X))^R$ for every variable *X* and such that $h(p)$ is a
factor of *w*. The *avoidability index* $λ(p)$ of a pattern with reversal *p* is the
size of the smallest alphabet $Σ$ such that there exists an infinite word *w* over
$Σ$ containing no occurrence of *p*. A pattern *p* such that $λ(p) ≤ k$ is said to be
$k$-avoidable. To emphasize that a pattern is without reversal (i.e., it contains
no $X^R$), it is said to be *classical*. A pattern is *doubled* if every variable occurs
at least twice.

Our aim is to strengthen the following result.

**Theorem 1.** [1, 7, 8] Every doubled pattern is 3-avoidable.

First, we extend it to patterns with reversal.

**Theorem 2.** Every doubled pattern with reversal is 3-avoidable.

Then, we notice that all the known classical doubled patterns that are
2-unavoidable contain a square, such as *AABB*, *ABAB*, or *ABCCBADD*.

**Conjecture 3.** Every square-free doubled pattern is 2-avoidable.

Notice that Conjecture 3 is related to but independent of the following
conjecture.

**Conjecture 4.** [8, 10] There exist only finitely many 2-unavoidable doubled patterns.

The proof of Conjecture 3 for patterns up to 3 variables follows from the
2-avoidability of *ABACBC*, *ABCBABC*, *ABCACB* and *ABCBAC*. We
were able to verify it for patterns up to 4 variables.

**Theorem 5.** Every square-free doubled pattern with at most 4 variables is 2-avoidable.

Finally, we obtain a lower bound on the number of ternary words avoiding
a doubled pattern. The factor complexity of a factorial language $L$ over $Σ$ is
$f(n) = |L \cap Σ^n|$. The growth rate of $L$ over $Σ$ is $\lim_{n \to \infty} f(n)^{\frac{1}{n}}$. We denote
by $GR_3(p)$ the growth rate of ternary words avoiding the doubled pattern $p$.
**Theorem 6.** For every doubled pattern $p$, $GR_3(p) \ge GR_3(AA)$.

Let $v(p)$ be the number of distinct variables of the pattern $p$. In the proof of Theorem 1, the set of doubled patterns is partitioned as follows:

1. Patterns with $v(p) \le 3$: the avoidability index of every ternary pattern has been determined [7].

2. Patterns shown to be 3-avoidable with the so-called power series method:

* Patterns with $v(p) \ge 6$ [1]

* Patterns with $v(p) = 5$ and prefix ABC or length at least 11 [8]

* Patterns with $v(p) = 4$ and prefix ABCD or length at least 9 [8]

3. Ten sporadic patterns with $4 \le v(p) \le 5$ whose 3-avoidability cannot be deduced from the previous results: they have been shown to be 2-avoidable [8] using the method in [7].

The proof of Theorems 2 and 6 use the same partition. Sections 3 to 5 are each devoted to one type of doubled pattern with reversal. Theorem 5 is proved in Section 6 Theorem 6 is proved in Section 7

# 2 Preliminaries

A word $w$ is *d-directed* if for every factor $f$ of $w$ of length $d$, the word $f^R$ is not a factor of $w$.

*Remark 7.* If a *d*-directed word contains an occurrence $h$ of $X.X^R$ for some variable $X$, then $|h(X)| \le d-1$.

A variable that appears only once in a pattern is said to be *isolated*. The formula_ f associated to a pattern _p_ is obtained by replacing every isolated variable in _p_ by a dot. The factors between the dots are called *fragments*. An occurrence of a formula _f_ in a word _w_ is a non-erasing morphism _h_ such that the _h_-image of every fragment of _f_ is a factor of _w_. As for patterns, the avoidability index $\lambda(f)$ of a formula _f_ is the size of the smallest alphabet allowing the existence of an infinite word containing no occurrence of _f_. Recently, the avoidability of formulas with reversal has been considered by Currie, Mol, and Rampersad [4, 5] and Ochem [9].
Recall that a formula is *nice* if every variable occurs at least twice in the same fragment. In particular, a doubled pattern is a nice formula with exactly one fragment.

The *avoidability exponent* $AE(f)$ of a formula $f$ is the largest real $x$ such that every $x$-free word avoids $f$. Every nice formula $f$ with $v(f) \ge 3$ variables is such that $AE(f) \ge 1 + \frac{1}{2v(f)-3} [12]$.

Let $\simeq$ be the equivalence relation on words defined by $w \simeq w'$ if $w' \in \{w, w^R\}$. Avoiding a pattern up to $\simeq$ has been investigated for every binary formulas [3]. Remark that for a given classical pattern or formula $p$, avoiding $p$ up to $\simeq$ implies avoiding simultaneously all the variants of $p$ with reversal.

Recall that a word is $(\beta^+, n)$-free if it contains no repetition with exponent strictly greater than $\beta$ and period at least $n$.

### 3 Formulas with at most 3 variables

For classical doubled patterns with at most 3 variables, all the avoidability indices are known. There are many such patterns, so it would be tedious to consider all their variants with reversal.

However, we are only interested in their 3-avoidability, which follows from the 3-avoidability of nice formulas with at most 3 variables [11].

Thus, to obtain the 3-avoidability of doubled patterns with reversal with at most 3 variables, we show that every minimally nice formula with at most 3 variables is 3-avoidable up to $\simeq$.

The minimally nice formulas with at most 3 variables, up to symmetries, are determined in [11] and listed in the following table. Every such formula $f$ is avoided by the image by a $q$-uniform morphism of either any infinite $(\frac{5}{4}^+)$-free word $w_5$ over $\Sigma_5$ or any infinite $(\frac{7}{5}^+)$-free word $w_4$ over $\Sigma_4$, depending on whether the avoidability exponent of $f$ is smaller than $\frac{7}{5}$.
<table><thead><tr><th>Formula f</th><th>= f<sup>R</sup></th><th>AE(f)</th><th>Word</th><th>q</th><th>d</th><th>freeness</th></tr></thead><tbody><tr><td>ABA.BAB</td><td>yes</td><td>1.5</td><td>g<sub>a</sub>(w<sub>4</sub>)</td><td>9</td><td>9</td><td>(131<sup>+</sup> / 90, 28)</td></tr><tr><td>ABCA.BCAB.CABC</td><td>yes</td><td>1.333333333</td><td>g<sub>b</sub>(w<sub>5</sub>)</td><td>6</td><td>8</td><td>(4<sup>+</sup> / 3, 25)</td></tr><tr><td>ABCBA.CBABC</td><td>yes</td><td>1.333333333</td><td>g<sub>c</sub>(w<sub>5</sub>)</td><td>4</td><td>9</td><td>(30<sup>+</sup> / 23, 18)</td></tr><tr><td>ABCA.BCAB.CBC</td><td>no</td><td>1.381966011</td><td>g<sub>d</sub>(w<sub>5</sub>)</td><td>9</td><td>4</td><td>(62<sup>+</sup> / 45, 37)</td></tr><tr><td>ABA.BCB.CAC</td><td>yes</td><td>1.5</td><td>g<sub>e</sub>(w<sub>4</sub>)<sup>1</sup></td><td>9</td><td>4</td><td>(67<sup>+</sup> / 45, 37)</td></tr><tr><td>ABCA.BCAB.CBAC</td><td>yes<sup>2</sup></td><td>1.333333333</td><td>g<sub>f</sub>(w<sub>5</sub>)</td><td>6</td><td>6</td><td>(31<sup>+</sup> / 24, 31)</td></tr><tr><td>ABCA.BAB.CAC</td><td>yes</td><td>1.414213562</td><td>g<sub>g</sub>(w<sub>4</sub>)</td><td>6</td><td>8</td><td>(89<sup>+</sup> / 63, 61)</td></tr><tr><td>ABCA.BAB.CBC</td><td>no</td><td>1.430159709</td><td>g<sub>h</sub>(w<sub>4</sub>)</td><td>6</td><td>7</td><td>(17<sup>+</sup> / 12, 61)</td></tr><tr><td>ABCA.BAB.CBAC</td><td>no</td><td>1.381966011</td><td>g<sub>i</sub>(w<sub>5</sub>)</td><td>8</td><td>7</td><td>(127<sup>+</sup> / 96, 41)</td></tr><tr><td>ABCBA.CABC</td><td>no</td><td>1.361103081</td><td>g<sub>j</sub>(w<sub>5</sub>)</td><td>6</td><td>8</td><td>(4<sup>+</sup> / 3, 25)</td></tr><tr><td>ABCBA.CAC</td><td>yes</td><td>1.396608253</td><td>g<sub>k</sub>(w<sub>5</sub>)</td><td>6</td><td>13</td><td>(4<sup>+</sup> / 3, 25)</td></tr></tbody></table>

In the table above, the columns indicate respectively, the considered minimally nice formula $f$, whether $f$ is equivalent to its reversed formula, the avoidability exponent of $f$, the infinite ternary word avoiding $f$, the value $q$ such that the corresponding morphism is $q$-uniform, the value such that the avoiding word is $d$-directed, the suitable property of $(\beta^+, n)$-freeness used in the proof that $f$ is avoided. We list below the corresponding morphisms.

<table><thead><tr><th>g<sub>a</sub></th><th>g<sub>b</sub></th><th>g<sub>c</sub></th><th>g<sub>d</sub></th><th>g<sub>e</sub></th></tr></thead><tbody><tr><td>002112201</td><td>021221</td><td>2011</td><td>020112122</td><td>001220122</td></tr><tr><td>001221122</td><td>021121</td><td>1200</td><td>020101112</td><td>001220112</td></tr><tr><td>001220112</td><td>020001</td><td>1120</td><td>020001222</td><td>001120122</td></tr><tr><td>001122012</td><td>011102</td><td>0222</td><td>010121222</td><td>001120112</td></tr><tr><td></td><td>010222</td><td>0012</td><td>000111222</td><td></td></tr></tbody></table>

<footnote n="1">¹The formula ABA.BCB.CAC seems also avoided up to ≃ by the Hall-Thue word, i.e., the fixed point of 0 → 012; 1 → 02; 2 → 1.</footnote>

<footnote n="2">²We mistakenly said in [11] that ABCA.BCAB.CBAC is different from its reverse.</footnote>
<table><thead><tr><th>g<sub>f</sub></th><th>g<sub>g</sub></th><th>g<sub>h</sub></th><th>g<sub>i</sub></th><th>g<sub>j</sub></th><th>g<sub>k</sub></th></tr></thead><tbody><tr><td>012220</td><td>021210</td><td>011120</td><td>01222112</td><td>021121</td><td>022110</td></tr><tr><td>012111</td><td>011220</td><td>002211</td><td>01112022</td><td>012222</td><td>021111</td></tr><tr><td>012012</td><td>002111</td><td>002121</td><td>01100022</td><td>011220</td><td>012222</td></tr><tr><td>011222</td><td>001222</td><td>001222</td><td>01012220</td><td>011112</td><td>012021</td></tr><tr><td>010002</td><td></td><td></td><td>01012120</td><td>000102</td><td>011220</td></tr></tbody></table>

As an example, we show that ABCBA.CAC is avoided by $g_k(w_5)$. First, we check that $g_k(w_5)$ is $(\frac{4^+}{3}, 25)$-free using the main lemma in [7], that is, we check the $(\frac{4^+}{3}, 25)$-freeness of the $g_k$-image of every $(\frac{5^+}{4})$-free word of length at most $\frac{2 \times \frac{4}{3}}{\frac{4}{3} - \frac{5}{4}} = 32$. Then we check that $g_k(w_5)$ is 13-directed by inspecting the factors of $g_k(w_5)$ of length 13. For contradiction, suppose that $g_k(w_5)$ contains an occurrence $h$ of ABCBA.CAC up to $\simeq$. Let us write $a = |h(A)|$, $b = |h(B)|$, $c = |h(C)|$.

Suppose that $a \ge 25$. Since $g_k(w_5)$ is 13-directed, all occurrences of $h(A)$ are identical. Then $h(ABCBA)$ is a repetition with period $|h(ABCBA)| \ge 25$. So the $(\frac{4^+}{3}, 25)$-freeness implies the bound $\frac{2a+2b+c}{a+2b+c} \le \frac{4}{3}$, that is, $a \le b + \frac{1}{2}c$.

In every case, we have

$$a \le \max \{b + \frac{1}{2}c, 24\}.$$

Similarly, the factors $h(BCB)$ and $h(CAC)$ imply

$$b \le \max \{\frac{1}{2}c, 24\}$$

and

$$c \le \max \{\frac{1}{2}a, 24\}.$$

Solving these inequalities gives $a \le 36$, $b \le 24$, and $c \le 24$. Now we can check exhaustively that $g_k(w_5)$ contains no occurrence up to $\simeq$ satisfying these bounds.

Except for ABCBA.CBABC, the avoidability index of the nice formulas in the above table is 3. So the results in this section extend their 3-avoidability up to $\simeq$.
## 4 The power series method

The so-called power series method has been used [1, 8] to prove the 3-avoidability of many classical doubled patterns with at least 4 variables and every doubled pattern with at least 6 variables, as mentioned in the introduction.

Let $p$ be such a classical doubled pattern and let $p'$ be a doubled pattern with reversal obtained by adding some $-^R$ to $p$. Witout loss of generality, the leftmost appearance of every variable $X$ of $p$ remains free of $-^R$ in $p'$. Then we will see that $p'$ is also 3-avoidable. The power series method is a counting argument that relies on the following observation. If the $h$-image of the leftmost appearance of the variable $X$ of $p$ is fixed, say $h(X) = w_X$, then there is exactly one possibility for the $h$-image of the other appearances of $X$, namely $h(X) = w_X$. This observation can be extended to $p'$, since there is also exactly one possibility for $h(X^R)$, namely $h(X^R) = w_X^R$.

Notice that this straightforward generalization of the power series method from classical doubled patterns to doubled patterns with reversal cannot be extended to avoiding a doubled pattern up to $\simeq$. Indeed, if $h(X) = w_X$ for the leftmost appearance of the variable $X$ and $w_X$ is not a palindrome, then there exist two possibilities for the other appearances of $X$, namely $w_X$ and $w_X^R$.

## 5 Sporadic patterns

Up to symmetries, there are ten doubled patterns whose 3-avoidability cannot be deduced by the previous results. They have been identified in [8] and are listed in the following table.

Let $w_5$ be any infinite $(\frac{5}{4}^+)$-free word over $\Sigma_5$ and let $h$ be the following 9-uniform morphism.

$$h(0) = 020022221$$

$$h(1) = 011111221$$

$$h(2) = 010202110$$

$$h(3) = 010022112$$

$$h(4) = 000022121$$
<table><caption>Table 1: The seven sporadic patterns on 4 variables and the three sporadic patterns on 5 variables</caption><thead><tr><td>Doubled pattern</td><td>Avoidability exponent</td></tr></thead><tbody><tr><td>ABACBDCD</td><td>1.381966011</td></tr><tr><td>ABACDBDC</td><td>1.333333333</td></tr><tr><td>ABACDCBD</td><td>1.340090632</td></tr><tr><td>ABCADBDC</td><td>1.292893219</td></tr><tr><td>ABCADCBD</td><td>1.295597743</td></tr><tr><td>ABCADCDB</td><td>1.327621756</td></tr><tr><td>ABCBDADC</td><td>1.302775638</td></tr><tr><td>ABACBDCDE</td><td>1.366025404</td></tr><tr><td>ABACDBCEDE</td><td>1.302775638</td></tr><tr><td>ABACDBDECE</td><td>1.320416579</td></tr></tbody></table>

First, we check that $h(w_5)$ is 7-directed and $(\frac{139}{108}^+, 46)$-free. Then, using the same method as in Section 3, we show that $h(w_5)$ avoids up to ≃ these ten sporadic patterns simultaneously.

# 6 Square-free doubled patterns with at most 4 variables

Here we show Theorem 5, that is, every square-free doubled pattern with at most 4 variables is 2-avoidable. We list them as follows:

* Among patterns that are equal up to letter permutation, we only list the lexicographically least.

* If a pattern is distinct from its mirror image, we only list the lexicographically least among the pattern and its mirror image.

* We do not list patterns that contain a square-free doubled pattern as a strict factor.

* We do not list patterns that contain an occurrence of ABACBC, ABCACB, ABCBABC, ABCDBDABC, ABCDBDAC, ABACDCBD, or their mirror image.
• We do not include the seven sporadic patterns on 4 variables from Table 1, which are 2-avoidable.

Table 2 contains every pattern $p$ in this list with an infinite binary word avoiding $p$. Let us detail how to read Table 2:

• A morphism is $m$ given in the format $m(0)/m(1)/...$

• We denote by $b_2, b_4, b_5$ the famous morphisms 01/10, 01/21/03/23, 01/23/4/21/0, respectively.

• We denote by $w_k$ any infinite $RT(k)^+$-free word over $\Sigma_k$.

• If the avoiding word is a pure morphic word $m^\omega(0)$, then $m$ is given.

• If the avoiding word is a morphic word $f(m^\omega(0))$, then we write $m$; $f$.

• If the avoiding word is of the form $f(w_k)$, then we write $w_k$; $f$.

The proofs that a (pure) morphic word avoids a pattern use Cassaigne's algorithm [2] and the proofs that a morphic image word a Dejean word avoids a pattern use the technique described in Section 3.

# 7 Growth rate of ternary words avoiding a doubled pattern

Theorem 6 obviously holds for $p = AA$. Without loss of generality, we do not need to consider a doubled pattern $p$ that contains an occurrence of another doubled pattern. In particular, $p$ is square-free. So we need to show that $GR_3(p)$ is at least $GR_3(AA)$, which is close to 1.30176 [13].

If $p$ is 2-avoidable, then $p$ is avoided by sufficiently many ternary words.
By Lemma 4.1 in [7], $\lambda(p) = 2$ implies that $GR_3(p) \ge 2^{\frac{1}{2}} > GR_3(AA)$.
Thus, Conjecture 3 implies Theorem 6. By Theorem 5, we can assume that
$v(p) \ge 5$. We can also rule out the three sporadic patterns on 5 variables
from Table 1, which are 2-avoidable.

According to the partition of the set of doubled patterns mentioned in
the introduction, there remains to consider the doubled patterns $p$ whose
3-avoidability has been obtained via the power series method. In that case,
we even get $GR_3(p) > 2 > GR_3(AA)$.
<table><caption>Table 2: Binary words avoiding doubled patterns</caption><thead><tr><th>Doubled pattern</th><th>Avoiding word</th></tr></thead><tbody><tr><td>ABCABDCBD</td><td>w<sub>5</sub>: 0001011110/0001001100/0001111110/0001110101/0000011001</td></tr><tr><td>ABCACDCBD</td><td>w<sub>5</sub>: 000101010111/000100110111/000011001111/000001011111/000000111111</td></tr><tr><td>ABCBABDBCBD</td><td>b<sub>4</sub>: 01/00/10/11</td></tr><tr><td>ABCBADCBCD</td><td>b<sub>4</sub>: 0000/0011/1111/1010</td></tr><tr><td>ABCBDACBCD</td><td>b<sub>4</sub>: 01/00/10/11</td></tr><tr><td>ABCBDBCACBCD</td><td>b<sub>2</sub></td></tr><tr><td>ABCBDBCBACBCD</td><td>b<sub>4</sub>: 1000/0111/0110/0010</td></tr><tr><td>ABCDACBD</td><td>w<sub>5</sub>: 000100110111111000/00100110111011000/00011110110101010/00001111111011010/00001010101011111</td></tr><tr><td>ABCDABCBD</td><td>w<sub>6</sub>: 010101111100/010010100000/001001110111/000111111101/00010101010111/000100011011</td></tr><tr><td>ABCDABDC</td><td>w<sub>5</sub>: 10001000101111101010110/00000110110101000111111/0000010111010001010011111/00000011101010001011111</td></tr><tr><td>ABCDDBACBD</td><td>001/011</td></tr><tr><td>ABCDCACBD</td><td>b<sub>5</sub>: 0011110110000/00110101000110/00011111000111/0001110001000/0001101101111</td></tr><tr><td>ABCDCAABCD</td><td>avoided by every (3/2+, 4)-free binary word [6]</td></tr><tr><td>ABCDDBCACBD</td><td>b<sub>5</sub>: 00/01/10/110/111</td></tr><tr><td>ABACDCBCD</td><td>w<sub>5</sub>: 10011011000/010111111000/00111010100/001001001111/000011111111</td></tr><tr><td>ABCABDBCD</td><td>w<sub>5</sub>: 00101111111/0010011110/00100111100/0000010101/0000001101</td></tr><tr><td>ABCADBCBD</td><td>w<sub>5</sub>: 001011010000/001001111000/000110011001/000011101010/000010111111</td></tr><tr><td>ABCADCBCD</td><td>w<sub>5</sub>: 001101111000/001101101000/001001111111/000101110101/000001100101</td></tr><tr><td>ABCBADBCD</td><td>w<sub>5</sub>: 0011111110110/0001010111100/0000101101110/0000010101111/0000001011111</td></tr><tr><td>ABCBDBABCD</td><td>b<sub>4</sub>: 1111/1101/0010/0000</td></tr><tr><td>ABCBDBABCD</td><td>w<sub>5</sub>: 101110000001/101100100001/011111111010/010001111110/010001101110</td></tr><tr><td>ABCBDACBD</td><td>b<sub>5</sub>: 00/01/10/110/111</td></tr><tr><td>ABCBDADBC</td><td>w<sub>5</sub>: 00110111010010/00110000000010/00011111111011/000111110101000/00010101100011</td></tr><tr><td>ABCBDADBCD</td><td>b<sub>5</sub>: 111/101/000/011/001</td></tr><tr><td>ABCBDBABBCD</td><td>b<sub>5</sub>: 00/01/10/110/111</td></tr><tr><td>ABCBDBABBCD</td><td>b<sub>5</sub>: 000/011/001/111/101</td></tr><tr><td>ABCBDBACBCD</td><td>b<sub>4</sub>: 01/00/10/11</td></tr><tr><td>ABCBDBACD</td><td>w<sub>5</sub>: 0001111101010/0001111011000/000101111111/000011100111/0000011011001</td></tr><tr><td>ABCBDBADBCD</td><td>011/100</td></tr><tr><td>ABCBDBADBC</td><td>00111101110000/00111011000010/00111010100000/00011001001111/00010101111111</td></tr><tr><td>ABCBDBACBD</td><td>b<sub>5</sub>: 00/01/10/110/111</td></tr><tr><td>ABCBDBCACBD</td><td>b<sub>5</sub>: 00/01/10/110/111</td></tr><tr><td>ABCBDBCAD</td><td>w<sub>5</sub>: 00011111011001/00011101101001/00011011010100/0001011111110/00000011111010</td></tr><tr><td>ABCBDBCBABCD</td><td>b<sub>4</sub>: 000/111/10/01</td></tr><tr><td>ABCBDBCBACBCD</td><td>b<sub>2</sub></td></tr><tr><td>ABCBDBCBACBD</td><td>b<sub>4</sub>: 00/01/10/11</td></tr><tr><td>ABCBDBCBACD</td><td>001/110</td></tr><tr><td>ABCBDCABCD</td><td>b<sub>5</sub>: 00/10/111/01/011</td></tr><tr><td>ABCBDCABD</td><td>w<sub>5</sub>: 10000000011/01111010010/01101100010/01011111110/00001010101</td></tr><tr><td>ABCBDCACBD</td><td>b<sub>5</sub>: 111/101/000/100/110</td></tr><tr><td>ABCBDCBACBD</td><td>b<sub>5</sub>: 00/01/10/110/111</td></tr><tr><td>ABCBDCBACBD</td><td>b<sub>5</sub>: 00/01/10/110/111</td></tr><tr><td>ABCBDCBACD</td><td>b<sub>5</sub>: 00/01/10/1100/111</td></tr><tr><td>ABCBDBAD</td><td>w<sub>5</sub>: 001101101100/001011111111/000100111100/000110010100/000001110100</td></tr><tr><td>ABCBDBCBAD</td><td>b<sub>4</sub>: 000/111/10/01</td></tr><tr><td>ABCBDBCAD</td><td>w<sub>5</sub>: 1111100/1100110/0110101/0010010/00000101</td></tr><tr><td>ABCDADCB</td><td>w<sub>5</sub>: 000001000111111010100010011111011/0000010001111100100001100101101111/00000010011111101000010101111011/00000001011110010000111111010010111</td></tr><tr><td>ABCDABBD</td><td>w<sub>5</sub>: 0011111110101/001011011010/0010101110000/0000111111001/0000110110001</td></tr><tr><td>ABCDABBC</td><td>w<sub>5</sub>: 01011111111/010010001111/00101000011/00011110101/00000001011</td></tr><tr><td>ABCDACBCBD</td><td>b<sub>5</sub>: 101/000/110/111/100</td></tr><tr><td>ABCDABCBAD</td><td>w<sub>5</sub>: 0110101/0100000/0011110/0001111/000011</td></tr><tr><td>ABCDDBAD</td><td>w<sub>5</sub>: 0001011101010/0000111101010/00001110001010/000011011111/000011000110</td></tr><tr><td>ABCDDBAD</td><td>w<sub>5</sub>: 000001101101100111000111101101101100001011110101001001011111/0000001101110101001001011111/0000001011110101001001011111/0000001011110101001001011111/0000001011110101001001011111/0000001011110101001001011111</td></tr><tr><td>ABCDDBADBC</td><td>w<sub>5</sub>: 01111101/00111100/001111001/00110110/00000101</td></tr><tr><td>ABCDCAACBD</td><td>w<sub>5</sub>: 00110001000110/0010101111110/000111101001/0000101011111/0000000101011</td></tr></tbody></table>
# 8 Conclusion

Unlike classical formulas, we know that there exist avoidable formulas with reversal of arbitrarily high avoidability index [9]. Maybe doubled patterns and nice formulas are easier to avoid. We propose the following open problems.

* Are there infinitely many doubled patterns up to $\simeq$ that are not 2-avoidable?

* Is there a nice formula up to $\simeq$ that is not 3-avoidable?

A first step would be to improve Theorem 2 by generalizing the 3-avoidability of doubled patterns with reversal to doubled patterns up to $\simeq$. Notice that the results in Sections 3 and 5 already consider avoidability up to $\simeq$. However, the power series method gives weaker results. Classical doubled patterns with at least 6 variables are 3-avoidable because

$$1 - 3x + \left( \frac{3x^2}{1 - 3x^2} \right)^v$$

has a positive real root for $v \ge 6$. The (basic) power series for doubled patterns up to $\simeq$ with $v$ variables would be

$$1 - 3x + \left( \frac{6x^2}{1 - 3x^2} - \frac{3x^2 + 3x^4}{1 - 3x^4} \right)^v.$$

The term $\frac{6x^2}{1-3x^2}$ counts for twice the term $\frac{3x^2}{1-3x^2}$ in the classical setting, for $h(V)$ and $h(V)^R$. The term $\frac{3x^2+3x^4}{1-3x^4}$ corrects for the case of palindromic $h(V)$, which should not be counted twice. This power series has a positive real root only for $v \ge 10$. This leaves many doubled patterns up to $\simeq$ whose 3-avoidability must be proved with morphisms.

Looking at the proof of Theorem 2, we may wonder if a doubled pattern with reversal is always easier to avoid than the corresponding classical pattern. This is not the case: backtracking shows that $\lambda(ABCA^RC^RB) = 3$, whereas $\lambda(ABCACB) = 2$ [7].

To get a more precise version of both conjectures 3 and 4, we plan to obtain the (conjectured) list of all 2-unavoidable doubled patterns, which should be a finite list containing no square-free pattern.
References

[1] J. Bell, T. L. Goh. Exponential lower bounds for the number of words of uniform length avoiding a pattern. *Inform. and Comput.* **205** (2007), 1295-1306.

[2] J. Cassaigne. *An Algorithm to Test if a Given Circular HD0L-Language Avoids a Pattern*. *IFIP Congress*, pages 459–464, 1994.

[3] J. Currie and L. Mol. The undirected repetition threshold and undirected pattern avoidance. *Theor. Comput. Sci.* **866** (2021), 56–69.

[4] J. Currie, L. Mol, and N. Rampersad. A family of formulas with reversal of high avoidability index. *International Journal of Algebra and Computation* **27(5)** (2017), 477–493.

[5] J. Currie, L. Mol, and N. Rampersad. Avoidance bases for formulas with reversal. *Theor. Comput. Sci.* **738** (2018), 25–41.

[6] L. Ilie, P. Ochem, and J.O. Shallit. A generalization of repetition threshold. *Theoret. Comput. Sci.* **92(2)** (2004), 71–76.

[7] P. Ochem. A generator of morphisms for infinite words. *RAIRO: Theoret. Informatics Appl.* **40** (2006), 427–441.

[8] P. Ochem. Doubled patterns are 3-avoidable. *Electron. J. Combinatorics.* **23(1)** (2016), #P1.19.

[9] P. Ochem. A family of formulas with reversal of arbitrarily high avoidability index. *Theoret. Comput. Sci.* **896** (2021), 168–170.

[10] P. Ochem and A. Pinlou. Application of entropy compression in pattern avoidance. *Electron. J. Combinatorics.* **21(2)** (2014), #RP2.7.

[11] P. Ochem and M. Rosenfeld. On some interesting ternary formulas. *Electron. J. Combinatorics.* **26(1)** (2019), #P1.12.

[12] P. Ochem and M. Rosenfeld. Avoidability of palindrome patterns. *Electron. J. Combinatorics.* **28(1)** (2021), #P1.4.

[13] A. Shur. Growth rates of complexity of power-free languages. *Theoret. Comput. Sci.* **411(34-36)** (2010), 3209–3223.