The seminar takes place biweekly on Tuesdays at 15:00 Paris time. 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.

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.

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.

February 25 2025: Bartek Pawlik Words Avoiding Tangrams

Work in collaboration with Michał Dębski, Jarosław Grytczuk, Jakub Przybyło and Małgorzata Śleszyńska-Nowak.

If, in a given word $W$, each letter appears an even number of times, then $W$ can be split into two identical, disjoint subwords. For example, the word $\mathtt{hotshots}$ can be split into two $\mathtt{hots}$ by dividing the word exactly in the middle: $\mathtt{hots\,|\,hots}$. More generally, any square can be separated into two identical words with a single cut. The word $\mathtt{tattletale}$ requires three cuts: $\mathtt{tat\,|\,tle\,|\,ta\,|\,le}$ to split it into two words $\mathtt{tatle}$. The minimal number of cuts needed to divide a word $W$ into two identical subwords is called the cut number of $W$. During the lecture, I will discuss several topics related to the cut number.

March 11 2025:Pierre Letouzey Generalizing some Hofstadter functions: G, H and beyond

Hofstadter's G function is recursively defined via $G(0)=0$ and then $G(n)=n-G(G(n-1))$. Following Hofstadter, a family $(F_k)$ of similar functions is obtained by varying the number $k$ of nested recursive calls in this equation. We present here a few nice properties of these functions. In particular, they can be described via some infinite morphic words generalizing the Fibonacci word. This was crucial for proving that this family is ordered pointwise: for all $k$ and $n$, $F_k(n) \le F_{k+1}(n)$. Moreover, these functions have a simple behavior on well-chosen numerical representations (Zeckendorf decompositions for some Fibonacci-like sequences). Thanks to that, we were also able to estimate the discrepancies for these $F_k$, i.e. the maximal distances between each $F_k$ and its linear equivalent. This whole work was formally proved using the Coq proof assistant (except for a beautiful fractal !) and we will give a gentle introduction to this Coq development.

Joint work with Shuo Li (U. Winnipeg) and Wolfgang Steiner (IRIF, Paris).

March 25 2025: Vuong Bui

April 8 2025: Hajime Kaneko

April 22 2025: Be'eri Greenfeld

May 6 2025: Jarkko Peltomäki

May 20 2025: Pranjal Jain

June 3 2025: Curtis Bright

June 17 2025: Noy Soffer Aranov

July 15 2025: Elżbieta Krawczyk Quasi-fixed points of substitutions and substitutive systems

We study automatic sequences and automatic systems (symbolic dynamical systems) generated by general constant length (nonprimitive) substitutions. While an automatic system is typically uncountable, the set of automatic sequences is countable, implying that most sequences within an automatic system are not themselves automatic. We provide a complete classification of automatic sequences that lie in a given automatic system in terms of the so-called quasi-fixed points of the substitution defining the system. Quasi-fixed points have already appeared implicitly in a few places (e.g. in the study of substitutivity of lexicographically minimal points in substitutive systems or in the study of subsystems of substitutive systems) and they have been described in detail by Shallit and Wang and, more recently, B\'eal, Perrin, and Restivo . We conjecture that a similar statement holds for general nonconstant length substitutions.

February 11 2025: Josef Rukavicka Palindromic length of infinite aperiodic words

slides

The palindromic length of the finite word $v$ is equal to the minimal number of palindromes whose concatenation is equal to $v$. It was conjectured in 2013 that for every infinite aperiodic word $x$, the palindromic length of its factors is not bounded. We prove this conjecture to be true.

Here is the paper.

January 28 2025: Lucas Mol Avoiding abelian and additive powers in rich words

slides

We construct an infinite additive 5-power-free rich word over $\{0,1\}$ and an infinite additive 4-power-free rich word over $\{0,1,2\}$. Both constructions involve affine morphisms, for which the length and sum of the images of the letters are linear functions of the letters. This allows us to prove the additive power-freeness of our constructions using a recent variation of the template method due to Currie, Mol, Rampersad, and Shallit.

January 14 2025: Christophe Reutenauer Christoffel matrices and Sturmian determinants

Work in collaboration with Jeffrey Shallit.

1. The set of Christoffel matrices (that is, Burrows-Wheeler matrices of Christoffel words) of size $n$ by $n$, where the alphabet is some commutative ring $R$, form a monoid under multiplication, and those which are invertible, form a subgroup of $GL_n(R)$. (this result was also obtained independently by Luca Zamboni)

2. The determinant of a Christoffel matrix has a simple form, using the Zolotareff symbol (the latter extends the Jacobi symbol).

3. Taking $n$ factors of length $n$ of a Sturmian sequence over $0$, $1$, one obtains a matrix and a determinant. There are$n+1$ such determinants; ordering them suitably, these $n+1$ determinants form a word on a two- or three-letter alphabet contained in $Z$; this word is perfectly clustering. If there are three letters, then one of them is the sum of the two others.

The talks of 2023 are available here.

The talks of 2023 are available here.

The talks of 2022 are available here.

The talks of 2021 are available here.

The talks of 2020 are available here.

Several starting lectures by Anna Frid are available here.