Proof. For each $f\in \mathcal {K}$ , there exists n such that X differs from $\mathrm {im}(f)$ on $[0,n]$ . The operator $f\mapsto \mathrm {im}(f)$ is continuous, so for all $g\in \mathcal {K}$ in a neighbourhood of f, X differs from $\mathrm {im}(g)$ on $[0,n]$ . As $\mathcal {K}$ is compact, $\mathcal {K}$ is covered by finitely many such neighbourhoods. Let N be the maximal n associated with these neighbourhoods. For every $f\in \mathcal {K}$ , X differs from $\mathrm {im}(f)$ on $[0,N]$ .

Proof. Assume X is not the image of any function in $\mathcal {C}$ . Assume for a contradiction that $X=\bigcup _{j\in \mathbb {N}} X_j$ , where each $X_j$ is the image of a function $f_j\in \mathcal {C}$ . By the Baire category theorem (Theorem A.4), there exist $j,k\in \mathbb {N}$ and a finite valid pattern $\pi $ on $Q_k$ such that $X_j\cap [\pi ]=X\cap [\pi ]$ , that is, $X_j$ contains all the valid extensions of $\pi $ . Let i be such that $f_j\in \mathcal {K}_i$ . By Proposition 4.7, there exists n such that for every $g\in \mathcal {K}_i$ , X differs from $\mathrm {im}(g)$ on $Q_n$ . As X is weakly mixing, there exists $p\in \mathbb {Z}^2$ such that $Q_k$ and $p+Q_n$ are independent. In particular, for every valid $Q_n$ -pattern $\pi '$ , $\pi \cup \sigma ^p(\pi ')$ is valid. Any valid configuration extending $\pi \cup \sigma ^p(\pi ')$ extends $\pi $ so belongs to $X_j=\mathrm {im}(f_j)$ . By assumption about $\mathcal {C}$ , there exists $g\in \mathcal {K}_i$ such that $\mathrm {im}(g)=\mathrm {im}(\sigma ^{-p}\circ f_j)=\sigma ^{-p}(X_j)$ . Therefore, every valid $Q_n$ -pattern $\pi '$ has a valid extension in g; conversely, every configuration in $\mathrm {im}(g)=\sigma ^{-p}(X_j)$ belongs to X. It implies that X coincides with $\mathrm {im}(g)$ on $Q_n$ , which contradicts the choice of n.

Proof. If $X\in \mathscr {L}^0$ , then X is the image of $K\times Y$ with $Y=A^{\mathbb {Z}^d}\times \prod _{i=1}^kA^{\mathbb {Z}^d/H_i}$ under a factor map $f:K\times Y\to X$ . For each $k\in K$ , the function $f_k:Y\to X$ sending y to $f(k,y)$ is a local function of a certain radius r. The set $\mathcal {K}$ of local functions $g:Y\to \Sigma ^{\mathbb {Z}^d}$ of radius r is a compact class of functions. Moreover, if $g\in \mathcal {K}$ and $p\in \mathbb {Z}^d$ , then $\sigma ^p\circ g\circ \sigma ^{-p}\in \mathcal {K}$ and its image is $\mathrm {im}(\sigma ^p\circ g)$ . As X is weakly mixing and ${X=\bigcup _{k\in K}\mathrm {im}(f_k)}$ , we can apply Proposition 4.8, implying that X is the image of a single  $g\in \mathcal {K}$ .

Proof. Let $(p_n)_{n\in \mathbb {N}}$ be a one-to-one enumeration of $\mathbb {Z}^d$ . Let $\mathcal {K}$ be the set of functions $f:A^{\mathbb {N}}\to B^{\mathbb {Z}^d}$ such that for each n, $p_n$ is determined by a region of size r contained in $[0,r(n+1))$ . This class is compact and each function in $\mathcal {K}$ is r-narrow. Moreover, every r-narrow function f has the same image as some $g\in \mathcal {K}$ , obtained as follows. The idea is that we tighten the input positions as close to $0$ as possible. We first let $W=\bigcup _{p\in \mathbb {Z}^d}\mathcal {W}_f(p)$ and define an injective function $h:W\to \mathbb {N}$ . We start defining an injective function $h:\mathcal {W}_f(p_0)\to [0,r)$ , which is possible as $|\mathcal {W}_f(p_0)|\leq r$ . Inductively, assume that $h:\mathcal {W}_f(p_0)\cup \cdots \cup \mathcal {W}_f(p_n)\to [0,r(n+1))$ has been defined. We extend h by sending $\mathcal {W}_f(p_{n+1})\setminus (\mathcal {W}_f(p_0)\cup \cdots \cup \mathcal {W}_f(p_n))$ to $[r(n+1),r(n+2))$ in an injective way, which is possible as $|\mathcal {W}_f(p_{n+1})|\leq r$ .

Given $x\in A^{\mathbb {N}}$ , let $y\in A^{\mathbb {N}}$ be defined by $y(k)=x(h(k))$ and let $g(x)=f(y)$ . Note that $g(x)(p_n)$ is determined by the values of y on $\mathcal {W}_f(p)$ , that is, by the values of x on $h(\mathcal {W}_f(p_n))$ which has size at most r and is contained in $[0,r(n+1))$ , so g belongs to $\mathcal {K}$ . One has $\mathrm {im}(g)\subseteq \mathrm {im}(f)$ because each $g(x)$ is $f(y)$ for some y. Conversely, one has $\mathrm {im}(f)\subseteq \mathrm {im}(g)$ because for each y, define $x(k)=y(h^{-1}(k))$ if $k\in \mathrm {im}(h)$ and let $x(k)$ be an arbitrary symbol, otherwise, one has $g(x)=f(y)$ .

Proof of Proposition 4.11

By Lemma 4.12, the narrow functions can be arranged as a countable union of compact classes $\bigcup _{A,r}\mathcal {K}_{A,r}$ satisfying the assumptions of Proposition 4.8.

Proof. For each $r\geq 1$ , the cell $(0,0)$ and the column $\{(-r,k):0\leq k\leq r\}$ are not independent and their distance is r. Indeed, colouring the column in black forces the whole triangle $T_r=\{(x,y):-r\leq x\leq 0,0\leq y\leq r-x\}$ , and in particular the cell $(0,0)$ , to be black as well (see Figure 2).

Proof. We build ramifications illustrated in Figure 3. Let $r\in \mathbb {N}$ and $V_r=\{(n,1):n\geq r+2\}$ , which is an infinite set of pairwise independent vectors. Let $F=\{(0,0)\}$ and $u=(0,-1)$ . For each r and each $v\in V_r$ , we build an $(r,v)$ -ramification x by putting a black triangle $T_r$ at each multiple of v, everything else being white. Precisely, for each $\unicode{x3bb} \in \mathbb {Z}$ , the cells in $\unicode{x3bb} v+T_r$ are black, the other cells are white.

Figure 3

A ramification: the cells $\unicode{x3bb} v$ are in green, the cells $\unicode{x3bb} v+\mu u$ , $\mu>0$ , are in red. In a black triangle, the purple and green regions are correlated, and the content of a red cell cannot be grafted in a green cell without changing the purple region (green cells have horizontal hatches, purple cells have vertical hatches and red cells have diagonal hatches) (colour online).

First, x is a valid configuration because the copies of $T_r$ are separated by white cells, so they do not create forbidden patterns: if $\unicode{x3bb} \neq \unicode{x3bb} '$ and $s,t\in T_r$ , then $d(\unicode{x3bb} v+s,\unicode{x3bb} ' v+t)=|(\unicode{x3bb} -\unicode{x3bb} ')v+(s-t)|\geq |v|-\mathop {\mathrm {diam}}(T_r)\geq (r+2)-r=2$ , so two cells from different triangles cannot belong to the forbidden pattern, which has diameter $1$ .

For $\mu>0$ , $\mu u=(0,-\mu )\notin T_r$ so the cells $\unicode{x3bb} v+\mu u$ are white. The white cell, seen as an F-pattern, appears at position $\unicode{x3bb} v+\mu u$ but cannot be r-grafted in x at any position $\unicode{x3bb} v$ . We have shown that x is an $(r,v)$ -ramification and that X is ramified.

Proof. We show that there exist non-zero integers $n_0,\ldots ,n_k$ such that the pairwise differences of $n_iu_i$ are multiples of v. If $n_0<0$ , then we replace each $n_i$ by $-n_i$ . We then take $\mu =n_0$ and $\unicode{x3bb} _i$ such that $n_0u_0-n_iu_i=\unicode{x3bb} _i v$ .

First, consider the case when $k=1$ . As $\mathbb {Z}^2$ has rank $2$ as a $\mathbb {Z}$ -module, there is a non-trivial combination $n_0u_0-n_1u_1+nv=0$ . As v is independent of each $u_i$ individually, one has $n_0\neq 0$ and $n_1\neq 0$ , and the difference of $n_0u_0$ and $n_1u_1$ is a multiple of v.

Let us now consider the general case $k\geq 2$ . For each i from $1$ to k, the previous argument applied to $u_0$ and $u_i$ provides non-zero coefficients $n^i_0$ and $n^i_1$ such that $n^i_0u_0-n^i_1u_i$ is a multiple of v. Let $n_0=\prod _j n^j_0$ and $n_i=n^i_1\prod _{j\neq i}n^j_0$ . All these coefficients are non-zero and $n_0u_0-n_iu_i=(n^i_0u_0-n^i_1u_i)\prod _{j\neq i}n^j_0$ is a multiple of v.

Proof. A configuration $x\in X$ is $(x_0,\ldots ,x_k)$ with each $x_i\in X_i$ . Let A be the finite alphabet such that $X\subseteq A^{\mathbb {Z}^2}$ .

Let v be independent of each $u_i$ and x be a $(0,v)$ -ramification, with $u,F$ . We apply Lemma 5.9, giving $\unicode{x3bb} _1,\ldots ,\unicode{x3bb} _k$ and $\mu>0$ such that $\mu u-\unicode{x3bb} _iv$ is a multiple of $u_i$ . Let $\unicode{x3bb} _0~=~0$ , $L^+=\max _{0\leq i\leq k}\unicode{x3bb} _i$ , $L^-=\min _{0\leq i\leq k}\unicode{x3bb} _i$ and $L=L^+-L^-+1$ .

We define a colouring of $[0,N]$ , where $N=N(A^F,L)$ is given by Van der Waerden’s theorem (Theorem A.1). Assign to n the F-pattern $\pi _n\in A^F$ appearing at position $nv$ in x. By Van der Waerden’s theorem, this colouring admits a monochromatic arithmetic progression of length L, that is, there exist a and $b>0$ such that all $(a+\unicode{x3bb} b)$ have the same colour, $\unicode{x3bb} \in [L^-,L^+]$ . Let $\pi $ be the common F-pattern appearing at these positions $(a+\unicode{x3bb} b)v$ . In particular, if $p_i=(a+\unicode{x3bb} _i b)v$ and $q\in F$ , then

(5.1) $$ \begin{align} x(p_i+q)=\pi(q) \end{align} $$

does not depend on i.

Let $p=av+b\mu u$ and $\xi $ be the F-pattern appearing at position p in x. We claim that $\xi $ can be $0$ -grafted into x at position $p_0$ . In other words, if we define $x'\in A^E$ by

$$ \begin{align*} x'(p_0+q)=\begin{cases} \xi(q)=x(p+q)&\text{if }q\in F,\\ x(p_0+q)&\text{otherwise,} \end{cases} \end{align*} $$

then we show that $x'$ belongs to X. Note that $x^{\prime }_0\in X_0$ because $X_0$ is the fullshift. We claim that for $i\geq 1$ , one has $x^{\prime }_i=x_i\in X_i$ , from which it will follow that $x'\in X$ .

We use the fact that $p-p_i=b(\mu u-\unicode{x3bb} _iv)$ , which is a multiple of $u_i$ , and that $x_i\in X_i$ is $u_i$ -periodic, so $x_i(p+q)=x_i(p_i+q)$ for all q.

If $q\notin F$ , then $x'(p_0+q)=x(p_0+q)$ by definition of $x'$ . If $q\in F$ and $i\geq 1$ , then

$$ \begin{align*} x^{\prime}_i(p_0+q)&=x_i(p+q)\quad\,\text{by definition of }x',\\ &=x_i(p_i+q)\quad\text{as }p-p_i\text{ is a multiple of }u_i,\\ &=x_i(p_0+q)\quad\text{as }x(p_i+q)=\pi(q)=x(p_0+q)\text{ by (5.1).} \end{align*} $$

As a result, $x^{\prime }_i=x_i\in X_i$ for $i\geq 1$ , so $x\in X$ .

We have shown that the F-pattern appearing at position $p=av+b\mu u$ in x can be $0$ -grafted into x at position $p_0=av$ , contradicting the assumption that x is a $(0,v)$ -ramification.

Proof. Let $f:X\to Y$ be a factor map and $k\in \mathbb {N}$ be such that each $p\in \mathbb {Z}^2$ is determined by its neighbourhood $\mathcal {N}(p,k)$ . For $r\in \mathbb {N}$ , let v be such that Y admits an $(r+2k,v)$ -ramification $y\in Y$ , witnessed by u and F. Let $x\in X$ be such that $f(x)=y$ . We claim that x is an $(r,v)$ -ramification, witnessed by u and $W:=\mathcal {N}(F,k)$ .

Let $\unicode{x3bb} $ and $\mu>0$ be integers. Assume for a contradiction that the W-pattern appearing at position $\unicode{x3bb} v+\mu u$ in x can be grafted into x at position $\unicode{x3bb} v$ , let $x'\in X$ be the result of this graft and $y'=f(x')$ . As $x'$ coincides with x outside $\mathcal {N}(\unicode{x3bb} v+W,r)=\mathcal {N}(\unicode{x3bb} v+F,r+k)$ , $y'$ coincides with y outside $\mathcal {N}(\unicode{x3bb} v+F,r+2k)$ . The F-pattern appearing at position $\unicode{x3bb} v$ in $y'$ is the F-pattern appearing at position $\unicode{x3bb} v+\mu u$ in y, so $y'$ witnesses that this pattern can be $(r+2k)$ -grafted into y, which contradicts the assumption.

Given $r\in \mathbb {N}$ , there exist infinitely many vectors v such that Y admits an $(r+2k,v)$ -ramification and X admits an $(r,v)$ -ramification for each such v.

Proof. If X is a fullshift, then it is strongly irreducible so it is not finitely ramified. We now assume that $X=\prod _{i=0}^kX_i$ , where $k\geq 1$ , $X_0$ is a fullshift and for $1\leq i\leq k$ , $X_i$ is a periodic shift of period $u_i\neq 0$ . A configuration $x\in X$ is $(x_0,\ldots ,x_k)$ with each $x_i\in X_i$ . Let A be the finite alphabet such that $X\subseteq A^{\mathbb {Z}^2}$ .

Let v be independent of each $u_i$ and such that X is finitely $(0,v)$ -ramified, using $u,F$ . Let $u_0=u$ . We apply Lemma 5.9, giving $\unicode{x3bb} _1,\ldots ,\unicode{x3bb} _k$ and $\mu>0$ such that each $\mu u-\unicode{x3bb} _iv$ is a multiple of $u_i$ . Let $\unicode{x3bb} _0=0$ , $L^+=\max _i\unicode{x3bb} _i$ , $L^-=\min _i\unicode{x3bb} _i$ and $L=L^+-L^-+1$ .

Let $N=N(A^F,L)$ be given by the Van der Waerden theorem (Theorem A.1) and $K=N\mu $ . There is $x\in X$ and $\alpha>0$ witnessing the finite $(0,v)$ -ramifications.

We define a colouring of $[0,N]$ . Assign to each $n\in [0,N]$ the F-pattern $\pi _n\in A^F$ appearing at position $n\alpha v$ in x. By the Van der Waerden theorem, this colouring admits a monochromatic arithmetic progression of length L, that is, there exist a and $b\geq 1$ such that all $(a+\unicode{x3bb} b)$ have the same colour, $\unicode{x3bb} \in [L^-,L^+]$ (in the trivial case when $L=1$ , we can take $b=1$ ). Let $\pi $ be the common F-pattern appearing at these positions $(a+\unicode{x3bb} b)\alpha v$ . In particular, if $p_i=(a+\unicode{x3bb} _i b)\alpha v$ and $q\in F$ , then $\pi (q)=x(p_i+q)$ does not depend on i.

Observe that $a\in [-K,K]$ and $b\mu \in [1,K]$ : indeed, $a=a+\unicode{x3bb} _0 b\in [0,N]$ and $b\leq N/(L-1)\leq N$ (if $L=1$ , then $b=1=N$ ).

Let $p=a\alpha v+b\mu \alpha u$ and $\xi $ be the F-pattern appearing at position p in x. We claim that $\xi $ can be $0$ -grafted into x at position $p_0$ . In other words, if we define $x'\in A^E$ by

$$ \begin{align*} x'(p_0+q)=\begin{cases} x(p+q)&\text{if }q\in F,\\ x(p_0+q)&\text{otherwise,} \end{cases} \end{align*} $$

then $x'$ belongs to X. Note that $x^{\prime }_0\in X_0$ because $X_0$ is the fullshift. We claim that for $i\geq 1$ , one has $x^{\prime }_i=x_i\in X_i$ , from which it follows that $x'\in X$ .

We use the fact that $p-p_i=b(\mu \alpha u-\unicode{x3bb} _i \alpha v)$ , which is a multiple of $u_i$ , so $x_i(p+q)=x_i(p_i+q)$ for all q.

If $q\notin F$ , then $x'(p_0+q)=x(p_0+q)$ by definition of $x'$ . If $q\in F$ and $i\geq 1$ , then

$$ \begin{align*} x^{\prime}_i(p_0+q)&=x_i(p+q)\quad\,\text{by definition of }x',\\ &=x_i(p_i+q)\quad\text{as }p-p_i\text{ is a multiple of }u_i,\\ &=x_i(p_0+q)\quad\text{as }x(p_i+q)=\pi(q)=x(p_0+q). \end{align*} $$

As a result, $x^{\prime }_i=x_i\in X_i$ for $i\geq 1$ , so $x\in X$ .

We have shown that the F-pattern appearing at position $p=a\alpha v+b\mu \alpha u$ in x can be $0$ -grafted into x at position $p_0=a\alpha v$ .

One has $|a|\leq K$ and $|b\mu |\leq K$ so it contradicts the property of finite $(0,v)$ - ramifications.

Proof. Let $f:X\to Y$ of radius k. Let $r\in \mathbb {N}$ and v be such that Y has an $(r+2k,v)$ -ramification y, witnessed by u and F. We define $W=\mathcal {N}(F,k)$ , which is the region that determines F, and show that X is finitely $(r,v)$ -ramified, witnessed by u and W.

Let $K\in \mathbb {N}$ and $G_K=\{\unicode{x3bb} v+\mu u:\unicode{x3bb} \in [-K,K],\mu \in [1,K]\}$ .

To each $p\in \mathbb {Z}^2$ , we associate the rule that determines the F-pattern appearing at position p in $f(x)$ from the W-pattern appearing at position p in x. If A and B are the finite alphabets underlying X and Y, respectively, then a rule is an element of the finite set $(B^F)^{A^W}$ . By the Gallai-Witt theorem (Theorem A.2), there exist $a\in \mathbb {Z}^2$ and $\alpha>0$ such that all the cells in $a+\alpha G_K$ have the same rule. The shift-invariance of X and Y enables us to get rid of a as follows: the function $g=\sigma ^a\circ f\circ \sigma ^{-a}$ is a surjective local function of radius k, it surjectively sends X to Y and all the cells in $\alpha G_K$ have the same rule.

Let $x\in X$ be such that $g(x)=y$ , we show that x and $\alpha $ satisfy the finite ramification property for X.

Assume for a contradiction that for some $\unicode{x3bb} \in [-K,K]$ and $\mu \in [1,K]$ , the W-pattern appearing at position $p=\unicode{x3bb} \alpha v+\mu \alpha u$ can be r-grafted into x at position $p_0=\unicode{x3bb} \alpha v$ , let $x'$ be the result of this r-graft and define $y'=g(x')$ . Note that $p,p_0\in \alpha G_K$ so the function g has the same rules at positions p and $p_0$ . This property and the fact that the W-pattern at position p in x coincides with the W-pattern at position $p_0$ in $x'$ imply that the F-pattern $\pi $ appearing at position p in y coincides with the F-pattern at position $p_0$ in $y'$ . As $x'$ coincides with x outside $\mathcal {N}(p_0+W,r)=\mathcal {N}(p_0+F,r+k)$ and g has radius k, $y'=g(x')$ coincides with $y=g(x)$ outside $\mathcal {N}(p_0+F,r+2k)$ . As $y'\in Y$ , it shows that the $\pi $ can be $(r+2k)$ -grafted into y at position $p_0$ , which contradicts the assumption that y is an $(r+2k,v)$ -ramification for Y.