# Random Algebraic Graphs and
Their Convergence to Erdős-Rényi

Kiril Bangachev Guy Bresler Dept. of EECS, MIT<EMAIL_ADDRESS>of EECS,
MIT<EMAIL_ADDRESS>Supported by NSF Career Award CCF-1940205.

###### Abstract

We introduce a new probabilistic model of latent space graphs, which we call
random algebraic graphs. A (right) random algebraic graph is defined by a
group $\mathcal{\mathcal{G}}$ with a well-defined “uniform” distribution
$\mathcal{D}$ over it and a measurable function
$\sigma:\mathcal{G}\longrightarrow[0,1]$ with expectation $p$ over
${\mathcal{D}},$ satisfying $\sigma(\mathbf{g})=\sigma(\mathbf{g}^{-1}),$
which we call a “connection”. The random graph
$\mathsf{RAG}(n,\mathcal{G},p,\sigma)$ with vertex set $[n]$ is formed as
follows. First, $n$ independent latent vectors
$\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n}$ are sampled according to
${\mathcal{D}}.$ Then, every two vertices $i,j$ are connected with probability
$\sigma(\mathbf{x}_{i}\mathbf{x}_{j}^{-1}).$ The random algebraic model
captures random geometric graphs with latent space the unit sphere and the
hypercube, certain regimes of the stochastic block model, and random subgraphs
of Cayley graphs.

The main question of interest to the current paper is: for what parameters is
a random algebraic graph $\mathsf{RAG}(n,\mathcal{G},p,\sigma)$ statistically
and/or computationally distinguishable from an Erdős-Rényi random graph
$\mathsf{G}(n,p)$? Our results fall into two main categories.

  1. 1.

Geometric: We mostly focus on the hypercube case $\mathcal{G}=\\{\pm
1\\}^{d},$ where we use Fourier-analytic tools. We expect that some of the
insights will also transfer to the sphere. For hard thresholds, we match
[LMS+22a] for $p=\omega(1/n)$ and for connections that are
$\frac{1}{r\sqrt{d}}$-Lipschitz we extend the results of [LR21a] when
$d=\Omega(n\log n)$ to the non-monotone setting. We also study other
connections such as indicators of interval unions and low-degree polynomials.
One novel phenomenon is that when $\sigma$ is even, that is
$\sigma(\mathbf{x})=\sigma(-\mathbf{x}),$ indistinguishability from
$\mathsf{G}(n,p)$ occurs at $d=\Theta(n^{3/2})$ instead of $d=\Theta(n^{3}),$
the latter condition (up to problem-dependent hidden parameters) appearing in
most previous results.

  2. 2.

Algebraic: We provide evidence for the following exponential statistical-
computational gap. Consider any finite group $\mathcal{G}$ and let
$A\subseteq\mathcal{G}$ be a set of elements formed by including each set of
the form $\\{\mathbf{g},\mathbf{g}^{-1}\\}$ independently with probability
$p=1/2.$ Let $\Gamma_{n}(\mathcal{G},A)$ be the distribution of random graphs
formed by taking a uniformly random induced subgraph of size $n$ of the Cayley
graph $\Gamma(\mathcal{G},A).$ Then, $\Gamma_{n}(\mathcal{G},A)$ and
$\mathsf{G}(n,1/2)$ are statistically indistinguishable with high probability
over $A$ if and only if $\log|\mathcal{G}|\gtrsim n.$ However, low-degree
polynomial tests fail to distinguish $\Gamma_{n}(\mathcal{G},A)$ and
$\mathsf{G}(n,1/2)$ with high probability over $A$ when
$\log|\mathcal{G}|=\log^{\Omega(1)}n.$

En-route, we also obtain two novel, to the best of our knowledge,
probabilistic results that might be of independent interest. First, we give a
nearly sharp bound on the moments of elementary symmetric polynomials of
independent Rademacher variables in certain regimes (Theorem 1.7). Second, we
show that the difference of two independent $n\times n$ Wishart matrices with
parameter $d$ converges to an appropriately scaled $n\times n$ GOE matrix in
KL when $d=\omega(n^{2}).$ This is polynomially smaller than the
$d=\omega(n^{3})$ required for the convergence of a single $n\times n$ Wishart
matrix with parameter $d$ to a GOE matrix, occurring at $d=\omega(n^{3})$
[BDE+14, JL13].

###### Contents

  1. 1 Introduction
    1. 1.1 Prior Work
    2. 1.2 Our Results on The Hypercube
    3. 1.3 Random Algebraic Graphs
    4. 1.4 Our Results on Typical Cayley Graphs
  2. 2 Notation and Preliminaries
    1. 2.1 Information Theory
    2. 2.2 Boolean Fourier Analysis
    3. 2.3 Detection and Indistinguishability via Fourier Analysis
  3. 3 The Main Theorem On Indistinguishability Over The Hypercube
    1. 3.1 Symmetrizing The Autocorrelation Function
    2. 3.2 Splitting into Elementary Symmetric Polynomials
    3. 3.3 Moments of Elementary Symmetric Polynomials
    4. 3.4 Putting It All Together
  4. 4 Applications of the Main Theorem
    1. 4.1 Symmetric Connections
    2. 4.2 Transformations of Symmetric Connections
    3. 4.3 Typical Indicator Connections
  5. 5 Indistinguishability of Typical Random Algebraic Graphs
  6. 6 Detection via Signed Triangle Count over the Hypercube
    1. 6.1 Detection for Symmetric Connections
    2. 6.2 The Doom Of Signed Triangles: Fourier-Paired Connections
  7. 7 Detection for Typical Indicator Connections
    1. 7.1 Signed Subgraph Counts
    2. 7.2 Low Degree Polynomials
    3. 7.3 Statistical Detection
  8. 8 Discussion and Future Directions
    1. 8.1 On The Indistinguishability Argument of Liu and Racz
    2. 8.2 Groups Beyond the Hypercube
    3. 8.3 The Statistical-Computational Gap
    4. 8.4 Boolean Fourier Analysis and Probability
  9. A Variance of the Signed Triangle Statistic
  10. B Fourier Weights on Level d
  11. C Boolean Functions Without Low-Degree and High-Degree Terms
  12. D Further Computations of Fourier Coefficients
    1. D.1 The Case of Symmetric Thresholds
    2. D.2 Interval Unions
  13. E Distributions of Cayley Graph Generators
  14. F Signed Four-Cycles on Probabilistic Latent Space Graphs

##  1 Introduction

Latent space random graphs are a family of random graph models in which edge-
formation depends on hidden (latent) vectors associated to nodes. One of many
examples of latent space graphs—appearing in [SAC19], for example—is that of
social networks, which form based on unobserved features (such as age,
occupation, geographic location, and others). One reason these models are
studied in the literature is that, unlike the more common Erdős-Rényi random
graphs, latent space graphs capture and explain real-world phenomena such as
“the friend of my friend is also (likely) a friend of mine” [SAC19].

A mathematical model that captures this structure is given by a probability
distribution ${\mathcal{D}}$ over some latent space $\Omega,$ an integer $n$,
and a connection function $\sigma:\Omega\times\Omega\longrightarrow[0,1]$ such
that $\sigma(\mathbf{x},\mathbf{y})=\sigma(\mathbf{y},\mathbf{x})$ a.s. with
respect to ${\mathcal{D}}.$ Denote
$p={\mathbf{E}}_{\mathbf{x},\mathbf{y}\sim_{iid}{\mathcal{D}}}[\sigma(\mathbf{x},\mathbf{y})]\in[0,1].$
The probabilistic latent space graph
$\mathsf{PLSG}(n,\Omega,\mathcal{D},\sigma,p)$ is defined as follows [LR21a].
For an adjacency matrix $\mathbf{A}=(\mathbf{A}_{i,j})_{i,j\in[n]},$

$\displaystyle{\mathbf{P}}(G=\mathbf{A})={\mathbf{E}}_{\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n}\sim_{iid}{\mathcal{D}}}\Bigg{[}\prod_{1\leq
i<j\leq
n}\sigma(\mathbf{x}_{i},\mathbf{x}_{j})^{\mathbf{A}_{i,j}}(1-\sigma(\mathbf{x}_{i},\mathbf{x}_{j}))^{1-\mathbf{A}_{i,j}}\Bigg{]}.$
(1)

In words, for each node $i\in[n]=\\{1,2,\ldots,n\\},$ an independent latent
vector $\mathbf{x}_{i}$ is drawn from $\Omega$ according to ${\mathcal{D}}$
and then for each pair of vertices $i$ and $j$ an edge is drawn independently
with probability $\sigma(\mathbf{x}_{i},\mathbf{x}_{j}).$

Note that if $\sigma$ is equal to $p$ a.s., this is just the Erdős-Rényi
distribution $\mathsf{G}(n,p).$ More interesting examples occur when there is
richer structure in $(\Omega,\mathcal{D},\sigma).$

The focus of this paper is the case when $\Omega$ is a group and $\sigma$ is
“compatible” with the group structure as in Definition 1.12. Before delving
into this novel algebraic setting, we provide some context and motivation for
our work by describing the setting with a geometric structure, which is widely
studied in the literature.

Suppose that $\Omega$ is a metric space (most commonly
$\Omega\subseteq\mathbb{R}^{d}$ with the induced $\|\cdot\|_{2}$ metric) and
$\sigma(\mathbf{x},\mathbf{y})$ depends only on the distance between
$\mathbf{x}$ and $\mathbf{y}.$ Such graphs are called random geometric graphs
and we write $\mathsf{RGG}$ instead of $\mathsf{PLSG}.$ In practice, random
geometric graphs have found applications in wireless networks [Hae12],
consensus dynamics [ES16], and protein-protein interactions [HRP08] among
others (see [Pen03, DC22] for more applications). On the more theoretical
side, random geometric graphs are, by construction, random graph models with
correlated edges which provide an interesting and fruitful parallel theory to
the better understood Erdős-Rényi model. Khot, Tulsiani, and Worah use random
geometric graphs on the sphere to provide approximation lower-bounds for
constraint satisfaction problems [KTW14], and Liu et al. recently showed that
random geometric graphs are high-dimensional expanders in certain regimes
[LMS+22]. Finally, the study of random geometric graphs has catalyzed the
development of other areas in probability such as the convergence of Wishart
matrices to GOE matrices [BG15, BDE+14, BBH21], which in turn has applications
such as average-case reductions between statistical problems [BB19].

Starting with [DGL+11, BDE+14], the high-dimensional setting (in which
$\Omega\subseteq\mathbb{R}^{d}$ and $d$ grows with $n$) has gained
considerable attention in recent years [BBH21, LR21a, LMS+22a, LMS+22, EM20,
EMP22, RR19, LR21, BBN20, BBH22]. The overarching direction of study in most
of these papers and also our current work is based on the following
observation, first made in [DGL+11]. When $d\longrightarrow+\infty$ for a
fixed $n,$ random geometric graphs typically lose their geometric structure
and become indistinguishable from Erdős-Rényi graphs of the same expected
density. This motivates the following question. How large does the dimension
$d$ need to be so that edges become independent?

More concretely, we view each of $\Omega,{\mathcal{D}},p,\sigma$ as an
implicit sequence indexed by $n$ and take $n\longrightarrow+\infty.$ This
gives rise to the following hypothesis testing problem for latent space
graphs:

$H_{0}:G\sim\mathsf{G}(n,p)\quad\text{versus}\quad
H_{1}:G\sim\mathsf{PLSG}(n,\Omega,\mathcal{D},\sigma,p).$ (2)

Associated to these hypotheses are (at least) two different questions:

  1. 1.

Statistical: First, when is there a consistent test? To this end, we aim to
characterize the parameter regimes in which the total variation between the
two distributions tends to zero or instead to one.

  2. 2.

Computational: Second, we can ask for a computationally efficient test. In
particular, when does there exist a polynomial-time test solving Eq. 2 with
high probability?

The literature has been, thus far, predominantly interested in geometric
models for which there has been no evidence that the answers to the
statistical and computational question are different. In particular, an
efficient test (counting signed subgraphs, which we will see in Section 6)
always matches or nearly matches the statistical threshold. In Section 7, we
give an example of a model with evidence of an _exponential_ gap between the
statistical and computational detection thresholds. Evidence for the gap is
provided in the increasingly popular framework of low-degree polynomial tests
(see [SW22], for example).

To evince this gap (as well as numerous other new phenomena depending on the
choice of $\sigma,$ see Section 1.2), we first focus on the case of the
Boolean hypercube111Throughout the entire paper, when we say hypercube, we
mean the Boolean hypercube $\\{\pm 1\\}^{d}$ rather than $[0,1]^{d}.$ This
distinction is very important as $[0,1]^{d}$ with its
$\left\lVert\cdot\right\rVert_{2}$ metric is not a homogeneous metric space,
which makes its behaviour substantially different from the behaviour of the
unit sphere and Boolean hypercube. Specifically, recent work [EAG+20] suggests
that random geometric graphs over $[0,1]^{d}$ do not necessarily converge to
Erdős-Rényi ., $\Omega=\\{\pm 1\\}^{d}\subseteq\mathbb{R}^{d}.$ Most previous
papers in the high-dimensional setting study the unit sphere or Gauss space.
The advantage of the hypercube model is that it possesses a very simple
algebraic structure — it is a product of $d$ groups of order 2 — in addition
to its geometric structure. The underlying group structure facilitates the use
of Fourier-analytic tools which lead to our results for much more general
connections $\sigma$ than previously considered.

Our results for the hypercube motivate us to analyze more general latent space
graphs for which $\Omega$ is a group. We call such graphs, defined in Section
1.3, random algebraic graphs. It turns out that a natural condition in this
setting is that $\sigma(\mathbf{x},\mathbf{y})$ depend only on
$\mathbf{x}\mathbf{y}^{-1}$ (or, alternatively, on
$\mathbf{x}^{-1}\mathbf{y}$). As we will see in Section 1.3, random algebraic
graphs turn out to be extremely expressive.

Figure 1: Different probabilistic latent space graph models depending on the
underlying structure of $\Omega.$ Denoted are the sections in the introduction
discussing the respective models.

The hypercube model can be viewed as a bridge between random algebraic graphs
and random geometric graphs. Of course, one needs to be careful when
interpreting results for the hypercube model since they can have their origin
both in the underlying geometry or underlying algebra. In Section 8, we
discuss the dependence of our results on geometry and algebra.

###  1.1 Prior Work

##### 1\. Hard Thresholds on The Unit Sphere and Gauss Space.

A majority of the papers on high-dimensional random geometric graphs deal with
hard thresholds on the unit sphere: the latent space is
$\Omega=\mathbb{S}^{d-1}$ and ${\mathcal{D}}$ is the uniform distribution
$\mathsf{Unif}$ over it. The connection $\sigma$ is given by
${\mathbf{T}}_{p}(\mathbf{x},\mathbf{y}):=\mathds{1}[\langle\mathbf{x},\mathbf{y}\rangle\geq\tau_{p,d}],$
where $\tau_{p,d}$ is chosen so that
${\mathbf{E}}[{\mathbf{T}}_{p,d}(\mathbf{x},\mathbf{y})]=p.$ For example,
$\tau_{1/2,d}=0.$ In [DGL+11], the authors initiated this line of work by
showing that when $d=\exp(\Omega(n^{2})),$ the two graph models are
indistinguishable. Bubeck et. al. make an exponential improvement to
$d={\omega}(n^{3})$ in [BDE+14]. Implicitly, the authors of [BDE+14] also
showed that the signed-triangle count statistic (which can be computed in
polynomial time) distinguishes $\mathsf{G}(n,p)$ and
$\mathsf{RGG}(n,\mathbb{S}^{d-1},\mathsf{Unif},p,{\mathbf{T}}_{p})$ when
$d=\tilde{O}(n^{3}p^{3})$ (explicitly, the calculation appears in [LMS+22a],
for example). It is believed that the the signed triangle statistic gives the
tight bound.

######  Conjecture 1.1 (Implicit in [BDE+14, BBN20, LMS+22a] and others).

${\mathsf{TV}}\Big{(}\mathsf{G}(n,p),\mathsf{RGG}(n,\mathbb{S}^{d-1},\mathsf{Unif},p,{\mathbf{T}}_{p})\Big{)}=o_{n}(1)$

when $d=\tilde{\Omega}(n^{3}p^{3})$ for $p=\Omega(\frac{1}{n}).$

The current progress towards this conjecture is the following. In the sparse
regime, when $p=\Theta(\frac{1}{n}),$ Liu et. al. resolve the conjecture in
[LMS+22a] by showing indistinguishability when $d=\Omega(\log^{36}n).$ When
$p\leq\frac{1}{2}$ and $p=\omega(\frac{1}{n}),$ the same paper shows that
${\mathsf{TV}}\Big{(}\mathsf{G}(n,p),\mathsf{RGG}(n,\mathbb{S}^{d-1},\mathsf{Unif},p,{\mathbf{T}}_{p})\Big{)}=o(1)$
holds when $d=\tilde{\Omega}(n^{3}p^{2}),$ missing a factor $p$ relative to
1.1.

Several papers, including [BDE+14], also study the related model when
$(\mathbb{S}^{d-1},\mathsf{Unif})$ is replaced
by$(\mathbb{R}^{d},\mathcal{N}(0,I_{d})^{\otimes n}).$ The two models are
nearly equivalent since if $\mathbf{x}^{\prime}\sim\mathcal{N}(0,I_{d}),$ then
$\mathbf{x}^{\prime}\times\left\lVert\mathbf{x}^{\prime}\right\rVert^{-1}_{2}\sim\mathsf{Unif}(\mathbb{S}^{d-1})$
and $\left\lVert\mathbf{x}^{\prime}\right\rVert^{2}_{2}$ is extremely well
concentrated around $d.$ We will say more about the significance of the Gauss
space model when discussing Wishart matrices momentarily.

##### 2\. Wishart Matrices.

For $X\sim\mathcal{N}(0,I_{d})^{\otimes n}\in\mathbb{R}^{n\times d},$ denote
by $\mathcal{W}(n,d),$ the law of the Wishart matrix $XX^{T}.$ In [BDE+14],
the authors prove and use the following result. A GOE matrix $M(n)$ is a
symmetric $n\times n$ matrix with random Gaussian entries, which are
independent on the main diagonal and above. The variance of each entry on the
main diagonal is $2$ and above the diagonal it is 1.

######  Theorem 1.2 ([BDE+14, JL13]).

When $d=\omega(n^{3}),$
$\displaystyle{\mathsf{TV}}\Big{(}\mathcal{W}(n,d),\sqrt{d}M(n)+I_{n}\Big{)}=o(1).$

This result shows that when $d$ is sufficiently large, $\mathcal{W}(n,d)$ is,
in total variation, a Gaussian matrix with i.i.d. entries. In the context of
random geometric graphs, this implies that inner products of latent vectors
are independent (in total variation) and, thus, the corresponding random
geometric graph has independent edges. The result Theorem 1.2 has been
generalized in several ways since. In [BG15], the authors obtain similar
results when the Gaussian density used in the construction of the Wishart
ensemble is replaced with a log-concave density. In [RR19], the authors show
that the transition between a Wishart ensemble and GOE is “smooth” by
calculating ${\mathsf{TV}}\Big{(}\mathcal{W}(n,d),\sqrt{d}M(n)+I_{n}\Big{)}$
when $\lim_{n\longrightarrow+\infty}d/n^{3}=c$ for a fixed constant $c.$
Finally, in [BBH21], the authors consider the convergence of a Wishart matrix
with hidden entries to a GOE with hidden entries. They consider both
structured and random “masks” hiding the entries. A special case of one of
their results for bipartite masks, which we will use later on, is the
following. Let $\mathcal{M}$ be an $n\times n$ matrix split into four
$\frac{n}{2}\times\frac{n}{2}$ blocks, where the upper-left and lower-right
ones contain only zeros and lower-left and upper-right contain only ones. Let
$\odot$ be the usual Schur (entrywise) product.

######  Theorem 1.3 ([BBH21]).

When $d={\omega}(n^{2}),$
$\displaystyle{\mathsf{TV}}\Big{(}\mathcal{M}\odot\mathcal{W}(n,d),\mathcal{M}\odot(\sqrt{d}M(n)+I_{n})\Big{)}=o_{n}(1).$

We also mention that Ch’etelat and Wells establish a sequence of phase
transitions of the density of $\mathcal{W}$ when $n^{K+3}=\omega(d^{K+1})$ for
all $K\in\mathbb{N}$ [CW17].

##### 3\. Soft Thresholds.

A line of work by Liu and Racz [LR21, LR21a] studies a soft threshold model.
In it, edges are random rather than deterministic functions of
$\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle,$ which corresponds to $\sigma$
taking other values than just $0$ and $1.$ In [LR21], the connection of
interest is given as a convex combination between pure noise $\sigma\equiv p,$
and ${\mathbf{T}}_{p},$ namely
$\phi_{q}(\mathbf{x},\mathbf{y})=(1-q)p+q{\mathbf{T}}_{p}(\mathbf{x},\mathbf{y})$
for some $q\in[0,1].$ In [LR21a], on the other hand, the authors consider
smooth monotone connections formed as follows. Take
$(\Omega,{\mathcal{D}})=(\mathbb{R}^{d},\mathcal{N}(0,I_{d})).$ Suppose that
$f$ is a $C_{2}$ $\alpha$-Lipschitz density corresponding to a zero-mean
distribution over $\mathbb{R}.$ Let $F$ be the corresponding CDF. Let
$\sigma_{f}(\mathbf{x},\mathbf{y}):=F\big{(}\frac{\langle\mathbf{x},\mathbf{y}\rangle-\mu_{p,d,r}}{r\sqrt{d}}\big{)},$
where $r\geq 1$ and $\mu_{p,d,r}$ is chosen so that
${\mathbf{E}}[\sigma_{f}(\mathbf{x},\mathbf{y})]=p.$ The fact that $f$ is
$\alpha$-Lipschitz implies that $\sigma_{f}$ is
$O_{\alpha}(\frac{1}{r\sqrt{d}})$-Lipschitz when viewed as a function of
$\langle\mathbf{x},\mathbf{y}\rangle$ (this follows directly from [LR21a,
Lemma 2.6.]). The main result is the following.

######  Theorem 1.4 ([LR21a]).

Let $\mathsf{RGG}(n,\mathbb{R}^{d},\mathcal{N}(0,I_{d}),p,\sigma_{f})$ be
defined as above.
1) If $d=\omega_{p,\alpha}(\frac{n^{3}}{r^{4}}),$ then

${\mathsf{TV}}\Big{(}\mathsf{G}(n,p),\mathsf{RGG}(n,\mathbb{R}^{d},\mathcal{N}(0,I_{d}),p,\sigma_{f})\Big{)}=o(1).$

2) If $d=o_{p,\alpha}(\frac{n^{3}}{r^{6}})$ and, additionally,
$d/\log^{2}d=\omega(r^{6})$ or $r/\log^{2}(r)=\omega(d^{1/6}),$ then

${\mathsf{TV}}\Big{(}\mathsf{G}(n,p),\mathsf{RGG}(n,\mathbb{R}^{d},\mathcal{N}(0,I_{d}),p,\sigma_{f})\Big{)}=1-o(1).$

The authors conjecture that the lower bound 2), which is derived via the
signed triangle statistic, is tight [LR21a]. They derive their upper bounds in
1) using the following general claim on latent space random graphs. This claim
is the starting point for the indistinguishability results in the current
paper.

######  Claim 1.5 ([LR21a]).

Let $p,q\in[0,1]$ be two not-necessarily equal probabilities. Consider the
graph $\mathsf{PLSG}(n,\Omega,{\mathcal{D}},\sigma,q)$ for some
$n,\Omega,{\mathcal{D}},\sigma,q.$ Define

$\gamma_{p}(\mathbf{x},\mathbf{y})={\mathbf{E}}_{\mathbf{z}\sim{\mathcal{D}}}\bigg{[}(\sigma(\mathbf{x},\mathbf{z})-p)(\sigma(\mathbf{z},\mathbf{y})-p)\bigg{]}.$
(3)

Then,

${\mathsf{KL}}\Big{(}\mathsf{PLSG}(n,\Omega,{\mathcal{D}},\sigma,q)\|\mathsf{G}(n,p)\Big{)}\leq\sum_{k=0}^{n-1}\log{\mathbf{E}}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}\times\mathcal{D}}\bigg{[}\Big{(}1+\frac{\gamma_{p}(\mathbf{x},\mathbf{y})}{p(1-p)}\Big{)}^{k}\bigg{]}.$

Typically, we take $p=q.$ We state the result in this more general form for
the purely technical reason that in Section 5 we will need it for
$q=p(1+\epsilon),$ where $\epsilon$ is exponentially smaller than $p.$

In light of Pinsker’s inequlity (see Theorem 2.2), showing that the KL-
divergence is of order $o(1)$ implies that the total variation is also of
order $o(1).$ Expanding the expression above, we obtain

${\mathbf{E}}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}\times\mathcal{D}}\Big{[}\Big{(}1+\frac{\gamma_{p}(\mathbf{x},\mathbf{y})}{p(1-p)}\Big{)}^{k}\Big{]}=\sum_{t=0}^{k}\binom{k}{t}\frac{{\mathbf{E}}[\gamma_{p}^{t}]}{p^{t}(1-p)^{t}}.$
(4)

Thus, 1.5 reduces the task of proving indistinguishability bounds to bounding
moments of $\gamma_{p}.$ In [LR21a], the authors achieve this via a wide range
of tools in Gaussian analysis. Our approach is quite different and it relies
on interpreting $\gamma_{p}$ as an autocorrelation function when $\Omega$ has
a group-theoretic structure.

Unfortunately, as noted by [LR21a], the claim is likely not tight. In Section
8.1, we demonstrate new instances in which (and reasons why) it is not tight,
which hopefully will shed light on how to improve 1.5. Improving the claim has
the potential to resolve several open problems such as 1.1 and the gap in
Theorem 1.4.

##### 4\. Other Random Geometric Graphs.

Several other random geometric graph models have been studied recently as
well. For example, [BBH22, EM20] consider the hard thresholds model for
anisotropic Gaussian vectors. Together, the two papers prove a tight condition
on the vector of eigenvalues of the covariance matrix under which the total
variation is of order $o(1).$

###  1.2 Our Results on The Hypercube

There is a large gap in the literature, with all prior works focusing on
connections $\sigma$ with the following two properties:

  1. 1.

Monotonicity: Monotonicity of
$\langle\mathbf{x},\mathbf{y}\rangle\longrightarrow\sigma(\langle\mathbf{x},\mathbf{y}\rangle)$
is a natural assumption which can be interpreted as closer/more aligned
vectors are more likely to form a connection. Nevertheless, many interesting
choices of $\sigma$ are not monotone. For example, connections could be formed
when vectors are instead weakly correlated, corresponding to the non-monotone
$\sigma(\mathbf{x},\mathbf{y})=\mathds{1}[|\langle\mathbf{x},\mathbf{y}\rangle|\leq\delta]$
for some $\delta.$ As we will see in Section 4.1, the underlying symmetry
around $0,$ i.e.,
$\sigma(\mathbf{x},\mathbf{y})=\sigma(\mathbf{x},-\mathbf{y})$ leads to a
different indistinguishability rate.

  2. 2.

Symmetry: Connections $\sigma(\mathbf{x},\mathbf{y})$ depending only on
$\langle\mathbf{x},\mathbf{y}\rangle$ are symmetric with respect to
permutations of coordinates. However, in some interesting examples different
coordinates can influence the connection in qualitatively different ways. For
example, suppose that the latent vectors correspond to characteristics of
people and edges in the graph to friendships among the set of people.
Similarity in some characteristics—such as geographical location—can make
people more likely to form a friendship, but others—such as competition for
scarce resources—can make them less likely to become friends due to
competitiveness. In Section 4.2 we use a simple mathematical model of such
connections, which again leads to different indistinguishability rates.

Theorem 3.1 in the current paper makes a step towards filling this gap. It
addresses a large family of probabilistic latent space graphs over the
hypercube $\Omega=\\{\pm 1\\}^{d}$ with the uniform measure
${\mathcal{D}}=\mathsf{Unif}$ for which neither monotonicity nor symmetry
holds. We remark that because our proofs are based on Fourier-analytic tools,
which have generalizations to products of abelian groups and tori, our results
likely hold in greater generality. In the interest of obtaining simple and
interpretable results, we do not pursue this here.

The main insight is that over the hypercube, Fourier-analytic tools facilitate
the analysis of connections depending on the coordinate-wise (group-theoretic)
product $(\mathbf{x},\mathbf{y})\longrightarrow\mathbf{x}\mathbf{y}\in\\{\pm
1\\}^{d}.$ This setup is strictly more general than the setting of inner
products since
$\sum_{i=1}^{d}(\mathbf{x}\mathbf{y})_{i}=\langle\mathbf{x},\mathbf{y}\rangle.$
When $\sigma$ only depends on $\mathbf{x}\mathbf{y},$ we use the notation
$\mathsf{RAG}$ (standing for random algebraic graph, see Definition 1.12)
instead of $\mathsf{PLSG}.$ Theorem 3.1 yields indistinguishability rates
depending on the largest magnitude of Fourier coefficients on each level (see
Section 2.2 for preliminaries on Boolean Fourier analysis). Informally, we
have:

######  Theorem 1.6 (Informal Theorem 3.1).

Suppose that $d=\Omega(n),$ $\sigma:\\{\pm 1\\}^{d}\longrightarrow[0,1]$ has
expectation $p,$ and $m\in\mathbb{N}$ is a constant. Let
$\sigma=\sum_{S\subseteq[d]}\widehat{\sigma}(S)\omega_{S}$. For $1\leq i\leq
d,$ let
$B_{i}=\max\big{\\{}|\widehat{\sigma}(S)|\binom{d}{i}^{1/2}:|S|=i\big{\\}}$.
Let

$C_{m}=\sum_{i=m+1}^{d/2en}B_{i}^{2}+\sum_{i=d-\frac{d}{2en}}^{d-m-1}B_{i}^{2}\quad\text{and}\quad
D=\sum_{\frac{d}{2en}\leq j\leq d-\frac{d}{2en}}B_{i}^{2}.$

If $C_{m},B_{u}^{2},B_{d-u}^{2}\leq p(1-p)$ for $0\leq u\leq m,$ then

$\displaystyle{\mathsf{KL}}\Big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma)\|\mathsf{G}(n,p)\Big{)}$
$\displaystyle\qquad\qquad=O\Bigg{(}\frac{n^{3}}{p^{2}(1-p)^{2}}\times\left(\sum_{i=1}^{m}\frac{B_{i}^{4}}{d^{i}}+\sum_{i=d-m}^{d}\frac{B_{i}^{4}}{d^{i}}+\frac{C^{2}_{m}}{{d}^{m+1}}+{D^{2}}\times\exp\left(-\frac{d}{2en}\right)\right)\Bigg{)}.$

Qualitatively, the ${\mathsf{KL}}$ divergence is small whenever all Fourier
coefficients of $\sigma$ are small. In Remark 6.6, we show the converse – a
single large Fourier coefficient makes the ${\mathsf{KL}}$ divergence large.

In the beginning of Section 3, we summarize the four main steps in our proof
of Theorem 1.6 before we fill in all the technical details. Here, we highlight
the following inequality we derive which is crucial to the proof. Its utility
comes into play as we derive an upper bound of the desired ${\mathsf{KL}}$
divergence via the moments of a symmetric function. Symmetric functions over
the hypercube are weighted sums of elementary symmetric polynomials.

######  Theorem 1.7 (Theorem 3.5).

Let $d\in\mathbb{N}.$ Consider the elementary symmetric polynomial
$e_{s}:\mathbb{R}^{d}\longrightarrow\mathbb{R}^{d}$ given by
$e_{s}(\mathbf{x})=\sum_{S\subseteq[d]\;:\;|S|=s}\prod_{i\in S}x_{i}.$ If
$t\in\mathbb{N}$ is such that $\frac{d}{2et}<s<d-\frac{d}{2et},$ then

$\binom{d}{s}\exp\Big{(}-\ln
2\times\frac{d}{t}\Big{)}\leq{\mathbf{E}}_{\mathbf{x}\sim\mathsf{Unif}(\\{\pm
1\\}^{d})}\big{[}|e_{s}(\mathbf{x})|^{t}\big{]}^{1/t}\leq\binom{d}{s}\exp\Big{(}-\frac{d}{2et}\Big{)}.$

We have not tried to optimize the constants in the exponent. The upper bound
also holds for other distributions such as uniform on the sphere and Gaussian
when $s<{d}/{2}.$

We now describe some applications of Theorem 1.6 to various choices of
$\sigma$. While the claim of the theorem is rather long, it turns out to be
relatively simple to apply. We organize our results based on the degree of
symmetry in the respective connections. Note that in the symmetric case over
$\\{\pm 1\\}^{d},$
$\sigma(\mathbf{x},\mathbf{y})=\sigma(\mathbf{x}\mathbf{y})$ only depends on
$\sum_{i=1}^{d}x_{i}y_{i}=\langle\mathbf{x},\mathbf{y}\rangle$ and this is the
usual inner-product model.

####  1.2.1 Symmetric Connections

Most previous work on indistinguishability focuses on monotone connections and
proves a necessary condition of the form $d=\tilde{\Omega}(n^{3})$ (with
hidden constants, depending on $p,$ Lipschitzness, etc). We show that even
some of the simplest instances of non-monotone, but still symmetric,
connections violate this trend.

######  Theorem 1.8 (Informal, Corollaries 4.10, 4.5 and 4.14).

If $\sigma$ is symmetric and even (i.e.,
$\sigma(\mathbf{g})=\sigma(-\mathbf{g})$), then
${\mathsf{TV}}\big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma),\mathsf{G}(n,p)\big{)}=o(1),$ whenever
$d=\tilde{\Omega}(n^{3/2})$.

The reason why this holds is that odd Fourier levels of $\sigma$ vanish for
even connections (so, in particular $B_{1}=0$ in Theorem 1.6). We generalize
this result with the following conjecture, which, unfortunately, does not
follow from our Theorem 3.1 for $m>3$ as the latter only applies to the regime
$d=\Omega(n).$

######  Conjecture 1.9 (4.16).

Suppose that $\sigma$ is a symmetric connection such that
$\widehat{\sigma}(S)=0$ whenever $1\leq|S|\leq m-1$ or $d-m-1\leq|S|\leq d$
for a fixed constant $m.$ If $d=\tilde{\Omega}(n^{3/m})$ holds,
${\mathsf{TV}}\big{(}\mathsf{G}(n,p),\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma)\big{)}=o(1).$

In Proposition 6.13 we show that, if correct, this conjecture is tight up to
logarithmic factors. Specifically, there exist connections $\sigma$ for which
the conditions of 4.16 are satisfied and the signed-triangle statistic
distinguishes the two models whenever $d=\tilde{o}(n^{3/m}).$

Some further nearly immediate applications of Theorem 1.6 in the symmetric
setting are the following.

  1. 1.

Hard Thresholds Connections. When $\sigma={\mathbf{T}}_{p}$ (defined over the
hypercube analogously to the definition of the unit sphere), we prove in
Corollary 4.8 that if $d=\max\big{(}\tilde{\omega}(n^{3}p^{2}),\Omega(n\log
n)\big{)}$ holds, then ${\mathsf{TV}}\big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,{\mathbf{T}}_{p}),\mathsf{G}(n,p)\big{)}=o(1).$ This matches the
state of the art result on the sphere in the regime $p=\omega(n^{-1})$ in
[LMS+22a]. For the even analogue of ${\mathbf{T}}_{p}$ given by
$\mathbf{D}_{p}(\mathbf{x},\mathbf{y}):=\mathds{1}\left[|\langle\mathbf{x},\mathbf{y}\rangle|\geq\tau_{p/2,d}|\right]$
with expectation $p,$ $\mathsf{G}(n,p)$ and $\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\mathbf{D}_{p})$ are indistinguishable when
$d=\max\big{(}(\tilde{\omega}(n^{3/2}p),\Omega(n\log n)\big{)}$ and
distinguishable when $d=o(n^{3/2}p^{3/2})$ (see Corollaries 4.10 and 6.2).

  2. 2.

Lipschitz Connections. In Corollary 4.4 we show that if
$d=\max\big{(}\Omega(n^{3}/r^{4}),\Omega(n\log n)\big{)}$ for an
$\frac{1}{r\sqrt{d}}$-Lipshcitz connection $\sigma,$
${\mathsf{TV}}\big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma),\mathsf{G}(n,p)\big{)}=o(1)$, extending the work of [LR21a]
to the non-monotone case. Again, we improve the dependence to
$d=\max\big{(}\Omega(n^{3/2}/r^{2}),\Omega(n\log n)\big{)}$ in the even case
in Corollary 4.5.

  3. 3.

Interval Unions and Fluctuations. In Section 4.1.3 we extend the classical
threshold model in which $\sigma$ is an indicator of a single interval, i.e.
$[\tau_{p,d},+\infty)$ to the case when $\sigma$ is an indicator of a union of
$s$ disjoint intervals. Namely, we have indistinguishability when
$d=\Omega(n^{3}+n^{3/2}s^{2})$ in the general case and
$d=\Omega(n^{3/2}s^{2})$ in the even case. We give lower bounds in Section
6.1.2 when $d=o(ns^{2}),$ showing that the dependence on $s$ is tight.

  4. 4.

Low-Degree Connections. In Section 4.1.5 we consider the case when $\sigma$ is
a symmetric polynomial of constant degree. In that case, we prove that the two
graph models are indistinguishable when $d=\Omega(n)$ and
$d=\tilde{\omega}(\min(n^{3}p^{2},np^{-2/3})).$ In Section 6.1.4, we give a
detection lower bound for $d=o((np)^{3/4}),$ which leaves a polynomial gap in
this setting.

####  1.2.2 Modifications of Symmetric Connections

As Theorem 3.1 only depends on the size of Fourier coefficients on each level,
it also applies to transformations of symmetric connections which do not
increase the absolute values of Fourier coefficients. We analyse two such
transofrmations, which we call “coefficients contractions” and “repulsion-
attraction” twists. Both have natural interpretations, see Section 4.2.1.

A special case of a coefficient contraction is the following. For a symmetric
connection $\sigma:\\{\pm 1\\}^{d}\longrightarrow[0,1]$ and fixed
$\mathbf{g}\in\\{\pm 1\\}^{d},$ the coefficient contraction
$\sigma_{\mathbf{g}}$ is given by
$\sigma_{\mathbf{g}}(\mathbf{x}):=\sigma(\mathbf{x}\mathbf{g})$ (which simply
negates the coordinates $x_{i}$ for which $g_{i}=-1$). All of our
indistinguishability results from Section 1.2.1 continue to hold with the
exact same quantitative bounds on $d$ if we replace the connection $\sigma$
with an arbitrary coefficient contraction $\sigma_{\mathbf{g}}$ of it. While
it is a virtue of our proof techniques for indistinguishability results that
they capture these more general non-symmetric connections, it is also a
drawback. It turns out that certain coefficient contractions become
statistically indistinguishable from $\mathsf{G}(n,p)$ for polynomially
smaller dimensions, but this phenomenon is not captured by Theorem 1.6.

A particularly interesting case which illustrates this is the following. In
Section 6.2, we consider coefficient contractions with
$\mathbf{h}=\underbrace{1,1,\ldots,1}_{d_{1}}\underbrace{-1,-1,\ldots,-1}_{d_{1}}$
for $d=2d_{1}.$ This choice of $\mathbf{h}$ negates exactly half the
variables. In that case,
$\sigma_{\mathbf{h}}(\mathbf{x}^{-1}\mathbf{y})=\sigma_{\mathbf{h}}(\mathbf{x}\mathbf{y})$
depends on $\sum_{i\leq d_{1}}x_{i}y_{i}-\sum_{j>d_{1}}x_{j}y_{j}.$ Thus,
edges depend on a difference of inner products rather than inner products
(equivalently, inner products with signature
$(\underbrace{+,+,\ldots,+}_{d_{1}}\underbrace{-,-,\ldots,-}_{d_{1}})$ ). The
corresponding analogue of Wishart matrices is of the form $XX^{T}-YY^{T},$
where $X,Y\in\mathbb{R}^{n\times d_{1}}.$ In the Gaussian case, we prove the
following statement.

######  Theorem 1.10 (Theorem 6.17).

Define the law of the difference of two Wishart matrices as
follows.$\mathcal{W}(n,d_{1},-d_{1})$ is the law of $XX^{T}-YY^{T},$ where
$X,Y\in\mathbb{R}^{n\times d_{1}}$ are iid matrices with independent standard
Gaussian entries. If $d_{1}={\omega}(n^{2}),$ then
$\displaystyle{\mathsf{TV}}\big{(}\mathcal{W}(n,d_{1},-d_{1}),\sqrt{d_{1}}M(n)\big{)}=o_{n}(1).$

Compared to Theorem 1.2, this statement differs only in dimension. A Wishart
matrix converges to GOE when $d=\omega(n^{3}),$ but a difference of
independent Wishart matrices converges to GOE when $d=\omega(n^{2}).$

This proves that in the Gaussian case, for any connection
$\sigma(\mathbf{x},\mathbf{y})$ over $\mathbb{R}^{d}\times\mathbb{R}^{d}$ that
only depends on $\sum_{i\leq d_{1}}x_{i}y_{i}-\sum_{j>d_{1}}x_{j}y_{j},$ it is
the case that
${\mathsf{TV}}\big{(}\mathsf{RGG}(n,\mathbb{R}^{2d_{1}},\mathcal{N}(0,I_{2d_{1}}),p,\sigma),\mathsf{G}(n,p)\big{)}=o(1)$
whenever $d={\omega}(n^{2}).$ We expect that the same thing holds for the
hypercube model, but our Theorem 3.1 yields dependence $d={\omega}(n^{3}).$

In Section 8.1, we use Theorem 1.10 to rigorously show that there is an
inefficiency in deriving 1.5 arising from the use of KL-convexity, as
predicted in [LR21a].

####  1.2.3 Typical Indicator Connections Induce a Statistical-Computational
Gap

Finally, we study the behaviour of $\mathsf{RAG}(n,\\{\pm
1\\}^{d},p_{A},\sigma_{A})$ where $A\subseteq\\{\pm 1\\}^{d}$ is a “typical”
subset of the hypercube, $\sigma_{A}$ is its indicator, and $p_{A}=|A|/2^{d}$
is the expectation. We obtain strong evidence for a nearly-exponential
statistical-computational gap.

######  Theorem 1.11 (Informal, Theorems 4.19, 7.5, 7.2 and 7.3).

In the setup above,

  1. (a)

If $d=\Omega(n\log n),$ then ${\mathsf{TV}}\Big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},p_{A},\sigma_{A})\|\mathsf{G}(n,1/2)\Big{)}=o(1)$ for a
$1-2^{-\Omega(d)}$ fraction of the subsets $A$ of $\\{\pm 1\\}^{d}.$

  2. (b)

If $d=\frac{n}{2}-\omega(1),$ then ${\mathsf{TV}}\Big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},p_{A},\sigma_{A})\|\mathsf{G}(n,1/2)\Big{)}=1-o(1)$ for all subsets
$A$ of $\\{\pm 1\\}^{d}.$

  3. (c)

If $d=\log^{\Omega(1)}n,$ no low-degree polynomial test can distinguish
$\mathsf{RAG}(n,\\{\pm 1\\}^{d},p_{A},\sigma_{A})$ and $\mathsf{G}(n,1/2)$ for
a $1-2^{-\Omega(d)}$ fraction of the subsets $A$ of $\\{\pm 1\\}^{d}.$

Our result is more general and holds for other values of $p$ beyond $1/2.$ We
describe this in more detail in the next section, when we extend Theorem 1.11
to arbitrary groups of appropriate size. The advantage of the Fourier-analytic
proof in the hypercube setting over our proof in the setting of general groups
is that it gives an explicit construction of connections for which the
statistical limit occurs at $d=\tilde{\Theta}(n).$ In particular, this is the
case for all $A$ such that $\sigma_{A}$ is ${{d^{C}}}/{2^{d/2}}$-regular for a
fixed constant $C$ (see 4.20 and 4.21).

###  1.3 Random Algebraic Graphs

The main insight about the Boolean hypercube is that we can analyze
connections $\sigma(\mathbf{x},\mathbf{y})$ depending only the group product,
which is much more general than the inner product induced by $\mathbb{R}^{d}.$
It turns out that this construction can be naturally extended to a wide class
of groups.

######  Definition 1.12 (Random Algebraic Graphs).

Suppose that $\Omega$ is a unimodular locally compact Hausdorff topological
group $\mathcal{G}$ with the unique left- and right-invariant probability Haar
measure $\mu$ corresponding to distribution $\mathcal{D}.$222 If $\mathcal{G}$
is finite, this measure is just the uniform measure over the group elements.
If $\mathcal{G}$ is, say, the orthogonal group, this is the Haar measure over
it. Importantly, since the group is unimodular, the left and right Haar
measures coincide.  Suppose further that the connection
$\zeta:\mathcal{G}\times\mathcal{G}\longrightarrow[0,1]$ given by
$\zeta(\mathbf{x},\mathbf{y})$ only depends on $\mathbf{x}^{-1}\mathbf{y},$
that is $\zeta(\mathbf{x},\mathbf{y})=\sigma(\mathbf{x}^{-1}\mathbf{y})$ for
some $\sigma:\mathcal{G}\longrightarrow[0,1].$ Then, we call
$\mathsf{PLSG}(n,\mathcal{G},{\mathcal{D}},p,\zeta)$ a left random algebraic
graph. We use the notation $\mathsf{LRAG}(n,\mathcal{G},p,\sigma).$ Similarly,
define a right random algebraic graph and denote by $\mathsf{RRAG}$ for
connections depending only on $\mathbf{x}\mathbf{y}^{-1}.$

Clearly, for abelian groups such as $\\{\pm 1\\}^{d}$, right- and left- random
algebraic graphs coincide, for which reason we will use the simpler notation
$\mathsf{RAG}.$ We now demonstrate the expressivity of random algebraic graphs
by relating them to (approximate versions) of other well-studied graph models.

##### 1\. Random Geometric Graphs over the Sphere and Hypercube.

Random geometric graphs over the hypercube are random algebraic graphs. More
surprisingly, any random geometric graph defined by
$\Omega=\mathbb{S}^{d-1},{\mathcal{D}}=\mathsf{Unif},$ and a connection
$\zeta$ depending only on inner products can be represented as a random
algebraic graph even though $\mathbb{S}^{d-1}$ does not possess a group
structure when $d>3.$ Namely, consider a different latent space - the
orthogonal group $\mathcal{O}(d)=\Omega$ with its Haar measure. The latent
vectors are iid “uniformly distributed” orthogonal matrices
$U_{1},U_{2},\ldots,U_{n}.$ To generate uniform iid latent vectors on
$\mathbb{S}^{d-1},$ take $U_{1}v,U_{2}v,\ldots,U_{n}v$ for an arbitrary
$v\in\mathbb{S}^{d-1},$ say $v=e_{1}.$ Define $\sigma(U):=\zeta(\langle
vv^{T},U\rangle)$ and observe that

$\zeta(U_{i}v,U_{j}v)=\zeta(\langle U_{i}v,U_{j}v\rangle)=\zeta(\langle
vv^{T},U_{i}^{T}U_{j}\rangle)=\sigma(U_{i}^{-1}U_{j}).$

Clearly, $\mathsf{RGG}(n,\mathbb{S}^{d-1},\mathsf{Unif},p,\zeta)$ and
$\mathsf{LRAG}(n,\mathcal{O}(d),p,\sigma)$ have the same distribution.

##### 2\. Cayley Graphs: Blow-ups and Random Subgraphs.

Suppose that $\mathcal{G}$ is a finite group and $\sigma$ is an indicator of
some $S\subseteq\mathcal{G}$ which satisfies $a\in S$ if and only if
$a^{-1}\in S.$ The Cayley graph $\Gamma(\mathcal{G},S)$ has vertex set
$\mathcal{G}$ and edges between any two distinct vertices $g,h\in
V(\Gamma(\mathcal{G},S))=\mathcal{G}$ for which $gh^{-1}\in S.$ We consider
two regimes.

First, when $n=o(\sqrt{|\mathcal{G}|}).$ With high probability, the latent
vectors in $\mathsf{RRAG}(n,\mathcal{G},p,\sigma)$ are pairwise distinct by
the birthday paradox. This immediately leads to the following observation.

######  Observation 1.13.

Suppose that $\mathcal{G}$ is a group of size at least $n$ and
$S\subseteq\mathcal{G}$ is closed under taking inverses. Denote by
$\Gamma_{n}(\mathcal{G},S)$ the uniform distribution over $n$-vertex induced
subgraphs of $\Gamma(\mathcal{G},S).$ If $|\mathcal{G}|=\omega(n^{2}),$

${\mathsf{TV}}\Big{(}\mathsf{RRAG}(n,\mathcal{G},p,\sigma),\Gamma_{n}(\mathcal{G},S)\Big{)}=o(1).$

Second, when $|\mathcal{G}|=o(\frac{\sqrt{n}}{\log n}).$ With high
probability, each $g\in\mathcal{G}$ appears $\frac{n}{|\mathcal{G}|}(1+o(1))$
times as a latent vector in $\mathsf{RRAG}(n,\mathcal{G},p,\sigma).$ It
follows that $\mathsf{RRAG}(n,\mathcal{G},p,\sigma)$ is approximately an
$\frac{n}{|\mathcal{G}|}$-blow-up of $\Gamma(\mathcal{G},S).$

It is interesting to consider whether this relationship to Cayley graphs can
be used to understand random geometric graphs. For example, there are several
results on the expansion properties of Cayley graphs [AR94, Con17], which
could be related to the expansion properties of random geometric graphs
[LMS+22].

##### 3\. Stochastic Block Model.

The stochastic block-model is given by an $n$ vertex graph, in which $k$
communities and edges between them are formed as follows ([RB17]). First, each
vertex is independently assigned a uniform label in $\\{1,2,\ldots,k\\}.$
Then, between every two vertices, an edge is drawn with probability $p$ if
they have the same label and with probability $q<p$ otherwise. Denote this
graph distribution by $\mathsf{SBM}(n,k,p,q).$

$\mathsf{SBM}(n,k,p,q)$ can be modeled as a random algebraic graph as follows.
Take an arbitrary abelian group $\mathcal{G}$ which has a subgroup
$\mathcal{H}$ of order $|\mathcal{G}|/k.$ Define
$\sigma:\mathcal{G}\longrightarrow[0,1]$ by
$\sigma(\mathbf{g}):=q+(p-q)\times\mathds{1}[\mathbf{g}\in\mathcal{H}].$ Then,
$\mathsf{RAG}(n,\mathcal{G},\frac{p+(k-1)q}{k},\sigma)$ has the same
distribution as $\mathsf{SBM}(n,k,p,q).$ This follows directly from the
observation that communities in the stochastic block model correspond to
subsets of vertices with latent vectors in the same coset with respect to
$\mathcal{H}$ in the random algebraic graph.

###  1.4 Our Results on Typical Cayley Graphs

We utilize the connection between random algebraic graphs and Cayley graphs to
study the high-probability behaviour of Cayley graphs when the generating set
is chosen randomly. The distribution over random generating sets that we
consider is the following.

######  Definition 1.14 (The ante-inverse-closed uniform measure).

Let $\mathcal{G}$ be a group and $0\leq p\leq 1$ a real number, possibly
depending on $\mathcal{G}.$ Define the density $\mathsf{AnteU}(\mathcal{G},p)$
as follows. Consider the action of $C_{2}=\\{1,\rho\\}$ on $\mathcal{G}$
defined by $\rho(\mathbf{g})=\mathbf{g}^{-1}$ and let
$\mathcal{O}_{1},\mathcal{O}_{2},\ldots,\mathcal{O}_{t}$ be the associated
orbits. Let $X_{1},X_{2},\ldots,X_{t}$ be $t$ iid $\mathsf{Bernoulli}(p)$
random variables. Then, $\mathsf{AnteU}(\mathcal{G},p)$ is the law of
$S=\bigcup_{j\;:\;X_{j}=1}\mathcal{O}_{j}.$

Our main result, extending Theorem 1.11, is the following.

######  Theorem 1.15 (Informal, Theorems 5.1, 7.5 and 7.2).

Consider a finite group $\mathcal{G}.$

  1. (a)

If $|\mathcal{G}|=\exp\big{(}\Omega(n\log\frac{1}{p})\big{)},$ then
${\mathsf{TV}}\Big{(}\Gamma_{n}(\mathcal{G},A),\mathsf{G}(n,p)\Big{)}=o(1)$
with probability at least $1-|\mathcal{G}|^{-1/7}$ over
$A\sim\mathsf{AnteU}(\mathcal{G},p).$

  2. (b)

If $|\mathcal{G}|=\exp(O(nH(p))),$ where $H$ is the binary entropy function,
then
${\mathsf{TV}}\Big{(}\Gamma_{n}(\mathcal{G},A),\mathsf{G}(n,p)\Big{)}=1-o(1)$
for any generating set $A.$

  3. (c)

If $|\mathcal{G}|=\exp(\Omega(k\log n)),$ no polynomial test of degree at most
$k$ with input the graph edges can distinguish $\mathsf{G}(n,p)$ and
$\Gamma_{n}(\mathcal{G},A)$ with high probability over
$A\sim\mathsf{AnteU}(\mathcal{G},p).$

We note that these results can be equivalently phrased if we replace
$\Gamma_{n}(\mathcal{G},A)$ by
$\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A}),$ where $\sigma_{A}$ is the
indicator of $A$ and $p_{A}$ is its expectation.

In particular, this suggests that indistinguishability between
$\Gamma_{n}(\mathcal{G},A)$ and $\mathsf{G}(n,p)$ depends only on the size of
$\mathcal{G},$ but not on its group structure. This continues the long-
standing tradition of certifying that important properties of random Cayley
graphs only depend on group size. Prior literature on the topic includes
results on random walks [AD86, DH96, HO21] (see [HO21] for further
references), related graph-expansion properties [AR94], and chromatic numbers
[Alo13] of typical Cayley graphs.

One major difference between previous results and our current result is the
measure over generating sets used. Previous works used is what we call the
post-inverse-closed uniform measure.

######  Definition 1.16 (The post-inverse-closed uniform measure).

Let $\mathcal{G}$ be a finite group and $k\leq|\mathcal{G}|$ be an integer.
Define the density $\mathsf{PostU}(\mathcal{G},k)$ as follows. Draw $k$
uniform elements $Z_{1},Z_{2},\ldots,Z_{k}$ from $\mathcal{G}$ and set
$Z=\\{Z_{1},Z_{2},\ldots,Z_{k}\\}.$ Then, $\mathsf{PostU}(\mathcal{G},k)$ is
the law of $S=Z\cup Z^{-1}.$

There are several differences between the two measures on generating sets, but
the crucial one turns out to be the following. In the ante-inverse-closed
uniform measure, each element appears in $S$ with probability $p.$ In the
post-inverse-closed uniform measure, an element $\mathbf{g}$ of order two
appears with probability $q:=1-(1-\frac{1}{|\mathcal{G}|})^{k}$ since
$\mathbf{g}\in Z\cup Z^{-1}$ if and only if $\mathbf{g}\in Z.$ On the other
hand, an element $\mathbf{h}$ of order greater than 2 with probability
$1-(1-\frac{2}{|\mathcal{G}|})^{k}\approx 2q.$ This suggests that we cannot
use the $\mathsf{PostU}$ measure for groups which simultaneously have a large
number of elements of order two and elements of order more than two to prove
indistinguishability results such as the ones given in Theorem 1.15. Consider
the following example.

######  Example 1.17.

Consider the group
$\mathcal{G}=\mathcal{C}_{3}\times\underbrace{\mathcal{C}_{2}\times\mathcal{C}_{2}\times\cdots\times\mathcal{C}_{2}}_{d}.$
Denote the three different cosets with respect to the $\mathcal{C}_{3}$
subgroup by
$H_{i}=\\{i\\}\times\underbrace{\mathcal{C}_{2}\times\mathcal{C}_{2}\times\cdots\times\mathcal{C}_{2}}_{d}$
for $i\in\\{0,1,2\\}.$ Elements in $H_{0}$ have order at most $2,$ while
elements in $H_{1},H_{2}$ have order $3.$ Now, consider
$\mathsf{PostU}(\mathcal{G},k),$ where $k$ is chosen so that
${\mathbf{E}}[|S|\times|\mathcal{G}|^{-1}]\approx\frac{1}{2}.$ Each element
from $H_{0}$ appears in $S$ with probability $q$ and each element in
$H_{1},H_{2}$ with probability $\sim 2q,$ such that
$q\times|H_{0}|+2q\times(|H_{1}|+|H_{2}|)=\frac{|\mathcal{G}|}{2}.$ It follows
that $q\approx\frac{3}{10}.$

Let $S$ be drawn from $\mathsf{PostU}(\mathcal{G},k)$ and
$G\sim\Gamma_{n}(\mathcal{G},S).$ With high probability, the vertices of $G$
can be split into three groups - $G_{0},G_{1},G_{2},$ where $G_{i}$ contains
the vertices coming from coset $H_{i}.$ The average density within each of
$G_{0},G_{1},G_{2}$ in $G$ will be approximately $\frac{3}{10},$ while the
average density of edges of $G$ which have at most one endpoint in each of
$G_{0},G_{1},G_{2}$ will be approximately $\frac{6}{10}.$ Clearly, such a
partitioning of the vertices $G_{0},G_{1},G_{2}$ typically does not exist for
Erdős-Rényi graphs. Thus, no statistical indistinguishability results can be
obtained using the $\mathsf{PostU}$ measure over
$\mathcal{G}=\mathcal{C}_{3}\times\underbrace{\mathcal{C}_{2}\times\mathcal{C}_{2}\times\cdots\times\mathcal{C}_{2}}_{d}.$

Of course, there are other differences between $\mathsf{AnteU}$ and
$\mathsf{PostU},$ such as the fact that in the $\mathsf{PostU}$ measure
elements from different orbits do not appear independently (for example, as
the maximal number of elements of $S$ is $2k$). These turn out to be less
consequential. In Appendix E, we characterize further distributions beyond
$\mathsf{AnteU}$ for which our statistical and computational
indistinguishability results hold. Informally, the desired property of a
distribution $\mathsf{D}(\mathcal{G},p)$ is the following. Let
$A\sim\mathsf{D}(\mathcal{G},p).$ For nearly all elements
$\mathbf{x}\in\mathcal{G},$ if we condition on any event $E$ that
$\mathsf{polylog}(|G|)$ elements besides $\mathbf{x},\mathbf{x}^{-1}$ are or
are not in $A,$ we still have ${\mathbf{P}}[\mathbf{x}\in
A|E]=p+O(|\mathcal{G}|^{-c}),$ where $c\in(0,1)$ is constant.

In particular, this means that our results over $\mathcal{G}=\\{\pm 1\\}^{d}$
hold when we use $\mathsf{PostU}(\mathcal{G},k)$ for an appropriately chosen
$k$ so that
$(1-\frac{1}{|\mathcal{G}|})^{k}=p+O\big{(}\frac{1}{|\mathcal{G}|}\big{)}$
since all elements of $\\{\pm 1\\}^{d}$ have order $2.$ Similarly, we can use
the $\mathsf{PostU}$ density with an appropriate $k$ for all groups without
elements of order two, which include the groups of odd cardinality.

##  2 Notation and Preliminaries

###  2.1 Information Theory

The main subject of the current paper is to understand when two graph
distributions - $\mathsf{G}(n,p)$
and$\mathsf{PLSG}(n,\Omega,\mathcal{D},\sigma,p)$ \- are statistically
indistinguishable or not. For that reason, we need to define similarity
measures between distributions.

######  Definition 2.1 (For example, [PWng]).

Let $\mathbf{P},\mathbf{Q}$ be two probability measures over the measurable
space $(\Omega,\mathcal{F}).$ Suppose that $\mathbf{P}$ is absolutely
continuous with respect to $\mathbf{Q}$ and has a Radon-Nikodym derivative
$\frac{d{\mathbf{P}}}{d\mathbf{Q}}.$ For a convex function $f:\mathbb{R}_{\geq
0}\longrightarrow\mathbb{R}$ satisfying $f(1)=0,$ the $f$-divergence between
$\mathbf{P},\mathbf{Q}$ is given by

$\mathsf{D}_{f}({\mathbf{P}}\|\mathbf{Q})=\int_{\Omega}f\bigg{(}\frac{d{\mathbf{P}}}{d\mathbf{Q}}\bigg{)}d\mathbf{Q}.$

The two $f$-divergences of primary interest to the current paper are the
following:

  1. 1.

Total Variation:
${\mathsf{TV}}(\mathbf{P},\mathbf{Q}):=\mathsf{D}_{f}({\mathbf{P}}\|\mathbf{Q})$
for $f(x)=\frac{1}{2}|x-1|.$ It easy to show that ${\mathsf{TV}}$ can be
equivalently defined by
${\mathsf{TV}}(\mathbf{P},\mathbf{Q})=\sup_{A\in\mathcal{F}}|\mathbf{P}(A)-\mathbf{Q}(A)|.$

  2. 2.

KL-Divergence:
${\mathsf{KL}}(\mathbf{P}\|\mathbf{Q}):=\mathsf{D}_{f}({\mathbf{P}}\|\mathbf{Q})$
for $f(x)=x\log x$ (where $f(0)=0$).

It is well-known that total variation characterizes the error probability of
an optimal statistical test. However, it is often easier to prove bounds on KL
and translate to total variation via Pinsker’s inequality.

######  Theorem 2.2 (For example, [PWng]).

Let $\mathbf{P},\mathbf{Q}$ be two probability measures over the measurable
space $(\Omega,\mathcal{F})$ such that $\mathbf{P}$ is absolutely continuous
with respect to $\mathbf{Q}.$ Then,

${\mathsf{TV}}(\mathbf{P},\mathbf{Q})\leq\sqrt{\frac{1}{2}{\mathsf{KL}}(\mathbf{P}\|\mathbf{Q})}.$

Another classic inequality which we will need is the data-processing
inequality. We only state it in the very weak form in which we will need it.

######  Theorem 2.3 (For example, [PWng]).

For any two distributions $\mathbf{P},\mathbf{Q},$ any measurable
deterministic function $h,$ and any $f$-divergence $\mathsf{D}_{f},$ the
inequality
$\mathsf{D}_{f}({\mathbf{P}}\|\mathbf{Q})\geq\mathsf{D}_{f}(h_{*}({\mathbf{P}})\|h_{*}(\mathbf{Q}))$
holds. Here, $h_{*}({\mathbf{P}}),h_{*}(\mathbf{Q})$ are the respective push-
forward measures.

###  2.2 Boolean Fourier Analysis

One of the main contributions of the current paper is that it introduces tools
from Boolean Fourier analysis to the study of random geometric graphs. Here,
we make a very brief introduction to the topic. An excellent book on the
subject is [ODo14], on which our current exposition is largely based.

We note that $\\{\pm 1\\}^{d}$ is an abelian group (isomorphic to
$\mathbb{Z}_{2}^{d}$) and we denote the product of elements
$\mathbf{x},\mathbf{y}$ in it simply by $\mathbf{x}\mathbf{y}.$ Note that
$\mathbf{x}=\mathbf{x}^{-1}$ over $\\{\pm 1\\}^{d}.$

Boolean Fourier analysis is used to study the behaviour of functions $f:\\{\pm
1\\}^{d}\longrightarrow\mathbb{R}.$ An important fact is the following theorem
stating that all functions on the hypercube are polynomials.

######  Theorem 2.4.

Every function $f:\\{\pm 1\\}^{d}\longrightarrow\mathbb{R}$ can be uniquely
represented as

$f(\mathbf{x})=\sum_{S\subseteq[d]}\widehat{f}(S)\omega_{S}(\mathbf{x}),$

where $\omega_{S}(\mathbf{x})=\prod_{i\in S}x_{i}$ and $\widehat{f}(S)$ is a
real number, which we call the Fourier coefficient on $S.$

We call the monomials $\omega_{S}(\mathbf{x})$ characters or Walsh
polynomials. One can easily check that $\omega_{\emptyset}\equiv 1$ and
$\omega_{s}\omega_{T}=\omega_{S\Delta T}.$ The Walsh polynomials form an
orthogonal basis on the space of real-valued functions over $\\{\pm 1\\}^{d}.$
Namely, for two such functions $f,g,$ define $\langle
f,g\rangle={\mathbf{E}}_{\mathbf{x}\sim\mathsf{Unif}(\\{\pm
1\\}^{d})}[f(\mathbf{x})g(\mathbf{x})].$ This is a well-defined inner-product,
to which we can associate an $L_{2}$-norm $\left\lVert
f\right\rVert^{2}_{2}:=\langle f,f\rangle$.

######  Theorem 2.5 (For example, [ODo14]).

The following identities hold.

  1. 1.

$\langle\omega_{s},\omega_{T}\rangle=\mathds{1}[T=S].$

  2. 2.

$\langle f,g\rangle=\sum_{S\subseteq[d]}\widehat{f}(S)\widehat{g}(S).$ In
particular,

    1. (a)

$\widehat{f}(S)={\mathbf{E}}[f(\mathbf{x})\omega_{S}(\mathbf{x})].$

    2. (b)

$\left\lVert f\right\rVert_{2}^{2}=\sum_{S\subseteq[d]}\widehat{f}(S)^{2}.$

    3. (c)

${\mathbf{E}}[f]=\widehat{f}(\emptyset),{\mathbf{Var}}[f]=\sum_{\emptyset\subsetneq
S\subseteq[d]}\widehat{f}(S)^{2}.$

  3. 3.

The Fourier convolution $(f*g):\\{\pm 1\\}^{d}\longrightarrow\mathbb{R}$
defined by
$(f*g)[\mathbf{x}]={\mathbf{E}}[f(\mathbf{x}\mathbf{z}^{-1})g(\mathbf{z})]$
can be expressed as

$(f*g)[\mathbf{x}]=\sum_{S\subseteq[d]}\widehat{f}(S)\widehat{g}(S)\omega_{S}(\mathbf{x}).$

Oftentimes, it is useful to study other $L_{p}$-norms, defined for $p\geq 1$
by $\displaystyle\left\lVert
f\right\rVert_{p}:={\mathbf{E}}_{\mathbf{x}\sim\mathsf{Unif}(\\{\pm
1\\}^{d})}[|f|^{p}]^{1/p}.$ By Jensen’s inequality, $\left\lVert
f\right\rVert_{p}\leq\left\lVert f\right\rVert_{q}$ holds whenever $p<q.$ It
turns out, however, that a certain reverse inequality also holds. To state it,
we need the noise operator.

######  Definition 2.6.

For $\mathbf{x}\in\\{\pm 1\\}^{d},$ let $\mathcal{N}_{\rho}(\mathbf{x})$ be
the $\rho$-correlated distribution of $\mathbf{x}$ for $\rho\in[0,1].$ That
is, $\mathbf{y}\sim\mathcal{N}_{\rho}(\mathbf{x})$ is defined as follows. For
each $i\in[d],$ independently $y_{i}=x_{i}$ with probability
$\frac{1+\rho}{2}$ and $y_{i}=-x_{i}$ with probability $\frac{1-\rho}{2}.$
Define:

  1. 1.

Noise Operator: The linear operator $T_{\rho}$ on functions over the hypercube
is defined by
$T_{\rho}f[\mathbf{x}]:={\mathbf{E}}_{\mathbf{y}\sim\mathcal{N}_{\rho}(\mathbf{x})}[f(\mathbf{y})].$
The Fourier expansion of $T_{\rho}f$ is given by

$T_{\rho}f=\sum_{S\subseteq[d]}\rho^{|S|}\widehat{f}(S)\omega_{S}.$

In light of this equality, $T_{\rho}$ can also be defined for $\rho>1.$

  2. 2.

Stability: The Stability of a function $f:\\{\pm
1\\}^{d}\longrightarrow\mathbb{R}$ is given by

${\mathbf{Stab}}_{\rho}[f]:=\langle
T_{\rho}f,f\rangle=\sum_{S\subseteq[d]}\rho^{|S|}\widehat{f}(S)^{2}=\left\lVert
T_{\sqrt{\rho}}f\right\rVert_{2}^{2}$

We are ready to state the main hypercontractivity result which we will use in
Section 3.

######  Theorem 2.7 ([Bon70]).

For any $1\leq p\leq q$ and any $f:\\{\pm 1\\}^{d}\longrightarrow\mathbb{R},$
we have the inequality

$\left\lVert
f\right\rVert_{q}\leq\Big{\|}{T_{\sqrt{\frac{q-1}{p-1}}}f}\Big{\|}_{p}.$

In particular, when $q\geq p=2,$ one has $\displaystyle\left\lVert
f\right\rVert^{2}_{q}\leq\sum_{S\subseteq\emptyset}(q-1)^{|S|}\widehat{f}(S)^{2}.$

The way in which the noise operator changes the Fourier coefficient of
$\omega_{S}$ depends solely on the size of $S.$ For that, and other, reasons,
it turns out that it is useful to introduce the Fourier weights. Namely, for a
function $f:\\{\pm 1\\}^{d}\longrightarrow\mathbb{R},$ we define its weight on
level $i\in\\{0,1,2,\ldots,d\\}$ by

$\mathcal{W}^{i}({f})=\sum_{S\subseteq[d]\;:\;|S|=i}\widehat{f}(S)^{2}.$

We similarly denote $\mathcal{W}^{\leq i}({f})=\sum_{j\leq
i}\mathcal{W}^{j}({f})$ and $\mathcal{W}^{\geq i}({f})=\sum_{j\geq
i}\mathcal{W}^{j}({f}).$ Trivially, for each $i,$ one has
$\mathcal{W}^{i}({f})\leq\sum_{j=0}^{d}\mathcal{W}^{j}({f})=\left\lVert
f\right\rVert_{2}^{2}.$ In particular, this means that if $|f|\leq 1$ holds
a.s. (which is the case for connections $\sigma$ in random geometric graphs by
definition), $\mathcal{W}^{i}({f})\leq 1$ also holds for each $i.$ It turns
out that in certain cases, one can derive sharper inequalities.

######  Theorem 2.8 ([KKL88]).

For any function $f:\\{\pm 1\\}^{d}\longrightarrow[-1,1]$ such that
$\left\lVert f\right\rVert_{1}=\alpha,$ the inequalities

$\mathcal{W}^{\leq
k}({f})\leq\Big{(}\frac{2e}{k}\ln(1/\alpha)\Big{)}^{k}\alpha^{2}\quad\text{and}\quad\mathcal{W}^{\geq
d-k}({f})\leq\Big{(}\frac{2e}{k}\ln(1/\alpha)\Big{)}^{k}\alpha^{2}$

hold whenever $k\leq 2\ln(1/\alpha).$

We end with a discussion on low-degree polynomials. We say that $f:\\{\pm
1\\}^{d}\longrightarrow\mathbb{R}$ has degree $k$ if it is a degree $k$
polynomial, that is $\widehat{f}(S)=0$ whenever $|S|>k.$ It turns out that
such polynomials have surprisingly small Fourier coefficients. Namely,
Eskenazis and Ivanisvili use a variant of the Bohnenblust-Hille to prove the
following result.

######  Theorem 2.9 ([EI22]).

For any fixed number $k\in\mathbb{N},$ there exists some constant $C_{k}$ with
the following property. If $f:\\{\pm 1\\}^{d}\longrightarrow[-1,1]$ is a
degree $k$ function, then for any $\ell>0$

$\sum_{S\;:\;|S|=\ell}|\widehat{f}(S)|\leq C_{k}d^{\frac{\ell-1}{2}}.$

In particular, if $f$ is symmetric
($f(x_{1},x_{2},\ldots,x_{n})=f(x_{\pi(1)},x_{\pi(2)},\ldots,x_{\pi(n)})$
holds for each $\mathbf{x}$ and permutation $\pi$), the following bound holds.

######  Corollary 2.10.

If $f:\\{\pm 1\\}^{d}\longrightarrow[-1,1]$ is a symmetric constant degree
function, then $\mathcal{W}^{\ell}({f})=O(1/d)$ for any $\ell>0.$

###### Proof.

We simply note that Theorem 2.9 implies that

$\mathcal{W}^{\ell}({f})=\binom{d}{\ell}\bigg{(}\frac{\sum_{S\;:\>|S|=\ell}|\widehat{f}(S)|}{\binom{d}{\ell}}\bigg{)}^{2}=O\Big{(}d^{\ell}\times\frac{d^{\ell-1}}{d^{2\ell}}\Big{)}.\qed$

###  2.3 Detection and Indistinguishability via Fourier Analysis

Before we jump into the main arguments of the current paper, we make two
simple illustrations of Fourier-analytic tools in the study of random
algebraic graphs, which will be useful later on. These observations cast new
light on previously studied objects in the literature.

####  2.3.1 Indistinguishability

First, we will interpret the function $\gamma$ from 1.5 as an autocorrelation
function.

######  Proposition 2.11.

Let $\mathcal{G}=\\{\pm 1\\}^{d}$ and suppose that $\sigma$ only depends on
$\mathbf{x}\mathbf{y}=\mathbf{x}\mathbf{y}^{-1}.$ Then,

$\gamma(\mathbf{x},\mathbf{y})=(\sigma-p)*(\sigma-p)[\mathbf{x}\mathbf{y}^{-1}].$

###### Proof.

Let
$\sigma(\mathbf{g})=\sum_{S\subseteq[d]}\widehat{\sigma}(S)\omega_{S}(\mathbf{g})$
for $\mathbf{g}\in\\{\pm 1\\}^{d}.$ In particular,
$\widehat{\sigma}(\emptyset)=p.$ Now, we have

$\displaystyle\gamma(\mathbf{x},\mathbf{y})$
$\displaystyle={\mathbf{E}}_{\mathbf{z}\sim\mathsf{Unif}(\\{\pm
1\\}^{d})}[(\sigma(\mathbf{x},\mathbf{z})-p)(\sigma(\mathbf{y},\mathbf{z})-p)]={\mathbf{E}}_{\mathbf{z}}\sum_{\emptyset\subsetneq
S,T\subseteq[d]}\left[\widehat{\sigma}(S)\widehat{\sigma}(T)\omega_{S}(\mathbf{x}\mathbf{z}^{-1})\omega_{T}(\mathbf{z}\mathbf{y}^{-1})\right]$
$\displaystyle=\sum_{\emptyset\subsetneq
S,T\subseteq[d]}\widehat{\sigma}(S)\widehat{\sigma}(T)\omega_{S}(\mathbf{x})\omega_{T}(\mathbf{y}^{-1}){\mathbf{E}}[\omega_{T\delta
S}(\mathbf{z})]=\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{2}\omega_{S}(\mathbf{x}\mathbf{y}^{-1})$
$\displaystyle=(\sigma-p)*(\sigma-p)[\mathbf{x}\mathbf{y}^{-1}].\qed$

The same argument applies verbatim when we replace $\\{\pm 1\\}^{d}$ with an
arbitrary finite abelian group (and some other groups such as a product of a
finite abelian group with a torus, provided $\sigma$ is $L_{2}$-integrable
with respect to ${\mathcal{D}}$). Hence our use of
$\mathbf{x}\mathbf{y}^{-1}$. In light of Eq. 4, we simply need to prove bounds
on the moments of the autocorrelation of $\sigma-p$ (i.e., the centered
moments of the autocorrelation of $\sigma$).

####  2.3.2 Detection Using Signed Cycles in Temrs of Fourier Coefficients

Let the indicator of edge $i,j$ be $G_{i,j}.$ Essentially all detection
algorithms appearing in the literature on random geometric graphs are derived
by counting “signed” $k$-cycles in the respective graph for $k\in\\{3,4\\}$
[LR21a, BDE+14, BBH21]. Formally, these works provide the following detection
algorithm, which is efficiently computable in time $O(n^{k})$ when $k$ is a
constant. One sums over the set $\mathcal{C}$ of all simple cycles
$i_{1},i_{2},\ldots,i_{k}$ the quantity
$\prod_{t=1}^{k}(G_{i_{t},i_{t+1}}-p),$ where $i_{k+1}:=i_{1}.$ The resulting
statistic is

$\tau_{k,p}(G):=\sum_{(i_{1},i_{2},\ldots,i_{k})\in\mathcal{C}}\prod_{t=1}^{k}(G_{i_{t},i_{t+1}}-p)\,.$
(5)

Since each edge $G_{i,j}$ appears independently with probability $p$ in an
Erdős-Rényi graph, clearly
$\displaystyle{\mathbf{E}}_{G\sim\mathsf{G}(n,p)}[\tau_{k}(G)]=0.$ Thus, to
distinguish with high probability between $\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma)$ and $\mathsf{G}(n,p),$ it is enough to show that

$|{\mathbf{E}}_{H\sim\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma)}\tau_{k}(G)|=\omega\b{(}{\mathbf{Var}}_{G\sim\mathsf{G}(n,p)}[\tau_{k}(G)]+{\mathbf{Var}}_{H\sim\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma)}[\tau_{k}(H)]\b{)}$

by Chebyshev’s inequality. We now demonstrate how to compute the relevant
quantities in the language of Boolean Fourier analysis.

######  Observation 2.12.

For any set of $k$ indices $i_{1},i_{2},\ldots,i_{k},$ it is the case that

${\mathbf{E}}_{G\sim\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma)}\left[\prod_{t=1}^{k}(G_{i_{t},i_{t+1}}-p)\right]=\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{k}.$

###### Proof.

We simply compute

$\displaystyle{\mathbf{E}}\left[\prod(G_{i_{t},i_{t+1}}-p)\right]={\mathbf{E}}\left[{\mathbf{E}}\left[\prod(G_{i_{t},i_{t+1}}-p)|\mathbf{x}_{i_{1}},\mathbf{x}_{i_{2}},\ldots,\mathbf{x}_{i_{t}}\right]\right]$
$\displaystyle={\mathbf{E}}\left[{\mathbf{E}}\left[\prod(\sigma(\mathbf{x}_{i_{t}}^{-1}\mathbf{x}_{i_{t+1}})-p)|\mathbf{x}_{i_{1}},\mathbf{x}_{i_{2}},\ldots,\mathbf{x}_{i_{t}}\right]\right].$

Now, observe that
$\mathbf{x}_{i_{1}},\mathbf{x}_{i_{2}},\ldots,\mathbf{x}_{i_{k}}$ are
independently uniform over the hypercube. Thus, when we substitute
$\mathbf{g}_{\ell}=\mathbf{x}_{i_{\ell-1}}^{-1}\mathbf{x}_{i_{\ell}},$ the
vectors $\mathbf{g}_{1},\mathbf{g}_{2},\ldots,\mathbf{g}_{k-1}$ are
independent and
$\mathbf{g}_{k}=\mathbf{g}_{1}^{-1}\mathbf{g}_{2}^{-1}\cdots\mathbf{g}_{k-1}^{-1}.$
We conclude that

$\displaystyle{\mathbf{E}}\left[{\mathbf{E}}\left[\prod(\sigma(\mathbf{x}_{i_{t}}^{-1}\mathbf{x}_{i_{t+1}})-p)|\mathbf{x}_{i_{1}},\mathbf{x}_{i_{2}},\ldots,\mathbf{x}_{i_{t}}\right]\right]$
$\displaystyle={\mathbf{E}}_{(\mathbf{g}_{1},\mathbf{g}_{2},\ldots,\mathbf{g}_{k-1})\sim_{iid}\mathsf{Unif}(\\{\pm
1\\}^{d})}(\sigma(\mathbf{g}_{1})-p)(\sigma(\mathbf{g}_{2})-p)\cdots(\sigma(\mathbf{g}_{t-1})-p)(\sigma(\mathbf{g}_{1}^{-1}\mathbf{g}_{2}^{-1}\cdots\mathbf{g}_{k-1}^{-1})-p).$

Expanding the above product in the Fourier basis yields

$\displaystyle{\mathbf{E}}\left[\sum_{S_{1},S_{2},\ldots,S_{t}}\prod_{i=1}^{t}\widehat{\sigma}(S_{i})\times\prod_{i=1}^{t-1}\omega_{S_{i}}(\mathbf{g}_{i})\times\omega_{S_{t}}(\mathbf{g}_{1}^{-1}\mathbf{g}_{2}^{-1}\cdots\mathbf{g}_{t-1}^{-1})\right]$
$\displaystyle=\sum_{S_{1},S_{2},\ldots,S_{t}}\prod_{i=1}^{t}\widehat{\sigma}(S_{i})\times\prod_{i=1}^{t-1}{\mathbf{E}}\left[\omega_{S_{i}}(\mathbf{g}_{i})\omega_{S_{t}}(\mathbf{g}_{i}^{-1})\right].$

Since $\langle\omega_{S_{i}},\omega_{S_{t}}\rangle=\mathds{1}[S_{i}=S_{t}],$
the conclusion follows. ∎

It follows that when $k=O(1),$

$\displaystyle{\mathbf{E}}_{G\sim\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma)}[\tau_{k}(G)]=\Theta\Big{(}n^{k}\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{k}\Big{)}.$

In Appendix A, using very similar reasoning, we show that the variance can
also be bounded in terms of the Fourier coefficients of $\sigma.$

######  Proposition 2.13.

$\displaystyle{\mathbf{Var}}_{G\sim\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma)}[\tau_{3}(G)]=O\Big{(}n^{3}p^{3}+n^{3}\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{3}+n^{4}\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{4}\Big{)}.$

Combining 2.12 and 2.13, we make the following conclusion.

######  Corollary 2.14.

If

$n^{6}\Big{(}\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{3}\Big{)}^{2}=\omega\Big{(}n^{3}p^{3}+n^{3}\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{3}+n^{4}\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{4}\Big{)},$

then ${\mathsf{TV}}\Big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma),\mathsf{G}(n,p)\Big{)}=1-o(1).$ Furthermore, the
polynomial-time algorithm of counting signed triangles distinguishes
$\mathsf{G}(n,p)$ and $\mathsf{RAG}(n,\\{\pm 1\\}^{d},p,\sigma)$ with high
probability.

Thus, we have shown that the entirety of the detection via signed triangles
argument has a simple interpretation in the language of Boolean Fourier
analysis. One can argue similarly for counting signed $k$-cycles when $k>3,$
but the variance computation becomes harder. We illustrate a very simple
instance of this computation for $k=4$ in Appendix F.

##  3 The Main Theorem On Indistinguishability Over The Hypercube

In this section, we prove our main technical result on indistinguishability
between $\mathsf{G}(n,p)$ and$\mathsf{RAG}(n,\\{\pm 1\\}^{d},p,\sigma).$ The
statement itself does not look appealing due to the many conditions one needs
to verify. In subsequent sections, we remove these conditions by exploring
specific connections $\sigma.$

######  Theorem 3.1.

Consider a dimension $d\in\mathbb{N},$ connection $\sigma:\\{\pm
1\\}^{d}\longrightarrow[0,1]$ with expectation $p,$ and constant
$m\in\mathbb{N}.$333We will usually take $m\leq 3$ when applying the theorem,
so one can really think of it as a small constant. There exists a constant
$K_{m}$ depending only on $m,$ but not on $\sigma,d,n,p,$ with the following
property. Suppose that $n\in\mathbb{N}$ is such that $nK_{m}<d.$ For $1\leq
i\leq d,$
let$B_{i}=\max\Big{\\{}|\widehat{\sigma}(S)|\binom{d}{i}^{1/2}:|S|=i\Big{\\}}.$
Denote also

$C_{m}=\sum_{i=m+1}^{\frac{d}{2en}}B_{i}^{2}+\sum_{i=d-\frac{d}{2en}}^{d-m-1}B_{i}^{2}\quad\text{and}\quad
D=\sum_{\frac{d}{2en}\leq j\leq d-\frac{d}{2en}}B_{i}^{2}.$

If the following conditions additionally hold

  * •

$d\geq K_{m}\times n\times\Big{(}\frac{C_{m}}{p(1-p)}\Big{)}^{\frac{2}{m+1}},$

  * •

$d\geq K_{m}\times
n\times\Big{(}\frac{B^{2}_{u}}{p(1-p)}\Big{)}^{\frac{2}{u}}$ for all $2\leq
u\leq m,$

  * •

$d\geq K_{m}\times
n\times\Big{(}\frac{B^{2}_{d-u}}{p(1-p)}\Big{)}^{\frac{2}{u}}$ for all $2\leq
u\leq m,$

then

$\displaystyle{\mathsf{KL}}(\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma)\|\mathsf{G}(n,p))$ $\displaystyle\leq
K_{m}\times\frac{n^{3}}{p^{2}(1-p)^{2}}\times\left(\sum_{i=1}^{m}\frac{B_{i}^{4}}{d^{i}}+\sum_{i=d-m}^{d}\frac{B_{i}^{4}}{d^{i}}+\frac{C^{2}_{m}}{{d}^{m+1}}+{D^{2}}\times\exp\left(-\frac{d}{2en}\right)\right).$

Before we proceed with the proof, we make several remarks. First, when one
applies the above theorem, typically the four conditions are reduced to just
the much simpler $d\geq K_{m}\times n.$ This is the case, for example, when
$\sigma$ is symmetric. Indeed, note that
$\sum_{i=1}^{d}B_{i}^{2}={\mathbf{Var}}[\sigma]\leq p(1-p)$ in that case, so
the three inequalities are actually implied by $d\geq K_{m}\times n.$ This
also holds for “typical” $\\{0,1\\}$-valued connections as we will see in
Section 4.3.

Next, we explain the expression bounding the ${\mathsf{KL}}$ divergence. In
it, we have separated the Fourier levels into essentially $2m+3$ intervals:

  * •

$I_{u}=\\{u\\}$ for $u\in[m],$

  * •

$I_{m+u}=\\{d-u\\}$ for $u\in[m],$

  * •

$I_{2m+1}=[m+1,\frac{d}{2en}]\cup[d-\frac{d}{2en},d-m-1],$

  * •

$I_{2m+2}=(\frac{d}{2en},d-\frac{d}{2en}),$

  * •

$I_{2m+3}=\\{d\\}.$

There are two reasons for this. First, as we will see in Sections 4.1 and
4.1.4, levels very close to 0 and $d,$ i.e indexed by $O(1)$ or $d-O(1)$ play
a fundamentally different role than the rest of the levels. This explains why
$I_{1},I_{2},\ldots I_{2m},I_{2m+3}$ are handled separately and why $I_{2m+1}$
and $I_{2m+2}$ are further separated (note that if $m$ is a constant, levels
$m,m+1,\ldots,2m$ in $I_{2m+1}$ also have indices of order $O(1)$). There is a
further reason why $I_{2m+2}$ is held separately from the rest. On the
respective levels, significantly stronger hypercontractivity bounds hold (see
Theorem 3.5).

While the above theorem is widely applicable, as we will see in Section 4, it
has an unfortunate strong limitation - it requires that $d=\Omega_{m}(n)$ even
when the other three inequalities are satisfied for much smaller values of $d$
(for an example, see Section 4.1.4). In Section 8.1, we show that this is not
a consequence of the complex techniques for bounding moments of $\gamma$ that
we use. In fact, any argument based on 1.5 applied to $\\{0,1\\}$-valued
connections over the hypercube requires $d=\Omega(n).$ In particular, this
means that one needs other tools to approach 1.1 in its analogue version on
the hypercube when $p=o(n^{-2/3})$ and our conjecture 4.16. In Theorem 7.5, we
illustrate another, independent of proof techniques, reason why $d=\Omega(n)$
is necessary for $\\{0,1\\}$-valued connections with expectation of order
$\Theta(1).$

Finally, we end with a brief overview of the proof, which is split into
several sections.

  1. 1.

First, in Section 3.1, we “symmetrize” $\sigma$ by increasing the absolute
values of its Fourier coefficients, so that all coefficients on the same level
are equal. This might lead to a function which does not take values in
$[0,1].$ As we will see, this does not affect our argument.

  2. 2.

Then, in Section 3.2, using a convexity argument, we bound the moments of the
symmetrized function by the moments on several (scaled) elementary symmetric
polynomials which depend on the intervals $I_{1},I_{2},\ldots,I_{2m+3}$
described above.

  3. 3.

Next, in Section 3.3, we bound separately the moments of elementary symmetric
polynomials using hypercontractivity tools. We prove new, to the best of our
knowledge, bounds on the moments of elementary symmetric polynomials in
certain regimes.

  4. 4.

Finally, we put all of this together to prove Theorem 3.1 in Section 3.4.

###  3.1 Symmetrizing The Autocorrelation Function

In light of Eq. 4 and 1.5, we need to bound the moments of $\gamma.$ Our first
observation is that we can, as far as bounding $k$-th moments is concerned,
replace $\gamma$ by a symmetrized version.

######  Proposition 3.2.

Suppose that $\gamma,B_{1},B_{2},\ldots,B_{d}$ are as in Theorem 3.1 and
consider the function

$f(\mathbf{g}):=\sum_{\emptyset\subseteq
S\subsetneq[d]}\frac{B_{|S|}^{2}}{\binom{d}{|S|}}\omega_{S}(\mathbf{g}).$

Then, for any $k\in\mathbb{N},$ it holds that $\displaystyle
0\leq{\mathbf{E}}_{\mathbf{g}}[\gamma(\mathbf{g})^{k}]\leq{\mathbf{E}}_{\mathbf{g}}[f(\mathbf{g})^{k}].$

###### Proof.

Using Proposition 2.11, we know that

$\displaystyle{\mathbf{E}}_{\mathbf{g}}[\gamma(\mathbf{g})^{k}]$
$\displaystyle={\mathbf{E}}\left(\sum_{\emptyset\subsetneq
S\subset[d]}\widehat{\sigma}^{2}(S)\omega_{S}(\mathbf{g})\right)^{k}$
$\displaystyle=\sum_{S_{1},S_{2},\ldots,S_{k}}\widehat{\sigma}^{2}(S_{1})\widehat{\sigma}^{2}(S_{2})\cdots\widehat{\sigma}^{2}(S_{k}){\mathbf{E}}[\omega_{S_{1}}(\mathbf{g})\omega_{S_{2}}(\mathbf{g})\cdots\omega_{S_{k}}(\mathbf{g})].$

Now, observe that
${\mathbf{E}}[\omega_{S_{1}}(\mathbf{g})\omega_{S_{2}}(\mathbf{g})\cdots\omega_{S_{k}}(\mathbf{g})]$
takes only values $0$ and 1, which immediately implies non-negativity of
${\mathbf{E}}[\gamma^{k}].$ Let $\mathcal{ECV}$ be the set of $k$-tuples
$(S_{1},S_{2},\ldots,S_{k})$ on which it is 1 (this is the set of even
covers). Using that $|\widehat{\sigma}^{2}(S)|\leq
B_{|S|}^{2}\binom{d}{|S|}^{-1}$ holds for all $S\neq\emptyset$ by the
definition of $B_{i},$ we conclude that

$\begin{split}{\mathbf{E}}_{\mathbf{g}}[\gamma(\mathbf{g})^{k}]&=\sum_{(S_{1},S_{2},\ldots,S_{k})\in\mathcal{ECV}}\widehat{\sigma}^{2}(S_{1})\widehat{\sigma}^{2}(S_{2})\cdots\widehat{\sigma}^{2}(S_{k})\\\
&\leq\sum_{(S_{1},S_{2},\ldots,S_{k})\in\mathcal{ECV}}\frac{B_{|S_{1}|}^{2}}{\binom{d}{|S_{1}|}}\frac{B_{|S_{2}|}^{2}}{\binom{d}{|S_{2}|}}\cdots\frac{B_{|S_{k}|}^{2}}{\binom{d}{|S_{k}|}}={\mathbf{E}}_{\mathbf{g}}[f(\mathbf{g})^{k}].\end{split}$
(6)

The last equality holds for the same reason as the first one in Eq. 6. ∎

Since $f$ is symmetric, we can express it in a more convenient way as a
weighted sum of the elementary symmetric polynomials $e_{i}.$ That is,

$f(\mathbf{g})=\sum_{i=1}^{d}\frac{B_{i}^{2}}{\binom{d}{i}}e_{i}(\mathbf{g}).$
(7)

Note that if $\sigma$ is symmetric, we have not incurred any loss at this step
since $\gamma=f.$ Moving forward, we will actually bound the $L_{k}$-norms of
$f,$ i.e. use the fact that
${\mathbf{E}}[f^{k}]\leq{\mathbf{E}}[|f|^{k}]=\left\lVert
f\right\rVert_{k}^{k}.$ There is no loss in doing so when $k$ is even. One can
also show that there is no loss (beyond a constant factor in the KL bound in
Theorem 3.1) for $k$ odd as well due to the positivity of
${\mathbf{E}}[f^{k}].$ Considering the expression in Eq. 4, we have

$\begin{split}{\mathbf{E}}_{(x,y)\sim\mathcal{D}\times\mathcal{D}}\left[\left(1+\frac{\gamma(\mathbf{x},\mathbf{y})}{p(1-p)}\right)^{k}\right]=\sum_{t=0}^{k}\binom{k}{t}\frac{{\mathbf{E}}_{\mathbf{g}\sim\mathsf{Unif}(\\{\pm
1\\}^{d})}[\gamma(\mathbf{g})^{k}]}{p^{t}(1-p)^{t}}&=1+\sum_{t\geq
2}\binom{k}{t}\frac{{\mathbf{E}}[\gamma^{k}]}{p^{t}(1-p)^{t}}\\\ &\leq
1+\sum_{t\geq 2}\binom{k}{t}\frac{{\mathbf{E}}[f^{k}]}{p^{t}(1-p)^{t}}\\\
&\leq 1+\sum_{t\geq 2}\binom{k}{t}\frac{\left\lVert
f\right\rVert_{k}^{k}}{p^{t}(1-p)^{t}},\end{split}$ (8)

where we used that ${\mathbf{E}}[\gamma]=\widehat{\gamma}(\emptyset)=0$ by
Proposition 2.11.

###  3.2 Splitting into Elementary Symmetric Polynomials

Our next step is to use a convexity argument to show that when bounding Eq. 8,
we simply need to consider the case when all the mass is distributed on
constantly many levels. The key idea is to view Eq. 8 as a function of the
coefficients on different levels. To do so, define

$h(W^{1},W^{2},\ldots,W^{d}):=1+\sum_{t\geq
2}\binom{k}{t}p^{-t}(1-p)^{-t}\left\lVert\sum_{i=1}^{d}\frac{W^{i}}{\binom{d}{i}}e_{i}(\mathbf{g})\right\rVert^{k}_{k}.$

Clearly, $(B^{2}_{1},B^{2}_{2},\ldots,B^{2}_{d})=(W^{1},W^{2},\ldots,W^{d})$
corresponds to $f$ and $h(B_{1}^{2},B_{2}^{2},\ldots,B_{d}^{2})$ is the
expression in the last line of Eq. 8. The high-level idea is that $h$ is
convex and, thus, its maximum on a convex polytope is attained at a vertex of
a polytope. We will construct polytopes in such a way that vertices correspond
to specific vectors of constant sparsity.

######  Proposition 3.3.

The function $h$ is convex.

###### Proof.

We simply show that $h$ is a composition of convex functions. First, for any
$t,$

$\displaystyle({W}^{i})_{i\in[d]}\longrightarrow\bigg{\|}\sum_{i=1}^{d}\frac{{W}^{i}}{\binom{d}{i}}e_{i}(g)\bigg{\|}_{t}$

is convex. Indeed, for any $\alpha\in[0,1]$ and vectors
$({W}_{1}^{i})_{i\in[d]}$ and $({W}_{2}^{i})_{i\in[d]},$ we have

$\displaystyle\bigg{\|}{\sum_{i\in[d]}\frac{\alpha{W}_{1}^{i}+(1-\alpha){W}_{2}^{i}}{\binom{d}{i}}e_{i}}\bigg{\|}_{t}$
$\displaystyle\leq\bigg{\|}{\alpha\sum_{i\in[d]}\frac{{W}_{1}^{i}}{\binom{d}{i}}e_{i}}\bigg{\|}_{t}+\bigg{\|}{(1-\alpha)\sum_{i\in
I[d]}\frac{{W}_{2}^{i}}{\binom{d}{i}}e_{i}}\bigg{\|}_{t}$
$\displaystyle=\alpha\bigg{\|}{\sum_{i\in[d]}\frac{{W}_{1}^{i}}{\binom{d}{i}}e_{i}}\bigg{\|}_{t}+(1-\alpha)\bigg{\|}{\sum_{i\in[d]}\frac{{W}_{2}^{i}}{\binom{d}{i}}e_{i}}\bigg{\|}_{t},$

by convexity of norms. Since $x\longrightarrow x^{t}$ for $t\geq 2$ is
increasing and convex on $[0,+\infty),$ it follows that
$\displaystyle({W}^{i})_{i\in
I}\longrightarrow\bigg{\|}{\sum_{i\in[d]}\frac{{W}^{i}}{\binom{d}{i}}e_{i}(g)}\bigg{\|}^{t}_{t}$
is also convex. Thus, $h$ is convex as a linear combination with positive
coefficients of convex functions. ∎

Now, we will define suitable polytopes on which to apply the convexity
argument as follows. For any partition size $\Xi\in[d],$ partition
$\mathbf{I}=(I_{\xi})_{\xi=1}^{\Xi}$ of $[d]$ into $\Xi$ disjoint sets, and
non-negative vector $\mathbf{w}=(w_{\xi})_{\xi=1}^{\Xi},$ define the following
product of simplices $\Delta_{\mathbf{I},\mathbf{w}}.$ It is given by
$0\leq{W}^{i}$ for all $i\in[d]$ and $\sum_{i\in I_{\xi}}{W}^{i}\leq w_{\xi}$
for all $\xi\in[\Xi].$ Using convexity of $h$ on
$\Delta_{\mathbf{I},\mathbf{w}},$ we reach the following conclusion.

######  Corollary 3.4.

For any $\Delta_{\mathbf{I},\mathbf{w}}$ defined as just above,

$\sup_{({W}^{i})_{i=1}^{d}\in\Delta_{\mathbf{I},\mathbf{w}}}h\left(({W}^{i})_{i=1}^{d}\right)\leq\sup_{i_{\xi}\in
I_{\xi}\;\forall\xi\in[\Xi]}1+\sum_{t=2}^{k}\binom{k}{t}\frac{\Xi^{t}}{p^{t}(1-p)^{t}}\bigg{(}\sum_{\xi\in[\Xi]}\bigg{\|}{\frac{w_{\xi}}{\binom{d}{i_{\xi}}}e_{i_{\xi}}}\bigg{\|}_{t}^{t}\bigg{)}.$

###### Proof.

Since $h$ is convex by the previous theorem, its supremum over the convex
polytope $\Delta_{\mathbf{I},\mathbf{w}}$ is attained at a vertex. Vertices
correspond to vectors $({V}^{i})_{i=1}^{d}$ of the following type. For each
$\xi\in[\Xi],$ there exists a unique index $i_{\xi}\in I_{\xi}$ such that
$V^{i_{\xi}}\neq 0$ and, furthermore, $V^{i_{\xi}}=w_{\xi}.$ Thus,

$\sup_{({W}^{i})_{i=1}^{d}\in\Delta_{\mathbf{I},\mathbf{w}}}h\left(({W}^{i})_{i=1}^{d}\right)\leq\sup_{i_{\xi}\in
I_{\xi}\;\forall\xi\in[\Xi]}1+\sum_{t=2}^{k}\binom{k}{t}p^{-t}(1-p)^{-t}\bigg{\|}{\sum_{\xi\in[\Xi]}\frac{w_{\xi}}{\binom{d}{i_{\xi}}}e_{i_{\xi}}}\bigg{\|}_{t}^{t}.$

Using triangle inequality and the simple inequality
$(\sum_{\xi\in[\Xi]}u_{\xi})^{t}\leq\Xi^{t}\sum_{\xi\in[\Xi]}u^{t}_{\xi}$ for
non-negative reals $u_{\xi},$ we complete the proof

$\bigg{\|}{\sum_{\xi\in[\Xi]}\frac{w_{\xi}}{\binom{d}{i_{\xi}}}e_{i_{\xi}}}\bigg{\|}^{t}_{t}\leq\bigg{(}\sum_{\xi\in[\Xi]}\bigg{\|}{\frac{w_{\xi}}{\binom{d}{i_{\xi}}}e_{i_{\xi}}}\bigg{\|}_{t}\bigg{)}^{t}\leq\Xi^{t}\sum_{\xi\in[\Xi]}\bigg{\|}{\frac{w_{\xi}}{\binom{d}{i_{\xi}}}e_{i_{\xi}}}\bigg{\|}^{t}_{t}.\qed$

Given the statement of Theorem 3.1, it should be no surprise that we will
apply the intervals$I_{1},I_{2},\ldots,I_{2m+3}$ defined right after Theorem
3.1. In doing so, however, we will need to bound the norms of elementary
symmetric polynomials which appear in Corollary 3.4. This is our next step.

###  3.3 Moments of Elementary Symmetric Polynomials

When dealing with norms of low-degree polynomials, one usually applies Theorem
2.7 for $q=2$ due to the simplicity of the formula for second moments. If we
directly apply this inequality in our setup, however, we obtain

$\displaystyle\left\lVert
e_{i}(g)\right\rVert_{t}\leq\left\lVert(t-1)^{i/2}e_{i}(g)\right\rVert_{2}=(t-1)^{i/2}\binom{d}{i}^{1/2}.$

This inequality becomes completely useless for our purposes when we consider
large values of $i.$ Specifically, suppose that $i=d/2.$ Then, this bound
gives $(t-1)^{d/4}2^{\Theta(d)},$ which is too large if $t=\omega(1),$ since

$\left\lVert e_{i}(\mathbf{g})\right\rVert_{t}\leq\left\lVert
e_{i}(\mathbf{g})\right\rVert_{\infty}\leq\binom{d}{i}\leq 2^{d}.$

Even though the $L_{\infty}$ bound is already much better, it is still
insufficient for our purposes. Instead, we obtain the following better bounds
in Theorem 3.5. To the best of our knowledge, the second of them is novel.

######  Theorem 3.5.

Suppose that $d$ and $t$ are integers such that $d>2te$ and $t>1.$ Take any
$s\in[0,d]$ and define $\mathsf{sm}(s)=\min(s,d-s).$ Then, we have the
following bounds:

  * •

For any $s,$

$\left\lVert
e_{s}\right\rVert_{t}\leq\binom{d}{s}^{1/2}(t-1)^{\frac{\mathsf{sm}(s)}{2}}.$

  * •

If, furthermore, $\mathsf{sm}(s)\geq\frac{d}{2te},$ then

$\left\lVert
e_{s}\right\rVert_{t}\leq\binom{d}{s}\exp\left(-\frac{d}{4te}\right).$

Finally, this second bound is tight up to constants in the exponent.

###### Proof.

First, we show that we can without loss of generality assume $s\leq d/2$ and,
hence, $\mathsf{sm}(s)=s.$ Indeed, note that for any function $q$ on the
hypercube and any character $\omega_{T},$ clearly $\left\lVert
q\omega_{T}\right\rVert_{k}={\mathbf{E}}[|q\omega_{T}|^{k}]^{1/k}={\mathbf{E}}[|q|^{k}]^{1/k}=\left\lVert
q\right\rVert_{k}.$ Thus,

$\left\lVert
e_{s}\right\rVert_{t}=\Big{\|}{\omega_{[d]}\sum_{S\;:\;|S|=s}\omega_{S}}\Big{\|}_{t}=\Big{\|}{\omega_{[d]}\sum_{S\;:\;|S|=s}\omega_{S}}\Big{\|}_{t}=\Big{\|}{\sum_{S\;:\;|S|=s}\omega_{\bar{S}}}\Big{\|}_{t}=\left\lVert
e_{d-s}\right\rVert_{t}.$

With this, we are ready to prove the first bound, which simply uses the
hypercontractivity inequality Theorem 2.7. Indeed, when $s<d/2,$

$\left\lVert e_{s}\right\rVert_{t}\leq\sqrt{t-1}^{s}\left\lVert
e_{s}\right\rVert_{2}=(t-1)^{\frac{\mathsf{sm}(s)}{2}}\binom{d}{s}^{1/2}.$

We now proceed to the much more interesting second bound. Suppose that
$s\geq\frac{d}{2et}$ and chose $\psi$ such that $s-\psi=\frac{d}{2et}$ (for
notational simplicity, we assume $\frac{d}{2et}$ is an integer). The problem
of directly applying Theorem 2.7 is that the degree $s$ of the polynomial
$e_{s}$ is too high. We reduce the degree as follows.

$\displaystyle\left\lVert e_{s}\right\rVert_{t}$
$\displaystyle=\Big{\|}{\sum_{S\;:\;|S|=t}\omega_{S}}\Big{\|}_{t}$
$\displaystyle=\bigg{\|}{\sum_{T\;:\;|T|=\psi}\sum_{A\;:\;|A|=s-\psi,A\cap
T=\emptyset}\omega_{A\cup T}\binom{s}{\psi}^{-1}}\bigg{\|}_{t}$
$\displaystyle\leq\sum_{T\;:\;|T|=\psi}\bigg{\|}{\sum_{A\;:\;|A|=s-\psi,A\cap
T=\emptyset}\omega_{A}\omega_{T}\binom{s}{\psi}^{-1}}\bigg{\|}_{t}$
$\displaystyle=\sum_{T\;:\;|T|=\psi}\bigg{\|}{\sum_{A\;:\;|A|=s-\psi,A\cap
T=\emptyset}\omega_{A}\binom{s}{\psi}^{-1}}\bigg{\|}_{t}.$

We used the following facts. Each $S$ can be represented in $\binom{s}{\psi}$
ways as $A\cup T,$ where $A$ and $T$ are disjoint and $|T|=\psi.$ Second, as
$A$ and $T$ are disjoint, $\omega_{A\cup T}=\omega_{A}\omega_{T}.$ Finally, we
used that for any polynomial $q,$
$\left\lVert\omega_{T}q\right\rVert_{t}=\left\lVert q\right\rVert_{t}.$ Now,
as the polynomial in the last equation is of degree $s-\psi=\frac{d}{2et},$
which is potentially much smaller than $s,$ we can apply Theorem 2.7 followed
by Paresval’s identity to obtain

$\displaystyle\sum_{T\;:\;|T|=\psi}\bigg{\|}{\sum_{A\;:\;|A|=s-\psi,A\cap
T=\emptyset}\omega_{A}\binom{s}{\psi}^{-1}}\bigg{\|}_{t}$
$\displaystyle\leq\sum_{T\;:\;|T|=\psi}(t-1)^{\frac{s-\psi}{2}}\bigg{\|}{\sum_{A\;:\;|A|=s-\psi,A\cap
T=\emptyset}\omega_{A}\binom{s}{\psi}^{-1}}\bigg{\|}_{2}$
$\displaystyle=\sum_{T\;:\;|T|=\psi}(t-1)^{\frac{s-\psi}{2}}\sqrt{\sum_{A\;:\;|A|=s-\psi,A\cap
T=\emptyset}\binom{s}{\psi}^{-2}}$
$\displaystyle=\sum_{T\;:\;|T|=\psi}(t-1)^{\frac{s-\psi}{2}}\sqrt{\binom{d-\psi}{s-\psi}\binom{s}{\psi}^{-2}}_{2}$
$\displaystyle=\binom{d}{\psi}(t-1)^{\frac{s-\psi}{2}}\sqrt{\binom{d-\psi}{s-\psi}\binom{s}{\psi}^{-2}}_{2}$
$\displaystyle=\binom{d}{s}\sqrt{(t-1)^{s-\psi}\binom{d}{\psi}^{2}\binom{d-\psi}{s-\psi}\binom{s}{\psi}^{-2}\binom{d}{s}^{-2}}.$

We now use the simple combinatorial identity that
$\displaystyle\binom{d}{\psi}\binom{d-\psi}{s-\psi}=\binom{s}{\psi}\binom{d}{s}.$
One can either prove it by expanding the factorials or note that both sides of
the equation count pairs of disjoint subsets $(T,A)$ of $[d]$ such that
$|T|=\psi,|A|=s-\psi.$ In other words, we have

$\displaystyle\binom{d}{s}\sqrt{(t-1)^{s-\psi}\binom{d}{\psi}^{2}\binom{d-\psi}{s-\psi}\binom{s}{\psi}^{-2}\binom{d}{s}^{-2}}$
$\displaystyle=\binom{d}{s}\sqrt{(t-1)^{s-\psi}\binom{d-\psi}{s-\psi}^{-1}}\leq\binom{d}{s}\sqrt{(t-1)^{s-\psi}\left(\frac{d-\psi}{s-\psi}\right)^{-(s-\psi)}}$
$\displaystyle=\binom{d}{s}\left(\frac{(t-1)(s-\psi)}{d-\psi}\right)^{\frac{s-\psi}{2}}\leq\binom{d}{s}\left(\frac{2t(s-\psi)}{d}\right)^{\frac{s-\psi}{2}}=\binom{d}{s}\exp\left(-\frac{d}{4et}\right),$

as desired. Above, we used the bounds
$\displaystyle\binom{d-\psi}{s-\psi}\geq\left(\frac{d-\psi}{s-\psi}\right)^{(s-\psi)}$
and $d-\psi\geq d-s\geq d/2,$ and the choice of $\psi$ given by $\displaystyle
s-\psi=\frac{d}{2et}.$ With this, the proof of the bounds is complete.

All that remains to show is the tightness of the second bound. Note, however,
that ${\mathbf{P}}[e_{s}(\mathbf{g})=\binom{d}{s}]=\frac{1}{2^{d}}$ as this
event happens when $\mathbf{g}_{i}=1$ holds for all $i.$ Therefore,

$\left\lVert
e_{s}\right\rVert_{t}\geq\left(\frac{1}{2^{d}}\binom{d}{s}^{t}\right)^{1/t}=\binom{d}{s}2^{d/t}=\binom{d}{s}\exp\left(-O\left(\frac{d}{t}\right)\right).\qed$

We make the following remarks about generalizing the inequality above. They
are of purely theoretical interest as we do not need the respective
inequalities in the paper.

######  Remark 3.6.

The exact same bounds and proof also work if we consider weighted versions
with coefficients in $[-1,1].$ That is, polynomials of the form

$q(\mathbf{g})=\sum_{S\;:\;|S|=s}\varepsilon_{S}\omega_{S}(\mathbf{g}),$

where $\varepsilon_{S}\in[-1,1]$ holds for each $S.$ This suggests that as
long as $q$ has a small spectral infinity norm (i.e., uniform small bound on
the absolute values of its Fourier coefficients), one can improve the
classical theorem Theorem 2.7. We are curious whether this phenomenon extends
beyond polynomials which have all of their weight on a single level.

######  Remark 3.7.

When $\frac{d}{2et}<s<\frac{d}{2},$ the same inequality with the exact same
proof also holds when we evaluate $e_{s}$ at other random vectors such as
standard Gaussian $\mathcal{N}(0,I_{d})$ and the uniform distribution on the
sphere since analogous inequalities to Theorem 2.7 hold (see [SA17,
Proposition 5.48, Remark 5.50]).

###  3.4 Putting It All Together

Finally, we combine all of what has been discussed so far to prove our main
technical result.

###### Proof of Theorem 3.1.

First, we note that without loss of generality, we can make the following
assumptions:

  1. 1.

$B^{4}_{1}=O_{m}(\frac{dp^{2}(1-p)^{2}}{n^{3}}),$

  2. 2.

$B^{4}_{d-1}=O_{m}(\frac{dp^{2}(1-p)^{2}}{n^{3}}),$

  3. 3.

$B^{4}_{d}=O_{m}(\frac{p^{2}(1-p)^{2}}{n^{3}}),$

  4. 4.

$D^{2}=O_{m}\left(\exp(\frac{d}{2en})\times\frac{p^{2}(1-p)^{2}}{n^{3}}\right).$

Indeed, if one of those assumptions is violated, the bound on the KL-
divergence that we are trying to prove is greater than 2 (for appropriate
hidden constants depending only on $m$). The resulting bound on total
variation via Pinsker’s inequality is more than 1 and is, thus, trivial.

We now proceed to apply Corollary 3.4 with the intervals
$I_{1},I_{2},\ldots,I_{2m+3}$ and the following weights.

  * •

$I_{u}=\\{u\\}$ and $w_{u}=B_{u}^{2}$ for $u\in[m],$

  * •

$I_{m+u}=\\{d-u\\}$ and $w_{m+u}=B_{d-u}^{2}$ for $u\in[m],$

  * •

$I_{2m+1}=[m+1,\frac{d}{2en}]\cup[d-\frac{d}{2en},d-m-1]$ and
$w_{2m+1}=C_{m},$

  * •

$I_{2m+2}=[\frac{d}{2en},d-\frac{d}{2en}]$ and $w_{2m+2}=D,$

  * •

$I_{2m+3}=\\{d\\}$ and $w_{2m+3}=B_{d}^{2}.$

The defined weights vector $\mathbf{w}$ exactly bounds the weight of $f$ on
each respective level. Thus, the supremum of $h$ over
$\Delta_{\mathbf{I},\mathbf{w}}$ is at least as large as the expression in Eq.
8 which gives an upper bound on the total variation between the two random
graph models of interest. Explicitly, using Eq. 4 and Corollary 3.4, we find

$\displaystyle
1+\sum_{t=2}^{k}\binom{k}{t}p^{-t}(1-p)^{-t}{\mathbf{E}}[\gamma^{t}]$
$\displaystyle\leq 1+\sum_{t=2}^{k}\binom{k}{t}p^{-t}(1-p)^{-t}\left\lVert
f\right\rVert_{t}^{t}$ $\displaystyle\leq 1+\sup_{i_{u}\in I_{u}\;\forall
u\in[2m+3]}\sum_{u\in[2m+3]}\sum_{t=2}^{k}\binom{k}{t}p^{-t}(1-p)^{-t}(2m+3)^{t}\bigg{\|}{\frac{w_{u}}{\binom{d}{u}}e_{i_{u}}}\bigg{\|}_{t}^{t}.$

We now consider different cases based on $u$ in increasing order of
difficulty.

##### Case 1)

When $u=2m+3.$ Then, $i_{u}=d,$ so $\left\lVert
e_{i_{u}}\right\rVert_{t}=\left\lVert e_{d}\right\rVert_{t}=1.$ We have

$\displaystyle\sum_{t=2}^{k}\binom{k}{t}p^{-t}(1-p)^{-t}(2m+3)^{t}\left\lVert
w_{u}e_{i_{u}}\right\rVert_{t}^{t}$
$\displaystyle=\sum_{t=2}^{k}\binom{k}{t}p^{-t}(1-p)^{-t}(2m+3)^{t}B_{d}^{2t}$
$\displaystyle=(1+\psi)^{k}-1-k\psi,$

where
$\displaystyle\psi=\frac{2m+3}{p(1-p)}B^{2}_{d}=o\left(\frac{1}{n}\right)=o\left(\frac{1}{k}\right)$
by the assumption on $B_{d}$ at the beginning of the proof. It follows that

$(1+\psi)^{k}-1-k\psi\leq e^{1+\psi k}-1-\psi k=O(\psi^{2}k^{2}).$

Thus, for $u=2m+3,$

$\begin{split}&\sum_{t=2}^{k}\binom{k}{t}p^{-t}(1-p)^{-t}(2m+3)^{t}\left\lVert
w_{u}e_{i_{u}}\right\rVert_{t}^{t}=O_{m}\left(k^{2}\frac{B_{d}^{4}}{p^{2}(1-p)^{2}}\right).\end{split}$
(9)

##### Case 2)

When $u=2m+2.$ We bound
$\sum_{t=2}^{k}\binom{k}{t}p^{-t}(1-p)^{-t}(2m+3)^{t}\left\lVert\frac{w_{2m+2}}{\binom{d}{i_{2m+2}}}e_{i_{2m+2}}\right\rVert^{t}_{t}.$
Note that for $i_{u}\in I_{2m+2},$ we have $\mathsf{sm}(i)\geq\frac{d}{2ne}.$
Thus, $\left\lVert e_{i_{u}}\right\rVert_{t}\leq\left\lVert
e_{i_{u}}\right\rVert_{n}\leq\binom{d}{i_{u}}\exp(-\frac{d}{4en})$ by Theorem
3.5. It follows that

$\displaystyle\sum_{t=2}^{k}\binom{k}{t}p^{-t}(1-p)^{-t}(2m+3)^{t}\frac{D^{t}}{\binom{d}{i_{u}}^{t}}\left\lVert
e_{i_{u}}\right\rVert_{t}^{t}$
$\displaystyle\leq\sum_{t=2}^{k}\binom{k}{t}p^{-t}(1-p)^{-t}(2m+3)^{t}\frac{D^{t}}{\binom{d}{i_{u}}^{t}}\binom{d}{i_{u}}^{t}\exp\left(-\frac{dt}{4en}\right)$
$\displaystyle=\left(1+\frac{D(2m+3)}{p(1-p)}\exp\left(-\frac{d}{4en}\right)\right)^{k}-1-k\frac{D(2m+3)}{p(1-p)}\exp\left(-\frac{d}{4en}\right).$

Note, however, that

$\psi:=\frac{D(2m+3)}{p(1-p)}\exp\left(-\frac{d}{4en}\right)=o\left(\frac{1}{n}\right)$

by the assumption on $D$ at the beginning of the proof. It follows that

$(1+\psi)^{k}-1-\psi k=O(\psi^{2}k^{2}).$

Thus, for $u=2m+2,$

$\displaystyle\sum_{t=2}^{k}\binom{k}{t}p^{-t}(1-p)^{-t}(2m+3)^{t}\bigg{\|}{\frac{w_{2m+2}}{\binom{d}{i_{u}}}e_{i_{u}}}\bigg{\|}^{t}_{t}=O_{m}\left(\frac{D^{2}}{p^{2}(1-p)^{2}}\exp\Big{(}-\frac{d}{2en}\Big{)}\right)$

for a large enough hidden constant depending only on $m.$

##### Case 3)

When $u=2m+1.$ Again, we assume without loss of generality that $i_{u}\leq
d/2$ and we want to bound

$\sum_{t=2}^{k}\binom{k}{t}p^{-t}(1-p)^{-t}(2m+3)^{t}\bigg{\|}{\frac{w_{2m+1}}{\binom{d}{i_{2m+1}}}e_{i_{u}}}\bigg{\|}_{t}^{t}.$

Using Theorem 3.5, we know that $\displaystyle\left\lVert
e_{i_{2m+1}}\right\rVert_{t}\leq\binom{d}{i_{2m+1}}^{1/2}(t-1)^{\frac{i_{2m+1}}{2}},$
so

$\displaystyle\sum_{t=2}^{k}\binom{k}{t}p^{-t}(1-p)^{-t}(2m+3)^{t}\frac{C_{m}^{t}}{\binom{d}{i_{2m+1}}^{t}}\left\lVert
e_{i_{2m+1}}\right\rVert_{t}^{t}$
$\displaystyle\leq\sum_{t=2}^{k}\binom{k}{t}p^{-t}(1-p)^{-t}(2m+3)^{t}\frac{C_{m}^{t}}{\binom{d}{i_{2m+1}}^{t}}\binom{d}{i_{2m+1}}^{t/2}(t-1)^{i_{2m+1}t/2}.$

This time we show exponential decay in the summands. More concretely, we prove
the following inequality

$\binom{k}{t}\left(\frac{(2m+3)C_{m}}{p(1-p)\binom{d}{i_{2m+1}}^{1/2}}\right)^{t}(t-1)^{i_{2m+1}t/2}\geq\frac{e}{2}\binom{k}{t+1}\left(\frac{(2m+3)C_{m}}{p(1-p)\binom{d}{i_{2m+1}}^{1/2}}\right)^{t+1}t^{i_{2m+1}(t+1)/2}\,.$

This reduces to showing that

$\displaystyle\binom{d}{i_{2m+1}}^{1/2}\geq\frac{(2m+3)e}{2}\frac{k-t}{t+1}\frac{C_{m}}{p(1-p)}t^{i_{2m+1}/2}\left(\frac{t}{t-1}\right)^{ti_{2m+1}/2}.$

Using that $\left(\frac{t}{t-1}\right)^{t}\leq
4,\binom{d}{i_{2m+1}}\geq\left(\frac{d}{i_{2m+1}}\right)^{i_{2m+1}},$ and
$n\geq k-t\geq k,$ we simply need to prove that

$\begin{split}\left(\frac{d}{i_{2m+1}}\right)^{i_{2m+1}/2}\geq\frac{(2m+3)e}{2}n\frac{C_{m}}{p(1-p)}t^{i_{2m+1}/2-1}4^{i_{2m+1}/2}.\end{split}$
(10)

Since $t\leq k\leq n,$ the right-hand side is maximized when $t=n,$ so we
simply need to show that

$\displaystyle\left(\frac{d}{i_{2m+1}}\right)^{i_{2m+1}/2}$
$\displaystyle\geq\frac{(2m+3)e}{2}n^{i_{2m+1}/2}4^{i_{2m+1}/2}\frac{C_{m}}{p(1-p)}\Longleftrightarrow$
$\displaystyle d$ $\displaystyle\geq i_{2m+1}\times n\times
4\times\left(\frac{(2m+3)eC_{m}}{2p(1-p)}\right)^{\frac{2}{i_{2m+1}}}.$

Now, the right-hand side has form $KxM^{\frac{1}{x}}:=Z(x)$ for $x=i_{2m+1}.$
The derivative of $\log Z(x)$ is $\frac{1}{x}(1-\frac{1}{x}\log M),$ which has
at most one positive root, at $x=\log M.$ Thus, the maximum of $Z(x)$ on
$[m+1,\frac{d}{2en}]$ is at either $m+1$ or $\frac{d}{2en}.$ Substitution at
these values, we obtain the following expressions for the right-hand side.
First, when $i_{2m+1}=m+1,$

$O_{m}\left(n\times\left(\frac{C_{m}}{p(1-p)}\right)^{\frac{2}{m+1}}\right)\leq
d,$

where the inequality holds from the assumptions in the theorem for large
enough constant $K_{m}.$ Second, when $i_{2m+1}=\frac{d}{2en},$

$\displaystyle\frac{2}{e}d\times\left(\frac{(2m+3)eC_{m}}{2p(1-p)}\right)^{\frac{4en}{d}}$
$\displaystyle=\frac{2}{e}d\times\left(\frac{(2m+3)e}{2}\right)^{\frac{4en}{d}}\times\left(\left(\frac{C}{p(1-p)}\right)^{\frac{2}{m+1}}\right)^{\frac{en(m+1)}{d}}$
$\displaystyle\leq\frac{2}{e}d\times\left(\frac{(2m+3)e}{2}\right)^{\frac{4en}{d}}\times\left(\frac{1}{K_{m}}\times\frac{d}{n}\right)^{\frac{en(m+1)}{d}}$
$\displaystyle\leq\frac{2}{e}d\times\left(\frac{(2m+3)e}{2}\right)^{\frac{4en}{d}}\times
K_{m}^{-\frac{en(m+1)}{d}}e^{e(m+1)}\,,$

where we used
$\left(\frac{d}{n}\right)^{\frac{n}{d}}\leq\exp(\left(\left(\frac{d}{n}\right)-1\right)\frac{n}{d})\leq
e.$ Now, for a large enough value of $K_{m},$ when $d>K_{m}n,$ the above
expression is at most $d.$ Since the exponential decay holds,

$\displaystyle\sum_{t=2}^{k}\binom{k}{t}p^{-t}(1-p)^{-t}\frac{C_{m}^{t}}{\binom{d}{i_{2m+1}}^{t}}\binom{d}{i_{2m+1}}^{t/2}(t-1)^{i_{2m+1}t/2}$
$\displaystyle=O\left(k^{2}\frac{C_{m}^{2}}{p^{2}(1-p^{2})\binom{d}{i_{2m+1}}}\right)$
$\displaystyle=O_{m}\left(k^{2}\frac{C_{m}^{2}}{p^{2}(1-p^{2})d^{m+1}}\right).$

##### Case 4)

When $u\leq 2m.$ The cases $u\in[2m]\backslash\\{1,m+1\\}$ are handled in the
exact same way as the previous Case 3), except that we use $w_{u}=B_{u}^{2}$
when $u\in[m]$ and $w_{u}=B^{2}_{d-u+m}$ when $u\in[m+1,2m]$ instead of
$w_{u}=C_{m}.$ The only subtlety occurs when $i_{u}\in\\{1,d-1\\}.$ Then, the
analogue of Eq. 10 becomes

$d^{1/2}\geq O_{m}\left(n\frac{w_{u}}{p(1-p)}t^{-1/2}\right).$

This time, however, the right-hand side is maximized for $t=2.$ Thus, we need

$d=\Omega_{m}\left(n^{2}\frac{w_{u}^{2}}{p^{2}(1-p)^{2}}\right),$

which is satisfied by the assumption made in the beginning of the proof.

Combining all of these cases, we obtain that for any fixed $k,$

$\displaystyle
1+\sum_{t=2}^{k}\binom{k}{t}p^{-t}(1-p)^{-t}{\mathbf{E}}[\gamma^{t}]$
$\displaystyle=1+O_{m}\Bigg{(}k^{2}\sum_{i=1}^{m}\frac{B_{i}^{4}}{p^{2}(1-p)^{2}d^{i}}+k^{2}\sum_{i=0}^{m}\frac{B_{d-i}^{4}}{p^{2}(1-p)^{2}d^{i}}+k^{2}\frac{C_{m}^{2}}{p^{2}(1-p)^{2}d^{m+1}}+\frac{D^{2}}{p^{2}(1-p)^{2}}\exp\bigg{(}-\frac{d}{en}\bigg{)}\Bigg{)}.$

Thus, the logarithm of this expression is at most

$K_{m}\Bigg{(}k^{2}\sum_{i=1}^{m}\frac{B_{i}^{4}}{p^{2}(1-p)^{2}d^{i}}+k^{2}\sum_{i=0}^{m}\frac{B_{d-i}^{4}}{p^{2}(1-p)^{2}d^{i}}+k^{2}\frac{C_{m}^{2}}{p^{2}(1-p)^{2}d^{m+1}}+k^{2}\frac{D^{2}}{p^{2}(1-p)^{2}}\exp\bigg{(}-\frac{d}{en}\bigg{)}\Bigg{)}$

for an appropriately chosen $K_{m}.$ Summing over $k\in[n-1],$ we arrive at
the desired conclusion. ∎

##  4 Applications of the Main Theorem

As already discussed, part of the motivation behind the current work is to
extend the ongoing effort towards understanding random geometric graphs to
settings in which the connection is not necessarily monotone or symmetric. We
remove the two assumptions separately. Initially, we retain symmetry and
explore the implications of Theorem 3.1 in existing monotone and novel non-
monotone setups. Then, we focus on two specific classes of non-monotone
connections which are obtained via simple modifications of symmetric
connections. These two classes will be of interest later in Section 6 as they
lead to the failure of the commonly used signed-triangle statistic, and in
Section 8.1 as they rigorously demonstrate an inefficiency in 1.5. Finally, we
go truly beyond symmetry by studying “typical” dense indicator connections.

###  4.1 Symmetric Connections

Consider Theorem 3.1 for symmetric functions. Then,
$B_{i}^{2}=\mathcal{W}^{i}({\sigma})\leq{\mathbf{Var}}[\sigma]\leq p(1-p).$
Similarly, the inequalities $C_{m}\leq p(1-p),D\leq p(1-p)$ hold. In
particular, this means that as long as $d=\Omega_{m}(n),$ all other conditions
are automatically satisfied. Now, if $d=\Omega(n\log n)$ for a large enough
hidden constant, the exponential term disappears. If we set $m=2,$ the term
$\frac{n^{3}}{p^{2}(1-p)^{2}}\frac{C_{m}^{2}}{d^{m+1}}\leq\frac{n^{3}}{d^{3}}=o_{n}(1)$
also disappears. We have the following corollary.

######  Corollary 4.1.

There exists an absolute constant $K$ with the following property. Suppose
that $d>Kn\log n.$ Let $\sigma:\\{\pm 1\\}^{d}\longrightarrow[0,1]$ be a
symmetric connection. Then,

$\displaystyle{\mathsf{KL}}(\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma)\|\mathsf{G}(n,p))$
$\displaystyle\quad=O\left(\frac{n^{3}\mathcal{W}^{d}({\sigma})^{2}}{p^{2}(1-p)^{2}}+\frac{n^{3}(\mathcal{W}^{1}({\sigma})^{2}+\mathcal{W}^{d-1}({\sigma})^{2})}{p^{2}(1-p)^{2}d}+\frac{n^{3}(\mathcal{W}^{2}({\sigma})^{2}+\mathcal{W}^{d-2}({\sigma})^{2})}{p^{2}(1-p)^{2}d^{2}}\right)+o(1).$

For symmetric connections in the regime $d=\Omega(n\log n),$ only Fourier
weights on levels $1,2,d-1,d-2,d-1,d$ matter. In Section 4.1.4 we conjecture
how to generalize this phenomenon.

Now, we proceed to concrete applications of Corollary 4.1. In them, we simply
need to bound the weights of $\sigma$ on levels $1,2,d-1,d-2,d.$ All levels
besides $d$ are easy since they have a normalizing term polynomial in $d$ in
the denominator. However, more care is needed to bound
$\mathcal{W}^{d}({\sigma}).$ As we will see in Section 4.1.3, this is not just
a consequence of our proof techniques, but an important phenomenon related to
the “fluctuations” of $\sigma.$ In the forthcoming sections, we use the
following simple bound, the proof of which is deferred to Appendix B.

######  Lemma 4.2.

Suppose that $f:\\{\pm 1\\}^{d}\longrightarrow\mathbb{R}$ is symmetric. Denote
by $f_{i}$ the value of $f$ when exactly $i$ of its arguments are equal to $1$
and the rest are equal to $-1.$ Then,

$|\widehat{f}([d])|\leq\frac{1}{2}{\mathbf{E}}_{j\sim
Bin(d-1,\frac{1}{2})}|f_{j+1}-f_{j}|=O\left(\frac{\sum_{j=1}^{d}|f_{j+1}-f_{j}|}{\sqrt{d}}\right).$

We remark that the quantity $\sum_{j=1}^{d}|f_{j+1}-f_{j}|$ is a direct
analogue of the total variation appearing in real analysis literature [SS05,
p.117], which measures the “fluctuations” of a function. As the name “total
variation” is already taken by a more central object in our paper, we will
call this new quantity fluctuation instead. We denote it by
${\mathsf{Fl}}(f):=\sum_{j=1}^{d}|f_{j+1}-f_{j}|.$ We believe that the
interpretation of $|\widehat{\sigma}([d])|$ as a measure of fluctuations may
be useful in translating our results to the Gaussian and spherical setups when
non-monotone connections are considered. We discuss this in more depth in
Section 4.1.3.

####  4.1.1 Lipschitz Connections

As the main technical tool for our indistinguishability results is 1.5, we
first consider Lipschitz connections to which Racz and Liu originally applied
the claim [LR21a]. We show that their result Theorem 1.4 can be retrieved
using our framework even if one drops the monotonicity assumption. The first
step is to bound $|\widehat{f}([d])|.$

######  Proposition 4.3.

If $f:\\{\pm 1\\}^{d}\longrightarrow\mathbb{R}$ is a symmetric $L$-Lipschitz
function with respect to the Hamming distance, meaning that

$|f(x_{1},x_{2},\ldots,x_{i-1},1,x_{i+1},\ldots,x_{n})-f(x_{1},x_{2},\ldots,x_{i-1},-1,x_{i+1},\ldots,x_{n})|\leq
L$

holds for all $i$ and $x_{1},x_{2},\ldots,x_{i_{1}},x_{i},\ldots,x_{n},$ then
$|\widehat{f}([d])|\leq\frac{L}{2}.$

###### Proof.

The proof is immediate given Lemma 4.2. Note that

$|f_{j+1}-f_{j}|=|f(\underbrace{1,1,\ldots,1}_{j+1},\underbrace{-1,\ldots,-1}_{d-j+1})-f(\underbrace{1,1,\ldots,1}_{j},\underbrace{-1,\ldots,-1}_{d-j})|\leq
L$

holds for all $j.$ ∎

Using this statement, we obtain the following result.

######  Corollary 4.4.

Suppose that $\sigma$ is a symmetric $\frac{1}{r\sqrt{d}}$-Lipschitz
connection. If $d=\omega_{p}(\frac{n^{3}}{r^{4}})$ and $d=\Omega(n\log n),$

${\mathsf{KL}}(\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma)\|\mathsf{G}(n,p))=o(1).$

###### Proof.

We will apply Corollary 4.1. By the well-known bounded difference inequality,
[Han, Claim 2.4] we know that since $\sigma$ is
$\frac{1}{r\sqrt{d}}$-Lipschitz, ${\mathbf{Var}}[\sigma]\leq\frac{1}{r^{2}},$
so each $\mathcal{W}^{i}({\sigma})$ is bounded by $\frac{1}{r^{2}}.$ On the
other hand, $\mathcal{W}^{d}({\sigma})$ is bounded by $\frac{1}{r^{2}d}$ by
Proposition 4.3. It follows that the expression in Corollary 4.1 is bounded by

$O\left(\frac{n^{3}}{dr^{4}}+\frac{n^{3}}{d^{2}r^{4}}+\frac{n^{3}}{d^{2}r^{4}}\right)=o(1).\qed$

The flexibility of our approach allows for a stronger result when the map
$\sigma$ is even.

######  Corollary 4.5.

Suppose that $\sigma$ is a symmetric even $\frac{1}{r\sqrt{d}}$-Lipschitz
connection in the sense that $\sigma(\mathbf{x})=\sigma(-\mathbf{x})$ also
holds. If $d$ is even, $d=\Omega(n\log n),$ and
$d=\omega_{p}(\frac{n^{3/2}}{r^{2}}),$ then

${\mathsf{KL}}\Big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma)\|\mathsf{G}(n,p)\Big{)}=o(1).$

###### Proof.

The proof is similar to the one in the previous proposition. However, we note
that when $\sigma$ is even, all Fourier coefficients on odd levels vanish. In
particular, this holds for levels $1$ and $d-1.$ Thus, the expression
Corollary 4.1 is bounded by

$O\left(\frac{n^{3}}{d^{2}r^{4}}+\frac{n^{3}}{d^{2}r^{4}}\right)=o(1).\qed$

######  Remark 4.6.

The stronger results for even connections observed in this section is a
general phenomenon, which will reappear in the forthcoming results. It is part
of our more general conjecture in Section 4.1.4. We note that the requirement
that $d$ is even is simply needed to simplify exposition. Otherwise, one needs
to additionally bound $\mathcal{W}^{d-1}({\sigma})$ which is a standard
technical task (see Appendix D).

####  4.1.2 Hard Threshold Connections

We now move to considering the classical setup of hard thresholds. Our tools
demonstrate a striking new phenomenon if we make just a subtle twist – by
introducing a “double threshold” – to the original model.

We start with the basic threshold model. Let $\tau_{p}$ be such that
${\mathbf{P}}_{\mathbf{x}\sim\mathsf{Unif}(\\{\pm
1\\}^{d})}[\sum_{i}x_{i}\geq\tau_{p}]=p.$ Let ${\mathbf{T}}_{p}$ be the map
defined by $\mathds{1}\left[\sum_{i=1}^{n}x_{i}\geq\tau_{p}\right].$ Again, we
want to understand the Fourier coefficient on the last level. Using that there
exists a unique $j$ such that $f_{j+1}\neq f_{j}$ for $f={\mathbf{T}}_{p}$ in
Lemma 4.2, in Appendix B we obtain the following bound.

######  Proposition 4.7.

$\widehat{{\mathbf{T}}_{p}}([d])=O\Big{(}\frac{p\sqrt{\log\frac{1}{p}}}{\sqrt{d}}\Big{)}.$

######  Corollary 4.8.

Suppose that $d=\Omega(n\log n),d=\omega(n^{3}p^{2}\log^{2}\frac{1}{p}),$ and
$p=d^{O(1)}.$ Then,

${\mathsf{KL}}\Big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,{\mathbf{T}}_{p})\|\mathsf{G}(n,p)\Big{)}=o(1).$

###### Proof.

From Theorem 2.8, we know that
$\mathcal{W}^{1}({\sigma})=O(p^{2}\log\frac{1}{p}),\mathcal{W}^{d-1}({\sigma})=O(p^{2}\log\frac{1}{p}),$
$\mathcal{W}^{2}({\sigma})=O(p^{2}\log^{2}\frac{1}{p}),$ and
$\mathcal{W}^{d-2}({\sigma})=O(p^{2}\log^{2}\frac{1}{p}).$ From Proposition
4.7, $\mathcal{W}^{d}({\sigma})=O(d^{-1}p^{2}\log\frac{1}{p}).$ Thus, the
expression in Corollary 4.1 becomes

$O\left(\frac{n^{3}p^{2}\log^{2}\frac{1}{p}}{d}+\frac{n^{3}p^{2}\log^{4}\frac{1}{p}}{d^{2}}+\frac{n^{3}p^{2}\log^{2}\frac{1}{p}}{d^{2}}\right)=o(1),$

where we used the fact that $p$ is polynomially bounded in $d.$ ∎

Remarkably, this matches the state of the art result for
$p=\omega(\frac{1}{n})$ of [LMS+22a]. As before, if we consider an even
version of the problem, we obtain a stronger result. Let $\delta_{p}$ be such
an integer that ${\mathbf{P}}[|\sum^{n}_{i=1}x_{i}|\geq\delta_{p}]=p.$
Consider the“double threshold” connection given by the indicator
$\mathbf{D}_{p}(\mathbf{x})=\mathds{1}\left[|\sum^{n}_{i=1}x_{i}|\geq\delta_{p}\right].$
In Appendix B, we prove the following inequality.

######  Proposition 4.9.

$\widehat{\mathbf{D}}_{p}([d])=O\Big{(}\frac{p\sqrt{\log\frac{1}{p}}}{\sqrt{d}}\Big{)}.$

######  Corollary 4.10.

Suppose that $d$ is even, $d=\Omega(n\log
n),d=\omega(n^{3/2}p\log^{2}\frac{1}{p}),$ and $p=d^{O(1)}.$ Then,

${\mathsf{KL}}\Big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\mathbf{D}_{p})\|\mathsf{G}(n,p)\Big{)}=o(1).$

###### Proof.

As in the proof of Corollary 4.5, we simply note that when $d$ is even, the
weights on levels 1 and $d-1$ vanish as $\mathbf{D}_{p}$ is an even map. Thus,
we are left with

$O\left(\frac{n^{3}p^{2}\log^{4}\frac{1}{p}}{d^{2}}+\frac{n^{3}p^{2}\log^{2}\frac{1}{p}}{d^{2}}\right)=o(1).\qed$

Note that the complement of $\mathsf{RAG}(n,\\{\pm 1\\}^{d},p,\mathbf{D}_{p})$
is the random algebraic graph defined with respect to the connection
$\sigma(\mathbf{x}):=\mathds{1}[\sum^{n}_{i=1}x_{i}\in(-\delta_{p},\delta_{p})].$
This random graph is very similar to the one used in [KTW14], where the
authors consider the interval indicator
$\mathds{1}\left[\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle\in[\tau_{1},\tau_{2}]\right],$
albeit with latent space the unit sphere. The utility of interval indicators
in [KTW14] motivates us to ask: What if $\sigma$ is the indicator of a union
of more than one interval?

####  4.1.3 Non-Monotone Connections, Interval Unions, and Fluctuations

To illustrate what we mean by fluctuations, consider first the simple
connection for $\kappa\in[0,1/2],$ given by

$\pi_{\kappa}(\mathbf{x}):=\frac{1}{2}+\kappa\omega_{[d]}(\mathbf{x}).$ (11)

When viewed as a function of the number of ones in $\mathbf{x},$ this function
“fluctuates” a lot for large values of $\kappa.$ Note that $\pi_{\kappa}$ only
takes values ${1}/{2}\pm\kappa$ and alternates between those when a single
coordinate is changed. In the extreme case $\kappa={1}/{2},$ $\pi_{\kappa}$ is
the indicator of all $\mathbf{x}$ with an even number of coordinates equal to
$-1.$ Viewed as a function of $\sum_{i=1}^{d}x_{i},$ this is a union of
$d/2+O(1)$ intervals. A simple application of 1.5 gives the following
proposition.

######  Corollary 4.11.

Whenever ${n\kappa^{4/3}}=o(1),$
$\displaystyle{\mathsf{KL}}\Big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},1/2,\pi_{\kappa}),\mathsf{G}(n,1/2)\Big{)}=o(1).$

###### Proof.

Let $\gamma_{\kappa}$ be the autocorrelation of $\pi_{\kappa}-\frac{1}{2}.$
Clearly, $\gamma_{\kappa}=\kappa^{2}\omega_{[d]}(\mathbf{x}),$ so
${\mathbf{E}}[\gamma_{\kappa}^{t}]=0$ when $t$ is odd and
${\mathbf{E}}[\gamma_{\kappa}^{t}]=\kappa^{2t}$ when $t$ is even. Since
$n\kappa^{2}=o(1)$ holds as ${n\kappa^{4/3}}=o(1),$ we obtain

$\displaystyle\sum_{k=0}^{n-1}\log{\mathbf{E}}\left[\left(1+\frac{\gamma_{\kappa}(\mathbf{x})}{p(1-p)}\right)^{k}\right]$
$\displaystyle\leq\sum_{k=0}^{n-1}\log\left(1+\sum_{t=2}^{k}\binom{k}{t}\frac{\kappa^{2t}}{4^{t}}\right)$
$\displaystyle=\sum_{k=0}^{n-1}\log\left(\left(1+\frac{\kappa^{2}}{4}\right)^{k}-k\frac{\kappa^{2}}{4}\right)$
$\displaystyle=\sum_{k=0}^{n-1}\log\left(1+O\left(k^{2}\frac{\kappa^{4}}{16}\right)\right)=O\left(\sum_{k=0}^{n-1}k^{2}\times\kappa^{4}\right)=O(n^{3}\kappa^{4}),$

from which the claim follows. ∎

We will explore tightness of these bounds later on. The main takeaway from
this example for now is the following - when the connection “fluctuates” more,
it becomes more easily distinguishable. Next, we show that this phenomenon is
more general. Recall the definition of fluctuations ${\mathsf{Fl}}$ from Lemma
4.2. We begin with two simple examples of computing the quantity
${\mathsf{Fl}}.$

######  Example 4.12.

If $\sigma:\\{\pm 1\\}^{d}\longrightarrow[0,1]$ is monotone, then
${\mathsf{Fl}}(\sigma)\leq 1.$ Indeed, this holds as all differences
$f_{i+1}-f_{i}$ have the same sign and, so,
$\sum_{i=0}^{d-1}|f_{i+1}-f_{i}|=|\sum_{i=0}^{d-1}f_{i+1}-f_{i}|=|f_{d}-f_{0}|\leq
1.$

######  Example 4.13.

Suppose that $I=[a_{1},b_{1}]\cup[a_{2},b_{2}]\cup\cdots\cup[a_{s},b_{s}],$
where these are $s$ disjoint intervals with integer endpoints
($b_{i}+1<a_{i+1}$). Then, if
$\sigma(\mathbf{x})=\mathds{1}[\sum_{i=1}^{d}x_{i}\in I],$ it follows that
${\mathsf{Fl}}(f)\leq 2s$ as
$|f_{b_{i}+1}-f_{b_{i}}|=1,|f_{a_{i}}-f_{a_{i}-1}|=1$ and all other marginal
differences equal $0.$

We already saw in Lemma 4.2 that
$|\widehat{f}([d])|=O\left(\frac{{\mathsf{Fl}}(\sigma)}{\sqrt{d}}\right).$
Using the same proof techniques developed thus far, we make the following
conclusion.

######  Corollary 4.14.

Suppose that $\sigma$ is a symmetric connection. Whenever $d=\Omega(n\log n)$
and $\displaystyle
d=\omega\left(\max\left(n^{3}p^{2}\log^{2}\frac{1}{p},n^{3/2}{\mathsf{Fl}}(\sigma)^{2}p^{-1}\right)\right)$
are satisfied,

$\displaystyle{\mathsf{KL}}\Big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma)\|\mathsf{G}(n,p)\Big{)}=o(1).$

If $\sigma$ and $d$ are even, the weaker condition $\displaystyle
d=\omega\left(\max\Big{(}n^{3/2}p\log^{2}\frac{1}{p},n^{3/2}{\mathsf{Fl}}(\sigma)^{2}p^{-1}\Big{)}\right),$
is sufficient to imply $\displaystyle{\mathsf{KL}}\Big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma)\|\mathsf{G}(n,p)\Big{)}=o(1).$

######  Example 4.15.

A particularly interesting case is when $\sigma$ is the indicator of $s$
disjoint intervals as in Example 4.13. We obtain indistinguishability rates by
replacing ${\mathsf{Fl}}(\sigma)$ with $2s$ above. Focusing on the case when
$p=\Omega(1)$ (so that the dependence on the number of intervals is clearer),
we need

$d=\omega(n^{3}+n^{3/2}s^{2})$

for indistinguishability for an arbitrary union of intervals and

$d=\omega(n^{3/2}s^{2})$

for indistinguishability for a union of intervals symmetric with respect to
$0.$

We note that both of these inequalities make sense only when $s=o(\sqrt{d}).$
The collapse of this behaviour at $s\approx\sqrt{d}$ is not a coincidence as
discussed in Remark 6.7.

####  4.1.4 Conjecture for Connections Without Low Degree and High Degree
Terms

We now present the following conjecture, which generalizes the observation
that random algebraic graphs corresponding to connections $\sigma$ satisfying
$\sigma(\mathbf{x})=\sigma(-\mathbf{x})$ are indistinguishable from
$\mathsf{G}(n,p)$ for smaller dimensions $d.$ Let $k\geq 0$ be a constant.
Suppose that the symmetric connection $\sigma:\\{\pm
1\\}^{d}\longrightarrow[0,1]$ satisfies $\mathcal{W}^{i}({\sigma})=0$ whenever
$i<k$ and $\mathcal{W}^{i}({\sigma})=0$ whenever $i>d-k.$ Consider the bound
on the ${\mathsf{KL}}$ divergence between $\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma)$ and $\mathsf{G}(n,p)$ in Theorem 3.1 for $m=k+1.$ Under
the additional assumption $d=\Omega(n\log n),$ it becomes of order

$\frac{n^{3}B^{2}_{m}}{p^{2}(1-p)^{2}d^{m}}+\frac{n^{3}C_{m}}{p^{2}(1-p)^{2}d^{m+1}}\leq\frac{n^{3}{\mathbf{Var}}[\sigma]}{p^{2}(1-p)^{2}d^{m}}+\frac{n^{3}{\mathbf{Var}}[\sigma]}{p^{2}(1-p)^{2}d^{m+1}}=O\left(\frac{n^{3}}{d^{m}}\right).$

In particular, this suggests that whenever $d=\omega(n^{3/m}),$
${\mathsf{KL}}\Big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma)\|\mathsf{G}(n,p)\Big{)}=o(1).$ Unfortunately, in our
methods, there is the strong limitation $d=\Omega(n\log n).$

######  Conjecture 4.16.

Suppose that $m\in\mathbb{N}$ is a constant and $\sigma$ is a symmetric
connection such that the weights on levels
$\\{1,2,\ldots,m-1\\}\cup\\{d-m+1,\ldots,d\\}$ are all equal to 0. If
$d=\tilde{\Omega}(n^{3/m}),$ then

${\mathsf{TV}}\Big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma),\mathsf{G}(n,p)\Big{)}=o(1).$

Unfortunately, our methods only imply this conjecture for $m=\\{1,2,3\\}$ as
can be seen from Theorem 3.1 as we also need $d=\Omega(n\log n).$ In Section
6.1.3, we give further evidence for this conjecture by proving a matching
lower bound. Of course, one should also ask whether there exist non-trivial
symmetric functions satisfying the property that their Fourier weights on
levels $\\{1,2,\ldots,m-1\\}\cup\\{d-m+1,\ldots,d\\}$ are all equal to 0. In
Appendix C, we give a positive answer to this question.

####  4.1.5 Low-Degree Polynomials

We end with a brief discussion of low-degree polynomials, which are a class of
particular interest in the field of Boolean Fourier analysis (see, for
example, [EI22, ODo14]). The main goal of our discussion is to complement
4.16. One could hastily conclude from the conjecture that it is only the “low
degree” terms of $\sigma$ that make a certain random algebraic graph
$\mathsf{RAG}(n,\\{\pm 1\\}^{d},p,\sigma)$ distinct from an Erdős-Rényi graph
for large values of $d.$ This conclusion, however, turns out to be incorrect -
symmetric connections which are low-degree polynomials, i.e. everything is
determined by the low degrees, also become indistinguishable from
$\mathsf{G}(n,p)$ for smaller dimensions $d.$ Thus, a more precise intuition
is that the interaction between low-degree and high-degree is what makes
certain random algebraic graphs $\mathsf{RAG}(n,\\{\pm 1\\}^{d},p,\sigma)$
distinct from Erdős-Rényi graphs for large values of $d.$

######  Corollary 4.17.

Suppose that $k\in\mathbb{N}$ is a fixed constant and $\sigma:\\{\pm
1\\}^{d}\longrightarrow[0,1]$ is a symmetric connection of degree $k.$ If
$d=\Omega(n)$ and
$d=\omega_{k}\left(\min(n^{3}p^{2}\log^{2}\frac{1}{p},np^{-2/3})\right),$ then

${\mathsf{KL}}\Big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma)\|\mathsf{G}(n,p)\Big{)}=o(1).$

###### Proof.

We apply Corollary 4.1 for $m=k$ and obtain

${\mathsf{KL}}\Big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\sigma)\|\mathsf{G}(n,p)\Big{)}=O\left(\frac{n^{3}\mathcal{W}^{1}({\sigma})}{p^{2}(1-p)^{2}d}+\frac{n^{3}\mathcal{W}^{2}({\sigma})}{p^{2}(1-p)^{2}d^{2}}\right).$

Now, we use Corollaries 2.10 and 2.8 to bound the right-hand side in two ways
by, respectively:

$O\left(\frac{n^{3}}{p^{2}(1-p)^{2}d^{3}}\right)\quad\text{and}\quad
O\left(\frac{n^{3}p^{2}\log^{2}\frac{1}{p}}{d}\right).$

The conclusion follows by taking the stronger bound of the two. ∎

###  4.2 Transformations of Symmetric Connections

One reason why Theorem 3.1 is flexible is that it does not explicitly require
$\sigma$ to be symmetric, but only requires a uniform bound on the absolute
values of Fourier coefficients on each level. This allows us, in particular,
to apply it to modifications of symmetric connections. In what follows, we
present two ways to modify a symmetric function such that the claims in
Corollaries 4.4, 4.5, 4.8, 4.10 and 4.14 still hold. The two modifications are
both interpretable and will demonstrate further important phenomena in Section
6.2.

It is far from clear whether previous techniques used to prove
indistinguishability for random geometric graphs can handle non-monotone, non-
symmetric connections. In particular, approaches based on analysing Wishart
matrices ([BDE+14, BBN20]) seem to be particularly inadequate in the non-
symmetric case as the inner-product structure inherently requires symmetry.
The methods of Racz and Liu in [LR21a] on the other hand, exploit very
strongly the representation of connections via CDFs which inherently requires
monotonicity. While our approach captures these more general settings, we will
see in Section 6.2 an example demonstrating that it is unfortunately not
always optimal.

####  4.2.1 Coefficient Contractions of Real Polynomials

Suppose that $f:\\{\pm 1\\}^{d}\longrightarrow\mathbb{R}$ is given. We know
that it can be represented as a polynomial

$f(x_{1},x_{2},\ldots,x_{d})=\sum_{S\subseteq[d]}\widehat{f}(S)\prod_{i\in
S}x_{i}.$

We can extend $f$ to the polynomial
$\tilde{f}:\mathbb{R}^{n}\longrightarrow\mathbb{R},$ also given by

$\tilde{f}(x_{1},x_{2},\ldots,x_{d})=\sum_{S\subseteq[d]}\widehat{f}(S)\prod_{i\in
S}x_{i}.$

Now, for any vector
$\alpha=(\alpha_{1},\alpha_{2},\ldots,\alpha_{d})\in[-1,1]^{d},$ we can
“contract” the coefficients of $\tilde{f}$ by considering the polynomial

$\tilde{f}_{\alpha}(x_{1},x_{2},\ldots,x_{d}):=\tilde{f}(x_{1}\alpha_{1},x_{2}\alpha_{2},\ldots,x_{d}\alpha_{d})=\sum_{S\subseteq[d]}\widehat{f}(S)\prod_{i\in
S}\alpha_{i}\prod_{i\in S}x_{i}.$

Subsequently, this induces the polynomial $f_{\alpha}:\\{\pm
1\\}^{d}\longrightarrow\mathbb{R}$ given by

${f}_{\alpha}(x_{1},x_{2},\ldots,x_{d})=\sum_{S\subseteq[d]}\widehat{f}(S)\prod_{i\in
S}\alpha_{i}\prod_{i\in S}x_{i}.$

This is a “coefficient contraction” since
$|\widehat{f_{\alpha}}(S)|\leq|\widehat{f}(S)|$ clearly holds. Note,
furthermore, that when $\mathbf{g}\in\\{\pm 1\\}^{d},$ clearly
$f_{\mathbf{g}}(\mathbf{x})=f(\mathbf{g}\mathbf{x}).$ In particular, this
means that if $f$ takes values in $[0,1],$ so does $f_{\mathbf{g}}.$ This
turns out to be the case more generally.

######  Observation 4.18.

For any function $f:\\{\pm 1\\}^{d}\longrightarrow[0,1]$ and vector
$\alpha\in[-1,1]^{d},$ $f_{\alpha}$ takes values in $[0,1].$

###### Proof.

Note that the corresponding real polynomials $\tilde{f},\tilde{f}_{\alpha}$
are linear in each variable. Furthermore, the sets
$A=\prod_{i=1}^{d}\left[-|\alpha_{i}|,|\alpha_{i}|\right],B=[-1,1]^{d}$ are
both convex and $A\subseteq B.$ Thus,

$\sup_{\mathbf{x}\in\\{\pm 1\\}^{d}}f_{\alpha}(\mathbf{x})=\sup_{\mathbf{y}\in
B}\tilde{f}_{\alpha}(\mathbf{y})=\sup_{\mathbf{z}\in
A}\tilde{f}(\mathbf{z})\leq\sup_{\mathbf{z}\in
B}\tilde{f}(\mathbf{z})=\sup_{\mathbf{x}\in\\{\pm 1\\}^{d}}f(\mathbf{x})\leq
1.$

In the same way, we conclude that $f_{\alpha}\geq 0$ holds. ∎

In particular, this means that for any $\alpha\in[-1,1]^{d}$ and connection
$\sigma$ on $\\{\pm 1\\}^{d}$, $\sigma_{\alpha}$ is a well-defined connection.
Therefore, all of Corollaries 4.4, 4.5, 4.8, 4.10 and 4.14 hold if we replace
the respective connections in them with arbitrary coefficient contractions of
those connections. As we will see in Section 6.2, particularly interesting is
the case when $\alpha\in\\{\pm 1\\}^{d}$ since this corresponds to simply
negating certain variables in $\sigma.$ In particular, suppose that
$\alpha=(\underbrace{1,1,\ldots,1}_{\ell},\underbrace{-1,-1,\ldots,-1}_{d-\ell})$
for some $1\leq\ell\leq d.$ Then, the connection
$\sigma(\mathbf{x},\mathbf{y})$ becomes a function of

$\sum_{i\leq\ell}x_{i}y_{i}-\sum_{i>\ell}x_{i}y_{i}.$

The corresponding two-form is not PSD, so it is unlikely that approaches based
on Gram-Schmidt and analysing Wishart matrices could yield meaningful results
in this setting.

####  4.2.2 Repulsion-Attraction Twists

Recall that one motivation for studying non-monotone, non-symmetric
connections was that in certain real world settings - such as friendship
formation - similarity in different characteristics might have different
effect on the probability of forming an edge.

To model this scenario, consider the simplest case in which $d=2d_{1}$ and
each latent vector has two components of length $d_{1},$ that is
$\mathbf{x}=[\mathbf{y},\mathbf{z}],$ where $\mathbf{y},\mathbf{z}\in\\{\pm
1\\}^{d_{1}}$ and $[\mathbf{y},\mathbf{z}]$ is their concatenation. Similarity
in the $\mathbf{y}$ part will “attract”, making edge formation more likely,
and similarity in $\mathbf{z}$ will “repulse”, making edge formation less
likely. Namely, consider two symmetric connections $a:\\{\pm
1\\}^{d_{1}}\longrightarrow[0,1]$ and $r:\\{\pm
1\\}^{d_{1}}\longrightarrow[0,1]$ with, say, means $1/2.$ We call the
following function their repulsion-attraction twist

$\rho_{a,r}([\mathbf{y},\mathbf{z}])=\frac{1+a(\mathbf{y})-r(\mathbf{z})}{2}.$

One can check that $\rho_{a,r}$ is, again, a connection with mean $1/2$ and
satisfies
${\mathbf{Var}}[\rho_{a,r}]=\frac{1}{4}({\mathbf{Var}}[a]+{\mathbf{Var}}[r]).$
Furthermore,

$(\rho_{a,r}-{1}/{2})*(\rho_{a,r}-{1}/{2})=(a-1/2)*(a-1/2)+(r-1/2)*(r-1/2).$

Thus, if we denote
$\gamma_{\rho}=\left(\rho_{a,r}-\frac{1}{2}\right)*\left(\rho_{a,r}-\frac{1}{2}\right),\gamma_{a}=(a-1/2)*(a-1/2),\gamma_{r}=(r-1/2)*(r-1/2),$
we have $\gamma_{\rho}=\gamma_{a}+\gamma_{r}.$ Using
$\left\lVert\gamma_{a}+\gamma_{r}\right\rVert_{p}\leq\left\lVert\gamma_{a}\right\rVert_{p}+\left\lVert\gamma_{r}\right\rVert_{p}$
for each $p,$ we can repeat the argument in Theorem 3.1 losing a simple factor
of 2 for $\gamma_{\rho}.$ In particular, this means that when $d=\Omega(n\log
n),$ we have that for any two symmetric connections $a,r,$

$\displaystyle{\mathsf{KL}}\Big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},p,\rho_{a,r})\|\mathsf{G}(n,p)\Big{)}$
$\displaystyle=O\left({n^{3}\mathcal{W}^{d}({a})^{2}}+\frac{n^{3}(\mathcal{W}^{1}({a})^{2}+\mathcal{W}^{d-1}({a})^{2})}{d}+\frac{n^{3}(\mathcal{W}^{2}({a})^{2}+\mathcal{W}^{d-2}({a})^{2})}{d^{2}}\right)$
$\displaystyle+O\left({n^{3}\mathcal{W}^{d}({r})^{2}}+\frac{n^{3}(\mathcal{W}^{1}({r})^{2}+\mathcal{W}^{d-1}({r})^{2})}{d}+\frac{n^{3}(\mathcal{W}^{2}({r})^{2}+\mathcal{W}^{d-2}({r})^{2})}{d^{2}}\right)+o(1).$

as in Corollary 4.1. One can now combine with Corollaries 4.4, 4.5, 4.8, 4.10
and 4.14. As we will see in Section 6.2, particularly interesting from a
theoretical point of view is the case when $a=r.$

One could also consider linear combinations of more than two connections. We
do not pursue this here.

###  4.3 Typical Indicator Connections

Finally, we turn to a setting which goes truly beyond symmetry. Namely, we
tackle the question of determining when a “typical” random algebraic graph
with an indicator connection is indistinguishable from $\mathsf{G}(n,p).$ More
formally, we consider $\mathsf{RAG}(n,\\{\pm 1\\}^{d},\sigma_{A},p_{A})$ for
which $\sigma_{A}(\mathbf{g})=\mathds{1}[\mathbf{g}\in A],$ where $A$ is
sampled from $\mathsf{AnteU}(\\{\pm 1\\}^{d},p).$ Recall that
$\mathsf{AnteU}(\\{\pm 1\\}^{d},p)$ is the distribution over subsets of
$\\{\pm 1\\}^{d}$ in which every element is included independently with
probability $p$ as all elements over the hypercube have order at most 2 (see
Definition 1.14).

######  Theorem 4.19.

Suppose that $d=\Omega(n\log n).$ With probability at least $1-2^{-d}$ over
$A\sim\mathsf{AnteU}(\\{\pm 1\\}^{d},p),$

${\mathsf{TV}}\Big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},\sigma_{A},p_{A})\|\mathsf{G}(n,p)\Big{)}=o_{n}(1).$

As we will see in Section 7, the dependence of $d$ on $n$ is tight up to the
logarithmic factor when $p=\Omega(1).$ We use the following well-known bound
on the Fourier coefficients of random functions.

######  Claim 4.20 ([ODo14]).

Suppose that $B$ is sampled from $\\{\pm 1\\}^{d}$ by including each element
independently with probability $p$ (i.e.,
$B\sim\mathsf{AnteU}(\mathcal{G},p)$). Let $\sigma_{B}$ be the indicator of
$B.$ Then, with probability at least $1-{2^{-d}},$ the inequalities
$|\widehat{\sigma_{B}}(\emptyset)-p|\leq 2^{1-d/2}\sqrt{d}$ and
$|\widehat{\sigma_{B}}(S)|\leq 2^{1-d/2}\sqrt{d}$ for all $S\neq\emptyset$
hold simultaneously.

Now, we simply combine 4.20 and Theorem 3.1.

###### Proof of Theorem 4.19.

We will prove the claim for all sets $A\subseteq\\{\pm 1\\}^{d}$ satisfying
that $|\widehat{\sigma_{A}}(\emptyset)-p|\leq\frac{2\sqrt{d}}{2^{d/2}}$ and
$|\widehat{\sigma_{A}}(S)|\leq\frac{2\sqrt{d}}{2^{d/2}}$ holds for all
$S\neq\emptyset.$ In light of 4.20, this is enough. Let $A$ be such a set and
let $p_{A}={\mathbf{E}}[\sigma_{A}]=\widehat{\sigma_{A}}(\emptyset).$ Consider
Theorem 3.1. It follows that $B_{i}\leq\Delta\binom{d}{i}^{1/2}$ for each $i,$
where $\Delta=\frac{2\sqrt{d}}{2^{d/2}}$ for brevity of notation. Take $m=1.$
Then,

$\displaystyle C_{m}$ $\displaystyle=\sum_{2\leq
i\leq\frac{d}{2en}}\Delta^{2}\binom{d}{i}+\sum_{d-\frac{d}{2en}\leq i\leq
d-2}\Delta^{2}\binom{d}{i}$
$\displaystyle=O\left(\Delta^{2}\binom{d}{\frac{d}{2en}}\right)$
$\displaystyle=O\left(\frac{4d}{2^{d}}(2e^{2}n)^{\frac{d}{2en}}\right)$
$\displaystyle=O\left(\frac{2^{O(d\log
n/n)}}{2^{d}}\right)=O\left(\frac{1}{2^{d/2}}\right).$

Similarly,

$D=\sum_{\frac{d}{2en}<i<d-\frac{d}{2en}}\Delta^{2}\binom{d}{i}\leq\Delta^{2}2^{d}=4d.$

Since $d=\Omega(n\log n),$ the conditions of Theorem 3.1 are satisfied. Thus,

$\displaystyle{\mathsf{KL}}\Big{(}\mathsf{RAG}(n,\\{\pm
1\\}^{d},1/2,\sigma_{A})\|\mathsf{G}(n,p_{A})\Big{)}$ (12)
$\displaystyle=O\left(\frac{n^{3}}{p_{A}^{2}}\times\left(\frac{B_{1}^{4}}{d}+\frac{B_{d-1}^{4}}{d}+B_{d}^{4}+\frac{O(\frac{1}{2^{d}})}{d^{2}}+{4d}\exp\left(-\frac{d}{2en}\right)\right)\right)$
(13)
$\displaystyle=O\left(\frac{n^{3}d^{3}}{p_{A}^{2}2^{2d}}+\frac{n^{3}}{p_{A}^{2}d^{2}2^{d}}+n^{3}d\times\exp\left(-\frac{d}{2en}\right)\right).$
(14)

The last expression is of order $o_{n}(1)$ when $d=\Omega(n\log n)$ for a
large enough hidden constant. Finally, note that

${\mathsf{TV}}\Big{(}\mathsf{G}(n,p),\mathsf{G}(n,p_{A})\Big{)}=o(1)$

whenever $p=\Omega({1}/{n^{2}}),$ and $|p_{A}-p|\leq 2^{1-d/2}\sqrt{d}.$
Indeed, this follows from the following observation. Suppose that $p_{A}<p$
without loss of generality. Then, $\mathsf{G}(n,p_{A})$ can be sampled by
first sampling $\mathsf{G}(n,p)$ and then retaining each edge with probability
$\frac{p_{A}}{p}\geq 1-2^{1-d/2}\sqrt{d}p^{-1}=1-o(n^{-3}).$ Thus, with high
probability $(1-o(n^{-3}))^{\binom{n}{2}}=1-o(n^{-1}),$ all edges are retained