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 6 2024: Eric Rowland Algebraic power series and their automatic complexity

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.

February 20 2024: Christopher Cabezas

March 5 2024: Finn Lidbetter

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

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.