Science, Faculty of
Mathematics, Department of
DSpace
UBCV
MacDonald, Sophie Querida Tennant
Doctor of Philosophy - PhD
University of British Columbia
This dissertation consists principally of four of the author’s research articles, included as Chapters 2 through 5, all within or related to the area of symbolic dynamics, especially to shifts of finite type (SFTs) and sofic shifts. More specifically, each of the articles involves either Gibbs measures or factor codes, with Chapter 3 involving both in an essential way. The research in Chapter 2, in the thermodynamic formalism of dynamical systems, shows that two commonly used definitions of a Gibbs measure coincide for an arbitrary subshift over an arbitrary countable group, and that two different forms of one of these definitions are equivalent under certain regularity hypotheses. The main innovation is a more careful decomposition of holonomies of the Gibbs relation than had previously appeared. Chapter 3 is concerned with the Dobrushin and Lanford-Ruelle theorems, which relate Gibbs and equilibrium measures. This chapter establishes these theorems for irreducible sofic shifts, by lifting to an irreducible SFT and using cyclic structure to reduce to the classical mixing SFT case. The result was already known, by work of Haydn-Ruelle and Baladi, but the proof presented in this chapter is more self-contained. In particular, the argument makes extensive use of the properties of doubly transitive points, and relates them in a novel way to the Gibbs relation studied in Chapter 2. The work in Chapter 4 resolves two new cases of a problem in automata theory that originated in symbolic dynamics. The methods combine the notion of stability, introduced by Culik-Karhumaki-Kari and used by Trahtman in the solution to the road colouring problem, with the framework of graph homomorphisms introduced by Ashley-Marcus-Tuncel. The chapter also includes several new algorithms relevant to the problem. Chapter 5 solves a symbolic dynamics problem related to zero-error coding. The main result, which generalizes Krieger’s embedding theorem, characterizes the subshifts of a given mixing SFT on which a given sliding block code is injective. The proof follows the overall strategy of Krieger’s proof, but with significant technical innovations required to make the embedding compatible with the code.
GIBBS MEASURES AND FACTOR CODES IN SYMBOLIC DYNAMICSbySOPHIE QUERIDA TENNANT MACDONALDA THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate and Postdoctoral Studies(Mathematics)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)April 2023© Sophie Querida Tennant MacDonald, 2023The following individuals certify that they have read, and recommend to the Faculty of Graduate andPostdoctoral Studies for acceptance, the dissertation entitled:Gibbs measures and factor codes in symbolic dynamicssubmitted by Sophie MacDonald in partial fulfillment of the requirements forthe degree of Doctor of Philosophyin MathematicsExamining committee:Brian Marcus, Professor, Mathematics, UBCCo-SupervisorTom Meyerovitch, Professor, Mathematics, Ben Gurion University of the NegevCo-SupervisorAndrew Rechnitzer, Professor, Mathematics, UBCUniversity ExaminerBruce Shepherd, Professor, Computer Science, UBCUniversity ExaminerAdditional Supervisory Committee Members:Lior Silberman, Professor, Mathematics, UBCSupervisory Committee MemberOmer Angel, Professor, Mathematics, UBCSupervisory Committee MemberiiAbstractThis dissertation consists principally of four of the author’s research articles, included as Chapters 2through 5, all within or related to the area of symbolic dynamics, especially to shifts of finite type(SFTs) and sofic shifts. More specifically, each of the articles involves either Gibbs measures or factorcodes, with Chapter 3 involving both in an essential way.The research in Chapter 2, in the thermodynamic formalism of dynamical systems, shows that twocommonly used definitions of a Gibbs measure coincide for an arbitrary subshift over an arbitrarycountable group, and that two different forms of one of these definitions are equivalent under certainregularity hypotheses. The main innovation is a more careful decomposition of holonomies of the Gibbsrelation than had previously appeared.Chapter 3 is concerned with the Dobrushin and Lanford-Ruelle theorems, which relate Gibbs andequilibrium measures. This chapter establishes these theorems for irreducible sofic shifts, by lifting toan irreducible SFT and using cyclic structure to reduce to the classical mixing SFT case. The resultwas already known, by work of Haydn-Ruelle and Baladi, but the proof presented in this chapteris more self-contained. In particular, the argument makes extensive use of the properties of doublytransitive points, and relates them in a novel way to the Gibbs relation studied in Chapter 2.The work in Chapter 4 resolves two new cases of a problem in automata theory that originatedin symbolic dynamics. The methods combine the notion of stability, introduced by Culik-Karhumaki-Kari and used by Trahtman in the solution to the road colouring problem, with the framework ofgraph homomorphisms introduced by Ashley-Marcus-Tuncel. The chapter also includes several newalgorithms relevant to the problem.Chapter 5 solves a symbolic dynamics problem related to zero-error coding. The main result, whichgeneralizes Krieger’s embedding theorem, characterizes the subshifts of a given mixing SFT on whicha given sliding block code is injective. The proof follows the overall strategy of Krieger’s proof, butwith significant technical innovations required to make the embedding compatible with the code.iiiLay SummaryIn certain areas of physics and computer science, a system of interest is represented by a large collectionof simple pieces arranged in a line or a grid. Each of the pieces can be in one of a few states, andeach piece is influenced by other pieces, especially the ones nearby. In physics, the classic exampleis a magnet, made up of many pieces each pointing north or south, with each piece trying to alignitself with nearby pieces. In computing, the main examples are methods of storing data in patternsof 0’s and 1’s in a way that is resilient against errors, by only allowing certain patterns. There maybe several ways of writing down models like this for the same system. This thesis investigates severalquestions about when one system is essentially the same as another, even though they may be writtendown in different-looking ways.ivPrefaceChapter 2. A version of this chapter has been published [15], having previously appeared as an arXivpreprint [17]. An account of the research based closely on the published version appeared in Borsato’sdissertation at the University of Sao Paulo, defended in October 2022 and not yet publicly availableas of the date of submission of this dissertation.We began work on the research that is presented in this chapter after a meeting in the summerof 2019 in which I raised the question of whether several definitions of a Gibbs measure extant in theliterature were in fact equivalent. I formulated the paper’s new definitions, namely Gibbs measureswith respect to general measurable cocycles, groups with bounded sphere ratios, shell-regular andvolume-regular potentials, and full-dimensional interactions. I devised the proofs of the main results,building on Borsato’s detailed knowledge of the works of Kimura and Muir. I wrote the majority ofthe manuscript, the quality of which Borsato brought to a substantially higher standard by identifyingerrors and gaps in my reasoning and presentation while the work was in progress and while we werepreparing the manuscript for submission.Chapter 3. A version of this chapter appeared as an arXiv preprint [16] but was not submitted forpublication. As with Chapter 2, an account of the research based closely on the preprint appeared inBorsato’s dissertation at the University of Sao Paulo, defended in October 2022 and not yet publiclyavailable as of the date of submission of this dissertation. As with Chapter 2, I devised the over-all structure of the argument and wrote the majority of the manuscript, while Borsato contributedcrucially to the review of the literature and corrected many errors throughout the work and the writing.Chapter 4. A version of this chapter appeared as an arXiv preprint [51]. A manuscript based closelyon that preprint has been submitted for publication and is in review as of the date of submission ofthis dissertation. I carried out the work and the writing with frequent supervisory feedback from BrianMarcus and Tom Meyerovitch.Chapter 5. A version of this chapter appeared as an arXiv preprint [50]. A manuscript based closelyon that preprint has been submitted for publication and is in review as of the date of submission ofthis dissertation. I carried out the work and the writing with frequent supervisory feedback from BrianMarcus and Tom Meyerovitch.vContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vContents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Symbolic dynamics and entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.1 Symbolic dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.2 Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Chapter 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Chapter 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.4 Chapter 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.4.1 Background: from toral automorphisms to finite automata . . . . . . . . . . . . . 41.4.2 Main ideas and contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.5 Chapter 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Conformal measures and the Dobrushin-Lanford-Ruelle equations . . . . . . . . . 72.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2 Cocycles and the Gibbs relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.3 Equivalence of the conformal and DLR properties . . . . . . . . . . . . . . . . . . . . . . 92.4 Interactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.5 Potentials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.6 Potentials induced by interactions, and vice versa . . . . . . . . . . . . . . . . . . . . . . 143 A Dobrushin-Lanford-Ruelle theorem for irreducible sofic shifts . . . . . . . . . . 193.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2 Definitions, notations, and conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2.1 Symbolic dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2.2 The Gibbs relation, cocycles, and Gibbs measures . . . . . . . . . . . . . . . . . 203.3 Preservation of Gibbsianness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.4 Equilibrium measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254 The road problem and homomorphisms of directed graphs . . . . . . . . . . . . . . 294.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.2 Graphs and graph homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.2.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.2.2 Subgraphs and connectedness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30vi4.3 Stability and synchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.3.1 Transitions, stability, and synchronization . . . . . . . . . . . . . . . . . . . . . . 314.3.2 Sufficient conditions for stability . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.4 The O(G) conjecture and the road problem . . . . . . . . . . . . . . . . . . . . . . . . . 354.4.1 Generalization of the road colouring theorem . . . . . . . . . . . . . . . . . . . . 354.4.2 The O(G) conjecture implies the road colouring theorem . . . . . . . . . . . . . . 354.5 Bunchiness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.5.1 Bunchy and almost bunchy graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 364.5.2 Proof of the O(G) conjecture in the bunchy case . . . . . . . . . . . . . . . . . . 374.5.3 Universal property of the fiber product . . . . . . . . . . . . . . . . . . . . . . . . 374.6 The O(G) conjecture and bunchy synchronizing factors . . . . . . . . . . . . . . . . . . . 394.7 Computing with right-resolvers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.7.1 Basic routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.7.2 Decision procedures for common synchronizing factors and extensions . . . . . . 414.8 Proofs of structural results and additional details . . . . . . . . . . . . . . . . . . . . . . 424.8.1 Remarks on the proof of Theorem 4.2.4 . . . . . . . . . . . . . . . . . . . . . . . 424.8.2 Proof of Theorem 4.3.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.8.3 Proofs of Propositions 4.5.4 and 4.5.5 . . . . . . . . . . . . . . . . . . . . . . . . 444.8.4 Proof of Theorem 4.5.12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454.8.5 Proofs of Lemma 4.5.14 and Proposition 4.5.16, and construction of B(G) . . . . 464.8.6 Proofs of Propositions 4.6.1 and 4.7.1 . . . . . . . . . . . . . . . . . . . . . . . . 464.9 Proof of Theorem 4.4.3, following Trahtman . . . . . . . . . . . . . . . . . . . . . . . . . 494.9.1 Systems of maps with unique tallest trees . . . . . . . . . . . . . . . . . . . . . . 494.9.2 Obtaining a right-resolver with a unique tallest tree . . . . . . . . . . . . . . . . 505 Encoding subshifts through sliding block codes . . . . . . . . . . . . . . . . . . . . . 515.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515.2 Conventions, definitions, and background . . . . . . . . . . . . . . . . . . . . . . . . . . 525.2.1 Subshifts and sliding block codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 525.2.2 Markers and Markov approximations . . . . . . . . . . . . . . . . . . . . . . . . . 545.3 Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.3.1 Blanks and stamps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.3.2 Blanks and markers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575.3.3 Stamps and SFTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585.4 Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595.4.1 Self-overlap and stamps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595.4.2 Entropy and periodic points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615.5 Proofs of Lemma 5.2.6 and Corollary 5.1.3 . . . . . . . . . . . . . . . . . . . . . . . . . . 62Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65viiAcknowledgmentsI offer my thanks to my supervisory committee, especially my supervisors Brian Marcus and TomMeyerovitch, who have been extraordinarily generous with their time, attention, and advice over thelast several years. The research presented in this dissertation would not have happened without theirextensive, careful feedback and stimulating questions. Similar thanks are owed to Doug Lind.I thank the many mentors at UBC who have enriched and supported my scholarly development beyondresearch, especially Malabika Pramanik, Matt Coles, Joseph Topornycky, and Elyse Yeager.I thank Lu´ısa Borsato for being a tremendously skilled, persistent, and supportive collaborator and adear friend. In a similar spirit, I thank my close friends in or near this department—Caleb Marshall,Maricela Best McKay, Katie Faulkner, Mia Kramer, and Anshula Gandhi—for our years of studying,teaching, strategizing, and celebrating. It has been a joy to be confused and frustrated together.Beyond the Math Department, I thank the many friends who have accompanied, supported, and en-tertained me these last few years, especially Matthew Jordan, Kayla Besse, Joseph Burkhart, WalkerWilliams, Alison Stevens, Yotam Ronen (and Noga Vieman), and Alexis Kellum-Creer.Finally, I thank my family for supporting me in our tradition of vigorous curiosity from the beginning,especially my mother, without whom I would have been entirely sunk countless times along the way.viiiChapter 1Introduction1.1 Symbolic dynamics and entropy1.1.1 Symbolic dynamicsThis dissertation treats several problems in or related to symbolic dynamics. Symbolic dynamics isa branch of the theory of abstract dynamical systems with a strong computational and combinato-rial flavour, drawing heavily on automata theory, formal language theory, computability theory, andinformation theory as well as on ergodic theory, topological dynamics, and statistical thermodynamics.Much of the distinctive character of symbolic dynamics (see [49] for a standard introduction) comesfrom the fact that, in contrast to other branches of ergodic theory and topological dynamics, whichstudy a diverse collection of spaces and often a wide array of transformations of any given space (forinstance, the many manifolds on which one can consider smooth flows, or the many automorphismsof the two-dimensional torus), the dynamical system under consideration in symbolic dynamics isalways a subsystem of one of a small number of systems, i.e. spaces and transformations of them,with very similar topological and measure-theoretic properties. Once the “ambient” space and thetransformation (or set of transformations) are fixed, one studies the restrictions of the transformationto various invariant subsystems, which exhibit remarkable variety in their dynamical properties, aswell as maps between these subsystems that commute with the overall transformation.The ambient system in question is a full shift space. A full shift is the set of all functions fromsome fixed countably infinite group or semigroup, often the integers or a higher-dimensional integerlattice, to a fixed finite (or sometimes, but never in this dissertation, countably infinite) set of symbols,called the alphabet. There is therefore a full shift for each countable (semi)group and each positivenatural number (the cardinality of the alphabet). The (semi)group acts on this space of functions bytranslation (hence the term shift space), with the transformation or set of transformations that definethe system generating the group. In the most classical theory, the alphabet consists of the binarysymbols 0 and 1 and the group is isomorphic to the group of integers, with a single generator, namelythe shift transformation.When one equips the alphabet with the discrete topology and takes the product topology overthe group, the full shift is a zero-dimensional compact metric space on which the shift map is ahomeomorphism. The aforementioned functions from the group to the alphabet are the points in thespace. Symbolic dynamics studies the dynamical properties of the restrictions of the shift map tothe closed, shift-invariant subspaces of the full shift, known as subshifts, and the continuous, shift-commuting (i.e. equivariant) maps between these systems. Any subshift is characterized by the setof finite patterns of symbols that appear in its points; in particular, a one-dimensional subshift (i.e.a subshift over the integers) is characterized by the language consisting of the finite words it allows.This is the key idea of symbolic dynamics: a subshift is a topological dynamical system defined byconstraints on finite configurations of symbols.11.1.2 EntropyMany of the stationary finite-valued stochastic processes or random fields studied in statistical physicsand information theory can be understood as shift-invariant Borel probability measures on subshifts,which leads to fruitful interactions of these areas with symbolic dynamics via the application of ergodictheory, the study of measure-preserving transformations in general.In particular, a central concept in symbolic dynamics, imported from ergodic theory, is that ofentropy, which refers to several different, closely related quantities. The (topological) entropy of asubshift is the asymptotic exponential growth rate of the number of finite patterns appearing in pointsin the subshift, with respect to the size of the patterns. Although elementary, this definition does notexplain the significance of entropy in the subject. We need some history in order to convey the contextand meaning of the present dissertation to a reader not trained in ergodic theory.The definition of the entropy of a measure-preserving system was introduced in its modern general-ity by Kolmogorov [46], who introduced it in order to resolve isomorphism problems in ergodic theory.In particular, he and Sinai [71] showed that entropy is an invariant of measure-theoretic isomorphismand was able to distinguish systems which were not previously known to be non-isomorphic, the best-known pair being the uniform Bernoulli processes on the full 2- and 3-shifts. Previously, the maininvariants known had been qualitative, such as ergodicity and other mixing properties, and spectral,referring to the spectrum of the Koopman operator, which translates functions along orbits. The mainresult on spectral invariants was due to von Neumann, who was motivated to work on the isomorphismproblem because he considered the essential properties of a physical system with an invariant measureto be those that were preserved by measure-theoretic isomorphism [60].When Kolmogorov introduced entropy into ergodic theory, he was drawing on the work of Shannon,who had defined entropy in the special case of finite Markov chains and shown that it was the essentialquantity for determining whether a given communication channel could transmit a given Markovsource of messages with acceptably low probability of error [69]. Shannon had observed that entropy, asdefined and used in statistical physics by Boltzmann, Gibbs, and later von Neumann, is a generalizationof a quantity introduced to information theory by Hartley [35] to calculate, among other things, therelationships between the redundancy of the code used for a telegraph and the electrical properties ofthe telegraph lines required for a receiver to reliably decode the sender’s messages.In these thermodynamic and information-theoretic contexts for entropy, although the probabilitymeasures involved can often be formulated as measures on subshifts, the dynamical and topologicalaspects are secondary. However, Kolmogorov also introduced another notion of entropy, namely a kindof covering number for a metric space–specifically, the ε-entropy of a metric space is the logarithmof the largest number of points that can be packed into the space such that any two are at distanceat least ε from each other [47]. A point in the space can be approximated to within a distance ofε/2 by the nearest of these points, which is in a precise sense analogous both to the decoding ofcontinuously varying voltages over an analog channel back into symbols, and to the approximationof the continuously varying thermodynamic variables in a small region of a system by a finite setof possible values. Moreover, by considering a continuous transformation of a metric space (i.e. atopological dynamical system), one can ask more generally about the largest number of points suchthat after n iterations of the transformation, any two of the points have been separated by a distanceof at least ε at least once in their orbits. This number grows exponentially in n, and the limit, as εtends to 0, of its asymptotic exponential growth rate is the topological entropy of the system [76].The concept of topological entropy allows us, both by analogy and by the essential theorems relatingit to measure-theoretic entropy, to ask information-theoretic and thermodynamic questions aboutdynamical systems with no obvious connection to telecommunications or thermodynamics. Both theinformation-theoretic and the statistical thermodynamic influences on symbolic dynamics are presentin this dissertation, with the thermodynamics emphasized in Chapters 2 and 3 and the informationtheory in Chapter 5, as we now elaborate. In what follows, see the respective chapters for precisedefinition and statements.21.2 Chapter 2This chapter is concerned with two notions of a Gibbs measure on a subshift over a countable group.The first of these is defined by the Dobrushin-Lanford-Ruelle (DLR) equations, or equivalently aGibbsian specification. This notion of a Gibbs measure appears for instance in the classical theoremsof Dobrushin [28] and Lanford-Ruelle [38]. The second is the notion of a conformal measure, introducedin [63] and [27] and used for instance by Meyerovitch in [56] as the setting for a stronger Lanford-Ruelletheorem. There are other definitions in the literature, such as a Gibbs measure in the sense of Bowen,but we do not consider these here.The purpose of this chapter is to show that the two notions of Gibbs measure recalled abovecoincide in some generality. Our results build on those of Kimura, obtained in his Master thesis [44],who proves two results relevant here. The first is that every conformal measure, with respect to anappropriately regular potential, satisfies the DLR equations for that potential. The second is a partialconverse, namely that every measure satisfying the DLR equations for such a potential is a topologicalGibbs measure (see e.g [44], Definition 5.14). This is a weaker property than being conformal, althoughequivalent on certain subshifts, such as shifts of finite type (SFTs) [56]. Sarig ([68], Proposition 2.1)shows that the two notions of Gibbsianness are equivalent in the case of a one-sided topological Markovshift, using martingale and Ruelle transfer operator methods (note that he uses the word “conformal”for a notion that is related to but different from the one we consider). Cioletti-Lopes-Stadlbauer([24]) prove the equivalence of the DLR and conformal notions of Gibbs measure for one-sided, one-dimensional shifts with a compact metric alphabet and a continuous potential. Muir [58] also obtainsthe full equivalence for the full shift on Zd over a countable alphabet.Our main result in this chapter, Theorem 2.3.4, strengthens one of Kimura’s results in a moregeneral setting. Specifically, we show that any measure satisfying certain equations with respect to ameasurable cocycle on the Gibbs relation must also be conformal with respect to that cocycle. Whenthe cocycle is induced either by an interaction or by a potential in the standard way, these equationsreduce to the classical DLR equations. We prove this result for arbitrary subshifts with finite alphabeton an arbitrary countable group. The results of Kimura and Sarig in the forward direction (conformalimplies DLR) can also be generalized to our setting; in §2.3, we mention the idea for the proof butrefer readers to [44] for the details in Kimura’s setting, as the proof strategy changes very little.1.3 Chapter 3The Dobrushin theorem establishes sufficient conditions on shift spaces X and potentials f ∈ C(X)such that every Gibbs measure for f is an equilibrium measure for f . This theorem holds in anyshift space, not necessarily of finite type, with a certain mixing condition known in the literature ascondition (D) [66]. This condition is implied, for instance, by strong irreducibility, and in this paperwe only use the strongly irreducible case of the classical theorem.The classical converse to the Dobrushin theorem is known as the Lanford-Ruelle theorem. Toour knowledge, the most general natural hypothesis known for the Lanford-Ruelle theorem is thetopological Markov property [9], which is satisfied in particular by SFTs. Examples are also known,however, of shift spaces which lack the topological Markov property, but for which the conclusion of theLanford-Ruelle theorem nevertheless holds, at various levels of generality [56]. It is therefore desirableto extend the Lanford-Ruelle theorem beyond the class of shifts with the topological Markov property,in the hope of explaining such examples.In this chapter, we do not treat the examples in [56], but we do prove a Lanford-Ruelle theorem forirreducible sofic shifts in one dimension (Theorem 3.4.7), which generally lack the topological Markovproperty. This is related to a question of Kitchens-Tuncel ([45], Remark 7.10(iii)). The proof relies on apreservation of Gibbsianness result for almost invertible factor codes on irreducible SFTs (Proposition3.3.7), which we generalize to finite-to-one factor codes in Corollary 3.4.10. We prove Theorem 3.4.7 bylifting an equilibrium measure on a sofic shift to an equilibrium measure on a covering SFT, which is3Gibbs by the classical Lanford-Ruelle theorem, then concluding by Proposition 3.3.7 that the originalequilibrium measure is Gibbs. Irreducibility of the sofic shift is essential: the Lanford-Ruelle theoremholds for SFTs with no irreducibility assumption, but it is false in general for reducible sofic shifts.The simplest counterexample is the sunny-side-up shift (the set of sequences in {0, 1}Z with at most asingle 1) with its unique shift-invariant measure.We also extend the Dobrushin theorem to irreducible sofic shifts (Theorem 3.4.11), which generallylack the mixing properties hypothesized in the classical version. Here, our approach is based on thecyclic structure of an irreducible SFT, combined with our other results.After posting a version of this chapter on the arXiv, we became aware of the work of VivianeBaladi [8], which obtains the same Dobrushin-Lanford-Ruelle result for Ho¨lder potentials on finitelypresented systems, of which irreducible sofic shifts are a particular case. We also became aware of thework of Haydn-Ruelle [36], which does the same for expansive homeomorphisms with specification, ofwhich mixing sofic shifts are a particular case. We hope that the self-contained symbolic approach ofthis paper, which leverages the classical Dobrushin and Lanford-Ruelle theorems essentially as blackboxes, may be accessible to a wider audience and may draw attention to the earlier work by Baladiand Haydn-Ruelle.1.4 Chapter 41.4.1 Background: from toral automorphisms to finite automataIn this chapter, we are concerned with a generalization of the road (colouring) problem. That problem,posed by Adler-Goodwyn-Weiss in [2] and solved by Trahtman in [74], asked whether every stronglyconnected, aperiodic directed graph of constant out-degree is the underlying graph of a synchronizingdeterministic finite automaton (DFA). A finite automaton is a very simple model of a computer,consisting of a directed graph with edges labeled with symbols from a finite alphabet. When thereis a distinguished initial state (vertex) and a distinguished set of accepting states, one considers thequestion of which words over the alphabet label a route from the initial state to one of the acceptingstates. More generally, one can ask about the mappings induced on the set of states by various words.An automaton, or graph labeling, is synchronizing if for some word it routes all states to a commonstate–that is, if the image of the mapping induced by some word is a singleton. Trahtman’s roadcolouring theorem (Theorem 4.4.1 below) gives an affirmative answer to the road problem, showingthat every graph with the aforementioned properties indeed admits a synchronizing colouring, and [21,10] give a generalization to periodic graphs (Theorem 4.4.2).The motivation for the road problem comes from ergodic theory. Specifically, a weak form ofthe road colouring theorem was used to prove the main theorem of [2], which gives a criterion formeasure-theoretic isomorphism of certain Markov chains. This was the first time the road problemwas explicitly posed, although the real origin of the problem is the earlier paper [3], which concernsthe analogous isomorphism problem for hyperbolic automorphisms of the two-dimensional torus.This chapter concerns a generalization of the road problem motivated by graph-theoretic invariantsfor a different, but related, isomorphism relation in ergodic theory. Specifically, Ashley-Marcus-Tuncel[6] identified a graph-theoretic criterion for isomorphism of one-sided stationary Markov chains, implicitin [19], and gave a complete, effectively computable set of isomorphism invariants. They observed thata certain conjectural uniqueness result (the O(G) conjecture, below in §4.3.1) would, if proven, simplifythe set of invariants, and proved the conjecture in a family of special cases. The conjecture reduces toa generalization of the road problem involving certain right-resolving graph homomorphisms (whichwe call right-resolvers; see §4.2.1). For graphs of constant out-degree, these homomorphisms coincidewith road colourings.41.4.2 Main ideas and contributionsThe main purpose of this chapter is to present new results toward the O(G) conjecture. There are twomain ideas in the paper. The first idea concerns the stability relation of a right-resolver, which wasintroduced in [37] for DFAs or road colourings. For context, Kari [39] solved the road problem in theEulerian case by finding, for a given graph, a road colouring with nontrivial (i.e. not merely diagonal)stability relation, then recursively finding a synchronizing road colouring of the strictly smaller quotientgraph (in which the states are stability classes), and lifting it to the original graph. Trahtman’s solutionof the full road problem uses the same inductive strategy, paired with a more sophisticated techniquefor obtaining a colouring with a nontrivial stability relation.By determining how the stability relation behaves with respect to composition of right-resolvers,we are able to study the aforementioned recursive lifting constructions more systematically, allowingus to apply them toward the O(G) conjecture. In particular, we adapt Trahtman’s proof of the roadcolouring theorem to cover a larger family of cases (Theorem 4.4.3), in which the out-degrees of statesare allowed to vary cyclically. To do so, we generalize, to the setting of right-resolvers, a sufficientcondition for a road colouring to have a nontrivial stable pair, based on the idea of a function graphwith a unique tallest tree. This condition is at the heart of all proofs of the road colouring theorem todate, and its importance has motivated detailed analysis [12].The second main idea in this chapter is a graph property that we call bunchiness, along with aweaker property called almost bunchiness. Bunchy and almost bunchy graphs are characterized bythe property that the right-resolvers they admit are unique up to automorphisms in a certain sense(Proposition 4.5.4). We highlight the implicit role of bunchiness both in [6] and in the road colouringliterature, and prove the O(G) conjecture for bunchy and almost bunchy graphs (Theorem 4.5.6).Furthermore, we show that the fiber product of right-resolving homomorphisms satisfies a universalproperty (Theorem 4.5.12) that further highlights the essential role of bunchy graphs.Motivated by these results, we introduce a new conjecture, which we call the bunchy factor con-jecture (see §4.6), asserting essentially that the O(G) conjecture can be proved using the stabilityapproach that Trahtman used to prove the road colouring theorem, with bunchy graphs as the baseof the recursion. Another way of articulating this conjecture is that the barrier to proving the O(G)conjecture is our lack of a sufficiently general method of producing homomorphisms with nontrivialstability relation. The fact that the bunchy factor conjecture implies the O(G) conjecture is madeexplicit in Proposition 4.6.2, which relies primarily on Proposition 4.5.15, a uniqueness result that usesthe universal property of the fiber product in an essential way.1.5 Chapter 5As mentioned above, Shannon introduced a model of a noisy communication channel [69], in which theinput and output are modeled by stationary probability measures on a space of sequences of symbols.Shannon gave conditions under which the input can be recovered from the output, at least with anacceptable rate of error or ambiguity, in the case of a Bernoulli source, and this work has since beenextended to more general sources [43].This chapter is motivated by the particular question of when one can ensure zero error, not justalmost surely as in information theory but in fact deterministically. A deterministic channel can bemodeled by a sliding block code, i.e. a continuous, shift-commuting map on a subshift, on which astationary process could be supported. In this model, we can use symbolic dynamics to investigatethe effects of deterministic noise [54], also called distortion [69], which we can interpret as a failure ofinjectivity of the sliding block code representing the channel, even in the absence of random errors.The main result of this chapter, Theorem 5.1.1, determines the extent to which the non-injectivityof a sliding block code on a mixing SFT can be avoided by restricting to a subshift of the domain.Interpreting the sliding block code as a channel with deterministic noise, Theorem 5.1.1 characterizesthe sources with entropy strictly lower than that of the output which can be transmitted without erroror ambiguity. That is, let X be a mixing SFT, Y a mixing sofic shift, and π : X → Y a factor code.5Let Z be a subshift. For there to exist an embedding ψ : Z → X such that π ◦ ψ is injective, theentropy of Z must be at most that of Y (with equality possible only if Z is conjugate to Y ), and Zmust have few enough periodic points that π ◦ ψ can be injective at least on the periodic points in Z.The content of Theorem 5.1.1 is that these two sufficient conditions are enough.In that spirit, Theorem 5.1.1 is a generalization of a theorem of Krieger (Theorem 2 in [48], quotedas Theorem 5.1.2 in this dissertation), which shows that two necessary conditions for the existence ofan embedding of a subshift Z into a mixing SFT X are also sufficient. These conditions are that theentropy of Z must be at most that of X, with equality possible if and only if Z and X are conjugate,and that there must a shift-commuting injection at least from the periodic points of Z to those of X.Krieger’s theorem is false if X is taken to be merely mixing sofic; indeed, the embedding problem formixing sofic shifts remains open, and seems to be delicate [73].Because the asymptotic exponential growth rate, with respect to least period, of the number ofperiodic points in a mixing sofic shift is equal to the entropy of the shift, the periodic point condition,in both Krieger’s theorem and Theorem 5.1.1, presents only a finite number of possible obstructions,coming from low-order periodic points in the source shift Z. In the proof of Theorem 5.1.1, which isclosely modeled on the proof of Krieger’s theorem as presented in [49], points in Z are broken intoblocks of moderate length and long blocks coming from lower-order periodic points. The entropyand periodic point conditions are used to construct injections on the moderate and long segmentsrespectively, first to blocks in Y and then to blocks in X. The moderate and long blocks are thenstitched together using blocks which we call “stamps”, in such a way that the locations of the originalblocks in Z can be unambiguously identified once the factor code π has been applied. Much of thechapter is concerned with establishing the existence of properties of these stamps.6Chapter 2Conformal measures and the Dobrushin-Lanford-Ruelleequations2.1 IntroductionThe plan is as follows. In §2.2, we review the definitions and basic facts required to prove our main resultin §2.3. In §2.4 and §2.5, we recall well-known material on interactions and potentials, respectively, inorder to show that the equations involved in our main theorem do in fact reduce to the classical DLRequations. In §2.6, we recall results of Muir and Kimura, elaborating on Ruelle, by which a potentialcan be constructed from a sufficiently regular interaction, and vice versa, with “physical” data (Gibbsand equilibrium measures) preserved.In §2.5 and §2.6, we require that the underlying group admits a finite generating set that yieldsa certain spherical growth condition, defined in §2.5. This condition is satisfied, for any generatingset, by any group of polynomial growth of nilpotency class at most 2, such as Zd, the case of greatestphysical interest. It is also satisfied by any free group Fn, with the usual generating set of cardinalityn, and, conditional on a folklore conjecture, is satisfied by any nilpotent group.2.2 Cocycles and the Gibbs relationThroughout, let G be a countable group with identity e. Let A be a finite alphabet equipped with thediscrete topology, and X ⊆ AG a subshift, i.e., a closed set in the product topology, invariant underthe shift action of G via (g · x)h = xg−1h. The topology on X is generated by cylinders, i.e., sets ofthe form [ω] = {x |xΛ = ω} for finite sets Λ ⋐ G. We use the notation Λ ⋐ G to indicate that Λ is afinite subset of G. This topology can be induced by a metric such that the resulting metric space iscomplete and separable; that is, AG is a Polish space. We equip X with the Borel σ-algebra F . Fora set A ⊆ G, we write FA for the sub-σ-algebra of F determined by A—that is, for any E ∈ FA andany x, x′ ∈ X, if x ∈ E and xA = x′A, then x′ ∈ E.The Gibbs relation, also called the asymptotic relation, is the equivalence relation TX ⊂ X×X suchthat (x, y) ∈ TX if and only if xΛc = yΛc for some finite set Λ ⋐ G. Let (ΛN )∞N=1 be a sequence of finitesets exhausting G, i.e., (ΛN )∞N=1 is an increasing sequence and G = ∪+∞N=1ΛN . Define the subrelationTX,N = {(x, y) : xΛcN = yΛcN } ⊆ TX . Observe that, for each subrelation TX,N , each equivalence classis a finite set, and that TX = ∪∞N=0TX,N . (In the language of Borel equivalence relations, this meansthat TX is hyperfinite [41], which we mention for context, although we do not use any theorems abouthyperfiniteness in this paper.) In particular, every equivalence class in TX is at most countable. Notethat we can write each subrelation as TX,N = ∩∞n=N ∪ω∈AΛn\ΛN [ω]× [ω], which shows that TX,N is ameasurable subset of X ×X in the product σ-algebra F ⊗ F , as is TX .For Borel sets A,B ⊆ X, a holonomy of TX is a Borel isomorphism ψ : A → B such that(x, ψ(x)) ∈ TX for all x ∈ A. We say that a holonomy ψ is global if A = B = X. The definitions forTX,N are analogous, with a holonomy of TX,N also a holonomy of TX , for every N .7For a Borel set A ⊆ X, we denote TX(A) =⋃x∈A{y ∈ X|(x, y) ∈ TX}, and the same for thesubrelations. The saturations TX(A) and TX,N (A) are easily shown to be Borel using the fact thatthe diagonal in X ×X is measurable in the product σ-algebra, which follows as an easy exercise fromthe fact that X is Polish.Lemma 2.2.1. There exists a countable group Γ of global holonomies of X such thatTX = {(x, γ(x)) : x ∈ X, γ ∈ Γ}.In other words, Γ generates TX .Proof. The group Γ can be described explicitly as a countable increasing union of finite groups ΓN . Foreach N , the group ΓN generates TX,N and is isomorphic to the symmetric group of order |AΛN |. TakeΓN to be generated by holonomies ψ of the following form: given ω, η ∈ AΛN , define ψω,η : X → X byψω,η(x) =ηxΛcN xΛN = ω, ηxΛcN ∈ XωxΛcN xΛN = η, ωxΛcN ∈ Xx otherwiseThat is, ψω,η exchanges ω and η, wherever possible, and otherwise does nothing. These involutionswere considered in [56] and [44], for slightly different purposes.Observe that (x, y) ∈ TX,N if and only if there exists ψ ∈ ΓN with ψ(x) = y, so TX,N is preciselythe orbit relation of ΓN . The result for Γ is immediate.Remark 2.2.2. We mention for context that Lemma 2.2.1 is a special case of the main theorem of[30], which in fact asserts the same for any Borel equivalence relation on a Polish space in whichevery equivalence class is countable. This result was adapted to the symbolic setting in [56], with thecountability of the equivalence classes established via the expansivity of the shift action. The proofis presented for subshifts over Zd, but the same proof goes through for arbitrary countable groupswithout modification. However, since we establish Lemma 2.2.1 directly, we do not need to appeal tothe theorem of [30] (nor the symbolic corollary in [56]).We say that a measure µ on X (by which we always mean a Borel probability measure) is TX -nonsingular if for every Borel A ⊂ X with µ(A) = 0, we have µ(TX(A)) = 0. Note that if µ isTX -nonsingular and ψ : A → B is a holonomy of TX , then whenever E ⊂ A has µ(E) = 0, we haveµ(ψ(E)) ≤ µ(TX(E)) = 0. In particular, the Radon-Nikodym derivative d(µ◦ψ)dµ is well-defined. Thesame holds with TX replaced by TX,N .A (real-valued) cocycle on TX is a Borel measurable function ϕ : TX → R such that ϕ(x, y) +ϕ(y, z) = ϕ(x, z) for all x, y, z ∈ X with (x, y), (y, z) ∈ TX (so that (x, z) ∈ TX as well). Any cocycleon TX clearly restricts to a cocycle on TX,N , for any given N . Given a TX -nonsingular measure µ onX, we say that a Borel function D : TX → R is a Radon-Nikodym cocycle on TX with respect to µ ifthe pushforward of µ by any holonomy ψ : A → B of TX satisfies d(µ◦ψ)dµ (x) = D(x, ψ(x)) for µ-a.e.x ∈ A. It is routine to show, using Lemma 2.2.1, that any TX -nonsingular measure µ on X has aµ-a.e. unique Radon-Nikodym cocycle.Definition 2.2.1 (conformal measure). Let µ be a TX -nonsingular Borel probability measure on X,and let ϕ : TX → R be a cocycle. We say that µ is (ϕ,TX)-conformal if for any holonomy ψ : A→ Bof TX , with A and B Borel sets, we haveµ(B) =∫Aexp(ϕ(x, ψ(x))) dµ(x)Note that this is equivalent to the condition thatDµ,TX (x, ψ(x)) = exp(ϕ(x, ψ(x)))for µ-a.e. x ∈ A. Note also that a TX -nonsingular measure is conformal precisely with respect to thelogarithm of its Radon-Nikodym cocycle.8Remark 2.2.3. The name “conformal measure” was given to a related kind of measure in [27] withrespect to a N-action. It can be shown that these are precisely those measures which are conformal inthe present sense and are non-singular with respect to the N-action. Note that [27] uses a multiplicativerather than an additive cocycle, and since Denker-Urbanski use only a single transformation, theircocycle is a function of one variable rather than of two. The name “conformal” was motivated, in [27],by analogy with Patterson’s study [62] of measures on the limit sets of Fuchsian groups of conformalmappings of the unit disc in the complex plane.Conformal measures in our sense were introduced in [22], where they were simply called Gibbsmeasures. For links between similar notions on one- and two-sided shifts in one dimension, see [11].Definition 2.2.2 (DLR equations for a cocycle). Let X ⊆ AG be a subshift, ϕ a cocycle on TX , andµ a measure on X. For a Borel set A ⊆ X and a finite set Λ ⋐ G, the DLR equation for x ∈ X is asfollows:µ(A | FΛc)(x) =∑η∈AΛ ∑ζ∈AΛexp(ϕ(ηxΛc , ζxΛc))1X(ζxΛc)−1 1A(ηxΛc) (2.1)We say that µ is DLR with respect to ϕ if, for any Borel A ⊆ X and any Λ ⋐ G, (2.1) holds for µ-a.e.x ∈ X.2.3 Equivalence of the conformal and DLR propertiesFor us, the main value of Lemma 2.2.1 is the following lemma, which reveals in particular that to showthat a given measure is conformal (such as in Theorem 2.3.4), it is sufficient to consider only globalholonomies.Lemma 2.3.1. Let µ be a Borel probability measure on X, let ϕ be a cocycle on TX , and let Γ bea countable group generating TX . Then µ is (ϕ,TX)-conformal if and only if, for each γ ∈ Γ, thepushforward µ ◦ γ is absolutely continuous with respect to µ, with d(µ◦γ)dµ (x) = exp(ϕ(x, γ(x))) forµ-a.e. x ∈ X.Proof. The “only if” direction is immediate from the definition of conformal measure. To confirm the“if” direction, we first check nonsingularity. Let A ⊂ X be Borel with µ(A) = 0. Then TX(A) =⋃γ∈Γ γ(A), which is a countable union and thus has measure zero by the explicit expression ford(µ◦γ)dµ .Now let ψ : A → B be a holonomy of TX and let E ⊆ A be Borel. Let Γ = (γn)n∈N be anenumeration of Γ. For each n ∈ N, let En = {x ∈ E : ψ(x) = γn(x)}. To see that each En is Borel,define the map τn : X → X ×X by τn(x) = (ψ(x), γn(x)), which is clearly measurable in the productσ-algebra. Then En = τ−1n (D) where D ⊂ X ×X is the diagonal, which, as discussed above, is alsoBorel in the product σ-algebra, because X is Polish.Now let E′0 = E0, and for n ≥ 1, let E′n = En \ ∪n−1k=0Ek. The Borel sets E′n partition E, soµ(ψ(E)) =∞∑n=0µ(γn(E′n)) =∫Eexp(ϕ(x, ψ(x))) dµ(x)Thus d(µ◦ψ)dµ (x) = exp(ϕ(x, ψ(x)) for µ-a.e. x ∈ A, as required.We will use Lemma 2.3.1 in concert with the following lemma, which reduces the question of(ϕ,TX)-conformality to that of conformality with respect to the finite-order subrelations.Lemma 2.3.2. Let µ be a measure on X and ϕ a cocycle on TX . Suppose that µ is (ϕ,TX,N )-conformalfor each N ≥ 0. Then, µ is (ϕ,TX)-conformal.9Proof. By Lemma 2.3.1, it is enough to consider only global holonomies. Let ψ : X → X be a globalholonomy of the Gibbs relation TX and let A ⊆ X be a Borel set. We begin by writing A as theincreasing union A = ∪∞N=0AN , where AN = {x ∈ A : (x, ψ(x)) ∈ TX,N}. Since ψ|AN is a holonomyof TX,N and µ is (ϕ,TX,N )-conformal, we haveµ(ψ(A)) = limN→∞µ(ψ(AN ))= limN→∞∫ANexp(ϕ(x, ψ(x))) dµ(x)=∫Aexp(ϕ(x, ψ(x))) dµ(x),by monotone convergence. Thus, µ is indeed (ϕ,TX)-conformal by Lemma 2.3.1.To echo the comment above on hyperfiniteness, we remark here that both of these results apply,with the same proofs, to any hyperfinite Borel equivalence relation on any Polish space. The followinglemma, by contrast, seems to rely more specifically on the structure of X as a subshift.Lemma 2.3.3. Let X ⊆ AG be a subshift, let ϕ be a cocycle on X, and let µ be a DLR measure onX with respect to ϕ. Let N ≥ 1. Then µ is (ϕ,TX,N )-conformal.Proof. It is enough to show that µ(ψ([ω])) =∫[ω]exp(ϕ(x, ψ(x))) dµ(x) for any cylinder [ω] and (byLemma 2.3.1) any global holonomy ψ of TX,N . Fix a holonomy ψ : X → X of TX,N . Since theequivalence classes of TX,N are finite, and in fact have bounded cardinality, there exists some r ≥ 0such that ψr(x) = x, for all x ∈ X. Let m ≥ N and fix ω ∈ AΛm . We now partition X according tothe orbits of points under ψ, in such a way that [ω] is partitioned into sets that are easy to control.Specifically, for each η = (η0, . . . , ηr−1) ∈ (AΛm)r, letTη = {x ∈ X : ψj(x)Λm = ηj , 0 ≤ j ≤ r − 1}Note that Tη can be empty. We have [ω] = ⊔η:η0=ωTη, and ψ(Tη) = Tση, where ση = (η1, . . . , ηr−1, η0)is a cyclic permutation of η. It is enough to show that, for all η ∈ (AΛm)r, we haveµ(ψ(Tη)) =∫Tηexp (ϕ(x, ψ(x))) dµ(x).By the equality ψ(Tη) = Tση, we haveµ(ψ(Tη)) =∫Xµ(Tση | FΛcm) dµ(x)For any x ∈ X, we know that1Tση (η1xΛcm) = 1Tη (η0xΛcm)By this identity, as well as the DLR hypothesis and the defining property of a cocycle, we have thefollowing manipulations:µ(Tση | FΛcm)(x) = ∑ζ∈AΛmexp(ϕ(η1xΛcm , ζxΛcm))1X(ζxΛcm)−1 1Tση (η1xΛcm)= ∑ζ∈AΛmexp(ϕ(η0xΛcm , ζxΛcm))1X(ζxΛcm)−1× 1Tη (η0xΛcm) exp(ϕ(η0xΛcm , η1xΛcm))= µ(Tη | FΛcm)(x) exp(ϕ(η0xΛcm , η1xΛcm))Integrating this equation yields the result.10We have therefore done all the work required to prove the following:Theorem 2.3.4. Let X ⊆ AG be a subshift, ϕ a cocycle on X, and µ a DLR measure on X withrespect to ϕ. Then µ is (ϕ,TX)-conformal.Proof. By Lemma 2.3.3, µ is (ϕ,TX,N )-conformal for each N . The result is then immediate fromLemma 2.3.2.Theorem 2.3.4 was proven by Kimura ([44], Theorem 5.30) in the special case that G = Zd, X isa shift of finite type, and the cocycle ϕ is induced by a potential, in the manner that we discuss inProposition 2.5.3 below. Furthermore, Kimura proved the following converse ([44], Corollary 5.33),again in the case of G = Zd and ϕ induced by a potential, but with no finite type assumption on X.Theorem 2.3.5. Let X ⊆ AG be a subshift, ϕ a cocycle on X, and µ a (ϕ,TX)-conformal measureon X. Then µ is DLR with respect to ϕ.The proof of Theorem 2.3.5 is a straightforward adaptation of the methods that Kimura used forthe case that he treated. The rough idea is to show that two cylinder sets have conditional measureswith the appropriate ratio by considering the holonomy that exchanges them, as in the proof of Lemma2.2.1 above, then applying the conformal hypothesis. The main difference required to adapt the proofis that the version stated here concerns the DLR equations for an arbitrary measurable cocycle, notnecessarily one induced by a potential.2.4 InteractionsIn this section, we show that, when a cocycle is induced by an interaction, the DLR equations for thecocycle reduce to those for the interaction.Definition 2.4.1 (interaction). An interaction is a family Φ = (ΦΛ)Λ⋐G of functions ΦΛ : X → Rsuch that for each Λ ⋐ G, ΦΛ is FΛ-measurable, and for all Λ ⋐ G, x ∈ X, the Hamiltonian seriesHΦΛ (x) =∑∆⋐G∆∩Λ̸=∅Φ∆(x)converges in the sense that there exists a real number HΦΛ (x) and, for every ε > 0, there exists someF ⋐ G such that, for all F ′ ⊇ F , ∣∣∣∣∣∣∣∣HΦΛ (x)−∑∆⊆F ′∆∩Λ̸=∅Φ∆(x)∣∣∣∣∣∣∣∣ < εProposition 2.4.1. Let Φ be an interaction. For each (x, y) ∈ TX , the series∑Λ⋐G[ΦΛ(x)− ΦΛ(y)]converges in the same sense as the Hamiltonian series. Moreover, the function ϕΦ : TX → R definedbyϕΦ(x, y) =∑Λ⋐G[ΦΛ(x)− ΦΛ(y)]is a cocycle on TX .11Proof. Let (x, y) ∈ TX be such that x∆c = y∆c . We claim that∑Λ⋐G[ΦΛ(x)− ΦΛ(y)] = HΦ∆(x)−HΦ∆(y)with the equality understood in the sense of convergence discussed in the statement of the proposition.Indeed, choose ε > 0. By the definition of an interaction, there exists some F ⋐ G sufficiently largethat whenever F ⊆ F ′ ⋐ G, we have (noting that ΦE(x)− ΦE(y) = 0 when E ∩∆ = ∅),∣∣∣∣∣∣[HΦ∆(x)−HΦ∆(y)]−∑E⊆F ′[ΦE(x)− ΦE(y)]∣∣∣∣∣∣≤∣∣∣∣∣∣∣∣HΦ∆(x)−∑E⊆F ′E∩∆ ̸=∅ΦE(x)∣∣∣∣∣∣∣∣+∣∣∣∣∣∣∣∣HΦ∆(y)−∑E⊆F ′E∩∆ ̸=∅ΦE(y)∣∣∣∣∣∣∣∣<εThis establishes that the series converges, in the sense claimed, to a real number ϕΦ(x, y) = HΦ∆(x)−HΦ∆(y). Moreover, this energy difference expression makes it obvious that ϕΦ is a cocycle, concludingthe proof.We now observe that the DLR equations for the cocycle ϕΦ, in the sense of Definition 2.1, areequivalent to the classical DLR equations for the interaction Φ. Indeed, if µ is a DLR measure withrespect to ϕΦ, then for any Λ ⋐ G, any Borel A ⊆ X, and µ-a.e. x ∈ X, we haveµ(A | FΛc)(x) =∑ζ∈AΛ ∑η∈AΛexp(ϕΦ(ζxΛc , ηxΛc))1X(ζxΛc)−1 1A(ζxΛc)=∑ζ∈AΛ ∑η∈AΛexp(HΦΛ (ζxΛc)−HΦΛ (ηxΛc))1X(ηxΛc)−1 1A(ζxΛc)=1ZΦΛ (x)∑ζ∈AΛexp(−HΦΛ (ζxΛc))1A(ζxΛc)whereZΦΛ (x) =∑η∈AΛexp(−HΦΛ (ηxΛc))1X(ηxΛc)By Theorem 2.3.4, if µ satisfies these (classical) DLR equations for Φ, then µ is (ϕΦ,TX)-conformal.2.5 PotentialsIn this section and the next, we restrict to finitely generated groups G satisfying a certain growthcondition. We need this condition in order to construct a cocycle from a potential in a way that iscompatible with interactions, in a sense to be made precise in §2.6. The condition is as follows. Itconcerns the spherical growth function |Bk \ Bk−1|, which is a basic quantity studied in geometricgroup theory, discussed for instance in ([34], §VI.A).Definition 2.5.1 (bounded sphere ratios). Let G be a finitely generated group. With respect to afinite generating set S ⋐ G, we can consider the open balls Bk = {g ∈ G : d(g, e) < n} of radius12k centered at the identity in the Cayley graph of G with respect to S. We say that a group G hasbounded sphere ratios if there exists a finite generating set S such thatsupm≥1|Bm+1 \Bm||Bm \Bm−1| < +∞.In this section and the next, when we refer to balls in a group G with bounded sphere ratios, wealways mean balls with respect to a generating set that witnesses the bounded sphere ratios. Notealso that if G has bounded sphere ratios, then (for some generating set S) we havesupm≥1|Bm+n \Bm+n−1||Bm \Bm−1| < +∞.for any n.Remark 2.5.1. A finitely generated group G has polynomial growth if |Bn| ≤ cnd for some c > 0, d ∈ Nand all n; exponential growth if |Bn| ≥ cαn for some α > 1, c > 0 and all n; and intermediategrowth otherwise. Here we outline certain types of polynomial and exponential growth known to implybounded sphere ratios.In the polynomial case, recall that a group has polynomial growth if and only if it is virtuallynilpotent, i.e. has a finite-index nilpotent group [32]. It is conjectured ([20], Conjecture 10) that forany nilpotent group, we have |Bn| = cnd + O(nd−1), where c > 0 is a constant depending only onthe group, with the coefficients of the lower-order terms depending on the generating set. This wouldimply ([20], Corollary 11) positive constant upper and lower bounds on the ratio |Bk \ Bk−1|/kd−1,and thus that the group has bounded sphere ratios. What is known is more restricted. Associatedto any nilpotent group is its nilpotency class, a number measuring how far the group is from beingabelian (abelian groups, like Zd, have class 1). By a result of Stoll [72], the conjectured asymptoticsfor |Bn| hold at least for groups of nilpotency class at most 2.In the exponential case, we say that a group (with a given generating set) has exact exponentialgrowth if there exist α > 1 and 0 < c < C < cα with c ≤ |Bn|/αn ≤ C for all n ≥ 1. (This is not astandard definition.) This condition is satisfied, for example, by a free group with the usual generatingset. To see that exact exponential growth implies bounded sphere ratios, note that|Bk+1 \Bk||Bk \Bk−1| ≤Cαk+1 − cαkcαk − Cαk−1 =(Cα− ccα− C)α <∞We now turn our attention to potentials. For a function f : X → R and k ≥ 1, define the kthvariation of f asvk(f) := sup{|f(y)− f(x)|∣∣∣x, y ∈ X, xBk = yBk} .We separately define v0(f) = ∥f∥∞. It is also convenient to define B0 = ∅. We define the shell norm∥·∥ShVar by∥f∥ShVar :=∞∑k=0|Bk+1 \Bk|vk(f).We define the space ShReg(X) as the space of shell-regular potentials, i.e., functions f : X → R with∥f∥ShVar < ∞. It is elementary to show that shell-regularity implies continuity, and that ShReg(X),with the shell norm, is a Banach space. Note that this space depends, in general, on the generatingset chosen.Remark 2.5.2. In earlier work on subshifts over Zd [56], the relevant space of potentials is known asSVd(X), the space of potentials with d-summable variation, defined by the norm ∥f∥SVd =∑∞k=1 kd−1vk−1(f).This space is also known as Regd−1(X) [59]. With Bn = Zd ∩ [−n, n]d, we have |Bk+1 \ Bk| =2dd(1 + o(1))kd−1. Thus, on Zd, we have ShReg(X) = SVd(X), with the identity a continuous linearmap.13Proposition 2.5.3. Let G be a group with bounded sphere ratios and X a subshift over G. For anyf ∈ ShReg(X) and any (x, y) ∈ TX , the series∑g∈G[f(g · y)− f(g · x)]converges absolutely and defines a cocycle ϕf on TX .Proof. Fix (x, y) ∈ TX , and let n ≥ 1 be such that xBcn = yBcn . If g ∈ G and m ≥ 1 are such thatBm−1 ⊆ g−1Bcn, then (g · x)|Bm−1 = (g · y)|Bm−1 so |f(g · y) − f(g · x)| ≤ vm−1(f). For m ≥ 1 andg ∈ Bk \ Bk−1, the triangle inequality guarantees that gBm−1 ⊆ Bcn if k − n ≥ m. Since the shellsBk+1 \Bk partition G, we have∑g∈G|f(g · y)− f(g · x)| ≤ 2|Bn|∥f∥∞ +∞∑k=n+1|Bk \Bk−1|vk−n−1(f)≤ 2|Bn|∥f∥∞ +(supk≥1|Bk+n \Bk+n−1||Bk \Bk−1|)∥f∥ShVarso indeed the cocycle is well-defined by an absolutely convergent series.Just as in the case of an interaction, this expression for the cocycle ϕf allows us to rewrite theDLR equations in a more classical form. Let f ∈ ShReg(X). It follows from a simple manipulationthat for any (x, y) ∈ TX , we haveexp(ϕf (x, y)) = limm→+∞ exp ∑g∈Bm[f(g · y)− f(g · x)] = limm→+∞exp fm(y)exp fm(x).where fm(z) =∑g∈Bm f(g · z). Now, let A ⊆ X be a Borel set. If µ is a DLR measure with respectto ϕf , then for µ-a.e. x ∈ X, we haveµ(A | FΛc)(x) =∑η∈AΛ ∑ζ∈AΛexp(ϕf (ηxΛc , ζxΛc))1X(ζxΛc)−1 1A(ηxΛc)=∑η∈AΛ ∑ζ∈AΛlimm→+∞exp fm(ζxΛc)exp fm(ηxΛc)1X(ζxΛc)−1 1A(ηxΛc)= limm→∞∑η∈AΛ exp (fm(ηxΛc))1A(ηxΛc)∑ζ∈AΛ exp (fm(ζxΛc))1X(ζxΛc)These are the DLR equations as found in Kimura [44]. Applying Theorem 2.3.4 therefore showsthat any DLR measure with respect to a potential f ∈ ShReg(X) is necessarily (ϕf ,TX)-conformal,providing the full converse for Kimura’s result described in the introduction.2.6 Potentials induced by interactions, and vice versaWe have seen that the DLR property implies the conformal property for an arbitrary cocycle on theGibbs relation, with Gibbs measures for interactions and for potentials as two special cases. These casesare not independent. In this section, we adapt the methods and results of Muir [59] and Ruelle [66] toconstruct potentials from interactions and vice versa. In this section, all interactions are translation-invariant, i.e., for any Λ ⋐ G and any x ∈ X, we require that ΦgΛ(g ·x) = ΦΛ(x). We recall a classicalspace of particularly well-behaved interactions:14Definition 2.6.1. For an interaction Φ, let∥Φ∥B =∑Λ⋐Ge∈Λ∥ΦΛ∥∞We define B as the space of absolutely summable Φ, i.e., those for which ∥Φ∥B <∞.It is routine to check that (B, ∥ · ∥B) is a Banach space. Moreover, forΦ ∈ B, we in fact haveabsolute convergence of the series defining the cocycle ϕΦ, since for any (x, y) ∈ TX with x∆c = y∆cfor some ∆ ⋐ G, we have ∑Λ⋐G|ΦΛ(x)− ΦΛ(y)| ≤ 2∑Λ⋐GΛ∩∆ ̸=∅∥ΦΛ∥∞≤ 2|∆|∑Λ⋐Ge∈Λ∥ΦΛ∥∞= 2|∆|∥Φ∥B <∞We introduce a family of linear maps that convert interactions into potentials.Definition 2.6.2 (translate-weighting maps). Let (aΛ)Λ⋐G, e∈Λ be a collection of nonnegative realcoefficients such that, for each Λ ⋐ G with e ∈ Λ, we have ∑g∈Λ ag−1Λ = 1. Then, for an interactionΦ, define the potential AΦ viaAΦ(x) = −∑Λ⋐Ge∈ΛaΛΦΛ(x)The map Φ 7→ AΦ is clearly linear. We refer to this map as the translate-weighting map determinedby the weights (aΛ)Λ⋐G,e∈Λ.Remark 2.6.1. Two important examples are the following.• The uniform map, where aΛ ∈ {0, 1|Λ|} for every nonempty Λ ⋐ G. Muir uses the letter A todenote this specific operator, i.e., A(Φ) = AΦ.• The class of dictator maps, where aΛ ∈ {0, 1} for every Λ ⋐ G. For instance, on Zd, Ruellestudies the operator for which aΛ = 1 if and only if 0 is the middle element, or more preciselythe ⌊(|Λ|+ 1)/2⌋-th element, of Λ in lexicographic order. In [59], Muir refers to this operator asAˆ.In Fact 7.8 in [59], it is claimed that AΦ ∈ ShReg(X) for every translate-weighting map and everyΦ ∈ B. This claim is incorrect, as we demonstrate with an example below. However, the argumentpresented for this claim is correct in the case of what Muir calls “cubic-type” interactions. Here wereproduce a version of this proof for a larger class of interactions.Definition 2.6.3. An interaction Φ is full-dimensional if there exists some C > 0 such that, for allΛ ⋐ G with e ∈ Λ and ΦΛ ̸≡ 0, we have the boundsup{|Bn| : n ∈ N, Λ ∩Bcn−1 ̸= ∅} ≤ C|Λ|Proposition 2.6.2. Let G be a group with bounded sphere ratios and let X be a subshift over G.If Φ ∈ B is full-dimensional, then AΦ ∈ ShReg(X), where AΦ is the image of Φ under an arbitrarytranslate-weighting map.15Proof. We first estimate vk−1(AΦ):vk−1(AΦ) = sup∣∣∣∣∣∣∣∑Λ⋐Ge∈ΛaΛ[ΦΛ(x)− ΦΛ(y)]∣∣∣∣∣∣∣ : x, y ∈ X, xBk−1 = yBk−1≤ 2∑Λ⋐Ge∈ΛΛ∩Bck−1 ̸=∅aΛ∥ΦΛ∥∞We can now estimate the shell norm by an exchange of summations:∥AΦ∥ShVar ≤ 2∞∑k=0|Bk+1 \Bk|∑Λ⋐Ge∈ΛΛ∩Bck ̸=∅aΛ∥ΦΛ∥∞= 2∑Λ⋐Ge∈ΛaΛ∥ΦΛ∥∞∑k≥0Λ∩Bck ̸=∅|Bk+1 \Bk|Observe that ∑k≥0Λ∩Bck−1 ̸=∅|Bk+1 \Bk| = sup{|Bn| : n ∈ N, Λ ∩Bcn ̸= ∅} ≤ C|Λ|so in fact∥AΦ∥ShVar ≤ 2C∑Λ⋐Ge∈ΛaΛ|Λ|∥ΦΛ∥∞We need to rearrange this sum. For a given Λ ⋐ G, consider the set of translates of Λ contain-ing the identity, denoted T (Λ) = {g−1Λ, g ∈ Λ}. For instance, in Z, if Λ = {0, 1}, then T (Λ) ={{−1, 0}, {0, 1}}. Let T denote the set of such sets of translates, i.e., T = {T (Λ) : Λ ⋐ G, e ∈ Λ}.Note that T is a partition of the set {Λ ⋐ G, e ∈ Λ}. Observe furthermore that |T | = |Λ| for anyΛ ∈ T .For any given T ∈ T , the value |Λ|∥ΦΛ∥∞ is the same for any Λ ∈ T , i.e., any Λ such that T = T (Λ).so we denote it by cT . We can then express the bound on ∥AΦ∥ShVar by summing over T ∈ T , asfollows: ∑Λ⋐Ge∈ΛaΛ|Λ|∥ΦΛ∥∞ =∑T∈T∑Λ∈TaΛcT=∑T∈TcT∑Λ∈TaΛ=∑T∈TcT=∑T∈T|Λ|∥ΦΛ∥∞=∑T∑Λ∈T∥ΦΛ∥∞= ∥Φ∥BThus ∥AΦ∥ShVar ≤ 2C∥Φ∥B <∞.16In the next example, Φ ∈ B is not full-dimensional, and AΦ is not shell-regular.Example 1. Let X = {0, 1}Z, with Bk = (−k, k)∩Z. Define Φ = (ΦΛ)Λ⋐Z as follows: for any i, j ∈ Z,Φ{i,j}(x) = 1(j−i)2 if xi = xj = 1 and 0 otherwise; and ΦΛ ≡ 0 for all other Λ ⋐ G. Clearly Φ istranslation-invariant. We claim that Φ ∈ B but AΦ /∈ ShReg(X), where AΦ is the image of Φ underthe dictator map that ignores Λ ⋐ Z unless 0 = inf Λ. Indeed, ∥Φ∥B = 2∑∞j=11j2 <∞, butvk(AΦ) =∞∑l=k1l2≥ 1kwhich implies that∥AΦ∥ShVar ≥ 2+∞∑k=11k= +∞We now show that for full-dimensional Φ ∈ B, the images AΦ and A′Φ of Φ under any two translate-weighting maps have the same Gibbs and equilibrium measures.Proposition 2.6.3. Let G be a group with bounded sphere ratios, let X be a subshift on G, and letΦ be an absolutely summable, full-dimensional interaction on X. Then Φ and AΦ induce the samecocycle, i.e., ϕAΦ = ϕΦ, where AΦ is the image of Φ under an arbitrary translate-weighting map.Proof. Suppose that (x, y) ∈ TX with x∆c = y∆c . Observe thatϕΦ(x, y) =∑Λ⋐GΛ∩∆ ̸=∅[ΦΛ(x)− ΦΛ(y)]Consider a translate-weighting map with weights aΛ. To compute ϕAΦ , we first obtain a convenientexpression for AΦ(g · x)−AΦ(g · y):AΦ(g · x)−AΦ(g · y) = −∑Λ⋐Ge∈ΛΛ∩g∆ ̸=∅aΛΦg−1Λ(x) +∑Λ⋐Ge∈ΛΛ∩g∆̸=∅aΛΦg−1Λ(y)= −∑Λ′⋐Gg∈Λ′Λ′∩∆ ̸=∅ag−1Λ′ [ΦΛ′(x)− ΦΛ′(y)]We then compute:ϕAΦ(x, y) =∑g∈G[AΦ(g · x)−AΦ(g · y)]=∑g∈G∑Λ⋐Gg∈ΛΛ∩∆ ̸=∅ag−1Λ[ΦΛ(x)− ΦΛ(y)]=∑Λ⋐GΛ∩∆̸=∅∑g∈Λag−1Λ [ΦΛ(x)− ΦΛ(y)]= ϕΦ(x, y)The interchange of summations is justified by the absolute convergence of the series defining thecocycles ϕAΦ and ϕΦ, implied by the regularity of Φ and AΦ.17Proposition 2.6.3 is similar to Theorem 5.42 in [44], which is stated for Ruelle’s operator A, usingspecifications rather than cocycles.Proposition 2.6.4. Let G be a group with bounded sphere ratios and let X be a subshift on G. Letµ be a G-invariant measure on X, let Φ ∈ B be full-dimensional. Let AΦ be the image of Φ undera translate-weighting map with weights (aΛ)Λ⋐G, e∈Λ. Then the integral∫XAΦ dµ depends only on Φand µ, and not on the weights aΛ.Proof. As in the proof of Proposition 2.6.2, for each finite Λ ⋐ G with e ∈ Λ, let T (Λ) = {g−1Λ | g ∈ Λ}.For any given T , the quantity∫XΦΛ dµ is constant as Λ ranges over T , so we denote it by bT . We nowcompute: ∫XAΦ dµ = −∫X∑T∈T∑Λ∈TaΛΦΛ dµ= −∑T∈TbT∑Λ∈TaΛ= −∑Λ⋐Ge∈Λ1|Λ|∫XΦΛ dµwhich does not depend on the weights aΛ, and in addition clearly expresses the integral∫XAΦ dµ asthe average energy at the identity due to the interaction Φ.To justify exchanging the integral and the sum above, let |Φ| be the interaction given by |Φ|Λ = |ΦΛ|.Then |Φ| is still full-dimensional, with ∥|Φ|∥B = ∥Φ∥B , so−∑T∈T∑Λ∈TaΛ|ΦΛ| = A|Φ| ∈ ShReg(X)by Proposition 2.6.2. Thus the sum converges absolutely to a continuous function.Finally, we introduce a smaller Banach space VolReg(X) of volume-regular functions, defined anal-ogously to ShReg(X) by a volume norm rather than a shell norm. That is, VolReg(X) = {f : X →R : ∥f∥VolVar <∞} where we define∥f∥VolVar :=∞∑k=0|Bk|vk(f)Volume-regularity clearly implies shell-regularity. The following result of Muir ([59], proof of Fact 7.6)is stated for Zd, with the name Regd(X) for VolReg(X), but is valid, with the same proof, on anyfinitely generated group.Theorem 2.6.5. Let G be a finitely generated group and let f ∈ VolReg(X) be a volume-regularpotential. Then there exists an absolutely summable Φ ∈ B with AΦ = f where AΦ is the image of Φunder some dictator map.In particular, any Gibbs measure for f ∈ VolReg(X) is also a Gibbs measure for any potentialΦ ∈ B with AΦ = f , and vice versa.18Chapter 3A Dobrushin-Lanford-Ruelle theorem for irreducible soficshifts3.1 IntroductionAs advertised in the introduction to the dissertation, this chapter proves the equivalence of Gibbs andequilibrium measures for irreducible sofic shifts in one dimension, extending the classical Dobrushin andLanford-Ruelle theorems, using a preservation of Gibbsianness approach. We repeat some definitionsfrom the previous chapter because we are now restricting to the group Z rather than more generalcountable groups, and in order to be clear about the present notation.3.2 Definitions, notations, and conventions3.2.1 Symbolic dynamicsLet A be a finite set with the discrete topology, to be thought of as an alphabet, and AZ be the full shiftwith the product topology, with respect to which AZ is compact and metrizable. The group Z actsnaturally on AZ by the shift action σ, given by (σnx)0 = xn. A shift space is any closed, σ-invariantsubset X ⊆ AZ.For each n ≥ 1, we write Bn(X) to denote the set of words of length n in the language B(X) ofX—that is, the set of patterns w ∈ An such that x[0,n−1] = w for some x ∈ X. For w ∈ An we denoteby [w]i the set of x ∈ X with x[i,i+n−1] = w.We will make extensive use of continuous, shift-equivariant factor codes π : X → Y between shiftspaces X and Y . By the Curtis-Hedlund-Lyndon theorem, any such map π is a sliding block code,induced by a map Π : Bm(X) → B1(Y ) for some m ≥ 1. Up to a conjugacy of X, we can in factassume that Π maps symbols to symbols, i.e., m = 1 ([49], Proposition 1.5.12). When π : X → Y issurjective, it is known as a factor code, and Y is a factor of X.Our main results in this paper concern shifts of finite type and sofic shifts, which we now define.Definition 3.2.1. [shift of finite type] A shift of finite type with alphabet A is any shift space of AZdefined by excluding a finite number of finite words. In other words, X ⊆ AZ is a shift of finite typeif for some n ≥ 1 there exists a finite set F ⊆ An of forbidden words such thatX = {x ∈ AZ : σm(x)[0,n−1] /∈ F , for all m ∈ Z}Definition 3.2.2. [sofic shift] A sofic shift is any shift space that is a continuous factor of a shift offinite type.Sofic shifts have an alternative characterization in terms of bi-infinite walks on finite edge-labeledgraphs (see [49]), but we will not need this here. Every shift of finite type is sofic, since the identitycode is continuous (more generally, conjugacies preserve the class of shifts of finite type), but not every19sofic shift has finite type. An example of a shift that is sofic but not of finite type is the even shift,which is the shift X ⊂ {0, 1}Z consisting of sequences in which 10n1 may appear only if n is even.We will, in particular, consider measures on shift spaces, which will always be Borel probabilitymeasures. We will refer to these as σ-invariant measures to avoid any possible ambiguity, since in§3.4 we also consider measures that are σp-invariant for some positive power p, but in general are notσ-invariant. In particular, we will often refer to ergodic measures, and these will always be ergodicwith respect to σ.3.2.2 The Gibbs relation, cocycles, and Gibbs measuresThe Gibbs relation on a shift space X, also called the tail, asymptotic, or homoclinic relation, is theequivalence relation TX ⊂ X ×X such that (x, y) ∈ TX if and only if x[−N,N ]c = y[−N,N ]c for someN ≥ 1. For Borel sets A,B ⊆ X, a holonomy of TX is a Borel isomorphism ψ : A → B such that(x, ψ(x)) ∈ TX for all x ∈ A. We say that a measure µ on X is TX -nonsingular if for every BorelA ⊂ X with µ(A) = 0, we have µ(TX(A)) = 0, where the saturation TX(A) is defined asTX(A) = {x′ ∈ X : ∃x ∈ A such that (x, x′) ∈ TX}Note that if µ is TX -nonsingular and ψ : A → B is a holonomy of TX , then whenever E ⊂ A hasµ(E) = 0, we have µ(ψ(E)) ≤ µ(TX(E)) = 0. In particular, the Radon-Nikodym derivative d(µ◦ψ)dµ iswell-defined.We note that TX is generated by a countable group Γ of holonomies, in the sense that (x, x′) ∈ TXif and only if there exists γ ∈ Γ with γ(x) = x′. This is a special case of the main theorem of [30].One could choose Γ consisting of holonomies of the form ψu,v,a,b, where u, v ∈ Bb−a+1(X), for somea, b ∈ Z with a ≤ b, andψu,v,a,b(x) =x(−∞,a)ux(b,∞), if x[a,b] = v and x(−∞,a)ux(b,∞) ∈ Xx(−∞,a)vx(b,∞), if x[a,b] = u and x(−∞,a)vx(b,∞) ∈ Xx, otherwiseThat is, ψu,v,a,b replaces u with v, or vice versa, whenever possible, and otherwise does nothing.A (real, additive) cocycle on TX is a Borel measurable function ϕ : TX → R such that ϕ(x, y) +ϕ(y, z) = ϕ(x, z) for all x, y, z ∈ X with (x, y), (y, z) ∈ TX (so that (x, z) ∈ TX as well). By expo-nentiating or taking logarithms, we can easily convert between additive and multiplicative notationfor cocycles. Additive notation is more natural when the cocycle is intended to represent an energy-difference function, and multiplicative notation is more natural when the cocycle serves as a Jacobianfor a change of variables.Given a TX -nonsingular measure µ on X, we say that a Borel function Dµ,TX : TX → R+ isa (multiplicative) Radon-Nikodym cocycle on TX with respect to µ if the pushforward of µ by anyholonomy ψ : A → B of TX satisfies d(µ◦ψ)dµ (x) = Dµ,TX (x, ψ(x)) for µ-a.e. x ∈ A. It is routine toshow that any TX -nonsingular measure µ on X has a µ-a.e. unique Radon-Nikodym cocycle.Definition 3.2.3. [Gibbs measure] Let µ be a TX -nonsingular Borel measure on a shift space X, andlet ϕ : TX → R be a cocycle. We say that µ is a Gibbs measure if for any holonomy ψ : A→ B of TX ,and µ-a.e. x ∈ A, we have Dµ,TX (x, ψ(x)) = exp(ϕ(x, ψ(x))).To put it another way, a measure is by definition Gibbs if and only if it is nonsingular, anda nonsingular measure is Gibbs precisely with respect to the logarithm of its own Radon-Nikodymcocycle. These measures are also known as conformal measures in the literature [15, 56].In [15] it is shown, building on results of Kimura [44], Keller [42], and others, that the definition ofa Gibbs measure that we have given is equivalent to another well-known one involving the Dobrushin-Lanford-Ruelle equations, in terms of which the theorems of Dobrushin (Theorem 3.4.2) and Lanford-Ruelle (Theorem 3.4.3) were originally stated. These Gibbs measures do not coincide, in general,with Gibbs measures in the sense of Bowen; see the second remark after Proposition 3.3.7 for furtherdiscussion.203.3 Preservation of GibbsiannessIn this section, we prove a pair of preservation of Gibbsianness results, namely Propositions 3.3.7 and3.3.10, which are essential to our main theorems, Theorem 3.4.7 and 3.4.11.Definition 3.3.1. [irreducibility] A shift space X is irreducible if for every ordered pair of blocksu, v ∈ B(X) there is w ∈ B(X) so that uwv ∈ B(X).Definition 3.3.2. [period] The period of an irreducible sofic shift is the greatest common divisor ofthe least periods of its periodic points.Definition 3.3.3. [strong irreducibility] A shift space X is strongly irreducible if there exists somer ≥ 1 such that for any u, v ∈ B(X) and any s ≥ r, there exists w ∈ Bs(X) with uwv ∈ B(X).Remark 3.3.1. A shift of finite type is strongly irreducible if and only if it is topologically mixing, ifand only if it is irreducible and has period 1.The following proposition generalizes part of the proof of Lemma 4.1 in [55]. (They treat the caseof a uniform Gibbs measure on a strongly irreducible shift of finite type over Zd.) The proof is alsovery similar to that of Proposition 5.2 in [53].Proposition 3.3.2. Let X be a strongly irreducible shift space. Then any TX-invariant nonsingularmeasure on X has full support.Proof. Let µ be a TX -invariant nonsingular measure on X. Let r ≥ 1 be a witness for the strongirreducibility of X. Fix a, b ∈ Z with a < b, and fix w ∈ Bb−a(X). By strong irreducibility, for eachn ≥ 1 and each p, s ∈ Bn(X), there exists w′ ∈ B(b−a)+2r(X) such that w′[a,b] = w and pw′s ∈ B(X).By compactness, it follows that for every x ∈ X, there exists some u ∈ B(X) with u[a,b] = w andx(−∞,a−r−1]ux[b+r+1,∞) ∈ X.For each pair u, v ∈ B(b−a)+2r+1(X) with u[a,b] = w, letEu,v = [v]a−r ∩ {x ∈ X : x(−∞,a−r−1]ux[b+r+1,∞) ∈ X}Then⋃u,v Eu,v = X. In particular, µ(Eu,v) > 0 for at least one pair u, v. Let ψu,v,a,b be the holonomyof TX that exchanges u and v on [a, b] when possible and does nothing else, as in §3.2.2. By thedefinition of Eu,v, we have that for every x ∈ Eu,v, ψu,v,a,b(x) ∈ [u]a−r. Then we haveµ([w]a) ≥ µ([u]a−r)≥ µ(ψu,v,a,b(Eu,v))=∫Eu,vDµ,TX (x, ψu,v,a,b(x)) dµ(x)> 0Since w was an arbitrary word at an arbitrary position, µ has full support.Remark 3.3.3. The statement and proof of Proposition 3.3.2 generalize essentially without modifi-cation when Z is replaced by an arbitrary countable group, with a suitable generalization of strongirreducibility [23, 9]. We also mention that strong irreducibility is used in the proof of Proposition3.3.2 to show that all TX equivalence classes are dense in X. These equivalence classes are the orbitsof the action of the countable group Γ generating TX . In the special case of a shift of finite type, Γcan be taken to be generated by homeomorphisms [56]. We can thus interpret Proposition 3.3.2 as thestatement that a nonsingular measure for a minimal continuous action must have full support.Definition 3.3.4. [doubly transitive point] Let X be a shift space. A point x ∈ X is doubly transitiveif every word w ∈ B(X) appears in x infinitely often to the left and to the right.21It is easy to check that a shift space X contains a doubly transitive point if and only if X isirreducible (see §9.1, [49] for more details). The following lemma will also be useful.Lemma 3.3.4. Let X be a shift space. Then the set DX ⊂ X of doubly transitive points is TX-invariant.Proof. If X is not irreducible then DX = ∅, which is trivially TX -invariant, so assume that X isirreducible. Let x ∈ DX and suppose that x′ ∈ X with (x, x′) ∈ TX . Then there exists some∆ = [a, b]∩Z such that x∆c = x′∆c . Since x ∈ DX , every word w ∈ B(X) appears infinitely often bothin x(−∞,a−1] = x′(−∞,a−1] and in x[b+1,∞) = x′[b+1,∞). Therefore x′ ∈ DX .It is then immediate that X \DX is also TX -invariant. (In general, if R is an equivalence relationon X and A is an R-invariant subset, then Ac is also R-invariant.)The following is a generalization of Theorem 9.4.9 in [49], which appears to be well-known ([78],proof of Lemma 4.5). We thank Tom Meyerovitch for this short proof.Proposition 3.3.5. Let X be an irreducible shift space and let µ be a fully supported σ-invariantergodic measure on X. Let DX denote the set of doubly transitive points. Then µ(DX) = 1.Proof. Recall that a generic point, for a continuous transformation of a compact space with an σ-invariant measure, is a point that satisfies the conclusion of the pointwise ergodic theorem (Theorem1.14, [76]) for every continuous function. Since µ is ergodic with respect to σ, the sets of genericpoints with respect to σ and σ−1 have full measure ([31], Proposition 3.7), so their intersection has fullmeasure as well. Since µ has full support, every point that is generic for both σ and σ−1 (in particular,almost every point in X) is doubly transitive. In greater detail: we prove the contrapositive. Supposex is not doubly transitive. Then there is a word w which appears at most finitely often, without lossof generality to the right, in x. Thenlimn→∞1nn−1∑k=01[w]0(σkx) = 0 ̸= µ([w]0)so x does not satisfy the conclusion of the ergodic theorem for the continuous function 1[w]0 . Thereforex is not generic for σ.Let X be a shift of finite type, let Y be a sofic shift, and let π : X → Y be a finite-to-one factorcode. Then there is an integer d ≥ 1, known as the degree of π, such that each doubly transitive pointy ∈ Y has exactly d π-preimages [49]. An important special case is when the degree is one, which isin fact equivalent to the following condition, which a priori might seem more general.Definition 3.3.5. [almost invertibility] Let X be an irreducible shift of finite type, let Y be anirreducible sofic shift, and let π : X → Y be a factor code. We say that π is almost invertible if everydoubly transitive point y ∈ DY has a unique preimage.Remark 3.3.6. A factor code on an irreducible shift of finite type is almost invertible if and only if itis finite-to-one with degree one ([49], Proposition 9.2.2).The following is our first preservation of Gibbsianness result.Proposition 3.3.7 (preservation of Gibbsianness for almost invertible factor codes). Let X be anirreducible shift of finite type, let Y be a sofic shift, and let π : X → Y be an almost invertible factorcode. Let µ be a measure on X which is fully supported, σ-invariant, ergodic, and TX-nonsingular.Let ν = π∗µ. Then ν is TY -nonsingular. Moreover, if µ is Gibbs with respect to an additive cocycle ϕ,then ν is Gibbs with respect to ϕ ◦ (π−1 × π−1), where π−1 is well-defined ν-almost everywhere.22Proof. First, for a technical reason described below, we assume that π is a one-block code, in the sensethat it is induced by a map Π: B1(X)→ B1(Y ). We assume further that it has a magic symbol—thatis, a symbol b ∈ B1(Y ) with a unique Π-preimage a ∈ B1(X), such that if π(x) = y and y0 = b, thenx0 = a. These assumptions incur no loss of generality ([49], §9.1).These assumptions made, we see how to lift holonomies of TY to holonomies of TX . Since π isa Borel map between complete separable metric spaces X,Y which restricts to an injection on theBorel set DX , the inverse π|−1DX : DY → DX is Borel ([40], Theorem 15.1). Now let ψ : A → B be aholonomy of TY . Define the map ψ˜ : π−1(A)∩DX → π−1(B)∩DX by ψ˜ = π−1 ◦ψ ◦ π; this is clearlya measurable bijection.Moreover, to see that (x, ψ˜(x)) ∈ TX for each x ∈ π−1(A) ∩DX , observe that (π(x), π ◦ ψ˜(x)) =(π(x), ψ ◦ π(x)) ∈ TY , so there exist m < n with π(x)[m,n]c = ψ ◦ π(x)[m,n]c . Since π(x) and ψ ◦ π(x)are doubly transitive, the magic symbol b for π appears infinitely often to the left and right. We maytherefore assume, by taking m and n larger if necessary, thatπ(x)m−1 = ψ ◦ π(x)m−1 = b = π(x)n+1 = ψ ◦ π(x)n+1Moreover, since the magic symbol occurs infinitely often to the left and right, any word outside [m,n]appears within a word beginning and ending with b. Proposition 9.1.9 in [49] asserts, in the almostinvertible case, that such a word has a unique π-preimage. This shows that (x, ψ˜(x)) agree outside of[m,n], so ψ˜ is indeed a holonomy of TX .Now, let ΓX ,ΓY be countable groups of holonomies generating TX ,TY respectively, and let A ⊂ Ybe Borel with ν(A) = 0. Observe that TY (A) =⋃γ∈ΓY γ(A). Observe further that, for each γ ∈ ΓY ,ν(γ(A)) = ν(γ(A) \DY ) + ν(γ(A) ∩DY )= µ(π−1(γ(A) ∩DY ))= µ(γ˜(π−1(A ∩DY )))= 0since π−1(A ∩DY ) is µ-null and µ is TX -nonsingular. Therefore ν is indeed TY -nonsingular.Again, let ψ : A→ B be a holonomy of TY and let ψ˜ be as above. Thenν(B) = µ(π−1(ψ(A ∩DY )))= µ(ψ˜(π−1(A) ∩DX))=∫π−1(A)∩DXDµ,TX (x, ψ˜(x)) dµ(x)=∫A∩DYDµ,TX (π−1(y), π−1(ψ(y))) dν(y),where the last equality follows from the change of variables formula.On the other hand, since ν is TY -nonsingular, we know thatν(B) =∫ADµ,TY (y, ψ(y)) dν(y)By the uniqueness of the Radon-Nikodym derivative, we then have, for almost all (y, y′) ∈ D2Y ∩ TY ,that Dν,TY (y, y′) = Dµ,TX (π−1(y), π−1(y′)).Remark 3.3.8. In Corollary 3.4.10, we generalize Proposition 3.3.7 from almost invertible to finite-to-one codes, in the case that the cocycle on the range is induced by a sufficiently regular potential. Itis therefore natural to ask whether the proof of Proposition 3.3.7 can be adapted to the finite-to-onesetting. However, such an adaptation would not be straightforward, because at higher degrees we losea key condition on which the proof of Proposition 3.3.7 relied: namely, that preimages of asymptotic23doubly transitive points must themselves be asymptotic. Indeed, if π has degree d > 1, then everydoubly transitive point y ∈ Y has d preimages, no two of which ever exhibit the same symbol in thesame position (see Exercise 9.1.3, [49]), and are therefore about as far from asymptotic as one couldimagine.Remark 3.3.9. The hypotheses of Proposition 3.3.7 are likely more restrictive than would be neededsimply to show that the pushforward of a TX -nonsingular measure is TY -nonsingular. The reason isthat, for the application in Theorem 3.4.7, we need pointwise control over the potential inducing theRadon-Nikodym cocycle of the pushforward measure, whereas for the purposes of [64], for instance,it is sufficient to determine the potential’s regularity. For instance, consider a very simple symbolamalgamation code from the full 3-shift X = {0, 1, 2}Z to the full 2-shift Y = {0, 1}Z, given byamalgamating the symbols 1, 2 into the symbol 1. This code takes the uniform Bernoulli measure onX, which is Gibbs for the zero cocycle, to the (1/3, 2/3) Bernoulli measure on Y , which is Gibbs withrespect to a cocycle obtained from a locally constant potential. This would count as preservation ofGibbsianness in the sense of [64] but not in ours.We now prove Proposition 3.3.10, which is a converse result to Proposition 3.3.7, showing that everynonsingular measure on an irreducible sofic shift is the pushforward, through an almost invertible code,of a nonsingular measure on an irreducible shift of finite type. We observe that an almost invertiblefactor code π : X → Y yields a Borel isomorphism πDX : DX → DY , so a fully supported σ-invariantmeasure ν on Y lifts to a unique measure µ on X, giving an isomorphism of measure-preservingsystems. In particular, if ν is ergodic, then so is µ.Proposition 3.3.10 (lifting Gibbs measures through almost invertible factor codes). Let X be anirreducible shift of finite type, let Y be a sofic shift, and let π : X → Y be an almost invertible factorcode. Let ν be a measure on Y which is fully supported, σ-invariant, ergodic, and TY -nonsingular. Ifν is Gibbs for an additive cocycle ϕ, then the unique σ-invariant measure µ on X with π∗µ = ν isTX-nonsingular and, in particular, is a σ-invariant Gibbs measure for ϕ ◦ (π × π).Proof. As in the proof of Proposition 3.3.7, we assume without loss of generality (that is, up to aconjugacy of X) that π is a one-block code, induced by a block map Π : B1(X)→ B1(Y ). We assumefurther that π has a magic symbol b ∈ B1(Y ), which has a unique Π-preimage a ∈ B1(X).Since π : DX → DY is a Borel isomorphism and ν(DY ) = 1 by Proposition 3.3.5, there is a uniquemeasure µ on X with π∗µ = ν, and µ is σ-invariant and ergodic. We now show that µ has full support.Let w ∈ B(X) be arbitrary. By irreducibility, there exist u, v ∈ B(X) such that auwva ∈ B(X). Lets = Π(uwv), so that, by the same argument as in the proof of Proposition 3.3.7 (using [49], §9.1),[auwva]0 = π−1([bsb]0). Since ν has full support by hypothesis, ν([bsb]0) > 0, so µ([w]0) > 0, since[auwva] ⊆ [w], with coordinates lined up appropriately. Since w was arbitrary and µ is σ-invariant, µhas full support.Let ψ : X → X be a holonomy of TX . As in the proof of Proposition 3.3.7 (but with the holonomiesbeing pushed in the opposite direction), π forms a Borel isomorphism between DX and DY , and ifx, x′ ∈ DX then (x, x′) ∈ TX if and only if (π(x), π(x′)) ∈ TY . Therefore, we have a holonomyψ˜ = π ◦ ψ ◦ (π|DX )−1 : DY → DY of TY .Let N ⊂ X be a Borel set with µ-measure zero. Observe thatψ(N) = ψ(N ∩DX) ∪ ψ(N \DX)This yields that µ(ψ(N)) = µ(ψ(N) ∩ DX), since ψ(N \ DX) = ψ(N) \ DX , and DX has fullmeasure by ergodicity and Proposition 3.3.5. Moreover,ψ(N ∩DX) = π−1 ◦ ψ˜(π(N) ∩DY )Now, ν(π(N)∩DY ) = µ(N ∩DX) = 0, so ν(ψ˜(π(N)∩DY )) = 0, since ν is TY -nonsingular. Thereforeµ(ψ(N ∩DX)) = 0 as well, so in fact µ(ψ(N)) = 0, which shows that µ is indeed TX -nonsingular. Acalculation in the same spirit, very similar to the calculation that concludes the proof of Proposition3.3.7, shows that µ is Gibbs for ϕ ◦ (π × π), as claimed.243.4 Equilibrium measuresDefinition 3.4.1. [topological pressure and equilibrium states] Let X be a shift space and let f : X →R be a continuous function. The topological pressure of f is the valuePX(σ, f) = sup{h(µ) +∫Xf dµ}where the supremum is over all σ-invariant measures µ on X. Any measure µ attaining the supremumis known as an equilibrium measure for f .Remark 3.4.1. The pressure is sometimes defined as above (see [42]), but is often defined differently(see e.g. [76]), with the variational property by which we defined it stated as a theorem. However, thisvariational property is the only one we will need, apart from the two classical theorems below.Definition 3.4.2. [the function space SV(X)] LetX be a shift space and let f : X → R be a continuousfunction. We define the kth variation of f asvk(f) = sup{|f(x)− f(y)| : x[−k,k] = y[−k,k]}for k ≥ 0; it is convenient to define var−1(f) = ∥f∥∞. We then define∥f∥SV(X) =∞∑k=0vk−1(f)and define the class of potentials SV(X) = {f ∈ C(X) : ∥f∥SV(X) <∞}.It is easy to verify that(SV(X), ∥·∥SV(X))is a Banach space, and that ([56], [15]) a potentialf ∈ SV(X) defines a cocycle ϕf on TX via the following absolutely convergent series:ϕf (x, y) =∑n∈Z[f(σny)− f(σnx)]We refer to a Gibbs measure for ϕf simply as a Gibbs measure for f . With this definition, werecall the following classical theorems, which we state only for the special cases that we require. Thesetheorems were originally proved in a somewhat different form, using the formalism of interactionsrather than potentials as we have used, but the methods adapt easily.Theorem 3.4.2 (Dobrushin; see [66]). Let X be a strongly irreducible shift space and let f ∈ SV(X).Every σ-invariant Gibbs measure for f is an equilibrium measure for f .Theorem 3.4.3 (Lanford-Ruelle; see [56]). Let X be a shift of finite type and let f ∈ SV(X). Everyequilibrium measure for f is a Gibbs measure for f .We also require the following result, closely following Lemma 4.5 in [78].Proposition 3.4.4. Let X be an irreducible shift of finite type. Any equilibrium measure for f ∈SV(X) has full support.Proof. When X is a mixing shift of finite type, the result follows from Theorem 3.4.3 and Proposition3.3.2. Now, let X be an irreducible shift of finite type such that X has period p. We decompose Xinto p cyclically moving classes (see [49], §4.5), i.e., X = ⊔p−1i=0Xi where σ(Xi) = Xi+1 mod p and eachXi is mixing with respect to σp. In particular, σp is a homeomorphism of each clopen set Xi; thesystem (X,σp) is known as the pth higher power shift of X ([49], §1.4).There is a bijection between σ-invariant measures µ on X and σp-invariant measures µ′ on X0,which is given by normalized restriction in one direction and averaging in the other. That is, we take25µ′ = pµ|X0 and µ = p−1∑p−1j=0 σj∗µ′. Observe that µ has full support if and only if µ′ does. Moreover,we havehX(µ) +∫Xf dµ =1p(hX0(µ′) +∫X0Rpf dµ′)where Rpf =∑p−1j=0 f ◦ σ−j . Therefore µ is an equilibrium measure for f on X precisely when µ′ is anequilibrium measure for Rpf on X0. So far, our discussion is essentially identical to Yoo’s.We now need to show that Rpf ∈ SV(X0); this is where we part from Yoo, who considers a differentclass of potentials. Observe that, for each j ∈ {0, . . . , p − 1}, the k-th variation of a function on X0behaves like the kp-th variation of that function on X, so we have∥∥f ◦ σ−j∥∥SV(X0)≤∞∑k=0vkp(f ◦ σ−j) ≤∥∥f ◦ σ−j∥∥SV(X)It is also easy to check that SV(X) is closed under translation, showing that indeed Rpf ∈ SV(X0).Let µ be an equilibrium measure for f . Then the unique µ′ on X0 such that µ = p−1∑p−1j=0 σj∗µ′ isan equilibrium measure for Rpf ; since X0 is mixing, µ′ is fully supported. Thus µ is fully supportedas well.We also require a result showing that equilibrium measures lift through almost invertible codes,indeed through any finite-to-one codes. We first prove the following lemma, which is well-known,and can be regarded as a relative version of the Krylov-Bogliubov theorem. One standard proofuses the Hahn-Banach theorem. For completeness, and possibly independent interest, we include adifferent proof, based on the standard proof of the (non-relative) Krylov-Bogliubov theorem [76]. TheHahn-Banach argument requires no dynamical assumptions at all, whereas our argument relies on thedynamical setting to make the argument somewhat more constructive. We state it only for ergodicmeasures on shift spaces; the argument goes through for any continuous transformation of a compactmetric space, and it easily generalizes to any σ-invariant measure by convexity.Lemma 3.4.5. Let X and Y be shift spaces, let π : X → Y be a factor code, and let ν be a σ-invariantmeasure on Y . Then there exists a σ-invariant measure µ on X with π∗µ = ν. If ν is ergodic then µcan be chosen to be ergodic as well.Proof. Let y ∈ Y be a generic point with a preimage x ∈ X, and let νn = 1n∑n−1k=0 δy ◦ σ−k be the nthempirical measure for y. By the ergodic theorem, νn converges to ν in the weak-∗ topology. Similarly,let µn =1n∑n−1k=0 δx ◦ σ−k, and appeal to compactness to extract a weak-∗ convergent subsequencewith limit µ. It is not hard to see that µ must be σ-invariant (since ∥µn−µn ◦σ∥TV ≤ 2/n). Moreover,since νn = π∗µn and the pushforward operation is continuous, we conclude that π∗µ = ν. The factthat µ can be chosen to be ergodic follows by a standard convexity argument (see [70], Chapter 8).Lemma 3.4.6. Let X be an irreducible shift of finite type, Y a sofic shift, and π : X → Y a finite-to-one factor code. Let f : Y → R be a function with summable variation, that is, f ∈ SV(Y ), and let ν bean equilibrium measure for f . Then any σ-invariant measure µ on X with π∗µ = ν is an equilibriummeasure is an equilibrium measure µ for f ◦ π; in particular, there exists an equilibrium measure µ forf ◦ π ∈ SV(X) with π∗µ = ν. If ν is ergodic, then µ can be chosen to be ergodic as well.Proof. By Lemma 3.4.5, there exists a σ-invariant measure µ on X with π∗µ = ν, and we can chooseµ to be ergodic whenever ν is ergodic. We now show that any such µ is an equilibrium measure forf ◦ π. Since π is finite-to-one, the Abramov-Rokhlin formula [1] shows that h(µ) = h(ν). Thenh(µ) +∫Xf ◦ π dµ = h(ν) +∫Yf dν = PY (σ, f)26We need to show that PX(σ, f ◦ π) = PY (σ, f). Clearly PX(σ, f ◦ π) ≥ PY (σ, f), so we only need thereverse inequality. Let λ be any σ-invariant measure on X. Again h(π∗λ) = h(λ) by the Abramov-Rokhlin formula, so we haveh(λ) +∫Xf ◦ π dλ = h(π∗λ) +∫Yf dπ∗λ ≤ PY (f)Therefore PX(σ, f ◦ π) = PY (σ, f), so µ is indeed an equilibrium measure for f ◦ π.We can now state and prove the first main result of this section.Theorem 3.4.7 (Lanford-Ruelle theorem for irreducible sofic shifts). Let Y be an irreducible soficshift and let f : Y → R be a potential with summable variation, that is, f ∈ SV (Y ). Let ν be anequilibrium measure for f . Then ν is a Gibbs measure for f .Proof. Since Y is an irreducible sofic shift, there exist an irreducible shift of finite type X and analmost invertible factor code π : X → Y , for instance the minimal right-resolving presentation ([49],§3.3, §9.2).Suppose first that ν is ergodic. By Lemma 3.4.6, there exists an ergodic equilibrium measure µ forf ◦ π such that ν = π∗µ. Then, by Theorem 3.4.3, µ is a Gibbs measure for f ◦ π, and by Proposition3.4.4, µ has full support. Then, by Proposition 3.3.7, which requires ergodicity and full support, ν isa Gibbs measure for f .The general result follows from the ergodic case via the Krein-Milman theorem [70], together withthe compactness and convexity of the sets of Gibbs and equilibrium measures [42] and the fact thatthe extreme points of these sets are precisely their ergodic elements.We now change course and proceed towards a Dobrushin type theorem for irreducible sofic shifts,which is the second main result of this section.Lemma 3.4.8. Let X be an irreducible shift of finite type of period p, partitioned into p cyclicallymoving classes Xi, 0 ≤ i ≤ p − 1. Then any TX-equivalence class is contained in a single cyclicallymoving class. That is, if x ∈ Xi and x′ ∈ Xj with (x, x′) ∈ TX , then i = j.Proof. Suppose without loss of generality that X is an edge shift with alphabet A = B1(X). Then Acan be partitioned into p subsets Ai, 0 ≤ i ≤ p− 1, corresponding to the cyclically moving classes Xi,such that for any x ∈ X, x ∈ Xi if and only if x ∈ Ai. Thus for x, x′ ∈ X, if xn = x′n for some n,then x, x′ are in the same cyclically moving class. But if (x, x′) ∈ TX then xn = x′n for all but finitelymany n, so in particular x and x′ are in the same cyclically moving class.Lemma 3.4.9 (Dobrushin theorem for irreducible shifts of finite type). Let X be an irreducible shiftof finite type and f : X → R be a potential with summable variation, that is f ∈ SV (X). Then everyσ-invariant Gibbs measure for f is an equilibrium measure for f .Proof. Let X have period p and let X0, . . . , Xp−1 be the cyclically moving classes of X as in the proofof Proposition 3.4.4. Note that each Xi, 0 ≤ i ≤ p − 1 is TX -invariant and that we can regard eachone as a mixing shift of finite type with alphabet a subset of Bp(X), so that it is meaningful to speakof the Gibbs relations TXi . Moreover, since each class Xi is TX -invariant, we have for each i that TXiis simply the restriction of TX to Xi ×Xi.Let µ be a Gibbs measure for f and µ′ be the normalized restriction of µ of X to X0, i.e., µ′(E) =pµ(E) for any Borel set E ⊆ X0. Lemma 3.4.8 shows that every holonomy ψ : A→ B of TX restrictsto a holonomy ψ0 : A ∩X0 → B ∩X0 of the relation TX0 . Moreover, every holonomy of TX0 clearlyarises as such a restriction: if ψ0 is a holonomy of TX0 , ψ0 = ψ|X0 where ψ|Xi = σi◦ψ0◦σ−i. Thereforethe measure µ′ inherits the Gibbsianness of µ, with respect to Rpf =∑p−1j=0 f ◦ σj . Since each Xi,270 ≤ i ≤ p− 1 is a mixing shift of finite type, therefore strongly irreducible, Theorem 3.4.2 shows thatµ′ is an equilibrium measure for Rpf . As in the proof of Proposition 3.4.4, we havehX(µ) +∫Xf dµ =1p(hX0(µ′) +∫X0Rpf dµ′),which concludes that µ is an equilibrium measure for f .The next corollary generalizes Proposition 3.3.7 from almost invertible codes to finite-to-one codes,in the case of a cocycle induced by a sufficiently regular potential. As discussed in §3.3, the prooftechnique that we used for Proposition 3.3.7 does not generalize to higher degrees. To obtain Corollary3.4.10, we apply Theorem 3.4.7, even though the statement of Corollary 3.4.10 does not mentionequilibrium measures explicitly.Corollary 3.4.10 (preservation of Gibbsianness for finite-to-one factor codes). Let X be an irreducibleshift of finite type and Y an irreducible sofic shift. Let π : X → Y be a finite-to-one factor code, letf : Y → R be a potential with summable variation, that is, f ∈ SV (Y ), and let µ be a σ-invariantGibbs measure for f ◦ π. Then ν = π∗µ is a Gibbs measure for f .Proof. First note that µ is an equilibrium measure for f ◦ π by Lemma 3.4.9. Since π is finite-to-one,ν is an equilibrium measure for f ([78], Lemma 4.4), so by Theorem 3.4.7, ν is Gibbs for f .While Corollary 3.4.10 may look like it generalizes Proposition 3.3.7 in that µ need no longer beergodic and π need no longer have degree one. However, the cocycle in Proposition 3.3.7 need not apriori be induced by the pullback of a potential with summable variation. Corollary 3.4.10 thereforegeneralizes Proposition 3.3.7 only in this special case.Theorem 3.4.11 (Dobrushin theorem for irreducible sofic shifts). Let Y be an irreducible sofic shiftand let f : Y → R be a potential with summable variation, that is, f ∈ SV (Y ). Let ν be a σ-invariantGibbs measure for f . Then ν is an equilibrium measure for f .Proof. First suppose that ν is ergodic. Let π : X → Y be the minimal right-resolving presentation ofY . By Lemma 3.3.10, there exists an ergodic σ-invariant Gibbs measure µ for f ◦ π with π∗µ = ν.By Lemma 3.4.9, µ is an equilibrium measure for f ◦ π. Finally, again by Lemma 4.4 in [78], ν is anequilibrium measure for f . The result for general (not necessarily ergodic) ν follows from the ergodiccase by compactness and convexity as in the proof of Theorem 3.4.7.Taken together, Theorems 3.4.7 and 3.4.11 show that for a potential with summable variations onan irreducible sofic shift, the equilibrium measures are precisely the σ-invariant Gibbs measures.Finally, we can use Theorem 3.4.11 to generalize Proposition 3.3.10 from almost invertible to finite-to-one codes, in the same special case for which Corollary 3.4.10 generalizes Proposition 3.3.7.Corollary 3.4.12 (lifting Gibbs measures through almost invertible factor codes). Let X be an irre-ducible shift of finite type and Y an irreducible sofic shift. Let π : X → Y be a finite-to-one factor code,let f : Y → R be a potential with summable variation, that is, f ∈ SV (Y ), and let ν be a σ-invariantGibbs measure for f . Then there exists a σ-invariant Gibbs measure µ for f ◦ π with π∗µ = ν.Proof. By Theorem 3.4.11, ν is an equilibrium measure for f . By Lemma 3.4.6, there is an equilibriummeasure µ for f ◦ π with π∗µ = ν. By Theorem 3.4.3, µ is a Gibbs measure for f ◦ π, and is certainlyσ-invariant.In closing, we note that it is an open problem to determine the existence of a finite-to-one factorcode from a given shift of finite type X onto a given sofic shift Y , as in the hypotheses of Corollaries3.4.10 and 3.4.12. Equal entropy is necessary, but there are additional necessary conditions; see [49],§12.2.28Chapter 4The road problem and homomorphisms of directed graphs4.1 IntroductionIn §4.2, we recall and adapt standard material on graphs and homomorphisms. In §4.3, we define thestability relation for a right-resolver, give its main structural properties, and relate it to synchroniza-tion. In §4.4, we recall from [6] the connection between the road problem and the O(G) conjecture,and state our generalization of the road colouring theorem.In §4.5, we introduce the concepts of bunchiness and almost bunchiness and present results involvingthem, including the O(G) conjecture for bunchy and almost bunchy graphs and the universal propertyof the fiber product. In §4.6, we pose the bunchy factor conjecture, which has several equivalentformulations, and discuss its relation to the O(G) conjecture and the road problem. In §4.7, wegive polynomial-time algorithms for construction and decision problems involving right-resolvers, anddiscuss the algorithmic implications of the O(G) and bunchy factor conjectures.The proofs of many results in §§4.2–4.7, comprising the structural properties of right-resolvers, aredeferred to §4.8. The proof of our generalization of the road colouring theorem is deferred to §4.9.4.2 Graphs and graph homomorphisms4.2.1 Basic definitionsWe take all graphs to be finite and directed. A graph G consists of a set V (G) of states, or vertices,and a set E(G) of edges, together with a pair of maps s, t : E(G)→ V (G) giving the source and targetof each edge. Loops (edges e with s(e) = t(e)) and parallel edges (distinct edges e, e′ with s(e) = s(e′),t(e) = t(e′)) are allowed. For I ∈ V (G), we write EI(G) = s−1(I) for the set of outgoing edges from I.We write F (I) = t(EI(G)) for the set of follower states of I, and we write EIJ(G) = s−1(I) ∩ t−1(J)for the set of edges from I to J . We write L(G) for the language of G, i.e. the set of finite edgepaths in G, i.e. e1e2 . . . en where t(ei) = s(ei+1), 1 ≤ i ≤ n− 1. We also refer to elements of L(G) aswords. The maps s, t extend to s, t : L(G) → V (G) by s(e1 . . . en) = s(e1), t(e1 . . . en) = t(en). Wedefine LI(G) = {u ∈ L(G) | s(u) = I}, and LIJ(G) = {u ∈ LI(G) | t(u) = J}. A cycle in G is a pathu ∈ L(G) with s(u) = t(u), i.e. an element of LII(G) for some I ∈ V (G).A graph homomorphism Φ : G → H is a pair of maps Φ : E(G) → E(H), ∂Φ : V (G) → V (H)such that s ◦ Φ = ∂Φ ◦ s and t ◦ Φ = ∂Φ ◦ t. If there is a surjective homomorphism from G to H,then we say that H is a factor of G, and that G is an extension of H. Observe that every factor of astrongly connected graph is strongly connected. A graph homomorphism Φ : G → H induces a mapL(G)→ L(H) (also written Φ) in the obvious way.A graph isomorphism is a homomorphism that is injective and surjective (i.e. on both edges andstates), and an automorphism of a graph G is an isomorphism from G to itself. We denote the groupof automorphisms of G by Aut(G), and by P (G) the (normal) subgroup of Aut(G) which acts triviallyon states and permutes parallel edges. We generally identify isomorphic graphs, and use the symbol29= to denote isomorphism, except when discussing algorithms for deciding isomorphism, or confirmingthat the automorphism group of a given graph is trivial.We now introduce the class of homomorphisms with which we are concerned.Definition 4.2.1 (right-resolver). Let G,H be graphs. Let Φ : G → H be a surjective graph ho-momorphism. We say that Φ is right-resolving, or is a right-resolver, if, for each I ∈ V (G), therestriction Φ|EI(G) : EI(G) → E∂Φ(I)(H) is a bijection. We denote the set of right-resolvers G → Hby homR(G,H), and we write H ≤R G if homR(G,H) ̸= ∅.Remark 4.2.1. The term “right-resolving” comes from symbolic dynamics, where the words are ofprimary importance and the actual graph is secondary. A graph homomorphism Φ : G → H isright-resolving if and only if the associated map Φ : L(G) → L(H) satisfies a certain condition onthe symbols (edges) appearing to the right of a given symbol in a word. See [6], §8.2 for details ifinterested.Remark 4.2.2. The class of right-resolving graph homomorphisms is closed under composition. Thisreduces to the fact, applied to the outgoing edges from each state, that a composition of bijections isa bijection. This means that the relation ≤R is transitive, and since the graphs are finite, it is clearlyantisymmetric, so it is indeed a partial order on the set of all graphs (really on the set of equivalenceclasses of graphs up to isomorphism).The following lemma is evident but we state it explicitly for future reference.Lemma 4.2.3. The image of a right-resolver is determined up to graph isomorphism by the partitionof the domain into fibers. That is, if H1, H2 ≤R G via Φi ∈ homR(G,Hi), and for any I1, I2 ∈ V (G)we have ∂Φ1(I1) = ∂Φ1(I2) if and only if ∂Φ2(I1) = ∂Φ2(I2), then in fact the Hi are isomorphic.Note that the converse is not true: for a given G,H with H ≤R G, there may exist Φ,Φ′ ∈homR(G,H) with distinct partitions {(∂Φ)−1(I) | I ∈ V (H)}, {(∂Φ′)−1(I) | I ∈ V (H)} of V (G). How-ever, this cannot occur when H is ≤R-minimal:Theorem 4.2.4 ([6], Theorem 3.2 and Corollary 3.3(a)). For any graph G, there exist a unique ≤R-minimal graph M(G) ≤R G and a unique map ΣG : V (G) → V (M(G)) such that ∂Φ = ΣG for anyΦ ∈ homR(G,M(G)).The construction ofM(G) was first given in [25], though not in this notation. We discuss the proofof Theorem 4.2.4 in §4.8.1. The notion of M(G), for a graph G, provides context for road colourings:Definition 4.2.2 (MD and road colourings). For D ≥ 1, let MD be the graph with a single stateand D self-loops. For a graph G of constant out-degree D, a road colouring of G is a right-resolverG→MD.Note that each MD is ≤R-minimal, and that homR(G,MD) is nonempty if and only if G hasconstant out-degree D, in which case M(G) =MD.4.2.2 Subgraphs and connectednessA sink in a graph G is a state I ∈ V (G) is a state with no outgoing edges, i.e. F (I) = ∅. Weassume throughout that all graphs are sink-free; this is purely for convenience, as all of the resultsthat do not require strong connectedness can be proved for graphs with sinks, with routine but tediousmodifications to the proofs. We say that a graph G is strongly connected, or irreducible, if for anyordered pair I, J ∈ V (G), there is a (directed) edge path in G from I to J , i.e. LIJ(G) ̸= ∅. Note thatstrongly connected graphs are sink-free. The period per(G) of a strongly connected graph G is the gcdof its cycle lengths.A graph H is a subgraph of a graph G if E(H) ⊆ E(G), V (H) ⊆ V (G), and the maps s, t withrespect to H agree with their counterparts on G, restricted to H. An induced subgraph of a graph G30is a subgraph H such that EIJ(H) = EIJ(G) for every I, J ∈ V (H). A strong component of a graphis a maximal strongly connected subgraph, i.e. a strongly connected subgraph that is not a propersubgraph of another strongly connected graph.A principal subgraph of a graph G is a subgraph H such that EI(H) = EI(G) for every I ∈ V (H).Note that every principal subgraph is induced. Note also that if H is a principal subgraph of G, andK is a principal subgraph of H, then K is a principal subgraph of G. A principal component is astrongly connected principal subgraph; note that the principal components are precisely the minimalprincipal subgraphs. In particular, any two principal components of a given graph have disjoint setsof states. The principal components of G correspond to the sink states in the condensation of G,which is the directed acyclic graph in which the states are the strong components, or maximal stronglyconnected subgraphs, of G, and with an edge C1 → C2 in the condensation if there is an edge I1 → I2for Ii ∈ V (Ci) in G.Let G,H be graphs with H ≤R G, and let Φ ∈ homR(G,H). Let K be a subgraph of G. Note,by the right-resolving property, that in order for Φ|K : K → H to be surjective, it is necessary andsufficient that ∂Φ|V (K) : V (K)→ V (H) be surjective and that K be a principal subgraph of G.Remark 4.2.5. The road problem and the O(G) problem were both originally raised for stronglyconnected graphs, which is a natural restriction given the origins of both problems in the ergodictheory of stationary Markov chains. Moreover, strong connectedness is used in an important way ina lemma used to prove both the road colouring theorem and the almost bunchy case of the bunchyfactor conjecture. This is why the O(G) conjecture and the bunchy factor conjecture are stated onlyfor strongly connected graphs.However, it is quite natural from an automata-theoretic perspective, especially concerning compu-tational complexity, to consider graphs that are not strongly connected. For instance, Eppstein [29]shows that it is NP-complete to determine whether the minimum length of a synchronizing word for agiven synchronizing DFA is at most some given value. Eppstein’s examples are not strongly connected.4.3 Stability and synchronization4.3.1 Transitions, stability, and synchronizationA right-resolver on a graph G induces transition maps on V (G) in the standard way:Definition 4.3.1 (transition map). Let G,H be graphs with H ≤R G. Let Φ ∈ homR(G,H). ForI ∈ V (G) and u ∈ L∂Φ(I)(H), we write I · u for the terminal state t(γ) of the unique γ ∈ LI(G) withΦ(γ) = u. That is, I · u = t((Φ|LI(G))−1(u)). We denote by SΦ the set of maps of the form I 7→ I · uwith respect to Φ.We now introduce the notion of a congruence (see [14], Chapter 1, or [39], §3), of which we willsee two important examples. The main example will be the stability relation, but we will also use acongruence in Proposition 4.8.7 to construct the maximal bunchy factor B(G) of a given graph G.Definition 4.3.2 (congruences and quotients). LetG,H be graphs withH ≤R G, let Φ ∈ homR(G,H),and let ∼ be an equivalence relation on V (G). We say that ∼ is a congruence with respect to Φ ifit is invariant under transitions, i.e. for all I ∈ V (H), all u ∈ LI(H), and all I1, I2 ∈ (∂Φ)−1(I)with I1 ∼ I2, we have I1 · u ∼ I2 · u. We “overload” a congruence ∼ by defining it also on paths (inparticular, edges), by saying that γ1 ∼ γ2, for γ1, γ2 ∈ L(G), if Φ(γ1) = Φ(γ2) and s(γ1) ∼ s(γ2).Define the quotient graph G/ ∼ by V (G/ ∼) = V (G)/ ∼, E(G/ ∼) = E(G)/ ∼, s([e]∼) = [s(e)]∼, andt([e]∼) = [t(e)]∼.Remark 4.3.1. Let G,H be graphs with H ≤R G, let Φ ∈ homR(G,H), and let ∼ be a congruence onG with respect to Φ. Observe that there are right-resolvers G→ G/ ∼, G/ ∼→ H which compose toΦ, where the right-resolver G→ G/ ∼ is the quotient map, and the right-resolver G/ ∼→ H takes a∼ class to the image in H of any of its representatives.31Remark 4.3.2. The coarsest congruence, with respect to a right-resolver Φ ∈ homR(G,H), is the totalrelation on the fibers, i.e. the relation⊔I∈V (H)((∂Φ)−1(I))2. The quotient of G by this relation issimply H, with Φ as the quotient map.Definition 4.3.3 (stability relation for a right-resolver). Let G,H be graphs with H ≤R G and letΦ ∈ homR(G,H). The stability relation for Φ, written ∼Φ, is the equivalence relation on V (G) definedas follows: for I ∈ V (H) and I1, I2 ∈ (∂Φ)−1(I), I1 ∼Φ I2 if and only if for all u ∈ LI(H), there existsv ∈ Lt(u)(H) such that I1 · uv = I2 · uv.Lemma 4.3.3. Let G,H be graphs with H ≤R G and let Φ ∈ homR(G,H). The stability relation ∼Φis a congruence with respect to Φ.Proof. Let I ∈ V (H) and I1, I2 ∈ (∂Φ)−1(I) with I1 ∼Φ I2. Let u ∈ LI(H) and let v ∈ Lt(u)(H).Since I1 ∼Φ I2, there exists w ∈ Lt(v)(H) such that I1 · uvw = I2 · uvw. Therefore I1 · u ∼Φ I2 · u, so∼Φ is indeed a congruence.We now define synchronizing right-resolvers in terms of the stability relation, then show in Propo-sition 4.3.4 that, at least in the strongly connected case, this definition is equivalent to a more obviousnotion of synchronization for a right-resolver.Definition 4.3.4 (synchronizer). Let G,H be graphs with H ≤R G and let Φ ∈ homR(G,H). Wesay that Φ is synchronizing, or is a synchronizer, if each fiber (∂Φ)−1(I), I ∈ V (H), is a ∼Φ class. Wedenote the set of synchronizers G→ H by homS(G,H), and we write H ≤S G if homS(G,H) ̸= ∅.Note that ∼Φ depends on Φ only through SΦ. That is, if Φ,Φ′ are such that SΦ = SΦ′ , then∼Φ=∼Φ′ .Proposition 4.3.4. Let G,H be graphs with H ≤R G and let Φ ∈ homR(G,H). Then Φ is synchro-nizing if and only if for every I ∈ V (H), there exists u ∈ LI(H) with |(∂Φ)−1(I) · u| = 1.Proof. First, suppose that Φ is synchronizing and let I ∈ V (H). If |(∂Φ)−1(I)| = 1, then we are done.Otherwise, there exist at least two distinct states I1, I2 ∈ (∂Φ)−1(I), and I1 ∼Φ I2 since (∂Φ)−1(I) isa ∼Φ class by assumption. Therefore, there exists u1 ∈ LI(H) with I1 · u1 = I2 · u1. In particular,|(∂Φ)−1(I) ·u1| < |(∂Φ)−1(I)|. Continuing inductively, we can produce a sequence of words u1, . . . , unsuch that t(ui) = s(ui+1) and |(∂Φ)−1(I) · u1 · · ·un| = 1. This proves the first claim.For the converse, let I ∈ V (H) and I1, I2 ∈ (∂Φ)−1(I). We will show that I1 ∼Φ I2. Let v ∈ LI(H)be arbitrary. By the assumption that each fiber can be collapsed to a single state, let w ∈ Lt(v)(H) besuch that |(∂Φ)−1(t(v)) ·w| = 1. Then |(∂Φ)−1(I) ·vw| = 1; in particular, I1 ·vw ∼Φ I2 ·vw. Therefore(∂Φ)−1(I) is a ∼Φ class, and Φ is synchronizing.We now summarize the structure of stability, in the sense of its behaviour with respect to compo-sition of right-resolvers. For the proof of Theorem 4.3.5, see §4.8.2.Theorem 4.3.5. Let G,K,H be graphs with H ≤R K ≤R G. Let Ψ ∈ homR(G,K), ∆ ∈ homR(K,H),and let Φ = ∆ ◦Ψ.1. The ∼Ψ classes in V (G) are the intersections of ∼Φ classes with ∂Ψ fibers. In particular, Ψ issynchronizing if and only if every ∂Ψ fiber is contained in a ∼Φ class.2. If K = G/ ∼Φ and Ψ is the quotient map for ∼Φ, then Ψ is synchronizing and ∼∆ is trivial.3. If ∼∆ is trivial, then ∼Φ=∼Ψ.4. Φ is synchronizing if and only if both Ψ and ∆ are synchronizing.The following observation follows immediately from Theorem 4.3.5(4).32Corollary 4.3.6. The relation ≤S is transitive, and is thus a partial order on the class of graphs(again, really isomorphism classes of graphs), refining the partial order ≤R.Conjecture (O(G) conjecture, Question 4.6 in [6]). Let G be a strongly connected graph. Then theset of graphs H with H ≤S G has a unique ≤S-minimal element O(G).Remark 4.3.7. This remark is intended for readers interested in algebraic or categorical perspectiveson automata theory. Recall that for a complete DFA, or road colouring Φ ∈ homR(G,MD), where Gis a graph of constant out-degree D, the set SΦ of transition maps forms a transformation semigroupunder composition. Indeed, a complete DFA is essentially a finite transformation semigroup togetherwith a choice of generators; this perspective is taken explicitly in [5, 21] and mentioned in [61], thefirst paper on the road problem after [2].For a general right-resolver Φ ∈ homR(G,H), one could see SΦ as the semigroup of transitions ofa partial finite automaton (PFA), where a given transition is defined only on a single fiber. However,it is more helpful to see SΦ as a semigroupoid (equivalently, if the empty word is included, a smallcategory). One reason is that, as we show in §4.7, it can be decided in polynomial time whether Φis synchronizing, and the length of a word synchronizing a given fiber is bounded by a polynomialin |V (G)|. This is in contrast to the high level of complexity typical of related problems in subsetsynchronization and synchronization of PFAs [13, 75].The reader may verify as an exercise, generalizing Cayley’s theorem or specializing the Yonedalemma, that every finite semigroupoid is isomorphic to SΦ for some graphs G,H (although possiblywith sinks) and some Φ ∈ homR(G,H), with appropriate generalizations to the infinite case. Moreover,just as every group is a quotient of a free group, SΦ is a quotient of the free semigroupoid L(H).4.3.2 Sufficient conditions for stabilityWe now give a pair of sufficient conditions for nontrivial stability, both of which are used in the proofof the road colouring theorem and one of which is also used in §4.5 to obtain a right-resolver withnontrivial stability on an almost bunchy graph.The first condition involves a special case of the operation known as in-amalgamation ([49], §2.4):Lemma 4.3.8. Let G,H be graphs with H ≤R G and let Φ ∈ homR(G,H) be a right-resolver. LetI ∈ V (H). Suppose that there exist I1, I2 ∈ (∂Φ)−1(I) such that |EI1J(G)| = |EI2J(G)| for allJ ∈ V (G). Then there exists Φ′ ∈ homR(G,H) such that I1 ∼Φ′ I2.Proof. We first claim that F (I1) = F (I2), where we recall from §4.2 the notation F (·) for the set offollower states of a given state. Indeed, the assumption that |EI1J(G)| = |EI2J(G)| for all J ∈ V (G)implies in particular that, for any V (G), we have |EI1J(G)| > 0, equivalently J ∈ F (I1), if and only|EI2J(G)| > 0, equivalently J ∈ F (I2).Let F = F (I1) = F (I2). For each J ∈ F , choose a bijection ΘJ : EI2J(G)→ EI1J(G). Define Φ′ asfollows: ∂Φ′ = ∂Φ, Φ′|E(G)\EI2 (G) = Φ|E(G)\EI2 (G), and, for each J ∈ F , Φ′|EI2J (G) = Φ|EI1J (G) ◦ΘJ .That is, Φ′ agrees with Φ on states and on all edges with initial state other than I2, but may disagreewith Φ on the outgoing edges from I2, specifically by permutations of parallel edges. Since Φ′|EI2 (G) :EI2(G)→ EI(G) is a bijection (being a composition of bijections), Φ′ is indeed right-resolving.By the construction of Φ′, for any a ∈ EI(G), we have I1 ·a = I2 ·a. Any w ∈ LI(H) is of the formw = au with a ∈ EI(G), so I1 · w = I2 · w. Therefore I1 ∼Φ′ I2.In Lemma 4.3.8, the states I1, I2 are said to be in-amalgamated by the operation G→ G/ ∼Φ′ ; theinverse operation is known as in-splitting. The lemma shows in particular that no fiber of a ≤S-minimalgraph G over M(G) has two states that can be in-amalgamated. Trahtman applies a special case ofthis fact to graphs of constant out-degree, and we follow his line of application; see the first paragraphof the proof of Theorem 4.4.3, found in §4.9.2.The second sufficient condition, given in Proposition 4.3.12, concerns minimal images:33Definition 4.3.5 (minimal image). Let G,H be graphs with H ≤R G, and let Φ ∈ homR(G,H). Aminimal image is a set of the form U = (∂Φ)−1(I) · u for some I ∈ V (H) and u ∈ LI(H), such that|U · v| = |U | for any v ∈ Lt(u)(H).Remark 4.3.9. Let G,H be graphs with H ≤R G, and let Φ ∈ homR(G,H). For any I ∈ V (H), anyu ∈ LI(H), and any v ∈ Lt(u)(H), if U = (∂Φ)−1(I) · u, we clearly have |U · v| ≤ |U |. If there existsv ∈ Lt(u)(H) such that this inequality is strict, then |U | is not minimal, i.e. U is not a minimal image.This is the reason for the term.For a right-resolver Φ on a strongly connected graph, all minimal images have the same size, whichis called the degree of Φ, and a word with minimal image is called a magic word. See [6], §9.1 for atreatment of degrees, using symbolic dynamics. In this chapter, we only need a small fragment of thetheory of degree, which we establish in a self-contained way with no connectedness assumptions, usingthe properties of stability.We use minimal images to give a criterion for stability that can be seen as a pairwise version ofProposition 4.3.4.Lemma 4.3.10. Let G,H be graphs with H ≤R G, and let Φ ∈ homR(G,H). For I ∈ V (H) andI1, I2 ∈ (∂Φ)−1(I), we have I1 ∼Φ I2 if and only if I1 · u = I2 · u for every word u ∈ LI(H) such that(∂Φ)−1(I) · u is a minimal image.Proof. Let I ∈ V (H) and let I1, I2 ∈ (∂Φ)−1(I). First suppose that I1 ∼Φ I2, and let u ∈ LI(H). IfI1 ·u ̸= I2 ·u, then let v ∈ Lt(u)(H) be such that I1 ·uv = I2 ·uv. Then |(∂Φ)−1(I) ·uv| < |(∂Φ)−1(I) ·u|,so (∂Φ)−1(I) · u is not a minimal image. Contrapositively, if (∂Φ)−1(I) · u is a minimal image, thenI1 · u = I2 · u.Conversely, suppose that I1 · u = I2 · u for every word u ∈ LI(H) such that (∂Φ)−1(I) · u is aminimal image. Let r = minu∈LI(H) |(∂Φ)−1(I) · u| and let u ∈ LI(H). We claim that there existsw ∈ Lt(u)(H) with I1 ·uw = I2 ·uw. Indeed, if I1 ·u ̸= I2 ·u, then (∂Φ)−1(I) ·u is not a minimal image,so there exists v ∈ Lt(u)(H) such that |(∂Φ)−1(I) · uv| < |(∂Φ)−1(I) · u|. We can thus inductivelyextend v to obtain the desired w, so indeed I1 ∼Φ I2.The following easy observation about minimal images is the main reason that our results towardthe bunchy factor conjecture (the generalized road colouring theorem and the related result for almostbunchy graphs) require strong connectedness.Lemma 4.3.11. Let G,H be strongly connected graphs with H ≤R G, and let Φ ∈ homR(G,H). Everyminimal image for Φ has the same cardinality, and for every I ′ ∈ V (G), there exists a minimal imageU with I ′ ∈ U .In the proof of the generalized road colouring theorem, we apply Lemma 4.3.11 both directly andvia Proposition 4.3.12. The proof of Proposition 4.3.12 is adapted from the proof of Lemma 10.4.4 in[14].Proposition 4.3.12. Let G,H be strongly connected graphs with H ≤R G and let Φ ∈ homR(G,H).Let I, J ∈ V (H) and let u1, u2 ∈ LIJ(H) be such that Ui = (∂Φ)−1(I) · ui are minimal images. If|U1∆U2| = 2, say U1∆U2 = {J1, J2} (where ∆ denotes the symmetric difference), then J1 ∼Φ J2.Proof. Let r = |U1| = |U2|. Suppose without loss of generality that Ji ∈ Ui, and let U0 = U1 ∩ U2, sothat Ui = U0 ∪{Ji}. For any v ∈ LJ(H), we have (U1 ∪U2) · v = (U0 · v)∪ ({J1, J2} · v). We must have|U0 · v| = |U0| = r− 1 and Ji · v /∈ U0 · v, since otherwise we would have |(∂Φ)−1(I) · uiv| = |Ui · v| < r,contradicting the minimality assumption. Therefore r − 1 + |{J1, J2} · v| = |(U1 ∪ U2) · v|. Note that|(U1 ∪ U2) · v| ∈ {r, r + 1}.Let v ∈ LJ(H) be such that (∂Φ)−1(J) · v is a minimal image. By Lemma 4.3.10, to show thatJ1 ∼Φ J2, we need to show that |{J1, J2} · v| = 1, or equivalently |(U1 ∪ U2) · v| ≤ r. By strongconnectedness and Lemma 4.3.11, we have |(∂Φ)−1(J) · v| = r. But (U1 ∪ U2) · v ⊆ (∂Φ)−1(J) · v, soindeed |(U1 ∪ U2) · v| ≤ r.344.4 The O(G) conjecture and the road problem4.4.1 Generalization of the road colouring theoremWe first introduce the class of graphs involved in the theorem. A bunch in a graph G is a state I ∈ V (G)with |F (I)| = 1. (This terminology, introduced in [74] and used also in [14], is the origin of our termbunchy, introduced in §4.5.) A strongly connected graph in which every state is a bunch is a cycle ofbunches. Let M be a cycle of bunches with V (M) = {I0, . . . , Ip−1}, where F (Ii) = {Ii+1} (subscriptsindexing states in a cycle of length p should be read modulo p throughout), and let Di = |EIi(M)|.Note that M is ≤R-minimal if and only if the sequence of out-degrees D0, . . . , Dp−1 is not a cyclicshift of a sequence obtained by concatenating a strictly shorter sequence with itself more than once.Let M be a ≤R-minimal cycle of bunches. Let OM,q be the cycle of bunches in which the sequenceof out-degrees consists of q cyclic repetitions of D0, . . . , Dp−1. Note that OM,1 =M . Observe that, fora strongly connected graph G with M = M(G) a cycle of bunches, if q = per(G)/per(M) and H is acycle of bunches with H ≤S G, then H = OM,q. Let OD,p = OMD,p be the cycle of bunches of periodp and constant out-degree D. Note that OD,1 = MD. For a strongly connected, aperiodic graph Gof constant out-degree D, a synchronizer G → MD is precisely a synchronizing road colouring of G(recall Definition 4.2.2).The road problem, posed in [2], was the problem of showing, in the notation and conceptual frame-work of this chapter, that MD ≤S G for every strongly connected, aperiodic graph of constant out-degree D. The problem was solved by Trahtman, and the statement of the solution is known as theroad colouring theorem:Theorem 4.4.1 (Trahtman, [74]). Let G be a strongly connected, aperiodic graph of constant out-degree D. Then MD ≤S G.Theorem 4.4.2 (Be´al-Perrin [10], Budzban-Feinsilver [21]). Let G be a strongly connected graph ofconstant out-degree D and period p. Then OD,p ≤S G.We prove the following generalization:Theorem 4.4.3. Let G be a strongly connected graph such that M(G) is a cycle of bunches. Letq = per(G)/per(M(G)). Then OM(G),q ≤S G.The proof (see §4.9) follows that of Theorems 4.4.1 and 4.4.2. The strategy is to show that ifG is not itself a cycle of bunches, then there exists Φ ∈ homR(G,M(G)) with ∼Φ nontrivial, byconstructing two minimal images that differ by a pair and applying Proposition 4.3.12. A very similarstrategy is used to prove the bunchy factor conjecture for almost bunchy graphs (Corollary 4.5.8),the (substantial) difference being the different techniques used to obtain the requisite pair of minimalimages.4.4.2 The O(G) conjecture implies the road colouring theoremWe now recall the sense in which theO(G) conjecture was first understood to relate to the road problem.Although the road colouring theorem clearly implies the O(G) conjecture for strongly connected,aperiodic graphs of constant out-degree, the converse implication may not be apparent. Indeed, theO(G) conjecture asserts that O(G) is well-defined for every strongly connected graph, but does notimmediately say how to compute O(G), whereas the road colouring theorem explicitly specifies theform of O(G) for the graphs G to which it applies. However, the O(G) conjecture does imply the roadcolouring theorem, via a key result from [2], for which we require a definition.Definition 4.4.1 (higher edge graph). Let G be a graph. For k ≥ 2, the k-th higher edge graph ofG is the graph G[k] with edge set consisting of edge paths e1e2 · · · ek−1ek of length k in G, and statesgiven by s(e1e2 · · · ek−1ek) = e1e2 · · · ek−1, t(e1e2 · · · ek−1ek) = e2 · · · ek−1ek. We define G[1] = G.35It is a standard result ([49], Chapter 2) that G ≤S G[k] for any strongly connected graph G andany k ≥ 1. In our terminology, Adler-Goodwyn-Weiss showed the following:Lemma 4.4.4 ([2], Lemma 4). Let G be a strongly connected, aperiodic graph of constant out-degreeD. Then for all sufficiently large k, we have MD ≤S G[k].Together with an easy observation about partially ordered sets, the Adler-Goodwyn-Weiss resultshows that the O(G) conjecture implies the road colouring theorem.Lemma 4.4.5. Let (P,⪯) be a partially ordered set such that, for any y ∈ P, there exists a unique⪯-minimal element O(y) ⪯ y. If x ⪯ y, then O(x) = O(y).Proposition 4.4.6 ([6]). Suppose that the O(G) conjecture is true. Let G be a strongly connected,aperiodic graph of constant out-degree D. Then MD ≤S G.Proof. Let k be large enough that MD ≤S G[k], by Lemma 4.4.4. Then in fact MD = O(G[k]). SinceG ≤S G[k] as well, the result follows by Lemma 4.4.5.4.5 BunchinessIn this section, we define and characterize the classes of bunchy and almost bunchy graphs, anddemonstrate the importance of bunchy graphs to the structural properties of right-resolvers.4.5.1 Bunchy and almost bunchy graphsWe recall from Theorem 4.2.4, for a graph G, the notation ΣG : V (G) → V (M(G)) for the uniquestate map among right-resolvers G→M(G).Definition 4.5.1 (bunchy states and graphs). Let G be a graph. We say that a state I ∈ V (G) isbunchy if ΣG|F (I) : F (I) → F (ΣG(I)) ⊆ V (M(G)) is a bijection. We say that G is bunchy if everyI ∈ V (G) is bunchy. We say that G is almost bunchy if for each I, J ∈ V (M), there exists at most oneI ′ ∈ Σ−1G (I) such that |F (I ′) ∩ Σ−1G (J)| ≥ 2.Remark 4.5.1. The definition of almost bunchiness means that for every ordered pair of ΣG fibers inG, say the fibers of states I, J ∈ V (M), there is at most one state in the fiber of I that does not “lookbunchy”, in the sense that it has non-parallel outgoing edges into the fiber of J . In other words, analmost bunchy graph almost satisfies the conditions for bunchiness, but an exception is allowed foreach ordered pair of fibers.The following is evident but we state it explicitly for reference:Lemma 4.5.2. The classes of bunchy and almost bunchy graphs are closed under right-resolvers.Moreover, if G is a bunchy graph and C is a principal subgraph of G with M(C) = M(G), then C isalso bunchy.Remark 4.5.3. We briefly discuss examples of bunchy and almost bunchy graphs. The only stronglyconnected bunchy graphs of constant out-degree are the cycles of bunches. For a given ≤R-minimalcycle of bunches M with sequence of out-degrees D0, . . . , Dp−1, the only strongly connected bunchygraphs G with M(G) =M are the graphs OM,q introduced in the previous section.A strongly connected almost bunchy (but not bunchy) graph of constant out-degree is a graph witha unique non-bunchy state, i.e. a state I with |F (I)| ≥ 2, together with a path from each element ofF (I) back to I. One example that has been considered in the literature is the graph Wn studied in[4], first discussed in [77], and of interest due to its slow synchronization.An almost bunchy graph G can have at most |V (M(G))|2 non-bunchy states, one for each orderedpair of ΣG fibers. One way to obtain an almost bunchy graph is to start with a bunchy graph andperform a sequence of in-splittings (recall Lemma 4.3.8, and see also [49], §2.4), but not all in-splittingswill preserve almost bunchiness, and not all almost bunchy graphs arise this way.36Bunchy and almost bunchy graphs are characterized in terms of automorphisms, with an importantuniqueness consequence for the sets of transition maps induced on them by right-resolvers:Proposition 4.5.4. A graph G is almost bunchy if and only if there is a unique right-resolver G →M(G) up to permutations of parallel edges: that is, if and only if, for any Φ1,Φ2 ∈ homR(G,M(G)),there exist σ ∈ P (G), τ ∈ P (M(G)) such that Φ1 = τ ◦ Φ2 ◦ σ. Moreover, G is bunchy if and only ifwe can take τ = id regardless of Φ1,Φ2.Proposition 4.5.5. Let G be an almost bunchy graph. Let Φ1,Φ2 ∈ homR(G,M(G)). Then SΦ1 =SΦ2 . In particular, ∼Φ1 =∼Φ2 .For the proofs of Propositions 4.5.4 and 4.5.5, see §4.8.3. The following definition is now justified.Definition 4.5.2. Let G be an almost bunchy graph. We denote by ∼G the unique relation on V (G)with ∼G=∼Φ for any Φ ∈ homR(G,M(G)).4.5.2 Proof of the O(G) conjecture in the bunchy caseWe now resolve the O(G) conjecture in the almost bunchy case (which includes the bunchy case). Thisextends Corollary 4.3 in [6], which resolves the conjecture for graphs G such thatM(G) has no paralleledges (so G is trivially bunchy). The proof here is quite different from the proof in the no-parallel-edgescase, and yields a polynomial-time algorithm (Algorithm 4.7.2) for constructing O(G).Theorem 4.5.6. Let G be an almost bunchy graph and let H ≤S G. If H is ≤S-minimal, thenH = G/ ∼G. In particular, the set {K |K ≤S G} has a unique ≤S-minimal element O = G/ ∼G.Proof. Let Ψ ∈ homS(G,H) and ∆ ∈ homR(H,M). We can naturally identify V (H) = V (G)/ ∼Ψby Lemma 4.2.3. The hypothesis that H is ≤S-minimal implies that ∼∆ is trivial, so ∼Ψ=∼∆◦Ψby Theorem 4.3.5(3). By Proposition 4.5.5, we have ∼∆◦Ψ=∼G. We can thus identify V (H) withV (G)/ ∼G= V (G/ ∼G). Thus H = G/ ∼G by a second application of Lemma 4.2.3.In the strongly connected case, we can apply Proposition 4.3.12, which is also used in the proof ofthe road colouring theorem, to say more.Proposition 4.5.7. Let G be a strongly connected almost bunchy graph. If G is not bunchy, then ∼Gis nontrivial.Proof. Let I, J ∈ V (M(G)) and I ′ ∈ Σ−1G (I) with |F (I ′) ∩ Σ−1G (J)| ≥ 2. Let J1, J2 ∈ F (I ′) ∩ Σ−1G (J),J1 ̸= J2, and let ei ∈ EI′Ji(G). Let Φ ∈ homR(G,M(G)) and let ai = Φ(ei). By strong connectednessand Lemma 4.3.11, there exists a minimal image U ⊆ Σ−1G (I) with I ′ ∈ U . Let U0 = U \ {I ′}. ThenU0 ·a1 = U0 ·a2 since G is almost bunchy. Moreover, Ji = I ′ ·ai /∈ U0 ·ai (otherwise, minimality wouldbe contradicted). Thus (U · a1)∆(U · a2) = {J1, J2}. By Proposition 4.3.12, J1 ∼Φ J2.Corollary 4.5.8. Let G be a strongly connected almost bunchy graph. Then O(G) is bunchy.Proof. If |V (G)| = 1 then the claim is clearly true. Suppose that the conclusion is true for all almostbunchy G with |V (G)| ≤R N , and let G be almost bunchy with |V (G)| = N + 1. If G is bunchy, thenO(G) is clearly bunchy by Lemma 4.5.2. If G is not bunchy, then ∼G is nontrivial by Proposition 4.5.7,so |V (G/ ∼G)| ≤R N . Moreover, since G/ ∼G≤S G, it follows that O(G) = O(G/ ∼G) is bunchy bythe inductive hypothesis and Lemma 4.5.2.4.5.3 Universal property of the fiber productWe recall a standard construction known as the fiber product, and derive several new properties. Chiefamong these is the one exhibited in Theorem 4.5.12, which is an analogue of the universal propertyoften enjoyed by the fiber product, or pullback, in other categories (see e.g. [65], Definition 3.1.15 andsubsequent discussion).37Definition 4.5.3 (fiber product). Let H1, H2,K be graphs and let Ψi : Hi → K be graph homomor-phisms. The fiber product of Ψ1,Ψ2 is the graph P = H1 ×Ψ1,Ψ2 H2 whereV (P ) =⊔I∈V (K)(∂Ψ1)−1(I)× (∂Ψ2)−1(I)E(P ) = {(e1, e2) | ei ∈ E(Hi), Ψ1(e1) = Ψ2(e2)}together with the coordinate projections Ψˆi : P → Hi. We write ΨP = Ψi ◦ Ψˆi : P → K.Remark 4.5.9. To see that Ψ1 ◦ Ψˆ1 = Ψ2 ◦ Ψˆ2 and thus that ΦP is well-defined, note that for every(I1, I2) ∈ V (P ) and every (e1, e2) ∈ E(I1,I2)(P ), we have, by the definition of P ,Ψ1 ◦ Ψˆ1(e1, e2) = Ψ1(e1) = Ψ2(e2) = Ψ2 ◦ Ψˆ2(e1, e2)Remark 4.5.10. Observe that the Ψˆi are surjective (respectively, right-resolving) when the Ψi are surjec-tive (respectively, right-resolving). Moreover, if C is a principal subgraph of P such that the restrictedstate maps ∂Ψˆi|V (C) : V (C) → V (Hi) are surjective, then Hi ≤R C, indeed Ψˆi|C ∈ homR(C,Hi). Inparticular, this condition is satisfied if the Hi are strongly connected and C is a principal componentof P .Remark 4.5.11. Often the convention is taken that V (P ) = V (H1) × V (H2). However, all of theelements of the full Cartesian product that are not elements of V (P ), as we have defined it, would beisolated states, and in particular would be sinks. Our definition has the feature that the fiber productof two sink-free graphs (or rather, of two right-resolvers defined on such graphs) is also sink-free.We now state the universal property of the fiber product. Compare with a similar diagram in [6](p. 289). See §4.8.4 for the proof.Theorem 4.5.12. Let H1, H2 be bunchy graphs with M(H1) =M(H2) =M . Let Ψi ∈ homR(Hi,M)be right-resolvers, and let P = H1×Ψ1,Ψ2H2. Let G be a common right-resolving extension of H1, H2 viaΦi ∈ homR(G,Hi). Then there exist a principal subgraph C of P and right-resolvers ∆i ∈ homR(G,C)such that Φi = Ψˆi ◦∆i and ∂∆1 = ∂∆2. In particular, Hi ≤R C ≤R G, with Ψˆi|C ∈ homR(C,Hi).Remark 4.5.13. The bunchiness hypothesis on the Hi cannot be dropped, as the following constructionillustrates. Let G be a graph and let Φ1,Φ2 ∈ Aut(G). In the notation of the the theorem, we willtake H1 = H2 = G. (Recall that any automorphism is right-resolving.) Let M = M(G). LetΨi ∈ homR(G,M) and P = G×Ψ1,Ψ2 G. Let C be a principal subgraph of P with Ψˆi|V (C) surjective,and let ∆i ∈ homR(G,C) with Φi = Ψˆi|C ◦ ∆i. Then Ψˆi|C and ∆i are isomorphisms, since theycompose to an isomorphism. In particular, since Ψ1 ◦ Ψˆ1|C = Ψ2 ◦ Ψˆ2|C , we have Ψ1 = Ψ2 ◦ τ whereτ = Ψˆ2|C ◦(Ψˆ1|C)−1is an isomorphism. In other words, any two elements of homR(G,M) agree upto an automorphism of G. That condition always holds when G is bunchy (see Proposition 4.5.4), butfails in general.We now give two applications of the universal property. The first, Proposition 4.5.15, is applied inProposition 4.6.2, which is the main motivation for the bunchy factor conjecture. See §4.8.5 for theproof of Lemma 4.5.14.Lemma 4.5.14. Let H1, H2 be bunchy graphs with M(H1) = M(H2) = M . Let Ψi ∈ homR(Hi,M),and let P = H1 ×Ψ1,Ψ2 H2. Then P is bunchy. In particular, if C is a principal subgraph of P suchthat the restrictions ∂Ψˆi|V (C) : V (C)→ V (Hi) are surjective, then C is bunchy.Proposition 4.5.15. Let G be a graph. Let H1, H2 ≤S G be bunchy. Then O(H1) = O(H2), i.e. Ghas at most one ≤S-minimal bunchy synchronizing factor.38Proof. Let M = M(G), let Φi ∈ homS(G,Hi), and let Ψi ∈ homR(Hi,M). Let P = H1 ×Ψ1,Ψ2 H2.By Theorem 4.5.12, there is a principal subgraph C of P admitting ∆i ∈ homR(G,C) such thatΦi = Ψˆi|C ◦ ∆i. Since each Φi is synchronizing, each restriction Ψˆi|C is synchronizing as well, soHi ≤S C. Since C is bunchy by Lemma 4.5.14, we know that O(C) is well-defined, and thus, byLemma 4.4.5, we have O(H1) = O(C) = O(H2) as claimed.For the second application of the universal property, recall that the only strongly connected bunchygraphs of constant out-degree are the cycles of bunches. In particular, by the periodic road colouringtheorem, for any strongly connected graph G of constant out-degree D and period p, the uniquemaximal bunchy right-resolving factor of G, namely OD,p, is a synchronizing factor of G (and is indeedequal to O(G)). We now show that every graph G has a unique maximal bunchy right-resolving factorB(G). The construction is similar to that of the auxiliary graph G˜ in [6], §5. See §4.8.5 for the proof,as well as an explicit construction of B(G) yielding a polynomial-time algorithm (Algorithm 4.7.3).Proposition 4.5.16. Let G be a graph.(1) The set {H ≤R G |H is bunchy} has a unique ≤R-maximal element B = B(G).(2) Let H ≤R G be bunchy and Φ ∈ homR(G,H). Then Φ factors through B, i.e. there exist∆ ∈ homR(G,B), Θ ∈ homR(B,H) such that Φ = Θ ◦∆.4.6 The O(G) conjecture and bunchy synchronizing factorsAs we have seen, the O(G) conjecture holds for strongly connected graphs G such that M(G) isa cycle of bunches, and for almost bunchy graphs (including the bunchy graphs) by Theorem 4.5.6.Moreover, for strongly connected almost bunchy graphs, and strongly connected graphs that factor ontocycles of bunches, we know that there is a bunchy synchronizing factor, which we show inductivelyby assuming non-bunchiness and obtaining a right-resolver with a nontrivial stability relation. Itseems plausible that, if the O(G) conjecture is true, then it can be proven by a similar approach:assume non-bunchiness, find a right-resolver with nontrivial stability relation, recursively find a bunchysynchronizing factor, and apply Proposition 4.5.15. The next proposition gives several equivalentformulations of the hypothesis that this approach can be made to work. See §4.8.6 for the proof.Proposition 4.6.1. The following statements are equivalent.(1) Any strongly connected ≤S-minimal graph is bunchy.(2) For any strongly connected graph G, there exists some bunchy H ≤S G.(3) For any non-bunchy strongly connected graph G, there exists some Φ ∈ homR(G,M(G)) with ∼Φnontrivial.(4) For any strongly connected graph G, B(G) ≤S G.Conjecture (bunchy factor conjecture). The assertions in Proposition 4.6.1 are true.Proposition 4.6.2. The bunchy factor conjecture implies the O(G) conjecture.Proof. Let G be a strongly connected graph and let A = {H |H ≤S G, H is ≤S-minimal}. Clearly|A| ≥ 1. By hypothesis, every element of A is bunchy. By Proposition 4.5.15, |A| ≤ 1, so A has asingle element, namely O(G).Observe that the bunchy factor conjecture is a straightforward generalization of the road problem.As discussed above, the O(G) conjecture was already known to imply the road colouring theorem, viathe higher-edge result from [2]. By contrast, the bunchy factor conjecture implies the road colouringtheorem more directly, without reference to [2].394.7 Computing with right-resolversWe now discuss the computational problems of constructing O(G1), O(G2), for input graphs G1, G2such that the O(Gi) are known to exist, and deciding whether the O(Gi) are isomorphic. Althoughone could apply generic graph isomorphism algorithms, which are efficient in practice (Theorem 1 in[57] gives a polynomial-time reduction from directed to undirected graph isomorphism, and see [7] fora survey of the state of the art), it is desirable to have a polynomial-time algorithm, in particular onethat only uses constructions involved in the theory of right-resolvers and synchronization. We do notattempt detailed complexity analyses, noting only that all of the procedures we give can be easily seento run in polynomial time.4.7.1 Basic routinesIn [6], a polynomial-time algorithm is given for computing M(G), along with ΣG and a total order-ing of V (M(G)) such that any graph isomorphism M(G) → M(H) must preserve the order of thestates. Deciding whether M(G), M(H) are isomorphic is therefore no harder than constructing them.Moreover, we can use ΣG to construct right-resolvers, as follows.Algorithm 4.7.1. Construct a right-resolver from a graph to its minimal right-resolving factor.1. Input: a graph G.2. Construct M(G) and ΣG.3. For each I, J ∈ V (M(G)):1. Choose a total ordering on EIJ(M).2. For each I ′ ∈ Σ−1G (I):1. Choose a total ordering on⋃J′∈Σ−1G (J)EI′J′(G), i.e. the edges e ∈ EI′(G) withΣG(t(e)) = J .2. For each e ∈ EI′(G) with ΣG(t(e)) = J , record as Φ(e) the edge in EIJ(M) with thesame position in the total ordering of EIJ(M) as e has in⋃J′∈Σ−1G (J)EI′J′(G).4. Return: Φ.There are also obvious polynomial-time procedures for constructing the fiber product of two right-resolvers, and for determining whether there is a path from one given state to another (in a graph thatmay not be strongly connected). With these basic routines, we can construct the stability relation ofa right-resolver in polynomial time, as follows.Algorithm 4.7.2. Construct the stability relation of a right-resolver.1. Input: graphs G,H, and Φ ∈ homR(G,H).2. Construct P = G×Φ,Φ G.3. Populate the set U of states (I1, I2) ∈ V (P ) with no outgoing path to the diagonal in V (P ).4. Populate and output: the set ∼Φ of states (I1, I2) ∈ V (P ) with no outgoing path to U .Recall that, by definition, Φ ∈ homS(G,H) if and only if H = G/ ∼Φ, i.e. the ∂Φ-fibers areprecisely the ∼Φ classes. Since this is easy to check, Algorithm 4.7.2 can be used to decide whether Φis synchronizing.A similar procedure can be used to construct the maximum bunchy factor B(G), following theconstruction in Proposition 4.8.7:40Algorithm 4.7.3. Construct the maximum bunchy right-resolving factor of a graph.1. Input: a graph G.2. Construct M(G), along with the quotient map ΣG : V (G)→ V (M).3. Construct a graph H with the following data:V (H) = V (G)× V (G)|E(I1,I2)(J1,J2)(H)| ={1, ΣG(I1) = ΣG(I2),ΣG(J1) = ΣG(J2), and Ji ∈ F (Ii)0, otherwise4. Populate the set ≈0 of pairs (I1, I2) with a path in H from the diagonal to (I1, I2).5. Construct and output: the transitive closure ≈ of the relation ≈0.Regarding step 4: referring to the description of ≈0 in Proposition 4.8.7, a path in H from thediagonal to (I1, I2) corresponds to a pair of paths γ, δ ∈ L(G) witnessing I1 ≈0 I2.4.7.2 Decision procedures for common synchronizing factors and exten-sionsSee §4.8.6 for the proof of the following Proposition, which collects several similar statements relatingcommon synchronizing factors and common synchronizing extensions. These results allow us to usefiber products of two graphs to decide questions about common factors of the graphs.Proposition 4.7.1. Let G1, G2 be strongly connected graphs with M(G1) =M(G2) =M .1. If G1, G2 have a common synchronizing factor, then there exist Φi ∈ homR(Gi,M) and a prin-cipal component C of Q = G1 ×Φ1,Φ2 G2 such that Φˆi|C ∈ homS(C,Gi).2. Assume the O(G) conjecture. Then the converse holds in (1). That is, suppose that there existΦi ∈ homR(Gi,M) and a principal component C of Q = G1 ×Φ1,Φ2 G2, such that Φˆi|C ∈homS(C,Gi). Then G1, G2 have a common synchronizing factor, specifically O(G1) = O(C) =O(G2).3. If the Gi are bunchy, then the equivalence described in (1) and (2) holds unconditionally (i.e.without assuming any unproven conjectures).4. Assume the bunchy factor conjecture. Then we have O(G1) = O(G2) if and only if, for theessentially unique Φi ∈ homR(B(Gi),M), there is a principal component C of P = B(G1)×Φ1,Φ2B(G2) such that Φˆi|C ∈ homS(C,B(Gi)).Ashley-Marcus-Tuncel give a polynomial-time algorithm for deciding whether two strongly con-nected graphs have a common strongly connected synchronizing extension. Their algorithm relies onthe construction of a graph that they call G˜, from an input graph G; see Theorem 5.2 and Remark5.10 in [6]. If the O(G) conjecture is true, then by Proposition 4.7.1(2), the Ashley-Marcus-Tuncelalgorithm also decides whether O(G1) = O(G2) for G1, G2 strongly connected. Without assuming anyunproven conjectures, a negative result from the algorithm shows, by Proposition 4.7.1(1), that G1, G2have no common synchronizing factor, while a positive result is inconclusive.For bunchy G1, G2, however, Theorem 4.5.6 and Proposition 4.7.1(3) show that it can be decided inpolynomial time whether O(G1), O(G2) are isomorphic without the Ashley-Marcus-Tuncel algorithm:Algorithm 4.7.4. Decide whether O(G1), O(G2) are isomorphic for G1, G2 strongly connected andbunchy.411. Input: strongly connected bunchy graphs G1, G2 such that M(G1) =M(G2) =M .2. Choose Φi ∈ homR(Gi,M), using Algorithm 4.7.1.3. Construct Q = G1 ×Φ1,Φ2 G2.4. For each principal component C, decide whether Φˆi|C ∈ homS(C,Gi), using Algorithm 4.7.2. Ifso, halt, and return the result that O(G1) = O(G2).5. If no affirmative result is returned in step 4, then halt and return the result that O(G1) ̸= O(G2).Regarding steps 4–5: Proposition 4.7.1(3) shows that we have O(G1) = O(G2) if and only ifΦˆi|C ∈ homS(C,Gi) for some principal component C of Q. The same algorithm would work evenif G1, G2 are not strongly connected but only bunchy, with “principal component C” replaced by“principal subgraph C such that each ∂Φˆi|V (C) is surjective”, but it is not clear that the number ofsuch subgraphs is bounded by a polynomial in |V (G)|.Furthermore, if the bunchy factor conjecture is true, then isomorphism of O(G1), O(G2) is equiva-lent, by Proposition 4.6.1, to isomorphism of O(B(G1)), O(B(G2)), which can be decided without theuse of the Ashley-Marcus-Tuncel G˜ algorithm, using the following procedure. Note that this workseven if we do not have an efficient way to find an element of homS(Gi, B(Gi)).Algorithm 4.7.5. Decide isomorphism of O(G1), O(G2) (assuming the bunchy factor conjecture).1. Input: strongly connected graphs G1, G2.2. Construct B(G1) and B(G2), using Algorithm 4.7.3.3. Decide whether O(B(G1)) = O(B(G2)), using Algorithm 4.7.4.4. Output: the Boolean value of “O(B(G1)) = O(B(G2))”.Observe that the procedure of Algorithm 4.7.5 is essentially what is described in Proposition 4.7.1(4).4.8 Proofs of structural results and additional details4.8.1 Remarks on the proof of Theorem 4.2.4In this subsection, we revisit the first proof of Theorem 4.2.4 given in [6]. The proof of the uniquenessof M(G), for a given graph G, is without issue, but the proof of the uniqueness of ΣG is not quitecomplete. That proof seems to assume that, for graphs G,H with H ≤R G, two right-resolvers G→ Hwith distinct state maps must partition V (G) differently. In general, this is false: per Lemma 4.8.3below, counterexamples arise precisely when Aut(H) acts nontrivially on V (H).The second proof given in [6], constructing V (M(G)) by successive refinements of an initial statepartition, can be made complete by observing that all of the state maps corresponding to the successiverefinements are invariant under Aut(G).Proposition 4.8.1 (Lemma 3.1 in [6]). Let G,H1, H2 be graphs with Hi ≤R G via Ψi ∈ homR(G,Hi),with partitions αi = V (Hi) of V (G). Then there is a graph K ≤R H1, H2, with V (K) equal to thefinest common coarsening of α1, α2.Corollary 4.8.2 (Theorem 3.2 in [6]). Let G be a graph. Then there exists a unique ≤R-minimalgraph M(G) ≤R G, with V (M(G)) given by the finest common coarsening of the partitions α = V (H)of V (G), where H ≤R G.42We will show further that for any Φ1,Φ2 ∈ homR(G,M(G)), we have ∂Φ1 = ∂Φ2. Note that∂Φ1, ∂Φ2 at least have the same sets of fibers, since, if they did not, then by Proposition 4.8.1, wecould take their finest common coarsening, contradicting the minimality of M(G). It is thereforeenough to show that Aut(M(G)) acts trivially on M(G). For this, we need a lemma.Lemma 4.8.3. Let G,H be graphs with H ≤R G, and let Φ1,Φ2 ∈ homR(G,H). Suppose that the∂Φi have the same fibers, i.e. for any I1, I2 ∈ V (G), we have ∂Φ1(I1) = ∂Φ1(I2) if and only if∂Φ2(I1) = ∂Φ2(I2). Then there exists an automorphism τ ∈ Aut(H) such that ∂Φ2 = ∂(τ ◦ Φ1).Proof. By the assumption of equal fibers, there exists a (unique) bijection T : V (H) → V (H) with∂Φ2 = T ◦ ∂Φ1. We need to find τ ∈ Aut(H) with ∂τ = T . Let I ∈ V (H). For J ∈ F (I), note,by the right-resolving hypothesis on the Φi and the choice of T , that |EIJ(H)| = |ET (I)T (J)(H)|.Letting τ |EIJ (H) : EIJ(H) → ET (I)T (J)(H) be any bijection, we have τ ∈ Aut(H) with T = ∂τ and∂Φ2 = ∂(τ ◦ Φ1).We now discuss the quotient of a graph by its automorphism group. Let G be a graph. Wewill construct a graph K = G/Aut(G) ≤R G as follows. Let V (K) consist of the orbits in V (G)under Aut(G). Let I, J ∈ V (K) and I1, I2 ∈ I. We need to specify |EIJ(K)|. We claim that∑J′∈J |EI1J′(G)| =∑J′∈J |EI2J′(G)|. Indeed, let τ ∈ Aut(G) such that I2 = ∂τ(I1). Then∂τ(F (I1)) = ∂τ(F (I2)), and τ(J) = J , so for any J′ ∈ J ∩ F (I1), we have ∂τ(J ′) ∈ J ∩ F (I2).Therefore∑J′∈J |EI1J′(G)| ≤R∑J′∈J |EI2J′(G)|. Replacing τ with τ−1, we obtain equality. DefineK by specifying that |EIJ(K)| =∑J′∈J |EIiJ′(G)|. This edge count ensures that K ≤R G.In particular, if Aut(G) acts nontrivially on V (G), then K ̸= G, so G is not ≤R-minimal. It followsthat, for a ≤R-minimal graph M , Aut(M) acts trivially on V (M). This observation, together withLemma 4.8.3, shows that for any Φ1,Φ2 ∈ homR(G,M(G)), we have ∂Φ1 = ∂Φ2.4.8.2 Proof of Theorem 4.3.5We prove Theorem 4.3.5 in several stages. First, in Lemma 4.8.4, we determine how stability classesintersect with fibers in compositions of right-resolvers.Lemma 4.8.4. Let G,K,H be graphs with H ≤R K ≤R G. Let Ψ ∈ homR(G,K), ∆ ∈ homR(K,H),and let Φ = ∆ ◦ Ψ. Then ∼Ψ-classes are intersections of ∼Φ-classes with ∂Ψ-fibers. That is, forI1, I2 ∈ V (G), if I1 ∼Ψ I2, then I1 ∼Φ I2; conversely, if I1 ∼Φ I2 and moreover ∂Ψ(I1) = ∂Ψ(I2),then I1 ∼Ψ I2.Proof. First suppose that I1 ∼Ψ I2. Then in particular ∂Ψ(I1) = ∂Ψ(I2) = Iˆ. Let I = ∂∆(Iˆ) andu ∈ LI(H), and consider the unique λ ∈ LIˆ(K) such that ∆(λ) = u. Since I1 ∼Ψ I2, there existsµ ∈ Lt(λ)(K) such that I1 · λµ = I2 · λµ. Letting v = ∆(µ), we have I1 · uv = I2 · uv, so I1 ∼Φ I2.For the converse, suppose that I1 ∼Φ I2 and ∂Ψ(I1) = ∂Ψ(I2) = Iˆ. Let I = ∆(Iˆ), let λ ∈ LIˆ(K),let u = ∆(λ), and let v ∈ Lt(u)(H) be such that I1 · uv = I2 · uv. Consider the unique µ ∈ Lt(λ)(K)such that ∆(µ) = v. Then I1 · λµ = I2 · λµ, so indeed I1 ∼Ψ I2.Corollary 4.8.5 follows immediately from Lemma 4.8.4, and together they comprise Theorem 4.3.5(1).Corollary 4.8.5. If Φ = ∆◦Ψ is a composition of right-resolvers, then Ψ is synchronizing if and onlyif every ∂Ψ-fiber is contained in a ∼Φ-class.Proof of Theorem 4.3.5(2). By assumption, the∼Φ classes are precisely the ∂Ψ-fibers, so by Lemma 4.8.4,they are also the ∼Ψ classes. Thus indeed Ψ ∈ homS(G,K).Moreover, let I ∈ V (H), let I ′1, I ′2 ∈ (∂∆)−1(I), and suppose that I ′1 ∼∆ I ′2. We claim that I ′1 = I ′2.Toward this end, we claim that (∂Ψ)−1({I ′1, I ′2}) is a subset of a ∼Φ class. Indeed, let u ∈ LI(H),and let Ii ∈ (∂Ψ)−1(I ′i). Let v ∈ Lt(u)(H) be such that I ′1 · uv = I ′2 · uv = J ′. Let Ji = Ii · uv.Then J1, J2 ∈ (∂Ψ)−1(J ′). Since Ψ is synchronizing, there exists γ ∈ LJ′(K) with J1 · γ = J2 · γ. Letw = ∆(γ). Then I1 · uvw = I2 · uvw. Since u ∈ LI(H) was arbitrary, it follows that I1 ∼Φ I2 as43claimed. Since, by assumption, a ∼Φ class is precisely a ∂Ψ-fiber of a single state of K, we must haveI ′1 = I′2 as claimed. Therefore ∼∆ is indeed trivial.Lemma 4.8.6. Let G,K,H be graphs with H ≤R K ≤R G. Let Ψ ∈ homR(G,K), ∆ ∈ homR(K,H),and let Φ = ∆ ◦ Ψ. Let I ∈ V (H), let I ′1, I ′1 ∈ (∂∆)−1(I), and let Ii ∈ (∂Ψ)−1(I ′i). If I1 ∼Φ I2, thenI ′1 ∼∆ I ′2.Proof. Suppose that I1 ∼Φ I2. Let u ∈ LI(H). Let v ∈ Lt(u)(H) be such that I1 · uv = I2 · uv. Then,since I ′i · uv = ∂Φ(Ii · uv), we have I ′1 · uv = I ′2 · uv. Therefore I ′1 ∼∆ I ′2.Proof of Theorem 4.3.5(3). Suppose that ∼∆ is trivial. Let I ∈ V (H), let I ′1, I ′2 ∈ (∂∆)−1(I) withI ′1 ̸= I ′2, and let Ii ∈ (∂Ψ)−1(I ′i). Since ∼∆ is trivial, there exists u ∈ LI(H) such that, for everyv ∈ Lt(u)(H), we have I ′1 · uv ̸= I ′2 · uv. This implies that I1 · uv ̸= I2 · uv, so I1 ̸∼Φ I2. It follows thateach ∼Φ class is contained inside a ∂Ψ fiber. By Lemma 4.8.4, this shows that ∼Φ=∼Ψ.The final part of Theorem 4.3.5 can be proved in the strongly connected case using symbolic dy-namics, via the multiplicativity of degree under composition of right-resolvers; see [49], §9.1. Using thetheory developed so far, we give a self-contained proof without the assumption of strong connectedness.Proof of Theorem 4.3.5(4). Suppose that Ψ,∆ are synchronizing. Let I ∈ V (H). Let I1, I2 ∈(∂Φ)−1(I). We need to show that I1 ∼Φ I2. Let u ∈ LI(K). We need to find v ∈ Lt(u)(H) suchthat I1 · uv = I2 · uv. Let I ′i = ∂Ψ(Ii). Then ∂∆(I ′1) = ∂∆(I ′2), so I ′1 ∼∆ I ′2 since ∆ is synchronizing.Let v1 ∈ Lt(u)(H) be such that I ′1 · uv1 = I ′2 · uv1. Note that I ′i · uv1 = ∂Ψ(Ii · uv1). Let J ′ = I ′i · uv1and Ji = Ii · uv1. Then ∂Ψ(J1) = J ′ = ∂Ψ(J2), so J1 ∼Ψ J2 since Ψ is synchronizing. Let γ ∈ LJ′(K)be such that J1 · γ = J2 · γ. Let v2 = ∆(γ). Then Ii · uv1v2 = Ji · γ, so taking v = v1v2, we haveI1 · uv = I2 · uv. Thus I1 ∼Φ I2, so Φ is indeed synchronizing.We prove the converse by the contrapositive. Suppose that ∆ is not synchronizing. Then there existI ∈ V (H) and I ′1, I ′2 ∈ (∂∆)−1(I) such that I ′1 ̸∼∆ I ′2. By Lemma 4.8.6, there exist Ii ∈ (∂Ψ)−1(I ′i)such that I1 ̸∼Φ I2. Thus Φ is not synchronizing. Similarly, suppose that Ψ is not synchronizing.Then there exist I ′ ∈ V (K) and I1, I2 ∈ (∂Ψ)−1(I ′) such that I1 ̸∼Ψ I2. By Lemma 4.8.4, I1 ̸∼Φ I2,so Φ is not synchronizing.4.8.3 Proofs of Propositions 4.5.4 and 4.5.5Proof of Proposition 4.5.4. Let M = M(G). First, suppose that G is almost bunchy. Let Φ1,Φ2 ∈homR(G,M). For each I, J ∈ V (M), and each I ′ ∈ Σ−1G (I), let AI′,J = {e ∈ EI′(G) |ΣG(t(e)) = J}.If there exists I ′ ∈ Σ−1G (I) with |F (I ′)∩Σ−1G (J)| ≥ 2 (by almost bunchiness, there is at most one suchI ′ for any given I, J), then let τIJ ∈ P (M) be the permutation of parallel edges in M given byτIJ |E(M)\EIJ (M) = id|E(M)\EIJ (M)τIJ |EIJ (M) = Φ1|AI′,J ◦ (Φ2|AI′,J )−1If there is no I ′ ∈ Σ−1G (I) with |F (I ′)∩Σ−1G (J)| ≥ 2, then let τIJ = id. Distinct τIJ are permutations ofdisjoint sets and therefore commute. Let τ =∏I,J∈V (M) τIJ . Note that if G is bunchy, then τIJ = idfor all I, J , so τ = id.Now, for each I, J ∈ V (M) and each I ′ ∈ Σ−1G (I), let σIJ,I′ ∈ P (G) be given byσIJ,I′ |E(G)\AI′,J = id|E(G)\AI′,JσIJ,I′ |AI′,J = Φ2|−1AI′,J ◦ τ−1 ◦ Φ1|AI′,JAll of the σIJ,I′ commute. Let σ =∏I,J∈V (M), I′∈Σ−1G (I) σIJ,I′ . Then for I ∈ V (M), J ∈ F (I), andI ′ ∈ Σ−1G (I),τ ◦ Φ2 ◦ σ|AI′,J = τ ◦ Φ2 ◦ (Φ2|−1AI′,J ◦ τ−1 ◦ Φ1|AI′,J ) = Φ1|AI′,J44This concludes the proof in the “only if” direction.For the “if” direction, which we prove in the contrapositive, suppose that G is not almost bunchy.Let I, J ∈ V (M) and I1, I2 ∈ Σ−1G (I) such that |F (Ii) ∩ Σ−1G (J)| ≥ 2 for i = 1, 2. Let ei,1, ei,2 ∈ AIi,Jbe such that t(ei,1) ̸= t(ei,2). Let a1, a2 ∈ EIJ(M), and let Φ1,Φ2 ∈ homR(G,M) be such thatΦ1(e1,j) = aj but Φ2(e2,1) = a2 and Φ2(e2,2) = a1. (The behaviour of Φi on E(G) \ {ei,j}i,j=1,2 isirrelevant.) Then there do not exist σ ∈ P (G), τ ∈ P (M) such that Φ1 = τ ◦ Φ2 ◦ σ.Finally, suppose that G is almost bunchy, but not bunchy. Let I, J ∈ V (M) and I ′ ∈ Σ−1G (I) suchthat |F (I ′) ∩Σ−1G (J)| ≥ 2. Let e1, e2 ∈ AI′,J be such that t(e1) ̸= t(e2). Let a1, a2 ∈ EIJ(M), and letΦ1,Φ2 ∈ homR(G,M) be such that Φ1(ei) = ai, Φ2(e1) = a2, and Φ2(e2) = a1. Then there does notexist σ ∈ P (G) such that Φ1 = Φ2 ◦ σ.Proof of Proposition 4.5.5. Let M =M(G). It is enough to show that SΦ1 , SΦ2 share a generating setT , which we now construct and examine. For I, J ∈ V (M), if J /∈ F (I), let TI,J,1 = TI,J,2 = ∅. IfJ ∈ F (I), then let TI,J,i be the set of maps fa,i : Σ−1G (I)→ Σ−1G (J) of the form I ′ 7→ t ◦ (Φi|EI′ )−1(a),i.e. I ′ · fa,i = I ′ · a with respect to Φi, where a ∈ EIJ(M). Clearly TI,J,i generates SΦi , in the sensethat SΦi is the smallest collection of maps closed under composition and containing the TI,J,i as I, Jrange over V (M).We claim that TI,J,1 = TI,J,2. Indeed, let a ∈ EIJ(M) and let I ′ ∈ Σ−1G (I) such that |F (I ′) ∩Σ−1G (J)| ≥ 2. It is enough to show that fa,1 ∈ TI,J,2, as this will show that TI,J,1 ⊆ TI,J,2, fromwhich equality follows by symmetry. By almost bunchiness, there is at most one state I ′ ∈ Σ−1G (I)with |F (I ′) ∩ Σ−1G (J)| ≥ 2. If there is no such state, then clearly fa,1 = fa,2, so assume that such astate I ′ exists. Observe that I ′ · fb,2 = I ′ · fa,1 where b = Φ2 ◦ (Φ1|EI′(G))−1(a). Moreover, for everyI ′′ ∈ Σ−1G (I) with I ′′ ̸= I ′, we also have, by almost bunchiness, that I ′′ · fb,2 = I ′′ · fa,1. Thereforefa,1 = fb,2 ∈ TI,J,2, so indeed TI,J,1 = TI,J,2 as claimed. Let TI,J = TI,J,i and let T =⋃I,J TI,J . ThenT generates both SΦ1 , SΦ2 , so indeed SΦ1 = SΦ2 .4.8.4 Proof of Theorem 4.5.12Proof of Theorem 4.5.12. Define T : V (G)→ V (P ) as follows: for I ′ ∈ V (G), let T (I ′) = (∂Φ1(I ′), ∂Φ2(I ′)).Note that ∂ΨP ◦ T = ∂(Ψi ◦ Φi) = ΣG for each i. Let C be the subgraph of P induced by T (V (G)).Let I ′ ∈ V (G) and J ′ ∈ F (I ′); I = ΣG(I ′) and J = ΣG(J ′); and Ii = ∂Φi(I ′) and Ji = ∂Φi(J ′).Observe that (I1, I2) = T (I′) and (J1, J2) = T (J ′).As in the proof of Proposition 4.5.4, let AI′,J = {e ∈ EI′(G) |ΣG(t(e)) = J}. Since Hi is bunchy,we have F (Ii) ∩ Σ−1Hi (J) = {Ji}, so Φi(AI′,J) = EIiJi(Hi). It therefore makes sense to define∆i|AI′,J = (Ψˆi|E(I1,I2)(J1,J2)(P ))−1 ◦ Φi|AI′,J : AI′,J → E(I1,I2)(J1,J2)(P )Gluing these together, we obtain maps ∆i : E(G)→ E(P ). For e ∈ AI′,J , we have s(∆i(e)) = T (s(e))and t(∆i(e)) = T (t(e)), so the ∆i : G→ P are graph homomorphisms with ∂∆i = T .We now claim that ∆i(E(G)) = E(C). Enumerate EIJ(M) = {a(1), . . . , a(k)}, and let e(j)i =(Ψi|EIiJi (Hi))−1(a(j)). Then(e(j)1 , e(j)2 ) ∈ E(I1,I2)(J1,J2)(P ) = E(I1,I2)(J1,J2)(C)where equality holds because (I1, I2), (J1, J2) ∈ V (C) and C is an induced subgraph of P . Fix-ing (I1, I2) and varying J′, thus varying (J1, J2), the sets E(I1,I2)(J1,J2)(P ) exhaust E(I1,I2)(P ), soE(I1,I2)(C) = E(I1,I2)(P ). Since ∆i|EI′ (G) : EI′(G) → E(I1,I2)(P ) is surjective, we have E(I1,I2)(C) =∆i(EI′(G)). Thus indeed E(C) = ∆i(E(G)).Since we already know that E(I1,I2)(C) = E(I1,I2)(P ) for each (I1, I2) ∈ V (C), it follows that C isindeed a principal subgraph of P . Finally, we haveΨˆi ◦∆i|AI′,J = Ψˆi ◦ (Ψˆi|E(I1,I2)(J1,J2)(P ))−1 ◦ Φi|AI′,J = Φi|AI′,Jas claimed. This shows that Ψˆi|C : C → Hi is surjective, so Hi ≤R C.454.8.5 Proofs of Lemma 4.5.14 and Proposition 4.5.16, and construction ofB(G)Proof of Lemma 4.5.14. Let (I1, I2) ∈ V (P ) with Ii ∈ V (Hi). Let e = (e1, e2), e′ = (e′1, e′2) ∈E(I1,I2)(P ) such that t(∂ΨP (e)) = t(∂ΨP (e′)). We must show that t(e) = t(e′). Toward that goal,note that for each i = 1, 2, we havet(∂ΨP (e)) = ∂ΨP (t(e)) = ∂Ψi(t(ei))t(∂ΨP (e′)) = ∂ΨP (t(e′)) = ∂Ψi(t(e′i))Therefore ∂Ψi(t(ei)) = ∂Ψi(t(e′i)) for each i, since t(∂ΨP (e)) = t(∂ΨP (e′)) by hypothesis. But sincethe Hi are bunchy, we in fact have t(ei) = t(e′i) for each i, so indeed t(e) = t(e′) as required. Thisshows that ∂ΨP |F ((I1,I2)) is a bijection, so P is bunchy.Let C be a principal subgraph of P such that ∂Ψˆi|V (C) : V (C) → V (Hi) are surjective. ThenM(C) =M . For each J ∈ V (M), we have Σ−1C (J) = Σ−1P (J) ∩ V (C). Thus C is bunchy.Proof of Proposition 4.5.16. To prove (1), let H1, H2 ≤R G be ≤R-maximal among the bunchy right-resolving factors of G. Let Φi ∈ homR(G,Hi) and Ψi ∈ homR(Hi,M). Let P = H1 ×Ψ1,Ψ2 H2. ByTheorem 4.5.12, there exist a principal subgraph C of P , and ∆i ∈ homR(G,C), such that Φi =Ψˆi|C ◦ ∆i, so Hi ≤R C. By Lemma 4.5.14, C is bunchy, so by the maximality of the Hi, we haveH1 = C = H2. This proves uniqueness, so we can take B = Hi = C.To prove (2), let H ≤R G be bunchy and let Φ ∈ homR(G,H). Let Φ′ ∈ hom(G,B), Ψ ∈homR(H,M), Ψ′ ∈ hom(B,M). Let P = H ×Φ,Φ′ B. By the universal property (Theorem 4.5.12),there exist a principal subgraph C of P and ∆,∆′ ∈ homR(G,C) with Φ = Ψˆ ◦∆ and Φ′ = Ψˆ′ ◦∆′.Again by Lemma 4.5.14, C is bunchy, so by (1) and the fact that B ≤R C, we have B = C. Thisproves (2) with Θ = Ψˆ′|C .We now present the construction of B(G) described in Algorithm 4.7.3.Proposition 4.8.7. Let G be a graph. For J1, J2 ∈ V (G) with ΣG(J1) = ΣG(J2), write J1 ≈0 J2if there exist paths γ = γ1 · · · γn, δ = δ1 · · · δn ∈ L(G) where γi, δi ∈ E(G), such that s(γ1) = s(δ1),t(γn) = J1, t(δn) = J2, and ΣG(t(γi)) = ΣG(t(δi)) for each i. Let ≈ denote the transitive closure of≈0 and let Φ ∈ homR(G,M(G)). Then ≈ is a congruence with respect to Φ, and B(G) = G/ ≈.Proof. Let M = M(G). Let I ∈ V (M), I1, I2 ∈ Σ−1G (I), and J ∈ F (I). Suppose that I1 ≈ I2. LetJi ∈ F (Ii) ∩ Σ−1G (J). We need to show that J1 ≈ J2. Let I1 = I(0), I(1), . . . , I(n) = I2 ∈ Σ−1G (I) withI(j) ≈0 I(j+1). Let γ(j), δ(j) ∈ L(G) witness the relation I(j) ≈0 I(j+1). Choose J (j) ∈ F (I(j))∩Σ−1G (J),with J (0) = J1 and J(n) = J2. Let e(j) ∈ EI(j)J(j)(G). Then γ(j)e(j), δ(j)e(j+1) witness J (j) ≈0 J (j+1).This shows that J1 ≈ J2.Let Φ ∈ homR(G,M(G)). As in the previous paragraph, let I ∈ V (M), let J ∈ F (I), and letI1, I2 ∈ Σ−1G (I). Suppose that I1 ≈ I2. Let a ∈ EIJ(M), let Ji = Ii · a, and let ei = (Φ|EIi (G))−1(a).Then t(ei) = Ji, so J1 ≈ J2. Therefore ≈ is indeed a congruence for Φ. It follows that F ([Ii]≈) ∩Σ−1G/≈(J) = {[Ji]≈}, so indeed G/ ≈ is bunchy.To see that G/ ≈ is ≤R-maximal among the bunchy factors of G, let H ≤R G be bunchy andΨ ∈ homR(G,H). If I1 ≈0 I2 and H is bunchy, then we must have ∂Ψ(I1) = ∂Ψ(I2). Therefore thepartition into ∂Ψ-fibers corresponds to an equivalence relation that coarsens the symmetric, reflexiverelation ≈0, and thus also coarsens the transitive closure ≈. Considering V (H) as a partition of V (G),we must therefore have V (H) ⪯ V (G)/ ≈, so (G/ ≈) = B(G) by the maximality of B(G).4.8.6 Proofs of Propositions 4.6.1 and 4.7.1Lemma 4.8.8. Let G1, G2, H,K be graphs with K ≤R H ≤R Gi. Let ∆ ∈ homR(H,K). LetΨi ∈ homR(Gi, H) and P = G1×Ψ1,Ψ2 G2. Let Φi = ∆◦Ψi and Q = G1×Φ1,Φ2 G2. Then, noting that46V (P ) = V (Q) and E(P ) ⊆ E(Q), we have Φˆi|P = Ψˆi, and every principal subgraph of P is a principalsubgraph of Q.Proof. Let C be a principal subgraph of P . By the definition of the fiber product, we have V (P ) =V (Q) = V (G1) × V (G2). Let I ∈ V (H) and let Ii ∈ (∂Ψi)−1(I). Suppose that (I1, I2) ∈ V (C). Weneed to show that E(I1,I2)(C) = E(I1,I2)(Q).Since E(I1,I2)(C) = E(I1,I2)(P ) by the definition of a principal subgraph, it is enough to show thatE(I1,I2)(P ) = E(I1,I2)(Q) for any (I1, I2) ∈ V (P ). Clearly E(I1,I2)(P ) ⊆ E(I1,I2)(Q), so it is enough toshow that |E(I1,I2)(P )| = |E(I1,I2)(Q)|. To see this equality, note that since ∆ ◦ΨP = ΦQ, we have|E(I1,I2)(P )| = |E∂ΨP (I1,I2)(H)| = |E∂ΦQ(I1,I2)(K)| = |E(I1,I2)(Q)|where the equalities follow from the facts that ΨP , ∆, and ΦQ respectively are right-resolving. There-fore E(I1,I2)(P ) = E(I1,I2)(Q). This shows that C is indeed a principal subgraph of Q. Moreover, fore = (e1, e2) ∈ E(P ), we have Φˆi(e) = ei = Ψˆi(e), so indeed Φˆi|P = Ψˆi.Lemma 4.8.9. Let G1, G2,K be graphs with K ≤S Gi via Φi ∈ homS(Gi,K). Let C be a principalsubgraph of P = G1 ×Φ1,Φ2 G2 such that the ∂Φˆi|V (C) : V (C) → V (Gi) are surjective. Then Φˆi|C ∈homS(C,Gi). In particular, C is a common synchronizing extension of the Gi.Proof. Let I ∈ V (K) and let Ii, I ′i ∈ V (Gi) with ∂Φi(Ii) = ∂Φi(I ′i) = I. Since the Φi are synchronizing,we have Ii ∼Φi I ′i. Suppose that (I1, I2), (I ′1, I ′2) ∈ V (C). In order to show that Φˆi|C ∈ homS(C,Gi),we claim that (I1, I2) ∼ΦP (I ′1, I ′2). This will show that ΦP |C ∈ homS(C,K). Since ΦP |C = Φi ◦ Φˆi|C ,it will then follow that Φˆi|C ∈ homS(C,Gi) by Theorem 4.3.5(4).To prove this claim, let u ∈ LI(K). Since I1 ∼Φ1 I ′1, there exists v1 ∈ Lt(u)(K) such that I1 ·uv1 =I ′1 ·uv1. Similarly, since I2 ∼Φ2 I ′2, there exists v2 ∈ Lt(v1)(K) such that I2 ·uv1v2 = I ′2 ·uv1v2. Then inparticular (I1, I2) ·uv1v2 = (I ′1, I ′2) ·uv1v2. Since u ∈ LI(K) was arbitrary, we have (I1, I2) ∼ΦP (I ′1, I ′2)as claimed.Proof of Proposition 4.7.1(1). Let K ≤S Gi and Ψi ∈ homS(Gi,K). Let P = G1×Ψ1,Ψ2 G2 and let Cbe a principal subgraph of P such that ∂Ψˆi|V (C) : V (C)→ V (Gi) are surjective. By Lemma 4.8.9, wehave Ψˆi|C ∈ homS(C,Gi). Let ∆ ∈ homR(K,M), let Φi = ∆◦Ψi, and let Q = G1×Φ1,Φ2G2. Then, byLemma 4.8.8, C is a principal subgraph ofQ, with Φˆi|C = Ψˆi|C . In particular, Φˆi|C ∈ homS(C,Gi).We now give an equivalent form of the O(G) conjecture. Fragments of this result appear in Propo-sition 4.7.1. The logical structure of Proposition 4.8.10 (one statement is equivalent to the equivalenceof four other statements) is unusual.Proposition 4.8.10. Let F be a family of graphs satisfying the following conditions:(i) If G ∈ F and H ≤R G, then H ∈ F .(ii) Let G1, G2,K ∈ F with K ≤R Gi. Let Φi ∈ homR(Gi,K), let P = G1 ×Φ1,Φ2 G2, and let C bea principal subgraph of P such that the ∂Φˆi|V (C) are surjective. Then C ∈ F .Then the following assertions are equivalent.(1) For any G ∈ F , there exists a unique ≤S-minimal graph O(G) ≤S G.(2) For any G1, G2 ∈ F , the following assertions are equivalent.(a) O(G1), O(G2) exist and are equal.(b) G1, G2 have a common synchronizing factor.(c) M(G1) = M(G2) = M and there exist Φi ∈ homR(Gi,M) such that Φˆi ∈ homS(C,Gi) forsome principal subgraph C of Q = G1 ×Φ1,Φ2 G2.47(d) G1, G2 have a common synchronizing extension K ∈ F .Remark 4.8.11. The proof of Proposition 4.8.10 in fact shows that both (1) and (2) are equivalent tothe assertion that (d) implies (b). Note that for G1 = G2 = G, (a) states that O(G) is well-defined,while (b)–(d) are trivial.Remark 4.8.12. The O(G) conjecture states that the equivalent statements (1) and (2) in Proposi-tion 4.8.10 hold with F equal to the class of all strongly connected graphs.Proof of Proposition 4.8.10. First, assume (2). Let G be a graph and let H1, H2 ≤S G be ≤S-minimal.Since H1, H2 have the common synchronizing extension G, they satisfy condition (d), so they alsosatisfy condition (b), i.e. there exists a common synchronizing factor K ≤S Hi. But since the Hi wereassumed minimal, we must have H1 = K = H2 = O(G).Now, assume (1) and deduce (2) as follows. Trivially, (a) implies (b) and (c) implies (d). Moreover,(b) implies (c) by Proposition 4.7.1(1). Finally, assume (d). Suppose that G1, G2 have a commonsynchronizing extension K. Then O(G1) = O(K) = O(G2), so (d) implies (a).Proof of Proposition 4.7.1(2). This is immediate from Proposition 4.8.10, specifically, the equivalenceof 2(b) and 2(c), with F taken to be the class of all strongly connected graphs.Proof of Proposition 4.7.1(3). By Theorem 4.5.6, this is immediate from Proposition 4.8.10, again viathe equivalence of 2(b) and 2(c), but with F taken to be the class of strongly connected almost bunchygraphs.Proposition 4.8.13. Let F be a family of graphs such that, if G ∈ F and H ≤R G, then H ∈ F .Then the following assertions are equivalent.(1) Any ≤S-minimal graph H ∈ F is bunchy.(2) For any G ∈ F , there exists some bunchy H ≤S G.(3) For any non-bunchy G ∈ F , there exists some Φ ∈ homR(G,M(G)) with ∼Φ nontrivial.(4) For any G ∈ F , B(G) ≤S G.Remark 4.8.14. Note that Proposition 4.8.13 is a more detailed version of Proposition 4.6.1.Proof. To see that (1) implies (2), let G ∈ F and consider the set {H |H ≤S G}. Being a finitepartially ordered set, this set must have at least one minimal element. If (1) holds, then this minimalelement is bunchy. Thus (2) holds.To see that (2) implies (3), let G ∈ F be non-bunchy. There exists at least one ≤S-minimal graphH ≤S G. If (2) holds, then G is not ≤S-minimal, so H ̸= G. Let Ψ ∈ homS(G,H). The ∂Ψ-fibers areprecisely the ∼Ψ-classes. Since H ̸= G, the ∂Ψ-fibers are not merely singletons, so ∼Ψ is nontrivial.LetM =M(G) and ∆ ∈ homR(H,M), and let Φ = ∆◦Ψ. By Lemma 4.8.4, the ∼Φ-classes are unionsof ∼Ψ-classes, so in particular, ∼Φ is nontrivial.To see that (3) implies (1), let G ∈ F be non-bunchy. If (3) holds, then there exists Φ ∈homR(G,M(G)) with ∼Φ nontrivial. Then G/ ∼Φ≤S G and G/ ∼Φ ̸= G; in particular, G is not≤S-minimal. This proves (1) in the contrapositive.Finally, we show that (2) and (4) are equivalent. If (4) holds, then (2) holds since B(G) is bunchy.Conversely, assume (2) and let G ∈ F . Then there exists H ≤S G bunchy. Let Φ ∈ homS(G,H)and let B = B(G). By Proposition 4.5.16(2) and Theorem 4.3.5(4), we have Φ = ∆ ◦ Θ for someΘ ∈ homS(G,B), ∆ ∈ homS(B,H). Therefore (4) holds.Corollary 4.8.15. Let F be a family of graphs such that, if G ∈ F and H ≤R G, then H ∈ F .Suppose that any ≤S-minimal element of F is bunchy. Then O(G) exists for any G ∈ F .The proof of Corollary 4.8.15 is a trivial adaptation of the proof of Proposition 4.6.2.48Proof of Proposition 4.7.1(4). Assuming the bunchy factor conjecture, the O(Gi) are well-defined. Bythe equivalence of conditions (a),(c) in Proposition 4.8.13, the hypothesis on the B(Gi) is equivalentto the equality O(B(G1)) = O(B(G2)), which in turn is equivalent to the equality O(G1) = O(G2) byProposition 4.8.13.4.9 Proof of Theorem 4.4.3, following TrahtmanIn this section, we recall Trahtman’s proof of the road colouring theorem and reformulate it in a formapplicable to Theorem 4.4.3.4.9.1 Systems of maps with unique tallest treesThe central idea in Trahtman’s proof is an idea well known in the literature on the combinatorics oftransformations of finite sets—namely, that, the graph of a transformation f of a set V is a directedgraph of constant out-degree 1 with V (G)‘V , where, for each state I ∈ V , the unique edge withsource I has target I · f . When V is finite, the graph consists of a set of state-disjoint directed cyclestogether with trees rooted on the cycles, directed toward their roots. Trahtman’s proof is based on theconstruction of a transformation with a unique tallest tree (the height of a tree being the maximumdistance from the root to a leaf). We need a few definitions in order to extend the notion of a uniquetallest tree to a system of maps taking one set to another, cyclically, as opposed to a transformationof a single set.Let p ∈ N and let {Vi}0≤i≤p−1 be disjoint finite sets. Let ai : Vi → Vi+1 be maps, with subscriptsread modulo p. For k ≥ 0, let bk = akak+1 · · · ap−1a0 · · · ak−1 : Vk → Vk. As noted above in thegeneral discussion of graphs of transformations, since each bk is a transformation of a finite set, it iseventually periodic—that is, for each k, there exist m ≥ 0, z ≥ 1 such that bm+zk = bmk . Moreover,the orbits of individual elements I ∈ Vk may vary in their eventually periodic behaviour. Specifically,for a given I ∈ Vk, consider the lexicographically minimal (ℓ,m, z) with 0 ≤ ℓ ≤ p− 1, m ≥ 0, z ≥ 1,such that I · ak · · · ak+ℓ−1bm+zk+ℓ = I · ak · · · ak+ℓ−1bmk+ℓ. Define the height h(I) = mp + ℓ and the rootρ(I) = I · ak · · · ak+ℓ−1bm+zk+ℓ . The idea is that h(I) is the number of steps required until the orbit of Ireaches the root ρ(I) and becomes periodic, with z(I) = z being the period as a multiple of p.To talk about unique tallest trees, let hmax,k = max{h(I) | I ∈ Vk}, and let hk(J) = max{h(I) | I ∈Vk, ρ(I) = J}. Let zk = lcm{z(I) | I ∈ Vk}. We say that the system (Vi, ai)0≤i≤p−1 has a uniquetallest tree at Vk if there is a unique J with hk(J) = hmax,k. Note that the terms we have definedhere still make sense even if the Vi are not all pairwise disjoint, as long as any two are either equal ordisjoint, since we can make them disjoint by replacing Vi with Vi × {i}.We now present our interpretation of a key step in Trahtman’s proof, applying Proposition 4.3.12and closely following [14].Lemma 4.9.1. Let G,H be strongly connected graphs with H ≤R G. Let Φ ∈ homR(G,H). LetI0, . . . Ip−1 ∈ V (H), not necessarily distinct, be such that Ii+1 ∈ F (Ii) ̸= ∅, and let ai ∈ EIiIi+1(H)(with subscripts read modulo p). Suppose that the system ((∂Φ)−1(Ii), ai)0≤i≤p−1 has a unique tallesttree, where we write ai for the map I 7→ I · ai, I ∈ (∂Φ)−1(Ii). Then ∼Φ is nontrivial.Proof. For 0 ≤ i ≤ p − 1, let Vi = (∂Φ)−1(Ii). Suppose without loss of generality that the systemhas a unique tallest tree at V0. Let I ∈ V0 be a state of maximal height h(I) = hmax,0. Let m ≥ 0,0 ≤ p− 1 be such that hmax,0 = mp+ ℓ, and let z = z(I) and let R = ρ(I). Note that R ∈ Vℓ. That is,upon cyclic application of the maps ai, I is eventually mapped to R, then returns to R every z cyclesaround the graph.By strong connectedness and Lemma 4.3.11, let U ⊆ I0 be a minimal image such that I ∈ U . Weclaim that there is no other state I ′ ∈ U with ρ(I ′) = R and I ′ ̸= I. Indeed, suppose that there is sucha state I ′. Then I · a0 · · · aℓ−1bmℓ = I ′ · a0 · · · aℓ−1bmℓ = R, so |U · a0 · · · aℓ−1bmℓ | < |U |, contradicting49the minimality of U . This proves the claim. Let U0 = U \ {I}. Then every element of U0 has heightstrictly less than hmax,0.Let u1 = a0 · · · aℓ−1bm−1ℓ aℓ · · · aℓ−2 : V0 → Vℓ−1, where the tail aℓ · · · aℓ−2 includes each ai exactlyonce, other than aℓ−1, and the subscripts are read modulo p. The effect of applying u1 to V0 is to bringI to one step before its first encounter its root R; since I has maximal height, every other I ′ ∈ V0 hasalready reached its root and is in the periodic part of its orbit after application of u1.Let u2 = u1bzℓℓ−1 = a0 · · · aℓ−1bm+zkℓ−1 aℓ · · · aℓ−2 : V0 → Vℓ−1. Let Ji = I · ui and Ui = U · ui. Asobserved in the previous paragraph, after application of u1, I is not yet in the periodic part of its orbit(i.e. the orbit under cyclic application of the maps ai), but every other element ofObserve that J1 ̸= J2 by the assumed value of h(I).However, since I is the unique element of U with this maximal height, we have U1∆U2 = {J1, J2}.Since the Ui are minimal images, we have J1 ∼Φ J2 by Proposition 4.3.12.4.9.2 Obtaining a right-resolver with a unique tallest treeLet G be a graph. We define a total order colouring to be a total ordering of each edge set EI(H), i.e.a labeling of the edges of G such that, if |EI(G)| = k, then the edges in EI(G) are labeled bijectivelyby {0, . . . , k − 1}. Suppose that M =M(G) is a cycle of bunches. Then, once a total order colouringof M is fixed, total order colourings of G correspond bijectively with right-resolvers Φ ∈ homR(G,M).Letting V (M) = {I0, . . . , Ip−1}, there is exactly one edge ai ∈ EIi(H) labeled 0 for each i. Thisyields a subgraph W of G consisting of edges labeled 0, which is a spanning subgraph of G of constantout-degree 1. Every graph of constant out-degree 1 consists of a set of state-disjoint cycles, togetherwith trees rooted on the cycles, directed toward their roots. The height of a tree is the maximum pathlength from a state in the tree to its root. Observe that the system ((∂Φ)−1(Ii), ai)p−1i=0 has a uniquetallest tree, in the sense of mappings, if and only if there is a unique tallest tree in W .We now present our interpretation of the main technical lemma in the proof of the road colouringtheorem (Lemma 10.4.6 in [14]). The following is not how the lemma is stated in [14], but one canfollow the proof and observe that it is equivalent.Lemma 4.9.2 (Trahtman). Let G be a strongly connected graph such that M(G) is a cycle of bunches.At least one of the following is true:1. G is itself a cycle of bunches.2. G has two distinct bunches whose outgoing edges have the same target.3. G admits a total order colouring with a unique tallest tree.With this result, we can prove our generalization of the road colouring theorem.Proof of Theorem 4.4.3. Let M = M(G). The claim is trivially true if |V (G)| = |V (M)|, in whichcase G = M . Suppose that it is true for all H with |V (H)| ≤R N and M(H) = M . Suppose that|V (G)| = N + 1. If G is bunchy, then we are done. If G is not bunchy, but has two states that can bein-amalgamated, then they are stable for some Φ ∈ homR(G,M) by Lemma 4.3.8. Let G′ = G/ ∼Φ.Then |V (G/ ∼Φ)| < |V (G)|, so by the inductive hypothesis, there is some bunchy H ≤S G/ ∼Φ≤S G.Now, suppose that G does not have two states that can be in-amalgamated—in particular, G doesnot have two distinct bunches whose outgoing edges have the same target. Since G is not bunchy,it is in particular not a cycle of bunches, so by Lemma 4.9.2, it admits a total order colouring withunique tallest tree. As remarked above, this total order colouring corresponds to some right-resolverΦ ∈ homR(G,M), which has ∼Φ nontrivial by Lemma 4.9.1. Then once more G/ ∼Φ is strictly smallerthan G. We can then apply Proposition 4.8.13 to conclude that any ≤S-minimal O with M = M(O)is a cycle of bunches. If O ≤S G, then O = OM,p for p = per(G)/per(M).50Chapter 5Encoding subshifts through sliding block codes5.1 IntroductionAs indicated in the introduction to the dissertation, this chapter proves the following theorem.Theorem 5.1.1. Let X be a mixing SFT, Y a mixing sofic shift, and π : X → Y a factor code. Let Zbe a subshift with topological entropy strictly less than that of Y . Then there exists a subshift Z ′ of Xconjugate to Z such that π|Z′ is injective, if and only if for every n ≥ 1, the number of periodic pointsof least period n in Z is at most the number of periodic points of least period n in Y with a π-preimageof equal least period.Theorem 5.1.1 is a generalization of the following theorem of Krieger in the case of unequal entropy;in particular, Theorem 5.1.1 reduces to Theorem 5.1.2 in the case that Y = X and π is the identity.Theorem 5.1.2 (Theorem 2 in [48]). Let Y be a mixing shift of finite type and Z a subshift. Thenthere is a subshift Z ′ ⊆ Y conjugate to Z if and only if Z and Y are conjugate or the (topological)entropy of Z is less than that of Y and, for every n ≥ 1, the number of periodic points of least periodn in Z is at most the corresponding number in Y .We note that with X,Y, Z, π as in the statement of Theorem 5.1.1, clearly there exists a subshiftZ ′ of X conjugate to Z such that π|Z′ is injective if and only if there exists a sliding block codeψ : Z → X such that π ◦ ψ is injective, in which case Z ′ = ψ(Z) ⊂ X. To verify the “only if”statement in Theorem 5.1.1, suppose that there is a subshift Z ′ of X conjugate to Z such that π|Z′ isinjective. Let y ∈ π(Z ′) be periodic. Let x = π|−1Z′ (y) be the unique preimage of y in Z ′. Then the orbitof x is in bijection with the orbit of y; otherwise, π would fail to be injective on the orbit of x, whichis contained in Z ′. In particular, x has finite orbit, so x is periodic, moreover with per(x) = per(y).Thus, every periodic point in π(Z ′) ⊂ Y has a periodic preimage in Z ′ ⊂ X of equal least period,which shows the necessity of the stated condition.Both Theorem 5.1.1 and Theorem 5.1.2 give conditions for the existence of an embedding in termsof entropy and a periodic point condition. The following corollary, which we prove in Section 5.5,shows that the periodic point condition can be removed in exchange for a small loss of injectivity.Corollary 5.1.3. Let X be a mixing SFT, Y a mixing sofic shift, and π : X → Y a factor code. LetZ be a subshift with topological entropy strictly less than that of Y . Then there exist a subshift Z ′, afinite-to-one factor code χ : Z ′ → Z, and a sliding block code ψ : Z ′ → X such that π ◦ ψ is injective.Moreover, if Z is mixing sofic with positive entropy (i.e. not a single fixed point), then Z ′ can be takento be a mixing SFT and χ can be taken to be almost invertible.The code χ is in fact injective except on points in Z ′ whose images in Z are backward-asymptoticto one of finitely many periodic points in Z. See Lemma 5.2.2 and Remark 5.2.3. From Corollary 5.1.3,we can immediately conclude the following, with h denoting the topological entropy of a subshift.51Corollary 5.1.4. Let X be a mixing SFT, Y a mixing sofic shift, and π : X → Y a factor code. Forany ε > 0, there exists a mixing SFT Z ⊂ X with h(Z) > h(Y )− ε such that π|Z is injective.The proof of Theorem 5.1.1 adapts the strategy used to prove Theorem 5.1.2 in [48, 49] andrelated results in [18]. The outline of the proof is as follows. We use a marker set, as in the proofof Theorem 5.1.2, to break points in Z into moderate blocks and long periodic blocks, separated bymarker coordinates. We code these separately using certain “data blocks” in Y , some of moderatelength and some long and periodic, where the long periodic data blocks come from periodic pointswith π-preimages of equal least period in X. A block in Z between marker coordinates is coded toa data block in Y which is shorter by an additive constant, so that there are gaps between the datablocks, filled with repetitions of a “blank” symbol. We then lift the data blocks from Y to data blocksfrom X, then replace the blanks with a “stamp” block from X to form a valid point in X. The stampblock is chosen to ensure that once the point in X is coded into Y by π, the locations of the stamp,and thus of the marker coordinates, can be recognized. These manipulations of markers, blanks, andstamps are presented in detail in Section 5.3, while the quantitative arguments required to constructthe data blocks and stamps are given in Section 5.4.The statement of Theorem 5.1.2 is false for X merely mixing sofic, and to date there is no knowncharacterization of the subshifts that embed into a given mixing sofic shift, though some sufficientconditions are known [18, 73]. Theorem 5.1.1 sheds some light on this problem, without resolving it.Salo-To¨rma¨ have answered [67] the following related question: let Y be a mixing sofic shift and Z ⊂ Ya mixing SFT. For which such Y, Z do there exist a mixing SFT extension π : X → Y and a (mixingSFT) Z ′ ⊂ X such that π|Z′ : Z ′ → Z is a conjugacy? However, it is unclear how the conditions givenin that answer compare to those in Theorem 5.1.1, or to the results given in [73]. As a final relatedquestion, when Y is an SFT and Z is conjugate to Y , the existence of an SFT Z ′ ⊂ X conjugate to Zsuch that π|Z′ : Z ′ → Y is a conjugacy, i.e. is surjective as well as injective, has been studied in [33],continuing work from [54].5.2 Conventions, definitions, and background5.2.1 Subshifts and sliding block codesWe recall the definition, from earlier in the paper, of a subshift over Z with alphabet A. A subshiftX ⊂ AZ is characterized by the set B(X) of blocks w ∈ A∗ such that X∩[w] ̸= ∅, called the language ofX. When the intended subshift X is clear, we write [w]i for X ∩ [w]i. We write Bn(X) = B(X) ∩An.We can equivalently characterize a subshift by a set of forbidden words F ⊂ A∗, writing XF :=AZ \⋃w∈F ⋃i∈Z[w]i. Note that in general F ⊊ A∗ \ B(XF ). For a given subshift X ⊂ AZ, there maybe several different sets of forbidden words F ⊂ A∗ such that X = XF . A shift of finite type (SFT)is a subshift X such that X = XF for some finite set F . A k-step SFT over A is an SFT of the formX = XF for some set F ⊂ Ak+1.We recall from Chapter 3 that, for subshifts X,Y , a function ϕ : X → Y is continuous andshift-equivariant if and only if it is a sliding block code, which means that there exist m,n ≥ 0 andΦ : Bm+n+1(X) → B1(Y ) such that for every x ∈ X and every i ∈ Z, ϕ(x)i = Φ(x[i−m,i+n]). We saythat ϕ is a k-block code if m + n + 1 = k. A factor code is a surjective sliding block code, and for asliding block code ϕ defined on a subshift X, we say that the image ϕ(X) is a factor of X, and that X,or more properly ϕ : X → ϕ(X), is an extension of ϕ(X). We recall also that a sofic shift is any factorof a shift of finite type. An injective sliding block code is called an embedding, and a bijective slidingblock code is called a conjugacy. The properties of being sofic and of finite type are both invariantunder conjugacy.As in Chapter 3, a subshift X is said to be irreducible if for all u,w ∈ B(X), there exists v ∈ B(X)such that uvw ∈ B(X), and strongly irreducible with gap g ≥ 1 if, for any u,w, we can take alwaystake v ∈ Bg(X). Any factor of an irreducible (resp. strongly irreducible) subshift is irreducible (resp.strongly irreducible). A periodic point in a subshift X is a point x ∈ X with x = σnx for some52n ≥ 1—we say that x has period n. The least period per(x) of a periodic point x is the least n suchthat σnx = x. Note that |{σnx |n ∈ Z}| = per(x). We write P (X) for the set of periodic points in asubshift X, Qn(X) for the set of periodic points of least period n, and qn(X) = |Qn(X)|. The numberof periodic points of a given least period is a conjugacy invariant.It is a theorem that periodic points are dense in any irreducible shift of finite type. As in Chapter3, the period per(X) of an irreducible shift of finite type X is the gcd of the periods of the periodicpoints of X. An irreducible SFT with period 1 is said to be aperiodic. An irreducible SFT is stronglyirreducible if and only if it is aperiodic, if and only if has periodic points of all sufficiently high periods.For irreducible sofic shifts, strong irreducibility is equivalent to having periodic points of all sufficientlyhigh periods, which clearly implies that the periods have gcd 1, but the reverse implication fails. Forexample, consider the odd shift over {0, 1}, in which the block 10n1 is permitted only for odd n.This is an irreducible sofic shift which contains the fixed point 0∞, so the periods of periodic pointstrivially have gcd 1. However, the odd shift has no other periodic points of odd period. We followthe convention of the literature in referring to strongly irreducible sofic shifts (in particular SFTs) asmixing sofic shifts (mixing SFTs), because they are also characterized by a topological mixing property,but we will not use that property explicitly, so we do not define it here.The following definition is new, and we use it extensively.Definition 5.2.1. Let X and Y be subshifts and let π : X → Y be a factor code. We write Rn(π) forthe set of periodic points y ∈ Y such that y = π(x) for some periodic point x ∈ X with per(x) = per(y).We write rn(π) = |Rn(π)|.For a subshift X, the (topological) entropy of X is the value h(X) = infn≥1 1n log |Bn(X)|; in fact,the limit limn→∞ 1n log |Bn(X)| exists and is equal to h(X). For a mixing sofic shift (in particular, amixing SFT) X, we also have h(X) = limn→∞ 1n log qn(X). Entropy is non-increasing under factorcodes and is thus a conjugacy invariant, though certainly not a complete invariant. For any irreduciblesofic shift X, and any proper subshift V ⊂ X, we have h(V ) < h(X). In Section 5.4, we use thefollowing lemma of Marcus, which allows us to approximate a sofic shift from the inside by SFTs interms of entropy.Lemma 5.2.1 (Proposition 3 in [52]). Let Y be a sofic shift. For every ε > 0, there exists an irreducibleSFT U ⊆ Y with h(U) > h(Y )− ε.For any subshift X and any k ≥ 1, we can form the kth higher block shift X [k] with alphabetBk(X), wherew = (a1,1a1,2 . . . a1,k)(a2,1a2,2 . . . a2,k) . . . (aℓ,1aℓ,2 . . . aℓ,k) ∈ B(X [k])if any only if for each i, j we have ai,j = ai+1,j−1, so thatw = (a1a2 . . . ak)(a2a3 . . . ak+1) . . . (aℓ+1aℓ+2 . . . aℓ+k),and a1a2 . . . ak+ℓ ∈ B(X). Observe that X and X [k] are conjugate for any subshift X and any k ≥ 1.Moreover, if X is an m-step SFT and k ≤ m − 1, then X [k] is an (m − k)-step SFT. In particular,every SFT is conjugate to a 1-step SFT, and every sliding block code on an SFT can be written asa composition of a conjugacy and a 1-block code. We will therefore frequently assume WLOG that agiven sliding block code on an SFT is a 1-block code on a 1-step SFT.For a sliding block code on an irreducible shift of finite type, either every fiber is a finite set (indeed,of bounded cardinality), in which case the code is said to be finite-to-one and the entropy of the imageis equal to that of the domain, or almost every fiber is uncountable, and the entropy of the imageis strictly less than that of the domain. In the finite-to-one case, the minimum fiber cardinality isgeneric and is known as the degree. In particular, a code (on an irreducible SFT) with degree 1 is saidto be almost invertible. It is a theorem that every irreducible (resp. mixing) sofic shift is an almostinvertible factor of an irreducible (resp. mixing) SFT. We use the following construction of almostinvertible codes, known as the “blowing-up lemma”, in the proof of Corollary 5.1.3 in Section 5.5.53Lemma 5.2.2 (Lemma 10.3.2, [49]). Let Z be a mixing SFT and let z ∈ Z be a periodic point withleast period p. Let M ≥ 1. Then there exist a mixing SFT Z ′ and an almost invertible factor codeχ : Z ′ → Z such that the preimage of the orbit of z under χ is a single orbit of length Mp. Moreover,every periodic point in Z not in the orbit of z has unique preimage under χ.Remark 5.2.3. Note that in [49], the extension χ in Lemma 5.2.2 is only stated to be finite-to-one, butthe existence of periodic points having unique preimage already implies almost invertibility. Indeed,the construction in [49], based on work in [18], in fact shows that χ is injective except on the pointsthat are backward-asymptotic to points in the preimage of the orbit of z, where we say that two pointsz, z′ are backward-asymptotic if d(σnz, σnz′)→ 0 as n→ −∞.5.2.2 Markers and Markov approximationsWe now recall the constructions with markers and long periodic blocks that are at the heart of theproof of Theorem 5.1.1. For an alphabet A, we say that a block w = w1 . . . wn ∈ An is k-periodic, orhas self-overlap of n− k, if for 1 ≤ i ≤ n− k we have wi = wi+k. A given block may be k-periodic forseveral different k.Lemma 5.2.4 (Lemma 2.3 in [18]). Let Z be a subshift, let N ≥ 1, and a, b ∈ Z with b− a ≥ 2N . Letz ∈ Z. If for every i ∈ [a +N, b −N ] there exists p ≤ N − 1 such that z[i−N,i+N ] is p-periodic, thenthere is at most one periodic point ζ ∈ Z with per(ζ) ≤ N − 1 and ζ[a,b] = z[a,b]. If Z is a 1-step SFT,then such a ζ exists.Lemma 5.2.5 (Lemma 2 in [48]). Let Z be a subshift. For any N ≥ 1, there exists a subset F ⊂ Z,which can be taken to be a finite union of cylinders, such that:1. the sets σiF , 0 ≤ i ≤ N − 1, are all disjoint, and2. if z /∈ σiF for all −(N − 1) ≤ i ≤ (N − 1), then z[−N,N ] is p-periodic for some p ≤ N − 1.Definition 5.2.2 (marker set). With Z, N , and F as in Lemma 5.2.5, we refer to F as a marker setfor Z with parameter N .For any subshift X and any n ≥ 1, we can form the nth Markov approximation Xn, which is theSFT defined by allowing precisely the blocks of length n which appear in X. Clearly Xn+1 ⊂ Xn. It isan exercise to show that for any ε > 0 and anyN ≥ 1, there existsN ′ ≥ N such that h(XN ′) < h(X)+εand qn(XN ′) = qn(X) for all n ≤ N . In Lemma 5.2.6, we use the Markov approximation, togetherwith higher block shifts, to show that in the proof of Theorem 5.1.1, we can assume WLOG that Z isa 1-step SFT, which allows us to apply Lemma 5.2.4.We remark that there are versions of Lemma 5.2.5 which obviate the need for Lemma 5.2.4. How-ever, for our purposes in this paper, embedding Z into an SFT has the additional benefit that the rateof convergence of 1n log qn(Z) to h(Z) can be easily estimated when Z is an SFT (see e.g. [49], pp.349-351), which gives a procedure for deciding whether a given X,Y, π, Z satisfy the periodic pointcondition in Theorem 5.1.1, assuming that h(Z) < h(Y ) (namely, compute N ≥ 1 such that for alln ≥ N , qn(Z) < rn(π), then check all n ≤ N to determine whether qn(Z) ≤ rn(π)).Lemma 5.2.6. Let X be a mixing SFT, Y a mixing sofic shift, and π : X → Y a factor code. Let Zbe a subshift with h(Z) < h(Y ) and qn(Z) ≤ rn(π) for all n ≥ 1. Then there exists a 1-step SFT Z ′such that Z embeds into Z ′, h(Z ′) < h(Y ), and qn(Z ′) ≤ rn(π) for all n ≥ 1.We defer the proof of Lemma 5.2.6 to Section 5.5.545.3 CodingIn Section 5.3.1, we introduce two coding constructions, namely subshifts with blanks adjoined, Defi-nition 5.3.1, and stamps, Definition 5.3.2, then use them to create one side of an interface between Zon the one hand and π : X → Y on the other. In Section 5.3.2, we use markers in Z to construct theother side of this interface. In Section 5.3.3, we use stamps to give a construction of SFTs analogousto S-gap shifts. We use this construction in Section 5.4.2 to construct the shifts that are used inSection 5.3.1 and Section 5.3.2.5.3.1 Blanks and stampsAs outlined in Section 5.1, the proof of Theorem 5.1.1 involves coding Z into X via certain intermediatesubshifts which consist of long “data” blocks separated by blanks. We now define this constructionprecisely.Definition 5.3.1 (subshift with blanks adjoined). Let W be a subshift and let N, ℓ ≥ 1 with ℓ < N .Let ∗ be a symbol not appearing in the alphabet of W . Let M ⊂ ⋃2Nn=1 Bn(W ) be a set of blocksand let Q ⊂ ∪2N−1n=1 Qn(W ) be a set of periodic points. Denote by Blanks(M,Q,N, ∗, ℓ) the subshift inwhich each point is of the form . . . w−1 ∗ℓ w0 ∗ℓ w1 . . . where either wi ∈ M or wi = yT where y ∈ Qand T = (−∞, 0], [0,+∞), (−∞,∞), or [0,m] with m ≥ 2N .The purpose of the Blanks construction is to provide an interface between the channel π : X → Yand the subshift Z to be embedded. One side of this interface, namely the embedding of a Blankssubshift into X, is specified in Proposition 5.3.4. The construction involves particular blocks, whichwe call stamps, that can be unambiguously recognized in the following sense:Definition 5.3.2 (stamp). Let Y be a subshift, W ⊂ Y a proper subshift, and k ≥ 1. We say thatµ ∈ B(Y ) \ B(W ) is a (Y,W, k) stamp if for all u1, u2 ∈ B(W ) and v1, v2 ∈ Bk(Y ), µ appears exactlyonce in u1v1µv2u2.Remark 5.3.1. In Definition 5.3.2, continuing with the notation there, we do not explicitly requireu1v1µv2u2 to be legal in Y . Doing so would neither affect the results nor simplify the proofs. In all ofthe examples we consider, such blocks will in fact be legal in Y .Proposition 5.3.2. Let Y be a strongly irreducible subshift with gap g and W ⊂ Y a proper subshift.For every k ≥ g and every sufficiently large n, there exists a (Y,W, k) stamp of length n.We defer the proof of Proposition 5.3.2 to Section 5.4.1, but before applying stamps in Proposi-tion 5.3.4, we prove a lemma that expresses how stamps are actually used in our constructions.Lemma 5.3.3. Let Y be a subshift, W ⊂ Y a proper subshift, k ≥ 1, and µ ∈ B(Y )\B(W ) a (Y,W, k)stamp. Let N ≥ |µ|. Then for any γ± ∈ Bk(Y ), and any w ∈ B(W ) with |w| ≥ N , the stamp µappears exactly twice in the block µγ−wγ+µ.Proof. By the hypotheses on µ, γ±, and w, and Definition 5.3.2, µ appears exactly once in eachsubblock µγ−w, wγ+µ. An appearance of µ other than at the positions explicitly indicated musttherefore overlap both of these subblocks. Since |w| ≥ |µ|, µ must therefore be a subblock of w,contradicting the hypothesis that w ∈ B(W ) and µ ∈ B(Y ) \ B(W ).We now give one of the main coding constructions (Proposition 5.3.4), embedding a subshift withblanks adjoined, and with blocks from a subshift V ⊂ X, into X via a sliding block code γ, such thatπ ◦ γ is injective. The large amount of data in the statement is representative of the complexity of theconstruction and the modular nature of the proof.55Proposition 5.3.4. Let X be a mixing SFT with gap g, let Y be a mixing sofic shift, and let π : X → Ybe a 1-block factor code.Let V ⊂ X, W = π(V ) ⊂ Y be proper subshifts. Let ∗ be a symbol not appearing in the alphabetsof X,Y . Let N ≥ 1. Let M ⊂ ⋃2N−1n=1 Bn(W ) be a collection of blocks, and let R ⊂ ⋃N−1n=1 Rn(π|V ) be aunion of finite (i.e. periodic) orbits inW with π-preimages of equal cardinality in V . Let κ :M → B(V )be an injection such that π◦κ(w) = w for each w ∈M , and let Mˆ = κ(M). Similarly, let λ : R→ P (V )be a shift-commuting injection such that π ◦ λ(y) = y for each y ∈ R, and let Rˆ = λ(R). Then for anyℓ ≥ 1, Blanks(M,R,N, ∗, ℓ) and Blanks(Mˆ, Rˆ,N, ∗, ℓ) are conjugate.Moreover, let µ ∈ B(Y ) \ B(W ) be a (Y,W, g) stamp such that |µ| ≤ N , and suppose that M ⊂⋃2N−1n=N Bn(W ), i.e. M contains no blocks of length less than N . Then there exists a sliding block codeγ : Blanks(Mˆ, Rˆ,N, ∗, |µ|+ 2g)→ X such that π ◦ γ is injective.Proof. First, the conjugacy. Let W [∗] = Blanks(M,R,N, ∗, ℓ) and V [∗] = Blanks(Mˆ, Rˆ,N, ∗, ℓ). Con-sider the 1-block code π[∗] defined on V [∗] by the block map π[∗](a) = π(a) for a in the alphabet of Vand π[∗](∗) = ∗. We claim that W [∗] = π[∗](V [∗]) and that π[∗] : V [∗]→ W [∗] is a conjugacy. To seethat W [∗] ⊆ π[∗](V [∗]), note that any ξ ∈ V [∗] is of the formξ = . . . w−1 ∗ℓ w0 ∗ℓ w1 . . .where either wi ∈ Mˆ or wi = xT for some x ∈ Rˆ and T an interval with 2N + 1 ≤ |T |. If wi ∈ Mˆ ,then π(wi) ∈M ; if wi = xT for some x ∈ Rˆ, then π(wi) = π(x)T , and π(x) ∈ R. Thereforeπ[∗](ξ) = . . . π(w−1) ∗ℓ π(w0) ∗ℓ π(w1) · · · ∈W [∗]This shows that indeed W [∗] ⊂ π[∗](V [∗]). Similarly, any η ∈W [∗] is of the formη = . . . w−1 ∗ℓ w0 ∗ℓ w1 . . .where either wi ∈ M or wi = yT for some y ∈ R and T an interval with 2N + 1 ≤ |T | ≤ ∞. For ηof this form, using Lemma 5.2.4, we can use the injections κ, λ to reconstruct a unique ξ ∈ V [∗] suchthat π[∗](ξ) = η.We now suppose that each block in M has length at least N and that we have a (Y,W, g) stampµ ∈ B(Y ) \ B(W ) such that |µ| ≤ N . Under these assumptions, we construct a sliding block codeγ : V [∗] → X and show that π ◦ γ is injective. Fix a π-preimage µˆ of µ, and let ℓ = |µ| + 2g.Using the hypothesis that X is a mixing 1-step SFT, define maps γ± : B1(V )→ Bg(X) such that, fora, b ∈ B1(V ), we have µˆγ−(a)a, bγ+(b)µˆ ∈ B(X). We then have a sliding block code γ : V [∗] → X,given by replacing each block b ∗ℓ a by bγ+(b)µˆγ−(a)a, and leaving the non-blank symbols unchanged.Letξ = · · · ∗ℓ v−1 ∗ℓ v0 ∗ℓ v1 ∗ℓ · · · ∈ V [∗]Thenγ(ξ) = . . . µˆγ−(a0)v0γ+(b0)µˆ . . .where ai, bi are, respectively, the initial and terminal symbols of vi. In turn, we haveπ ◦ γ(ξ) = . . . µ(π ◦ γ−(a0))π(v0)(π ◦ γ+(b0))µ . . .Moreover, by Lemma 5.3.3 and the lower bound on lengths of blocks in M , it follows that µ appears inπ◦γ(ξ) only where µˆ appears at the same position in γ(ξ). By replacing, in π◦γ(ξ), each appearance ofµ, and the blocks of length k to the left and right of µ, with ∗ℓ, we obtain the point · · · ∗ℓ π(v0)∗ℓ · · · =π[∗](ξ) ∈ Blanks(M,R,N, ∗, ℓ), from which ξ can be recovered since π[∗] is a conjugacy.565.3.2 Blanks and markersWe now prove a lemma that encapsulates the use of marker constructions in our proof of Theorem 5.1.1.Lemma 5.3.5. Let Z,W be subshifts with Z a 1-step SFT. Let N, ℓ ≥ 1 be such that qn(Z) ≤ qn(W )for n ≤ N − 1 and |Bn(Z)| ≤ |Bn−ℓ(W )| for N + ℓ ≤ n ≤ 2N + ℓ − 1. Let M ⊂⋃2N−1n=N Bn(W )and Q ⊂ ⋃N−1n=1 Qn(W ) be a union of finite (i.e. periodic) orbits such that |Bn(Z)| ≤ |M ∩ Bn−ℓ(W )|for N + ℓ ≤ n ≤ 2N + ℓ − 1, and qn(Z) ≤ |Q ∩ Qn(W )| for n ≤ N − 1. Then Z embeds intoBlanks(M,Q,N, ∗, ℓ).Remark 5.3.6. The lower bound on the length of blocks in M is not in fact needed for Lemma 5.3.5,but it is needed in order to apply Lemma 5.3.5 in conjunction with Proposition 5.3.4 in the proof ofTheorem 5.1.1 below.Proof. Let F be a marker set for Z with parameter N . For z ∈ Z, let A(z) = {i ∈ Z |σiz ∈ F}.Enumerate each A(z) as {aj(z)}j∈J(z) where the index set J(z) may be the empty set, or a finite set,or the integers, or the positive or negative natural numbers, and where aj(z) < aj+1(z) for each j.We refer to the elements of A(z) as marker coordinates for z. Say that T is a marker interval for z if:T = [aj(z), aj+1(z)) where aj(z), aj+1(z) are both defined; or T = [a0(z),∞) if a0(z) = maxA(z) <∞;or T = (−∞, a0(z)] if a0(z) = minA(z) > −∞; or T = (−∞,∞) if A(z) = ∅.We construct an embedding of Z into Blanks(M,Q,N, ∗, ℓ) by constructing a function Φ that maps ablock occurring between marker coordinates to a data block padded with ∗ℓ. Let cn : Qn(Z)→ Qn(W )be shift-commuting injections for n ≤ N − 1. Let dn : Bn(Z) → Bn−ℓ(W ) ∩ M be injections forN + ℓ ≤ n ≤ 2N + ℓ − 1. (This is despite the fact that the parameter for the marker set F is N .We need the extra space in order to pad data blocks with blanks.) For a block w ∈ Bn(Z) withN + ℓ ≤ n ≤ 2N + ℓ − 1, let Φ(w) = ∗ℓdn(w). For z ∈ Z periodic with n = per(z) ≤ N − 1,if m ≥ 2N + ℓ, let Φ(z[0,m]) = ∗ℓcn(z)[ℓ,m]. Similarly, let Φ(z[0,∞)) = ∗ℓcn(z)[ℓ,∞). Finally, letΦ(z(−∞,0]) = cn(z)(−∞,0] and let Φ(z) = cn(z). Observe that Φ is injective, by Lemma 5.2.4.Define ϕ : Z → W by declaring that ϕ(z)T = Φ(zT ) whenever T is a marker interval for z. Weneed to show that ϕ is an embedding. Certainly ϕ is shift-commuting, since, if T is a marker intervalfor z, then T − 1 is a marker interval for σz, soϕ(σz)T−1 = Φ((σz)T−1) = Φ(zT ) = ϕ(z)T = (σϕ(z))T−1Thus indeed ϕ(σz) = σϕ(z). Moreover, ϕ is injective because the appearances of ∗ℓ in ϕ(z) allow us toreconstruct the marker coordinates, and then the injectivity of Φ allows us to reconstruct zT for eachmarker interval T for z.We need to show finally that ϕ is continuous, i.e. that for z ∈ Z, ϕ(z)0 depends only on z[−L,L] forsome finite L independent of z. To see this, let L′ be such that F is a union of cylinders on [−L′, L′].Let L = L′ + 2N . By examining z[−L,L], we can determine whether there are marker coordinates forz in [−2N, 0) and/or [0, 2N ]. If each of these intervals contains a marker coordinate, then ϕ(z)0 isdetermined by zT where T ⊂ [−2N, 2N ] is the unique marker interval for z containing 0. If at leastone of [−2N, 0), [0, 2N ] has no marker coordinates, then 0 is in a long marker interval for z. If thereis a marker coordinate in (−ℓ, 0], then ϕ(z)0 = ∗. Otherwise, by Lemma 5.2.4, ϕ(z)0 is determined byany subblock z[a,b] where a < 0 ≤ b, b− a ≥ 2N , and [a, b] contains no marker coordinate for z. Thisconcludes the proof that ϕ is continuous.The remainder of the proof of Theorem 5.1.1 follows from the following proposition, the proof ofwhich is taken up in Section 5.4.Proposition 5.3.7. Let X be a mixing SFT with gap g, Y a mixing sofic shift, and π : X → Y afactor code. Let Z be a subshift with h(Z) < h(Y ) and qn(Z) ≤ rn(π) for every n ≥ 1. Then thereexist: N ≥ 1, subshifts V ⊂ X, W = π(V ) ⊂ Y , and a (Y,W, g) stamp µ ∈ B(Y ) \ B(W ), such that|µ| ≤ N , qn(Z) ≤ rn(π|V ) for n ≤ N − 1 and |Bn(Z)| ≤ |Bn−ℓ(W )| for N + ℓ ≤ n ≤ 2N + ℓ− 1, whereℓ = |µ|+ 2g.57Proof of Theorem 5.1.1. By Lemma 5.2.6, assume WLOG that Z is a 1-step SFT. Let N , ℓ, V ⊂ X,W = π(V ) ⊂ Y , and µ be as in Proposition 5.3.7. Let M ⊂ ⋃2N−1n=N Bn(W ) be as in Lemma 5.3.5, andlet R ⊂ ⋃N−1n=1 Rn(π|V ) be a union of finite orbits, such that qn(Z) ≤ |R ∩ Rn(π|V )| for n ≤ N − 1.Each of which the orbits in R is, by the definition of Rn, necessarily the image of an orbit with equalcardinality in V . Here, R takes the role that Q plays in Lemma 5.3.5, but in Lemma 5.3.5, there wasno channel π, and thus no preimage requirement, hence the change in notation. By Lemma 5.3.5, letϕ : Z → Blanks(M,R,N, ∗, ℓ) be an embedding.Let Mˆ , Rˆ be as in Proposition 5.3.4, let π[∗] : Blanks(Mˆ, Rˆ,N, ∗, ℓ) → Blanks(M,R,N, ∗, ℓ) bea conjugacy, and let γ : Blanks(Mˆ, Rˆ,N, ∗, ℓ) → X be an embedding such that π ◦ γ is injective (byProposition 5.3.4, using µ). Then ψ = γ ◦ (π[∗])−1 ◦ ϕ : Z → X is a sliding block code such that π ◦ ψis injective.5.3.3 Stamps and SFTsIn this subsection, we prove Lemma 5.3.10, which, in conjunction with Lemma 5.2.1, allows us, inProposition 5.4.4, to construct a mixing SFT V ⊂ X such that the image π(V ) ⊂ Y is a propersubshift of Y but has entropy at least h(Y ) − ε for a given ε > 0. It may be possible to give a moreefficient construction of such a V , but we have not found one. We first prove Lemma 5.3.8, which isrelated to the characterization of SFTs among S-gap shifts (Theorem 3.3 in [26]).Lemma 5.3.8. Let X be a mixing SFT with gap g and let V0 ⊂ X be an SFT. Let k ≥ g and letµ ∈ B(X) \ B(V0) be an (X,V0, k) stamp. Let N ≥ |µ| and let V1 ⊂ X be the closure of the set ofpoints of the form. . . v−1γ+−1µγ−0 v0γ+0 µγ−1 v1 · · · ∈ Xwhere, for each i, γ±i ∈ Bk(X) and vi ∈ B(V0) with |vi| ≥ N . Then V1 is a mixing SFT.Remark 5.3.9. Note that V1, as defined in the statement of Lemma 5.3.8, clearly contains V0.Proof. Assume without loss of generality that X is a 1-step SFT. We first perform a small recodingfor convenience, specifically to make it easier to recognize stamps, by replacing X by a conjugate shiftXˆ. For each x ∈ X, define xˆ as follows: if x[i,i+|µ|) = µ, then for each i ∈ [−k, |µ|+ k), let a = xi andlet xˆi = aˆ, where for symbols a, b in the alphabet of X, we have aˆ = bˆ if and only if a = b, and the setof symbols with hats is disjoint from the alphabet of X. If there is no j ∈ (i − (|µ| + k), i + k] withx[j,j+|µ|) = µ, then let xˆi = xi. Clearly the map x 7→ xˆ is a sliding block code, and it is just as clearlyinjective, since we recover x from xˆ by dropping hats. Therefore Xˆ = {xˆ |x ∈ X} is a mixing SFT,conjugate to X.Denote by Vˆ1 ⊂ Xˆ the image of V1 under the map x 7→ xˆ. Let ℓ = |µ|+2k. Since µ is an (X,V0, k)stamp, and N ≥ |µ|, blocks of the form γ+i µγ−i+1 do not overlap in any point in V by Lemma 5.3.3,so symbols with hats occur in Vˆ1 in blocks of length exactly ℓ. The blocks of symbols with hats areseparated by blocks from V0. Since Vˆ1 is the image of V under a conjugacy X → Xˆ, V1 is an SFT ifand only if Vˆ1 is an SFT.Let m ≥ N be such that Xˆ and V0 are m-step SFTs. We claim that if xˆ ∈ Xˆ is such thatx[i,i+m] ∈ Bm+1(Vˆ1) for all i ∈ Z, then xˆ ∈ Vˆ1, which means precisely that V is an m-step SFT. Toprove this claim, let F ⊂ Bm+1(X) be the set of blocks of length m+ 1 which contain at least one ofthe following: a block of length greater than ℓ in which all symbols have hats; a block without hatsthat is not in B(V0); or a block of symbols without hats, of length less than N , bounded on both sidesby symbols with hats. Note that F is disjoint from Bm+1(Vˆ1). Suppose that xˆ[i,i+m] /∈ F for all i ∈ Z.Then any block of symbols with hats in xˆ has length exactly ℓ, and is thus of the form γ+µγ−, whereγ± ∈ Bg(X) (with hats added). Furthermore, the blocks separating the blocks with hats must havelength at least N and must be in B(V0), since every subblock of length m+ 1 is in B(V0) and V0 is anm-step SFT. Thus indeed xˆ ∈ Vˆ1, so Vˆ1 is indeed an SFT.58To see that V1 is irreducible, let u−, u+ ∈ B(V1). We need to construct u0 ∈ B(V ) such thatu−u0u+ ∈ B(V1). We do so as follows. Extend u− on the right to form a block v− ∈ B(V1), which beginswith u− and ends with γ+−1µγ−0 where γ+−1, γ−0 ∈ Bk(V1). (It is possible that u− overlaps γ+−1µγ−0 .) Letv0 ∈ BN (V0) be such that v−v0 ∈ B(X). Similarly, extend u+ on the left to form a block v+ ∈ B(V1)which ends with u+ and begins with γ+0 µγ−1 , where γ+0 , γ−1 ∈ Bk(V1) and v0γ+0 ∈ B(X). Let x± ∈ B(V1)be such that x−[0,∞) begins with v− and x+(−∞,−1] ends with v+. Let x = x−(−∞,−1]v−v0v+x+[0,∞). Thenx ∈ X since X is a 1-step SFT. Moreover, x ∈ V1, since the tails x−(−∞,−1]v− and v+x+[0,∞) appear inV1 and are joined together in a way that creates no violations of the restrictions defining V1. Lettingu0 be the block appearing between u−, u+, such that v−v0v+ = u−u0u+ ∈ B(V ), the construction iscomplete, showing that V1 is indeed irreducible.To see that V1 is mixing, let u1, u2 ∈ B(V0) with |u1| > m, where m is as above, and |u2| = |u1|+1.Let γ±i ∈ B(X), i = 1, 2, be such that uiγ+i µγ−i ui ∈ B(X). Then xi = (uiγ+i µγ−i )∞ ∈ V1 for bothi = 1, 2. Indeed, certainly xi ∈ X, since uiγ+i µγ−i ui ∈ B(X) and X is a 1-step SFT. Moreover, per(xi)divides ℓ+ |ui|, and gcd(ℓ+ |u1|, ℓ+ |u2|) = gcd(ℓ+ |u1|, ℓ+ |u1|+1) = 1, so gcd(per(x1),per(x2)) = 1.Since V1 is an irreducible SFT with periodic points of coprime periods, V1 is mixing.As advertised, we now use Lemma 5.3.8 to prove the following lemma, which is applied in the proofof Proposition 5.4.4, which in turn is the main input to the proof of Proposition 5.3.7.Lemma 5.3.10. Let X be a mixing SFT, Y a mixing sofic shift, and π : X → Y a factor code. LetW0 ⊊ Y be an SFT. Then there exists a mixing SFT V1 ⊂ X with W0 ⊂ π(V1) ⊊ Y .Proof. Let V0 = π−1(W0) ⊂ X. Note that V0 is an SFT since W0 is an SFT. Let g be the mixing gapof X. Let y ∈ Y \W0 be a periodic point with least period k ≥ g. Such a y certainly exists becauseperiodic points are dense in Y and W0 is a proper subshift. Let k′ be such that y[0,k′) /∈ Bk′(W0). Letℓ = k + k′. Then every ℓ-block in y is forbidden in W0. In particular, for any x ∈ π−1({y}) and anyi ∈ Z, we have x[i,i+ℓ) /∈ B(V0).By Proposition 5.3.2, let µ be an (X,V0, g) stamp. Let V1 consist of the closure of the set of points ofthe form . . . v−1γ+−1µγ−0 v0γ+0 µγ−1 v1 · · · ∈ X where each vi ∈ B(V0) with |vi| ≥ ℓ and each γ±i ∈ Bg(X).By Lemma 5.3.8, V1 is indeed a mixing SFT. Note that every point in V1 contains ℓ-blocks permittedin V0, so V1 is disjoint from π−1({y}), and therefore π(V1) ⊊ Y .5.4 CountingIn this section, we prove Proposition 5.3.2 and Proposition 5.3.7, which state the existence and prop-erties respectively of the stamps and the shifts V ⊂ X,W ⊂ Y used in Section 5.3. Section 5.4.1contains two results required for the proof of Proposition 5.3.2, one (Lemma 5.4.1) showing that mostblocks in a subshift with positive entropy have little self-overlap, and the other (Lemma 5.4.2) showingthat one can assume, at the cost of a small loss of entropy, that a given sufficiently long block appearssyndetically in a mixing sofic shift. Section 5.4.2 then gives a crucial asymptotic result on the num-ber of periodic points in Y with a preimage of equal least period in X, and applies the results fromSection 5.3.3 to construct the shifts V and W .5.4.1 Self-overlap and stampsWe begin by showing that most blocks have very little self-overlap, which we use both to constructstamps and to determine the asymptotic number of periodic points in Y with a π-preimage of equalleast period.Lemma 5.4.1. Let Y be a subshift with h(Y ) > 0. For every α ∈ (0, 1), there exist N ≥ 1 and b > 0such that for every n ≥ N , there are at least (1 − exp(−bn)) exp(nh(Y )) blocks w ∈ Bn(Y ) with noself-overlap of more than αn.59Proof. Let ε = 12 (α−1−1)h(Y ), so that α(h(Y )+ε) < h(Y ). Let r = exp(h(Y )) and s = exp(h(Y )+ε).Note that sα < r < s and that rn ≤ |Bn(Y )| for every n. Let N0 be large enough that for all n ≥ N0,we have |Bn(Y )| ≤ sn. Let C1 =∑N0−1k=1 |Bk(Y )|. Then the number of blocks in X of length n withself-overlap of more than αn is at most⌈αn⌉∑k=1|Bk(Y )| ≤N0−1∑k=1|Bk(Y )|+⌈αn⌉∑k=N0|Bk(Y )|≤ C1 +⌈αn⌉∑k=N0sk≤ C1 + sαn+2 − sN0s− 1≤ C2sαnwhereC2 = C1 +s2s− 1Let N > (1−α)h(Y )−αεlogC2 . Then, for n ≥ N , the number of blocks in Y of length n with no self-overlapby more than αn is at least|Bn(Y )| −⌈αn⌉∑k=1|Bk(Y )| ≥ rn − C2sαn= rn(1− C2(sαr)n)> (1− exp(−bn)) exp(nh(Y ))where we can takeb =12log(C2( rsα)N)= (1− α)h(Y )− αε− 1NlogC2which is positive by the choice of N .We now control the entropy loss incurred by requiring a given long block to appear syndetically.Lemma 5.4.2. Let Y be a strongly irreducible subshift with h(Y ) > 0. For every ε > 0, there existβ ∈ (0, 1) and N ≥ 1 such that for every n ≥ N and every θ ∈ B⌊βn⌋(Y ), the subshift S ⊂ Y consistingof points y ∈ Y in which θ appears at least once in y[i,i+n) for every i ∈ Z has entropy at least h(Y )−ε.Proof. Let g be the gap for Y . Let β = min{ε/(4h(Y )), 1/2} and let N = ⌈4(2g − 1)h(Y )/ε⌉. Letn ≥ N and fix θ ∈ B⌊βn⌋(Y ). For m ≥ n, and for all u1, . . . , uk ∈ Bn−⌊βn⌋−2g(Y ), where k = ⌊m/n⌋,there exist v±1 , . . . , v±k ∈ Bg(Y ) and v0 ∈ Bm−kn(Y ) such thatv0θv−1 u1v+1 θv−2 u2v+2 . . . θv−k ukv+k ∈ Bm(Y )60Therefore, by manipulation of logarithms and the fact that h(Y ) = infℓ≥1 1ℓ log |Bℓ(Y )| by definition,|Bm(S)| ≥ |Bn−⌊βn⌋−2g(Y )|⌊m/n⌋1mlog |Bm(S)| ≥ 1mlog(|Bn−⌊βn⌋−2g(Y )|(m−1)/n)=(1− 1m)1nlog |B⌊(1−2β)n⌋−2g(Y )|≥(1− 1m)1n(n− ⌊βn⌋ − 2g)h(Y )> h(Y )− ε/2for large enough m, where the final inequality follows from the choices of β and N . We conclude thath(S) = lim infm→∞ 1m |Bn(S)| > h(Y )− ε.Proof of Proposition 5.3.2. It is clearly enough to prove the result for u1, u2 sufficiently long, sincewe can then pass to subwords of u1, u2. By Lemma 5.4.2, let β ∈ (0, 1), m sufficiently large, andθ ∈ Bβm(Y ) \ B(W ) be such that the subshift S ⊂ Y defined by requiring at least one appearance ofθ in any block of length m has h(S) > 0. Let α ∈ (0, 1) be arbitrary, and let n > (m+ k)/(1− α) belarge enough that, by Lemma 5.4.1, there exists µ ∈ Bn(S) such that µ has no self-overlap by morethan αn, in particular by more than n− (m+ k).Let u1 ∈ Bk1(S), u2 ∈ Bk2(S) with k1, k2 ≥ m and let v1, v2 ∈ Bk(Y ). Then µ cannot appear inu1v2µv2u2 except at the position explicitly indicated. Indeed, µ cannot appear at a position shiftedby at most m+ k—otherwise, µ would overlap itself by too much—and it cannot appear at a positionshifted by more than m + k, as it would then overlap with u1 or u2 in a block of length at least m,contradicting the fact that µ ∈ B(S), and thus has θ as a subword.5.4.2 Entropy and periodic pointsWe first show that at least a positive fraction of periodic points in Y of sufficient least period have apreimage of equal least period, and in particular that their growth is exponential with rate h(Y ).Proposition 5.4.3. Let X be a mixing SFT, Y a mixing sofic shift, and π : X → Y a factor code.Then limn→∞ 1n log rn(π) = h(Y ).Proof. Let g be the mixing gap of X. By Lemma 5.4.1, let b > 0 and N > 3g be such that, forall n ≥ N , the number of blocks in Y of length n − g with no self-overlap by more than n/3 isat least c exp(nh(Y )), where we may take c = 12 exp(−gh(X)). For each block v ∈ Bn−g(Y ), thereexists a periodic point x ∈ X with π(x)[0,n−g) = v such that per(x) divides n. Thus π(x) is alsoperiodic with least period dividing n. Moreover, if v has no self-overlap by more than n/3, then infact per(π(x)) = n. Therefore rn(π) ≥ c exp(nh(Y )), so lim infn→∞ 1n log rn(π) ≥ h(Y ), matchinglim supn→∞1n log rn(π) ≤ limn→∞ 1n log qn(Y ) = h(Y ).We now assemble the quantitative results proven so far.Proposition 5.4.4. Let X be a mixing SFT, Y a mixing sofic shift, and π : X → Y a factor code. Letε > 0 and N0 ≥ 1. Then there exist N1 ≥ N0 and proper subshifts W ⊊ Y , V = π−1(W ) ⊂ X, suchthat: h(W ) > h(Y )− ε; for n ≤ N1, rn(π|V ) = rn(π); and for n ≥ N1, rn(π|V ) > exp(n(h(Y )− ε)).Proof. By Lemma 5.2.1 and Lemma 5.3.10, let V1 ⊂ X be a mixing SFT such that h(Y ) − ε/2 <h(π(V1)) < h(Y ). Let W1 = π(V1). By Proposition 5.4.3, let N1 ≥ N0 be such that for any n ≥ N1,we have 1n log rn(π|V1) > h(W1) − ε/2 > h(Y ) − ε. Let W = W1 ∪⋃N1n=1Rn(π) and V = π−1(W ).Then rn(π|V ) = rn(π) for all n ≤ N1.To see that W ̸= Y , observe that the only n-blocks in W that may not be in W1 are those inthe low-order periodic points that have been adjoined, which are bounded in number by a constant.61That is, |Bn(W )| ≤ |Bn(W1)| + C for all n ≥ N1, where we can take C =∑N1k=1 k|Rk(π)|. Thush(W ) = h(W1) < h(Y ).Proposition 5.4.4 is the final input to the proof of Proposition 5.3.7, and thus of Theorem 5.1.1.Proof of Proposition 5.3.7. Let ε = h(Y )− h(Z). Let N0 ≥ 1 be large enough that for all n ≥ N0,1nlogmax{qn(Z), |Bn(Z)|} < h(Z) + ε4By Proposition 5.4.4, let W ⊂ Y , V = π−1(W ) ⊂ X, and N1 ≥ N0 be such that h(W ) > h(Y ) − ε4 ,rn(π|V ) = rn(π) for all n ≤ N1, and 1n log rn(π|V ) > h(Y ) − ε4 for all n ≥ N1. Note that h(W ) >h(Z) + ε2 and that qn(Z) ≤ rn(π|V ) for all n ≥ 1.Let g be the mixing gap of X. By Proposition 5.3.2, let µ ∈ B(Y ) \ B(W ) be a (Y,W, g) stamp.Let ℓ = |µ| + 2g. Then since h(Z) < h(W ), there exists N sufficiently large so that for all n ≥ N , inparticular for N + ℓ ≤ n ≤ 2N + ℓ− 1, we have |Bn(Z)| < |Bn−ℓ(W )|.5.5 Proofs of Lemma 5.2.6 and Corollary 5.1.3We first use Proposition 5.4.3, along with facts about Markov approximations in Section 5.2.2, to proveLemma 5.2.6, which reduces Theorem 5.1.1 to the case where Z is a 1-step SFT.Proof of Lemma 5.2.6. We use the properties of Markov approximations mentioned in Section 5.2.Let ε = h(Y ) − h(Z). Let m0 be such that h(Zm0) < h(Z) + ε/3, where Zm0 is the m0th Markovapproximation to Z, and such that, by Proposition 5.4.3, for all n ≥ m0, 1n log rn(π) > h(Y ) − ε/3.Let m1 ≥ m0 be such that 1n log qn(Zm0) < h(Zm0) + ε/3 for all n ≥ m1. Let m2 ≥ m1 be such thatfor all periodic points z ∈ P (Zm1) \Z (under the natural embedding Z ↪→ Zm1) with per(z) ≤ m1, wehave z[0,m2) /∈ Bm2(Z). Then Zm2 satisfies qn(Zm2) = qn(Z) ≤ rn(π) for all n ≤ m1. Moreover, sinceZm2 ⊂ Zm0 , 1n log qn(Zm2) ≤ 1n log qn(Zm0) for all n; in particular,1nlog qn(Zm2) < h(Zm0) + ε/3< h(Z) + 2ε/3< h(Y )− ε/3<1nlog rn(π)for all n ≥ m1. Taking Z ′ = Z [m2]m2 to be the m2th higher block shift, the lemma is proved.To prove Corollary 5.1.3, in the mixing sofic case, we use Lemma 5.2.2 to handle low-order periodicpoint obstructions, with periodic points of sufficiently high order controlled by Proposition 5.4.3. Tohandle the arbitrary case, we first give an improved Markov approximation (Lemma 5.5.2), embeddingan arbitrary subshift into a mixing SFT with only slightly greater entropy. The construction usesLemma 5.3.8; in Lemma 5.5.1 we estimate the entropy of the mixing SFT constructed in Lemma 5.3.8.Lemma 5.5.1. Let X be a mixing SFT with gap g and let V0 ⊂ X be an SFT. Let k ≥ g and let µ ∈B(X) \ B(V0) be an (X,V0, k) stamp. For any ε > 0, there exists N ≥ |µ| such that h(V1) < h(V0) + ε,where V1 (depending on N) is as in Lemma 5.3.8.Proof. Let N0 ≥ 1 be such that for all n ≥ N0 we have 1n log |Bn(V0)| + ε/4. Let N > 2N0 be suchthat1Nmax{logN, log |Bk(X)|2, log |BN0(V0)|} <ε462We will show that 1N log |BN (V1)| < h(V0) + ε. Consider a block of length N in V1. Such a blockcan contain at most one full or partial block of the form γ+µγ− where γ± ∈ Bk(X). The µ, if present,can begin at any of the N positions. The rest of the block of length N , outside the block γ+µγ−,consists of one or two blocks from V0, with length totalling at most N . We thus have|BN (V1)| ≤ N |Bk(X)|2 max0≤ℓ≤N/2|Bℓ(V0)||BN−ℓ(V0)|If 0 ≤ ℓ ≤ N0, then |Bℓ(V0)||BN−ℓ(V0)| ≤ |BN0(V0)||BN (V0)|, so1Nlog (|Bℓ(V0)||BN−ℓ(V0)|) ≤ 1Nlog |BN0(V0)|+1Nlog |BN (V0)|< h(V0) +ε2If N0 ≤ ℓ ≤ N/2, then1Nlog (|Bℓ(V0)||BN−ℓ(V0)|) = ℓN1ℓlog |Bℓ(V0)|+ N − ℓN1N − ℓ log |BN−ℓ(V0)|<ℓN(h(V0) +ε4)+N − ℓN(h(V0) +ε4)= h(V0) +ε4Therefore1Nlog |BN (V1)| < 1NlogN +1Nlog |Bk(X)|2 + h(V0) + ε2< h(V0) + εby the above choice of N .We also use the following standard lemma improving the construction of the Markov approximation.For completeness, we include a proof using Lemma 5.3.8.Lemma 5.5.2. Let Z be a subshift and let ε > 0. Then there exists a mixing SFT V containing Zwith h(V ) < h(Z) + ε.Proof. Let m be large enough that h(Zm) < h(Z) + ε/2, where Zm is the mth Markov approximationto Z. Let X be the full shift on the alphabet of Z. Certainly Zm ⊆ X. If Zm = X, then we cantake V = X. If Zm ̸= X, then by Proposition 5.3.2, let µ be an (X,Zm, k) stamp for some k ≥ 0.Let V0 = Zm and V = V1 as in Lemma 5.3.8 where N is large enough that, by Lemma 5.5.1, we haveh(V ) < ε/2. Thus V is indeed a mixing SFT containing Z with h(V ) < h(Z) + ε.Proof of Corollary 5.1.3. We first consider the case in which Z is mixing sofic. Let Z˜ be a mixing SFTand χ0 : Z˜ → Z an almost invertible factor code. If already qn(Z˜) ≤ rn(π) for all n ≥ 1, then we cantake Z ′ = Z˜ and apply Theorem 5.1.1 immediately to construct the claimed embedding ψ : Z ′ → X.However, if qn(Z˜) > rn(π) for some n, so that X,Y, π, Z˜ violate the hypotheses of Theorem 5.1.1, thenwe need to construct a further extension of Z˜ which satisfies the hypotheses of Theorem 5.1.1. Theconstruction, consisting a tower of extensions via Lemma 5.2.2, is as follows.By Proposition 5.4.3, since h(Z˜) = h(Z) < h(Y ), there are at most finitely many n such thatqn(Z˜) > rn(π). Let N denote the greatest such n. Let C =∑Nk=1max{0, qk(Z˜) − rk(π)}. Thatis, C is the number of periodic points by which X,Y, π, Z˜ violate the hypotheses of Theorem 5.1.1.For 1 ≤ k ≤ N and 1 ≤ ℓ ≤ k−1max{0, qk(Z˜) − rk(π)}, let zk,ℓ be periodic points with pairwisedisjoint orbits, such that per(zk,ℓ) = k. For a given k, the union of the orbits of the points zk,ℓ hascardinality max{0, qk(Z˜)− rk(π)}. Let C ′ =∑Nk=1 k−1max{0, qk(Z˜)− rk(π)} (counting orbits, ratherthan points), and let {z(j)}C′j=1 = {zk,ℓ}k,ℓ be an enumeration of the points zk,ℓ.63Again by Proposition 5.4.3, let M > N be large enough that for all n ≥M , we have qn(Z˜)+Cn ≤rn(π). We now repeatedly apply Lemma 5.2.2. Let Z(0) = Z˜. For 1 ≤ j ≤ C ′, let Z(j) be a mixingSFT and χ(j) : Z(j) → Z(j−1) an almost invertible factor code such that the preimage of the orbit of zjunder χ(j) is a single orbit of length Mper(zj), and such that every periodic point in Z(j−1) not in theorbit of zj has a unique preimage under χ(j). Let η(1) = χ(1) and η(j+1) = η(j) ◦χ(j+1). Let Z ′ = Z(C′)and η = η(C′) : Z ′ → Z˜. Certainly η is almost invertible, so h(Z ′) = h(Z˜) < h(Y ). We claim thatqn(Z′) ≤ rn(π) for all n ≥ 1. Indeed, for each j, if per(zj) = k, then we have qk(Z(j)) = qk(Z(j−1))−k,qMk(Z(j)) = qMk(Z(j−1)) +Mk, and qn(Z(j)) = qn(Z(j−1)) for all n /∈ {k,Mk}. Therefore qk(Z ′) =rk(π), andqMk(Z′) = qMk(Z˜) +M max{0, qk(Z˜)− rk(π)}≤ qMk(Z˜) + CM≤ rMk(π)where the last inequality follows from the choice of M . Therefore X,Y, π, Z ′ satisfy the hypothesesof Theorem 5.1.1, so there exists a sliding block code ψ : Z ′ → X such that π ◦ ψ is injective. Thisconcludes the proof in the case that Z is mixing sofic.We now handle the general case, where Z is an arbitrary subshift with h(Z) < h(Y ). ByLemma 5.5.2, let V be a mixing SFT containing Z with h(V ) < h(Y ). By the mixing sofic case, letV ′ be a mixing SFT such that X,Y, π, V ′ satisfy the hypotheses of Theorem 5.1.1, and let χ : V ′ → Vbe an almost invertible factor code. Let Z ′ = χ−1(Z). Then χ|Z′ is still finite-to-one, which concludesthe proof.64Bibliography[1] R.L. Adler. “A note on the entropy of skew product transformations”. In: Proc. Am. Math. Soc.14.4 (1963).[2] R.L. Adler, L.W. Goodwyn, and B. Weiss. “Equivalence of topological Markov shifts”. In: Isr.J. Math. 27.1 (1977), pp. 49–63.[3] R.L. Adler and B. Weiss. “Entropy, a complete metric invariant for automorphisms of the torus”.In: Proc. Nat. Acad. Sci. 57.6 (1967), pp. 1573–1576.[4] D. Ananichev, V. Gusev, and M. Volkov. “Slowly synchronizing automata and digraphs”. In:MFCS 2010. Ed. by Petr Hlineny´ and Anton´ın Kucera. Vol. 6281. Lect. Notes Comput. Sci.Springer-Verlag Berlin Heidelberg, 2010, pp. 55–65.[5] J. Arau´jo, P. Cameron, and B. Steinberg. “Between primitive and 2-transitive: synchronizationand its friends”. In: EMS Surv. Math. Sci. 40.2 (2017), pp. 101–184.[6] J. Ashley, B. Marcus, and S. Tuncel. “The classification of one-sided Markov chains”. In: Ergod.Th. Dynam. Syst. 17.2 (1997), pp. 269–295.[7] L. Babai. “Groups, graphs, algorithms: the graph isomorphism problem”. In: ICM 2018. Ed. byB. Sirakov, P. Ney de Souza, and M. Viana. Vol. 3. World Scientific, 2018, pp. 3303–3320.[8] V. Baladi. “Gibbs states and equilibrium states for finitely presented dynamical systems”. In: J.Stat. Phys. 62.1/2 (1991), pp. 239–256.[9] S. Barbieri et al. “Equivalence of relative Gibbs and relative equilibrium measures for actions ofcountable amenable groups”. In: Nonlinearity 33.5 (2020), pp. 2409–2454.[10] M.-P. Be´al and D. Perrin. “A quadratic algorithm for road coloring”. In: Discrete Appl. Math.169 (2014), pp. 15–29.[11] S. Berghout, S. Ferna´ndez, and E. Verbitskiy. “On the relation between Gibbs and g-measures”.In: Ergod. Th. Dynam. Syst. 39.12 (2018), pp. 3224–3249.[12] M.V. Berlinkov. “On the probability of being synchronizable”. In: CALDAM 2016. Ed. by S.Govindarajan and A. Maheshwari. Vol. 9602. Lect. Notes Comput. Sci. Springer InternationalPublishing Switzerland, 2016, pp. 73–84.[13] M.V. Berlinkov. “On two algorithmic problems about synchronizing automata”. In: DLT 2014.Ed. by A.M. Shur and M.V. Volkov. Vol. 8633. LNCS. 2014, pp. 61–67.[14] J. Berstel, D. Perrin, and C. Reutenauer. Codes and Automata. Vol. 129. Encycl. Math. Appl.Cambridge University Press, 2009.[15] L. Borsato and S. MacDonald. “Conformal measures and the Dobrushin-Lanford-Ruelle equa-tions”. In: Proc. Amer. Math. Soc. 149.10 (2021), pp. 4355–4369.[16] Lu´ısa Borsato and Sophie MacDonald. A Dobrushin-Lanford-Ruelle theorem for irreducible soficshifts. Preprint, arXiv:2007.05862. 2020.65[17] Lu´ısa Borsato and Sophie MacDonald. Conformal measures and the Dobrushin-Lanford-Ruelleequations. Preprint, arXiv:2003.05532. 2020.[18] M. Boyle. “Lower entropy factors of sofic systems”. In: Ergod. Th. Dynam. Syst. 4 (1984), pp. 541–557.[19] M. Boyle and S. Tuncel. “Regular isomorphism of Markov chains is almost topological”. In:Ergod. Th. Dynam. Syst. 10.1 (1990), pp. 89–100.[20] E. Breuillard and E. Le Donne. “On the rate of convergence to the asymptotic cone for nilpotentgroups and subFinsler geometry”. In: Proc. Natl. Acad. Sci. USA 110.48 (2013), pp. 19220–19226.[21] G. Budzban and P. Feinsilver. “The generalized road coloring problem and periodic digraphs”.In: Appl. Algebra Engrg. Comm. Comput. 22.1 (2011), pp. 21–35.[22] D. Capocaccia. “A definition of Gibbs state for a compact set with Zν action”. In: Comm. Math.Phys. 48 (1976), pp. 85–88.[23] T. Ceccherini-Silberstein and M. Coornaert. “On the density of periodic configurations in stronglyirreducible subshifts”. In: Nonlinearity 25 (2012), pp. 2119–2131.[24] L. Cioletti, A.O. Lopes, and M. Stadlbauer. “Ruelle operator for continuous potentials and DLR-Gibbs measures”. In: Discrete Contin. Dyn. Syst. 40.8 (2020), p. 4625.[25] D.G. Corneil and C.C. Gotlieb. “An efficient algorithm for graph isomorphism”. In: J. Assoc.Comput. Mach. 17.1 (1970), pp. 51–64.[26] D.A. Dastjerdi and S. Jangjoo. “Dynamics and topology of S-gap shifts”. In: Topology Appl. 159(2012), pp. 26554–2661.[27] M. Denker and M. Urban´ski. “On the existence of conformal measures”. In: Trans. Amer. Math.Soc. 328.2 (1991).[28] R.L. Dobrushin. “Gibbsian random fields for lattice systems with pairwise interactions”. In:Funct. Anal. Appl. 2.4 (1969), pp. 292–301.[29] D. Eppstein. “Reset sequences for monotonic automata”. In: SIAM J. Comput. 19.3 (1990),pp. 500–510.[30] J. Feldman and C.C. Moore. “Ergodic equivalence relations, cohomology, and von Neumannalgebras. I”. In: Trans. Amer. Math. Soc. 234.2 (1977), pp. 289–324.[31] H. Furstenberg. Recurrence in ergodic theory and combinatorial number theory. M.B. PorterLectures. Princeton University Press, 1981.[32] M. Gromov. “Groups of polynomial growth and expanding maps (with an appendix by JacquesTits)”. In: Publications Mathe´matiques de l’IHE´S 53 (1981), pp. 53–78.[33] G. Han, B. Marcus, and C. Wu. Markov capacity for codes with an unambiguous symbol. arXivpreprint. 2022. url: https://arxiv.org/abs/2210.12251.[34] P. de la Harpe. Topics in geometric group theory. Chicago Lectures in Mathematics. Chicago,2000.[35] R.V.L. Hartley. “Transmission of information”. In: Bell Syst. Tech. J. 7.3 (1928), pp. 535–563.[36] N.T.A. Haydn and D. Ruelle. “Equivalence of Gibbs and equilibrium states for homeomorphismssatisfying expansiveness and specification”. In: Comm. Math. Phys. 148 (1992), pp. 155–167.[37] K. Culik II, J. Karhuma¨ki, and J. Kari. “A note on synchronized automata and road coloringproblem”. In: DLT 2001. Ed. by W. Kuich, G. Rozenberg, and A. Salomaa. Vol. 2295. Lect.Notes Comput. Sci. Springer-Verlag Berlin Heidelberg, 2002, pp. 175–185.[38] O.E. Lanford III and D. Ruelle. “Observables at infinity and states with short range correlationsin statistical mechanics”. In: Comm. Math. Phys. 13.3 (1969), pp. 194–215.66[39] J. Kari. “Synchronizing finite automata on Eulerian digraphs”. In: Theor. Comput. Sci. 295(2003), pp. 223–232.[40] A.S. Kechris. Classical descriptive set theory. Springer, 1995.[41] A.S. Kechris. The theory of countable Borel equivalence relations. Preprint. http://www.math.caltech.edu/~kechris/. 2019.[42] G. Keller. Equilibrium states in ergodic theory. London Mathematical Society Student Texts 42.Cambridge University Press, 1998.[43] J.C. Kieffer. “Zero-error stationary coding over stationary channels”. In: Prob. Th. Rel. Fields56 (1981), pp. 113–126.[44] B. Kimura. “Gibbs measures on subshifts”. MA thesis. University of Sa˜o Paulo, 2015.[45] B. Kitchens and S. Tuncel. Finitary measures for subshifts of finite type and sofic systems. Vol. 58.Mem. Amer. Math. Soc. 338. 1985.[46] A.N. Kolmogorov. “Entropy per unit time as a metric invariant of automorphisms”. In: DokladyAkad. Nauk SSSR 124 (1959). (Russian), pp. 754–755.[47] A.N. Kolmogorov. “On certain asymptotic characteristics of completely bounded metric spaces”.In: Doklady Akad. Nauk SSSR 108 (1956). (Russian), pp. 385–388.[48] W. Krieger. “On the subsystems of topological Markov chains”. In: Ergod. Th. Dynam. Syst. 2.2(1982), pp. 195–203.[49] D. Lind and B. Marcus. An introduction to symbolic dynamics and coding. Cambridge UniversityPress, 1995.[50] Sophie MacDonald. Encoding subshifts through sliding block codes. Preprint, arXiv:2210.08150.2022.[51] Sophie MacDonald. The road problem and homomorphisms of directed graphs. Preprint, arXiv:2201.12942.2022.[52] B. Marcus. “Sofic systems and encoding data”. In: IEEE Trans. Info. Th. IT-31.3 (1985), pp. 366–377.[53] B. Marcus and R. Pavlov. “Approximating entropy for a class of Z2 Markov random fields andpressure for a class of functions on Z2 shifts of finite type”. In: Ergod. Th. Dynam. Syst. 33.1(2013), pp. 186–220.[54] B. Marcus, K. Petersen, and S. Williams. “Transmission rates and factors of Markov chains”.In: Conference in modern analysis and probability: Yale University, New Haven CT, June 8–11,1982. Ed. by R. Beals et al. Vol. 26. Contemp. Math. Amer. Math. Soc., 1984, pp. 279–293.[55] R. Meester and J.E. Steif. “Higher-dimensional subshifts of finite type, factor maps and measuresof maximal entropy”. In: Pacific J. Math. 200.2 (2001), pp. 497–510.[56] T. Meyerovitch. “Gibbs and equilibrium measures for some families of subshifts”. In: Ergod. Th.Dynam. Syst. 33.3 (2013), pp. 934–953.[57] G.L. Miller. “Graph isomorphism, general remarks”. In: J. Comput. Syst. Sci. 18 (1979), pp. 128–142.[58] S.R. Muir. “A new characterization of Gibbs measures on NZd”. In: Nonlinearity 24 (2011),pp. 2933–2952.[59] S.R. Muir. “Gibbs/equilibrium measures for functions of multidimensional shifts with countablealphabets”. PhD thesis. University of North Texas, 2011.[60] J. von Neumann. “Zur Operatorenmethode in der klassiche Mechanik”. In: Ann. of Math. 33.3(1932). German, pp. 587–642.[61] G.L. O’Brien. “The road-colouring problem”. In: Isr. J. Math. 39.1–2 (1981), pp. 145–154.67[62] S.J. Patterson. “The limit set of a Fuchsian group”. In: Acta Math. 136 (1976), pp. 241–273.[63] K. Petersen and K. Schmidt. “Symmetric Gibbs measures”. In: Trans. Amer. Math. Soc. 349.7(1997), pp. 2775–2811.[64] M. Pollicott and T.M.W. Kempton. “Factors of Gibbs measures for full shifts”. In: Entropy ofhidden Markov processes and connections to dynamical systems. Ed. by B. Marcus, K. Petersen,and T. Weissman. Cambridge University Press, 2011. Chap. 8, pp. 246–257.[65] E. Riehl. Category Theory in Context. Aurora. Dover, 2017.[66] D. Ruelle. Thermodynamic formalism: the mathematical structures of equilibrium statistical me-chanics. 2nd. Cambridge, 2004.[67] V. Salo. Cohomology for extension problems in symbolic/topological dynamics? MathOverflow.url: https://mathoverflow.net/q/424145.[68] O.M. Sarig. “Lecture notes on thermodynamic formalism for countable Markov shifts”. Unpub-lished lecture notes available from the author’s webpage. 2009.[69] C. Shannon. “A mathematical theory of communication”. In: Bell Syst. Tech. J. 27 (1948),pp. 379–423, 623–656.[70] B. Simon. Convexity: an analytic viewpoint. Vol. 187. Cambridge Tracts in Mathematics. Cam-bridge University Press, 2011.[71] Ya. Sinai. “On the concept of entropy for a dynamic system. (Russian)”. In: Dolk. Akad. NaukSSSR 124 (1959), pp. 768–771.[72] M. Stoll. “On the asymptotics of 2-step nilpotent groups”. In: J. London. Math. Soc. 58.1 (1998),pp. 38–48.[73] K. Thomsen. “On the structure of a sofic shift space”. In: Trans. Amer. Math. Soc. 356.9 (2004),pp. 3557–3619.[74] A.N. Trahtman. “The road coloring problem”. In: Isr. J. Math. 172.1 (2009), pp. 51–60.[75] V. Vorel. “Subset synchronization and careful synchronization of binary finite automata”. In:Intern. J. Found. Comput. Sci. 27.5 (2016), pp. 557–577.[76] P. Walters. An introduction to ergodic theory. Springer, 1982.[77] H.W. Wielandt. “Unzerlegbare, nicht negative Matrizen”. In: Math. Z. 52 (1950). (German),pp. 642–648.[78] J. Yoo. “Decomposition of infinite-to-one factor codes and uniqueness of relative equilibriumstates.” In: J. Mod. Dyn. 13 (2018), pp. 271–284.68
Thesis/Dissertation
eng
Mathematics
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Marcus, Brian, 1949-
Meyerovitch, Tom
Gibbs measures and factor codes in symbolic dynamics
Text