Éviter les carrés additifs sur ℤ²

Matthieu Rosenfeld
LIP, ENS de Lyon
https://www.lirmm.fr/~mrosenfeld/

Date(s) : 21/03/2017   iCal
13 h 00 min - 14 h 00 min

Les résultats de Thue en 1906-1912 ont initié l’étude de l’évitabilité des motifs dans les mots. C’est Erdös en 1957 qui souleva le cas des répétitions abéliennes :
est-il possible d’éviter les carrés abéliens (deux facteurs consécutifs qui sont permutations l’un de l’autre) dans les mots infinis sur 4 lettres?
Keränen répondit positivement en 1992 en construisant explicitement un tel mot par morphisme. Erdös demanda aussi s’il est possible d’éviter les longs carrés sur l’alphabet binaire et Entringer, Jackson et Schatz donnèrent une réponse positive en 1974.

Mäkelä posa, en 2002, deux questions rappelant les questions d’Erdös et concernant l’évitabilité des longs carrés (resp., cubes) abéliens sur l’alphabet ternaire (resp., binaire).

Je présenterai une technique pour décider si un mot morphique évite les répétitions abéliennes (et certaines généralisations). Cette technique permet de prouver certains nouveaux résultats d’évitabilité. En particulier nous répondons à la version faible d’une question de Mäkelä et montrons que les carrés additifs sont évitables sur ℤ². Ce dernier résultat peut se reformuler en disant qu’il existe une séquence infinie sur un ensemble fini de ℤ² qui ne contient pas deux blocs consécutifs ayant la même longueur et la même somme. Ces résultats sont basés sur un travail avec Michaël Rao.

Avoid additive squares on ℤ²

Thue’s results in 1906-1912 initiated the study of the avoidability of patterns in words. It was Erdös in 1957 who raised the case of abelian repetitions: is it possible to avoid abelian squares (two consecutive factors which are permutations of each other) in infinite words over 4 letters? Keränen responded positively in 1992 by explicitly constructing such a word by morphism. Erdös also asked if it is possible to avoid long squares on the binary alphabet and Entringer, Jackson and Schatz gave a positive answer in 1974.

In 2002, Mäkelä asked two questions reminiscent of Erdös’ questions and concerning the avoidability of abelian long squares (resp., Cubes) on the ternary (resp., Binary) alphabet.

I will present a technique for deciding whether a morphic word avoids abelian repetitions (and some generalizations). This technique makes it possible to prove certain new avoidability results. In particular, we answer the weak version of a Mäkelä question and show that the additive squares are avoidable on ℤ². This last result can be reformulated by saying that there exists an infinite sequence on a finite set of ℤ² which does not contain two consecutive blocks having the same length and the same sum. These results are based on a work with Michaël Rao.

https://arxiv.org/abs/1511.05875

http://perso.ens-lyon.fr/matthieu.rosenfeld/

Catégories



Retour en haut