# On ternary Dejean words avoiding 010

Pascal Ochem

► To cite this version:

Pascal Ochem. On ternary Dejean words avoiding 010. Notes on Number Theory and Discrete Mathematics, 2023, 29 (3), pp.545-548. 10.7546/nntdm.2023.29.3.545-548. hal-04241523

HAL Id: hal-04241523

https://hal.science/hal-04241523v1

Submitted on 14 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 CC BY 4.0 - Attribution - International License
# On ternary Dejean words avoiding 010

Pascal Ochem

LIRMM, Université de Montpellier, CNRS

Montpellier, France

e-mail: ochem@lirmm.fr

**Received:** 3 March 2023

**Revised:** 17 July 2023

**Accepted:** 25 July 2023

**Online First:** 27 July 2023

**Abstract:** Thue has shown the existence of three types of infinite square-free words over $\{0, 1, 2\}$ avoiding the factor 010. They respectively avoid $\{010, 212\}$, $\{010, 101\}$, and $\{010, 020\}$. Also Dejean constructed an infinite $(\frac{7}{4})$-free ternary word. A word is *d*-directed if it does not contain both a factor of length *d* and its mirror image. We show that there exist exponentially many $(\frac{7}{4})$-free 180-directed ternary words avoiding 010. Moreover, there does not exist an infinite $(\frac{7}{4})$-free 179-directed ternary word avoiding 010.

**Keywords:** Word, Repetitions.

**2020 Mathematics Subject Classification:** 68R15.

## 1 Introduction

This note is about words avoiding repetitions, a well-studied area in combinatorics on words [5,6]. A *repetition* is a factor of the form $r = u^n v$ where *u* is non-empty and *v* is a prefix of *u*. Then $|u|$ is the *period* of the repetition *r* and its *exponent* is $|r|/|u|$. A word is $\alpha$-free (resp. $\alpha$-free) if it contains no repetition with exponent $\beta$ such that $\beta > \alpha$ (resp. $\beta \ge \alpha$).

We consider ternary square-free words (i.e., 2-free words) with additional avoidance constraints. Thue [7] has shown that there exist infinite square-free words avoiding the factors $\{010, 212\}$, $\{010, 101\}$, and $\{010, 020\}$ respectively. In each case, the avoiding word is essentially unique. Consider for example the fixed point of the morphim $0 \mapsto 012, 1 \mapsto 02, 2 \mapsto 1$, which is a

<figure><img src="image_2.png" /></figure>
[4] Ochem, P. (2006). A generator of morphisms for infinite words. *RAIRO – Theoretical Informatics and Applications*, 40, 427–441.

[5] Ochem, P., Rao, M., & Rosenfeld, M. (2018). Avoiding or limiting regularities in words. *Sequences, Groups, and Number Theory (Trends in Mathematics)*, 177–212.

[6] Rampersad, N., & Shallit, J. (2012). Repetitions in words. *Combinatorics, Words and Symbolic Dynamics (Encyclopedia of Mathematics and its Applications)*, 101–150.

[7] Thue, A. (1912). Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. *Norske Videnskabers Selskabs Skrifter, I Mathematisch-Naturwissenschaftliche Klasse*, 1, 1–67. Reprinted in Nagell, T. (Ed.). *Selected Mathematical Papers of Axel Thue*. Universitetsforlaget, Oslo, 1977, 413–478.