# Antisquares and Critical Exponents

Aseem Baranwal, James Currie, Lucas Mol, Pascal Ochem, Narad Rampersad, Jeffrey Shallit

► To cite this version:

Aseem Baranwal, James Currie, Lucas Mol, Pascal Ochem, Narad Rampersad, et al. Antisquares and Critical Exponents. 2023. lirmm-03799689

HAL Id: lirmm-03799689

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

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Antisquares and Critical Exponents

Aseem Baranwal, James Currie, Lucas Mol, Pascal Ochem, Narad Rampersad, Jeffrey Shallit

► To cite this version:

Aseem Baranwal, James Currie, Lucas Mol, Pascal Ochem, Narad Rampersad, et al.. Antisquares and Critical Exponents. Discrete Mathematics and Theoretical Computer Science, 2023, 25 (2), pp.#11. 10.46298/dmtcs.10063 . lirmm-03799689v2

HAL Id: lirmm-03799689

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03799689v2

Submitted on 23 Jul 2024

**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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Antisquares and Critical Exponents

Aseem Baranwal<fnref n="1" />

James Currie<fnref n="2" />*

Lucas Mol<fnref n="3" />

Pascal Ochem<fnref n="4" />

Narad Rampersad<fnref n="2" />†

Jeffrey Shallit<fnref n="1" />‡

revisions 20th Sep. 2022, 27th July 2023; accepted 2nd Aug. 2023.

The (bitwise) complement $\bar{x}$ of a binary word $x$ is obtained by changing each 0 in $x$ to 1 and vice versa. An antisquare is a nonempty word of the form $x \bar{x}$. In this paper, we study infinite binary words that do not contain arbitrarily large antisquares. For example, we show that the repetition threshold for the language of infinite binary words containing exactly two distinct antisquares is $(5 + \sqrt{5})/2$. We also study repetition thresholds for related classes, where “two” in the previous sentence is replaced by a larger number.

We say a binary word is good if the only antisquares it contains are 01 and 10. We characterize the minimal antisquares, that is, those words that are antisquares but all proper factors are good. We determine the growth rate of the number of good words of length $n$ and determine the repetition threshold between polynomial and exponential growth for the number of good words.

**Keywords:** antisquare, critical exponent, binary complement, binary word, avoidability, repetition threshold, enumeration, minimal forbidden word

## 1 Introduction

Let $x$ be a finite nonempty binary word. We say that $x$ is an antisquare if there exists a word $y$ such that $x = y \bar{y}$, where the overline denotes a morphism that maps $0 \to 1$ and $1 \to 0$. For example, 011100 is an antisquare. The order of an antisquare $y \bar{y}$ is defined to be $|y|$, where $|y|$ denotes the length of $y$.

Avoidance of antisquares has been studied previously in combinatorics on words. For example, Mousavi et al. (2016) proved that the infinite Fibonacci word

$$f = 01001010\cdots,$$

the fixed point of the morphism $0 \to 01, 1 \to 0$, has exactly four antisquare factors, namely, 01, 10, 1001, and 10100101. More generally, all the antisquares in Sturmian words have recently been characterized

<footnote n="1">¹ University of Waterloo, Canada</footnote>

<footnote n="2">² University of Winnipeg, Canada</footnote>

<footnote n="3">³ Thompson Rivers University, Canada</footnote>

<footnote n="4">⁴ LIRMM, CNRS, Université de Montpellier, France</footnote>

<footnote>*The research of JC is supported by NSERC Grant 2017-03901.</footnote>

<footnote>†The research of NR is supported by NSERC Grant 2019-04111.</footnote>

<footnote>‡The research of JS is supported by NSERC Grant 2018-04118.</footnote>
# Antisquares and Critical Exponents

Aseem Baranwal<fnref n="1" /> James Currie<fnref n="2" />* Lucas Mol<fnref n="3" /> Pascal Ochem<fnref n="4" /> Narad Rampersad<fnref n="2" />† Jeffrey Shallit<fnref n="1" />‡

revisions 20th Sep. 2022, 27th July 2023; accepted 2nd Aug. 2023.

The (bitwise) complement $\bar{x}$ of a binary word $x$ is obtained by changing each 0 in $x$ to 1 and vice versa. An antisquare is a nonempty word of the form $x \bar{x}$. In this paper, we study infinite binary words that do not contain arbitrarily large antisquares. For example, we show that the repetition threshold for the language of infinite binary words containing exactly two distinct antisquares is $(5 + \sqrt{5})/2$. We also study repetition thresholds for related classes, where “two” in the previous sentence is replaced by a larger number.

We say a binary word is good if the only antisquares it contains are 01 and 10. We characterize the minimal antisquares, that is, those words that are antisquares but all proper factors are good. We determine the growth rate of the number of good words of length $n$ and determine the repetition threshold between polynomial and exponential growth for the number of good words.

**Keywords:** antisquare, critical exponent, binary complement, binary word, avoidability, repetition threshold, enumeration, minimal forbidden word

## 1 Introduction

Let $x$ be a finite nonempty binary word. We say that $x$ is an antisquare if there exists a word $y$ such that $x = y \bar{y}$, where the overline denotes a morphism that maps $0 \to 1$ and $1 \to 0$. For example, 011100 is an antisquare. The order of an antisquare $y \bar{y}$ is defined to be $|y|$, where $|y|$ denotes the length of $y$.

Avoidance of antisquares has been studied previously in combinatorics on words. For example, Mousavi et al. (2016) proved that the infinite Fibonacci word

$$f = 01001010\cdots,$$

the fixed point of the morphism $0 \to 01, 1 \to 0$, has exactly four antisquare factors, namely, 01, 10, 1001, and 10100101. More generally, all the antisquares in Sturmian words have recently been characterized

<footnote n="1">¹ University of Waterloo, Canada</footnote>

<footnote n="2">² University of Winnipeg, Canada</footnote>

<footnote n="3">³ Thompson Rivers University, Canada</footnote>

<footnote n="4">⁴ LIRMM, CNRS, Université de Montpellier, France</footnote>

<footnote>*The research of JC is supported by NSERC Grant 2017-03901.</footnote>

<footnote>†The research of NR is supported by NSERC Grant 2019-04111.</footnote>

<footnote>‡The research of JS is supported by NSERC Grant 2018-04118.</footnote>
in Hieronymi et al. (2022). On the other hand, Ng et al. (2019) classified those infinite binary words containing the minimum possible numbers of distinct squares and antisquares.

It is easy to see that no infinite binary word, except the trivial families given by $(0+\epsilon)1^\omega$ and $(1+\epsilon)0^\omega$, can contain at most one distinct antisquare. (Here the notation $x^\omega$ refers to the right-infinite word $xxx\cdots$.) However, once we move to two distinct antisquares, the situation is quite different. We have the following:

**Proposition 1.** There are exponentially many finite binary words of length $n$ having at most two distinct antisquares, and there are uncountably many infinite binary words with the same property.

**Proof:** It is easy to see that every binary word in $\{1000, 10000\}^*$ has only the antisquares 01 and 10, which proves the first claim.

For the second, consider the uncountable set of infinite words $\{1000, 10000\}^\omega$. (Here, by $S^\omega$ for a set $S$ of nonempty finite words, we mean the set of all infinite words arising from concatenations of elements of $S$.) $\square$

Furthermore, it is easy to see that if an infinite binary word, other than $001^\omega$ and its complement, contains exactly two antisquares, then these antisquares must be 01 and 10. Call a binary word good if it contains no antisquare factors, except possibly 01 and 10. This suggests studying the following problem.

**Problem 2.** Find the repetition threshold for good words.

The repetition threshold for a class of (finite or infinite) words is defined as follows. First, we say that a finite word $w = w[1..n]$ has period $p \ge 1$ if $w[i] = w[i+p]$ for $1 \le i \le n-p$. The smallest period of a word $w$ is called the period, and we write it as $\text{per}(w)$. The exponent of a finite word $w$, written $\exp(w)$, is defined to be $|w|/\text{per}(w)$. We say a word (finite or infinite) is $\alpha$-free if the exponents of its nonempty factors are all $< \alpha$. We say a word is $\alpha^+$-free if the exponents of its nonempty factors are all $\le \alpha$. The *critical exponent* of a finite or infinite word $x$ is the supremum, over all nonempty finite factors $w$ of $x$, of $\exp(w)$; it is written $\text{ce}(x)$. Finally, the *repetition threshold* for a language $L$ of infinite words is defined to be the infimum, over all $x \in L$, of $\text{ce}(x)$.

The critical exponent of a word can be either rational or irrational. If it is rational, then it can either be attained by a particular finite factor, or not attained. For example, the critical exponent of both

* the Thue-Morse word $t = 0110100110010110100101100\cdots$, fixed point of the morphism $0 \to 01, 1 \to 10$; and

* the variant Thue-Morse word $vtm = 2102012101202102012021012\cdots$, fixed point of the morphism $2 \to 210, 1 \to 20, 0 \to 1$

is 2, but it is attained in the former case and not attained in the latter. If the critical exponent $\alpha$ is attained, we typically write it as $\alpha^+$.

In 1972, Dejean (1972) wrote a classic paper on combinatorics on words, where she determined the repetition threshold for the language of all infinite words over $\{0, 1, 2\}$—it is $\frac{7}{4}$—and conjectured the value of the repetition threshold for the languages $\Sigma_k^*$ for $k \ge 4$, where $\Sigma_k = \{0, 1, \dots, k-1\}$. Dejean's conjecture was only completely resolved in 2011, in Rao (2011) and Currie and Rampersad (2011), independently.

The repetition threshold has been studied for many classes of words. To name a few, there are the

* Sturmian words, studied in (Carpi and Luca, 2000, Prop. 15);
in Hieronymi et al. (2022). On the other hand, Ng et al. (2019) classified those infinite binary words containing the minimum possible numbers of distinct squares and antisquares.

It is easy to see that no infinite binary word, except the trivial families given by $(0+\epsilon)1^\omega$ and $(1+\epsilon)0^\omega$, can contain at most one distinct antisquare. (Here the notation $x^\omega$ refers to the right-infinite word $xxx\cdots$.) However, once we move to two distinct antisquares, the situation is quite different. We have the following:

**Proposition 1.** There are exponentially many finite binary words of length $n$ having at most two distinct antisquares, and there are uncountably many infinite binary words with the same property.

**Proof:** It is easy to see that every binary word in $\{1000, 10000\}^*$ has only the antisquares 01 and 10, which proves the first claim.

For the second, consider the uncountable set of infinite words $\{1000, 10000\}^\omega$. (Here, by $S^\omega$ for a set $S$ of nonempty finite words, we mean the set of all infinite words arising from concatenations of elements of $S$.) $\square$

Furthermore, it is easy to see that if an infinite binary word, other than $001^\omega$ and its complement, contains exactly two antisquares, then these antisquares must be 01 and 10. Call a binary word good if it contains no antisquare factors, except possibly 01 and 10. This suggests studying the following problem.

**Problem 2.** Find the repetition threshold for good words.

The repetition threshold for a class of (finite or infinite) words is defined as follows. First, we say that a finite word $w = w[1..n]$ has period $p \ge 1$ if $w[i] = w[i+p]$ for $1 \le i \le n-p$. The smallest period of a word $w$ is called the period, and we write it as $\text{per}(w)$. The exponent of a finite word $w$, written $\exp(w)$, is defined to be $|w|/\text{per}(w)$. We say a word (finite or infinite) is $\alpha$-free if the exponents of its nonempty factors are all $< \alpha$. We say a word is $\alpha^+$-free if the exponents of its nonempty factors are all $\le \alpha$. The *critical exponent* of a finite or infinite word $x$ is the supremum, over all nonempty finite factors $w$ of $x$, of $\exp(w)$; it is written $\text{ce}(x)$. Finally, the *repetition threshold* for a language $L$ of infinite words is defined to be the infimum, over all $x \in L$, of $\text{ce}(x)$.

The critical exponent of a word can be either rational or irrational. If it is rational, then it can either be attained by a particular finite factor, or not attained. For example, the critical exponent of both

* the Thue-Morse word $t = 0110100110010110100101100\cdots$, fixed point of the morphism $0 \to 01, 1 \to 10$; and

* the variant Thue-Morse word $vtm = 2102012101202102012021012\cdots$, fixed point of the morphism $2 \to 210, 1 \to 20, 0 \to 1$

is 2, but it is attained in the former case and not attained in the latter. If the critical exponent $\alpha$ is attained, we typically write it as $\alpha^+$.

In 1972, Dejean (1972) wrote a classic paper on combinatorics on words, where she determined the repetition threshold for the language of all infinite words over $\{0, 1, 2\}$—it is $\frac{7}{4}$—and conjectured the value of the repetition threshold for the languages $\Sigma_k^*$ for $k \ge 4$, where $\Sigma_k = \{0, 1, \dots, k-1\}$. Dejean's conjecture was only completely resolved in 2011, in Rao (2011) and Currie and Rampersad (2011), independently.

The repetition threshold has been studied for many classes of words. To name a few, there are the

* Sturmian words, studied in (Carpi and Luca, 2000, Prop. 15);
• palindromes, studied in Shallit (2016);

• rich words, studied in Currie et al. (2020);

• balanced words, studied in Rampersad et al. (2019) Dvořáková et al. (2022); and

• complementary symmetric Rote words, studied in Dvořáková et al. (2020).

For variations on and generalizations of repetition threshold, see Ilie et al. (2005); Badkobeh and Crochemore (2011); Fiorenzi et al. (2011); Samsonov and Shur (2012); Mousavi and Shallit (2013).

The goal of this paper is to study the repetition threshold for two classes of infinite words:

• $AO_ℓ$, the binary words avoiding all antisquares of order $\geqslant \ell$;

• $AN_n$, the binary words with no more than $n$ antisquares.

It turns out that there is an interesting and subtle hierarchy, depending on the values of $ℓ$ and $n$.

Our work is very similar in flavor to that of Shallit (2004), which found a similar hierarchy concerning critical exponents and sizes of squares avoided. The hierarchy for antisquares, as we will see, however, is significantly more complex.

In this paper, in Sections 2 and 3, we solve Problem 2, and show that the repetition threshold for good words is $2 + \alpha$, where $\alpha = (1 + \sqrt{5})/2$ is the golden ratio.

Proving that the repetition threshold for a class of infinite words equals some real number $\beta$ generally consists of two parts: first, an explicit construction of a word avoiding $\beta^+$ powers. This is often carried out by finding an appropriate morphism $h$ whose infinite fixed point $x$ (or an image of $x$ under a second morphism) has the desired property. Second, if $\beta$ is rational, then one can prove there is no infinite word avoiding $\beta$-powers by a breadth-first or depth-first search of the infinite tree of all words. If $\beta$ is irrational, however, one must generally be more clever.

In Section 4 we determine the repetition threshold for binary words avoiding all antisquares of order $\geqslant \ell$, and in Section 5 we determine the repetition threshold for binary words with no more than $n$ antisquares. In Section 6 we completely characterize the minimal antisquares; i.e., the binary words that are antisquares but have the property that all proper factors are good. This characterization is then used in Section 7, where we determine the growth rate of the number of good words of length $n$. In this section we also show that the repetition threshold between polynomial and exponential growth for good words avoiding $\alpha$-powers is $\alpha = \frac{15}{4}$; i.e., there are exponentially many such words avoiding $\frac{15}{4}$-powers, but only polynomially many that avoid $\frac{15}{4}$-powers.

## 2 A good infinite word with critical exponent $2 + \alpha$

Consider the morphisms below:

$$ \varphi: \begin{array}{rcl} 0 & \mapsto & 001 \\ 1 & \mapsto & 01 \end{array} $$

$$ g: \begin{array}{rcl} 0 & \mapsto & 01 \\ 1 & \mapsto & 11. \end{array} $$

Let us write $\varphi^\omega(0)$ for the (unique) infinite fixed point of $\varphi$ that starts with $0$. We claim that the infinite word $w = g(\varphi^\omega(0))$ does not have antisquares other than $01$ and $10$, and has critical exponent $2 + \alpha$, where $\alpha = (1 + \sqrt{5})/2$. The infinite word $w$ is Fibonacci-automatic, in the sense of Mousavi et al.
• palindromes, studied in Shallit (2016);

• rich words, studied in Currie et al. (2020);

• balanced words, studied in Rampersad et al. (2019) Dvořáková et al. (2022); and

• complementary symmetric Rote words, studied in Dvořáková et al. (2020).

For variations on and generalizations of repetition threshold, see Ilie et al. (2005); Badkobeh and Crochemore (2011); Fiorenzi et al. (2011); Samsonov and Shur (2012); Mousavi and Shallit (2013).

The goal of this paper is to study the repetition threshold for two classes of infinite words:

• $AO_ℓ$, the binary words avoiding all antisquares of order $\geqslant \ell$;

• $AN_n$, the binary words with no more than $n$ antisquares.

It turns out that there is an interesting and subtle hierarchy, depending on the values of $ℓ$ and $n$.

Our work is very similar in flavor to that of Shallit (2004), which found a similar hierarchy concerning critical exponents and sizes of squares avoided. The hierarchy for antisquares, as we will see, however, is significantly more complex.

In this paper, in Sections 2 and 3, we solve Problem 2, and show that the repetition threshold for good words is $2 + \alpha$, where $\alpha = (1 + \sqrt{5})/2$ is the golden ratio.

Proving that the repetition threshold for a class of infinite words equals some real number $\beta$ generally consists of two parts: first, an explicit construction of a word avoiding $\beta^+$ powers. This is often carried out by finding an appropriate morphism $h$ whose infinite fixed point $x$ (or an image of $x$ under a second morphism) has the desired property. Second, if $\beta$ is rational, then one can prove there is no infinite word avoiding $\beta$-powers by a breadth-first or depth-first search of the infinite tree of all words. If $\beta$ is irrational, however, one must generally be more clever.

In Section 4 we determine the repetition threshold for binary words avoiding all antisquares of order $\geqslant \ell$, and in Section 5 we determine the repetition threshold for binary words with no more than $n$ antisquares. In Section 6 we completely characterize the minimal antisquares; i.e., the binary words that are antisquares but have the property that all proper factors are good. This characterization is then used in Section 7, where we determine the growth rate of the number of good words of length $n$. In this section we also show that the repetition threshold between polynomial and exponential growth for good words avoiding $\alpha$-powers is $\alpha = \frac{15}{4}$; i.e., there are exponentially many such words avoiding $\frac{15}{4}$-powers, but only polynomially many that avoid $\frac{15}{4}$-powers.

## 2 A good infinite word with critical exponent $2 + \alpha$

Consider the morphisms below:

$$ \varphi: \begin{array}{rcl} 0 & \mapsto & 001 \\ 1 & \mapsto & 01 \end{array} $$

$$ g: \begin{array}{rcl} 0 & \mapsto & 01 \\ 1 & \mapsto & 11. \end{array} $$

Let us write $\varphi^\omega(0)$ for the (unique) infinite fixed point of $\varphi$ that starts with $0$. We claim that the infinite word $w = g(\varphi^\omega(0))$ does not have antisquares other than $01$ and $10$, and has critical exponent $2 + \alpha$, where $\alpha = (1 + \sqrt{5})/2$. The infinite word $w$ is Fibonacci-automatic, in the sense of Mousavi et al.
(2016), so we can apply the Walnut theorem-prover Mousavi (2016) to establish this claim. For more
about Walnut, see Shallit (2022).

We start with the Fibonacci automaton for φ<sup>ω</sup>(0), as displayed in Figure 1.

<figure><img src="image_2.png" /><figcaption>Fig. 1: Fibonacci automaton for φ<sup>ω</sup>(0).</figcaption></figure>

Let us name the above automaton FF.txt, and store it in the Word Automata Library of
Walnut. We can verify the correctness of this automaton as follows. First, we claim that φ<sup>ω</sup>(0) = 0f. To
see this, let f denote the morphism that maps 0 → 010, 1 → 01; i.e., the morphism f is the square of the
Fibonacci morphism. One can easily verify the identities φ<sup>n</sup>(0) = 0f<sup>n</sup>(0)0<sup>-1</sup> and φ<sup>n</sup>(01) = 0f<sup>n</sup>(10)0<sup>-1</sup>
by simultaneous induction, whence follows the claim. We can then use Walnut to verify the correctness
of the automaton FF with the command

eval verifyFF "?msd_fib FF[0]=@0 & Ai FF[i+1]=F[i]":

which returns TRUE.

Now we can use Walnut to create a Fibonacci automaton for w.

morphism g "0->01 1->11":

image GF g FF:

The resulting automaton is called GF.txt and is displayed in Figure 2.
(2016), so we can apply the Walnut theorem-prover Mousavi (2016) to establish this claim. For more
about Walnut, see Shallit (2022).

We start with the Fibonacci automaton for $\varphi^\omega(0)$, as displayed in Figure 1.

<figure><img src="image_2.png" /><figcaption>Fig. 1: Fibonacci automaton for $\varphi^\omega(0)$.</figcaption></figure>

Let us name the above automaton FF.txt, and store it in the Word Automata Library of
Walnut. We can verify the correctness of this automaton as follows. First, we claim that $\varphi^\omega(0) = 0f$. To
see this, let $f$ denote the morphism that maps $0 \to 010, 1 \to 01$; i.e., the morphism $f$ is the square of the
Fibonacci morphism. One can easily verify the identities $\varphi^n(0) = 0f^n(0)0^{-1}$ and $\varphi^n(1) = 0f^n(10)0^{-1}$
by simultaneous induction, whence follows the claim. We can then use Walnut to verify the correctness
of the automaton FF with the command

eval verifyFF "?msd_fib FF[0]=@0 & Ai FF[i+1]=F[i]":

which returns TRUE.

Now we can use Walnut to create a Fibonacci automaton for w.

morphism g "0->01 1->11":

image GF g FF:

The resulting automaton is called GF.txt and is displayed in Figure 2.
<figure><img src="image_3.png" /><figcaption>**Fig. 2:** Fibonacci automaton for $w = g(\varphi^\omega(0))$.</figcaption></figure>

**Theorem 3.** The word $w$ does not contain antisquares other than 01 and 10, and has critical exponent $2 + \alpha$.

**Proof:** We write a Walnut formula asserting that there exists an antisquare of order $\ge 2$, as follows:

eval antisq "?msd_fib Ei,n (n>=2) & At (t<n) => GF[i+t]!:=GF[i+n+t]":

This returns FALSE, so there are no antisquares of order $\ge 2$.

We now compute the periods that are associated with factors that have exponent $\ge 3$.

eval gfper "?msd_fib Ei (p>=1) & (Aj (j<=2*p) => GF[i+j]=GF[i+j+p])":

The predicate above produces the automaton in Figure 3, which shows that these periods are of the form $10010^*$ in Fibonacci representation.

<figure><img src="image_4.png" /><figcaption>**Fig. 3:** Automaton for periods associated with $3^+$-powers in $w$.</figcaption></figure>
<figure><img src="image_3.png" /><figcaption>**Fig. 2:** Fibonacci automaton for $w = g(\varphi^{\omega}(0))$.</figcaption></figure>

**Theorem 3.** The word $w$ does not contain antisquares other than 01 and 10, and has critical exponent $2 + \alpha$.

**Proof:** We write a Walnut formula asserting that there exists an antisquare of order $\ge 2$, as follows:

eval antisq "?msd_fib Ei,n (n>=2) & At (t<n) => GF[i+t]!:=GF[i+n+t]":

This returns FALSE, so there are no antisquares of order $\ge 2$.

We now compute the periods that are associated with factors that have exponent $\ge 3$.

eval gfper "?msd_fib Ei (p>=1) & (Aj (j<=2*p) => GF[i+j]=GF[i+j+p])":

The predicate above produces the automaton in Figure 3, which shows that these periods are of the form $10010^*$ in Fibonacci representation.

<figure><img src="image_4.png" /><figcaption>**Fig. 3:** Automaton for periods associated with $3^+$-powers in $w$.</figcaption></figure>
Next, we compute the pairs $(n, p)$ such that $w$ contains a factor of length $n + p$ with period $p$ of the form $10010^*$ and $n + p$ is the longest length of any factor with this period.

```
reg pows msd_fib "0*10010*";
def maximalreps "?msd_fib Ei
(Aj (j<n) => GF[i+j] = GF[i+j+p]) & (GF[i+n] != GF[i+n+p])":
eval highestpow "?msd_fib (p>=1) & $pows(p) &
$maximalreps(n,p) & (Am $maximalreps(m,p) => m <= n)":
```

The automaton produced by the predicate highestpow is given in Figure 4.

<figure><img src="image_5.png" /><figcaption>Fig. 4: Automaton for pairs $(n, p)$ associated with highest powers in $w$.</figcaption></figure>

The strings accepted by this automaton, omitting the leading `[0, 0]`, are as follows:

* `[1, 0][0, 0][0, 1][0, 0][0, 0][0, 1]`

* `[1, 0][0, 0][0, 1][0, 0][0, 0][1, 1][0, 0]`

* `[1, 0][0, 0][0, 1][0, 0][1, 0][1, 0]([1, 0][0, 0])^k[0, 0][1, 0][0, 0], k \ge 0`

* `[1, 0][0, 0][0, 1][0, 0][1, 0][1, 0]([1, 0][0, 0])^k[0, 0][0, 0], k \ge 0`

These correspond, respectively, to the values

* $(n, p) = (13, 6) = (2F_6 - 3, 2F_4)$

* $(n, p) = (23, 10) = (2F_7 - 3, 2F_5)$

* $(n, p) = (F_{2k+10} + F_3 + \sum_{3 \le i \le k+3} F_{2i}, F_{2k+8} + F_{2k+5}) = (2F_{2k+9} - 3, 2F_{2k+7}) \text{ for } k \ge 0$

* $(n, p) = (F_{2k+9} + \sum_{3 \le i \le k+3} F_{2i-1}, F_{2k+7} + F_{2k+4}) = (2F_{2k+8} - 3, 2F_{2k+6}) \text{ for } k \ge 0$

where we have used the well-known Fibonacci identities

$$F_2 + F_4 + F_6 + \dots + F_{2t} = F_{2t+1} - 1$$

$$F_1 + F_3 + F_5 + \dots + F_{2t-1} = F_{2t}.$$
Next, we compute the pairs $(n, p)$ such that $w$ contains a factor of length $n + p$ with period $p$ of the form $10010^*$ and $n + p$ is the longest length of any factor with this period.

```
reg pows msd_fib "0*10010*";
def maximalreps "?msd_fib Ei
(Aj (j<n) => GF[i+j] = GF[i+j+p]) & (GF[i+n] != GF[i+n+p])":
eval highestpow "?msd_fib (p>=1) & $pows(p) &
$maximalreps(n,p) & (Am $maximalreps(m,p) => m <= n)":
```

The automaton produced by the predicate highestpow is given in Figure 4.

<figure><img src="image_5.png" /><figcaption>Fig. 4: Automaton for pairs $(n, p)$ associated with highest powers in $w$.</figcaption></figure>

The strings accepted by this automaton, omitting the leading `[0, 0]`, are as follows:

* `[1, 0][0, 0][0, 1][0, 0][0, 0][0, 1]`

* `[1, 0][0, 0][0, 1][0, 0][0, 0][1, 1][0, 0]`

* `[1, 0][0, 0][0, 1][0, 0][1, 0][1, 0]([1, 0][0, 0])^k[0, 0][1, 0][0, 0], k \ge 0`

* `[1, 0][0, 0][0, 1][0, 0][1, 0][1, 0]([1, 0][0, 0])^k[0, 0][0, 0], k \ge 0`

These correspond, respectively, to the values

* $(n, p) = (13, 6) = (2F_6 - 3, 2F_4)$

* $(n, p) = (23, 10) = (2F_7 - 3, 2F_5)$

* $(n, p) = (F_{2k+10} + F_3 + \sum_{3 \le i \le k+3} F_{2i}, F_{2k+8} + F_{2k+5}) = (2F_{2k+9} - 3, 2F_{2k+7}) \text{ for } k \ge 0$

* $(n, p) = (F_{2k+9} + \sum_{3 \le i \le k+3} F_{2i-1}, F_{2k+7} + F_{2k+4}) = (2F_{2k+8} - 3, 2F_{2k+6}) \text{ for } k \ge 0$

where we have used the well-known Fibonacci identities

$$F_2 + F_4 + F_6 + \dots + F_{2t} = F_{2t+1} - 1$$

$$F_1 + F_3 + F_5 + \dots + F_{2t-1} = F_{2t}.$$
Now the exponent of these finite factors is $(n+p)/p$, which is

$$ \frac{2F_j + 2F_{j-2} - 3}{2F_{j-2}} $$

for $j \ge 6$. These quotients tend to $2 + \alpha$ from below, and hence the critical exponent is $2 + \alpha$. $\square$

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

### 3 Optimality of the previous construction

In this section we show that the critical exponent of the word constructed in Section 2 is best possible; i.e., that every infinite good word has critical exponent at least $2 + \alpha$. It is somewhat easier to work with bi-infinite words, so we begin with results concerning bi-infinite words and then explain at the end of the section how to obtain the desired result for right-infinite words.

If $S$ is a set of nonempty finite words, then by $\omega S\omega$ we mean the set of bi-infinite words made up of concatenations of the elements of $S$.

**Theorem 4.** Every bi-infinite binary word avoiding 4-powers and $\{11, 000, 10101\}$ has the same set of factors as $f$.

**Proof:** First, we check that $f$ avoids 4-powers and $\{11, 000, 10101\}$.

Now consider a bi-infinite binary word $w$ avoiding 4-powers and $\{11, 000, 10101\}$. Since $w$ avoids 11, we have $w \in \omega\{01, 0\}^\omega$. Thus there exists a bi-infinite word $v$ such that $w = h(v)$, where $h$ is the morphism $0 \to 01, 1 \to 0$. Now it suffices to show that the pre-image $v$ also avoids 4-powers and $\{11, 000, 10101\}$. Clearly, $v$ avoids 4-powers, since otherwise $w = h(v)$ would contain a 4-power. Now we show by contradiction that $v$ avoids every factor in $\{11, 000, 10101\}$.

* If $v$ contains 11, then $v$ contains 110. So $w$ contains $h(110) = 0001$—a contradiction, since $w$ avoids 000.

* If $v$ contains 000 then $w$ contains $h(000) = 010101$—a contradiction, since $w$ avoids 10101.

* If $v$ contains 10101 then $v$ contains $0101010$, since $v$ avoids 11. So $w$ contains $h(0101010) = 01001001001$. Since $w$ avoids 11, we see that $w$ contains $010010010010 = (010)^4$—a contradiction, since $w$ avoids 4-powers.

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

**Lemma 5.** Every bi-infinite binary word avoiding 4-powers and

$$ F = \{0011, 0110, 1100, 1001, 010101, 101010, 1000101110, 0111010001, 101110111011101, 010001000100010\} $$

has the same set of factors as $g(f)$ or $g(\overline{f})$.

**Proof:** Notice that $F$ is closed under bitwise complement and reversal. Let $w$ be a bi-infinite binary word avoiding 4-powers and $F$. Suppose that $w$ contains $001011$.
Now the exponent of these finite factors is $(n+p)/p$, which is

$$ \frac{2F_j + 2F_{j-2} - 3}{2F_{j-2}} $$

for $j \ge 6$. These quotients tend to $2 + \alpha$ from below, and hence the critical exponent is $2 + \alpha$. $\square$

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

### 3 Optimality of the previous construction

In this section we show that the critical exponent of the word constructed in Section 2 is best possible; i.e., that every infinite good word has critical exponent at least $2 + \alpha$. It is somewhat easier to work with bi-infinite words, so we begin with results concerning bi-infinite words and then explain at the end of the section how to obtain the desired result for right-infinite words.

If $S$ is a set of nonempty finite words, then by $\omega S\omega$ we mean the set of bi-infinite words made up of concatenations of the elements of $S$.

**Theorem 4.** Every bi-infinite binary word avoiding 4-powers and $\{11, 000, 10101\}$ has the same set of factors as $f$.

**Proof:** First, we check that $f$ avoids 4-powers and $\{11, 000, 10101\}$.

Now consider a bi-infinite binary word $w$ avoiding 4-powers and $\{11, 000, 10101\}$. Since $w$ avoids 11, we have $w \in \omega\{01, 0\}^\omega$. Thus there exists a bi-infinite word $v$ such that $w = h(v)$, where $h$ is the morphism $0 \to 01, 1 \to 0$. Now it suffices to show that the pre-image $v$ also avoids 4-powers and $\{11, 000, 10101\}$. Clearly, $v$ avoids 4-powers, since otherwise $w = h(v)$ would contain a 4-power. Now we show by contradiction that $v$ avoids every factor in $\{11, 000, 10101\}$.

* If $v$ contains 11, then $v$ contains 110. So $w$ contains $h(110) = 0001$—a contradiction, since $w$ avoids 000.

* If $v$ contains 000 then $w$ contains $h(000) = 010101$—a contradiction, since $w$ avoids 10101.

* If $v$ contains 10101 then $v$ contains $0101010$, since $v$ avoids 11. So $w$ contains $h(0101010) = 01001001001$. Since $w$ avoids 11, we see that $w$ contains $010010010010 = (010)^4$—a contradiction, since $w$ avoids 4-powers.

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

**Lemma 5.** Every bi-infinite binary word avoiding 4-powers and

$$ F = \{0011, 0110, 1100, 1001, 010101, 101010, 1000101110, 0111010001, 101110111011101, 010001000100010\} $$

has the same set of factors as $g(f)$ or $g(\overline{f})$.

**Proof:** Notice that $F$ is closed under bitwise complement and reversal. Let $w$ be a bi-infinite binary word avoiding 4-powers and $F$. Suppose that $w$ contains $001011$.
* Since $1001 \in F$ and $0110 \in F$, the word $w$ contains $00010111$.

* Since $0000$ and $1111$ are $4$-powers, the word $w$ contains $1000101110$.

This is a contradiction since $1000101110 \in F$. So $w$ avoids $001011$. By considering the complement, the word $w$ also avoids $110100$. Now suppose that $w$ contains $110111011$.

* Since $0110 \in F$, the word $w$ contains $11101110111$.

* Since $1111$ is a $4$-power, the word $w$ contains $0111011101110$.

* Since $0011 \in F$ and $1100 \in F$, the word $w$ contains $101110111011101$.

This is a contradiction since $101110111011101 \in F$. So $w$ avoids $110111011$. By considering the complement, the word $w$ also avoids $001000100$. Thus, $w$ avoids $4$-powers and

$$F' = \{0011, 0110, 1100, 1001, 010101, 101010, 001011, 110100, 110111011, 001000100\}$$

Notice that $F'$ is closed under complement and reversal. By symmetry, we now suppose that $w$ contains $11$. Notice that $111, 11011$, and $1101011$ are the only possible factors of $w$ that start with $11$, end with two identical letters, and contain two identical letters only as a prefix and a suffix. In particular, the word $w$ avoids $00$. Moreover, the blocks of consecutive $1$'s have length $1$ or $3$. So $w \in \omega\{01, 11\}^\omega$. Thus $w = g(v)$ for some bi-infinite binary word $v$.

Since $w$ avoids $4$-powers, the word $v$ also avoids $4$-powers. Moreover,

* $g(11) = 1111$ is a $4$-power,

* $g(000) = 010101$ belongs to $F$,

* $g(10101) = 1101110111$ contains $110111011 \in F'$.

So $v$ also avoids $\{11, 000, 10101\}$. By Theorem 4, the word $v$ has the same set of factors as $f$. That is, the word $w$ has the same set of factors as $g(f)$. $\square$

**Theorem 6.** Every good bi-infinite binary word has critical exponent at least $2 + \alpha$.

**Proof:** Suppose that $w$ is a good bi-infinite binary word; that is, it contain no antisquares except possibly $01$ and $10$. Also assume $w$ has critical exponent smaller than $2+\alpha$. Consider the set $F$ from Lemma 5 and notice that $F \setminus \{101110111011101, 010001000100010\}$ contains only antisquares. So $w$ avoids $4$-powers and $F \setminus \{101110111011101, 010001000100010\}$. Moreover, $w$ avoids $101110111011101 = (1011)^{15/4}$ since $15/4 > 2+\alpha$. By symmetry, $w$ also avoids $010001000100010$. So $w$ avoids $4$-powers and $F$.

By Lemma 5, $w$ has the same set of factors as either $g(f)$ or $g(\overline{f})$. So $w$ has critical exponent $2+\alpha$. $\square$

**Corollary 7.** Every (right-) infinite good binary word has critical exponent at least $2 + \alpha$.

**Proof:** Let $w$ be an infinite good binary word, and let $\text{RecFac}(w)$ denote the set of its recurrent factors. That is, the set $\text{RecFac}(w)$ consists of the factors of $w$ that appear infinitely often in $w$. Then for any $y \in \text{RecFac}(w)$, we see that $y$ has arbitrarily large two-sided extensions in $\text{RecFac}(w)$. By a 'two-sided' analogue of König's infinity lemma, there exists a bi-infinite word $w'$ such that every factor of $w'$ is an element of $\text{RecFac}(w)$. By Theorem 6, the bi-infinite word $w'$ has critical exponent at least $2+\alpha$, and thus so does the infinite word $w$. $\square$
* Since $1001 \in F$ and $0110 \in F$, the word $w$ contains $00010111$.

* Since $0000$ and $1111$ are $4$-powers, the word $w$ contains $1000101110$.

This is a contradiction since $1000101110 \in F$. So $w$ avoids $001011$. By considering the complement, the word $w$ also avoids $110100$. Now suppose that $w$ contains $110111011$.

* Since $0110 \in F$, the word $w$ contains $11101110111$.

* Since $1111$ is a $4$-power, the word $w$ contains $0111011101110$.

* Since $0011 \in F$ and $1100 \in F$, the word $w$ contains $101110111011101$.

This is a contradiction since $101110111011101 \in F$. So $w$ avoids $110111011$. By considering the complement, the word $w$ also avoids $001000100$. Thus, $w$ avoids $4$-powers and

$$F' = \{0011, 0110, 1100, 1001, 010101, 101010, 001011, 110100, 110111011, 001000100\}$$

Notice that $F'$ is closed under complement and reversal. By symmetry, we now suppose that $w$ contains $11$. Notice that $111, 11011$, and $1101011$ are the only possible factors of $w$ that start with $11$, end with two identical letters, and contain two identical letters only as a prefix and a suffix. In particular, the word $w$ avoids $00$. Moreover, the blocks of consecutive $1$'s have length $1$ or $3$. So $w \in \omega\{01, 11\}^\omega$. Thus $w = g(v)$ for some bi-infinite binary word $v$.

Since $w$ avoids $4$-powers, the word $v$ also avoids $4$-powers. Moreover,

* $g(11) = 1111$ is a $4$-power,

* $g(000) = 010101$ belongs to $F$,

* $g(10101) = 1101110111$ contains $110111011 \in F'$.

So $v$ also avoids $\{11, 000, 10101\}$. By Theorem 4, the word $v$ has the same set of factors as $f$. That is, the word $w$ has the same set of factors as $g(f)$. $\square$

**Theorem 6.** Every good bi-infinite binary word has critical exponent at least $2 + \alpha$.

**Proof:** Suppose that $w$ is a good bi-infinite binary word; that is, it contain no antisquares except possibly $01$ and $10$. Also assume $w$ has critical exponent smaller than $2+\alpha$. Consider the set $F$ from Lemma 5 and notice that $F \setminus \{101110111011101, 010001000100010\}$ contains only antisquares. So $w$ avoids $4$-powers and $F \setminus \{101110111011101, 010001000100010\}$. Moreover, $w$ avoids $101110111011101 = (1011)^{15/4}$ since $15/4 > 2+\alpha$. By symmetry, $w$ also avoids $010001000100010$. So $w$ avoids $4$-powers and $F$.

By Lemma 5, $w$ has the same set of factors as either $g(f)$ or $\overline{g(f)}$. So $w$ has critical exponent $2+\alpha$. $\square$

**Corollary 7.** Every (right-) infinite good binary word has critical exponent at least $2 + \alpha$.

**Proof:** Let $w$ be an infinite good binary word, and let $\text{RecFac}(w)$ denote the set of its recurrent factors. That is, the set $\text{RecFac}(w)$ consists of the factors of $w$ that appear infinitely often in $w$. Then for any $y \in \text{RecFac}(w)$, we see that $y$ has arbitrarily large two-sided extensions in $\text{RecFac}(w)$. By a 'two-sided' analogue of König's infinity lemma, there exists a bi-infinite word $w'$ such that every factor of $w'$ is an element of $\text{RecFac}(w)$. By Theorem 6, the bi-infinite word $w'$ has critical exponent at least $2+\alpha$, and thus so does the infinite word $w$. $\square$
# 4 The class AOℓ

Instead of avoiding all antisquares of order greater than one, we could consider avoiding arbitrarily large antisquares.

**Proposition 8.** Every infinite binary word avoiding $\frac{7}{3}$-powers contains arbitrarily large antisquares.

**Proof:** By a result of Karhumäki and Shallit (2004), we know that every infinite binary word avoiding $\frac{7}{3}$-powers can be written in the form $x_1\mu(x_2\mu(x_3\mu(\cdots))\cdots)$, where $x_i \in \{\epsilon, 0, 1, 00, 11\}$ and $\mu$ is the Thue-Morse morphism, defined by $\mu: 0 \to 01, 1 \to 10$. It follows that every such word must contain arbitrarily large factors of the form $\mu^n(0)$. But every word $\mu^n(0)$ for $n \ge 1$ is an antisquare. $\square$

On the other hand, we can prove the following result on the class AOℓ of binary words avoiding antisquares of order $\ge \ell$:

**Theorem 9.** There exists an infinite $\beta^+$-free binary word containing no antisquare of order $\ge \ell$ for the following pairs $(\ell, \beta)$:

(a) $(2, 2 + \alpha)$

(b) $(3, 8/3)$

(c) $(5, 5/2)$

(d) $(6, 7/3)$

These are all optimal.

**Proof:** Item (a) was already proved in Section 2. For each of the remaining pairs $(\ell, \beta)$, we apply a morphism $\xi_\ell$ to any ternary squarefree infinite word $w$ and check that it has the desired properties. The morphisms are given in Table 1. The columns are $\ell$, where the word contains no antisquares of order $\ge \ell$; $\beta$, where the word avoids $\beta^+$ powers; $s$, the size of the uniform morphism; and the morphism.

<table><caption>**Tab. 1:** Morphisms generating words in AOℓ.</caption><thead><tr><th>ℓ</th><th>β</th><th>s</th><th>morphism name</th><th>morphism</th></tr></thead><tbody><tr><td>3</td><td>8/3</td><td>36</td><td>ξ<sub>3</sub></td><td>0 → 001001010011001010010011001001010011<br>1 → 001001010010011001010011001010010011<br>2 → 001001010010011001001010011001010011</td></tr><tr><td>5</td><td>5/2</td><td>19</td><td>ξ<sub>5</sub></td><td>0 → 0010110100101101011<br>1 → 0010110100101100101<br>2 → 0010110011001010011</td></tr><tr><td>6</td><td>7/3</td><td>37</td><td>ξ<sub>6</sub></td><td>0 → 0010011010010110100110110011010011011<br>1 → 0010011010010110100110110010011010011<br>2 → 0010011010010110100110110010011001011</td></tr></tbody></table>

To verify the $\beta^+$-freeness of $\xi_\ell(w)$ we use (Mol et al., 2020, Lemma 23). In order to do so, we check that $\xi_\ell$ is synchronizing and that $\xi_\ell(u)$ is $\beta^+$-free for every squarefree ternary word $u$ of length $t$, where
# 4 The class AOℓ

Instead of avoiding all antisquares of order greater than one, we could consider avoiding arbitrarily large antisquares.

**Proposition 8.** Every infinite binary word avoiding $\frac{7}{3}$-powers contains arbitrarily large antisquares.

**Proof:** By a result of Karhumäki and Shallit (2004), we know that every infinite binary word avoiding $\frac{7}{3}$-powers can be written in the form $x_1\mu(x_2\mu(x_3\mu(\cdots))\cdots)$, where $x_i \in \{\epsilon, 0, 1, 00, 11\}$ and $\mu$ is the Thue-Morse morphism, defined by $\mu: 0 \to 01, 1 \to 10$. It follows that every such word must contain arbitrarily large factors of the form $\mu^n(0)$. But every word $\mu^n(0)$ for $n \ge 1$ is an antisquare. $\square$

On the other hand, we can prove the following result on the class AOℓ of binary words avoiding antisquares of order $\ge \ell$:

**Theorem 9.** There exists an infinite $\beta^+$-free binary word containing no antisquare of order $\ge \ell$ for the following pairs $(\ell, \beta)$:

(a) $(2, 2 + \alpha)$

(b) $(3, 8/3)$

(c) $(5, 5/2)$

(d) $(6, 7/3)$

These are all optimal.

**Proof:** Item (a) was already proved in Section 2. For each of the remaining pairs $(\ell, \beta)$, we apply a morphism $\xi_\ell$ to any ternary squarefree infinite word $w$ and check that it has the desired properties. The morphisms are given in Table 1. The columns are $\ell$, where the word contains no antisquares of order $\ge \ell$; $\beta$, where the word avoids $\beta^+$ powers; $s$, the size of the uniform morphism; and the morphism.

<table><caption>**Tab. 1:** Morphisms generating words in AOℓ.</caption><thead><tr><th>ℓ</th><th>β</th><th>s</th><th>morphism name</th><th>morphism</th></tr></thead><tbody><tr><td>3</td><td>8/3</td><td>36</td><td>ξ<sub>3</sub></td><td>0 &rarr; 001001010011001010010011001001010011<br>1 &rarr; 001001010010011001010011001010010011<br>2 &rarr; 001001010010011001001010011001010011</td></tr><tr><td>5</td><td>5/2</td><td>19</td><td>ξ<sub>5</sub></td><td>0 &rarr; 0010110100101101011<br>1 &rarr; 0010110100101100101<br>2 &rarr; 0010110011001010011</td></tr><tr><td>6</td><td>7/3</td><td>37</td><td>ξ<sub>6</sub></td><td>0 &rarr; 0010011010010110100110110011010011011<br>1 &rarr; 0010011010010110100110110010011010011<br>2 &rarr; 0010011010010110100110110010011001011</td></tr></tbody></table>

To verify the $\beta^+$-freeness of $\xi_\ell(w)$ we use (Mol et al., 2020, Lemma 23). In order to do so, we check that $\xi_\ell$ is synchronizing and that $\xi_\ell(u)$ is $\beta^+$-free for every squarefree ternary word $u$ of length $t$, where
t is specified by (Mol et al., 2020, Lemma 23). In order to show that $\xi_{\ell}(w)$ contains no antisquares of order $\ge \ell$, we find a length $m$ such that if $v$ and its complement are both factors of $\xi_{\ell}(w)$, then $|v| \le m$. We can then check that $\xi_{\ell}(w)$ contains no antisquares of order $\ge \ell$ by exhaustively checking all factors of length at most $2m$. The parameters $t$ and $m$ for each $\xi_{\ell}$ are given in Table 2.

<table><caption>**Tab. 2:** Parameters for checking correctness of $\xi_{\ell}$.</caption><thead><tr><th>morphism</th><th>l</th><th>β</th><th>t</th><th>m</th></tr></thead><tbody><tr><td>ξ<sub>3</sub></td><td>3</td><td>8/3</td><td>8</td><td>6</td></tr><tr><td>ξ<sub>5</sub></td><td>5</td><td>5/2</td><td>10</td><td>16</td></tr><tr><td>ξ<sub>6</sub></td><td>6</td><td>7/3</td><td>14</td><td>26</td></tr></tbody></table>

The optimality of item (a) was already proved in Section 3. The optimality of the remaining items can be established by depth-first search. For each pair $(\ell, \beta)$, a longest word containing no antisquares of order $\ge \ell$, but avoiding $\beta$-powers (instead of $\beta^+$), is given in Table 3. The columns give $\ell, \beta$, the length $L$ of a longest such word, and a longest such word.

<table><caption>**Tab. 3:** Longest words avoiding $\beta$-powers and containing no antisquares of order $\ge \ell$.</caption><thead><tr><th>l</th><th>β</th><th>L</th><th>example</th></tr></thead><tbody><tr><td>4</td><td>8/3</td><td>29</td><td>00100101001100101001100110100</td></tr><tr><td>5</td><td>5/2</td><td>32</td><td>00100101100101101001011001011011</td></tr><tr><td>6</td><td>7/3</td><td>30</td><td>001011001101001011010011001011</td></tr></tbody></table>

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

# 5 The class $AN_n$

In this section, we consider the class $AN_n$ of binary words containing no more than $n$ distinct antisquares as factors.

**Theorem 10.** There exists an infinite $\beta^+$-free binary word containing no more than $n$ antisquares for the following pairs $(n, \beta)$:

(a) $(2, 2 + \alpha)$

(b) $(3, 3)$

(c) $(6, 8/3)$

(d) $(9, 38/15)$

(e) $(10, 5/2)$

(f) $(15, 17/7)$
t is specified by (Mol et al., 2020, Lemma 23). In order to show that $\xi_{\ell}(w)$ contains no antisquares of order $\ge \ell$, we find a length $m$ such that if $v$ and its complement are both factors of $\xi_{\ell}(w)$, then $|v| \le m$. We can then check that $\xi_{\ell}(w)$ contains no antisquares of order $\ge \ell$ by exhaustively checking all factors of length at most $2m$. The parameters $t$ and $m$ for each $\xi_{\ell}$ are given in Table 2.

<table><caption>**Tab. 2:** Parameters for checking correctness of $\xi_{\ell}$.</caption><thead><tr><th>morphism</th><th>l</th><th>β</th><th>t</th><th>m</th></tr></thead><tbody><tr><td>ξ<sub>3</sub></td><td>3</td><td>8/3</td><td>8</td><td>6</td></tr><tr><td>ξ<sub>5</sub></td><td>5</td><td>5/2</td><td>10</td><td>16</td></tr><tr><td>ξ<sub>6</sub></td><td>6</td><td>7/3</td><td>14</td><td>26</td></tr></tbody></table>

The optimality of item (a) was already proved in Section 3. The optimality of the remaining items can be established by depth-first search. For each pair $(\ell, \beta)$, a longest word containing no antisquares of order $\ge \ell$, but avoiding $\beta$-powers (instead of $\beta^+$), is given in Table 3. The columns give $\ell, \beta$, the length $L$ of a longest such word, and a longest such word.

<table><caption>**Tab. 3:** Longest words avoiding $\beta$-powers and containing no antisquares of order $\ge \ell$.</caption><thead><tr><th>l</th><th>β</th><th>L</th><th>example</th></tr></thead><tbody><tr><td>4</td><td>8/3</td><td>29</td><td>00100101001100101001100110100</td></tr><tr><td>5</td><td>5/2</td><td>32</td><td>00100101100101101001011001011011</td></tr><tr><td>6</td><td>7/3</td><td>30</td><td>001011001101001011010011001011</td></tr></tbody></table>

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

# 5 The class $AN_n$

In this section, we consider the class $AN_n$ of binary words containing no more than $n$ distinct antisquares as factors.

**Theorem 10.** There exists an infinite $\beta^+$-free binary word containing no more than $n$ antisquares for the following pairs $(n, \beta)$:

(a) $(2, 2 + \alpha)$

(b) $(3, 3)$

(c) $(6, 8/3)$

(d) $(9, 38/15)$

(e) $(10, 5/2)$

(f) $(15, 17/7)$
(g) (16, 7/3).

These are all optimal.

**Proof:** Item (a) was already proved in Section 2. For the remaining cases, the proof is similar to that of Theorem 9: for each pair $(n, \beta)$, we apply a morphism $\zeta_n$ to any ternary squarefree infinite word $w$ and check that it has the desired properties. The morphisms are given in Table 4. The columns are $n$, the largest number of allowed antisquares; $\beta$, where the word avoids $\beta^+$ powers; $s$, the size of the uniform morphism; and the morphism.

<table><caption>**Tab. 4:** Morphisms generating words in $AN_n$.</caption><thead><tr><th>n</th><th>β</th><th>s</th><th>morphism name</th><th>morphism</th></tr></thead><tbody><tr><td>3</td><td>3</td><td>13</td><td>ζ<sub>3</sub></td><td>0 → 0010001000101<br>1 → 0001001000101<br>2 → 0001000100101</td></tr><tr><td>6</td><td>8/3</td><td>36</td><td>ζ<sub>6</sub></td><td>0 → 0010010100110010100100110010010011<br>1 → 0010010100100110010100110010010010011<br>2 → 0010010100100110010010010100110010010011</td></tr><tr><td>9</td><td>38/15</td><td>192</td><td>ζ<sub>9</sub></td><td>0 → 0010100101100110010100101100110010110010100101100110101100110010<br>110010100101100110010110010100101100110101100110010110010101001011<br>00110010011001010010110011001011001010010100110011010110011001011<br>1 → 0010100101100110010100101100110010110010100101001100110010<br>11001010010110011001010011001010011001010010100110011001011<br>011001100101100101001011001100101100101001010011001100101011<br>2 → 0010100101100110010100101100110010110010100101100110010<br>1001011001100101100101001011001100101001011001100101001011<br>0011001010011001001001011001100101100101001010011001100101011</td></tr><tr><td>10</td><td>5/2</td><td>75</td><td>ζ<sub>10</sub></td><td>0 → 001010010110011001010010010100101100110010110010100101001100110010<br>10011001011<br>1 → 001010010110011001010010011001010010110011001010010100110011<br>2 → 0010100101100110010100110010100101100110010100101100110010<br>10011001011</td></tr><tr><td>15</td><td>17/7</td><td>194</td><td>ζ<sub>15</sub></td><td>0 → 0010011001011001001101001011001001100101100100110010100101100100110010<br>0011001001101001011001001011001001100100110010100101100100110010<br>11010011001001101001011001001100101100100101001100100110010<br>1 → 00100110010110010011010010110010011001011001010010110010<br>00110010011001010011001001100101100100110010100101100100110010<br>11001011001001101001011001001100101001011001001100101001011<br>2 → 00100110010110010011010010110010011001011001011001010010<br>001100100110010110010100101100101100101100101001011001010010<br>110010110010011001010010110010110010100101100101100101001011</td></tr><tr><td>16</td><td>7/3</td><td>192</td><td>ζ<sub>16</sub></td><td>0 → 001001100101100100110100101100100110010100101100100110010<br>1011001001100110010011010010110010011001011001001010010110010<br>01101001100100110100101100100110010110010100101100101001011<br>1 → 00100110010110010011010010110010011001011001010010110010<br>010110010011010010110011010010110010011001010010100110010<br>011001011001001101001011001001100101001011001010010110010<br>2 → 0010011001011001001101001011001001100101001011001010010<br>010110010011001010110010011001011001001011001010010110010<br>011001011001001101001011001010010110010100101100101001011</td></tr></tbody></table>

To verify the $\beta^+$-freeness of $\zeta_n(w)$ we use (Mol et al., 2020, Lemma 23). In order to do so, we check
# 6 Minimal antisquares

Consider the language $L$ of all finite good words. In this section we determine the minimal antisquares or minimal forbidden factors for $L$ Mignosi et al. (2002). These are the words $w$ such that $w$ is an antisquare, but $w$ properly contains no antisquare factors, except possibly 01 and 10. This characterization will be useful for enumerating the number of length-$n$ words in $L$.

The goal is to prove the following theorem:

**Theorem 11.** The minimal antisquares are, organized by order $n$, as follows:

* $n = 1$: $\{01, 10\}$

* $n = 2$: $\{0011, 0110, 1001, 1100\}$

* $n = 3$: $\{010101, 101010\}$

* $n = 4$: $\emptyset$

* $n \ge 5$: all the $2n$ conjugates (cyclic shifts) of $0^{n-2}101^{n-2}01$.

We start with some basic results about antisquares.

**Lemma 12.** If $x$ is an antisquare, so is every conjugate of $x$.

*Proof:* Write $x$ as $ay\overline{ay}$ for some (possibly empty) word $y$. Then a cyclic shift by one symbol gives $y\overline{ay}$, which is clearly an antisquare. Repeating this argument $|x|$ times gives the result. $\square$

**Lemma 13.** A word $w$ is a minimal antisquare if and only if all conjugates of $w$ are minimal antisquares.

*Proof:* Let $w = u\bar{u}$. Let us prove the forward direction first. Assume, contrary to what we want to prove, that $w$ is a minimal antisquare, but some rotation of $w$ contains a shorter antisquare, other than 01 and 10. Let $rs$ be an antisquare of minimum length with $|rs| > 2$ that is not a factor of $w$, but is a factor of some rotation of $w$. Then we can write $w = sxr$ with $r, s, x \neq \epsilon$. There are three cases to consider:

$|r| \ge |\bar{u}|$: Let $t$ be defined by $r = t\bar{u}$. Then $w = u\bar{u} = sxt\overline{s\bar{x}t}$, where $rs = t\overline{s\bar{x}t}s$ is an antisquare. If $t = \epsilon$, then $rs = \overline{s\bar{x}s}$; hence $w = s\overline{x\bar{s}x}$ contains the antisquare $sx\overline{s}$. This is a contradiction, since we assumed $w$ does not have a shorter antisquare, but $sx\overline{s}$ is an antisquare in $w$ with $s, x \neq \epsilon$. Therefore $t \neq \epsilon$.

Since $w$ and $rs$ are both antisquares, they have even length. Therefore $|x|$ is even. Consider the factorization $x = x_1x_2$ with $|x_1| = |x_2|$. Then $rs = t\overline{s\bar{x}t}s = t\overline{s\bar{x}}_1\overline{x_2t}s$ is an antisquare, where $|t\overline{s\bar{x}}_1| = |\overline{x_2t}s|$. Therefore, $t\overline{s\bar{x}}_1$ must end with $t\overline{s}$ and $\overline{x_2t}s$ must begin with $\overline{t}s$, giving the antisquare $t\overline{s\bar{t}}s$, which is not 01 or 10 (since $t, s \neq \epsilon$), and is shorter than $rs$. This contradicts our assumption that $rs$ is the smallest such antisquare.

$|s| \ge |u|$: Let $s$ be defined by $s = ut$. Then $w = u\bar{u} = \overline{t\bar{x}r}\overline{txr}$. Now $rs = r\overline{t\bar{x}r}\overline{t}$ is an antisquare, and hence the complement $\overline{rs} = \overline{r}\overline{txr}\overline{t}$ is also an antisquare. Let $r' = \overline{r}\overline{txr}$ and $s' = \overline{t}$. So we can write $w = \overline{t\bar{x}r}\overline{txr} = s'\overline{\bar{x}r}'$ where $r's'$ is an antisquare of the same length as $rs$, and $|r'| > |\bar{u}|$. This reduces the problem to the previous case.
# 6 Minimal antisquares

Consider the language $L$ of all finite good words. In this section we determine the minimal antisquares or minimal forbidden factors for $L$ Mignosi et al. (2002). These are the words $w$ such that $w$ is an antisquare, but $w$ properly contains no antisquare factors, except possibly 01 and 10. This characterization will be useful for enumerating the number of length-$n$ words in $L$.

The goal is to prove the following theorem:

**Theorem 11.** The minimal antisquares are, organized by order $n$, as follows:

* $n = 1$: $\{01, 10\}$

* $n = 2$: $\{0011, 0110, 1001, 1100\}$

* $n = 3$: $\{010101, 101010\}$

* $n = 4$: $\emptyset$

* $n \ge 5$: all the $2n$ conjugates (cyclic shifts) of $0^{n-2}101^{n-2}01$.

We start with some basic results about antisquares.

**Lemma 12.** If $x$ is an antisquare, so is every conjugate of $x$.

*Proof:* Write $x$ as $ay\overline{ay}$ for some (possibly empty) word $y$. Then a cyclic shift by one symbol gives $y\overline{ay}$, which is clearly an antisquare. Repeating this argument $|x|$ times gives the result. $\square$

**Lemma 13.** A word $w$ is a minimal antisquare if and only if all conjugates of $w$ are minimal antisquares.

*Proof:* Let $w = u\bar{u}$. Let us prove the forward direction first. Assume, contrary to what we want to prove, that $w$ is a minimal antisquare, but some rotation of $w$ contains a shorter antisquare, other than 01 and 10. Let $rs$ be an antisquare of minimum length with $|rs| > 2$ that is not a factor of $w$, but is a factor of some rotation of $w$. Then we can write $w = sxr$ with $r, s, x \ne \epsilon$. There are three cases to consider:

$|r| \ge |\bar{u}|$: Let $t$ be defined by $r = t\bar{u}$. Then $w = u\bar{u} = sxt\overline{s\bar{x}t}$, where $rs = t\overline{s\bar{x}t}s$ is an antisquare. If $t = \epsilon$, then $rs = \overline{s\bar{x}s}$; hence $w = s\overline{x\bar{s}x}$ contains the antisquare $sx\overline{s}$. This is a contradiction, since we assumed $w$ does not have a shorter antisquare, but $sx\overline{s}$ is an antisquare in $w$ with $s, x \ne \epsilon$. Therefore $t \ne \epsilon$.

Since $w$ and $rs$ are both antisquares, they have even length. Therefore $|x|$ is even. Consider the factorization $x = x_1x_2$ with $|x_1| = |x_2|$. Then $rs = t\overline{s\bar{x}t}s = t\overline{s\bar{x}}_1\overline{x_2t}s$ is an antisquare, where $|t\overline{s\bar{x}}_1| = |\overline{x_2t}s|$. Therefore, $t\overline{s\bar{x}}_1$ must end with $\overline{t}s$ and $\overline{x_2t}s$ must begin with $\overline{t}s$, giving the antisquare $t\overline{\overline{s\bar{x}}_1t}s$, which is not 01 or 10 (since $t, s \ne \epsilon$), and is shorter than $rs$. This contradicts our assumption that $rs$ is the smallest such antisquare.

$|s| \ge |u|$: Let $s$ be defined by $s = ut$. Then $w = u\bar{u} = \overline{t\bar{x}r}\overline{t}\overline{txr}$. Now $rs = r\overline{t\bar{x}r}\overline{t}$ is an antisquare, and hence the complement $\overline{rs} = \overline{r}\overline{txr}\overline{t}$ is also an antisquare. Let $r' = \overline{r}\overline{txr}$ and $s' = \overline{t}$. So we can write $w = \overline{t\bar{x}r}\overline{t}\overline{txr} = s'\overline{\bar{x}r}'$ where $r's'$ is an antisquare of the same length as $rs$, and $|r'| > |\bar{u}|$. This reduces the problem to the previous case.
$|s| < |u|, |r| < |\bar{u}|$: In this case we can write $u = sy$ and $\bar{u} = zr$ where $y, z \neq \epsilon$. This means that $u$ ends in $\bar{r}$ and $\bar{u}$ begins with $\bar{s}$, implying that $w$ contains the antisquare $\bar{rs}$. This contradicts the assumption that $w$ does not contain a shorter antisquare.

The reverse direction is easy. If $w$ contains a shorter antisquare, other than 01 and 10, then at least one rotation of $w$ also has the same antisquare. $\square$

We introduce some terminology. A *run* in a word is a maximal block of consecutive identical symbols. The *run-length encoding* $r: \Sigma^* \to \mathbb{N}^*$, where $\mathbb{N} = \{1, 2, 3, \dots\}$ is a map sending a word $x$ to the list of the lengths of the consecutive runs in $x$. For example, $r(\text{access}) = 1212$.

**Lemma 14.** If a nonempty word $x$ is an antisquare, then the number of runs it contains must be congruent to 2 or 3 (mod 4).

**Proof:** Write $x = u\bar{u}$ and consider the runs in $u$. If $u$ has $2k + 1$ runs, then so does $\bar{u}$. Furthermore, $u$ ends in a different letter than the start of $\bar{u}$. Hence $x$ has $4k + 2$ runs.

Otherwise $u$ has $2k$ runs. Then the last letter of $u$ is the same as the first letter of $\bar{u}$. Hence $x$ has $4k - 1$ runs. $\square$

**Lemma 15.** The word $0^k 10 1^{k} 01$ is a minimal antisquare for $k \ge 3$.

**Proof:** It is easy to see that $x = 0^k 10 1^{k} 01$ is an antisquare. Suppose $k \ge 3$ and suppose $x$ has an antisquare proper factor $w$ other than 01 and 10. Now $x$ has six runs, so by Lemma 14 we know that $w$ has either two, three, or six runs.

If $w$ has two runs, it must be of the form $a^i \bar{a}^i$ for $i \ge 2$, but inspection shows that $x$ has no factor of that form.

If $w$ has three runs, it must be of the form $a^i \bar{a}^{i+j} a^j$ for some $i, j \ge 1$. The only possibility is $i = 1$, $i + j = k$, $j = 1$, which forces $k = 2$, a contradiction.

Finally, if $w$ has six runs, then $w = 0^\ell 101 \ell 01$ for some $\ell < k$, which would not be a factor of $x$. $\square$

We are now ready to complete the proof of Theorem 11. We say $x$ has an *interior occurrence* of $y$ if we can write $x = \text{wyz}$ for nonempty words $w, z$.

**Proof** *Proof of Theorem 11.:* By combining Lemmas 12, 13, and 15, and verifying the listed cases for $n \le 4$, we see that all the words given in the statement of the theorem are minimal antisquares.

It now remains to see that there are no other minimal antisquares. The idea is to classify antisquares $x$ by the number of runs. In what follows, we assume, without loss of generality, that $x$ begins with 0.

Two runs: then $x = 0^i 1^i$ for some $i \ge 1$. If $i \ge 3$ then $x$ contains the antisquare 0011. So the only minimal antisquares are 01 and 0011.

Three runs: then $x = 0^i 1^{i+j} 0^j$. If either $i$ or $j$ is at least 2, then $x$ contains the antisquare 0011 or 1100. So the only minimal antisquare is 0110.

Six runs: then $x = 0^i 1^j 0^k 1^i 0^j 1^k$. If $i, j \ge 2$ then $x$ contains the antisquare 0011, and similarly if $j, k \ge 2$ and $k, i \ge 2$. It follows that $(i, j, k) \in \{(1, 1, 1), (1, 1, n), (1, n, 1), (n, 1, 1)\}$ for $n \ge 2$. The cases $(1, 1, 2), (1, 2, 1), (2, 1, 1)$ are ruled out by an antisquare of the form 1001 or 0110. So $(i, j, k) \in \{(1, 1, 1), (1, 1, n), (1, n, 1), (n, 1, 1)\}$ for $n \ge 3$. The case $(1, 1, 1)$ corresponds to the word 010101,
$|s| < |u|, |r| < |\bar{u}|$: In this case we can write $u = sy$ and $\bar{u} = zr$ where $y, z \neq \epsilon$. This means that $u$ ends in $\bar{r}$ and $\bar{u}$ begins with $\bar{s}$, implying that $w$ contains the antisquare $\bar{rs}$. This contradicts the assumption that $w$ does not contain a shorter antisquare.

The reverse direction is easy. If $w$ contains a shorter antisquare, other than 01 and 10, then at least one rotation of $w$ also has the same antisquare. $\square$

We introduce some terminology. A *run* in a word is a maximal block of consecutive identical symbols. The *run-length encoding* $r: \Sigma^* \to \mathbb{N}^*$, where $\mathbb{N} = \{1, 2, 3, \dots\}$ is a map sending a word $x$ to the list of the lengths of the consecutive runs in $x$. For example, $r(\text{access}) = 1212$.

**Lemma 14.** If a nonempty word $x$ is an antisquare, then the number of runs it contains must be congruent to 2 or 3 (mod 4).

**Proof:** Write $x = u\bar{u}$ and consider the runs in $u$. If $u$ has $2k + 1$ runs, then so does $\bar{u}$. Furthermore, $u$ ends in a different letter than the start of $\bar{u}$. Hence $x$ has $4k + 2$ runs.

Otherwise $u$ has $2k$ runs. Then the last letter of $u$ is the same as the first letter of $\bar{u}$. Hence $x$ has $4k - 1$ runs. $\square$

**Lemma 15.** The word $0^k 10 1^k 01$ is a minimal antisquare for $k \ge 3$.

**Proof:** It is easy to see that $x = 0^k 10 1^k 01$ is an antisquare. Suppose $k \ge 3$ and suppose $x$ has an antisquare proper factor $w$ other than 01 and 10. Now $x$ has six runs, so by Lemma 14 we know that $w$ has either two, three, or six runs.

If $w$ has two runs, it must be of the form $a^i \bar{a}^i$ for $i \ge 2$, but inspection shows that $x$ has no factor of that form.

If $w$ has three runs, it must be of the form $a^i \bar{a}^{i+j} a^j$ for some $i, j \ge 1$. The only possibility is $i = 1$, $i + j = k$, $j = 1$, which forces $k = 2$, a contradiction.

Finally, if $w$ has six runs, then $w = 0^\ell 101^\ell 01$ for some $\ell < k$, which would not be a factor of $x$. $\square$

We are now ready to complete the proof of Theorem 11. We say $x$ has an *interior occurrence* of $y$ if we can write $x = \text{wyz}$ for nonempty words $w, z$.

**Proof** *Proof of Theorem 11.:* By combining Lemmas 12, 13, and 15, and verifying the listed cases for $n \le 4$, we see that all the words given in the statement of the theorem are minimal antisquares.

It now remains to see that there are no other minimal antisquares. The idea is to classify antisquares $x$ by the number of runs. In what follows, we assume, without loss of generality, that $x$ begins with 0.

Two runs: then $x = 0^i 1^i$ for some $i \ge 1$. If $i \ge 3$ then $x$ contains the antisquare 0011. So the only minimal antisquares are 01 and 0011.

Three runs: then $x = 0^i 1^{i+j} 0^j$. If either $i$ or $j$ is at least 2, then $x$ contains the antisquare 0011 or 1100. So the only minimal antisquare is 0110.

Six runs: then $x = 0^i 1^j 0^k 1^i 0^j 1^k$. If $i, j \ge 2$ then $x$ contains the antisquare 0011, and similarly if $j, k \ge 2$ and $k, i \ge 2$. It follows that $(i, j, k) \in \{(1, 1, 1), (1, 1, n), (1, n, 1), (n, 1, 1)\}$ for $n \ge 2$. The cases $(1, 1, 2), (1, 2, 1), (2, 1, 1)$ are ruled out by an antisquare of the form 1001 or 0110. So $(i, j, k) \in \{(1, 1, 1), (1, 1, n), (1, n, 1), (n, 1, 1)\}$ for $n \ge 3$. The case $(1, 1, 1)$ corresponds to the word 010101,
and the remaining cases correspond to certain conjugates of $0^n 101^n 01$ for $n \ge 3$, already listed in the statement of the theorem.

Seven runs: then $x = 0^i 1^j 0^k 1^{i+l} 0^j 1^k 0^l$. Again, if $i, j \ge 2$, or $j, k \ge 2$, or $k, l \ge 2$, then $x$ contains a shorter antisquare 0011 or 1100. Since $i+l \ge 2$, the same argument rules out $k \ge 2$ and $j \ge 2$. So the only cases remaining are

$$ (i, j, k, l) \in \{(1, 1, 1, 1), (1, 1, 1, n), (n, 1, 1, 1), (n, 1, 1, n)\} $$

for $n \ge 2$. The first case (1, 1, 1, 1) corresponds to 010110101, which has the antisquare 0110, and it is easy to verify that the remaining cases are certain conjugates of $0^{n+1}101^{n+1}01$ for $n \ge 3$, already listed in the statement of the theorem.

It now remains to handle the case of more than 7 runs. By Lemma 14 $x$ has at least 10 runs. This involves a rather tedious examination of cases, based on the following three simple observations:

(a) if $r(x)$ contains two consecutive terms, both $\ge 2$, then $x$ contains the shorter antisquare 0011 or 1100;

(b) if $r(x)$ contains six consecutive terms $a1bc1d$ with $a \ge c$ and $b \le d$, then $x$ contains the shorter antisquare $0^c 10^b 1^c 01^b$ or its complement.

(c) if $r(x)$ contains an interior occurrence of 2, then $x$ contains the antisquare 0110 or 1001.

Suppose $x = u\bar{u}$. If $z = r(u)$ is of odd length, then $zz = r(x)$. If $z = r(u)$ is of even length, then writing $z = ayb$ with $a, b$ single numbers, we have $r(x) = ay(a + b)yb$. When we speak of a maximal 1-block in what follows, we mean one that cannot be extended by additional 1's to the left or right.

It now suffices to prove the following two lemmas:

**Lemma 16.** Let $z \in \mathbb{N}^*$, and suppose $|z| \ge 5$ is odd. Then $zz$ contains either

(a) two consecutive terms that are $\ge 2$, or

(b) six consecutive terms $a1bc1d$ with $a \ge c$ and $b \le d$.

**Proof:** If condition (a) is not satisfied, then $z$ consists of isolated occurrences of numbers $\ge 2$, separated by blocks of consecutive 1's. We assume this in what follows.

If $z$ both begins and ends with a number $\ge 2$, then $zz$ satisfies (a). Thus we may assume that $z$ either begins or ends with 1 (or both).

Suppose $z$ contains the block 1111. Then $zz$ contains the block $b1111c$ for $b, c \ge 1$, and hence satisfies (b). Thus we may assume that the maximal 1-blocks in $z$ are of length 1, 2, or 3.

Suppose all the maximal 1-blocks of $z$ are of length 1 or 3. If $z$ begins with 1 and ends with $b \ge 2$, then $z$ cannot be of odd length, and similarly if $z$ ends with 1 and begins with $b \ge 2$. So $z$ must begin and end with 1. Since $|z| \ge 5$, we know $z$ has a prefix of the form $1c1d$ and a suffix of the form $a1b1$, where $a, b, c, d \ge 1$. Hence $zz$ contains the block $a1b11c1d$. If $b \le c$, then the block $a1b11c$ fulfills condition (b); if $b \ge c$, then the block $b11c1d$ fulfills condition (b).

Thus there must be a maximal 1-block of length 2 in $z$. Then $zz$ contains two blocks, one of the form $a1b11c$ and one of the form $b11c1d$, where $a, d \ge 1$ and $b, c \ge 2$. If $b \le c$, then the block $a1b11c$ fulfills condition (b); if $b \ge c$, then the block $b11c1d$ fulfills condition (b). $\square$
and the remaining cases correspond to certain conjugates of $0^n 101^n 01$ for $n \ge 3$, already listed in the statement of the theorem.

Seven runs: then $x = 0^i 1^j 0^k 1^{i+l} 0^j 1^k 0^l$. Again, if $i, j \ge 2$, or $j, k \ge 2$, or $k, l \ge 2$, then $x$ contains a shorter antisquare 0011 or 1100. Since $i+l \ge 2$, the same argument rules out $k \ge 2$ and $j \ge 2$. So the only cases remaining are

$$ (i, j, k, l) \in \{(1, 1, 1, 1), (1, 1, 1, n), (n, 1, 1, 1), (n, 1, 1, n)\} $$

for $n \ge 2$. The first case (1, 1, 1, 1) corresponds to 010110101, which has the antisquare 0110, and it is easy to verify that the remaining cases are certain conjugates of $0^{n+1}101^{n+1}01$ for $n \ge 3$, already listed in the statement of the theorem.

It now remains to handle the case of more than 7 runs. By Lemma 14 $x$ has at least 10 runs. This involves a rather tedious examination of cases, based on the following three simple observations:

(a) if $r(x)$ contains two consecutive terms, both $\ge 2$, then $x$ contains the shorter antisquare 0011 or 1100;

(b) if $r(x)$ contains six consecutive terms $a1bc1d$ with $a \ge c$ and $b \le d$, then $x$ contains the shorter antisquare $0^c 10^b 1^c 01^b$ or its complement.

(c) if $r(x)$ contains an interior occurrence of 2, then $x$ contains the antisquare 0110 or 1001.

Suppose $x = u\bar{u}$. If $z = r(u)$ is of odd length, then $zz = r(x)$. If $z = r(u)$ is of even length, then writing $z = ayb$ with $a, b$ single numbers, we have $r(x) = ay(a + b)yb$. When we speak of a maximal 1-block in what follows, we mean one that cannot be extended by additional 1's to the left or right.

It now suffices to prove the following two lemmas:

**Lemma 16.** Let $z \in \mathbb{N}^*$, and suppose $|z| \ge 5$ is odd. Then $zz$ contains either

(a) two consecutive terms that are $\ge 2$, or

(b) six consecutive terms $a1bc1d$ with $a \ge c$ and $b \le d$.

**Proof:** If condition (a) is not satisfied, then $z$ consists of isolated occurrences of numbers $\ge 2$, separated by blocks of consecutive 1's. We assume this in what follows.

If $z$ both begins and ends with a number $\ge 2$, then $zz$ satisfies (a). Thus we may assume that $z$ either begins or ends with 1 (or both).

Suppose $z$ contains the block 1111. Then $zz$ contains the block $b1111c$ for $b, c \ge 1$, and hence satisfies (b). Thus we may assume that the maximal 1-blocks in $z$ are of length 1, 2, or 3.

Suppose all the maximal 1-blocks of $z$ are of length 1 or 3. If $z$ begins with 1 and ends with $b \ge 2$, then $z$ cannot be of odd length, and similarly if $z$ ends with 1 and begins with $b \ge 2$. So $z$ must begin and end with 1. Since $|z| \ge 5$, we know $z$ has a prefix of the form $1c1d$ and a suffix of the form $a1b1$, where $a, b, c, d \ge 1$. Hence $zz$ contains the block $a1b11c1d$. If $b \le c$, then the block $a1b11c$ fulfills condition (b); if $b \ge c$, then the block $b11c1d$ fulfills condition (b).

Thus there must be a maximal 1-block of length 2 in $z$. Then $zz$ contains two blocks, one of the form $a1b11c$ and one of the form $b11c1d$, where $a, d \ge 1$ and $b, c \ge 2$. If $b \le c$, then the block $a1b11c$ fulfills condition (b); if $b \ge c$, then the block $b11c1d$ fulfills condition (b). $\square$
**Lemma 17.** Let $z \in \mathbb{N}^*$, and suppose $|z| \ge 6$ is even, and write $z = ayb$. Define $z' = ay(a+b)yb$. Then $z'$ contains either

(a) two consecutive terms that are $\ge 2$, or

(b) six consecutive terms $a1bc1d$ with $a \ge c$ and $b \le d$, or

(c) an interior occurrence of 2.

**Proof:** If condition (a) is not satisfied, then $z$ consists of isolated occurrences of numbers $\ge 2$, separated by blocks of consecutive 1's. We assume this in what follows.

If $z$ begins and ends with 1, then $z'$ has an interior occurrence of 2, so (c) is satisfied. So assume this is not the case.

If $z$ begins $1b$ with $b \ge 2$, then by the previous paragraph it must end in $c \ge 2$. Then $z'$ has an occurrence of $(c+1)b$, so (a) is satisfied. Exactly the same argument works if $z$ ends with $b1$ with $b \ge 2$. So assume neither of these hold.

If $z$ has an interior occurrence of $1111$, then $z'$ has an occurrence of $c1111$, fulfilling condition (b). If $z$ begins $1111c$ for $c \ge 1$, it must end with $d \ge 2$, so $z'$ has an occurrence of $(d+1)111c$, fulfilling (b). The analogous argument holds if $z$ ends $c1111$. So all maximal 1-blocks in $z$ are of length $\le 4$.

Now we consider the case that $z$ has a maximal block of the form $111$. If this occurrence is interior in $z$, then $z'$ contains the block $b1111c$ for $b, c \ge 1$, and hence satisfies (b). If $z$ has the prefix $111$, then $z$ cannot end in 1 by above. Hence, since $z$ has even length, it must contain another maximal 1-block of even length, which must be interior. Since we have already ruled out the possibility of an interior occurrence of $111$, it must be an interior 1-block of size 2. But then $z'$ has a block of the form $a1b11c1d$ where $a, d \ge 1$ and $b, c \ge 2$. As in the previous lemma, if $b \le c$, then the block $a1b11c$ fulfills condition (b); if $b \ge c$, then the block $b11c1d$ fulfills condition (b). The analogous argument holds if the occurrence of $111$ is a suffix. Hence $z$ contains no maximal 1-block of size 4.

Thus we may assume that the maximal 1-blocks in $z$ are of length 1, 2, or 3.

If $z$ has a maximal 1-block of size 2, then since $|z|$ is even, it must have a second maximal 1-block of size 2. Then $z'$ has a factor of the form $a1b11c1d$ where $a, d \ge 1$ and $b, c \ge 2$, and by the argument above, this satisfies condition (b).

Hence all the maximal 1-blocks of $z$ are of size 1 or 3. Hence all the maximal 1-blocks of $z$ are size 1 or 3. Since $z$ has even length, exactly one of its first and last symbols must be 1. We know from above that $z$ cannot begin $1b$ or end $b1$ with $b \ge 2$. So $z$ must either begin $111$ or end $111$. If $z$ begins $111$, then $z$ ends in $b \ge 2$, and $z'$ contains the block $a1(b+1)11c1d$ for some $a, d \ge 1$ and $b, c \ge 2$. If $c \le b+1$, then the block $a1(b+1)11c$ fulfills condition (b); if $b+1 \ge c$, then the block $(b+1)11c1d$ fulfills (b). If $z$ ends $111$, then an analogous argument holds. $\square$

Applying the two lemmas to the case where $x = u\bar{u}$ and $z = r(u)$ completes the proof of Theorem 11. $\square$

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

# 7 Enumerating words with only two distinct antisquares

In this section we obtain some enumeration results for good words. Here the notation $^\omega x$ refers to the left-infinite word $\cdots xxx$.
**Lemma 17.** Let $z \in \mathbb{N}^*$, and suppose $|z| \ge 6$ is even, and write $z = ayb$. Define $z' = ay(a+b)yb$. Then $z'$ contains either

(a) two consecutive terms that are $\ge 2$, or

(b) six consecutive terms $a1bc1d$ with $a \ge c$ and $b \le d$, or

(c) an interior occurrence of 2.

**Proof:** If condition (a) is not satisfied, then $z$ consists of isolated occurrences of numbers $\ge 2$, separated by blocks of consecutive 1's. We assume this in what follows.

If $z$ begins and ends with 1, then $z'$ has an interior occurrence of 2, so (c) is satisfied. So assume this is not the case.

If $z$ begins $1b$ with $b \ge 2$, then by the previous paragraph it must end in $c \ge 2$. Then $z'$ has an occurrence of $(c+1)b$, so (a) is satisfied. Exactly the same argument works if $z$ ends with $b1$ with $b \ge 2$. So assume neither of these hold.

If $z$ has an interior occurrence of $1111$, then $z'$ has an occurrence of $c1111$, fulfilling condition (b). If $z$ begins $1111c$ for $c \ge 1$, it must end with $d \ge 2$, so $z'$ has an occurrence of $(d+1)111c$, fulfilling (b). The analogous argument holds if $z$ ends $c1111$. So all maximal 1-blocks in $z$ are of length $\le 4$.

Now we consider the case that $z$ has a maximal block of the form $111$. If this occurrence is interior in $z$, then $z'$ contains the block $b1111c$ for $b, c \ge 1$, and hence satisfies (b). If $z$ has the prefix $111$, then $z$ cannot end in 1 by above. Hence, since $z$ has even length, it must contain another maximal 1-block of even length, which must be interior. Since we have already ruled out the possibility of an interior occurrence of $111$, it must be an interior 1-block of size 2. But then $z'$ has a block of the form $a1b11c1d$ where $a, d \ge 1$ and $b, c \ge 2$. As in the previous lemma, if $b \le c$, then the block $a1b11c$ fulfills condition (b); if $b \ge c$, then the block $b11c1d$ fulfills condition (b). The analogous argument holds if the occurrence of $111$ is a suffix. Hence $z$ contains no maximal 1-block of size 4.

Thus we may assume that the maximal 1-blocks in $z$ are of length 1, 2, or 3.

If $z$ has a maximal 1-block of size 2, then since $|z|$ is even, it must have a second maximal 1-block of size 2. Then $z'$ has a factor of the form $a1b11c1d$ where $a, d \ge 1$ and $b, c \ge 2$, and by the argument above, this satisfies condition (b).

Hence all the maximal 1-blocks of $z$ are of size 1 or 3. Hence all the maximal 1-blocks of $z$ are size 1 or 3. Since $z$ has even length, exactly one of its first and last symbols must be 1. We know from above that $z$ cannot begin $1b$ or end $b1$ with $b \ge 2$. So $z$ must either begin $111$ or end $111$. If $z$ begins $111$, then $z$ ends in $b \ge 2$, and $z'$ contains the block $a1(b+1)11c1d$ for some $a, d \ge 1$ and $b, c \ge 2$. If $c \le b+1$, then the block $a1(b+1)11c$ fulfills condition (b); if $b+1 \ge c$, then the block $(b+1)11c1d$ fulfills (b). If $z$ ends $111$, then an analogous argument holds. $\square$

Applying the two lemmas to the case where $x = u\bar{u}$ and $z = r(u)$ completes the proof of Theorem 11. $\square$

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

# 7 Enumerating words with only two distinct antisquares

In this section we obtain some enumeration results for good words. Here the notation $^\omega x$ refers to the left-infinite word $\cdots xxx$.
**Proposition 18.** If a bi-infinite good word $w$ contains the factor $001011$, then $w = \omega^0101\omega^0$.

**Proof:** Consider a maximal factor of $w$ of the form $0^k101^k$, with $2 \le k < \infty$. By maximality and by symmetry, we can assume that $w$ contains $0^k101^k0$. This factor is not extendable to the right:

* $0^k101^k00$ contains the antisquare 1100 as a suffix.

* $0^k101^k01$ is an antisquare.

This is a contradiction to $k < \infty$, so $w = \omega^0101\omega^0$.

□

**Theorem 19.** There are $\Theta(\psi^n)$ good words of length $n$, where $\psi \doteq 1.465571231876768$ is the super-golden ratio, root of the equation $X^3 = X^2 + 1$.

**Proof:** Let $F = \{0011, 1100, 0110, 1001, 010101, 101010, 001011, 110100\}$. By Theorem 11, $F$ contains the minimal antisquares of order 2 and 3, and the minimal antisquares of order at least 4 contain $001011$ or $110100$. Thus, the binary words avoiding $F$ are exactly the good words that avoid $\{001011, 110100\}$.

By Proposition 18, there are not enough good words containing $001011$ to contribute to the growth rate of good words. This also holds for good words containing the symmetric factor $110100$. Thus, good words and binary words avoiding $F$ have the same growth rate.

To enumerate binary words avoiding $F$, we instead enumerate the ‘Pansiot codes’ of these words. If $x = x_1x_2\cdots x_n$ is a binary word, then the Pansiot code of $x$ is the binary word $p_1p_2\cdots p_{n-1}$ such that for $i = 1, \dots, n-1$

$$x_{i+1} = \begin{cases} x_i & \text{if } p_i = 0; \\ \bar{x}_i & \text{if } p_i = 1. \end{cases}$$

For example, the binary word $010$ is the Pansiot code for the two binary words $0011$ and $1100$.

The Pansiot codes of binary words avoiding $F$ are the binary words avoiding $\{010, 101, 11111, 01110\}$. These words consist of blocks of 0's of length at least 2 and blocks of 1's of length 2 or 4. Consider the number $C_n$ of such words ending with 00. They are obtained from shorter words by adding a suffix 0, 1100, or $111100$. From the relation $C_n = C_{n-1} + C_{n-4} + C_{n-6}$, the growth rate is the positive real root of $X^6 = X^5 + X^2 + 1$. Since $X^6 - X^5 - X^2 - 1 = (X+1)(X^2 - X + 1)(X^3 - X^2 - 1)$, this is the root $\psi$ of $X^3 = X^2 + 1$. □

Next we show that the threshold exponent at which the number of good words becomes exponential is $\frac{15}{4}$. (For overlap-free words, the threshold is $\frac{7}{3}$; see Karhumäki and Shallit (2004).)

**Theorem 20.** Let $w$ be any squarefree word over the alphabet $\{0, 1, 2\}$. Apply the map $h$ that sends

$$\begin{aligned} 0 &\rightarrow 010001 \\ 1 &\rightarrow 0100010001 \\ 2 &\rightarrow 01000100010001. \end{aligned}$$

The resulting word is good, and has exponent at most $\frac{15}{4}$, and it is exactly $\frac{15}{4}$ if $|w| \ge 5$.
**Proposition 18.** If a bi-infinite good word $w$ contains the factor $001011$, then $w = \omega^0101\omega$.

**Proof:** Consider a maximal factor of $w$ of the form $0^k101^k$, with $2 \le k < \infty$. By maximality and by symmetry, we can assume that $w$ contains $0^k101^k0$. This factor is not extendable to the right:

* $0^k101^k00$ contains the antisquare 1100 as a suffix.

* $0^k101^k01$ is an antisquare.

This is a contradiction to $k < \infty$, so $w = \omega^0101\omega$.

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

**Theorem 19.** There are $\Theta(\psi^n)$ good words of length $n$, where $\psi \doteq 1.465571231876768$ is the super-golden ratio, root of the equation $X^3 = X^2 + 1$.

**Proof:** Let $F = \{0011, 1100, 0110, 1001, 010101, 101010, 001011, 110100\}$. By Theorem 11, $F$ contains the minimal antisquares of order 2 and 3, and the minimal antisquares of order at least 4 contain $001011$ or $110100$. Thus, the binary words avoiding $F$ are exactly the good words that avoid $\{001011, 110100\}$.

By Proposition 18, there are not enough good words containing $001011$ to contribute to the growth rate of good words. This also holds for good words containing the symmetric factor $110100$. Thus, good words and binary words avoiding $F$ have the same growth rate.

To enumerate binary words avoiding $F$, we instead enumerate the ‘Pansiot codes’ of these words. If $x = x_1x_2\cdots x_n$ is a binary word, then the Pansiot code of $x$ is the binary word $p_1p_2\cdots p_{n-1}$ such that for $i = 1, \dots, n-1$

$$x_{i+1} = \begin{cases} x_i & \text{if } p_i = 0; \\ \bar{x}_i & \text{if } p_i = 1. \end{cases}$$

For example, the binary word 010 is the Pansiot code for the two binary words 0011 and 1100.

The Pansiot codes of binary words avoiding $F$ are the binary words avoiding $\{010, 101, 11111, 01110\}$. These words consist of blocks of 0's of length at least 2 and blocks of 1's of length 2 or 4. Consider the number $C_n$ of such words ending with 00. They are obtained from shorter words by adding a suffix 0, 1100, or $111100$. From the relation $C_n = C_{n-1} + C_{n-4} + C_{n-6}$, the growth rate is the positive real root of $X^6 = X^5 + X^2 + 1$. Since $X^6 - X^5 - X^2 - 1 = (X+1)(X^2 - X + 1)(X^3 - X^2 - 1)$, this is the root $\psi$ of $X^3 = X^2 + 1$. $\square$

Next we show that the threshold exponent at which the number of good words becomes exponential is $\frac{15}{4}$. (For overlap-free words, the threshold is $\frac{7}{3}$; see Karhumäki and Shallit (2004).)

**Theorem 20.** Let $w$ be any squarefree word over the alphabet $\{0, 1, 2\}$. Apply the map $h$ that sends

$$\begin{align*} 0 &\rightarrow 010001 \\ 1 &\rightarrow 0100010001 \\ 2 &\rightarrow 01000100010001. \end{align*}$$

The resulting word is good, and has exponent at most $\frac{15}{4}$, and it is exactly $\frac{15}{4}$ if $|w| \ge 5$.
**Proof:** The goodness of $h(w)$ can be seen by inspection. Regarding the exponent $\frac{15}{4}$, suppose that $h(w)$ contains a $\frac{15}{4}$ power $zzzz'$, where $z'$ is a prefix of $z$. Note that in $h(w)$ the factor 101 can only occur at the 'boundary' between $h(a)$ and $h(b)$, where $a, b \in \{0, 1, 2\}$. So we have two cases:

Case 1: $z$ contains 101. Write $z = x101y$. Then $h(w)$ contains the square $01yx101yx1$, where $01yx1 = h(Z)$ for some factor $Z$ of $w$. Then $w$ contains the square $ZZ$, which is a contradiction.

Case 2: $z$ does not contain 101. Clearly $z = h(a)$ or $z = h(a)0$ for some $a \in \{0, 1, 2\}$ is not possible, so $z$ is contained within some $h(a)$, where $a \in \{0, 1, 2\}$. The only such $\frac{15}{4}$-power is $h(2)0 = (0100)^3010$, which establishes the claim. $\square$

**Corollary 21.** *There are exponentially many length-$n \frac{15}{4}$-free good words.*

To show that there are only polynomially many length-$n$ good words avoiding $\frac{15}{4}$-powers we need a version of the results in Section 3 for finite words rather than bi-infinite words. Let $g$ and $\varphi$ be defined as in Section 2 and let $g'$ be the morphism that maps $0 \mapsto 01$ and $1 \mapsto 00$.

**Lemma 22.** *Let $w$ be a 4-free word of length $\ge 15$ that contains no antisquares other than 01 and 10. Then $w$ can be written as either $w = w_1g(v)w_2$ or $w = w_1g'(v)w_2$ for some $v$, where $|w_1|, |w_2| \le 5$.*

**Proof:** By a finite search, one verifies that any $w$ satisfying the hypotheses of the lemma has a prefix of length $\le 9$ that contains either 0001 or 0111. Suppose it contains 0111. Since $w$ avoids the antisquares 0110 and 1001 and the 4-powers 0000 and 1111 we can write $w = w_10111z$, where $z$ is a prefix of a word in $\{0001, 01, 0111\}^*$ and $|w_1| \le 5$. We claim that $z$ does not contain 0001. Note that $|z| \ge 6$.

If $z$ has 0001 as a prefix, then $w$ contains the antisquare 111000. Suppose $z$ has 01 as a prefix. If $z$ has 010001 as a prefix, then $w$ contains the antisquare 0111010001. If $z$ has 01010 as a prefix, then $w$ contains the antisquare 101010, so necessarily $z$ has 010111 as a prefix. Finally, it may be the case that $z$ has 0111 as a prefix. Applying this argument repeatedly to the suffix of $w$ following this new occurrence of 0111, until we no longer have such a suffix of length at least 6, we see that $z$ does not contain 0001. It follows that $w$ can be written as $w = w_1xw_2$, where $x \in \{01, 0111\}^*$ (and hence $x \in \{01, 11\}^*$), and $|w_2| \le 5$. Thus $w = w_1g(v)w_2$ for some $v$, as required.

A similar argument shows that if $w$ contains 0001 then $w = w_1g'(v)w_2$ for some $v$, where $|w_1| \le 5$ and $|w_2| \le 5$. $\square$

In what follows we will consider words of the form $g(v)$; the analysis for $g'(v)$ is similar.

**Lemma 23.** *Let $n \ge 1$ and $y = g(\varphi^n(x))$ for some binary word $x$ with $|x| \ge 5$. If $y$ is $\frac{15}{4}$-free, then $x$ is 4-free and can be written in the form $x = px'$s where $|p| \le 2$, $|s| \le 1$ and $x'$ has no 000 or 11.*

**Proof:** Clearly $x$ is 4-free. Suppose $x$ contains an occurrence of 000 that is neither a prefix nor a suffix of $x$. Then $\varphi(x)$ contains the 4-power $(0100)^30 = (010)^4$ and hence $y$ contains a 4-power, which is a contradiction. Suppose $x$ contains an occurrence of 11 of the form $x = u11v$, where $|u| \ge 2$ and $|v| \ge 1$. Then $\varphi(x)$ contains 0101 and hence, extending this occurrence of 0101 to the left and right with blocks 001 and 01 and avoiding 4-powers, we see that $\varphi(x)$ contains 00101010. Indeed, extending two blocks to the left and one block to the right suffices. If $n = 1$ then $g(00101010)$ contains the $\frac{15}{4}$-power $(1011)^3101$, which is a contradiction. If $n > 1$, then $\varphi(00101010)$ contains the 4-power $(01001)^4$ and hence $y$ contains a 4-power, which is a contradiction. $\square$
**Proof:** The goodness of $h(w)$ can be seen by inspection. Regarding the exponent $\frac{15}{4}$, suppose that $h(w)$ contains a $\frac{15}{4}$ power $zzzz'$, where $z'$ is a prefix of $z$. Note that in $h(w)$ the factor 101 can only occur at the 'boundary' between $h(a)$ and $h(b)$, where $a, b \in \{0, 1, 2\}$. So we have two cases:

Case 1: $z$ contains 101. Write $z = x101y$. Then $h(w)$ contains the square $01yx101yx1$, where $01yx1 = h(Z)$ for some factor $Z$ of $w$. Then $w$ contains the square $ZZ$, which is a contradiction.

Case 2: $z$ does not contain 101. Clearly $z = h(a)$ or $z = h(a)0$ for some $a \in \{0, 1, 2\}$ is not possible, so $z$ is contained within some $h(a)$, where $a \in \{0, 1, 2\}$. The only such $\frac{15}{4}$-power is $h(2)0 = (0100)^3010$, which establishes the claim. $\square$

**Corollary 21.** *There are exponentially many length-$n \frac{15}{4}$-free good words.*

To show that there are only polynomially many length-$n$ good words avoiding $\frac{15}{4}$-powers we need a version of the results in Section 3 for finite words rather than bi-infinite words. Let $g$ and $\varphi$ be defined as in Section 2 and let $g'$ be the morphism that maps $0 \mapsto 01$ and $1 \mapsto 00$.

**Lemma 22.** *Let $w$ be a 4-free word of length $\ge 15$ that contains no antisquares other than 01 and 10. Then $w$ can be written as either $w = w_1g(v)w_2$ or $w = w_1g'(v)w_2$ for some $v$, where $|w_1|, |w_2| \le 5$.*

**Proof:** By a finite search, one verifies that any $w$ satisfying the hypotheses of the lemma has a prefix of length $\le 9$ that contains either 0001 or 0111. Suppose it contains 0111. Since $w$ avoids the antisquares 0110 and 1001 and the 4-powers 0000 and 1111 we can write $w = w_10111z$, where $z$ is a prefix of a word in $\{0001, 01, 0111\}^*$ and $|w_1| \le 5$. We claim that $z$ does not contain 0001. Note that $|z| \ge 6$.

If $z$ has 0001 as a prefix, then $w$ contains the antisquare 111000. Suppose $z$ has 01 as a prefix. If $z$ has 010001 as a prefix, then $w$ contains the antisquare 0111010001. If $z$ has 01010 as a prefix, then $w$ contains the antisquare 101010, so necessarily $z$ has 010111 as a prefix. Finally, it may be the case that $z$ has 0111 as a prefix. Applying this argument repeatedly to the suffix of $w$ following this new occurrence of 0111, until we no longer have such a suffix of length at least 6, we see that $z$ does not contain 0001. It follows that $w$ can be written as $w = w_1xw_2$, where $x \in \{01, 0111\}^*$ (and hence $x \in \{01, 11\}^*$), and $|w_2| \le 5$. Thus $w = w_1g(v)w_2$ for some $v$, as required.

A similar argument shows that if $w$ contains 0001 then $w = w_1g'(v)w_2$ for some $v$, where $|w_1| \le 5$ and $|w_2| \le 5$. $\square$

In what follows we will consider words of the form $g(v)$; the analysis for $g'(v)$ is similar.

**Lemma 23.** *Let $n \ge 1$ and $y = g(\varphi^n(x))$ for some binary word $x$ with $|x| \ge 5$. If $y$ is $\frac{15}{4}$-free, then $x$ is 4-free and can be written in the form $x = px'$s where $|p| \le 2$, $|s| \le 1$ and $x'$ has no 000 or 11.*

**Proof:** Clearly $x$ is 4-free. Suppose $x$ contains an occurrence of 000 that is neither a prefix nor a suffix of $x$. Then $\varphi(x)$ contains the 4-power $(0100)^30 = (010)^4$ and hence $y$ contains a 4-power, which is a contradiction. Suppose $x$ contains an occurrence of 11 of the form $x = u11v$, where $|u| \ge 2$ and $|v| \ge 1$. Then $\varphi(x)$ contains 0101 and hence, extending this occurrence of 0101 to the left and right with blocks 001 and 01 and avoiding 4-powers, we see that $\varphi(x)$ contains 00101010. Indeed, extending two blocks to the left and one block to the right suffices. If $n = 1$ then $g(00101010)$ contains the $\frac{15}{4}$-power $(1011)^3101$, which is a contradiction. If $n > 1$, then $\varphi(00101010)$ contains the 4-power $(01001)^4$ and hence $y$ contains a 4-power, which is a contradiction. $\square$
**Lemma 24.** Let $w$ be a $\frac{15}{4}$-free word of length $\ge 33$ that contains no antisquares other than 01 and 10. Then $w$ can be written in the form

$$w = w_1 G(u_1 \varphi(u_2 \cdots \varphi(u_r \varphi(V)v_r) \cdots v_2)v_1)w_2$$

for some $r$, where $G \in \{g, g'\}$, $|w_1|, |w_2| \le 5$, $|u_i| \le 4$, $|v_i| \le 3$, for $i = 1, \dots, r$, and $|V| \le 4$.

**Proof:** By Lemma 22, we can write $w = w_1 G(v)w_2$, where $|w_1|, |w_2| \le 5$. Without loss of generality, suppose $G = g$. Clearly $v$ must be 4-free. Furthermore, $v$ does not contain 000 or 11, since otherwise $g(v)$ would contain either the antisquare 010101 or the 4-power 1111. Thus $v = u_1 \varphi(v')v_1$, where $|u_1|, |v_1| \le 2$ and $|v'| \ge 5$. We can then apply Lemma 23 to $g(\varphi(v'))$ to find that $v'$ is 4-free and can be written in the form $v' = px's$, where $|p| \le 2$, $|s| \le 1$ and $x'$ has no 000 or 11. Then we can write $v' = u_2 \varphi(v'')v_2$, where $|u_2| \le 4$ and $|v_2| \le 3$, and repeat the process to obtain the desired decomposition. $\square$

**Theorem 25.** There are polynomially many length-$n$ good words avoiding $\frac{15}{4}$-powers.

**Proof:** Let $w$ be such a word of length $n$, where $n \ge 33$. By Lemma 24 $w$ can be written in the form

$$w = w_1 G(u_1 \varphi(u_2 \cdots \varphi(u_r \varphi(V)v_r) \cdots v_2)v_1)w_2$$

for some $r$, where $G \in \{g, g'\}$, $|w_1|, |w_2| \le 5$, $|u_i| \le 4$, $|v_i| \le 3$, for $i = 1, \dots, r$, and $|V| \le 4$. Suppose $G = g$ and under this assumption let $A$ (resp. $B, C, D, E$) be the maximum number of possible choices for $w_1$ (resp. $w_2, u_i, v_i, V$). Then the number of words $w$ is at most $AB(CD)^r E$. There is a constant $\rho$ such that $r \le \rho \log n$, so the number of words $w$ is at most $ABE n^{\rho \log(CD)}$. A similar calculation applies when $G = g'$. $\square$

# 8 Further work

In this paper we have studied antisquares. This situation has an obvious generalization to patterns with morphic and antimorphic permutations, as studied in Currie et al. (2015). This could be the subject of a future study.

A companion paper to this one is Currie et al. (2023), which investigates complement avoidance in binary words.

# References

G. Badkobeh and M. Crochemore. Finite-repetition threshold for infinite ternary words. In P. Ambrož, Š. Holub, and Z. Masáková, editors, *WORDS 2011*, volume 63 of *Elec. Proc. Theor. Comput. Sci.*, pages 37–43. Open Publishing Association, 2011.

A. Carpi and A. d. Luca. Special factors, periodicity, and an application to Sturmian words. *Acta Informatica*, 36:983–1006, 2000.

J. Currie and N. Rampersad. A proof of Dejean's conjecture. *Math. Comp.*, 80:1063–1070, 2011.
**Lemma 24.** Let $w$ be a $\frac{15}{4}$-free word of length $\ge 33$ that contains no antisquares other than 01 and 10. Then $w$ can be written in the form

$$w = w_1 G(u_1 \varphi(u_2 \cdots \varphi(u_r \varphi(V)v_r) \cdots v_2)v_1)w_2$$

for some $r$, where $G \in \{g, g'\}$, $|w_1|, |w_2| \le 5$, $|u_i| \le 4$, $|v_i| \le 3$, for $i = 1, \dots, r$, and $|V| \le 4$.

**Proof:** By Lemma 22, we can write $w = w_1 G(v)w_2$, where $|w_1|, |w_2| \le 5$. Without loss of generality, suppose $G = g$. Clearly $v$ must be 4-free. Furthermore, $v$ does not contain 000 or 11, since otherwise $g(v)$ would contain either the antisquare 010101 or the 4-power 1111. Thus $v = u_1 \varphi(v')v_1$, where $|u_1|, |v_1| \le 2$ and $|v'| \ge 5$. We can then apply Lemma 23 to $g(\varphi(v'))$ to find that $v'$ is 4-free and can be written in the form $v' = px's$, where $|p| \le 2$, $|s| \le 1$ and $x'$ has no 000 or 11. Then we can write $v' = u_2 \varphi(v'')v_2$, where $|u_2| \le 4$ and $|v_2| \le 3$, and repeat the process to obtain the desired decomposition. $\square$

**Theorem 25.** There are polynomially many length-$n$ good words avoiding $\frac{15}{4}$-powers.

**Proof:** Let $w$ be such a word of length $n$, where $n \ge 33$. By Lemma 24 $w$ can be written in the form

$$w = w_1 G(u_1 \varphi(u_2 \cdots \varphi(u_r \varphi(V)v_r) \cdots v_2)v_1)w_2$$

for some $r$, where $G \in \{g, g'\}$, $|w_1|, |w_2| \le 5$, $|u_i| \le 4$, $|v_i| \le 3$, for $i = 1, \dots, r$, and $|V| \le 4$. Suppose $G = g$ and under this assumption let $A$ (resp. $B, C, D, E$) be the maximum number of possible choices for $w_1$ (resp. $w_2, u_i, v_i, V$). Then the number of words $w$ is at most $AB(CD)^r E$. There is a constant $\rho$ such that $r \le \rho \log n$, so the number of words $w$ is at most $ABE n^{\rho \log(CD)}$. A similar calculation applies when $G = g'$. $\square$

# 8 Further work

In this paper we have studied antisquares. This situation has an obvious generalization to patterns with morphic and antimorphic permutations, as studied in Currie et al. (2015). This could be the subject of a future study.

A companion paper to this one is Currie et al. (2023), which investigates complement avoidance in binary words.

# References

G. Badkobeh and M. Crochemore. Finite-repetition threshold for infinite ternary words. In P. Ambrož, Š. Holub, and Z. Masáková, editors, *WORDS 2011*, volume 63 of *Elec. Proc. Theor. Comput. Sci.*, pages 37–43. Open Publishing Association, 2011.

A. Carpi and A. d. Luca. Special factors, periodicity, and an application to Sturmian words. *Acta Informatica*, 36:983–1006, 2000.

J. Currie and N. Rampersad. A proof of Dejean's conjecture. *Math. Comp.*, 80:1063–1070, 2011.
J. Currie, F. Manea, and D. Nowotka. Unary patterns with permutations. In I. Potapov, editor, *DLT 2015*, volume 9168 of *Lecture Notes in Computer Science*, pages 191–202. Springer-Verlag, 2015.

J. Currie, L. Dvořaková, D. Opočenská, N. Rampersad, and J. Shallit. Complement avoidance in binary words. Arxiv preprint arXiv:2209.09598 [math.CO]. Available at https://arxiv.org/abs/2209.09598, 2023.

J. D. Currie, L. Mol, and N. Rampersad. The repetition threshold for binary rich words. *Discrete Math. & Theoret. Comput. Sci.*, 22(1):DMTCS-22-1-6, 2020. URL https://dmtcs.episciences.org/6082.

F. Dejean. Sur un théorème de Thue. *J. Combin. Theory. Ser. A*, 13:90–99, 1972.

L. Dvořáková, K. Medková, and E. Pelantová. Complementary symmetric Rote sequences: the critical exponent and the recurrence function. *Discrete Math. & Theoret. Comput. Sci.*, 22(1):DMTCS-22-1-20, 2020. URL https://dmtcs.episciences.org/6519/.

L. Dvořáková, D. Opočenská, E. Pelantová, and A. M. Shur. On minimal critical exponent of balanced sequences. Preprint, available at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4011686, 2022.

F. Fiorenzi, P. Ochem, and E. Vaslet. Bounds for the generalized repetition threshold. *Theoret. Comput. Sci.*, 412:2955–2963, 2011.

P. Hieronymi, D. Ma, R. Oei, L. Schaeffer, C. Schulz, and J. Shallit. Decidability for Sturmian words. In F. Manea and A. Simpson, editors, *30th EACSL Annual Conference on Computer Science Logic (CSL 2022)*, Leibniz International Proceedings in Informatics, pages 24:1–24:23. Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 2022.

L. Ilie, P. Ochem, and J. Shallit. A generalization of repetition threshold. *Theoret. Comput. Sci.*, 345:359–369, 2005.

J. Karhumäki and J. Shallit. Polynomial versus exponential growth in repetition-free binary words. *J. Combin. Theory. Ser. A*, 105(2):335–347, 2004.

F. Mignosi, A. Restivo, and M. Sciortino. Words and forbidden factors. *Theoret. Comput. Sci.*, 273:99–117, 2002.

L. Mol, N. Rampersad, and J. Shallit. Extremal overlap-free and extremal *β*-free binary words. *Electronic J. Combinatorics*, 27(4):#P4.42, 2020.

H. Mousavi. Automatic theorem proving in *Walnut*. Arxiv preprint arXiv:1603.06017 [cs.FL], available at http://arxiv.org/abs/1603.06017, 2016.

H. Mousavi and J. Shallit. Repetition avoidance in circular factors. In M.-P. Béal and O. Carton, editors, *DLT 2013*, volume 7907 of *Lecture Notes in Computer Science*, pages 384–395. Springer-Verlag, 2013.

H. Mousavi, L. Schaeffer, and J. Shallit. Decision algorithms for Fibonacci-automatic words, I: Basic results. *RAIRO Inform. Théor. App.*, 50:39–66, 2016.
J. Currie, F. Manea, and D. Nowotka. Unary patterns with permutations. In I. Potapov, editor, *DLT 2015*, volume 9168 of *Lecture Notes in Computer Science*, pages 191–202. Springer-Verlag, 2015.

J. Currie, L. Dvořaková, D. Opočenská, N. Rampersad, and J. Shallit. Complement avoidance in binary words. Arxiv preprint arXiv:2209.09598 [math.CO]. Available at https://arxiv.org/abs/2209.09598, 2023.

J. D. Currie, L. Mol, and N. Rampersad. The repetition threshold for binary rich words. *Discrete Math. & Theoret. Comput. Sci.*, 22(1):DMTCS-22-1-6, 2020. URL https://dmtcs.episciences.org/6082.

F. Dejean. Sur un théorème de Thue. *J. Combin. Theory. Ser. A*, 13:90–99, 1972.

L. Dvořáková, K. Medková, and E. Pelantová. Complementary symmetric Rote sequences: the critical exponent and the recurrence function. *Discrete Math. & Theoret. Comput. Sci.*, 22(1):DMTCS-22-1-20, 2020. URL https://dmtcs.episciences.org/6519/.

L. Dvořáková, D. Opočenská, E. Pelantová, and A. M. Shur. On minimal critical exponent of balanced sequences. Preprint, available at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4011686, 2022.

F. Fiorenzi, P. Ochem, and E. Vaslet. Bounds for the generalized repetition threshold. *Theoret. Comput. Sci.*, 412:2955–2963, 2011.

P. Hieronymi, D. Ma, R. Oei, L. Schaeffer, C. Schulz, and J. Shallit. Decidability for Sturmian words. In F. Manea and A. Simpson, editors, *30th EACSL Annual Conference on Computer Science Logic (CSL 2022)*, Leibniz International Proceedings in Informatics, pages 24:1–24:23. Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 2022.

L. Ilie, P. Ochem, and J. Shallit. A generalization of repetition threshold. *Theoret. Comput. Sci.*, 345:359–369, 2005.

J. Karhumäki and J. Shallit. Polynomial versus exponential growth in repetition-free binary words. *J. Combin. Theory. Ser. A*, 105(2):335–347, 2004.

F. Mignosi, A. Restivo, and M. Sciortino. Words and forbidden factors. *Theoret. Comput. Sci.*, 273:99–117, 2002.

L. Mol, N. Rampersad, and J. Shallit. Extremal overlap-free and extremal *β*-free binary words. *Electronic J. Combinatorics*, 27(4):#P4.42, 2020.

H. Mousavi. Automatic theorem proving in *Walnut*. Arxiv preprint arXiv:1603.06017 [cs.FL], available at http://arxiv.org/abs/1603.06017, 2016.

H. Mousavi and J. Shallit. Repetition avoidance in circular factors. In M.-P. Béal and O. Carton, editors, *DLT 2013*, volume 7907 of *Lecture Notes in Computer Science*, pages 384–395. Springer-Verlag, 2013.

H. Mousavi, L. Schaeffer, and J. Shallit. Decision algorithms for Fibonacci-automatic words, I: Basic results. *RAIRO Inform. Théor. App.*, 50:39–66, 2016.
T. Ng, P. Ochem, N. Rampersad, and J. Shallit. New results on pseudosquare avoidance. In R. Mercas and D. Reidenbach, editors, *WORDS 2019*, volume 11682 of *Lecture Notes in Computer Science*, pages 264–274. Springer-Verlag, 2019.

N. Rampersad, J. Shallit, and É. Vandomme. Critical exponents of infinite balanced words. *Theoret. Comput. Sci.*, 777:454–463, 2019.

M. Rao. Last cases of Dejean's conjecture. *Theoret. Comput. Sci.*, 412:3010–3018, 2011.

A. V. Samsonov and A. M. Shur. On Abelian repetition threshold. *RAIRO Inform. Théor. App.*, 46: 147–163, 2012.

J. Shallit. Simultaneous avoidance of large squares and fractional powers in infinite binary words. *Internat. J. Found. Comp. Sci.*, 15:317–327, 2004.

J. Shallit. Minimal critical exponents for palindromes. ArXiv preprint, arXiv:1612.05320 [cs.FL]. Available at https://arxiv.org/abs/1612.05320, 2016.

J. Shallit. *The Logical Approach To Automatic Sequences: Exploring Combinatorics on Words with Walnut*, volume 482 of *London Math. Soc. Lecture Note Series*. Cambridge University Press, 2022.
T. Ng, P. Ochem, N. Rampersad, and J. Shallit. New results on pseudosquare avoidance. In R. Mercas and D. Reidenbach, editors, *WORDS 2019*, volume 11682 of *Lecture Notes in Computer Science*, pages 264–274. Springer-Verlag, 2019.

N. Rampersad, J. Shallit, and É. Vandomme. Critical exponents of infinite balanced words. *Theoret. Comput. Sci.*, 777:454–463, 2019.

M. Rao. Last cases of Dejean's conjecture. *Theoret. Comput. Sci.*, 412:3010–3018, 2011.

A. V. Samsonov and A. M. Shur. On Abelian repetition threshold. *RAIRO Inform. Théor. App.*, 46: 147–163, 2012.

J. Shallit. Simultaneous avoidance of large squares and fractional powers in infinite binary words. *Internat. J. Found. Comp. Sci.*, 15:317–327, 2004.

J. Shallit. Minimal critical exponents for palindromes. ArXiv preprint, arXiv:1612.05320 [cs.FL]. Available at https://arxiv.org/abs/1612.05320, 2016.

J. Shallit. *The Logical Approach To Automatic Sequences: Exploring Combinatorics on Words with Walnut*, volume 482 of *London Math. Soc. Lecture Note Series*. Cambridge University Press, 2022.