On the cohomology of homshifts

Basic Information

• Paper ID: 2510.11969
• Title: On the cohomology of homshifts
• Authors: Nishant Chandgotia, Silvère Gangloff, Benjamin Hellouin de Menibus, Piotr Oprocha
• Classification: math.DS (Dynamical Systems)
• Publication Date: October 15, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.11969

Abstract

This paper investigates the cohomological properties of symbolic dynamical systems called homshifts. Homshifts are nearest-neighbor $\mathbb{Z}^d$ shifts of finite type whose adjacency rules are identical in each direction. Building on the work of Klaus Schmidt, the paper provides necessary and sufficient conditions for the cohomological triviality of homshifts. These conditions are expressed in terms of topological properties of natural simplicial complexes generated by the shift space, which can be analyzed in many natural cases. However, the authors prove that in general, the cohomological triviality of homshifts is algorithmically undecidable.

Research Background and Motivation

1. Research Problem: The core problem addressed in this paper is to characterize the cohomological triviality of homshifts (graph homomorphism shifts). Specifically, it determines when all continuous cocycles on homshifts are trivial.
2. Problem Significance:
   • Cohomology theory plays a crucial role in symbolic dynamics with deep connections to geometry, group theory, and statistical physics
   • In tiling problems, cohomological triviality can be used to decide extension problems: given a configuration defined outside a finite region, whether it can be extended inward to a global configuration of the shift
   • The algebraic structure of the Conway-Lagarias-Thurston tiling group naturally appears in the cohomology of shift spaces
3. Limitations of Existing Methods:
   • Schmidt's work primarily addresses cocycles in locally compact second-countable groups, while this paper focuses on cocycles in discrete groups
   • Cohomological properties of general shifts of finite type are typically undecidable, but homshifts as a special subclass exhibit better tractability
4. Research Motivation:
   • Homshifts have important applications in statistical physics (e.g., hard-core models, proper colorings, ice models)
   • They provide fertile ground for exploring the boundary between tractable and intractable problems in symbolic dynamics

Core Contributions

1. Main Theorem: Provides a complete characterization of cohomological triviality for mixing homshifts (Theorem 1.1): For $d > 1$ and a graph $G$ such that $X^d_G$ is topologically mixing, $X^d_G$ is cohomologically trivial if and only if the square group is isomorphic to $\mathbb{Z}/2\mathbb{Z}$ if and only if the even square group of $G$ is trivial.
2. Undecidability Result: Proves that cohomological triviality of homshifts is algorithmically undecidable (Theorem 1.2).
3. Technical Innovations:
   • Introduces the concept of the even square group, an index-2 subgroup of the square group
   • Defines square group cocycles to prove cohomological non-triviality
   • Establishes the strip-gluing property, generalizing Schmidt's specification property
4. Dimension Generalization: Extends results from the two-dimensional case to higher-dimensional homshifts.

Detailed Methodology

Task Definition

The core task of this paper is to characterize the cohomological triviality of d-dimensional homshift $X^d_G$, where:

• Input: A finite connected undirected graph $G$
• Output: Determine whether the corresponding homshift is cohomologically trivial
• Constraint: The homshift is required to be topologically mixing (i.e., $G$ is a connected non-bipartite graph)

Core Concepts and Constructions

1. Definition of Homshifts

Given a finite graph $G$, the d-dimensional homshift $X^d_G$ is defined as the space of all graph homomorphisms from $\mathbb{Z}^d$ (as a Cayley graph) to $G$.

2. Square Group and Even Square Group

• Square Group $\pi^{\square}_1(G)$: The quotient of the fundamental group $\pi_1(G)$ by the normal subgroup generated by all squares (non-backtracking loops of length 4)
• Even Square Group $E^{\square}_G$: The quotient of the subgroup of even-length loops by square relations

3. Square Group Cocycles

Define the map $c^{T,a}_G: \mathbb{Z}^d \times X^d_G \to \pi^{\square}_1(G)[a]$: $c^{T,a}_G(n,x) := (p^{\square}_G(p^a_T(x_0) \star x_p \star (p^a_T(x_n))^{-1}))^{-1}$ where $p$ is a path from 0 to $n$, and $T$ is a spanning tree of $G$.

Technical Innovations

1. Introduction of Even Square Group: By restricting to even-length loops, more precisely characterizes the algebraic structure related to cohomology.
2. Strip-Gluing Property: Generalizes Schmidt's specification property, applicable to discrete group-valued cocycles.
3. Generalization from Two to Higher Dimensions: Extends two-dimensional results to arbitrary dimensions through projection sub-dynamical systems techniques.

Experimental Setup

Theoretical Verification

This paper is primarily theoretical work, with results verified through mathematical proofs. The main "experiments" involve constructing concrete examples:

1. Concrete Graph Examples

• Kenkatabami Graph: An example with trivial square group but not satisfying the box-extension property
• Complete Graph $K_3$: Three-coloring problem, demonstrating construction of non-trivial cocycles
• Bipartite Graphs: Illustrating the relationship between even square group and square group

2. Counterexample Construction

• Proves that box-extension property is strictly stronger than cohomological triviality
• Constructs non-trivial cocycles in non-mixing cases

Proof Strategy

Forward Direction ($\Rightarrow$)

Constructs square group cocycles to prove that when the even square group is non-trivial, there exist non-trivial cocycles.

Reverse Direction ($\Leftarrow$)

1. Two-Dimensional Case: Utilizes strip-gluing property and density of Gibbs equivalence classes
2. Higher-Dimensional Case: Projection to two-dimensional subsystems

Experimental Results

Main Theoretical Results

Theorem 1.1 (Main Characterization Theorem)

For $d > 1$ and a graph $G$ such that $X^d_G$ is topologically mixing, the following are equivalent:

1. $X^d_G$ is cohomologically trivial
2. The square group $\pi^{\square}_1(G) \cong \mathbb{Z}/2\mathbb{Z}$
3. The even square group $E^{\square}_G$ is trivial

Theorem 1.2 (Undecidability)

For $d > 1$, given a graph $G$ such that $X^d_G$ is topologically mixing, it is impossible to algorithmically determine whether $X^d_G$ has non-trivial cocycles.

Technical Results

1. Characterization of Strip-Gluing Property

Lemma 5.3: If the even square group of $G$ is trivial, then $X^2_G$ has the strip-gluing property relative to checkerboard configurations.

2. Separation of Box-Extension Property

Theorem 7.4: Box-extension property implies triviality of the even square group. Corollary 7.6: The homshift corresponding to the Kenkatabami graph does not have the box-extension property but has trivial cohomology.

Dimension Generalization Results

Theorem 6.1: If $X^2_G$ has trivial cohomology and is mixing, then for $d > 2$, $X^d_G$ also has trivial cohomology.

Related Work

Historical Development

1. Conway-Lagarias-Thurston (1990): Introduced group-theoretic invariants for studying tiling problems
2. Klaus Schmidt (1995): Interpreted tiling groups as cocycles of certain $\mathbb{Z}^2$-subshifts
3. Katok-Spatzier (1994): Studied cohomological rigidity phenomena for higher-order abelian group actions

Related Concepts

1. Projective Fundamental Group (Geller-Propp, 1995): Related to the square group under the restriction to four-cycle-free non-bipartite graphs
2. Specification Property (Schmidt, 1995): The strip-gluing property in this paper is its generalization to the discrete group case

Advantages of This Work

1. Provides complete characterization of cohomological triviality for homshifts
2. Handles discrete group-valued cocycles rather than locally compact groups
3. Establishes precise correspondence between algebra (even square group) and dynamics (cohomology)

Conclusions and Discussion

Main Conclusions

1. Complete Characterization: Establishes equivalence between cohomological triviality of homshifts and triviality of the even square group
2. Algorithmic Complexity: Proves undecidability of this problem, contrasting with general shifts of finite type
3. Geometric Interpretation: Provides geometric perspective through topological analysis of natural simplicial complexes

Limitations

1. Mixing Assumption: Main results require homshifts to be mixing (i.e., the graph is connected and non-bipartite)
2. Non-Mixing Cases: Cohomological behavior is more complex for non-mixing homshifts; counterexamples are provided
3. Computational Complexity: While the square group can be computed in special cases (e.g., surfaces or four-cycle-free graphs), it remains difficult in general

Future Directions

1. Large-Scale Phenomena: Utilize properties of hyperbolic square groups to apply non-commutative ergodic theorems to study large-scale phenomena of random graph homomorphisms
2. Box-Extension Property: Characterize which graphs yield homshifts with the box-extension property
3. Strong Irreducibility: Investigate whether strong irreducibility implies cohomological triviality

In-Depth Evaluation

Strengths

1. Theoretical Completeness: Provides complete characterization of cohomological triviality for mixing homshifts, resolving a fundamental problem in the field
2. Technical Innovations:
   • Introduction of even square group concept is natural and effective
   • Generalization of strip-gluing property has technical value
   • Dimension generalization method is general-purpose
3. Deep Results: Undecidability result reveals the essential complexity of the problem
4. Application Potential: Connections to statistical physics models provide possibilities for practical applications

Weaknesses

1. Mixing Restriction: Main results are limited to the mixing case; treatment of non-mixing cases is incomplete
2. Computational Aspects: While providing theoretical characterization, actually computing the even square group remains difficult
3. Concrete Examples: Could provide more specific graph classes and corresponding cohomological property analyses

Impact

1. Theoretical Contribution: Provides new tools and perspectives for cohomology theory in symbolic dynamics
2. Interdisciplinary Value: Connects dynamical systems, algebraic topology, and statistical physics
3. Methodological Significance: Proof techniques provide insights for related problems

Applicable Scenarios

1. Theoretical Research: For researchers in symbolic dynamics and ergodic theory
2. Statistical Physics: For studying lattice models and phase transitions
3. Computational Complexity: For studying undecidability theory

References

The paper cites 33 important references, primarily including:

1. Klaus Schmidt (1995): "The cohomology of higher-dimensional shifts of finite type" - Main theoretical foundation of this paper
2. Conway & Lagarias (1990): "Tiling with polyominoes and combinatorial group theory" - Foundational work on tiling group theory
3. William Thurston (1990): "Conway's tiling groups" - Group-theoretic approach to tiling problems
4. Katok & Spatzier (1994): Cohomological rigidity for higher-order abelian group actions
5. Chandgotia & Marcus (2018): Study of mixing properties of homshifts

These references form a solid theoretical foundation for this work, reflecting the development trajectory from tiling problems to cohomology theory in symbolic dynamics.