11institutetext: Institute of Mathematical Sciences, HBNI, Chennai
11email<EMAIL_ADDRESS>
# Recursive methods for some problems in coding and random permutations

Ghurumuruhan Ganesan

###### Abstract

In this paper, we study three applications of recursion to problems in coding
and random permutations. First, we consider locally recoverable codes with
partial locality and use recursion to estimate the minimum distance of such
codes. Next we consider weighted lattice representative codes and use
recursive subadditive techniques to obtain convergence of the minimum code
size. Finally, we obtain a recursive relation involving cycle moments in
random permutations and as an illustration, evaluate recursions for the mean
and variance.

Key words: Locally recoverable codes, partial locality, minimum distance,
lattice identification codes, minimum size, random permutations, cycle
moments.

##  1 Introduction

Recursive techniques are used quite frequently in coding to obtain bounds on
code sizes. As a typical example, the Singleton bound [9] obtains bounds on
sizes of $n-$length codes by reducing the problem to that of an $(n-1)-$length
code. Similarly, recursive relations are also frequent in terms related to
permutations like for example, Stirling numbers of the first kind [8]. In this
paper, we study further applications of recursive methods to problems in
coding and random permutations.

The paper is organized as follows: In Section 2, we consider locally
recoverable codes with partial locality and estimate the minimum distance of
such codes (Theorem 2.1) using iterations on subcodes. Next, in Section 3, we
study lattice representative codes with weights and prove asymptotic
convergence of the minimum size, using subadditive techniques (Theorem 3.1).
Finally, in Section 4, we establish a recursion for cycle moments of random
permutations (Theorem 4.1) and illustrate our result for the cases of mean and
variance (Corollary 1).

##  2 Locally recoverable codes with partial locality

Locally recoverable codes for erasures have tremendous applications in
distributed storage and retrieval [12] and it is therefore important to
understand the properties of such codes. Typically each erasure correction is
performed using a locality set of small size and it is of interest to design
codes capable of correcting multiple erasures simultaneously. Such codes are
also known as locally repairable codes and storage-bandwidth tradeoff and
construction of such codes has been well-studied; for an overview we refer to
the recent survey [2]. For distinction, we refer to codes above as _fully_
locally recoverable codes since _every_ symbol position has a locality set of
small size associated with it. In [7], bounds are obtained for the minimum
distance of linear fully locally recoverable codes in terms of the size of the
locality sets. Later [5] studied bounds on the minimum distance of non-linear
systematic fully locally recoverable codes.

In this section, we study minimum distance of locally recoverable codes with
partial locality. We assume that only a _subset_ of symbol positions have
locality set size at most $r$ and obtain bounds on the minimum distance. Let
$n\geq k\geq 1$ be integers and let ${\cal A}$ be a set of cardinality
$\\#{\cal A}=q.$ A set ${\cal C}\subseteq{\cal A}^{n}$ of cardinality $q^{k}$
is defined to be an $(n,k)-$code.

For a set ${\cal U}\subseteq\\{1,2,\ldots,n\\}$ and an integer
$j\in\\{1,2,\ldots,n\\}\setminus{\cal U},$ we say that position $j$ is
determined by ${\cal U}$ if there exists a function $g_{j}$ such that

$c_{j}=g_{j}\left(c_{i}:i\in{\cal U}\right)=:g_{j}\left({\cal U}\right)$ (2.1)

for all codewords $\mathbf{c}=(c_{1},\ldots,c_{n})\in{\cal C}.$ In words, the
symbol at the $j^{th}$ position of any codeword can be determined from the
symbols with positions in ${\cal U}.$ The set ${\cal F}_{\cal U}$ of all
positions determined by ${\cal U}$ is called the _reach_ of ${\cal U}.$ For
integer $1\leq w\leq n,$ we define

$L(w)=L(w,{\cal C}):=\max_{{\cal U}:\\#{\cal U}=w}\\#{\cal F}_{\cal U}.$ (2.2)

For any $w\geq 1$ we have that $L(w,{\cal C})\leq\Delta(w),$ where
$\Delta(w)=q^{w}$ if ${\cal C}$ is a linear code and $\Delta(w)=q^{q^{w}}$
otherwise. We remark here that $q^{q^{w}}$ is the _total_ number of maps from
${\cal A}^{w}$ to ${\cal A}.$

###### Definition 1

For integers $\tau,r\geq 2$ and a subset $\Theta\subseteq\\{1,2,\ldots,n\\},$
we say that the code ${\cal C}$ has $(\Theta,\tau,r)-$local correction
capability if for every subset ${\cal P}\subseteq\Theta$ of size $\tau,$ there
exists a set ${\cal T}_{\cal P}\subseteq\\{1,2,\ldots,n\\}\setminus{\cal P}$
of size at most $r$ such that each position in ${\cal P}$ is determined by
${\cal T}_{\cal P}.$

We define ${\cal T}_{\cal P}$ to be the $r-$locality set corresponding to the
set ${\cal P}.$ Also if $\Theta=\\{1,2,\ldots,n\\},$ we say that ${\cal C}$
has $(\tau,r)-$local correction capability.

For example, consider the binary linear code ${\cal C}$ formed in the
following way: For $k\geq 10$ and a word
$(c_{1},\ldots,c_{k})\in\\{0,1\\}^{k},$ let
$d_{i_{1},i_{2},i_{3}}:=c_{i_{1}}\oplus c_{i_{2}}\oplus c_{i_{3}}$ where
$\oplus$ denotes addition modulo two. There are ${k\choose 3}=:n-k-1$ such
terms $\\{d_{i_{1},i_{2},i_{3}}\\}$ which we relabel as
$c_{k+1},\ldots,c_{n-1}.$ Finally we let $c_{n}:=\oplus_{i=1}^{k}c_{i}.$ We
let $(c_{1},\ldots,c_{n})$ be the codeword corresponding to the word
$(c_{1},\ldots,c_{k}).$ The collection of codewords ${\cal C}$ has
$(\Theta,\tau,r)-$local correction capability with
$\Theta=\\{1,2,\ldots,n-1\\},\tau=1$ and $r=3.$ For example to recover
$c_{1},$ we use the relation

$d_{1,2,3}\oplus d_{1,2,4}\oplus d_{1,3,4}=c_{1}.$

In general, each bit $c_{j},1\leq j\leq k$ can be recovered in a similar
manner. Because $k\geq 10,$ the bit $c_{n}$ cannot be recovered by using any
three bits of $\\{c_{1},\ldots,c_{n-1}\\}.$

Let ${\cal C}$ be any code with $(\Theta,\tau,r)-$local correction capability.
For words $\mathbf{x}=(x_{1},\ldots,x_{n})$ and
$\mathbf{y}=(y_{1},\ldots,y_{n})$ in ${\cal C}$ we define the Hamming distance
between $\mathbf{x}$ and $\mathbf{y}$ to be
$d(\mathbf{x},\mathbf{y}):=\sum_{i=1}^{n}1{1}(x_{i}\neq y_{i}),$ where
$1{1}(.)$ denotes the indicator function. The minimum distance of ${\cal C}$
is then defined as $d({\cal C}):=\min_{\mathbf{x},\mathbf{y}\in{\cal
C}}d(\mathbf{x},\mathbf{y}).$ We have the following result.

###### Theorem 2.1

Let ${\cal C}$ be any $(n,k)-$code with $(\Theta,\tau,r)-$parallel correction
capability and let $\theta=\\#\Theta.$ The minimum distance of ${\cal C}$
satisfies

$d({\cal C})\leq n-k+1-T\cdot\tau,$ (2.3)

where $T$ is the largest integer $t$ such that

$t\cdot r\leq k-1+\theta-n\text{ and }t\cdot r+\Delta(t\cdot
r)\leq\theta-\tau+1.$ (2.4)

To obtain the bound (2.4), we proceed as in [5] and iteratively construct a
sequence of codes with decreasing size, until no further reduction is
possible. We use the pigeonhole principle at the end of each step and obtain
the sufficient conditions that allow continuation of the iteration procedure.
In the proof below, we see that the first estimate in (2.4) determines the
maximum number of iterations the procedure can proceed before we run out of
codewords to choose from and the second estimate in (2.4) determines the
maximum number of iterations for which we are able to choose a “fresh”
locality set.

Finally, we recall that $n-k+1$ is the Singleton bound [9] and is the maximum
possible minimum distance of an $(n,k)-$code. Therefore the parameter $T$ is
in some sense, the “cost” for requiring partial locality.

### Proof of Theorem 2.1

Let ${\cal P}_{1}\subseteq\Theta$ be any set of size $\tau$ and let ${\cal
I}_{1}:={\cal T}_{{\cal P}_{1}}=\\{l_{1},\ldots,l_{m_{1}}\\},m_{1}\leq r$ be
the corresponding locality set of cardinality at most $r$ as defined in the
paragraph following (2.2) that determines the value of the symbols in
positions in ${\cal P}_{1}.$ For $\mathbf{x}=(x_{1},\ldots,x_{m_{1}})\in{\cal
A}^{m_{1}},$ let ${\cal C}(\mathbf{x})={\cal C}\left(\mathbf{x},{\cal
I}_{1}\right)$ be the set of codewords of ${\cal C}$ such that the symbol in
position $l_{j}$ equals $x_{j}$ for $1\leq j\leq m_{1}.$

The number of choices for $\mathbf{x}$ is at most $q^{m_{1}}$ and there are
$q^{k}$ codewords in ${\cal C}.$ Therefore by pigeonhole principle, there
exists $\mathbf{x}_{1}$ such that

$\\#{\cal C}(\mathbf{x}_{1})\geq\frac{\\#{\cal C}}{q^{m_{1}}}=q^{k-m_{1}}.$
(2.5)

We set ${\cal C}_{1}:={\cal C}(\mathbf{x}_{1})$ and let ${\cal J}_{1}:={\cal
F}_{{\cal I}_{1}}$ be the reach of ${\cal I}_{1}$ (see (2.1)) with cardinality
$\tau\leq\\#{\cal J}_{1}\leq\Delta(r).$ The first inequality is true since
${\cal P}_{1}\subseteq{\cal J}_{1}$ and the second estimate follows from
(2.1). By construction, all words in the code ${\cal C}_{1}$ have the same
values in the symbol positions determined by ${\cal J}_{1};$ i.e., if
$a=(a_{1},\ldots,a_{n})$ and $b=(b_{1},\ldots,b_{n})$ both belong to ${\cal
C}_{1},$ then $a_{j}=b_{j}$ for all $j\in{\cal J}_{1}.$

We now repeat the above procedure with the code ${\cal C}_{1}$ assuming that
$r+n-\theta<k,$ where $\theta:=\\#\Theta.$ If ${\cal
R}_{1}:=\Theta\setminus\left({\cal I}_{1}\cup{\cal J}_{1}\right)$ is the set
of positions not encountered in the first iteration then

$\\#{\cal R}_{1}\geq\\#\Theta-\\#{\cal J}_{1}-\\#{\cal
I}_{1}\geq\theta-\Delta(r)-r$ (2.6)

since $\\#{\cal J}_{1}\leq\Delta(r).$ For a set ${\cal P}\subseteq{\cal
R}_{1}$ of size $\tau,$ let ${\cal I}({\cal P}):={\cal T}_{\cal P}\bigcap{\cal
R}_{1}$ be the union of positions within the locality sets of the selected
$\tau$ positions in ${\cal P},$ not encountered in the first iteration.

Suppose for every ${\cal P}\subseteq{\cal R}_{1},$ we have ${\cal I}({\cal
P})=\emptyset.$ This means that all symbols with positions in ${\cal R}_{1}$
can simply be determined by the symbol values with positions in ${\cal
I}_{1}\cup{\cal J}_{1}.$ This in turn implies that the symbols with positions
in ${\cal I}_{1}$ determine _all_ the symbols with positions in $\Theta.$
Using $r+n-\theta<k$ we then get that the total number of words in the code
${\cal C}$ is at most

$q^{\\#{\cal I}_{1}}\cdot q^{n-\\#\Theta}=q^{m_{1}+n-\theta}\leq
q^{r+n-\theta}<q^{k},$

a contradiction. Thus there exists ${\cal P}_{2}\subseteq{\cal R}_{1}$ of size
$\tau$ whose corresponding set ${\cal I}_{2}:={\cal I}({\cal P}_{2})$ is not
completely contained in ${\cal I}_{1}\cup{\cal J}_{1}.$

Letting $1\leq m_{2}\leq r$ denote the cardinality of ${\cal I}_{2}$ and using
the pigeonhole principle as before, we get a code ${\cal C}_{2}\subseteq{\cal
C}_{1}$ of size

$\\#{\cal C}_{2}\geq\frac{\\#{\cal C}_{1}}{q^{m_{2}}}\geq
q^{k-m_{1}-m_{2}}\geq q^{k-2r}$

and all of whose words have the same symbol values in the positions determined
by ${\cal I}_{1}\cup{\cal I}_{2}.$ In the above, we use the estimate for
${\cal C}_{1}$ obtained in (2.5). As before, let ${\cal
J}_{2}\subseteq\\{1,2,\ldots,n\\}$ be the set of positions of the codeword
symbols determined by the set ${\cal I}_{1}\cup{\cal I}_{2}$ so that ${\cal
P}_{1}\cup{\cal P}_{2}\subseteq{\cal J}_{2}.$ The set ${\cal I}_{1}\cup{\cal
I}_{2}$ has cardinality at most $2r$ and so we have from (2.2) that the reach
${\cal J}_{2}$ has cardinality

$2\tau\leq\\#{\cal P}_{1}+\\#{\cal P}_{2}\leq\\#{\cal J}_{2}\leq\Delta(2r).$

If ${\cal R}_{2}:=\Theta\setminus\left({\cal I}_{1}\cup{\cal I}_{2}\cup{\cal
J}_{2}\right),$ then $\\#{\cal R}_{2}\geq\theta-2r-\Delta(2r).$ Continuing
this way, after the end of $t$ iterations, we have a code ${\cal C}_{t}$ of
size

$\\#{\cal C}_{t}\geq q^{k-\sum_{j=1}^{t}\\#{\cal I}_{j}}\geq q^{k-t\cdot r}$
(2.7)

and a set ${\cal R}_{t}\subseteq\Theta$ of remaining positions not fixed so
far, with cardinality

$\\#{\cal R}_{t}\geq\theta-\sum_{j=1}^{t}\\#{\cal I}_{j}-\\#{\cal
J}_{t}\geq\theta-t\cdot r-\Delta(t\cdot r).$ (2.8)

The above procedure can therefore be performed for at least $T$ steps where
$T$ is the largest integer $t$ such that

$t\cdot r\leq k-1+\theta-n\text{ and }t\cdot r+\Delta(t\cdot
r)\leq\theta-\tau+1.$ (2.9)

The first condition in (2.9) ensures that $k-T\cdot r\geq 1$ and so the code
${\cal C}_{T}$ has at least two codewords. The second condition in (2.9)
ensures that the set ${\cal P}_{j}\subseteq\Theta$ of symbols we pick is at
least $\tau$ and so

$\\#{\cal J}_{j}\geq\sum_{l=1}^{j}\\#{\cal P}_{l}\geq j\cdot\tau$ (2.10)

for each $1\leq j\leq T.$

Since ${\cal C}_{T}\subseteq{\cal C},$ the minimum distance $d({\cal C}_{T})$
of ${\cal C}_{T}$ is at least the minimum distance $d({\cal C})$ of ${\cal
C}.$ By definition we recall that the symbol values in positions determined by
the set $\bigcup_{1\leq j\leq T}{\cal I}_{j}\bigcup{\cal
J}_{T}:=\\{1,2,\ldots,n\\}\setminus{\cal Q}_{T}$ is the same for all the words
in ${\cal C}_{T}.$ For every word $\mathbf{x}=(x_{1},\ldots,x_{n})\in{\cal
C}_{T},$ we therefore let $\mathbf{x}_{T}=(x_{i})_{i\in{\cal Q}_{T}}$ be the
reduced word obtained by just considering the symbols in the remaining
positions determined by ${\cal Q}_{T}.$ Defining the reduced code ${\cal
D}_{T}=\\{\mathbf{x}_{T}:\mathbf{x}\in{\cal C}_{T}\\}$ we then have that the
minimum distance $d({\cal D}_{T})\geq d({\cal C}_{T})\geq d({\cal C}).$

The length of the each word in ${\cal D}_{T}$ equals $n-\\#{\cal Q}_{T}$ and
so using the estimate for $\\#{\cal D}_{T}=\\#{\cal C}_{T}$ from (2.7) and the
Singleton bound we have

$d({\cal D}_{T})\leq\left(n-\sum_{j=1}^{T}\\#{\cal I}_{j}-\\#{\cal
J}_{T}\right)-\left(k-\sum_{j=1}^{T}\\#{\cal I}_{j}\right)+1.$

Thus $d({\cal D}_{T})\leq n-k+1-\\#{\cal J}_{T}\leq n-k+1-T\cdot\tau,$ by
(2.10). Using the fact that $d({\cal C})\leq d({\cal D}_{T}),$ we then get
(2.3). ∎

##  3 Lattice representative codes

Representative codes [10] (also known as hitting sets in some contexts) are
important from both theoretical and application perspectives. In [11] the
minimum size of hitting sets that intersect all combinatorial rectangles of a
given volume are studied. Explicit constructions were described using expander
graphs and random walks. Later [14] determined lower bounds for the hitting
set size of combinatorial rectangles and also illustrated an application in
approximation algorithms. Recently [4] used fractional perfect hash families
to study construction of explicit hitting sets for combinatorial shapes.

In this section, we study lattice representative codes for _weighted_
rectangles where each vertex is assigned a positive finite weight. We study
the minimum size of a representative code that intersects _all_ subsets of a
given minimum weight. For integers $d,m\geq 1$ let ${\cal S}={\cal
S}(m):=\\{1,2,\ldots,m\\}^{d}.$ We refer to elements of ${\cal S}$ as points
and for a point $v=(v_{1},\ldots,v_{d})\in{\cal S},$ we refer to $v_{i}$ as
the $i^{th}$ entry. For each point $v\in{\cal S},$ we assign a finite positive
weight $w(v).$ For a set ${\cal U}\subseteq{\cal S}$ the corresponding weight
$w\left({\cal U}\right):=\sum_{v\in{\cal U}}w(v)$ is the sum of the weights of
the points in ${\cal U}.$ The size of ${\cal U}$ is the number of points in
${\cal U}$ and is denoted by $\\#{\cal U}.$

Let

$1=\inf_{m}\min_{v\in{\cal S}(m)}w(v)\leq\sup_{m}\max_{v\in{\cal
S}(m)}w(v)=:\beta<\infty$ (3.1)

and for $0<\epsilon<1$ say that ${\cal B}\subseteq{\cal S}$ is an
$\epsilon-$representative code or simply representative code if ${\cal
B}\cap{\cal U}\neq\emptyset$ for any set ${\cal U}\subseteq{\cal S}$ of weight
$w\left({\cal U}\right)\geq\epsilon~{}\cdot~{}m^{d}.$

The following result obtains an estimate on the minimum size $b_{m}$ of an
$\epsilon-$representative code.

###### Theorem 3.1

For any $0<\epsilon<1$ and $\beta\geq 1$ we have that

$m^{d}\cdot(1-\epsilon)\leq b_{m}\leq
m^{d}\cdot\left(1-\frac{\epsilon}{\beta}\right)+1.$ (3.2)

Suppose the weight function satisfies the following monotonicity relation: If
$u$ and $v$ are any two points of ${\cal S}$ differing only in the $i^{th}$
entry and $u_{i}>v_{i},$ then the weights $w(u)\leq w(v).$ We then have

$\frac{b_{m}}{m^{d}}\longrightarrow\lambda$ (3.3)

as $m\rightarrow\infty$ where $1-\epsilon\leq\lambda\leq
1-\frac{\epsilon}{\beta}.$

Thus there exists a _fraction_ of vertices in a large rectangle that hits
_all_ sets of a given minimum weight. Moreover, if the weight assignment is
monotonic, then the scaled minimum representative code size converges to a
positive constant strictly between $0$ and $1.$

An example of non-trivial weight assignment that satisfies the monotonicity
relation is the following: Defining $w(1,1):=2$ we iteratively assign the
weight of each vertex in the set
$\\{1,2,\ldots,i+1\\}^{d}\setminus\\{1,2,\ldots,i\\}^{d}$ as $1+\frac{1}{i}.$
The conditions in Theorem 3.1 are then satisfied with $\beta=2.$

### Proof of Theorem 3.1

We begin with the proof of (3.2). Throughout we assume that $d=2$ and an
analogous analysis holds for general $d.$ If ${\cal F}$ is any representative
code of ${\cal S},$ then by definition, the weight of the set ${\cal
S}\setminus{\cal F}$ is at most $\epsilon m^{2}$ and since the weight of each
vertex is at least one (see (3.1)), we get that the number of points in ${\cal
S}\setminus{\cal F}$ is at most $\epsilon m^{2}.$ This implies that the size
of ${\cal F}$ is at least $(1-\epsilon)m^{2}$ and so
$b_{m}\geq(1-\epsilon)m^{2}.$

To find an upper bound on $b_{m},$ we let ${\cal T}\subseteq{\cal S}$ be any
“critical” set such that the weight of ${\cal T}$ is at most $\epsilon
m^{2}-1$ and the weight of ${\cal T}\cup\\{v\\}$ for any point $v\in{\cal
S}\setminus{\cal T}$ is at least $\epsilon m^{2}.$ The set ${\cal
S}\setminus{\cal T}$ is then a representative code of ${\cal S}$ and since the
weight of any point is at most $\beta$ (see (3.1)), we get that the number of
vertices in ${\cal T}$ is at least $\frac{\epsilon}{\beta}\cdot m^{2}-1.$ This
in turn implies that $b_{m}\leq m^{2}\left(1-\frac{\epsilon}{\beta}\right)+1.$
This proves (3.2).

To prove (3.3), we use a subsequence argument analogous to the proof of
Fekete’s lemma. For integers $m\geq r\geq 1,$ we let $m=k\cdot r+s,$ where
$k\geq 1$ and $0\leq s\leq r-1$ are integers and split
$\\{1,2,\ldots,m\\}^{2}$ into four sets

${\cal S}_{1}:=\\{1,2,\ldots,kr\\}^{2},\;\;\;{\cal
S}_{2}:=\\{1,2,\ldots,kr\\}\times\\{kr+1,kr+2,\ldots,kr+s\\},$ ${\cal
S}_{3}:=\\{kr+1,\ldots,kr+s\\}\times\\{1,2,\ldots,kr\\}\text{ and }{\cal
S}_{4}:=\\{kr+1,\ldots,kr+s\\}^{2}.$

Thus ${\cal S}_{2}$ is essentially a “rotated” version of ${\cal S}_{3}.$ For
$1\leq i\leq 4,$ let ${\cal G}_{i}(\epsilon)$ be a representative code of
${\cal S}_{i}$ and let ${\cal R}$ be any set in $\\{1,2,\ldots,m\\}^{2}$ of
weight $w\left({\cal R}\right)\geq\epsilon m^{2}=\epsilon(kr+s)^{2}.$ We first
see that $\bigcup_{i=1}^{4}{\cal G}_{i}(\epsilon)$ is a representative code of
$\\{1,2,\ldots,m\\}^{2}.$ Indeed if ${\cal R}_{i}={\cal R}\cap{\cal S}_{i},$
then using the fact that $w\left({\cal R}\right)=\sum_{i=1}^{4}w\left({\cal
R}_{i}\right),$ we get that either $w\left({\cal
R}_{1}\right)\geq\epsilon(kr)^{2}$ or $w\left({\cal R}_{2}\right)\geq\epsilon
krs$ or $w\left({\cal R}_{3}\right)\geq\epsilon krs$ or $w\left({\cal
R}_{4}\right)\geq\epsilon s^{2}.$ Consequently, we must have that ${\cal
R}\bigcap\bigcup_{i=1}^{4}{\cal G}_{i}(\epsilon)\neq\emptyset.$

If $b^{(i)}$ denotes the minimum size of a representative code of ${\cal
S}_{i},$ then from the discussion above we get

$b_{kr+s}\leq\sum_{i=1}^{4}b^{(i)}\leq b^{(1)}+2krs+s^{2}\leq
b^{(1)}+(2k+1)r^{2}$ (3.4)

where the second inequality in (3.4) follows from the trivial estimate that
the size of any representative code of ${\cal R}_{i}$ is at most the total
number of points in ${\cal R}_{i}$ and the final inequality in (3.4) follows
from the fact that $s\leq r.$

To estimate $b^{(1)},$ we split ${\cal S}_{1}:=\\{1,2,\ldots,kr\\}^{2}$ into
$k^{2}$ disjoint rectangles ${\cal T}_{i},$
$1\leq i\leq k^{2}$ each containing $r^{2}$ points with ${\cal
T}_{1}=\\{1,2,\ldots,r\\}^{2}.$ If $c_{i}$ denotes the minimum size of a
representative code of ${\cal T}_{i},$ then using the weight monotonicity
relation, we get that $c_{i}\leq c_{1}.$ To see this is true suppose ${\cal
T}_{2}=\\{1,2,\ldots,r\\}\times$
$\\{r+1,\ldots,r+2r\\}$ so that ${\cal T}_{2}={\cal T}_{1}+(r,0)$ is obtained
by translation of ${\cal T}_{1}.$ If ${\cal U}\subset{\cal T}_{2}$ is any set
of weight at least $\epsilon r^{2}$ then ${\cal U}-(r,0)\subseteq{\cal T}_{1}$
also has weight at least $\epsilon r^{2},$ by the weight monotonicity
relation. Consequently if ${\cal W}_{1}$ is a representative code of ${\cal
T}_{1},$ then ${\cal W}_{1}+(r,0)$ is a representative code of ${\cal T}_{2}.$
Thus $c_{2}\leq c_{1}$ and the proof of general $c_{i}$ is analogous.

From (3.4) and the discussion in the above paragraph, we get that
$b_{m}=b_{kr+s}\leq k^{2}b_{r}+(2k+1)r^{2}$ and so

$\frac{b_{m}}{m^{2}}\leq\frac{k^{2}b_{r}+(r^{2}(2k+1))}{m^{2}}=\left(\frac{kr}{kr+s}\right)^{2}\left(\frac{b_{r}}{r^{2}}+\frac{2k+1}{k^{2}}\right).$

If $m\rightarrow\infty$ with $r$ fixed, then
$k=k(m,r)=\frac{m-s}{r}\geq\frac{m-r}{r}\rightarrow\infty$ as well and so
$\frac{kr}{kr+s}\rightarrow 1.$ This in turn implies that

$\limsup_{m}\frac{b_{m}}{m^{2}}\leq\limsup_{m}\left(\frac{b_{r}}{r^{2}}+\frac{2k+1}{k^{2}}\right)=\frac{b_{r}}{r^{2}}.$
(3.5)

Since $r\geq 1$ is arbitrary we get from (3.5) that

$\limsup_{m}\frac{b_{m}}{m^{2}}=\liminf_{r}\frac{b_{r}}{r^{2}}=\inf_{r}\frac{b_{r}}{r^{2}}=:\lambda.$

Also, the bounds for $\lambda$ follow from (3.2). ∎

##  4 Random permutations

Random permutations and applications are frequently encountered in computing
problems and it is of interest to study the cycle properties of a randomly
chosen permutation. The papers [6], [13] studied limiting distributions for
the convergence of the number of cycles and cycles lengths of a uniform random
permutation, after suitable renormalization. Later [1] used Poisson
approximation and estimates on the total variation distance to study the
convergence of the overall cycle structure to a process of independent Poisson
random variables. Recently [3] have used probability generating functions to
study convergence of number of cycles of uniform random permutations
conditioned not to have large cycles, scaled and centred, to the Gaussian
distribution.

From the combinatorial aspect, Stirling numbers of the first kind and
generating functions have been used to study random permutation statistics.
Using the Flajolet-Sedgewick theorem it is possible to enumerate permutations
with constraints [8]. In this section, we use conditioning to obtain a
recursive relation involving cycle moments of random permutations. As an
illustration, we compute recursive relation involving the mean and the
variance of the number of cycles in a uniformly random permutation.

We begin with a couple of definitions. A permutation $\pi$ of
$\\{1,2,\ldots,n\\}$ is a bijective map
$\pi:\\{1,2,\ldots,n\\}\rightarrow\\{1,2,\ldots,n\\}.$ The total number of
possible permutations of $\\{1,2,\ldots,n\\}$ is therefore

$n!:=n\cdot(n-1)\cdots 2\cdot 1.$

A _cycle_ of length $k$ in a permutation $\pi$ is a $k-$tuple
$(i_{1},\ldots,i_{k})$ such that $\pi(i_{j})=i_{j+1}$ for $1\leq j\leq k-1$
and $\pi(i_{k})=i_{1}.$ Every number in $\\{1,2,\ldots,n\\}$ belongs to some
cycle of $\pi$ and this provides an alternate representation of $\pi;$ for
example $(1345)(267)(89)$ is the cycle representation of the permutation $\pi$
on $\\{1,2,\ldots,9\\}$ satisfying
$\pi(1)=3,\pi(3)=4,\pi(4)=5,\pi(5)=1,\pi(2)=6,\pi(6)=7,\pi(7)=2,\pi(8)=9,\pi(9)=8.$

Let $\Pi$ denote a uniformly chosen random permutation of $\\{1,2,\ldots,n\\}$
defined on the probability space $(\Omega_{n},{\cal F}_{n},\mathbb{P}_{n})$ so
that

$\mathbb{P}_{n}(\Pi=\pi)=\frac{1}{n!}$

for any deterministic permutation $\pi.$ Let $N_{n}=N_{n}(\Pi)$ be the random
number of cycles in $\Pi$ and for integers $n,s\geq 1,$ set $\mu_{0,s}:=0$ and
$\mu_{n,s}:=\mathbb{E}N_{n}^{s}.$ We have the following result.

###### Theorem 4.1

For integers $n,s\geq 1$ we have

$\mu_{n,s}=1+\frac{1}{n}\sum_{r=1}^{s}\sum_{j=1}^{n-1}{s\choose r}\mu_{j,r},$
(4.1)

where ${s\choose r}=\frac{s!}{r!(s-r)!}$ is the Binomial coefficient.

From the recursive structure of equation (4.1), we then have that $\mu_{n,s}$
could be computed using the previous values $\\{\mu_{j,r}\\}_{j\leq n-1,r\leq
s}.$

As a Corollary of Theorem 4.1 we have the following recursive relations for
the mean and variance of $N_{n}.$

###### Corollary 1

The mean $\mu_{n}:=\mu_{n,1}$ satisfies $\mu_{1}=1$ and the recursive equation

$\mu_{n}=1+\frac{1}{n}\sum_{i=1}^{n-1}\mu_{i}$ (4.2)

for $n\geq 2.$ The sequence $H_{n}:=\sum_{j=1}^{n}\frac{1}{j}$ is the unique
sequence satisfying (4.2).

The variance $v_{n}=var(N_{n}):=\mu_{n,2}-\mu_{n,1}^{2}$ satisfies $v_{1}=0$
and the recursive equation

$v_{n}=1+\frac{1}{n}\sum_{i=1}^{n-1}v_{i}-\frac{H_{n}}{n}.$ (4.3)

The sequence $M_{n}:=H_{n}-\sum_{i=1}^{n}\frac{1}{i^{2}}$ is the unique
sequence satisfying (4.3).

Using (4.2), (4.3) and the recursive relation (4.1), we could similarly
compute higher order moments.

We prove Theorem 4.1 and Corollary 1 in that order.

### Proof of Theorem 4.1

To obtain the desired recursive relation, we condition on the length of the
first cycle and study the number of cycles in the remaining set of elements.

Let ${\cal S}_{1}$ denote the cycle of the random permutation $\Pi$ containing
the number $1$ and let $L_{1}=\\#{\cal S}_{1}$ be the length of ${\cal S}_{1}$
so that ${\cal S}_{1}$ is an $L_{1}-$tuple. If $L_{1}=k\leq n-1,$ then $\Pi$
induces a permutation
$\sigma:\\{1,2,\ldots,n-k\\}\rightarrow\\{1,2,\ldots,n-k\\}$ on the remaining
$n-k$ numbers $\\{1,2,\ldots,n\\}\setminus{\cal S}_{1}$ in the following way.
Arrange the numbers in $\\{1,2,\ldots,n\\}\setminus{\cal S}_{1}$ in increasing
order $j_{1}<j_{2}<\ldots<j_{n-k}$ and suppose that $\pi(j_{l})=m_{l}$ for
$1\leq l\leq n-k.$ The induced permutation $\sigma$ then satisfies
$m_{l}=j_{\sigma(l)}$ for $1\leq l\leq n-k.$

Conditional on $L_{1}=k$ we now see that $\sigma$ is uniformly distributed in
the sense that for any deterministic permutation
$\sigma_{0}:\\{1,2,\ldots,n-k\\}\rightarrow\\{1,2,\ldots,n-k\\}$ we have

$\mathbb{P}_{n}\left(\sigma=\sigma_{0}|L_{1}=k\right)=\mathbb{P}_{n-k}(\sigma_{0})=\frac{1}{(n-k)!}.$
(4.4)

To see (4.4) is true, we first write

$\mathbb{P}_{n}\left(\sigma=\sigma_{0}|L_{1}=k\right)=\frac{\mathbb{P}_{n}\left(\\{\sigma=\sigma_{0}\\}\cap\\{L_{1}=k\\}\right)}{\mathbb{P}_{n}(L_{1}=k)}.$
(4.5)

If $k=1,$ then the numerator in the right side of (4.5) is $\frac{1}{n!}.$
Moreover, if the first cycle simply consists of the single element $1,$ then
the remaining $n-1$ numbers can be arranged in $(n-1)!$ ways and so
$\mathbb{P}_{n}(L_{1}=1)=\frac{(n-1)!}{n!}.$ Thus (4.4) is true for $k=1.$

For $2\leq k\leq n-1,$ we have from (4.5) that
$\mathbb{P}_{n}\left(\sigma=\sigma_{0}|L_{1}=k\right)$ equals

$\frac{\sum_{(i_{1},\ldots,i_{k-1})}\mathbb{P}_{n}\left(\\{\sigma=\sigma_{0}\\}\cap\\{{\cal
S}_{1}=(1,i_{1},\ldots,i_{k-1})\\}\right)}{\sum_{(i_{1},\ldots,i_{k-1})}\mathbb{P}_{n}({\cal
S}_{1}=(1,i_{1},\ldots,i_{k-1}))}\\\ $

where the summation is over all $k-1$ tuples $(i_{1},\ldots,i_{k-1})$
containing distinct elements. For any $(1,i_{1},\ldots,i_{k-1}),$ the term

$\mathbb{P}_{n}\left(\\{\sigma=\sigma_{0}\\}\cap\\{{\cal
S}_{1}=(1,i_{1},\ldots,i_{k-1})\\}\right)=\frac{1}{n!}$ (4.6)

and

$\mathbb{P}_{n}({\cal S}_{1}=(1,i_{1},\ldots,i_{k-1}))=\frac{(n-k)!}{n!}$
(4.7)

since there are $(n-k)!$ ways to permute the remaining $n-k$ elements of the
set
$\\{2,\ldots,n\\}\setminus\\{i_{1},\ldots,i_{k-1}\\}.$ Substituting (4.6) and
(4.7) into (4), we get (4.4).

Summing (4.7) over all $k-1$ tuples with distinct entries (for which there are
$(n-1)\cdot(n-2)\cdots(n-k+1)$ choices), we also get that
$\mathbb{P}_{n}(L_{1}=\\#{\cal S}_{1}=k)=\frac{1}{n}.$ From the discussion in
the previous paragraph, we get that the above relation holds for all $1\leq
k\leq n.$ Thus

$\mu_{n,s}=\mathbb{E}_{n}N_{n}^{s}=\sum_{k=1}^{n}\mathbb{E}_{n}(N_{n}^{s}|L_{1}=k)\mathbb{P}_{n}(L_{1}=k)=\frac{1}{n}\sum_{k=1}^{n}\mathbb{E}_{n}(N_{n}^{s}|L_{1}=k).$
(4.8)

If $k=n$ then $N_{n}=1$ and if $1\leq k\leq n-1,$ then $N_{n}=1+M_{n},$ where
$M_{n}$ is the number of cycles in the induced permutation $\sigma.$ Therefore
we get from (4.8) that

$\mu_{n,s}=\frac{1}{n}+\frac{1}{n}\sum_{k=1}^{n-1}\mathbb{E}_{n}\left((1+M_{n})^{s}|L_{1}=k\right).$
(4.9)

Using the conditional distribution equivalence (4.4), we have for $1\leq k\leq
n-1$ that $\mathbb{E}_{n}\left((1+M_{n})^{s}|L_{1}=k\right)$ equals

$\mathbb{E}_{n-k}(1+N_{n-k})^{s}=1+\sum_{r=1}^{s}{s\choose
r}\mathbb{E}_{n-k}N^{r}_{n-k},$ (4.10)

by the Binomial expansion. Substituting (4.10) into (4.9) we get (4.1). ∎

### Proof of Corollary 1

We begin with the proof of (4.2). Setting $s=1$ in (4.1) and
$\mu_{n}=\mu_{n,1},$ we get that $\mu_{1}=1$ and for $n\geq 2,$ we get that
$\mu_{n}$ satisfies (4.2). We first see by induction that $H_{n}$ as defined
in Proposition 1 satisfies (4.2). For $n=2,$ this statement is true and
suppose $H_{l}$ satisfies (4.2) for $1\leq l\leq n-1.$ For $l=n,$ the right
side of (4.2) evaluated with $\mu_{i}=H_{i}$ equals

$1+\frac{1}{n}\sum_{i=1}^{n-1}\sum_{j=1}^{i}\frac{1}{j}=1+\frac{1}{n}\sum_{j=1}^{n-1}\sum_{i=j}^{n-1}\frac{1}{j}=1+\frac{1}{n}\sum_{j=1}^{n-1}\frac{n-j}{j},$
(4.11)

by interchanging the order of summation in the second equality. The final term
in (4.11) equals $H_{n}$ and this proves the induction step.

Suppose now that $\\{b_{n}\\}$ is some sequence satisfying (4.2) with
$b_{1}=1$ and let $u_{n}=b_{n}-H_{n}$ denote the difference. The sequence
$\\{u_{n}\\}$ satisfies $u_{1}=0$ and $u_{n}=\frac{1}{n}\sum_{i=1}^{n-1}u_{i}$
for all $n\geq 2.$ Thus $u_{2}=\frac{u_{1}}{2}=0$ and iteratively, we get
$u_{n}~{}=~{}u_{2}~{}=~{}0$ for all $n\geq 2.$ Thus $H_{n}$ is the unique
sequence satisfying (4.2).

We now obtain the variance estimate as follows. Letting $d_{n}:=\mu_{n,2}$ and
$\mu_{n}:=\mu_{n,1}=H_{n},$ we get from (4.1) that

$d_{n}=1+\frac{1}{n}\sum_{i=1}^{n-1}(d_{i}+2\mu_{i})=2\mu_{n}-1+\frac{1}{n}\sum_{i=1}^{n-1}d_{i},$
(4.12)

since $\frac{1}{n}\sum_{i=1}^{n-1}\mu_{i}=\mu_{n}-1$ (see (4.2)). From (4.12)
we get that $v_{n}=d_{n}-\mu_{n}^{2}$ equals

$\displaystyle v_{n}$ $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n-1}(d_{i}-\mu_{i}^{2})+\frac{1}{n}\sum_{i=1}^{n-1}\mu_{i}^{2}-(\mu_{n}-1)^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n-1}v_{i}+\frac{1}{n}\sum_{i=1}^{n-1}\mu_{i}^{2}-(\mu_{n}-1)^{2}.$

It only remains to see that
$\frac{1}{n}\sum_{i=1}^{n-1}\mu_{i}^{2}-(\mu_{n}-1)^{2}=1-\frac{H_{n}}{n}$ and
for that we use $\mu_{i}=H_{i}=\sum_{j=1}^{i}\frac{1}{j}$ (see (4.2)) to first
get that $\frac{1}{n}\sum_{i=1}^{n-1}\mu_{i}^{2}$ equals

$\displaystyle\frac{1}{n}\sum_{i=1}^{n-1}\sum_{j_{1}=1}^{i}\sum_{j_{2}=1}^{i}\frac{1}{j_{1}\cdot
j_{2}}=\frac{1}{n}\sum_{j_{1}=1}^{n-1}\sum_{j_{2}=1}^{n-1}\sum_{i=\max(j_{1},j_{2})}^{n-1}\frac{1}{j_{1}\cdot
j_{2}}$
$\displaystyle\frac{1}{n}\sum_{j_{1}=1}^{n-1}\sum_{j_{2}=1}^{n-1}\frac{(n-\max(j_{1},j_{2}))}{j_{1}\cdot
j_{2}}=\frac{1}{n}\sum_{j_{1}=1}^{n-1}\Delta(j_{1}),$ (4.13)

where $\Delta(j_{1})=\sum_{j_{2}=1}^{j_{1}}\frac{n-j_{1}}{j_{1}\cdot
j_{2}}+\sum_{j_{2}=j_{1}+1}^{n-1}\frac{n-j_{2}}{j_{1}\cdot j_{2}}$ equals

$\sum_{j_{2}=1}^{n-1}\frac{n}{j_{1}\cdot
j_{2}}-\sum_{j_{2}=1}^{j_{1}}\frac{1}{j_{2}}-\sum_{j_{2}=j_{1}+1}^{n-1}\frac{1}{j_{1}}.$

Thus $\frac{1}{n}\sum_{i=1}^{n-1}\mu_{i}^{2}$ equals

$\sum_{j_{1}=1}^{n-1}\sum_{j_{2}=1}^{n-1}\frac{1}{j_{1}\cdot
j_{2}}-\frac{1}{n}\sum_{j_{1}=1}^{n-1}\sum_{j_{2}=1}^{j_{1}}\frac{1}{j_{2}}-\frac{1}{n}\sum_{j_{1}=1}^{n-1}\sum_{j_{2}=j_{1}+1}^{n-1}\frac{1}{j_{1}}.$
(4.14)

The first term in (4.14) is

$\sum_{j_{1}=1}^{n-1}\sum_{j_{2}=1}^{n-1}\frac{1}{j_{1}\cdot
j_{2}}=H_{n-1}^{2}=\left(H_{n}-\frac{1}{n}\right)^{2}$

and the second term in (4.14) is

$\frac{1}{n}\sum_{j_{1}=1}^{n-1}\sum_{j_{2}=1}^{j_{1}}\frac{1}{j_{2}}=\frac{1}{n}\sum_{j_{1}=1}^{n-1}H_{j_{1}}=H_{n}-1$

using the fact that $\mu_{n}=H_{n}$ satisfies (4.2). The third term in (4.14)
equals

$\frac{1}{n}\sum_{j_{1}=1}^{n-1}\frac{n-1-j_{1}}{j_{1}}=\left(\frac{n-1}{n}\right)\left(H_{n}-1-\frac{1}{n}\right)$

after rearrangement of terms. Substituting these three expressions into
(4.14), we get that $\frac{1}{n}\sum_{i=1}^{n-1}\mu_{i}^{2}$ equals
$1+(H_{n}-1)^{2}-\frac{H_{n}}{n},$ which is what we wanted to prove. Finally,
arguing as before, we also have that $M_{n}$ is the unique sequence satisfying
(4.3). ∎

### Acknowledgements

I thank Professors Rahul Roy, V. Guruswami, C. R. Subramanian and the referees
for crucial comments that led to an improvement of the paper. I also thank
IMSc for my fellowships.

## References

  * [1] Arratia, R. and Tavaré, S.,  The Cycle Structure of Random Permutations,  Ann. Probab., 20, 1567–1591 (1992).
  * [2] Balaji, S. B., Krishnan, M. N., Vajha, M., Ramkumar, V., Sasidharan, B., Kumar, P. V.,  Erasure Coding for Distributed Storage: An Overview,  Science China Information Sciences, 61 (2018).
  * [3] Betz V. and Schäfer, H.,  The Number of Cycles in Random Permutations Without Long Cycles is Asymptotically Gaussian,  ALEA, Lat. Am. J. Probab. Stat., 14, 427–444, (2017).
  * [4] Bhaskara, A., Desai, D. and Srinivasan, S.,  Optimal Hitting Sets for Combinatorial Shapes,  Theory of Computing, 9, 441–470, (2013).
  * [5] Forbes, M. and Yekhanin, S.,  On the Locality of Codeword Symbols in Non-linear Codes,  Discrete Mathematics, 324, 78–84, (2014).
  * [6] Gončarov, V.,  On the Field of Combinatory Analysis,  Amer. Math. Soc. Transl., 19, 1–46, (1962).
  * [7] Gopalan, P., Huang, C., Simitci, H. and Yekhanin, S.,  On the Locality of Codeword Symbols,  IEEE Transactions on Information Theory, 58, 6925–6934, (2012)..
  * [8] Graham, R., Knuth D. and Patashnik, O.,  Concrete Mathematics,  Addison–Wesley, (1989).
  * [9] Huffman, W. C. and Pless, V.,  Fundamentals of Error Correcting Codes,  Cambridge University Press (2003).
  * [10] Karpovsky, M. G., Chakrabarty, K., Levitin, L. B.,  On a New Class of Codes for Identifying Vertices in Graphs,  IEEE Transactions Information Theory, 44, 599–611, (1998).
  * [11] Linial, N., Luby, M., Saks, M. and Zuckerman, D.,  Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension,  Combinatorica, 17, pp. 215–234, (1997).
  * [12] Rashmi, K. V., Shah, N. B. and Kumar, P. V.,  Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction,  IEEE Transactions on Information Theory, 57, pp. 5227–5239, (2011).
  * [13] Shepp, L. A. and Lloyd, S. P.  Ordered Cycle Lengths in a Random Permutation,  Transactions of the American Mathematical Society, 121, pp. 340–357 (1966).
  * [14] Sunil Chandran, L.,  A Lower Bound for the Hitting Set Size for Combinatorial Rectangles and an Application,  Information Processing Letters, 86, pp. 75–78, (2003).


# Shadowing in non-compact spaces with a global attractor.

Gonzalo Cousillas

###### Abstract.

This paper studies the behavior of dynamical systems in non-compact spaces,
specifically focusing on the concepts of global attractors and shadowing. Let
$K$ be a compact global attractor. We show that the shadowing property holds
in certain types of dynamical systems in non-compact spaces if and only if $K$
is trivial.

###### Key words and phrases:

Topological shadowing property, global attractor.

###### 2000 Mathematics Subject Classification:

Primary: 37E30; Secondary: 37B20

##  1\. Introduction

Dynamical systems are a fundamental concept in mathematics, appearing in a
wide range of applications from physics to economics. In a dynamical system, a
set of variables evolve over time according to law of movement. The behavior
of the system can be studied by examining the long-term behavior of the
orbits.

One important concept in the study of dynamical systems is global attraction.
A global attractor is a subset of the phase space of a dynamical system
satisfying that all orbits eventually approach. The study of attractors has
important implications for understanding the long-term behavior of a system.

Much of the existing research on global attractors has focused on compact
spaces, where the phase space is bounded. In this paper, we study global
attractors on non-compact spaces.

Another important property of dynamical systems that has played an important
role is the pseudo-orbit tracing property or shadowing property. See [9, 8,
6]. It allows us to approximate a true orbit with a nearby orbit. This
property has important implications for numerical simulations of dynamical
systems, as it allows us to approximate the true solution with a simpler, more
computationally tractable solution. In the non-compact setting for the
shadowing to be a conjugacy invariant property the usual definition is adapted
[5].

In this paper, we study the shadowing property and its relation with the
existance of a gobal attractor and its topology in non-compact spaces. We
obtain the following two main results.

######  Theorem 1.

Let $X$ be a locally compact metric space, $f:X\to X$ a map and $p$ a globally
asymptotically stable fixed point. Then $f$ has the topological shadowing
property.

######  Theorem 2.

Let $f:{\mathbb{R}}^{n}\to{\mathbb{R}}^{n}$ be a homeomorphism such that there
exists $K$ is a compact global attractor for the dynamical system $(f,X)$.

$f$ has TSP if and only if $K$ is trivial.

##  2\. Preliminaries

Let $(X,d)$ be a metric space and $f$ a continuous map from $X$ to itself. A
point $p$ is a fixed point of the map $f$ if $f(p)=p$. A fixed point $p\in X$
is a globally attracting point provided that the orbit of every point tends to
$p$, and it is asymptotically stable if for every $\epsilon>0$ there exists
$\delta>0$ such that $d(x,p)<\delta$, implies $d(f^{n}(x),p)<\epsilon$ for
every $n>0$. Another definition of an attracting point which is not equivalent
to the previous one is to require the existence of an arbitrary small compact
neightborhood of $p$ such that $f(K)\subset int(K)$ and $\cap_{n\geq
0}f^{n}(K)=\\{p\\}$. We denote $C^{+}(X)$ the set of continuous and positive
functions from $X$ to ${\mathbb{R}}$. Let $\omega={\mathbb{N}}$ or
${\mathbb{Z}}$. Let $\delta\in C^{+}(X)$, a $\delta$-pseudo-orbit for $f$ is a
sequence $\\{x_{n}\\}_{n\in\omega}$ such that
$d(f(x_{n}),x_{n+1})<\delta(f(x_{n}))$ for every $n\in\omega$, i.e. the
$\delta$-error commited depends continuously on the position of the point
$f(x_{n})$. Let $\epsilon\in C^{+}(X)$, a $\delta$-pseudo-orbit
$\\{x_{n}\\}_{n\in\omega}$ is $\epsilon$-shadowed by an orbit if there exists
an orbit $\\{y_{n}\\}_{n\in\omega}$ such that $d(x_{n},y_{n})<\epsilon(x_{n})$
for all $n\in\omega$. A map $f$ satisfies the topological shadowing property
(TSP) if for all $\epsilon\in C^{+}(X)$ there exists $\delta\in C^{+}(X)$ such
that every $\delta$-pseudo-orbit is $\epsilon$-shadowed by an orbit.

In the literature, the shadowing property for non-invertible maps is
considered for pseudo-orbits and orbits indexed in the natural numbers [2, 7],
we will denote it forward topological shadowing property. In case $X$ is a
locally compact metric space both definitions are equivalent.

##  3\. Shadowing property for maps with a globally attracting fixed point

Kerékjártó proved that a planar homeomorphism with an asymptotically stable
fixed point is conjugate, on its basin of attraction, to one of the maps
$z\mapsto\frac{1}{2}z$ or $z\mapsto\frac{1}{2}\bar{z}$ depending on whether it
preserves or reverses the orientation. In a previos work made by the author
[3] it is shown that an homothety on ${\mathbb{R}}^{n}$ has the topological
shadowing property (TSP), and since it is preserved under topological
conjugacy, any system conjugate to an homothety has TSP too. Kerékjártó’s
theorem was also proved in ${\mathbb{R}}^{n}$ for $n\neq 4,5$. Then it is
known that any homeomorphism of ${\mathbb{R}}^{n}$ ($n\neq 4,5$) with a
globally asymptotically stable fixed point has the topological shadowing
property.

The purpose of this part is to prove the shadowing property for a dynamical
system with a globally asymptotically stable point (Theorem 1).

We adopt the definition of $p$ to be an attracting point if there exists a
compact neighborhood $K$ of $p$ such that $f(K)\subset int(K)$ and
$\cap_{n\geq 0}f^{n}(K)=\\{p\\}$. In addition we say that the $p$ is a
globally attracting point if $\cup_{n\geq 0}f^{-n}(K)=X$.

Denote $A_{1}=\overline{B(p,1)}$, $A_{i+1}=\overline{B(p,i+1)\setminus
B(p,i)}$ for every $i>0$ and $A^{n}_{i}=f^{n}(A_{i})$, for $n>0$.

To prove the shadowing property we will prove the forward shadowing property.
The idea is simple although the computations may not be. Since $p$ is a
globally attracting point and each $A_{i}=\overline{B(p,i)\setminus B(p,i-1)}$
is compact, the orbit of every $x\in A_{i}$ enters $B(p,i-1)$ in a uniform
finite time. We will define the $\delta_{i}>0$ inductively for
$i\in{\mathbb{N}}$. We choose $\delta_{i}>0$ small enough such that whenever
the orbit of $x$ enters $B(p,i-1)$, then the orbit and the
$\delta_{i}$-pseudo-orbit stay closer that $\delta_{i-1}$. We apply this
argument again for $A_{j}$, $j<i$ and keep control of the distance between the
orbit and the $\delta_{j}$-pseudo-orbit all the way until it finally enters
$f(K)$. We resume these ideas in the next lemma.

######  Lemma 3.

For every $i\in{\mathbb{N}}$, there exists $\delta_{i}>0$ and
$r_{i}\in{\mathbb{N}}$ satisfying that if $y\in A_{i}$ and
$\\{x_{n}\\}_{n\in{\mathbb{N}}}$ is a $\delta_{i}$-pseudo orbit such that
$d(y,x_{0})<\delta_{i}$ then $d(f^{r}(y),x_{r})<\delta_{i-1}$ for every $r\leq
r_{i}$.

###### Proof.

Take $K$ a neighborhood of $p$ of the definition of attracting point such that
$K\subset A_{1}$. For $A_{1}$, let $r_{1}>0$ be the first integer such that
$A_{1}^{r_{1}}\subset f(K)$. Take $\delta_{0}>0$, such that
$B(f(K),\delta_{0})\subset K$ Name $\alpha_{1r_{1}}=\delta_{0}$ and take
$\alpha_{1(r_{1}-1)}<\alpha_{1r_{1}}$ such that
$\overline{f(B(A_{1}^{r_{1}-1},\frac{\alpha_{1(r_{1}-1)}}{4}))}\subset
B(A_{1}^{r_{1}},\frac{\alpha_{1r_{1}}}{8})$. Then take
$\alpha_{1(r_{1}-2)}<\alpha_{1(r_{1}-1)}$ such that

$\overline{f(B(A_{1}^{r_{1}-2},\frac{\alpha_{1(r_{1}-2)}}{4}))}\subset
B(A_{1}^{r_{1}-1},\frac{\alpha_{1(r_{1}-1)}}{8}).$

Continue this procedure to finally obtain $\alpha_{10}<\alpha_{11}$ such that

$\overline{f(B(A_{1},\frac{\alpha_{10}}{4}))}\subset
B(A_{1}^{1},\frac{\alpha_{11}}{8}).$

This way if $x,y\in\overline{B(A_{1}^{r},\frac{\alpha_{1r}}{4})}$ and
$d(x,y)<\frac{\alpha_{1r}}{4}$, then $d(f(x),f(y))<\frac{\alpha_{1(r+1)}}{8}$
for $0\leq r<r_{1}$. Choose $\delta_{1}<\alpha_{10}/8$. Now take $y\in A_{1}$
and $\\{x_{n}\\}_{n\in{\mathbb{N}}}$ a $\delta_{1}$-pseudo-orbit such that
$d(y,x_{0})<\delta_{1}$ -then $d(y,x_{0})<\alpha_{10}/4$-. For $r=1$, it holds
that

$d(f(y),x_{1})\leq\underbrace{d(f(y),f(x_{0}))}_{<\frac{\alpha_{11}}{8}}+\underbrace{d(f(x_{0}),x_{1})}_{<\delta_{1}<\frac{\alpha_{11}}{8}}<\frac{\alpha_{11}}{4}<\delta_{0}.$

Now suppose that $d(f^{r-1}(y),x_{r-1})<\frac{\alpha_{1(r-1)}}{4}$ for some
$r\in\\{2,\ldots,r_{1}\\}$, then

$d(f^{r}(y),x_{r})\leq\underbrace{d(f^{r}(y),f(x_{r-1})}_{<\frac{\alpha_{1r}}{8}}+\underbrace{d(f(x_{r-1}),x_{r})}_{<\delta_{1}<\frac{\alpha_{1r}}{8}}<\frac{\alpha_{1r}}{4}<\delta_{0}.$

Next consider $A_{2}$ and let $r_{2}>0$ be the first integer such that
$A_{2}^{r_{2}}\subset A_{1}$. We take $B(A_{2}^{r_{2}},\delta_{1})$ and
proceed similarly to the previous lines finding other $\alpha_{2r}$ and
finally $\delta_{2}<\delta_{1}$. This way, if $y\in A_{2}$ and
$\\{x_{n}\\}_{n\in{\mathbb{N}}}$ is a $\delta_{2}$-pseudo-orbit such that
$d(y,x_{0})<\delta_{2}$, then

$d(f^{r}(y),x_{r})\leq\underbrace{d(f^{r}(y),f(x_{r-1})}_{<\frac{\alpha_{r}}{8}}+\underbrace{d(f(x_{r-1}),x_{r})}_{<\delta_{2}<\frac{\alpha_{r}}{8}}<\frac{\alpha_{r}}{4}<\delta_{1}$

for every $r\leq r_{2}$.

We proceed inductively for every $A_{i}$ considering $r_{i}$ the first
positive integer such that $A_{i}^{r_{i}}\subset B(p,i-1)$. By construction of
the $\delta_{i}$ the result follows.

∎

######  Remark 4.

Suppose we take some $x_{0}\in A_{i_{0}}$. We know by the previous lemma that
a $\delta_{i_{0}}$-pseudo-orbit $\\{x_{n}\\}_{n\in{\mathbb{N}}}$ starting at
$x_{0}$ stays closer than $\delta_{i_{0}-1}$ of the orbit of $x_{0}$ until it
enters $\overline{B(p,i_{0}-1)}$. Once this happens we can identify the first
$r\in{\mathbb{N}}$ such that $f^{r}(x_{0})\in\overline{B(p,i_{0}-1)}$, then
$f^{r}(x_{0})\in A_{i_{1}}$ for some $i_{1}<i_{0}$ and
$d(f^{r}(x_{0}),x_{r})<\delta_{i_{0}-1}\leq\delta_{i_{1}}$. This way we apply
the previous lemma again to the points $f^{r}(x_{0})$ and $x_{r}$ considering
now $\\{x_{n}\\}_{n>r}$ as a $\delta_{i_{1}}$-pseudo-orbit. This procedure
ends once the orbit of $x_{0}$ enters $K$.

###### Proof of Theorem 1.

Without loss of generality take $p=0$. Given an arbitrary $\epsilon\in
C^{+}(X)$, take $\epsilon(0)>0$ and a positive real number
$\alpha:\,\alpha<\epsilon(0)/4$ such that if $y\in B(0,\alpha)$, then
$\epsilon(y)>\epsilon(0)/2$. Take $K$ of the definition of attracting point
for $0$ such that $int(K)\subset B(0,\alpha)$. Notice that since every
$A_{i}=\overline{B(0,i)\setminus B(0,i-1)}$ is compact and $0$ is a globally
attracting point, there exists $n_{i}\in{\mathbb{N}}$ such that
$A_{i}^{n}\subset f(K)$ for every $n\geq n_{i}$.

For each $A_{i}$ take $s_{i}>0$ the minimum integer such that $\bigcup_{r\geq
0}A_{i}^{r}\subset B(0,s_{i})$. Then for $A_{1}$ consider
$0<\delta_{0}<\min\\{\epsilon(x):x\in\overline{B(0,s_{1})}\\}$ such that
$B(f(K),\delta_{0})\subset K$. For $\delta_{0}$ take $\hat{\delta}_{1}$
corresponding to $A_{1}$ of the previous Lemma. For $A_{2}$ consider
$0<\delta_{1}<\min\\{\epsilon(x):x\in\overline{B(0,s_{2})},\hat{\delta}_{1}\\}$.
For $\delta_{1}$ we take $\hat{\delta}_{2}$ of the previous Lemma. Inductively
we define $\delta_{i}$ for every $i>0$ such that
$0<\delta_{i}<\min\\{\epsilon(x):x\in\overline{B(0,s_{i+1})},\hat{\delta}_{i}\\}$.
Now since we have defined the $\delta_{i}>0$ in each annulus $A_{i}$ we can
take $\delta\in C^{+}(X)$ depending only on the norm of $x$ such that
$\delta(x)<\delta_{i}$ for every $x\in A_{i}$.

Let $\\{x_{n}\\}_{n\in{\mathbb{N}}}$ be a $\delta$-pseudo-orbit such that
$x_{0}\in A_{i}$. Then $\\{x_{n}\\}_{n\in{\mathbb{N}}}$ is a
$\delta_{i}$-pseudo-orbit until it enters $\overline{B(0,i-1)}$. Suppose
$r_{i}$ is the first integer such that
$f^{r_{i}}(x_{0})\in\overline{B(0,i-1)}$. Then

$d(f^{n}(x_{0}),x_{n})<\delta_{i-1}<\epsilon(f^{n}(x_{0})),\;\;\;\;\mbox{ for
}n\leq r_{i}.$

Now $f^{r_{i}}(x_{0})\in A_{j}$ for some $j<i$, then
$d(f^{r_{i}}(x_{0}),x_{r_{i}})<\delta_{j}$. Let $r_{j}$ be the first time such
that $f^{r_{j}+r_{i}}(x_{0})\in\overline{B(0,j-1)}$. Since
$\delta(x)<\delta_{j}$ for every $x\in A_{j}$,
$\\{x_{n}\\}_{n\in{\mathbb{N}}}$ is a $\delta_{j}$-pseudo-orbit for
$r_{i}<n\leq r_{i}+r_{j}$. Then

$d(f^{n}(x_{0}),x_{n})<\delta_{j-1}<\epsilon(f^{n}(x_{0})),\;\;\;\;\mbox{ for
}r_{i}<n\leq r_{i}+r_{j}.$

We repeat this procedure until the orbit of $x_{0}$ enters $f(K)$. For $n$
such that $f^{n}(x_{0})\in f(K)$ it holds that $x_{n}\in K$, then

$d(f^{n}(x_{0}),x_{n})\leq\underbrace{d(f^{n}(x_{0}),0)}_{<\alpha}+\underbrace{d(0,x_{n})}_{<\alpha}<\epsilon(0)/2<\epsilon(f^{n}(x_{0}))$

We finally obtain that the orbit of $x_{0}$ $\epsilon$-shadows this
$\delta$-pseudo-orbit for every $n>0$. This proves the forward shadowing
property. Then $f$ has TSP. ∎

##  4\. Global attractors and the TSP for homeomorphisms

Now we address the following question: Is it possible for a homeomorphism $f$
of a non-compact metric space with a non-trivial global attractor to satisfy
the TSP?

We answer this by Theorem 2, which states that:
Let $X$ be an unbounded locally path connected metric space, $f:X\to X$ be a
homeomorphism such that there exists $K$ is a compact global attractor for the
dynamical system $(f,X)$.

$f$ has TSP if and only if $K$ is trivial.

Recall that $K$ is a global attractor if there exists an open neighborhood $U$
of $K$ such that $f(\overline{U})\subset U$, $K=\bigcap_{n\geq 0}f^{n}(U)$ and
$X=\bigcup_{n\geq 0}f^{-n}(U)$.

We recall a very important consequence of the shadowing property in non-
compact spaces.

######  Lemma 5.

[4, Remark 1 and Lemma 2] Let $X$ be an unbounded metric space, $f:X\to X$ be
a homeomorphism with the TSP. If $\\{y_{n}\\}_{n\in{\mathbb{Z}}}$ is an orbit
such that $y_{n}$ comes from infinity when $n\to-\infty$, then any pseudo-
orbit $\\{x_{n}\\}_{n\in{\mathbb{Z}}}$ such that $x_{n}=y_{n}$ for $n<0$, is
shadowed by $\\{y_{n}\\}_{n\in{\mathbb{Z}}}$.

######  Definition 6 (Lyapunov Stability).

A point $x$ is Lyapunov stable if given $\epsilon>0$, there exists $\delta>0$
such that $d(x,y)<\delta$, implies $d(f^{n}(x),f^{n}(y))<\epsilon$ for every
$n>0$.

######  Lemma 7.

Let $f:X\to X$ be a homeomorfism with TSP, $K$ a compact global attractor. If
$x\in\partial K$, then $x$ is Lyapunov stable.

###### Proof.

Let $x\in\partial K$. Given $\epsilon>0$, take $\tilde{\epsilon}\in C^{+}$
such that $\tilde{\epsilon}(f^{n}(x))<\epsilon/4$ for every $n\geq-1$, and
such that $\tilde{\epsilon}(y)<\epsilon/2$ for every $y\in
B(f^{n}(x),\epsilon/4)$. For $\tilde{\epsilon}$ we take $\tilde{\delta}\in
C^{+}$ of the shadowing property. Since $K$ is a global attractor, there
exists $\bar{x}\in B(x,\tilde{\delta}(x)/2)$ such that
$\|f^{-n}(\bar{x})\|\to\infty$ as $n\to+\infty$, satisfying $x\in
B(\bar{x},\tilde{\delta}(\bar{x}))$, $f^{-1}(x)\in
B(f^{-1}(\bar{x}),\tilde{\delta}(f^{-1}(\bar{x})))$.

We consider the following two $\tilde{\delta}$-pseudo-orbits:
$\\{z_{n}\\}_{n\in{\mathbb{Z}}}$ such that

$z_{n}=\begin{cases}f^{n}(\bar{x})&n<0\\\ f^{n}(x)&n\geq 0\end{cases}$

and $\\{y_{n}\\}_{n\in{\mathbb{Z}}}$ such that

$y_{n}=\begin{cases}f^{n}(\bar{x})&n<-1\\\ f^{-1}(x)&n=-1\\\ f^{n}(y)&n\geq
0\end{cases}$

for every $y\in B(x,\tilde{\delta}(x)/2)$. Both $\tilde{\delta}$-pseudo-orbits
are $\tilde{\epsilon}$-shadowed by $\\{f^{n}(\bar{x})\\}_{n\in{\mathbb{Z}}}$.
Then $d(f^{n}(x),f^{n}(y))\leq
d(f^{n}(x),f^{n}(\bar{x}))+d(f^{n}(\bar{x}),f^{n}(y))<\tilde{\epsilon}(f^{n}(x))+\tilde{\epsilon}(f^{n}(\bar{x}))<\epsilon/4+\epsilon/2$
for every $n>0$ and we have $f^{n}(y)\in B(f^{n}(x),\epsilon)$ for $n\geq 0$.
Taking $\delta=\tilde{\delta}(x)/2$ the result follows. ∎

Next we mention a theorem relating to Lyapunov stability of every point in
$\partial K$ with the existence of an equivalent metric such that
$f|_{\partial K}$ is a weak contraction.

######  Lemma 8.

[1, Theorem 2.1] Let $(X,d)$ be a metric space, $f:X\to X$ a continuous map.
It is equivalent:

  1. a.

Every $x\in X$ is Lyapunov stable.

  2. b.

The metric $d_{f}(x,y)=\sup_{n\in{\mathbb{N}}}d(f^{n}(x),f^{n}(y))$ is
equivalent to $d$ and $f$ is a weak contraction respecto to $d_{f}$

######  Remark 9.

Since every $x\in\partial K$ is Lyapunov stable, there exists a metric $d^{*}$
equivalent to $d$ in $\partial K$ such that $f|_{\partial K}$ is a weak
contraction.

Suppose $\partial K$ is connected.

######  Lemma 10.

If $f|_{\partial K}$ is a weak contraction, then for every $a,b\in\partial K$
there exists a pseudo-orbit coming from infinity passing through $a$ and
$f^{n}(b)$ for some $n\in{\mathbb{N}}$.

###### Proof.

Take $d^{*}$ of the previous Remark. Let $a,b\in\partial K$, given $\delta>0$,
consider a $\delta$-chain $\\{a=x_{0},x_{1},\ldots,x_{n}=b\\}$ for some
$n\in{\mathbb{N}}$, i.e. $d^{*}(x_{i},x_{i+1})<\delta$ for $0\leq i\leq n-1$.
Let $x\in B(a,\delta)\cap B$, where $B$ is the bassin of attraction of $K$.
Take $\\{\tilde{x}_{k}\\}_{k\in{\mathbb{Z}}}$ such that

$\tilde{x}_{k}=\begin{cases}f^{k}(x)&\mbox{if }k<0\\\ f^{k}(x_{k})&\mbox{if
}0\leq k<n\\\ f^{k}(b)&\mbox{if }k\geq n\end{cases}.$

Let us see that $\\{\tilde{x}_{k}\\}_{k\in{\mathbb{Z}}}$ is a $\delta$-pseudo-
orbit: for $k<0$ and $k\geq n$ it is immediate; if $0\leq k<n$, then
$d^{*}(f(\tilde{x}_{k}),\tilde{x}_{k+1})=d^{*}(f^{k+1}(x_{k}),f^{k+1}(x_{k+1}))\leq
d^{*}(x_{k},x_{k+1})<\delta$. ∎

######  Lemma 11.

If $f$ has TSP, then every pair of points in $\partial K$ are asymptotic,
i.e.: given $a,b\in\partial K$ and $\epsilon>0$, there exists $n$ such that
$d(f^{k}(a),f^{k}(b))<\epsilon$ for every $k\geq n$.

###### Proof.

Take $d$ of the previous Remark. Given $a,b\in\partial K$ and $\epsilon>0$, we
choose $\delta>0$ of the shadowing property corresponding to $\epsilon/2$.
Take on one hand $(\tilde{x}_{k})_{k\in{\mathbb{Z}}}$ a $\delta$-pseudo-orbit
of Lemma 10 such thath

$\tilde{x}_{k}=\begin{cases}f^{k}(x)&\mbox{if }k<0\\\ f^{k}(x_{k})&\mbox{if
}0\leq k<n\\\ f^{k}(b)&\mbox{if }k\geq n\end{cases},$

for $x\in B(a,\delta)\cap B$. On the other hand
$(\tilde{y}_{k})_{k\in{\mathbb{Z}}}$ such that

$\tilde{y}_{k}=\begin{cases}f^{k}(x)&\mbox{if }k<0\\\ f^{k}(a)&\mbox{if }k\geq
0\end{cases}.$

Note that by Lemma 5 both $\delta$\- pseudo-orbits are $\epsilon$-shadowed by
the orbit of $x$. Then

$d(f^{k}(a),f^{k}(b))\leq d(f^{k}(a),f^{k}(x))+d(f^{k}(x),f^{k}(b))<\epsilon.$

for $k\geq n$. ∎

######  Theorem 12.

If $f$ has TSP, then $\partial K$ is trivial.

###### Proof.

Take $d$ such that $f|_{\partial K}$ is a weak contraction. Suppose $\partial
K$ is not trivial. Then $diam(\partial K)>0$. Since $\partial K$ is compact,
there exists $a,b\in\partial K$ such that $diam(\partial K)=d(a,b)$. Note that
$d(f^{-k}(a),f^{-k}(b))=d(a,b)$ for every $k>0$. Let $\tilde{a}\in\alpha(a)$,
then there exists a subsequence of $\\{\ f^{-k}(a)\\}_{k\in{\mathbb{N}}}$
converging to $\tilde{a}$. Take a subsubsequence of
$\\{f^{-k}(b)\\}_{k\in{\mathbb{N}}}$ indexed as the previous subsequence, then
$\tilde{b}$ a limit point. It holds that $d(\tilde{a},\tilde{b})=d(a,b)$. This
two points are not asymptotic: consider $\epsilon<d(a,b)/2$, for each $n$ take
$n_{i}>n$ of the previous subsequence. Then

$\displaystyle d(f^{n_{i}}(\tilde{a}),f^{n_{i}}(\tilde{b}))$ $\displaystyle=$
$\displaystyle
d(f^{n_{i}}(\lim_{n_{k}}f^{-n_{k}}(a)),f^{n_{i}}(\lim_{n_{k}}f^{-n_{k}}(b)))$
$\displaystyle=$
$\displaystyle\lim_{n_{k}}d(f^{n_{i}-n_{k}}(a),f^{n_{i}-n_{k}}(b))$
$\displaystyle=$ $\displaystyle d(a,b)$ $\displaystyle>$
$\displaystyle\epsilon$

This concludes the proof. ∎

###### Proof of Theorem 2.

For the converse we apply Theorem 1 to the case of a homeomorphism. For the
direct, by the previous Theorem we have that $\partial K$ is trivial, name
$\\{p\\}=\partial K$. Suppose $K\neq\partial K$, then $intK\neq\emptyset$.
Take $U$ an open neigborhood of $p$ and $q,r\in U$ such that $q\in int(K)$,
$r\in int(K^{c})$. Then take two different arcs $\gamma$ and $\gamma^{\prime}$
whose extreme poins are $q$ and $r$ such that
$\gamma\cap\gamma^{\prime}=\\{q,r\\}$. Then $\gamma\cap\partial
K\neq\emptyset$ and $\gamma^{\prime}\cap\partial K\neq\emptyset$. This implies
$\partial K$ is not trivial. A contradiction. ∎

## References

  * [1] Ethan Akin, Joseph Auslander, and Kenneth Berg.  When is a transitive map chaotic?  In Convergence in ergodic theory and probability (Columbus, OH, 1993), volume 5 of Ohio State Univ. Math. Res. Inst. Publ., pages 25–40. de Gruyter, Berlin, 1996.
  * [2] J. H. Brown and J. O. Warren.  The strong shadowing property on the unit interval.  Elec. Journal of Undergrad Math, 4, 1998.
  * [3] G. Cousillas.  A fixed point theorem for plane homeomorphisms with the topological shadowing property.  Arxiv.org, 2017.
  * [4] G. Cousillas, J. Groisman, and J. Xavier.  Topologically anosov plane homeomorphisms.  TMNA, 54(1):371–382, 2019.
  * [5] T. Das, K. Lee, D. Richeson, and J. Wiseman.  Spectral decomposition for topologically Anosov homeomorphisms on noncompact and non-metrizable spaces.  Topology Appl., 160(1):149–158, 2013.
  * [6] D. W. Pearson.  Shadowing and prediction of dynamical systems.  Math. Comput. Modelling.
  * [7] T. Pennings and J. Van Eeuwen.  Pseudo-orbit shadowing on the unit interval.  Real Anal. Exchange, 16(1):238–244, 1990/91.
  * [8] S. Yu. Pilyugin.  Shadowing in dynamical systems, volume 1706 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, 1999.
  * [9] P. Walters.  On the pseudo-orbit tracing property and its relationship to stability.  Lecture Notes in Math. Springer., 668:231–244, 1978.


# Quantum hard disks on a lattice

Vighnesh Dattatraya Naik  Fabian Ballar Trigueros  Markus Heyl  Theoretical
Physics III, Center for Electronic Correlations and Magnetism, Institute of
Physics, University of Augsburg, 86135 Augsburg, Germany

###### Abstract

We formulate a quantum version of the hard-disk problem on lattices, which
exhibits a natural realization in systems of Rydberg atoms. We find that
quantum hard disks exihibit unique dynamical quantum features. In 1D, the
crystal melting process displays ballistic behavior as opposed to classical
sub-diffusion. For 2D, crystal structures remain intact against most defects,
whereas classically they are washed out completely. We link this peculiar
quantum behavior to quantum many-body scars. Our study highlights the
potential of constrained 2D quantum matter to display unique dynamical
behaviors.

††preprint: APS/123-QED

Introduction.—The recent tremendous advances in quantum simulators have led to
unprecedented experimental control of the real-time dynamics in constrained
quantum matter. This includes constraints generated by symmetries such as
dipole conservation relating to fractonic systems Guardado-Sanchez  _et al._
(2020); Scherg  _et al._ (2021); Kohlert  _et al._ (2023) or strong local
interactions Bernien  _et al._ (2017); Keesling  _et al._ (2019); de Léséleuc
_et al._ (2019); Browaeys and Lahaye (2020); Ebadi  _et al._ (2021); Semeghini
_et al._ (2021); Scholl  _et al._ (2021); Bluvstein  _et al._ (2021), which
can lead to the emergence of quantum many-body scars Bernien  _et al._ (2017);
Turner  _et al._ (2018); Serbyn  _et al._ (2021); Bluvstein  _et al._ (2021).
The latter case nowadays finds a natural realization in Rydberg atom arrays
due to the famous Rydberg blockade mechanism originating from the strong
underlying Rydberg interactions Browaeys and Lahaye (2020). It is of key
importance to recognize that Rydberg blockade, on a general level, is
equivalent to associating with each excitation an excluded volume, which on
the classical level represents a paradigmatic class of systems with unique
properties, such as in the context of the hard-disk problem Li  _et al._
(2022). In the quantum domain, the equilibrium properties of hard disks in the
continuum have been already investigated Huang and Yang (1957); Luban (1965);
Lieb (1967); Winer  _et al._ (2023). However, the exploration of quantum hard
disks on a lattice and their associated dynamical properties has, until now,
remained unexplored.

In this work, we introduce a quantum hard-disk model on lattices inspired by
current experiments in Rydberg atom arrays. We show that the static properties
at high temperatures are identical to the classical analogue yielding
crystalline phases at sufficiently high particle densities. However, we find
that the dynamical features turn out to be fundamentally different, which we
illustrate with a crystal melting process in one spatial dimension (1D) and
the dynamics of crystal defects in two-dimensional (2D) quantum hard-disk
systems. In particular, for the 2D case we observe that, generically, the
crystals remain intact in the presence of defects, while they are washed out
on the classical level. We associate this unique quantum feature with the
presence of quantum many-body scars and Hilbert-space fragmentation. We
discuss the feasibility of implementing the quantum hard-disk problem
experimentally in Rydberg atom arrays as the natural platform to realize
excluded volumes through the Rydberg blockade mechanism.

Figure 1: Hilbert-space fragmentation and 2D phase diagram. (A) An
illustration of the considered hard-disk models on 1D chains and 2D square
lattices. (B) Hilbert-space fragmentation in 2D as a function of particle
density with representative configurations. (C) Infinite-temperature structure
factor in 2D as a function of particle density $\eta$ for several system sizes
$L\times L$.

The quantum hard-disk model on a lattice.— We model the quantum hard-disk
problem as a system of hard-core bosons on a lattice with nearest-neighbor
hopping:

$H=J\sum_{\langle
i,j\rangle}P_{i}\left({a}_{i}^{\dagger}a_{j}+a_{j}^{\dagger}a_{i}\right)P_{j}.$
(1)

Here, $a_{i}^{\dagger}$ and $a_{i}$ are the corresponding creation and
annihilation operators for a hard-core boson on lattice site $i=1,\dots
L^{d}$, respectively, with $L^{d}$ denoting the total number of lattice sites,
and $d$ is the dimension of the lattice. We set the lattice constant $a=1$ in
the following.

The excluded volume due to the hard disk we include through the projection
operators $P_{i}=\prod_{j\ni|\vec{r}_{i}-\vec{r}_{j}|=1}(1-n_{j})/2$, that
prevents particles from occupying nearest-neighboring sites (see Fig. 1A for
an illustration), and $n_{i}\equiv a_{i}^{\dagger}a_{i}$. Notice, that it is
straightforward to adjust the disk radius by adjusting these projection
operators to include more lattice sites. The above Hamiltonian is equivalent
to a model of spin-1/2’s upon identifying $a_{i}\mapsto S_{i}^{-}$,
$a_{i}^{\dagger}\mapsto S_{i}^{+}$, and $n_{i}\mapsto S_{i}^{z}+1/2$ Kwan  _et
al._ (2023), which links directly to a system of Rydberg atoms, see below for
a more detailed discussion on the potential experimental realization. We will
consider open boundary conditions for convenience, which is also motivated by
potential experimental scenarios in quantum simulators.

Hilbert-space fragmentation.—A general feature of strong local constraints is
the fragmentation of the Hilbert space into kinetically disconnected regions
Pai  _et al._ (2019); Sala  _et al._ (2020); Rakovszky  _et al._ (2020);
Khemani  _et al._ (2020); Moudgalya and Motrunich (2022); Smith  _et al._
(2017a, b); Brenes  _et al._ (2018); Russomanno  _et al._ (2020); Karpov  _et
al._ (2021); Chakraborty  _et al._ (2022a, b), which can have drastic
consequences on dynamical properties such as the emergence of quantum many-
body scars Bernien  _et al._ (2017); Turner  _et al._ (2018); Michailidis  _et
al._ (2020); Serbyn  _et al._ (2021) or disorder-free localization in gauge
theories Smith  _et al._ (2017a, b); Brenes  _et al._ (2018); Russomanno  _et
al._ (2020); Karpov  _et al._ (2021); Chakraborty  _et al._ (2022a, b). In the
thermodynamic limit one can distinguish weakly
($\mathcal{N}_{\textrm{max}}/\mathcal{N}\rightarrow 1$) and strongly
fragmented regimes ($\mathcal{N}_{\textrm{max}}/\mathcal{N}\rightarrow 0$)
Moudgalya and Motrunich (2022), where $\mathcal{N}_{\textrm{max}}$ denotes the
size of the largest fragment and $\mathcal{N}$ the Hilbert-space dimension.

In the 1D case, we find that there is no fragmentation except at the maximum
particle density $\eta=1/2$. However, in 2D, the system exhibits both weak and
strong fragmentation depending on the particle density $\eta=M/L^{d}$ with $M$
the total number of particles, see Ref. Kwan  _et al._ (2023). Now we
determine the precise threshold densities, illustrated in Fig. 1 B. A
configuration with occupied sites on the diagonal (termed a snake) is a static
object due to the excluded volume and creates a barrier confining particles to
the two regions. Consequently, we obtain Hilbert-space fragmentation whenever
the particle density $\eta\geq 1/L$ or equivalently whenever the particle
number $M\geq L$ becomes larger than the linear extent $L$ of the system. For
not too high densities, this leads to a weakly fragmented situation with the
Hilbert space breaking up into several small fragments containing the states
with snakes and a large fragment without snakes. However, when
$\eta\geq(1/2)-\lceil L/2\rceil/L^{2}$ (with $\lceil L/2\rceil$ denoting the
ceiling operation), each allowed configuration must contain at least one snake
or completely filled diagonals adjacent to the main diagonal, preventing large
fragments and leading to strong fragmentation.

Fragmentation also facilitates the numerical solution by means of exact
diagonalization. To simulate the quantum dynamics, instead of addressing the
full Hamiltonian, we only solve for the relevant Hamiltonian blocks. For the
dynamics, we employ a Lanczos algorithm with 7 Krylov vectors at each time
step. We choose the time steps as large as possible while still achieving
convergence. In a subsequent section, we will compare the resulting quantum
dynamics to a classical analog. Viewing quantum dynamics as a quantum walk of
hard disks on the lattice, we perform its natural classical counterpart—the
random walk.

Static properties.—Let us first discuss the static equilibrium properties of
the quantum hard-disk problem on a lattice. Since we will be mostly interested
in the dynamics at high energies, we focus in the following on the case of
infinite temperature $T=\infty$. Classically, it is known that there is a
dilute-crystalline phase transition in 2D Fernandes  _et al._ (2007). Since
the crystalline phase can be characterized by the structure factor, here we
also take it as the natural order parameter:
$C_{\infty}(\eta)=N^{-1}(2\pi/L^{d})^{2}\sum_{i,j}e^{i\vec{\pi}\cdot(\vec{r}_{i}-\vec{r}_{j})}\operatorname{Tr}\left(n_{i}\,n_{j}\right)$.
The trace is taken for the Hamiltonian blocks with particle density $\eta$,
$N$ denotes the number of states in the block, and $\vec{\pi}$ is $\pi$ for 1D
and equal to $(\pi,\pi)$ for 2D. Clearly, there is no difference to the
classical case because the quantum trace becomes equal to the sum over all
classical configurations and therefore the static phase diagrams are
identical.

In 1D, this implies that there is crystalline order only at $\eta=1/2$. For
2D, the system exhibits a critical particle density $\eta_{c}=0.37$ with a
crystalline phase for $\eta>\eta_{c}$ Fernandes  _et al._ (2007). Notice that
the crystalline phase transition is located in the weakly fragmented regime
detached from the fragmentation thresholds. The finite-size behavior of the
structure factor we display in Fig. 1C. In the next step, we aim to study the
dynamical properties, which will exhibit distinct quantum features.

Crystal melting in 1D.—For the 1D case, we study the melting of a finite-size
crystal object of $M$ tightly packed particles embedded in an otherwise empty
lattice. In Fig. 2, we display the numerically obtained data for the local
occupations $\langle n_{i}(t)\rangle$. We observe that the spreading of the
occupations exhibits fundamentally different behaviors in the quantum and
classical cases, which can be proven analytically by mappings to effective
models where the excluded volume is eliminated. In the quantum domain, this
can be achieved by removing the site to the right of each particle in every
basis configuration. The unitary dynamics are then equivalent to the single-
particle quantum walk that is known to be ballistic, which is consistent with
the results in Fig. 2 and with the Bethe-ansatz integrability of the 1D model
Alcaraz and Bariev (1999); Pozsgay  _et al._ (2021). In the classical domain,
one can perform a mapping from the hard-disk model to one where disks have no
radius Grabsch  _et al._ (2023), where, however, it is key to take into
account that due to the hard-core interaction particles cannot pass through
each other implying preservation of the order of particles. The dynamics turn
then out to be sub-diffusive according to the Kardar-Parisi-Zhang universality
class Grabsch  _et al._ (2023). As a key consequence, we find that the 1D
quantum crystal melts much faster than the classical one.

Figure 2: Crystal melting in 1D comparing quantum versus classical dynamics.
The average on-site occupation $\langle n_{i}(t)\rangle$ is displayed as a
function of time $Jt$ for an initial finite-size crystal with $M=5$ particles.
Due to the symmetry of the spreading about the center of the crystal, we show
the quantum and classical melting on the left and right halves, respectively.
The classical time as a function of the number of steps taken
$N_{\textrm{steps}}$ is given by, $Jt=2\pi N_{\textrm{steps}}/M$. Figure 3:
Defect dynamics on the square lattice comparing quantum and classical
dynamics. (A) Initial defect configuration for a $8\times 8$ lattice with
density $\eta=25/64$. (B) Long-time occupations $\langle n_{i}(t)\rangle$ at
$Jt=750$ for the quantum (C) as well as the classical case. (D) Memory of the
initial condition as measured through the autocorrelation function $G(t)$ for
both the classical and quantum dynamics as a function of time $Jt$. The
classical average is computed for $10^{6}$ trajectories.

Defect dynamics in 2D.— We will now explore the nonequilibrium real-time
evolution of crystal defects in 2D and we will show that their dynamics
exhibit genuine quantum features. For that purpose, we prepare the system in a
specific many-body configuration and monitor the subsequent dynamics, see Fig.
3. In the beginning, let us briefly discuss the limits of weak and high
particle densities. Clearly, preparing a configuration with density $\eta<1/L$
in the non-fragmented regime the excluded volume becomes irrelevant and the
dynamics of the particles becomes essentially equivalent to a simple tight-
binding problem and any initial configuration is smeared out uniformly. In the
opposite regime $\eta\geq(1/2)-\lceil L/2\rceil/L^{2}$, the strong
fragmentation of Hilbert space naturally leads to nonergodic behavior leaving
any crystal intact.

Most importantly, in the regime of weak fragmentation, the dynamics yields
unexpected behavior, see Fig. 3. For the initial configuration in Fig. 3(A),
we observe that the detailed crystal structure remains stable under quantum
evolution, whereas classically the crystal structure is completely washed out.
Accordingly, the quantum system retains a memory as opposed to the classical
counterpart calling for the importance of quantum interference effects, a key
aspect absent in the random walk. As we will discuss, this is a generic
behavior not fine-tuned to this particular initial condition. We quantify the
memory of the crystal pattern through:

$G(t)=\frac{1}{L^{2}}\sum_{i=1}^{L^{2}}\left\langle\left(2n_{i}(t)-1\right)\left(2n_{i}(0)-1\right)\right\rangle-G^{*}~{}.$
(2)

Here, $\langle\dots\rangle=\langle\psi|\dots|\psi\rangle$ represents the
expectation value with $|\psi\rangle$ the initial condition for the quantum
case and an average over trajectories for the classical one. A constant
$G^{*}=\left(2\eta-1\right)^{2}$ is subtracted such that $G(t)\rightarrow 0$
when the crystal melts and $\langle n_{i}(t)\rangle\to\eta$.

In Fig. 3(D), we display $G(t)$ as a function of time $t$ for the initial
condition in Fig. 3(A). For the quantum evolution, $G(t)$ saturates to a
nonzero value, while in the classical domain $G(t)$ decays. Notice that
classically $G(t\rightarrow\infty)$ can retain a small non-zero value due to
finite-size effects vanishing in the thermodynamic limit Sup .

Figure 4: Quantum many-body scars in the 2D quantum hard-disk model. Bipartite
entanglement entropy $S_{A}$ as a function of eigenstate energy density
colored by the normalized Edwards-Anderson order parameter $Q$ for a $6\times
6$ lattice. A circle denotes eigenstates from the largest Hilbert-space
fragment whereas triangles indicate eigenstates from the smaller ones. (A) In
the non-fragmented region, there is only a large ergodic component. (B) In the
weak fragmentation region, there are towers of eigenstates with low
entanglement entropy and high normalized Edwards-Anderson order parameter $Q$
signaling quantum many-body scars. (C) For high densities in the regime of
strong fragmentation all eigenstates lie in small Hilbert-space fragments.

The defect dynamics in Fig. 3 highlights the crucial role of quantum
interference effects leading to nonergodic behavior. In the following, we
provide compelling numerical evidence that this originates from the presence
of quantum many-body scars in the spectrum. For that purpose, we will study
the eigenstate properties through the bipartite entanglement entropy:

$S_{A}=-\operatorname{Tr}\bigg{[}\operatorname{Tr}_{\bar{A}}\big{(}|\Psi\rangle\langle\Psi|\big{)}\log\left[\operatorname{Tr}_{\bar{A}}\big{(}|\Psi\rangle\langle\Psi|\big{)}\right]\bigg{]}.$
(3)

Here, $|\Psi\rangle$ denotes an eigenstate, $A$ the subsystem, chosen as the
bottom half of the 2D lattice, and $\bar{A}$ is the complement of $A$.
Additionally, we aim to quantify how close a given eigenstate is to a single
many-body configuration, such as the one for the dynamics shown in Fig. 3.
This can be achieved by means of an Edwards-Anderson (EA) order parameter
$Q_{\textrm{EA}}=L^{-4}\sum_{i,j}|\langle\Psi|(2n_{i}-1)(2n_{j}-1)|\Psi\rangle|^{2}$.
In order to quantitatively compare the EA order parameter for different
particle densities $\eta$ we further introduce a normalized version:

$Q=\frac{Q_{\textrm{EA}}-\left(2\eta-1\right)^{4}}{1-\left(2\eta-1\right)^{4}}~{},$
(4)

so that $Q=1$ when $|\Psi\rangle$ is a single configuration and $Q\rightarrow
0$ when $|\Psi\rangle$ represents a superposition over all basis states.

In Fig. 4 we display $S_{A}$ for all eigenstates as a function of energy
density $E/L^{2}$ for three different densities $\eta$ and associated levels
of fragmentation. We include the normalized EA order parameter $Q$ by coloring
the data points.

In the non-fragmented domain, see Fig. 4(A), we observe a dome for $S_{A}$
consistent with ergodic behavior, further supported by the uniform small
values of $Q$. In the strong fragmentation regime, see Fig. 4(C), there is no
ergodic component but rather only small fragments yielding small values of
$S_{A}$ and high values of $Q$. Consequently, the eigenstates represent almost
individual many-body configurations.

Concerning the stability of defects in Fig. 3, the regime of most interest is
the weakly fragmented region, see Fig. 4(B). There, one can identify a set of
ergodic eigenstates. On the other hand, there is a large number of
eigenstates, which don’t follow the conventional ergodic paradigm, which we
identify as quantum many-body scars where $S_{A}$ and $Q$ significantly depart
from the ergodic expectations. Most importantly, these nonergodic eigenstates
not only emerge from the small Hilbert-space fragments but also from the large
one, where they arrange along towers at specific energy densities. As these
nonergodic eigenstates are mostly also associated with large values of $Q$, we
conclude that there is a large number of many-body configurations, which are
not thermalizing but rather retain their original structure over time. This is
exactly related to the stability of the crystal defects displayed in Fig. 3
and we conclude that our initial configuration in Fig. 3 was not fine-tuned.
When it comes to the stability of our observed quantum many-body scars, it
might happen that additional interactions yield dynamical heterogeneous
behavior as has been studied for a related quasi-1D ladder system Lan  _et
al._ (2018). Notice that recent works in strong-coupling limits of the quantum
Ising model have recognized also regimes of nonergodic behaviors for certain
types of domain wall interfaces Hart and Nandkishore (2022); Balducci  _et
al._ (2022, 2023a, 2023b).

Conclusions.—In this letter, we have studied the quantum hard-disk model on
lattices, which as we have shown displays unique quantum features in its
dynamics. The considered hard-disk model exhibits a direct realization in
Rydberg atomic systems. The Rydberg blockade mechanism naturally implements
the excluded volume, so that a Rydberg excitation (identified here with a
hard-core bosonic particle) blocks for the presence of a second excitation
within the blockade radius Browaeys and Lahaye (2020). When considering
Rydberg atoms on a lattice, it remains to adjust the lattice spacing between
the atoms such that the Rydberg blockade radius is exactly such that it blocks
the presence of particles on nearest-neighboring sites. The typical
microscopic interactions realized in Rydberg atomic systems are either of
Ising character, leading to PXP-type models Bernien  _et al._ (2017);
Bluvstein  _et al._ (2021), or $XY$ character Chen  _et al._ (2023).
Importantly, our hard-disk model exhibits particle-number conservation, which
would be either implementable directly via $XY$-type interactions or via
Ising-type models upon enforcing particle-number conservation through a strong
longitudinal magnetic field for instance.

We envision a large range of further interesting prospective research
questions for the future emerging from this work. A natural extension would be
to consider disks or excluded volumes with larger radii as well as different
shapes. Further, it might be interesting to consider how the dynamics are
modified upon relaxing the hard-disk constraint to a soft one, such as for the
soft-shoulder potentials realized naturally in Rydberg dressing Zeiher  _et
al._ (2017).

Data availability.—The data to generate all figures in this letter is
available in Zenodo Naik  _et al._ (2023).

Acknowledgements.—We thank Werner Krauth, Juan Garrahan, Alessio Lerose, and
Tobias Wiener for fruitful discussions. V.D.N. and F.B.T. contributed equally
to this work. This project has received funding from the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation
programme (grant agreement No. 853443). This work was supported by the German
Research Foundation DFG via project 499180199 (FOR 5522).

## References

  * Guardado-Sanchez  _et al._ (2020) E. Guardado-Sanchez, A. Morningstar, B. M. Spar, P. T. Brown, D. A. Huse, and W. S. Bakr, Physical Review X 10, 011042 (2020), arXiv:1909.05848 [cond-mat.quant-gas] .
  * Scherg  _et al._ (2021) S. Scherg, T. Kohlert, P. Sala, F. Pollmann, B. Hebbe Madhusudhana, I. Bloch, and M. Aidelsburger, Nature Communications 12, 4490 (2021), arXiv:2010.12965 [cond-mat.quant-gas] .
  * Kohlert  _et al._ (2023) T. Kohlert, S. Scherg, P. Sala, F. Pollmann, B. Hebbe Madhusudhana, I. Bloch, and M. Aidelsburger, Phys. Rev. Lett. 130, 010201 (2023).
  * Bernien  _et al._ (2017) H. Bernien, S. Schwartz, A. Keesling, H. Levine, A. Omran, H. Pichler, S. Choi, A. S. Zibrov, M. Endres, M. Greiner, V. Vuletić, and M. D. Lukin, Nature 551, 579 (2017).
  * Keesling  _et al._ (2019) A. Keesling, A. Omran, H. Levine, H. Bernien, H. Pichler, S. Choi, R. Samajdar, S. Schwartz, P. Silvi, S. Sachdev, P. Zoller, M. Endres, M. Greiner, Vuletić, V. , and M. D. Lukin, Nature (London) 568, 207 (2019).
  * de Léséleuc  _et al._ (2019) S. de Léséleuc, V. Lienhard, P. Scholl, D. Barredo, S. Weber, N. Lang, H. P. Büchler, T. Lahaye, and A. Browaeys, Science 365, 775 (2019), arXiv:1810.13286 [quant-ph] .
  * Browaeys and Lahaye (2020) A. Browaeys and T. Lahaye, Nature Physics 16, 132 (2020).
  * Ebadi  _et al._ (2021) S. Ebadi, T. T. Wang, H. Levine, A. Keesling, G. Semeghini, A. Omran, D. Bluvstein, R. Samajdar, H. Pichler, W. W. Ho, S. Choi, S. Sachdev, M. Greiner, V. Vuletić, and M. D. Lukin, Nature 595, 227 (2021).
  * Semeghini  _et al._ (2021) G. Semeghini, H. Levine, A. Keesling, S. Ebadi, T. T. Wang, D. Bluvstein, R. Verresen, H. Pichler, M. Kalinowski, R. Samajdar, A. Omran, S. Sachdev, A. Vishwanath, M. Greiner, V. Vuletić, and M. D. Lukin, Science 374, 1242 (2021).
  * Scholl  _et al._ (2021) P. Scholl, M. Schuler, H. J. Williams, A. A. Eberharter, D. Barredo, K.-N. Schymik, V. Lienhard, L.-P. Henry, T. C. Lang, T. Lahaye, A. M. Läuchli, and A. Browaeys, Nature 595, 233 (2021).
  * Bluvstein  _et al._ (2021) D. Bluvstein, A. Omran, H. Levine, A. Keesling, G. Semeghini, S. Ebadi, T. T. Wang, A. A. Michailidis, N. Maskara, W. W. Ho, S. Choi, M. Serbyn, M. Greiner, V. Vuletić, and M. D. Lukin, Science 371, 1355 (2021).
  * Turner  _et al._ (2018) C. J. Turner, A. A. Michailidis, D. A. Abanin, M. Serbyn, Papić, and Z. , Nature Physics 14, 745 (2018).
  * Serbyn  _et al._ (2021) M. Serbyn, D. A. Abanin, and Z. Papić, Nature Physics 17, 675 (2021).
  * Li  _et al._ (2022) B. Li, Y. Nishikawa, P. Höllmer, L. Carillo, A. C. Maggs, and W. Krauth, J. Chem. Phys. 157, 234111 (2022), arXiv:2207.07715 [cond-mat.stat-mech] .
  * Huang and Yang (1957) K. Huang and C. N. Yang, Phys. Rev. 105, 767 (1957).
  * Luban (1965) M. Luban, Phys. Rev. 138, A1033 (1965).
  * Lieb (1967) E. H. Lieb, Journal of Mathematical Physics 8, 43 (1967).
  * Winer  _et al._ (2023) M. Winer, C. L. Baldwin, R. Barney, V. Galitski, and B. Swingle, “The glass transition of quantum hard spheres in high dimensions,” (2023), arXiv:2311.04968 [cond-mat.stat-mech] .
  * Kwan  _et al._ (2023) Y. H. Kwan, P. H. Wilhelm, S. Biswas, and S. A. Parameswaran, “Minimal hubbard models of maximal hilbert space fragmentation,” (2023), arXiv:2304.02669 [cond-mat.stat-mech] .
  * Pai  _et al._ (2019) S. Pai, M. Pretko, and R. M. Nandkishore, Physical Review X 9, 021003 (2019), arXiv:1807.09776 [cond-mat.stat-mech] .
  * Sala  _et al._ (2020) P. Sala, T. Rakovszky, R. Verresen, M. Knap, and F. Pollmann, Physical Review X 10, 011047 (2020), arXiv:1904.04266 [cond-mat.str-el] .
  * Rakovszky  _et al._ (2020) T. Rakovszky, P. Sala, R. Verresen, M. Knap, and F. Pollmann, Phys. Rev. B 101, 125126 (2020), arXiv:1910.06341 [cond-mat.str-el] .
  * Khemani  _et al._ (2020) V. Khemani, M. Hermele, and R. Nandkishore, Phys. Rev. B 101, 174204 (2020), arXiv:1910.01137 [cond-mat.stat-mech] .
  * Moudgalya and Motrunich (2022) S. Moudgalya and O. I. Motrunich, Phys. Rev. X 12, 011050 (2022).
  * Smith  _et al._ (2017a) A. Smith, J. Knolle, D. L. Kovrizhin, and R. Moessner, Phys. Rev. Lett. 118, 266601 (2017a), arXiv:1701.04748 [cond-mat.str-el] .
  * Smith  _et al._ (2017b) A. Smith, J. Knolle, R. Moessner, and D. L. Kovrizhin, Phys. Rev. Lett. 119, 176601 (2017b), arXiv:1705.09143 [cond-mat.str-el] .
  * Brenes  _et al._ (2018) M. Brenes, M. Dalmonte, M. Heyl, and A. Scardicchio, Phys. Rev. Lett. 120, 030601 (2018), arXiv:1706.05878 [cond-mat.str-el] .
  * Russomanno  _et al._ (2020) A. Russomanno, S. Notarnicola, F. M. Surace, R. Fazio, M. Dalmonte, and M. Heyl, Physical Review Research 2, 012003 (2020), arXiv:1906.03185 [cond-mat.quant-gas] .
  * Karpov  _et al._ (2021) P. Karpov, R. Verdel, Y. P. Huang, M. Schmitt, and M. Heyl, Phys. Rev. Lett. 126, 130401 (2021), arXiv:2003.04901 [cond-mat.str-el] .
  * Chakraborty  _et al._ (2022a) N. Chakraborty, M. Heyl, P. Karpov, and R. Moessner, Phys. Rev. B 106, L060308 (2022a), arXiv:2203.06198 [cond-mat.dis-nn] .
  * Chakraborty  _et al._ (2022b) N. Chakraborty, M. Heyl, P. Karpov, and R. Moessner, arXiv e-prints , arXiv:2211.14328 (2022b), arXiv:2211.14328 [cond-mat.dis-nn] .
  * Michailidis  _et al._ (2020) A. A. Michailidis, C. J. Turner, Z. Papić, D. A. Abanin, and M. Serbyn, Physical Review Research 2, 022065 (2020).
  * Fernandes  _et al._ (2007) H. C. M. Fernandes, J. J. Arenzon, and Y. Levin, The Journal of Chemical Physics 126, 114508 (2007).
  * Alcaraz and Bariev (1999) F. C. Alcaraz and R. Z. Bariev, arXiv e-prints , cond-mat/9904042 (1999), arXiv:cond-mat/9904042 [cond-mat.stat-mech] .
  * Pozsgay  _et al._ (2021) B. Pozsgay, T. Gombor, A. Hutsalyuk, Y. Jiang, L. Pristyák, and E. Vernier, Phys. Rev. E 104, 044106 (2021).
  * Grabsch  _et al._ (2023) A. Grabsch, P. Rizkallah, A. Poncet, P. Illien, and O. Bénichou, Physical Review E 107 (2023), 10.1103/physreve.107.044131.
  * (37) See Supplemental Material for details.
  * Lan  _et al._ (2018) Z. Lan, M. van Horssen, S. Powell, and J. P. Garrahan, Phys. Rev. Lett. 121, 040603 (2018).
  * Hart and Nandkishore (2022) O. Hart and R. Nandkishore, Phys. Rev. B 106, 214426 (2022), arXiv:2203.06188 [cond-mat.stat-mech] .
  * Balducci  _et al._ (2022) F. Balducci, A. Gambassi, A. Lerose, A. Scardicchio, and C. Vanoni, Phys. Rev. Lett. 129, 120601 (2022), arXiv:2203.09495 [cond-mat.stat-mech] .
  * Balducci  _et al._ (2023a) F. Balducci, A. Scardicchio, and C. Vanoni, Phys. Rev. B 107, 024201 (2023a), arXiv:2207.11246 [cond-mat.dis-nn] .
  * Balducci  _et al._ (2023b) F. Balducci, A. Gambassi, A. Lerose, A. Scardicchio, and C. Vanoni, Phys. Rev. B 107, 024306 (2023b), arXiv:2209.08992 [cond-mat.stat-mech] .
  * Chen  _et al._ (2023) C. Chen, G. Emperauger, G. Bornet, F. Caleca, B. Gély, M. Bintz, S. Chatterjee, V. Liu, D. Barredo, N. Y. Yao, T. Lahaye, F. Mezzacapo, T. Roscilde, and A. Browaeys, arXiv e-prints , arXiv:2311.11726 (2023), arXiv:2311.11726 [cond-mat.quant-gas] .
  * Zeiher  _et al._ (2017) J. Zeiher, J.-y. Choi, A. Rubio-Abadal, T. Pohl, R. van Bijnen, I. Bloch, and C. Gross, Physical Review X 7, 041063 (2017), arXiv:1705.08372 [physics.atom-ph] .
  * Naik  _et al._ (2023) V. D. Naik, F. Ballar Trigueros, and M. Heyl, “Quantum hard disks on a lattice,”  (2023).