Math 2.0

Dynamical systems and ergodic theory Symbolic dynamics Theorem

Curtis–Hedlund–Lyndon theorem

Builds on Shift spaceContinuous functionProduct topology

Statement

Let AA be a finite set and let d≥1d \ge 1. Give AℤdA^{\Z^d} the product topology of the discrete topologies. For v∈ℤdv \in \Z^d let σv ⁣:Aℤd→Aℤd\sigma_v \colon A^{\Z^d} \to A^{\Z^d} be the shift σv(x)u=xu+v\sigma_v(x)_u = x_{u + v}. Let F ⁣:Aℤd→AℤdF \colon A^{\Z^d} \to A^{\Z^d} be a map. Then the following are equivalent:

  1. FF is continuous and F∘σv=σv∘FF \circ \sigma_v = \sigma_v \circ F for all v∈ℤdv \in \Z^d.
  2. There are a finite set N⊆ℤdN \subseteq \Z^d and a map f ⁣:AN→Af \colon A^N \to A such that F(x)u=f((xu+n)n∈N)F(x)_u = f\big((x_{u + n})_{n \in N}\big) for all xx and all u∈ℤdu \in \Z^d.

Remarks

Condition 2 says that FF is a cellular automaton with neighbourhood NN and local rule ff. For 2 implies 1, the value F(x)uF(x)_u depends only on finitely many coordinates of xx, which gives continuity. The same rule is used at every site, which gives commutation with shifts. For 1 implies 2, the space AℤdA^{\Z^d} is compact, so FF is uniformly continuous. Hence F(x)0F(x)_0 is determined by the coordinates xnx_n with nn in some finite set NN, and this defines ff. Commutation with the shifts then gives the formula at every site uu. Compactness is essential: over an infinite alphabet there are continuous shift-commuting maps that are not given by a finite rule. The same statement holds for maps between shift spaces, where condition 2 says that FF is a sliding block code.

Going deeper

For a student

The theorem lets one treat a cellular automaton as an endomorphism of the dynamical system (Aℤd,σ)(A^{\Z^d}, \sigma). It shows, for instance, that the inverse of a bijective cellular automaton is again a cellular automaton. A continuous bijection of a compact space onto a Hausdorff space has a continuous inverse, and that inverse commutes with the shifts. In one dimension the theorem identifies the conjugacies between shift spaces with invertible sliding block codes. It is a basic tool in the classification of subshifts of finite type.

Reading path

To understand this page from the ground up, read these 26 pages in order. The foundations come first.

Show the path as a graph
Element, definition, no evidence levelElementdefinitionLimit point of a set, definition, no evidence levelLimit point of a setdefinitionProposition, concept, no evidence levelPropositionconceptShift space, concept, no evidence levelShift spaceconceptSet, definition, no evidence levelSetdefinitionLimit of a function, definition, no evidence levelLimit of a functiondefinitionConjunction, definition, no evidence levelConjunctiondefinitionDisjunction, definition, no evidence levelDisjunctiondefinitionImplication, definition, no evidence levelImplicationdefinitionPredicate, definition, no evidence levelPredicatedefinitionEmpty set, object, no evidence levelEmpty setobjectFamily of sets, definition, no evidence levelFamily of setsdefinitionOrdered pair, definition, no evidence levelOrdered pairdefinitionIntersection, definition, no evidence levelIntersectiondefinitionContinuity at a point, definition, no evidence levelContinuity at a pointdefinitionUnion, definition, no evidence levelUniondefinitionExistential quantifier, definition, no evidence levelExistential quantifierdefinitionUniversal quantifier, definition, no evidence levelUniversal quantifierdefinitionCartesian product, definition, no evidence levelCartesian productdefinitionSubset, definition, no evidence levelSubsetdefinitionContinuous function, definition, no evidence levelContinuous functiondefinitionUnion of a family of sets, definition, no evidence levelUnion of a family of …definitionTopological space, definition, no evidence levelTopological spacedefinitionBasis of a topology, definition, no evidence levelBasis of a topologydefinitionProduct topology, definition, no evidence levelProduct topologydefinitionCurtis–Hedlund–Lyndon theorem, statement, no evidence levelCurtis–Hedlund–Lyndon…statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Element definition
  2. Limit point of a set definition
  3. Proposition concept
  4. Shift space concept
  5. Set definition
  6. Limit of a function definition
  7. Conjunction definition
  8. Disjunction definition
  9. Implication definition
  10. Predicate definition
  11. Empty set object
  12. Family of sets definition
  13. Ordered pair definition
  14. Intersection definition
  15. Continuity at a point definition
  16. Union definition
  17. Existential quantifier definition
  18. Universal quantifier definition
  19. Cartesian product definition
  20. Subset definition
  21. Continuous function definition
  22. Union of a family of sets definition
  23. Topological space definition
  24. Basis of a topology definition
  25. Product topology definition
  26. Curtis–Hedlund–Lyndon theorem statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Curtis%E2%80%93Hedlund%E2%80%93Lyndon_theorem
About this page
TagN35QM9G83G
URIm2://N35QM9G83G
Kindstatement, theorem
WritingW0 stub
MSC37B10, 37B15
StatusThis copy of the site has no build data. Run m2 status N35QM9G83G.
AboutCellular automaton, Shift space
UsesShift space, Continuous function, Product topology
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.