Iteration of continuous functions, univoque numbers, and automatic sequences

Jean-Paul Allouche (Institut Mathématique de Jussieu)

Frank Adams Room 1, Alan Turing Building,

At the beginning of the eighties, Michel Cosnard, who was working at that time on iteration of unimodal continuous functions, asked me about a "combinatorial" problem. He was interested in the set of binary sequences defined by
\[\forall k\geq 0,\, \overline{A}\leq S^k(A)\leq A\]
where \(S\) is the shift on sequences, \(\leq\) is the lexicographical order, and \(\overline{A}\) is the sequence obtained from \(A\) by replacing \(0\)'s by \(1\)'s and \(1\)'s by \(0\)'s. The first few sequences in this set are
\[(10)^\infty, (1100)^\infty, (11010010)^\infty,\dots\]
seemingly tending to a limit
We identified this limit as an avatar of the (Prouhet-)Thue-Morse sequence. We wrote a Note aux Comptes-Rendus de l'Académie des Sciences, Michel Cosnard published an article on the dynamical part, while the combinatorial part was written down in the author's Thèse d'État.
About 20 years later, Jeff Shallit told me that a paper by Komornik and Loreti had just appeared: it was reproving the Thue-Morse result in a different context, namely the context of "univoque numbers", i.e., real numbers \(\beta\) in \((0,1)\) such that there exists a unique expansion of \(1\) as
\[1=\sum_{i\geq 1}\frac{a_i}{\beta^i},\text{ with }a_i\in\{0,1\}.\]
We will describe these results as well as results in a recent paper by Matthew Clarke, Nikita Sidorov and the author, that shows a link with Sharkovskiĭ's order.

Import this event to your Outlook calendar
▲ Up to the top