# 4-tangrams are 4-avoidable

Pascal Ochem, Théo Pierron

► To cite this version:

Pascal Ochem, Théo Pierron. 4-tangrams are 4-avoidable. Discrete Mathematics and Theoretical Computer Science, 2025, 27:3 (Combinatorics), 10.46298/dmtcs.15310. lirmm-05154498

HAL Id: lirmm-05154498

https://hal-lirmm.ccsd.cnrs.fr/lirmm-05154498v1

Submitted on 9 Jul 2025

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
# 4-tangrams are 4-avoidable

Pascal Ochem<fnref n="1" />

Théo Pierron<fnref n="2" />

revisions 3rd Mar. 2025, 16th June 2025; accepted 26th June 2025.

A tangram is a word in which every letter occurs an even number of times. Thus it can be cut into parts that can be arranged into two identical words. The cut number of a tangram is the minimum number of required cuts in this process. Tangrams with cut number one correspond to squares. For $k \ge 1$, let $t(k)$ denote the minimum size of an alphabet over which an infinite word avoids tangrams with cut number at most $k$. The existence of infinite ternary square-free words shows that $t(1) = t(2) = 3$. We show that $t(3) = t(4) = 4$, answering a question from Dębski, Grytczuk, Pawlik, Przybyło, and Śleszyńska-Nowak.

**Keywords:** combinatorics on words

## 1 Introduction

A tangram is a word in which every letter occurs an even number of times, possibly zero. In particular, tangrams are a generalization of squares. In this article, we consider a classification of tangrams depending on how close they are from being a square. This relies on the so-called cut number of a tangram, recently introduced by Dębski, Grytczuk, Pawlik, Przybyło, and Śleszyńska-Nowak [3]. The cut number of a tangram is defined as the minimum number of cuts needed so that the parts can be rearranged into two identical words. Tangrams with cut number at most $k$ are called $k$-tangrams. Note that 1-tangrams are exactly squares, and the larger the cut number, the farther the tangram is from a square.

Let $\Sigma_q = \{0, 1, \dots, q-1\}$ denote the $q$-letter alphabet. It is straightforward to check that every binary word of length 4 contains a square, while a famous theorem from Thue in 1906 asserts that there exist infinite words avoiding squares over $\Sigma_3$. In [3], the authors consider a similar question by investigating (infinite) words without tangrams. By Lemma 3 in [9], every infinite word must contain some tangram. Thus, they consider the relation between the size of the alphabet and the cut number of the excluded tangrams. For $k \ge 1$, the authors thus define $t(k)$ as the minimum alphabet size such that there exists an infinite word avoiding $k$-tangrams. By definition, $t(k)$ is non-decreasing, and since every 2-tangram contains a square, the result of Thue shows that $t(1) = t(2) = 3$.

The other results in [3] are summarized in the following.

**Theorem 1 ([3]).**

$$ \bullet t(k) \le 1024 \lfloor \log_2 k + \log_2 \log_2 k + 1 \rfloor \text{ for every } k \ge 3. $$

<footnote n="1">¹ LIRMM, CNRS, Université de Montpellier, Montpellier, France.</footnote>

<footnote n="2">² Univ Lyon, UCBL, CNRS, INSA Lyon, LIRIS, Lyon, France.</footnote>
• $t(k) \le k + 1$ for every $k \ge 4$.

• $4 \le t(3) \le t(4) \le 5$

Moreover, the authors leave as an open problem the exact value of $t(3)$. In this article, we prove the following.

**Theorem 2.** $t(3) = t(4) = 4$.

## 2 Preliminaries

To obtain Theorem 2, we heavily use the following relation observed in [3] between $k$-tangrams and patterns. A pattern $P$ is a finite word over the alphabet $\Delta = \{A, B, \dots\}$, whose letters are called *variables*. An *occurrence* of a pattern $P$ in a word $w \in \Sigma^*$ is a non-erasing morphism $h : \Delta^* \to \Sigma^*$ such that $h(P)$ is a factor of $w$, and a word $w$ avoids a pattern $P$ if it contains no occurrence of $P$. Given a square-free word $w$, a *repetition* in $w$ is a factor of $w$ of the form $uvu$. Its *period* is $|uv|$ and its *exponent* is $\frac{|uvu|}{|uv|}$. Given $\alpha \in \mathbb{Q}$ and $n \in \mathbb{N}$, a word $w$ is $(\alpha^+, n)$-free if it does not contain any repetition with period at least $n$ and exponent strictly greater than $\alpha$. We say that $w$ is $\alpha^+$-free if it is $(\alpha^+, 1)$-free. A morphism $f : \Sigma_s^* \to \Sigma_e^*$ is $q$-uniform if $|f(a)| = q$ for every $a \in \Sigma_s$.

As noticed in [3], a $k$-tangram is an occurrence of some pattern with at most $k$ variables such that every variable occurs exactly twice. So for every $k \ge 1$, there exists a minimum set $S_k$ of such patterns such that avoiding $S_k$ is equivalent to avoiding $k$-tangrams. Obviously, $S_k \subset S_{k+1}$ for every $k \ge 1$. A small case analysis gives the first four sets $S_k$:

• $S_1 = S_2 = \{AA\}$

• $S_3 = \{AA, ABACBC, ABCACB, ABCBAC\}$

• $S_4 = \{AA, ABACBC, ABCACB, ABCBAC, ABACBDCD, ABACDBDC, ABACDCBD, ABCACDBD, ABCADBD, ABCADCBD, ABCADCB, ABCBADCD, ABCBDACD, ABCBDADC, ABCBDCAD, ABCDACBD, ABCDADCB, ABCDBADC, ABCDBDAC, ABCDCADB, ABCDCBAD\}$

In the next section, we prove Theorem 2 by constructing infinite words over $\Sigma_4$ avoiding all patterns in $S_4$. But first, let us show the weaker result $t(3) \le 4$ as a straightforward (and computer-free) consequence of well-known results in pattern avoidance. Following Cassaigne [2], we associate to each pattern a *formula*, by replacing each variable appearing only once by a dot (such variables are called *isolated*). For example, the formula associated to the pattern *ABBACABADAA* is *ABBA.ABA.AA*. The factors between the dots are called *fragments*. Similarly to patterns, an *occurrence* of a formula $f$ in a word $w \in \Sigma^*$ is a non-erasing morphism $h : \Delta^* \to \Sigma^*$ such that every fragment of $f$ is mapped under $h$ to a factor of $w$ (note that the order of the fragments does not matter). A word $w$ avoids a formula $f$ if it contains no occurrence of $f$.

Consider the formula $F_3 = AB.BA.AC.CA.BC$. Notice that the pattern *AA*, considered as a word, contains an occurrence of $F_3$. Moreover, *ABACBC*, *ABCACB*, and *ABCBAC* also contain an occurrence of $F_3$ since they have 5 distinct factors of length 2. So every pattern in $S_3$ contains an occurrence of $F_3$. Baker, McNulty, and Taylor [1] have considered the fixed point $b_4 \in \Sigma_4^\omega$ of the morphism defined by $0 \mapsto 01, 1 \mapsto 21, 2 \mapsto 03, 3 \mapsto 23$ (that is, $b_4 = 01210321012303210121...$) and shown that $b_4$ avoids $F_3$. Then $b_4$ avoids every pattern in $S_3$. So $b_4$ avoids 3-tangrams, which implies that $t(3) \le 4$.
### 3 Proof of $t(4) \le 4$

Unfortunately, the word $b_4$ contains the factor 03210123 which is a 4-tangram. Moreover, backtracking shows that every infinite word over $\Sigma_4$ avoiding 4-tangrams must contain a factor aba for some letters a and b. In particular, every $\frac{7}{5}^+$-free word over $\Sigma_4$ contains a 4-tangram. More generally, we have not been able to find a word that might witness $t(4) \le 4$ in the literature. Thus we use an ad-hoc construction. Consider the 312-uniform morphism $h: \Sigma_6^* \to \Sigma_4^*$ below.

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

We will show that for every $\frac{6}{5}^+$-free word $w$ over $\Sigma_6$, $h(w)$ avoids every pattern in $S_4$. Together with the result of [5] that there exist exponentially many $\frac{6}{5}^+$-free infinite words over $\Sigma_6$, and the fact that $h$ is injective, this implies that there exist exponentially many words over $\Sigma_4$ avoiding 4-tangrams.

First, we show that $h(w)$ is $(\frac{5}{4}^+, 9)$-free by using the following lemma. A uniform morphism $f: \Sigma^* \to \Delta^*$ is synchronizing if for all $a, b, c \in \Sigma$ and $u, v \in \Delta^*$, if $f(ab) = uf(c)v$, then either $u = \varepsilon$ and $a = c$, or $v = \varepsilon$ and $b = c$.

**Lemma 3 ([6]).** Let $\alpha, \beta \in \mathbb{Q}$, $1 < \alpha < \beta < 2$ and $n \in \mathbb{N}^*$. Let $h: \Sigma_s^* \to \Sigma_e^*$ be a synchronizing $q$-uniform morphism (with $q \ge 1$). If $h(w)$ is $(\beta^+, n)$-free for every $\alpha$-free word $w$ such that $|w| < \max(\frac{2\beta}{\beta-\alpha}, \frac{2(q-1)(2\beta-1)}{q(\beta-1)})$, then $h(t)$ is $(\beta^+, n)$-free for every (finite or infinite) $\alpha$-free word $t$.
To see that $h$ is synchronizing, notice that $p = 13032103101230102013$ is a prefix of the $h$-image of every letter and that $p$ does not appear elsewhere. Moreover, we have checked that the $h$-image of every $\frac{6}{5}$-free word of length smaller than $\frac{2 \times \frac{5}{4}}{\frac{5}{4} - \frac{6}{5}} = 50$ is $(\frac{5}{4}, 9)$-free. Therefore $h(w)$ is $(\frac{5}{4}, 9)$-free by Lemma 3.

Now we show that every occurrence $m$ of a pattern $P \in S_4$ in a $(\frac{5}{4}, 9)$-free word is such that $|m(P)|$ is bounded (see Table 1). As an example, let us detail the case of $ABCDACBD$. To lighten notations, we write $y = |m(Y)|$ for every variable $Y$.

**Lemma 4.** Let $z$ be a $(\frac{5}{4}, 9)$-free word. Then if $z$ contains an occurrence $m$ of $ABCDACBD$, then $|m(ABCDACBD)| \le 24$.

**Proof:** Consider an occurrence $m$ of $ABCDACBD$ in $z$. The factor $m(ABCDA)$ of $z$ is a repetition with period $|m(ABCD)|$ and exponent $\frac{|m(ABCDA)|}{|m(ABCD)|}$.

Since $z$ is $(\frac{5}{4}, 9)$-free, then $a + b + c + d \le 8$ or $\frac{2a+b+c+d}{a+b+c+d} \le \frac{5}{4}$. The latter inequality gives $\frac{a}{a+b+c+d} \le \frac{1}{4}$ and then

$$3a \le b + c + d. \qquad (1)$$

Similarly, the repetition $m(BCDACB)$ implies that $a + b + 2c + d \le 8$ or

$$3b \le a + 2c + d. \qquad (2)$$

$m(CDAC)$ implies that $a + c + d \le 8$ or

$$3c \le a + d. \qquad (3)$$

$m(DACBD)$ implies that $a + b + c + d \le 8$ or

$$3d \le a + b + c. \qquad (4)$$

Suppose that $a+c+d \ge 9$. Then the combination $6 \times (1) + 4 \times (2) + 7 \times (3) + 6 \times (4)$ gives $a+c+d \le 0$, a contradiction. Therefore

$$a + c + d \le 8. \qquad (5)$$

This implies

$$c \le 6. \qquad (6)$$

Now suppose that $b \ge 5$, so that $a+b+2c+d \ge 9$. Then the combination $(2) + (5) + (6)$ gives $3b \le 14$, which contradicts $b \ge 5$. Therefore

$$b \le 4. \qquad (7)$$

By (5) and (7), we get that $a+b+c+d \le 12$, hence $|m(ABCDACBD)| \le 24$. $\square$

Now, notice that every pattern in $S_4$ is doubled, that is, every variable appears at least twice [4, 7]. Alternatively, a doubled pattern is a formula with exactly one fragment. The avoidability exponent $AE(f)$ of a pattern or a formula $f$ is the largest real $x$ such that every $x$-free word avoids $f$. By Lemma 10 in [8], the avoidability exponent of a doubled pattern with 4 variables is at least $\frac{6}{5}$. This bound is not good
enough, so we have computed the avoidability exponent of every pattern in $S_4$, see Table 1. Notice that these avoidability exponents are greater than $\frac{5}{4}$. Then the $(\frac{5}{4}^+, 9)$-freeness of $h(w)$ ensures that there is no "large" occurrence of a pattern in $S_4$, that is, such that the period of every repetition is at least 9. This is witnessed by the combination $6 \times (1) + 4 \times (2) + 7 \times (3) + 6 \times (4)$ in the proof of Lemma 4. Now, to bound the length of the other occurrences, we do not rely on a tedious analysis by hand as in Lemma 4. Instead, the bound in the last column of Table 1 is computed as the maximum of $2(a + b + c + d)$ such that $1 \le a, b, c, d < 100^{(i)}$ and $(a + b + c + d \le 8 \lor 3a \le b + c + d) \land (a + b + 2c + d \le 8 \lor 3b \le a + 2c + d) \land (a + c + d \le 8 \lor 3c \le a + d) \land (a + b + c + d \le 8 \lor 3d \le a + b + c)$, again with the example of $P = ABCDACBD$ of Lemma 4.

Finally, for every pattern $P \in S_4$, we check exhaustively by computer that $h(w)$ contains no occurrence of $P$ of length at most the corresponding bound$^{(ii)}$. So $h(w)$ avoids every $P \in S_4$. So $h(w)$ avoids 4-tangrams. So $t(4) \le 4$.

<table><caption>Tab. 1: The patterns in $S_4$, their avoidability exponent, and the upper bound for the length of their occurrences in a $(\frac{5}{4}^+, 9)$-free word.</caption><thead><tr><th>Pattern P</th><th>P<sup>R</sup></th><th>AE(P)</th><th>Bound on |m(P)|</th></tr></thead><tbody><tr><td>AA</td><td>self-reverse</td><td>2</td><td>16</td></tr><tr><td>ABACBC</td><td>self-reverse</td><td>1.414213562 = &radic;2</td><td>30</td></tr><tr><td>ABCACB</td><td>ABCBAC</td><td>1.361103081</td><td>26</td></tr><tr><td>ABACBDCD</td><td>self-reverse</td><td>1.381966011</td><td>32</td></tr><tr><td>ABACDBDC</td><td>ABCBADCD</td><td>1.333333333 = <sup>4</sup>&frasl;<sub>3</sub></td><td>40</td></tr><tr><td>ABACDCBD</td><td>ABCACDBD</td><td>1.340090632</td><td>32</td></tr><tr><td>ABCADBDC</td><td>ABCBDACD</td><td>1.292893219</td><td>32</td></tr><tr><td>ABCADCBD</td><td>self-reverse</td><td>1.295597743</td><td>28</td></tr><tr><td>ABCADCDB</td><td>ABCBDCAD</td><td>1.327621756</td><td>32</td></tr><tr><td>ABCBDADC</td><td>self-reverse</td><td>1.302775638</td><td>32</td></tr><tr><td>ABCDACBD</td><td>self-reverse</td><td>1.258055872</td><td>24</td></tr><tr><td>ABCDADCB</td><td>ABCDCBAD</td><td>1.288391893</td><td>42</td></tr><tr><td>ABCDDBADC</td><td>self-reverse</td><td>1.267949192</td><td>24</td></tr><tr><td>ABCDDBDAC</td><td>ABCDCADB</td><td>1.309212406</td><td>44</td></tr></tbody></table>

# 4 Concluding remarks

Our words $h(w)$ contain the factor $012130212321$ which is a 5-tangram since $0|1|213021|2|3|21$ can be rearranged as $213021|2|1|3|0|21$. The exact value of $t(k)$ remains unknown for every $k \ge 5$. In particular, we only known that $4 \le t(5) \le 6$. Improving the upper bound on $t(5)$ using the approach in this paper might be tedious, as we expect the set $S_5$ to be quite large.

<footnote>(i) We chose the bound 100 as it is sufficient and keeps the computer check short.</footnote>

<footnote>(ii) The C code to check the properties of the morphism $h$ and the bounds on $|m(P)|$ is available at http://www.lirmm.fr/~ochem/morphisms/tangram4.htm.</footnote>
References

[1] K. A. Baker, G. F. McNulty, and W. Taylor. Growth problems for avoidable words. *Theor. Comput. Sci.*, 69(3):319–345, 1989.

[2] J. Cassaigne. *Motifs évitables et régularité dans les mots*. PhD thesis, Université Paris VI, 1994.

[3] M. Dębski, J. Grytczuk, B. Pawlik, J. Przybyło, and M. Śleszyńska-Nowak. Words avoiding tangrams. *Annals of Combinatorics.*, 2024.

[4] A. Domenech and P. Ochem. Doubled patterns with reversal and square-free doubled patterns. *Electron. J. Combinatorics.*, 30(1), 2023.

[5] R. Kolpakov and M. Rao. On the number of Dejean words over alphabets of 5, 6, 7, 8, 9 and 10 letters. *Theor. Comput. Sci.*, 412(46):6507–6516, 2011.

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

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

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

[9] N. Rampersad. Further applications of a power series method for pattern avoidance. *Electron. J. Combinatorics.*, 18(1), 2011.