Skip to Main content Skip to Navigation

Évitabilité de puissances additives en combinatoire des mots

Abstract : The present thesis is dedicated to the various aspects of the problem of avoiding additive cubes in the fixed points of morphisms. Problems concerning the avoidability of additive powers are closely related to questions in the theory of semigroups. Since the publication of the article of J. Cassaigne, J.D. Currie, L. Schaeffer and J.O. Shallit (2013) we know that it is possible to construct an infinite word over {0, 1 ,3, 4} that avoids additive cubes, i.e., a word that avoids three consecutive blocks of same size and same sum. We first explain the methods used by the authors in their article, and then use it as a starting point for our discussions, with the ultimate aim to clarify the various similarities and connections between the different morphisms that allow to avoid additive cubes on alphabets over 4 letters. We next discuss our implementation in C++ of the investigation of theses morphisms, and then proceed to give an infinite family of morphisms (corresponding to classes of equivalence) that avoid additive cubes. After this investigation, we give a general proof scheme that is based on substitutions between morphisms. The main result of the thesis is that for any alphabet of 4 letters, with the sole exception of the alphabet {0, 1 ,2, 3} and its affine transformations, there is an explicit morphism whose infinite fixed point avoids additive cubes over the given alphabet. This work has been carried out in collaboration with Matthieu Rosenfeld and gave rise to an article in a peer-reviewed journal. In order to show this result, we use arguments from the article of Cassaigne et al., several numerical estimates for the underlying quantities, case disjunction as well as symmetry considerations for the alphabets under consideration. In the final part of the thesis we then study the question of avoiding additive cubes over {0, 1 ,2, 3} with the hope to answer a question posed by M. Rao and M. Rosenfeld in 2018. This alphabet is the only 4-letters alphabet where our result does not apply. We first study by graphical means the words that contain additive powers, and we discuss and implement in a second step two parallelized computer programs. The first program detects in an efficient way the occurrence of additive powers in very long words, whereas the second one allows to create long words over {0, 1 ,2, 3} without introducing any additive cube. With the help of these programs, we obtain a word of over 70 million letters that avoids additive cubes over {0, 1 ,2, 3}. This largely improves on the former known bound (1.4 x 10^5). To obtain our result, as suggested by our graphical considerations, we periodically reverse the order of priority for the choice of the letters in the construction of our word. Our programs use multi-computers and multi-threads settings to gain considerably on efficiency.
Document type :
Complete list of metadata
Contributor : Thèses Ul <>
Submitted on : Wednesday, April 21, 2021 - 9:49:12 AM
Last modification on : Friday, April 23, 2021 - 3:33:14 AM


Files produced by the author(s)


  • HAL Id : tel-03203854, version 1


Florian Lietard. Évitabilité de puissances additives en combinatoire des mots. Mathématiques [math]. Université de Lorraine, 2020. Français. ⟨NNT : 2020LORR0259⟩. ⟨tel-03203854⟩



Record views


Files downloads