# Short-range and long-range order: a transition in block-gluing behavior in
Hom shifts.

Silvère Gangloff111Corresponding author AGH University of Science and
Technology, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Kraków,
Poland<EMAIL_ADDRESS>Benjamin Hellouin de Menibus  Université Paris-
Saclay, CNRS, Laboratoire Interdisciplinaire des Sciences du Numérique, 91400,
Orsay, France Orcid ID : 0000-0001-5194-929X<EMAIL_ADDRESS>Piotr Oprocha
AGH University of Science and Technology, Faculty of Applied Mathematics, al.
Mickiewicza 30, 30-059 Kraków, Poland<EMAIL_ADDRESS>National
Supercomputing Centre IT4Innovations, University of Ostrava, IRAFM, 30\. dubna
22, 70103 Ostrava, Czech Republic<EMAIL_ADDRESS>
###### Abstract

_Hom shifts_ form a class of multidimensional shifts of finite type (SFT) and
consist of colorings of the grid $\mathbb{Z}^{2}$ where adjacent colours must
be neighbors in a fixed finite undirected simple graph $G$. This class
includes several important statistical physics models such as the hard square
model. The _gluing gap_ measures how far any two square patterns of size $n$
can be glued, which can be seen as a measure of the range of order, and
affects the possibility to compute the entropy (or free energy per site) of a
shift. This motivates a study of the possible behaviors of the gluing gap. The
class of Hom shifts has the interest that mixing type properties can be
formulated in terms of algebraic graph theory, which has received a lot of
attention recently. Improving some former work of N. Chandgotia and B. Marcus,
we prove that the gluing gap either depends linearly on $n$ or is dominated by
$\log(n)$. We also find a Hom shift with gap $\Theta(\log(n))$, infirming a
conjecture formulated by R. Pavlov and M. Schraudner. The physical interest of
these results is to better understand the transition from short-range to long-
range order (respectively sublogarithmic and linear gluing gap), which is
reflected in whether some parameter, the square cover, is finite or infinite.

##  1 Introduction

Multidimensional shifts of finite type are multidimensional dynamical systems
defined as the action of the group $\mathbb{Z}^{d}$, via the shift, on the
compact subset of $\mathcal{A}^{\mathbb{Z}^{d}}$ whose elements are the ones
in which no pattern in $\mathcal{F}$ appear, where $\mathcal{A}$ is a finite
set, $d\geq 2$, and $\mathcal{F}$ is a finite set of patterns on
$\mathcal{A}$. They appear in various areas of mathematics: in particular as a
natural extension of (unidimensional) subshifts of finite type, which
themselves were first used by J.Hadamard in his work on geodesic flows on
surfaces of negative curvature [Had98]; in statistical physics, as lattice
models such as the hard square model and square ice model; in mathematical
logic, with the work of H.Wang [Wan61] on tilings of the plane with square
tiles.

#### Topological entropy

of a shift of finite type, which in statistical physics is usually called free
energy per site, is the asymptotic growth rate of the number of restrictions
on $\llbracket 0,n-1\rrbracket^{d}$ of its elements. In a celebrated article,
E.H.Lieb [Lie67] has computed an exact formula of topological entropy for the
square ice model, with the rationale of developing tools for computing
physically relevant quantities of models with high number of variables in an
efficient way. Unfortunately, the method proposed by Lieb does not generalize
to other shifts of finite type easily. In general, computing exactly
topological entropy of a multidimensional shift of finite type is a very hard
problem.

#### Uncomputability of entropy in general.

As a matter of fact, L.Hurd, J.Kari and K.Culik [HKC92] have proved that
topological entropy is uncomputable for cellular automata, which form a
subclass of multidimensional shifts of finite type. This leaves no hope to
find a general method to compute topological entropy. Later, M.Hochman and
T.Meyerovitch [HM07] provided a characterization of possible values of
topological entropy on the class of shifts of finite type of dimension $d$,
for any $d$, as the non-negative real number which are computable from above,
tightening the relation between multidimensional symbolic dynamics and
computability theory.

#### Computability under block gluing property.

On the other hand, algorithms have been developed in order to find rational
approximations of topological entropy with arbitrary precision, in particular
cases such as the hard square model [Pav10]. Furthermore, there exists a
general method to compute topological entropy this way for shifts of finite
type which satisfy the block gluing property in two dimensions $(d=2)$ [PS15].
This property consists in the possibility to ‘glue’ any pair of square
patterns of the same size, provided that the distance between them is greater
than a fixed constant, and then fill the grid $\mathbb{Z}^{d}$ into an element
of the shift.

#### Edge of uncomputability.

Together with M.Sablik [GS21], the first author proposed a quantification of
the block gluing property, in which a function of the size of the patterns,
called gap function, replaces the constant. This function reflects the ‘range
of order’ in the system: the larger this function, the farther the presence of
one particular pattern has an influence over the configuration. They studied
the ‘edge of uncomputability’ (by analogy with the edge of chaos) for this
quantification, with the purpose of understanding how the uncomputability
phenomenon appears. In particular, they identified the ‘area’ in between
logarithmic and linear functions as were uncomputability occurs for
topological entropy. Unfortunately, no tool is available in order to analyze
shifts of finite type in this area. In particular, it is not known if there
exists a shift of finite type in two dimensions which has the block gluing
property with a gap function strictly between logarithmic and linear. On the
class of decidable shifts, close to the one of shifts of finite type, the
first and second authors identified [GdM19] a threshold at which
uncomputability of entropy occurs, defined by the condition

$\sum_{n}\frac{f(n)}{n^{2}}=+\infty,$

where $f$ is the gap function. This suggests that if it is possible to find a
similar threshold for shifts of finite type, it should be strictly in between
logarithmic and linear.

#### Hom shifts.

In order to understand better block gluing classes, which group together
shifts of finite type having equivalent gap functions the strategy that we
propose here is to restrict the scope to a natural subclass of the one of two-
dimensional shifts of finite type. In this text, we consider Hom shifts, that
is, the set of graph morphisms from $\mathbb{Z}^{d}$ to $G$, where $G$ is an
undirected, simple, connected graph (self-loops are allowed). In the symbolic
dynamics context, they were studied by N. Chandgotia [Cha17], who coined the
name ‘Hom shifts’, borrowing the definition from Brightwell & Winkler [BW00].
Although entropy is computable on Hom shifts [Fri97], this is a natural class
to better understand the block-gluing property for the following reasons. 1.
First, it is related to statistical physics models, in the sense that the hard
square shift is included in it, and the square ice model is related to the set
of three-colourings of $\mathbb{Z}^{2}$ (in particular they have the same
entropy), also in this class. 2. While several problems are undecidable for
multidimensional shifts of finite type, many of them become decidable for Hom
shifts. For instance, the fact that Hom shifts can be defined by a symmetric
set of forbidden patterns allows us to compute the value of topological
entropy [Fri97] \- a fact related to the intuition that it is impossible to
embed universal computation in shifts under this (strong) constraint. 3. The
conceptual richness of graph theory should help to forge concepts in order to
analyze block gluing classes in this restricted context, concepts which may
then be extended to the general context of multidimensional shifts of finite
type.

#### Mixing-type properties and algebraic topology.

Mixing-type properties have been studied for Hom shifts in the recent years,
in particular topological and measure-theoretical mixing [BP17, CM18, BBDL21].
In [CM18], the authors express gap functions for mixing-type properties of Hom
shifts in terms of the diameter of the graph of walks of length $n$ on $G$.
They use concepts of topological algebraic nature defined on finite graphs (as
done in algebraic graph theory), in particular the universal cover - related
to the fundamental group - in order to prove that whenever the graph $G$ is
square-free, the gap function is $O(1)$ or $\Theta(n)$. R. Pavlov & M.
Schraudner conjectured that this holds for general graphs as well (section 6.3
in _op. cit._).

The concepts and tools used in [CM18] and the square free-hypothesis appear
also in works related to homomorphism reconfiguration in graph theory, using a
non-standard reconfiguration step (see for instance [Wro20]). As well concepts
of topological algebraic nature appear also in other works on symbolic
dynamics, such as for instance the projective fundamental group [GP95]. For
more details on the link between our tools and algebraic topology, see the
second half of Section 4.1.

#### This article.

We focus here on two-dimensional Hom shifts. Despite this restriction, this
setting still covers a plethora of important examples, since most of
statistical physics models are two-dimensional. We consider the problem of
characterizing the possible equivalence classes of gap functions for a
property slightly more general than classical block gluing, called ‘phased
block gluing’ by N.Chandgotia. Any Hom shift given by a finite graph $G$ is
phased block gluing for some gap function, denoted by $\gamma_{G}$. The
problem that we are interested in here is the following:

######  Problem.

1. What are the possible equivalences classes $\Theta(\gamma_{G})$ for all finite graphs $G$? 2. Given a graph $G$, is it decidable which equivalence class the function $\gamma_{G}$ belongs to?

Our main results, which address the first part of this problem, are the
following:

######  Theorem.

For any finite graph $G$, $\gamma_{G}(n)=\Theta(n)$ or $O(\log(n))$ (Theorem
4.23). There exists a graph $K$ such that $\gamma_{K}(n)=\Theta(\log(n))$
(Theorem 7.1).

In particular, we infirm R. Pavlov and M. Schraudner’s conjecture. In order to
prove this theorem, we extend the methods developed in [CM18], and remove the
square free hypothesis by considering, instead of the universal cover, its
quotient by squares of $G$. Mathematically, the impact of this result is
twofold. First, we deepen the relation between dynamical properties of Hom
shifts (and by extension multidimensional shifts of finite type) and algebraic
topology, because we prove a tight correspondence between behaviors of phased
block gluing gap functions in the ‘upper part’ of the spectrum of possible
behaviors properties of the universal cover - finiteness or infiniteness of
the quotient by squares - on the whole class of Hom shifts. Second, we develop
technical tools which enable us to prove that there are no Hom shifts whose
gluing gap function is intermediate in the sense that they are strictly
between $O(\log(n))$ and $\Theta(n)$, which can serve as prototype for the
general context of block-gluing in multidimensional shifts of finite type. The
perspective of a complete classification of phased block gluing classes,
motivated by a better understanding of these classes, allows us to expect
further tools of topological algebraic nature to be developed along the way,
which can be of interest in themselves, or may be useful in order to answer
questions about Hom shifts or multidimensional shifts of finite type in
general. In particular we hope that algebraic properties may help determining
the edge of uncomputability for computing or finding a closed form for
entropy, but also other questions related to entropy, entropy minimality, and
mixing-type properties. In this direction, we conjecture the following:

######  Conjecture 1.1.

Every two-dimensional Hom shift is either $O(1)$-phased block gluing,
$\Theta(\log(n))$-phased block gluing or $\Theta(n)$-phased block gluing.

#### Physical interpretation.

We mentioned earlier that some Hom shifts appear often as simple models in
statitstical physics. The above conjecture states that mixing properties of
Hom shifts are _rigid_ , in the sense that they can be classified into three
classes with no possible intermediate behavior. In this sense they do not
correspond to phase transitions in the classical meaning of the term: a sudden
change of behavior when some parameter (usually a real number) passes a
threshold. Still, we believe that this phenomenon is related to phase
transitions: if one considers a system of a family of systems that can be
represented by Hom shifts and change some parameters, then this system must go
from a mixing class to the next without any intermediate behavior. Since
mixing properties are a description of the range of the order present in the
system, this corresponds a sudden change of behavior of the system that we
hope to be mathematically tractable. In Section 8, we leave some open
questions in this direction.

#### Structure of the article

First, in Section 3, we relate properties of $G$ and the associated Hom shift
$X_{G}$, and in particular how block-gluing on $X_{G}$ translates in terms of
graph properties. In Section 4, we define the notion of universal cover,
already used by Chandgotia. We introduce a notion of square decomposition for
cycles of $G$, which lets us define a square cover $\mathcal{U}^{\square}_{G}$
by quotienting the universal cover by the squares of $G$. This lets us prove
that if the square cover of $G$ is infinite, then $\gamma_{G}(n)=\Theta(n)$.
In Section 5, we define a representation of cycles on $G$ as a tree of simple
cycles. This representation is used in Section 6 to prove that if the square
cover of $G$ is finite, then $\gamma_{G}(n)=O(\log(n))$. In Section 7, we
exhibit a graph $K$ such that $\gamma_{K}\in\Theta(\log)$. Finally, we briefly
discuss in Section 8 some problems that are left open.

##  2 Definitions and notations

For any set $S$, we denote by $S^{*}$ the set of finite words on $S$. For a
word $u$, we denote the number of its letters by $|u|$. We usually write $u$
as $u_{0}\ldots u_{|u|-1}$. The empty word is denoted by $\epsilon$. Let us
denote $\mathbb{N}^{*}=\\{1,2,\dots\\}$ the set of positive integers and set
$\mathbb{N}=\mathbb{N}^{*}\cup\\{0\\}$. For all integers $a,b\in\mathbb{Z}$,
we denote by $\llbracket a,b\rrbracket$ the interval $\\{j\in\mathbb{Z}:a\leq
j\leq b\\}$. Similarly $\rrbracket a,b\llbracket:=\llbracket
a+1,b-1\rrbracket$. Let also $\|\cdot\|_{\infty}$ be the norm defined by
$\|\textbf{k}\|_{\infty}:=\max(|\textbf{k}_{1}|,|\textbf{k}_{2}|)$ for any
$k\in\mathbb{Z}^{2}$.

###  2.1 Shifts

Let us consider some finite set $\mathcal{A}$. A (two-dimensional) pattern $p$
on $\mathcal{A}$ is an element of $\mathcal{A}^{\mathbb{U}}$, where
$\mathbb{U}$ is a finite subset of $\mathbb{Z}^{2}$, and is called the support
of $p$. We say that $p$ appears in an element $x$ of
$\mathcal{A}^{\mathbb{Z}^{2}}$ when the restriction of $x$ to some
$\textbf{u}+\mathbb{U}$, $\textbf{u}\in\mathbb{Z}^{2}$, is equal to $p$. A
block pattern is a pattern on support $\llbracket 0,n-1\rrbracket^{2}$ for
some $n\geq 1$, which is called the size of this pattern. The shift action on
$\mathcal{A}^{\mathbb{Z}^{2}}$ is the action of the group $\mathbb{Z}^{2}$ on
this set defined by
$\sigma_{\textbf{v}}(x)=(x_{\textbf{u}+\textbf{v}})_{\textbf{u}\in\mathbb{Z}^{2}}$
for all $\textbf{v}\in\mathbb{Z}^{2}$ and $x\in\mathcal{A}^{\mathbb{Z}^{2}}$.
We endow $\mathcal{A}^{\mathbb{Z}^{2}}$ with Tikhonov topology, defined by
discrete topology on $\mathcal{A}$. This makes $\mathcal{A}^{\mathbb{Z}^{2}}$
metrizable compact metric space and $\sigma_{\textbf{v}}$ continuous for every
v.

A shift on alphabet $\mathcal{A}$ is any compact subset $X$ of
$\mathcal{A}^{\mathbb{Z}^{2}}$ which is invariant under the shift action. A
pattern is said to be globally admissible for a shift $X$ when it appears in
at least one of its elements. Provided a set of patterns $\mathcal{F}$ on
alphabet $\mathcal{A}$, we denote by $X_{\mathcal{F}}$ the shift on alphabet
$\mathcal{A}$ whose elements are the ones in which no element of $\mathcal{F}$
appear. A shift $X$ is said to be of finite type when there exists a finite
$\mathcal{F}$ such that $X=X_{\mathcal{F}}$. Provided such a set
$\mathcal{F}$, we say that a pattern $p$ is locally admissible when no element
of $\mathcal{F}$ appears in $p$.

###  2.2 Graphs

In the whole text $G=(V_{G},E_{G})$ is some undirected, simple and connected
graph, where $V_{G}$ denotes the set of vertices of $G$ and $E_{G}$ its set of
edges. Depending on the context, this graph may not necessarily be finite.
Whenever we consider another graph $H$, we denote by $V_{H}$ the set of its
vertices and $E_{H}$ the set of its edges.

######  Definition 2.1.

A walk on the graph $G$ is a non-empty word $p$ in $V_{G}^{*}$ such that for
all $k\leq|p|-2$, $(p_{k},p_{k+1})\in E_{G}$. We denote by $l(p)$ the number
$|p|-1$, and call it the length of $p$ (equivalently, this is the number of
edges that the walk follows). A cycle on $G$ is a walk $c$ such that
$c_{0}=c_{l(c)}$. It is said to be simple when $i<j$ and $c_{i}=c_{j}$ imply
that $i=0$ and $j=l(c)$. Similarly we say that a walk $p$ is simple when for
all $i\neq j$, $p_{i}\neq p_{j}$.

######  Notation 2.2.

$\mathcal{C}^{0}_{G}$ is the set of simple cycles of $G$.

######  Notation 2.3.

For all walk $p$, we will denote $p^{-1}$ the walk $p_{l(p)}\ldots p_{0}$.

######  Definition 2.4.

A spine on $a\in V_{G}$ is any cycle of length $2$ starting and finishing at
$a$. A walk is said to be non-backtracking if it has no spine as a subword.

######  Notation 2.5.

In what follows, we will denote by $\varphi$ the function from the set of
walks on $G$ to itself defined as follows: for every walk $p$, $\varphi(p)$ is
obtained from $p$ by replacing successively every spine $aba$ by $a$ until
there is none left. $\varphi$ is well-defined because the remaining word does
not depend on the order in which the spines are replaced.

######  Notation 2.6.

For a walk $p$ of length $n\geq 1$ on $G$, say $p=p_{0}\ldots p_{n}$, we
denote by $\rho_{l}(p)$ (resp. $\rho_{r}(p)$) the set of walks of the form

$p_{1}\ldots p_{n}x\quad(resp.\ xp_{0}\ldots p_{n-1}).$

An element of this set is called a left shift (resp. a right shift) of $p$.

######  Notation 2.7.

For two walks $p$ and $q$ such that $q_{0}=p_{l(p)}$, denote by $p\odot q$ the
walk $p_{0}\ldots p_{l(p)}q_{1}\ldots q_{l(q)}$. For any cycle $c$, denote by
$c^{n}$, $n\geq 1$ the cycles such that for all $n\geq 2$, $c^{n}=c\odot
c^{n-1}$ and $c^{1}=c$.

######  Notation 2.8.

For any pair of vertices $a,b\in V_{G}$, we denote by $\delta(a,b)$ the
shortest length of a walk in $G$ which begins at $a$ and ends at $b$. The
diameter of $G$ is:

$\text{diam}(G):=\max_{a,b\in V_{G}}\delta(a,b).$

######  Definition 2.9.

A _graph homomorphism_ from $G_{1}$ to $G_{2}$ is a function
$\psi:V_{G_{1}}\to V_{G_{2}}$ such that $(a,b)\in
E_{G_{1}}\implies(\psi(a),\psi(b))\in E_{G_{2}}$.

###  2.3 Hom shifts

######  Notation 2.10.

The two-dimensional Hom shift corresponding to the graph $G$ is the shift
$X_{G}$ on alphabet $V_{G}$ such that $x\in V_{G}^{\mathbb{Z}^{2}}$ is an
element of $X_{G}$ if and only if for all
$\textbf{u},\textbf{v}\in\mathbb{Z}^{2}$ such that
$\|\textbf{u}-\textbf{v}\|_{\infty}=1$, $x_{\textbf{u}}$ and $x_{\textbf{v}}$
are neighbors in $G$.

######  Remark 2.11.

We may view $\mathbb{Z}^{2}$ as a graph such that $(u,v)\in
E_{\mathbb{Z}^{2}}$ if and only if $\|u-v\|=1$. This way, each $x\in X_{G}$
can be viewed as a graph homomorphism $x\colon\mathbb{Z}^{2}\to G$. Then the
set $X_{G}$ can be seen as the set of graph homomorphisms, which explains the
name ‘Hom shift’.

######  Remark 2.12.

If $G$ is finite, then $X_{G}$ is a shift of finite type. Indeed, denoting by
$\mathcal{F}_{G}$ the set of patterns $vw$ and $\begin{array}[]{c}v\\\
w\end{array}$, where $(v,w)\notin E_{G}$, we have $X_{G}=X_{\mathcal{F}_{G}}$.
Whenever we consider locally admissible patterns for $X_{G}$, this notion is
relative to this set $\mathcal{F}_{G}$.

######  Remark 2.13.

A pattern $p$ on support $\mathbb{U}$ is locally admissible for $X_{G}$ when
there is a graph homomorphism from $\mathbb{U}$ to $G$, where $\mathbb{U}$ is
seen as a subgraph of the grid $\mathbb{Z}^{2}$.

We denote by $L_{G}^{n}$ the set of walks of length $n$ on $G$.

######  Notation 2.14.

For any integer $n\geq 0$, denote $X^{(n)}_{G}$ the subset of
$\left(L^{n}_{G}\right)^{\mathbb{Z}}$ whose elements $x$ are such that there
exists some $z\in X_{G}$ such that $x=z_{|\llbracket
0,n\rrbracket\times\mathbb{Z}}$.

######  Notation 2.15.

For all $n\geq 1$, let us denote by $\Delta_{G}^{n}$ the graph whose vertices
are the elements of $L^{n}_{G}$, and whose edges are the pairs $(p,q)\in
L^{n}_{G}\times L^{n}_{G}$ such that $x_{0}=p$ and $x_{1}=q$ for some $x\in
X^{(n)}_{G}$. For all $n$ and $(p,q)\in L^{n}_{G}\times L^{n}_{G}$, we denote
by $d_{G}(p,q)$ the distance between $p$ and $q$, defined as the smallest
length of a walk on $\Delta_{G}^{n}$ which begins at $p$ and ends on $q$.

In other words, the graph $\Delta_{G}^{n}$ tells which walks can be written
next to each other, as vertical or horizontal patterns, in an element of
$X_{G}$.

######  Remark 2.16.

For every walk $p$ and right or left shift $q$ of $p$, we have $d_{G}(p,q)=1$.

###  2.4 Block-gluing

For two subsets $\mathbb{U}$ and $\mathbb{U}^{\prime}$ of $\mathbb{Z}^{2}$,
denote
$\delta(\mathbb{U},\mathbb{U}^{\prime})=\min_{\begin{subarray}{c}\textbf{u}\in\mathbb{U}\\\
\textbf{u}^{\prime}\in\mathbb{U}^{\prime}\end{subarray}}\|\textbf{u}-\textbf{u}^{\prime}\|_{\infty}$.

######  Definition 2.17.

Let us consider a function $f:\mathbb{N}^{*}\rightarrow\mathbb{N}$, and an
integer $k\in\mathbb{N}^{*}$. A shift on some alphabet $\mathcal{A}$ is said
to be $(f,k)$-phased block gluing when, for every globally admissible block
patterns $p$ and $p^{\prime}$ having the same size $n$, and
$\textbf{u},\textbf{u}^{\prime}\in\mathbb{Z}^{2}$ such that

$\delta\left(\textbf{u}+\llbracket
0,n-1\rrbracket^{2},\textbf{u}^{\prime}+\llbracket
0,n-1\rrbracket^{2}\right)\geq f(n),$

there exists some $x\in X$ and some $\textbf{v}\in\mathbb{Z}^{2}$ such that
$\|\textbf{v}\|_{\infty}<k$, $x_{\textbf{u}+\llbracket 0,n-1\rrbracket^{2}}=p$
and $x_{\textbf{u}^{\prime}+\textbf{v}+\llbracket
0,n-1\rrbracket^{2}}=p^{\prime}$. A shift which is $(f,1)$-phased block gluing
for some $f$ is simply said to be $f$-block gluing. A shift which is $(f,k)$\-
phased block gluing for some $f$ and $k\geq 1$ is said to be phased block
gluing.

######  Definition 2.18.

Whenever a shift $X$ is $(f,k)$-phased block gluing for some function $f$ and
some integer $k$, we call phase of $X$ the minimal integer $l$ such that $X$
is $(g,l)$-block gluing for some function $g$, and denote it by $\theta_{X}$.

######  Definition 2.19.

When a shift $X$ is phased-block-gluing, we denote by
$\gamma_{X}:\mathbb{N}^{*}\rightarrow\mathbb{N}$ function such that for all
$n\geq 1$, $\gamma_{X}(n)$ is the minimal integer $m$ such that for every
block patterns $p$ and $p^{\prime}$ having size $n$, and
$\textbf{u},\textbf{u}^{\prime}\in\mathbb{Z}^{2}$ such that

$\delta\left(\textbf{u}+\llbracket
0,n-1\rrbracket^{2},\textbf{u}^{\prime}+\llbracket
0,n-1\rrbracket^{2}\right)\geq m,$

there exists some $x\in X$ and some $\textbf{v}\in\mathbb{Z}^{2}$ such that
$\|\textbf{v}\|_{\infty}<\theta_{X}$, $x_{\textbf{u}+\llbracket
0,n-1\rrbracket^{2}}=p$ and $x_{\textbf{u}^{\prime}+\textbf{v}+\llbracket
0,n-1\rrbracket^{2}}=p^{\prime}$. The function $\gamma_{X}$ is called the gap
function of $X$ for the phased block gluing property.

In general it is difficult to compute exactly or obtain a concrete description
of a gap function. We instead look at equivalence classes defined as follows:

######  Notation 2.20.

Let us consider two functions $f,g:\mathbb{N}^{*}\rightarrow\mathbb{N}$. We
write $g(n)=O(f(n))$ when there exist $c>0$ and $K>0$ such that for all $n$,

$g(n)\leq cf(n)+K.$

$O(g)$ is the set of functions $f$ such that $f(n)=O(g(n))$.

We write $f(n)=\Theta(g(n))$ when $f(n)=O(g(n))$ and $g(n)=O(f(n))$. This is
an equivalence relation, and we denote by $\Theta(g)$ the equivalence class of
$g$.

######  Denomination 2.21.

A shift $X$ is said to be $(\Theta(g),k)$-block gluing (resp. $(O(g),k)$-block
gluing) when it is $(f,k)$-block gluing with $f\in\Theta(g)$ (resp. $O(g)$).

##  3 Block-gluing of $X_{G}$ and properties of $G$

In this section, we analyze which properties of $G$ translate as block-gluing
on $X_{G}$.

If $G$ is not connected, $X_{G}$ cannot be $(f,k)$-phased block gluing for any
$(f,k)$. Therefore, for the remainder of that text we assume that $G$ is
connected.

###  3.1 Distance between walks

In this section, we prove that for any finite graph $G$, $X_{G}$ is phased
block gluing and its phase is $1$ or $2$ (Proposition 3.6). For simplicity, we
use the notation $\gamma_{G}:=\gamma_{X_{G}}$.

A subset $\mathbb{U}\subset\mathbb{Z}^{2}$ is said to be connected when the
corresponding subgraph of $\mathbb{Z}^{2}$ is connected.

######  Definition 3.1.

A finite set $\mathbb{U}\subset\mathbb{Z}^{2}$ is said to be _block-like_ when
it is connected and for every $k\in\mathbb{Z}$,
$\mathbb{U}\cap(\\{k\\}\times\mathbb{Z})$ and
$\mathbb{U}\cap(\mathbb{Z}\times\\{k\\})$ are intervals.

When the support is a rectangle, that is, the product of two intervals, the
following lemma corresponds to Proposition 2.1 in [CM18].

######  Lemma 3.2.

Every pattern $p$ which is locally admissible for $X_{G}$ and whose support is
block-like is globally admissible.

###### Proof.

Let us fix a locally admissible pattern $p$ on a block-like support
$\mathbb{U}$. We are going to define some configuration $x$ in which $p$
appears. We first set $x_{|\mathbb{U}}=p$.

Because $\mathbb{U}$ is block-like, a point $(i,j)\notin\mathbb{U}$ cannot
have more than two neighbors in $\mathbb{U}$. Let us assume that there is some
$(i,j)\notin\mathbb{U}$ which has two neighbors in $\mathbb{U}$. These
neighbors are respectively of the form $(i\pm 1,j)$ and $(i,j\pm 1)$,
otherwise $\\{i\\}\times\mathbb{Z}$ or $\mathbb{Z}\times\\{j\\}$ would not be
an interval. Without loss of generality, let us assume that they are $(i+1,j)$
and $(i,j+1)$ (other cases are processed in a similar way). Let us prove that
$(i+1,j+1)\in\mathbb{U}$. Since $\mathbb{U}$ is connected, there exists a walk
on $\mathbb{U}$ from $(i+1,j)$ to $(i,j+1)$. Such a walk intersects
$\\{i\\}\times\rrbracket-\infty,j\llbracket$ or $\\{i+1\\}\times\rrbracket
j,+\infty\llbracket$ (see for instance Figure 1).

$\boldsymbol{(i,j)}$ Figure 1: Illustration for the proof of Lemma 3.2: two
possible paths from $(i+1,j)$ to $(i,j+1)$ in $\mathbb{U}$. Only the one on
the right can be contained in $\mathbb{U}$.

Since $\mathbb{U}$ is block-like and $(i,j)\notin\mathbb{U}$, it can’t
intersect the first set and thus intersects the second. Again, since
$\mathbb{U}$ is block-like, we have $(i+1,j+1)\in\mathbb{U}$.

Therefore, every block-like subset of $\mathbb{Z}^{2}$ such that no
$(i,j)\notin\mathbb{U}$ has two neighbors in $\mathbb{U}$ is a rectangle.
Indeed, for every $j\in\mathbb{Z}$ such that the columns
$\mathbb{Z}\times\\{j\\}$ and $\mathbb{Z}\times\\{j+1\\}$ intersect
$\mathbb{U}$, their respective intersections with $\mathbb{U}$ are equal. A
similar statement is satisfied for rows. This implies that $\mathbb{U}$ is a
rectangle.

Let us consider the minimal rectangle $R$ which contains the set $\mathbb{U}$.
There exists a sequence $(\textbf{v}_{l})_{1\leq l\leq m}$ of elements of
$\mathbb{Z}^{2}$ such that, denoting

$\forall l\in\llbracket 0,m\rrbracket,\
\mathbb{U}_{l}:=\mathbb{U}\cup\\{\textbf{v}_{1},\dots,\textbf{v}_{l}\\},$

we have $\mathbb{U}_{m}=R$ and, for all $l<m$, $\textbf{v}_{l+1}$ is not in
$\mathbb{U}_{l}$ but has exactly two neighbors in $\mathbb{U}_{l}$.

For all $l<m$, $\mathbb{U}_{l}$ is block-like, and therefore there is a an
element $\textbf{w}_{l}\in\mathbb{U}_{l}$ which is neighbor of the two
neighbors of $\textbf{v}_{l+1}$ in $\mathbb{U}_{l}$. We set
$x_{\textbf{v}_{l+1}}:=x_{\textbf{w}_{l}}$.

The defined pattern $x_{|R}$ is locally admissible on a rectangle support $R$,
so it is globally admissible by Proposition 2.1 in [CM18]. Hence $p$ is
globally admissible. ∎

The following characterisation is well-known:

######  Lemma 3.3.

A graph $H$ is bipartite if and only if it has no cycle of odd length.

######  Lemma 3.4.

Let $H$ be a finite graph. For every $u,v\in V_{H}$ and
$k\geq\textrm{diam}(H)$, there is a walk from $u$ to $v$ which has length $k$
or $k+1$. If $H$ is not bipartite, then for all $k\geq 3\textrm{diam}(H)$,
there is a walk of length $k$ from $u$ to $v$.

###### Proof.

By definition of the diameter, there is a walk $p$ from $u$ to $v$ whose
length is at most $\textrm{diam}(H)$. Take any spine $t$ on $v$, $p\odot t$
has length $l(p)+2$ and also begins at $u$ and ends on $v$. The first claim
follows.

Let us assume that $H$ is not bipartite. This implies that $H$ contains a
cycle $c$ of odd length (see Lemma 3.3). Let $p$ and $q$ be the shortest walk
from $u$ to $c_{0}$ and from $c_{0}$ to $v$, respectively. The respective
lengths of walks $p\odot q$ and $p\odot c\odot q$ have different parities and
are both smaller than $k$. Let us denote $r$ the one which has the same parity
as $k$. Then for any spine $t$ on $v$, the cycle $r\odot t^{(k-l(r))/2}$ has
length $k$ and is from $u$ to $v$. ∎

######  Lemma 3.5.

For all $n\geq 1$, the graph $\Delta_{G}^{n}$ is bipartite if and only if $G$
is bipartite.

###### Proof.

If $\Delta_{G}^{n}$ is not bipartite, it has a cycle of odd length. Along the
cycle, we take the last letter of the walk on $G$ corresponding to each
vertex, we find a cycle in $G$ of odd length. Reciprocally, assume $G$ has a
cycle $c$ of odd length $m$. For all $j$ between $0$ and $m-1$, we denote by
$p^{(j)}$ the walk on $G$ which begins at $c_{j}$ and alternates between
$c_{j}$ and $c_{j+1}$. Then $p^{(0)}\ldots p^{(m-1)}p^{(0)}$ is a cycle of odd
length on $\Delta_{G}^{n}$. ∎

######  Proposition 3.6.

Let $d_{G}(n):=\textrm{diam}(\Delta_{G}^{n})$. The shift $X_{G}$ is
$(\Theta(d_{G}),2)$-phased-block-gluing. When $G$ is not bipartite, it is also
$\Theta(d_{G})$-block-gluing.

This implies that $\gamma_{X_{G}}\in\Theta(d_{G})$, generalizing Proposition
4.1 in [CM18].

###### Proof.

Let us first prove the second claim. We assume that $G$ is not bipartite. We
are going to show that $X_{G}$ is $O(d_{G})$-block gluing. Consider some
$k\geq 3d_{G}(n)$ and let $p$ and $q$ be two locally admissible block patterns
of size $n$ and $\textbf{u},\textbf{v}$ such that

$\delta\left(\textbf{u}+\llbracket 0,n-1\rrbracket^{2},\textbf{v}+\llbracket
0,n-1\rrbracket^{2}\right)=k.$

By Lemma 3.2, there exist $x,y\in X_{G}$ such that $x_{\textbf{u}+\llbracket
0,n-1\rrbracket^{2}}=p$ and $y_{\textbf{v}+\llbracket 0,n-1\rrbracket^{2}}=q$.
Without loss of generality, we can assume that
$\textbf{v}_{1}\geq\textbf{u}_{1}$ and $\textbf{v}_{2}\geq\textbf{u}_{2}$, as
well as $\textbf{v}_{1}-\textbf{u}_{1}=n+k-1$.

We apply Lemma 3.4 on the graph $H=\Delta_{G}^{n}$ obtaining that there exists
a walk of length exactly $k$ from
$x_{(\textbf{u}_{1},\textbf{v}_{2})+\\{n-1\\}\times\llbracket
0,n-1\rrbracket}$ to $y_{\textbf{v}+\\{0\\}\times\llbracket 0,n-1\rrbracket}$.
This corresponds to a locally admissible pattern $p^{\prime}$ on support
$\llbracket 0,k\rrbracket\times\llbracket 0,n-1\rrbracket$. Let us denote by
$\mathbb{V}$ the following set:

$\mathbb{V}=\left(\mathbf{u}+\llbracket 0,n-1\rrbracket\times\llbracket
0,n-1+\textbf{v}_{2}-\textbf{u}_{2}\rrbracket\right)\bigcup\left(\mathbf{v}+\llbracket\textbf{u}_{1}-\textbf{v}_{1},n-1\rrbracket\times\llbracket
0,n-1\rrbracket\right)$

uvpqnk$\mathbb{V}$uvqn$\mathbb{V}$pk Figure 2: Illustration of the definition
of $\mathbb{V}$ in two different situations.

One can find an illustration of $\mathbb{V}$ on Figure 2. We define a locally
admissible pattern $w$ on $\mathbb{V}$ by setting

$w|_{(\textbf{u}_{1}+n-1,\textbf{v}_{2})+(\llbracket
0,k\rrbracket\times\llbracket 0,n-1\rrbracket)}=p^{\prime},$
$w|_{\textbf{v}+\llbracket 0,n-1\rrbracket^{2}}=q\ $

and $w$ coincides with $x$ on the remainder of $\mathbb{V}$.

By definition of $p^{\prime}$, $w$ is well defined where the above three
rectangles intersect. Since $\mathbb{V}$ is a block-like set, by Lemma 3.2,
$w$ is globally admissible. This proves that $X_{G}$ is $O(d_{G})$-block
gluing, that is, $\gamma_{G}=O(d_{G})$. By the definition $\gamma_{G}(n)\geq
d_{G}(n)$, so we obtain that $d_{G}=O(\gamma_{G})$.

In the case $G$ is bipartite, the proof follows the same lines, except that
Lemma 3.4 provides a walk of length $k$ or $k+1$, depending on parity. In the
latter case we have to shift $y|_{\mathbf{v}}$ by one column to the right
(modifying $\mathbb{V}$ accordingly). We obtain this way that $X_{G}$ is
$(O(d_{G}),2)$-phased block gluing. ∎

###  3.2 From walks to cycles

First, we prove that we only need some values to determine the class of the
function $\gamma_{G}$.

######  Lemma 3.7.

For all $n$, we have $\gamma_{G}(n)\leq\gamma_{G}(n+1)\leq\gamma_{G}(n)+2$. In
particular, the equivalence class $\Theta(\gamma_{G})$ is the same as for the
function $n\mapsto\gamma_{G}(k\lfloor n/k\rfloor)$ for any $k>0$.

###### Proof.

The inequality $\gamma_{G}(n)\leq\gamma_{G}(n+1)$ is trivial. Let us prove the
second one. Let us consider two walks $p$ and $q$ of length $n+1$. There
exists $m\leq\gamma_{G}(n)$ and a walk $p^{(0)},\dots,p^{(m)}$ in
$\Delta^{n+1}_{G}$ from $p^{(0)}=p_{0}\ldots p_{n+1}$ and $p^{(m)}=q_{0}\ldots
q_{n+1}$. For all $i\geq 1$, let us set $q^{(i)}=p^{(i)}p^{(i-1)}_{n+1}$ and
$q^{(0)}=p$. For all $i<m$, $(q^{(i)},q^{(i+1)})$ is an edge of
$\Delta^{n+1}_{G}$, and $q^{(0)}=p$. Since $q^{(m)}$ is equal to $q$ except
for the last vertex, $q^{(m)}\in\rho_{r}(\rho_{l}(q))$. As a consequence
$d_{G}(p,q)\leq l+2$, and thus $\gamma_{G}(n+1)\leq\gamma_{G}(n)+2$. ∎

In Proposition 3.6, we related $\gamma_{G}$ to the diameter of the graph. For
bipartite graphs, it is enough to consider the distance between pairs of
cycles.

######  Lemma 3.8.

Let us assume that $G$ is bipartite. For every walk $p$ of even length, there
exists a cycle $c$ such that $d_{G}(p,c)\leq\text{diam}(G)+1$.

###### Proof.

Consider a walk $p$ of even length $n$. The result is clear when
$n\leq\text{diam}(G)$, so we assume that $n>\text{diam}(G)$.

  1. 1.

There exists $m\leq\text{diam}(G)+1$ such that there is a walk from $p_{n}$ to
$p_{m}$ of length $m$ or $m-1$: For all $k\in\\{0,\dots,n\\}$, let us set
$l_{k}:=k-\delta(p_{n},p_{k})$. We have that $l_{0}=-\delta(p_{n},p_{0})\leq
0$, and $l_{\text{diam}(G)+1}\geq 1$ by definition of the diameter.
Furthermore, for all $k<n$, we have:

$0\leq l_{k+1}-l_{k}\leq 2.$

As a consequence there exists an integer $m\leq\text{diam}(G)+1$ such that
$l_{m}\in\\{0,1\\}$, which means that $\delta(p_{n},p_{m})$ is $m$ or $m-1$.

  2. 2.

We have $\delta(p_{n},p_{m})=m$: Let $q$ be a walk of length
$\delta(p_{n},p_{m})$ from $p_{n}$ to $p_{m}$. If $q$ is of length $m-1$, the
walk $p_{m}\ldots p_{n}\odot q_{0}\ldots q_{m-1}$ is a cycle of odd length
$n-1$, which is impossible since $G$ is bipartite; it follows that $q$ is of
length $m$.

  3. 3.

Conclusion: Define, for all $k\leq m$, the walk $p^{(k)}=p_{k}\ldots
p_{n}\odot q_{0}\ldots q_{k}$. Then $p^{(0)}=p$, $p^{(k)}$ and $p^{(k+1)}$ are
neighbors in $\Delta^{n}_{G}$ for all $k\leq m-1$, and $p^{(m)}$ is a cycle. ∎

##  4 Decomposability of simple cycles into squares

###  4.1 Universal cover

The notion of universal cover comes from the notion of topological covering
space and can be defined in an abstract manner as a universal object with
regards to so-called graph coverings. This point of view is well-explained in
[Sta83] Section 4.1 or [CM18] Section 5. Below we present an explicit
construction due to [Ang80].

######  Definition 4.1.

For every $a\in V_{G}$, let $\mathcal{U}_{G}[a]$ be the graph whose vertices
are the non-backtracking walks on $G$ beginning at $a$ and whose edges are the
pairs of walks $(p,q)$ such that $p=qv$ or $q=pv$ for some vertex $v\in
V_{G}$.

######  Notation 4.2.

For two vertices $a,b$ which are neighbors in $G$, let $\psi_{a\mapsto
b}:\mathcal{U}_{G}[a]\rightarrow\mathcal{U}_{G}[b]$ be the graph morphism
defined by $\psi_{a\mapsto b}(q)=\varphi(bq)$ for all $q\in
V_{\mathcal{U}_{G}[a]}$.

######  Lemma 4.3.

For all $a,b$ neighbors in $G$, $\psi_{a\mapsto b}\circ\psi_{b\mapsto
a}=id_{V_{\mathcal{U}_{G}[b]}}$.

###### Proof.

Let $p$ be a non-backtracking walk beginning at $b$. Since $p_{0}=b$ and
spines can be removed in any order, we have that $\psi_{a\mapsto
b}\circ\psi_{b\mapsto a}=\varphi(bap)=p$. ∎

######  Lemma 4.4.

All the graphs $\mathcal{U}_{G}[a]$, $a\in V_{G}$, are isomorphic.

###### Proof.

By Lemma 4.3, $\mathcal{U}_{G}[a]$ and $\mathcal{U}_{G}[b]$ are isomorphic for
all $a$ and $b$ neighbors in $G$. Since $G$ is connected, this is sufficient.
∎

The corresponding isomorphic class is usually called the universal cover of
$G$, denoted by $\mathcal{U}_{G}$, and is thought as an unlabeled graph which
admits labelings having an interpretation in terms of walks on $G$.

In the following sections, we are going to introduce concepts which are built
upon the universal cover, in particular what we call the square cover (Section
4.3). Let us take a moment here to explain the intuition behind this
construction. We would like to establish a correspondence between $X_{G}$ and
$X_{\mathcal{U}_{G}}$, in order to deduce the block gluing gap function of
$X_{G}$ from the one of $X_{\mathcal{U}_{G}}$: the latter is much easier as
$\mathcal{U}_{G}$ is a tree.

We proceed as follows. Associate to any $x\in X_{G}$ a configuration
$\overline{x}$ in $X_{\mathcal{U}_{G}}$ in the following way, using labeling
$\mathcal{U}_{G}[x_{\textbf{0}}]$ for $\mathcal{U}_{G}$: first set
$\overline{x}_{\textbf{0}}=x_{\textbf{0}}$; then for all other
$\textbf{i}\in\mathbb{Z}^{2}$, choose a walk $p$ from 0 to i, and set
$\overline{x}_{\textbf{i}}$ equal to $\varphi(x_{p_{0}}x_{p_{1}}\dots
x_{p_{l(p)}})$ (in particular, $\eta(\overline{x}_{i})=x_{i}$). However this
definition makes sense only if the value of $\overline{x}_{i}$ is independent
from the choice of walk $p$. This is the case only if, for every $x\in X_{G}$
and every cycle in $\mathbb{Z}^{2}$ (see an illustration on Figure 3), the
corresponding cycle in $G$ backtracks to a trivial cycle.

abc

$a$$b$$a$$c$$a$$b$$a$$b$$c$$a$$c$$a$$c$$b$$a$

Figure 3: On the left: a graph $G$ containing a cycle of length four
($aabca$). On the right: the cycle $w=acaacbaacbaba$ obtained by following a
loop in $\mathbb{Z}^{2}$ in a configuration of $X_{G}$.

On the one hand, the set of cycles which are obtained as above, by following a
cycle of $\mathbb{Z}^{2}$ in a configuration of $X_{G}$, corresponds to
trivial cycles in the _fundamental group_ of the subshift $X_{G}$, a notion
that was introduced in [GP95] for general subshifts and received some recent
attention [PSV22]. On the other hand, the universal cover of a graph is
related to its own fundamental group: a cycle is trivial if and only if
removing backtracks yields the empty cycle; removing backtracks plays the role
of homotopy in this context.

With this homotopic point of view, the definition above makes sense when the
fundamental group of $X_{G}$ and the fundamental group of $G$ are isomorphic.
The results of [CM18] use implicitely the fact that this is true when $G$ does
not contain any cycle of length $4$: this was their driving hypothesis.
However this is not true in general.

In the general case, we can see that the structure of loops in
$\mathbb{Z}^{2}$ implies that cycles in $X_{G}$ correspond to cycles in $G$
that can be, in some sense, decomposed into cycles of length $4$. Therefore
the fundamental group of $X_{G}$ is related to the quotient of the universal
cover by cycles of length $4$. This is the intuition behind the definition of
the square cover.

###  4.2 Square decomposition

######  Denomination 4.5.

A square is a non-backtracking cycle of length four.

In the present section, we define the notion of decomposability into squares
for simple cycles of $G$.

######  Definition 4.6.

Let us consider two non-backtracking walks $p,q$. We say that $p$ and $q$
differ by a square when there exists an integer $k$ and a square $s$ such that
$q=\varphi(p{\oplus}_{k}s)$ or $p=\varphi(q{\oplus}_{k}s)$. Figure 4
illustrates the types of pairs $(p,q)$ of walks which differ by a square.

Let $\sim_{\square}$ be the transitive closure of this relation between walks.

pq(i)pq(ii)pq(iii) Figure 4: Partial representation of two walks $p,q$ which
differ by a square.

######  Definition 4.7.

A square decomposition of a simple cycle $c$ on $G$ is any sequence
$(p^{(i)})_{0\leq i\leq m}$ of non-backtracking walks such that $c=p^{(0)}$,
$p^{(m)}$ is an empty cycle, and $p^{(i)}$ and $p^{(i+1)}$ differ by a square
for all $i<m$. The cycle $c$ is said to be decomposable into squares when such
a decomposition exists, which is equivalent to $c\sim_{\square}c^{\prime}$ for
some empty cycle $c^{\prime}$. The smallest length $m$ for which $c$ has a
decomposition $(p^{(i)})_{0\leq i\leq m}$ is called the area of $c$ and is
denoted $m_{c}$.

######  Definition 4.8.

A graph is said to be square-decomposable when all of its simple cycles are
decomposable into squares.

It is straightforward that when $G$ is square-decomposable, every cycle (non
necessarily simple) of $G$ is also decomposable into squares. It follows that:

######  Lemma 4.9.

A square-decomposable graph is bipartite.

###### Proof.

It is sufficient to see that for $p,q$ two walks which differ by a square,
$l(p)-l(q)$ is even. Therefore every cycle of a square-decomposable graph is
of even length. ∎

As a consequence of Lemma 4.9 and Lemma 3.8 we have the following:

######  Corollary 4.10.

If $G$ is square-decomposable, then $\Theta(\gamma_{G})$ is the class of the
function $n\mapsto\max d_{G}(c,c^{\prime})$ where the maximum is taken on all
cycles $c$ and $c^{\prime}$ of length $n$.

###  4.3 Square cover

In this section, we define the square cover, which is central in the dichotomy
between $\Theta(n)$-block gluing and $O(\log(n))$-block gluing Hom shifts.

######  Notation 4.11.

Denote by $\mathcal{U}^{\square}_{G}[a]$ the quotient of $\mathcal{U}_{G}[a]$
by the equivalence relation $\sim_{\square}$. This means that it is the graph
whose vertices are the equivalence classes for $\sim_{\square}$ of vertices of
$\mathcal{U}_{G}[a]$, and there is an edge between two classes if there is an
edge between two elements of these classes. We also denote by $\pi_{a}$ the
projection from $\mathcal{U}_{G}[a]$ to $\mathcal{U}^{\square}_{G}[a]$.

Let us see that the graphs $\mathcal{U}^{\square}_{G}[a]$, $a\in V_{G}$ are
all isomorphic.

######  Lemma 4.12.

For every $a,b$ neighbors in $G$ and $p,q\in V_{\mathcal{U}_{G}[b]}$ which
differ by a square, we have that $\psi_{b\mapsto a}(p)$ and $\psi_{b\mapsto
a}(q)$ also differ by a square.

###### Proof.

There exist a square $s$ and some $k\leq l(q)$ such that
$q=\varphi(p\oplus_{k}s)$. Since removing spines in any order give the same
result, we have:

$\psi_{b\mapsto
a}(q)=\varphi(aq)=\varphi(a\varphi(p\oplus_{k}s))=\varphi(a(p\oplus_{k}s))=\varphi(ap\oplus_{k+1}s).$

We now distinguish three cases.

  1. 1.

If $p_{1}\neq a$, then $\psi_{b\mapsto a}(p)=ap$ so
$\varphi(ap\oplus_{k+1}s)=\varphi(\psi_{b\mapsto a}(p)\oplus_{k+1}s)$.

  2. 2.

If $p_{1}=a$ and $k>0$, then $ap\oplus_{k+1}s=ap_{0}(\psi_{b\mapsto
a}(p)\oplus_{k-1}s)$ and, since spines can be removed in any order,
$\varphi(ap\oplus_{k+1}s)=\varphi(\psi_{b\mapsto a}(p)\oplus_{k-1}s)$.

  3. 3.

If $p_{1}=a$ and $k=0$, then $\psi_{b\mapsto
a}(q)=\varphi(as_{0}s_{1}s_{2}s_{3}s_{0}\odot p)$. We again distinguish three
cases:

    1. (a)

If $s_{3}=a$, then $\psi_{b\mapsto
a}(q)=\varphi(as_{0}s_{1}s_{2}\varphi(ap))=\varphi(\psi_{b\mapsto
a}(p)\oplus_{0}as_{0}s_{1}s_{2}s_{3})$.

    2. (b)

If $s_{1}=a\neq s_{3}$, then
$\varphi(as_{0}s_{1}s_{2}s_{3}p)=as_{2}s_{3}p=\varphi(\psi_{b\to
a}(p)\oplus_{0}as_{2}s_{3}ba)$.

    3. (c)

If $s_{1}\neq a\neq s_{3}$, then
$\varphi(as_{0}s_{1}s_{2}s_{3}p)=as_{0}s_{1}s_{2}s_{3}p$. In that case,
$\varphi(\psi_{b\mapsto a}(q)\oplus_{1}s^{-1})=\varphi(ap)=\psi_{b\mapsto
a}(p)$.

In all three cases, $\psi_{b\mapsto a}(p)$ and $\psi_{b\mapsto a}(q)$ differ
by a square. ∎

######  Corollary 4.13.

For every $a,b$ neighbors in $G$ and $p,q\in V_{\mathcal{U}_{G}[b]}$ such that
$p\sim_{\square}q$, we have that $\psi_{b\mapsto
a}(p)\sim_{\square}\psi_{b\mapsto a}(q)$.

A direct consequence is that for all $a,b$ neighbors in $G$, we can define a
morphism $\overline{\psi}_{a\mapsto
b}:\mathcal{U}^{\square}_{G}[a]\rightarrow\mathcal{U}^{\square}_{G}[b]$ by
setting $\overline{\psi}_{a\mapsto b}(\pi_{a}(p))=\pi_{b}\left(\psi_{a\mapsto
b}(p)\right)$ for every $p\in V_{\mathcal{U}_{G}[a]}$. Furthermore:

######  Lemma 4.14.

The graphs $\mathcal{U}^{\square}_{G}[a]$, $a\in V_{G}$, are all isomorphic.

###### Proof.

As a direct consequence of Lemma 4.3, the morphism $\overline{\psi}_{a\mapsto
b}\circ\overline{\psi}_{b\mapsto a}$ is the identity of
$V_{\mathcal{U}^{\square}_{G}[a]}$. ∎

######  Definition 4.15.

We call square cover of $G$ and denote by $\mathcal{U}^{\square}_{G}$ the
isomorphic class of the graphs $\mathcal{U}^{\square}_{G}[a]$, for $a\in
V_{G}$.

In the same way as $\mathcal{U}_{G}$, we represent $\mathcal{U}^{\square}_{G}$
as an unlabeled graph which admits labelins $\mathcal{U}_{G}^{\square}[a]$,
$a\in V_{G}$. Some examples are given on Figure 5. Notice that the example (b)
is isomorphic to its square cover. Proposition 4.20 below states that this is
true for any square-decomposable graph. On the other hand a graph which is not
square-decomposable may have a finite or infinite square cover (examples (a)
and (c)).

(a)$\ldots$$\ldots$(b)(c)(d) Figure 5: Some finite graphs (on the left) and
their square cover (on the right).

######  Notation 4.16.

Since two walks which differ by a square have the same endpoint, we can define
$\eta:\bigcup_{a}\mathcal{U}^{\square}_{G}[a]\to G$ by setting
$\eta(\pi_{a}(p)):=p_{l(p)}$ for any non backtracking walk $p$ which begins
with $a$. We use the same notation for walks: for all $a$ and all walk $q$ on
$\mathcal{U}^{\square}_{G}[a]$, we set
$\eta(q):=\eta(q_{0})\ldots\eta(q_{l(q)})$.

We now arrive at the goal we set in Section 4.1: lifting configurations of
$X_{G}$ to $X_{\mathcal{U}^{\square}_{G}}$; such lifting allows us to relate
block-gluing properties of $X_{G}$ and $X_{\mathcal{U}^{\square}_{G}}$.

######  Proposition 4.17.

For every $x\in X_{G}$ and $\textbf{i}_{0}\in\mathbb{Z}^{2}$, there exists a
configuration $z$ of $X_{\mathcal{U}^{\square}_{G}[x_{\boldsymbol{i}_{0}}]}$
such that
$z_{\boldsymbol{i}_{0}}=\pi_{x_{\boldsymbol{i}_{0}}}(x_{\boldsymbol{i}_{0}})$
and for all $\boldsymbol{i}\in\mathbb{Z}^{2}$,
$\eta(z_{\boldsymbol{i}})=x_{\boldsymbol{i}}$.

###### Proof.

For all $\textbf{i}\in\mathbb{Z}^{2}$, take any walk
$\textbf{i}_{0}\dots\textbf{i}_{m}$ in $\mathbb{Z}^{2}$ such that
$\textbf{i}_{m}=\textbf{i}$ , and define
$z_{\boldsymbol{i}}=\pi_{x_{\boldsymbol{i}_{0}}}(x_{\textbf{i}_{0}}\dots
x_{\textbf{i}_{m}})\in\mathcal{U}^{\square}_{G}[x_{\boldsymbol{i}_{0}}]$.
Taking another walk in $\mathbb{Z}^{2}$ would yield the same equivalence class
$z_{\boldsymbol{i}}$, since the corresponding walks in $G$ are equivalent for
$\sim_{\square}$. Therefore $z$ is well-defined and satisfies the
requirements. ∎

######  Proposition 4.18.

Let $G$ be a graph such that $\mathcal{U}^{\square}_{G}$ is finite. Then
$\gamma_{G}=O(\gamma_{\mathcal{U}^{\square}_{G}})$.

Note that, since $\mathcal{U}^{\square}_{G}$ is always bipartite, $G$ and
$\mathcal{U}^{\square}_{G}$ do not necessarily have the same phase (for block-
gluing). Nevertheless, Proposition 3.6 still applies.

###### Proof.

By Proposition 3.6 and Lemma 3.7, it is sufficient to prove that

$\textrm{diam}(\Delta_{G}^{2n})=O\left(\textrm{diam}(\Delta_{\mathcal{U}^{\square}_{G}}^{2n})\right).$

For all $n$, set $\Lambda_{G}^{n}=\\{s^{n}:s\text{ is a spine on }G\\}$. It is
straightforward that $\textrm{diam}(\Lambda_{G}^{n})\leq\textrm{diam}(G)$. It
is thus sufficient to prove that

$\max_{p\in\Delta_{G}^{2n}}\min_{q\in\Lambda_{G}^{n}}d_{G}(p,q)\leq\textrm{diam}(\Delta_{\mathcal{U}^{\square}_{G}}^{2n}),$

where the left-hand term is the Hausdorff distance between $\Delta_{G}^{2n}$
and $\Lambda_{G}^{n}$.

We denote $(\pi_{p_{0}}\circ\varphi)^{\ast}$ the function that, to a walk $p$
on $G$, associates the sequence $(\pi_{p_{0}}\circ\varphi(p_{0}\ldots
p_{i}))_{i\leq l(p)}$.

Let $p$ be a walk of length $2n$ on $G$ and $q$ an element of
$\Lambda_{G}^{n}$ which begins on $p_{0}$. There is a walk $(p^{(i)})_{0\leq
i\leq k}$ of length $k$ in $\Delta_{\mathcal{U}^{\square}_{G}[p_{0}]}^{2n}$
between $(\pi_{p_{0}}\circ\varphi)^{\ast}(p)$ and
$(\pi_{p_{0}}\circ\varphi)^{\ast}(q)$ for some
$k\leq\textrm{diam}(\Delta_{\mathcal{U}^{\square}_{G}[p_{0}]}^{2n})$. Then the
walk $(\eta(p^{(i)}))_{0\leq i\leq k}$ is a walk in $\Delta_{G}^{2n}$ from
$\eta((\pi_{p_{0}}\circ\varphi)^{\ast}(p))=p$ to
$\eta((\pi_{p_{0}}\circ\varphi)^{\ast}(q))=q$. From this we deduce that
$d_{G}(p,q)\leq\textrm{diam}(\Delta_{\mathcal{U}^{\square}_{G}}^{2n})$. Since
$p$ can be chosen arbitrarily and $q$ chosen according to $p$, this implies
that
$\max_{p\in\Delta_{G}^{2n}}\min_{q\in\Lambda_{G}^{n}}d_{G}(p,q)\leq\textrm{diam}(\Delta_{\mathcal{U}^{\square}_{G}}^{2n})$,
and the proposition follows. ∎

######  Lemma 4.19.

Let us assume that $G$ is square-decomposable. Then for all $p,q$ non-
backtracking walks on $G$ such that $p_{0}=q_{0}$ and $p_{l(p)}=q_{l(q)}$,
$p\sim_{\square}q$.

###### Proof.

Let us prove this by induction on the area of the cycle $p\odot q^{-1}$. When
this area is equal to $0$, $p$ is equal to $q$ and they are therefore
equivalent for $\sim_{\square}$. Let us assume that the statement is proved
whenever $p\odot q^{-1}$ has area $\leq m$, and fix $p,q$ for which this cycle
has area $m+1$. Let us set $c=p\odot q^{-1}$ and consider some square $s$ and
integer $k$ such that $\varphi(c\oplus_{k}s)$ has area $m$. Let us denote by
$p^{\prime}$ and $q^{\prime}$ the following paths:

  1. 1.

if $k\leq l(p)$, $p^{\prime}=p\oplus_{k}s$ and $q^{\prime}=q$;

  2. 2.

if $k>l(p)$, $p^{\prime}=p$ and $q^{\prime}=q\oplus_{l(q)-(k-l(p))}s^{-1}$.

By induction, $p^{\prime}\sim_{\square}q^{\prime}$. Therefore, by definition
of $p^{\prime},q^{\prime}$, $p\sim q$. ∎

######  Proposition 4.20.

If $G$ is square-decomposable, $G$ and $\mathcal{U}^{\square}_{G}$ are
isomorphic.

###### Proof.

It is sufficient to see that in this case $G$ is isomorphic to
$\mathcal{U}^{\square}_{G}[a_{0}]$ for $a_{0}$ some vertex of $G$. For every
$a$ in $G$, choose some non-backtracking simple walk $p_{a}$ from $a_{0}$ to
$a$. The elements of $\pi_{a_{0}}(p_{a})$ are walks which begin at $a_{0}$ and
end at $a$. As a consequence, all the classes $\pi_{a_{0}}(p_{a})$, $a\in
V_{G}$ are different. Furthermore, because $G$ is square-decomposable, Lemma
4.19 implies that every equivalence class is equal to some
$\pi_{a_{0}}(p_{a})$.

Furthermore for all $a,b$ there is an edge between $a$ and $b$ if and only if
there is an edge between $\pi_{a_{0}}(p_{a})$ and $\pi_{a_{0}}(p_{b})$, which
yields the statement. ∎

######  Proposition 4.21.

The square cover of $G$ is square-decomposable.

###### Proof.

Let us consider some vertex $a$ of $G$. We will use the following: if $c$ is a
cycle on $\mathcal{U}^{\square}_{G}[a]$, then $\eta(c)$ is a cycle, and $c$
has a backtrack iff $\eta(c)$ has a backtrack as well.

Furthermore, for any vertex $v$ of $\mathcal{U}^{\square}_{G}[a]$, let $u$ be
a non-backtracking walk on $G$ such that $v=\pi_{a}(u)$ and let $w$ be a walk
on $G$ such that $w_{0}=\eta(v)$, we denote by $\eta^{-1}_{v}(w)$ the walk
such that for all $i\leq l(w)$:

$\eta^{-1}_{v}(w)_{i}\text{ is the class for }\sim_{\square}\text{ of the walk
}\varphi(u\odot w_{1}\dots w_{i}).$

It is straightforward that for any walk $w^{\prime}$ on
$\mathcal{U}^{\square}_{G}[a]$,
$\eta^{-1}_{w^{\prime}_{0}}\circ\eta(w^{\prime})=w^{\prime}$.

Let us turn to the proof. Consider a cycle $c$ on
$\mathcal{U}^{\square}_{G}[a]$. We will prove that it is square-decomposable.

  1. 1.

The cycle $\eta(c)$ is square-decomposable:

Since $c$ is a non-backtracking cycle, $\eta(c)$ is also a non-backtracking
cycle. Furthermore, since $c_{0}=c_{l(c)}$, there exists $p$ in $c_{0}$ such
that $\varphi(p\eta(c))\in c_{0}$, therefore
$\varphi(p\eta(c))\sim_{\square}p$. Then we can use Corollary 4.13 repeatedly
to have

$\psi_{p_{l(p)-1}\mapsto p_{l(p)}}\circ\cdots\circ\psi_{p_{0}\mapsto
p_{1}}(\varphi(p\eta(c)))\sim_{\square}\psi_{p_{l(p)-1}\mapsto
p_{l(p)}}\circ\cdots\circ\psi_{p_{0}\mapsto p_{1}}(p).$

This is rewritten into $\eta(c)\sim_{\square}p_{l(p)}$ (empty cycle), which
means that $\eta(c)$ is square-decomposable. Let us consider $(q^{(i)})_{0\leq
i\leq l}$ a square decomposition of $\eta(c)$.

  2. 2.

The sequence $(\eta^{-1}_{c_{0}}(q^{(i)}))_{0\leq i\leq l}$ is a square
decomposition of $c$:

It is clear that $\eta^{-1}_{c_{0}}(\eta(c))=c$ and
$\eta^{-1}_{c_{0}}(\eta(c_{0}))=c_{0}$ (empty cycle). Therefore, it is
sufficient to prove that for all $i$ such that $0\leq i<l$,
$\eta^{-1}_{c_{0}}(q^{(i)})$ and $\eta^{-1}_{c_{0}}(q^{(i+1)})$ differ by a
square.

Considering such integer $i$, we can assume that
$q^{(i+1)}=q^{(i)}\oplus_{k}s$ for some square $s$ and index $k$ (the other
possible case is processed similarly). For any vertex $v$ of
$\mathcal{U}^{\square}_{G}[a]$ such that $\eta(v)=s_{0}$, we have that
$\eta^{-1}_{v}(s)$ is a square in $\mathcal{U}^{\square}_{G}[a]$. Indeed, it
is non-backtracking, and it is a cycle since $v$ and $v\odot s$ differ by a
square.

It is straightforward to check that
$\eta^{-1}_{c_{0}}(q^{(i+1)})=\eta^{-1}_{c_{0}}(q^{(i)})\oplus_{k}\eta^{-1}_{v}(s)$,
where $v=\eta^{-1}_{c_{0}}(q^{(i)})_{k}$. Since $\eta^{-1}_{v}(s)$ is a
square, we have that $\eta^{-1}_{c_{0}}(q^{(i)})$ and
$\eta^{-1}_{c_{0}}(q^{(i+1)})$ differ by a square. This concludes the proof.∎

###  4.4  When $|\mathcal{U}^{\square}_{G}|=+\infty$, the gap function is
linear

[CM18] works in the context of four-cycle-hom-free graphs, which is exactly
the condition for the universal cover and the square cover to be equal. In
this context, Corollary 5.6 in _op.cit._ restated in our notation is:

######  Theorem 4.22 ([CM18]).

Let $G$ be a four-cycle-hom-free graph. $\gamma_{G}=\Theta(1)$ if and only if
$\mathcal{U}_{G}$ is finite.

Starting from this section, we extend this work by characterising the
equivalence classes of $\gamma_{G}$ for general graphs by using the square
cover. Notice however that Chandgotia and Marcus’ result holds in any
dimension while we restricted our attention to dimension 2.

We generalise the “infinite” case of Theorem 4.22 as follows:

######  Theorem 4.23.

If the square cover $\mathcal{U}^{\square}_{G}$ of $G$ is infinite, then
$\gamma_{G}(n)=\Theta(n)$.

###### Proof.

Let us fix some vertex $a$ of $G$. Since $\mathcal{U}^{\square}_{G}$ is
infinite and the degree of every vertex is less than $|V_{G}|$, for all $n$
there exists a path $p_{n}$ on $G$ such that $\pi_{a}(p_{n})$ is at distance
$2n$ from $\pi_{a}(a)$ in $\mathcal{U}^{\square}_{G}[a]$. Let
$a_{0},\ldots,a_{2n}$ be walks on $G$ such that
$\pi_{a}(a_{0})\cdots\pi_{a}(a_{2n})$ is a walk (of length $2n$) from
$\pi_{a}(a)$ to $\pi_{a}(p_{n})$ in $\mathcal{U}^{\square}_{G}[a]$. We denote
$u:=aa_{2}\cdots a_{2n}$ its image for $\eta$, and $v:=(aa_{2})^{n}a$. Let us
prove that $d_{G}(u,v)\geq n$.

Take some $x\in X_{G}$ such that $x|_{\llbracket
0,2n\rrbracket\times\\{0\\}}=u$ and $x|_{\llbracket
0,2n\rrbracket\times\\{k\\}}=v$ for some $k<n$. We know by Proposition 4.17
that there exists a unique configuration $z$ of
$X_{\mathcal{U}^{\square}_{G}}$ such that $z_{0,0}=\pi_{a}(a)$ and
$\eta(z_{\textbf{i}})=x_{\textbf{i}}$ for all $\textbf{i}\in\mathbb{Z}^{2}$.
As a consequence, $z_{2n,0}$ is the class $\pi_{a}(p_{n})$, and since
$\pi_{a}(v)=\pi_{a}(a)$ (empty cycle), $z_{2n,k}=z_{0,k}$. By triangular
inequality,

$d_{\mathcal{U}^{\square}_{G}}(z_{0,0},z_{2n,0})\leq
d_{\mathcal{U}^{\square}_{G}}(z_{0,0},z_{0,k})+d_{\mathcal{U}^{\square}_{G}}(z_{0,k},z_{2n,k})+d_{\mathcal{U}^{\square}_{G}}(z_{2n,k},z_{2n,0})\leq
2k.$

It follows that $k\geq n$. We conclude that $\gamma_{G}(2n)\geq n$ for all
$n\geq 1$, which implies that $\gamma_{G}(n)=\Theta(n)$. ∎

##  5 Writing cycles as trees of simple cycles

We use a representation of cycles on $G$ as _cacti_ , which are rooted finite
ordered trees whose vertices are labelled with simple cycles of $G$ satisfying
some conditions that allow to ’glue’ them together. This construction will be
used when proving that some Hom shifts have logarithmic gluing gap (Theorem
6.15) by applying some transformations ”in parallel” to different parts of a
large cycle.

###  5.1 Definition of a cactus

Here is an inductive definition of a cactus.

######  Definition 5.1.

A cactus of depth $\boldsymbol{1}$, also called a leaf, is an element of
$\mathcal{C}_{G}^{0}$. For all other integer $n>1$, a cactus of depth
$\boldsymbol{n}$ is a triple $C=(\xi,s,\chi)$ such that
$\xi\in\mathcal{C}^{0}_{G}$, $s=(s_{1},\dots,s_{d})$ is a sequence of cacti
whose depth is strictly less than $n$, and $\chi=(\chi_{1},\dots,\chi_{d})$ is
a non-decreasing sequence of non-negative integers such that:

  * •

For all $i$, $\chi_{i}\leq l(\xi(C))$ and $\xi(s_{i})_{0}=\xi_{\chi_{i}}$.

  * •

At least one element of $s$ has depth exactly $n-1$.

We use the notation $(\xi(C),s(C),\chi(C)):=C$ whenever $C$ has depth at most
two, and denote by $d(C)$ the common length of $s(C)$ and $\chi(C)$.
Furthermore, we denote depth of $C$ by $n(C)$.

######  Definition 5.2.

A cactus forest is a sequence of cacti $(C_{1},\ldots C_{k})$ such that
$\xi(C_{j})_{0}$ does not depend on $j$. Its depth, denoted by
$n(C_{1},\ldots,C_{k})$, is equal to $\max_{i}n(C_{i})$.

######  Notation 5.3.

For every cactus $C$ and every $k\leq n(C)$, we call $k$-th level of $C$ and
denote $\ell_{k}(C)$ the set of cacti defined inductively by:

$\begin{array}[]{ll}\ell_{1}(C)=\\{C\\}\\\ \ell_{k}(C)=\bigcup_{1\leq i\leq
d(C)}\ell_{k-1}(s(C)_{i})\quad\text{when }k\geq 2.\end{array}$

Furthermore, for all $k>n(C)$, we set $\ell_{k}(C)=\emptyset$. For a cactus
forest $(C_{1},\ldots,C_{l})$, and $k\leq n(C_{1},\ldots,C_{l})$, its $k$-th
level $\ell_{k}(C_{1},\ldots,C_{l})$ is defined as

$\ell_{k}(C_{1},\ldots,C_{l})=\bigcup_{j}\ell_{k}(C_{j}).$

######  Example 5.4.

A cactus can be represented as labeled rooted tree, although we will not use
such a representation formally:

abc

1012$abca$$aa$$bcab$$cac$$abca$

.

Figure 6: A graph $G$ and a cactus of depth $3$ on $G$. Every subtree is a
cactus $C$ whose root is labeled by $\xi(C)$, whose children are $s(C)$
(ordered from bottom to top) and where the edge to each child is labeled by
the corresponding $\chi_{i}(C)$.

###  5.2 Cycle $\pi(C)$ encoded by a cactus $C$

The purpose of cacti is to encode cycles on $G$. It is clear how a cactus $C$
of depth $1$ encodes $\xi(C)$. The cycle encoded by a cactus $C$ of depth
$n>1$ is obtained by ‘plugging’ in $\xi(C)$ the cycles encoded by the cacti in
the sequence $s(C)$ in order, on positions of $\xi(C)$ determined by the
sequence $\chi(C)$. We provide a formal definition below.

######  Notation 5.5.

For two cycles $c$ and $c^{\prime}$ and $k\leq l(c)$ such that
$c_{k}=c^{\prime}_{0}$, the cycle $c{\oplus}_{k}c^{\prime}$ is defined by:

$c{\oplus}_{k}c^{\prime}=c_{0}\ldots c_{k-1}c^{\prime}c_{k+1}\ldots c_{l(c)}.$

More generally, consider a sequence of cycles $c^{(0)},c^{(1)},\dots,c^{(m)}$
with $m\geq 2$ and a non-decreasing sequence of integers
$k_{1},\dots,k_{m}\leq l(c)$ such that for all $0<j\leq m$,
$c^{(0)}_{k_{j}}=c^{(j)}_{0}$. We define inductively a cycle
$c^{(0)}\oplus_{k_{1}}c^{(1)}\ldots\oplus_{k_{m}}c^{(m)}$ by:

$c^{(0)}\oplus_{k_{1}}c^{(1)}\ldots\oplus_{k_{m}}c^{(m)}=(c^{(0)}\oplus_{k_{1}}c^{(1)}\ldots\oplus_{k_{m-1}}c^{(m-1)})\oplus_{k_{m}+\sum_{j=1}^{m-1}l(c^{(j)})}c^{(m)}$

######  Remark 5.6.

This reflects what we mean by ‘plugging’ successively the cycles $c^{(j)}$ in
$c$ at positions $k_{j}$.

######  Notation 5.7.

Every cactus $C$ is said to _encode_ a cycle $\pi(C)$, which we define
inductively. When $C$ is a leaf, $\pi(C):=C$. For any depth $n\geq 2$, and $C$
a cactus of depth $n$, we set:

$\pi(C)=\xi(C)\oplus_{\chi(C)_{0}}\pi(s(C)_{0})\oplus_{\chi(C)_{1}}\pi(s(C)_{1})\oplus\cdots\oplus_{\chi(C)_{d(C)}}\pi(s(C)_{d(C)}).$

As well, a cactus forest $(C_{1},\ldots,C_{k})$ encodes the cycle

$\pi(C_{1})\odot\pi(C_{2})\ldots\odot\pi(C_{k}),$

which we denote by $\pi(C_{1},\ldots,C_{k})$.

######  Example 5.8.

For the cactus $C$ defined in Example 5.4, the cycle $\pi(C)$ is:

$\pi(C)=aabcacabcabca.$

###  5.3 Encoding any cycle with a cactus of bounded depth

A cycle may be encoded by more than one cacti:

######  Example 5.9.

Let $C$ be the cactus defined in Example 5.4. The cycle $\pi(C)$ is encoded by
another cactus $C^{\prime}\neq C$ (which means that $\pi(C^{\prime})=\pi(C)$):

abc2220$abca$$aa$$cac$$cabc$$cabc$

However, we can encode any cycle with a cactus forest which has the nice
property of having bounded depth:

######  Lemma 5.10.

For any cycle $c$ on a graph $H$, there exists a cactus forest
$(C_{1},\ldots,C_{k})$ such that $\pi(C_{1},\ldots,C_{k})=c$ with
$n(C_{1},\ldots,C_{k})\leq|V_{H}|$.

###### Proof.

Let us consider a graph $H$ and let us prove the statement for this graph, by
induction on $|V_{H}|$. When $|V_{H}|=1$, since we assumed that all graph
considered are connected, $H$ consists in a unique vertex $a$ with a self
loop. Therefore the statement is straightforward, since all the cycles on $H$
are of the form $a\ldots a$. Let us assume that we have proved the lemma
whenever $|V_{H}|\leq n$ for some integer $n\geq 1$ and assume that
$|V_{H}|=n+1$. Let us consider a cycle $c$ on $H$.

Without loss of generality we can assume that $c_{j}=c_{0}$ implies that $j=0$
or $j=l(c)$. Indeed we can write $c$ as a product for $\odot$ of cycles which
satisfy this property. It is sufficient then to prove that each of these
cycles is encoded by a cactus forest (in practice we will prove that it is
encoded by a cactus) in order to prove that $c$ is encoded by a cactus forest.

It is then straightforward that there exist a simple cycle $d$ which begins
and ends at $c_{0}$ and a sequence of cycles $d^{(1)},\ldots,d^{(k)}$ in which
$c_{0}$ does not appear, and integers $l_{1},\ldots,l_{k}$ such that

$c=d\oplus_{l_{1}}d^{(1)}\ldots\oplus_{l_{k}}d^{(k)}.$

The cycles $d^{(j)}$ can be seen as the maximal cycles which appear in $c$ in
which $c_{0}$ does not appear. Since the cycles $d^{(1)},\ldots,d^{(k)}$ are
on the subgraph $H^{\prime}$ of $H$ on vertices $V_{H}\backslash\\{c_{0}\\}$,
by induction each of these cycles is encoded by a cactus forest of depth no
larger than $|V_{H}|-1$. This implies that $c$ is encoded by a cactus forest
of depth no larger than $|V_{H}|$.

∎

######  Remark 5.11.

Notice that in Lemma 5.10, the bound $|V_{H}|$ is tight only if there is a
vertex of $H$ with a self-loop.

##  6  When $|\mathcal{U}^{\square}_{G}|<+\infty$, $\gamma_{G}(n)=O(\log(n))$

In this section, we prove that when the square-cover of $G$ is finite,
$\gamma_{G}(n)=O(\log(n))$. As a consequence of Proposition 4.18 and
Proposition 4.21 it is sufficient to prove that if $G$ is square-decomposable,
then $\gamma_{G}(n)=O(\log(n))$. This is stated as Theorem 6.15 in Section
6.3. In Section 6.1, we provide a way to transform a cycle $c$ on which have
been ‘attached’, by the operation $\odot$, additional spines, into a power of
a spine. By ‘transforming’ a cycle $c$ into another one which has the same
length we mean that it is possible to find a walk in $\Delta_{G}^{l(c)}$ which
begins at the cycle $c$ and ends on the second one. We use this term
systematically in this section, for simplicity. Then in Section 6.2 we show
that these transformations can be parallelized in an ‘efficient’ way. This
parallelization will be a central tool in the proof of Theorem 6.15.

###  6.1 Transforming cycles with additional spines

In this section, we show how to ‘transform’ a cycle of the form $t^{k}\odot
u$, where $u$ is a cycle and $t$ is a spine on $u_{0}$, into $t^{k+l(u)/2}$.
In practice, we only need to consider the case $k=2\lambda_{G}$ and
$u=c^{\lambda_{G}}$, where $\lambda_{G}$ is a characteristic of the graph $G$
defined below. Furthermore, we find a bound on the distance $d_{G}$ between
the cycles $t^{2\lambda_{G}}\odot c^{\lambda_{G}}$ and
$t^{2\lambda_{G}+\lambda_{G}l(c)/2}$.

Although the distance $d_{G}$ provides us, by restriction, with a distance
between cycles, we need, in order to parallelize these transformations, to use
another distance that we denote by $d_{G}^{\mathcal{R}}$ (see Notation 6.1).
From the bounds obtained here on $d_{G}^{\mathcal{R}}$ for $t^{k}\odot u$, we
are able to obtain bounds on $d_{G}^{\mathcal{R}}$ for larger words in which
the transformations are executed in parallel (in Section 6.2).

Lemma 6.2 provides a relation between $d_{G}$ and $d_{G}^{\mathcal{R}}$, which
enables us to recover bounds on distances for $d_{G}$ from bounds on distances
for $d_{G}^{\mathcal{R}}$.

The main result of this section is Corollary 6.5, which derives from the
intermediate results in Lemma 6.3 and Lemma 6.4.

######  Notation 6.1.

For all cycles $c,c^{\prime}$ on $G$ such that $l(c)=l(c^{\prime})$ and
$c_{0}=c^{\prime}_{0}$, denote $c\mathcal{R}_{0}c^{\prime}$ (resp.
$c\mathcal{R}_{1}c^{\prime}$) when there exists a left (resp. right) shift of
$c^{\prime}$ which is neighbor of $c$ in the graph $\Delta_{G}^{l(c)}$. Also
denote by $d_{G}^{\mathcal{R}}(c,c^{\prime})$ the minimal $m$ such that there
is a sequence $(c^{(k)})_{0\leq k\leq m}$ of cycles such that $c^{(0)}=c$,
$c^{(m)}=c^{\prime}$ and for all $k<m$, $c^{(k)}\mathcal{R}_{0}c^{(k+1)}$ or
$c^{(k)}\mathcal{R}_{1}c^{(k+1)}$.

######  Lemma 6.2.

For all cycles $c,c^{\prime}$ such that $l(c)=l(c^{\prime})$, we have the
inequality

$d_{G}(c,c^{\prime})\leq 2d_{G}^{\mathcal{R}}(c,c^{\prime}).$

###### Proof.

First consider the case $d_{G}^{\mathcal{R}}(c,c^{\prime})=1$. Let us assume
that $c\mathcal{R}_{0}c^{\prime}$ (the other case is symmetric). This means
that there is a left shift of $c$ which is a neighbor of both $c^{\prime}$ and
$c$ in $\Delta_{G}^{l(c)}$. As a consequence $d_{G}(c,c^{\prime})\leq
2=2d_{G}^{\mathcal{R}}(c,c^{\prime})$.

For the general case, we have for any $c,c^{\prime}$:

$2d_{G}^{\mathcal{R}}(c,c^{\prime})=2\sum_{k=0}^{m}d_{G}^{\mathcal{R}}(c^{(k)},c^{(k+1)})\geq\sum_{k=0}^{m}d_{G}(c^{(k)},c^{(k+1)})\geq
d_{G}(c,c^{\prime}),$

where $m=d_{G}^{\mathcal{R}}(c,c^{\prime})$ and $(c^{(k)})_{0\leq k\leq m}$
are as defined in Notation 6.1. ∎

######  Lemma 6.3.

Let $c,c^{\prime}$ be two non-backtracking cycles which differ by a square and
$t$ a spine on $c_{0}$. Assume that $l(c)\geq l(c^{\prime})$. Then

$d^{\mathcal{R}}_{G}(c,t^{(l(c)-l(c^{\prime}))/2}\odot
c^{\prime})\leq\max\left(2,\frac{l(c)-l(c^{\prime})}{2}\right).$

###### Proof.

We recall in Figure 7 the three possible ways two non-backtracking cycles
$c,c^{\prime}$ can differ by a square. In particular we have
$(l(c)-l(c^{\prime}))\in 2\mathbb{N}$.

$c_{n}$$c^{\prime}_{n}$(i)$c_{n}$$c_{n+1}$(ii)$c_{n}$$c_{n+1}$$c_{n+2}$$c_{n-1-k}=c_{n+3+k}$(iii)
Figure 7: The three ways two non-backtracking cycles can differ by a square.

We consider each case one by one. In each of the cases
$(l(c)-l(c^{\prime}))\in\\{0,2,4\\}$ the table below provide a sequence of
cycles from $c$ to $t^{l(c)-l(c^{\prime})/2}\odot c^{\prime}$ which yields the
statement in this case.

  1. (i)

$\boldsymbol{l(c)-l(c^{\prime})=0}$:
$c=$$c_{0}$$\dots$$\dots$$c_{n-1}$$c_{n}$$c_{n+1}$$\dots$$\rho_{l}(c)\ni$$c_{1}$$\dots$$c_{n-1}$$c_{n}$$c_{n+1}$$\dots$$\dots$$c^{\prime}=$$c_{0}$$\dots$$\dots$$c_{n-1}$$c^{\prime}_{n}$$c_{n+1}$$\dots$

  2. (ii)

$\boldsymbol{l(c)-l(c^{\prime})=2}$:
$c=$$c_{0}$$\dots$$\dots$$c_{n-1}$$c_{n}$$c_{n+1}$$c_{n+2}$$\dots$$\dots$$\rho_{r}(c)\ni$$t_{1}$$c_{0}$$\dots$$\dots$$c_{n-1}$$c_{n}$$c_{n+1}$$c_{n+2}$$\dots$$t\odot
c^{\prime}=$$t_{0}$$t_{1}$$c_{0}$$\dots$$\dots$$c_{n-1}$$c_{n+2}$$\dots$$\dots$

  3. (iii)

$\boldsymbol{l(c)-l(c^{\prime})=4}$:
$c=$$c_{0}$$\dots$$\dots$$c_{n-1}$$c_{n}$$c_{n+1}$$c_{n+2}$$c_{n+3}$$\dots$$\dots$$\rho_{r}(c)\ni$$t_{1}$$c_{0}$$\dots$$\dots$$c_{n-1}$$c_{n}$$c_{n+1}$$c_{n+2}$$c_{n+3}$$\dots$$\tilde{c}=$$t_{0}$$t_{1}$$c_{0}$$\dots$$\dots$$c_{n-1}$$c_{n}$$c_{n+3}$$\dots$$\dots$$\rho_{r}(\tilde{c})\ni$$t_{1}$$t_{0}$$t_{1}$$c_{0}$$\dots$$\dots$$c_{n-1}$$c_{n}$$c_{n+3}$$\dots$$t^{2}\odot
c^{\prime}=$$t_{0}$$t_{1}$$t_{0}$$t_{1}$$c_{0}$$\dots$$\dots$$c_{n-1}$$c_{n+4}$$\dots$

When $l(c)-l(c^{\prime})>4$, let $k>0$ be such that for all $i\leq k$,
$c_{n+3+i}=c_{n-1-i}$ and $c_{n+3+k+1}\neq c_{n-1-k-1}$. By applying the case
$l(c)-l(c^{\prime})=4$, we have

$d_{G}^{\mathcal{R}}(c,t^{2}\odot c^{\prime\prime})\leq
2\quad\text{where}\quad c^{\prime\prime}=c_{0}\ldots c_{n-1}c_{n+4}\ldots
c_{l(c)}.$

We thus only need to prove that $d_{G}^{\mathcal{R}}(t^{2}\odot
c^{\prime\prime},t^{(l(c)-l(c^{\prime}))/2}\odot c^{\prime})\leq k$. For this
it is sufficient to see that

$\forall i\in\llbracket 2,k+1\rrbracket,\ d_{G}^{\mathcal{R}}(t^{i}\odot
c^{(i)},t^{i+1}\odot c^{(i+1)})=1,$

where we set

$c^{(i)}=c_{0}\ldots c_{n-1-(i-2)}c_{n+4+(i-2)}\ldots c_{l(c)}.$

∎

By a repeated application of the previous lemma, we can transform a simple
cycle into the power of a spine in bounded time:

######  Lemma 6.4.

There exists a constant $\lambda_{G}$ such that, for any cycle $c$ which is
decomposable into squares and spine $t$ on $c_{0}$, we have:

$d^{\mathcal{R}}_{G}(t^{\lambda_{G}}\odot
c,t^{\lambda_{G}+l(c)/2})\leq\lambda_{G}\qquad\text{and}\qquad l(c)\leq
2\lambda_{G}.$

###### Proof.

Recall that $m_{c}$ denotes the area of $c$ (see Definition 4.7). Denote by
$\mathcal{D}_{c}$ the set of decompositions of length $m_{c}$ of a cycle $c$.
We define:

$\lambda_{G}:=\max_{c\in\mathcal{C}_{G}^{0}}\min_{\left(c^{(i)}\right)\in\mathcal{D}_{c}}\left(\sum_{i\leq
m_{c}}\max\left(2,\left|\frac{l(c^{(i+1)})-l(c^{(i)})}{2}\right|\right)\right).$

The definition should make clear that $l(c)\leq 2\lambda_{G}$ for all square-
decomposable cycles $c$. Let $(c^{(i)})_{0\leq i\leq m_{c}}$ be a square
decomposition of $c$ that realizes the minimum in the definition of
$\lambda_{G}$. For all $j\leq m_{c}$, let us set
$\gamma^{(j)}:=t^{\lambda_{G}+(l(c)-l(c^{(j)}))/2}\odot c^{(j)}$. This
sequence is well-defined because for all $j$, $\sum_{0\leq
k<j}\left|\frac{l(c^{(k+1)})-l(c^{(k)})}{2}\right|\leq\lambda_{G}$, and as a
consequence:

$\lambda_{G}+(l(c)-l(c^{(j)}))/2\geq 0.$

As a consequence of Lemma 6.3, for all $j\leq m_{c}-1$,
$m_{c}d^{\mathcal{R}}_{G}(\gamma^{(j)},\gamma^{(j+1)})\leq\lambda_{G}$. Thus
by triangular inequality we get the statement of the lemma. ∎

######  Corollary 6.5.

Let $c$ be a cycle which decomposable into squares and let $t$ be a spine on
$c_{0}$. We have:

$d^{\mathcal{R}}_{G}(t^{\lambda_{G}}\odot
c^{\lambda_{G}},t^{\lambda_{G}+\lambda_{G}l(c)/2})\leq\lambda_{G}^{2}.$

###  6.2 Parallelization

In this section, we show how to perform the transformations defined in Section
6.1 in parallel on different parts of a cycle.

We introduce (Notation 6.6) $\Gamma^{\textbf{r}}_{\textbf{z}}(d)$ which is a
cycle obtained by “inserting” a sequence of cycles r inside the cycle $d$ at
positions given by z. This lets us consider transformations on different parts
of $d$ while leaving unchanged the inserted cycles of the sequence r.

The main results of this section are Lemma 6.10 and Lemma 6.11, which prove
respectively that the words of r in $\Gamma^{\textbf{r}}_{\textbf{z}}(d)$ can
be moved in parallel; and that transformations such as the ones of Section 6.1
can be performed in parallel on the different parts of $d$.

######  Notation 6.6.

Let $\textbf{z}=(\textbf{z}_{0},\dots,\textbf{z}_{l})$ be a sequence of non-
negative integers and $\textbf{r}=(r^{(j)})_{0\leq j\leq l}$ be a sequence of
cycles all beginning and ending at some vertex $a\in V_{G}$. For any cycle $d$
of length $\sum_{j=0}^{l}\textbf{z}_{j}$ such that for all $j\in\llbracket
0,l\rrbracket$, $d_{\textbf{z}_{0}+\ldots+\textbf{z}_{j}}=d_{0}=a$, we define:

$\Gamma^{\textbf{r}}_{\textbf{z}}(d):=d_{|\llbracket
0,\textbf{z}_{0}\rrbracket}\odot r^{(0)}\odot d_{|\textbf{z}_{0}+\llbracket
0,\textbf{z}_{1}\rrbracket}\odot\ldots\odot
d_{|\textbf{z}_{0}+\ldots+\textbf{z}_{l-1}+\llbracket
0,\textbf{z}_{l}\rrbracket}\odot r^{(l)}.$

######  Lemma 6.7.

For:

  * •

any sequence $\textbf{r}=(r^{(j)})_{0\leq j\leq l}$ of cycles all beginning
and ending at some vertex $a\in V_{G}$ and any sequence
$\textbf{z}=(z^{(j)})_{0\leq j\leq l}$ of integers,

  * •

any sequence $(\epsilon_{k})_{0\leq k\leq m-1}$ in $\\{0,1\\}^{m}$,

  * •

any double sequence of cycles $(c^{(k,i)})_{(k,i)\in\llbracket
0,m\rrbracket\times\llbracket 0,l\rrbracket}$ which all begin and end at $a$,
such that $l\left(c^{(k,i)}\right)=z_{i}$ and
$c^{(k+1,i)}\mathcal{R}_{\epsilon_{k}}c^{(k,i)}$ for all $(k,i)$,

we have:

$d^{\mathcal{R}}_{G}(\Gamma^{\textbf{r}}_{\textbf{z}}(c^{(0,0)}\odot\dots\odot
c^{(0,l)}),\Gamma^{\textbf{r}}_{\textbf{z}}(c^{(m,0)}\odot\dots\odot
c^{(m,l)}))\leq m.$

###### Proof.

It is sufficient to see for all $k<m$, we have

$\Gamma^{\textbf{r}}_{\textbf{z}}(c^{(k+1,0)}\odot\dots\odot
c^{(k+1,l)})\mathcal{R}_{\epsilon_{k}}\Gamma^{\textbf{r}}_{\textbf{z}}(c^{(k,0)}\odot\dots\odot
c^{(k,l)}).$

This derives from the fact that for all $i$,
$r^{(i)}\mathcal{R}_{\epsilon}r^{(i)}$ and that the second letter and the
penultimate letter of $r^{(i)}$ are both neighbors of $a$. ∎

######  Remark 6.8.

If we have a sequence of cycles

$(c^{(i,j)})_{\begin{subarray}{c}1\leq i\leq k\\\ 0\leq j\leq
l_{i}\end{subarray}}$

such that $c^{(i,j)}\mathcal{R}_{0}c^{(i,j+1)}$ for all $i$ and $j<l_{i}$, we
can complete this sequence into

$(c^{(i,j)})_{\begin{subarray}{c}1\leq i\leq k\\\ 0\leq j\leq
L\end{subarray}},$

where $L:=\max_{i}l_{i}$, by setting $c^{(i,j)}:=c^{(i,l_{i})}$ when
$j>l_{i}$, and then apply Lemma 6.7 in order to get:

$d^{\mathcal{R}}_{G}(\Gamma^{\textbf{r}}_{\textbf{z}}(c^{(1,0)}\odot
c^{(2,0)}\odot\ldots\odot
c^{(k,0)}),\Gamma^{\textbf{r}}_{\textbf{z}}(c^{(1,L)}\odot
c^{(2,L)}\odot\ldots\odot c^{(k,L)}))\leq L,$

where $\textbf{z}=(l(c^{(i)}))_{1\leq i\leq k}$.

######  Lemma 6.9.

Let us fix $\textbf{r}=(r^{(j)})_{0\leq j\leq l}$ a sequence of cycles all
beginning and ending at some vertex $a\in V_{G}$. Let us also consider a pair
$(\textbf{z}$, $\textbf{z}^{\prime})$ for which there exists an increasing
sequence $(j_{i})_{1\leq i\leq 2\tau}$ of integers in $\llbracket
0,l\rrbracket$ such that:

  * •

$\forall i\in\llbracket 1,2t\rrbracket$,
$\textbf{z}_{j_{i}}=\textbf{z}^{\prime}_{j_{i}}+2\cdot(-1)^{i}$;

  * •

for all $j$ which are not in the sequence $(j_{i})_{1\leq i\leq 2\tau}$,
$\textbf{z}^{\prime}_{j}=\textbf{z}_{j}$.

Then, for all cycles $d$ such that $\Gamma^{\textbf{r}}_{\textbf{z}}(d)$ and
$\Gamma^{\textbf{r}}_{\textbf{z}^{\prime}}(d)$ are well defined, we have

$d_{G}^{\mathcal{R}}(\Gamma^{\textbf{r}}_{\textbf{z}}(d),\Gamma^{\textbf{r}}_{\textbf{z}^{\prime}}(d))=1.$

###### Proof.

That $\Gamma^{\textbf{r}}_{\textbf{z}}(d)$ and
$\Gamma^{\textbf{r}}_{\textbf{z}^{\prime}}(d)$ are well-defined means that for
all $j$,

$d_{|\textbf{z}_{0}+\ldots+\textbf{z}_{j}}=d_{|\textbf{z}^{\prime}_{0}+\ldots+\textbf{z}^{\prime}_{j}}=a.$

For any $j$, as a consequence of the hypothesis, the difference $\sum_{i\leq
j}\textbf{z}^{\prime}_{i}-\sum_{i\leq j}\textbf{z}_{i}$ is equal to $0$ or
$2$. Whenever $\sum_{i\leq j}\textbf{z}^{\prime}_{i}-\sum_{i\leq
j}\textbf{z}_{i}=2$, since

$d_{|\textbf{z}_{0}+\ldots+\textbf{z}_{j}}=d_{|\textbf{z}^{\prime}_{0}+\ldots+\textbf{z}^{\prime}_{j}}=a,$

this means that
$d_{|\textbf{z}^{\prime}_{0}+\ldots+\textbf{z}^{\prime}_{j}+\llbracket-2,0\rrbracket}$
is a spine on $a$ that we denote by $t$. Therefore $d$ can be decomposed as
follows:

$d=\left(d^{(0)}\odot t^{(0)}\right)\odot\ldots\odot\left(d^{(l)}\odot
t^{(l)}\right),$

where $t^{(j)}$ is a spine on $a$ when
$\sum_{i<j}\textbf{z}^{\prime}_{i}-\sum_{i<j}\textbf{z}_{i}=2$ and $t^{(j)}=a$
(empty cycle) otherwise. This is illustrated on Figure 8.

$d^{(0)}$$d^{(1)}$$d^{(2)}$$d^{(3)}$$t^{(0)}$$t^{(2)}$$\textbf{z}_{0}$$\textbf{z}_{1}$$\textbf{z}_{2}$$\textbf{z}_{3}$$\textbf{z}^{\prime}_{0}$$\textbf{z}^{\prime}_{1}$$\textbf{z}^{\prime}_{2}$$\textbf{z}^{\prime}_{3}$
Figure 8: Decomposition of $d$ in the case where the sequence $(j_{i})$ is
$(0,1,2,3)$.

Furthermore,

$\Gamma^{\textbf{r}}_{\textbf{z}}(d)=\left(d^{(0)}\odot\left(t^{(0)}\odot
r^{(0)}\right)\right)\odot\ldots\odot\left(d^{(l)}\odot\left(t^{(l)}\odot
r^{(l)}\right)\right)$

and

$\Gamma^{\textbf{r}}_{\textbf{z}^{\prime}}(d)=\left(d^{(0)}\odot\left(r^{(0)}\odot
t^{(0)}\right)\right)\odot\ldots\odot\left(d^{(l)}\odot\left(r^{(l)}\odot
t^{(l)}\right)\right)$

Now the fact that $t\odot r^{(i)}\mathcal{R}_{0}r^{(i)}\odot t$ for all $i$,
together with Lemma 6.7, implies the result. ∎

######  Lemma 6.10.

Let us fix $\textbf{r}=(r^{(j)})_{0\leq j\leq l}$ a sequence of cycles all
beginning and ending at some vertex $a\in V_{G}$. Let $c$ be a cycle
decomposable into squares and $t$ a spine on $c_{0}$. For all $n\geq 0$, we
have

$d_{G}^{\mathcal{R}}(\Gamma^{\textbf{r}}_{\textbf{z}}(t^{\lambda_{G}l(c)/2}\odot
c^{(2^{n}-1)\lambda_{G}}),\
\Gamma^{\textbf{r}}_{\textbf{z}}(t^{2^{n-1}\lambda_{G}l(c)}))\leq
30\lambda_{G}^{2}n$

where $\textbf{z}:=(\lambda_{G}l(c),k_{1}l(c),\ldots,k_{l}l(c))$ for any
sequence of positive integers $(k_{j})_{1\leq j\leq l}$ such that
$k_{1}+\ldots+k_{l}=(2^{n}-1)\lambda_{G}$.

#### Sketch of the proof:

We transform a cycle of the form $t^{k}\odot c^{2^{n}}$ into a trivial cycle
(containing only spines). To do this, we move enough copies of the spine $t$
from the left to the center of the word that we are able to use apply results
of Section 6.1 at the center of the word. This transforms a number of
occurrences of $c$ at the center into spines; after this the word consists in
two identical blocks of the form $t^{k}\odot c^{2^{n-1}}$. We repeat the
previous transformation on each of these two blocks, etc. Straightforwardly,
this ‘dichotomic’ process finishes in time which is linear in $n$.

###### Proof.

When $l(c)=2$, there is nothing to prove. Let us assume that $l(c)\geq 4$.

  1. 1.

The dichotomic process: For all $k\leq n$, let us denote:

$\gamma_{k}=\left(t^{\lambda_{G}l(c)/2}\odot
c^{\left(2^{n-k}-1\right)\lambda_{G}}\right)^{2^{k}},$

where $\lambda_{G}$ is as defined in Lemma 6.4. In particular
$\gamma_{0}=t^{l(c)\lambda_{G}/2}\odot c^{(2^{n}-1)\lambda_{G}}$ and
$\gamma_{n}=t^{2^{n-1}\lambda_{G}l(c)}$.

Let us prove that there are sequences $\textbf{z}^{k}$, $k\leq n$, such that
$\textbf{z}^{0}=\textbf{z}$ and

$\forall k<n,\
d_{G}^{\mathcal{R}}(\Gamma^{\textbf{r}}_{\textbf{z}^{k}}(\gamma_{k}),\Gamma^{\textbf{r}}_{\textbf{z}^{k+1}}(\gamma_{k+1}))\leq{15\lambda_{G}^{2}}.$

  2. 2.

From $\gamma_{k-1}$ to $\gamma_{k}$ \- moving spines: Let us assume that
$\textbf{z}^{0},\dots,\textbf{z}^{k-1}$ have been defined, where $k\geq 1$.
Let the sequence of cycles $(\gamma_{k,j})_{j\in\llbracket
0,2\lambda_{G}\rrbracket}$ be defined for all $k$ and $j$ as the concatenation
of $2^{k-1}$ identical words that we call blocks:

$\gamma_{k,j}=\left(t^{\lambda_{G}l(c)/2-j}\odot
c^{\left(2^{n-k}-1\right)\lambda_{G}}\odot t^{j}\odot
c^{2^{n-k}\lambda_{G}}\right)^{2^{k-1}}.$

Informally, for all $j$, $\gamma_{k,j+1}$ is obtained from $\gamma_{k,j}$ by
‘moving’ a spine $t$ from the left to the right inside each block. This will
also affect the sequence $\textbf{z}^{k,j}$ responsible for places of
insertions of $\mathbf{r}$. Then by Lemma 6.7,

$d^{\mathcal{R}}_{G}\left(\Gamma^{\textbf{r}}_{\textbf{z}^{k,j}}(\gamma_{k,j}),\Gamma^{\textbf{r}}_{\textbf{z}^{k,j}}(\gamma_{k,j+1})\right)=1.$

Let us construct a sequence $\left(\textbf{z}^{k,j}\right)_{j\in\llbracket
0,2\lambda_{G}\rrbracket}$, such that $\textbf{z}^{k,0}=\textbf{z}^{k-1}$. Let
us assume that this sequence has been defined for some $j<2\lambda_{G}$.

In the definition of $\Gamma^{\textbf{r}}_{\textbf{z}^{k,j}}(\gamma_{k,j})$ it
may happen that $\Gamma^{\textbf{r}}$ inserts an element of r in between
$t^{\lambda_{G}l(c)/2}$ and $t^{j}$, which changes the relative position of
the spine being moved in the $i$-th block when constructing $\gamma_{k,j+1}$
from $\gamma_{k,j}$. To cancel out this movement, we define a quantity
$\omega^{k,j+1}_{q}$ to be $1$ when this happens, and $0$ otherwise, and we
define:

     * •

$\textbf{z}^{k,j+1}_{0}=\textbf{z}^{k,j}_{0}-2\omega^{k,j+1}_{0}$;

     * •

for all $q>0$,
$\textbf{z}^{k,j+1}_{q}=\textbf{z}^{k,j}_{q}-2\omega^{k,j+1}_{q}+2\omega^{k,j+1}_{q-1}$.

Formally, denote $(\omega^{k,j+1}_{q})_{0\leq q\leq l}\in\\{0,1\\}^{l+1}$ such
that for all $q$, $\omega^{k,j+1}_{q}=1$ when there exists some
$i\in\llbracket 0,2^{k-1}-1\rrbracket$ for which

$\underbrace{\left(\lambda_{G}l(c)-2j\right)+\overbrace{i\cdot\lambda_{G}2^{n-k+1}l(c)}^{\text{the
spine is in block $i+1$}}}_{\text{position of spine $t$ before
moving}}<\underbrace{\textbf{z}^{k,j}_{0}+\ldots+\textbf{z}^{k,j}_{q}}_{\text{insertion
position of $r^{(q)}$}}$

and

$\textbf{z}^{k,j}_{0}+\ldots+\textbf{z}^{k,j}_{q}\leq\underbrace{\left(2^{n-k}\lambda_{G}l(c)-2j\right)+i\cdot\lambda_{G}2^{n-k+1}l(c)}_{\text{position
of spine $t$ after moving}},$

and $\omega^{k,j+1}_{q}=0$ otherwise.

From this definition, we have that

     * •

$\textbf{z}^{k,j+1}_{q}=\textbf{z}^{k,j}_{q}$ whenever
$\omega^{k,j+1}_{q}=\omega^{k,j+1}_{q-1}$ ;

     * •

$\textbf{z}^{k,j+1}_{q}=\textbf{z}^{k,j}_{q}+2$ whenever
$\omega^{k,j+1}_{q}=0$ and $\omega^{k,j+1}_{q-1}=1$ ;

     * •

$\textbf{z}^{k,j+1}_{q}=\textbf{z}^{k,j}_{q}-2$ whenever
$\omega^{k,j+1}_{q}=1$ and $\omega^{k,j+1}_{q-1}=0$.

Necessarily these two last types of indexes alternate. This implies that it is
possible to apply Lemma 6.9 in which $\textbf{z},\textbf{z}^{\prime}$ are
replaced respectively by $\textbf{z}^{k,j+1}$ and $\textbf{z}^{k,j}$.

By Lemma 6.9, we have:

$d^{\mathcal{R}}_{G}\left(\Gamma^{\textbf{r}}_{\textbf{z}^{k,j}}(\gamma_{k,j+1}),\Gamma^{\textbf{r}}_{\textbf{z}^{k,j+1}}(\gamma_{k,{j+1}})\right)=1.$

We have $\gamma_{k,0}=\gamma_{k-1}$, $\textbf{z}^{k,0}=\textbf{z}^{k-1}$ and
$\gamma_{k,2\lambda_{G}}=\gamma^{\prime}_{k}$ where:

$\gamma^{\prime}_{k}:=\left(t^{(l(c)/2-2)\lambda_{G}}\odot
c^{\left(2^{n-k}-1\right)\lambda_{G}}\odot t^{2\lambda_{G}}\odot
c^{2^{n-k}\lambda_{G}}\right)^{2^{k-1}}.$

Thus by triangular inequality,

$d^{\mathcal{R}}_{G}\left(\Gamma^{\textbf{r}}_{\textbf{z}^{k-1}}(\gamma_{k-1}),\Gamma^{\textbf{r}}_{\textbf{z}^{k,2\lambda_{G}}}(\gamma^{\prime}_{k})\right)\leq
4\lambda_{G}.$ (1)

In $\Gamma^{\textbf{r}}_{\textbf{z}^{k,2\lambda_{G}}}(\gamma^{\prime}_{k})$,
it may happen that the cycles $r^{(j)}$ appear inside an occurrence of
$t^{2\lambda_{G}}\odot c$. We change the sequence
$\textbf{z}^{k,2\lambda_{G}}$ by moving its elements to the left when it
happens, in a similar way as we did with $\omega_{q}^{k,j+1}$ above, so that
we can do further modifications to the block in question.

Formally, we define a sequence $\textbf{x}^{0},\dots,\textbf{x}^{m}$ as
follows. Put $\textbf{x}^{0}=\textbf{z}^{k,2\lambda_{G}}$. For all $p$,
consider the following cases in order to define $\textbf{x}^{p}$:

     * •

for some indices $q$, $\textbf{x}^{p}_{0}+\dots+\textbf{x}^{p}_{q}$ falls in
$\Gamma^{\textbf{r}}_{\textbf{x}^{p}}(\gamma^{\prime}_{k})$ inside an
occurrence of $t^{2\lambda_{G}}\odot c$. Then we set:

       * –

$\textbf{x}^{p+1}_{q}=\textbf{x}^{p}_{q}-2$ if $q$ is such an index but $q-1$
is not (or $q=0$);

       * –

$\textbf{x}^{p+1}_{q}=\textbf{x}^{p}_{q}+2$ if $q$ is not such an index but
$q-1$ is;

       * –

$\textbf{x}^{p+1}_{q}=\textbf{x}^{p}_{q}$ in all other cases.

     * •

If there are no such indices, the sequence terminates at $\textbf{x}^{p}$ and
we set $m=p$.

We can check that $m\leq 3\lambda_{G}$.

In the end, we have that every occurrence of the word $t^{2\lambda_{G}}\odot
c$ in $\gamma^{\prime}_{k+1}$ is in some sub-word
$\left(\gamma^{\prime}_{k+1}\right)_{\textbf{z}^{m}_{0}+\ldots\textbf{z}^{m}_{j}+\llbracket
0,\textbf{z}^{m}_{j+1}\rrbracket}$ for some $j<l$. By another application of
Lemma 6.9, we have:

$d^{\mathcal{R}}_{G}\left(\Gamma^{\textbf{r}}_{\textbf{z}^{k,2\lambda_{G}}}(\gamma^{\prime}_{k}),\Gamma^{\textbf{r}}_{\textbf{x}^{m}}(\gamma^{\prime}_{k})\right)\leq{3\lambda_{G}}.$
(2)

  3. 3.

Dichotomic decomposition: Similarly as in Corollary 6.5, we decompose in each
block the copies of $c$ in $c^{\lambda_{G}}$ using the spines
$t^{2\lambda_{G}}$. For all $m$, we set:

$\gamma^{\prime}_{k,m}:=\left(t^{(l(c)/2-2)\lambda_{G}}\odot
c^{\left(2^{n-k}-1\right)\lambda_{G}}\odot t^{2\lambda_{G}+ml(c)/2}\odot
c^{\left(2^{n-k}\right)\lambda_{G}-m}\right)^{2^{k-1}}.$

We have $\gamma^{\prime}_{k,0}=\gamma^{\prime}_{k}$ and, by Lemma 6.4 and
Lemma 6.7,

$d^{\mathcal{R}}_{G}\left(\Gamma^{\textbf{r}}_{\textbf{y}^{0}}(\gamma^{\prime}_{k,0}),\Gamma^{\textbf{r}}_{\textbf{y}^{0}}(\gamma^{\prime}_{k,1})\right)\leq
2\lambda_{G},$

where we set $\textbf{y}^{0}:=\textbf{x}^{m}$.

Some cycles in r may appear inside an occurrence of $t^{2\lambda_{G}}\odot c$
in $\Gamma^{\textbf{r}}_{\textbf{x}^{0}}(\gamma^{\prime}_{k,1})$. This is the
reason why, instead of just applying Corollary 6.5, we define a sequence
$\gamma^{\prime}_{k,m}$, $0\leq m\leq\lambda_{G}$ step by step: we need to
correct each time these ‘misplacements’. Applying the same argument as in the
previous step, there is some $\textbf{y}^{1}$ such that this is no longer the
case and

$d^{\mathcal{R}}_{G}\left(\Gamma^{\textbf{r}}_{\textbf{y}^{0}}(\gamma^{\prime}_{k,1}),\Gamma^{\textbf{r}}_{\textbf{y}^{1}}(\gamma^{\prime}_{k,1})\right)\leq{3\lambda_{G}}.$

In a similar manner, we build a sequence $\left(\textbf{y}^{m}\right)_{1\leq
m\leq\lambda_{G}}$ such that for all $m$,

$d^{\mathcal{R}}_{G}\left(\Gamma^{\textbf{r}}_{\textbf{y}^{m-1}}(\gamma^{\prime}_{k,m-1}),\Gamma^{\textbf{r}}_{\textbf{y}^{m}}(\gamma^{\prime}_{k,m})\right)\leq
2\lambda_{G}+{3\lambda_{G}},$

Summing up,

$d^{\mathcal{R}}_{G}\left(\Gamma^{\textbf{r}}_{\textbf{y}^{0}}(\gamma^{\prime}_{k,0}),\Gamma^{\textbf{r}}_{\textbf{y}^{\lambda_{G}}}(\gamma^{\prime}_{k,\lambda_{G}})\right)\leq{5}\lambda_{G}^{2}.$
(3)

Now notice that $\gamma^{\prime}_{k,\lambda_{G}}$ is the same word as
$\gamma_{k}$, except for some blocks of $2\lambda_{G}$ ‘misplaced’ spines. We
can move them back in ${3\lambda_{G}}$ steps, exactly as in Step 2 of the
current proof: thus there is some $\textbf{z}^{k}$ such that

$d^{\mathcal{R}}_{G}\left(\Gamma^{\textbf{r}}_{\textbf{y}^{\lambda_{G}}}(\gamma^{\prime}_{k,\lambda_{G}}),\Gamma^{\textbf{r}}_{\textbf{z}^{k}}(\gamma_{k})\right)\leq{3\lambda_{G}}.$
(4)

Summing Equations 1, 2, 3 and 4, and by triangular inequality:

$d^{\mathcal{R}}_{G}(\Gamma^{\textbf{r}}_{\textbf{z}^{k-1}}(\gamma_{k-1}),\Gamma^{\textbf{r}}_{\textbf{z}^{k}}(\gamma_{k}))\leq
4\lambda_{G}+{3\lambda_{G}}+{5\lambda_{G}^{2}}+{3\lambda_{G}}\leq{15\lambda_{G}^{2}}.$

  4. 4.

Conclusion: As a consequence, again by triangular inequality:

$d_{G}^{\mathcal{R}}(\Gamma^{\textbf{r}}_{\textbf{z}}(t^{\lambda_{G}l(c)/2}\odot
c^{(2^{n}-1)\lambda_{G}}),\
\Gamma^{\textbf{r}}_{\textbf{z}^{n}}(t^{2^{n-1}\lambda_{G}l(c)}))\leq{15\lambda_{G}^{2}n}$

The previous equation implies that, to go from the sequence z to
$\textbf{z}^{n}$, we had to apply Lemma 6.9 at most $15\lambda_{G}^{2}n$
times. Each time, we apply the same lemma to come back to the initial
sequence, which leads to the following estimate:

$d_{G}^{\mathcal{R}}(\Gamma^{\textbf{r}}_{\textbf{z}^{n}}(t^{2^{n-1}\lambda_{G}l(c)})),\Gamma^{\textbf{r}}_{\textbf{z}}(t^{2^{n-1}\lambda_{G}l(c)})))\leq{15\lambda_{G}^{2}n}.$

By triangular inequality, we obtain:

$d_{G}^{\mathcal{R}}(\Gamma^{\textbf{r}}_{\textbf{z}}(t^{\lambda_{G}l(c)/2}\odot
c^{(2^{n}-1)\lambda_{G}}),\
\Gamma^{\textbf{r}}_{\textbf{z}}(t^{2^{n-1}\lambda_{G}l(c)}))\leq{30\lambda_{G}^{2}}n,$

which concludes the proof.∎

######  Lemma 6.11.

If $G$ is square decomposable then there is a constant $\alpha_{G}>0$ such
that, for every simple cycle $c$, spine $t$ on $c_{0}$, integer $n$, and
sequence of cycles $\textbf{r}=(r^{(j)})_{0\leq j\leq l}$ all beginning and
ending at some vertex $a\in V_{G}$, we have:

$d_{G}(\Gamma^{\textbf{r}}_{\textbf{z}}(t^{\lambda_{G}l(c)/2}\odot
c^{n}),\Gamma^{\textbf{r}}_{\textbf{z}}(t^{(\lambda_{G}+n)l(c)/2}))\leq\alpha_{G}\cdot\log_{2}(n),$

where $\textbf{z}:=(\lambda_{G}l(c),k_{1}l(c),\ldots,k_{l}l(c))$ for any
sequence of positive integers $(k_{j})_{1\leq j\leq l}$ such that
$k_{1}+\ldots+k_{l}=n$.

###### Proof.

Let us fix a cycle $c$, and some integer $n\geq\lambda_{G}$. Let us denote by
$k\geq 1$ and $s<\lambda_{G}$ integers such that $n=k\lambda_{G}-s$.

By Lemma 6.10,

$d_{G}^{\mathcal{R}}\left(\Gamma^{\textbf{r}}_{\textbf{z}}\left(t^{\lambda_{G}l(c)/2}\odot
c^{\lambda_{G}(2^{\lceil\log_{2}(k)\rceil+1}-1)}\right),\Gamma^{\textbf{r}}_{\textbf{z}}\left(t^{\lambda_{G}l(c)2^{\lceil\log_{2}(k)\rceil}}\right)\right)\leq{30}\lambda_{G}^{2}(\log_{2}(k)+2),$

and by Lemma 6.2,

$d_{G}\left(\Gamma^{\textbf{r}}_{\textbf{z}}\left(t^{\lambda_{G}l(c)/2}\odot
c^{\lambda_{G}(2^{\lceil\log_{2}(k)\rceil+1}-1)}\right),\Gamma^{\textbf{r}}_{\textbf{z}}\left(t^{\lambda_{G}l(c)2^{\lceil\log_{2}(k)\rceil}}\right)\right)\leq{60}\lambda_{G}^{2}(\log_{2}(k)+2).$

It is straightforward that $d_{G}$ is conserved when taking prefixes of the
same length. Since $n\geq\lambda_{G}$, we have
$\lambda_{G}(2^{\lceil\log_{2}(k)\rceil+1}-1)\geq
2\lambda_{G}k-\lambda_{G}\geq 2(n+s)-\lambda_{G}\geq n$. It follows that
$\Gamma^{\textbf{r}}_{\textbf{z}}(t^{\lambda_{G}l(c)/2}\odot c^{n})$ is a
prefix of $\Gamma^{\textbf{r}}_{\textbf{z}}(t^{\lambda_{G}l(c)/2}\odot
c^{\lambda_{G}(2^{\lceil\log_{2}(k)\rceil+1}-1)})$. Therefore:

$d_{G}(\Gamma^{\textbf{r}}_{\textbf{z}}(t^{\lambda_{G}l(c)/2}\odot
c^{n}),\Gamma^{\textbf{r}}_{\textbf{z}}(t^{(\lambda_{G}+n)l(c)/2}))\leq{60}\lambda_{G}^{2}\cdot(\log_{2}(k)+2)\leq
240\lambda_{G}^{2}\cdot\log_{2}(n).$

This inequality is still satisfied when replacing $240\lambda_{G}^{2}$ by any
value $\alpha_{G}\geq 240\lambda_{G}^{2}$. We can thus take $\alpha_{G}$
sufficiently large that the inequality holds for all simple cycles $c$ and all
$n<\lambda_{G}$ as well. ∎

###  6.3 The gap function is logarithmic

In this section, we prove Theorem 6.15. By representing a cycle as a cactus,
we can apply the transformation defined in the previous sections in parallel
on all leaves. Doing this in a repeated way, every cycle can be transformed
into a power of a spine in a number of steps which depends logarithmically on
the length of the cycle.

Before this, we need a last technical tool. Let us recall that we have, for
any cycle $c$, any spine $t$ on $c_{0}$, and any $m\geq 0$:

$d^{\mathcal{R}}_{G}(t^{m}\odot c,c\odot t^{m})\leq m.$

The next lemma provides another useful bound that holds in a more general
context.

######  Lemma 6.12.

Let $u$ be a walk and let $t,t^{\prime}$ be spines on $u_{0}$ and $u_{l(u)}$,
respectively. Then

$d^{\mathcal{R}}_{G}(t^{m}\odot u,u\odot t^{\prime m})\leq l(u).$

###### Proof.

Let $t^{(i)}$ be the spine $u_{i}u_{i+1}u_{i}$ and $u^{(i)}=u_{0}\dots
u_{i}\odot\left(t^{(i)}\right)^{m}\odot u_{i}\dots u_{l(u)}$. It is enough to
check that $(t^{m}\odot u)\mathcal{R}_{0}u^{(1)}$, that
$u^{(i)}\mathcal{R}_{0}u^{(i+1)}$ for all $0<i<l(u)-1$, and that
$u^{(l(u)-1)}\mathcal{R}_{0}(u\odot t^{\prime m})$. ∎

######  Remark 6.13.

Lemma 6.12 still holds when, instead of $u\odot t^{\prime m}$, spines appear
in $u$ in arbitrary positions. This allows us to gather all spines on the left
or right side of $u$ within $l(u)$ bound on $d^{\mathcal{R}}_{G}$.

######  Lemma 6.14.

Take $a,b$ in $V_{G}$, $r$ and $r^{\prime}$ simple walks respectively from $b$
to $a$ and from $a$ to $b$, and $c,c^{\prime}$ two cycles of same length from
$a$ to $a$. Then:

$d_{G}(r\odot c\odot r^{\prime},r\odot c^{\prime}\odot r^{\prime})\leq
d_{G}(c,c^{\prime})+4\text{diam}(G).$

###### Proof.

Let $\left(p^{(i)}\right)_{0\leq i\leq m}$ be a sequence of walks on $G$,
where $m=d_{G}(c,c^{\prime})$, which all have the same length $l(c)$ such that
for all $i$, $p^{(i+1)}$ and $p^{(i)}$ are neighbors and
$p^{(0)}=c,p^{(m)}=c^{\prime}$. Let us define two other sequences
$r_{l}^{(i)}$ and $r_{r}^{(i)}$ such that
$r_{l}^{(0)}=r,r_{r}^{(0)}=r^{\prime}$, and for all $i$, $r_{l}^{(i+1)}$
(resp. $r_{r}^{(i+1)}$) is the left (resp. right) shift of $r_{l}^{(i)}$ which
ends (resp. begins) on $p^{(i+1)}_{0}$ (resp. $p^{(i+1)}_{l(c)}$). Then the
sequence of walks

$q^{(i)}:=r_{l}^{(i)}\odot p^{(i)}\odot r_{r}^{(i)}$

is well-defined and for all $i$, $q^{(i+1)}$ and $q^{(i)}$ are neighbors.
Since $r$ and $r^{\prime}$ have length smaller than $\text{diam}(G)$, by
shifting $\text{diam}(G)$ times to the left, $\text{diam}(G)$ times to the
right, $\text{diam}(G)$ times to the right and then $\text{diam}(G)$ times to
the left again, we can find a walk on $\Delta_{G}^{l(c)}$ from $q^{(m)}$ to
$r\odot c^{\prime}\odot r^{\prime}$. Triangular inequality implies the
statement of the lemma. ∎

######  Theorem 6.15.

If $G$ is square decomposable, $\gamma_{G}(n)=O(\log(n))$.

$n(C)=3$$n(C^{\prime})=3$$n(C^{\prime\prime})=2$ Figure 9: Illustration of
Steps 3 (left) and 4 (right) in the proof of Theorem 6.15.

###### Proof.

  1. 1.

Roadmap of the proof: Consider a cycle $c$ of length $n$ on $G$. Our goal is
to prove that $c$ can be compressed into spines so that:

$d_{G}(c,t^{l(c)/2})\leq
2|V_{G}|(|\mathcal{C}_{G}^{0}|\alpha_{G}\log(n)+|\mathcal{C}_{G}^{0}|\text{diam}(G)+|V_{G}|)$

This ends the proof because, together with Lemma 3.8 and Lemma 3.7, this
implies that $\gamma_{G}(n)=O(\log(n))$.

  2. 2.

Using the cactus representation to write $c$ relatively to its leaves: From
Lemma 5.10 we know that there exists a cactus forest $(C_{1},\ldots,C_{l})$
such that $\pi(C_{1},\ldots,C_{l})=c$ with depth $k\leq|V_{G}|$. Let us denote
by $w^{(1)},\ldots,w^{(m)}$ an enumeration of the highest level
$\ell_{k}(C_{1},\ldots,C_{l})$ of this cactus forest such that there exist
walks $\gamma^{(1)},\dots,\gamma^{(m+1)}$ such that:

$c=\gamma^{(1)}\odot w^{(1)}\odot\gamma^{(2)}\odot\ldots\odot\gamma^{(m)}\odot
w^{(m)}\odot\gamma^{(m+1)}.$ (5)

Let us recall that each of the cycles $w^{(i)}$ is simple.

  3. 3.

Compressing the leaves into spines: Let us consider $d^{(1)},\dots,d^{(\tau)}$
an enumeration of $\mathcal{C}_{G}^{0}$. Let us construct a sequence of cycles
$u^{(0)},\dots.,u^{(\tau)}$ as follows. The aim is to recursively replace all
$\xi(w^{(j)})$ in (5) representing $d^{(i)}$ by spines. First, $u^{(0)}=c$ and
for all $p<\tau$, assuming that $u^{(0)},\dots,u^{(p)}$ have been constructed,
if there exist a sequence r, some $q\geq 1$, and some simple walks $v,w$ such
that $u^{(p)}=v\odot\Gamma^{\textbf{r}}_{\textbf{z}}(d)\odot w$, where
$d=\left(d^{(p+1)}\right)^{q}$ and z consists in multiples of
$l\left(d^{(p)}\right)$, then we set

$u^{(p+1)}:=v\odot\Gamma^{\textbf{r}}_{\textbf{z}}(t^{ql\left(d^{(p+1)}\right)/2})\odot
w,$

Otherwise, $u^{(p+1)}:=u^{(p)}$. Note that such representation exists if and
only if $d^{(p+1)}$ was among $\xi(w^{(j)})$ in (5).

By Lemma 6.11 and Lemma 6.14, for all $p<\tau$,

$d_{G}(u^{(p+1)},u^{(p)})\leq\alpha_{G}\log(n)+\text{diam}(G).$

As a result of this recursive elimination, $u:=u^{(\tau)}$ can be written as
follows:

$u:=\gamma^{(1)}\odot\left(t^{(1)}\right)^{a_{1}}\odot\gamma^{(2)}\odot\left(t^{(2)}\right)^{a_{2}}\odot\cdots\odot\gamma^{(m_{c})}\odot\left(t^{(m_{c})}\right)^{a_{m_{c}}}\odot\gamma^{(m_{c}+1)},$

where each $t^{(i)}$ is a spine.

Using Lemma 6.2, we have:

$d_{G}(c,u)\leq\tau\alpha_{G}\log(n)\leq|\mathcal{C}_{G}^{0}|\left(\alpha_{G}\log(n)+\text{diam}(G)\right).$

Another way to describe $u$ is to say that we have
$u=\pi(C^{\prime}_{1},\ldots,C^{\prime}_{l})$ where
$(C^{\prime}_{1},\ldots,C^{\prime}_{l})$ is the cactus forest obtained from
$(C_{1},\ldots,C_{l})$ by replacing each leaf $w^{(i)}$ in its $k$-th level by
$a_{i}$ cacti $w^{(i,j)}$, $1\leq j\leq a_{i}$ such that for all $i,j$,
$\chi(w^{(i,j)})=\chi(w^{(i)})$ and $\xi(w^{(i,j)})=t^{(i)}$. Figure 9 (left)
illustrates the transformation of $(C_{1},\ldots,C_{l})$ into
$(C^{\prime}_{1},\ldots,C^{\prime}_{l})$.

  4. 4.

Gathering the spines: Now we bring every spine at depth $k$ to depth $k-1$. We
consider two cases:

    1. (i)

When $\boldsymbol{k>2}$. For all $q\leq l$, consider the cactus
$C^{\prime\prime}_{q}$ obtained from $C^{\prime}_{q}$ as follows. For every
cactus $C^{\ast}$ in $\ell_{k-2}(C^{\prime}_{q})$ and every $m$, take all
cacti $w^{(i,j)}$ that appears in $s(s(C^{\prime})_{m})$, remove them from
$s(s(C^{\prime})_{m})$, and add them to $s(C^{\prime})$ just before
$s(C^{\prime})_{m}$, keeping their relative order. Furthermore, fix
$\chi(w^{(i,j)})=\chi(s(C^{\prime})_{m})$. Let us denote
$c^{\prime}:=\pi(C^{\prime\prime}_{1},\ldots,C^{\prime\prime}_{l})$.

    2. (ii)

When $\boldsymbol{k=2}$. In this case, we consider
$c^{\prime}:=\pi(C^{\prime\prime})$, where $C^{\prime\prime}$ is a cactus
forest obtained from $(C^{\prime}_{1},\ldots,C^{\prime}_{l})$ in the following
way. For all $q\leq l$, remove the cacti $w^{(i,j)}$ which appear in
$s(C^{\prime}_{q})$ and insert them in the cactus forest in between
$C^{\prime}_{q}$ and $C^{\prime}_{q+1}$.

Using Lemma 6.12 on every such cactus $C^{\ast}$ and Remark 6.8, we get that:

$d^{\mathcal{R}}_{G}(u,c^{\prime})\leq\max_{d\in\mathcal{C}_{G}^{0}}l(d)\leq|V_{G}|\qquad\text{and
thus}\qquad d_{G}(u,c^{\prime})\leq 2|V_{G}|.$

Since every leaf was moved one level down we have
$n(C^{\prime\prime})=n(C^{\prime})-1=n(C_{1},\ldots,C_{l})-1$.

Figure 9 (right) illustrates the transformation of
$(C^{\prime}_{1},\ldots,C^{\prime}_{l})$ into
$(C^{\prime\prime}_{1},\ldots,C^{\prime\prime}_{l})$.

  5. 5.

Iterating the process: In steps 3 and 4, we found a cycle $c^{\prime}$
represented by a cactus forest of depth $n(C_{1},\ldots,C_{l})-1$ such that
$l(c)=l(c^{\prime})$ and

$d_{G}(c,c^{\prime})\leq|\mathcal{C}_{G}^{0}|\left(\alpha_{G}\log(n)+\text{diam}(G)\right)+2|V_{G}|.$

By repeating this argument, and since $n(C_{1},\ldots,C_{l})\leq|V_{G}|$, we
find a cycle $f_{q}$ which is represented by a cactus forest of depth $1$ such
that

$d_{G}(c,f)\leq
2(|V_{G}|-1)(|\mathcal{C}_{G}^{0}|\alpha_{G}\log(n)+|\mathcal{C}_{G}^{0}|\text{diam}(G)+|V_{G}|).$

By applying again Lemma 6.11 as in Step $3$ of the present proof, we have:

$d_{G}(f,t^{l(c)/2})\leq|\mathcal{C}_{G}^{0}|\alpha_{G}\log(n).$

and thus, by triangular inequality:

$d_{G}(c,t^{l(c)/2})\leq|V_{G}|(|\mathcal{C}_{G}^{0}|\alpha_{G}\log(n)+|\mathcal{C}_{G}^{0}|\text{diam}(G)+|V_{G}|).$

This implies that the claim from the first step holds, and thus the theorem is
proved.∎

##  7 A $\Theta(\log(n))$-phased block gluing Hom shift

This section disproves R. Pavlov and M. Schraudner’s conjecture [CM18] that
this class is empty.

$\epsilon_{1}$$\mu_{6}$$\mu_{3}$$\mu_{5}$$\mu_{4}$$\delta_{3}$$\delta_{2}$$\mu_{1}$$\mu_{2}$$\gamma_{3}$$\gamma_{1}$$\epsilon_{3}$$\epsilon_{2}$$\gamma_{2}$$\omega$$\delta_{1}$
Figure 10: The Kenkatabami graph.

######  Theorem 7.1.

There exists a graph $K$ such that $X_{K}$ is $\Theta(\log(n))$-phased block
gluing.

###### Proof.

$K$ is the Ken-katabami graph shown on Figure 10 (we use the notations of the
figure for the vertices)222The name comes from a visual similarity with the
Ken-katabami (剣片喰) Japanese crest, see
https://commons.wikimedia.org/wiki/File:Ken-Katabami_inverted.png. Since the
graph is clearly square decomposable, Theorem 6.15 applies, and
$\gamma_{K}(n)=O(\log(n))$. Thus it is sufficient to prove that
$\log(n)=O(\gamma_{K}(n))$.

  1. 1.

Notations: Let us denote by
$c=\epsilon_{1}\gamma_{1}\epsilon_{2}\gamma_{2}\epsilon_{3}\gamma_{3}\epsilon_{1}$
the anti-clockwise exterior cycle of the graph $K$.

For any walk $p$ on the graph $K$, a $c$-block of $p$ is a maximal word of the
form $c^{n}$ in $p$. This $n$ is called the order of this $c$-block. We also
denote by $\mu_{c}(p)$ the maximal order of a $c$-block.

  2. 2.

Lower bound on $\mu_{c}(p_{2})$ for $p_{2}$ neighbor of $p_{1}$:

(i) Claim: We claim that for $n$ large enough and two walks $p,q$ that are
neighbours in $\Delta_{K}^{N}$, the following formula holds:

$\mu_{c}(p)\geq\frac{1}{2}\mu_{c}(q)-3.$

(ii) Characteristics of the neighbors of $c^{n}$ in $\Delta_{K}^{6n}$: For all
$n\geq 4$, let us prove that a neighbor $p$ of $q=c^{n}$ in the graph
$\Delta_{K}^{6n}$ is of the form

    1. (a)

$u\odot w\odot v$ with $|w|\leq 3$,

    2. (b)

$u\odot w$ or $w\odot v$ with $|w|=1$,

    3. (c)

$u$ or $v$,

where the words $u$ and $v$ are respectively a right shift of a prefix of
$c^{n}$ and a left shift of a suffix of $c^{n}$.

The only common neighbor of $\epsilon_{i}$ and $\epsilon_{i+1}$ is
$\gamma_{i}$ and the only common neighbor of $\gamma_{i}$ and $\gamma_{i+1}$
is $\epsilon_{i}$ (where for technical reasons the index $i$ is identified
with the corresponding element of $\mathbb{Z}/3\mathbb{Z}$). Take an arbitrary
$k$, and assume for simplicity that $q_{k}=\epsilon_{2}$ (other cases are
processed similarly). Then possible values for $p_{k}$ are
$\gamma_{1},\gamma_{2}$ or $\delta_{2}$, and we can check that the only
possibilities for $p$ are the following:

$k+$$-2$$-1$$0$$+1$$+2$$q$$p$$\epsilon_{1}$$\gamma_{1}$$\epsilon_{2}$$\gamma_{2}$$\epsilon_{3}$$\gamma_{1}$$\epsilon_{2}$$\gamma_{2}$ | $k+$$-2$$-1$$0$$+1$$+2$$q$$p$$\epsilon_{1}$$\gamma_{1}$$\epsilon_{2}$$\gamma_{2}$$\epsilon_{3}$$\gamma_{1}$$\epsilon_{2}$$\gamma_{2}$ | $k+$$-2$$-1$$0$$+1$$+2$$q$$p$$\epsilon_{1}$$\gamma_{1}$$\epsilon_{2}$$\gamma_{2}$$\epsilon_{3}$$\gamma_{1}$$\nicefrac{{\epsilon_{2}}}{{\mu_{3}}}$$\delta_{2}$$\nicefrac{{\epsilon_{2}}}{{\mu_{4}}}$$\gamma_{2}$
---|---|---

In the leftmost case ($p_{k}=q_{k-1}$), we see that $p_{\llbracket
k,6n\rrbracket}=q_{\llbracket k,6n\rrbracket-1}$. Similarly, in the center
case, ($p_{k}=q_{k+1}$), we have $p_{\llbracket 0,k\rrbracket}=q_{\llbracket
0,k\rrbracket+1}$. Finally, in the rightmost case
($p_{k}\notin\\{q_{k-1},q_{k+1}\\}$), we can see that $p_{\llbracket
0,k-2\rrbracket}=q_{\llbracket 0,k-2\rrbracket+1}$ or $p_{\llbracket
k+2,6n\rrbracket}=q_{\llbracket k+2,6n\rrbracket-1}$.

Therefore:

     * •

if for any $k$, $p_{k}\notin\\{q_{k-1},q_{k+1}\\}$, we are in case (a).

     * •

if $p_{k}=q_{k+1}$ for all $k$, we are in case (b) or (c); similarly if
$p_{k}=q_{k-1}$.

     * •

we cannot have $p_{k}=q_{k-1}$ and $p_{k+1}=q_{k+2}$ since $q_{k-1}$ and
$q_{k+2}$ are not neighbours in the graph.

(iii) Lower bound on $\mu_{c}(p)$ for $p$ a neighbor of $c^{n}$ in
$\Delta_{K}^{6n}$:

If $u$ is a prefix or suffix of $c^{n}$, it is clear that
$\mu_{c}(u)\geq\lfloor\frac{l(u)}{6}\rfloor$. Furthermore, for any walk
$p^{\prime}$, $\mu_{c}(p^{\prime})\geq\mu_{c}(p^{\prime\prime})-1$ for any
shift $p^{\prime\prime}$ of $p^{\prime}$.

As a consequence of point (ii), any neighbor $p$ of $c^{n}$ in
$\Delta_{K}^{6n}$ has a subword which is a shift of a prefix or suffix of
$c^{n}$ and whose length is at least $\frac{6n-3}{2}$. Thus we have that

$\mu_{c}(p)\geq\left\lfloor\frac{1}{6}\frac{6n-3}{2}-1\right\rfloor\geq\frac{n}{2}-3.$

(iv) Proof of the claim: Let us consider $p$ and $q$ two words which are
neighbors in $\Delta_{K}^{N}$. By definition, if $n=\mu_{c}(p)$, then $p$ has
$c^{n}$ as a subword. The corresponding subword of $q$ is a neighbour of
$c^{n}$ in $\Delta_{K}^{6n}$, which means that
$\mu_{c}(q)\geq\frac{n}{2}-3=\frac{\mu_{c}(p)}{2}-3$.

  3. 3.

Lower bound on $\gamma_{K}(n)$: For any integer $n$, consider $c^{n}$ and
$q_{n}$ any walk of length $6n$ that does not contain $c$, such as a repeated
spine. Thus $\mu_{c}(c^{n})=n$ and $\mu_{c}(q_{n})=0$. By the previous claim,
any walk $p_{0},\dots,p_{m}$ in $\Delta_{K}^{6n}$ satisfies
$\mu_{c}(p_{i+1})\geq\frac{\mu_{c}(p_{i})}{2}-3$ for all $i$. It follows that
$\log(n)=O(d_{G}(c^{n},q_{n}))$. By Lemma 3.7 and Proposition 3.6, this
implies that $\log(n)=O(\gamma_{K}(n))$.∎

##  8 Open problems

We leave two main problems for further research. The first problem is the
classification of block gluing classes for Hom shifts. We conjecture the
following:

######  Conjecture 8.1.

The only possible classes of gap functions for Hom shifts are $\Theta(1)$,
$\Theta(\log(n))$ and $\Theta(n)$.

Any tree provides a $\Theta(1)$-block gluing Hom shift, and there are several
nontrivial examples of $\Theta(1)$-phased block gluing Hom shifts (see Figure
11). We can construct more examples of $\Theta(\log(n))$-block gluing Hom
shifts by ’gluing’ these graphs together (see Figure 12). What intuitively
separates these two sets of graphs is whether every cycle can be deformed to a
trivial cycle so that no intermediate cycle is larger that the original.
However formalizing this intuition has provn difficult.

Figure 11: Example of graphs whose Hom shift is $\Theta(1)$-phased block
gluing.

Figure 12: Example of graphs whose Hom shift is $\Theta(\log(n))$-phased block
gluing.

The second problem is finding an algorithm which, provided a graph $G$,
decides in which class (for $\Theta$) its gap function belongs to. In
particular, since we know that there is no intermediate class between
$O(\log(n))$ and $\Theta(n)$ and that the class to which a graph belongs
depends on whether or not its square cover is finite, the key question seems
to be:

######  Question 8.2.

Is there an algorithm which decides, given a finite graph $G$, whether
$\mathcal{U}^{\square}_{G}$ is finite or not ?

This question seems to be close to known undecidability results: the square
cover is finite if and only if the quotient of the fundamental group of $G$ by
squares of $G$ is finite, and it is not possible in general to decide if a
group defined by a finite number of generators and relations is finite or not.
This is a consequence of the Adian-Rabin theorem [Adi57, Rab58] – see [NB22]
for a translation and exposition of Adian’s work.

Additional open questions on Hom shifts can be found in [Cha17, CM18]. For
example, we do not know how to characterise mixing properties relative to
general shapes (not only rectangular) in Hom shifts.

## Acknowledgements

The second author wishes to thank Nishant Chandgotia for introducing him to
Hom shifts and many fruitful discussions, and Jan van der Heuvel along with
the organizers of CoRe 2019 where the Ken-Katabami graph was found. (As well
the first author is thankful to the second author for introducing him to Hom
shifts, as well as the third author is thankful to the first one).

The second author was partially supported by a LISN internal project. The
research of the first and the third author was supported in part by National
Science Centre, Poland (NCN), grant no. 2019/35/B/ST1/02239.

## References

  * [Adi57] Sergei Ivanovich Adian.  Unsolvability of some algorithmic problems in the theory of groups.  Trudy Moskovskogo Matematicheskogo Obshchestva, 6:231–298, 1957\.
  * [Ang80] Dana Angluin.  Local and global properties in networks of processors.  In Proceedings of the twelfth annual ACM symposium on Theory of computing, pages 82–93, 1980.
  * [BBDL21] Raimundo Briceño, Andrei Bulatov, Víctor Dalmau, and Benoît Larose.  Dismantlability, connectedness, and mixing in relational structures.  Journal of Combinatorial Theory, Series B, 147:37–70, 2021.
  * [BP17] Raimundo Briceño and Ronnie Pavlov.  Strong spatial mixing in homomorphism spaces.  SIAM Journal on Discrete Mathematics, 31(3):2110–2137, 2017.
  * [BW00] Graham R Brightwell and Peter Winkler.  Gibbs measures and dismantlable graphs.  Journal of combinatorial theory, series B, 78(1):141–166, 2000\.
  * [Cha17] Nishant Chandgotia.  Four-cycle free graphs, height functions, the pivot property and entropy minimality.  Ergodic Theory and Dynamical Systems, 37(4):1102–1132, 2017.
  * [CM18] Nishant Chandgotia and Brian Marcus.  Mixing properties for hom-shifts and the distance between walks on associated graphs.  Pacific Journal of Mathematics, 294(1):41–69, 2018.
  * [Fri97] Shmuel Friedland.  On the entropy of zd subshifts of finite type.  Linear algebra and its applications, 252(1-3):199–220, 1997.
  * [GdM19] Silvère Gangloff and Benjamin Hellouin de Menibus.  Effect of quantified irreducibility on the computability of subshift entropy.  Discrete and Continuous Dynamical Systems, 39(4):1975–2000, 2019\.
  * [GP95] William Geller and James Propp.  The projective fundamental group of a $\mathbb{z}^{2}$-shift.  Ergodic Theory and Dynamical Systems, 15(6):1091–1118, 1995.
  * [GS21] Silvere Gangloff and Mathieu Sablik.  Quantified block gluing for multidimensional SFT: aperiodicity and entropy.  Journal d’Analyse mathématique, 144:21––118, 2021.
  * [Had98] Jacques Hadamard.  Les surfaces à courbures opposées et leur lignes geodesiques.  Journal de Mathématiques Pures et Appliqués, 4:27––73, 1898\.
  * [HKC92] Lyman P. Hurd, Jarkko Kari, and Karel Culik.  The topological entropy of cellular automata is uncomputable.  Ergodic Theory and Dynamical Systems, 12(2):255––265, 1992.
  * [HM07] Michael Hochman and Tom Meyerovitch.  A characterization of the entropies of multidimensional shifts of finite type.  Annals of Mathematics, 171:2011–2038, 2007.
  * [Lie67] Elliott H. Lieb.  Residual entropy of square ice.  Phys. Rev., 162:162–172, 1967.
  * [NB22] Carl-Fredrik Nyberg-Brodda.  The adian-rabin theorem–an english translation.  arXiv preprint arXiv:2208.08560, 2022.
  * [Pav10] Ronnie Pavlov.  Approximating the hard square entropy constant with probabilistic methods.  Annals of Probability, 40:2362–2399, 2010.
  * [PS15] Ronnie Pavlov and Michael Schraudner.  Entropies realizable by block gluing ${Z}^{d}$ shifts of finite type.  Journal d’Analyse Mathematique, 126:113–174, 2015.
  * [PSV22] Léo Paviet-Salomon and Pascal Vanier.  Realizing finitely presented groups as projective fundamental groups of SFTs.  HAL preprint arXiv:2208.08560, 2022.
  * [Rab58] Michael O. Rabin.  Recursive unsolvability of group theoretic problems.  Annals of Mathematics, pages 172–194, 1958.
  * [Sta83] John R Stallings.  Topology of finite graphs.  Inventiones mathematicae, 71(3):551–565, 1983.
  * [Wan61] Hao Wang.  Proving theorems by pattern recognition — ii.  Bell System Technical Journal, 40(1):1–41, 1961.
  * [Wro20] Marcin Wrochna.  Homomorphism reconfiguration via homotopy.  SIAM Journal on Discrete Mathematics, 34(1):328–350, 2020.