The goal of the covering lemma is perhaps opposite to that of the packing lemma because it applies to a setting in which one party wishes to make messages indistinguishable to another party (instead of trying to make them distinguishable, as in the packing lemma of the previous chapter). That is, the covering lemma is helpful when one party is trying to simulate a noisy channel to another party, rather than trying to simulate a noiseless channel. One party can accomplish this task by randomly “covering” the Hilbert space of the other party (this viewpoint gives the covering lemma its name).

One can certainly simulate noise by choosing a quantum state uniformly at random from a large set of quantum states and passing along the chosen quantum state to a third party without indicating which state was chosen. But the problem with this approach is that it could potentially be expensive if the set from which we choose a random state is large, and we would really like to use as few resources as possible in order to simulate noise. That is, we would like the set from which we choose a quantum state uniformly at random to be as small as possible when simulating noise. The covering lemma is similar to the packing lemma in the sense that its conditions for application are general (involving bounds on projectors and an ensemble), and it gives an effective scheme for simulating noise when we apply it in an i.i.d. setting.

One application of the covering lemma in quantum Shannon theory is in the construction of a code for transmitting private classical information over a quantum channel (discussed in Chapter 23). The method of proof for private classical transmission involves a clever combination of packing messages so that Bob can distinguish them, while covering Eve's space in such a way that Eve cannot distinguish the messages intended for Bob. A few other applications of the covering lemma are in secret key distillation, determining the amount of noise needed to destroy correlations in a bipartite state, and compressing the outcomes of an i.i.d. measurement on an i.i.d. quantum state.

This chapter marks the beginning of our study of the asymptotic theory of quantum information, where we develop the technical tools underpinning this theory. The intuition for it is similar to the intuition we developed in the previous chapter on typical sequences, but we will find some important differences between the classical and quantum cases.

So far, there is not a single known information-processing task in quantum Shannon theory where the tools from this chapter are not helpful in proving the achievability part of a coding theorem. For the most part, we can straightforwardly import many of the ideas from the previous chapter about typical sequences for use in the asymptotic theory of quantum information. However, one might initially think that there are some obstacles to doing so. For example, what is the analogy of a quantum information source? Once we have established this notion, how would we determine if a state emitted from a quantum information source is a typical state? In the classical case, a simple way of determining typicality is to inspect all of the bits in the sequence. But there is a problem with this approach in the quantum domain—“looking at quantum bits” is equivalent to performing a measurement and doing so destroys delicate superpositions that we would want to preserve in any subsequent quantum information-processing task.

So how can we get around the aforementioned problem and construct a useful notion of quantum typicality? Well, we should not be so destructive in determining the answer to a question when it has only two possible answers. After all, we are only asking “Is the state typical or not?”, and we can be a bit more delicate in the way that we ask this question. As an analogy, suppose Bob is curious to determine whether Alice could join him for dinner at a nice restaurant on the beach. He would likely just phone her and politely ask, “Sweet Alice, are you available for a lovely oceanside dinner?”, as opposed to barging into her apartment, probing through all of her belongings in search of her calendar, and demanding that she join him if she is available.

Redundancy: a versatile notion

The notion of redundancies in texts, regarded as sequences of symbols, appear under various concepts in the literature of combinatorics on words and of algorithms on strings: repetitions, repeats, runs, covers, seeds and palindromes, for example. Fundamental elements along these concepts are spread in books by Lothaire (1997, 2002, 2005). This has been also illustrated in Chapter 4.

Squares and cubes (concatenations of 2 or 3 copies of the same non-empty word) are instances of repetitions whose exponent is at least 2 and have been studied for more than a century after the seminal work of Thue (1906b) who described infinite words containing none of them.

Repeats refer to less repetitive segments in text, that is, those segments having a rational exponent smaller than 2 (but larger than 1). The frontier between repetitions and repeats is indeed rather blurred in literature. The famous conjecture of Dejean (1972) refers mainly to repeats and provides the repetitive threshold of each alphabet size: it is the minimum of maximal exponents of factors occurring in infinite words drawn from the alphabet (also see Section 4.3). After several partial results, including the result of Dejean on the 3-letter alphabet, the conjecture has eventually been solved recently see (Carpi, 2007), (Rao, 2011) and (Currie and Rampersad, 2011). Also see Section 4.3.

Further works show that maximal-exponent repeats or repetitions occurring in infinite words complying with the threshold can also have a bounded length (Shallit, 2004). Their minimal number is known for alphabets of size 2 and 3 (Badkobeh, 2011; Badkobeh and Crochemore, 2010), introducing the notion of finite-repetition threshold attached to each alphabet size. The latter threshold is proved to be Dejean's threshold for larger alphabet sizes and the minimum number of Dejean's factors is studied in (Badkobeh et al., 2014).

The design of methods for computing all the occurrences of repetitions in a word has lead to several optimal algorithms by Crochemore (1981), by Apostolico and Preparata (1983) and by Main and Lorentz (1984), all running in O(nlogn) time on a word of length n. They have been extended to algorithms producing certain types of repetitions with rational exponent by Main (1989), or a unique occurrence for each repetition by Gusfield and Stoye (2004). These latter variants run in O(nloga) time on an alphabet of size a.

Introduction

The notions of synchronising word and synchronised automaton are simple to define and occur in many applications of automata. A synchronising word maps every state of an automaton to the same state. It is remarkable that this simple notion is linked with difficult combinatorial problems.

Some of them, like the Černý Conjecture, have been open for a long time. This conjecture asserts that a synchronised deterministic automaton with n states has a synchronising word of length at most (n−1)2.

Another longstanding open problem, the Road Colouring Problem, was solved by Trahtman in 2009. The problem asks whether any complete deterministic automaton has the same graph as a synchronised automaton. The choice of the labels of the edges defines a colouring to which the term Road Colouring Problem refers.

A reason to explain the difficulty of these questions may be the fact that there is no simple description of the class of automata that are not synchronised. It is relatively simple to verify whether an automaton is synchronised since it can be checked with a polynomial algorithm. On the contrary, it was proved by Eppstein (1990) that finding a synchronising word of minimal length is NP-hard.

Recently, some results have been obtained on the synchronising properties of random automata showing that a random automaton is synchronised with high probability (see Berlinkov (2013), Nicaud (2014)).

In this chapter, we present a survey of results concerning synchronised automata. We first define the notions of synchronising words and synchronised automata for deterministic automata. We extend these notions to the more general class of unambiguous automata.

In Section 7.3, we present Černý's conjecture and discuss several particular cases where a positive answer is known. This includes the important case of aperiodic automata solved by Trahtman (2007).We also describe the case of circular automata Dubuc (1998), the case of one-cluster automata introduced by Béal et al. (2011), and more generally the strongly transitive automata of Carpi and D'Alessandro (2013).

In Section 7.4, we present the Road Colouring Theorem (i.e., the solution of Trahtman to the Road Colouring Problem). We present here Trahtman's cubic-time algorithm. A quadratic-time algorithmis given in Béal and Perrin (2014).

Introduction

A measure of randomness on the unit interval ℐ := [0,1] tests how a sequence X ⊂ℐ differs from a ‘truly random’ sequence. See books (Drmota and Tichy, 1997; Kuipers and Niederreiter, 1974) for a general discussion on the subject. Such a measure describes the difference between the behaviour of the truncated sequence X⟨T⟩ formed with the first T terms of the sequence and a ‘truly random’ sequence formed with T elements of ℐ, and explains what happens when the truncation T becomes large.

Here, we focus on the case of the Kronecker sequence K (α), formed of the fractional parts of the multiples of a real α. The three-distance theorem states that there are at most three possible distinct distances between geometric consecutive points in the truncated sequence K⟨T⟩(α). For some values of T, only two distances occur (we refer to this situation as the two-distance phenomenon below). The length and the exact number of these distinct distances depend on the continued fraction expansion of the real α. Such a sequence K(α) is thus very particular, and is surely not pseudo-random at all. On the other hand, it can be precisely studied since its main parameters are expressed as a function of the continued fraction expansion of the real α. This explains why there are many existing works that deal with various randomness measures of the Kronecker sequence, notably the discrepancy. However, they all adopt an ‘individual’ point of view: for which reals α, and for which integers T, the discrepancy of the sequence K (α) is minimal, maximal?

Our points of view

Here, we adopt different points of view, which appear to be new.

1. (1) We focus on the special case when the truncation T gives rise to the two-distance phenomenon: the computations are easier, but already show very interesting phenomena. In particular, we introduce two different types of truncation (see Section 11.2.2), which depend on the position μ ∈ [0,1] of the truncation: the boundary positions which correspond to μ = 0 or μ = 1, and the generic positions, with μ ∈]0,1[and we describe how they lead to different probabilistic behaviours.

2. […]

Introduction

The topic of this chapter is the study of avoidable repetitions in words (finite or infinite sequences). The study of regularities in mathematical structures is a basic one in mathematics. The area of Ramsey theory is devoted to the study of unavoidable regularities in mathematical structures. Here we are principally concerned with the study of certain kinds of avoidable regularities in words. In particular, we are interested in the question, ‘What kinds of repetitions can be avoided by infinite words?’ The first work relating to this question dates back at least to the beginning of the twentieth century and the work of Thue (1906a, 1912) on repetitions in words. Thue's results were independently rediscovered from time to time in the first half of the twentieth century; however, a systematic study of what is now known as combinatorics on words was not initiated until perhaps the late 1970s or early 1980s.

The study of repetitions in words has as its principal motivation nothing other than its inherent mathematical appeal (indeed, this was Thue's reason for studying it). Nevertheless, the study of repetitions in words has several applications, the most famous of which is perhaps the work of Novikov and Adian (1968) in solving the Burnside problem for groups. Other applications have been found in cryptography and bioinformatics, such as discussed in Section 5.6 and also in Section 6.2.4. Recently, combinatorial results regarding repetitions in words have been used to prove deep results in transcendental number theory. A survey of these recent developments has been given by Adamczewski and Bugeaud (2010). Note that repetitions are also the main object of study of the next chapter (Chapter 5) where detection algorithms are also provided.

Avoidability

The notions of alphabet, letter, finite or infinite word, factor, prefix, suffix and morphism have been defined in Section 1.2.We recall in particular that the Thue–Morse morphism μ : {0,1}∗→{0,1}∗ is defined by

Frequently we shall deduce the existence of an infinite word with a certain property from the existence of arbitrarily large finite words with the desired property. To pass from the finite to the infinite, we shall often rely (implicitly) on the following form of König's infinity lemma.

Inspired by the celebrated Lothaire series (Lothaire, 1983, 2002, 2005) and animated by the same spirit as in the book (Berthé and Rigo, 2010), this collaborative volume aims at presenting and developing recent trends in combinatorics with applications in the study of words and in symbolic dynamics.

On the one hand, some of the newest results in these areas have been selected for this volume and here benefit from a synthetic exposition. On the other hand, emphasis on the connections existing between the main topics of the book is sought. These connections arise, for instance, from numeration systems that can be associated with algorithms or dynamical systems and their corresponding expansions, from cellular automata and the computation or the realisation of a given entropy, or even from the study of friezes or from the analysis of algorithms.

This book is primarily intended for graduate students or research mathematicians and computer scientists interested in combinatorics on words, pattern avoidance, graph theory, quivers and frieze patterns, automata theory and synchronised words, tilings and theory of computation, multidimensional subshifts, discrete dynamical systems, ergodic theory and transfer operators, numeration systems, dynamical arithmetics, analytic combinatorics, continued fractions, probabilistic models. We hope that some of the chapters can serve as usefulmaterial for lecturing at master/graduate level. Some chapters of the book can also be interesting to biologists and researchers interested in text algorithms or bio-informatics.

Let us succinctly sketch the general landscape of the volume. Short abstracts of each chapter can be found below. The book can roughly be divided into four general blocks. The first one, made of Chapters 2 and 3, is devoted to numeration systems. The second block, made of Chapters 4 to 6, pertains to combinatorics of words. The third block is concernedwith symbolic dynamics: in the one-dimensional setting with Chapter 7, and in the multidimensional one, with Chapters 8 and 9. The last block, made of Chapters 10 and 11, has again a combinatorial nature.

Words, i.e., finite or infinite sequences of symbols taking values in a finite set, are ubiquitous in the sciences. It is because of their strong representation power: they arise as a natural way to code elements of an infinite set using finitely many symbols. So let us start our general description with combinatorics on words.

Cellular automata are discrete dynamical systems based on local, synchronous and parallel updates of symbols written on an infinite array of cells. Such systems were conceived in the early 1950s by John von Neumann and Stanislaw Ulam in the context of machine self-reproduction, while one-dimensional variants were studied independently in symbolic dynamics as block maps between sequences of symbols. In the early 1970s, John Conway introduced Game-Of-Life, a particularly attractive two-dimensional cellular automaton that became widely known, in particular once popularised by Martin Gardner in Scientific American. In physics and other natural sciences, cellular automata are used as models for various phenomena. Cellular automata are the simplest imaginable devices that operate under the nature-inspired constraints of massive parallelism, locality of interactions and uniformity in time and space. They can also exhibit the physically relevant properties of time reversibility and conservation laws if the local update rule is chosen appropriately.

Today cellular automata are studied from a number of perspectives in physics, mathematics and computer science. The simple and elegant concept makes them also objects of study of their own right. An advanced mathematical theory has been developed that uses tools of computability theory, discrete dynamical systems and ergodic theory.

Closely related notions in symbolic dynamics are subshifts (of finite type). These are sets of infinite arrays of symbols defined by forbidding the appearance anywhere in the array of some (finitely many) local patterns. In comparison to cellular automata, the dynamic local update function has been replaced by a static local matching relation. Two-dimensional subshifts of finite type are conveniently represented as tiling spaces by Wang tiles. There are significant differences in the theories of oneand two-dimensional subshifts. One can implant computations in tilings, which leads to the appearance of undecidability in decision problems that are trivially decidable in the one-dimensional setting. Most notably, the undecidability of the tiling problem — asking whether a given two-dimensional subshift of finite type is non-empty — implies deep differences in the theories of one- and two-dimensional cellular automata.

In this chapter we present classical results about cellular automata, discuss algorithmic questions concerning tiling spaces and relate these questions to decision problems about cellular automata, observing some fundamental differences between the one- and two-dimensional cases.

Introduction

Sequences of natural numbers have always been the subject of all kind of investigations. Among them is the famous Fibonacci sequence, related to the well-known Golden Ratio. This sequence is the paradigmatic example of a sequence satisfying a linear recursion. Latter sequences are of fundamental importance in algebra, combinatorics, and number theory, as well as in automata theory, since they count languages associated with finite automata.

The first scope of the present chapter is to prove a classification theorem: it characterises a class of sequences associated with certain quivers (directed graphs); in general these sequences satisfy non-linear recursions; it turns out that these sequences satisfy also a linear recursion exactly when the undirected underlying graph is of Dynkin, or extended Dynkin, type. This is perhaps the first example of a classification theorem, that uses Dynkin diagrams, in the realm of integer sequences.

Note that, for the sake of simplicity, we have dealt here with diagrams and quivers, whose underlying graphs are simple graphs; the corresponding Dynkin diagrams are sometimes called simply laced. The whole theory may be done with more general diagrams, that is, using Cartan matrices, see (Assem et al., 2010).

The sequences we consider are called friezes: they were introduced by Philippe Caldero and they satisfy non-linear recursions associated with quivers. Such a recursion is a particular case of a mutation, an operation introduced by Fomin and Zelevinsky in their theory of cluster algebras. The recursion does not show at all that these sequences are integer-valued. This must be proved separately and for this we follow Fomin and Zelevinsky's Laurent phenomenon (Fomin and Zelevinsky, 2002a,b), for which a proof is given.

We shall explain all details about Dynkin and extended Dynkin diagrams. These diagrams have been used to classify several mathematical objects, starting with the Cartan–Killing classification of simple Lie algebras. There is a simple combinatorial characterisation of these diagrams, due to (Vinberg, 1971) for Dynkin diagrams, and to (Berman et al., 1971/72) for extended Dynkin diagrams: they are characterised by the existence of a certain function on the graph, which must be subadditive or additive. See Section 10.8 for more detail.

Introduction

In this chapter we discuss (multidimensional) shifts of finite type, or SFTs for short. These are the sets X(ℰ) ⊆ ΣZd of d-dimensional configurations that arise by forbidding the occurrence of a finite list ℰ of finite patterns. This local, combinatorial and perhaps naive definition leads to surprisingly complex behaviour, and therein lies some of the interest in these objects. SFTs also arise independently in a variety of contexts, including language theory, statistical physics, dynamical systems theory and the theory of cellular automata. We shall touch upon some of these connections later on.

The answer to the question ‘what do SFTs look like’ turns out to be profoundly different depending on whether one works in dimension one or higher. In dimension one, the configurations in an SFT X(ℰ) can be described constructively: there is a certain finite directed graph G, derived explicitly from ℰ, such that X(ℰ) is (isomorphic to) the set of bi-infinite vertex paths in G. Most of the elementary questions, and many of the hard ones, can then be answered by combinatorial and algebraic analysis of G and its adjacency matrix. For a brief account of these matters, see Section 9.2.5.

In dimension d ≥ 2, which is our main focus here, things are entirely different. First and foremost, given ℰ, one cannot generally give a constructive description of the elements of X(ℰ). In fact, Berger showed in 1966 that it is impossible even to decide, given ℰ, whether X(ℰ) = ∅. Consequently, nearly any other property or quantity associated with X(ℰ) is undecidable or uncomputable.

What this tells us is that, in general, we cannot hope to know what a particular SFT behaves like. But one can still hope to classify the types of behaviours that can occur in the class of SFTs, and, quite surprisingly, it has emerged in recent years that for many properties of SFTs such a classification exists. The development of this circle of ideas began with the characterisation of the possible rates of ‘word-growth’ (topological entropy) of SFTs, and was soon followed by a characterisation of the degrees of computability (in the sense of Medvedev and Muchnik) of SFTs, and of the languages that arise by restricting configurations of SFTs to lower-dimensional lattices.