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.

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.

April 22 2025: Be'eri Greenfeld On the Complexity of Infinite Words

Given an infinite word $w$, its complexity function $p_w(n)$ counts the number of distinct subwords of length $n$ it contains. A longstanding open problem in the combinatorics of infinite words is the {\it inverse problem}: describe which functions $f: \mathbb N \to \mathbb N$ arise as complexity functions of infinite words. Such functions must be non-decreasing and, unless eventually constant, strictly increasing; they must also be submultiplicative, i.e., $f(n+m)≤f(n)f(m)$. Many interesting results, both positive and negative, have been obtained in this direction.

We resolve this problem up to asymptotic equivalence in the sense of large-scale geometry. Specifically, given any increasing, submultiplicative function $f$, we construct an infinite recurrent word $w$ such that $c f(cn) ≤ p_w(n) ≤ d f(dn)$ for some constants $c,d>0$. For uniformly recurrent words, we obtain a weaker version allowing a linear error factor. Time permitting, we will discuss connections and applications of these results to asymptotic questions in algebra.

Joint work with C. G. Moreira and E. Zelmanov.

April 8 2025: Hajime Kaneko Analogs of Markoff and Lagrange spectra on one-sided shift spaces

slides

The Lagrange spectrum is related to the rational approximations of badly approximable numbers. The discrete part of the spectrum is denoted in terms of Christoffel words. A multiplicative analog of the Lagrange spectrum was recently investigated, which is defined by Diophantine approximations of geometric sequences and more general linear recurrences. Dubickas investigated the minimal limit points of certain multiplicative Markoff-Lagrange spectra in terms of symbolic dynamical systems and certain substitutions.

In this talk, we study an analog of the Markoff-Lagrange spectrum for general one-sided shift spaces. As our main results, we determine the discrete parts and minimal limit points in terms of $S$-adic sequences, where $S$ is an infinite set of substitutions. This is joint work with Wolfgang Steiner.

March 25 2025: Vuong Bui An explicit condition for boundedly supermultiplicative subshifts

slides

We study some properties of the growth rate of $L(A,F)$, that is, the language of words over the alphabet $A$ avoiding the set of forbidden factors $F$. We first provide a sufficient condition on $F$ and $A$ for the growth of $L(A,F)$ to be boundedly supermultiplicative. That is, there exist constants $C>0$ and $\alpha\ge 0$, such that for all $n$, the number of words of length $n$ in $L(A,F)$ is between $\alpha^n$ and $C\alpha^n$. In some settings, our condition provides a way to compute $C$, which implies that $\alpha$, the growth rate of the language, is also computable whenever our condition holds. We also apply our technique to the specific setting of power-free words where the argument can be slightly refined to provide better bounds. Finally, we apply a similar idea to $F$-free circular words and in particular we make progress toward a conjecture of Shur about the number of square-free circular words.

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

slides

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).

February 25 2025: Bartek Pawlik Words Avoiding Tangrams

slides

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.

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.