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.

March 5 2024: Finn Lidbetter Improved bound for the Gerver-Ramsey collinearity problem

Let $S$ be a finite subset of $\mathbb{Z}^n$. A vector sequence $(z_i)$ is an $S$-walk if and only if $z_{i+1}-z_i$ is an element of $S$ for all $i$. Gerver and Ramsey showed in 1979 that for $S\subset\mathbb{Z}^3$ there exists an infinite $S$-walk in which no $5^11+1=48,828,126$ points are collinear. Using the same general approach, but with the aid of a computer search, we show how to improve the bound to $189$. We begin by restating the infinite $S$-walk as the fixed point of iterating a morphism defined for a $12$ letter alphabet.

March 19 2024: Cor Kraaikamp

April 2 2024: John Campbell On the evaluation of infinite products involving automatic sequences

We explore and discuss some recently introduced techniques concerning the evaluation of infinite products involving automatic sequences.

April 16 2024: Radosław Piórkowski

April 30 2024: Michael Baake

May 14 2024: Josef Rukavicka

May 28 2024: Pascal Ochem

June 11 2024: Markus Whiteland

June 25 2024: Julien Cassaigne

July 9 2024: Jamie Simpson

February 20 2024: Christopher Cabezas Large normalizer of odometers and higher-dimensional automatic sequences

slides

For a $\mathbb Z^d$ topological dynamical system $(X, T, \mathbb Z^d)$, an isomorphism is a self-homeomorphism $\phi : X\to X$ such that for some matrix $M \in GL(d, \mathbb Z)$ and any $n \in \mathbb Z^d$, $\phi \circ T^n = T^{M_n} \circ \phi$, where $T^n$ denote the self-homeomorphism of $X$ given by the action of $n \in \mathbb Z^d$. The collection of all the isomorphisms forms a group that is the normalizer of the set of transformations $T^n$. In the one-dimensional case isomorphisms correspond to the notion of flip conjugacy of dynamical systems and by this fact are also called reversing symmetries.

These isomorphisms are not well understood even for classical systems. In this talk we will present a description of them for odometers and more precisely for $\mathbb Z^2$-constant base odometers, that is not simple. We deduce a complete description of the isomorphism of some $\mathbb Z^2$ minimal substitution subshifts. Thanks to this, we will give the first known example of a minimal zero-entropy subshift with the largest possible normalizer group. This is a joint work with Samuel Petite (Universitè de Picardie Jules Verne).

February 6 2024: Eric Rowland Algebraic power series and their automatic complexity

slides

A theorem of Christol gives a characterization of automatic sequences over a finite field: a sequence is automatic if and only if its generating series is algebraic. Since there are two representations for such a sequence – as an automaton and as a bivariate polynomial – a natural question is how the size of one representation relates to the size of the other. Bridy used tools from algebraic geometry to bound the size of the minimal automaton in terms of the size of the minimal polynomial. We have a new proof of Bridy's bound that works by converting algebraic sequences to diagonals of rational functions. Crucially for our interests, this approach can be adapted to work not just over a finite field but over the integers modulo a prime power. This is joint work with Manon Stipulanti and Reem Yassawi.

January 23 2024: Jakub Konieczny Arithmetical subword complexity of automatic sequences

slides

It is well-known that the subword complexity of an automatic sequence grows at most linearly, meaning that the number of length-$\ell$ subwords which appear in a given automatic sequence $a = (a(n))_n$ is at most $C \ell$ for a constant $C$ dependent only on $a$. In contrast, arithmetic subword complexity measures the number of subwords which appear along arithmetic progressions, and can grow exponentially even for very simple automatic sequences. Indeed, the classical Thue-Morse sequence has arithmetic subword complexity $2^{\ell}$, which is the maximal possible complexity for $\{0,1\}$-valued sequence.

Together with Jakub Byszewski and Clemens Müllner we obtained a decomposition result which allows us to express any (complex-valued) automatic sequence as the sum of a structured part, which is easy to work with, and a part which is pseudorandom or uniform from the point of view of higher order Fourier analysis. We now apply these techniques to the study of arithmetic subword complexity of automatic sequences. We show that for each automatic sequence $a$ there exists a parameter $r$ — which we dub “effective alphabet size” — such that the arithmetic subword complexity of $a$ is at least $r^{\ell}$ and at most $(r+o(1))^{\ell}$.

This talk is based on joint work with Jakub Byszewski and Clemens Müllner, and is closely related to the previous talk of Clemens Müllner at One World Combinatorics on Words Seminar.

January 9 2024: Clemens Müllner Synchronizing automatic sequences along Piatetski-Shapiro sequences

slides

Automatic sequences - that is, sequences computable by finite automata - have long been studied from the point of view of combinatorics on words. A notable property of these sequences is that their subword-complexity is at most linear. Avgustinovich, Fon-Der-Flaass and Frid introduced the notion of arithmetic subword-complexity - that is the number of different subwords of length $n$ that appear along some arithmetic progression. They also showed that a special class of synchronizing automatic sequences have at most linear arithmetic subword-complexity and some other class of automatic sequences on the alphabet $\Sigma$ have maximal possible subword-complexity $|\Sigma|^n$.

Synchronizing automatic sequences can be efficiently approximated using periodic functions and are usually more structured than general automatic sequences. We discuss a recent result showing that the arithmetic (and even polynomial) subword-complexity of synchronizing automatic sequences grows subexponentially. This was a key result to show that the subword-complexity of synchronizing automatic sequences along regularly growing sequences (such as Piatetski-Shapiro sequences) grows subexponentially, which is in stark contrast to other automatic sequences such as the Thue-Morse sequence. Moreover, this was a key ingredient to obtain rather precise estimates for the arithmetic (and polynomial) subword-complexity of general automatic sequences.

This is joint work with Jean-Marc Deshouillers, Michael Drmota, Andrei Shubin and Lukas Spiegelhofer.

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.