🔢 mathematics

Parametrized complexity of relations between multidimensional subshifts

This paper investigates the parametrized complexity of fundamental relations between multidimensional subshifts by fixing one subshift as a parameter, revealing how specific dynamical properties influence computational difficulty, identifying decidable cases for multidimensional SFTs, and uncovering connections between computable languages and minimality that challenge conjugacy invariance.

Original authors: Nicanor Carrasco-Vargas, Benjamin Hellouin de Menibus, Rémi Pallen

Published 2026-02-16

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Nicanor Carrasco-Vargas, Benjamin Hellouin de Menibus, Rémi Pallen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are an architect designing a city. In this paper, the "cities" are called subshifts. They are infinite grids (like a 2D city map or a 1D street) filled with colored tiles. The rules of the city are simple: you can't have certain patterns of tiles next to each other (like a red tile next to a blue one).

The authors are asking a very specific question: "How hard is it to compare two of these cities?"

Usually, computer scientists ask, "Is City A the same as City B?" or "Can City A fit inside City B?" The answer is often "We can't know for sure; it's impossible to decide." This is the famous "undecidability" problem in computer science.

But this paper asks a different, more nuanced question: "What if City B is a famous, fixed landmark (like the Eiffel Tower), and we only get to change City A?"

They call this Parametrized Complexity. They fix one city (the Parameter) and ask how hard it is to check the relationship with a new, input city (the Input).

Here is a breakdown of their findings using everyday analogies:

1. The Two Main Types of Cities

The paper studies two types of cities:

SFTs (Subshifts of Finite Type): These are cities with a finite rulebook. You can write down all the forbidden patterns on a single sheet of paper. (e.g., "No red next to blue").
Effective Subshifts: These are cities with a rulebook generated by a robot (Turing Machine). The robot can list forbidden patterns forever. The rulebook is infinite, but the robot follows a logical algorithm to generate it.

2. The Four Relationships They Check

They look at four ways to compare the Input City ( $X$ ) to the Fixed Parameter City ( $Y$ ):

Equality ( $X = Y$ ): Are they exactly the same?
Conjugacy ( $X \simeq Y$ ): Are they "topologically the same"? Imagine City A is a city made of Lego, and City B is the same city made of clay. If you can stretch and squish one to look exactly like the other without tearing it, they are conjugate. They have the same "shape" and "vibe," even if the tiles look different.
Inclusion ( $X \subseteq Y$ ): Is City A a subset of City B? (Can every valid pattern in A also exist in B?)
Embedding ( $X \hookrightarrow Y$ ): Can City A be "pasted" inside City B? (Is there a way to map every tile of A into B without breaking the rules?)

3. The Big Discovery: It Depends on the "Fixed" City

The most surprising finding is that the difficulty of the problem changes completely depending on the nature of the Fixed City ( $Y$ ).

The "Easy" Cases (Decidable)

Sometimes, if the Fixed City has special properties, the problem becomes easy (solvable by a computer).

The "Finite" City: If the Fixed City is tiny (only a few repeating patterns), checking if a new city fits inside it is easy. It's like checking if a specific puzzle piece fits into a small, known box.
The "Simple" City: If the Fixed City is an SFT (finite rulebook) and has a "computable language" (we can easily list all its valid patterns), checking equality or inclusion becomes manageable.

The "Hard" Cases (Undecidable)

If the Fixed City is complex, the problem becomes impossible to solve.

The "Chaotic" City: If the Fixed City contains a specific type of "almost periodic" pattern (a pattern that repeats but has a glitch in the middle), checking if a new city can embed into it becomes as hard as solving the Halting Problem (a classic unsolvable computer problem).
The "Infinite Rulebook" City: If the Fixed City is an Effective Subshift (generated by a robot), checking if a new city is exactly the same as it is often impossible.

4. The "Swamp of Undecidability"

The authors mention a "swamp" where most properties of these cities are impossible to determine. However, they found islands of safety.

The Surprise: They found that for some Fixed Cities, checking if a new city can be embedded (pasted inside) is actually easier than checking if it is included (a subset).
- Analogy: Imagine you are checking if a new guest list ( $X$ ) fits into a party ( $Y$ ).
- Inclusion: You must check if every single person on the guest list is already on the party list. (Hard if the party list is weird).
- Embedding: You just need to find one way to seat the guests so they don't break the rules. Sometimes, finding one valid seating arrangement is easier than proving everyone is already there.

5. The "Conjugacy" Mystery

The hardest relationship to check is Conjugacy (are they the same shape?).

If the Fixed City is a simple, repeating pattern, it's easy.
If the Fixed City is a "minimal" city (it has no smaller parts inside it) and follows certain mathematical rules, the problem becomes "just hard enough" to be solvable but tricky.
But if the Fixed City is a complex SFT, the problem can jump to the highest level of difficulty (Σ₀³), meaning it's incredibly hard, even for powerful computers.

6. The "One-Dimensional" Exception

The paper notes that in 1D (a single line of tiles), things are much friendlier.

Checking if two 1D cities are the same or if one fits inside the other is usually solvable.
However, checking if they are "conjugate" (same shape) in 1D is a famous open mystery that no one has solved yet. It's like a locked door that mathematicians have been trying to open for decades.

Summary

This paper is like a complexity map for comparing digital cities.

Old View: "Comparing cities is impossible."
New View: "It depends on which city you are comparing to."
- If you compare against a simple, finite city, it's easy.
- If you compare against a chaotic, infinite city, it's impossible.
- And sometimes, the way you ask the question (Inclusion vs. Embedding) changes the difficulty entirely.

The authors successfully mapped out exactly which properties of the "Fixed City" make the math easy, hard, or impossible, revealing a rich landscape of computational difficulty hidden within these grid patterns.

Technical Summary: Parametrized Complexity of Relations Between Multidimensional Subshifts

1. Problem Statement and Context

This paper investigates the parametrized complexity of fundamental relations between multidimensional subshifts (specifically Subshifts of Finite Type - SFTs, and Effective Subshifts). The relations studied include:

Equality ( $X = Y$ )
Conjugacy ( $X \simeq Y$ ): Existence of a continuous, shift-equivariant bijection.
Inclusion ( $X \subseteq Y$ and $Y \subseteq X$ )
Embedding ( $X \hookrightarrow Y$ and $Y \hookrightarrow X$ ): Existence of a continuous, shift-equivariant injection.

The Parametrized Approach:
Unlike previous work (e.g., Jeandel and Vanier) which treated these as two-input problems (determining the relation between two arbitrary subshifts), this paper fixes one subshift, $Y$ (the parameter), and treats the other, $X$ (the input), as the variable. The input $X$ ranges over the class of SFTs or Effective Subshifts.

Core Motivation:
The authors aim to understand how the dynamical and combinatorial properties of the fixed parameter $Y$ (e.g., periodicity, minimality, being of finite type, having a computable language) influence the computational complexity of deciding the relation with an arbitrary input $X$ . This approach seeks to identify "easy" cases where problems become decidable despite the general "swamp of undecidability" associated with SFT properties, and to characterize the exact complexity bounds (within the arithmetical hierarchy) for specific parameters.

2. Methodology

The authors employ a combination of computability theory and dynamical systems techniques:

Reductions: They reduce classical undecidable problems (Halt, Total, COF, Domino Problem) to the parametrized subshift problems to establish lower bounds (hardness).
Simulation: They utilize SFT constructions (e.g., Robinson SFT, Wang tiles) that simulate Turing machines to encode computational states into subshift configurations.
Arithmetical Hierarchy Analysis: They classify the complexity of these problems within classes such as $\Sigma^0_1$ , $\Pi^0_1$ , $\Sigma^0_2$ , $\Pi^0_2$ , $\Sigma^0_3$ , and $D(\Sigma^0_1)$ (the difference of two $\Sigma^0_1$ sets).
Dynamical Properties: They analyze how properties like minimality, entropy-minimality, strong periodicity, and computable language of $Y$ act as constraints that lower the complexity of the decision problem.
Lifts: They use group homomorphisms to lift 1-dimensional results to higher dimensions ( $d \ge 2$ ).

3. Key Contributions and Results

A. General Bounds and Trivial Cases

SFT Inputs: For $d \ge 2$ , problems $X=Y$ , $X \simeq Y$ , $X \subseteq Y$ , and $X \hookrightarrow Y$ are generally $\Sigma^0_1$ -complete (recursively enumerable) if $Y$ is an SFT. If $Y$ is not an SFT, these problems are often trivial (always "no").
Effective Inputs: For effective inputs, most non-trivial properties are undecidable ( $\Sigma^0_1$ -hard or $\Pi^0_1$ -hard) due to Rice-like theorems.

B. The Inclusion Problem ( $Y \subseteq X$ )

Decidability Condition: The problem $Y \subseteq X$ with SFT inputs is decidable if and only if the language of $Y$ ( $L(Y)$ ) is computable.
Complexity: The problem is enumeration-equivalent to the complement of the language of $Y$ ( $L(Y)^c$ ).
Hardness: There exist SFTs $Y$ for which this problem is $\Pi^0_2$ -complete (specifically when $Y$ is not an SFT or has non-computable language properties).

C. The Embedding Problem ( $Y \hookrightarrow X$ )

Surprising Asymmetry: Unlike inclusion, embedding can be decidable even when the language of $Y$ $Y$ is not computable.
- Example: There exists an effective subshift $Y$ where $Y \hookrightarrow X$ is decidable for SFT inputs, but $Y \subseteq X$ is undecidable.
Undecidability Conditions: If $Y$ contains a configuration that is "almost" strongly periodic (periodic outside a finite region) but not fully periodic, the problem becomes $\Sigma^0_1$ -hard.
Decidability Conditions: If $Y$ is a finite subshift, the problem is decidable.

D. The Inclusion/Embedding Problem ( $X \subseteq Y$ and $X \hookrightarrow Y$ )

When the parameter $Y$ is effective (but not necessarily an SFT):

Upper Bounds: $X \subseteq Y$ is at most $\Pi^0_2$ -complete; $X \hookrightarrow Y$ is at most $\Sigma^0_3$ -complete.
Tightness: The authors construct examples of effective subshifts $Y$ that reach these upper bounds.
Lower Bounds: If $Y$ contains only finitely many SFT subsystems, both problems drop to $\Sigma^0_1$ -complete.

E. The Equality Problem ( $X = Y$ )

Complexity Range: For effective inputs, the complexity lies between $D(\Sigma^0_1)$ and $\Pi^0_2$ .
Characterization of SFTs:
- If $Y$ is an SFT with a computable language, the problem is $D(\Sigma^0_1)$ -complete.
- If $Y$ is an SFT with a non-computable language (or not an SFT), the problem can reach $\Pi^0_2$ -complete.
Significance: In dimension $d=1$ , the complexity of the equality problem with effective inputs completely characterizes whether $Y$ is an SFT.

F. The Conjugacy Problem ( $X \simeq Y$ )

Complexity Range: For effective inputs, the complexity ranges from $D(\Sigma^0_1)$ to $\Sigma^0_3$ .
Maximal Complexity: There exist SFTs $Y$ for which $X \simeq Y$ is $\Sigma^0_3$ -complete.
Minimal Complexity: If $Y$ is minimal for a conjugacy-invariant $\Pi^0_1$ property (e.g., having a dense set of periodic points, being entropy-minimal with computable entropy), the problem drops to $D(\Sigma^0_1)$ -complete.
Key Insight: The paper demonstrates that the property of "having a computable language" is not always conjugacy-invariant. An SFT can be minimal for a $\Pi^0_1$ property (making conjugacy easy) but fail to be minimal for a conjugacy-invariant $\Pi^0_1$ property (keeping the problem hard).

4. Significance and Implications

Refining Undecidability: The paper challenges the notion of a uniform "swamp of undecidability" for SFTs. It shows that by fixing a parameter with specific dynamical properties (like finiteness or minimality), one can find non-trivial decidable problems in dimensions where most properties are undecidable.
Asymmetry of Relations: The study reveals significant asymmetries between inclusion and embedding. For instance, embedding can be decidable for parameters with non-computable languages, whereas inclusion requires computable languages.
Connection to Computability and Dynamics: The work establishes deep links between the computability of the language of a subshift and its dynamical minimality. It clarifies that while computable language often implies easier decision problems, this relationship depends heavily on whether the underlying dynamical property is conjugacy-invariant.
Dimensional Dependence: The results highlight the stark difference between 1D and $d \ge 2$ subshifts. While 1D SFTs have computable languages and decidable inclusion, higher-dimensional SFTs exhibit the full spectrum of arithmetical complexity.
Future Directions: The paper suggests that the complexity of these problems is closely tied to the "simplicity" of the parameter (e.g., factor maps). It opens the door to classifying subshifts based on the computational difficulty of their relational problems, potentially leading to a finer taxonomy of subshifts beyond just "SFT" or "Effective."

In summary, this paper provides a comprehensive map of the computational landscape of subshift relations, demonstrating that the complexity is not an intrinsic property of the problem alone but is fundamentally shaped by the dynamical nature of the fixed parameter.