# One World Combinatorics on Words Seminar

The seminar takes place biweekly on Mondays at 15:00 CET. In summer, it means 6:00 in California, 9:00 in New-York or Waterloo, 14:00 in London, 15:00 in Paris, 16:00 in Moscow and 22:00 in Tokyo. In winter, some of these numbers change. Please check in advance the time in your time zone.

#### URL

The address of the Zoom meeting is https://zoom.us/j/92245493528 . The password is distributed in announcements. If you want to receive them, or receive them and want to unsubscribe, please write to Anna Frid.

All recorded talks are also available here.

#### Organizers:

Anna E. Frid, Aix-Marseille Université, Narad Rampersad, University of Winnipeg, Jeffrey O. Shallit, University of Waterloo, Manon Stipulanti, Université de Liège.

If you are interested in giving a talk, you are welcome to contact Narad Rampersad and Manon Stipulanti.

### Upcoming talks

** 30 May 2022: Pierre-Adrien Tahay** *Column representation of words in cellular automata*

The task of representing a sequence over a finite alphabet in the space-time diagram of a cellular automaton is a non-trivial and still not entirely explored topic. One of the first results on the subject was done by Fischer in 1965 with a construction of the characteristic sequence of primes numbers. Many results and improvements have been established since. In 2015, Rowland and Yassawi showed that there is a close connection between the $p$-automatic sequences and the linear cellular automata. More precisly the columns of linear cellular automata are $p$- automatic sequences and all $p$-automatic sequences can be realized by some linear cellular automata with memory. Moreover their proof is constructive. In 2018, Marcovici, Stoll and Tahay investigated some constructions for nonautomatic sequences such as the characteristic sequences of polynomials and the Fibonacci word.

In this talk I will present recent results obtained in collaboration with Francesco Dolce where we generalized the construction for the Fibonacci word in a column of a cellular automaton, to any Sturmian word with quadratic slope. Our proof is constructive and use the ultimate periodicity of the continued fraction expansion of the slope of the word.

** 13 June 2022: Kristina Ago and Bojan Bašić ** *Some recent results on two “palindromicity” measures*

Various measures of the degree of “palindromicity” of a given word have been defined in the literature. In this talk we present some of our results concerning two such measures. The first one is the so-called *palindromic defect* (or only *defect*). Let $|\mathrm{Pal}(w)|$ denote the number of palindromic factors of a word $w$. The palindromic defect of $w$ is defined by $|w|+1-|\mathrm{Pal}(w)|$ (it can be proved that this value is always nonnegative). This definition can be naturally extended to infinite words. While infinite words whose defect is zero (called *rich*) have been researched quite much, there are noticeably less results in the literature on infinite words of finite positive defect. In the first part of the talk we introduce a construction of an infinite family of infinite words whose defect is finite and in many cases positive (with fully characterized cases when the defect is $0$), and we analyze their properties. Each of those words is either periodic (which is a less interesting case, and explicitly characterized), or recurrent but not uniformly recurrent. Examples of explicit constructions of such words that are not uniformly recurrent have been quite deficient in the literature so far.

The second part of talk is devoted to the so-called *MP-ratio*. The concept of MP-ratio is based on palindromic subwords (and not factors) of a given finite word. Call a word over an $n$-ary alphabet *minimal-palindromic* if it does not contain palindromic subwords of length greater than $\big\lceil\frac{|w|}n\big\rceil$. The *MP-ratio* of a given $n$-ary word $w$ is defined as the quotient $\frac{|rws|}{|w|}$, where $r$ and $s$ are words such that the word $rws$ is minimal-palindromic and that the length $|r|+|s|$ is minimal possible. In order for the MP-ratio to be well-defined, it has to be shown that such a pair $(r,s)$ always exist. It has been known for some time that this is true in the binary case, but this question becomes much more complicated for larger arities. In this talk we show that the MP-ratio is well-defined for any arity, and we present some further results on this topic.

** 20 June 2022: Antoine Domenech **

** 27 June 2022: Pierre Popoli**

** 11 July 2022: Zachary Chase**

### Past talks 2022

** 16 May 2022: Moussa Barro** *Billard dans le cube* in French with English slides

On considère le billard dans un cube. On code une trajectoire par les faces rencontrées. Le but de l'exposé sera de décrire le langage d'un tel mot dans le cas ou l'orbite n'est pas dense.

** 25 April 2022: Christophe Reutenauer** *Constructions and parametrization of conjugates of Christoffel words*

Following a recent work of Michel Laurent and the first author, we propose a deformation of the Rauzy rules (equivalently of the de Luca construction of standard words) in order to construct all conjugates of all Christoffel words (equivalently of all standard words). This construction is based on integer legal Ostrowski representations, following Frid. The constructed word depends only the represented integer (and even works in the free group, up to conjugation however). Choosing greedy representations, we determine of the longest border of conjugates, thereby recovering results of Lapointe on the smallest periods. Choosing the lazy representation, we may revisit the Sturmian graph of Epifanio, Frougny, Gabriele, Mignosi and Shallit; in particular we show that this graph is essentially a subgraph of the Stern-Brocot tree, and that the compact graph (which is a compaction of the minimal automaton of the set of suffixes of a central word) is similarly embedded in the tree of central words of Aldo de Luca.

** 4 April 2022: Colin Defant** *Anti-powers in Aperiodic Recurrent Words*

In 2016, Fici, Restivo, Silva, and Zamboni introduced the notion of a $k$-anti-power, which is a word of the form $w_1 \cdots w_k$, where $w_1,\ldots,w_k$ are words of the same length that are all distinct. I will begin by reviewing the main results that these authors proved about anti-powers. I will then discuss anti-powers appearing as factors in the Thue-Morse word. This will lead into a discussion of anti-powers in aperiodic recurrent words and aperiodic morphic words.

** 21 March 2022: Narad Rampersad** *Applications of Walnut to problems of local periodicity*

There are a number of natural choices for measuring the local periodicity at a given position $i$ of an infinite word: for instance, one could consider repetitions 1) ending at position $i$; 2) starting at position $i$; or 3) centered at position $i$. With regards to option 1), it is known that aperiodic infinite words cannot have all sufficiently large prefixes end with cubes. It is natural then to ask for such words how many prefixes can end with cubes. Using Walnut, we obtain a characterization of these prefixes for the Fibonacci word. Regarding option 3), Mignosi and Restivo introduced an interesting complexity measure: $h_{\bf w}(n)$, which is the average of the local periods over the first $n$ positions of ${\bf w}$. Again using Walnut, we estimate the asymptotic behaviour of this function for some 2-automatic sequences, such as the Thue-Morse sequence, the Rudin-Shapiro sequence, and the period-doubling sequence.

** 07 March 2022: Jean-Paul Allouche** *Thue and 7-3*

March 7, 2022 (in French 7/3) is the 100th anniversary of the death of Axel Thue. He was a Norwegian mathematician, principally known for his work in Diophantine approximation, but he is also known for his work in combinatorics.

We will speak a little of his number-theoretic papers, and more about his contribution in combinatorics, essentially restricting ourselves to the –ubiquitous– Thue-Morse or Prouhet-Thue-Morse sequence. We will try to survey not only some well-known features of this sequence, but also less classical properties: one of these is an occurrence of… 7/3 for this sequence, the other is about Shogi (将棋), or Japanese chess, and the Sennichite (千日手) (a new rule decided after a play dated March… 8, 1983).

To conclude this abstract, we do not resist to give a quote of Thue: “The further removed from usefulness or practical application, the more important.” Removed from practical application? one might want to look at the definition of the programming language “Thue” that Wikipedia describes as follows: “Thue is an esoteric programming language invented by John Colagioia in early 2000. It is a meta-language that can be used to define or recognize Type-0 languages from the Chomsky hierarchy. Because it is able to define languages of such complexity, it is also Turing-complete itself. Thue is based on a nondeterministic string rewriting system called semi-Thue grammar, which itself is named after the Norwegian mathematician Axel Thue.”

**21 February 2022: Etienne Moutot** *Pattern complexity of 2D substitutive shifts*

In this presentation, I will talk about pattern complexity of two-dimensional substitutive shifts. More precisely, I will focus on lower bounds on the complexity of **aperiodic** 2D substitutive shifts.

*Pattern complexity* consists in counting the number of different mxn rectangular patterns that appear in an infinite coloring of $\mathbb Z^2$ or in a shift space. A corollary of our recent work with Jarkko Kari on Nivat's conjecture [1] shows that any aperiodic subshift have pattern complexity at least $mn+1$ for all $m$ and $n$.

With Coline Petit-Jean we have been trying to improve this lower bound for a particular class of shift spaces: substitutive shifts. For some substitutions (*primitive* and *marked* substitutions), we show that if their shift space is aperiodic, then it has complexity at least $C*mn$, with $C>1$ a constant depending on the substitution. I will also talk briefly about non-marked substitutions and why our current proof does not apply to them, even if we believe that a similar result might still hold.

[1] Decidability and Periodicity of Low Complexity Tilings. Jarkko Kari, Etienne Moutot, Theory of Computing Systems, 2021

**07 February 2022: Michel Dekking ** *Combinatorics of Fibonacci and golden mean number representations*

How many ways are there to represent a number as a sum of powers of the golden mean? Among these, what is the best way to do this? What is the relation with representing a number as a sum of Fibonacci numbers? I will give some answers to these questions in my talk.

**24 January 2022: Markus Whiteland** *On some decidable properties of discrete-time linear dynamical systems*

A discrete-time linear dynamical system (LDS) $(A,x)$ is the orbit of a point $x \in \mathbb{R}^d$ under a linear map $A\colon \mathbb{R}^d \to \mathbb{R}^d$. In this talk we consider decision problems on LDS arising from program verification, such as reachability problems: given a LDS $(A,x)$ and a semi-algebraic target set $T \in \mathbb{R}^d$, does the orbit intersect $T$? It is well-known that such questions quickly lead to open problems, such as Skolem's problem on linear recurrence sequences. We identify the borderline between hard instances and decidable instances with respect to the dimension of the target set $T$. The methods used in the decidable cases quickly give rise to symbolic dynamical systems over which we have a lot of control: this allows us to go beyond mere reachability to deciding $\omega$-regular properties of the LDS with respect to a low-dimensional target set $T$.

Joint work with C. Baier, F. Funke, S. Jantsch, T. Karimov, E. Lefaucheux, F. Luca, J. Ouaknine, D. Purser, A. Varonka, and J. Worrell.

** 10 January 2022: Lubomíra Dvořáková ** *On minimal critical exponent of balanced sequences*

The conjecture stated by Rampersad, Shallit and Vandomme says that the minimal critical exponent of balanced sequences over the alphabet of size $d>4$ equals $(d-2)/(d-3)$. This conjecture is known to hold for $d=5, 6, 7, 8, 9, 10$.

In this talk, we will describe in more details the ideas and the techniques used to refute this conjecture by showing that the picture is different for bigger alphabets. We prove that critical exponents of balanced sequences over an alphabet of size $d>10$ are lower bounded by $(d-1)/(d-2)$ and this bound is attained for all even numbers $d>10$.

According to this result, we conjecture that the least critical exponent of a balanced sequence over $d$ letters is $(d-1)/(d-2)$ for all $d>10$.

### Archives 2021

The talks of 2020 are available here.

### Archives 2020

The talks of 2020 are available here.

### Lectures on combinatorics on words

Several starting lectures by Anna Frid are available here.