new books and old articles (18)
Our perusal of "An Introduction to Symbolic Dynamics and Coding" by Douglas Lind and Brian Marcus, published by Cambridge University Press, is gradually advancing, eight of the thirteen chapters having been scrutinized. Although the book is promoted as a textbook dedicated to symbolic dynamics, especially coding theory, such characterizations have to be taken with a grain of salt.
As an introduction, with possible application as a textbook, it is something which has been lacking for the longest time - a single, coherent account of a whole generation of research on these topics, taking up roughly where G. A. Hedlund's often cited paper on automorphisms and endomorphisms of the shift left off. It is filled with interesting exercises - hundreds of them - thus traditionally incoporating still more material into an exposition, providing thereby sidelights and additional details which would otherwise make the text even bulkier.
It also follows the tradition of placing historical notes at the ends of the chapters; what else could we desire except maybe some biography of assorted investigators, with a flow chart showing who studied under whom, who met at what conference, and other nice, gossipy details? In other words, an even longer book?
What kind of students are going to assimilate a five hundred page book, filled with the most advanced and abstract of modern mathematics, even in a full year course? That is another matter. Especially when it turns out that still more time is going to be required for even the experts to assimilate and organize all the fascinating ideas which are just barely peeking out from beneath a horrendous maze of facts. We are reminded of that kindly elephant, she who provided gainful employment to a whole coterie of wise mem.
Close inspection shows vestiges of Hedlund's magnum opus surfacing here and there in the book; mention has already been made of the way that continuity and shift invariance influence the kinds of mappings; for the authors, they define the sliding block codes, even as they define the cellular automata for others.
Allusion to Hedlund's encounter with uniform multiplicity finds its way into the historical notes concluding Chapter 8, although the chapter's presentation is slightly weighted toward the effects of non-uniformity as seen in Moore's Garden of Eden Theorem. From the outset the orientation of coding theory is toward surjective mappings, which means that it is very much concerned with multiplicities, uniqueness and decodability, and would take anything else as an aberration.
The third leg of Hedlund's trinity (your reviewer's interpretation, not Hedlund's) quantifies exact details of the loss of limiting multiplicity, via the Welsh Indices. Hedlund's treatment relies on quite a few supplementary notions, such as periodicity, transitivity, recurrence, and still others without coming to an entirely conclusive termination. All this makes its appearance in Chapter 9, "Degrees of Codes and Almost Conjugacy." One time more, Hedlund's influence is recognized in that chapter's historical notes.
Welch's index theory is pretty definitive with respect to the left and right indices, which have already made their presence felt in the previous chapters through the concepts of closings, coverings, resolutions and all their variants. But the last has not yet been heard from the middle index, the actual surviving multiplicity, "All endomorphisms have the same multiplicity but some of them are more obtrusive than others," to paraphrase a famous quotation; Hedlund expressed it by saying that "almost all endomorphisms have the same number of counterimages."
The first section of Chapter 9, The Degree of a Finite-to-One Code, defines the degree of a code and introduces such concepts as a magic word (could that be the vertex at which a path enters or leaves the Pair Diagram on the one-way trip required by the bubble theorem?).
The second section, Almost Invertible Codes, begins with "Definition 9.2.1. A Factor Code (phi) is <almost invertible> if every doubly transitive point has exactly one preimage, i.e., d(sub)(phi)=1." Could we be asking whether or not the nuclei of extradiagonal subsets of the Pair Diagram encompass a sufficiently representative set of vertices?
The third section, Almost Conjugacy, goes on: "in this section we strengthen the relation of finite equivalence by requiring the legs to be almost invertible," and we meet the non-wandering sets.
The fourth and final section of the chapter is entitled: Typical Points According to Probability." This is an interesting way to confront those endomorphisms whose failure to be reversible is due to a few mavericks; they are simply banished to a set of measure zero.
As we know, there are essentially three views of symbolic dynamics: combinatorial, topological, and probabilistic. The first would probably answer all questions were it to be pursued diligently. In the worst case, topological or measure theoretic arguments could simply be followed out without mentioning the specialized vocabulary of these disciplines. So symbolic dynamics must have some unique features, not found in all topological spaces or in all measure algebras, which give it a unique personality. Certainly, commutation with the shift is one of them, and its derivation from finite sequences must be another.
It is nice that topological continuity enters the picture, and much is to be gained from applying knowledge of topological spaces which is already available within a body of knowledge which has been studied for many years. As this final section illustrates, measure theory encompasses a vocabulary and style of reasoning which can be equally illuminating, when used with discretion and applied with caution.
Had the authors not used restraint, the book could easily have acquired another chapter or two, because there has been no lack of interest and publlications on the probabilistic aspects of symbolic dynamics. Here is just enough of an introduction to rationalize the lukewarm endomorphisms which aren't invertible, but only weakly so.
Moving on to Chapter 10, Embeddings and Factor Codes, the complement to surjection, which is injection, comes to the fore. In both cases, concern lies with the circumstances under which all the invariants, equivalences, and partial invariants can be used to compare two shifts. As expected, emphasis is given to shifts of finite type. Also, the subject matter of the chapter splits into three parts, one of which was already presented Chapter 7. Thus the chapter is confined to strict embeddings, and strict entropy change; entropy conservation is reserved for Chapter 12.
What is left is spread out into three sections, the first of which is called "The Embedding Theorem." It asserts that a strict embedding is possible when there is a lessening of entropy and cyclage (distribution of cycles), requiring fourteen pages for its proof, and introducing a refinement of the cycle count wherein multiplicity counts. Those who actually work with zeta functions know that there are tricky distinctions amongst the ways cycles can be enumerated.
The second section, "The Masking Lemma," is short and concerns the behavior of the graphs defining shifts of finite type consequent to embedment of the shifts themselves.
The third section, "Lower Entropy Factor Codes," covers similar ground for surjections rather than injections.
The book still has three more chapters, one of which contains still more technical detail, one of which surveys the extent to which all the theory shows up in actual practice, and the conclusion which tells us of all the things which remain to be done and possible directions which the theory could take.
Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx