We show how to construct 'simple' symbolic dynamical systems in terms of renormalisation schemes associated with multidimensional continued fractions. Continued fractions are used here to generate infinite words thanks to the iteration of infinite sequences of substitutions. Simple means that these symbolic systems have a linear number of factors of a given length, or that they have pure discrete spectrum, or else, that they have a low symbolic discrepancy. We also discuss the relation between these notions.[-]

We consider the assignment (or bipartite matching) problem between $n$ source points and $n$ target points on the real line, where the assignment cost is a concave power of the distance, i.e. |x − y|p, for 0 < p < 1. It is known that, differently from the convex case (p > 1) where the solution is rigid, i.e. it does not depend on p, in the concave case it may varies with p and exhibit interesting long-range connections, making it more appropriate to model realistic situations, e.g. in economics and biology. In the random version of the problem, the points are samples of i.i.d. random variables, and one is interested in typical properties as the sample size n grows. Barthe and Bordenave in 2013 proved asymptotic upper and lower bounds in the range 0 < p < 1/2, which they conjectured to be sharp. Bobkov and Ledoux, in 2020, using optimal transport and Fourier-analytic tools, determined explicit upper bounds for the average assignment cost in the full range 0 < p < 1, naturally yielding to the conjecture that a “phase transition” occurs at p = 1/2. We settle affirmatively both conjectures. The novel mathematical tool that we develop, and may be of independent interest, is a formulation of Kantorovich problem based on Young integration theory, where the difference between two measures is replaced by the weak derivative of a function with finite q-variation.
Joint work with M. Goldman (arXiv:2305.09234).[-]

Wang's tiles were introduced in the 1960s and have been an inexhaustible source of undecidable problems ever since. They are unit square tiles with colored edges and fixed orientation, which can be placed together provided they share the same color on their common edge. Many decision problems involving Wang tiles follow the same global structure: given a finite set of Wang tiles, is there an algorithm to determine if they tile a particular shape or subset of the infinite grid? If we look for a tiling of the whole grid, this is the domino problem which is known to be undecidable for Z2 and many other groups. In this talk we focus on infinite snake tilings. Originally the infinite snake problem asks is there exists a tiling of a self-avoiding bi-infinite path on the grid Z2. In this talk I present how to expand the scope of domino snake problems to finitely generated groups to understand how the underlying structure affects computability. This is joint work with Nicolás Bitar.[-]

String attractor, a relatively new combinatorial notion, is closely related to measuring the complexity of words and offers a unified approach to the repetitiveness measures induced by dictionary compressors. However, attractors have been only little studied in the context of combinatorics on words, particularly for classes of low complexity, including complementary-symmetric Rote sequences. In this talk, we work with pseudopalindromic closures as a useful way to generate these sequences, and then show the form of minimal attractors of their pseudopalindromic prefixes.[-]

Starting from a presentation of the many recent applications of Galois theory of functional equations to enumerative combinatorics, we will introduce the Galois theory of (different kinds) of difference equations. We will focus on the point of view of the applications, hence with little emphasis on the technicalities of the domain, but I'm willing to do an hour of « exercises » (i.e. to go a little deeper into the proofs), if a part of the audience is interested.[-]

D-finite functions play a prominent role in computer algebra because they are well suited for representation in a symbolic software system, and because they include many functions of interest, such as special functions, orthogonal polynomials, generating functions from combinatorics, etc. Whenever one wishes to study the integral or the sum of a D-finite function, the method of creative telescoping may be applied. This method has been systematically introduced by Zeilberger in the 1990s, and since then has found applications in various different domains. In this lecture, we explain the underlying theory, review some of the history and talk about some recent developments in this area.[-]

For every positive integer $n$, we introduce a set $\mathcal{T}_n$ made of $(n+3)^2$ Wang tiles (unit squares with labeled edges). We represent a tiling by translates of these tiles as a configuration $\mathbb{Z}^2 \rightarrow \mathcal{T}_n$. A configuration is valid if the common edge of adjacent tiles has the same label. For every $n \geqslant 1$, we consider the Wang shift $\Omega_n$ defined as the set of valid configurations over the tiles $\mathcal{T}_n$. The family $\left\{\Omega_n\right\}_{n \geqslant 1}$ broadens the relation between quadratic integers and aperiodic tilings beyond the omnipresent golden ratio as the dynamics of $\Omega_n$ involves the positive root $\beta$ of the polynomial $x^2-n x-1$. This root is sometimes called the $n$-th metallic mean, and in particular, the golden mean when $n=1$ and the silver mean when $n=2$. The family gathers the hallmarks of other small aperiodic sets of Wang tiles. When $n=1$, the set of Wang tiles $\mathcal{T}_1$ is equivalent to the Ammann aperiodic set of 16 Wang tiles. The tiles in $\mathcal{T}_n$ satisfy additive versions of equations verified by the Kari-Culik aperiodic sets of 14 and 13 Wang tiles. Also configurations in $\Omega_n$ are the codings of a $\mathbb{Z}^2$-action on a 2-dimensional torus by a polygonal partition like the Jeandel-Rao aperiodic set of 11 Wang tiles. The tiles can be defined as the different instances of a square shape computer chip whose inputs and outputs are 3-dimensional integer vectors. There is an almost one-to-one factor map $\Omega_n \rightarrow \mathbb{T}^2$ which commutes the shift action on $\Omega_n$ with horizontal and vertical translations by $\beta$ on $\mathbb{T}^2$. The factor map can be explicitely defined by the average of the top labels from the same row of tiles as in Kari and Culik examples. We also show that $\Omega_n$ is self-similar, aperiodic and minimal for the shift action. Also, there exists a polygonal partition of $\mathbb{T}^2$ which we show is a Markov partition for the toral $\mathbb{Z}^2$-action. The partition and the sets of Wang tiles are symmetric which makes them, like Penrose tilings, worthy of investigation. Details can be found in the preprints available at https://arxiv.org/abs/ 2312.03652 (part I) and https://arxiv.org/abs/2403. 03197 (part II). The talk will present an overview of the main results.[-]