Computability of Extender Sets in Multidimensional Subshifts

Callard, Antonin; Paviet Salomon, Léo; Vanier, Pascal

doi:10.4230/LIPIcs.STACS.2025.21

Computability of Extender Sets in Multidimensional Subshifts

Antonin Callard

Normandie Univ, UNICAEN, ENSICAEN, CNRS, GREYC, 14000, Caen, France Léo Paviet Salomon

Université de Lorraine, CNRS, Inria, LORIA, 54000, Nancy, France Pascal Vanier

Normandie Univ, UNICAEN, ENSICAEN, CNRS, GREYC, 14000, Caen, France

Abstract

Subshifts are sets of colorings of $\mathbb{Z}^{d}$ defined by families of forbidden patterns. Given a subshift and a finite pattern, its extender set is the set of admissible completions of this pattern. It has been conjectured that the behavior of extender sets, and in particular their growth called extender entropy [10], could provide a way to separate the classes of sofic and effective subshifts. We prove here that both classes have the same possible extender entropies: exactly the $\Pi_{3}$ real numbers of $[0,+\infty)$ .

Keywords and phrases:

Symbolic dynamics, subshifts, extender sets, extender entropy, computability, sofic shifts, tilings

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Discrete mathematics ; Theory of computation

\rightarrow

Models of computation

Related Version:

Extended Version: https://doi.org/10.48550/arXiv.2401.07549

Acknowledgements:

We are thankful to the referees for their many helpful remarks and suggestions.

Funding:

This research was partially funded by ANR JCJC 2019 19-CE48-0007-01.

DOI:

10.4230/LIPIcs.STACS.2025.21

Event:

42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Editors:

Olaf Beyersdorff, Michał Pilipczuk, Elaine Pimentel, and Nguyễn Kim Thắng

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

In dimension $d\in\mathbb{N}$ , subshifts are sets of colorings of $\mathbb{Z}^{d}$ where a family of patterns, i.e. colorings of finite portions of $\mathbb{Z}^{d}$ , have been forbidden. They were originally introduced to discretize continuous dynamical systems [19]. One of the main families of subshifts that has been studied is the class of subshifts of finite type (SFTs), which can be defined with a finite family of forbidden patterns. This class has independently been introduced under the formalism of Wang tiles [25] in dimension 2 in order to study fragments of second order logic.

In dimension 1, sofic subshifts [26], which are obtained as letter-to-letter projections of SFTs, are studied mainly through their defining graphs. In dimension 2 and higher, SFTs (and thus sofic subshifts) can embed arbitrary Turing machine computations; as such, the main tool in the study of subshifts becomes computability theory. This led to the introduction of a new class of subshifts, the effective subshifts, which can be defined by computably enumerable families of forbidden patterns [13].

An important question in symbolic dynamics is thus to find criteria separating sofic from effective subshifts [15, 22, 12, 3]. In dimension 1, a subshift is sofic if it can be defined by a regular language of forbidden patterns: the Myhill–Nerode theorem states that these are exactly the languages that have finitely many Nerode congruence classes. In dimension 2 and higher, no such clear characterization exists. Indeed, many effective subshifts have been proved to be sofic, such as substitutive subshifts [20], or effective subshifts on $\{\texttt{0},\texttt{1}\}$ whose densities of symbols 1 are sublinear [6]; it even turns out that sofic subshifts of dimension $d+1$ capture all the behaviors of effective shifts of dimension $d$ [13, 8, 2].

All the methods used to prove some cases of non-soficity that are known by the authors revolve around a counting argument: only a linear amount of information may cross the border of an $n\times n$ square pattern (see for example [1, Proposition 9.4.5]). The most recent argument in this vein uses resource-bounded Kolmogorov complexity [7].

One formalization of this counting argument relies on extender sets of patterns [15], which can be considered as a higher-dimensional generalization of Nerode congruence classes: the extender set of a pattern $p$ is the set of all configurations with a $p$ -shaped hole that may extend $p$ . For SFTs, the extender set of a given pattern is entirely determined by its boundary, which implies that the number of extender sets of an SFT cannot grow too quickly. For subshifts in dimension 1, [21, Lemma 3.4] proves the analog of Myhill-Nerode theorem: a subshift is sofic if and only if its number of extender sets of every size is bounded. In dimension 2 and higher, only sufficient conditions are known: for example, a subshift whose number of extender sets for patterns of size $n^{d}$ is bounded by $n$ must be sofic [21].

The study of the growth rate of the number of extender sets can be done asymptotically through the notion of the extender entropy, which is defined in a similar way to the classical notion of topological entropy [17]. Extender entropies in fact relate to the to notion of follower entropies [4], but are more robust in the sense that, despite it not being decreasing under factor map applications, the extender entropy of a subshift is still a conjugacy invariant.

In this paper, we achieve characterizations of the possible extender entropies in terms of computability, in the same vein as recent results on conjugacy invariants of subshifts [14, 18].

Theorem A.

The set of extender entropies of $\mathbb{Z}$ effective subshifts is exactly $\Pi_{3}\cap[0,+\infty)$ .

Theorem B.

The set of extender entropies of $\mathbb{Z}^{2}$ sofic subshifts is exactly $\Pi_{3}\cap[0,+\infty)$ .

These results generalize to dimension $d\geq 2$ by Claim 8 and Corollary 12. While sofic subshifts were conjectured in [15] to have extender entropy zero, this was later disproved (see for example [7]); in fact, our characterization shows that the possible values are dense in $[0,+\infty)$ . This also proves that extender entropies do not separate sofic from effective shifts.

	$\mathbb{Z}$	$\mathbb{Z}^{d},d\geq 2$
SFT	$\{0\}$ (Folklore: see Proposition 6)
Sofic	$\{0\}$ ([9, Theorem 1.1])	$\Pi_{3}$ (B)
Effective	$\Pi_{3}$ (A)
Computable ( $\mathbb{Z}$ effective, $\mathbb{Z}^{d}$ sofic)	$\Pi_{2}$ (Theorem 27)
Sofic and minimal	$\{0\}$ (Corollary 29)
Effective and minimal	$\Pi_{1}$ (Corollary 30)
Effective and $1$ -Mixing/Block-Gluing	$\Pi_{3}$ (Proposition 32)	$\Pi_{3}$ (Proposition 34)

Figure 1: Sets of possible extender entropies for various classes of subshifts.

Finally, we also study extender entropies of subshifts constrained by some dynamical assumptions, such as minimality or mixingness. What is known by the authors at this stage can be summed up by the table Figure 1.

2 Definitions

2.1 Subshifts

Let $\mathcal{A}$ denote a finite set of symbols and $d\in\mathbb{N}$ the dimension. A configuration is a coloring $x\in\mathcal{A}^{\mathbb{Z}^{d}}$ , and the color of $x$ at position $p\in\mathbb{Z}^{d}$ is denoted by $x_{p}$ . A ( $d$ -dimensional) pattern over $\mathcal{A}$ is a coloring $w\in\mathcal{A}^{P}$ for some set $P\subseteq\mathbb{Z}^{d}$ called its support¹¹1It is sometimes convenient to consider patterns up to the translation of their support. Usually, context will make it clear whether patterns are truly equal, or only up to a $\mathbb{Z}^{d}$ translation.. For any pattern $w$ over $\mathcal{A}$ of support $P$ , we say that $w$ appears in a configuration $x$ (and we denote $w\sqsubseteq x$ ) if there exists $p_{0}\in\mathbb{Z}^{d}$ such that $w_{p}=x_{p+p_{0}}$ for all $p\in P$ .

The shift functions $(\sigma^{t})_{t\in\mathbb{Z}^{d}}$ act on configurations as $(\sigma^{t}(x))_{p}=x_{p+t}$ . For $t\in\mathbb{Z}^{d}$ , a configuration $x$ is $t$ -periodic if $\sigma^{t}(x)=x$ . We sometimes consider patterns or configuration by their restriction: for $S\subseteq\mathbb{Z}^{d}$ either finite or infinite, and $x\in\mathcal{A}^{\mathbb{Z}^{d}}$ a configuration (resp. $w$ a pattern), we denote by $x|_{S}$ (resp. $w|_{S}$ ) the coloring of $\mathcal{A}^{S}$ it induces on $S$ .

Definition 1 (Subshift).

For any family of finite patterns $\mathcal{F}$ , we define

X_{\mathcal{F}}=\left\{x\in\mathcal{A}^{\mathbb{Z}^{d}}\mid\forall w\in% \mathcal{F},\,w\not\sqsubseteq x\right\}

A set $X\subseteq\mathcal{A}^{\mathbb{Z}^{d}}$ is called a subshift if it is equal to some $X_{\mathcal{F}}$ .

Given a subshift $X$ and a finite support $P\subseteq\mathbb{Z}^{d}$ , we define $\mathcal{L}_{P}(X)$ as the set of patterns $w$ of support $P$ that appear in the configurations of $X$ . Such patterns are said to be globally admissible in $X$ . We define the language of $X$ as $\smash{\mathcal{L}(X)=\bigcup\limits_{P\subseteq\mathbb{Z}^{d}\text{ finite}}% \mathcal{L}_{P}(X)}$ . Slightly abusing notations, we denote $\mathcal{L}_{n}(X)=\mathcal{L}_{\llbracket 0,n-1\rrbracket^{d}}(X)$ for $n\in\mathbb{N}$ .

For $X\subseteq\mathcal{A}^{\mathbb{Z}^{d}}$ and $Y\subseteq\mathcal{B}^{\mathbb{Z}^{d}}$ two subshifts, $\varphi\colon X\to Y$ is a factor map if there exists some $N\subseteq\mathbb{Z}^{d}$ and $f\colon\mathcal{A}^{N}\to\mathcal{B}$ such that $\varphi(x)_{p}=f(x|_{p+N})$ : then $Y$ is a factor of $X$ . $X$ and $Y$ are conjugate if there exists a bijective factor map $\varphi\colon X\to Y$ (called a conjugacy). Any object associated with subshifts that is preserved by conjugacy is a conjugacy invariant.

Subshifts can be classified as follows: a subshift is of finite type (SFT) if it is equal to $X_{\mathcal{F}}$ for some finite family $\mathcal{F}$ of forbidden patterns; a subshift $X$ is effective if it is equal to $X_{\mathcal{F}}$ for some computably enumerable family $\mathcal{F}$ of forbidden patterns; and a subshift is sofic if it is a factor of some SFT, called its SFT cover. SFTs are sofic by definition, and sofic subshifts are effective.

Reciprocally, for a $\mathbb{Z}^{d}$ subshift $X\subseteq\mathcal{A}^{\mathbb{Z}^{d}}$ , define the following lifts:

$\blacksquare$

the periodic lift ${X^{\uparrow}}=\{{x^{\uparrow}}\in\mathcal{A}^{\mathbb{Z}^{d+1}}\mid x\in X\}$ , where $({x^{\uparrow}})|_{\mathbb{Z}^{d}\times\{i\}}=x$ for all $i\in\mathbb{Z}$ ;
$\blacksquare$

the free lift ${X^{\Uparrow}}=\{y\in\mathcal{A}^{\mathbb{Z}^{d+1}}\mid\forall i\in\mathbb{Z},% \,y_{\mathbb{Z}^{d}\times\{i\}}\in X\}$ .

If $X$ is sofic (resp. effective), then both ${X^{\uparrow}}$ and ${X^{\Uparrow}}$ are also sofic (resp. effective) since they can be defined by the same forbidden patterns. On the other hand:

Theorem 2 ([13], [2, Theorem 3.1], [8, Theorem 10]).

If $X$ is an effective $\mathbb{Z}^{d}$ subshift, then ${X^{\uparrow}}$ is a sofic $\mathbb{Z}^{d+1}$ subshift.

Finally, most of our constructions will involve the notion of layers: for a subshift of a cartesian product $X\subseteq\prod_{i\in I}L_{i}$ , the layers of $X$ are the projections of $X$ onto each of the $L_{i}$ , which are often named for convenience. For $J\subseteq I$ , we will denote by $\pi_{L_{j_{1}}\times L_{j_{2}}\times\dots}\colon\prod_{i\in I}L_{i}\mapsto% \prod_{j\in J}L_{j}$ the cartesian projection.

2.2 Pattern Complexity and Extender Sets

The traditional notion of complexity is called pattern complexity and is defined by $N_{X}(n)=\mathcal{L}_{n}(X)$ . The exponential growth rate of $\lvert N_{X}(n)\rvert$ is the topological entropy:

h(X)=\lim_{n\mapsto+\infty}\frac{\log\,\lvert N_{X}(n)\rvert}{n^{d}}.

In this article, we focus on another notion of complexity based on extender sets:

Definition 3 (Extender set).

For $X\subseteq\mathcal{A}^{\mathbb{Z}^{d}}$ a $d$ -dimensional subshift, $P\subseteq\mathbb{Z}^{d}$ and $w\in\mathcal{A}^{P}$ a pattern of support $P$ , the extender set of $w$ is the set

E_{X}(w)=\{x\in\mathcal{A}^{\mathbb{Z}^{d}\setminus P}\mid x\sqcup w\in X\},

where $(x\sqcup w)_{p}=w_{p}$ if $p\in P$ and $(x\sqcup w)_{p}=x_{p}$ otherwise.

In other words, $E_{X}(w)$ is the set of all possible valid “completions” of the pattern $w$ in $X$ . For example, for two patterns with the same support $w,w^{\prime}$ , we have $E_{X}(w)\subseteq E_{X}(w^{\prime})$ if and only if the pattern $w$ can be replaced by $w^{\prime}$ every time it appears in any configuration of $X$ .

In the case of $\mathbb{Z}$ subshifts, extender sets are similar to the more classical notions of follower (resp. predecessor) sets, which are the set of right-infinite (resp. left-infinite) words that complete a finite given pattern (see for example [9]). Parallels can also be drawn with Nerode congruence classes.

For $X$ a $\mathbb{Z}^{d}$ subshift, denote $E_{X}(n)=\{E_{X}(w)\mid w\in\mathcal{L}_{n}(X)\}$ its set of extender sets. The extender set sequence $(\lvert E_{X}(n)\rvert)_{n\in\mathbb{N}}$ and its growth rate²²2The authors define it for $\mathbb{Z}$ subshifts, but the definition makes sense for higher dimensional shifts. are defined in [9]:

Definition 4 ([10, Definition 2.17]).

For a $\mathbb{Z}^{d}$ subshift $X$ , its extender entropy is

h_{E}(X)=\lim\limits_{n\to+\infty}\frac{\log\,\lvert E_{X}(n)\rvert}{n^{d}}.

This limit is well-defined by the multivariate subadditive lemma (see [5, Theorem 1]). In particular, $h_{E}(X)=\inf\limits_{n\to+\infty}\frac{\log\,\lvert E_{X}(n)\rvert}{n^{d}}$ , and $h_{E}(X)$ could actually be computed along any sequence of hyperrectangles that eventually fills $\mathbb{Z}^{d}$ .

Examples

1.

Let us consider $X=\mathcal{A}^{\mathbb{Z}^{d}}$ some full-shift in dimension $d$ . Then $X$ has maximal topological entropy, but $h_{E}(X)=0$ : indeed, for any two patterns $w,w^{\prime}\in\mathcal{L}_{n}(X)$ , we have $E_{X}(w)=E_{X}(w^{\prime})=\{\mathcal{A}^{\mathbb{Z}^{d}\setminus\llbracket 0,% n-1\rrbracket^{d}}\}$ ; which implies that $\lvert E_{X}(n)\rvert=1$ for every $n\in\mathbb{N}$ .
2.

Let us consider $X$ a (strongly) periodic subshift: there exist $p_{1},\dots,p_{d}\in\mathbb{N}$ such that, for every $x\in X$ and $i\leq d$ , we have $\sigma^{p_{i}\cdot e_{i}}(x)=x$ . Then $X$ has zero topological entropy, and we also have $h_{E}(X)=0$ . Indeed, for $n\geq\max p_{i}$ and $w\in\mathcal{L}_{n}(X)$ , $w$ is the only pattern $w^{\prime}$ such that $E_{X}(w^{\prime})=E_{X}(w)$ ; so that $\lvert E_{X}(n)\rvert=\lvert\mathcal{L}_{n}(X)\rvert\leq p\mathcal{A}^{p}$ for $p=\prod_{i}p_{i}$ .

Some Properties

Theorem 5 (From [10] on $\mathbb{Z}$ subshifts).

On $\mathbb{Z}^{d}$ subshifts:

$\blacksquare$

$h_{E}$ is a conjugacy invariant.
$\blacksquare$

$h_{E}$ is not necessarily decreasing under factor map.
$\blacksquare$

$h_{E}$ is additive under product (i.e. for $X, Y$ two subshifts, $h_{E}(X\times Y)=h_{E}(X)+h_{E}(Y)$ ).
$\blacksquare$

$h_{E}$ is upper bounded by $h$ (i.e. for $X$ a subshift, $h_{E}(X)\leq h(X)$ ).

For SFTs, the following proposition is folklore:

Proposition 6 ([15, Section 2]).

Let $X$ be a $d$ -dimensional SFT. Then $h_{E}(X)=0$ .

Sketch of proof.

In an SFT defined by adjacency constraints, the extender set of a pattern $w\in\mathcal{A}^{\llbracket 0,n-1\rrbracket^{d}}$ is determined by its border; and there are at most $2^{O(n^{d-1})}$ such borders. $\hfill\blacktriangleleft$ By an analog of the Myhill-Nerode theorem, $\mathbb{Z}$ sofic subshifts have extender entropy zero:

Proposition 7 ([21, Lemma 3.4]).

Let $X$ be a $1$ -dimensional subshift. Then $X$ is sofic if and only if $(\lvert E_{n}(X)\rvert)_{n\in\mathbb{N}}$ is uniformly bounded.

2.3 Computability Notions

2.3.1 Arithmetical Hierarchy

The arithmetical hierarchy [24, Chapter 4] stratifies formulas of first-order arithmetic over $\mathbb{N}$ by the number of their alternating unbounded quantifiers: for $n\in\mathbb{N}$ , define

	$\displaystyle\Pi^{0}_{n}$	$\displaystyle=\{\forall k_{1},\exists k_{2},\forall k_{3},\dots\ \phi(k_{1},% \dots,k_{n})\mid\phi\text{ only contains bounded quantifiers}\}$
	$\displaystyle\Sigma^{0}_{n}$	$\displaystyle=\{\exists k_{1},\forall k_{2},\exists k_{3},\dots\ \phi(k_{1},% \dots,k_{n})\mid\phi\text{ only contains bounded quantifiers}\}.$

A decision problem is said to be in $\Pi^{0}_{n}$ (resp. $\Sigma^{0}_{n}$ ) if its set of solutions $S\subseteq\mathbb{N}$ is described by a $\Pi^{0}_{n}$ (resp. $\Sigma^{0}_{n}$ ) formula: in other words, $\Pi^{0}_{0}=\Sigma^{0}_{0}$ corresponds to the set of computable decision problems; $\Sigma^{0}_{1}$ is the set of computably enumerable decision problems, etc…

2.3.2 Arithmetical Hierarchy of Real Numbers

The arithmetical hierarchy of real numbers [27] stratifies real numbers depending on the difficulty of computably approximating them: for $n\geq 0$ , define

	$\displaystyle\Sigma_{n}$	$\displaystyle=\{x\in\mathbb{R}\mid\{r\in\mathbb{Q}\mid r\leq x\}\text{ is a }% \Sigma^{0}_{n}\text{ set}\}$
	$\displaystyle\Pi_{n}$	$\displaystyle=\{x\in\mathbb{R}\mid\{r\in\mathbb{Q}\mid r\geq x\}\text{ is a }% \Sigma^{0}_{n}\text{ set}\}{\color[rgb]{0.3,0.3,0.3}\definecolor[named]{% pgfstrokecolor}{rgb}{0.3,0.3,0.3}\pgfsys@color@gray@stroke{0.3}% \pgfsys@color@gray@fill{0.3}\;=\{x\in\mathbb{R}\mid\{r\in\mathbb{Q}\mid r\leq x% \}\text{ is a }\Pi^{0}_{n}\text{ set}\}}.$

In particular, $\Sigma_{0}=\Pi_{0}$ is the set of computable real numbers, i.e. numbers that can be computably approximated up to arbitrary precision; $\Pi_{1}$ real numbers are also called right-computable, since they can be computably approximated from above; etc…

Alternatively, this hierarchy is also defined by the number of alternating limit operations needed to obtain a real number from the computable ones [27]. In other words, for $n\geq 1$ :

	$\displaystyle\Sigma_{n}$	$\displaystyle=\Big{\{}\sup_{k_{1}\in\mathbb{N}}\inf_{k_{2}\in\mathbb{N}}\sup_{% k_{3}\in\mathbb{N}}\dots\ \beta_{k_{1},\dots,k_{n}}\mid(\beta_{k_{1},\dots,k_{% n}})_{k_{1},\dots,k_{n}\in\mathbb{N}}\in\mathbb{Q}^{\mathbb{N}^{n}}\text{ is % computable}\Big{\}}$
	$\displaystyle\Pi_{n}$	$\displaystyle=\Big{\{}\inf_{k_{1}\in\mathbb{N}}\sup_{k_{2}\in\mathbb{N}}\inf_{% k_{3}\in\mathbb{N}}\dots\ \beta_{k_{1},\dots,k_{n}}\mid(\beta_{k_{1},\dots,k_{% n}})_{k_{1},\dots,k_{n}\in\mathbb{N}}\in\mathbb{Q}^{\mathbb{N}^{n}}\text{ is % computable}\Big{\}}$

3 Elementary Constructions on Extender Sets

The free lift

We use this construction to generalize results on $\mathbb{Z}$ or $\mathbb{Z}^{2}$ subshifts to higher dimensions:

Claim 8.

For a subshift $X\subseteq\mathcal{A}^{\mathbb{Z}^{d}}$ , $h_{E}(X)=h_{E}({X^{\Uparrow}})$ .

Proof.

Consider ${X^{\Uparrow}}\subseteq\mathcal{A}^{\mathbb{Z}^{d+1}}$ . Since each $d$ -dimensional hyperplane of $\mathbb{Z}^{d+1}$ contains an independent configuration, we have $\lvert E_{{X^{\Uparrow}}}(n)\rvert=\lvert E_{X}(n)\rvert^{n}$ and $h_{E}({X^{\Uparrow}})=h_{E}(X)$ . $\hfill\vartriangleleft$

The (semi)-mirror construction

Claim 9.

Let $Y$ be any $\mathbb{Z}^{2}$ sofic subshift over an alphabet $\mathcal{A}$ . There exists a $\mathbb{Z}^{2}$ sofic subshift $Y_{\mathrm{mirror}}$ such that $h_{E}(Y_{\mathrm{mirror}})=h(Y)$ ( $=h(Y_{\mathrm{mirror}})$ ).

A first idea to create one extender set per pattern of $Y$ is the mirror construction: add a line of some special symbol $\ast$ to separate two half-planes; the upper half-plane contains a half-configuration of $Y$ , while the lower half-plane contains its reflection by the line of $\ast$ . As any two patterns of $Y$ have distinct reflections, they generate different extender sets: this results in a subshift $Y^{\prime}$ verifying $h_{E}(Y^{\prime})=h(Y)$ . Unfortunately, $Y^{\prime}$ is not always sofic, see for example [1, Proposition 57].

Refer to caption — (a) The (classical) mirror shift.

To solve this non-soficness issue, the semi-mirror with large discrepancy from [7, Example $5^{\prime\prime}$ ] reflects a single symbol instead of the whole upper-plane:

Sketch of proof.

For $\mathcal{A}^{\prime}=\mathcal{A}\cup\{\square,\ast\}$ , define $Y_{\mathrm{mirror}}$ over the alphabet $\mathcal{A}^{\prime}$ as follows:

$\blacksquare$

Symbols $\ast$ must be aligned in a row, and there is at most one such row per configuration.
$\blacksquare$

If a row of $\ast$ appears in a configuration $x$ , then the lower half-plane contains at most one non- $\square$ position; and the upper half-plane must appear in a configuration of $Y$ .
$\blacksquare$

If $x_{i,j}=\ast$ and $x_{i,j-k}\in\mathcal{A}$ for some $i\in\mathbb{Z},j\in\mathbb{Z},k\in\mathbb{N}$ , then $x_{i,j+k}=x_{i,j-k}$ . In other words, the only symbol of $\mathcal{A}$ in the lower half-plane must be the mirror of the same symbol in the upper half-plane, as reflected by the horizontal row of $\ast$ symbols.

Then $Y_{\mathrm{mirror}}$ is sofic and $h_{E}(Y_{\mathrm{mirror}})=h(Y)$ . Indeed, any two distinct patterns of $Y$ must appear in $Y_{\mathrm{mirror}}$ and have distinct extender sets, since they can have different reflections. $\hfill\blacktriangleleft$

This construction shows that there exist subshifts with arbitrarily large extender entropy; and since every $\Pi_{1}$ real number is the topological entropy of some (SFT, thus) sofic subshift [14], every $\Pi_{1}$ number can be realized as the extender entropy of some sofic subshift. In particular, this further disproves the conjecture from [15] mentioned in the introduction.

4 Decision Problems on Extender Sets

4.1 Inclusion of Extender Sets

Let us consider the following decision problem:

Extender-inclusion
Input:	An effective subshift $X\subseteq\mathcal{A}^{\mathbb{Z}^{d}}$ , and $u,v\in\mathcal{L}(X)$ ,
Output:	Whether $E_{X}(u)\subseteq E_{X}(v)$ .

Proposition 10.

Extender-inclusion is a $\Pi_{2}^{0}$ -complete problem.

Proof of inclusion.

As $E_{X}(u)\subseteq E_{X}(v)$ if and only if $\forall B\in\mathcal{A}^{\ast},u\sqsubseteq B\implies(B\not\in\mathcal{L}(X)\,% \vee\,((B\setminus u)\sqcup v)\in\mathcal{L}(X))$ , we obtain inclusions: indeed, for $X$ effective, deciding whether a pattern $w$ belongs in $\mathcal{L}(X)$ is a $\Pi^{0}_{1}$ problem. $\hfill\blacktriangleleft$

Proof of $\Pi^{0}_{2}$ -hardness for $\mathbb{Z}$ subshifts.

We reduce the following known $\Pi^{0}_{2}$ problem³³3It is equivalent to Inf (does a given machine halt on infinitely many inputs?). See [24, Theorem 4.3.2].:

Det-Rec-state
Input:	A deterministic Turing Machine $M$ , and a state $q$ ,
Output:	Is $q$ visited infinitely often by $M$ during its run on the empty input?

Let $(M,q)$ be an instance of this Det-Rec-state. We construct an effective subshift $X$ over the alphabet $\{\texttt{0},\texttt{1},\square\}$ as follows:

$\blacksquare$

Symbols 0 and 1 cannot appear together in a configuration. The symbol 1 can only appear at most once in a configuration.
$\blacksquare$

If two symbols 0 appear in a configuration at distance, say, $n>0$ , then the whole configuration is $n$ -periodic; and if $M$ enters $q$ at least $n^{\prime}$ times, then we impose $n>n^{\prime}$ .

As the rules above forbid an enumerable set of patterns, $X$ is an effective subshift.

Finally, $E_{X}(\texttt{0})\subseteq E_{X}(\texttt{1})$ if and only if $M$ enters $q$ infinitely many times. Indeed, the symbol 0 can be extended either by semi-infinite lines of symbols $\square$ , which also extend the symbol 1 ; or by configurations containing $n$ -periodic symbols 0, which do not extend the symbol 1 because of the first rule. However, by the second rule, this $n$ -periodic configuration exists if and only if $M$ visits $q$ less than $n$ times. $\hfill\blacktriangleleft$

4.2 Computing the Number of Extender Sets

Let us determine the computational complexity of the problem “ $k\leq\lvert E_{X}(n)\rvert$ ”, when given a subshift $X$ , some size $n$ and some $k$ . It is equivalent to the following:

\bigvee_{v_{1},\dots,v_{k}\in\mathcal{L}_{n}(X)}\bigwedge_{1\leq i<j\leq k}E_{% X}(v_{i})\neq E_{X}(v_{j}).

Since $v_{i}\in\mathcal{L}_{n}(X)$ is a $\Pi^{0}_{1}\subseteq\Sigma^{0}_{2}$ problem and that the class of $\Sigma^{0}_{2}$ problems is stable by finite disjunctions and conjunctions, we conclude from Proposition 10 that:

Lemma 11.

For an effective subshift $X$ , “ $\,k\leq\lvert E_{X}(n)\rvert$ ” is a $\Sigma_{2}^{0}$ problem.

4.3 Upper Computational Bounds on Extender Entropies

Corollary 12.

For $X$ an effective subshift, $h_{E}(X)\in\Pi_{3}$ .

Proof.

Given $X$ and $n$ , the set $\{k\leq\lvert E_{X}(n)\rvert\}$ is a $\Sigma^{0}_{2}$ set if $X$ is effective by Lemma 11. This implies that $\frac{\log\,\lvert E_{X}(n)\rvert}{n^{d}}$ is $\Sigma_{2}$ ; and since $h_{E}(X)=\inf_{n}\frac{\log\,\lvert E_{X}(n)\rvert}{n^{d}}$ , we obtain $h_{E}(X)\in\Pi_{3}$ as the infimum of $\Sigma_{2}$ real numbers. $\hfill\blacktriangleleft$

5 $\Pi_{3}$ Extender Entropies for $\mathbb{Z}$ Effective Subshifts

Let us focus on one-dimensional subshifts for the time being.

See A

In order to construct a subshift $Z_{\alpha}$ with $h_{E}(Z_{\alpha})=\alpha$ , we would like to have $\lvert E_{Z_{\alpha}}(n)\rvert\simeq 2^{\alpha n}$ . To do so, we could create one extender set per pattern, and $2^{\alpha n}$ patterns of size $n$ (as the semi-mirror in Section 3); however, since effective subshifts have $\Pi_{1}$ entropies, this would not realize the whole class of $\Pi_{3}$ numbers.

Yet, realizing the right number of patterns is the main idea behind the proof that follows: we just do not blindly create one extender set per pattern, but only separate extender sets when some conditions are met.

5.1 Preliminary: Encoding Integers With Configurations $\left\langle i\right\rangle_{k}$

Before we begin our construction, we fix a way to encode integers in configurations: to encode the integer $i\in\mathbb{N}$ , we use configurations where a symbol $\ast$ is $i$ -periodic, and the rest is blank.

More formally, consider the alphabet $\mathcal{A}_{\ast}=\{\ast,\texttt{\textvisiblespace}\}$ . Denote by $\left\langle i\right\rangle_{k_{1}}$ the $i$ -periodic configuration $\left\langle i\right\rangle_{k_{1}}=\sigma^{k_{1}}(\dots\texttt{% \textvisiblespace}\underbrace{\ast\,\texttt{\textvisiblespace}\dots\texttt{% \textvisiblespace}\,\ast}_{i+1\text{ symbols}}\texttt{\textvisiblespace}\dots% \texttt{\textvisiblespace}\ast\texttt{\textvisiblespace}\dots)$ properly defined as $(\left\langle i\right\rangle_{k_{1}})_{p}=\ast$ if and only if $p=k_{1}\bmod i$ . A configuration $\left\langle i\right\rangle_{k_{1}}$ is said to encode the integer $i\in\mathbb{N}$ . Considering the subshift all the configurations $\left\langle i\right\rangle_{k_{1}}$ for $i\in\mathbb{N}$ and $k_{1}\leq i$ generate, we denote:

X_{\ast}=\bigcup_{i\in\mathbb{N}}\{\left\langle i\right\rangle_{k_{1}}\in% \mathcal{A}_{\ast}^{\mathbb{Z}}\mid k_{1}\leq i\}\cup\left\langle\infty\right\rangle

where $\left\langle\infty\right\rangle=\{x\in\mathcal{A}_{\ast}^{\mathbb{Z}}\mid|x|_{% \ast}\leq 1\}$ is the set of configurations having at most one symbol $\ast$ . The configurations of $\left\langle\infty\right\rangle$ are said to be degenerate, and they appear when taking the closure of all $\left\langle i\right\rangle_{k_{1}}$ .

5.2 Preliminary: Toeplitz Density in Periodic Configurations

Our construction will also need to build configurations with a controlled density of symbols, i.e. configurations on $\{0,1\}$ where the number of symbols $1$ in large patterns converges to some value: for some fixed $\alpha$ , we want to build configurations $x\in\{0,1\}^{\mathbb{Z}}$ such that $\lim_{n\to+\infty}\frac{1}{n}\cdot|x|_{\llbracket 0,n-1\rrbracket}|_{1}=\alpha$ . Several explicit constructions of such configurations and subshifts exist. We choose to work with Toeplitz sequences.

Toeplitz density words

Consider the ruler sequence $T=12131214\dots$ defined by $T_{n}=\max\{m\in\mathbb{N}:2^{m}\mid 2n\}$ (see Oeis A001511). For a given binary sequence $u=(u_{n})_{n\in\mathbb{N}}\in\{0,1\}^{\mathbb{N}}$ , we consider its Toeplitzification $T(u)\in\{0,1\}^{\mathbb{N}}$ defined as $T(u)_{n}=u_{T_{n}}$ for $n\in\mathbb{N}$ .

In particular, for $\beta\in[0,1]$ a real number and $(\beta_{n})_{n\in\mathbb{N}}$ its proper binary expansion, we consider the word $T(\beta)=(\beta_{T_{n}})_{n\in\mathbb{N}}=\beta_{1}\,\beta_{2}\,\beta_{1}\,% \beta_{3}\,\beta_{1}\,\beta_{2}\dots$ . Denoting by $|w|_{1}$ the numbers of letters $1$ in a binary word $w\in\{0,1\}^{*}$ and by $|w|$ its length, we have:

Claim 13.

For $\beta\in[0,1]$ and $w\sqsubseteq T(\beta)$ a factor of $T(\beta)$ , we have $|w|_{1}=\beta\cdot|w|+O(1)$ .

Toeplitz density in periodic configurations

For our specific construction, let $\alpha\in[0,1]$ and $i\in\mathbb{N}$ , and consider the subshift $T_{\leq\alpha,i}$ composed of $i$ -periodic configurations made of truncated Toeplitz words:

T_{\leq\alpha,i}=\{x\in\{0,1\}^{\mathbb{Z}}\mid\exists\beta\leq\alpha,\exists k% _{1}\in\llbracket 0,i-1\rrbracket,\forall p\in\mathbb{Z},\,x_{p}=T(\beta)_{(p+% k_{1}\bmod i)}\}

We denote $T(\beta,i)_{k_{1}}\in\{0,1\}^{\mathbb{Z}}$ the configuration defined by $(T(\beta,i)_{k_{1}})_{p}=T(\beta)_{(p+k_{1}\bmod i)}$ for $p\in\mathbb{Z}$ . Notice that, for any $\alpha\in[0,1]$ , $i\in\mathbb{N}$ and $n\in\mathbb{N}$ , there are $|\mathcal{L}_{n}(T_{\leq\alpha,i})|=2^{\log(\min(i,n))+O(1)}\cdot O(\min(i,n))$ factors of length $n$ in $T_{\leq\alpha,i}$ .

Claim 14.

Let $\alpha\in[0,1]\cap\Pi_{1}$ . Then $T_{\leq\alpha,i}$ is an SFT, and a family of forbidden patterns realizing $T_{\leq\alpha,i}$ can be computably enumerated from $\alpha$ .

Proof.

Consider $\alpha\in\Pi_{1}$ : the set $\{r\in Q\mid r>\alpha\}$ is computably enumerable. Thus, the following family $\mathcal{F}$ of forbidden patterns that realizes $T_{\leq\alpha,i}$ is recursively enumerable: forbid finite pattern that are either not $i$ -periodic, or do not respect the structure of the ruler sequence in an $i$ -period; and inside an $i$ -period, forbid patterns $r_{T_{1}}\,r_{T_{2}}\,r_{T_{1}}\ldots\in\{0,1\}^{i}$ that encode the finite expansion of a rational $r=\sum_{k=1}^{\log i}r_{k}2^{-k}$ if $r$ is such that $r>\alpha$ . $\hfill\vartriangleleft$

5.3 Construction: the Effective $\mathbb{Z}$ Subshift $Z_{\alpha}$

Let us now begin the construction to prove A. Let $\alpha\in\Pi_{3}$ be a positive real number, $\alpha=\inf_{i}\sup_{j}\alpha_{i,j}$ for some computable sequence $(\alpha_{i,j})$ of $\Pi_{1}$ real numbers. We can assume $\alpha\leq 1$ since extender entropy is additive under cartesian products, and using [27, Lemma 3.1] we can assume that $(\alpha_{i,j})_{i,j\in\mathbb{N}^{2}}$ satisfies some monotonicity properties: for all $i$ , $(\alpha_{i,j})_{j\in\mathbb{N}}$ is weakly increasing towards some $\alpha_{i}$ ; and the sequence $(\alpha_{i})_{i\in\mathbb{N}}$ is weakly decreasing towards $\alpha$ .

Auxiliary subshift $Z_{\alpha}^{\prime}$

We create an auxiliary subshift $Z_{\alpha}^{\prime}$ on the following three layers:

1.

First layer $L_{1}$ : We take $L_{1}=X_{\ast}$ to encode integers $i\in\mathbb{N}$ . Intuitively, $i$ will denote which $\Sigma_{2}$ number $\alpha_{i}$ is approximated in the configuration.
2.

Second layer $L_{2}$ : We also set $L_{2}=X_{\ast}$ to encode integers $j\in\mathbb{N}$ , $j\geq i$ . Intuitively, $j$ will denote which $\Pi_{1}$ number $\alpha_{i,j}$ is approximated in the configuration.
3.

Density layer $L_{d}$ : We define the density layer as $L_{d}=\{0,1\}^{\mathbb{Z}}$ . Whenever the first two layers are non-degenerate, this layer will be restricted to densities $\lesssim\alpha_{i,j}$ . Since the real numbers $\alpha_{i,j}$ are $\Pi_{1}$ , the subshifts $T_{\leq\alpha_{i,j},i}$ are effective from the numbers $\alpha_{i,j}$ .

such that $Z_{\alpha}^{\prime}$ is defined as:

	$\displaystyle Z_{\alpha}^{\prime}$	$\displaystyle=\Big{\{}(z^{(1)},z^{(2)},z^{(d)})\in L_{1}\times L_{2}\times L_{% d}\mid z^{(2)}\in\left\langle\infty\right\rangle\Big{\}}$
		$\displaystyle\hskip 5.69046pt\cup\bigcup_{i\in\mathbb{N}}\bigcup_{j\geq i}\Big% {\{}(z^{(1)},z^{(2)},z^{(d)})\in L_{1}\times L_{2}\times L_{d}\mid\exists k_{1% },k_{2}\in\mathbb{N},$
		$\displaystyle\hskip 85.35826ptz^{(1)}=\left\langle i\right\rangle_{k_{1}},\,z^% {(2)}=\left\langle j\right\rangle_{k_{2}}\,\text{and }\exists\beta\leq\alpha_{% i,j},\,z^{(d)}=T(\beta,i)_{k_{1}}\Big{\}}$

Figure 3: A proper configuration:

L_{d}

contains a Toeplitz encoding of

\overline{.1010}^{2}=\frac{5}{8}

.

z=(\left\langle 15\right\rangle_{11},\left\langle 18\right\rangle_{1},T(\frac{% 5}{8},15)_{10})

. The vertical red line indicates the origin.

Claim 15.

The $\mathbb{Z}$ subshift $Z_{\alpha}^{\prime}$ is an effective subshift.

Proof.

Since the subshift $X_{\ast}$ is effective, the conditions on the first two layers $L_{1}$ and $L_{2}$ are straightforward to enforce. Furthermore, since the $\alpha_{i,j}$ are $\Pi_{1}$ real numbers enumerated by a single machine, by Claim 14 we can obtain $Z_{\alpha}^{\prime}$ as follows: a pattern $w=(w^{(1)},w^{(2)},w^{(d)})\in\mathcal{L}(X_{\ast})\times\mathcal{L}(X_{\ast})% \times\{0,1\}^{n}$ is forbidden whenever both $w^{(1)}$ and $w^{(2)}$ contain at least two symbols $\ast$ (so that $w^{(1)}$ encodes an integer $i\in\mathbb{N}$ , $w^{(2)}$ encodes an integer $j\geq i$ ) and $w^{(d)}$ contains a pattern forbidden in $T_{\leq\alpha_{i,j},i}$ . $\hfill\vartriangleleft$

A configuration $z=(\left\langle i\right\rangle_{k_{1}},\left\langle j\right\rangle_{k_{2}},T(% \beta,i)_{k_{1}})\in Z_{\alpha}^{\prime}$ is said to be proper. A configuration $z=(z^{(1)},z^{(2)},\cdot\,)\in Z_{\alpha}^{\prime}$ with $z^{(2)}\in\left\langle\infty\right\rangle$ is said to be degenerate. Thus, we separate patterns into two categories: whenever $w\in\mathcal{L}(Z_{\alpha}^{\prime})$ only appears in degenerate configurations, we call it a degenerate pattern; if $w$ can appear in a proper configuration, we call it a proper pattern.

On the one hand, degenerate patterns of $Z_{\alpha}^{\prime}$ do not contribute much to the number of extender sets, despite being exponentially many:

Claim 16.

Let $n\in\mathbb{N}$ , and consider $D_{E}(n)=\{E_{Z_{\alpha}^{\prime}}(w)\mid w\in\mathcal{L}_{n}(Z_{\alpha}^{% \prime})\text{ degenerate}\}$ , the set of extender sets of degenerate patterns of size $n$ . Then $|D_{E}(n)|=O(n^{3})$ .

Proof.

Let $u,v\in\mathcal{L}_{n}(Z_{\alpha}^{\prime})$ be two degenerate patterns. Whenever $u^{(1)}=v^{(1)}$ and $u^{(2)}=v^{(2)}$ , we have $E_{Z_{\alpha}^{\prime}}(u)=E_{Z_{\alpha}^{\prime}}(v)$ because the density layer of such patterns can be anything. Since at most a single symbol $\ast$ can appear on the second layer of degenerate patterns, by counting possibilities for their first layers we obtain $|D_{E}(n)|=O(n^{3})$ . $\hfill\vartriangleleft$

On the other hand, all proper patterns of $Z_{\alpha}^{\prime}$ belong to distinct extender sets:

Claim 17.

Let $u,v\in\mathcal{L}_{n}(Z_{\alpha}^{\prime})$ be two distinct proper patterns. Then $E_{Z_{\alpha}^{\prime}}(u)\neq E_{Z_{\alpha}^{\prime}}(v)$ .

Proof.

Let $u\in\mathcal{L}_{n}(Z_{\alpha}^{\prime})$ be a proper pattern. It can be extended into a whole proper configuration $z=(\left\langle i\right\rangle_{k_{1}},\left\langle j\right\rangle_{k_{2}},z^{% (d)})\in Z_{\alpha}^{\prime}$ such that $z|_{\llbracket 0,n-1\rrbracket}=u$ . By definition, $z$ is periodic of period $i\cdot j$ : thus, $z|_{\llbracket 0,n-1\rrbracket}$ is entirely determined by $z|_{\llbracket n,i\cdot j+n-1\rrbracket}$ , and $z|_{\mathbb{Z}\setminus\llbracket 0,n-1\rrbracket}$ can only extend the pattern $u$ itself. $\hfill\vartriangleleft$

However, there are only polynomially many distinct proper patterns of a given size in $Z_{\alpha}^{\prime}$ . The next section will neverthelesss create a subshift $Z_{\alpha}$ with the correct (exponential) amount of proper patterns, thanks to the following remark:

Claim 18.

$\blacksquare$

For an integer $i\in\mathbb{N}$ and a proper configuration $z\in Z_{\alpha}^{\prime}$ such that $z^{(1)}=\left\langle i\right\rangle_{k_{1}}$ , an $i$ -period of the density layer $z^{(d)}$ contains at most $\alpha_{i}\cdot i+O(1)$ symbols $1$ .
$\blacksquare$

For integers $n\in\mathbb{N}$ and $i\geq n$ , and a proper configuration $z\in Z_{\alpha}^{\prime}$ such that $z^{(1)}=\left\langle i\right\rangle_{k_{1}}$ , a factor of length $n$ of the density layer $z^{(d)}$ contains at most $\alpha_{n}\cdot n+O(1)$ symbols $1$ .

Proof.

This follows from Claim 13 and the monotonicity of the sequence $(\alpha_{i,j})_{i,j\in\mathbb{N}^{2}}$ . $\hfill\vartriangleleft$

Free bits in the subshift $Z_{\alpha}$

To create the desired exponential number of extender sets, we create the subshift $Z_{\alpha}$ by adding free bits on top of the symbols $1$ of the density layer. Informally, if there were $\beta\cdot i+O(1)$ symbols $1$ in an $i$ -period of the density layer in $Z_{\alpha}^{\prime}$ , adding free bits on top of the symbols $1$ creates $2^{\beta\cdot i+O(1)}$ patterns in $Z_{\alpha}$ . Thus, we add a fourth layer to $Z_{\alpha}^{\prime}$ :

4.

Free layer $L_{f}$ : We define the free layer as $L_{f}=\{\texttt{\textvisiblespace},0,1\}^{\mathbb{Z}}$ . Given the synchronizing map $\pi_{\mathrm{sync}}\colon\{\texttt{\textvisiblespace},0,1\}\to\{0,1\}$ defined as $\pi_{\mathrm{sync}}(0)=\pi_{\mathrm{sync}}(1)=1$ and $\pi_{\mathrm{sync}}(\texttt{\textvisiblespace})=0$ , we say that two configurations $z^{(d)}\in L_{d}$ and $z^{(f)}\in L_{f}$ are synchronized if $\pi_{\mathrm{sync}}(z^{(f)})=z^{(d)}$ .

and we define $Z_{\alpha}$ as:

	$\displaystyle Z_{\alpha}$	$\displaystyle=\Big{\{}(z^{(1)},z^{(2)},z^{(d)},z^{(f)})\in L_{1}\times L_{2}% \times L_{d}\times L_{f}\mid z^{(1)}\in\left\langle\infty\right\rangle\text{ % or }z^{(2)}\left\langle\infty\right\rangle\Big{\}}$
		$\displaystyle\cup\bigcup_{i\in\mathbb{N}}\bigcup_{j\geq i}\Big{\{}(z^{(1)},z^{% (2)},z^{(d)},z^{(f)})\in L_{1}\times L_{2}\times L_{d}\times L_{f}\mid\exists k% _{1},k_{2}\in\mathbb{N},$
		$\displaystyle\hskip 85.35826ptz^{(1)}=\left\langle i\right\rangle_{k_{1}},\,z^% {(2)}=\left\langle j\right\rangle_{k_{2}}\,\pi_{\mathrm{sync}}(z^{(f)})=z^{(d)},$
		$\displaystyle\hskip 85.35826pt\exists\beta\leq\alpha_{i,j},\,z^{(d)}=T(\beta,i% )_{k_{1}}\,\text{and }z^{(f)}\text{ is $i$-periodic }\Big{\}}.$

Claim 19.

The $\mathbb{Z}$ subshift $Z_{\alpha}$ is effective.

Proof.

In addition to the forbidden patterns of $Z_{\alpha}^{\prime}$ , forbid patterns $w=(w^{(1)},w^{(2)},w^{(d)},w^{(f)})$ for which $w^{(1)}$ and $w^{(2)}$ both contain two symbols $\ast$ (in which case, denote by $i$ the distance between two symbols $\ast$ in $w^{(1)}$ ), but $w^{(f)}$ is either not synchronized with $w^{(d)}$ or not $i$ -periodic. $\hfill\vartriangleleft$

We extend the terminology from $Z_{\alpha}^{\prime}$ to $Z_{\alpha}$ and call proper the configurations of $Z_{\alpha}$ that encode integers $i\in\mathbb{N}$ and $j\geq i$ on their first two layers, and degenerate those who do not. Similarly, a pattern is proper if it can be extended into a proper configuration, and degenerate if it only extends into degenerate configurations.

Since the free layer is required to be $i$ -periodic only in proper configurations, Claims 16 and 17 both extend from $Z_{\alpha}^{\prime}$ to $Z_{\alpha}$ by the very same arguments:

Claim 20.

$\blacksquare$

For $n\in\mathbb{N}$ , consider $D_{E}(n)=\{E_{Z_{\alpha}}(w)\mid w\in\mathcal{L}_{n}(Z_{\alpha})\text{ % degenerate}\}$ . Then $D_{E}(n)=O(n^{2})$ .
$\blacksquare$

Let $u,v\in\mathcal{L}_{n}(Z_{\alpha})$ be two distinct proper patterns. Then $E_{Z_{\alpha}}(u)\neq E_{Z_{\alpha}}(v)$ .

Lemma 21.

Let $P(n)=\{w\in\mathcal{L}_{n}(Z_{\alpha})\mid w\text{ is proper}\}$ . Then

2^{n\cdot\alpha_{n}+O(1)}\leq P(n)\leq\mathrm{poly}(n)\cdot\sum_{i=1}^{n}2^{% \alpha_{i}\cdot i+O(1)}.

Proof: lower bound..

Consider the patterns $w^{\prime}=(\left\langle n\right\rangle_{0},\left\langle j\right\rangle_{0},T(% \alpha_{n,j},n)_{0})|_{\llbracket 0,n-1\rrbracket}$ in $Z_{\alpha}^{\prime}$ for $j\geq n$ : the number of symbols $1$ in the density layer $w^{\prime(d)}$ of such $w^{\prime}$ is $\alpha_{n,j}\cdot n+O(1)$ by Claim 13. Since $\alpha_{n,j}\to\alpha_{n}$ , by taking $j\geq n$ large enough we obtain a proper pattern $w^{\prime}\in\mathcal{L}_{n}(Z_{\alpha}^{\prime})$ such that its density layer $w^{\prime(d)}$ contains $\alpha_{n}\cdot n+O(1)$ symbols $1$ .

Thus, we obtain $2^{\alpha_{n}\cdot n+O(1)}$ proper patterns $w\in\mathcal{L}_{n}(Z_{\alpha})$ such that $\pi_{L_{1}\times L_{2}\times L_{d}}(w)=w^{\prime}$ (since each symbol $1$ in $w^{(d)}$ leads to two distinct patterns in the free layer $L_{f}$ ). $\hfill\blacktriangleleft$

Proof: upper bound..

To overestimate the number of proper patterns $|P(n)|$ , we consider the restrictions $w^{\prime}=z^{\prime}_{\llbracket 0,n-1\rrbracket}$ for $z^{\prime}$ ranging in the proper configurations of $Z_{\alpha}^{\prime}$ (consider all values of $\left\langle i\right\rangle_{k_{1}},\left\langle j\right\rangle_{k_{2}}$ and of $n$ -factors in $y^{(d)}$ ), and bound the number of symbols $1$ in each case: by Claim 18,

$\blacksquare$

If $i\leq n$ , an $i$ -period of the density layer $w^{\prime(d)}$ contains less than $\alpha_{i}\cdot i+O(1)$ symbols $1$ .
$\blacksquare$

For $i>n$ , $w^{\prime(d)}$ contains less than $\alpha_{n}\cdot n+O(1)$ symbols $1$ .

Since each symbol $1$ in an $i$ -period of the density layer results in two distinct patterns in the free layer, and there are less than $O(i^{2})$ possibilities for such periods, we obtain:

	$\displaystyle P(n)$	$\displaystyle\leq\sum_{i=1}^{n}\sum_{k_{1}=0}^{i-1}\sum_{j=1}^{n}\sum_{k_{2}=0% }^{j-1}O(i^{2})\cdot 2^{\alpha_{i}\cdot i+O(1)}+\sum_{k_{1}=0}^{n}\sum_{k_{2}=% 0}^{n}O(n^{2})\cdot 2^{\alpha_{n}\cdot n+O(1)}$
		$\displaystyle\leq\mathrm{poly}(n)\cdot\sum_{i=1}^{n}2^{\alpha_{i}\cdot i+O(1)}.\$

$\hfill\blacktriangleleft$

Combining Lemma 21 with Claim 20, we obtain by taking the limit over $\alpha_{n}\to\alpha$ that $h_{E}(Z_{\alpha})=\alpha$ , which concludes the proof.

6 $\Pi_{3}$ Extender Entropies for $\mathbb{Z}^{2}$ Sofic Subshifts

We now want to extend A to multidimensional sofic shifts: an idea could be to replace $i$ -periodic words on $\mathbb{Z}$ in the previous construction with $(i,i)$ -periodic squares on $\mathbb{Z}^{2}$ . Unfortunately, such a subshift cannot be sofic⁴⁴4The argument proving that the classical mirror subshift cannot be sofic still applies here: there would be $2^{O(i^{2})}$ distinct $i\times i$ patterns, but only $2^{O(i)}$ borders in the SFT cover..

Yet, making configurations periodic is not necessary to ensure that two proper patterns $u$ and $v$ have distinct extender sets: it is enough to have a configuration that witnesses the difference between $u$ and $v$ (by extending one but not the other). This was already illustrated in the semi-mirror shift (see Section 3): instead of mirroring the whole half-plane (which is not sofic), non-deterministically reflecting a single bit from the upper to the lower half-plane is actually enough, since each bit can be reflected individually in some configuration. In this section, we use this idea to prove (see Figure 4):

See B

6.1 Preliminary: Marking Offsets With Configurations $\left[2i\right]_{m_{1},m_{2}}$

In our construction, we will need to mark some positions $(m_{1}+i\mathbb{Z},m_{2}+i\mathbb{Z})$ . To do so, we consider the alphabet $A_{m}=\{\square,{\color[rgb]{1,0.7,0.7}\definecolor[named]{pgfstrokecolor}{rgb% }{1,0.7,0.7}\blacksquare}\}$ . Denote by $\left[2i\right]_{m_{1},m2}$ the $(2i,2i)$ -periodic configuration formally defined as $(\left[2i\right]_{m_{1},m_{2}})_{p}={\color[rgb]{1,0.7,0.7}\definecolor[named]% {pgfstrokecolor}{rgb}{1,0.7,0.7}\blacksquare}$ if and only if $p=(m_{1},m_{2})\bmod(2i,2i)$ . We say that a symbol ${\color[rgb]{1,0.7,0.7}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.7,0.7}\blacksquare}$ is a marker.

For a configuration $x=\left[2i\right]_{m_{1},m_{2}}$ with $(m_{1},m_{2})\in\llbracket 0,2i-1\rrbracket^{2}$ , we say that a position $p\in\mathbb{Z}^{2}$ is marked if $p\in(m_{1}+i\mathbb{Z},m_{2}+i\mathbb{Z})$ . This lattice has unit cells of size $i\times i$ instead of $2i\times 2i$ : this is voluntary. In particular, some marked positions $p\in\mathbb{Z}^{2}$ satisfy $x_{p}=\square$ .

Considering the subshift generated by all the configurations $\left[i\right]_{m_{1},m_{2}}$ , we define:

\mathcal{G}=\bigcup_{i\in\mathbb{N}}\{\left[i\right]_{m_{1},m_{2}}\mid(m_{1},m% _{2})\in\llbracket 0,i-1\rrbracket^{2}\}\cup\left[\infty\right]

where $\left[\infty\right]=\{x\in A_{m}^{\mathbb{Z}^{2}}\mid|x|_{{\color[rgb]{% 1,0.7,0.7}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.7,0.7}\blacksquare}}% \leq 1\}$ is the set of configurations having at most one marker symbol ${\color[rgb]{1,0.7,0.7}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.7,0.7}\blacksquare}$ : these are the configurations that appear when taking the closure of all $\left[i\right]_{m_{1},m_{2}}$ .

6.2 Construction: the Sofic $\mathbb{Z}^{2}$ Subshift $Y_{\alpha}$

Let us now begin a construction to prove B. We use the notations introduced in the proof of A: we fix $\alpha\in[0,1]\cap\Pi_{3}$ such that $\alpha=\inf_{i}\sup_{j}\alpha_{i,j}$ for $\alpha_{i,j}$ a computable sequence of $\Pi_{1}$ real numbers (we assume the same monotonicity properties). We define a subshift $Y_{\alpha}$ on the following five layers:

$\blacksquare$

Lifted layers: We define the first three layers of $Y_{\alpha}$ as ${L_{1}^{\uparrow}}\times{L_{2}^{\uparrow}}\times{L_{d}^{\uparrow}}$ , where $L_{1},L_{2}$ and $L_{d}$ are the three layers of the subshift $Z_{\alpha}^{\prime}$ defined in the proof of A.
$\blacksquare$

Marker layer $L_{m}$ : We define $L_{m}=\mathcal{G}$ to mark positions $p\in(m_{1}+i\mathbb{Z},m_{2}+i\mathbb{Z})$ .
$\blacksquare$

Free layer $L_{f}$ : We also define the free layer by $L_{f}=\{\texttt{\textvisiblespace},0,1\}^{\mathbb{Z}^{2}}$ .

and we define $Y_{\alpha}$ as (see Figure 5 for an illustration):

	$\displaystyle Y_{\alpha}$	$\displaystyle=\Big{\{}(y^{(1)\uparrow},y^{(2)\uparrow},y^{(d)\uparrow},y^{(m)}% ,y^{(f)})\in{L_{1}^{\uparrow}}\times{\left\langle\infty\right\rangle^{\uparrow% }}\times{L_{d}^{\uparrow}}\times L_{m}\times L_{f}\mid$
		$\displaystyle\hskip 56.9055pt\forall i\in\mathbb{N},(\exists k_{1}\in\mathbb{N% },\ y^{(1)}=\left\langle i\right\rangle_{k_{1}}\iff\exists m_{1},m_{2}\in% \mathbb{N},\ y^{(m)}=\left[2i\right]_{m_{1},m_{2}})\Big{\}}$
		$\displaystyle\hskip 5.69046pt\cup\bigcup_{i\in\mathbb{N}}\bigcup_{j\geq i}\Big% {\{}(y^{(1)\uparrow},y^{(2)\uparrow},y^{(d)\uparrow},y^{(m)},y^{(f)})\in{L_{1}% ^{\uparrow}}\times{L_{2}^{\uparrow}}\times{L_{d}^{\uparrow}}\times L_{m}\times L% _{f}\mid\exists k_{1},m_{1},m_{2},k_{2}\in\mathbb{N},$
		$\displaystyle\hskip 56.9055pty^{(1)}=\left\langle i\right\rangle_{k_{1}},\,y^{% (m)}=\left[2i\right]_{m_{1},m_{2}},\,y^{(2)}=\left\langle j\right\rangle_{k_{2% }},\,\pi_{\mathrm{sync}}(y^{(f)})=y^{(d)\uparrow},$
		$\displaystyle\hskip 56.9055pt\exists\beta\leq\alpha_{i,j},\,y^{(d)}=T(\beta,i)% _{k_{1}}\,\text{and }y^{(f)}\|_{(m_{1}+i\mathbb{Z})\times(m_{2}+i\mathbb{Z})}% \text{ is constant}\Big{\}}.$

Figure 5: Projection of a proper configuration on

{L_{1}^{\uparrow}}\times L_{m}\times L_{f}

. The symbols

{\color[rgb]{0.4,0.4,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{0.4,0.4,0.4}% \pgfsys@color@gray@stroke{0.4}\pgfsys@color@gray@fill{0.4}\ast}

are on

{L_{1}^{\uparrow}}

, the symbols

{\color[rgb]{1,0.7,0.7}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.7,0.7}\blacksquare}

on

L_{m}

the symbols

1

on

L_{f}

. All the other bits of

L_{f}

(not drawn here) are free.

Extending the terminology from $Z_{\alpha}$ to $Y_{\alpha}$ , we call proper the configurations of $Y_{\alpha}$ that encode integers $i\in\mathbb{N}$ and $j\geq i$ on their first two layers, and degenerate those which do not. Additionally we say that a pattern is proper if it can be extended into a proper configuration, and degenerate otherwise. We say that two proper patterns $u,v\in\mathcal{L}_{n}(Y_{\alpha})$ are similar if they are equal on their first four layers (i.e. $\pi_{{L_{1}^{\uparrow}}\times{L_{2}^{\uparrow}}\times{L_{d}^{\uparrow}}\times L% _{m}}(u)=\pi_{{L_{1}^{\uparrow}}\times{L_{2}^{\uparrow}}\times{L_{d}^{\uparrow% }}\times L_{m}}(v)$ ).

Claim 22.

Two similar proper patterns $u,v\in\mathcal{L}_{n}(Y_{\alpha})$ have distinct extender sets if and only if there exists a proper configuration $y$ that extends $u$ and that marks a position $p\in\llbracket 0,n-1\rrbracket^{2}$ such that $u^{(f)}_{p}\neq v^{(f)}_{p}$ .

We would very much like an analog of Claim 20: unfortunately, not all proper patterns generate distinct extender sets. Indeed, by the previous claim, similar proper patterns generate distinct extender sets only when the positions at which they differ can be marked by an extending configuration (this depends on the relative position of an $n\times n$ window covering the four quadrants of a $2i\times 2i$ square, etc…). Yet, we do not need precise considerations to count the number of extender sets, and simply prove the following bounds:

Lemma 23.

Let $P_{E}(n)=\{E_{Y_{\alpha}}(w)\in\mathcal{L}_{n}(Y_{\alpha})\mid w\text{ is % proper}\}$ . Then

2^{\alpha_{n}\cdot n^{2}+O(n)}\leq P_{E}(n)\leq\mathrm{poly}(n)\cdot\sum_{i=0}% ^{n}2^{\alpha_{i}\cdot i^{2}+O(i)}.

Proof: lower bound..

For $j\geq n$ , consider the set $J_{j}=\{(y\in Y_{\alpha}\mid y^{(1)}=\left\langle n\right\rangle_{0},y^{(2)}=% \left\langle j\right\rangle_{0},y^{(d)}=T(\alpha_{n,j},n)\}$ . The number of symbols $1$ in an $(n\times n)$ -period in the density layer of such configurations is $\alpha_{n,j}\cdot n^{2}+O(n)$ by Claim 13. Since $\alpha_{n,j}\to\alpha_{n}$ , by taking $j\geq n$ large enough we obtain a set $J=J_{j}$ of proper configurations $y$ whose density layer $y^{(d)}$ contains $\alpha_{n}\cdot n^{2}+O(n)$ symbols $1$ in an $(n\times n)$ -period.

Considering the free layer of such patterns, there are at least $2^{\alpha_{n}\cdot n^{2}+O(n)}$ distinct patterns in the finite set $W=\{y|_{\llbracket 0,n-1\rrbracket^{2}}\mid y\in J_{j}\text{ and }y^{(m)}|_{% \llbracket 0,n-1\rrbracket^{2}}=\square^{\llbracket 0,n-1\rrbracket^{2}}\}$ , and we claim that they all generate distinct extender sets. Indeed, for any two distinct patterns $u,v\in W$ , there exists a position $p\in\llbracket 0,n-1\rrbracket^{2}$ such that $u^{(f)}_{p}\neq v^{(f)}_{p}$ ; and there exists a configuration $y\in J_{j}$ that extends $u$ with $y^{(m)}=\left[2n\right]_{p+(n,n)}$ : in particular, $y$ marks the position $p$ .⁵⁵5Markers were chosen to be $(2i,2i)$ -periodic for this reason: we need to be able to mark a position $p\in\llbracket 0,i-1\rrbracket^{2}$ in a configuration without seeing a marker in the square $\llbracket 0,i-1\rrbracket^{2}$ . By Claim 22, we obtain $E_{Y_{\alpha}}(u)\neq E_{Y_{\alpha}}(v)$ . This proves that $P_{E}(n)\geq 2^{\alpha_{n}\cdot n^{2}+O(n)}$ . $\hfill\blacktriangleleft$

Proof: upper bound..

We proceed as with the $\mathbb{Z}$ effective subshift $Z_{\alpha}$ : to bound the cardinality of $P_{E}(n)$ , we consider the restrictions $w=y|_{\llbracket 0,n-1\rrbracket^{2}}$ for $y$ ranging in the proper configurations of $Y_{\alpha}$ (for all values of $\left\langle i\right\rangle_{k_{1}}$ , $\left\langle j\right\rangle_{k_{2}}$ , $T(\beta,i)$ and $\left[2i\right]_{m_{1},m_{2}})$ , and count free layers by Claim 18:

$\blacksquare$

If $i\leq n$ , an $i\times i$ square of the density layer $w^{(d)}$ contains less than $\alpha_{i}\cdot i^{2}+O(i)$ symbols $1$ .
$\blacksquare$

If $i>n$ , the density layer $w^{(d)}$ contains less than $\alpha_{n}\cdot n^{2}+O(n)$ symbols $1$ .

Finally, when summing over all these cases, we overestimate the number of extender sets generated by the free layer by assuming that each position $p\in\llbracket 0,i-1\rrbracket^{2}$ containing a symbol $1$ on the density layer can be marked by a proper configuration $y$ extending the pattern (while only a subset of such positions can be marked):

	$\displaystyle P_{E}(n)$	$\displaystyle\leq\sum_{i=1}^{n}\sum_{k_{1}=0}^{i-1}\sum_{j=1}^{n}\sum_{k_{2}=0% }^{j-1}O(i^{4})\cdot 2^{\alpha_{i}\cdot i^{2}+O(i)}+\sum_{k_{1}=0}^{n}\sum_{k_% {2}=0}^{n}O(n^{4})\cdot 2^{\alpha_{n}\cdot n^{2}+O(n)}$
		$\displaystyle\leq\mathrm{poly}(n)\cdot\sum_{i=1}^{n}2^{\alpha_{i}\cdot i^{2}+O% (i)}.\$

$\hfill\blacktriangleleft$

By taking the limit $\alpha=\lim_{n}\alpha_{n}$ , we obtain that $h_{E}(Y_{\alpha})=\alpha$ . Thus, we are left to prove:

Claim 24.

The subshift $Y_{\alpha}$ is a sofic subshift.

This proof is very standard and unsurprising, yet is included for the sake of exhaustiveness.

Sketch of proof.

First, we introduce a grid subshift. Let us denote by $Y_{\mathrm{grid}}$ the subshift on the alphabet $\{\leavevmode\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 2.96063pt\hbox{% {\leavevmode\includegraphics{}{}{dagpub-tikzpictures/p021-Callard.latexml-% figure4.pdf}}}},\leavevmode\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\hbox{\lower 2.760% 64pt\hbox{{\leavevmode\includegraphics{}{}{dagpub-tikzpictures/p021-Callard.la% texml-figure5.pdf}}}},\leavevmode\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate\hbox{% \lower 2.96063pt\hbox{{\leavevmode\includegraphics{}{}{dagpub-tikzpictures/p02% 1-Callard.latexml-figure6.pdf}}}}\}$ defined as the closure of all the square grid configurations (see Figure 6(a)). It is a sofic subshift: by enforcing the continuity of black lines between adjacent positions, we obtain an irregular grid; to obtain a regular square grid, we make each cross send diagonals in the SFT cover (since diagonals can only go through a cross, the grid becomes regular).

(a) A square grid configuration of mesh

i\times i

.

(b) Vertical blue columns of symbols

\ast

are

i

-periodic, the square grid has mesh

i\times i

.

Figure 6: Two configurations using grids.

Let us now synchronize $Y_{\mathrm{grid}}$ with ${L_{1}^{\uparrow}}$ : we define $Y_{\mathrm{grid}\ast}\subseteq{L_{1}^{\uparrow}}\times Y_{\mathrm{grid}}$ the set of configurations $(x^{(1)\uparrow},x^{(g)})$ such that $x^{(g)}$ has mesh $i\times i$ if and only if $x^{(1)}$ encodes some $i\in\mathbb{N}$ (see Figure 6(b)).

Claim 25.

$Y_{\mathrm{grid}\ast}$ is a $\mathbb{Z}^{2}$ sofic subshift.

Sketch of proof..

Using areas of colors in the SFT cover, ensure that exactly one black vertical line in $Y_{\mathrm{grid}}$ can appear between two vertical lines of symbols $\ast$ in ${L_{1}^{\uparrow}}$ . $\hfill\vartriangleleft$

Let us now prove that $Y_{\alpha}$ is a $\mathbb{Z}^{2}$ sofic subshift. Intuitively, it follows from Theorem 2: $Y_{\alpha}$ is a “decorated version” of ${Z_{\alpha}^{\prime\uparrow}}$ . The most tricky step is in the periodicity condition: periodicity of a free bit in $L^{(f)}$ should only be enforced whenever both layers $y^{(1)}$ and $y^{(2)}$ do not belong in ${\left\langle\infty\right\rangle^{\uparrow}}$ , i.e. whenever they both actually encode some integers $i\in\mathbb{N}$ and $j\in\mathbb{N}$ .

To proceed, we slightly alter the $\mathbb{Z}$ subshift $Z_{\alpha}^{\prime}$ to define a new subshift $Z_{\alpha}^{\prime\prime}$ : it contains an additional layer $L_{p}$ (the proper layer) that can take two values (either $\mathsf{p}^{\mathbb{Z}}$ or $\mathsf{d}^{\mathbb{Z}}$ ), and is forced to be $\mathsf{p}^{\mathbb{Z}}$ whenever both the first and second layer do encode integers:

	$\displaystyle Z_{\alpha}^{\prime\prime}$	$\displaystyle=\Big{\{}(z^{(1)},z^{(2)},z^{(d)},z^{(p)})\in L_{1}\times L_{2}% \times L_{d}\times\{\mathsf{p}^{\mathbb{Z}},\mathsf{d}^{\mathbb{Z}}\}\mid z^{(% 2)}\in\left\langle\infty\right\rangle\Big{\}}$
		$\displaystyle\hskip 5.69046pt\cup\bigcup_{i\in\mathbb{N}}\bigcup_{j\geq i}\Big% {\{}(z^{(1)},z^{(2)},z^{(d)},z^{(p)})\in L_{1}\times L_{2}\times L_{d}\times\{% \mathsf{p}^{\mathbb{Z}}\}\mid\exists k_{1},k_{2}\in\mathbb{N},$
		$\displaystyle\hskip 85.35826ptz^{(1)}=\left\langle i\right\rangle_{k_{1}},\,z^% {(2)}=\left\langle j\right\rangle_{k_{2}}\,\text{and }\exists\beta\leq\alpha_{% i,j},\,z^{(d)}=T(\beta,i)_{k_{1}}\Big{\}}.$

By a slight alteration of Claim 15, the subshift $Z_{\alpha}^{\prime\prime}$ is effective whenever $\alpha$ is a $\Pi_{3}$ real number. By Theorem 2, the $\mathbb{Z}^{2}$ subshift ${Z_{\alpha}^{\prime\prime\uparrow}}$ is thus sofic. Then, we use the proper layer to enforce periodicity of a free bit in $L^{(f)}$ only whenever $y^{(p)}=\mathsf{p}^{Z^{2}}$ , and define $Y_{\alpha}^{\prime}$ as:

	$\displaystyle Y_{\alpha}^{\prime}$	$\displaystyle=\Big{\{}(y^{(1)\uparrow},y^{(2)\uparrow},y^{(d)\uparrow},y^{(p)% \uparrow},y^{(g)},y^{(f)})\in{Z_{\alpha}^{\prime\prime\uparrow}}\times Y_{% \mathrm{grid}}\times\{\texttt{\textvisiblespace},0,1\}^{\mathbb{Z}^{2}}\mid$
		$\displaystyle\hskip 42.67912pt(y^{(1)\uparrow},y^{(g)})\in Y_{\mathrm{grid}% \ast},\quad\pi_{\mathrm{sync}}(y^{(f)})=y^{(d)\uparrow},$
		$\displaystyle\hskip 42.67912pt\exists b\in\{\texttt{\textvisiblespace},0,1\},% \forall p\in\mathbb{Z}^{2},\ y^{(p)}=\mathsf{p}^{\mathbb{Z}}\wedge\,y^{(g)}_{p% }=\leavevmode\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 2.96063pt\hbox{% {\leavevmode\includegraphics{}{}{dagpub-tikzpictures/p021-Callard.latexml-% figure8.pdf}}}}\implies y^{(f)}_{p}=b\Big{\}}$

Claim 26.

$Y_{\alpha}^{\prime}$ is a $\mathbb{Z}^{2}$ sofic subshift.

Sketch of proof..

By the previous paragraph, the first four layers are sofic; and by Claim 25, the synchronization $Y_{\mathrm{grid}\ast}$ of ${L_{1}^{\uparrow}}$ and $Y_{\mathrm{grid}}$ is sofic. To make a free bit periodic, one can carry a unique symbol $b_{\mathrm{grid}}\in\{\texttt{\textvisiblespace},0,1\}$ along the black lines of $Y_{\mathrm{grid}}$ in an SFT cover, and enforce the following: on positions at which a cross symbol appears on the grid layer $y^{(g)}$ , and a symbol $\mathsf{p}$ appears on the proper layer $y^{(p)\uparrow}$ , the free bit in $y^{(f)}$ is then made equal to the symbol $b_{\mathrm{grid}}$ . $\hfill\vartriangleleft$

We can now prove that $Y_{\alpha}$ is sofic. Indeed, fix an SFT cover of $Y_{\alpha}^{\prime}$ in which we color cross symbols into two colors alternatingly: let us say, red and blue. On each horizontal and vertical line of the grid layer $Y_{\mathrm{grid}}$ , crosses are now alternating between red and blue. We claim that we obtain the subshift $Y_{\alpha}$ by projecting this SFT cover as follows:

$\blacksquare$

Erase the proper layer.
$\blacksquare$

Projection of the grid layer: red crosses become ${\color[rgb]{1,0.7,0.7}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.7,0.7}\blacksquare}$ , and all other symbols become $\square$ .

Indeed, projecting the grid layer as mentioned creates the marker layer $L_{m}$ . The only condition that remains to be checked is the $(i,i)$ -periodicity condition on a free bit.

Notice that in $Y_{\alpha}^{\prime}$ , both cases $y^{(p)\uparrow}=\mathsf{p}^{\mathbb{Z}^{2}}$ and $y^{(p)\uparrow}=\mathsf{d}^{\mathbb{Z}^{2}}$ are possible whenever $y^{(1)}\in\left\langle\infty\right\rangle$ or $y^{(2)}\in\left\langle\infty\right\rangle$ , so that erasing the proper layer in the projection merges the two cases together and removes the periodicity enforced a free bit of $y^{(f)}$ ; while whenever $y^{(1)}=\left\langle i\right\rangle_{k_{1}}$ and $y^{(2)}=\left\langle j\right\rangle_{k_{2}}$ , only the case $y^{(p)}=\mathsf{p}^{\mathbb{Z}^{2}}$ is allowed: so that, when projecting, the periodicity condition is still enforced. $\hfill\vartriangleleft$

7 Realizing Extender Entropies: Computable Subshifts

A subshift $X$ is said to be computable if its language $\mathcal{L}(X)$ is decidable. Following the proofs from Section 4, one proves that extender entropies of computable subshifts are $\Pi_{2}$ real numbers. We prove the converse inclusion and obtain:

Theorem 27.

The set of extender entropies of computable $\mathbb{Z}$ effective subshifts (resp. computable $\mathbb{Z}^{2}$ sofic subshifts) is exactly $\Pi_{2}\cap[0,+\infty)$ .

Sketch of proof.

We slightly alter our previous constructions. The subshift $Z_{\alpha}^{\prime}$ constructed in A might not be computable whenever $\alpha\in\Pi_{3}$ , since, given some $i,j\in\mathbb{N}$ and some factor of $T(\beta,i)$ , it might be undecidable to know whether $\beta\leq\alpha_{i,j}$ when $\alpha_{i,j}\in\Pi_{1}$ .

Yet, when taking $\alpha=\inf_{i}\alpha_{i}=\inf_{i}\sup_{j}\alpha_{i,j}\in\Pi_{2}$ for $(\alpha_{i,j})$ a computable sequence, the previous problem becomes decidable; thus, the subshift $Z_{\alpha}^{\prime}$ is computable. Both proofs, on $\mathbb{Z}$ and $\mathbb{Z}^{2}$ , then go through without any other modification. $\hfill\blacktriangleleft$

8 Extender Sets of Minimal Subshifts

Minimality is a general dynamical notion; in our context, a subshift is minimal if it contains no nonempty proper subshift. Extender sets are much easier in minimal subshifts and do not even depend on the computability of the language:

Proposition 28.

Let $X$ be a minimal subshift over $\mathbb{Z}^{d}$ . Then for any $n>0$ and any patterns $u,v\in\mathcal{L}_{n}(X)$ , $E_{X}(u)\subseteq E_{X}(v)\iff u=v$ .

Proof.

Let $u,v\in\mathcal{L}_{n}(X)$ and suppose that $E_{X}(u)\subseteq E_{X}(v)$ . Then any appearance of $u$ in a configuration can be replaced by $v$ : by iterating the process while ordering patterns lexicographically (see [23, Lemma 2.2] for the complete argument), we obtain by compactness a configuration of $X$ is which $u$ does not appear, which contradicts minimality. $\hfill\blacktriangleleft$

This implies that $h_{E}(X)=h(X)$ if $X$ is minimal. Since minimal sofic subshifts have zero entropy (folklore, see [11, Proposition 6.1]), and minimal effective subshifts have arbitrary $\Pi_{1}$ entropy (consider [16, Theorem 4.77] with computable sequences $(k_{n})_{n\in\mathbb{N}}$ ), we obtain:

Corollary 29.

The extender entropy of a minimal $\mathbb{Z}^{d}$ sofic subshift is always $0$ .

Corollary 30.

The set of extender entropies of minimal $\mathbb{Z}^{d}$ effective subshifts is exactly $\Pi_{1}\cap[0,+\infty)$ .

9 Extender Sets of Subshifts With Mixing Properties

9.1 Mixing $\mathbb{Z}$ Subshifts

Mixingness is another dynamical notion. In the context of $\mathbb{Z}$ subshifts, mixingness intuitively implies that for any pair of admissible words, there exists a configuration containing both of them at arbitrary positions, provided they are sufficiently far apart:

Definition 31 (Mixing subshift).

A $\mathbb{Z}$ subshift $X$ is mixing if

\forall n>0,\exists N>0,\forall u,v\in\mathcal{L}_{n}(X),\forall k\geq N,% \exists w\in\mathcal{L}_{k}(X),\,uwv\in\mathcal{L}(X).

We say that $X$ is $f(n)$ -mixing for some function $f$ if $N$ can be taken equal to $f(n)$ in the previous definition. When $f$ is constant $f(n)=N$ , we simply write that $X$ is $N$ -mixing.

One could expect that strong mixing conditions would restrict the behaviors of extender sets: indeed, all the examples we mentioned so far either have strong mixing properties (the full shift, $\mathbb{Z}$ SFTs…) and zero extender entropy, or have positive extender entropy but are far from mixing (periodicity, reflected positions, …). However, we show in this section that even very restrictive mixing properties do not imply anything on extender entropies.

Proposition 32.

Let $X$ be a one-dimensional subshift. There exists a $1$ -mixing subshift $X_{\#}$ with $h_{E}(X)=h_{E}(X_{\#})$ . (Furthermore, if $X$ was effective, then $X_{\#}$ can be taken effective.)

Proof.

Let $X\subseteq\mathcal{A}^{\mathbb{Z}}$ be a subshift, and $\alpha=h_{E}(X)$ . Denote $\mathcal{F}=\mathcal{A}^{*}\setminus\mathcal{L}(X)$ . Let us define a subshift $X_{\#}$ over the alphabet $\mathcal{A}\sqcup\{\#\}$ (assuming that $\#$ is a free symbol not in $\mathcal{A})$ by the same family of forbidden patterns $\mathcal{F}$ : configurations of $X_{\#}$ are composed of (possibly infinite) words of $\mathcal{L}(X)$ separated by the safe symbol $\#$ . Then $X_{\#}$ is $1$ -mixing, as for any $u,v\in\mathcal{L}(Y)$ , we have $u\#v\in\mathcal{L}(Y)$ .

We are left with proving that $h_{E}(X_{\#})=h_{E}(X)$ . First, we need to introduce the notion of follower and predecessor sets: in $X$ , the follower and predecessor sets are respectively defined as $F_{X}(w)=\{x\in\mathcal{A}^{\mathbb{N}}\mid wx\sqsubseteq X\}$ and $P_{X}(w)=\{x\in\mathcal{A}^{-\mathbb{N}}\mid xw\sqsubseteq X\}$ . In other words, the follower set (resp. predecessor set) of some word $w$ correspond to the set of right-infinite (resp. left-infinite) sequences $x$ such that $u x$ (resp. $x u$ ) appears in some configuration of $X$ .

Let $n\geq 0$ . We prove that:

\lvert E_{X}(n)\rvert\leq\lvert E_{X_{\#}}(n)\rvert\leq\lvert E_{X}(n)\rvert+% \sum_{i+j<n}\lvert P_{X}(i)\rvert\lvert F_{X}(j)\rvert

Lower bound.

The lower bound holds simply because if $x$ extends a pattern $w\in\mathcal{L}(X)$ but not $w^{\prime}\in\mathcal{L}(X)$ , then $x$ also belongs in $X_{\#}$ and still extends $w$ but not $w^{\prime}$ in $X_{\#}$ , so that $E_{X_{\#}}(w)\neq E_{X_{\#}}(w^{\prime})$ . $\hfill\blacktriangleleft$

Upper bound.

For the rightmost inequality, we need to distinguish some cases according to whether a pattern contains a $\#$ or not.

$\blacksquare$

Let $w\in\mathcal{L}_{n}(X_{\#})$ that does not contain a symbol $\#$ . Then

$E_{X_{\#}}(w)=E_{X}(w)\cup\bigcup_{l,r\in\mathcal{A}^{*}\mid lwr\in\mathcal{L}% (X)}\{(x\,\#\,l,r\,\#\,x^{\prime})\mid x,x^{\prime}\text{ admissible in }X_{\#}\}$

So, for $w,w^{\prime}\in\mathcal{L}_{n}(X_{\#}).$ So, for $w,w^{\prime}\in\mathcal{L}_{n}(X_{\#})$ that do not contain a symbol $\#$ , we have $E_{X_{\#}}(w)=E_{X_{\#}}(w^{\prime})$ if and only if $E_{X}(w)=E_{X}(w^{\prime})$ .
$\blacksquare$

Let $w\in\mathcal{L}_{n}(X_{\#})$ containing at least a symbol $\#$ , and let $i\leq j$ be the first and last positions in $w$ at which a symbol $\#$ appear. Let $l,r\in\mathcal{A}^{*}$ be respectively $w_{\llbracket 0,i-1\rrbracket}$ and $w_{\llbracket j+1,n-1\rrbracket})$ . Since $\#$ is a safe symbol, $E_{X_{\#}}(w)$ is entirely determined by $(P_{X}(l),F_{X}(r))$ :

$\displaystyle E_{X_{\#}}(w)$ $\displaystyle=(P_{X}(l)\times F_{X}(r))\cup\bigcup_{\begin{subarray}{c}l^{% \prime},r^{\prime}\in\mathcal{A}^{*}\mid\\ l^{\prime}\cdot l,\ r\cdot r^{\prime}\in\mathcal{L}(X)\end{subarray}}\{(y\,\#% \,l^{\prime},r^{\prime}\#\,y^{\prime})\mid y,y^{\prime}\text{ admissible in }X% _{\#}\}.$

Doing a disjunction on these two cases, and over the pairs $i+j<n$ in the second case (and abusing notations again by denoting $P_{X}(i)=\{P_{X}(w)\mid w\in\mathcal{L}_{i}(X)\}$ and $F_{X}(j)=\{F_{X}(w)\mid w\in\mathcal{L}_{j}(X)$ ) we obtain:

\lvert E_{X_{\#}}(n)\rvert\leq\lvert E_{X}(n)\rvert+\sum_{i+j<n}\lvert P_{X}(i% )\rvert\lvert F_{X}(j)\rvert\

$\hfill\blacktriangleleft$

As $\lvert P_{X}(n)\rvert\leq\lvert E_{X}{(n)}\rvert$ and $\lvert F_{X}(n)\rvert\leq\lvert E_{X}(n)\rvert$ , and that $\lvert E_{X}(n)\rvert=2^{\alpha n+o(n)}$ , we obtain $2^{\alpha_{n}n+o(n)}\leq\lvert E_{X_{\#}}(n)\rvert\leq\mathrm{poly}(n)\cdot 2^% {\alpha_{n}n+o(n)}$ , and conclude that $h_{E}(X_{\#})=\alpha$ . $\hfill\blacktriangleleft$

9.2 Block-gluing $\mathbb{Z}^{d}$ Subshifts

There exists various mixing notions in higher dimension. We formulate our results for block-gluing subshifts:

Definition 33.

Let $X\subseteq\mathcal{A}^{\mathbb{Z}^{d}}$ be a subshift, and $f\colon\mathbb{N}\to\mathbb{N}$ be a (weakly) increasing function. We say that $X$ is $f$ -block-gluing if

\forall p,q\in\mathcal{L}_{n}(X),\forall k\geq n+f(n),\forall u\in\mathbb{Z}^{% d},\left\lVert u\right\rVert_{\infty}\geq k\implies(p\cup\sigma^{u}(q)\in% \mathcal{L}(X))

Said differently, $X$ is $f$ -block-gluing if any two square patterns of size $n$ can appear at any position as long as they are placed with a gap of size at least $f(n)$ between them. As with Definition 31, we will simply write $N$ -block-gluing for constant gluing distance $(f\colon n\to N)$ .

Proposition 34.

For any $\alpha\in\Pi_{3}\cap[0,+\infty)$ , there exists an effective and $1$ -block-gluing $\mathbb{Z}^{d}$ subshift $Z_{\alpha,\#}$ such that $h_{E}(Z_{\alpha,\#})=\alpha$ .

Proof.

Notice that the free lift of a $1$ -block-gluing $\mathbb{Z}^{d}$ subshift to $\mathbb{Z}^{d+1}$ is also $1$ -block-gluing. By Claim 8, the free lift preserves the extender entropy: thus, we reduce to the one-dimensional case. We conclude by combining the previous Proposition 32 with A. $\hfill\blacktriangleleft$

References

[1] Nathalie Aubrun, Sebastián Barbieri, and Emmanuel Jeandel. About the Domino Problem for Subshifts on Groups, pages 331–389. Springer International Publishing, Cham, 2018. doi:10.1007/978-3-319-69152-7_9.
[2] Nathalie Aubrun and Mathieu Sablik. Simulation of effective subshifts by two-dimensional subshifts of finite type. Acta applicandae mathematicae, 126:35–63, 2013. doi:10.1007/s10440-013-9808-5.
[3] Sebastián Barbieri, Mathieu Sablik, and Ville Salo. Soficity of free extensions of effective subshifts. Discrete and Continuous Dynamical Systems, 45(4):1117–1149, 2025. doi:10.3934/dcds.2024125.
[4] Jérôme Buzzi. Subshifts of quasi-finite type. Inventiones mathematicae, 2003. doi:10.1007/s00222-004-0392-1.
[5] Silvio Capobianco. Multidimensional cellular automata and generalization of Fekete’s lemma. Discrete Mathematics & Theoretical Computer Science (DMTCS), 10(3):95–104, 2008. doi:10.46298/dmtcs.442.
[6] Julien Destombes. Algorithmic Complexity and Soficness of Shifts in Dimension Two. PhD thesis, Université de Montpellier, 2023. arXiv:2309.12241, doi:10.48550/arXiv.2309.12241.
[7] Julien Destombes and Andrei Romashchenko. Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts. Journal of Computer and System Sciences, 128:107–134, 2022. doi:10.1016/j.jcss.2022.04.002.
[8] Bruno Durand, Andrei Romashchenko, and Alexander Shen. Fixed-point tile sets and their applications. Journal of Computer and System Sciences, 78(3):731–764, 2012. doi:10.1016/j.jcss.2011.11.001.
[9] Thomas French. Characterizing follower and extender set sequences. Dynamical Systems, 31(3):293–310, 2016. doi:10.1080/14689367.2015.1111865.
[10] Thomas French and Ronnie Pavlov. Follower, predecessor, and extender entropies. Monatshefte für Mathematik, 188:495–510, 2019. doi:10.1007/s00605-018-1224-5.
[11] Silvère Gangloff. Algorithmic complexity of growth-type invariants of SFT under dynamical constraints. PhD thesis, Aix-Marseille Université, 2018. URL: http://www.theses.fr/2018AIXM0231/document.
[12] Pierre Guillon and Emmanuel Jeandel. Infinite communication complexity, 2015. arXiv:1501.05814.
[13] Michael Hochman. On the dynamics and recursive properties of multidimensional symbolic systems. Inventiones Mathematicae, 176(1):2009, April 2009. doi:10.1007/s00222-008-0161-7.
[14] Michael Hochman and Tom Meyerovitch. A characterization of the entropies of multidimensional shifts of finite type. Annals of Mathematics, 171(3):2011–2038, 2010. doi:10.4007/annals.2010.171.2011.
[15] Steve Kass and Kathleen Madden. A sufficient condition for non-soficness of higher-dimensional subshifts. Proceedings of the American Mathematical Society, 141(11):3803–3816, 2013. doi:10.1090/S0002-9939-2013-11646-1.
[16] Petr Kůrka. Topological and Symbolic Dynamics. Société mathématique de France, 2003.
[17] Douglas Lind and Brian Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge university press, 2021.
[18] Tom Meyerovitch. Growth-type invariants for $\mathbb{Z}^{d}$ subshifts of finite type and arithmetical classes of real numbers. Inventiones Mathematicae, 184(3), 2010. doi:10.1007/s00222-010-0296-1.
[19] Harold Marston Morse and Gustav Arnold Hedlund. Symbolic Dynamics. American Journal of Mathematics, 60(4):815–866, October 1938. doi:10.2307/2371264.
[20] Shahar Mozes. Tilings, substitution systems and dynamical systems generated by them. Journal d’Analyse Mathématique, 53(1):139–186, 1989. doi:10.1007/bf02793412.
[21] Nic Ormes and Ronnie Pavlov. Extender sets and multidimensional subshifts. Ergodic Theory and Dynamical Systems, 36(3):908–923, 2016. doi:10.1017/etds.2014.71.
[22] Ronnie Pavlov. A class of nonsofic multidimensional shift spaces. Proceedings of the American Mathematical Society, 141(3):987–996, 2013. doi:10.1090/S0002-9939-2012-11382-6.
[23] Anthony N. Quas and Paul B. Trow. Subshifts of multi-dimensional shifts of finite type. Ergodic Theory and Dynamical Systems, 20(3):859–874, 2000. doi:10.1017/S0143385700000468.
[24] Robert I Soare. Turing computability: Theory and applications, volume 300. Springer, 2016. doi:10.1007/978-3-642-31933-4.
[25] Hao Wang. Proving theorems by Pattern Recognition II. Bell Systems technical journal, 40:1–41, 1961. doi:10.1002/j.1538-7305.1961.tb03975.x.
[26] Benjamin Weiss. Subshifts of finite type and sofic systems. Monatshefte für Mathematik, 77:462–474, 1973. doi:10.1007/BF01295322.
[27] Xizhong Zheng and Klaus Weihrauch. The arithmetical hierarchy of real numbers. Mathematical Logic Quarterly: Mathematical Logic Quarterly, 47(1):51–65, 2001. doi:10.1002/1521-3870(200101)47:1<51::AID-MALQ51>3.0.CO;2-W.

[bib.bib1] [1] Nathalie Aubrun, Sebastián Barbieri, and Emmanuel Jeandel. About the Domino Problem for Subshifts on Groups, pages 331–389. Springer International Publishing, Cham, 2018. doi:10.1007/978-3-319-69152-7_9.

[bib.bib2] [2] Nathalie Aubrun and Mathieu Sablik. Simulation of effective subshifts by two-dimensional subshifts of finite type. Acta applicandae mathematicae, 126:35–63, 2013. doi:10.1007/s10440-013-9808-5.

[bib.bib3] [3] Sebastián Barbieri, Mathieu Sablik, and Ville Salo. Soficity of free extensions of effective subshifts. Discrete and Continuous Dynamical Systems, 45(4):1117–1149, 2025. doi:10.3934/dcds.2024125.

[bib.bib4] [4] Jérôme Buzzi. Subshifts of quasi-finite type. Inventiones mathematicae, 2003. doi:10.1007/s00222-004-0392-1.

[bib.bib5] [5] Silvio Capobianco. Multidimensional cellular automata and generalization of Fekete’s lemma. Discrete Mathematics & Theoretical Computer Science (DMTCS), 10(3):95–104, 2008. doi:10.46298/dmtcs.442.

[bib.bib6] [6] Julien Destombes. Algorithmic Complexity and Soficness of Shifts in Dimension Two. PhD thesis, Université de Montpellier, 2023. arXiv:2309.12241, doi:10.48550/arXiv.2309.12241.

[bib.bib7] [7] Julien Destombes and Andrei Romashchenko. Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts. Journal of Computer and System Sciences, 128:107–134, 2022. doi:10.1016/j.jcss.2022.04.002.

[bib.bib8] [8] Bruno Durand, Andrei Romashchenko, and Alexander Shen. Fixed-point tile sets and their applications. Journal of Computer and System Sciences, 78(3):731–764, 2012. doi:10.1016/j.jcss.2011.11.001.

[bib.bib9] [9] Thomas French. Characterizing follower and extender set sequences. Dynamical Systems, 31(3):293–310, 2016. doi:10.1080/14689367.2015.1111865.

[bib.bib10] [10] Thomas French and Ronnie Pavlov. Follower, predecessor, and extender entropies. Monatshefte für Mathematik, 188:495–510, 2019. doi:10.1007/s00605-018-1224-5.

[bib.bib11] [11] Silvère Gangloff. Algorithmic complexity of growth-type invariants of SFT under dynamical constraints. PhD thesis, Aix-Marseille Université, 2018. URL: http://www.theses.fr/2018AIXM0231/document.

[bib.bib12] [12] Pierre Guillon and Emmanuel Jeandel. Infinite communication complexity, 2015. arXiv:1501.05814.

[bib.bib13] [13] Michael Hochman. On the dynamics and recursive properties of multidimensional symbolic systems. Inventiones Mathematicae, 176(1):2009, April 2009. doi:10.1007/s00222-008-0161-7.

[bib.bib14] [14] Michael Hochman and Tom Meyerovitch. A characterization of the entropies of multidimensional shifts of finite type. Annals of Mathematics, 171(3):2011–2038, 2010. doi:10.4007/annals.2010.171.2011.

[bib.bib15] [15] Steve Kass and Kathleen Madden. A sufficient condition for non-soficness of higher-dimensional subshifts. Proceedings of the American Mathematical Society, 141(11):3803–3816, 2013. doi:10.1090/S0002-9939-2013-11646-1.

[bib.bib16] [16] Petr Kůrka. Topological and Symbolic Dynamics. Société mathématique de France, 2003.

[bib.bib17] [17] Douglas Lind and Brian Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge university press, 2021.

[bib.bib18] [18] Tom Meyerovitch. Growth-type invariants for $\mathbb{Z}^{d}$ subshifts of finite type and arithmetical classes of real numbers. Inventiones Mathematicae, 184(3), 2010. doi:10.1007/s00222-010-0296-1.

[bib.bib19] [19] Harold Marston Morse and Gustav Arnold Hedlund. Symbolic Dynamics. American Journal of Mathematics, 60(4):815–866, October 1938. doi:10.2307/2371264.

[bib.bib20] [20] Shahar Mozes. Tilings, substitution systems and dynamical systems generated by them. Journal d’Analyse Mathématique, 53(1):139–186, 1989. doi:10.1007/bf02793412.

[bib.bib21] [21] Nic Ormes and Ronnie Pavlov. Extender sets and multidimensional subshifts. Ergodic Theory and Dynamical Systems, 36(3):908–923, 2016. doi:10.1017/etds.2014.71.

[bib.bib22] [22] Ronnie Pavlov. A class of nonsofic multidimensional shift spaces. Proceedings of the American Mathematical Society, 141(3):987–996, 2013. doi:10.1090/S0002-9939-2012-11382-6.

[bib.bib23] [23] Anthony N. Quas and Paul B. Trow. Subshifts of multi-dimensional shifts of finite type. Ergodic Theory and Dynamical Systems, 20(3):859–874, 2000. doi:10.1017/S0143385700000468.

[bib.bib24] [24] Robert I Soare. Turing computability: Theory and applications, volume 300. Springer, 2016. doi:10.1007/978-3-642-31933-4.

[bib.bib25] [25] Hao Wang. Proving theorems by Pattern Recognition II. Bell Systems technical journal, 40:1–41, 1961. doi:10.1002/j.1538-7305.1961.tb03975.x.

[bib.bib26] [26] Benjamin Weiss. Subshifts of finite type and sofic systems. Monatshefte für Mathematik, 77:462–474, 1973. doi:10.1007/BF01295322.

[bib.bib27] [27] Xizhong Zheng and Klaus Weihrauch. The arithmetical hierarchy of real numbers. Mathematical Logic Quarterly: Mathematical Logic Quarterly, 47(1):51–65, 2001. doi:10.1002/1521-3870(200101)47:1<51::AID-MALQ51>3.0.CO;2-W.

Computability of Extender Sets in Multidimensional Subshifts

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem A.

Theorem B.

2 Definitions

2.1 Subshifts

Definition 1 (Subshift).

Theorem 2 ([13], [2, Theorem 3.1], [8, Theorem 10]).

2.2 Pattern Complexity and Extender Sets

Definition 3 (Extender set).

Definition 4 ([10, Definition 2.17]).

Examples

Some Properties

Theorem 5 (From [10] on ℤ subshifts).

Proposition 6 ([15, Section 2]).

Sketch of proof.

Proposition 7 ([21, Lemma 3.4]).

2.3 Computability Notions

2.3.1 Arithmetical Hierarchy

2.3.2 Arithmetical Hierarchy of Real Numbers

3 Elementary Constructions on Extender Sets

The free lift

Claim 8.

Proof.

The (semi)-mirror construction

Claim 9.

Sketch of proof.

4 Decision Problems on Extender Sets

4.1 Inclusion of Extender Sets

Proposition 10.

Proof of inclusion.

Proof of 𝚷𝟐𝟎-hardness for ℤ subshifts.

4.2 Computing the Number of Extender Sets

Lemma 11.

4.3 Upper Computational Bounds on Extender Entropies

Corollary 12.

Proof.

5 𝚷𝟑 Extender Entropies for ℤ Effective Subshifts

5.1 Preliminary: Encoding Integers With Configurations ⟨𝒊⟩𝒌

5.2 Preliminary: Toeplitz Density in Periodic Configurations

Toeplitz density words

Claim 13.

Toeplitz density in periodic configurations

Claim 14.

Proof.

5.3 Construction: the Effective ℤ Subshift 𝒁𝜶

Auxiliary subshift 𝒁𝜶′

Claim 15.

Proof.

Claim 16.

Proof.

Claim 17.

Proof.

Claim 18.

Proof.

Free bits in the subshift 𝒁𝜶

Claim 19.

Proof.

Claim 20.

Lemma 21.

Proof: lower bound..

Proof: upper bound..

6 𝚷𝟑 Extender Entropies for ℤ𝟐 Sofic Subshifts

6.1 Preliminary: Marking Offsets With Configurations [𝟐⁢𝒊]𝒎𝟏,𝒎𝟐

6.2 Construction: the Sofic ℤ𝟐 Subshift 𝒀𝜶

Claim 22.

Lemma 23.

Proof: lower bound..

Proof: upper bound..

Theorem 5 (From [10] on $\mathbb{Z}$ subshifts).

Proof of $\Pi^{0}_{2}$ -hardness for $\mathbb{Z}$ subshifts.

5 $\Pi_{3}$ Extender Entropies for $\mathbb{Z}$ Effective Subshifts

5.1 Preliminary: Encoding Integers With Configurations $\left\langle i\right\rangle_{k}$

5.3 Construction: the Effective $\mathbb{Z}$ Subshift $Z_{\alpha}$

Auxiliary subshift $Z_{\alpha}^{\prime}$

Free bits in the subshift $Z_{\alpha}$

6 $\Pi_{3}$ Extender Entropies for $\mathbb{Z}^{2}$ Sofic Subshifts

6.1 Preliminary: Marking Offsets With Configurations $\left[2i\right]_{m_{1},m_{2}}$

6.2 Construction: the Sofic $\mathbb{Z}^{2}$ Subshift $Y_{\alpha}$

9.1 Mixing $\mathbb{Z}$ Subshifts

9.2 Block-gluing $\mathbb{Z}^{d}$ Subshifts