and the two distributions are a distance $o(1)$ apart in ${\mathsf{TV}}.$ We
use triangle inequality and combine with Eq. 12. ∎

######  Remark 4.21.

The above proof provides a constructive way of finding connections $\sigma$
for which indistinguishability occurs when $d=\tilde{\Omega}(n).$ Namely, a
sufficient condition is that all of the Fourier coefficients of $\sigma_{A}$
except for $\widehat{\sigma_{A}}(\emptyset)$ are bounded by
$\frac{2\sqrt{d}}{2^{d/2}}$ and
$|\widehat{\sigma_{A}}(\emptyset)-p|\leq\frac{2\sqrt{d}}{2^{d/2}}$ In fact,
one could check that the same argument holds even under the looser condition
that all coefficients are bounded by $\frac{d^{C}}{2^{d}}$ for any fixed
constant $C.$ Such functions with Fourier coefficients bounded by $\epsilon$
on levels above $0$ are known as $\epsilon$-regular [ODo14]. Perhaps the
simplest examples for $\frac{2\sqrt{d}}{2^{d/2}}$-regular indicators with mean
1/2 are given by the inner product mod 2 function and the complete quadratic
function [ODo14, Example 6.4]. These provide explicit examples of functions
for which the phase transition to Erdős-Rényi occurs at $d=\tilde{\Theta}(n).$

##  5 Indistinguishability of Typical Random Algebraic Graphs

We now strengthen Theorem 4.19 by (1) extending it to all groups of
appropriate size and (2) replacing the $\log n$ factor by a potentially
smaller $\log\frac{1}{p}$ factor. The proof is probabilistic and, thus, does
not provide means for explicitly constructing functions for which the phase
transition occurs at $d=\tilde{\Omega}(n).$

######  Theorem 5.1.

An integer $n$ is given and a real number $p\in[0,1].$ Let $\mathcal{G}$ be
any finite group of size at least $\exp(Cn\log\frac{1}{p})$ for some universal
constant $C.$ Then, with probability at least $1-|\mathcal{G}|^{-1/7}$ over
$A\sim\mathsf{AnteU}(\mathcal{G},p),$ we have

${\mathsf{KL}}\Big{(}\mathsf{RRAG}(n,\mathcal{G},\sigma_{A},p_{A})\|\mathsf{G}(n,p)\Big{)}=o(1),$

where
$p_{A}={\mathbf{E}}_{\mathbf{g}\sim\mathsf{Unif}(\mathcal{G})}[\sigma_{A}(\mathbf{g})].$
The exact same holds for $\mathsf{LRAG}$ instead of $\mathsf{RRAG}.$

###### Proof.

In light of Eq. 4, we simply need to show that for typical sets $A,$ the
function

$\gamma_{A}(\mathbf{g})={\mathbf{E}}_{\mathbf{z}\sim\mathsf{Unif}(\mathcal{G})}[(\sigma_{A}(\mathbf{g}\mathbf{z}^{-1})-p)(\sigma_{A}(\mathbf{z})-p)]$

has sufficiently small moments. We bound the moments via the second moment
method over $A.$ Namely, for $t\geq 1,$ define the following functions:

$\phi_{t}(A)={\mathbf{E}}_{\mathbf{g}\sim\mathsf{Unif}(\mathcal{G})}[\gamma_{A}(\mathbf{g})^{t}]\;\text{
and
}\;\Phi(t)={\mathbf{E}}_{A\sim\mathsf{AnteU}(\mathcal{G},p)}[\phi_{t}^{2}(A)].$

We show that for typical $A,$ $\phi_{t}(A)$ is small by bounding the second
moment $\Phi(t)$ and using Chebyshev’s inequality. We begin by expressing
$\phi_{t}(A)$ and $\Phi(t).$ First,

$\displaystyle\phi_{t}(A)$
$\displaystyle={\mathbf{E}}_{\mathbf{g}\sim\mathsf{Unif}(\mathcal{G})}[\gamma_{A}(\mathbf{g})^{t}]={\mathbf{E}}_{\mathbf{g}\sim\mathsf{Unif}(\mathcal{G})}\Big{[}{\mathbf{E}}_{\mathbf{z}}[(\sigma_{A}(\mathbf{g}\mathbf{z}^{-1})-p)(\sigma_{A}(\mathbf{z})-p)]^{t}\Big{]}$
$\displaystyle={\mathbf{E}}_{\mathbf{g},\\{\mathbf{z}_{i}\\}_{i=1}^{t}\sim_{iid}\mathsf{Unif}(\mathcal{G})}\Bigg{[}\prod_{i=1}^{t}(\sigma_{A}(\mathbf{g}\mathbf{z}_{i}^{-1})-p)(\sigma_{A}(\mathbf{z}_{i})-p)\Bigg{]}.$

Therefore,

$\displaystyle\Phi(t)$
$\displaystyle={\mathbf{E}}_{A\sim\mathsf{AnteU}(\mathcal{G},p)}[\phi_{t}^{2}(A)]$
$\displaystyle={\mathbf{E}}_{A\sim\mathsf{AnteU}(\mathcal{G},p)}\Bigg{[}\Bigg{(}{\mathbf{E}}_{\mathbf{g},\\{\mathbf{z}_{i}\\}_{i=1}^{t}\sim_{iid}\mathsf{Unif}(\mathcal{G})}\bigg{[}\prod_{i=1}^{t}(\sigma_{A}(\mathbf{g}\mathbf{z}_{i}^{-1})-p)(\sigma_{A}(\mathbf{z}_{i})-p)\bigg{]}\Bigg{)}^{2}\Bigg{]}$
$\displaystyle={\mathbf{E}}_{A\sim\mathsf{AnteU}(\mathcal{G},p)}\Bigg{[}{\mathbf{E}}_{\mathbf{g}^{(1)},\mathbf{g}^{(2)},\\{\mathbf{z}^{(1)}_{i}\\}_{i=1}^{t},\\{\mathbf{z}^{(2)}_{i}\\}_{i=1}^{t}\sim_{iid}\mathsf{Unif}(\mathcal{G})}\bigg{[}\prod_{i=1}^{t}(\sigma_{A}(\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{i})^{-1})-p)$
$\displaystyle\qquad\qquad\qquad\qquad\times\prod_{i=1}^{t}(\sigma_{A}(\mathbf{z}^{(1)}_{i})-p)\prod_{i=1}^{t}(\sigma_{A}(\mathbf{g}^{(2)}(\mathbf{z}^{(2)}_{i})^{-1})-p)\prod_{i=1}^{t}(\sigma_{A}(\mathbf{z}^{(2)}_{i})-p)\bigg{]}\Bigg{]}.$

The main idea now is that we can change the order of expectation between $A$
and
$\\{\mathbf{g}^{(1)},\mathbf{g}^{(2)},\\{\mathbf{z}^{(1)}_{i}\\}_{i=1}^{t},\\{\mathbf{z}^{(2)}_{i}\\}_{i=1}^{t}\\}.$
Since
${\mathbf{E}}_{A\sim\mathsf{AnteU}(\mathcal{G},p)}\sigma_{A}(\mathbf{h})=p$
for each $\mathbf{h}\in\mathcal{G}$ by the definition of the density
$\mathsf{AnteU}(\mathcal{G},p),$ each of the terms of the type
$(\sigma_{A}(\cdot)-p)$ has zero expectation over $A.$ The lower bound we have
on the size of $\mathcal{G}$ will ensure that for “typical” choices of
$\\{\mathbf{g}^{(1)},\mathbf{g}^{(2)},\\{\mathbf{z}^{(1)}_{i}\\}_{i=1}^{t},\\{\mathbf{z}^{(2)}_{i}\\}_{i=1}^{t}\\},$
at least one of the terms of the type $(\sigma_{A}(\cdot)-p)$ is independent
of the others, which will lead to a (nearly) zero expectation. Namely, rewrite
the above expression as

$\begin{split}{\mathbf{E}}_{\mathbf{g}^{(1)},\mathbf{g}^{(2)},\\{\mathbf{z}^{(1)}_{i}\\}_{i=1}^{t},\\{\mathbf{z}^{(2)}_{i}\\}_{i=1}^{t}\sim_{iid}\mathsf{Unif}(\mathcal{G})}&\Bigg{[}{\mathbf{E}}_{A\sim\mathsf{AnteU}(\mathcal{G},p)}\bigg{[}\prod_{i=1}^{t}(\sigma_{A}(\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{i})^{-1})-p)\prod_{i=1}^{t}(\sigma_{A}(\mathbf{z}^{(1)}_{i})-p)\\\
&\qquad\qquad\times\prod_{i=1}^{t}(\sigma_{A}(\mathbf{g}^{(2)}(\mathbf{z}^{(2)}_{i})^{-1})-p)\prod_{i=1}^{t}(\sigma_{A}(\mathbf{z}^{(2)}_{i})-p)\bigg{]}\Bigg{]}.\end{split}$
(15)

Now, observe that if there exists some
$\xi\in\\{\mathbf{g}^{(1)},\mathbf{g}^{(2)},\\{\mathbf{z}^{(1)}_{i}\\}_{i=1}^{t},\\{\mathbf{z}^{(2)}_{i}\\}_{i=1}^{t}\\}$
such that $\xi\neq\zeta,\xi\neq\zeta^{-1}$ for any other
$\zeta\in\\{\mathbf{g}^{(1)},\mathbf{g}^{(2)},\\{\mathbf{z}^{(1)}_{i}\\}_{i=1}^{t},\\{\mathbf{z}^{(2)}_{i}\\}_{i=1}^{t}\\},$
the above expression is indeed equal to 0 since this means that
$\sigma_{A}(\xi)$ is independent of all other terms $\sigma_{A}(\zeta).$ Call
$B=B\bigg{(}\\{\mathbf{g}^{(1)},\mathbf{g}^{(2)},\\{\mathbf{z}^{(1)}_{i}\\}_{i=1}^{t},\\{\mathbf{z}^{(2)}_{i}\\}_{i=1}^{t}\\}\bigg{)}$
the event that all
$\xi\in\\{\mathbf{g}^{(1)},\mathbf{g}^{(2)},\\{\mathbf{z}^{(1)}_{i}\\}_{i=1}^{t},\\{\mathbf{z}^{(2)}_{i}\\}_{i=1}^{t}\\}$
satisfy this property. As discussed, over $B$ we have

${\mathbf{E}}_{A\sim\mathsf{AnteU}(\mathcal{G},p)}\Bigg{[}\prod_{i=1}^{t}(\sigma_{A}(\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{i})^{-1})-p)\prod_{i=1}^{t}(\sigma_{A}(\mathbf{z}^{(1)}_{i})-p)\prod_{i=1}^{t}(\sigma_{A}(\mathbf{g}^{(2)}(\mathbf{z}^{(2)}_{i})^{-1})-p)\prod_{i=1}^{t}(\sigma_{A}(\mathbf{z}^{(2)}_{i})-p)\Bigg{]}=0,$

and outside of $B,$ we have

$\displaystyle{\mathbf{E}}_{A\sim\mathsf{AnteU}(\mathcal{G},p)}\Bigg{[}\prod_{i=1}^{t}(\sigma_{A}(\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{i})^{-1})-p)\prod_{i=1}^{t}(\sigma_{A}(\mathbf{z}^{(1)}_{i})-p)\prod_{i=1}^{t}(\sigma_{A}(\mathbf{g}^{(2)}(\mathbf{z}^{(2)}_{i})^{-1})-p)\prod_{i=1}^{t}(\sigma_{A}(\mathbf{z}^{(2)}_{i})-p)\Bigg{]}$
$\displaystyle\leq\left\lVert\prod_{i=1}^{t}(\sigma_{A}(\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{i})^{-1})-p)\prod_{i=1}^{t}(\sigma_{A}(\mathbf{z}^{(1)}_{i})-p)\prod_{i=1}^{t}(\sigma_{A}(\mathbf{g}^{(2)}(\mathbf{z}^{(2)}_{i})^{-1})-p)\prod_{i=1}^{t}(\sigma_{A}(\mathbf{z}^{(2)}_{i})-p)\right\rVert_{\infty}\leq
1.$

It follows that $\Phi(t)\leq 1-{\mathbf{P}}[B].$ Next, we will show that
${\mathbf{P}}[B]=1-O\left({|\mathcal{G}|^{-1/3}}\right).$

Denote by $M\subseteq\mathcal{G}$ the set of group elements $\mathbf{h}$ for
which the equation $\mathbf{x}^{2}=\mathbf{h}$ has at least
$|\mathcal{G}|^{1/3}$ solutions $\mathbf{x}$ over $\mathcal{G}.$ By Markov’s
inequality, $|M|\leq|\mathcal{G}|^{2/3}.$ We now draw the elements
$\\{\mathbf{g}^{(1)},\mathbf{g}^{(2)},\\{\mathbf{z}^{(1)}_{i}\\}_{i=1}^{t},\\{\mathbf{z}^{(2)}_{i}\\}_{i=1}^{t}\\}$
sequentially in that order and track the probability with which one of the
following conditions fails (we terminate if a condition fails):

  1. 1.

$\mathbf{g}^{(1)}\not\in M\cup\\{1\\}$ and $\mathbf{g}^{(2)}\not\in
M\cup\\{1\\}.$

  2. 2.

$\mathbf{z}^{(1)}_{i}\not\in\\{\mathbf{z}^{(1)}_{j},(\mathbf{z}^{(1)}_{j})^{-1}\;:\;j<i\\}\cup\\{(\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{j})^{-1},(\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{j})^{-1})^{-1}\;:\;j<i\\}.$

  3. 3.

$\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{i})^{-1}\not\in\\{\mathbf{z}^{(1)}_{j},(\mathbf{z}^{(1)}_{j})^{-1}\;:\;j\leq
i\\}\cup\\{(\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{j})^{-1},(\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{j})^{-1})^{-1}\;:\;j<i\\}.$

  4. 4.

$\mathbf{z}^{(2)}_{i}\not\in\\{\mathbf{z}^{(2)}_{j},(\mathbf{z}^{(2)}_{j})^{-1}\;:\;j<i\\}\cup\\{\mathbf{g}^{(2)}(\mathbf{z}^{(2)}_{j})^{-1},(\mathbf{g}^{(2)}(\mathbf{z}^{(2)}_{j})^{-1})^{-1}\;:\;j<i\\},$
and
$\mathbf{z}^{(2)}_{i}\not\in\\{\mathbf{z}^{(1)}_{j},(\mathbf{z}^{(1)}_{j})^{-1},\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{j})^{-1},(\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{j})^{-1})^{-1}\;:\;j\leq
n\\}.$

  5. 5.

$\mathbf{g}^{(2)}(\mathbf{z}^{(2)}_{i})^{-1}\not\in\\{\mathbf{z}^{(2)}_{j},(\mathbf{z}^{(2)}_{j})^{-1}\;:\;j<i\\}\cup\\{\mathbf{g}^{(2)}(\mathbf{z}^{(2)}_{j})^{-1},(\mathbf{g}^{(2)}(\mathbf{z}^{(2)}_{j})^{-1})^{-1}\;:\;j<i\\},$
and
$\mathbf{z}^{(2)}_{i}\not\in\\{\mathbf{z}^{(1)}_{j},(\mathbf{z}^{(1)}_{j})^{-1},\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{j})^{-1},(\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{j})^{-1})^{-1}\;:\;j\leq
n\\}.$

Note that conditions 2-5 exactly capture that event $B$ occurs, so conditions
1-5 hold together with probability at most ${\mathbf{P}}[B].$ Condition 1 is
added to help with the proof. We analyze each step separately.

  1. 1.

${\mathbf{P}}[\mathbf{g}^{(1)}\in
M\cup\\{1\\}]=\frac{|M|\cup\\{1\\}}{|\mathcal{G}|}=O(|\mathcal{G}|^{-1/3})$
and the same for $\mathbf{g}^{(2)}.$ Thus, the drawing procedure fails at this
stage with probability at most $O(|\mathcal{G}|^{-1/3}).$

  2. 2.

Since the elements
$\mathbf{z}^{(1)}_{i}\not\in\\{\mathbf{z}^{(1)}_{j},(\mathbf{z}^{(1)}_{j})^{-1}\;:\;j<i\\}\cup\\{(\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{j})^{-1},(\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{j})^{-1})^{-1}\;:\;j<i\\}$
are independent of $\mathbf{z}^{(1)}_{i}$ and there are at most $4i\leq 4t\leq
4n$ of them, we fail with probability $O({n}/{|\mathcal{G}|})$ at this step.

  3. 3.

The calculation for $\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{i})^{-1}$ is almost
the same, except that we have to separately take care of the cases
$\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{i})^{-1}=(\mathbf{z}^{(1)}_{i})^{-1}$ and
$\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{i})^{-1}=\mathbf{z}^{(1)}_{i}.$ The first
event can only happen if $\mathbf{g}^{(1)}=1,$ in which case the drawing
procedure has already terminated at Step 1. The second event is equivalent to
$\mathbf{g}^{(1)}=(\mathbf{z}^{(1)}_{i})^{2}.$ If the drawing procedure has
not terminated at Step 1, this occurs with probability at most
$|\mathcal{G}|^{-2/3}$ since $\mathbf{g}^{(1)}\not\in M.$ Thus, the total
probability of failure is $O({n}/{|\mathcal{G}|}+{|\mathcal{G}|^{-2/3}}).$

  4. 4.

As in Step 2, the calculation for $\mathbf{z}^{(2)}_{i}$ gives
$O({n}/{|\mathcal{G}|}).$

  5. 5.

As in Step 5, the calculation for
$\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{i})^{-1}$ gives
$O({n}/{|\mathcal{G}|}+{|\mathcal{G}|^{-2/3}}).$

Summing over all $j\in[t],\ell\in\\{1,2\\},$ via union bound, we obtain a
total probability of failure at most

$O\bigg{(}\frac{1}{|\mathcal{G}|^{1/3}}\bigg{)}+O\bigg{(}\frac{t}{|\mathcal{G}|^{2/3}}\bigg{)}+O\bigg{(}\frac{tn}{|\mathcal{G}|}\bigg{)}=O\bigg{(}\frac{1}{|\mathcal{G}|^{1/3}}\bigg{)}$

as $t\leq n\leq\log|\mathcal{G}|$ by the definition of $t$ and assumption on
$|\mathcal{G}|.$

Going back, we conclude that $1-{\mathbf{P}}[B]\leq{C}{|\mathcal{G}|^{-1/3}}$
for some absolute constant $C,$ so $\Phi(t)\leq{C}{|\mathcal{G}|^{-1/3}}$ for
some absolute constant $C.$

Now, we can apply the moment method over $A$ and conclude that

${\mathbf{P}}_{A}[|\phi_{t}(A)|>|\mathcal{G}|^{-1/12}]\leq\frac{{\mathbf{E}}_{A}[\phi_{t}(A)^{2}]}{|\mathcal{G}|^{-1/6}}=\frac{\Phi(t)}{|\mathcal{G}|^{-1/6}}\leq
C|\mathcal{G}|^{-1/6}.$

Therefore, with high probability $1-C|\mathcal{G}|^{-1/6}$ over
$A\sim\mathsf{AnteU}(\mathcal{G},p),$ $\phi_{t}(A)\leq|\mathcal{G}|^{-1/12}.$
Taking a union bound over $t\in\\{1,2,\ldots,n-1\\},$ we reach the conclusion
that with high probability $1-Cn|\mathcal{G}|^{-1/6}>1-|\mathcal{G}|^{-1/7}$
over $A\sim\mathsf{AnteU}(\mathcal{G},p),$
$\phi_{t}(A)\leq|\mathcal{G}|^{-1/12}$ holds for all $t\in[n-1].$

Now, suppose that $A$ is one such set which satisfies that
$\phi_{t}(A)\leq|\mathcal{G}|^{-1/12}$ holds for all $t\in[n-1].$ Using Eq. 4,
we obtain

$\displaystyle\sum_{k=0}^{n-1}\log\sum_{t=0}^{k}\binom{k}{t}{\mathbf{E}}_{\mathbf{g}\sim\mathsf{Unif}(\mathcal{G})}\left[\frac{\gamma(\mathbf{g})^{t}}{p^{t}(1-p)^{t}}\right]\leq\sum_{k=0}^{n-1}\log\Bigg{(}1+\sum_{t=1}^{k}\binom{k}{t}\frac{|\mathcal{G}|^{-1/12}}{p^{t}(1-p)^{t}}\Bigg{)}.$

Now, suppose that $|\mathcal{G}|>n^{24}2^{12n}p^{-12n}(1-p)^{-12n},$ which is
of order $\exp(Cn\log\frac{1}{p})$ for some absolute constant $C$ when
$p\leq\frac{1}{2}.$ Then, the above expression is bounded by

$\displaystyle\sum_{k=0}^{n-1}\log\Bigg{(}1+\frac{1}{n^{2}2^{n}}\sum_{t=1}^{k}\binom{k}{t}\frac{p^{n}(1-p)^{n}}{p^{t}(1-p)^{t}}\Bigg{)}$
$\displaystyle\leq\sum_{k=0}^{n-1}\log\Bigg{(}1+\frac{1}{n^{2}2^{n}}\sum_{t=1}^{k}\binom{k}{t}\Bigg{)}$
$\displaystyle\leq\sum_{k=0}^{n-1}\log\Bigg{(}1+\frac{1}{n^{2}2^{n}}2^{k}\Bigg{)}\leq\sum_{k=0}^{n-1}\log\bigg{(}1+\frac{1}{n^{2}}\bigg{)}\leq\sum_{k=0}^{n-1}\frac{1}{n^{2}}=\frac{1}{n}=o(1).\qed$

##  6 Detection via Signed Triangle Count over the Hypercube

Here, we explore the power of counting signed triangles. We will first provide
counterparts to the arguments on symmetric connection in Section 4.1. As we
will see in Section 6.2, there are fundamental difficulties in applying the
signed triangle statistic to non-symmetric connections. Section 7 shows an
even deeper limitation that goes beyond counting any small subgraphs.

###  6.1 Detection for Symmetric Connections

We first simplify Corollary 2.14.

######  Corollary 6.1.

Suppose that $d=\omega(n),p=\Omega({1}/{n}),$ and $\sigma$ is a symmetric
connection. If

$n^{6}\Big{(}\sum_{S\;:\;|S|\in\\{1,2,d-1,d-1,d\\}}\widehat{\sigma}(S)^{3}\Big{)}^{2}=\omega\Big{(}n^{3}p^{3}+n^{4}\sum_{|S|\in\\{1,d-1,d\\}}\widehat{\sigma}(S)^{4}\Big{)},$

then the signed triangle statistic distinguishes between $\mathsf{G}(n,p)$ and
$\mathsf{RAG}(n,\\{\pm 1\\}^{d},p,\sigma)$ with high probability.

###### Proof.

We will essentially show that the above inequality, together with
$d=\omega(n),p=\Omega({1}/{n}),$ imply the conditions of Corollary 2.14.
Denote

$A=\displaystyle\sum_{S\;:\;|S|\in\\{1,2,d-1,d-1,d\\}}\widehat{\sigma}(S)^{3}.$

As $\sum_{|S|\in\\{1,d-1,d\\}}\widehat{\sigma}(S)^{4}>0,$ the conditions above
imply that $n^{6}A^{2}=\omega(n^{3}p^{3}),$ so $A=\omega(n^{-3/2}p^{3/2}).$
Note however, that

$B:=\sum_{S\;:\;|S|\not\in\\{1,2,d-1,d-1,d\\}}\widehat{\sigma}(S)^{3}\leq\sum_{S\;:\;|S|\not\in\\{1,2,d-1,d-1,d\\}}|\widehat{\sigma}(S)|^{3}=\sum_{3\leq
j\leq
d-3}\binom{d}{j}\bigg{(}\frac{\mathcal{W}^{j}({\sigma})}{\binom{d}{j}}\bigg{)}^{3/2},$

where for the last equality we used the symmetry of $\sigma.$ However, as
$\mathcal{W}^{j}({\sigma})\leq{\mathbf{Var}}[\sigma]\leq p-p^{2}<p,$ the last
sum is bounded by

$\sum_{3\leq j\leq
d-3}\binom{d}{j}^{-1/2}p^{3/2}=O\left(d^{-3/2}p^{3/2}\right)=o(n^{-3/2}p^{3/2})=o(A).$

In particular, this means that $A+B=\Omega(A),$ and
$n^{3}|A+B|=\omega(n^{3/2}p^{3/2})=\omega(1).$ Thus,

$\displaystyle
n^{6}\Big{(}\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{3}\Big{)}^{2}=\Omega\Big{(}n^{6}\sum_{S\;:\;|S|\in\\{1,2,d-1,d-1,d\\}}\widehat{\sigma}(S)^{3}\Big{)}^{2}$
$\displaystyle=\omega\Big{(}n^{3}p^{3}+n^{4}\sum_{|S|\in\\{1,d-1,d\\}}\widehat{\sigma}(S)^{4}\Big{)}+\omega\Big{(}n^{3}\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{3}\Big{)}$
$\displaystyle=\omega\Big{(}n^{3}p^{3}+n^{3}\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{3}+n^{4}\sum_{|S|\in\\{1,d-1,d\\}}\widehat{\sigma}(S)^{4}\Big{)},$

where we used the assumptions of the corollary and the fact that
$n^{6}(A+B)^{2}=\omega(|n^{3}(A+B)|)$ which follows from
$|n^{3}(A+B)|=\omega(1).$ To finish the proof, we simply need to add the
missing terms in the sum of fourth powers. Using the same approach with which
we bounded $B,$ we have

$n^{4}\sum_{S\;:\;|S|\not\in\\{1,2,d-1,d-1,d\\}}\widehat{\sigma}(S)^{4}=n^{4}\sum_{2\leq
j\leq
d-2}\binom{d}{j}p^{2}\binom{d}{j}^{-2}=O(n^{4}p^{2}d^{-2})=o(n^{2}p^{2})=o(n^{3}p^{3}),$

where in the last line we used the fact that $pn=\Omega(1).$ With this, the
conclusion follows. ∎

Note that this proposition gives an exact qualitative counterpart to Corollary
4.1 since it also depends only on levels $1,2,d-2,d-1,d.$

We now transition to proving detection results for specific functions, which
serve as lower bounds for our indistinguishability results. We don’t give any
lower-bound results for Corollary 4.4 and Corollary 4.8 as these already
appear in literature (even though for the slightly different model over Gauss
space). Namely, in [LR21a], Liu and Racz prove that when there $\sigma$ is
monotone $\frac{1}{r\sqrt{d}}$-Lipschitz, the signed triangle statistic
distinguishes the underlying geometry whenever $d=o({n^{3}}/{r^{6}}).$ In
[LMS+22a], the authors show that the signed triangle statistic distinguishes
the connection ${\mathbf{T}}_{p}$ when $d=\tilde{o}(n^{3}p^{3}).$

####  6.1.1 Hard Threshold Connections

Here, we prove the following bound corresponding to Corollary 4.10.

######  Corollary 6.2.

When $d$ is even and $d=\omega(n),p=\Omega(\frac{1}{n})$ and
$d=o(n^{3/2}p^{3/2}),$

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

It should be no surprise that we need to calculate the Fourier coefficients of
$\mathbf{D}_{p}$ to prove this statement. From Proposition 4.9 we know that
$\widehat{\mathbf{D}_{p}}([d])=\tilde{O}(\frac{p}{d^{1/2}}).$ In Section D.1,
we prove the following further bounds.

######  Proposition 6.3.

When $p=d^{O(1)},$ the Fourier coefficients of $\mathbf{D}_{p}$ satisfy

  1. 1.

$\widehat{\mathbf{D}_{p}}([2])=\Omega(\frac{p}{d}).$

  2. 2.

$\widehat{\mathbf{D}_{p}}([d-2])=\tilde{O}(\frac{p}{d^{3/2}}).$

These are enough to prove the corollary.

###### Proof of Corollary 6.2 .

We simply apply Corollary 6.1. As all Fourier coefficients on levels, 1,
$d-1,$ equal zero, we focus on levels $2,d-2,d.$

$\displaystyle\sum_{S\;:\;|S|\in\\{1,2,d-2,d-1,d\\}}\widehat{\sigma}(S)^{3}$
$\displaystyle=\Omega\left(\frac{p^{3}}{d^{3}}\binom{d}{2}\right)+\tilde{O}\left(\binom{d}{2}\frac{p^{3}}{d^{9/2}}+\frac{p^{3}}{d^{3/2}}\right)=\Omega\left(\frac{p^{3}}{d}\right),$
$\displaystyle\sum_{S\;:\;|S|\in\\{1,d-1,d\\}}\widehat{\sigma}(S)^{4}$
$\displaystyle=\tilde{O}\left(\frac{p^{4}}{d^{2}}\right).$

Therefore, by Corollary 6.1, we can detect geometry when

$n^{6}\frac{p^{6}}{d^{2}}=\omega(n^{3}p^{3})+\tilde{\omega}\left(\frac{p^{4}}{d^{2}}\right).$

One can easily check that this is equivalent to $d=o(n^{3/2}p^{3/2}).$ ∎

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

We now turn to the more general case of non-monotone connections and interval
unions. We only consider the case when $p=\Theta(1)$ so that we illustrate
better the dependence on the correlation with parity, manifested in the number
of intervals and analytic total variation. We first handle the simple case of
$\pi_{\kappa}.$

######  Corollary 6.4.

If $n\kappa^{2}=\omega(1),$ the signed triangle statistic distinguishes
$\mathsf{G}(n,p)$ and $\mathsf{RAG}(n,\\{\pm 1\\}^{d},1/2,\pi_{\kappa})$ with
high probability.

###### Proof.

By Corollary 2.14, the signed triangle statistic distinguishes the two graph
models with high probability whenever

$n^{6}\kappa^{6}=\omega(n^{3}+n^{3}\kappa^{3}+n^{4}\kappa^{4}).$

Trivially, this is equivalent to $n\kappa^{2}=\omega(1).$ ∎

######  Remark 6.5.

In particular, note that when $\kappa=\Theta(1),$ one can distinguish with
high probability $\mathsf{G}(n,1/2)$ and $\mathsf{RAG}(n,\\{\pm
1\\}^{d},1/2,\pi_{\kappa})$ for any $d.$ This phenomenon is clearly specific
to the hypercube. In the Gaussian setting, whenever $d=\tilde{\omega}(n^{3}),$
${\mathsf{TV}}\Big{(}\mathsf{G}(n,p),\mathsf{RGG}(n,\mathbb{R}^{d},\mathcal{N}(0,I_{d}),p,\sigma)\Big{)}=o(1)$
for any connection $\sigma(\mathbf{x},\mathbf{y})$ depending only on
$\langle\mathbf{x},\mathbf{y}\rangle$ simply because of the fact that Wishart
and GOE matrices are indistinguishable in this regime due to Theorem 1.2. One
way to understand this difference between Gaussian space and the hypercube is
that the latter also posses an arithmetic structure, so connections such as
$\pi_{\kappa}$ which heavily depend on the arithmetic might lead to a very
different behaviour. In the particular case of $\pi_{1/2},$ the resulting
graph $\mathsf{RAG}(n,\\{\pm 1\\}^{d},1/2,\pi_{1/2})$ is bipartite: vertices
$i,j$ in this graph are adjacent if and only if the number of coordinates
equaling $-1$ has the same parity in $\mathbf{x}_{i}$ and $\mathbf{x}_{j}.$

######  Remark 6.6.

Note that $\pi_{1/2}$ has a single large Fourier coefficient on non-zero
levels, but this already makes $\mathsf{RAG}(n,\\{\pm 1\\}^{d},1/2,\pi_{1/2})$
detectable for any value of $n.$ This is the qualitative converse of Theorem
3.1.

######  Remark 6.7.

Finally, take any $s=\omega(\sqrt{d})$ and let
$h(\mathbf{x}):=\mathds{1}\left[\sum_{i=1}^{d}x_{i}\in[-s,s]\right].$ Then,
the connection $\sigma(\mathbf{x}):=h(\mathbf{x})\times\pi_{1/2}(\mathbf{x})$
is an indicator of a union of $O(s)$ intervals. Nevertheless,
$\mathsf{RAG}(n,\\{\pm 1\\}^{d},p,\sigma)$ and $\mathsf{G}(n,1/2)$ are
distinguishable with probability $1-o(1).$ Indeed,
${\mathbf{P}}_{\mathbf{g}\sim\mathsf{Unif}(\\{\pm
1\\}^{d})}[\sigma(\mathbf{g})=\pi_{1/2}(\mathbf{g})]=1-o(1),$ which implies
that ${\mathsf{TV}}\Big{(}\mathsf{RAG}(m,\\{\pm
1\\}^{d},1/2,\sigma),\mathsf{RAG}(m,\\{\pm
1\\}^{d},1/2,\pi_{1/2})\Big{)}=o(1)$ for all small enough $m.$ Thus, one can
distinguish $\mathsf{RAG}(n,\\{\pm 1\\}^{d},p,\sigma)$ and $\mathsf{G}(n,1/2)$
by focusing on the induced subgraphs on vertices $\\{1,2,\ldots,m\\}$ for a
small enough $m=\omega(1).$

We now proceed to the more interesting interval unions. Note that in this
case, the indistinguishability rates we prove are
$d=\omega(n^{3}+n^{3/2}s^{2})$ for a general union of intervals and
$d=\omega(n^{3/2}s^{2})$ for a union of intervals symmetric around 0. The
counterparts to these rates that we present are based on the following
interval unions. For simplicity, assume that $d$ is even and $d=2d_{1}.$ We
begin with the general case.

######  Corollary 6.8.

Suppose that $s=\tilde{\Omega}(d^{1/3})$ and $s=o(\sqrt{d}).$ Then, there
exists a connection $\zeta$ which is the indicator of a union of $s$ intervals
and ${\mathbf{E}}[\zeta]=\Omega(1).$ Furthermore, $\zeta$ is detected by the
signed triangle statistic whenever $d=o(ns^{2}).$

We construct this function $\zeta$ as follows.

######  Proposition 6.9.

Let $s=o(\sqrt{d})$ and consider the union of $s$ intervals given by

$I_{s}=\left\\{d_{1},d_{1}+2,d_{1}+4,\ldots,d_{1}+2(s-2)\right\\}\cup[d_{1}+\sqrt{d},d].$

Let the connection $\zeta_{s}$ be defined as
$\displaystyle\zeta_{s}(x)=\mathds{1}[\sum_{i=1}^{d}x_{i}\in I_{s}].$ Then,
the following facts hold: ${\mathbf{E}}[\zeta_{s}]=\Omega(1),$
$\displaystyle|\widehat{\zeta_{s}}([\ell])|\leq{\binom{d}{l}}^{-1/2}$ for
$\ell\in\\{1,2,d-1,d-2\\},$ and
$\widehat{\zeta_{s}}([d])=\Theta(\frac{s}{\sqrt{d}}).$

We defer the proof to Section D.2. We proceed to providing lower bounds for
connections which are indicators of interval unions.

###### Proof of Corollary 6.8.

We use Corollary 6.1 for the interval union indicator $\zeta_{s}.$ The left-
hand side becomes

$n^{6}\Bigg{(}\tilde{\Theta}\bigg{(}\frac{s^{3}}{d^{3/2}}\bigg{)}+dO\bigg{(}\binom{d}{1}^{-3/2}\bigg{)}+\binom{d}{2}O\bigg{(}\binom{d}{2}^{-3/2}\bigg{)}\Bigg{)}=n^{6}\tilde{\Theta}\Bigg{(}\frac{s^{3}}{d^{3/2}}\Bigg{)}$

as $s=\tilde{\Omega}(d^{1/3}).$ Similarly, in the right-hand side is

$\Theta(n^{3})+n^{4}\tilde{\Theta}\bigg{(}\frac{s^{4}}{d^{2}}\bigg{)}+n^{4}dO\bigg{(}\binom{d}{1}^{-2}\bigg{)}+n^{4}s^{2}O\bigg{(}\binom{d}{2}^{-2}\bigg{)}=O\Bigg{(}n^{3}+n^{4}\frac{s^{4}}{d^{2}}\Bigg{)}.$

Thus, we need the following inequality to hold for detection:

$n^{6}\frac{s^{6}}{d^{3}}=\tilde{\omega}\Bigg{(}n^{3}+n^{4}\frac{s^{4}}{d^{2}}\Bigg{)}.$

This is equivalent to $d=\tilde{o}(ns^{2}).$ ∎

Our construction for the symmetric case is similar.

######  Proposition 6.10.

Let $s=o(\sqrt{d})$ and consider the union of $2s-1$ intervals given by

$I^{sym}_{s}=[-d,-d_{1}-\sqrt{d}]\cup\left\\{d_{1}-2(s-2),\ldots,d_{1},\ldots,d_{1}+2(s-2)\right\\}\cup[d_{1}+\sqrt{d},d].$

Define the connection
$\zeta^{sym}_{s}(x)=\mathds{1}\Big{[}\sum_{i=1}^{d}x_{i}\in
I^{sym}_{s}\Big{]}.$ Then, the following facts hold about $\zeta^{sym}_{s}$:
${\mathbf{E}}[\zeta^{sym}_{s}]=\Omega(1),$
$|\widehat{\zeta^{sym}_{s}}([\ell])|\leq{1}/{\sqrt{\binom{d}{l}}}$ for
$\ell\in\\{1,2,d-1,d-2\\},$ and
$\widehat{\zeta^{sym}_{s}}([d])=\Theta({s}/{\sqrt{d}}).$

The same proof yields the following.

######  Corollary 6.11.

Suppose that $s=\Omega(d^{1/6})$ and $s=o(\sqrt{d}).$ Then, there exists a
connection $\zeta$ which is the indicator of a union of $2s-1$ intervals,
symmetric around 0, and ${\mathbf{E}}[\zeta]=\Omega(1).$ Furthermore $\zeta$
is detected by the signed triangle statistic whenever $d=o(ns^{2}).$

####  6.1.3 Connections Without Low Degree and High Degree Terms

Finally, we turn to proving a detection rate that matches the conjecture we
stated in 4.16.

######  Example 6.12.

Suppose that $m$ is fixed. There exists a symmetric connection $\sigma:\\{\pm
1\\}^{d}\longrightarrow[0,1]$ such that $\mathcal{W}^{k}({\sigma_{1}})=0$ for
$k\in\\{1,2,\ldots,m-1\\}\cup\\{d-m,\ldots,d\\}$ and, furthermore, if
$d=\tilde{\omega}_{p}(n^{3/m}),$ the graphs $G(n,p)$ and
$\mathsf{RAG}(n,\\{\pm 1\\}^{d},p,\sigma)$ are distinguishable with high
probability via the signed-triangle statistic.

To prove this result, we will use the following construction. Again, we focus
on the case $p=\frac{1}{2}$ to illustrate better the dependence on $m.$

######  Proposition 6.13.

For any constant $m\in\mathbb{N},$ there exists a symmetric connection
$\sigma:\\{\pm 1\\}^{d}\longrightarrow[0,1]$ such that

  1. 1.

${\mathbf{E}}[\sigma_{1}]=\frac{1}{2},$

  2. 2.

$\mathcal{W}^{m}({\sigma_{1}})=\Omega(\frac{1}{\log^{m}d}),$

  3. 3.

$\mathcal{W}^{k}({\sigma_{1}})=0$ for
$k\in\\{1,2,\ldots,m-1\\}\cup\\{d-m,d-m+1,\ldots,d\\}.$

We construct this connection in Appendix C and now we continue to the proof of
the detection statement.

###### Proof of Example 6.12.

We simply apply Corollary 2.14. To do so, we need to compute the sum of third
and fourth powers of Fourier coefficients. Let the sign on the $m$-th level of
$\sigma$ be $\epsilon.$

$\displaystyle\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{3}=\sum_{S:|S|=m}\widehat{\sigma_{1}}(S)^{3}+\sum_{S:m<|S|<d-m}\widehat{\sigma_{1}}(S)^{3}$
$\displaystyle=\epsilon\binom{d}{m}\left(\frac{\mathcal{W}^{m}({\sigma_{1}})}{\binom{d}{m}}\right)^{3/2}+O\left(\sum_{m<j<d-m}\binom{d}{j}\left(\frac{p^{2}}{\binom{d}{j}}\right)^{3/2}\right)$
$\displaystyle=\epsilon\times\Omega(d^{-m/2}\log^{-3m/2}d)+O(d^{-(m+1)/2})=\Omega(d^{-m/2}\log^{-3m/2}d).$

In the exact same way, we conclude that

$\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{3}=O(d^{-m/2})\text{ and
}\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{4}=O(d^{-m}).$

Thus, to detect the geometry, we simply need the following inequality to be
satisfied.

$n^{6}d^{-m}\log^{-3m}d=\omega(n^{3}+n^{3}d^{-m/2}+n^{4}d^{-m}).$

One can easily check that this is satisfied when $d=o(n^{3/m}\log^{3}d)$ or ,
equivalently, $d=\tilde{o}(n^{3/m}).$ ∎

####  6.1.4 Low Degree Polynomials

Our lower bounds for low-degree connections leave a large gap to Corollary
4.17.

######  Theorem 6.14.

There exists a degree 1 symmetric connection $\sigma$ with expectation $p$
such that the signed triangle statistic distinguishes $\mathsf{G}(n,p)$ and
$\mathsf{RAG}(n,\\{\pm 1\\}^{d},p,\sigma)$ with probability $1-o(1)$ when
$d=o((np)^{3/4}).$

###### Proof.

Consider the connection $\sigma(\mathbf{g})=p+\sum_{i=1}^{d}\frac{p}{d}g_{i}$
and apply Corollary 6.1. ∎

###  6.2 The Doom Of Signed Triangles: Fourier-Paired Connections

Thus far, we have used the signed triangle statistic as a useful tool in
detecting geometry. However, this technique is not foolproof - it might be the
case that the signed triangle statistic does not yield any detection rates. We
must note that [BBH21] explores a similar idea as the authors introduce a
bipartite mask and, thus, their graphs do not include any (signed) triangles.
Here, we illustrate a different, perhaps more intrinsic way, of making the
signed triangle statistic fail. Indeed suppose that
$\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{3}=0.$ Then, in expectation, the
signed triangle statistic applied to $\mathsf{G}(n,p)$ and
$\mathsf{RAG}(n,\\{\pm 1\\}^{d},p,\sigma)$ gives the same count: zero.

Of course, one should ask: are there any interesting functions $\sigma$ which
satisfy $\widehat{\sigma}(S)^{3}=0$? We show that the answer is yes. We
analyze two concrete families of connections, both of which satisfy the
following broader definition.

######  Definition 6.15.

We call a connection $\sigma:\\{\pm 1\\}^{d}\longrightarrow[0,1]$ Fourier-
paired if the following condition holds. There exists a bijection $\beta$ on
the nonempty subsets of $[d]$ such that
$\widehat{\sigma}(S)=-\widehat{\sigma}(\beta(S))$ for each $S\neq\emptyset.$

Trivially, any Fourier-paired connection $\sigma$ satisfies
$\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{k}=0$ for any odd integer $k.$ The
converse is also true – if $\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{k}=0$
holds for any odd $k,$ the connection is Fourier-paired. So, how can we
construct Fourier-paired connections? It turns out that in Section 4.2. we
already have!

First, note that for any connection $\sigma$ (not even necessarily,
symmetric), its repulsion-attraction twist $\rho_{\sigma,\sigma}$ is Fourier-
paired! Another example can be derived using the approach of negating certain
variables. Consider first the majority mapping over $d=2d_{1}$ variables
defined as follows. ${\mathbf{Maj}}(\mathbf{g})=1$ if
$\displaystyle\sum_{i=1}^{d}g_{i}>0,$ ${\mathbf{Maj}}(\mathbf{g})=1/2$ if
$\displaystyle\sum g_{i}=0,$ and ${\mathbf{Maj}}(\mathbf{g})=0$ if
$\displaystyle\sum g_{i}<0.$ Note that $\mathsf{RAG}(n,\\{\pm
1\\}^{d},1/2,{\mathbf{Maj}})$ is just the analogue of the usual dense random
geometric graph with hard thresholds considered in [BDE+14].444Of course,
there is the small difference at latent vectors
$\mathbf{x}_{i},\mathbf{x}_{j}$ for which
$\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle=0$ since the edge between them is
not formed deterministically. But we will ignore this. One can easily show
using Corollary 6.1 that $\mathsf{G}(n,p)$ and $\mathsf{RAG}(n,\\{\pm
1\\}^{d},1/2,{\mathbf{Maj}})$ are distinguishable when $d=o(n^{3})$ and this
is tight in light of Corollary 4.8.

Now, consider the small modification of ${\mathbf{Maj}},$ which we call the
half-negated majority and denote by ${\mathbf{HNMaj}}.$ Let
$\mathbf{h}=(\underbrace{1,1,\ldots,1}_{d_{1}}\underbrace{-1,-1,\ldots,-1}_{d_{1}})$
and ${\mathbf{HNMaj}}(\mathbf{g}):={\mathbf{Maj}}(\mathbf{h}\mathbf{g}),$
which is just the coefficient contraction with respect to $\mathbf{h}.$ It
turns out that it is relatively easy to show that ${\mathbf{HNMaj}}$ is
Fourier-paired.

######  Proposition 6.16.

The mapping ${\mathbf{HNMaj}}$ is Fourier-paired.

###### Proof.

First, we claim that all coefficients on even levels greater than 1 of
${\mathbf{HNMaj}}$ are equal to 0. Indeed, consider
$f(\mathbf{g}):=2{\mathbf{HNMaj}}(\mathbf{g})-1.$ Clearly , $f$ is odd in the
sense that $f(\mathbf{g})=-f(-\mathbf{g})$ holds for all $\mathbf{g}.$ Thus,
all coefficients of $f$ on even levels equal $0,$ so this also holds for
${\mathbf{HNMaj}}$ except for level $0.$

Now, for each $S\subseteq[d]$ of odd size, define
$\mathsf{s}(S)=S\cap[1,d_{1}]$ and $\mathsf{b}(S)=S\cap[d_{1}+1,2d].$ We claim
that the bijection $\beta$ sending $S$ to a set $T$ such that
$\mathsf{s}(S)=\mathsf{b}(T)$ and $\mathsf{s}(T)=\mathsf{b}(S)$ proves that
${\mathbf{HNMaj}}$ is Fourier paired. Indeed, this follows from the following
fact. For any two $\mathbf{g}_{1},\mathbf{g}_{2}\in\\{\pm 1\\}^{d_{1}},$ we
have555By $\mathbf{g}_{1},\mathbf{g}_{2},$ below we mean their concatenation.
${\mathbf{HNMaj}}(\mathbf{g}_{1},\mathbf{g}_{2})={\mathbf{Maj}}(\mathbf{g}_{1},-\mathbf{g}_{2})={\mathbf{Maj}}(-\mathbf{g}_{2},\mathbf{g}_{1})={\mathbf{HNMaj}}(-\mathbf{g}_{2},-\mathbf{g}_{1}).$
Combining these two statements, we obtain:

$\widehat{{\mathbf{HNMaj}}}(S)\omega_{S}(\mathbf{g}_{1},\mathbf{g}_{2})=\widehat{{\mathbf{HNMaj}}}(T)\omega_{T}(-\mathbf{g}_{2},-\mathbf{g}_{1})=-\widehat{{\mathbf{HNMaj}}}(T)\omega_{T}(\mathbf{g}_{2},\mathbf{g}_{1}),$

from which the claim follows as $|T|=|S|$ and $|S|$ is odd. ∎

Now, for both $\rho_{{\mathbf{Maj}},{\mathbf{Maj}}}$ and ${\mathbf{HNMaj}},$
our Theorem 3.1 implies that the corresponding random algebraic graphs are
indistinguishable from $\mathsf{G}(n,1/2)$ when $d=\omega(n^{3}).$ However, we
cannot apply our usual statistic for counting triangles to detect those graphs
as the number of signed triangles matches the corresponding quantity in the
Erdős-Rényi model. Clearly, counting signed 4-cycles, one can hope to obtain
some lower bound as their number $\sum_{S\neq}\widehat{\sigma}(S)^{4}$ (see
2.12) is positive unless $\sigma$ is constant. Indeed, one can easily verify
the following facts:

$\displaystyle{\mathbf{E}}_{G\sim\mathsf{G}(n,1/2)}[\tau_{4}(G)]$
$\displaystyle=0,$
$\displaystyle{\mathbf{Var}}_{G\sim\mathsf{G}(n,1/2)}[\tau_{4}(G)]$
$\displaystyle=\Theta(n^{4}),$
$\displaystyle{\mathbf{E}}_{H\sim\mathsf{RAG}(n,\\{\pm
1\\}^{d},1/2,{\mathbf{HNMaj}})}[\tau_{4}(H)]$
$\displaystyle=\Theta\Big{(}\frac{n^{4}}{d}\Big{)},$
$\displaystyle{\mathbf{E}}_{K\sim\mathsf{RAG}(n,\\{\pm
1\\}^{d},1/2,\rho_{{\mathbf{Maj}},{\mathbf{Maj}}})}[\tau_{4}(K)]$
$\displaystyle=\Theta\Big{(}\frac{n^{4}}{d}\Big{)}.$

These suggest that when $d=o(n^{2}),$ the two random algebraic graph models
have a total variation of $1-o(1)$ with $\mathsf{G}(n,1/2).$ Of course, to
make this conclusion rigorous, we also need to compute the quantities
${\mathbf{Var}}_{G\sim\mathsf{RAG}(n,\\{\pm
1\\}^{d},1/2,\cdot)}[\tau_{4}(G)].$ We choose not to take this approach in the
current paper as it is computationally cumbersome. Instead, we demonstrate
that this in the case for the analogue of ${\mathbf{HNMaj}}$ with Gaussian
latent vectors using Theorem 1.3 from [BBH21].

Suppose that $d=2d_{1},\Omega=\mathbb{R}^{d},$
${\mathcal{D}}=\mathcal{N}(0,I_{d})$ and
$\sigma(\mathbf{x},\mathbf{y}):=\mathds{1}\left[\sum_{i\leq
d_{1}}x_{i}y_{i}-\sum_{j>d_{1}}x_{j}y_{j}\geq 0\right].$ We want to understand
when the following inequality holds.

${\mathsf{TV}}\Big{(}\mathsf{RGG}(n,\mathbb{R}^{d},\mathcal{N}(0,I_{d}),1/2,\sigma),\mathsf{G}(n,1/2)\Big{)}=o(1).$
(16)

The edges of $\mathsf{RGG}(n,\mathbb{R}^{d},\mathcal{N}(0,I_{d}),1/2,\sigma)$
are formed as follows. Each of the latent vectors
$\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n}$ can be represented as a
concatenation of two iid standard Gaussian vectors in $\mathbb{R}^{d_{1}},$
that is $\mathbf{x}_{i}=(\mathbf{x}^{1}_{i},\mathbf{x}^{2}_{i}).$ With respect
to those, one forms the matrix $W\in\mathbb{R}^{n\times n},$ where
$W_{i,j}=\langle\mathbf{x}^{1}_{i},\mathbf{x}^{1}_{j}\rangle-\langle\mathbf{x}^{2}_{i},\mathbf{x}^{2}_{j}\rangle.$
Finally, one forms the adjacency matrix $\mathbf{A}$ of
$\mathsf{RGG}(n,\mathbb{R}^{d},\mathcal{N}(0,I_{d}),1/2,\sigma)$ by taking
$\mathbf{A}_{i,j}=sign(W_{i,j}).$ As in [BDE+14], it is enough to show that
$W$ is close in total variation to a symmetric matrix with iid entries to
conclude that Eq. 16 holds. This is our next result. Recall the definition of
$M(n)$ from Section 1.1.

######  Theorem 6.17.

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

${\mathsf{TV}}\Big{(}\mathcal{W}(n,d,-d),\sqrt{d}M(n)\Big{)}=o_{n}(1).$

###### Proof.

Since $X,Y$ are independent Gaussian matrices, so are $X-Y,X+Y.$ Thus

$V=\frac{1}{\sqrt{2}}\begin{pmatrix}X-Y\\\
X+Y\end{pmatrix}\sim\mathcal{N}(0,I_{d_{1}})^{\otimes 2n}.$

Now, consider the bipartite mask on $VV^{T}$ from Theorem 1.3. Specifically,
focus on the lower-left triangle. From $VV^{T},$ we have
$\frac{1}{2}(X+Y)(X-Y)^{T}$ and from $\sqrt{d_{1}}M(2n)+I_{2n},$ we have
$\sqrt{d_{1}}Z,$ where $Z\sim\mathcal{N}(0,1)^{n\times n}$ since it is the
lower-left corner of a GOE matrix. From Theorem 1.3, when $d={\omega}(n^{2}),$
we conclude

${\mathsf{TV}}\Big{(}\frac{1}{2}(X+Y)(X-Y),\sqrt{d_{1}}Z\Big{)}=o(1).$

By data-processing inequality (Theorem 2.3) for the function $f(V)=(V+V^{T}),$
we conclude that

${\mathsf{TV}}\Big{(}f\left(\frac{1}{2}(X+Y)(X-Y)\right),f\left(\sqrt{d_{1}}Z\right)\Big{)}=o(1).$

Now, $f(\frac{1}{2}(X+Y)(X-Y))=XX^{T}-YY^{T}\sim\mathcal{W}(n,d,-d)$ and
$f(\sqrt{d_{1}}Z)=\sqrt{d_{1}}(Z+Z^{T})\sim\sqrt{d}M(n).$ The conclusion
follows. ∎

Conversely, [BBH21, Theorem 3.2] directly shows that counting signed 4-cycles
in the adjacency matrix $\mathbf{A}$ distinguishes $W$ from a GOE matrix and,
thus, $\mathsf{RGG}(n,\mathbb{R}^{d},\mathcal{N}(0,I_{d}),1/2,\sigma)$ from
$\mathsf{G}(n,1/2),$ so the phase transition indeed occurs at
$d=\Theta(n^{2}).$

We use this result in Section 8.1 to formally demonstrate the inefficiency of
${\mathsf{KL}}$-convexity used to derive 1.5 in [LR21a].

####  6.2.1 Beyond Triangles

Thus far in this section, we showed that the triangle statistic can sometimes
be useless. Certain connections – for example, the Fourier-paired ones –
result in latent space graphs which cannot be distinguished from
$\mathsf{G}(n,p)$ using signed triangle counts. One can prove that something
more is true. For any odd $k$ and $\mathcal{H},$ an induced subgraph of the
$k$-cycle, the expected number of copies of $\mathcal{H}$ in $\mathsf{G}(n,p)$
and $\\{\pm 1\\}^{d}$ is the same whenever $\sigma$ is Fourier-paired.

At a first glance, the key word here turns out to be odd. Note that unless
$\sigma$ is constant, the expected number of signed $k$-cycles in
$\mathsf{RAG}(n,\\{\pm 1\\}^{d},p,\sigma)$ for $k$ even,
$\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{k},$ is positive and, thus,
strictly greater than the expected number for $\mathsf{G}(n,p).$ Therefore,
for any fixed $\sigma$ and $d,$ if we take $n$ to be large enough, we can
distinguish $\mathsf{RAG}(n,\\{\pm 1\\}^{d},p,\sigma)$ and $\mathsf{G}(n,p)$
by counting signed 4-cycles (or signed $k$-cycles for some other $k$ even). In
particular, this demonstrates an extremal property of Erdős-Rényi graphs which
is a priori not all obvious. For any fixed $p,$ the latent space graph
$\mathsf{RAG}(n,\\{\pm 1\\}^{d},p,\sigma)$ with the minimal expected number of
signed $k$-cycles for any even $k$ is $\mathsf{G}(n,p).$ This difference
between odd and even cycles in random graphs which are close to Erdős-Rényi is
not accidental. It plays a crucial role in the literature on quasi-random
graphs [KS06].

Nevertheless, we next show that counting (signed) even cycles is also
sometimes useless.

##  7 Detection for Typical Indicator Connections

We move on to establishing lower bounds for Theorem 4.19 and Theorem 5.1.

###  7.1 Signed Subgraph Counts

Most naturally, we would like to apply signed cycle counts to detect a random
algebraic graph. However, a simple calculation over the hypercube shows that
this approach will typically fail unless $\log|\mathcal{G}|=O(\log n).$

######  Proposition 7.1.

A fixed constant $k\in\mathbb{N},k\geq 3$ is given. With probability at least
$1-2^{-d}$ over$A\sim\mathsf{AnteU}(\mathcal{G},p),$

${\mathbf{E}}_{H\sim\mathsf{RAG}(n,\\{\pm
1\\}^{d},\sigma_{A},p_{A})}[\tau_{k,p}(H)]=O\Big{(}\frac{(2\sqrt{d})^{k}}{2^{(k-2)d/2}}\Big{)}=O\left(2^{-d/3}\right).$

###### Proof.

In light of 4.20, it is enough to prove the claim for all sets
$A\subseteq\\{\pm 1\\}^{d}$ such that
$|\widehat{\sigma_{A}}(S)|\leq\frac{2\sqrt{d}}{2^{d/2}}$ holds for all
$S\neq\emptyset$ and
$|\widehat{\sigma_{A}}(\emptyset)-p|\leq\frac{2\sqrt{d}}{2^{d/2}}.$ Let $A$ be
such a set. Applying 2.12, we have

${\mathbf{E}}_{H\sim\mathsf{RAG}(n,\\{\pm
1\\}^{d},\sigma_{A},p_{A})}[\tau_{k}(H)]=(p_{A}-p)^{k}+\sum_{S\neq\emptyset}\widehat{\sigma_{A}}(S)^{k}=O\bigg{(}2^{d}\times\Big{(}\frac{2\sqrt{d}}{2^{d/2}}\Big{)}^{k}\bigg{)},$

as desired. ∎

This makes the signed $k$-cycle statistic useless for $k=O(1)$ when
$d=\omega(\log n),p=\omega(\frac{1}{n})$ since one can trivially check that
${\mathbf{Var}}_{G\sim\mathsf{G}(n,p)}[\tau_{k}(G)]=\Theta(np^{k}(1-p)^{k}).$

###  7.2 Low Degree Polynomials

So, can we do better by considering some other poly-time computable statistic?
We show that the answer to this question is no, insofar as one considers
statistics which are low-degree polynomial tests. Our argument applies in the
same way over any finite group $\mathcal{G}$ of appropriate size. We consider
right algebraic graphs, due to their relevance to Cayley graphs, but the same
statement with the exact same proof holds for left algebraic graphs.

######  Theorem 7.2.

An integer $k=o(n)$ and real number $p\in[\frac{1}{n^{3}},1-\frac{1}{n^{3}}]$
are given. Suppose that $\mathcal{G}$ is an arbitrary group of size at least
$\exp(Ck\log n)$ for some universal constant $C.$ Let
$A\sim\mathsf{AnteU}(\mathcal{G},p).$ Consider the connection
$\sigma_{A}(\mathbf{x},\mathbf{y}):=\mathds{1}[\mathbf{x}\mathbf{y}^{-1}\in
A]$ with ${\mathbf{E}}[\sigma_{A}]=p_{A}.$ Then, one typically cannot
distinguish $\mathsf{G}(n,p)$ and
$\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})$ using low-degree polynomials
in the following sense. With high probability$1-\exp(-\Omega(k\log n))$ over
$A,$

$|{\mathbf{E}}_{G\sim\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})}P(G)-{\mathbf{E}}_{H\sim\mathsf{G}(n,p)}P(H)|=O\left(\frac{n^{2k}}{|\mathcal{G}|^{1/3}}\right)=\exp(-\Omega(k\log
n))$

holds simultaneously for all polynomials $P$ of degree at most $k$ in
variables the edges of the input graph which satisfy
${\mathbf{Var}}_{H\sim\mathsf{G}(n,p)}[P(H)]\leq 1.$

As we will see, the proof of this theorem highly resembles the proof of
Theorem 5.1.

###### Proof.

Suppose that $P$ is a polynomial of degree at most $k.$ For a graph $G,$
denote by $(G)_{(i,j)\in[n]\otimes[n]}$ the $\\{0,1\\}$ edge indicators of
edges of $G,$ where $[n]\otimes[n]$ is the set of $\binom{n}{2}$ pairs of
distinct numbers $i,j$ in $[n].$ We can express $P$ as

$P=\sum_{\mathcal{H}\subseteq[n]\otimes[n]:|\mathcal{H}|\leq
k}a_{\mathcal{H}}\prod_{(i,j)\in\mathcal{H}}\frac{G_{(i,j)}-p}{\sqrt{p(1-p)}}.$

Indeed,
$\psi_{\mathcal{H}}(G):=\prod_{(i,j)\in\mathcal{H}}\frac{G_{(i,j)}-p}{\sqrt{p(1-p)}}$
are just the $p$-based Walsh polynomials with respect to the $\\{\pm
1\\}$-valued indicators $(2G-1)_{(i,j)\in[n]\otimes[n]}.$ Note that the Walsh
polynomial $\psi_{\mathcal{H}}(G)$ corresponds to (signed) subgraph indicator
of $\mathcal{H}$ in $G.$ Now, by Parseval’s identity,

$1={\mathbf{Var}}_{H\sim\mathsf{G}(n,p)}[P(H)]=\sum_{0<|\mathcal{H}|\leq
k}a^{2}_{\mathcal{H}}.$

In particular, this means that $|a_{\mathcal{H}}|\leq 1$ holds for each non-
empty subgraph $\mathcal{H}$ with at most $k$ edges. Using triangle
inequality,

$\begin{split}&|{\mathbf{E}}_{G\sim\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})}P(G)-{\mathbf{E}}_{H\sim\mathsf{G}(n,p)}P(H)|\\\
&\leq\sum_{\mathcal{H}\subseteq[n]\otimes[n]:0<|\mathcal{H}|\leq
k}|a_{\mathcal{H}}|\times|{\mathbf{E}}_{G\sim\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})}\psi_{\mathcal{H}}(G)-{\mathbf{E}}_{H\sim\mathsf{G}(n,p)}\psi_{\mathcal{H}}(H)|\\\
&=\sum_{\mathcal{H}\subseteq[n]\otimes[n]:0<|\mathcal{H}|\leq
k}|a_{\mathcal{H}}|\times|{\mathbf{E}}_{G\sim\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})}\psi_{\mathcal{H}}(G)|\\\
&\leq\sum_{\mathcal{H}\subseteq[n]\otimes[n]:0<|\mathcal{H}|\leq
k}|{\mathbf{E}}_{G\sim\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})}\psi_{\mathcal{H}}(G)|\\\
&\leq n^{2k}\times\sup_{\mathcal{H}\subseteq[n]\otimes[n]:0<|\mathcal{H}|\leq
k}|{\mathbf{E}}_{G\sim\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})}\psi_{\mathcal{H}}(G)|,\end{split}$
(17)

where in the last line we used the fact that there are at most $n^{2k}$
choices for $\mathcal{H}$ as $|[n]\otimes[n]|=\binom{n}{2}.$ Thus, we simply
need to establish a sufficiently strong bound on
$|{\mathbf{E}}_{G\sim\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})}\psi_{\mathcal{H}}(G)|$
for all small enough $\mathcal{H}.$ We do so by taking a square of the desired
quantity and using second moment method as follows.

$\begin{split}\Psi(A)&:=|{\mathbf{E}}_{G\sim\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})}\psi_{\mathcal{H}}(G)|^{2}\\\
&\;={\mathbf{E}}_{G_{1},G_{2}\sim_{iid}\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})}\left[\psi_{\mathcal{H}}(G_{1})\psi_{\mathcal{H}}(G_{2})\right]\\\
&\;={\mathbf{E}}_{G\sim_{iid}\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})}\left[\psi_{\mathcal{K}}(G)\right],\end{split}$
(18)

where $\mathcal{K}$ is an arbitrary union of two vertex-disjoint copies of
$\mathcal{H}.$ Indeed, suppose that $\mathcal{H}$ has a vertex set
$V(\mathcal{H})\subseteq[n],$ where $|V(\mathcal{H})|\leq 2k$ (as
$|E(\mathcal{H})|\leq k$). Take some set of vertices
$V_{1}\subseteq[n]\backslash V(\mathcal{H})$ such that
$|V_{1}|=|V(\mathcal{H})|$ (this is possible since $n>4k=o(n)$) and let
$\mathcal{H}_{1}$ be an isomorphic copy of $\mathcal{H}$ on $V_{1}.$ Since the
vertex sets of $\mathcal{H}$ and $\mathcal{H}_{1}$ are disjoint, the variables
$\psi_{\mathcal{H}}(G)$ and $\psi_{\mathcal{H}_{1}}(g)$ are independent.
Indeed, $\psi_{\mathcal{H}}(G)$ only depends on latent vectors
$(\mathbf{x}_{i})_{i\in V(\mathcal{H})}$ and $\psi_{\mathcal{H}_{1}}(G)$ on
latent vectors $(\mathbf{x}_{i})_{i\in V(\mathcal{H}_{1})}.$ Furthermore, the
two variables are trivially iid. Thus,

${\mathbf{E}}_{G_{1},G_{2}\sim_{iid}\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})}\left[\psi_{\mathcal{H}}(G_{1})\psi_{\mathcal{H}}(G_{2})\right]={\mathbf{E}}_{G\sim_{iid}\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})}\left[\psi_{\mathcal{H}\cup\mathcal{H}_{1}}(G)\right],$

and $\mathcal{K}$ is isomorphic to $\mathcal{H}\cup\mathcal{H}_{1}.$

Note that $\mathcal{K}$ has at most $2k$ edges. Without loss of generality,
let $V(\mathcal{K})=\\{1,2,\ldots,s\\},$ where $s\leq 4k.$ We want to show
that, with high probability over $A,$
$\displaystyle\Psi(A)={\mathbf{E}}_{G\sim_{iid}\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})}\left[\psi_{\mathcal{K}}(G)\right]$
is small. Note that $0\leq\Psi(A)$ by construction (see Eq. 18), which will
allow us to use Markov’s inequality. Now, taking the expectation over $A,$ we
have

$\begin{split}{\mathbf{E}}_{A}[\Psi(A)]&={\mathbf{E}}_{A}{\mathbf{E}}_{G\sim_{iid}\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})}\left[\psi_{\mathcal{K}}(G)\right]\\\
&={\mathbf{E}}_{A}{\mathbf{E}}_{\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{s}\sim_{iid}\mathsf{Unif}(\mathcal{G})}\prod_{(i,j)\in
E(\mathcal{K})}\frac{\mathds{1}[\mathbf{x}_{i}\mathbf{x}_{j}^{-1}\in
A]-p}{\sqrt{p(1-p)}}\\\
&={\mathbf{E}}_{\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{s}\sim_{iid}\mathsf{Unif}(\mathcal{G})}{\mathbf{E}}_{A}\prod_{(i,j)\in
E(\mathcal{K})}\frac{\mathds{1}[\mathbf{x}_{i}\mathbf{x}_{j}^{-1}\in
A]-p}{\sqrt{p(1-p)}}.\end{split}$ (19)

We proceed in a similar fashion to Theorem 5.1. Let
$B\subseteq\mathcal{G}^{s}$ be the subset of $s$-tuples of vectors for which
the following holds. For each $(i,j)\neq(i^{\prime},j^{\prime}),$ where
$(i,j)\in[s]\otimes[s]$ and $(i^{\prime},j^{\prime})\in[s]\otimes[s],$
$\mathbf{x}_{i}\mathbf{x}_{j}^{-1}\neq\mathbf{x}_{i^{\prime}}\mathbf{x}_{j^{\prime}}^{-1}$
and
$\mathbf{x}_{j}\mathbf{x}_{i}^{-1}\neq\mathbf{x}_{i^{\prime}}\mathbf{x}_{j^{\prime}}^{-1}.$
Clearly, each of these equalities, which $B$ has to avoid, happens with
probability at most $\frac{1}{|\mathcal{G}|}$ when
$\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{s}\sim_{iid}\mathsf{Unif}(\mathcal{G}).$
As there are at most $2\binom{s}{2}^{2}\leq O(k^{4})$ such equalities to be
avoided,

${\mathbf{P}}_{\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{s}\sim_{iid}\mathsf{Unif}(\mathcal{G})}\left[(\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{s})\in
B\right]\geq 1-O\left(\frac{k^{4}}{|\mathcal{G}|}\right).$

Note that if $(\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{s})\in B,$
then

${\mathbf{E}}_{A\sim\mathsf{AnteU}(\mathcal{G},p)}\prod_{(i,j)\in
E(\mathcal{K})}\frac{\mathds{1}[\mathbf{x}_{i}\mathbf{x}_{j}^{-1}\in
A]-p}{\sqrt{p(1-p)}}=\prod_{(i,j)\in
E(\mathcal{K})}\frac{{\mathbf{E}}_{A\sim\mathsf{AnteU}(\mathcal{G},p)}\Big{[}\mathds{1}[\mathbf{x}_{i}\mathbf{x}_{j}^{-1}\in
A]-p\Big{]}}{\sqrt{p(1-p)}}=0,$

where we used that $p\leq$ This follows directly from the definition of
$\mathsf{AnteU}$ since the different terms $\mathbf{x}_{i}\mathbf{x}_{j}^{-1}$
are all in different orbits as defined in Definition 1.14. On the other hand,
whenever $(\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{s})\not\in B,$

$\displaystyle{\mathbf{E}}_{A}\prod_{(i,j)\in
E(\mathcal{K})}\frac{\mathds{1}[\mathbf{x}_{i}\mathbf{x}_{j}^{-1}\in
A]-p}{\sqrt{p(1-p)}}$ $\displaystyle\leq\bigg{\|}{\prod_{(i,j)\in
E(\mathcal{K})}\frac{\mathds{1}[\mathbf{x}_{i}\mathbf{x}_{j}^{-1}\in
A]-p}{\sqrt{p(1-p)}}}\bigg{\|}_{\infty}=\bigg{(}\max\Big{(}\sqrt{\frac{1-p}{p}},\sqrt{\frac{p}{1-p}}\Big{)}\bigg{)}^{|E(\mathcal{K})|}\leq\sqrt{n^{3}}^{2k}\leq
n^{3k},$

where we used the fact that $p\in[\frac{1}{n^{3}},1-\frac{1}{n^{3}}].$
Combining these observations,

$\displaystyle{\mathbf{E}}_{A}[\Psi(A)]$
$\displaystyle={\mathbf{E}}_{\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{s}\sim_{iid}\mathsf{Unif}(\mathcal{G})}{\mathbf{E}}_{A}\prod_{(i,j)\in
E(\mathcal{K})}\frac{\mathds{1}[\mathbf{x}_{i}\mathbf{x}_{j}^{-1}\in
A]-p}{\sqrt{p(1-p)}}$
$\displaystyle\leq(1-{\mathbf{P}}[B])n^{3k}=O\left(\frac{k^{4}n^{3k}}{|\mathcal{G}|}\right)<\frac{n^{4k}}{|\mathcal{G}|}$

for sufficiently large $n.$ Therefore, by positivity of $\Psi,$ we conclude
from Markov’s inequality that

${\mathbf{P}}[\Psi(A)\geq|\mathcal{G}|^{2/3}\times|\mathcal{G}|^{-1}]=\frac{n^{4k}}{|\mathcal{G}|^{2/3}}\leq\frac{\exp(4k\log
n)}{|\mathcal{G}|^{2/3}}.$

Thus, with high probability $1-\frac{\exp(4k\log n)}{|\mathcal{G}|^{2/3}}$
over $A,$ we conclude from Eq. 18 that

$|{\mathbf{E}}_{G\sim\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})}\psi_{\mathcal{H}}(G)|\leq|\mathcal{G}|^{-1/3},$

where we used $p=\Omega(n^{-2}).$ Taking union bound over all $O(n^{2k})$
Walsh polynomials of degree at most $k,$ we conclude that

$|{\mathbf{E}}_{G\sim\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})}\psi_{\mathcal{H}}(G)|\leq|\mathcal{G}|^{-1/3}$

holds for all $\mathcal{H}$ with at most $k$ edges with probability at least
$1-O(n^{2k}\frac{\exp(4k\log n)}{|\mathcal{G}|^{2/3}})=1-\frac{\exp(6k\log
n)}{|\mathcal{G}|^{2/3}}.$ Combining with Eq. 17, we conclude that with
probability at least $1-\frac{\exp(6k\log n)}{|\mathcal{G}|^{2/3}},$ the
inequality

$|{\mathbf{E}}_{G\sim\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})}P(G)-{\mathbf{E}}_{H\sim\mathsf{G}(n,p)}P(H)|\leq\frac{n^{2k}}{|\mathcal{G}|^{1/3}}$

holds for all polynomials $P$ satisfying the assumptions of the theorem. ∎

In particular, this means that if $|\mathcal{G}|=\exp(\omega(\log n)),$ one
cannot distinguish $\mathsf{G}(n,p)$ and
$\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})$ for typical sets
$A\sim\mathsf{AnteU}(\mathcal{G},p)$ with constant-degree polynomials and if
$|\mathcal{G}|=\exp(\omega(\log^{2}n)),$ one cannot distinguish the two graph
models with polynomials of degree $O(\log n).$ Polynomials of degree $O(\log
n)$ capture a very wide range of algorithms such as spectral methods and
others [SW22].

It turns out that the dependence on $|\mathcal{G}|$ is essentially tight and
this is illustrated by a variety of simple algorithms which identify the
latent space structure for groups of size at most $\exp(C\log n)=n^{C}$ for
appropriate constants $C.$ In fact, some of these algorithms do not even use
the algebraic structure, but apply over arbitrary latent-space graphs with
indicator connections! One such algorithm (which is not a direct converse to
the low-degree polynomials) is the following.

######  Theorem 7.3.

Suppose that $\Omega$ is an arbitrary finite latent space of size $o(n^{2}).$
Let $\sigma$ be any indicator connection with
${\mathbf{E}}_{\mathbf{x},\mathbf{y}\sim\mathsf{Unif}(\Omega)}[\sigma(\mathbf{x},\mathbf{y})]=p=\omega(\frac{\log
n}{n}).$ One can distinguish the graphs $\mathsf{G}(n,p)$ and
$\mathsf{PLSG}(n,\Omega,\mathsf{Unif},p,\sigma)$ with high probability in
polynomial time using $O(n^{2})$ polynomials of degree 2. Namely, in
$\mathsf{PLSG}(n,\Omega,\mathsf{Unif},p,\sigma),$ with high probability there
exist two vertices $u\neq v$ which satisfy the following property. For any
$w\not\in\\{v,u\\},$ $(v,w)$ is an edge if and only if $(u,w)$ is an edge.

###### Proof.

Call two vertices $u\neq v$ neighbourhood-identical if for any
$w\not\in\\{v,u\\},$ $(v,w)$ is an edge if and only if $(u,w)$ is an edge. A
simple union bound calculation shows that in $\mathsf{G}(n,p),$ the
probability that two neighbourhood-identical vertices exist is of order
$O\left(\binom{n}{2}(1-2p+p^{2})^{n}\right)=o(1).$ On the other hand, by the
Birthday Paradox, whenever $|\mathcal{G}|=o(n^{2}),$ with high probability
there exist two integers $u,v\in\\{1,2,\ldots,n\\}$ such that
$\mathbf{x}_{u}=\mathbf{x}_{v}.$ Clearly, whenever
$\mathbf{x}_{u}=\mathbf{x}_{v},$ the vertices $u$ and $v$ are neighbourhood-
identical.

Finally, we need to translate the above argument to degree 2 polynomials. One
simple way to do this is to analyze the supremum over all pairs
$(i,j)\in[n]\otimes[n]$ of

$P_{i,j}(G):=\sum_{k\not\in\\{i,j\\}}(1-G_{i,k}-G_{j,k})^{2}.$

Note that $P_{i,j}$ counts the number of vertices $u$ such that $(i,u)$ is an
edge if and only if $(j,u)$ is an edge. ∎

For more direct converses of the low-degree framework one can, for example,
count signed four-cycles. We have the following proposition, the proof of
which we deffer to Appendix F due to its relative simplicity.

######  Theorem 7.4.

Suppose that $\Omega$ is an arbitrary finite latent space of size
$o(n^{1/8}).$ Let $\sigma$ be any indicator connection with
${\mathbf{E}}_{\mathbf{x},\mathbf{y}\sim\mathsf{Unif}(\Omega)}[\sigma(\mathbf{x},\mathbf{y})]=p>0.$
One can distinguish the graphs $\mathsf{G}(n,p)$ and
$\mathsf{PLSG}(n,\Omega,\mathsf{Unif},p,\sigma)$ with high probability in
polynomial time using the signed 4-cycle statistic.

The constant $1/8$ can easily be improved to $1/3$ (and, perhaps, beyond) if
we consider random algebraic graphs. We do not pursue this.

###  7.3 Statistical Detection

So far, in this section we have provided strong evidence that
$|\mathcal{G}|=\exp(\log^{O(1)}n)$ is the computational limit for detecting
$\mathsf{RRAG}(h,\mathcal{G},p_{A},\sigma_{A})$ for a typical
$A\sim\mathsf{AnteU}(\mathcal{G},p).$ This leaves a large gap from the
$|\mathcal{G}|=\Omega(n\log\frac{1}{p})$ in Theorem 5.1 above which we proved
that the two graph models are statistically indistinguishable. So, a question
remains - can we prove a better statistical detection rate, ideally on the
order of $\exp(\tilde{\Omega}(n))$? We obtain the following lower-bound, which
matches our indistinguishability rate when $p=\Omega(1).$ It holds in the more
general setup of probabilistic latent space graphs.

######  Theorem 7.5.

There exists an absolute constant $C$ with the following property. Suppose
that $\min(p,1-p)=\omega(\frac{1}{n^{2}})$ and $\Omega$ is a latent space of
size at most $\exp(CnH(p)),$ where$H(p)=-p\log_{2}p-(1-p)\log_{2}(1-p)$ is the
binary entropy. Let ${\mathcal{D}}$ be an arbitrary distribution over $\Omega$
and let $\sigma$ be an arbitrary $\\{0,1\\}$-valued connection. Then,

${\mathsf{TV}}\Big{(}\mathsf{G}(n,p),\mathsf{PLSG}(n,\Omega,\mathcal{D},\sigma,p)\Big{)}=1-o(1).$

###### Proof.

We analyze the case of $p\leq\frac{1}{2},$ in which we simply have
$|\Omega|\leq\exp(C^{\prime}p\log\frac{1}{p}n).$ We apply a simple entropy
argument. Consider the $n$ latent vectors,
$\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n}.$ The $n$-tuple
$(\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n})$ can take at most
$|\mathcal{G}|^{n}\leq\exp(C^{\prime}n^{2}p\log\frac{1}{p})$ values. Since
edges are deterministic functions of latent vector (because $\sigma$ is
$\\{0,1\\}$-valued), $\mathsf{PLSG}(n,\Omega,\mathcal{D},\sigma,p)$ is a
distribution with support of size at most
$\exp(C^{\prime}n^{2}p\log\frac{1}{p}).$ Denote this support by $S.$

Now, consider $H\sim\mathsf{G}(n,p).$ First, by standard Chernoff bounds,

${\mathbf{P}}\bigg{[}|E(H)|\leq\frac{1}{2}{\mathbf{E}}[|E(H)|]\bigg{]}\leq\exp(-\Omega({\mathbf{E}}[|E(H)|]))=\exp(-\Omega(n^{2}p))=o(1).$

On the other hand, for any fixed graph $K$ on at least
$\frac{1}{2}{\mathbf{E}}|E(H)|=\frac{1}{2}\binom{n}{2}p$ vertices, we have

${\mathbf{P}}[H=K]=p^{|E(K)|}(1-p)^{\binom{n}{2}-|E(K)|}\leq
p^{|E(K)|}\leq\exp\bigg{(}\log
p\frac{1}{2}\binom{n}{2}p\bigg{)}\leq\exp\bigg{(}-\frac{1}{5}n^{2}p\log\frac{1}{p}\bigg{)}.$

Combining these two inequalities, we conclude that

$\displaystyle{\mathbf{P}}_{H\sim\mathsf{G}(n,p)}[H\in S^{c}]$
$\displaystyle=1-{\mathbf{P}}_{H\sim\mathsf{G}(n,p)}[H\in S]$
$\displaystyle\geq
1-{\mathbf{P}}\bigg{[}|E(H)|\leq\frac{1}{2}\binom{n}{2}p\bigg{]}-{\mathbf{P}}\bigg{[}|E(H)|>\frac{1}{2}\binom{n}{2}p,H\in
S\bigg{]}$ $\displaystyle\geq
1-o(1)-|S|\times\sup_{K\;:\;|E(K)|>\frac{1}{2}\binom{n}{2}p}{\mathbf{P}}[H=K]$
$\displaystyle\geq
1-o(1)-\exp\bigg{(}-\frac{1}{5}n^{2}p\log\frac{1}{p}\bigg{)}\times|S|$
$\displaystyle=1-o(1)-\exp\bigg{(}-\frac{1}{5}n^{2}p\log\frac{1}{p}\bigg{)}\times\exp\bigg{(}C^{\prime}n^{2}p\log\frac{1}{p}\bigg{)}=1-o(1)$

for small enough $C^{\prime}.$ The definition of total variation immediately
implies the desired conclusion. ∎

##  8 Discussion and Future Directions

We introduced random algebraic graphs, which turn out to be a very expressive
family of random graph models. In particular, it captures the well-studied
random geometric graphs on the unit sphere with connections depending on inner
products of latent vectors, the stochastic block model, and blow-ups and
random subgraphs of Cayley graphs. We studied in depth the model when the
latent space is given by the group $\\{\pm 1\\}^{d}.$ The hypercube is of
primary interest as it simultaneously captures a geometry of “uniformly
arranged” directions like the sphere, but also has an abelian-group structure.
Using this duality of the hypercube, we exploited tools from Boolean Fourier
analysis to study a wide range of non-monotone and/or non-symmetric
connections, many of which seem unapproachable with previous techniques for
studying random geometric graphs. Some of these connections revealed new
phenomena. Perhaps most interesting among them is a suggested nearly-
exponential statistical-computational gap in detecting geometry over the
hypercube for almost all indicator connections with a prescribed density. We
extended this to arbitrary groups of appropriate size and interpreted the
respective result in the language of random Cayley graphs.

As promised in the beginning, we briefly discuss which of our results on the
hypercube can be attributed to the algebraic structure of $\\{\pm 1\\}^{d}$
and which to the geometric.

  1. 1.

Algebraic. Two of our results stand out as algebraic. First, our results on
indicators of $s$ intervals show that for $s$ sufficiently large, even though
$\sigma$ only depends on the inner product of latent vectors, the dimension
might need to be an arbitrary large function of $n$ for the phase transition
to Erdős-Rényi to occur, Corollaries 4.14 and 6.8. This, as discussed in
Remark 6.5, is a phenomenon specific to the hypercube as it captures the
arithmetic property of parity. As follows Theorem 1.2, random geometric graphs
with Gaussian latent vectors become indistinguishable from Erdős-Rényi when
$\sigma$ only depends on the inner product for $d=\omega(n^{3}),$ regardless
of the specific form of $\sigma.$ Second, our result on typical indicator
connections Theorem 4.19 not only relies on the fact that the hypercube is a
group, but it also utilizes the fact that it is a finite latent space. It is
far from obvious how to define “typical dense indicator connections” when the
latent space is, say, the sphere. In Theorem 5.1, we extend Theorem 4.19 to
more general groups of appropriate size, which is further evidence for the
dependence of this result on the underlying group structure.

  2. 2.

Geometric. We believe that most of the other results are a feature of the
geometry of $(\\{\pm 1\\}^{d},\mathsf{Unif},\sigma)$ and, thus, likely extend
to other random geometric graphs such as ones defined over the sphere. First,
we extended the result of Liu and Racz on Lipschitz connections Corollary 4.4
to non-monotone connections, which we believe can be also done over the sphere
or Gaussian space (potentially, via arguments close to the ones of [LR21a]).
Next, we showed that if $\sigma$ is even — that is, depends on
$|\langle\mathbf{x},\mathbf{y}\rangle|$ — phase transitions occur at
$d=\tilde{\Theta}(n^{3/2})$ instead of $d=\tilde{\Theta}(n^{3})$ (Corollaries
4.10, 4.5 and 4.14). Again, this behaviour seems to be purely geometric and we
expect it to extend to Gauss space and the unit sphere.

Since this work is the first to explicitly study random algebraic graphs and
to apply tools from Boolean Fourier analysis to random geometric graphs in
high dimension, it opens the door to many new exciting lines of research.

###  8.1 On The Indistinguishability Argument of Liu and Racz

Our indistinguishability results are based on 1.5 due to Liu and Racz.
Unfortunately, as the authors themselves note in [LR21a], the statement of
this claim is suboptimal. We join Liu and Racz in posing the task of improving
1.5.

The current paper demonstrates that such an improvement can have further
interesting consequences beyond closing the gap in Theorem 1.4. Of special
interest is its relevance to the Boolean analogue of 1.1 demonstrated in
Corollary 4.8. In light of this connection, one could hope to close 1.1 with
an improved 1.5. Further applications related to the current paper are 4.16
and the gaps in the setting of union of intervals (Corollaries 6.8 and 4.14),
low degree polynomials (Sections 4.1.5 and 6.1.4) coefficient contractions and
repulsion-attraction twists (Sections 4.2 and 6.2), and the statistical phase
transition for typical random algebraic graphs Theorems 5.1 and 7.5.

Here, we formally prove two limitations of 1.5.

##### 1\. Sublinear dimensions for indicator connections.

First, we show that if $\sigma$ is an indicator with expectation $p<1/2,$ one
cannot hope to prove indistinguishability for $d=o(n)$ over the hypercube
using 1.5. Suppose that $n>8d$ and $\sigma$ is $\\{0,1\\}$-valued, in which
case

$\sup_{\mathbf{g}}\gamma(\mathbf{g})=\sup_{\mathbf{g}}\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{2}\omega_{S}(\mathbf{g})=\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{2}={\mathbf{Var}}[\sigma]=p(1-p).$

Consider the term $t=2d$ for $k=4d$ in Eq. 4. Using
$\|\gamma\|_{t}^{t}\geq\frac{1}{2^{d}}\left\lVert\gamma\right\rVert^{t}_{\infty}=\frac{1}{2^{d}}{\mathbf{Var}}[\sigma]^{t}=\frac{p^{t}(1-p)^{t}}{2^{d}},$
together with the positivity in Proposition 3.2, we conclude

$\displaystyle\sum_{t=0}^{4d}\binom{4d}{t}\frac{{\mathbf{E}}[\gamma^{t}]}{p^{t}(1-p)^{t}}$
$\displaystyle\geq\binom{4d}{2d}\frac{{\mathbf{E}}[\gamma^{2d}]}{p^{2d}(1-p)^{2d}}$
$\displaystyle\geq\binom{4d}{2d}\times\frac{p^{2d}(1-p)^{2d}}{2^{d}}\frac{1}{p^{2d}(1-p)^{2d}}$
$\displaystyle\geq\binom{4d}{2d}\frac{1}{2^{d}}\geq 2^{d}.$

This shows that the bound used in 1.5 gives a KL-divergence at least $d$ and,
thus, no non-trivial bound on total variation. Note that there is a
significant gap to the entropy bound of $d=\tilde{\Omega}(np)$ when $p=o(1)$
Theorem 7.5.

##### 2\. Inefficiency in KL-Convexity.

Using our observation on differences of Wishart matrices in Section 4.2, we
give a formal proof that the KL-convexity used by Racz and Liu in deriving 1.5
is indeed at least sometimes suboptimal. Consider
$(\Omega,{\mathcal{D}})=(\mathbb{R}^{d},\mathcal{N}(0,I_{d})),$ where without
loss of generality $d$ is even, $d=2d_{1}.$ Consider the following two
indicator connections:

$\displaystyle\sigma_{+}(\mathbf{x},\mathbf{y})=\mathds{1}[\sum_{i=1}^{d}x_{i}y_{i}\geq
0],$
$\displaystyle\sigma_{+,-}(\mathbf{x},\mathbf{y})=\mathds{1}[\sum_{i=1}^{d_{1}}x_{i}y_{i}-\sum_{i=d_{1}+1}^{2d_{1}}x_{i}y_{i}\geq
0].$

Clearly, both have expectation $1/2.$ From [BDE+14], we know that
$\mathsf{RGG}(n,\mathbb{R}^{d},\mathcal{N}(0,I_{d}),\sigma_{+},1/2)$ converges
to $\mathsf{G}(n,1/2)$ in ${\mathsf{TV}}$ if and only if $d=\omega(n^{3}).$
However, Theorem 6.17 shows that
$\mathsf{RGG}(n,\mathbb{R}^{d},\mathcal{N}(0,I_{d}),\sigma_{+,-},1/2)$ already
converges to $\mathsf{G}(n,1/2)$ in ${\mathsf{TV}}$ when $d=\omega(n^{2}).$

Despite this difference, once KL-convexity is applied as in [LR21a], the
bounds on the two models become identical. Namely, the proof in [LR21a] goes
as follows. Let $\mathbf{A}$ be the adjacency matrix of
$\mathsf{RGG}(n,\mathbb{R}^{d},\mathcal{N}(0,I_{d}),\sigma,1/2)$ and let
$\mathbf{B}$ be the adjacency matrix of $\mathsf{G}(n,1/2).$ Let
$\mathbf{A}_{k},\mathbf{B}_{k}$ be the principle minors of order $k,$ and let
$\mathbf{a}_{k},\mathbf{b}_{k}$ be the respective last rows. Finally, let
$\mathbf{X}=(\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n})^{T}\in\mathbb{R}^{n\times
d}$ be the matrix of latent vectors and $\mathbf{X}_{k}$ its $k\times d$
submatrix on the first $k$ rows. Clearly, $\mathbf{X}_{k}$ determines
$\mathbf{A}_{k}.$

Then, Racz and Liu write:

$\displaystyle{\mathsf{KL}}\Big{(}\mathsf{RGG}(n,\mathbb{R}^{d},\mathcal{N}(0,I_{d}),\sigma,1/2)\|\mathsf{G}(n,1/2)\Big{)}$
$\displaystyle={\mathsf{KL}}(\mathbf{A}\|\mathbf{B})$
$\displaystyle=\sum_{k=0}^{n-1}{\mathbf{E}}_{\mathbf{A}_{k}}{\mathsf{KL}}\Big{(}\mathbf{a}_{k+1}|\mathbf{A}_{k}\|\mathbf{b}_{k+1}|\mathbf{B}_{k}=\mathbf{A}_{k}\Big{)}$
$\displaystyle=\sum_{k=0}^{n-1}{\mathbf{E}}_{\mathbf{A}_{k}}{\mathsf{KL}}\Big{(}\mathbf{a}_{k+1}|\mathbf{A}_{k}\|\mathbf{b}_{k+1}\Big{)}$
$\displaystyle\leq\sum_{k=0}^{n-1}{\mathbf{E}}_{\mathbf{X}_{k},\mathbf{A}_{k}}{\mathsf{KL}}\Big{(}\mathbf{a}_{k+1}|\mathbf{A}_{k},\mathbf{X}_{k}\|\mathbf{b}_{k+1}\Big{)}$
$\displaystyle=\sum_{k=0}^{n-1}{\mathbf{E}}_{\mathbf{X}_{k}}{\mathsf{KL}}\Big{(}\mathbf{a}_{k+1}|\mathbf{X}_{k}\|\mathbf{b}_{k+1}\Big{)}.$

We claim that at this point, there is noting distinguishing $\sigma_{+}$ and
$\sigma_{+,-}.$ Namely, we claim that $\mathbf{a}^{(+)}_{k+1}|\mathbf{X}_{k}$
and $\mathbf{a}^{(+,-)}_{k+1}|\mathbf{X}_{k}$ have identical distributions for
any fixed $k$ (where the subscripts show the dependence on $\sigma$). This
captured by the following simple fact. Take any $\mathbf{v}\in\\{0,1\\}^{k}.$
Then,

$\displaystyle{\mathbf{P}}[\mathbf{a}^{(+)}_{k+1}=\mathbf{v}|\mathbf{X}_{k}]$
$\displaystyle={\mathbf{P}}\bigg{[}\mathds{1}\bigg{[}\sum_{i=1}^{d}(\mathbf{x}_{k+1})_{i}(\mathbf{x}_{j})_{i}\bigg{]}=\mathbf{v}_{j}\;\forall
j\in[k]\bigg{]}$
$\displaystyle={\mathbf{P}}\bigg{[}\mathds{1}\bigg{[}\sum_{i=1}^{d_{1}}(\mathbf{x}_{k+1})_{i}(\mathbf{x}_{j})_{i}-\sum_{i=d_{1}}^{2d}(-(\mathbf{x}_{k+1})_{i})(\mathbf{x}_{j})_{i}\bigg{]}=\mathbf{v}_{j}\;\forall
j\in[k]\bigg{]}$
$\displaystyle{\mathbf{P}}[\mathbf{a}^{(+,-)}_{k+1}=\mathbf{v}|\mathbf{X}_{k}],$

which follows from the fact that

$(\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{d_{1}},\mathbf{x}_{d_{1}+1},\mathbf{x}_{d_{1}+2},\ldots,\mathbf{x}_{d})\longrightarrow(\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{d_{1}},-\mathbf{x}_{d_{1}+1},-\mathbf{x}_{d_{1}+2},\ldots,-\mathbf{x}_{d})$

is a measure preserving map on
$\bigg{(}\mathbb{R}^{d},\mathcal{N}(0,I_{d})\bigg{)}.$

The fact that the 1.5 cannot distinguish between $\sigma_{+}$ and
$\sigma_{+,-}$ also has a natural interpretation in the hypercube setting.
Note that $\sigma_{+}$ is just the ${\mathbf{Maj}}$ connection and
$\sigma_{+,-}$ is the ${\mathbf{HNMaj}}$ connection (see Section 6.2).
However, those two functions only differ in the signs of their Fourier
coefficients. However, any information about signs is lost when one analyses
the respective autocorrelation $\gamma$ as Fourier coefficients are squared
(see Section 2.2).

###  8.2 Groups Beyond the Hypercube

As already discussed, the random algebraic model is very expressive and, for
that reason, it would be interesting to consider further instances of it,
especially over groups other than $\\{\pm 1\\}^{d}.$ Nevertheless, these other
groups remain challenging and interesting, especially in the case of concrete
rather than typical connections.

##### 1\. Abelian Groups.

We believe that products of small (of, say, constant size) cyclic groups can
be handled in nearly the same way in which we handled the hypercube. In
particular, for such groups a very strong hypercontratcivity result analogous
to Theorem 2.7 holds (see [ODo14, Ch. 10]). Nevertheless, analysing more
general groups - even in the finite case - seems challenging. If one chooses
to study those via Fourier analysis, this could lead to a fruitful
investigation of complex Wishart matrices since functions of finite groups are
spanned by their representations over the complex plane. Similarly, one would
encounter complex representations when studying connections over finite-
dimensional tori. High-dimensional random geometric graphs over tori are
studied, for example, in [FGK+23].

##### 2\. Non-Abelian Groups.

The situation with non-abelian groups seems more challenging even in the
finite case due to the fact that 1-dimensional characters are insufficient to
span all functions. Several alternative directions seem viable. As a first
step, one could study connections depending only on conjugacy classes, which
are spanned by 1-dimensional characters. Alternatively, one could try to
develop hyperconcentration tools in the non-abelian case as in [FKL+20]. This
seems like a difficult but extremely worthwhile pursuit even independently of
random geometric graphs. Finally, in the finite case, one could undertake a
purely combinatorial approach based on the relationship between random
algebraic graphs and Cayley graphs outlined in Section 1.3.

In the infinite case, it could be especially fruitful to study the orthogonal
group, which is relevant to spherical random geometric graphs (see Section
1.3).

###  8.3 The Statistical-Computational Gap

In Section 7, we gave evidence for a new statistical-computational gap. We
propose several further directions to studying it.

######  Problem 8.1.

Find explicit group $\mathcal{G}$ and set $A\subseteq\mathcal{G}$ for which
one cannot distinguish $\mathsf{G}(n,p)$
and$\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})$ using low-degree
polynomials when $|\mathcal{G}|=\exp(\log^{O(1)}n).$ Does there exist such a
pair $\mathcal{G},A$ with a short (polynomial in $n$) description?

Note that our arguments only show that typical sets $A$ satisfy the desired
property, but provide no means of constructing such sets $A.$ Similarly, when
$\mathcal{G}$ is not a hypercube, our proofs for statistical
indistinguishability are not constructive, which leads to the following
question.

######  Problem 8.2.

Given is a number $n$ and a group $\mathcal{G}$ of size $\exp(\Omega(n)).$
Find an explicit set $A\subseteq\mathcal{G}$ for which

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

Does there exist such a set $A$ with a short (polynomial in $n$) description?

Based on our construction over the hypercube in Remark 4.21, we believe that
the answer to the existence question should be affirmative for general groups.

Another natural direction is proving hardness results against other
computational models than low-degree polynomials. We note that our current
result leaves many possible poly-time algorithms unaddressed such as ones
based on arithmetic. Low-degree polynomials over $\mathbb{F}_{2}$ are not
necessarily low-degree polynomials over $\mathbb{R}$ (see [ODo14]). Refuting
the statistical-computational gap we proposed for general groups via
arithmetic-based polynomial-time algorithms does not seem completely
unfeasible due to the underlying arithmetic in random algebraic graphs.

###  8.4 Boolean Fourier Analysis and Probability

We end with a few directions in Boolean Fourier analysis and probability
related to the current paper that might be of independent interest.

##### 1\. Wishart Matrices.

Theorem 6.17 suggests that differences of Wishart matrices might behave very
differently from Wishart matrices. It could be interesting to study more
general linear combinations of Wishart matrices. Specifically, it could be
interesting to study the following problem asking for the linear combination
closest to GOE.

######  Problem 8.3.

Given are $n,d_{1},d_{2},\ldots,d_{k}\in\mathbb{N}.$ Let
$X_{1},X_{2},\ldots,X_{k}$ be $k$ independent Gaussian matrices where,
$X_{i}\sim\mathcal{N}(0,I_{d_{i}})^{\otimes n}\in\mathbb{R}^{n\times d_{i}}.$
Find

$\mathbf{a}\in\arg\min_{\mathbf{a}\;:\;\left\lVert\mathbf{a}\right\rVert_{2}=1}{\mathsf{TV}}\Big{(}\sum_{i=1}^{k}a_{i}X_{i}X_{i}^{T},\sqrt{\sum_{i=1}^{k}d_{i}}M(n)+\left(\sum_{i=1}^{k}d_{i}\alpha_{i}\right)I_{n}\Big{)}.$

Tools related to the eigenvalues of Wishart matrices similar to the ones
developed in [KC20] for the complex case may be useful.

##### 2\. Hypercontractivity.

In Theorem 3.5, we developed novel, to the best of our knowledge, bounds on
the moments of elementary symmetric polynomials of Rademacher variables in
certain regimes. As discussed, these also hold with standard Gaussian and
uniform spherical arguments. We noted that these bounds improve the classical
hypercontractivity result of Theorem 2.7 because of the small spectral
$\infty$-norm of the respective polynomials. We wonder whether one can
generalize this phenomenon beyond (signed) elementary symmetric polynomials.

##### 3\. Bohnenblust-Hille and Level-$k$ Inequalities.

In Section 4.1.5, we used a combination of level-$k$ inequalities Theorem 2.8
and the corollary of the Bohnenblust-Hille inequality given in Corollary 2.10.
We wonder if there is a stronger result that interpolates between the two.
Specifically, in the case of symmetric polynomials, we pose the following
question.

######  Problem 8.4.

Does there exist a universal constant $c>0$ such that for any symmetric
polynomial $f:\\{\pm 1\\}^{d}\longrightarrow[0,1]$ of constant degree with
${\mathbf{E}}[f]=p,$ the inequality
$\displaystyle{\mathbf{Var}}[f]=O\left(\frac{p^{c}}{d}\right)$ holds?

Such an inequality would, in particular, improve the bounds in our Corollary
4.17.

##### 4\. Interpretable Boolean Functions Without Low-Degree and High-Degree
Terms.

In Proposition 6.13 we constructed a function $\sigma:\\{\pm
1\\}^{d}\longrightarrow[0,1]$ with weight 0 on levels
$1,2,\ldots,m-1,d-m+1,d-m+2,\ldots,d$ and variance of order
$\tilde{\Omega}(1)$ when $m$ is a constant. We wonder whether there are
interpretable functions satisfying these properties when $m>3.$

## Acknowledgements

We would like to thank Miklos Racz for a helpful discussion.

## References

  * [AD86] David Aldous and Persi Diaconis  “Shuffling Cards and Stopping Times”  In _The American Mathematical Monthly_ 93.5 Taylor & Francis, 1986, pp. 333–348  URL: https://doi.org/10.1080/00029890.1986.11971821
  * [Alo13] Noga Alon  “The chromatic number of random Cayley graphs” Special Issue in memory of Yahya Ould Hamidoune  In _European Journal of Combinatorics_ 34.8, 2013, pp. 1232–1243  URL: https://www.sciencedirect.com/science/article/pii/S019566981300084X
  * [AR94] Noga Alon and Yuval Roichman  “Random Cayley graphs and expanders”  In _Random Structures & Algorithms_ 5.2, 1994, pp. 271–284  URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.3240050203
  * [BB19] Matthew Brennan and Guy Bresler  “Optimal average-case reductions to sparse pca: From weak assumptions to strong hardness”  In _32nd Annual Conference on Learning Theory_ , 2019, pp. 469–470  PMLR
  * [BBH21] Matthew Brennan, Guy Bresler and Brice Huang  “De Finetti-Style Results for Wishart Matrices: Combinatorial Structure and Phase Transitions”, 2021  arXiv:2103.14011
  * [BBH22] Matthew Brennan, Guy Bresler and Brice Huang  “Threshold for Detecting High Dimensional Geometry in Anisotropic Random Geometric Graphs” To appear in Random Structures and Algorithms, 2022  URL: 10.48550/arXiv.2206.14896
  * [BBN20] Matthew Brennan, Guy Bresler and Dheeraj Nagaraj  “Phase transitions for detecting latent geometry in random graphs”  In _Probability Theory and Related Fields_ 178, 2020, pp. 1215–1289
  * [BDE+14] Sébastien Bubeck, Jian Ding, Ronen Eldan and Miklós Rácz  “Testing for high-dimensional geometry in random graphs”  In _Random Structures & Algorithms_ 49, 2014
  * [BG15] Sébastien Bubeck and Shirshendu Ganguly  “Entropic CLT and Phase Transition in High-dimensional Wishart Matrices”  In _International Mathematics Research Notices_ , 2015
  * [Bon70] Aline Bonami  “Étude des coefficients de Fourier des fonctions de $L^{p}(G)$”  In _Annales de l’institut Fourier_ 20.2 Association des Annales de l’Institut Fourier, 1970, pp. 335–402  URL: http://eudml.org/doc/74019
  * [Con17] David Conlon  “Hypergraph expanders from Cayley graphs”  In _Israel Journal of Mathematics_ 233, 2017
  * [CW17] Didier Ch’etelat and Martin T. Wells  “The middle-scale asymptotics of Wishart matrices”  In _The Annals of Statistics_ , 2017  URL: https://www.jstor.org/stable/26784041
  * [DC22] Quentin Duchemin and Yohann Castro  “Random Geometric Graph: Some recent developments and perspectives”, 2022  arXiv:2203.15351
  * [DGL+11] Luc Devroye, András György, Gábor Lugosi and Frederic Udina  “High-Dimensional Random Geometric Graphs and their Clique Number”  In _Electronic Journal of Probability_ 16 Institute of Mathematical StatisticsBernoulli Society, 2011, pp. 2481–2508  URL: https://doi.org/10.1214/EJP.v16-967
  * [DH96] Carl Dou and Martin Hildebrand  “Enumeration and random random walks on finite groups”  In _The Annals of Probability_ 24.2 Institute of Mathematical Statistics, 1996, pp. 987–1000  URL: https://doi.org/10.1214/aop/1039639374
  * [EAG+20] Vittorio Erba, Sebastiano Ariosto, Marco Gherardi and Pietro Rotondo  “Random geometric graphs in high dimension”  In _Phys. Rev. E_ 102 American Physical Society, 2020, pp. 012306  URL: https://link.aps.org/doi/10.1103/PhysRevE.102.012306
  * [EI22] Alexandros Eskenazis and Paata Ivanisvili  “Learning Low-Degree Functions from a Logarithmic Number of Random Queries”  In _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ , STOC 2022  Association for Computing Machinery, 2022, pp. 203–207  URL: https://doi.org/10.1145/3519935.3519981
  * [EM20] Ronen Eldan and Dan Mikulincer  “Information and Dimensionality of Anisotropic Random Geometric Graphs”  In _Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 2017-2019 Volume I_ Cham: Springer International Publishing, 2020, pp. 273–324  URL: https://doi.org/10.1007/978-3-030-36020-7_13
  * [EMP22] Ronen Eldan, Dan Mikulincer and Hester Pieters  “Community detection and percolation of information in a geometric setting”  In _Combinatorics, Probability and Computing_ 31, 2022, pp. 1–22  URL: https://doi.org/10.1017/S0963548322000098
  * [ES16] Ernesto Estrada and Matthew Sheerin  “Consensus dynamics on random rectangular graphs” Nonlinear Dynamics on Interconnected Networks  In _Physica D: Nonlinear Phenomena_ 323-324, 2016, pp. 20–26  URL: https://www.sciencedirect.com/science/article/pii/S0167278915002171
  * [FGK+23] Tobias Friedrich, Andreas Göbel, Maximilian Katzmann and Leon Schiller  “Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs”, 2023  arXiv:2302.04113
  * [FKL+20] Yuval Filmus, Guy Kindler, Noam Lifshitz and Dor Minzer  “Hypercontractivity on the symmetric group”, 2020  arXiv:2009.05503
  * [Hae12] Martin Haenggi  “Random geometric graphs and continuum percolation”  In _Stochastic Geometry for Wireless Networks_ Cambridge University Press, 2012, pp. 221–245  URL: https://doi.org/10.1017/CBO9781139043816.012
  * [Han] Ramon van Handel  “Lecture Notes on Probability in High Dimension”  URL: https://web.math.princeton.edu/~rvan/APC550.pdf
  * [HO21] Jonathan Hermon and Sam Olesker-Taylor  “Cutoff for Almost All Random Walks on Abelian Groups”, 2021  arXiv:2102.02809
  * [HRP08] Desmond J. Higham, Marija Rašajski and Nataša Pržulj  “Fitting a geometric graph to a protein–protein interaction network”  In _Bioinformatics_ 24.8, 2008, pp. 1093–1099  URL: https://doi.org/10.1093/bioinformatics/btn079
  * [JL13] Tiefeng Jiang and Danning Li  “Approximation of Rectangular Beta-Laguerre Ensembles and Large Deviations”  In _Journal of Theoretical Probability_ 28, 2013, pp. 804–847  URL: https://ideas.repec.org/a/spr/jotpro/v28y2015i3d10.1007_s10959-013-0519-7.html
  * [KC20] Santosh Kumar and S Sai Charan  “Spectral statistics for the difference of two Wishart matrices”  In _Journal of Physics A: Mathematical and Theoretical_ 53.50 IOP Publishing, 2020  URL: https://doi.org/10.1088%5C%2F1751-8121%5C%2Fabc3fe
  * [KKL88] Jeff D. Kahn, Gil Kalai and Nathan Linial  “The influence of variables on Boolean functions”  In _29th Annual Symposium on Foundations of Computer Science_ , 1988, pp. 68–80  URL: https://ieeexplore.ieee.org/document/21923
  * [KS06] Michael Krivelevich and Benny Sudakov  “Pseudo-random Graphs”  In _More Sets, Graphs and Numbers: A Salute to Vera Sós and András Hajnal_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 199–262  URL: https://doi.org/10.1007/978-3-540-32439-3_10
  * [KTW14] Subhash Khot, Madhur Tulsiani and Pratik Worah  “A Characterization of Strong Approximation Resistance”  In _Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing_ , STOC ’14  New York, New York: Association for Computing Machinery, 2014, pp. 634–643  URL: https://doi.org/10.1145/2591796.2591817
  * [LMS+22] Siqi Liu, Sidhanth Mohanty, Tselil Schramm and Elizabeth Yang  “Local and global expansion in random geometric graphs”, 2022  arXiv:2210.00158
  * [LMS+22a] Siqi Liu, Sidhanth Mohanty, Tselil Schramm and Elizabeth Yang  “Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs”  New York, NY, USA: Association for Computing Machinery, 2022  URL: https://doi.org/10.1145/3519935.3519989
  * [LR21] Suqi Liu and Miklos Racz  “Phase transition in noisy high-dimensional random geometric graphs”, 2021  arXiv:2103.15249
  * [LR21a] Suqi Liu and Miklós Z. Rácz  “A probabilistic view of latent space graphs and phase transitions”  In _ArXiv_ , 2021  arXiv:2110.15886
  * [ODo14] Ryan O’Donnell  “Analysis of Boolean Functions”  Cambridge University Press;, 2014  URL: https://arxiv.org/abs/2105.10386
  * [Pen03] Mathew Penrose  “Random Geometric Graphs”  Oxford University Press, 2003  URL: https://doi.org/10.1093/acprof:oso/9780198506263.001.0001
  * [PWng] Yuri Polianskiy and Yihong Wu  “Information Theory: From Coding to Learning”  Cambridge University Press, Forthcoming  URL: https://people.lids.mit.edu/yp/homepage/data/itbook-export.pdf
  * [RB17] Miklós Z. Rácz and Sébastien Bubeck  “Basic models and questions in statistical network analysis”  In _Statistics Surveys_ 11 Amer. Statist. Assoc., the Bernoulli Soc., the Inst. Math. Statist.,the Statist. Soc. Canada, 2017, pp. 1–47  URL: https://doi.org/10.1214/17-SS117
  * [RR19] Miklos Racz and Jacob Richey  “A smooth transition from Wishart to GOE”  In _Journal of Theoretical Probability_ 32, 2019  URL: https://doi.org/10.1007/s10959-018-0808-2
  * [SA17] Stanislaw Szarek and Guillaume Aubrun  “Alice and Bob Meet Banach: The Interface of Asymptotic Geometric Analysis and Quantum Information Theory”  Providence, RI: American Mathematical Society, 2017  URL: https://www.ams.org/books/surv/223/surv223-endmatter.pdf
  * [SAC19] Anna L. Smith, Dena M. Asta and Catherine A. Calder  “The Geometry of Continuous Latent Space Models for Network Data”  In _Statistical Science_ 34.3 Institute of Mathematical Statistics, 2019, pp. 428–453  URL: https://doi.org/10.1214/19-STS702
  * [SS05] Elias M. Stein and Rami Shakarchi  “Real Analysis: Measure Theory, Integration, and Hilbert Spaces”  Princeton University Press, 2005  URL: http://www.jstor.org/stable/j.ctvd58v18
  * [SW22] Tselil Schramm and Alexander S. Wein  “Computational barriers to estimation from low-degree polynomials”  In _The Annals of Statistics_ 50.3 Institute of Mathematical Statistics, 2022  URL: https://doi.org/10.1214%2F22-aos2179

##  Appendix A Variance of the Signed Triangle Statistic

###### Proof of Proposition 2.13.

Denote $\tau_{(i,j,k)}(G)=(G_{i,j}-p)(G_{j,k}-p)(G_{k,i}-p).$
For$G\sim\mathsf{RAG}(n,\\{\pm 1\\}^{d},p,\sigma),$ as in [LR21a], we have

$\displaystyle{\mathbf{Var}}[\tau_{3}(G)]$
$\displaystyle=\binom{n}{3}{\mathbf{Var}}[\tau_{(1,2,3)}(G)]^{2}+O\left(\binom{n}{4}\right){\mathbf{Cov}}[\tau_{(1,2,3)}(G),\tau_{(1,2,4)}(G)]+$
$\displaystyle
O\left(\binom{n}{5}\right){\mathbf{Cov}}[\tau_{(1,2,3)}(G),\tau_{(1,4,5)}(G)]+O\left(\binom{n}{6}\right){\mathbf{Cov}}[\tau_{(1,2,3)}(G),\tau_{(4,5,6)}(G)].$

We bound each of the four terms separately.

##### Case 1)

Covariance when the two triangles have overlap of size 3. Using that each edge
is an indicator,

$\displaystyle{\mathbf{E}}[\tau_{(1,2,3)}(G)^{2}]={\mathbf{E}}[(G_{1,2}-p)^{2}(G_{2,3}-p)^{2}(G_{3,1}-p)^{2}]$
$\displaystyle={\mathbf{E}}[(1-2p)(G_{1,2}-p)+(p-p^{2})][(1-2p)(G_{2,3}-p)+(p-p^{2})][(1-2p)(G_{3,1}-p)+(p-p^{2})]$
$\displaystyle=(1-2p)^{3}\tau_{(1,2,3)}(G)+(p-p^{2})^{3}.$

We used the simple observations that ${\mathbf{E}}[G_{i,j}-p]=0$ and

${\mathbf{E}}[(G_{i,j}-p)(G_{j,k}-p)]={\mathbf{E}}[(\sigma(\bf\mathbf{x}_{i}^{-1}\mathbf{x}_{j})-p)(\sigma(\mathbf{x}_{j}^{-1}\mathbf{x}_{k})-p)]={\mathbf{E}}_{\mathbf{g},\mathbf{h}\sim_{iid}\mathsf{Unif}(\\{\pm
1\\}^{d})}[(\sigma(\mathbf{g})-p)(\sigma(\mathbf{h})-p)]=0.$

It follows that

$\displaystyle\binom{n}{3}{\mathbf{Var}}[\tau_{(1,2,3)}(G)^{2}]=\binom{n}{3}\left((p-p^{2})^{3}+(1-2p)^{3}{\mathbf{E}}[\tau_{(1,2,3)}(G)]-{\mathbf{E}}[\tau_{(1,2,3)}(G)^{2}]\right)$
$\displaystyle=\binom{n}{3}\left((p-p^{2})^{3}+(1-2p)^{3}\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{3}-\left(\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{3}\right)^{2}\right)=O\left(n^{3}p^{3}+n^{3}\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{3}\right).$

##### Case 2)

When the two triangles have an overlap of size $2.$

$\displaystyle{\mathbf{E}}[\tau_{(1,2,3)}(G)\tau_{(1,2,4)}(G)]=$
$\displaystyle{\mathbf{E}}[(G_{1,2}-p)^{2}(G_{1,3}-p)(G_{2,3}-p)(G_{1,4}-p)(G_{2,4}-p)]=$
$\displaystyle{\mathbf{E}}\left[{\mathbf{E}}\left[(G_{1,2}(1-2p)+p^{2})(G_{1,3}-p)(G_{2,3}-p)(G_{1,4}-p)(G_{2,4}-p)|\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{x}_{2},\mathbf{x}_{4},\mathbf{x}_{5}\right]\right]=$
$\displaystyle{\mathbf{E}}\left[(\sigma(\mathbf{x}_{1}^{-1}\mathbf{x}_{2})(1-2p)+p^{2})(\sigma(\mathbf{x}_{1}^{-1}\mathbf{x}_{3})-p)(\sigma(\mathbf{x}_{2}^{-1}\mathbf{x}_{3})-p)(\sigma(\mathbf{x}_{1}^{-1}\mathbf{x}_{4})-p)(\sigma(\mathbf{x}_{2}^{-1}\mathbf{x}_{4})-p)\right]=$
$\displaystyle{\mathbf{E}}\left[(\sigma(\mathbf{x}_{1}^{-1}\mathbf{x}_{2})(1-2p)+p^{2}){\mathbf{E}}_{\mathbf{x}_{3}}\left[(\sigma(\mathbf{x}_{1}^{-1}\mathbf{x}_{3})-p)(\sigma(\mathbf{x}_{2}^{-1}\mathbf{x}_{3})-p)\right]{\mathbf{E}}_{\mathbf{x}_{4}}\left[(\sigma(\mathbf{x}_{1}^{-1}\mathbf{x}_{4})-p)(\sigma(\mathbf{x}_{2}^{-1}\mathbf{x}_{4})-p)\right]\right].$

Now, observe that

$\displaystyle{\mathbf{E}}_{\mathbf{x}_{3}}\left[(\sigma(\mathbf{x}_{1},\mathbf{x}_{3})-p)(\sigma(\mathbf{x}_{2}^{-1}\mathbf{x}_{3})-p)\right]{\mathbf{E}}\left[(\sigma(\mathbf{x}_{1}^{-1}\mathbf{x}_{4})-p)(\sigma(\mathbf{x}_{2}^{-1}\mathbf{x}_{4})-p)\right]$
$\displaystyle={\mathbf{E}}_{\mathbf{x}}\left[(\sigma(\mathbf{x}_{1}^{-1}\mathbf{x})-p)(\sigma(\mathbf{x}_{2}^{-1}\mathbf{x})-p)\right]^{2}\geq
0.$

Therefore, as
$(\sigma(\mathbf{x}_{1}^{-1}\mathbf{x}_{2})(1-2p)+p^{2})\in[0,1]$ (as $\sigma$
takes values in $0,1$), the above expression is bounded by

$\displaystyle{\mathbf{E}}\left[{\mathbf{E}}_{\mathbf{x}_{3}}\left[(\sigma(\mathbf{x}_{1}^{-1}\mathbf{x}_{3})-p)(\sigma(\mathbf{x}_{2}^{-1}\mathbf{x}_{3})-p)\right]{\mathbf{E}}_{\mathbf{x}_{4}}\left[(\sigma(\mathbf{x}_{1}^{-1}\mathbf{x}_{4})-p)(\sigma(\mathbf{x}_{2}^{-1}\mathbf{x}_{4})-p)\right]\right]$
$\displaystyle={\mathbf{E}}\left[(\sigma(\mathbf{x}_{1}^{-1}\mathbf{x}_{3})-p)(\sigma(\mathbf{x}_{2}^{-1}\mathbf{x}_{3})-p)(\sigma(\mathbf{x}_{1}^{-1}\mathbf{x}_{4})-p)(\sigma(\mathbf{x}_{2}^{-1}\mathbf{x}_{4})-p)\right]$
$\displaystyle=\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{4},$

where the last equality follows from 2.12. Thus, the total contribution to the
variance from this case is $\displaystyle
O\left(n^{4}\sum_{S\neq\emptyset}\widehat{\sigma}(S)^{4}\right).$

##### Case 3)

When the two triangles have an overlap of size $1.$

$\displaystyle{\mathbf{E}}[\tau_{(1,2,3)}(G)\tau_{(1,4,5)}(G)]$
$\displaystyle={\mathbf{E}}[(\sigma(\mathbf{x}_{1}^{-1}\mathbf{x}_{2})-p)(\sigma(\mathbf{x}_{2}^{-1}\mathbf{x}_{3})-p)(\sigma(\mathbf{x}_{3}^{-1}\mathbf{x}_{1})-p)(\sigma(\mathbf{x}_{1}^{-1}\mathbf{x}_{4})-p)(\sigma(\mathbf{x}_{4}^{-1}\mathbf{x}_{5})-p)(\sigma(\mathbf{x}_{5}^{-1}\mathbf{x}_{1})-p))]$
$\displaystyle={\mathbf{E}}[(\sigma(\mathbf{g})-p)(\sigma(\mathbf{h})-p)(\sigma(\mathbf{g^{-1}h^{-1}})-p)(\sigma(\mathbf{k})-p)(\sigma(\mathbf{\ell})-p)(\sigma(\mathbf{k^{-1}\ell^{-1}})-p))]$
$\displaystyle={\mathbf{E}}[(\sigma(\mathbf{g})-p)(\sigma(\mathbf{h})-p)(\sigma(\mathbf{g^{-1}h^{-1}})-p)]{\mathbf{E}}[(\sigma(\mathbf{k})-p)(\sigma(\mathbf{\ell})-p)(\sigma(\mathbf{k^{-1}\ell^{-1}})-p)]$
$\displaystyle={\mathbf{E}}[\tau_{(1,2,3)}(G)]{\mathbf{E}}[\tau_{(1,4,5)}(G)],$

so the covariance equals 0 in that case.

##### Case 4)

When the two triangles have an overlap of size $0.$

${\mathbf{E}}[\tau_{(1,2,3)}(G)\tau_{(4,5,6)}(G)]={\mathbf{E}}[\tau_{(1,2,3)}(G)]{\mathbf{E}}[\tau_{(4,5,6)}(G)],$

so the covariance is also zero in this case. The conclusion follows by adding
the four covariances. ∎

##  Appendix B Fourier Weights on Level d

###### Proof of Lemma 4.2.

Suppose that $f:\\{\pm 1\\}^{d}\longrightarrow[0,1]$ is a symmetric function.
Define by $f_{i}$ the value of $f$ when exactly $i$ of its coordinates are
equal to $1.$ Let $a_{i}=f_{i+1}-f_{i}$ and $a_{0}=f_{0},$ so
$f_{i}=\sum_{j=0}^{i}a_{j}.$ Consider $\widehat{f}([d]),$ which is the
correlation of $f$ with the parity function $\omega_{[d]}(\mathbf{x}).$ By
definition,

$\begin{split}&\widehat{f}([d])={\mathbf{E}}[f(\mathbf{x})\omega_{[d]}(\mathbf{x})]\\\
&=\frac{1}{2^{d}}\sum_{i=0}^{d}\binom{d}{i}(-1)^{d-i}f(\underbrace{1,1,\ldots,1}_{i}\underbrace{-1,-1,\ldots,-1}_{d-i})\\\
&=\frac{1}{2^{d}}\sum_{i=0}^{d}\binom{d}{i}(-1)^{d-i}\sum_{j=0}^{i}a_{j}\\\
&=\frac{1}{2^{d}}\sum_{j=0}^{d}a_{j}\sum_{i=j}^{d}\binom{d}{i}(-1)^{d-i}\\\
&=\frac{1}{2^{d}}\sum_{j=0}^{d}a_{j}(-1)^{d-j}\binom{d-1}{j-1},\end{split}$
(20)

where in the last line we used the simple combinatorial fact that
$\displaystyle\sum_{i=j}^{d}\binom{d}{i}(-1)^{d-i}=(-1)^{d-j}\binom{d-1}{j-1},$
which can be easily proved by induction and Paskal’s identity
$\binom{d-1}{j-1}-\binom{d}{j}=-\binom{d-1}{j}.$ We modify this expression
even further, showing that

$\begin{split}|\widehat{f}([d])|&=\left|\frac{1}{2^{d}}\sum_{j=0}^{d}a_{j}(-1)^{d-j}\binom{d-1}{j-1}\right|=\frac{1}{2}\left|{\mathbf{E}}_{j\sim
Bin(d-1,\frac{1}{2})}(-1)^{d-j}(f_{j+1}-f_{j})\right|\\\
&\leq\frac{1}{2}{\mathbf{E}}_{j\sim
Bin(d-1,\frac{1}{2})}|f_{j+1}-f_{j}|=O\left(\frac{\sum_{i=1}^{d}|f_{j+1}-f_{j}|}{\sqrt{d}}\right)=O\left(\frac{{\mathsf{Fl}}(f)}{\sqrt{d}}\right).\qed\end{split}$
(21)

We now continue to bounding $\widehat{{\mathbf{T}}_{p}}([d])$ and
$\widehat{\mathbf{D}_{p}}([d]).$ In what follows, we omit all floor and
ceiling signs for simplicity of exposition. Clearly, they don’t affect the
asymptotics.

###### Proof of Proposition 4.7.

Note that for $f={\mathbf{T}}_{p},$ we only have one non-negative value $a,$
which corresponds to the case when $\sum_{i=1}^{d}x_{i}=\tau_{p}-1$ or,
equivalently, there are exactly $t=\frac{\tau_{p}-1+d}{2}$ ones in the vector
$x.$ Thus, $a_{t}=1$ and $a_{s}=0$ when $s\neq t.$ In other words,

$|\widehat{{\mathbf{T}}_{p}}([d])|=\frac{1}{2^{d}}\binom{d-1}{t-1}.$

Thus, we simply need to bound the binomial coefficient $\binom{d}{t}.$ To do
so, we first bound $\tau_{p}.$ As each $x_{i}$ is supported on $[-1,1],$ it is
$1$-subgaussian. Therefore, $\sum_{i=1}^{d}x_{i}$ is $d$-subgaussian666For
these simple applications of subgaussian concentration, see [Han, Ch.3]. and,
thus,

$p={\mathbf{P}}\left[\sum
x_{i}\geq\tau_{p}\right]\leq\exp\left(-\frac{\tau_{p}^{2}}{2d}\right),$

so $\tau_{p}\leq\sqrt{2d\log\frac{1}{p}}.$ By taking a large enough constant
in $O\left(\frac{p\sqrt{\log\frac{1}{p}}}{\sqrt{d}}\right),$ we can also
assume that$\tau_{p}\geq\sqrt{d}/10.$ Indeed, this is true because

${\mathbf{P}}\left[\sum_{i=1}^{d}x_{i}\geq\sqrt{d}/10\right]=\frac{1}{2}-\frac{1}{2^{d}}\sum_{s=d/2}^{d/2+\sqrt{d}/10}\binom{d}{s}\geq\frac{1}{2}-\frac{1}{2^{d}}\times\frac{\sqrt{d}}{10}\binom{d}{d/2}\geq\frac{1}{2}-\frac{1}{2^{d}}\times\frac{2^{d}}{\sqrt{d}}\frac{\sqrt{d}}{10}=\Omega(1).$

Now, let $\psi=\frac{d}{\tau_{p}}<10\sqrt{d}.$ We claim that
$\binom{d}{t+\psi}\geq C\binom{d}{t}$ for some absolute constant $C,$
independent of $d$ and $p.$ Indeed, note that

$\displaystyle\frac{\binom{d}{t+\psi}}{\binom{d}{t}}=\prod_{i=0}^{\psi-1}\frac{d-t-i}{t+i+1}\geq\left(\frac{d-t-\psi}{t+\psi}\right)^{\psi}$
$\displaystyle\geq\left(\frac{\frac{d}{2}-\frac{\tau_{p}-1}{2}-\psi}{\frac{d}{2}+\frac{\tau_{p}-1}{2}+\psi}\right)^{\psi}=\left(1-\frac{\tau_{p}-1+2\psi}{\frac{d}{2}+\frac{\tau_{p}-1}{2}+\psi}\right)^{\psi}\geq\left(1-\frac{2\tau_{p}+4\psi}{d}\right)^{\psi}$
$\displaystyle\geq\exp\left(-\frac{2\tau_{p}\psi+4\psi^{2}}{d}\right)\geq\exp\left(-\frac{2d+100d}{d}\right)=\exp(-102),$

as desired.

Now, by definition of $t,$ the function ${\mathbf{T}}_{p}$ is equal to one if
and only if there are at least $\frac{\tau_{p}+d}{2}$ ones among
$x_{1},x_{2},\ldots,x_{d}.$ It follows that

$p=\frac{1}{2^{d}}\sum_{j=t}^{d}\binom{d}{j}\geq\frac{1}{2^{d}}\sum_{i=0}^{\psi-1}\binom{d}{t+i}\geq
C\psi\frac{1}{2^{d}}\binom{d}{t}.$

Thus,

$\frac{1}{2^{d}}\binom{d-1}{t-1}\leq\frac{1}{2^{d}}\binom{d}{t}=O\left(\frac{p}{\psi}\right)=O\left(\frac{p\tau_{p}}{d}\right)=O\left(\frac{p\sqrt{\log\frac{1}{p}}}{\sqrt{d}}\right).\qed$

The proof of Proposition 4.9 is a nearly trivial consequence.

###### Proof of Proposition 4.9.

Note that $\delta_{p}=\tau_{\frac{p}{2}}.$ For the function
$f=\mathbf{D}_{p},$ we easily see that if $t=\frac{\tau_{p/2}-1+d}{2},$ we
have $a_{0}=1,a_{d-t}=-1,a_{t}=1,$ and all the other differences are equal to
$0.$ Thus, we simply need to bound
$\frac{1}{2^{d}}\left(\binom{d}{t}+\binom{d}{d-t}\right)$ as above. Using the
result of the previous proof, this expression is just
$O\left(\frac{\frac{p}{2}\sqrt{\log\frac{2}{p}}}{\sqrt{d}}\right)=O\left(\frac{p\sqrt{\log\frac{1}{p}}}{\sqrt{d}}\right).$
∎

We we end with a remark which will be useful later on and shows that our
estimate for $\binom{d}{t}$ is optimal up to the small logarithmic factor.

######  Corollary B.1.

When $p=d^{O(1)},$

$\frac{1}{2^{d}}\binom{d}{\frac{d+\tau_{p}-1}{2}}=\Omega\left(\frac{p}{\sqrt{d}}\right).$

###### Proof.

Again, let $t=\frac{d+\tau_{p}-1}{2}.$ Note that $t\in[d/2,2d/3]$ by the
assumption on $p.$ We will first show that whenever $z\geq\frac{d}{2},$ it is
the case that

$\binom{d}{z+2\sqrt{d}}\leq C\binom{d}{z}$

for $C=e^{-1/2}<1.$ Indeed, this is nearly trivial as

$\frac{\binom{d}{z+2\sqrt{d}}}{\binom{d}{z}}=\prod_{i=0}^{2\sqrt{d}-1}\frac{d-z-i}{z+i+1}\leq\prod_{i=\sqrt{d}}^{2\sqrt{d}-1}\frac{d-z-i}{d/2}\leq\left(\frac{d-\sqrt{d}}{d/2}\right)^{\sqrt{d}}=\left(1-\frac{1}{2\sqrt{d}}\right)^{\sqrt{d}}\leq
e^{-1/2}.$

This, however, is sufficient as

$p=\frac{1}{2^{d}}\sum_{j=t}^{d}\binom{d}{j}\leq\frac{1}{2^{d}}\sum_{s=0}^{\infty}2\sqrt{d}\binom{d}{t+s2\sqrt{d}}\leq\frac{1}{2^{d}}2\sqrt{d}\binom{d}{t}\sum_{s=0}^{\infty}C^{s}=O\left(\sqrt{d}\frac{1}{2^{d}}\binom{d}{t}\right),$

from which the conclusion follows. ∎

##  Appendix C Boolean Functions Without Low-Degree and High-Degree Terms

######  Proposition C.1.

For every integer $d$ and integer $m<d/2,$ there exists a symmetric
function$f:\\{\pm 1\\}^{d}\longrightarrow[-1,1]$ such that:

  1. 1.

$\mathcal{W}^{1}({f})=\mathcal{W}^{2}({f})=\cdots=\mathcal{W}^{m-1}({f})=0,$

  2. 2.

$\mathcal{W}^{d-m}({f})=\mathcal{W}^{d-m+1}({f})=\cdots=\mathcal{W}^{d}({f})=0,$

  3. 3.

$\mathcal{W}^{m}({f})=\Omega\left(\frac{1}{m^{13/2}\log^{m}d}\right).$

We only prove the statement when $d$ and $m$ are both odd, but explain how to
remove these parity assumptions. Our construction is based on modifying the
majority function ${\mathbf{Maj}}={\mathbf{T}}_{1/2},$ about which we first
recall the following fact.

######  Lemma C.2 ([ODo14]).

Suppose that $d$ is odd and $k<d.$ If $k$ is even,
$\mathcal{W}^{k}({{\mathbf{Maj}}})=0.$ If $k$ is odd and $k<d/2,$
$\mathcal{W}^{k}({{\mathbf{Maj}}})=\Theta(\frac{1}{k^{3/2}}).$

Now, define the threshold operator $T(\cdot)$ over real functions on the
hypercube as follows. $T(f)[\mathbf{x}]=\min(f(\mathbf{x}),1)$ when
$f(\mathbf{x})\geq 0$ and $T(f)[x]=\max(f(\mathbf{x}),-1)$ when
$f(\mathbf{x})<0.$ Define also the operator $R_{m}$ on real functions over
$\\{\pm 1\\}^{d}$ removing layers
$\\{1,2,\ldots,m-1\\}\cup\\{d-m,d-m+1,\ldots,d\\}.$ Formally, for any $h,$

$R_{m}(h)=h-\sum_{i=1}^{m-1}h^{=i}-\sum_{j=d-m}^{d}h^{=j}=\sum_{S\;:\;m\leq|S|\leq
d-m}\widehat{h}(S)\omega_{S}.$

With this definition in mind, we are ready to prove the statement of
Proposition C.1 in the case when $d$ and $m$ are both odd. Our goal will be to
roughly construct a function satisfying the desired properties by combining
the operators $T$ and $R_{m}$ over ${\mathbf{Maj}}.$

###### Proof of Proposition C.1 when $m$ and $d$ are both odd..

Let $\displaystyle A=\left(e(4m+1)(2m+2)\log^{m/2}d\right)^{-1}$ (we will
demistify this number in the proof). We will show that the function
$\frac{1}{2}R_{m}\circ T\circ(A\times R_{m}\circ{\mathbf{Maj}})$ satisfies the
desired properties. We do this in steps and begin with analyzing the mapping

$\displaystyle g(\mathbf{x}):$ $\displaystyle=A\times
R_{m}({\mathbf{Maj}})[x]$
$\displaystyle=A\left({\mathbf{Maj}}(\mathbf{x})-\sum_{0<i<m}{\mathbf{Maj}}^{=i}(\mathbf{x})-\sum_{d-m\leq
j\leq d}{\mathbf{Maj}}^{=j}(\mathbf{x})\right)$
$\displaystyle=A\left({\mathbf{Maj}}(\mathbf{x})-\sum_{0<i<m}\widehat{{\mathbf{Maj}}}([i])p_{i}(\mathbf{x})-\sum_{d-m\leq
j\leq d}\widehat{{\mathbf{Maj}}}([j])p_{j}(\mathbf{x})\right).$

Note that
$\mathcal{W}^{m}({g})=A^{2}\mathcal{W}^{m}({{\mathbf{Maj}}})=\Omega(\frac{1}{m^{11/2}\log^{m}d})$
and

$\widehat{g}([m])=\binom{d}{m}^{-1/2}\mathcal{W}^{m}({g})^{1/2}=\Omega\left(\binom{d}{m}^{-1/2}\frac{1}{m^{11/4}\log^{m/2}d}\right).$

We will show that with probability at least $\frac{1}{d^{3m}},$ it is the case
that $g(\mathbf{x})\in[-1,1].$ Indeed, note that

$|g(\mathbf{x})|\leq A|{\mathbf{Maj}}(\mathbf{x})|+A\sum_{1\leq
i<m}|\widehat{{\mathbf{Maj}}}([i])|\times|e_{i}(\mathbf{x})|+A\sum_{d-m\leq
j\leq d}|\widehat{{\mathbf{Maj}}}([j])|\times|e_{j}(\mathbf{x})|.$

The first term is clearly bounded by $A.$ Note also that for each $i,$
$\binom{d}{i}|\widehat{{\mathbf{Maj}}}([i])|^{2}=\mathcal{W}^{i}({{\mathbf{Maj}}})\leq
1,$ so $|\widehat{{\mathbf{Maj}}}([{i}])|\leq\binom{d}{i}^{-1/2}.$ Finally, we
bound each $|e_{i}|$ in high probability using the moment method and Theorem
2.7. Suppose first that $i<m.$ For $t=(4m+1)\log d$ and
$a=\frac{1}{A(2m+2)}=e(4m+1)\log^{m/2}d,$

${\mathbf{P}}\left[|e_{i}(\mathbf{x})|>a\sqrt{\binom{d}{i}}\right]\leq\frac{\left\lVert
e_{i}(\mathbf{x})\right\rVert_{t}^{t}}{a^{t}\sqrt{\binom{d}{i}}^{t}}\leq\frac{\sqrt{t-1}^{it}\left\lVert
e_{i}(\mathbf{x})\right\rVert_{2}^{t}}{a^{t}\sqrt{\binom{d}{i}}^{t}}.$

Now, observe that $\left\lVert
e_{i}\right\rVert_{2}^{2}={\mathbf{E}}[\sum_{S,T\;|S|=|T|=i}\omega_{S}\omega_{T}]=\binom{d}{i}.$
Thus, the above expression becomes

$\left(\frac{(t-1)^{i/2}}{a}\right)^{t}\leq\left(\frac{(t-1)^{m/2}}{a}\right)^{t}\leq\left(\frac{(4m+1)^{m/2}\log^{m/2}d}{a}\right)^{(4m+1)\log
d}\leq e^{-(4m+1)\log d}\leq\frac{1}{d^{4m+1}}.$

The same conclusion follows for $i\geq d-m$ by observing that
$|e_{i}(\mathbf{x})|=|\omega_{[d]}e_{i}(\mathbf{x})|=|e_{d-i}(\mathbf{x})|$
holds for all $\mathbf{x}.$ By union bound, with probability at least
$1-\frac{2m}{d^{4m+1}}\geq 1-\frac{1}{d^{4m}},$ the event

$K=\left\\{\mathbf{x}\;:\;|e_{i}(\mathbf{x})|\leq
a\sqrt{\binom{d}{i}}\;\forall
i\in\\{1,2,\ldots,m-1\\}\cup\\{d-m,d-m+1,\ldots,d\\}\right\\}$

occurs. Note that on $K,$ however,

$\displaystyle|g(\mathbf{x})|$ $\displaystyle\leq A\left(1+\sum_{1\leq
i<m}\binom{d}{i}^{-1/2}a\binom{d}{i}^{1/2}+\sum_{d-m\leq j\leq
d}\binom{d}{j}^{-1/2}a\binom{d}{j}^{1/2}\right)$ $\displaystyle\leq
A(1+(2m+1)a)\leq Aa(2m+2)=1.$

Thus, on $K,$ the function $g$ is bounded by $1.$ Outside of $K,$ we can just
bound $g$ by its $L_{\infty}$ norm

$\displaystyle|g(\mathbf{x})|$ $\displaystyle\leq
A\left(\left\lVert{\mathbf{Maj}}\right\rVert_{\infty}+\sum_{1\leq
i<m}\binom{d}{i}^{-1/2}\left\lVert e_{i}\right\rVert_{\infty}+\sum_{d-m\leq
j\leq d}\binom{d}{j}^{-1/2}\left\lVert e_{j}\right\rVert_{\infty}\right)$
$\displaystyle\leq A\left(1+\sum_{1\leq
i<m}\binom{d}{j}^{-1/2}\binom{d}{i}+\sum_{d-m\leq j\leq
d}\binom{d}{j}^{-1/2}\binom{d}{j}\right)\leq d^{m}.$

Now, define $h(\mathbf{x}):=g(\mathbf{x})-T\circ g(\mathbf{x}).$ Note that
$h\equiv 0$ on $K.$ Therefore, any Fourier coefficient of $h$ is bounded as
follows.

$\displaystyle|\widehat{h}(S)|$
$\displaystyle=|{\mathbf{E}}[h(\mathbf{x})\omega_{S}(\mathbf{x})]|=|{\mathbf{E}}[h(\mathbf{x})\omega_{S}(\mathbf{x})1_{K^{c}}(\mathbf{x})]|$
$\displaystyle\leq{\mathbf{E}}[|h(\mathbf{x})\omega_{S}(\mathbf{x})|1_{K^{c}}(\mathbf{x})]\leq\left\lVert
h\right\rVert_{\infty}{\mathbf{E}}[1_{K^{c}}]$ $\displaystyle\leq(\left\lVert
g\right\rVert_{\infty}+\left\lVert T\circ
g\right\rVert_{\infty}){\mathbf{P}}[K^{c}]$
$\displaystyle\leq(d^{m}+1)\frac{1}{d^{4m}}<\frac{1}{d^{2m}}.$

Therefore, for any set $S,$ we have that $|\widehat{[T\circ
g-g]}{(S)}|\leq\frac{1}{d^{2m}}.$ In particular, this means that

$\displaystyle\mathcal{W}^{m}({T\circ
g})\geq\binom{d}{m}\left(\widehat{g}([i])-\frac{1}{d^{2m}}\right)^{2}$
$\displaystyle=\Omega\left(\binom{d}{m}\left(\binom{d}{m}^{-1/2}\frac{1}{m^{11/4}\log^{m/2}d}-\frac{1}{d^{2m}}\right)^{2}\right)=\Omega\left(\frac{1}{m^{11/2}\log^{m/2}}d\right).$

Furthermore, for $i\in\\{1,2,\ldots,m-1\\}\cup\\{d-m,d-m+1,\ldots,d\\},$
$|\widehat{T\circ g}([i])|=\|\widehat{[T\circ
g-g]}([i])\|\leq\frac{1}{d^{2m}}.$ Finally, we will show that the symmetric
function $\frac{1}{2}R_{m}\circ T\circ g$ satisfies the desired properties.
First, note that $\mathcal{W}^{m}({\frac{1}{2}R_{m}\circ T\circ
g})=\frac{1}{2}\mathcal{W}^{m}({T\circ
g})=\Omega(\frac{1}{m^{11/2}\log^{m/2}d}).$ Since $R_{m}$ is the last operator
applied, also $\mathcal{W}^{i}({\frac{1}{2}R_{m}\circ T\circ g})=0$ for
$i\in\\{1,2,\ldots,m-1\\}\cup\\{d-m,d-m+1,\ldots,d\\}.$ Finally, we need to
show that $\frac{1}{2}R_{m}\circ T\circ g$ is bounded in $[-1,1].$ This,
however, is simple.

$\displaystyle\left\lVert\frac{1}{2}R_{m}\circ T\circ g\right\rVert_{\infty}$
$\displaystyle=\frac{1}{2}\left\lVert T\circ g-\sum_{i=1}^{m-1}(T\circ
g)^{=i}-\sum_{j=d-m}^{d}(T\circ g)^{=j}\right\rVert_{\infty}$
$\displaystyle\leq\frac{1}{2}\left\lVert T\circ
g\right\rVert_{\infty}+\frac{1}{2}\sum_{i=1}^{m-1}\left\lVert(T\circ
g)^{=i}\right\rVert_{\infty}+\frac{1}{2}\sum_{j=d-m}^{d}\left\lVert(T\circ
g)^{=j}\right\rVert_{\infty}$
$\displaystyle\leq\frac{1}{2}+\frac{1}{2}\sum_{i=1}^{m-1}|\widehat{T\circ
g}([i])|\times\left\lVert
e_{i}\right\rVert_{\infty}+\frac{1}{2}\sum_{j=d-m}^{d}|\widehat{T\circ
g}([j])|\times\left\lVert e_{j}\right\rVert_{\infty}$
$\displaystyle\leq\frac{1}{2}+\frac{1}{2}\sum_{i=1}^{m-1}\frac{1}{d^{2m}}\binom{d}{i}+\frac{1}{2}\sum_{j=d-m}^{d}\frac{1}{d^{2m}}\binom{d}{j}\leq
1,$

with which the proof is complete. ∎

######  Remark C.3 (Removing parity assumptions).

Removing the assumption on $d$ being odd is easy as we can just consider the
majority function over an even number of elements, introduced in Section 6.2.
Removing the parity assumption on $m$ is also not hard. We need to repeat the
above argument with some function instead of ${\mathbf{Maj}},$ which also has
$\Omega(\frac{1}{m^{3/2}\log d})$ weight on even levels. Using the same
reasoning as above, we can prove that such a function is

$\mathbf{H}(\mathbf{x}):=T\left({\mathbf{Maj}}(\mathbf{x})\frac{\sum_{i=1}x_{i}}{\log
d\sqrt{d}}\right)=T\left(\left|\frac{\sum_{i=1}^{d}x_{i}}{\sqrt{d}\log
d}\right|\right)$

Now, suppose that $f$ satisfies the conditions in Proposition C.1 and let
$\alpha={\mathbf{E}}[f].$ Then, $h=\frac{f-\alpha}{2}$ also satisfies the
conditions in Proposition C.1 and has mean zero. Thus, for any $p\leq 1/2,$
the mapping $p(1+h)$ has mean $p$ and takes values in $[0,1].$ With this, we
are ready to state our main corollary in this appendix.

######  Corollary C.4.

For every integer $d,$ integer $m<d/2,$ and real number $p\in[0,1]$ there
exists a symmetric connection $\sigma:\\{\pm 1\\}^{d}\longrightarrow[0,1]$
such that:

  1. 1.

$\mathcal{W}^{1}({\sigma})=\mathcal{W}^{2}({\sigma})=\cdots=\mathcal{W}^{m-1}({\sigma})=0,$

  2. 2.

$\mathcal{W}^{d-m}({\sigma})=\mathcal{W}^{d-m+1}({\sigma})=\cdots=\mathcal{W}^{d}({\sigma})=0,$

  3. 3.

$\mathcal{W}^{m}({\sigma})=\Omega\left(\frac{p^{2}}{m^{13/2}\log^{m}d}\right).$

  4. 4.

${\mathbf{E}}[\sigma]=p.$

##  Appendix D Further Computations of Fourier Coefficients

###  D.1 The Case of Symmetric Thresholds

###### Proof of Proposition 6.3.

Suppose that $S$ has size 2 or $d-2,$ in particular $|S|$ is even. Then,

$\displaystyle\widehat{\mathbf{D}_{p}}(S)={\mathbf{E}}[\mathbf{D}_{p}(\mathbf{x})\omega_{S}(\mathbf{x})]={\mathbf{E}}\left[\mathds{1}[\sum
x_{i}\geq\tau_{p/2}]\omega_{S}(\mathbf{x})\right]+{\mathbf{E}}\left[\mathds{1}[\sum
x_{i}\leq-\tau_{p/2}]\omega_{S}(\mathbf{x})\right]$
$\displaystyle={\mathbf{E}}\left[\mathds{1}[\sum
x_{i}\geq\tau_{p/2}]\omega_{S}(\mathbf{x})\right]+{\mathbf{E}}\left[\mathds{1}[\sum(-x_{i})\geq\tau_{p/2}]\omega_{S}(-\mathbf{x})\right]$
$\displaystyle=2{\mathbf{E}}\left[\mathds{1}[\sum
x_{i}\geq\tau_{p/2}]\omega_{S}(\mathbf{x})\right]=2\widehat{{\mathbf{T}}_{p/2}}(S),$

where we used the fact $\mathbf{x}$ and $-\mathbf{x}$ have the same
distribution and $|S|$ is even. Thus, we simply need to find the Fourier
coefficients of ${\mathbf{T}}_{p/2}$ for our purposes. We do this in a similar
manner to [ODo14, Chapter 5]. Namely, suppose that $|S|=2k$ and, without loss
of generality due to symmetry, $S=\\{d\\}\cup S_{1},$ where $S_{1}$ has size
$2k-1$ it follows that

$\displaystyle{\mathbf{E}}[{\mathbf{T}}_{p/2}(\mathbf{x})\omega_{S}(\mathbf{x})]$
$\displaystyle=\frac{1}{2}{\mathbf{E}}\left[\left({\mathbf{T}}_{p/2}(x_{1},x_{2},\ldots,x_{d-1},1)-{\mathbf{T}}_{p/2}(x_{1},x_{2},\ldots,x_{d-1},-1)\right)\omega_{S_{1}}\right]=\frac{1}{2}{\mathbf{E}}[J(\mathbf{y})\omega_{S_{1}}(\mathbf{y})]=\frac{1}{2}\widehat{J}(S_{1}),$

where $\mathbf{y}=(x_{1},x_{2},\ldots,x_{d-1})$ and

$J(\mathbf{y}):=\left({\mathbf{T}}_{p/2}(y_{1},y_{2},\ldots,y_{d-1},1)-{\mathbf{T}}_{p/2}(y_{1},y_{2},\ldots,y_{d-1},-1)\right)=\mathds{1}\left[\sum_{i=1}^{d-1}y_{i}=\tau_{p/2}-1\right].$

We now find the coefficients of $J$ via the noise-stability operator. Namely,
pick the all-ones vector $\mathbf{b}=\mathbf{1}$ and let $\mathbf{z}$ be
$\rho-$correlated with $\mathbf{b}.$ On the one hand,

${\mathbf{P}}[J(\mathbf{z})=1]=\binom{d-1}{\frac{d-1+\tau_{p/2}-1}{2}}\left(\frac{1}{2}+\frac{\rho}{2}\right)^{\frac{d-1+\tau_{p/2}-1}{2}}\left(\frac{1}{2}-\frac{\rho}{2}\right)^{\frac{d-1-\tau_{p/2}+1}{2}}$

as we need exactly $\frac{d-1+\tau_{p/2}-1}{2}$ of the coordinates of
$\mathbf{y}$ to equal $1$ and each $y_{i}$ is iid
$Bernoulli(\frac{1}{2}+\frac{\rho}{2})$ as $\mathbf{y}$ and
$\mathbf{b}=\mathbf{1}$ are $\rho-$correlated. On the other hand, by the
definition of the noise operator

${\mathbf{P}}[J(\mathbf{z})=1]={\mathbf{E}}[J(\mathbf{z})]=T_{\rho}J(\mathbf{b})=\sum_{S}\rho^{|S|}\widehat{J}(S)\omega_{S}(\mathbf{b})=\sum_{s=0}^{d-1}\rho^{s}\binom{d}{s}\widehat{J}(S_{1}).$

Now, we simply compare coefficients of the two polynomial expressions as

$\sum_{s=0}^{d-1}\rho^{s}\binom{d-1}{s}\widehat{J}([s])=\binom{d-1}{\frac{d-1+\tau_{p/2}-1}{2}}\left(\frac{1}{2}+\frac{\rho}{2}\right)^{\frac{d-1+\tau_{p/2}-1}{2}}\left(\frac{1}{2}-\frac{\rho}{2}\right)^{\frac{d-1-\tau_{p/2}+1}{2}}$

holds for all $\rho\in[-1,1].$ For notational purposes, we set
$t=\frac{d-1+\tau_{p/2}-1}{2}.$

##### Case 1)

When $s=1.$ Then, we have

$\displaystyle\binom{d-1}{1}\widehat{J}([1])$
$\displaystyle=\frac{1}{2^{d}}\binom{d-1}{t}\left(t-(d-t-1)\right)$
$\displaystyle=\frac{1}{2^{d}}\binom{d-1}{t}\left(2t-d+1\right)$
$\displaystyle=\Omega\left(\frac{\sqrt{d}}{2^{d}}\binom{d}{t}\right)=\Omega(p),$

using the bounds $t=\frac{d}{2}+\Omega(\sqrt{d})$ and
$\frac{1}{2^{d}}\binom{d}{t}=\Omega(\frac{p}{\sqrt{d}})$ in Appendix B on $t$
and $\binom{d}{t}.$ Thus, $\widehat{J}([1])=\Omega(\frac{p}{d})$ and so
$\widehat{\mathbf{D}_{p}}([2])=\Omega(\frac{p}{d}).$ Using the bounds
$t=\frac{d}{2}+\tilde{O}(\sqrt{d})$ and
$\frac{1}{2^{d}}\binom{d}{t}=\tilde{O}(\frac{p}{\sqrt{d}}),$ we similarly
conclude that $\widehat{\mathbf{D}_{p}}([2])=\tilde{O}(\frac{p}{d}).$

##### Case 2)

When $s=d-3,$ we similarly have

$\displaystyle\binom{d-1}{d-3}\widehat{J}([d-2])$
$\displaystyle=\frac{1}{2^{d}}\binom{d-1}{t}\left(\binom{t}{t-2}(-1)^{d-t}+\binom{t}{t-1}\binom{d-1-t}{d-2-t}(-1)^{d-t-1}+\binom{d-1-t}{d-3-t}(-1)^{d-t-2}\right)$
$\displaystyle=\frac{1}{2^{d}}\binom{d-1}{t}O\left(\binom{t}{t-2}-\binom{t}{t-1}\binom{d-1-t}{d-2-t}+\binom{d-1-t}{d-3-t}\right)$
$\displaystyle=\frac{1}{2^{d}}\binom{d-1}{t}O\left(\frac{t(t-1)+(d-t-1)(d-t-2)-2t(d-1-t)}{2}\right)$
$\displaystyle=\frac{1}{2^{d}}\binom{d-1}{t}O\left(\frac{t(t-1)+(d-t-1)(d-t-2)-2t(d-1-t)}{2}\right)$
$\displaystyle=\frac{1}{2^{d}}\binom{d-1}{t}O\left(\frac{(\tau_{p/2}-1)^{2}-(d-1)}{2}\right)$
$\displaystyle=\tilde{O}\left(\frac{p}{\sqrt{d}}d\right)=\tilde{O}\left(p\sqrt{d}\right),$

where we used the fact that $t=\frac{d-1+\tau_{p/2}-1}{2}$ to expand the
expression and the bounds $\tau_{p/2}=\tilde{O}\left(\sqrt{d}\right)$ and
$\frac{1}{2^{d}}\binom{d-1}{t}=\tilde{O}(\frac{p}{\sqrt{d}}).$ Hence, we know
that
$\widehat{\mathbf{D}_{p}}([d-2])=\frac{1}{2}\widehat{J}([d-2])=\tilde{O}\left(pd^{-3/2}\right),$
as desired. ∎

###  D.2 Interval Unions

###### Proof of Proposition 6.9.

We have to prove three things about $\zeta_{s}.$ First, note that

${\mathbf{E}}[\zeta_{s}]\geq{\mathbf{P}}\left[\sum x_{i}\geq
d_{1}+\sqrt{d}\right]=\Omega(1).$

Second, for each $\ell,$ we have that

$1\geq{\mathbf{E}}[\zeta_{s}^{2}]\geq\mathcal{W}^{\ell}({\zeta_{s}})=\binom{d}{\ell}\widehat{\zeta_{s}}([\ell])^{2},$

from which the bound on coefficients on levels $1,2,d-1,d-2$ follow. Lemma 4.2
implies that

$\displaystyle\left|\widehat{\zeta_{s}}\right|$
$\displaystyle=\left|\frac{1}{2^{d}}\sum_{j=0}^{s-2}(-1)^{d-d_{1}-2j}\binom{d-1}{d_{1}+2j-1}+(-1)^{d-d_{1}-\sqrt{d}}\binom{d-1}{d_{1}+\sqrt{d}-1}\right|$
$\displaystyle=\Omega\left(\frac{s-1}{\sqrt{d}}+(-1)^{d_{1}-\sqrt{d}}\frac{1}{\sqrt{d}}\right)=\Omega\left(\frac{s}{\sqrt{d}}\right),$

where we used the fact that
$\frac{1}{2^{d}}\binom{d-1}{d_{1}+\psi}=\Theta(\frac{1}{\sqrt{d}})$ whenever
$\psi=O(\sqrt{d}).$ ∎

##  Appendix E Distributions of Cayley Graph Generators

Here, we show that both our statistical and computational indistinguishability
results on typical Cayley graphs Theorems 5.1 and 7.2 are robust with respect
to the underlying distribution of generators in the following sense. They
still hold (with potentially different constants) as long as the distribution
satisfies the following “small-scale conditional independence” property even
if it is not $\mathsf{AnteU}.$

######  Definition E.1.

(Small-scale Conditional Independence) Given are a group $|\mathcal{G}|,$ a
probability $p\in(0,1),$ and an integer $N=o(|\mathcal{G}|).$ We say that a
distribution $\mathsf{D}(\mathcal{G},p)$ satisfies the “$(c_{1},c_{2})$-small-
scale conditional independence property for $(\mathcal{G},N,p),$” where
$c_{1},c_{2}\in(0,1)$ are constants if the following holds. There exists a set
$\mathcal{L}\subseteq\mathcal{G}$ of size at most $|\mathcal{G}|^{c_{1}}$ such
that all $\mathbf{x}\in\mathcal{G}\backslash\mathcal{L}$ satisfy the
condition: For any set
$M\subseteq\mathcal{G}\backslash\\{\mathbf{x},\mathbf{x}^{-1}\\}$ of
cardinality $0\leq|M|\leq N$ and any $I\subseteq M,$

$\bigg{|}{\mathbf{P}}_{A\sim\mathsf{D}(\mathcal{G},p)}[\mathbf{x}\in A|A\cap
M=I]-p\bigg{|}\leq\frac{1}{|\mathcal{G}|^{c_{2}}}.$

Importantly, one can easily see that this definition captures $\mathsf{PostU}$
if the underlying group has at most $|\mathcal{G}|^{c}$ elements of order two
for some $c<1$ or, respectively, at most most $|\mathcal{G}|^{c}$ elements of
order at least three for some $c<1.$ Our theorems are rephrased as follows.

######  Claim E.2.

(See Theorem 5.1) An integer $n$ is given and a real number $p\in[0,1].$ Let
$\mathcal{G}$ be any finite group of size at least $\exp(Cn\log\frac{1}{p})$
for some universal constant $C.$ Let $\mathsf{D}(\mathcal{G},p)$ be a
distribution over subsets of $\mathcal{G}$ satisfying the
“$(c_{1},c_{2})$-small-scale conditional independence property for
$(\mathcal{G},n^{3},p),$” where $c_{1},c_{2}$ are constant independent of
$|\mathcal{G}|,n,p.$ Then, with high probability at least
$1-|\mathcal{G}|^{-D}$ over $A\sim\mathsf{D}(\mathcal{G},p),$ we have

${\mathsf{KL}}\Big{(}\mathsf{RAG}(n,\mathcal{G},\sigma_{A},p_{A})\|\mathsf{G}(n,p)\Big{)}=o(1),$

where
$p_{A}={\mathbf{E}}_{\mathbf{g}\sim\mathsf{Unif}(\mathcal{G})}[\sigma_{A}(\mathbf{g})]$
and $D>0$ depends only on $c_{1},c_{2}.$

######  Claim E.3.

(See Theorem 7.2) An integer $k=o(n)$ and real number
$p\in[\frac{1}{n^{3}},1-\frac{1}{n^{3}}]$ are given. Suppose that
$\mathcal{G}$ is an arbitrary group of size at least $\exp(Ck\log n)$ for some
universal constant $C.$ Let $\mathsf{D}(\mathcal{G},p)$ be a distribution over
subsets of $\mathcal{G}$ satisfying the ‘$(c_{1},c_{2})$-small-scale
conditional independence property for $(\mathcal{G},n^{3},p),$” where
$c_{1},c_{2}$ are constant independent of $|\mathcal{G}|,n,p.$ Let
$A\sim\mathsf{D}(\mathcal{G},p).$ Consider the connection
$\sigma_{A}(\mathbf{x},\mathbf{y}):=\mathds{1}[\mathbf{x}\mathbf{y}^{-1}\in
A]$ with ${\mathbf{E}}[\sigma_{A}]=p_{A}.$ Then, one typically cannot
distinguish $\mathsf{G}(n,p)$ and
$\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})$ using low-degree polynomials
in the following sense. With high probability $1-\exp(-Dk\log n)$ over $A,$

$\displaystyle|{\mathbf{E}}_{G\sim\mathsf{RRAG}(n,\mathcal{G},p_{A},\sigma_{A})}P(G)-{\mathbf{E}}_{H\sim\mathsf{G}(n,p)}P(H)|=\exp(-Dk\log
n)$

holds simultaneously for all polynomials $P$ of degree at most $k$ in
variables the edges of the input graph which satisfy
${\mathbf{Var}}_{H\sim\mathsf{G}(n,p)}[P(H)]\leq 1.$ Here, $D>0$ is a constant
depending only on $c_{1},c_{2}.$

For both statements, the proofs are simple modifications of Theorem 5.1,
respectively Theorem 7.2. We only outline how one needs to change the first
proof as the modifications are identical.

###### Proof sketch of E.2.

proceed in the same way as in Theorem 5.1, except that we remove from $B$ the
event that one of
$\mathbf{g}^{(1)}(\mathbf{z}_{i}^{(1)})^{-1},\mathbf{z}_{i}^{(1)},\mathbf{g}^{(2)}(\mathbf{z}_{i}^{(2)})^{-1},\mathbf{z}_{i}^{(2)}$
belongs to the set $\mathcal{L}$ from Definition E.1. By union bound, the
resulting event $B_{1}$ satisfies

${\mathbf{P}}[B_{1}]\geq{\mathbf{P}}[B]-4t\frac{|\mathcal{L}|}{|\mathcal{G}|}=1-O(|\mathcal{G}|^{-D_{1}})$

for some fixed constant $D_{1}.$ Thus, again, over $B_{1}^{c},$ the
expectation of Eq. 15 is at most $O(|\mathcal{G}|^{-D_{1}}).$ On the other
hand, over $B_{1}^{c},$ we have that

$\displaystyle\Bigg{|}{\mathbf{E}}_{A\sim\mathsf{D}(\mathcal{G},p)}\Bigg{[}\prod_{i=1}^{t}(\sigma_{A}(\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{i})^{-1})-p)\prod_{i=1}^{t}(\sigma_{A}(\mathbf{z}^{(1)}_{i})-p)\prod_{i=1}^{t}(\sigma_{A}(\mathbf{g}^{(2)}(\mathbf{z}^{(2)}_{i})^{-1})-p)\prod_{i=1}^{t}(\sigma_{A}(\mathbf{z}^{(2)}_{i})-p)\Bigg{]}\Bigg{|}$
$\displaystyle\qquad\qquad\leq{|\mathcal{G}|^{-c_{2}}},$

where the last inequality follows directly from Definition E.1 applied to
$\mathbf{x}=\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{1})^{-1}$ and the fact that

$\Bigg{\|}\prod_{i=2}^{t}(\sigma_{A}(\mathbf{g}^{(1)}(\mathbf{z}^{(1)}_{i})^{-1})-p)\prod_{i=1}^{t}(\sigma_{A}(\mathbf{z}^{(1)}_{i})-p)\prod_{i=1}^{t}(\sigma_{A}(\mathbf{g}^{(2)}(\mathbf{z}^{(2)}_{i})^{-1})-p)\prod_{i=1}^{t}(\sigma_{A}(\mathbf{z}^{(2)}_{i})-p)\Bigg{\|}<1$

holds with probability $1$ over $A.$ Using these bounds in Eq. 15, we finish
the proof analogously. ∎

##  Appendix F Signed Four-Cycles on Probabilistic Latent Space Graphs

###### Proof of Theorem 7.4.

We need to bound ${\mathbf{E}}[\tau_{4}(H)],{\mathbf{Var}}[{\tau_{4}(H)}]$ for
$H\sim\mathsf{G}(n,p)$
and$H\sim\mathsf{PLSG}(n,\Omega,\mathsf{Unif},p,\sigma).$ We begin with
${\mathbf{E}}_{H\sim\mathsf{PLSG}(n,\Omega,\mathsf{Unif},p,\sigma)}[\tau_{4}(H)].$
Since $\sigma$ is an indicator with positive expectation $p,$ there exists
some $\mathbf{y}_{1},\mathbf{y}_{2}\in\Omega$ such that
$\sigma(\mathbf{y}_{1},\mathbf{y}_{2})=1.$ In particular, this means that
$p\geq{|\Omega|^{-2}}.$ Consider the signed cycle $(1,2,3,4).$

$\displaystyle{\mathbf{E}}_{H\sim\mathsf{PLSG}(n,\Omega,\mathsf{Unif},p,\sigma)}[(H_{1,2}-p)(H_{2,3}-p)(H_{3,4}-p)(H_{4,1}-p)]$
$\displaystyle={\mathbf{E}}[(\sigma(\mathbf{x}_{1},\mathbf{x}_{2})-p)(\sigma(\mathbf{x}_{2},\mathbf{x}_{3})-p)(\sigma(\mathbf{x}_{3},\mathbf{x}_{4})-p)(\sigma(\mathbf{x}_{4},\mathbf{x}_{1})-p)]$
$\displaystyle={\mathbf{E}}_{\mathbf{x}_{1},\mathbf{x}_{3}}\bigg{[}{\mathbf{E}}_{\mathbf{x}_{2}}[(\sigma(\mathbf{x}_{1},\mathbf{x}_{2})-p)(\sigma(\mathbf{x}_{3},\mathbf{x}_{2})-p)|\mathbf{x}_{1},\mathbf{x}_{3}]{\mathbf{E}}_{\mathbf{x}_{4}}[(\sigma(\mathbf{x}_{1},\mathbf{x}_{4})-p)(\sigma(\mathbf{x}_{3},\mathbf{x}_{4})-p)|\mathbf{x}_{1},\mathbf{x}_{3}]\bigg{]}$
$\displaystyle={\mathbf{E}}_{\mathbf{x}_{1},\mathbf{x}_{3}}\bigg{[}{\mathbf{E}}_{\mathbf{x}_{2}}[(\sigma(\mathbf{x}_{1},\mathbf{x}_{2})-p)(\sigma(\mathbf{x}_{3},\mathbf{x}_{2})-p)|\mathbf{x}_{1},\mathbf{x}_{3}]^{2}\bigg{]}$
$\displaystyle\geq\bigg{[}{\mathbf{E}}_{\mathbf{x}_{2}}[(\sigma(\mathbf{y}_{1},\mathbf{x}_{2})-p)(\sigma(\mathbf{y}_{1},\mathbf{x}_{2})-p)]\bigg{]}^{2}\times{\mathbf{P}}[\mathbf{x}_{1}=\mathbf{x}_{3}=\mathbf{y}_{1}]$
$\displaystyle\geq\frac{1}{|\Omega|^{2}}\bigg{[}{\mathbf{E}}_{\mathbf{x}_{2}}[(\sigma(\mathbf{x}_{1},\mathbf{x}_{2})-p)^{2}]^{2}\bigg{]}$
$\displaystyle\geq\frac{1}{|\Omega|^{2}}[(1-p)^{2}{\mathbf{P}}[\mathbf{x}_{2}=\mathbf{y}_{2}]]^{2}$
$\displaystyle=\frac{1}{|\Omega|^{4}}(1-p)^{4}.$

In particular, this means that

$\displaystyle{\mathbf{E}}_{H\sim\mathsf{PLSG}(n,\Omega,\mathsf{Unif},p,\sigma)}[\tau_{4}(H)]=\Omega(n^{4})|\mathcal{G}|^{-3}(1-p)^{4}=\Omega(n^{4}|\Omega|^{-4}).$

Now, we will prove that

${\mathbf{Var}}_{H\sim\mathsf{PLSG}(n,\Omega,\mathsf{Unif},p,\sigma)}[\tau_{4}(H)]=O(n^{7}).$

For brevity, denote

$\tau_{(i_{1},i_{2},i_{3},i_{4})}(H)=(H_{i_{1},i_{2}}-p)(H_{i_{2},i_{3}}-p)(H_{i_{3},i_{4}}-p)(H_{i_{4},i_{1}}-p).$

Under thies notation, clearly
$\tau_{4}(H)=\sum_{i_{1},i_{2},i_{3},i_{4}}\tau_{(i_{1},i_{2},i_{3},i_{4})}(H).$
Now,

$\displaystyle{\mathbf{Var}}_{H\sim\mathsf{PLSG}(n,\Omega,\mathsf{Unif},p,\sigma)}[\tau_{4}(H)]$
$\displaystyle={\mathbf{Var}}_{H\sim\mathsf{PLSG}(n,\Omega,\mathsf{Unif},p,\sigma)}\bigg{[}\sum_{(i_{1},i_{2},i_{3},i_{4})}\tau_{(i_{1},i_{2},i_{3},i_{4})}(H)\bigg{]}$
$\displaystyle=\sum_{(i_{1},i_{2},i_{3},i_{4})}{\mathbf{Var}}_{H\sim\mathsf{PLSG}(n,\Omega,\mathsf{Unif},p,\sigma)}[\tau_{(i_{1},i_{2},i_{3},i_{4})}(H)]$
$\displaystyle+\sum_{(i_{1},i_{2},i_{3},i_{4})\neq(j_{1},j_{2},j_{3},j_{4})}{\mathbf{Cov}}_{H\sim\mathsf{PLSG}(n,\Omega,\mathsf{Unif},p,\sigma)}[\tau_{(i_{1},i_{2},i_{3},i_{4})}(H),\tau_{(j_{1},j_{2},j_{3},j_{4})}(H)].$

The key observation is that if $(i_{1},i_{2},i_{3},i_{4})$ and
$(j_{1},j_{2},j_{3},j_{4})$ are disjoint, the covariance is zero since the two
functions depend on disjoint set of latent vectors. Otherwise, the covariance
is at most 1 since $\tau$ only takes values in $[0,1].$ However, there are
$O(n^{7})$ ways to take two four-tuples which are not disjoint among the
elements of $[n],$ so the claim follows. Finally, note that one similarly has

${\mathbf{E}}_{H\sim\mathsf{G}(n,p)}[\tau_{4}(H)]=0,{\mathbf{Var}}_{H\sim\mathsf{G}(n,p)}[\tau_{4}(H)]=O(n^{7}).$

Thus, a sufficient condition for the signed 4-cycle statistic to differentiate
between the two graph distributions with high probability is that
$n^{4}|\Omega|^{-4}=\omega(\sqrt{n^{7}}),$ which is guaranteed by
$|\Omega|=o(n^{1/8}).$ ∎