# Betti Numbers of Gaussian Excursions in the Sparse Regime

Gugan Thoppe<EMAIL_ADDRESS>[ Sunder Ram Krishnan
<EMAIL_ADDRESS>[ Duke Universitym1 and Technion–Israel
Institute of Technologym2  Gugan Thoppe
Dept. of Statistical Science
Duke University
Durham, NC 27708
USA
Sunder Ram Krishnan
Faculty of Electrical Engineering
Technion - Israel Institute of Technology
Haifa 32000
Israel

###### Abstract

Random field excursions is an increasingly vital topic within data analysis in
medicine, cosmology, materials science, etc. This work is the first detailed
study of their Betti numbers in the so-called ‘sparse’ regime. Specifically,
we consider a piecewise constant Gaussian field whose covariance function is
positive and satisfies some local, boundedness, and decay rate conditions. We
model its excursion set via a Čech complex. For Betti numbers of this complex,
we then prove various limit theorems as the window size and the excursion
level together grow to infinity. Our results include asymptotic mean and
variance estimates, a vanishing to non-vanishing phase transition with a
precise estimate of the transition threshold, and a weak law in the non-
vanishing regime. We further obtain a Poisson approximation and a central
limit theorem close to the transition threshold. Our proofs combine extreme
value theory and combinatorial topology tools.

60G15,

60F05,

05E45,

60G60,

60G70,

60G10,

55U10,

Gaussian,

field,

topology,

Betti numbers,

excursion,

Cech,

Vietoris-Rips,

complex,

###### keywords:

[class=MSC]

###### keywords:

journalname Constsymbol=C Asmsymbol=A arXiv:1807.11018

and

t1Both GT and SRK were previously supported by URSAT, European Research
Council’s Advanced Grant 320422. GT is now supported by grants NSF
IIS-1546331, NSF DMS-1418261, and NSF DMS-1613261, while SRK is supported by
the Viterbi Postdoctoral Fellowship. A portion of this work was done when GT
was a postdoc at Technion.

##  1 Introduction

Key insights into the behaviour of a random field can be inferred from its
excursion set, the sub-domain where the field value exceeds some level. Hence,
functionals of excursion sets have generated considerable interest both in
theory [5, 8] and in practice [6, 29, 40]. In this paper, we provide limit
theorems, together with rates of convergence, for Betti numbers
$\\{\beta_{k}\\}$ of Gaussian excursions in the so-called ‘sparse’ regime.
This work is the first study of the sparse regime behaviour of Betti number of
random field excursions of any kind. Intuitively, for a topological space,
$\beta_{0}$ is the number of components while $\beta_{k},$ for $k\geq 1,$ is
the number of $(k+1)-$dimensional ‘holes’. A $(k+1)-$dimensional hole is
loosely the hollow region that opens up when the interior of a solid
$(k+1)-$dimensional object is removed. Specifically, in three dimensions,
$\beta_{1}$ is the number of ‘tunnels’ (regions through which one can poke
one’s hand), $\beta_{2}$ is the number of ‘voids’ (regions that look like the
interior of a tennis ball, doughnut, etc.), while other higher order Betti
numbers are all zero. Thus, our results statistically quantify the topology of
high-level Gaussian excursions.

The majority of recent work on Gaussian excursions concerns what is known as
the ‘thermodynamic’ regime. Even within these, the major focus of most papers
([14, 27, 31], etc.) has been on a different set of functionals called the
Lipschitz-Killing curvatures (LKCs), which include as special cases the Euler-
Poincaré characteristic (EPC) and the $d-$dimensional volume. LKCs do provide
useful topological information, but not at the level of individual Betti
numbers. In relation to Betti numbers, the only paper of which we are aware is
[35]. There, a weak law and a (multivariate) CLT have been shown for a generic
class of (quasi-) local statistics of spin models on Cayley graphs. By using a
suitable random cubical complex to model Gaussian excursions on
$\mathbb{Z}^{d},$ one can apply these results to Betti numbers in the
thermodynamic regime. As can be seen in Section 2.2.3 there, it is required
that the underlying spin model be subcritical and the covariance function
decay exponentially. We point out that, unlike this fast decay assumption, the
results in [14, 27, 31] and related papers require only that the covariance
function be integrable (see also Remark $\boldsymbol{\mathcal{R}_{5}}$).

In [3, 4], existence probabilities of connecting paths and holes in high level
excursions of Gaussian fields on the continuum have been studied. However, as
noted in those papers, it is difficult to handle such questions in the
continuum and those works obtained estimates for these probabilities only at
the level of large deviations. Separately, in [32, 36], existence results on
topology of level sets of stationary Gaussian fields have been provided. It is
not clear whether any of those results can easily be translated to excursion
sets.

In contrast, and as highlighted previously, we study Gaussian excursions in
the sparse regime (see Remark $\boldsymbol{\mathcal{R}_{6}}$ for a formal
description of sparse/thermodynamic regime). Our results are explicit and we
obtain them under significantly weaker assumptions; in fact, in some cases,
these assumptions are tight. We achieve these by focussing on Gaussian fields
on discrete parameter spaces and using a novel approach of modelling their
excursion sets via simplicial complexes (generalization of graphs). The latter
enables use of suitable combinatorial approximators to study the Betti numbers
of these excursions, a trick motivated by studies in the random simplicial
complex literature [28, 30, 21, 22, 24]. We then obtain precise distributional
limit theorems for these approximators by employing the Stein-Chen approach
[18], together with Slepian’s lemma and Savage’s multivariate Gaussian tail
estimates [37]. We finally transfer these results to Betti numbers, building
upon the topological ideas from [22, 24]. A detailed description of all these
notions is given in Section 2.

Figure 1:  Possible realization of our Gaussian field $X$ on $\mathbb{Z}^{2}$
and its piecewise constant extension to $\mathbb{R}^{2}$ (colors are used only
to provide a clearer illustration).

Figure 2:  Possible realizations of the excursion set $\mathcal{A}(n;u)$ in
two and three dimensions with non-trivial first Betti numbers(created using
voxelbuilder).

Formally, we consider a piecewise constant random field
$X:\mathbb{R}^{d}\to\mathbb{R}$ with the below properties.

  1. 1.

$\\{X_{\bar{t}}\\}_{\bar{t}\in\mathbb{Z}^{d}}$ is a zero mean, stationary,
$\|\cdot\|_{1}-$isotropic, discrete parameter Gaussian field with the
covariance sequence $\\{\rho_{q}\\}_{q\geq 0}.$ That is,

    1. (a)

$\mathbb{E}[X_{\bar{t}}]=0,$ for all $\bar{t}\in\mathbb{Z}^{d},$ and

    2. (b)

$\textnormal{Cov}[X_{\bar{t}},X_{\bar{t}^{\prime}}]=\rho_{{}_{\|\bar{t}-\bar{t}^{\prime}\|_{1}}},$
for all $\bar{t},\bar{t}^{\prime}\in\mathbb{Z}^{d}.$

  2. 2.

For $\bar{t}\in\mathbb{R}^{d}\backslash\mathbb{Z}^{d},$ $X_{\bar{t}}$ equals
the value of the above discrete field at the lattice point closest to
$\bar{t}$ in the $\|\cdot\|_{\infty}$ norm (if there is more than one closest
point, we pick the one that is the largest in lexicographical ordering).

Its excursion set of interest to us is

$\mathcal{A}(n;u):=\\{\bar{t}\in[-n-1/2,n+1/2)^{d}:X_{\bar{t}}\geq u\\}$ (1.1)

where $n\geq 0$ is the window size parameter and $u\in\mathbb{R}_{>0}$ is the
excursion level; here, $\mathbb{R}_{>0}$ is the set of positive real numbers.
See Figures 1 and 2 for an illustration.

To study the topology of $\mathcal{A}(n;u),$ as mentioned above, we model it
using a simplicial complex defined as follows. Let
$\Gamma_{n}:=\\{\bar{t}\in\mathbb{Z}^{d}:\|\bar{t}\|_{\infty}\leq n\\}$ be the
discrete window of side length $(2n+1)$ and let
$\mathscr{B}_{\infty}(\bar{t},r):=\\{\bar{t}^{\prime}\in\mathbb{R}^{d}:\|\bar{t}-\bar{t}^{\prime}\|_{\infty}\leq
r\\}.$

######  Definition 1.1.

The random Čech complex $\mathcal{K}(n;u)$ on the excursion set
$\mathcal{A}(n;u)$ is the simplicial complex with vertex set
$\mathcal{F}_{0}:=\\{\bar{t}\in\Gamma_{n}:X_{\bar{t}}\geq u\\},$ and
$\sigma\subset\mathcal{F}_{0}$ is a face of $\mathcal{K}(n;u)$ if

$\bigcap_{\bar{t}\in\sigma}\mathscr{B}_{\infty}\left(\bar{t},\tfrac{1}{2}\right)\neq\emptyset.$

Observe that the vertex set of $\mathcal{K}(n;u)$ is random, while its faces
are decided using a deterministic rule based on the
$\|\cdot\|_{\infty}-$distance between the vertex pairs. This places it in the
family of random geometric complexes. It is called a Čech complex since each
of its face is chosen based on the mutual intersection of suitable balls
centered at the vertices in that face.

An alternative way to model $\mathcal{A}(n;u)$ could have been the complex
$\hat{\mathcal{K}}(n;u)$ defined as follows.

######  Definition 1.2.

The random Vietoris-Rips complex $\hat{\mathcal{K}}(n;u)$ on the excursion set
$\mathcal{A}(n;u)$ is the simplicial complex with vertex set
$\mathcal{F}_{0}:=\\{\bar{t}:\bar{t}\in\Gamma_{n},X_{\bar{t}}\geq u\\},$ and
$\sigma\subset\mathcal{F}_{0}$ is a face of $\hat{\mathcal{K}}(n;u)$ if

$\mathscr{B}_{\infty}\left(\bar{t}_{i},\tfrac{1}{2}\right)\cap\mathscr{B}_{\infty}\left(\bar{t}_{j},\tfrac{1}{2}\right)\neq\emptyset$

for every pair $\bar{t}_{i},\bar{t}_{j}\in\sigma.$

This is also a geometric complex. It is called the Vietoris-Rips complex
because its faces are decided based on pairwise intersections. Usually, a Čech
and Vietoris-Rips complex are different as the rules for defining them differ.
However, in our setup, using the fact that they are defined on a lattice, it
turns out that $\mathcal{K}(n;u)=\hat{\mathcal{K}}(n;u);$ see Proposition 3.1
for details. Thus, according to need, we shall view $\mathcal{K}(n;u)$
sometimes as a Čech and at other times as a Vietoris-Rips complex. Taking one
of the views, let $\beta_{n,k}(u)$ be the $k-$th Betti number of
$\mathcal{K}(n;u);$ Figures 2 and 3 show a few representative examples. With
details given in Section 2, we point out that the coefficients to define these
Betti numbers can be from either a field or $\mathbb{Z}.$

Figure 3:  Possible subcomplexes of $\mathcal{K}(n;u).$ The left image shows how a part of our excursion set may appear (grey color) when $d=2$ and the simplicial complex associated with it; because of the top left formation, the first Betti number of this subcomplex is $1.$ The right image shows a subcomplex, the second Betti number of which equals $1;$ this may appear only when $d\geq 3.$ (Source: Wikipedia). Id | Assumption | Applicable when | Type
---|---|---|---
$\Cl[Asm]{a:r0Asm}$ | $\rho_{0}=1$ |  | Local
$\Cl[Asm]{a:r1Asm}$ | $0\leq\rho_{1}<\rho_{0}$ |  | Local
$\Cl[Asm]{a:rCAsm}$ | $\begin{cases}0\leq\sup\limits_{q\geq 2}\rho_{q}\leq\rho_{1}\\\\[8.61108pt] 0\leq\sup\limits_{q\geq 4}\rho_{q}\leq\rho_{3}<\rho_{2}<\rho_{1}\end{cases}$ |  $k=0$ $1\leq k<d$ | Boundedness
$\Cl[Asm]{a:ComC}(k)$ | $\begin{cases}1=1\\\\[8.61108pt] 1+(2k+1)\rho_{2}>2(k+1)\rho_{1}\end{cases}$ |  $k=0$ $1\leq k<d$ | Local
$\Cl[Asm]{a:PoiG}$ | $\lim_{q\to\infty}\rho_{q}\log q=0$ |  | Decay Rate
$\Cl[Asm]{a:CLTG}$ | $\sum_{q=0}^{\infty}q^{d-1}\rho_{q}<\infty$ |  | Decay Rate

Table 1:  Assumptions for different results.

Our key results can now be summarized as follows. The different assumptions
are listed in Table 1; these are in addition to the conditions on
$\\{\rho_{q}\\}$ imposed by the fact that the covariance function of $X$ must
be positive definite. For $k$ such that $1\leq k<d,$ define the constants
$\tau_{k},$ $a_{k},$ and $b_{k}$ using

$\tau_{k}:=\frac{\tbinom{d}{k+1}}{(2\pi)^{k+1}}\frac{[1+(2k+1)\rho_{2}]^{2k+\tfrac{1}{2}}}{[1-\rho_{2}]^{k+\tfrac{1}{2}}},\;\;a_{k}:=\frac{k+1}{1+(2k+1)\rho_{2}},\text{
and }b_{k}:=k+1.$ (1.2)

Separately, let

$\tau_{0}:=\frac{1}{\sqrt{2\pi}},\;\;a_{0}:=\tfrac{1}{2},\text{ and
}b_{0}:=\tfrac{1}{2}.$ (1.3)

For $n\geq 0,$ $k$ such that $0\leq k<d,$ and $u\in\mathbb{R}_{>0},$ define
$\lambda_{n,k}(u)$ using

$\lambda_{n,k}(u):=\tau_{k}\;(2n+1)^{d}u^{-2b_{k}}\exp[-a_{k}u^{2}].$ (1.4)

Finally, let $\mathbb{R}_{>0}^{\infty}$ be the set of sequences in
$\mathbb{R}_{>0}.$

Our first result gives a precise asymptotic formula for
$\mathbb{E}[\beta_{n,k}(u)].$ Here, and elsewhere, $O(\cdot)$ denotes the
Big-O notation and it characterizes a function’s behaviour as $n\to\infty.$

######  Theorem 1.3 (Asymptotic Mean of $\beta_{n,k}(u_{n})$).

Let $k$ be such that $0\leq k<d$ and $\\{u_{n}\\}\in\mathbb{R}_{>0}^{\infty}$
be such that $\lim_{n\to\infty}u_{n}=\infty.$ Suppose
$\Cr{a:r0Asm},\Cr{a:r1Asm},\Cr{a:rCAsm},$ and $\Cr{a:ComC}(k)$ hold. Then,

$\left|\frac{\mathbb{E}[\beta_{n,k}(u_{n})]}{\lambda_{n,k}(u_{n})}-1\right|=O\left(\frac{1}{u_{n}^{2}}+\frac{1}{n}\right).$

The constants involved in the $O$ notation depend on $k.$

From (1.4), note that the limit of the sequence $\\{\lambda_{n,k}(u_{n})\\}$
can be either zero, a constant, or infinity, depending on the growth rate of
$\\{u_{n}\\}.$ An alternative way to view this is to let

$u_{n}=\sqrt{\frac{1}{a_{k}}\left[\log[\tau_{k}(2n+1)^{d}]-b_{k}\log\left[\frac{\log[\tau_{k}(2n+1)^{d}]}{a_{k}}\right]+\nu_{n}\right]},$
(1.5)

where $\\{\nu_{n}\\}$ is any real sequence that ensures
$\\{u_{n}\\}\in\mathbb{R}_{>0}^{\infty}$ and $\lim_{n\to\infty}u_{n}=\infty.$
Then, $\\{\lambda_{n,k}(u_{n})\\}$ has the above three limits precisely when
$\lim_{n\to\infty}\nu_{n}$ is either $\infty,$ some constant, or $-\infty.$
Our next result gives the asymptotic behaviour of the $k-$th Betti number in
these three scenarios.

######  Theorem 1.4 (Asymptotic Distributional Behaviour of
$\beta_{n,k}(u_{n})$).

Let $k$ be such that $0\leq k<d$ and $\\{u_{n}\\}\in\mathbb{R}_{>0}^{\infty}$
be such that $\lim_{n\to\infty}u_{n}=\infty.$ In the different regimes
dictated by the limit of $\\{\nu_{n}\\},$ or equivalently of
$\\{\lambda_{n,k}(u_{n})\\},$ the $k-$th Betti number behaves as follows.

  1. 1.

Vanishing regime $(\nu_{n}\to\infty$ or $\lambda_{n,k}(u_{n})\to 0$): If
$\Cr{a:r0Asm},\Cr{a:r1Asm},\Cr{a:rCAsm},$ and $\Cr{a:ComC}(k)$ hold, then

$1-\mathbb{P}\\{\beta_{n,k}(u_{n})=0\\}=O\left(e^{-\nu_{n}}\left[\frac{\log
n}{\log n+\nu_{n}}\right]^{b_{k}}\right).$

  2. 2.

Poisson regime $(\nu_{n}\to\log[\tfrac{1}{\lambda}]$ or
$\lambda_{n,k}(u_{n})\to\lambda,$ for some $\lambda\in\mathbb{R}_{>0}$): If
$\Cr{a:r0Asm},\Cr{a:r1Asm},\Cr{a:rCAsm},\Cr{a:ComC}(k),$ and $\Cr{a:PoiG}$
hold, then $\beta_{n,k}(u_{n})\Rightarrow\textnormal{Poi}(\lambda);$ in
particular, we have

$\|\beta_{n,k}(u_{n})-\textnormal{Poi}(\lambda)\|_{\textnormal{TV}}=O\left(\frac{\log
n}{n}\sum_{q=1}^{2dn}\rho_{q}+\frac{\log\log n}{\log
n}+|e^{-\nu_{n}}-\lambda|\right).$

  3. 3.

Non-vanishing regime ($\nu_{n}\to-\infty$ or $\lambda_{n,k}(u_{n})\to\infty$):
If $\Cr{a:r0Asm},\Cr{a:r1Asm},\Cr{a:rCAsm},\Cr{a:ComC}(k),$ and $\Cr{a:CLTG}$
hold, then

$\lim_{n\to\infty}\frac{\textnormal{Var}[\beta_{n,k}(u_{n})]}{\lambda_{n,k}^{2}(u_{n})}=0,$
(1.6) $\lim\limits_{n\to\infty}\mathbb{P}\\{\beta_{n,k}(u_{n})=0\\}=0,$ (1.7)

and

$\frac{\beta_{n,k}(u_{n})-\mathbb{E}[\beta_{n,k}(u_{n})]}{\lambda_{n,k}(u_{n})}\overset{i.p.}{\longrightarrow}0.$
(1.8)

Additionally, there exists a constant $C^{\nu}_{k}>0,$ depending on $k,$ such
that, if $C\in(0,C^{\nu}_{k})$ and $\nu_{n}\geq-C\log(2n+1)^{d},$ then

$\dfrac{\beta_{n,k}(u_{n})-\mathbb{E}[\beta_{n,k}(u_{n})]}{\sqrt{\lambda_{n,k}(u_{n})}}\Rightarrow
N(0,1),$ (1.9)

where $N$ denotes the Gaussian distribution. The explicit formula for
$C^{\nu}_{k}$ is given in (3.20).

This result proves that the $k-$th Betti number undergoes a vanishing to non-
vanishing phase transition as its asymptotic mean changes from zero to
infinity. It also shows a weak law in the non-vanishing regime. In addition,
close to the transition threshold, the result gives a Poisson approximation
and a CLT. Loose rates of convergence for (1.6) and (1.9) are given in their
proofs.

We now provide some remarks on our assumptions, model setup, and results.

  1. $\boldsymbol{\mathcal{R}_{1}}$.

We assume $\|\cdot\|_{1}-$isotropy in our model mainly in order to simplify
our estimates and computations. With other forms of isotropy, we strongly
believe that results with a similar flavor to ours should hold, but will
require some more involved calculations; see Section 7.

  2. $\boldsymbol{\mathcal{R}_{2}}$.

For all our results, we need the covariance function to be positive. This is
because it is unclear at present how to apply our Stein-Chen approach when
negative covariances are involved; in particular, we are then unable to
establish a result such as Theorem 2.11. For the specific case of $\beta_{0},$
however, this assumption can be relaxed; see [18] for the outline.

  3. $\boldsymbol{\mathcal{R}_{3}}$.

We also need that $\Cr{a:ComC}(k)$ holds. For Gaussian fields on the continuum
with covariance functions given by
$\exp[-\|\bar{t}-\bar{t}^{\prime}\|_{2}^{q}],$
$\|\bar{t}-\bar{t}^{\prime}\|_{2}^{-q},$ etc. with $q>0,$ this condition
places a lower bound on the distance at which these fields need to be sampled
so that our results hold. However, note that this condition is natural in ARMA
models. It may be possible to eliminate this assumption, but the computations
would then become involved. See Section 7 for details.

  4. $\boldsymbol{\mathcal{R}_{4}}$.

For the vanishing and Poisson regime results, we require the covariance
function to also satisfy $\Cr{a:PoiG},$ the so-called ‘Berman’ condition. This
condition is known to be tight for Poisson approximation; see [18, Remark 1]
for example. It is worth noting that this condition holds even for Gaussian
fields that are long-range dependent and also for Gaussian free fields on
$\mathbb{Z}^{d}$ with $d\geq 3$ [12].

  5. $\boldsymbol{\mathcal{R}_{5}}$.

The non-vanishing regime results including the CLT need the stronger
$\Cr{a:CLTG}$ condition, which basically means that covariances should be
summable in the domain dimension $d.$ This is a common assumption in the
Gaussian excursions literature [14, 26, 27, 9]. However, it is unclear whether
it is tight.

  6. $\boldsymbol{\mathcal{R}_{6}}$.

In all the three regimes determined by the limit of $\nu_{n},$ the average
vertex degree (i.e., $\mathbb{E}[\mbox{number of
edges}]/\mathbb{E}[\mbox{number of vertices}]$) of our Čech complex
asymptotically vanishes. In random graphs terminology, this places all our key
results in the ‘sparse’ regime. The asymptotics in [14, 27, 31, 35], from the
perspective of our setup, loosely translates to keeping $u$ fixed and letting
only $n$ increase to infinity. It is easy to see that the average vertex
degree would asymptotically then be a constant. This positions the results of
these studies concerning LKCs and Betti numbers in what is usually referred to
as the thermodynamic regime.

  7. $\boldsymbol{\mathcal{R}_{7}}$.

From Theorem 1.4 and (1.5), in terms of $u_{n}^{2},$

$\frac{1}{a_{k}}\left[\log[\tau_{k}(2n+1)^{d}]-b_{k}\log\left[\tfrac{\log[\tau_{k}(2n+1)^{d}]}{a_{k}}\right]\right]$
(1.10)

is the transition threshold for non-triviality of the $k-$th Betti number. The
lower order $\log\log$ term in the above expression is due to the sharp
multivariate Gaussian tail estimates given in [37]. By using only the large
deviation approach, such precision cannot be obtained.

  8. $\boldsymbol{\mathcal{R}_{8}}$.

In [41] and [17], studies of random cubical complexes have been carried out.
In [17], a strong law and a CLT for Betti numbers have been derived; while the
strong law holds for generic distributions, the CLT needs independence. It may
be possible to translate these results to Gaussian excursions, but then they
would again apply in the thermodynamic regime. As opposed to cubical
complexes, we model $\mathcal{A}(n;u)$ here using simplicial complexes, since
a richer set of results are available for the latter class.

  9. $\boldsymbol{\mathcal{R}_{9}}$.

From the point of view of the random simplicial complexes literature, our work
extends recent advances. We introduce a new random simplicial complex model.
While being in the family of geometric complexes, it facilitates the study of
random field excursions. However, the in-built dependence amongst the faces in
our model contrasts it with most existing random complexes such as Linial-
Meshulam complexes [28, 30], clique complexes [21, 23], and random geometric
complexes [11]. In all the latter models, independence plays a crucial role in
both their definitions and their study.

  10. $\boldsymbol{\mathcal{R}_{10}}$.

Despite the dependence, however, our results share several similarities with
the sparse regime phenomena in random geometric complexes studied in [22, 24];
the presence of faces in their model is decided based on the Euclidean
proximity of the vertices that are generated as an IID sequence, while the
asymptotics is in terms of the coupling between the number of vertices and the
proximity thresholds. As in these works, the behaviour of our Betti numbers is
dictated by the simplest, minimal subcomplexes that generate them.
Furthermore, for each Betti number, we sequentially observe a vanishing,
Poisson, and non-vanishing behaviour. We also see that the lower order Betti
numbers appear earlier than the higher order ones as the growth rate of the
excursion levels is lowered. Mathematically, we mean that, as $k$ increases
from $0$ to $d-1,$ the phase transition threshold decreases; this follows from
Remark $\boldsymbol{\mathcal{R}_{7}}$ and the fact that $a_{k}$ monotonically
increases with $k.$ In fact, a consequence of Theorem 1.3 is that

$\lim_{n\to\infty}\frac{\mathbb{E}[\beta_{n,k_{1}}(u_{n})]}{\mathbb{E}[\beta_{n,k_{2}}(u_{n})]}\to\infty,$

whenever $k_{1}<k_{2}$ and $\\{u_{n}\\}$ is such that
$\lim_{n\to\infty}u_{n}=\infty.$

  11. $\boldsymbol{\mathcal{R}_{11}}$.

If we assume independence in our model ($\rho_{q}=0\;\forall q\geq 1$), our
calculations simplify significantly. However, the basic nature of our results
will remain the same, except that the associated constants, and hence regimes,
will be different. For a more detailed discussion, see Section 7.

  12. $\boldsymbol{\mathcal{R}_{12}}$.

As compared to the estimate for variance of Betti numbers in Theorem 1.4, we
conjecture that

$\lim_{n\to\infty}\frac{\textnormal{Var}[\beta_{n,k}(u_{n})]}{\lambda_{n,k}(u_{n})}=1.$

The evidence for this follows from Lemma 3.9.1 and Remark 5.9.

  13. $\boldsymbol{\mathcal{R}_{13}}$.

In our CLT result, the additional requirement that
$\nu_{n}\geq-C\log(2n+1)^{d}$ restricts the validity of the theorem to a
regime close to the phase transition threshold. Outside this regime, the CLT
for Betti numbers does not follow from that of the approximators that we use
throughout this work. To obtain better approximators necessitates, as of now,
an equivalent of Theorem 2.11 when negative covariances are also involved.
But, presently, it is unclear how to obtain such a result. Some more details
about this are given in Section 7.

We end this section by describing how the rest of the paper is structured.

_Structure of the Paper_ : The following section provides all the requisite
background material concerning the topological and probabilistic aspects of
this work. In Section 3, we outline our proofs for the key results.
Specifically, we first state all our major intermediate results and then,
assuming them to true, prove our key results. The topological portions of
these intermediate results are proved in Section 4, while the remaining ones
are proved in Sections 5, 6, and the Appendix. We end with a discussion on
future directions in Section 7.

##  2 Background

This section begins with a brief overview of relevant notions from simplicial
homology with a focus on Betti numbers; this is based on [21] and the
references therein. After that, we give the description of a non-trivial cycle
and, in the context of a special simplicial complex called the clique complex,
recall some useful results concerning it from [21, 22]. These results are
crucially used in Section 4 later to obtain the approximators for our Betti
numbers, mentioned before. Following all of that, we discuss few pertinent
results from probability theory. First, we give Savage’s multivariate Gaussian
tail estimates from [37]. Here, we also provide the Savage condition under
which this bound holds. We then describe Slepian’s lemma which relates tail
probabilities to covariance relations. We finally state a special case of the
Stein-Chen method, which is the same one that was used in [18]. This method
gives a bound on the total variation distance between a sum of indicator
random variables and a Poisson random variable having the same mean.

###  2.1 Topological Background

A key object of study across this work is a simplicial complex—a
generalization of a graph to higher dimensions. Specifically, an (abstract)
simplicial complex $\mathcal{K}$ on a vertex set $V$ is a collection of non-
empty subsets of $V$ such that for any $\sigma\in\mathcal{K},$ if
$\sigma^{\prime}\neq\emptyset$ and $\sigma^{\prime}\subset\sigma,$ then
$\sigma^{\prime}\in\mathcal{K}$ as well. That is, $\mathcal{K}$ is closed
under the subset operation. The elements of $\mathcal{K}$ are called faces and
the dimension of a face $\sigma$ is $|\sigma|-1,$ where $|\cdot|$ denotes
cardinality. The dimension of $\mathcal{K}$ itself is the maximum over the
dimension of all its faces. The $k-$skeleton of $\mathcal{K}$ is the
simplicial complex made up of all the faces of $\mathcal{K}$ with dimension
$k$ or less.

Given a simplicial complex $\mathcal{K},$ one way to study its topology (or
shape) is via its Betti numbers $\\{\beta_{k}(\mathcal{K})\\}_{k\geq 0}.$
These are described next, first intuitively and then formally.

Intuitive Description of Betti Numbers: Imagine the $k-$dimensional faces of
$\mathcal{K},$ or $k-$faces in short, to be solid $k-$dimensional objects.
Then, a $k-$cycle in $\mathcal{K}$ is a collection of its $k-$faces whose
union is ‘topologically equivalent to’ the boundary of a solid
$(k+1)-$dimensional object. If it is not the boundary of any subset of
$(k+1)-$faces in $\mathcal{K},$ then that $k-$cycle, in fact, represents a
$(k+1)-$dimensional hole. Finally, $\beta_{0}(\mathcal{K})$ is one more than
the number of ‘independent’ $1-$holes in $\mathcal{K},$ while, for $k\geq 1,$
$\beta_{k}(\mathcal{K})$ is exactly the number of ‘independent’
$(k+1)-$dimensional holes. In this sense, the simplicial complex in the left
image of Figure 3 has two $1-$cycles, but only the top left cycle represents a
$2-$hole. This description extends the intuitive picture given at the outset.

Formal Description of Betti Numbers: Let $\sigma$ be a $k-$face made up of the
vertices $v_{0},\ldots,v_{k}.$ An _orientation_ of $\sigma$ is an ordering of
its vertices and is denoted by $(v_{0},\ldots,v_{k}).$ Two orderings induce
the same orientation if and only if they differ by an even permutation of the
vertices. We shall assume henceforth that each face in $\mathcal{K}$ is
assigned a specific orientation, i.e., ordering. Let $\mathbb{F}$ be
$\mathbb{Z}$ or some field. Then, a simplicial $k$-chain is a formal sum of
oriented $k-$faces, i.e., $\sum_{i}c_{i}\sigma_{i},$ with
$c_{i}\in\mathbb{F}.$ The $k-$chain group $\mathfrak{C}_{k}(\mathcal{K})$ is
the free Abelian group generated by all $k$-chains, i.e.,

$\mathfrak{C}_{k}(\mathcal{K}):=\left\\{\sum_{i}c_{i}\sigma_{i}:c_{i}\in\mathbb{F},\sigma_{i}\in\mathcal{F}_{k}(\mathcal{K})\right\\},$

where $\mathcal{F}_{k}(\mathcal{K})$ is the set of all $k-$faces in
$\mathcal{K}.$ Clearly, if $\mathbb{F}=\mathbb{Z},$ then
$\mathfrak{C}_{k}(\mathcal{K})$ is a $\mathbb{Z}$-module, and if $\mathbb{F}$
is a field, then $\mathfrak{C}_{k}(\mathcal{K})$ is a $\mathbb{F}$-vector
space. Separately, set $\mathfrak{C}_{-1}=\mathbb{F}.$ Now, for $k\geq 0,$
define the boundary operator
$\partial_{k}:\mathfrak{C}_{k}\to\mathfrak{C}_{k-1}$ first on each $k-$simplex
using

$\partial_{k}\left((v_{0},\ldots,v_{k})\right)=\sum_{i=0}^{k}(-1)^{i}(v_{0},\ldots,\hat{v}_{i},\ldots,v_{k})$

and then extend it linearly on $\mathfrak{C}_{k}.$ Here, $\hat{v}_{i}$ implies
that the vertex $v_{i}$ is to be omitted. It is easy see that
$\partial_{k-1}\circ\partial_{k}=0$ for all $k\geq 1,$ i.e., boundary of a
boundary is zero. The $k-$th boundary space, denoted by $\mathcal{B}_{k},$ is
the image of $\partial_{k+1}$ and the $k-$th cycle space $\mathcal{Z}_{k}$ is
the kernel of $\partial_{k}$. The elements of $\mathcal{Z}_{k}$ are called
$k-$cycles, while the elements of $\mathcal{B}_{k}$ are called $k-$boundaries.
The $k$-th homology group $\mathcal{H}_{k}$ is defined to be the quotient
group $\mathcal{H}_{k}=\mathcal{Z}_{k}/\mathcal{B}_{k}.$ Clearly,
$\mathcal{H}_{k}$ is also a $\mathbb{F}$-module or a $\mathbb{F}$-vector space
depending on whether $\mathbb{F}=\mathbb{Z}$ or $\mathbb{F}$ is a field.
Finally, $\beta_{0}(\mathcal{K})=\textnormal{rank}(\mathcal{H}_{0})+1,$ while
$\beta_{k}(\mathcal{K})=\textnormal{rank}(\mathcal{H}_{k})$ when $k\geq 1.$

We now give a couple of definitions including that of a non-trivial cycle
(NTC) and then state two of its useful properties from [21, 22] in the context
of what is known as a clique complex.

Continuing with the above notions, for a chain $\gamma\in\mathfrak{C}_{k},$
let
$[\gamma]:=\\{\gamma^{\prime}\in\mathfrak{C}_{k}:\gamma^{\prime}-\gamma\in\mathcal{B}_{k}\\}$
be its equivalence class with respect to $\mathcal{B}_{k}.$ Then, it is easy
to see that $\mathcal{H}_{k}=\\{[\gamma]:\gamma\in\mathcal{Z}_{k}\\}.$

For $\sigma\in\mathcal{K},$ let $\textnormal{vsupp}(\sigma)$ be its vertex
support. For $\gamma=\sum_{i}c_{i}\sigma_{i},$ let
$\textnormal{vsupp}(\gamma):=\bigcup_{i:c_{i}\neq
0}\textnormal{vsupp}(\sigma_{i}).$ A chain $\gamma$ is a $k-$NTC if
$\gamma\in\mathcal{Z}_{k}\setminus\mathcal{B}_{k},$ and it has minimal vertex
support if
$|\textnormal{vsupp}(\gamma)|\leq|\textnormal{vsupp}(\gamma^{\prime})|$ for
each $\gamma^{\prime}\in[\gamma].$ Clearly, $\beta_{0}(\mathcal{K})$ is one
more than the maximal number of independent $0-$NTCs, while, for $k\geq 1,$
$\beta_{k}(\mathcal{K})$ is the maximal number of independent $k-$NTCs. Based
on this, given a set $\\{\mathcal{C}\\}$ of isolated induced subcomplexes of
$\mathcal{K},$ one can show that
$\beta_{k}(\mathcal{K})=\sum_{\mathcal{C}}\beta_{k}(\mathcal{C}).$

Separately, for a vertex $v\in\mathcal{K},$ its link
$\textnormal{lk}(v):=\\{\sigma\in\mathcal{K}:v\notin\sigma,\text{ but
}\sigma\cup\\{v\\}\in\mathcal{K}\\},$ while its star, denoted
$\textnormal{st}(v),$ is the smallest simplicial complex containing
$\\{\sigma\in\mathcal{K}:v\in\sigma\\}.$ Clearly, both the link and star of a
vertex are themselves simplicial complexes.

The $(k+1)-$dimensional cross-polytope is the convex hull of the $2k+2$ points
$\\{\pm e_{1},\ldots,\pm e_{k+1}\\},$ where $\bar{e}_{1},\bar{e}_{2}$ etc. are
the standard basis vectors. The boundary of this polytope can be represented
using a $k$-dimensional simplicial complex. Let $O_{k}$ denote the
$1-$skeleton of this complex. This is the graph on the above $2k+2$ points
where an edge is present between a pair if and only if the
$\|\cdot\|_{\infty}-$distance between them is $1.$

Given a graph $G\equiv(V,E),$ a set of vertices $v_{1},\ldots,v_{k}\in V$ is
said to form a clique if $\\{v_{i},v_{j}\\}\in E$ for all $v_{i},v_{j}.$ The
associated clique complex $\mathscr{X}(G)$ is the simplicial complex made up
of all the subsets of $V$ that form a clique in $G.$

######  Lemma 2.1.

[22, Lemma 3.4] Let $\mathscr{X}(G)$ be the clique complex associated with a
graph $G.$ Let $k\geq 0$ and $\gamma$ be a $k-$NTC of $\mathscr{X}(G).$ Then,
$|\textnormal{vsupp}(\gamma)|\geq 2(k+1).$ If
$\textnormal{vsupp}(\gamma)=2(k+1),$ then the $1-$skeleton of the induced
subcomplex of $\mathscr{X}(G)$ restricted to $\textnormal{vsupp}(\gamma)$ is
isomorphic to $O_{k}.$

######  Lemma 2.2.

[21, Lemma 5.2] Let $\mathcal{K}$ be a simplicial complex. For $k\geq 1$ and
$F$ being some set of $k-$faces, let $\gamma=\sum_{\sigma\in
F}c_{\sigma}\sigma$ be a $k-$NTC in $\mathcal{K}$ with minimal vertex support
and $c_{\sigma}\neq 0$ for all $\sigma\in F.$ Then, for any
$v\in\textnormal{vsupp}(\gamma),$
$\gamma\cap\textnormal{lk}(v):=\sum_{\sigma\in
F\cap\textnormal{st}(v)}c_{\sigma}\partial_{k}(\sigma)$ is a $(k-1)-$NTC in
$\textnormal{lk}(v)\cap\\{\sigma\in\mathcal{K}:\sigma\subseteq\textnormal{vsupp}(\gamma)\\}.$

######  Remark 2.3.

Consider the setup as in Lemma 2.2. For $v\in\textnormal{vsupp}(\gamma),$
define $\gamma\cap\textnormal{st}(v)$ to be $\sum_{\sigma\in F:v\in
F}c_{\sigma}\sigma.$ Then, it is easy to see that
$\gamma\cap\textnormal{lk}(v)=\partial_{k}(\gamma\cap\textnormal{st}(v)).$
Also, since $\gamma$ is a $k-$cycle, it follows that
$v\notin\textnormal{vsupp}(\gamma\cap\textnormal{lk}(v)).$

###  2.2 Probabilistic Background

Another key element across our computations is the tail probability of a
multivariate Gaussian random vector. A tight estimate for this has been given
in [37]. We state this result below after introducing some relevant notations.

Henceforth, we use the bar notation for vectors such as $\bar{Y},\bar{t},$
etc. To refer to their $l$-th coordinate we use $\bar{Y}(l),\bar{t}(l),$ etc.
All our vectors are row vectors and we denote their transpose using $\top.$
All vector inequalities mean that they hold coordinate wise. Specifically, for
any random vector $\bar{X}\in\mathbb{R}^{i}$ and $\bar{u}\in\mathbb{R}^{i},$
by $\\{\bar{X}\geq\bar{u}\\},$ we mean the event
$\\{\bar{X}(1)\geq\bar{u}(1),\ldots,\bar{X}(i)\geq\bar{u}(i)\\}.$ The
determinant of a matrix $M$ is denoted by $|M|,$ while $|r|$ denotes the
absolute value for any $r\in\mathbb{R}.$ Lastly, we use $\mathds{1}$ to denote
both the indicator random variable as well as the indicator function.

######  Lemma 2.4.

[37, (I), (II)] Let $i\geq 1$ and let $\bar{Y}\in\mathbb{R}^{i}$ be a zero
mean multivariate Gaussian random vector with positive definite covariance
matrix $M.$ Then, for each $\bar{u}\in\mathbb{R}^{i}$ such that
$\bar{\Delta}:=\bar{u}M^{-1}>0$ holds, the so called ‘Savage condition’, we
have

$1-\frac{1}{2}\sum_{j,\ell=1}^{i}\frac{M_{j\ell}[1+\delta_{j\ell}]}{\bar{\Delta}(j)\;\bar{\Delta}(\ell)}\leq\dfrac{\mathbb{P}\\{\bar{Y}\geq\bar{u}\\}}{(2\pi)^{-i/2}|M|^{-1/2}\exp[-[\bar{u}M^{-1}\bar{u}^{\top}]/2]\left[\prod_{j=1}^{i}\bar{\Delta}(j)\right]^{-1}}\leq
1,$ (2.1)

where $M_{j\ell}$ is $j\ell-$th entry of $M^{-1},$ and $\delta_{j\ell}=1$ if
$j=\ell,$ and $0$ otherwise.

To get elegant closed form expressions for tail probabilities using the above
result, it is important that the covariance matrix be ‘nice’. Often, this will
not be the case in our computations. To deal with the same, we shall be using
the following comparison inequality.

######  Lemma 2.5 (Slepian’s lemma).

Let $i\geq 0.$ Let $\bar{Y},\bar{Z}\in\mathbb{R}^{i}$ be multivariate Gaussian
random vectors such that $\mathbb{E}[\bar{Y}]=\mathbb{E}[\bar{Z}],$
$\textnormal{Var}[\bar{Y}(j)]=\textnormal{Var}[\bar{Z}(j)]$ for all $j,$ and
$\textnormal{Cov}[\bar{Y}(j),\bar{Y}(\ell)]\geq\textnormal{Cov}[\bar{Z}(j),\bar{Z}(\ell)]$
for all $j,\ell$ with $j\neq\ell.$ Then, for any $\bar{u}\in\mathbb{R}^{i},$
we have
$\mathbb{P}\\{\bar{Y}\geq\bar{u}\\}\geq\mathbb{P}\\{\bar{Z}\geq\bar{u}\\}.$

The proof of this result follows from [2, Theorem 2.3] by substituting
$h(\bar{x}(1),\bar{x}(2),\ldots,\bar{x}(i))=\prod_{j=1}^{i}\mathds{1}[\bar{x}(j)\geq\bar{u}(j)],$
where $h$ is as defined there. The only catch is that this function is not
smooth. But this can be easily overcome by approximating the indicators with
smooth increasing functions.

We prove both the Poisson as well the CLT portions of Theorem 1.4 using the
Stein-Chen method. As is the case here, this method is useful when we are
dealing with limit distributions of a sum of dependent indicator random
variables. To apply this method, a bound on the total variation distance
between the above mentioned sum and a Poisson random variable having the same
mean is required. We give one such bound in Theorem 2.9. In order to be able
to apply this bound to excursions of Gaussian random vectors, an additional
technical result is required. This is given in Theorem 2.11, the proof of
which is along the lines given in [18, Theorem 2.2].

######  Definition 2.6.

Let $Y,Z$ be $\mathbb{R}-$valued random variables. The total variation
distance between $Y$ and $Z$ is
$\|Y-Z\|_{\textnormal{TV}}:=\sup_{R\subseteq\mathbb{R}}|\mathbb{P}\\{Y\in
R\\}-\mathbb{P}\\{Z\in R\\}|.$

######  Remark 2.7.

If $Y$ and $Z$ are integer valued random variables defined on the same
probability space, then $\|Y-Z\|_{\textnormal{TV}}\leq\mathbb{P}\\{Y\neq
Z\\};$ see [15, pg 129].

######  Remark 2.8.

$\|\textnormal{Poi}(\lambda_{1})-\textnormal{Poi}(\lambda_{2})\|_{\textnormal{TV}}\leq|\lambda_{1}-\lambda_{2}|;$
see [1, Corollary 3.1].

######  Theorem 2.9.

[18, Theorem 2.1] (Stein-Chen method) Let $\Gamma$ be a finite index set. For
$i\in\Gamma,$ let $\Gamma_{i}:=\Gamma\setminus\\{i\\}.$ Let
$S=\sum_{i\in\Gamma}\mathds{1}_{i}$ and $\lambda=\mathbb{E}[S],$ where
$\\{\mathds{1}_{i}\\}_{i\in\Gamma}$ are some indicator random variables. For
each $i,$ let there be a probability space with indicator random variables
$\\{\zeta_{ji}\\}_{j\in\Gamma}$ and $\\{\eta_{ji}\\}_{j\in\Gamma_{i}}$ defined
on it such that

$\mathscr{L}(\zeta_{ji}:j\in\Gamma)=\mathscr{L}(\mathds{1}_{j}:j\in\Gamma),$

and

$\mathscr{L}(\eta_{ji}:j\in\Gamma_{i})=\mathscr{L}(\mathds{1}_{j}:j\in\Gamma_{i}\;|\;\mathds{1}_{i}=1),$

where $\mathscr{L}(\cdot)$ denotes the distribution function. Then, for
$\mathcal{U}_{i}=\sum_{j\in\Gamma}\zeta_{ji}$ and
$\mathcal{V}_{i}=\sum_{j\in\Gamma_{i}}\eta_{ji},$

$\|S-\textnormal{Poi}(\lambda)\|_{\textnormal{TV}}\leq\frac{1-e^{-\lambda}}{\lambda}\sum_{i\in\Gamma}\mathbb{E}[\mathds{1}_{i}]\;\mathbb{E}|\mathcal{U}_{i}-\mathcal{V}_{i}|.$

In addition, if there exists a partition
$\Gamma_{i}=\Gamma_{i}^{+}\cup\Gamma_{i}^{-}\cup\Gamma_{i}^{0}$ with
$\zeta_{ji}\leq\eta_{ji}$ a.s. for $j\in\Gamma_{i}^{+},$ and
$\zeta_{ji}\geq\eta_{ji}$ a.s. for $j\in\Gamma_{i}^{-},$ then

$\|S-\textnormal{Poi}(\lambda)\|_{\textnormal{TV}}\leq\frac{1-e^{-\lambda}}{\lambda}\left[\sum_{i\in\Gamma}[\mathbb{E}[\mathds{1}_{i}]]^{2}+\sum_{i\in\Gamma}\sum_{j\in\Gamma_{i}^{+}\cup\Gamma_{i}^{-}}|\textnormal{Cov}[\mathds{1}_{i},\mathds{1}_{j}]|+\sum_{i\in\Gamma}\sum_{j\in\Gamma_{i}^{0}}\left[\mathbb{E}[\mathds{1}_{i}\mathds{1}_{j}]+\mathbb{E}[\mathds{1}_{i}]\mathbb{E}[\mathds{1}_{j}]\right]\right].$

######  Remark 2.10.

For ease of use here, the above result is stated slightly differently from the
original version given in [18, Theorem 2.1].

######  Theorem 2.11.

Let $j,k\geq 0.$ Let $\bar{Y}_{i},$ for $0\leq i\leq j,$ be a random vector in
$\mathbb{R}^{k}$ so that $(\bar{Y}_{0},\ldots,\bar{Y}_{j})$ is multivariate
Gaussian with
$\textnormal{Cov}[\bar{Y}_{0}(\ell_{1}),\bar{Y}_{i}(\ell_{2})]\geq 0$ for all
$0\leq i\leq j$ and $1\leq\ell_{1},\ell_{2}\leq k.$ Then, for any
$\bar{u}\in\mathbb{R}^{k},$ there exists a probability space with
$\mathbb{R}^{k}-$valued random vectors $\\{\bar{Z}_{i}:1\leq i\leq j\\}$ and
$\\{\bar{Z}^{\prime}_{i}:1\leq i\leq j\\}$ such that

$\mathscr{L}(\bar{Z}_{i}:0\leq i\leq j)=\mathscr{L}(\bar{Y}_{i}:0\leq i\leq
j),$ $\mathscr{L}(\bar{Z}^{\prime}_{i}:0\leq i\leq
j)=\mathscr{L}(\bar{Y}_{i}:0\leq i\leq j\;|\;\bar{Y}_{0}\geq\bar{u}),$

and, for all $0\leq i\leq j,1\leq\ell\leq k,$

$\bar{Z}_{i}(\ell)\leq\bar{Z}^{\prime}_{i}(\ell)\text{ a.s.}$

The latter implies that
$\mathds{1}[\bar{Z}_{i}\geq\bar{u}]\leq\mathds{1}[\bar{Z}^{\prime}_{i}\geq\bar{u}]$
a.s. for all $0\leq i\leq j.$

###### Proof.

Let $g_{\bar{u}}:\mathbb{R}^{k}\to\mathbb{R}$ be the map
$g_{\bar{u}}(\bar{y})=\mathds{1}[\bar{y}\geq\bar{u}].$ Clearly, $g_{\bar{u}}$
is monotonically increasing in its arguments (with respect to coordinate-wise
partial order). Let $h:\mathbb{R}^{(j+1)k}\to\mathbb{R}$ be an arbitrary
increasing function in the above sense. Then, from [20, Corollary 3],

$\mathbb{E}[g_{\bar{u}}(\bar{Y}_{0}(1),\ldots,\bar{Y}_{0}(k))\,h(\bar{Y}_{0}(1),\ldots,\bar{Y}_{0}(k),\ldots,\bar{Y}_{j}(1),\ldots,\bar{Y}_{j}(k))]\geq\\\
\mathbb{E}[g_{\bar{u}}(\bar{Y}_{0}(1),\ldots,\bar{Y}_{0}(k))]\mathbb{E}[h(\bar{Y}_{0}(1),\ldots,\bar{Y}_{0}(k),\ldots,\bar{Y}_{j}(1),\ldots,\bar{Y}_{j}(k))].$
(2.2)

Hence, we have

$\mathbb{E}[h(\bar{Y}_{0}(1),\ldots,\bar{Y}_{0}(k),\ldots,\bar{Y}_{j}(1),\ldots,\bar{Y}_{j}(k))\;|\;\bar{Y}_{0}\geq\bar{u}]\geq\\\
\mathbb{E}[h(\bar{Y}_{0}(1),\ldots,\bar{Y}_{0}(k),\ldots,\bar{Y}_{j}(1),\ldots,\bar{Y}_{j}(k))].$

The desired result now holds from the equivalence of conditions (i) and (iv)
in [25, Theorem 1] (under the coordinate-wise partial order). ∎

##  3 Outline of Proof of Key Results

Here we first state all our major intermediate results and then prove Theorems
1.3 and 1.4. Proofs of these intermediate results are given later in Sections
4, 5, 6, and the Appendix; the page numbers are noted near the statements. The
result here either needs none or only a subset of the assumptions from Table
1. While $\Cr{a:rCAsm}$ is never needed in its entirety, various weaker
implications of it are used at different times. These are stated in Table 2.

Id | Assumption | Applicable when | Type | Implied by
---|---|---|---|---
$\Cl[Asm]{a:r2Asm}$ | $\begin{cases}1=1\\\\[8.61108pt] 0\leq\rho_{2}<\rho_{0}\end{cases}$ |  $k=0$ $1\leq k<d$ | Local |  $\Cr{a:r1Asm}$ and $\Cr{a:r2LAsm}$
$\Cl[Asm]{a:rqAsm}$ | $\begin{cases}1=1\\\\[8.61108pt] 0\leq\sup\limits_{q\geq 4}\rho_{q}\leq\rho_{3}<\rho_{2}\end{cases}$ |  $k=0,d-1$ $1\leq k<d-1$ | Boundedness | $\Cr{a:rCAsm}$
$\Cl[Asm]{a:r2LAsm}$ | $\begin{cases}0\leq\sup\limits_{q\geq 2}\rho_{q}\leq\rho_{1}\\\\[8.61108pt] 0\leq\sup\limits_{q\geq 3}\rho_{q}\leq\rho_{2}<\rho_{1}\end{cases}$ |  $k=0$ $1\leq k<d$ | Boundedness | $\Cr{a:rCAsm}$

Table 2:  Weaker Implications of Assumption $\Cr{a:r1Asm}$ and $\Cr{a:rCAsm}.$

Understanding the statistical behaviour of Betti numbers is not
straightforward. This is because they, being rank of some space, are not nice
enough combinatorial objects to be handled directly. Hence, as remarked in
Section 1, the trick is to use good approximators. We provide these in Theorem
3.3. But to see the motivation behind them, we initially discuss few relevant
properties of the Betti numbers of our Čech complex $\mathcal{K}(n;u),$ which
we establish separately.

First we show that the Čech and Vietoris-Rips complexes from Definitions 1.1
and 1.2 are equivalent. The statement is given below and the proof follows
from Lemma 4.3.

######  Proposition 3.1.

Let $n\geq 0$ and $u\in\mathbb{R}_{>0}.$ Then,
$\mathcal{K}(n;u)=\hat{\mathcal{K}}(n;u).$

An immediate and an important consequence of the above result and Definition
1.2 is that its $1-$skeleton, the underlying graph, completely characterizes
$\mathcal{K}(n;u).$ In that, $\sigma$ is a face in $\mathcal{K}(n;u)$ if and
only if the vertices in $\sigma$ form a clique in the $1-$skeleton of
$\mathcal{K}(n;u).$ In other words, $\mathcal{K}(n;u)$ is the clique complex
associated with its $1-$skeleton.

Henceforth, we shall say that the $k-$th Betti number is non-trivial if it is
at least $2$ when $k=0,$ and at least $1$ when $k\geq 1.$ Then, from
Proposition 3.1, and Lemma 2.1 along with the discussions above it on the
relationship between Betti numbers and NTCs, we right away have that every
induced subcomplex of $\mathcal{K}(n;u)$ with non-trivial $k-$th Betti number
has at least $2k+2$ vertices. Note that the induced subcomplex whose
$1-$skeleton is isomorphic to $O_{k}$ has non-trivial $\beta_{k}.$ Hence, it
follows that the minimal induced subcomplex having non-trivial $\beta_{k}$
must be the one that is isolated, has $2k+2$ vertices, and whose $1-$skeleton
is isomorphic to $O_{k}.$ Extending these facts to our setup, we prove the
following additional characteristic of induced subcomplexes with non-trivial
$\beta_{k}.$ Its proof is via induction and follows from Theorem 4.4.

######  Theorem 3.2.

In every induced subcomplex $\mathcal{C}\subseteq\mathcal{K}(n;u)$ with non-
trivial $k-$th Betti number, where $0\leq k<d,$ there exist at least $2k+2$
vertices with pairwise $\|\cdot\|_{1}$-distances at least $2.$

In general, the $1-$skeleton of a minimal induced subcomplex with non-trivial
$k-$th Betti number can either be $\|\cdot\|_{1}-$isometric to $O_{k}$ or not;
Figure 4 gives an example for each of these cases when $d=3$ and $k=1.$
Keeping in mind this observation, Figure 2, and the well known topological
fact, that the $k-$th Betti number is bounded from above by the number of
$k-$faces, we now introduce the different terms with which we approximate the
Betti numbers. Let

$\displaystyle\check{S}_{n,k}(u)$ $\displaystyle:=\begin{cases}\text{number of
isolated vertices in $\mathcal{K}(n;u),$}&\hskip 15.00002pt\text{if
$k=0,$}\\\\[4.30554pt] \parbox{270.00041pt}{ number of subgraph components in
the $1-$skeleton of $\mathcal{K}(n;u)$ that are isomorphic and
$\|\cdot\|_{1}-$isometric to $O_{k},$ }&\hskip 15.00002pt\text{if $1\leq
k<d;$}\end{cases}$

and

$\displaystyle\check{N}_{n,k}(u)$ $\displaystyle:=\begin{cases}0,&\hskip
15.00002pt\text{if $k=0,$}\\\\[4.30554pt] \parbox{270.00041pt}{ number of
subgraph components in the $1-$skeleton of $\mathcal{K}(n;u)$ that are
isomorphic but not $\|\cdot\|_{1}$-isometric to $O_{k},$ }&\hskip
15.00002pt\text{if $1\leq k<d.$}\end{cases}$

Further, for $0\leq k<d,$ to deal with non-minimal subcomplexes that
contribute to the $k-$th Betti number, let $\check{L}_{n,k}(u)$ be the number
of subgraphs in the $1-$skeleton of $\mathcal{K}(n;u)$ that are isomorphic to
a graph $G\in\mathcal{P}_{k},$ where $\mathcal{P}_{k}$ is as specified below.
With $\Gamma_{2k+1}$ defined as above Definition 1.1, let $\mathcal{G}_{k}$ be
the geometric graph on $\Gamma_{2k+1}$ with respect to
$\mathscr{B}_{\infty}(\cdot,\tfrac{1}{2});$ i.e., an edge is present between
two vertices whenever the $\|\cdot\|_{\infty}-$distance between them equals
$1.$ Now, if $k\geq 2,$ let

$\mathcal{P}_{k}:=\\{\text{Subgraphs
}G\equiv(V,E)\subseteq\mathcal{G}_{k}:G\text{ is connected, }\text{ elements
of $V$ are ordered }\\\ \text{lexicographically, }|V|\geq 2k+3,\;\exists\text{
$2k+2$ vertices in $V$ with pairwise}\\\ \text{$\|\cdot\|_{1}$-distances $\geq
2,$ $\exists$ \text{unique $(k+1)-$sized subset of $V$ that forms a clique in
$G$}}\\};$ (3.1)

whereas, if $k=1,$ let

$\mathcal{P}_{1}:=\\{\text{Subgraphs
}G\equiv(V,E)\subseteq\mathcal{G}_{1}:G\text{ is connected, }\text{ elements
of $V$ are ordered }\\\ \text{lexicographically, }|V|\geq 5,\;\text{
$\exists\;4$ vertices in $V$ with pairwise $\|\cdot\|_{1}$-distances $\geq
2$}\\};$ (3.2)

and, lastly, if $k=0,$ let

$\mathcal{P}_{0}:=\\{\text{Subgraphs
}G\equiv(V,E)\subseteq\mathcal{G}_{0}:G\text{ is connected, }\\\ \text{
elements of $V$ are ordered }\text{lexicographically, }|V|=2\\}.$ (3.3)

Loosely, $\mathcal{P}_{k}$ is the set of subgraphs to which each $k-$face, of
an induced subcomplex with non-trivial $\beta_{k},$ can be extended into. For
$1\leq k<d,$ the idea is similar to [22, Fig. 1]; the difference is, while
there the fact that each subgraph has $2k+3$ vertices is harnessed, we
additionally exploit the property that there is a further subset of $2k+2$
vertices with pairwise $\|\cdot\|_{1}-$distances at least $2.$

Figure 4:  A few examples of minimal induced subcomplexes with non-trivial
$\beta_{1}$ when $d=3.$

Using the above notions, the aforementioned approximators for Betti numbers of
$\mathcal{K}(n;u)$ are the lower and upper bounds given below. Its proof is
via induction and follows from Theorem 4.7.

######  Theorem 3.3.

Let $u\in\mathbb{R}_{>0}$ and $k$ be such that $0\leq k<d.$ Then,

$\check{S}_{n,k}(u)\leq\beta_{n,k}(u)\leq\check{S}_{n,k}(u)+\check{N}_{n,k}(u)+{\Cl[Const]{c:Betti}}_{,k}\,\check{L}_{n,k}(u),$

where ${\Cr{c:Betti}}_{,k}=1$ when $k=0$ or $2\leq k<d,$ while
${\Cr{c:Betti}}_{,1}$ is an universal upper bound on the number of edges in a
graph $G\in\mathcal{P}_{1}.$

######  Remark 3.4.

The constant ${\Cr{c:Betti}}_{,1}$ in the above result differs for the same
reasons as discussed below [22, Fig. 3]. But, roughly, $\check{L}_{n,1}(u)$
needs to be scaled suitably for it be a valid upper bound for the number of
edges and subsequently for the first Betti number.

We now elaborate on how we use these approximators or bounds to prove our key
results. The core idea is to show that, as $n$ and $u$ become large,
$\check{N}_{n,k}(u)$ and $\check{L}_{n,k}(u)$ become negligible compared to
$\check{S}_{n,k}(u)$ and that the latter more or less determines
$\beta_{n,k}(u).$ At this point, it is worth noting that the two terms
$\check{S}_{n,k}(u)$ and $\check{N}_{n,k}(u)$ are not simple combinatorial
objects themselves. In that, these terms count components and the isolation
condition, enforced thereby, is not easy to deal with directly. We overcome
this difficulty by further approximating these terms with even simpler
expressions. Specifically, instead of $\check{S}_{n,k}(u),$ we actually deal
with

$S_{n,k}(u)=\begin{cases}\sum_{\bar{t}\in\Gamma_{n}}\mathds{1}[X_{\bar{t}}\geq
u],&\text{ if }k=0,\\\\[4.30554pt]
\sum_{(\bar{t},\,\bar{\Omega})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}}\mathds{1}[\bar{X}_{\bar{t},\bar{\Omega}}\geq
u\bar{\mathbf{1}}_{2b_{k}}],&\text{ if }1\leq k<d.\end{cases}$ (3.4)

Here, for $i\geq 1,$ $\langle i\rangle$ is the increasingly ordered set
$(1,\ldots,i);$ $\tbinom{\langle d\rangle}{b_{k}}$ is the collection of all
increasingly ordered subsets of $\langle d\rangle$ with size $b_{k};$ for
$\bar{\Omega}\equiv(\omega_{1},\ldots,\omega_{k+1})\in\tbinom{\langle
d\rangle}{b_{k}},$

$\bar{X}_{\bar{t},\bar{\Omega}}=(X_{\bar{t}+\bar{e}_{\omega_{1}}},X_{\bar{t}-\bar{e}_{\omega_{1}}},\ldots,X_{\bar{t}+\bar{e}_{\omega_{b_{k}}}},X_{\bar{t}-\bar{e}_{\omega_{b_{k}}}});$
(3.5)

and $\bar{\mathbf{1}}_{i}$ is the all ones $i-$dimensional row vector. The set
$\tbinom{\langle d\rangle}{b_{k}}$ captures the different orientations in
which the minimal Betti generating complexes can occur; see the image on the
right in Figure 2 for an illustration. Working with $S_{n,k}(u)$ is much
easier than $\check{S}_{n,k}(u)$ as the former does not involve conditions
enforcing isolation and, for $k$ such that $1\leq k<d,$ it also has no
condition on $X_{\bar{t}}$ itself.

In the same spirit, as against $\check{N}_{n,k}(u),$ we work with $N_{n,k}(u)$
which is defined as follows. For each $k$ such that $1\leq k<d-1,$ let

$\mathcal{N}_{k}:=\\{\text{Subgraphs
}G\equiv(V,E)\subseteq\mathcal{G}_{0}:|V|=2k+2,\text{ elements of $V$ are
ordered}\\\ \text{lexicographically, }G\text{ is isomorphic but not
$\|\cdot\|_{1}-$isometric to }O_{k}\\},$ (3.6)

where $\mathcal{G}_{0}$ is as defined above (3.1). For
$\bar{t}\in\mathbb{Z}^{d}$ and $G\equiv(V,E),$ where
$V\subseteq\mathbb{Z}^{d}$ is ordered, let $\bar{X}_{\bar{t},G}$ be the
ordered vector $(X_{\bar{t}+\bar{v}}:\bar{v}\in V).$ Then,

$N_{n,k}(u):=\begin{cases}0,&\text{ if $k=0,d-1,$}\\\
\sum_{(\bar{t},\,G)\in\Gamma_{n}\times\mathcal{N}_{k}}\mathds{1}[\bar{X}_{\bar{t},G}\geq
u\bar{\mathbf{1}}_{2b_{k}}],&\text{ if $1\leq k<d-1.$}\end{cases}$ (3.7)

Separately, for $0\leq k<d,$ let

$L_{n,k}(u):=\sum_{(\bar{t},\,G)\in\Gamma_{n}\times\mathcal{P}_{k}}\mathds{1}[\bar{X}_{\bar{t},G}\geq
u\bar{\mathbf{1}}_{|V|}],$ (3.8)

where $\mathcal{P}_{k}$ is as in (3.1), (3.2), or (3.3); $V$ is the vertex set
of $G;$ and $\bar{X}_{\bar{t},G}$ is as defined above. While
$\check{L}_{n,k}(u)$ does not count components, nevertheless, the above
expression is the easier to handle.

The next result compares $S_{n,k}(u),N_{n,k}(u),$ and $L_{n,k}(u)$ with the
approximators in Theorem 3.3; its proof is given in Section 5, p. 5. As we
shall see in Remark 5.1 later, the additional $D_{n,k}(u)$ term is due to
boundary conditions.

######  Lemma 3.5.

Fix $k$ so that $0\leq k<d.$ Let $n\geq 0$ and $u\in\mathbb{R}_{>0}.$ Then,
the below statements hold:

  1. 1.

$\check{S}_{n,k}(u)\leq
S_{n,k}(u)\leq\check{S}_{n,k}(u)+{\Cr{c:Betti}}_{,k}\,\check{L}_{n,k}(u)+D_{n,k}(u),$
where ${\Cr{c:Betti}}_{,k}$ is as in Theorem 3.3, and

$D_{n,k}(u):=\begin{cases}0,&\text{ if $k=0,$}\\\\[4.30554pt]
\sum\limits_{\begin{subarray}{c}(\bar{t},\,\bar{\Omega})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}:\\\
\|\bar{t}\|_{\infty}=n\end{subarray}}\mathds{1}[\bar{X}_{\bar{t},\bar{\Omega}}\geq
u\bar{\mathbf{1}}_{2b_{k}}],&\text{ if $1\leq k<d.$}\end{cases}$ (3.9)

  2. 2.

$\check{N}_{n,k}(u)\leq N_{n,k}(u).$

  3. 3.

$\check{L}_{n,k}(u)\leq L_{n,k}(u).$

An immediate consequence of Theorem 3.3 and Lemma 3.5 is the following result,
which bounds the difference between $S_{n,k}(u)$ and $\beta_{n,k}(u).$

######  Lemma 3.6.

Fix $k$ such that $0\leq k<d.$ Let $n\geq 0$ and $u\in\mathbb{R}_{>0}.$ Then,

$|\beta_{n,k}(u)-S_{n,k}(u)|\leq
N_{n,k}(u)+{\Cr{c:Betti}}_{,k}\,L_{n,k}(u)+D_{n,k}(u),$

where ${\Cr{c:Betti}}_{,k}$ is as in Theorem 3.3.

Because of the above result, in order to prove Theorems 1.3 and 1.4, it
suffices to establish the corresponding results first for $S_{n,k}(u)$ and
then show that $N_{n,k}(u),$ $L_{n,k}(u),$ and $D_{n,k}(u)$ are all negligible
relative to $S_{n,k}(u).$ Indeed, this is precisely what we do.

In the above line of thought, our first result describes the asymptotic
behaviour of the mean value, along with the rate of convergence, of the
different terms in Lemma 3.6. Before stating it formally, we introduce few
notations. For $m\geq 1,$ and $\rho,\mu^{\prime}\in[0,1),$ let

$\phi_{m}(\rho,\mu^{\prime})=\dfrac{m+1+(m-1)\rho-2m\mu^{\prime}}{2(1+(m-1)\rho-m[\mu^{\prime}]^{2})}.$
(3.10)

Now, define constants

$\varrho_{k}:=\phi_{2b_{k}-1}(\rho_{2},\rho_{3}),\quad\text{ if $1\leq k<d,$}$
(3.11)

and

$\varphi_{k}:=\phi_{2b_{k}}(\rho_{2},\rho_{1})=\frac{1-2a_{k}[2\rho_{1}-1]}{2[1-2a_{k}\rho_{1}^{2}]},\quad\text{
if $0\leq k<d,$}$ (3.12)

######  Lemma 3.7.

Fix $k$ such that $0\leq k<d.$ Let $\lambda_{n,k}(u)$ be as in (1.4) and let
$\\{u_{n}\\}\in\mathbb{R}_{>0}^{\infty}$ be such that
$\lim_{n\to\infty}u_{n}=\infty.$ Then, the following statements are true.

  1. 1.

If $\Cr{a:r0Asm}$ and $\Cr{a:r2Asm}$ hold, then
$\left|\dfrac{\mathbb{E}[S_{n,k}(u_{n})]}{\lambda_{n,k}(u_{n})}-1\right|=O\left(\dfrac{1}{u_{n}^{2}}\right).$

  2. 2.

If $\Cr{a:r0Asm},\Cr{a:r2Asm},$ and $\Cr{a:rqAsm}$ hold, then
$\varrho_{k}>a_{k},$ for $1\leq k<d-1,$ and

$\dfrac{\mathbb{E}[N_{n,k}(u_{n})]}{\lambda_{n,k}(u_{n})}=\begin{cases}0,&\text{
if $k=0,d-1,$}\\\ O(\exp[-(\varrho_{k}-a_{k})u_{n}^{2}]),&\text{ if $1\leq
k<d-1.$}\end{cases}$

  3. 3.

If $\Cr{a:r0Asm},\Cr{a:r1Asm},$ $\Cr{a:ComC}(k),$ and $\Cr{a:r2LAsm}$ hold,
then $\varphi_{k}>a_{k}$ and
$\dfrac{\mathbb{E}[L_{n,k}(u_{n})]}{\lambda_{n,k}(u_{n})}=O(u_{n}^{-1}\exp[-(\varphi_{k}-a_{k})u_{n}^{2}]).$

  4. 4.

If $\Cr{a:r0Asm}$ and $\Cr{a:r2Asm}$ hold, then

$\dfrac{\mathbb{E}[D_{n,k}(u_{n})]}{\lambda_{n,k}(u_{n})}=\begin{cases}0,&\text{
if $k=0,$}\\\ O\left(\dfrac{1}{n}\right),&\text{ if $1\leq k<d.$}\end{cases}$

The proof of this result is given in Section 5, p. 5 and uses Slepian’s lemma
(Lemma 2.5) and Multivariate Gaussian tail estimates (Lemma 2.4); the Savage
condition in the latter is ensured due to our assumptions in Table 1.

It is now straightforward to establish Theorem 1.3 and the Statement 1 of
Theorem 1.4.

###### Proof of Theorem 1.3.

By a simple triangle inequality and Lemma 3.6,

$\left|\frac{\mathbb{E}[\beta_{n,k}(u_{n})]}{\lambda_{n,k}(u_{n})}-1\right|\leq\left|\dfrac{\mathbb{E}[S_{n,k}(u_{n})]}{\lambda_{n,k}(u_{n})}-1\right|+\dfrac{\mathbb{E}[N_{n,k}(u_{n})]}{\lambda_{n,k}(u_{n})}+\dfrac{\mathbb{E}[L_{n,k}(u_{n})]}{\lambda_{n,k}(u_{n})}+\dfrac{\mathbb{E}[D_{n,k}(u_{n})]}{\lambda_{n,k}(u_{n})}.$

Because
$1/u_{n}^{2}+\exp[-(\varphi_{k}-a_{k})u_{n}^{2}]+\exp[-(\varrho_{k}-a_{k})u_{n}^{2}]=O(1/u_{n}^{2}),$
the desired result is now easy to see from Lemma 3.7. ∎

###### Proof of Theorem 1.4.1.

From Markov’s inequality, we have

$1-\mathbb{P}\\{\beta_{n,k}(u_{n})=0\\}=\mathbb{P}\\{\beta_{n,k}(u_{n})\geq
1\\}\leq\mathbb{E}[\beta_{n,k}(u_{n})].$

On the other hand,

$\mathbb{E}[\beta_{n,k}(u_{n})]=\lambda_{n,k}(u_{n})\frac{\mathbb{E}[\beta_{n,k}(u_{n})]}{\lambda_{n,k}(u_{n})}=\lambda_{n,k}(u_{n})O\left(1+\frac{1}{u_{n}^{2}}+\frac{1}{n}\right)=\lambda_{n,k}(u_{n})O(1)=O(\lambda_{n,k}(u_{n})),$

where the second relation follows from Theorem 1.3, while the third one
follows because both $u_{n}$ and $n$ grow to $\infty.$ Finally, from (1.4) and
(1.5), and since $\nu_{n}\to\infty,$ we have

$\lambda_{n,k}(u_{n})=O\left(e^{-\nu_{n}}\left[\frac{\log n}{\log
n+\nu_{n}}\right]^{b_{k}}\right).$

The desired result is now easy to see. ∎

Moving on, our next result shows that $S_{n,k}(u_{n})$ has a Poisson behaviour
when $\lambda_{n,k}(u_{n})$ converges to a constant. Let

$\vartheta_{k}:=\frac{[1+(2b_{k}-1)\rho_{2}-2b_{k}\rho_{1}]^{2}}{1+(2b_{k}-1)\rho_{2}-2b_{k}\rho_{1}^{2}}=\frac{b_{k}[1-2a_{k}\rho_{1}]^{2}}{a_{k}[1-2a_{k}\rho_{1}^{2}]},\quad\text{
if $0\leq k<d,$}$ (3.13)

######  Theorem 3.8.

Fix $k$ such that $0\leq k<d.$ Let $\lambda_{n,k}(u)$ be as in (1.4) and
$\\{u_{n}\\}\in\mathbb{R}_{>0}^{\infty}$ be as in (1.5) with
$\lim_{n\to\infty}\nu_{n}=\log\left[\tfrac{1}{\lambda}\right]$ for some fixed
$\lambda\in\mathbb{R}_{>0}.$ Suppose
$\Cr{a:r0Asm},\Cr{a:r1Asm},\Cr{a:ComC}(k),\Cr{a:PoiG},$ and $\Cr{a:r2LAsm}$
hold. Then, $0<\vartheta_{k}<1;$ further,

$\|S_{n,k}(u_{n})-\textnormal{Poi}(\mathbb{E}[S_{n,k}(u_{n})])\|_{\textnormal{TV}}=O\left(n^{-d\vartheta_{k}/(2b_{k})}[\log
n]^{-(1-\vartheta_{k})/2}+\frac{\log n}{n}\sum_{q=1}^{2dn}\rho_{q}\right).$

The $k=0$ case of this result has been shown in [18, Theorem 3.6] using
Theorem 2.9. We build upon their ideas to show the multi-dimensional version
here. Our proof is given in Section 5, p. 5.

Using the above result and Lemma 3.7, we now establish the Poisson result for
$\beta_{n,k}(u_{n}).$

###### Proof of Theorem 1.4.2.

By the triangle inequality, and Remarks 2.7 and 2.8,

$\displaystyle\|\beta_{n,k}(u_{n})-\textnormal{Poi}(\lambda)\|_{\textnormal{TV}}$
$\displaystyle\leq$
$\displaystyle\|S_{n,k}(u_{n})-\textnormal{Poi}(\mathbb{E}[S_{n,k}(u_{n})])\|_{\textnormal{TV}}$
$\displaystyle\|\textnormal{Poi}(\mathbb{E}[S_{n,k}(u_{n})])-\textnormal{Poi}(\lambda)\|_{\textnormal{TV}}+\|\beta_{n,k}(u_{n})-S_{n,k}(u_{n})\|_{\textnormal{TV}}$
$\displaystyle\leq$
$\displaystyle\|S_{n,k}(u_{n})-\textnormal{Poi}(\mathbb{E}[S_{n,k}(u_{n})])\|_{\textnormal{TV}}$
$\displaystyle+\;|\mathbb{E}[S_{n,k}(u_{n})]-\lambda|+\mathbb{P}\\{\beta_{n,k}(u_{n})\neq
S_{n,k}(u_{n})\\}.$

Separately, Markov’s inequality and Lemma 3.6 show that

$\displaystyle\mathbb{P}\\{\beta_{n,k}(u_{n})\neq S_{n,k}(u_{n})\\}$
$\displaystyle=$
$\displaystyle\mathbb{P}\\{|\beta_{n,k}(u_{n})-S_{n,k}(u_{n})|\geq 1\\}$
(3.15) $\displaystyle\leq$
$\displaystyle\mathbb{E}[N_{n,k}(u_{n})]+\mathbb{E}[L_{n,k}(u_{n})]+\mathbb{E}[D_{n,k}(u_{n})].$

Further, we have

$\displaystyle\mathbb{E}[N_{n,k}(u_{n})]+\mathbb{E}[L_{n,k}(u_{n})]+\mathbb{E}[D_{n,k}(u_{n})]$
(3.16) $\displaystyle=$ $\displaystyle
O(\exp[-(\varrho_{k}-a_{k})u_{n}^{2}])+O(u_{n}^{-1}\exp[-(\varphi_{k}-a_{k})u_{n}^{2}])+O\left(\frac{1}{n}\right)$
$\displaystyle=$ $\displaystyle O\left(\frac{[\log
n]^{(\varrho_{k}-a_{k})b_{k}/a_{k}}}{n^{d(\varrho_{k}-a_{k})/a_{k}}}\right)+O\left(\frac{[\log
n]^{(\varphi_{k}-a_{k})b_{k}/a_{k}-0.5}}{n^{d(\varphi_{k}-a_{k})/a_{k}}}\right)+O\left(\frac{1}{n}\right)$
(3.17)

and

$|\mathbb{E}[S_{n,k}(u_{n})]-\lambda_{n,k}(u_{n})|=O\left(\frac{1}{u_{n}^{2}}\right)=O\left(\frac{1}{\log
n}\right),$ (3.18)

where (3.16) and (3.18) hold due to Lemma 3.7 and the fact that
$\lambda_{n,k}(u_{n})\to\lambda,$ a constant, while (3.17) follows by
observing
$\exp[-(\varrho_{k}-a_{k})u_{n}^{2}]=[\tau_{k}(2n+1)^{d}u_{n}^{-2b_{k}}]^{-(\varrho_{k}-a_{k})/a_{k}}[\lambda_{n,k}(u_{n})]^{(\varrho_{k}-a_{k})/a_{k}},$
and so on, and then making use of the facts that
$\lambda_{n,k}(u_{n})\to\lambda$ and $a_{k}u_{n}^{2}/[d\log n]\to 1.$

By substituting (1.5) in (1.4), additionally observe that

$|\lambda_{n,k}(u_{n})-\lambda|=\left|\left[\frac{\log[\tau_{k}(2n+1)^{d}]}{\left[\log[\tau_{k}(2n+1)^{d}]-b_{k}\log\left[\frac{\log[\tau_{k}(2n+1)^{d}]}{a_{k}}\right]+\nu_{n}\right]}\right]^{b_{k}}e^{-\nu_{n}}-\lambda\right|.$

Using the triangle inequality and the fact that
$\lim_{n\to\infty}\nu_{n}=\log[1/\lambda],$ it then follows that

$|\lambda_{n,k}(u_{n})-\lambda|=O(|e^{-\nu_{n}}-\lambda|)+O\left(\left|\left[\frac{\log[\tau_{k}(2n+1)^{d}]}{\log[\tau_{k}(2n+1)^{d}]-b_{k}\log\left[\frac{\log[\tau_{k}(2n+1)^{d}]}{a_{k}}\right]+\nu_{n}}\right]^{b_{k}}-1\right|\right).$

Recall that, if $f(x)=x^{b_{k}},$ then, by the monotonicity of $f^{\prime}(x)$
and the mean value theorem,

$|f(x)-f(1)|\leq b_{k}\left[\sup_{c\in\\{x,1\\}}x^{b_{k}-1}\right]|x-1|.$

Applying this above and using the fact that $\lim_{n\to\infty}\nu_{n}$ is a
constant, we get

$|\lambda_{n,k}(u_{n})-\lambda|=O(|e^{-\nu_{n}}-\lambda|)+O\left(\frac{\log\log
n}{\log n}\right).$

Consequently, the triangle inequality and (3.18) show

$|\mathbb{E}[S_{n,k}(u_{n})]-\lambda|=O(|e^{-\nu_{n}}-\lambda|)+O\left(\frac{\log\log
n}{\log n}\right).$ (3.19)

The desired result now follows from (3), (3.15), (3.17), (3.19), and Theorem
3.8. ∎

Finally, it remains to establish the non-vanishing regime behavior in Theorem
1.4. Towards that, we establish the following two results. The first one
discusses second order moments of $S_{n,k}(u),N_{n,k}(u),L_{n,k}(u),$ and
$D_{n,k}(u),$ while the next one obtains a CLT for $S_{n,k}(u).$ Unlike
Theorem 1.4, note that the CLT for $S_{n,k}(u)$ holds for the entire non-
vanishing regime (see Remark $\boldsymbol{\mathcal{R}_{13}}$).

######  Lemma 3.9.

Fix $k$ such that $0\leq k<d.$ Let $\lambda_{n,k}(u)$ be as in (1.4) and
$\\{u_{n}\\}\in\mathbb{R}_{>0}^{\infty}$ be as in (1.5) with
$\nu_{n}\to-\infty.$ Then, the following statements are true.

  1. 1.

If $\Cr{a:r0Asm},\Cr{a:r1Asm},\Cr{a:ComC}(k),$ $\Cr{a:CLTG},$ and
$\Cr{a:r2LAsm}$ hold, then
$\left|\dfrac{\textnormal{Var}[S_{n,k}(u_{n})]}{\lambda_{n,k}(u_{n})}-1\right|=O\left(\frac{1}{u_{n}^{2}}\right).$

  2. 2.

If $\Cr{a:r0Asm},\Cr{a:CLTG},\Cr{a:r2Asm},$ and $\Cr{a:rqAsm}$ hold, then

$\dfrac{\mathbb{E}[N_{n,k}^{2}(u_{n})]}{\lambda_{n,k}^{2}(u_{n})}=\begin{cases}0,&\text{
if $k=0,d-1,$ }\\\
O\left(\dfrac{\exp[-(\varrho_{k}-a_{k})u_{n}^{2}]}{\lambda_{n,k}(u_{n})}\right)+O\left(\exp[-2(\varrho_{k}-a_{k})u_{n}^{2}]\right),&\text{
if $1\leq k<d-1.$}\end{cases}$

  3. 3.

If $\Cr{a:r0Asm},\Cr{a:r1Asm},\Cr{a:ComC}(k),$ $\Cr{a:CLTG},$ and
$\Cr{a:r2LAsm}$ hold, then

$\dfrac{\mathbb{E}[L_{n,k}^{2}(u_{n})]}{\lambda_{n,k}^{2}(u_{n})}=O\left(\dfrac{u_{n}^{-1}\exp[-(\varphi_{k}-a_{k})u_{n}^{2}]}{\lambda_{n,k}(u_{n})}\right)+O\left(u_{n}^{-2}\exp[-2(\varphi_{k}-a_{k})u_{n}^{2}]\right).$

  4. 4.

If $\Cr{a:r0Asm},\Cr{a:r1Asm},\Cr{a:ComC}(k),$ $\Cr{a:CLTG},$ and
$\Cr{a:r2LAsm}$ hold, then

$\dfrac{\mathbb{E}[D_{n,k}^{2}(u_{n})]}{\lambda_{n,k}^{2}(u_{n})}=\begin{cases}0,&\text{
if $k=0,$}\\\
O\left(\dfrac{1}{n\lambda_{n,k}(u_{n})}\right)+O\left(\dfrac{1}{n^{2}}\right),&\text{
if $1\leq k<d.$}\end{cases}$

The proof of this result is given in Section 5, p. 5. Statements 1 and 4 need
the covariance bounds from Lemmas 5.6 and 5.7, while Statements 2 and 3
require the covariance type bounds from Lemma 5.8.

######  Theorem 3.10.

Fix $k$ such that $0\leq k<d.$ Let $\lambda_{n,k}(u)$ be as in (1.4) and
$\\{u_{n}\\}\in\mathbb{R}_{>0}^{\infty}$ be as in (1.5) with
$\lim_{n\to\infty}\nu_{n}=-\infty.$ Suppose
$\Cr{a:r0Asm},\Cr{a:r1Asm},\Cr{a:ComC}(k),\Cr{a:CLTG},$ and $\Cr{a:r2LAsm}$
hold. Then,

$\frac{S_{n,k}(u_{n})-\mathbb{E}[S_{n,k}(u_{n})]}{\sqrt{\lambda_{n,k}(u_{n})}}\Rightarrow
N(0,1).$

The proof for this result is given in Section 5, p. 5. Under the new set of
assumptions, the key trick, as in Theorem 3.8, again is to show
$\|S_{n,k}(u_{n})-\textnormal{Poi}(\mathbb{E}[S_{n,k}(u_{n})])\|_{\textnormal{TV}}\to
0.$ The desired result then follows from the fact that a sequence of Poisson
random variables with mean tending to $\infty,$ after suitable normalization,
converge in distribution to a standard Gaussian.

We now discuss the proof of Theorem 1.4.3.

###### Proof of Theorem. 1.4.3.

By Chebyshev’s inequality,

$\mathbb{P}\left\\{\left|\frac{\beta_{n,k}(u_{n})-\mathbb{E}[\beta_{n,k}(u_{n})]}{\lambda_{n,k}(u_{n})}\right|\geq\epsilon\right\\}\leq\frac{\textnormal{Var}[\beta_{n,k}(u_{n})]}{\epsilon^{2}\lambda_{n,k}^{2}(u_{n})}$

for all $\epsilon>0.$ Additionally, if $\epsilon\in(0,1),$ then it follows
from Theorem 1.3 that for all large enough $n$

$\\{\beta_{n,k}(u_{n})=0\\}\subseteq\left\\{\left|\frac{\beta_{n,k}(u_{n})-\mathbb{E}[\beta_{n,k}(u_{n})]}{\lambda_{n,k}(u_{n})}\right|\geq\epsilon\right\\},$

and hence

$\mathbb{P}\\{\beta_{n,k}(u_{n})=0\\}\leq\mathbb{P}\left\\{\left|\frac{\beta_{n,k}(u_{n})-\mathbb{E}[\beta_{n,k}(u_{n})]}{\lambda_{n,k}(u_{n})}\right|\geq\epsilon\right\\}.$

Consequently, both (1.7) and (1.8) are simple consequences of (1.6) which we
now prove.

Observe that

$\displaystyle\textnormal{Var}[\beta_{n,k}(u_{n})]$ $\displaystyle\leq$
$\displaystyle
2\textnormal{Var}[S_{n,k}(u_{n})]+2\,\textnormal{Var}[\beta_{n,k}(u_{n})-S_{n,k}(u_{n})]$
$\displaystyle\leq$ $\displaystyle
2\textnormal{Var}[S_{n,k}(u_{n})]+2\mathbb{E}|\beta_{n,k}(u_{n})-S_{n,k}(u_{n})|^{2}$
$\displaystyle=$ $\displaystyle
O\left(\textnormal{Var}[S_{n,k}(u_{n})]+\mathbb{E}[N_{n,k}^{2}(u_{n})]+\mathbb{E}[L_{n,k}^{2}(u_{n})]+\mathbb{E}[D_{n,k}^{2}(u_{n})]\right),$

where the first relation follows since, for any two random variables $Y_{1}$
and $Y_{2},$ we have
$2|\textnormal{Cov}[Y_{1},Y_{2}]|\leq\textnormal{Var}[Y_{1}]+\textnormal{Var}[Y_{2}];$
the second holds because $\textnormal{Var}[Y]\leq\mathbb{E}|Y|^{2}$ for any
random variable $Y;$ while the third one follows from Lemma 3.6. From Lemma
3.9, it is then easy to see that

$\frac{\textnormal{Var}[\beta_{n,k}(u_{n})]}{\lambda_{n,k}^{2}(u_{n})}=O\left(\frac{1}{\lambda_{n,k}(u_{n})}\right)+O\left(\exp[-2(\varrho_{k}-a_{k})u_{n}^{2}]\right)+O\left(u_{n}^{-2}\exp[-2(\varphi_{k}-a_{k})]\right)+O\left(\frac{1}{n^{2}}\right).$

Since $\varrho_{k}>a_{k}$ and $\varphi_{k}>a_{k}$ on account on Lemma 3.7 and,
also, since $\lambda_{n,k}(u_{n})\to\infty,$ it follows that (1.6) holds, as
desired.

We now turn to proving (1.9). Let

$C^{\nu}_{k}:=\begin{cases}\frac{\varphi_{k}-a_{k}}{\varphi_{k}-a_{k}/2},&\text{
if $k=0,$}\\\\[4.30554pt]
\min\left\\{\frac{\varrho_{k}-a_{k}}{\varrho_{k}-a_{k}/2},\frac{\varphi_{k}-a_{k}}{\varphi_{k}-a_{k}/2},\frac{2}{d}\right\\},&\text{
if $1\leq k<d.$}\end{cases}$ (3.20)

Since $\Cr{a:rCAsm}$ holds, note that $\rho_{2}\geq 0.$ Hence, $a_{k}\geq 0.$
Therefore, from Lemmas 3.7.2 and 3.7.3 and by the above definition, it follows
that $C^{\nu}_{k}\in(0,1].$

Suppose that $1\leq k<d.$ Using Lemma 3.7, we have

$\displaystyle\mathbb{P}\left\\{\left|\frac{[\beta_{n,k}(u_{n})-S_{n,k}(u_{n})]-\mathbb{E}[\beta_{n,k}(u_{n})-S_{n,k}(u_{n})]}{\sqrt{\lambda_{n,k}(u_{n})}}\right|>\epsilon\right\\}$
$\displaystyle\leq$
$\displaystyle\frac{2}{\epsilon}\frac{\mathbb{E}[N_{n,k}(u_{n})]+\mathbb{E}[L_{n,k}(u_{n})]+\mathbb{E}[D_{n,k}(u_{n})]}{\sqrt{\lambda_{n,k}(u_{n})}}$

for any $\epsilon>0.$ Hence, (1.9) follows from Theorem 3.10 and Slutsky’s
Theorem once we show that the three terms on the RHS decays to zero.

Observe that

$\displaystyle\frac{\mathbb{E}[N_{n,k}(u_{n})]}{\sqrt{\lambda_{n,k}(u_{n})}}$
$\displaystyle=$ $\displaystyle
O\left(\frac{(2n+1)^{d/2}}{u_{n}^{b_{k}}}\exp[-(\varrho_{k}-a_{k}/2)u_{n}^{2}]\right)$
$\displaystyle=$ $\displaystyle
O\left(\frac{(2n+1)^{d/2}}{u_{n}^{b_{k}}}\exp\left[-[\varrho_{k}/a_{k}-1/2]\left[[1-C]\log(2n+1)^{d}-b_{k}\log\left[\log(2n+1)^{d}\right]\right]\right]\right)$
$\displaystyle=$ $\displaystyle
O\left(\frac{1}{u_{n}^{b_{k}}}\exp\left[-[\varrho_{k}/a_{k}-1/2]\left[\left[\frac{\varrho_{k}-a_{k}}{\varrho_{k}-a_{k}/2}-C\right]\log(2n+1)^{d}-b_{k}\log\left[\log(2n+1)^{d}\right]\right]\right]\right)$
$\displaystyle\to$ $\displaystyle 0,$

where the first relation follows from Lemma 3.7.2 and (1.4), the second holds
due to (1.5) and the assumptions on $\nu_{n},$ the third relation follows by
simple algebra, while the last relation follows from (3.20) and since
$C<C^{\nu}_{k}.$

Similarly, one can see that
$\lim_{n\to\infty}\mathbb{E}[L_{n,k}(u_{n})]/\sqrt{\lambda_{n,k}(u_{n})}=0.$

Next, observe that

$\displaystyle\frac{\mathbb{E}[D_{n,k}(u_{n})]}{\sqrt{\lambda_{n,k}(u_{n})}}$
$\displaystyle=$ $\displaystyle
O\left(\frac{(2n+1)^{d/2}}{nu_{n}^{b_{k}}}\exp[-a_{k}u_{n}^{2}/2]\right)$
$\displaystyle=$ $\displaystyle
O\left(\frac{(2n+1)^{d/2}}{nu_{n}^{b_{k}}}\exp\left[-[1/2]\left[[1-C]\log(2n+1)^{d}-b_{k}\log\left[\log(2n+1)^{d}\right]\right]\right]\right)$
$\displaystyle\to$ $\displaystyle 0,$

where the first relation follows from Lemma 3.7.4 and (1.4), the second one
holds on account of (1.5) and the assumptions on $\nu_{n},$ while the last
relation follows since $C^{\nu}_{k}\leq 2/d$ and $C<C^{\nu}_{k}.$

This establishes (1.9) for the $1\leq k<d$ case. One can similarly argue the
$k=0$ case. This completes the proof. ∎

##  4 Key Properties of Geometric Complexes on a Lattice

Here we establish the main properties (Proposition 3.1 and Theorems 3.2 and
3.3) of our Čech and equivalently Vietoris-Rips complex that we mentioned in
Section 3 earlier. We also prove some additional features that we use later in
Sections 5 and 6. While we employ these results afterwards for our random
setup from Section 1, we emphasize that the discussion here is completely from
a deterministic perspective.

Throughout this section, let $V$ be an arbitrary fixed subset of
$\mathbb{Z}^{d}.$ As in Definitions 1.1 and 1.2 respectively, let
$\mathcal{K}$ be the Čech and $\hat{\mathcal{K}}$ be the Vietoris-Rips complex
on $V$ with respect to $\mathscr{B}_{\infty}(\cdot,\tfrac{1}{2}).$

Our first aim is to show that $\mathcal{K}=\hat{\mathcal{K}}.$ This follows
from their definitions and holds since these are defined on a lattice. We
begin with two trivial facts.

######  Fact 4.1.

If $r_{1},r_{2}\in\mathbb{Z}$ with $|r_{1}-r_{2}|=1,$ then for all
$r\in\mathbb{Z}$ with $\max\\{|r-r_{1}|,|r-r_{2}|\\}\leq 1,$ we have
$r\in\\{r_{1},r_{2}\\}.$

######  Fact 4.2.

If $r_{1},r_{2}\in\mathbb{Z}$ with $|r_{1}-r_{2}|=2,$ then for all
$r\in\mathbb{Z}$ with $\max\\{|r-r_{1}|,|r-r_{2}|\\}\leq 1,$ we have
$r=(r_{1}+r_{2})/2.$

######  Lemma 4.3.

$\mathcal{K}=\hat{\mathcal{K}}.$

###### Proof.

By definition, $\sigma\in\mathcal{K}$ implies that
$\sigma\in\hat{\mathcal{K}}.$ It thus suffices to show only the converse.
Clearly, if $\sigma\in\hat{\mathcal{K}}$ and $|\sigma|\in\\{1,2\\},$ then
$\sigma\in\mathcal{K}.$ Consider
$\sigma\equiv\\{\bar{t}_{0},\ldots,\bar{t}_{k}\\}\in\hat{\mathcal{K}}$ for
some $k\geq 2.$ As $\sigma\in\hat{\mathcal{K}},$
$\mathscr{B}_{\infty}(\bar{t}_{i},1/2)\cap\mathscr{B}_{\infty}(\bar{t}_{j},1/2)\neq\emptyset,$
or equivalently $\|\bar{t}_{i}-\bar{t}_{j}\|_{\infty}=1,$ for each pair
$\bar{t}_{i},\bar{t}_{j}.$ Without loss of generality, let
$\bar{t}_{0}\equiv\bar{0}.$ Then, using Fact 4.1, for any coordinate index
$l,$ exactly one of the following cases is true:

  * i)

$\bar{t}_{0}(l)=\bar{t}_{1}(l)=\bar{t}_{2}(l)=\cdots=\bar{t}_{k}(l)=0,$ or

  * ii)

for some $i\in\\{1,\ldots,k\\},$ $\bar{t}_{i}(l)=1;$ hence,
$\bar{t}_{i^{\prime}}(l)\in\\{0,1\\}$ for all
$i^{\prime}\in\\{1,\ldots,k\\}\setminus i,$ or

  * ii)

for some $i\in\\{1,\ldots,k\\},$ $\bar{t}_{i}(l)=-1;$ hence,
$\bar{t}_{i^{\prime}}(l)\in\\{-1,0\\}$ for all
$i^{\prime}\in\\{1,\ldots,k\\}\setminus i.$

Now define the vector $\bar{t}\in\mathbb{R}^{d}$ as follows:

$\bar{t}(l)=\begin{cases}\frac{1}{2},&\text{ if Cases i) or ii) hold, }\\\
-\frac{1}{2},&\text{ if Case iii) holds.}\end{cases}$

Trivially, $\bar{t}\in\mathscr{B}_{\infty}(\bar{t}_{i},1/2)$ for each
$i\in\\{0,\ldots,k\\}.$ The desired result is now easy to see. ∎

Precisely due to this equivalence, $\mathcal{K}$ here and $\mathcal{K}(n;u)$
from Definition 1.1 is both a Čech complex as well as a Vietoris-Rips complex.

We next establish the deterministic equivalent of Theorem 3.2.

######  Theorem 4.4.

In every induced subcomplex $\mathcal{C}\subseteq\mathcal{K}$ with non-trivial
$k-$th Betti number, where $0\leq k<d,$ there exist at least $2k+2$ vertices
with pairwise $\|\cdot\|_{1}$-distances at least $2.$

Before giving its proof, we state and prove two technical lemmas. For any
$\bar{t}\in\mathbb{Z}^{d}$ and $1\leq j\leq d,$ let
$\mathfrak{N}(\bar{t}),\mathfrak{N}^{{}^{-}}_{j}(\bar{t}),$ and
$\mathfrak{N}^{{}^{+}}_{j}(\bar{t})$ be suitable
$\|\cdot\|_{\infty}-$neighbourhoods of $\bar{t}$ in $\mathbb{Z}^{d}$ given by

$\mathfrak{N}(\bar{t}):=\\{\bar{t}^{\prime}\in\mathbb{Z}^{d}:\|\bar{t}-\bar{t}^{\prime}\|_{\infty}\leq
1\\},$
$\mathfrak{N}^{{}^{-}}_{j}(\bar{t}):=\\{\bar{t}^{\prime}\in\mathfrak{N}(\bar{t}):\bar{t}^{\prime}(j)=\bar{t}(j)-1\\},\text{
and
}\mathfrak{N}^{{}^{+}}_{j}(\bar{t}):=\\{\bar{t}^{\prime}\in\mathfrak{N}(\bar{t}):\bar{t}^{\prime}(j)=\bar{t}(j)+1\\}.$

######  Lemma 4.5.

Let $\bar{t}\in\mathbb{Z}^{d}$ and $j\in\\{1,\ldots,d\\}.$ Then, the following
statements hold:

  * •

For every induced subcomplex $\mathcal{C}\subseteq\mathcal{K}$ such that
$\mathcal{F}_{0}(\mathcal{C})\subseteq\mathfrak{N}(\bar{t})\setminus\mathfrak{N}^{{}^{-}}_{j}(\bar{t})$
and $\bar{t}+\bar{e}_{j}\in\mathcal{C},$ all its Betti numbers are trivial.

  * •

For every induced subcomplex $\mathcal{C}\subseteq\mathcal{K}$ such that
$\mathcal{F}_{0}(\mathcal{C})\subseteq\mathfrak{N}(\bar{t})\setminus\mathfrak{N}^{{}^{+}}_{j}(\bar{t})$
and $\bar{t}-\bar{e}_{j}\in\mathcal{C},$ all its Betti numbers are trivial.

###### Proof.

The first statement is proved here; the other one follows similarly. We use
induction on $k,$ the index of Betti numbers. For any
$\bar{t}^{\prime}\in\mathfrak{N}(\bar{t})\setminus\mathfrak{N}^{{}^{-}}_{j}(\bar{t}),$
we have

$\|\bar{t}^{\prime}-(\bar{t}+\bar{e}_{j})\|_{\infty}\leq 1.$ (4.1)

From this, the $k=0$ case is easy to see. Now assume the result for some
$(k-1).$ For the sake of contradiction, assume that there exists $\mathcal{C}$
with
$\mathcal{F}_{0}(\mathcal{C})\subseteq\mathfrak{N}(\bar{t})\setminus\mathfrak{N}^{{}^{-}}_{j}(\bar{t})$
and $\bar{t}+\bar{e}_{j}\in\mathcal{C}$ such that $\beta_{k}(\mathcal{C})\geq
1.$ This then immediately implies that there exists a $k-$NTC in $\mathcal{C}$
with minimal vertex support. In fact, we claim that there exists a $k-$NTC
$\gamma$ in $\mathcal{C}$ having minimal vertex support such that
$\bar{v}\equiv\bar{t}+\bar{e}_{j}\in\textnormal{vsupp}(\gamma).$ For the time
being, suppose that this latter claim is true. Then, for any
$\bar{v}^{\prime}\in\textnormal{vsupp}(\gamma)$ such that
$\bar{v}^{\prime}\neq\bar{v},$ from Lemma 2.2,
$\gamma\cap\textnormal{lk}(\bar{v}^{\prime})$ is a $(k-1)-$NTC in
$\mathcal{C}^{\prime}:=\textnormal{lk}(\bar{v}^{\prime})\cap\\{\sigma\in\mathcal{C}:\sigma\subseteq\textnormal{vsupp}(\gamma)\\},$
i.e., the $(k-1)-$th Betti number of $\mathcal{C}^{\prime}$ is non-trivial.
But $\mathcal{C}^{\prime}$ is an induced subcomplex of $\mathcal{K}$ with
$\mathcal{F}_{0}(\mathcal{C}^{\prime})\subseteq\mathfrak{N}(\bar{t})\setminus\mathfrak{N}^{{}^{-}}_{j}(\bar{t})$
and $\bar{v}\in\mathcal{C}^{\prime},$ where the latter is due to (4.1). These
statements contradict the induction hypothesis and we are done.

It only remains to establish our above claim. Let
$\gamma\equiv\sum_{\sigma\in\textnormal{supp}(\gamma)}c_{\sigma}\sigma$ be a
$k-$NTC in $\mathcal{C}$ with minimal vertex support such that
$\bar{v}\notin\textnormal{vsupp}(\gamma),$ where $\textnormal{supp}(\gamma)$
restriction in the summation means that the linear sum representation of
$\gamma$ has only those faces $\sigma$ for which $c_{\sigma}\neq 0.$ Pick
$\bar{v}^{\prime}\in\textnormal{vsupp}(\gamma);$ clearly,
$\bar{v}^{\prime}\neq\bar{v}.$ Consider the $k-$chain

$\gamma_{1}=\gamma\cap\textnormal{st}(\bar{v}^{\prime})=\sum_{\sigma\in\textnormal{st}(\bar{v}^{\prime})}c_{\sigma}\sigma,$

and let

$\gamma_{1}*\\{\bar{v}\\}:=\sum_{\sigma\in\textnormal{st}(\bar{v}^{\prime})}c_{\sigma}(\sigma,\bar{v}),$

where $(\sigma,\bar{v})$ is the oriented $(k+1)-$face whose first $(k+1)$
vertices are those of $\sigma$ and in the same order as in $\sigma,$ and the
last vertex is $\bar{v};$ and $\gamma\cap\textnormal{st}(\bar{v}^{\prime})$ is
defined as in Remark 2.3. As $\mathcal{C}$ is an induced complex,
$\gamma_{1}*\\{\bar{v}\\}$ is necessarily a $(k+1)-$chain in $\mathcal{C}.$
With $(\gamma\cap\textnormal{lk}(\bar{v}^{\prime}))*\\{v\\}$ defined as in the
spirit of $\gamma_{1}*\\{\bar{v}\\},$ and using the relation
$\gamma\cap\textnormal{lk}(\bar{v}^{\prime})=\partial_{k}(\gamma_{1})$ from
Remark 2.3, it is easy to see that

$\partial_{k+1}(\gamma_{1}*\\{\bar{v}\\})=(\gamma\cap\textnormal{lk}(\bar{v}^{\prime}))*\\{v\\}+(-1)^{k+1}\gamma_{1}.$

Let
$\gamma_{2}:=\gamma-(-1)^{k+1}\partial_{k+1}(\gamma^{\prime}*\\{\bar{v}\\}).$
Then, as $\partial_{k}\circ\partial_{k+1}=0,$ $\gamma_{2}\in[\gamma].$ From
Remark 2.3, $\bar{v}^{\prime}\notin\textnormal{vsupp}(\gamma_{2}),$ while,
from the definition of $\gamma_{2},$
$\bar{v}\in\textnormal{vsupp}(\gamma_{2})$ and
$\textnormal{vsupp}(\gamma_{2})\setminus\\{\bar{v}\\}\subseteq\textnormal{vsupp}(\gamma).$
Consequently, because $\gamma$ is a $k-$NTC with minimal vertex support,
$\gamma_{2}$ is also a $k-$NTC with minimal vertex support. Since
$\bar{v}\in\textnormal{vsupp}(\gamma_{2}),$ our claim follows. ∎

######  Lemma 4.6.

Let $j\in\\{1,\ldots,d\\}$ and $k$ be such that $1\leq k<d.$ Let $\gamma$ be a
$k-$NTC in $\mathcal{K}$ with minimal vertex support. Then, the following
statements hold:

  * •

If $\bar{t}\in\textnormal{vsupp}(\gamma)$ and
$\mathfrak{N}^{{}^{-}}_{j}(\bar{t})\cap\textnormal{vsupp}(\gamma)=\emptyset,$
then $\bar{t}+\bar{e}_{j}\notin\textnormal{vsupp}(\gamma).$

  * •

If $\bar{t}\in\textnormal{vsupp}(\gamma)$ and
$\mathfrak{N}^{{}^{+}}_{j}(\bar{t})\cap\textnormal{vsupp}(\gamma)=\emptyset,$
then $\bar{t}-\bar{e}_{j}\notin\textnormal{vsupp}(\gamma).$

###### Proof.

We only prove the first statement here; the other one follows similarly. From
Lemma 2.2, $\gamma\cap\textnormal{lk}(\bar{t})$ is a $(k-1)-$NTC in
$\mathcal{C}:=\textnormal{lk}(\bar{t})\cap\\{\sigma\in\mathcal{K}:\sigma\subseteq\textnormal{vsupp}(\gamma)\\},$
i.e., the $(k-1)-$th Betti number of $\mathcal{C}$ is non-trivial. Also,
$\mathfrak{N}^{{}^{-}}_{j}(\bar{t})\cap\textnormal{vsupp}(\gamma)=\emptyset$
implies that
$\mathcal{F}_{0}(\mathcal{C})\subseteq\mathfrak{N}(\bar{t})\setminus\mathfrak{N}^{{}^{-}}_{j}(\bar{t}).$
The desired result now follows from Lemma 4.5. ∎

We are now ready to prove Theorem 4.4.

###### Proof of Theorem 4.4.

We use induction on $k$. The result is trivially true for $k=0.$ Suppose the
result holds for some $k-1.$ Now consider an induced subcomplex
$\mathcal{C}\subseteq\mathcal{K}$ such that $\beta_{k}(C)\geq 1.$ For the sake
of contradiction, let the assumption below hold.

$\Cl[Asm]{a:pwDist}:\text{every $2k+2$ vertices in $\mathcal{C}$ have a pair
$\bar{t},\bar{t}^{\prime}$ such that $\|\bar{t}-\bar{t}^{\prime}\|_{1}=1.$}$

Since $\beta_{k}(\mathcal{C})\geq 1,$ there exists at least one $k-$NTC in
$\mathcal{C}$ with minimal vertex support. Below we show that, under
assumption $\Cr{a:pwDist},$ no such cycle can exist. This gives the desired
contradiction.

Let $\gamma$ be an arbitrary $k-$NTC with minimal vertex support in
$\mathcal{C}.$ From Lemma 2.1, $|\textnormal{vsupp}(\gamma)|\geq 2k+2.$ By
Assumption $\Cr{a:pwDist}$ above, every $2k+2$ vertices in
$\textnormal{vsupp}(\gamma)$ have a pair $\bar{t},\bar{t}^{\prime}$ such that
$\|\bar{t}-\bar{t}^{\prime}\|_{1}=1;$ without loss of generality, let
$\bar{0},\bar{e}_{1}\in\textnormal{vsupp}(\gamma).$ Since $\gamma$ is a
$k-$NTC of minimal vertex support and since
$\bar{0},\bar{e}_{1}\in\textnormal{vsupp}(\gamma),$ it follows from Lemma 4.6
that
$\mathfrak{N}^{{}^{-}}_{1}(\bar{0})\cap\textnormal{vsupp}(\gamma)\neq\emptyset$
and
$\mathfrak{N}^{{}^{+}}_{1}(\bar{e}_{1})\cap\textnormal{vsupp}(\gamma)\neq\emptyset.$
Let $\bar{v}_{{}_{-}},\bar{v}_{{}_{+}}$ respectively lie in
$\mathfrak{N}^{{}^{-}}_{1}(\bar{0})\cap\textnormal{vsupp}(\gamma)$ and
$\mathfrak{N}^{{}^{+}}_{1}(\bar{0})\cap\textnormal{vsupp}(\gamma).$

Through a series of claims, we first show that Assumption $\Cr{a:pwDist}$
forces all vertices in $\textnormal{vsupp}(\gamma)$ to be sufficiently close
to either $\bar{0}$ or $\bar{e}_{1}.$ We then show that this violates Lemma
4.5. Since $\gamma$ is arbitrary, the desired result follows.

$\textbf{Claim}_{1}:$ For all $\bar{t}\in\textnormal{vsupp}(\gamma),$
$-1\leq\bar{t}(1)\leq 2.$

For sake of contradiction, suppose that there exists
$\bar{t}\in\textnormal{vsupp}(\gamma)$ with $\bar{t}(1)\geq 3.$ From Lemma
2.2, $\gamma\cap\textnormal{lk}(\bar{t})$ is a $(k-1)-$NTC. Hence, by
induction hypothesis, there are $2k$ vertices in
$\mathfrak{N}(\bar{t})\cap\textnormal{vsupp}(\gamma)$ such that their pairwise
$\|\cdot\|_{1}-$distances are $\geq 2.$ Similarly, it follows that there are
$2k$ vertices in
$\mathfrak{N}(\bar{v}_{{}_{-}})\cap\textnormal{vsupp}(\gamma)$ with pairwise
$\|\cdot\|_{1}-$distances $\geq 2.$ But then we have a contradiction to
Assumption $\Cr{a:pwDist}$ above. By a symmetric argument, one can obtain a
contradiction if $\exists\bar{t}\in\textnormal{vsupp}(\gamma)$ with
$\bar{t}(1)\leq-2.$ Thus, the above claim follows.

$\textbf{Claim}_{2}:$ For all $\bar{t}\in\textnormal{vsupp}(\gamma),$
$|\bar{t}(j)|\leq 2$ for each $j\neq 1.$

To see this, suppose that there exists a
$\bar{t}\in\textnormal{vsupp}(\gamma)$ with $|\bar{t}(j)|\geq 3$ for some
$j\neq 1.$ Then, from Lemma 2.2 and the induction hypothesis, there exist $2k$
vertices, say $\bar{t}_{1},\ldots,\bar{t}_{2k},$ in
$\mathfrak{N}(\bar{t})\cap\textnormal{vsupp}(\gamma)$ with pairwise
$\|\cdot\|_{1}-$distances $\geq 2.$ If $\bar{t}(1)\geq 1,$ then it is easy see
that $\\{\bar{t}_{1},\ldots,\bar{t}_{2k},\bar{v}_{{}_{-}},\bar{e}_{1}\\}$ is a
set of $2k+2$ vertices with pairwise $\|\cdot\|_{1}-$distances $\geq 2.$ On
the other hand, if $\bar{t}(1)\leq 0,$ then
$\\{\bar{t}_{1},\ldots,\bar{t}_{2k},\bar{0},\bar{v}_{{}_{+}}\\}$ is a set of
$2k+2$ vertices with pairwise $\|\cdot\|_{1}-$distances $\geq 2.$ Both
contradict assumption $\Cr{a:pwDist}.$ The above claim follows.

In fact, we can improve upon $\textbf{Claim}_{2}$ as shown below.

$\textbf{Claim}_{3}:$ For all $\bar{t}\in\textnormal{vsupp}(\gamma),$
$|\bar{t}(j)|\leq 1$ for each $j\neq 1.$

Again, for sake of contradiction, assume there exists a
$\bar{t}\in\textnormal{supp}(\gamma)$ with $|\bar{t}(j)|=2$ for some $j\geq
1.$ For ease of exposition, first assume $\bar{t}(j)=2$ and $\bar{t}(1)\geq
1.$ From Lemma 2.2 and the induction hypothesis, there are $2k$ vertices, say
$\bar{t}_{1},\ldots,\bar{t}_{2k},$ in
$\mathfrak{N}(\bar{t})\cap\textnormal{vsupp}(\gamma)$ with pairwise
$\|\cdot\|_{1}-$distances $\geq 2.$ By similar arguments as for
$\textbf{Claim}_{1},$ it now follows that for each
$\bar{v}\in\textnormal{vsupp}(\gamma),$ $\bar{v}(j)\geq-1.$ In fact, we now
show that it cannot even be $-1;$ not even in
$\mathfrak{N}^{{}^{-}}_{1}(\bar{0})$ or
$\mathfrak{N}^{{}^{+}}_{1}(\bar{e}_{1}).$ To see this, suppose there exists a
$\bar{v}\in\textnormal{vsupp}(\gamma)$ such that $\bar{v}(j)=-1.$

  * •

Subcase $\bar{v}(1)\geq 1.$ From $\textbf{Claim}_{1},$ we have
$\mathfrak{N}^{{}^{-}}_{1}(\bar{v}_{{}_{-}})\cap\textnormal{vsupp}(\gamma)=\emptyset.$
Hence, from Lemma 4.6,
$\bar{v}_{{}_{-}}+\bar{e}_{1}\notin\textnormal{vsupp}(\gamma).$ Combining this
with $\bar{t}(1)\geq 1,$ it follows that
$\|\bar{v}_{{}_{-}}-\bar{t}_{i}\|_{1}\geq 2$ for all $i\in\\{1,\ldots,2k\\}.$
Also, since $\bar{t}(j)=2$ and $\bar{v}(j)=-1,$
$\|\bar{v}-\bar{t}_{i}\|_{1}\geq 2$ for all $i\in\\{1,\ldots,2k\\}.$ As
$\bar{v}_{{}_{-}}(1)=-1$ and $\bar{v}(1)\geq 1,$ we further have
$\|\bar{v}_{{}_{-}}-\bar{v}\|_{1}\geq 2.$ In other words,
$\\{\bar{t}_{1},\ldots,\bar{t}_{2k},\bar{v}_{{}_{-}},\bar{v}\\}$ is a set of
$2k+2$ vertices with pairwise $\|\cdot\|_{1}-$distances $\geq 2.$ This
contradicts $\Cr{a:pwDist}$ above.

  * •

Subcase $\bar{v}(1)\leq 0.$ Again, from Lemma 2.2 and the induction
hypothesis, there are $2k$ vertices, say $\bar{v}_{1},\ldots,\bar{v}_{2k},$ in
$\mathfrak{N}(\bar{v})\cap\textnormal{vsupp}(\gamma)$ with pairwise
$\|\cdot\|_{1}-$distances $\geq 2.$ From $\textbf{Claim}_{1},$ we have
$\mathfrak{N}^{{}^{+}}_{1}(\bar{v}_{{}_{+}})\cap\textnormal{vsupp}(\gamma)=\emptyset.$
Hence, from Lemma 4.6,
$\bar{v}_{{}_{+}}-\bar{e}_{1}\notin\textnormal{vsupp}(\gamma).$ Combining this
with $\bar{v}(1)\leq 0,$ we have $\|\bar{v}_{{}_{+}}-\bar{v}_{i}\|_{1}\geq 2$
for all $i\in\\{1,\ldots,2k\\}.$ As $\bar{v}(j)=-1$ and $\bar{t}(j)=2,$ we
additionally have $\|\bar{t}-\bar{v}_{i}\|_{1}\geq 2$ for all
$i\in\\{1,\ldots,2k\\}.$ Separately, from $\textbf{Claim}_{2},$ we have
$\mathfrak{N}^{{}^{+}}_{j}(\bar{t})\cap\textnormal{vsupp}(\gamma)=\emptyset.$
Hence, from Lemma 4.6, $\bar{t}-\bar{e}_{j}\notin\textnormal{vsupp}(\gamma).$
This necessarily implies that $\|\bar{t}-\bar{v}_{{}_{+}}\|_{1}\geq 2.$
Putting all the above together, it follows that
$\\{\bar{v}_{1},\ldots,\bar{v}_{2k},\bar{v}_{{}_{+}},\bar{t}\\}$ is a set of
$2k+2$ vertices with pairwise $\|\cdot\|_{1}-$distances $\geq 2.$ This
contradicts Assumption $\Cr{a:pwDist}$ above.

Hence, it follows that there cannot exist
$\bar{v}\in\textnormal{vsupp}(\gamma)$ such that $\bar{v}(j)=-1.$ In
particular,
$\mathfrak{N}^{{}^{-}}_{j}(\bar{e}_{1})\cap\textnormal{vsupp}(\gamma)=\emptyset.$
But from Lemma 4.6, we then immediately have
$\bar{e}_{1}+\bar{e}_{j}\notin\textnormal{vsupp}(\gamma).$ This means that
$\|\bar{e}_{1}-\bar{t}_{i}\|_{1}\geq 2$ for all $i\in\\{1,\ldots,2k\\}.$
Consequently, as in the first subcase above,
$\\{\bar{t}_{1},\ldots,\bar{t}_{2k},\bar{v}_{{}_{-}},\bar{e}_{1}\\}$ is a set
of $2k+2$ vertices with pairwise $\|\cdot\|_{1}-$distances $\geq 2.$ This
contradicts Assumption $\Cr{a:pwDist}$ again. So there exists no
$\bar{t}\in\textnormal{vsupp}(\gamma)$ such that $\bar{t}(1)\geq 1$ and
$\bar{t}(j)=2$ for some $j\neq 1.$ Similarly, by symmetric arguments, one can
show that there cannot exist any $\bar{t}\in\textnormal{vsupp}(\gamma)$ such
that $|\bar{t}(j)|=2$ for some $j\neq 1.$ The desired claim now follows.

Combining the three claims above, it follows that all vertices in
$\textnormal{vsupp}(\gamma)$ must be sufficiently close to either $\bar{0}$ or
$\bar{e}_{1};$ i.e., for all $\bar{t}\in\textnormal{vsupp}(\gamma),$ either
$\|\bar{t}-\bar{0}\|_{\infty}\leq 1$ or $\|\bar{t}-\bar{e}_{1}\|_{\infty}\leq
1.$ Consider $\bar{v}_{{}_{-}}$ as defined earlier. From Lemma 2.2,
$\gamma\cap\textnormal{lk}(\bar{v}_{{}_{-}})$ is a $(k-1)$-NTC in
$\mathcal{C}^{\prime}:=\textnormal{lk}(\bar{v}_{{}_{-}})\cap\\{\sigma\in\mathcal{C}:\sigma\subseteq\textnormal{vsupp}(\gamma)\\},$
i.e., $\beta_{k-1}(\mathcal{C}^{\prime})\geq 1.$ But observe that, since all
vertices in $\textnormal{vsupp}(\gamma)$ are sufficiently close to either
$\bar{0}$ or $\bar{e}_{1}$ as described above,
$\mathcal{F}_{0}(\mathcal{C}^{\prime})\subseteq\mathfrak{N}(-\bar{e}_{1})\setminus\mathfrak{N}^{{}^{-}}_{1}(-\bar{e}_{1}).$
Further, since $\mathcal{C}$ is an induced subcomplex of $\mathcal{K},$ it
follows that $\bar{0}\in\mathcal{C}^{\prime}.$ Together, these contradict
Lemma 4.5. Thus, $\gamma$ cannot exist as desired. ∎

We next prove the deterministic variant of Theorem 3.3. Let
$\check{S}_{k}(\mathcal{K}),$ $\check{N}_{k}(\mathcal{K}),$ and
$\check{L}_{k}(\mathcal{K})$ be the respective deterministic analogues of
$\check{S}_{n,k}(u),$ $\check{N}_{n,k}(u),$ and $\check{L}_{n,k}(u)$ from
Section 3 obtained by replacing $\mathcal{K}(n;u)$ there with $\mathcal{K}.$
The statement of Theorem 3.3 then translates to the following.

######  Theorem 4.7.

For $0\leq k<d,$

$\check{S}_{k}(\mathcal{K})\leq\beta_{k}(\mathcal{K})\leq\check{S}_{k}(\mathcal{K})+\check{N}_{k}(\mathcal{K})+{\Cr{c:Betti}}_{,k}\,\check{L}_{k}(\mathcal{K}).$

###### Proof.

The $k=0$ case is trivially true. So suppose that $1\leq k<d.$

Because $\mathcal{K}$ is also a Vietoris-Rips complex, the induced subcomplex
associated with a subgraph component that is isomorphic to $O_{k}$ contributes
exactly $1$ to the $k-$th Betti number. From this, the lower bound is easy to
see.

It now only remains to show the upper bound. Suppose that $k\geq 2.$ As
discussed above Lemma 2.1,
$\beta_{k}(\mathcal{K})=\sum_{\mathcal{C}}\beta_{k}(\mathcal{C}),$ where the
sum is over the isolated induced subcomplexes of $\mathcal{K}.$ Using Lemma
2.1 and the standard inequality
$\beta_{k}(\mathcal{C})\leq|\mathcal{F}_{k}(\mathcal{C})|$ from the simplicial
homology theory, we then have

$\beta_{k}(\mathcal{K})\leq\check{S}_{k}(\mathcal{K})+\check{N}_{k}(\mathcal{K})+\sum_{\mathcal{C}:|\mathcal{F}_{0}(\mathcal{C})|\geq
2k+3}|\mathcal{F}_{k}(\mathcal{C})|\;\mathds{1}[\beta_{k}(\mathcal{C})\geq
1].$

Consider the $1-$skeleton of an arbitrary $\mathcal{C}$ with
$|\mathcal{F}_{0}(\mathcal{C})|\geq 2k+3$ and $\beta_{k}(\mathcal{C})\geq 1.$
Using Theorem 4.4, in this skeleton there exists a tree $G_{\mathcal{C}}$ such
that: (a) it has at least $2k+3$ vertices, (b) it has a further subset of
$2k+2$ vertices having pairwise $\|\cdot\|_{1}-$distances at least two, and
(c) its $\|\cdot\|_{\infty}-$diameter is at most $4k+3.$ The vertex properties
in (a) and (b) trivially hold in a tree with diameter $4k+3,$ justifying the
$4k+3$ limit. Now let $\sigma$ be any $k-$face in $\mathcal{C}.$ Clearly,
there exists a subgraph in $\mathcal{C}$ connecting
$\textnormal{vsupp}(\sigma)$ to $G_{\mathcal{C}}.$ Depending on the
$\|\cdot\|_{\infty}-$distance of $\textnormal{vsupp}(\sigma)$ from
$G_{\mathcal{C}},$ and removing edges if necessary, it is easy to see that
there exists a subgraph isomorphic to one in $\mathcal{P}_{k}$ such that
$\textnormal{vsupp}(\sigma)$ forms the only $(k+1)-$sized clique in this
subgraph. Therefore,
$|\mathcal{F}_{k}(\mathcal{C})|\mathds{1}[\beta_{k}(\mathcal{C})\geq
1]\leq\check{L}_{k}(\mathcal{C}).$ The desired result now follows.

By making suitable changes to the above argument, in the exact same spirit as
discussed below [22, Fig. 3], the desired result follows for the $k=1$ case as
well. ∎

The rest of the section describes some useful properties concerning subgraph
components in the $1-$skeleton of $\mathcal{K}$ that are isomorphic to
$O_{k}.$ Fix $k\geq 1$ and let
$V\equiv\\{\bar{t}_{1},\ldots,\bar{t}_{2k+2}\\}\subseteq\mathbb{Z}^{d}$ be
such that the geometric graph $G$ on these vertices, with respect to
$\mathscr{B}_{\infty}(\cdot,\tfrac{1}{2}),$ is isomorphic to $O_{k}.$

The following result is a consequence of Theorem 4.4 and the fact that the
induced subcomplex of $\mathcal{K}$ associated with $G$ has non-trivial $k-$th
Betti number.

######  Corollary 4.8.

For any $i_{1},i_{2}\in\\{1,\ldots,2k+2\\}$ with $i_{1}\neq i_{2},$
$\|\bar{t}_{i_{1}}-\bar{t}_{i_{2}}\|_{1}\geq 2.$

Observe that, for every vertex in $O_{k},$ there is precisely one other vertex
to which it is not connected to. The following result shows that the
$\|\cdot\|_{\infty}-$distance between the corresponding vertex pairs in $G$ is
precisely $2.$

######  Lemma 4.9.

Fix an arbitrary $i\in\\{1,\ldots,2k+2\\}.$ Then, there exists a unique
$i^{\prime}$ such that $\|\bar{t}_{i}-\bar{t}_{i^{\prime}}\|_{\infty}\geq 2;$
in fact, $\|\bar{t}_{i}-\bar{t}_{i^{\prime}}\|_{\infty}=2.$

###### Proof.

Fix an arbitrary $i.$ Because $G$ is isomorphic to $O_{k},$ clearly, there
exists a unique $i^{\prime}$ such that
$\|\bar{t}_{i}-\bar{t}_{i^{\prime}}\|_{\infty}\geq 2.$ However, for each
$j\neq i,i^{\prime},$ we additionally have
$\|\bar{t}_{j}-\bar{t}_{i}\|_{\infty}=\|\bar{t}_{j}-\bar{t}_{i^{\prime}}\|_{\infty}=1.$
But the latter condition can hold only if
$\|\bar{t}_{i}-\bar{t}_{i^{\prime}}\|_{\infty}=2.$ The desired result thus
follows. ∎

From the above result and the definition of $G,$ the below statement is
immediate.

######  Corollary 4.10.

$G$ is $\|\cdot\|_{\infty}-$isometric to $O_{k}.$

For a general $k,$ the graph $G$ can either be $\|\cdot\|_{1}-$isometric to
$O_{k}$ or not. We now show that, if $k=d-1,$ then it has to be.

######  Lemma 4.11.

If $k=d-1,$ then $G$ is also $\|\cdot\|_{1}-$isometric to $O_{d-1}.$

###### Proof.

First, observe that $V$ has $2d$ vertices. Separately, from Corollary 4.10, we
have that, for each $i,$ there is a unique $i^{\prime}$ such that
$\|\bar{t}_{i}-\bar{t}_{i^{\prime}}\|_{\infty}=2.$ Hence, $V$ can be written
as
$\\{\bar{t}_{1},\bar{t}_{1^{\prime}},\ldots,\bar{t}_{d},\bar{t}_{d^{\prime}}\\}.$
Let $\mathcal{I}_{i}$ be the set of coordinate indices in which $\bar{t}_{i}$
and $\bar{t}_{i^{\prime}}$ differ by $2;$ this is clearly non-empty.

Fix some arbitrary $i,j.$ From Corollary 4.10,
$\|\bar{t}_{j_{1}}-\bar{t}_{j_{2}}\|_{\infty}=1$ for
$j_{1}\in\\{j,j^{\prime}\\}$ and $j_{2}\in\\{i,i^{\prime}\\}.$ From Fact 4.2,
it then follows that, for each $l\in I_{i},$
$\bar{t}_{j}(l)=\bar{t}_{j^{\prime}}(l)=(\bar{t}_{i}(l)+\bar{t}_{i^{\prime}}(l))/2,$
and viceversa. Consequently, $\mathcal{I}_{i}\cap\mathcal{I}_{j}=\emptyset.$
As $i,j$ were arbitrary, and since there are only $d$ distinct coordinate
indices, the desired result is easy to see. ∎

The next result states that, for general $k,$ if $G$ is indeed
$\|\cdot\|_{1}-$isometric to $O_{k},$ then its vertices have a unique ordered
representation.

######  Lemma 4.12.

$G$ is $\|\cdot\|_{1}-$isometric to $O_{k}$ if and only if there is a unique
$\bar{t}\in\mathbb{Z}^{d}$ and a unique
$\bar{\Omega}\equiv(\omega_{1},\ldots,\omega_{k+1})\in\tbinom{\langle
d\rangle}{b_{k}}$ such that the vertices of $G$ are, up to permutation,

$(\bar{t}+\bar{e}_{\omega_{1}},\bar{t}-\bar{e}_{\omega_{1}},\ldots,\bar{t}+\bar{e}_{\omega_{k+1}},\bar{t}-\bar{e}_{\omega_{k+1}}).$

###### Proof.

We only show the necessary part of the statement as the other direction is
obvious. Suppose $G$ is $\|\cdot\|_{1}-$isometric to $O_{k}.$ Then, using
Corollary 4.10, we have that, for any $i,$ there exists a unique
$i^{\prime}\neq i$ such that
$\|\bar{t}_{i}-\bar{t}_{i^{\prime}}\|_{\infty}=\|\bar{t}_{i}-\bar{t}_{i^{\prime}}\|_{1}=2;$
further, for each $j_{1}\in\\{i,i^{\prime}\\}$ and
$j_{2}\notin\\{i,i^{\prime}\\},$
$\|\bar{t}_{j_{1}}-\bar{t}_{j_{2}}\|_{\infty}=1$ and
$\|\bar{t}_{j_{1}}-\bar{t}_{j_{2}}\|_{1}=2.$ From these observations and Fact
4.2, it is easy to see that the desired result holds with
$\bar{t}=(\sum_{i=1}^{2k+2}\bar{t}_{i})/(2k+2).$ ∎

Suppose $k<d-1.$ Then, it is possible that $G$ is only isomorphic but not
$\|\cdot\|_{1}-$isometric to $O_{k}.$ The next result show that, while there
is no unique representation, there does exist a common neighbour to all its
vertices with respect to the $\|\cdot\|_{\infty}-$distance.

######  Lemma 4.13.

Suppose $G$ is not $\|\cdot\|_{1}-$isometric to $O_{k}.$ Then, there is a
$\bar{t}\in\mathbb{Z}^{d}$ such that $\|\bar{t}-\bar{t}_{i}\|_{\infty}=1$ for
all $j.$

###### Proof.

Fix an arbitrary $i.$ It follows from Corollary 4.10 that there exists a
unique $i^{\prime}\neq i$ such that
$\|\bar{t}_{i}-\bar{t}_{i^{\prime}}\|_{\infty}=2.$ Now define $\bar{t}$ using
the following rule: for each $l\in\langle d\rangle,$

$\bar{t}(l):=\begin{cases}(\bar{t}_{i}(l)+\bar{t}_{i^{\prime}}(l))/2,&\text{
if $|\bar{t}_{i}(l)-\bar{t}_{i^{\prime}}(l)|=2,$}\\\ \bar{t}_{i}(l),&\text{
otherwise. }\end{cases}$

Keeping in mind $\|\bar{t}_{i}-\bar{t}_{i^{\prime}}\|_{\infty}=2,$ it is easy
to see that
$\|\bar{t}-\bar{t}_{i}\|_{\infty}=\|\bar{t}-\bar{t}_{i^{\prime}}\|_{\infty}=1.$

Now consider any arbitrary $j\notin\\{i,i^{\prime}\\}.$ Again, from Corollary
4.10, we have that $\|\bar{t}_{j}-\bar{t}_{j^{\prime}}\|_{\infty}=1$ for all
$j^{\prime}\in\\{i,i^{\prime}\\}.$ From these observations and Fact 4.2, it is
easy to see that $\|\bar{t}_{j}-\bar{t}\|_{\infty}=1.$

Since $j$ is arbitrary, the desired result follows. ∎

Whenever $G$ is only isomorphic but not $\|\cdot\|_{1}-$isometric to $O_{k},$
our final result here shows that the vertex set of $G$ can be partitioned into
two non-empty subsets such that the pairwise $\|\cdot\|_{1}-$distances between
vertices in the two subsets is at least $3.$

######  Lemma 4.14.

Suppose $G$ is not $\|\cdot\|_{1}-$isometric to $O_{k}.$ Then, its vertex set
$V$ can be partitioned into non-empty subsets $V_{1}$ and $V_{2}$ so that
$1\leq|V_{1}|\leq k+1;$ further, for every $\bar{t}_{j_{1}}\in V_{1}$ and
$\bar{t}_{j_{2}}\in V_{2},$ $\|\bar{t}_{j_{1}}-\bar{t}_{j_{2}}\|_{1}\geq 3.$

###### Proof.

From Corollary 4.8 and the fact that $G$ is not $\|\cdot\|_{1}-$isometric to
$O_{k},$ it follows that there exists a pair $i_{1},i_{2}$ such that
$\|\bar{t}_{i_{1}}-\bar{t}_{i_{2}}\|_{1}\geq 3.$ With such a pair, partition
$V$ into two subsets $V_{1}$ and $V_{2}$ where

$V_{1}:=\\{\bar{t}_{j}:\|\bar{t}_{i_{1}}-\bar{t}_{j}\|_{1}\leq 2\\}\text{ and
}V_{2}:=V\setminus V_{1}.$

Clearly, $V_{1}$ contains $\bar{t}_{i_{1}}$ and $V_{2}$ contains
$\bar{t}_{i_{2}};$ so, both are non-empty. We now show that for
$\bar{t}_{j_{1}}\in V_{1}$ and $\bar{t}_{j_{2}}\in V_{2}$

$\|\bar{t}_{j_{1}}-\bar{t}_{j_{2}}\|_{1}\geq 3.$

Fix $\bar{t}_{j_{1}}\in V_{1}$ and $\bar{t}_{j_{2}}\in V_{2}.$ From Corollary
4.10, either

$\|\bar{t}_{j_{1}}-\bar{t}_{j_{2}}\|_{\infty}=2\text{ or
}\|\bar{t}_{j_{1}}-\bar{t}_{j_{2}}\|_{\infty}=1.$

Keeping this in mind, we break our arguments into several cases:

  1. 1.

$j_{1}=i_{1}:$ Here the claim follows from the definition of $V_{1}.$

  2. 2.

$j_{1}\neq i_{1}$ and $\|\bar{t}_{j_{1}}-\bar{t}_{j_{2}}\|_{\infty}=2:$
Clearly, there exists a coordinate index $l$ such that
$|\bar{t}_{j_{1}}(l)-\bar{t}_{j_{2}}(l)|=2.$ If there is more than one such
coordinate index, then we are already done. So, consider the case when there
is precisely one such $l.$ It suffices to show that there is a coordinate
index, other than $l,$ where $\bar{t}_{j_{1}}$ and $\bar{t}_{j_{2}}$ differ by
at least $1.$ Due to Corollary 4.10, it follows that
$\|\bar{t}_{i_{1}}-\bar{t}_{j_{1}}\|_{\infty}=\|\bar{t}_{i_{1}}-\bar{t}_{j_{2}}\|_{\infty}=1.$
Hence, using Fact 4.2,
$|\bar{t}_{i_{1}}(l)-\bar{t}_{j_{1}}(l)|=|\bar{t}_{i_{1}}(l)-\bar{t}_{j_{2}}(l)|=1.$
From the definition of $V_{1},$ we also have
$\|\bar{t}_{i_{1}}-\bar{t}_{j_{2}}\|_{1}\geq 3.$ Further, by combining the
definition of $V_{1}$ and Corollary 4.8, we have
$\|\bar{t}_{i_{1}}-\bar{t}_{j_{1}}\|_{1}=2.$ These observations imply that,
other than $l,$ $\bar{t}_{j_{2}}$ must differ from $\bar{t}_{i_{1}}$ in at
least two other coordinates, and the value of the difference must be exactly
$1;$ while $\bar{t}_{j_{1}}$ must vary from $\bar{t}_{i_{1}}$ in only one
other coordinate, with the difference being exactly one again. The desired
claim is now easy to see.

  3. 3.

$j_{1}\neq i_{1}$ and $\|\bar{t}_{j_{1}}-\bar{t}_{j_{2}}\|_{\infty}=1:$ From
Lemma 4.9, there exists a unique $j_{1}^{\prime}$ such that
$\|\bar{t}_{j_{1}}-\bar{t}_{j_{1}^{\prime}}\|_{\infty}=2.$ The subsequent
arguments are broken into further subcases.

    1. (a)

$j_{1}^{\prime}=i_{1}:$ From the definition of $V_{1}$ and Corollary 4.8,
$\|\bar{t}_{i_{1}}-\bar{t}_{j_{1}}\|_{1}=2.$ This implies there is precisely
one coordinate index $l$ in which $\bar{t}_{i_{1}}$ and $\bar{t}_{j_{1}}$
differ and that $|\bar{t}_{i_{1}}(l)-\bar{t}_{j_{1}}(l)|=2.$ Due to Corollary
4.10,
$\|\bar{t}_{j_{1}}-\bar{t}_{j_{2}}\|_{\infty}=\|\bar{t}_{i_{1}}-\bar{t}_{j_{2}}\|_{\infty}=1.$
But, from the definition of $V_{1},$
$\|\bar{t}_{i_{1}}-\bar{t}_{j_{2}}\|_{1}\geq 3.$ Combining these observations
with Fact 4.2, the desired claim is now easy to see.

    2. (b)

$j_{1}^{\prime}\neq i_{1}:$ Again, from Corollary 4.10,
$\|\bar{t}_{\ell_{1}}-\bar{t}_{\ell_{2}}\|_{\infty}=1$ for each
$\ell_{1}\in\\{j_{1},j_{1}^{\prime}\\}$ and $\ell_{2}\in\\{i_{1},j_{2}\\}.$
Along with Fact 4.2, the above implies that, for each coordinate index $l$
where $|\bar{t}_{j_{1}}(l)-\bar{t}_{j_{1}^{\prime}}(l)|=2,$ we have
$|\bar{t}_{i_{1}}(l)-\bar{t}_{j_{2}}(l)|=0$ and
$|\bar{t}_{j_{1}}(l)-\bar{t}_{j_{2}}(l)|=1.$ Let $\mathcal{I}$ be the
collection of all such $l.$ Now fix an $l\in\mathcal{I}.$ From the definition
of $V_{1}$ and Corollary 4.8, $\|\bar{t}_{i_{1}}-\bar{t}_{j_{1}}\|_{1}=2.$
Therefore, $\bar{t}_{i_{1}}$ and $\bar{t}_{j_{2}}$ differ in only one
coordinate, other than $l,$ and that difference is precisely $1.$ But, from
the definition of $V_{1},$ $\|\bar{t}_{i_{1}}-\bar{t}_{j_{2}}\|_{1}\geq 3.$
Now, whether $\|\bar{t}_{i_{1}}-\bar{t}_{j_{2}}\|_{\infty}$ equals $1$ or $2,$
the desired result is easy to see.

Since $V_{1}$ and $V_{2}$ are non-empty and $|V_{1}|+|V_{2}|=2k+2,$ it is easy
to see that $1\leq\min\\{|V_{1}|,|V_{2}|\\}\leq k+1.$ Hence, by using the
above arguments and interchanging the labels of $V_{1}$ and $V_{2}$ if
necessary, we have the desired result. ∎

##  5 Asymptotic Behavior of Betti Approximators

The intermediate results concerning the asymptotic behaviour of Betti
approximators from Section 3 are proved here. Often, some technical results
are needed. Their proofs are given either in Section 6 or the Appendix.

Using (3.4), (3.7), (3.8), and Lemma 4.12, we first make the following
observations.

######  Remark 5.1.

For $k=0,$ $S_{n,0}$ is the number of vertices in $\mathcal{K}(n;u).$ On the
other hand, for $k\geq 1,$ $S_{n,k}(u)$ is roughly the number of subgraphs in
$\mathcal{K}(n;u)$ which are isomorphic and $\|\cdot\|_{1}-$isometric to
$O_{k}.$ We say ‘roughly’ because $S_{n,k}(u)$ counts additional subgraphs at
the boundary of $\Gamma_{n}$ which cannot be part of $\mathcal{K}(n;u).$
Separately, and as remarked earlier in Section 3, note that $S_{n,k}(u)$ does
not require that these subgraphs be components themselves.

######  Remark 5.2.

For $k\geq 1,$ $N_{n,k}(u)$ overcounts (by a constant factor) the number of
subgraphs in $\mathcal{K}(n;u)$ that are isomorphic but not
$\|\cdot\|_{1}-$isometric to $O_{k}.$ The overcounting is due to the two
facts: (i) the same subgraph is counted for more than one $\bar{t},$ and (ii)
extra subgraphs are counted at the boundary of $\Gamma_{n}$ that cannot be
part of $\mathcal{K}(n;u)$. But this does not matter for us, since it will
only add a constant factor in the associated estimates.

######  Remark 5.3.

In the same spirit as in Remark 5.2, $L_{n,k}(u)$ overestimates the number of
subgraphs in $\mathcal{K}(n;u)$ that is isomorphic to a graph in
$\mathcal{P}_{k}.$ In particular, we note that $L_{n,0}(u)$ is at least twice
the number of edges in $\mathcal{K}(n;u).$

Separately, using (3.6) and Lemma 4.14, we note the following.

######  Remark 5.4.

For each $G\equiv(V,E)\in\mathcal{N}_{k},$ Lemma 4.14 gives a partition of $V$
with certain properties. It is not difficult to see that such a partition is
not unique. For convenience, however, we shall henceforth assume that each $G$
is uniquely associated with one such partition.

We are now ready to prove Lemma 3.5.

###### Proof of Lemma 3.5.

We prove each statement separately.

  * •

Arguments for Statement 1: Consider the $k=0$ case first. From Remark 5.1
above, the lower bound follows trivially. It remains to show the upper bound.
Note that a vertex in $\mathcal{K}(n;u)$ can either be isolated or not.
Separately, given a graph, recall that a connected component with $i$ vertices
must have at least $i-1$ edges within it. Therefore, the number of vertices in
a connected component, with at least two vertices, is bounded from above by
twice the number of edges in it. From these observations and Remark 5.3, the
upper bound is easy to see.

Now suppose that $1\leq k<d.$ For
$(\bar{t},\,\bar{\Omega})\in\mathbb{Z}^{d}\times\tbinom{\langle
d\rangle}{b_{k}},$ let $G_{\bar{t},\bar{\Omega}}$ be the geometric graph on
the vertex set
$\\{\bar{t}\pm\bar{e}_{\omega_{1}},\ldots,\bar{t}\pm\bar{e}_{\omega_{b_{k}}}\\}$
with respect to $\mathscr{B}_{\infty}(\cdot,\tfrac{1}{2}).$ Then, from (3.4),
we have

$S_{n,k}(u)=\sum_{(\bar{t},\,\bar{\Omega})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}}\mathds{1}[\bar{X}_{\bar{t},\bar{\Omega}}\geq
u\bar{\mathbf{1}}_{2b_{k}}]\;\mathds{1}[G_{\bar{t},\bar{\Omega}}\text{ forms a
component}]\\\\[8.61108pt]
+\sum_{(\bar{t},\,\bar{\Omega})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}}\mathds{1}[\bar{X}_{\bar{t},\bar{\Omega}}\geq
u\bar{\mathbf{1}}_{2b_{k}}]\;\mathds{1}[G_{\bar{t},\bar{\Omega}}\text{ does
not form a component}].$ (5.1)

Therefore, it follows from Remark 5.1 and the definition of
$\check{S}_{n,k}(u)$ that

$\check{S}_{n,k}(u)\leq\sum_{(\bar{t},\,\bar{\Omega})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}}\mathds{1}[\bar{X}_{\bar{t},\bar{\Omega}}\geq
u\bar{\mathbf{1}}_{2b_{k}}]\;\mathds{1}[G_{\bar{t},\bar{\Omega}}\text{ forms a
component}].$

From this, we get the lower bound.

With regards to the upper bound, first observe that

$\sum_{(\bar{t},\,\bar{\Omega})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}}\mathds{1}[\bar{X}_{\bar{t},\bar{\Omega}}\geq
u\bar{\mathbf{1}}_{2b_{k}}]\;\mathds{1}[G_{\bar{t},\bar{\Omega}}\text{ forms a
component}]\leq\check{S}_{n,k}(u)+D_{n,k}(u).$

On the other hand, from the definition of $\check{L}_{n,k}(u),$ we have

$\sum_{(\bar{t},\,\bar{\Omega})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}}\mathds{1}[\bar{X}_{\bar{t},\bar{\Omega}}\geq
u\bar{\mathbf{1}}_{2b_{k}}]\;\mathds{1}[G_{\bar{t},\bar{\Omega}}\text{ does
not form a component}]\leq\check{L}_{n,k}(u).$

From these observations and (5.1), the upper bound is easy to see. The desired
result follows.

  * •

Arguments for Statement 2: Consider the definition of $\check{N}_{n,k}(u),$
(3.7), Lemmas 4.13 and 4.11, and Remark 5.2. By the same argument used for
deriving the lower bound above, the desired result follows.

  * •

Arguments for Statement 3: From the definition of $\check{L}_{n,k}(u),$ (3.8),
and Remark 5.3, the desired result follows trivially.

This completes the proof. ∎

We now aim to prove Lemma 3.7. But, for that, we first need probability
estimates for the events associated with the indicators in (3.4), (3.7),
(3.8), and (3.9). Due to the stationarity assumption on field $X$ (see Section
1), it suffices to obtain these estimates for $\bar{t}=0.$ For the $k\geq 1$
case in (3.4) and (3.9), by additionally using the $\|\cdot\|_{1}-$isotropy
assumption on $X,$ it in fact follows that we only need to consider
$\bar{\Omega}=\langle b_{k}\rangle.$ The next result gives these bounds. Its
proof is in Section 6, p. 6, and uses Lemmas 2.4 and 2.5; the Savage condition
holds due to our assumptions in Table 1.

######  Lemma 5.5.

Let $\\{u_{n}\\}\in\mathbb{R}_{>0}^{\infty}$ be such that
$\lim_{n\to\infty}u_{n}=\infty.$ Then, the following claims are true.

  1. 1.

If $\Cr{a:r0Asm}$ holds, then $\left|\dfrac{\mathbb{P}\\{X_{\bar{0}}\geq
u_{n}\\}}{\tau_{0}u_{n}^{-2b_{0}}\exp[-a_{0}u_{n}^{2}]}-1\right|=O\left(\dfrac{1}{u_{n}^{2}}\right).$

  2. 2.

Suppose $1\leq k<d.$ If $\Cr{a:r0Asm}$ and $\Cr{a:r2Asm}$ hold, then
$\left|\dfrac{\mathbb{P}\\{\bar{X}_{\bar{0},\langle b_{k}\rangle}\geq
u_{n}\bar{\mathbf{1}}_{2b_{k}}\\}}{\left[\tau_{k}/\tbinom{d}{b_{k}}\right]u_{n}^{-2b_{k}}\exp[-a_{k}u_{n}^{2}]}-1\right|=O\left(\dfrac{1}{u_{n}^{2}}\right).$

  3. 3.

Suppose $1\leq k<d-1.$ If $\Cr{a:r0Asm},\Cr{a:r2Asm},$ and $\Cr{a:rqAsm}$
hold, and $G\in\mathcal{N}_{k},$ then

$\mathbb{P}\\{\bar{X}_{\bar{0},G}\geq
u_{n}\bar{\mathbf{1}}_{2b_{k}}\\}=O\left(u_{n}^{-2b_{k}}\exp[-\varrho_{k}\,u_{n}^{2}]\right).$

  4. 4.

If $\Cr{a:r0Asm}$ and $\Cr{a:r1Asm}$ hold, then

$\mathbb{P}\\{(X_{\bar{0}},X_{\bar{e}_{1}})\geq
u_{n}\bar{\mathbf{1}}_{2}\\}=O\left(u_{n}^{-(2b_{0}+1)}\exp[-\varphi_{0}\,u_{n}^{2}]\right).$

  5. 5.

Suppose $1\leq k<d.$ If $\Cr{a:r0Asm},\Cr{a:r1Asm},$ and $\Cr{a:ComC}(k)$
hold, then

$\mathbb{P}\\{(\bar{X}_{\bar{0},\langle k+1\rangle},X_{\bar{0}})\geq
u_{n}\bar{\mathbf{1}}_{2b_{k}+1}\\}=O\left(u_{n}^{-(2b_{k}+1)}\exp[-\varphi_{k}\,u_{n}^{2}]\right),$

  6. 6.

Suppose $0\leq k<d.$ If $\Cr{a:r0Asm},\Cr{a:r1Asm},$ $\Cr{a:r2LAsm},$ and
$\Cr{a:ComC}(k)$ hold, and $G\in\mathcal{P}_{k},$ then

$\mathbb{P}\\{\bar{X}_{\bar{0},G}\geq
u_{n}\bar{\mathbf{1}}_{|V|}\\}=O\left(u_{n}^{-(2b_{k}+1)}\exp[-\varphi_{k}\,u_{n}^{2}]\right),$

We are now ready to prove Lemma 3.7.

###### Proof of Lemma 3.7.

Each statement is proved individually.

  * •

Arguments for Statement 1: First consider the case $1\leq k<d.$ Using (3.4),
we have

$\mathbb{E}[S_{n,k}(u_{n})]=\sum_{(\bar{t},\,\bar{\Omega})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}}\mathbb{P}\\{\bar{X}_{\bar{t},\bar{\Omega}}\geq
u\bar{\mathbf{1}}_{2b_{k}}\\},$

where $\bar{X}_{\bar{t},\bar{\Omega}}$ is as in (3.5). For each
$(\bar{t},\,\bar{\Omega})\in\mathbb{Z}^{d}\times\tbinom{\langle
d\rangle}{b_{k}},$ note that the pairwise $\|\cdot\|_{1}-$distances between
the indices involved in the definition of $\bar{X}_{\bar{t},\bar{\Omega}}$ is
exactly $2.$ Consequently, using the fact that the field $X$ is both
stationary and $\|\cdot\|_{1}-$isotropic, it follows that

$\mathbb{E}[S_{n,k}(u_{n})]=(2n+1)^{d}\binom{d}{b_{k}}\mathbb{P}\\{\bar{X}_{\bar{0},\langle
b_{k}\rangle}\geq u_{n}\bar{\mathbf{1}}_{2b_{k}}\\}.$

From (1.4), we then have

$\frac{\mathbb{E}[S_{n,k}(u_{n})]}{\lambda_{n,k}(u_{n})}=\dfrac{\mathbb{P}\\{\bar{X}_{\bar{0},\langle
b_{k}\rangle}\geq
u_{n}\bar{\mathbf{1}}_{2b_{k}}\\}}{\left[\tau_{k}/\tbinom{d}{b_{k}}\right]u_{n}^{-2b_{k}}\exp[-a_{k}u_{n}^{2}]}.$
(5.2)

The desired result now follows from Lemma 5.5.2.

The case $k=0$ follows similarly using Lemma 5.5.1, except, no condition on
$\rho_{2}$ is needed here.

  * •

Arguments for Statement 2: The expectation bound is trivially true when $k=0$
or $d-1.$ Suppose that $1\leq k<d-1.$ From (3.7) and the fact that the field
$X$ is stationary,

$\mathbb{E}[N_{n,k}(u_{n})]=(2n+1)^{d}\sum_{G\in\mathcal{N}_{k}}\mathbb{P}\\{\bar{X}_{\bar{0},G}\geq
u_{n}\bar{\mathbf{1}}_{2b_{k}}\\}.$

Therefore, from (1.4),

$\frac{\mathbb{E}[N_{n,k}(u_{n})]}{\lambda_{n,k}(u_{n})}\leq\frac{|\mathcal{N}_{k}|\left[\sup_{G\in\mathcal{N}_{k}}\mathbb{P}\\{\bar{X}_{\bar{0},G}\geq
u_{n}\bar{\mathbf{1}}_{2k+2}\\}\right]}{\tau_{k}u_{n}^{-2b_{k}}\exp[-a_{k}u_{n}^{2}]}.$

Since $|\mathcal{N}_{k}|$ is finite, by invoking Lemma 5.5.3, the desired
bound follows.

It only remains to show that $\varrho_{k}>a_{k}$ for $1\leq k<d-1.$ But, from
(1.2) and (3.11),

$\varrho_{k}-a_{k}=\frac{(2b_{k}-1)(\rho_{2}-\rho_{3})(1-\rho_{3}+(b_{k}-1)(\rho_{2}-\rho_{3}))}{(1-\rho_{3}^{2}+2(b_{k}-1)(\rho_{2}-\rho_{3}^{2}))(1+(2b_{k}-1)\rho_{2})}>0,$

where the positivity follows since $0\leq\rho_{3}<\rho_{2}<1,$ which itself
holds on due to $\Cr{a:r0Asm},$ $\Cr{a:r2Asm},$ and $\Cr{a:rqAsm}.$ This
completes the proof.

  * •

Arguments for Statement 3: Using (3.8), Lemma 5.5.6, and similar arguments as
in the proof of Statement 2 above, the expectation bound is easy see. It only
remains to show $\varphi_{k}>a_{k}$ for $k\geq 0.$

Using (1.3), (1.2), and (3.12), note that

$\varphi_{k}-a_{k}=(1-2a_{k}\rho_{1})^{2}/[2(1-2a_{k}\rho_{1}^{2})].$ (5.3)

For the $k=0$ case, the expression on the right is positive due to
$\Cr{a:r0Asm}$ and $\Cr{a:r1Asm};$ for the $1\leq k<d$ case, it is positive
due to $\Cr{a:ComC}(k)$ and the facts that $\rho_{2}\geq 0$ and
$0\leq\rho_{1}<1,$ which itself hold due to $\Cr{a:r0Asm},$ $\Cr{a:r1Asm},$
and $\Cr{a:r2LAsm}.$ We are now done.

  * •

Arguments for Statement 4: The $k=0$ case is trivial. So, suppose that $1\leq
k<d.$ A simple observation here is that
$|\\{(\bar{t},\,\bar{\Omega})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}:\|\bar{t}\|_{\infty}=n\\}|\leq 2d(2n+1)^{d-1}.$ Further, from
Lemma 5.5.2,

$\dfrac{\mathbb{P}\\{\bar{X}_{\bar{0},\langle b_{k}\rangle}\geq
u_{n}\bar{\mathbf{1}}_{2b_{k}}\\}}{\left[\tau_{k}/\tbinom{d}{b_{k}}\right]u_{n}^{-2b_{k}}\exp[-a_{k}u_{n}^{2}]}=O\left(1+\frac{1}{u_{n}^{2}}\right)=O(1),$

where the latter holds since $u_{n}\to\infty.$ Arguing now as in the proof of
Statement 1 above, the desired result is easy to see.

This completes the proof. ∎

Our next objective is to establish Theorem 3.8 by making use of Theorem 2.9.
As mentioned earlier, the $k=0$ case of this result has been proved in [18,
Theorem 3.6]. That proof makes use of Lemma 3.4 there, which discusses several
covariance bounds concerning the indicators that add up to give $S_{n,0}(u);$
see (3.4) for the definition of the latter. Below we restate a few of these
covariance bounds in a form that is convenient to us. While these bounds have
been shown in [18], they also follow from our proof for Lemma 5.7 stated
below.

From now on, whenever appropriate, we shall write $\mathds{1}[X_{\bar{t}}\geq
u]$ as $\mathds{1}_{\bar{t}}(u).$

######  Lemma 5.6.

Let $\bar{t},\bar{t}^{\prime}\in\mathbb{Z}^{d}$ and
$\\{u_{n}\\}\in\mathbb{R}_{>0}^{\infty}$ be such that
$\lim_{n\to\infty}u_{n}=\infty.$ Let $a_{0}$ and $b_{0}$ be as in (1.3).
Suppose $\Cr{a:r0Asm},$ $\Cr{a:r1Asm},$ and $\Cr{a:r2LAsm}$ hold. Then, the
following statements are true.

  1. 1.

$\textnormal{Cov}[\mathds{1}_{\bar{t}}(u_{n}),\mathds{1}_{\bar{t}^{\prime}}(u_{n})]\geq
0$ for all $n\geq 0.$

  2. 2.

If $\|\bar{t}-\bar{t}^{\prime}\|_{1}=q\geq 1,$ then
$\textnormal{Cov}[\mathds{1}_{\bar{t}}(u_{n}),\mathds{1}_{\bar{t}^{\prime}}(u_{n})]=O\left(u_{n}^{-4b_{0}}\exp\left[\dfrac{-2a_{0}u_{n}^{2}}{1+2a_{0}\rho_{q}}\right]\right).$

  3. 3.

If $\|\bar{t}-\bar{t}^{\prime}\|_{1}=q\geq 1,$ then

$\textnormal{Cov}[\mathds{1}_{\bar{t}}(u_{n}),\mathds{1}_{\bar{t}^{\prime}}(u_{n})]=O\left(\rho_{q}u_{n}^{-(4b_{0}-2)}\exp\left[\dfrac{-2a_{0}u_{n}^{2}}{1+2a_{0}\rho_{q}}\right]\right)=O\left(\rho_{q}\exp\left[\dfrac{-2a_{0}u_{n}^{2}}{1+2a_{0}\rho_{q}}\right]\right).$

In each statement, the constants involved in the $O$ notation are independent
of both $\bar{t}$ and $\bar{t}^{\prime}.$

In order to handle the $1\leq k<d$ case in Theorem 3.8, our first aim is to
obtain similar covariance bounds for the indicators that sum up to
$S_{n,k}(u);$ the latter is as defined in (3.4). These bounds are stated next.

Henceforth, as and when convenient, we shall shorten
$\mathds{1}[\bar{X}_{\bar{t},\bar{\Omega}}\geq u\bar{\mathbf{1}}_{2b_{k}}]$ to
$\mathds{1}_{\bar{t},\bar{\Omega}}(u).$ Separately, keeping in mind that the
covariance sequence $\\{\rho_{q}\\}$ may not be monotonically decreasing, for
$(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})\in\mathbb{Z}^{d}\times\tbinom{\langle
d\rangle}{b_{k}},$ let

$\tilde{\rho}_{(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})}:=\max\left\\{\rho_{\|[\bar{t}+\alpha\bar{e}_{\omega}]-[\bar{t}^{\prime}+\alpha^{\prime}\bar{e}_{\omega^{\prime}}]\|_{1}}:\alpha,\alpha^{\prime}\in\\{-1,+1\\},\omega\in\bar{\Omega},\omega^{\prime}\in\bar{\Omega}^{\prime}\right\\}.$
(5.4)

The triangle inequality shows that, whenever
$\tilde{\rho}_{(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})}=\rho_{q},$

$\max\\{q-2,0\\}\leq\|\bar{t}-\bar{t}^{\prime}\|_{1}\leq q+2.$ (5.5)

From this, it immediately follows that there exists a $k-$dependent positive
constant ${\Cl[Const]{c:upBdRho}}_{,k}$ such that, for any
$(\bar{t},\,\bar{\Omega})\in\mathbb{Z}^{d}\times\tbinom{\langle
d\rangle}{b_{k}}$ and $q\geq 1,$

$|\\{(\bar{t}^{\prime},\bar{\Omega}^{\prime})\in\mathbb{Z}^{d}\times\tbinom{\langle
d\rangle}{b_{k}}:\tilde{\rho}_{(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})}=\rho_{q}\\}|\leq{\Cr{c:upBdRho}}_{,k}\;q^{d-1}.$
(5.6)

######  Lemma 5.7.

Fix $k$ such that $1\leq k<d.$ Let
$(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})\in\mathbb{Z}^{d}\times\tbinom{\langle
d\rangle}{b_{k}},$ and $\\{u_{n}\\}\in\mathbb{R}_{>0}^{\infty}$ be such that
$\lim_{n\to\infty}u_{n}=\infty.$ Let $a_{k}$ and $b_{k}$ be as in (1.2) and
let $\varphi_{k}$ be as in (3.12). Suppose
$\Cr{a:r0Asm},\Cr{a:r1Asm},\Cr{a:r2LAsm},$ and $\Cr{a:ComC}(k)$ hold. Then,
the following statements are true.

  1. 1.

$\textnormal{Cov}[\mathds{1}_{\bar{t},\bar{\Omega}}(u_{n}),\mathds{1}_{\bar{t}^{\prime},\bar{\Omega}^{\prime}}(u_{n})]\geq
0$ for all $n.$

  2. 2.

If $(\bar{t},\,\bar{\Omega})\neq(\bar{t}^{\prime},\bar{\Omega}^{\prime}),$
then

$\textnormal{Cov}[\mathds{1}_{\bar{t},\bar{\Omega}}(u_{n}),\mathds{1}_{\bar{t}^{\prime},\bar{\Omega}^{\prime}}(u_{n})]=O\left(u_{n}^{-(2b_{k}+1)}\exp[-\varphi_{k}u_{n}^{2}]\right).$

  3. 3.

If
$\tilde{\rho}_{(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})}=\rho_{q}$
with $q\geq 1,$ then

$\textnormal{Cov}[\mathds{1}_{\bar{t},\bar{\Omega}}(u_{n}),\mathds{1}_{\bar{t}^{\prime},\bar{\Omega}^{\prime}}(u_{n})]=O\left(u_{n}^{-4b_{k}}\exp\left[\frac{-2a_{k}u_{n}^{2}}{1+2a_{k}\rho_{q}}\right]\right).$

  4. 4.

If
$\tilde{\rho}_{(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})}=\rho_{q}$
with $q\geq 1,$ then

$\textnormal{Cov}[\mathds{1}_{\bar{t},\bar{\Omega}}(u_{n}),\mathds{1}_{\bar{t}^{\prime},\bar{\Omega}^{\prime}}(u_{n})]=O\left(\rho_{q}\;u_{n}^{-(4b_{k}-2)}\exp\left[\frac{-2a_{k}u_{n}^{2}}{1+2a_{k}\rho_{q}}\right]\right).$

In each statement, while the constants involved in the $O$ notation do depend
on $k,$ they are independent of both $(\bar{t},\,\bar{\Omega})$ and
$(\bar{t}^{\prime},\bar{\Omega}^{\prime}).$

We prove this result in Section 6, p. 6. Statements 1, 2, and 3 of this result
follow by an application of Lemmas 2.4 and 2.5; these ideas are multivariate
extensions of those discussed in the proof of [18, Lemma 3.4]. In contrast,
our proof of Statement 4 above is significantly different to the one used in
[18] to derive (the analogous version of) Lemma 5.6.3. There, given that the
setup is much simpler, the proof proceeds via first principles. In contrast,
here we first approximate the desired covariance by a definite integral and
then make use of Lemma A.4, which provides bounds on the integrand.

###### Proof of Theorem 3.8.

Because $\Cr{a:r0Asm},\Cr{a:r1Asm},$ $\Cr{a:ComC}(k),$ and $\Cr{a:r2LAsm}$
hold, both $1+(2b_{k}-1)\rho_{2}-2b_{k}\rho_{1}$ and $\rho_{1}$ lie in
$(0,1),$ while $\rho_{2}\in[0,1).$ Using this, it is easy to see that
$0<\vartheta_{k}<1,$ as desired.

It now remains to establish the total variation bounds. The $k=0$ case has
been proved in [18, Theorem 3.6]. We only deal with the $1\leq k<d$ case here.
So, fix one such $k.$

For any $n\geq 0,$ it is not difficult to see from (3.4), Theorems 2.9 and
2.11, and Lemma 5.7.1 that

$\displaystyle\|S_{n,k}(u_{n})-\textnormal{Poi}(\mathbb{E}[S_{n,k}(u_{n})])\|_{\textnormal{TV}}$
(5.7) $\displaystyle\leq$
$\displaystyle\frac{1-e^{-\lambda_{n,k}(u_{n})}}{\lambda_{n,k}(u_{n})}\Bigg{[}\sum_{(\bar{t},\,\bar{\Omega})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}}[\mathbb{E}[\mathds{1}_{\bar{t},\bar{\Omega}}(u_{n})]]^{2}+\sum_{\begin{subarray}{c}(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}},\\\
(\bar{t},\,\bar{\Omega})\neq(\bar{t}^{\prime},\bar{\Omega}^{\prime})\end{subarray}}\textnormal{Cov}[\mathds{1}_{\bar{t},\bar{\Omega}}(u_{n}),\mathds{1}_{\bar{t}^{\prime},\bar{\Omega}^{\prime}}(u_{n})]\Bigg{]}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\lambda_{n,k}(u_{n})}\Bigg{[}\sum_{(\bar{t},\,\bar{\Omega})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}}[\mathbb{E}[\mathds{1}_{\bar{t},\bar{\Omega}}(u_{n})]]^{2}+\sum_{\begin{subarray}{c}(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}},\\\
(\bar{t},\,\bar{\Omega})\neq(\bar{t}^{\prime},\bar{\Omega}^{\prime})\end{subarray}}\textnormal{Cov}[\mathds{1}_{\bar{t},\bar{\Omega}}(u_{n}),\mathds{1}_{\bar{t}^{\prime},\bar{\Omega}^{\prime}}(u_{n})]\Bigg{]},$

where the last relation follows since $1-e^{-x}\leq 1.$ Since $\Cr{a:r1Asm}$
and $\Cr{a:r2LAsm}$ imply $\Cr{a:r2Asm}$ and also because
$\vartheta_{k}/2b_{k}\in(0,1),$ the desired result clearly follows from the
following two claims:

  1. 1.

If $\Cr{a:r0Asm}$ and $\Cr{a:r2Asm}$ hold, then
$\dfrac{1}{\lambda_{n,k}(u_{n})}\sum_{(\bar{t},\,\bar{\Omega})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}}[\mathbb{E}[\mathds{1}_{\bar{t},\bar{\Omega}}(u_{n})]]^{2}=O\left(\dfrac{1}{n^{d}}\right).$

  2. 2.

If $\Cr{a:r0Asm},\Cr{a:r1Asm},\Cr{a:ComC}(k),\Cr{a:PoiG},$ and
$\Cr{a:r2LAsm},$ hold, then

$\displaystyle\frac{1}{\lambda_{n,k}(u_{n})}\sum_{\begin{subarray}{c}(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}\\\
(\bar{t},\,\bar{\Omega})\neq(\bar{t}^{\prime},\bar{\Omega}^{\prime})\end{subarray}}\textnormal{Cov}[\mathds{1}_{\bar{t},\bar{\Omega}}(u_{n}),\mathds{1}_{\bar{t}^{\prime},\bar{\Omega}^{\prime}}(u_{n})]$
$\displaystyle=$ $\displaystyle O\left(n^{-d\vartheta_{k}/(2b_{k})}[\log
n]^{-(1-\vartheta_{k})/2}+\frac{\log n}{n}\sum_{q=1}^{2dn}\rho_{q}\right).$

In the remainder of this proof, we establish the above bounds.

  * •

Arguments for Claim 1: We have

$\displaystyle\frac{1}{\lambda_{n,k}(u_{n})}\sum_{(\bar{t},\,\bar{\Omega})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}}[\mathbb{E}[\mathds{1}_{\bar{t},\bar{\Omega}}(u_{n})]]^{2}$
(5.8) $\displaystyle=$
$\displaystyle(2n+1)^{d}\tbinom{d}{b_{k}}[\mathbb{P}\\{\bar{X}_{\bar{0},\langle
b_{k}\rangle}\geq u_{n}\bar{\mathbf{1}}_{2b_{k}}\\}]^{2}/\lambda_{n,k}(u_{n})$
$\displaystyle=$
$\displaystyle\frac{\lambda_{n,k}(u_{n})}{(2n+1)^{d}\tbinom{d}{b_{k}}}\left[\frac{\mathbb{P}\\{\bar{X}_{\bar{0},\langle
b_{k}\rangle}\geq
u_{n}\bar{\mathbf{1}}_{2b_{k}}\\}}{\left[\tau_{k}/\tbinom{d}{b_{k}}\right]u_{n}^{-2b_{k}}\exp[-a_{k}u_{n}^{2}]}\right]^{2}$
$\displaystyle=$
$\displaystyle\frac{\lambda_{n,k}(u_{n})}{(2n+1)^{d}\tbinom{d}{b_{k}}}O\left(1+\frac{1}{u_{n}^{2}}+\frac{1}{u_{n}^{4}}\right),$

where the first relation is due to the stationarity and
$\|\cdot\|_{1}-$isotropy of the field $X,$ the second is because of (1.4),
while third one is a consequence of Lemma 5.5.2. The desired result now
follows from the fact that $u_{n}\to\infty$ and
$\lambda_{n,k}(u_{n})\to\lambda,$ a constant.

  * •

Arguments for Claim 2: Pick a $\delta$ satisfying

$0<(4a_{k}+1)\delta<\frac{2a_{k}\rho_{1}}{1+2a_{k}\rho_{1}}<1.$ (5.9)

While the effectiveness of this choice will become clear below, the choice
itself can be made because $\Cr{a:r0Asm},\Cr{a:r1Asm},$ and $\Cr{a:r2LAsm}$
ensure $\rho_{1}\in(0,1)$ and $\rho_{2}\in[0,1).$ For any
$(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}},$ it is easy to see from (5.5) that
$\tilde{\rho}_{(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})}=\rho_{q}$
for some $q\in\\{0,\ldots,2dn+2\\}.$ Keeping this in mind, we rewrite the
covariance sum in the claim as $T_{1}(n)+\ldots+T_{4}(n),$ where

$T_{1}(n):=\frac{1}{\lambda_{n,k}(u_{n})}\sum_{\begin{subarray}{c}(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}:\\\\[1.50694pt]
(\bar{t},\,\bar{\Omega})\,\neq\,(\bar{t}^{\prime},\bar{\Omega}^{\prime}),\;\tilde{\rho}_{(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})}\,=\,\rho_{0}\end{subarray}}\textnormal{Cov}[\mathds{1}_{\bar{t},\bar{\Omega}}(u_{n}),\mathds{1}_{\bar{t}^{\prime},\bar{\Omega}^{\prime}}(u_{n})],$
(5.10)
$T_{2}(n):=\frac{1}{\lambda_{n,k}(u_{n})}\sum_{q:\rho_{q}\geq\delta,\;q\neq
0}\sum_{\begin{subarray}{c}(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}:\\\\[1.50694pt]
\tilde{\rho}_{(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})}\,=\,\rho_{q}\end{subarray}}\textnormal{Cov}[\mathds{1}_{\bar{t},\bar{\Omega}}(u_{n}),\mathds{1}_{\bar{t}^{\prime},\bar{\Omega}^{\prime}}(u_{n})],$
(5.11)
$T_{3}(n):=\frac{1}{\lambda_{n,k}(u_{n})}\sum_{q:\rho_{q}<\delta,\;q\leq(2n+1)^{\delta}}\sum_{\begin{subarray}{c}(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}:\\\\[1.50694pt]
\tilde{\rho}_{(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})}\,=\,\rho_{q}\end{subarray}}\textnormal{Cov}[\mathds{1}_{\bar{t},\bar{\Omega}}(u_{n}),\mathds{1}_{\bar{t}^{\prime},\bar{\Omega}^{\prime}}(u_{n})],$
(5.12)

and

$T_{4}(n):=\frac{1}{\lambda_{n,k}(u_{n})}\sum_{\begin{subarray}{c}q:\rho_{q}<\delta,\\\\[1.50694pt]
(2n+1)^{\delta}<q\leq
2dn+2\end{subarray}}\sum_{\begin{subarray}{c}(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}:\\\\[1.50694pt]
\tilde{\rho}_{(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})}\,=\,\rho_{q}\end{subarray}}\textnormal{Cov}[\mathds{1}_{\bar{t},\bar{\Omega}}(u_{n}),\mathds{1}_{\bar{t}^{\prime},\bar{\Omega}^{\prime}}(u_{n})].$
(5.13)

We now sequentially bound each of these four terms. Since
$\lambda_{n,k}(u_{n})\to\lambda,$ a constant, we ignore the
$1/\lambda_{n,k}(u_{n})$ scaling factor, present in each term, in the
computations below.

Using the stationarity property of the field $X,$ the fact that
$\\{(\bar{t}^{\prime},\bar{\Omega}^{\prime}):\tilde{\rho}_{(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})}=\rho_{0}\\}$
is finite for each $(\bar{t},\,\bar{\Omega}),$ and Lemma 5.7.2, it follows
that

$T_{1}(n)=O\left((2n+1)^{d}u_{n}^{-(2b_{k}+1)}\exp[-\varphi_{k}u_{n}^{2}]\right).$
(5.14)

Hence, writing $\exp[-\varphi_{k}u_{n}^{2}]$ as
$[\tau_{k}(2n+1)^{d}u_{n}^{-2b_{k}}]^{-\varphi_{k}/a_{k}}[\lambda_{n,k}(u_{n})]^{\varphi_{k}/a_{k}}$
and, again, using the fact that $\lambda_{n,k}(u_{n})\to\lambda,$ it follows
from (5.3) that

$T_{1}(n)=O\left(n^{-d\vartheta_{k}/2b_{k}}u_{n}^{-(1-\vartheta_{k})}\right).$

Consider the second term. We have

$\displaystyle T_{2}(n)$ $\displaystyle=$ $\displaystyle
O\Biggl{(}\sum_{q:\rho_{q}\geq\delta,\;q\neq
0}\sum_{\begin{subarray}{c}(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}:\\\\[1.50694pt]
\tilde{\rho}_{(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})}\,=\,\rho_{q}\end{subarray}}u_{n}^{-4b_{k}}\exp\left[\frac{-2a_{k}u_{n}^{2}}{1+2a_{k}\rho_{q}}\right]\Biggr{)}$
$\displaystyle=$ $\displaystyle O\Biggl{(}\sum_{q:\rho_{q}\geq\delta,\;q\neq
0}\sum_{\begin{subarray}{c}(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})\in\Gamma_{n}\times\tbinom{\langle
d\rangle}{b_{k}}:\\\\[1.50694pt]
\tilde{\rho}_{(\bar{t},\,\bar{\Omega}),(\bar{t}^{\prime},\bar{\Omega}^{\prime})}\,=\,\rho_{q}\end{subarray}}u_{n}^{-4b_{k}}\exp\left[\frac{-2a_{k}u_{n}^{2}}{1+2a_{k}\rho_{1}}\right]\Biggr{)}$
$\displaystyle=$ $\displaystyle
O\left((2n+1)^{d}u_{n}^{-4b_{k}}\exp\left[\frac{-2a_{k}u_{n}^{2}}{1+2a_{k}\rho_{1}}\right]\sum_{q:\rho_{q}\geq\delta,\;q\neq
0}q^{d-1}\right)$ $\displaystyle=$ $\displaystyle
O\left((2n+1)^{d}u_{n}^{-4b_{k}}\exp\left[\frac{-2a_{k}u_{n}^{2}}{1+2a_{k}\rho_{1}}\right]\right),$

where the first relation follows from Lemma 5.7.3, the second one holds since
$\rho_{q}\leq\rho_{1}$ which itself holds due to $\Cr{a:r2LAsm},$ the truth of
the third one is on account of (5.6) and the fact that
$|\Gamma_{n}\times\tbinom{\langle d\rangle}{b_{k}}|=O((2n+1)^{d}),$ while the
last one follows because $\\{q:\rho_{q}\geq\delta\\}$ is a finite set which is
true due to $\Cr{a:PoiG}.$ As we did for $T_{1}(n),$ by expressing the
exponential term suitably so as to enable use of the fact that
$\lambda_{n,k}(u_{n})\to\lambda,$ we get

$T_{2}(n)=O\left(n^{-d(1-2a_{k}\rho_{1})/(1+2a_{k}\rho_{1})}\;u_{n}^{-8b_{k}a_{k}\rho_{1}/(1+2a_{k}\rho_{1})}\right).$