Here are the talks of One World Combinatorics on Words Seminar dated 2021.
20 December 2021: Jakub Konieczny Finitely-valued generalised polynomials
Generalised polynomials are expressions constructed from polynomials with the use of the floor function, addition and multiplication, such as $\lfloor \sqrt{2} n \lfloor \sqrt{3} n^2\rfloor + \sqrt{6} + \frac{1}{2}\rfloor$. Despite superficial similarity, generalised polynomials exhibit many phenomena which are impossible for ordinary polynomials. In particular, there exist generalised polynomial sequences which take only finitely many values but are not constant. This is the case, for instance, for Sturmian sequences.
In my talk, I will discuss finitely-valued generalised polynomial sequences from the perspective of combinatorics on words. The talk will include a survey of existing results on generalised polynomials, adapted to the current context, as well as several new results obtained in joint works with Boris Adamczewski and with Jakub Byszewski.
6 December 2021: Gabriele Fici Some Remarks on Automatic Sequences, Toeplitz words and Perfect Shuffling
One of the many nice properties of the Thue-Morse sequence $t = 0110100110010110\cdots$ is that t is equal to the perfect shuffling of itself with its binary complement $(1-t)$, i.e., it can be defined by means of the equation $t = t ⧢ (1 − t)$. In general, for any automatic sequence $w$, there exist two automatic sequences $w'$ and $w’’$ such that $w = w' ⧢ w''$. We call the sequences $w’$ and $w’’$ the even and the odd part of $w$, respectively. We will exhibit some curious facts about this decomposition for some (more or less) known 2- and 3-automatic sequences.
22 November 2021: Day of short talks.
- 15:00 Gregory Kucherov Minimizers and one question about de Bruijn graphs
- 15:30 Jeffrey O. Shallit Abelian cubes and additive cubes in the Tribonacci word
- 15:45 Jarosław Grytczuk Twins in permutations
A pair of disjoint subsequences in a permutation having the same relative order is called twins. How long twins must occur in every permutation of length n? The shape of a sequence of distinct integers is a binary sequence of signs of differences of consecutive terms of the sequence. A pair of disjoint subsequences in a permutation having the same shape is called weak twins. How long weak twins must occur in every permutation of length n? I will present some results and conjectures concerning the above questions.
- 16:15 Daniel Gabric Words that almost commute
The Hamming distance $\text{ham}(u,v)$ between two equal-length words $u$, $v$ is the number of positions where $u$ and $v$ differ. The words $u$ and $v$ are said to be conjugates if there exist non-empty words $x,y$ such that $u=xy$ and $v=yx$. The smallest value $\text{ham}(xy,yx)$ can take on is $0$, when $x$ and $y$ commute. But, interestingly, the next smallest value $\text{ham}(xy,yx)$ can take on is $2$ and not $1$. We provide an efficient formula to count the number $h(n)$ of length-$n$ words $u=xy$ over a $k$-letter alphabet that have a conjugate $v=yx$ such that $\text{ham}(xy,yx)=2$. We also provide efficient formulae for other quantities closely related to $h(n)$. Finally, we give some results on the asymptotic behaviour of $h(n)$.
8 November 2021: Dan Rust Random substitutions
A random substitution is a generalisation of a substitution on a finite alphabet. Whereas with classical substitutions, letters have a single word as an image, random substitutions have a finite set of possible image words that are independently chosen each time it is applied to the letters in a word. As an example, the `random Fibonacci substitution' is given by
$$ a \mapsto \{ab,ba\}, b \mapsto \{a\}.$$
This gives rise to languages of legal words that share similar properties with substitutive words (i.e., hierarchical structures) but which also have exponential complexity functions (entropy). I will give an overview of this rarely explored class of systems, some of the aspects that have recently been studied, and some easy-to-state open problems.
25 October 2021: Fabien Durand Beyond substitutive sequences : Self-induced dynamical systems and sequences on compact alphabets
It is well-known that primitive substitutions are recognizable. This property implies that the minimal substitution subshifts $(X,S)$ are self-induced. That is, there exists a clopen set $U$ included in $X$ such that $(U,S_U)$ is isomorphic to $(X,S)$, where $S_U (x)=S^n (x)$ and $n>0$ is the first iterate coming back to $U$.
We will see that all dynamical systems are self-induced in a measurable perspective.
But from a topological point of view self induction characterizes minimal substitution subshifts on possibly infinite alphabets (even uncountable).
11 October 2021: France Gheeraert $S$-adic characterization of dendric languages: ternary case
Uniformly recurrent dendric languages generalize Arnoux-Rauzy languages and interval exchanges and are defined via the left-, right- and biextensions of their words. In a series of articles, Berthé et al. introduced them and, among other results, proved that this family is stable under derivation, which leads to the existence of particular $S$-adic representations.
In this talk, we will see how we can use the properties of these representations to obtain an $S$-adic characterization of uniformly recurrent dendric languages. We give some general results then focus on the case of a ternary alphabet to obtain a simpler characterization.
This is a joint work with Marie Lejeune and Julien Leroy.
27 September 2021: Arseny Shur Abelian repetition threshold revisited
Abelian repetition threshold ART$(k)$ is the number separating fractional Abelian powers which are avoidable and unavoidable over the $k$-letter alphabet. In contrast with the «usual» repetition threshold RT$(k)$, no exact values of ART$(k)$ are known. The lower bounds were proved in [A.V. Samsonov, A.M. Shur. On Abelian repetition threshold. RAIRO ITA, 2012] and conjectured to be tight. We present a method of study of Abelian power-free languages using random walks in prefix trees and some experimental results obtained by this method. On the base of these results, we conjecture that the lower bounds for ART$(k)$ by Samsonov and Shur are not tight for all $k$ except for $k=5$ and prove this conjecture for $k=6,7,8,9,10$. Namely, we show that ART$(k)>(k-2)(k-3)$ in all these cases.
26 July 2021: Jason Bell Lie complexity of words
Given a right-infinite word $\bf{w}$ over a finite alphabet, we introduce a new complexity function $L_{\bf w}(n)$, motivated by the theory of Lie algebras, whose value at $n$ is the number of equivalence classes of factors $x$ of ${\bf w}$ of length $n$ with the property that every cyclic permutation of $x$ is again a factor of ${\bf w}$, where two words $x$ and $y$ are equivalent if there exist words $a$ and $b$ such that $x=ab$ and $y=ba$. We show that the Lie complexity function is uniformly bounded for words ${\bf w}$ of linear factor complexity and that it is a $k$-automatic sequence when ${\bf w}$ is $k$-automatic. As a consequence of these results we can show that if ${\bf w}$ is a word of linear factor complexity then there are only finitely many primitive factors $v$ of ${\bf w}$ with the property that $v^n$ is a factor of ${\bf w}$ for every $n\ge 1$. We also consider extensions of these results. This is joint work with Jeffrey Shallit.
12 July 2021: Štěpán Holub Using Isabelle/HOL in Combinatorics on Words research
In this talk I will introduce a (growing) library of results in Combinatorics on Words formalized in the proof assistant Isabelle/HOL. I will emphasize the practical use of this library by a beginner, rather than theoretical aspects of either the proof assistant or the formalized results. The participants are therefore strongly encouraged to try Isabelle along with me during my talk, which requires to have Isabelle installed, as well as the draft version of our formalization downloaded. Questions stemming from your own attempts are most welcome, independently of how naïve they may seem.
For an installation guide, visit https://gitlab.com/formalcow/combinatorics-on-words-formalized#a-short-guide-for-isabellehol-beginners-how-to-formalize-your-combinatorics-on-words-result Everything should be straightforward. If you encounter any problem, you can write me to holub@karlin.mff.cuni.cz. Issues with the installation can be also addressed during the preliminary technical session: I will be available 20 minutes before the official start.
28 June 2021: Florin Manea Combinatorial algorithms for subsequences
In this talk, we will cover a series of recent algorithmic results related to the processing of subsequences occurring in words. Firstly, we will show how to test in linear time whether two given words have exactly the same set of subsequences of length $k$ (or, in other words, whether they are $k$-equivalent w.r.t. the Simon congruence), where $k$ is a positive integer also given as input. Secondly, we show how to compute in linear time, for two given words, which is the largest positive integer $k$ for which the two words are $k$-Simon-congruent. We will conclude this talk with a series of related results. On the one hand, we consider the problem of transforming words by edit operations so that they become Simon-congruent and, on the other hand, we consider the notion of absent subsequences in words and problems related to this.
21 June 2021: Day of short talks
As usual, the event will consist of short talks in 25-minute slots. Speakers:
- 15:00 Jakub Byszewski Automata and finite order automorphisms of the power series ring
- 15:30 Jarosław Duda Generalized Fibonacci coding problem using Maximal Entropy Random Walk and Asymmetric Numeral Systems
- 16:00 Jarkko Peltomäki Initial nonrepetitive complexity of regular episturmian words and their Diophantine exponents
- 16:30 Palak Pandoh Counting scattered palindromes in a finite word
- 17:00 Clément Lagisquet (LAMA) On Markov Numbers: An answer to three conjectures from Aigner
- 17:30 Bartłomiej Pawlik Nonchalant procedure
You can find the abstracts, the slides and the videos at the event page.
14 June 2021: Golnaz Badkobeh Left Lyndon tree construction
We extend the left-to-right Lyndon factorisation of a word to the left Lyndon tree construction of a Lyndon word. It yields an algorithm to sort the prefixes of a Lyndon word according to the infinite ordering defined by Dolce et al. (2019). A straightforward variant computes the left Lyndon forest of a word. All algorithms run in linear time in the letter-comparison model.
7 June 2021: Pascal Ochem Avoiding large squares in trees and planar graphs
The Thue number $T(G)$ of a graph $G$ is the minimum number of colors needed to color $G$ without creating a square on a path of $G$. For a graph class $C$, $T(C)$ is the supremum of $T(G)$ over the graphs $G$ in $C$. The Thue number has been investigated for famous minor-closed classes: $T(tree) = 4$, $7 \leq T(outerplanar) \leq 12$, $11 \leq T(planar) \leq 768$. Following a suggestion of Grytczuk, we consider the generalised parameters $T_k(C)$ such that only squares of period at least $k$ must be avoided. Thus, $T(C) = T_1(C)$. We show that $T_2(tree) = 3$, $T_5(tree) = 2$, and $T_k(planar) \geq 11$ for every fixed $k$. This is a joint work with Daniel Gonçalves and Matthieu Rosenfeld.
31 May 2021: Etienne Moutot Recent advances around Nivat's conjecture
Nivat's conjecture states that any two dimensional word with “low enough” pattern complexity must be periodic. Even if the statement of the conjecture is quite simple and very similar to the one dimensional Morse-Hedlund theorem, the conjecture is still open since stated by Maurice Nivat in 1997. However, there have been a lot of progress towards a proof in the last five years, and many new tools started to emerge. In 2015, Cyr and Kra started to use tools from symbolic dynamics to improve the bound required to prove periodicity. At about the same time, Jarkko Kari and Michal Szabados started to develop an algebraic approach to tackle the conjecture, leading to very elegant proofs of new results related to Nivat's conjecture.
In this talk I will present the conjecture and some of the last results around it. I will then focus on the algebraic approach initiated by Kari and Szabados.
17 May 2021: Jeffrey Shallit The Walnut Tutorial: Using A Tool for Doing Combinatorics on Words
Walnut is free open-source software, written by Hamoon Mousavi, that can rigorously prove or disprove claims about automatic sequences (broadly understood), such as the Thue-Morse sequence, the Fibonacci infinite word, and others. It can also be used to create explicit formulas for various aspects of such sequences, such as subword complexity, palindrome complexity, and so forth.
In this talk I won't discuss how it works. Instead I'll give a tutorial, surveying the kinds of things you can and can't do with it. We'll “get our hands dirty” and solve problems in real time.
At the end, if there's time, I'll solicit problems about such sequences from the audience and try to solve them with Walnut. Come prepared with some conjecture you haven't been able to prove yet!
The tutorial lasts about 90 minutes.
10 May 2021: Kevin Buzzard Teaching computers to prove theorems
Over the last few years I have been teaching proofs of theorems to computers, and teaching students how to teach proofs of theorems to computers. The Kruskal Katona theorem is a theorem I learnt as an MSc student, and Cambridge PhD student Bhavik Mehta taught it to the Lean theorem prover here: https://b-mehta.github.io/combinatorics/ . Lean's maths library `mathlib` https://github.com/leanprover-community/mathlib is now half a million lines of theorem proofs, many of them proved by mathematicians who have picked up this language, and most of them learnt it like Bhavik, just choosing a project and working on it. I will talk about how I learnt Lean, how you can learn Lean, what the point of learning Lean is, what the point of teaching Lean is, and where all this stuff might end up going. Rest assured – I will not assume any prior familiarity with computer theorem provers in this talk!
3 May 2021: Gwenaël Richomme On sets of indefinitely desubstitutable words
The stable set associated to a given set $S$ of nonerasing endomorphisms or substitutions is the set of all right infinite words that can be indefinitely desubstituted over $S$. This notion generalizes the notion of sets of fixed points of morphisms. It is linked to $S$-adicity and to property preserving morphisms. Two main questions are considered. Which known sets of infinite words are stable sets? Which ones are stable sets of a finite set of substitutions? While bringing answers to the previous questions, some new way of characterizing several well-known sets of words such as the set of binary balanced words or the set of episturmian words are presented. A characterization of the set of nonerasing endomorphisms that preserve episturmian words is also provided.
26 April 2021: Luca Zamboni Singular words
The extremal solutions to certain problems in the theory of finite continued fractions are characterised by a special combinatorial property which we call the singular property. This property may be interpreted in the framework of finite words, cyclic words, and one and two-sided infinite words over arbitrary ordered alphabets. Each linear (resp. cyclic) word w is Abelian equivalent to a singular linear (resp. cyclic) word w’ which is in general unique up to reversal. We develop an algorithm for generating all singular words having a prescribed Parikh vector which is based in part on a non-commutative variant of the usual Euclidean algorithm. This allows us to answer a question of G. Ramharter from 1983 on the extremal values of the regular and semi-regular cyclic continuants introduced by Motzkin and Straus in the 1950’s. We also confirm a conjecture of Ramharter in certain instances and exhibit counter examples in other cases. As for infinite words, the singular property in the context of bi-infinite binary words coincides with the Markoff property which was shown by C. Reutenauer to be equivalent to the balance property. We generalise this to higher alphabets by showing that the singular property is the fundamental property which characterises the language structure of codings of symmetric k-interval exchange transformations. This is based on a collaboration with Alessandro De Luca and Marcia Edson initiated during the first Covid lockdown of 2020.
12 April 2021: Valérie Goyheneche Eigenvalues and constant arithmetical progressions for substitutive sequences
The main subject of this talk is to answer the following decidability question : does a substitutive sequence $x$ admit a constant arithmetical progression $ (x_{k+np})_n $?
Our method mainly relies on the link between constant arithmetical subsequences and (dynamical) eigenvalues of the underlying dynamical system. We will explain a method to compute the set of (additive) eigenvalues associated to such systems. We can then deduce, given an integer $p$, if the sequence $x$ contains a constant arithmetical progression with period $p$. At the end of the talk, we will focus on the case of primitive constant-length substitutions, for which the set of such periods can be described by an automaton.
29 March 2021: Jacques Sakarovitch, RIF, CNRS / Univ. de Paris and Télécom Paris, IPP From Fibonacci to golden mean representations
The video will not be distributed, but we hope to get the slides later.
Every positive integer can be written as a sum of Fibonacci numbers; this yields a Fibonacci representation of the integer. A positive integer can also be written as a (finite) sum of (positive and negative) powers of the golden mean; this yields a golden mean representation of the integer, with the radix point roughly in the middle of the writing. It is the golden mean expansion when it contains no consecutive digits equal to 1.
We show that there exists a letter-to-letter finite two-tape automaton that maps the Fibonacci representation of any positive integer onto its golden mean expansion, provided the latter is folded around the radix point. As a corollary, the set of golden mean expansions of the positive integers is a linear context-free language.
These results are generalised to the more general case of integer representations in numeration systems built upon quadratic Pisot units.
Joint work with Christiane Frougny, published in 1999 in the Journal of Algebra and Computation. This talk is a follow-up to the one of October 15 by Michel Dekking, who kindly quoted this paper but deemed it hard to understand.
22 March 2021: Day of Short Talks
This second event also consisted of short talks in 25-minute slots.
- 15:00 Jane D. Palacio Coverable bi-infinite substitution shifts
- 15:30 Ibai Aedo On long arithmetic progressions in binary Morse-like words
- 16:00 Francesco Dolce On morphisms preserving palindromic richness
- 16:30 Jeffrey Shallit Robbins and Ardila meet Berstel
- 17:00 Anna E. Frid The semigroup of trimmed morphisms
See the event page for the abstracts; slides and videos of talks.
15 March 2021: Szymon Stankiewicz Square-free reducts of words
We discuss a joint work with Jarosław Grytczuk (https://arxiv.org/abs/2011.12822) about square-free reducts of words.
In any finite word one may delete the repeated block of a square, obtaining thereby a shorter word. By repeating this process, a square-free word is eventually reached, which we call a reduct of the original word.
We will show that for each positive integer $n$ there is a word over ternary alphabet which can be reduced to at least $n$ different words and also that there is a word over alphabet of size four which has exactly $n$ reducts. We will also show that there exists infinitely many ternary words having exponential many reducts in the length of these words.
For a fixed alphabet one can create a poset with nodes being words and $u > v$ iff word $u$ can be reduced to word $v$. We will describe some properties of those posets.
1 March 2021: Mickaël Postic Open and closed complexity functions of infinite words
Closed words, also known as complete first returns, have been studied for a long time, and play an important role in symbolic dynamics. A word which is not closed is said to be open. In this talk based on a joint work with Olga Parshina, I will present a characterization of aperiodic words in terms of their open complexity function and closed complexity function, in the spirit of Morse and Hedlund's theorem. The preprint is available at https://arxiv.org/pdf/2005.06254.pdf
22 February 2021: Day of Short Talks
This mini-event is designed to take the place of a small and very informal conference in our field, since many of us miss direct communication of this kind.
The event consisted of short talks in 25-minute slots. Speakers:
- 15:00 Christophe Reutenauer An arithmetical characterization of Christoffel words
- 15:30 Célia Cisternino Two applications of the composition of a $2$-tape automaton and a weighted automaton
- 16:00 Lubka Dvořáková On balanced sequences with the minimal asymptotic critical exponent
- 16:30 Štěpán Holub Formalization of Combinatorics on Words in Isabelle/HOL
- 17:00 Florin Manea Efficiently Testing Simon's Congruence
- 17:30 Mélodie Andrieu A Rauzy fractal unbounded in all directions of the plane
For the abstracts, slides and videos of the talks, see the event page.
15 February 2021: Petr Ambrož Morphisms generating antipalindromic words
We introduce two classes of morphisms over the alphabet $A=\{0,1\}$ whose fixed points contain infinitely many antipalindromic factors. An antipalindrome is a finite word invariant under the action of the antimorphism $E:\{0,1\}^*\to\{0,1\}^*$, defined by $E(w_1\cdots w_n)=(1-w_n)\cdots(1-w_1)$. We conjecture that these two classes contain all morphisms (up to conjugation) which generate infinite words with infinitely many antipalindromes. This is an analogue to the famous HKS conjecture concerning infinite words containing infinitely many palindromes. We prove our conjecture for two special classes of morphisms, namely (i) uniform morphisms and (ii) morphisms with fixed points containing also infinitely many palindromes.
8 February 2021: Robert Mercas (Trying to do a) Counting of distinct repetitions in words
The topic of counting the distinct repetitions that a word contains has been around for at least two decades. The problem of counting distinct squares in a word was introduced by Fraenkel and Simpson in ’98, who also showed that their number is upper bounded by twice the length of the word. However, their conjecture that the factor of 2 is superfluous (the length of the word is a strict bound) is still open (though there exist several improvements of their original result). Moreover, recently Manea and Seki showed that proving the bound for binary words is enough. Moreover, further work was done on counting distinct repetitions of higher exponent with quite sharp bounds. By looking at non-extendable repetitions of power at least two (thus considering fractional ones as well) Kolpakov and Kucherov tried to bound in ‘99 the number of runs in a word (non-necessarily distinct). This was recently shown to be less than the length $n$ of the word that we consider and more than 0.9482 times $n$. However, all of these ideas have a common sticking point, namely the three squares lemma of Crochemore and Rytter, which they all use as main tool. In this talk I will present a different technique (which so far is not fully exploited) of trying to count distinct squares and show some surprising connections between all of the above notions.
1 February 2021: Jean-Paul Allouche Hidden automatic sequences
We discuss a joint work with Michel Dekking and Martine Queffélec (https://arxiv.org/abs/2010.00920) about sequences given as fixed points of non-uniform morphisms that happen to be actually automatic.
One of the most ancien example is probably the one due to Berstel, who proved that the Istrail squarefree sequence defined as the fixed point of the morphism $f$ with $f(0) = 12$, $f(1) = 102$, $f(2) = 0$ is also $2$-automatic.
After revisiting an old criterion due to M. Dekking at the end of the 70's, we give several examples (in particular of sequences in the OEIS). Finally we focus on morphisms associated with Grigorchuk(-like) groups.
4 January 2021: Anna Frid Is not prefix palindromic length of a $k$-automatic word $k$-regular?
We consider the function of the prefix palindromic length for $k$-automatic words and prove that it is $k$-regular for such words containing a finite number of distinct palindromes, like for example the paperfolding word. We also observe that in the opposite case, if the number of distinct palindromes is infinite, this function can be $k$-regular, as for the Thue-Morse word, or seemingly not, as for the period-doubling word. The fact of non-regularity, however, stays unproven.
This is a joint work with Enzo Laborde and Jarkko Peltomäki. The preprint is available at https://arxiv.org/abs/2009.02934.