text:
\begin{document}
\maketitle

\begin{abstract}
We make the first steps towards generalizing the theory of stochastic block models, in the sparse regime, towards a model where the discrete community structure is replaced by an underlying geometry. We consider a geometric random graph over a homogeneous metric space where the probability of two vertices to be connected is an arbitrary function of the distance. We give sufficient conditions under which the locations can be recovered (up to an isomorphism of the space) in the sparse regime. Moreover, we define a geometric counterpart of the model of flow of information on trees, due to Mossel and Peres, in which one considers a branching random walk on a sphere and the goal is to recover the location of the root based on the locations of leaves. We give some sufficient conditions for percolation and for non-percolation of information in this model.
\end{abstract}

\section{Introduction}
Community detection in large networks is a central task in data science. It is often the case that one gets to observe a large network, the links of which depends on some unknown, underlying community structure. A natural task in this case is to detect and recover this community structure to the best possible accuracy.

Perhaps the most well-studied model in this topic is the \emph{stochastic block model} where a random graph whose vertex set is composed of several communities, $\{c_1,...,c_k\}$ is generated in a way that every pair of nodes $v,u$ which belong to communities $c(u), c(v)$, will be connected to each other with probability $p = p(c(v),c(u))$, hence with probability that only depends on the respective communities, and otherwise independently. The task is to recover the communities $c(\cdot)$ based on the graph (and assuming that the function $p(\cdot, \cdot)$ is known). The (unknown) association of nodes with communities is usually assumed to be random and independent between different nodes. See \cite{Abbe18} for an extensive review of this model.

A natural extension of the stochastic block model is the geometric random graph, where the discrete set of communities is replaced by a metric space. More formally, given a metric space $(X,d)$, a function $f: V \to X$ from a vertex set $V$ to the metric space and a function $\vphi:\RR_+ \to [0,1]$, a graph is formed by connecting each pair of vertices $u,v$ independently, with probability
$$
p(u,v) := \vphi \left ( d(f(u), f(v)) \right ).
$$
This model can sometimes mimic the behavior of real-world networks more accurately than the stochastic block model. For example, a user in a social network may be represented as a point in some linear space in a way that the coordinates correspond to attributes of her personality and her geographic location. The likelihood of two persons being associated with each other in the network will then depend on the proximity of several of these attributes. A flat community structure may therefore be two simplistic to reflect these underlying attributes.

Therefore, a natural extension of the theory of stochastic block models would be to understand under what conditions the geometric representation can be recovered by looking at the graph. Our focus is on the case that the metric is defined over a symmetric space, such as the Euclidean sphere in $d$-dimensions. By symmetry, we mean that the probability of two vertices to be connected, given their locations, is invariant under a natural group acting on the space. We are interested in the sparse regime where the expected degrees of the vertices do not converge to infinity with the size of the graph. This is the (arguably) natural and most challenging regime for the stochastic block model.

\subsection{Inference in geometric random graphs}

For the sake of simplicity, in what follows, we will assume that the metric space is the Euclidean sphere, and our main theorems will be formulated in this setting; It will be straightforward to generalize our results to any symmetric space (see \cite{de2017adaptive} for further discussion on this point).

In order to construct our model, we need some notation. Let $\sigma$ be the uniform probability measure on $\Spd$ and let $\vphi: \Spd \times \Spd \to [0,1]$, be of the form $\vphi(x,y) = f(\inner{x}{y})$ for some $f: [-1,1] \to [0,1]$.
Define the integral operator $A_\vphi: L^2\left(\Spd\right)\to L^2\left(\Spd\right)$ by
$$A_\vphi(g)(x) = \int\limits_{\Spd} \vphi(x,y)g(y)d\sigma(y).$$
It is standard to show that $A_\vphi$ is a self-adjoint compact operator (see \cite{hirsch2012elements}, for example) and so has a discrete spectrum, except at $0$. By definition, $\vphi$ is invariant to rotations and so $A_\vphi$ commutes with the Laplacian. It follows that the eigenfunctions of $A_\vphi$ are precisely the \emph{spherical harmonics} which we denote by
$\{\psi_i\}_{i=0}^\infty$. Thus, if $\lambda_i(A_\vphi)$ denotes the eigenvalue of $\vphi$ corresponding to $\psi_i$ we have the following identity,
\begin{equation} \label{eq: l2 decomp}
\vphi = \sum\limits_{i=0}^\infty \lambda_i \psi_i \otimes \psi_i.
\end{equation}In particular, $\psi_0 = 1$ and for $i = 1,...,d$, $\psi_i$ are linear functionals such that, for $x,y \in \Spd$,
\begin{equation} \label{eq: inner product}
d \cdot \inner{x}{y} = \sum_{l=1}^d \psi_l(x)\psi_l(y).
\end{equation}

Note that in our notation the eigenvalues are indexed by the spherical harmonics, and are therefore not necessarily in decreasing order. By rotational invariance it must hold that
\begin{equation} \label{eq: lambda equality}
\lambda(\vphi) := \lambda_1=...=\lambda_d.
\end{equation}
Define $\|\varphi\|_\infty = \sup_{x,y} \varphi(x,y)$.
We make the following, arguably natural, assumptions on the function $\vphi$:

\begin{enumerate}[label={A\arabic*.}, ref=A\arabic*]
\item \label{assumption1}
There exist $\delta > 0$ such that $\min_{i\neq 1,\dots, d}|\lambda(\vphi) - \lambda_i|>\delta$.
\item \label{assumption 2}
Reordering the eigenvalues in decreasing order $\lambda_{l_0}\geq \lambda_{l_1}\geq\lambda_{l_2}\geq\dots$ there exists $C > 0$ such that for every $i\geq 0, \lambda_{l_i}\leq \frac{C}{(i+1)^2}$.
\end{enumerate}

Let $\{X_i\}_{i=1}^n\sim \sigma$ be a sequence of independently-sampled vectors, uniformly distributed on $\Spd$.
Let $G\left(n, \frac{1}{n} \vphi(X_i, X_j)\right)$ be the inhomogeneous Erd\"{o}s-R\'{e}nyi model where edges are formed independently with probability $\frac{1}{n} \vphi(X_i, X_j)$  and let $A$ be the adjacency matrix of a random graph drawn from $G\left(n, \frac{1}{n}\vphi(X_i,X_j)\right)$.

\begin{definition}
We say that the model is $\eps-\emph{reconstructible}$ if, for all $n$ large enough, there is an algorithm which returns an $n \times n$ matrix $A$ such that
$$
\frac{1}{n^2} \sum_{i,j} |A_{i,j} - X_i \cdot X_j|^2 \leq \eps.
$$
\end{definition}

Remark that, due the symmetry of the model, it is clear that the locations can only be reconstructed up to an orthogonal transformation, which is equivalent to reconstruction of the Gram matrix.

\begin{theorem}
\label{thm: reconstruction bound}
	For every $\eps >0$ there exists a constant $C=C(\eps,d)$, such that the model is $\eps$-reconstructible whenever
	\begin{equation} \label{eq:thm1}
	\min_{i\neq 0,\dots,d}|\lambda_{i}-\lambda(\vphi)|^2 \geq C \| \vphi \|_{\infty}.
	\end{equation}
\end{theorem}

\begin{remark}
Observe that, since the left hand side of condition \eqref{eq:thm1} is $2$-homogeneous, whereas its right hand side is $1$-homogeneous, we have that as long as the left hand side is nonzero, by multiplication of the function $\vphi$ by a large enough constant,  the condition can be made to hold true.
\end{remark}

\begin{example}
	Consider the linear kernel,
	$\varphi(x,y) =a + b\langle x,y\rangle$, with $|b|\leq a$. A calculation shows that
	\begin{align*}
	\lambda_0 &= a \\
	\lambda(\vphi) &= \frac{b}{d}.
	\end{align*}
	Applying our theorem, we show that the model is reconstructible whenever
	\[
	\left| a-\frac{b}{d}\right|^2 \geq C \cdot (a+b).
	\]
\end{example}

\paragraph{Methods and related works.} Our reconstruction theorem is based on a spectral method, via the following steps:
\begin{enumerate}
\item
We observe that by symmetry of our kernel, linear functions are among its eigenfunctions. We show that the kernel matrix (hence the matrix obtained by evaluating the kernel at pairs of the points $(X_i)$) will have a respective eigenvalues and eigenvectors which approximate the ones of the continuous kernel.
\item
Observing that the kernel matrix is the expectation of the adjacency matrix, we rely on a matrix concentration inequality due to Le-Levina-Vershynin \cite{LeLevVer18} to show that the eigenvalues of the former are close to the ones of the latter.
\item
We use the Davis-Kahan theorem to show that the corresponding eigenvectors are also close to each other.
\end{enumerate}

The idea in Steps 2 and 3 is not new, and rather standard (see \cite{LeLevVer18} and references therein). Thus, the main technical contribution in proving our upper bound is in Step 1, where we prove a bound for the convergence of eigenvectors of kernel matrices. So far, similar results have only been obtained in the special case that the Kernel is positive-definite, see for instance \cite{braun2006accurate}.

The paper \cite{valdivia2018relative} considers kernels satisfying some Sobolev-type hypotheses similar to our assumptions on $\varphi$ (but gives results on the spectrum rather than the eigenvectors). Reconstruction of the eigenspace has been considered in \cite{SusTanPrie13} for positive definite kernels in the dense regime, in \cite{SusTanPrie14} for random dot products graphs and in \cite{Valdivia_DeCastro19} in the dense and relatively sparse regimes again for kernels satisfying some Sobolev-type hypotheses.

\iffalse
\begin{example}
	Consider the Gaussian kernel,
	\[
	\varphi(x,y) = K \cdot e^{-\|x-y\|^2/\sigma^2}
	\]
	Denote by $\mu_k$ the eigenvalue corresponding to the spherical harmonics in degree $k$. Then (see e.g. \cite{MiNiYa14}):
	\[
	\mu_k = K e^{-2/\sigma^2} \sigma^{d-2} I_{k+d/2-1}\left(\frac{2}{\sigma^2}\right)\Gamma\left(\frac{d}{2}\right),
	\]
	with
	\[
	I_\nu(z) = \sum_{j=0}^\infty \frac{1}{j!\Gamma(\nu+j+1)}\left(\frac{z}{2}\right)^{\nu + 2j},
	\]
	the modified Bessel function of the first kind.
	\\
	The $\mu_k$'s are decreasing if $\sigma\geq\left(\frac{2}{d}\right)^{1/2}$ and the reconstruction bound is then given by
	\[
	(\mu_1 - \mu_2)^2 \geq C \cdot K
	\]
	The average degree
	\[
	d_{av} = \lambda_0 = \mu_0 = K e^{-2/\sigma^2} \sigma^{d-2} I_{d/2-1}\left(\frac{2}{\sigma^2}\right)\Gamma\left(\frac{d}{2}\right),
	\]
	and for $k\geq 1$:
	\[
	\mu_k = d_{av} \cdot\frac{I_{k+d/2-1}\left(\frac{2}{\sigma^2}\right)}{I_{d/2-1}\left(\frac{2}{\sigma^2}\right)},
	\]
	which gives the reconstruction bound
	\[
	\left(I_{d/2}\left(\frac{2}{\sigma^2}\right)- I_{d/2 +1}\left(\frac{2}{\sigma^2}\right)\right)^2 \leq C \frac{I_{d/2-1}\left(\frac{2}{\sigma^2}\right)e^{2/\sigma^2}}{d_{av} \sigma^{d-2}\Gamma\left(\frac{d}{2}\right)}.
	\]
\end{example}
\subsubsection{Related work}
For the stochastic block model the recovery of communities is a well studied problem, see \cite{Abbe18} and the references in this survey. In our case, the proof of Theorem \ref{thm: reconstruction bound} relies on reconstructing the eigenspace spanned by the degree $1$ harmonics $\{\psi_i\}_{i=1}^d$. The convergence of eigenvalues has been shown in \cite{braun2006accurate} for positive definite kernels and in \cite{valdivia2018relative} also for nonpositive definite kernels satisfying some Sobolev-type hypotheses similar to our assumptions on $\varphi$. Reconstruction of the positions/eigenspace has been considered in \cite{SusTanPrie13} for positive definite kernels in the dense regime, in \cite{SusTanPrie14} for random dot products graphs and in \cite{Valdivia_DeCastro19} in the dense and relatively sparse regimes again for kernels satisfying some Sobolev-type hypotheses similar to our assumptions on $\varphi$. As far as we are aware there has been no previous work on the lower bound for the threshold of reconstruction for such models.
\fi

\subsection{Percolation of geometric information in trees} \label{sec:perco}

The above theorem gives an upper bound for the threshold for reconstruction. The question of finding respective lower bounds, in the stochastic block model, is usually reduced to a related but somewhat simpler model of percolation of information on \emph{trees}. The idea is that in the sparse regime, the neighborhood of each node in the graph is usually a tree, and it can be shown that recovering the community of a specific node based on observation of the entire graph, is more difficult than the recovery of its location based on knowledge of the community association of the leaves of a tree rooted at this node. For a formal derivation of this reduction (in the case of the stochastic block model), we refer to \cite{Abbe18}.

This gives rise to the following model, first described in Mossel and Peres \cite{MosPer03} (see also \cite{Mos04}): Consider a $q$-ary tree $T=(V,E)$ of depth $k$, rooted at $r \in V$. Suppose that each node in $V$ is associated with a label $\ell: V \to \{1,..,k\}$ in the following way: The root $r$ is assigned with some label and then, iteratively, each node is assigned with its direct ancestor's label with probability $p$ and with a uniformly picked label with probability $1-p$ (independent between the nodes at each level). The goal is then to detect the assignment of the root based on observation of the leaves.

Let us now suggest an extension of this model to the geometric setting. We fix a Markov kernel $\vphi(x,y) = f(\langle x,y \rangle)$ such that $\int_{\Sph} \varphi(x,y) d \sigma(y) = 1$ for all $x \in \Spd$. We define $\ff: T \to \Spd$ in the following way. For the root $r$, $\ff(r)$ is picked according to the uniform measure. Iteratively, given that $\ff(v)$ is already set for all nodes $v$ at the $\ell$-th level, we pick the values $\ff(u)$ for nodes $u$ at the $(\ell+1)$th level independently, so that if $u$ is a direct descendant of $v$, the label $\ff(u)$ is distributed according to the law $\varphi(\ff(v), \cdot) d \sigma$.

Denote by $T_k \subset V$ the set of nodes at depth $k$, and define by $\mu_k$ the conditional distribution of $\ff(r)$ given $(\ff(v))_{v \in T_k}$. We say that the model has positive information flow if
$$
\lim_{k \to \infty} \EE \left [ \mathrm{TV} (\mu_k, \sigma) \right ] > 0.
$$
Remark that by symmetry, we have
$$
\EE \left [ \mathrm{TV} (\mu_k, \sigma) \right ] = \EE \left [ \mathrm{TV} (\mu_k, \sigma) | \ff(r) = e_1 \right ]
$$
where $r$ is the root and $e_1$ is the north pole.

Our second objective in this work is to make the first steps towards understanding under which conditions the model has positive information flow, and in particular, our focus is on providing nontrivial sufficient conditions on $q, \varphi$ for the above limit to be equal to zero.

Let us first outline a natural sufficient condition for the information flow to be positive which, as we later show, turns out to be sharp in the case of Gaussian kernels. Consider the following simple observable,
$$
Z_k := \frac{1}{|T_k|} \sum_{v \in T_k} \ff(v).
$$
By Bayes' rule, we clearly have that the model has positive information flow if (but not only if)
\begin{equation}\label{eq:flowdecay}
\liminf_{k \to \infty} \frac{ \EE[ \langle Z_k, e_1 \rangle | \ff(r)=e_1] }{\sqrt{\mathrm{Var} \left [\langle Z_k, e_1 \rangle \right | \ff(r) = e_1 ]} } > 0.
\end{equation}
This gives rise to the parameter
$$
\lambda(\vphi) := \int_{\Spd} \langle x , e_1  \rangle  \varphi(e_1, x) d\sigma(x),
$$
which is the eigenvalue corresponding to linear harmonics. By linearity of expectation, we have
$$
\EE[ \langle Z_k, e_1 \rangle | \ff(r)=e_1] = \lambda(\vphi)^k.
$$
For two nodes $u,v \in T$ define by $c(u,v)$ the deepest common ancestor of $u,v$ and by $\ell(u,v)$ its level. A calculation gives
\begin{align*}
\mathrm{Var} \left [\langle Z_k, e_1 \rangle \right | \ff(r) = e_1 ] & = \frac{1}{q^{2k}} \sum_{u,v \in T_k} \EE \left [ \ff(v)_1 \ff(u)_1  | \ff(r) = e_1 \right ] - \lambda(\vphi)^{2k} \\
& = \frac{1}{q^{2k}} \sum_{u,v \in T_k} \EE \left [ \EE [\ff(v)_1 | \ff(c(u,v))] \EE[\ff(u)_1 | \ff(c(u,v))]  | \ff(r) = e_1 \right ] - \lambda(\vphi)^{2k} \\
& = \frac{1}{q^{2k}} \sum_{u,v \in T_k} \EE \left [\ff(c(u,v))_1^2 | \ff(r) = e_1 \right ] \lambda(\vphi)^{2(k-\ell(u,v))}  - \lambda(\vphi)^{2k} \\
& \leq \frac{1}{q^{2k}} \sum_{u,v \in T_k} \lambda(\vphi)^{2(k-\ell(u,v))}  - \lambda(\vphi)^{2k} \\
& = \frac{\lambda(\vphi)^{2k}}{q^{2k}} \sum_{u,v \in T_k} \lambda(\vphi)^{-2\ell(u,v)}  - \lambda(\vphi)^{2k} \\
& = \frac{\lambda(\vphi)^{2k}}{q^{2k}} \sum_{\ell=0}^k q^\ell q^{2(k-\ell)} \lambda(\vphi)^{-2\ell} - \lambda(\vphi)^{2k} = \lambda(\vphi)^{2k} \sum_{\ell=1}^k \left (q \lambda(\vphi)^2 \right )^{-\ell}.
\end{align*}
This gives a sufficient condition for \eqref{eq:flowdecay} to hold true, concluding:
\begin{claim}
The condition $q \lambda(\vphi)^2 > 1$ is sufficient for the model to have positive percolation of information.
\end{claim}
\noindent We will refer to this as the Kesten-Stigum (KS) bound. \\

We now turn to describe our lower bounds. For the Gaussian kernel, we give a lower bound which misses by a factor of $2$ from giving a matching bound to the KS bound. To describe the Gaussian kernel, fix $\beta > 0$, let $X$ be a normal random variable with law $\mathcal{N}(0,\beta)$ and suppose that $\vphi : \mathbb{S}^1 \times \mathbb{S}^1 \to \RR $ is such that
\begin{equation} \label{eq:gausskernel}
\varphi(x, \cdot)\text{ is the density of }(x + X) \mathrm{mod} 2 \pi,
\end{equation} where we identify $\mathbb{S}^1$ with the interval $[0,2 \pi)$. We have the following result.

\begin{theorem} \label{thm:Gaussian2d}
For the Gaussian kernel defined above, there is zero information flow whenever $q \lambda(\vphi) < 1$.
\end{theorem}

In the general case, we were unable to give a corresponding bound, nevertheless we are able to give some nontrivial sufficient condition for zero flow of information for some $q>1$, formulated in terms of the eigenvalues of the kernel. In order to formulate our result, we need some definitions.

We begin with a slightly generalized notion of a $q$-ary tree.
\begin{definition}
	Let $q > 1$, we say that $T$ is a tree of growth at most $q$ if for every $k \in \NN$,
	$$\left|T_k\right| \leq \left\lceil q^k \right\rceil.$$
\end{definition}
Now, recall that $\vphi(x,y) = f(\inner{x}{y})$.
Our bound is proven under the following assumptions on the kernel.
\begin{itemize} \label{ass:kernel}
	\item $f$ is monotone.
	\item $f$ is continuous.
	\item $\lambda(\vphi) > 0$ and for every $i \geq 1$, $ |\lambda_i| \leq \lambda(\vphi)$.
\end{itemize}

\noindent We obtain the following result.
\begin{theorem} \label{thm:lowerbound}
	Let $\vphi$ satisfy the assumptions above and let $T$ be a tree of growth at most $q$. There exists a universal constant $c > 0$, such that if
	$$
	q \leq \left(1-c\frac{\ln(\lambda(\vphi))(1-\lambda(\varphi))^2}{\ln\left(\frac{\lambda(\vphi)(1-\lambda(\vphi))}{f(1)}\right)}\right)^{-1}
	$$
	then the model has zero percolation of information.
\end{theorem}

\section{The upper bound: Proof of Theorem \ref{thm: reconstruction bound}}

Recall that
\begin{displaymath}
\vphi = \sum\limits_{k=0}^\infty \lambda_k \psi_k \otimes \psi_k,
\end{displaymath}
with the eigenvalues $\lambda_k$ indexed by the spherical harmonics.  Define the random matrices $M_n, \Psi_n$ by
$$(M_n)_{i,j} = \frac{1}{n}\vphi(X_i,X_j),  ~~~~~ (\Psi_n)_{i,k} = \frac{1}{\sqrt{n}}\psi_k(X_i).$$
Note that $M_n$ is an $n \times n$ matrix, while $\Psi_n$, has infinitely many columns. Furthermore, denote by $\Lambda$ the diagonal matrix $\mathrm{diag}\{\lambda_i\}_{i=0}^\infty$. Then
\[
(M_n)_{i,j} = \frac{1}{n}\sum _{k=0}^\infty \lambda_k\psi_k(X_i)\psi_k(X_j) =(\Psi_n\Lambda\Psi_n^T)_{i,j}.
\]
For $r \in \NN$ we also denote
$$\vphi^r := \sum\limits_{k=0}^r \lambda_k \psi_k \otimes \psi_k,$$
the finite rank approximation of $\vphi$, $\Lambda^r = \mathrm{diag}\{\lambda_k\}_{k=0}^r$, and $\Psi_n^r$ the sub-matrix of $\Psi_n$ composed of its first $r$ columns. Finally, denote
$$M_n^r =\Psi_n^r\Lambda^r(\Psi_n^r)^T.$$
As before, let $A$ be an adjacency matrix drawn from $G\left(n, \frac{1}{n}\vphi(X_i,X_j)\right)$ so that $\EE A = M_n$. Our goal is to recover $\Psi_n^{d+1}$ from the observed $A$.
The first step is to recover $\Psi_n^{d+1}$ from $M_n$. We begin by showing that the columns of $\Psi_n^r$ are, up to a small additive error, eigenvectors of $M_n^r$.
To this end, denote
$$E_{n,r} := (\Psi_n^r)^T\Psi_n^r - \mathrm{Id}_r,$$
$C(n,r) = \norm{E_{n,r}}^2_{op}$, and $K = \max_i{\lambda_i}$.
\begin{lemma} \label{lem: lambda approx}
	Let $u_i$ be the $i$'th column of $\Psi_n$ and let $\eta >0$. Then
	\[
	\norm{M_n^ru_i - \lambda_iu_i}_2^2\leq K^2(\sqrt{C(n,r)}+1)C(n,r).
	\]
	Moreover, whenever $n\geq l(r) \log (2r/\eta)$, we have with probability larger than $1-\eta$,
	\[
	C(n,r) \leq \frac{4 l(r)\log(2r/\eta)}{n}.
	\]
	where $l(r)$ only depends on $r$ and on the dimension.
\end{lemma}
\begin{proof}
	Let $e_i\in\RR^r$ be the $i$'th standard unit vector so that $u_i = \Psi_n^re_i$. So,
	\[(\Psi_n^r)^Tu_i = (\Psi_n^r)^T\Psi_n^re_i =(\mathrm{Id}_r + (\Psi_n^r)^T\Psi_n^r - \mathrm{Id}_r)e_i=e_i + E_{n,r}e_i.\]
	We then have
	\begin{align*}
	M_n^ru_i &= \Psi_n^r\Lambda^r(\Psi_n^r)^Tu_i = \Psi_n^r\Lambda^re_i + \Psi_n^r\Lambda^rE_{n,r}e_i \\
	&= \lambda_i\Psi_n^re_i + \Psi_n^r\Lambda^rE_{n,r}e_i = \lambda_iu_i + \Psi_n^r\Lambda^rE_{n,r}e_i.
	\end{align*}
	To bound the error, we estimate $\norm{M_n^ru_i - \lambda_iu_i}_2^2=\norm{\Psi_n^r\Lambda^rE_{n,r}e_i}_2^2$ as
	\begin{align*}
	\inner{\Lambda^rE_{n,r}e_i}{(\Psi_n^r)^T\Psi_n^r\Lambda^rE_{n,r}e_i} &= \inner{\Lambda^rE_{n,r}e_i}{E_{n,r}\Lambda^rE_{n,r}e_i}+ \norm{\Lambda^rE_{n,r}e_i}_2^2 \\
	&\leq \left(\sqrt{C(n,r)}+1\right)\norm{\Lambda^rE_{n,r}e_i}_2^2 \leq K^2\left(\sqrt{C(n,r)}+1\right)C(n,r).
	\end{align*}

	It remains to bound $C(n,r)$. Let  $X_i^r = ( \psi_0(X_i),\dots, \psi_{r-1}(X_i))$ stand for the $i$'th row of $\Psi_n^r$. Then, $E_{n,r} = \frac{1}{n}\sum_{i=1}^n\left((X_i^r)^T X_i^r - \mathrm{Id}_r\right)$, is a sum of independent, centered random matrices.
	We have
	\begin{align*}
	\sigma_{n,r}^2 &:= \norm{ \EE\left( \frac{1}{n}\sum_{i=1}^n\left((X_i^r)^T X_i^r - \mathrm{Id}_r\right)\right)^2}_{op} \\
	&= \frac{1}{n} \norm{\EE \left( (X_1^r)^T X_1^r - \mathrm{Id}_r\right)^2}_{op}
	\end{align*}
	Furthermore, the norm of the matrices can be bounded by
	\begin{align*}
	\norm{\frac{1}{n}\left((X_1^r)^T X_1^r - \mathrm{Id}_r\right)}_{op} &=\frac{1}{n} \max(1, \norm{X_1^r}_2^2 -1) \\
	&\leq \frac{1}{n}\max\left(1, \norm{ \sum_{i=0}^r \psi_i^2}_\infty - 1\right).
	\end{align*}
	Note that the right hand side of the two last displays are of the form $\frac{1}{n} l(r)$ where $l(r)$ depends only on $r$ and $d$ (not not on $n$). Applying matrix Bernstein (\cite[Theorem 6.1]{Tropp12}) then gives
	\[
	\PP\left( \norm{E_{n,r}}_{op}\geq t \right) \leq 2r \exp\left(-\frac{n}{2l(r)}\frac{t^2}{1+t/3} \right),
	\]
	where $l(r)$ depends only on $r$ and $d$. Choose now $t_0 = \frac{4 l(r)\log(2r/\eta)}{n}$. As long as $n\geq l(r) \log (2r/\eta)$, $t_0 \leq 4$, and the above bound may be refined to
	\[
\PP\left( \norm{E_{n,r}}_{op}\geq t_0 \right) \leq 2r \exp\left(-\frac{n}{l(r)}\frac{t_0^2}{7} \right).
	\]
	With the above conditions, it may now be verified that $2r \exp\left(-\frac{n}{l(r)}\frac{t_0^2}{7} \right) \leq \eta$, and the proof is complete.
\end{proof}
We now show that as $r$ increases, the eigenvectors of $M_n^r$ converge to those of $M_n$. Order the eigenvalues in decreasing order $\lambda_{l_0}\geq \lambda_{l_1} \geq \lambda_{l_2} \geq\dots$ and  let $\Lambda_{>r} = \sum_{i=r}^\infty \lambda_{l_i}^2$. Note that it follows from assumption \ref{assumption 2} that $\Lambda_{>r} = O(r^{-3})$. We will denote by $\lambda_i(M_n), \lambda_i(M_n^r)$ the respective eigenvalues of $M_n$ and $M_n^r$, ordered in a decreasing way, and by $v_i(M_n),v_i(M_n^r)$ their corresponding unit eigenvectors. Suppose that $s$ is such that
\begin{equation}\label{eq:defs}
\lambda(\vphi) = \lambda_{l_{s+1}} = \dots = \lambda_{l_{s+d}}.
\end{equation}
Moreover, define
$$
V_n := \mathrm{span}(v_{l_{s+1}}(M_n),..., v_{l_{s+d}}(M_n)), ~~~ V_n^r := \mathrm{span}\left(v_{l_{s+1}}(M_n^r),..., v_{l_{s+d}}(M_n^r)\right).
$$
The next lemma shows that $V_n$ is close to $V_n^r$ whenever both $n$ and $r$ are large enough.
\begin{lemma}  \label{lem: finite rank}
	For all $n,r$, let $P_{n,r}$ be the orthogonal projection onto $V_n^r$. Then, for all $\eta > 0$ there exist constants $n_0,r_0$ such that for all $n>n_0$ and $r>r_0$, we have with probability at least $1-\eta$ that, for all $w\in V_n$,
	$$\norm{w - P_{n,r}w}_2 \leq \frac{4C}{\eta\delta^2 r^3 }.$$
	where $\delta$ and $C$ are the constants from Assumption \ref{assumption1} and Assumption \ref{assumption 2}.
\end{lemma}
\begin{proof}
	We have
	\begin{align*}
	\EE \norm{M_n - M_n^r}^2_{F} &= \sum_{i,j} \EE (M_n -M_n^r)^2_{i,j} \\
	& = \sum_{i,j} \frac{1}{n^2} \EE \left(\sum_{k=r}^\infty \lambda_k\psi_k(X_i)\psi_k(X_j)\right)^2 \\
	& =  \EE_{x,y \sim \sigma} \left(  \sum_{k=r}^\infty \lambda_k \psi_k(x)\psi_k(y)\right)^2 \\
	& = \sum_{k=r}^\infty \lambda_k^2 = \Lambda_{>r}.
	\end{align*}
	Applying Markov's inequality gives that with probability $1-\eta$
	\begin{equation}
	\label{eq: approx Mn}
	\norm {M_n - M_n^r}^2_{F} \leq \frac{\Lambda_{>r}}{\eta}\leq\frac{C}{\eta r^3}.
	\end{equation}
	Theorem 1 in \cite{valdivia2018relative} shows that there exists $n$ large enough such that with probability larger than $1-\eta$, one has
	\[
	|\lambda_i(M_n) - \lambda_{l_{s+i}}| \leq \delta / 4,
	\]
	with $\delta$ being the constant from Assumption \ref{assumption1}. It follows that
	\begin{equation}\label{eq:lambdas}
	\lambda_{l_{s+1}}(M_n),...,\lambda_{l_{s+d}}(M_n) \in \left[\lambda(\vphi)-\frac{\delta}{4}, \lambda(\vphi)+\frac{\delta}{4}\right],
	\end{equation}
	while by \eqref{eq: approx Mn} and Weyl's Perturbation Theorem (e.g., \cite[Corollary III.2.6]{Bhatia1997}), for $r$ large enough with probability $1-\eta$,
	\begin{equation}\label{eq:otherlambdas}
	\lambda_i(M_n^r) \notin \left[\lambda(\vphi)-\frac{3\delta}{4}, \lambda(\vphi)+\frac{3\delta}{4}\right], \text{ for } i \neq l_{s+1},\dots l_{s+d}.
	\end{equation}
	Combining \eqref{eq: approx Mn}, \eqref{eq:lambdas} and \eqref{eq:otherlambdas} it follows from the classical Davis-Kahan theorem (see e.g. \cite[Section VII.3]{Bhatia1997}) that with probability at-least $1-2\eta$, for every $w \in V_n$,
	$$\norm{w - P_{n,r}w}_2^2 \leq \frac{4C}{\eta\delta^2 r^3}.$$
\end{proof}
Denote
$$
G_n := \frac{1}{d} \sum_{k=1}^d v_{l_{s+k}}(M_n) v_{l_{s+k}}(M_n)^T, ~~~ (G_n')_{i,j} = \frac{1}{n}\langle X_i, X_j \rangle.
$$
A combination of the last two lemmas produces the following:
\begin{theorem}
	\label{thm:eigenvectors_converge}
	One has
	$$
	\| G_n - G_n' \|_F \to 0
	$$
	in probability, as $n \to \infty$.
\end{theorem}
\begin{proof}
	Denote
	$$
	G_n^r:=\frac{1}{d}\sum_{k=1}^d v_{l_{s+k}}(M_n^r)(v_{l_{s+k}}(M_n^r))^T.
	$$
	Then
	$$
	\| G_n - G_n' \|_F \leq \|G_n^r - G_n'\|_F + \|G_n-G_n^r\|_F
	$$
	We will show that the two terms on the right hand side converge to zero. Let $r(n)$ be a function converging to infinity slowly enough so that $C(n,r)\to 0$, for the constant $C(n,r)$ defined in Lemma \ref{lem: lambda approx}. Taking $\eta = \eta(n)$ to converge to zero slowly enough and applying Lemma \ref{lem: lambda approx}, gives for all $2 \leq i \leq d+1$,
	$$
	\|(M_n^r - \lambda(\vphi)) u_i \|_2^2 \leq \eps_{n}
	$$
	with $u_i$ the $i$'th column of $\Psi_n^{r}$ and where $\eps_n \to 0$ as $n\to \infty$. Now, if we write
	$$
	u_i = \sum_{j=0}^\infty \alpha_{i,j} v_j(M_n^r),
	$$
	the last inequality becomes
	$$
	\sum_j |\lambda_j(M_n^r) -\lambda(\vphi)|^2 \alpha_{i,j}^2 = \sum_j |(M_n^r - \lambda(\vphi)) v_j(M_n^r) |^2 \alpha_{i,j}^2 \leq \eps_n, ~~ \forall 2 \leq i \leq d+1.
	$$
	Using Equation \eqref{eq:otherlambdas}, we have
	\begin{equation}\label{eq:alphas}
	\sum_{j \notin \{l_{s+1},..,l_{s+d}\}} \alpha_{i,j}^2 \leq \frac{4 \eps_n}{\delta} \to 0,
	\end{equation}
	and thus
	$$
	\left\|u_i - \sum_{k=1}^d \alpha_{i, l_{s+k}} v_{l_{s+k}}(M_n^r)\right\|_2^2\to 0,  ~~ \forall 2 \leq i \leq d+1.
	$$
	Define a $d\times d$-matrix $B$ by $B_{i,j}=\alpha_{i, l_{s+j}}$. Then we can rewrite the above as
	$$
	\left\|(u_1,\dots,u_d) - (v_{l_{s+1}}(M_n^r),\dots, v_{l_{s+d}}(M_n^r))\cdot B\right\|_F^2 \to 0.
	$$
	Now, since for two $n\times d$ matrices $R,S$ we have $\|RR^T - SS^T\|_F\leq (\|R\|_{op} +\|S\|_{op})\|R-S\|_F$. It follows that
	\begin{equation}\label{eq:interm1}
	\|G_n' - (v_{l_{s+1}}(M_n^r), \dots, v_{l_{s+d}}(M_n^r))BB^T(v_{l_{s+1}}(M_n^r), \dots, v_{l_{s+d}}(M_n^r))^T\|_F \to 0.
	\end{equation}
	Observe that
	$$
	B_{i,j} = \langle u_i, u_j \rangle - \sum_{k \notin \{l_{s+1},..,l_{s+d}\}} \alpha_{i,k} \alpha_{j,k},
	$$
	implying that
	$$
	|(B B^T)_{i,j} - E_{i,j}| \leq \sqrt{ \sum_{k \notin \{l_{s+1},..,l_{s+d}\}} \alpha_{i,k}^2 \sum_{k \notin \{l_{s+1},..,l_{s+d}\}} \alpha_{j,k}^2 } \stackrel{ \eqref{eq:alphas} }{\longrightarrow} 0.
	$$
	where $E = E_{n,r}$. Consequently we have
	$$
	\|B B^T - \mathrm{Id}_d \|_{op} \leq C(n,r) \to 0,
	$$
	which implies that
	\begin{align*}
	\|v_{l_{s+1}}(M_n^r), \dots, v_{l_{s+d}}(M_n^r))(BB^T-\mathrm{Id}_d)(v_{l_{s+1}}(M_n^r), \dots, v_{l_{s+d}}(M_n^r))^T\|_F^2\to 0.
	\end{align*}
	Combining with \eqref{eq:interm1} finally yields
	$$
	\|G_n' - G_n^r\|_F \to 0.
	$$
	in probability, as $n\to\infty$.
	\\
	If $P$ is the orthogonal projection onto $V^r_n=\mathrm{span}(v_{l_{s+1}}(M_n^r),\dots,v_{l_{s+d}}(M_n^r))$, and $Q$ is the orthogonal projection onto $\mathrm{span}(v_{l_{s+1}}(M_n),\dots,v_{l_{s+d}}(M_n))$, then Lemma \ref{lem: finite rank} shows that for all $\eta > 0$, with probability at least $1-\eta$, as $n\to \infty$ (and $r=n^{\frac{1}{2d}}\to\infty$), we have for every unit vector $v$
	\begin{equation}\label{eq:PnotP}
	|(P - \mathrm{Id}) Q v | \leq \eps_n
	\end{equation}
	with some $\eps_n \to 0$. By symmetry, we also have for every unit vector $v$ that
	$$
	|(Q - \mathrm{Id}) P v | \leq \eps_n
	$$
	(this uses that fact that both $P$ and $Q$ are projections into subspaces of the same dimension). The last two inequalities easily yield that $\|P - Q\|_{op} \leq \eps_n$. Since this is true for every $\eta > 0$, it follows that
	$$
	\|G_n-G_n^r\|_F\to 0 ,
	$$
	in probability, as $n\to\infty$.
\end{proof}

Now, after establishing that $M_n$ is close to $\Psi_n^{d+1}$, the second step is to recover $M_n$ (and therefore $\Psi_n^{d+1}$), from the observed $A$. For the proof we will need the following instance of the Davis-Kahan theorem.
\begin{theorem} [{\cite[Theorem 2]{YuWaSa14}}]
	\label{thm:Davis-Kahan}
	Let $X,Y$ be symmetric matrices with eigenvalues $\lambda_0\geq\dots \geq\lambda_p$ resp. $\hat\lambda_0\geq\dots\geq\hat{\lambda}_p$ with corresponding orthonormal eigenvectors 			$v_0,\dots,v_p$ resp. $\hat v_0,\dots, \hat v_p$. Let $V=(v_{s+1},\dots, v_{s+d})$ and $\hat V = (\hat v_{s+1},\dots, \hat v_{s+d})$. Then there exists an orthogonal $ d \times d$ 	matrix $R$ such that
	\[
	\| \hat V R - V \|_{F} \leq \frac{2^{3/2} \min(d^{1/2}\| Y-X\|_{op}, \|Y-X\|_F)}{\min(\lambda_{s}-\lambda_{s+1}, \lambda_{s+d}-\lambda_{s+d+1})}.
	\]
\end{theorem}
Our main tool to pass from the expectation of the adjacency matrix to the matrix itself is the following result regarding concentration of random matrices, which follows from \cite[Theorem 5.1]{LeLevVer18}.
\begin{theorem}
	\label{thm:perturbationbound}
	Let $A$ be the adjacency matrix of a random graph drawn from $G\left(n, \frac{1}{n} \vphi(X_i, X_j)\right)$. Consider any subset of at most $10n/\|\vphi\|_\infty$ vertices, and reduce the weights of the edges incident to those vertices in an arbitrary way but so that all degrees of 	the new (weighted) network become bounded by $2\|\vphi\|_\infty$. Then with probability at least $1- n^{-1}$ the adjacency matrix $A'$ of the new weighted graph satisfies
	\[
	\|A'-M_n\| \leq C \sqrt{\|\vphi\|_\infty}.
	\]
\end{theorem}

We can now prove the main reconstruction theorem.
\begin{proof}[Proof of Theorem \ref{thm: reconstruction bound}]

	Let $A$ be the adjacency matrix of a random graph drawn from the model $G\left(n, \frac{1}{n} \vphi(X_i, X_j)\right)$. We first claim that with probability tending to $1$, there exists a re-weighted adjacency matrix $A'$ as defined in Theorem \ref{thm:perturbationbound}. Indeed by Chernoff inequality for have for all $i \in [n]$,
	$$
	\PP(d_i > 1.5 \|\vphi\|_\infty ) \leq e^{-c n}
	$$
	and therefore, by Markov's inequality, the expectation of the number of vertices whose degree exceeds $2 \|\vphi\|_\infty$ goes to zero with $n$.

	Denote by $\lambda_0'\geq\lambda_1'\geq\dots$ its eigenvalues and by $v_0', v_1',\dots$ the corresponding orthonormal eigenvectors of $A'$. Let $Y = (v_{l_{s+1}}',\dots,v_{l_{s+d}}')$. By Theorem \ref{thm:Davis-Kahan} there exists an $R\in \mathcal{O}(d)$ such that
	\begin{align*}
	\norm{ \left(v_{l_{s+1}}(M_n),...,v_{l_{s+d}}(M_n)\right) - YR }_{F} &\leq \frac{2^{3/2} d^{1/2}\| M_n - A'\|_{op}}{\min_{i\neq 1,\dots,d}|\lambda_{i}-\lambda(\vphi)|}.
	\end{align*}
	Hence by Theorem \ref{thm:perturbationbound} we have
	\[
	\norm{ \left(v_{l_{s+1}}(M_n),...,v_{l_{s+d}}(M_n)\right) - YR }_{F} \leq C \sqrt{ d} \cdot \frac{\sqrt{\|\varphi\|_\infty}}{ \min_{i\neq 1,\dots,d}|\lambda_{i}-\lambda(\vphi)|},
	\]
	with probability $1-n^{-1}$. It follows that
	$$
	\norm{ G_n - Y Y^T  }_{F} \leq  C \sqrt{ d} \cdot \frac{\sqrt{\|\varphi\|_\infty}}{ \min_{i\neq 1,\dots,d}|\lambda_{i}-\lambda(\vphi)|}
	$$
	Combining this with Theorem \ref{thm:eigenvectors_converge} yields
	\begin{align*}
	\norm{  G_n' - Y Y^T \ }_{F} \leq  C \sqrt{d} \cdot \frac{\sqrt{\|\varphi\|_\infty}}{\min_{i\neq 1,\dots,d}|\lambda_{i}-\lambda(\vphi)|},
	\end{align*}
	So,
	$$
	\frac{1}{n^2} \sum_{i,j} \left |X_i \cdot X_j - (n Y Y^T)_{i,j} \right |^2 \leq  C d  \frac{\|\varphi\|_\infty}{\min_{i\neq 1,\dots,d}|\lambda_{i}-\lambda(\vphi)|^2}
	$$
	which gives the desired reconstruction bound.
	\iffalse
	Let $X$ be the matrix
	$$
	X = (X_1, ..., X_n)
	$$
	with the $X_i's$ as column vectors. Consider the singular value decompositions
	$$
	X = U_1 \Sigma_1 V_1, ~~~ Y = U_2 \Sigma_2 V_2.
	$$
	Then we have
	$$
	\norm{\frac{1}{n} U_1 \Sigma_1^2 U_1^T - U_2 \Sigma_2^2 U_2^T}_F^2 \leq C d \cdot \left (\frac{\sqrt{\|\varphi\|_\infty}}{\min_{i\neq 1,\dots,d}|\lambda_{i}-\lambda(\vphi)|} \right )^2
	$$
	\fi

\end{proof}

\section{Lower bounds} \label{sec:lower}

Our approach to proving lower bounds will be to exploit some symmetries which are inherent to well behaved kernel functions. We thus make the following definition:
\begin{definition}[DPS property]
	Let $\mu$ be a probability measure on $\Spd$, and let $w \in \Spd$. We say that $\mu$ has the Diminishing Post-translation Symmetry (DPS) around $w$ property with constant $\eps$, if there exists a decomposition,
	\[\mu = (1-\eps)\mu_w + \eps \mu_w^s.\]
	Here $\mu_w^s$ is a probability measure, invariant to reflections with respect to $w^\perp$.
	In other words, if $R = \mathrm{I}_d - 2ww^T$, $R_*\mu_w^s = \mu_w^s$.
	For such a measure we denote $\mu \in \mathrm{DPS}_w(\eps)$.\\

	If instead $\mu$ is a measure on $(\Spd)^{|T_k|}$, we say that $\mu \in \mathrm{DPS}^k_w(\eps)$ if a similar decomposition exists
	but now the reflections should be applied to each coordinate separately.
\end{definition}
We now explain the connection between the DPS property and percolation of information in trees. For this, let us recall the random function $g:T \to \Spd$, introduced in Section \ref{sec:perco}, which assigns to the root, $r$, a uniformly random value and for any other $u \in T$, the label $g(u)$ is distributed according to $\vphi(g(\mathrm{parent}(u)),\cdot)d\sigma$.
\begin{lemma} \label{lem:generallower}
	Suppose that there exist a sequence $(p_k)_k$ with $\lim_{k\to \infty} p_k= 1$ such that for every $w,x_0 \in \Spd$ and every $k > 0$,
	\[\mathrm{Law}((g(v))_{v\in T_k}|g(r) = x_0) \in \mathrm{DPS}^k_w(p_k).\]
	Then there is zero percolation of information along $T$.
\end{lemma}
\begin{proof}
	 Denote $X = g(r)$ and $Y = g(v)_{v\in T_k}$ and let $\rho_{X|Y}$ be the density of $X|Y$ with respect to $\sigma$.
	 Our aim is to show that $\EE_Y\left[\mathrm{TV}(X|Y,\sigma)\right] = o(1)$. We first claim that it is enough to show that for all $x,x' \in \Spd$ and all $\delta > 0$ one has
	$$
	\PP \left . \left ( \frac{\rho_{X|Y}(x)  }{ \rho_{X|Y}(x') } - 1 \leq \delta \right | X = x  \right ) = 1-o(1).
	$$
	Indeed, let $H = \left  \{\frac{\rho_{X|Y}(x)  }{ \rho_{X|Y}(x') } - 1 \leq \delta \right \}$. Note that, by Bayes' rule,
	$$
	\frac{\rho_{X|Y}(x)  }{ \rho_{X|Y}(x') } = \frac{\rho_{Y|X=x}(Y)  }{ \rho_{Y|X=x'}(Y) }.
	$$
	Let $x \in \Spd$ be some fixed point and let $x'$ be uniformly distributed is $\Spd$.
	Consider the random variables $\alpha:= \alpha(Y) = \frac{\rho_{Y|X=x}(Y)}{ \rho_{Y}(Y) }$ and $\beta:=\beta(x',Y) = \frac{\rho_{Y|X=x'}(Y)}{\rho_Y(Y)}$.
	By definition of $H$ , we have
	\begin{equation} \label{eq:betalarge}
	(1-\delta)\mathbf{1}_H\alpha\leq \mathbf{1}_H\beta,
	\end{equation}
	 and
	\[
	(1-2\delta)\leq(1-\delta)\PP\left(H|X=x\right)=(1-\delta)\EE_{Y}\left[\alpha\mathbf{1}_H\right]	\leq \EE_{x',Y}\left[\beta\mathbf{1}_H\right]\leq\EE_{x',Y}\left[\beta\right]\leq1.
	\]
	So, from Markov's inequality
	\begin{equation}\label{eq:betasmall}
	\PP\left(\beta\mathbf{1}_H\geq (1-\delta)\alpha\mathbf{1}_H+2\sqrt{\delta}\right)\leq \frac{\EE\left[\beta\mathbf{1}_{H}\right]-(1-\delta)\EE\left[\alpha\mathbf{1}_H\right]}{2\sqrt{\delta}}\leq \sqrt{\delta}.
	\end{equation}
	By integrating over $x'$, we get
	\begin{equation} \label{eq:alphalarge}
	(1-\delta)\alpha\mathbf{1}_{H} \leq \EE_{x'}\left[\beta\mathbf{1}_{H}\right] \leq 1 \implies \alpha\mathbf{1}_{H} \leq \frac{1}{1-\delta}.
	\end{equation}
	So, an application of the the reverse Markov's inequality shows,
	\begin{align} \label{eq:alphasmall}
	\PP\left(\alpha\mathbf{1}_{H}\geq 1-\sqrt{\delta}\right) \geq \frac{\EE\left[\alpha\mathbf{1}_{H}\right] - (1-\sqrt{\delta})}{(1-\delta)^{-1} - (1-\sqrt{\delta})}
	&= \frac{\PP\left(H|X=x\right) - (1-\sqrt{\delta})}{(1-\delta)^{-1} - (1-\sqrt{\delta})}\nonumber \\
	&\geq \frac{(1-\delta) - (1-\sqrt{\delta})}{(1-\delta)^{-1} - (1-\sqrt{\delta})}.
	\end{align}
	Note that the as $\delta \to 0$ the RHS goes to $1$. Thus, by combining the above displays, there exists a function $h$, which satisfies $\lim\limits_{\delta \to 0}h(\delta) = 0$ and some $H' \subset H$, with $\PP\left(H'\right) \geq 1 -h(\delta)$, such that, by \eqref{eq:alphalarge} and \eqref{eq:alphasmall},
	\[
	\mathbf{1}_{H'}|\alpha -1|\leq h(\delta),
	\]
	which implies, together with \eqref{eq:betalarge} and \eqref{eq:betasmall}
	\[
	\mathbf{1}_{H'}|\alpha -\beta|\leq h(\delta).
	\]
	This then gives
	\[
	\mathbf{1}_{H'}|1 -\beta|\leq 2h(\delta).
	\]
	 We can thus conclude,
	 \begin{align*}
	 \EE_Y \mathrm{TV} \left ( X|Y, X \right ) &= \EE_{Y,x'} \left [ |\beta - 1| \right ] = 2\EE_{Y,x'} \left [(1-\beta)\mathbf{1}_{\beta \leq 1} \right ] \\
	 &\leq 2 \EE_{Y,x'} \left [(1-\beta)\mathbf{1}_{\beta \leq 1}\mathbf{1}_{H'}\right ] +1-\PP\left(H'\right)\\
	 &= 2 \EE_{Y,x'} \left [|1-\beta|\mathbf{1}_{H'}\right ] +h(\delta)\\
	 &\leq 5h(\delta).\\
	 \end{align*}
	 Take now $\delta \to 0$ to get $\EE_Y \mathrm{TV} \left ( X|Y, X \right ) \to 0$.\\

	Thus, we may assume towards a contradiction that there exist $x, x' \in \Spd$ and a set $F\subset(\Spd)^{|T_k|}$, such that
	\begin{equation}\label{eq:Fbig}
	\PP\left(Y \in F | X = x \right) \geq \delta,
	\end{equation}
	and under $\{Y \in F \}$,
	\begin{equation}\label{eq:badF}
	\frac{\rho_{X|Y}(x)}{\rho_{X|Y}(x')} \geq 1+ \delta,
	\end{equation}
	for some constant $\delta > 0$.\\

	Let $w\in \Spd$ be such that the reflection $R:=\mathrm{I}_d - 2ww^T$ satisfies $Rx = x'$. Under our assumption, there exists an event $A_k$, which satisfies
	\begin{equation*}
	\PP(A_k|X=x) = 1 - o(1)
	\end{equation*}
	and such that $Y|(X=x,A_k)$ is $R$-invariant. By \eqref{eq:Fbig}, we also have
	$$\PP(A_k|X=x,Y \in F) = 1 - o(1),$$
	and thus there exists $y \in F$ such that
	\begin{equation} \label{eq:symmetricY}
	\PP(A_k | X=x,Y = y ) = 1-o(1).
	\end{equation}
	By continuity, we can make sense of conditioning on the zero probability event $E := \bigl \{X = x, ~  Y \in \{y, R y\} \bigr \}$. Note that we have by symmetry and since $y \in F$,
	\begin{equation}\label{eq:tocontradict}
	Y = y ~~ \Rightarrow ~~ 1+\delta \leq  \frac{\rho_{X|Y}(x)}{\rho_{X|Y}(x')} = \frac{\PP( Y = y | E )}{ \PP( Y = R y | E )}.
	\end{equation}
	On the other hand, we have by definition of $A_k$,
	$$
	\PP( Y = R y | E, A_k ) = \PP( Y = y | E, A_k ),
	$$
	which implies that
	\begin{align*}
	\PP( Y = R y | E ) & \geq \PP \bigl( \{Y = R y \} \cap A_k | E  \bigr) \\
	& = \PP \bigl( \{Y = y \} \cap A_k | E  \bigr) \\
	& \geq \PP( Y = y | E ) (1-o(1))
	\end{align*}
	which contradicts \eqref{eq:tocontradict}. The proof is complete.
\end{proof}
\iffalse
\begin{proof}
	Denote $g(T_k) := (g(v))_{v\in T_k}$ and let $\rho_k$ as the density of $g(r)|g(T_k)$ with respect to $\sigma$. Let $x,x' \in \Spd$ and let $w \in \Spd$, such that for the reflection $R:= \mathrm{I}{d}-2ww^T$, $Rx = x'$. We will show that $\rho(x)$ is close to $\rho(x')$. For $\eps > 0$, denote,
	$$K_x(\eps)= \{y \in \Spd| \inner{x}{y}> 1- \eps\}\text{ and }
	K_{x'}(\eps)= \{y \in \Spd| \inner{x'}{y}> 1- \eps\}.$$
	Fix $v\in T_k$. Since the law of $g(v)$ is in $\mathrm{DPS}_w(1-p^k)$, we may write the condition as
	$$g(v) = P_v\tilde{g}(v) + (1-P_v)\tilde{g}(v)^s,$$
	where $\tilde{g}(v)^s$ is $R$-invariant and $P_v \sim \mathrm{Bernoulli}(Cp^k)$ is independent.\\

	Thus, under our assumption, a union bound shows that there exists an event $A_k$, which satisfies
	\begin{equation} \label{eq:badprobaxb}
	p_{k}:=	\PP(\bar{A}_k) \leq Cq^kp^k
	\end{equation}
	and such that $g(T_k)|A_k$ is $R$-invariant.\\
	We use the law of total probability to obtain
	\begin{align*}
	|\PP&\left(g(r)\in K_x(\eps)|g(T_k)\right) - \PP\left(g(r)\in K_{x'}(\eps)|g(T_k)\right)| \\
	&\leq \PP\left(A_k\right)\left|\PP\left(g(r)\in K_x(\eps)|g(T_k) \in A_k\right) - \PP\left(g(r)\in K_{x'}(\eps)|g(T_k)\in A_k\right)\right| + p_k.
	\end{align*}
	By symmetry,
	$$\PP\left(g(T_k)\in A_k|g(r)\in K_{x'}(\eps)\right) = \PP\left(g(T_k)\in A_k|g(r)\in K_{x}(\eps)\right),$$
	and as the root is uniformly distributed,
	$$\PP\left(g(r)\in K_{x'}(\eps)\right) = \PP\left(g(r)\in K_{x}(\eps)\right).$$
	Hence, Bayes' law implies
	\begin{align*}
	|\PP&\left(g(r)\in K_x(\eps)|g(T_k) \in A_k\right) - \PP\left(g(r)\in K_{x'}(\eps)|g(T_k)\in A_k\right)| = 0.
	\end{align*}
	As, $$q\cdot p < 1,$$
	we may choose $\eps_k$ in such a way that
	$$|\rho_k(x) - \rho_k(x')| = \lim\limits_{k \to \infty}\frac{|\PP\left(g(r)\in K_x(\eps_k)|g(T_k)\right) - \PP\left(g(r)\in K_{x'}(\eps_k)|g(T_k)\right)|}{\PP\left(g(r)\in K_x(\eps_k)\right)} \leq \frac{2p_k}{\eps_k} \to 0.$$
	$\rho_k$ is a density and there exists $y_k\in \Spd$ for which $\rho_k(y_k)\leq 1$.
	Since $x,x'$ were arbitrary, we now have for every $z \in \Spd$,
	$$\rho_k(z) \leq |\rho_k(z) - \rho_k(y_k)|+\rho_k(y_k) \leq \frac{2p_k}{\eps_k} +1 < \infty.$$
	But combining the above two displays, the dominated convergence theorem shows,
	$$
	\lim_{k \to \infty} \mathrm{TV} (\mu_k, \sigma) = 0,
	$$
	and the proof is complete.
\end{proof}
\fi
\subsection{The Gaussian case}
Our aim is to show that certain classes of kernel functions satisfy the DPS condition.
We begin by considering the case where the kernel $\varphi$ is Gaussian, as in \eqref{eq:gausskernel}. In this case, the function $g$ may be defined as follows. Let $T$ be a $q$-ary tree. To each edge $e \in E(T)$ we associate a Brownian motion $(B_e(t))_{t \in (0,1)}$ of rate $\beta$ such that for every node $v \in V$ we have
$$
\ff(v) = \sum_{e \in P(v)} B_e(1) ~ \mathrm{mod} 2 \pi
$$
where $P(v)$ denotes the shortest path from the root to $v$.

For every node $v \in T_k$ let us now consider the Brownian motion $(B_v(t))_{t=0}^k$ defined by concatenating the Brownian motions $B_e$ along the edges $e \in P(v)$. Define by $E_v$ the event that the image of $B_v \mathrm{mod} \pi$ contains the entire interval $[0, \pi)$, and define $E_k = \bigcap_{v \in T_k} E_v$. Our lower bound relies on the following observation.
\begin{claim} \label{claim:uniform}
	Fix $v\in T_k$ and set $p_k := \PP(E_k)$. Then, for every $\theta ,x_0 \in \mathbb{S}^1$,
	$\mathrm{Law}(g(v)|g(r)=x_0)\in \mathrm{DPS}^k_\theta(p_k).$
\end{claim}
\begin{proof}
	Fix $\theta \in [0, \pi)$. Given the event $E_v$, we have almost surely that there exists a time $t_v \leq k$ such that $B_v(t_v) \in \{\theta- \pi, \theta \}$. By symmetry and by the Markov property of Brownian motion, we have that the distribution of $\ff(v)$ conditioned on the event $\{B_v(t_v) = \theta, ~~ \forall v\}$ is symmetric around $\theta$. Thus, by considering
	$(B_v(t))_{v\in T_k}$, under the event $\{t_v \leq k|v \in T_k \}$ we get that for any $x_0$, $\mathrm{Law}((g(v))_{v\in T_k}|g(r)=x_0)$ is symmetric around $\theta$.
	So,
	\[\mathrm{Law}((g(v))_{v\in T_k}|g(r)=x_0)\in \mathrm{DPS}^k_\theta(p_k).\]
\end{proof}
We will also need the following bound, shown for example in \cite{ES16}.
\begin{lemma} \label{lem:brownianimage}
	Let $B(t)$ be a Brownian motion of rate $\beta$ on the unit circle. Then,
	\[
	\PP( \mathrm{Image} (B(s) \mathrm{mod} \pi )_{0 \leq s \leq t}  = [0, \pi)  ) \geq 1- C e^{- t \beta /2}.
	\]
\end{lemma}
\iffalse
\begin{proof}
	Define $a = \min_{s \in [0,t]} B(s)$ and $b = \max_{s \in [0,t]}  B(s)$. By continuity,
	\[
	b \geq a + \pi \Rightarrow \mathrm{Image} (B(s) \mathrm{mod} \pi )_{0 \leq s \leq t}  = [0, \pi).
	\]
	Thus, ...
	Let $\ff(t,x)$ be the probability that $B(s)$ does not reach $\{-\pi, \pi\}$ before time $t$. Then by Feynman-Kac's formula, this function satisfies the partial differential equation
	\[
	f_t + \frac{1}{2} \beta f_{xx} = 0
	\]
	with boundary conditions $\ff(0,x) = \mathbf{1}_{|x| \leq \pi}$ and $\ff(t,\pi) = \ff(t, -\pi) = 0$. The corresponding Dirichlet problem $f_{xx} = \lambda f$, $\ff(\pm \pi) = 0$ has a spectral gap of $\lambda = 1$, so we have
	\[
	\ff(t,x) \leq C e^{-t \beta / 2}.
	\]
\end{proof}
\fi
We are now in a position to prove Theorem \ref{thm:Gaussian2d}.
\begin{proof}[Proof of Theorem \ref{thm:Gaussian2d}]
	Lemma \ref{lem:brownianimage} immediately implies that for all $v \in T_k$,
	\[
	\PP(E_v) \geq 1 - C e^{-k \beta / 2}.
	\]
	On the other hand, a calculation gives $\lambda(\vphi) = \EE[\cos(B_1)] = e^{-\beta/2}$. Thus, applying a union bound implies that for some constant $C > 0$, $\PP(E_k)\geq 1-Cq^k\lambda(\vphi)^k$.
	Hence, by Claim \ref{claim:uniform},
	\[\mathrm{Law}((g(v))_{v\in T_k}|g(r)=x_0) \in \mathrm{DPS}_w(1-Cq^k\lambda(\vphi)^k).\]
	The result is now a direct consequence of Lemma \ref{lem:generallower}.
\end{proof}
In the next section we generalize the above ideas and obtain a corresponding bound which holds for distributions other than the Gaussian one.
\subsection{The general case}

\subsubsection{On symmetric functions}
We begin this section with simple criterion to determine whether a measure belongs to some $\mathrm{DPS}$ class. In the sequel, for $w \in \Spd$, we denote,
\[
H_w^+ =\{x \in \Spd| \inner{x}{w} \geq 0\}\text{ and }H_w^- =\{x \in \Spd| \inner{x}{w} < 0\}.
\]
\newpage
\begin{lemma} \label{lem: montone ref}
	Let $f: [-1,1] \to \RR^+$ satisfy the assumptions of Theorem \ref{thm:lowerbound} and let $y \in \Spd$. If $\mu = f(\inner{\cdot}{y})d\sigma$,
	then for any $w \in \Spd$, $\mu \in \mathrm{DPS}_w(2\cdot p_w)$, where $p_w = \min\left(\mu(H_w^+),\mu(H_w^-)\right)$.
\end{lemma}
\begin{proof}
	Without loss of generality let us assume that $y \in H_w^+$. Monotonicity of $f$ implies $\mu(H_w^+)\geq\mu(H_w^-)$. Now, if $R = \mathrm{I}_d - 2ww^T$ is the reflection matrix with respect to $w^\perp$, then we have for any $x \in H^-_w$,
	\[
	f(\inner{x}{y}) \leq f(\inner{Rx}{y}).
	\]
	This follows since $\inner{x}{y} \leq \inner{Rx}{y}$.\\

	Let us now define the measure $\tilde{\mu}_w^s$ such that
	$$
	\frac{d\tilde{\mu}_w^s}{d\sigma}(x) = \begin{cases}
	f(\inner{x}{y}) & \text{ if }x \in H^-_w\\
	f(\inner{Rx}{y})& \text{ if }x \in H^+_w.
	\end{cases}
	$$
	$\tilde{\mu}_w^s$ is clearly $R$-invariant and the above observation shows that $\tilde{\mu}_w^s(\Spd) \leq 1$. We can thus define $\tilde{\mu}_w = \mu - \tilde{\mu}_w^s$.\\
	To obtain a decomposition, define $\mu_w^s = \frac{\tilde{\mu}^s_w}{\tilde{\mu}_w^s(\Spd)}$ and $\mu_w = \frac{\tilde{\mu}_w}{\tilde{\mu}_w(\Spd)}$, for which
	$$\mu = (1-\tilde{\mu}^s_w(\Spd))\mu_w + \tilde{\mu}_w^s(\Spd)\mu_w^s.$$
	The proof is concluded by noting $\tilde{\mu}_w^s(\Spd) = 2\mu(H_w^-)$.

\end{proof}
Our main object of interest will be the measure $\mu_\vphi(y)$ which, for a fixed $y$, is defined by
\begin{equation} \label{eq:muphi}
\mu_\vphi(y) := \vphi (x,y)d\sigma(x) = f (\inner{x}{y})d\sigma(x).
\end{equation}
Let us now denote,
\[
\beta_d(t) := \frac{\Gamma(\frac{d}{2})}{\Gamma(\frac{d-1}{2})}(1-t^2)^{(d-3)/2},
\]
which is the marginal of the uniform distribution on the sphere.
We now show that the spectral gap of $\vphi$ may determine the $\mathrm{DPS}$ properties of $\mu_\vphi(y)$.
\begin{lemma} \label{lem:eigendps}
	Let $w \in \Spd$ and suppose that $f$ is monotone. If $|\inner{w}{y}|\leq \frac{1-\lambda(\vphi)}{16\sqrt{d}}$, then
	$$\mu_\vphi(y) \in \mathrm{DPS}_w\left(\frac{1-\lambda(\vphi)}{35}\right).$$
\end{lemma}
\begin{proof}
	Assume W.L.O.G. that $\inner{y}{w} > 0$. By Lemma \ref{lem: montone ref} it will be enough to bound $\int\limits_{H_w^-}\mu_{\vphi}(y)$ from below. Let $X \sim \mu_{\vphi}(y)$ and define $Z = \inner{X}{y}$. We have $\EE\left[Z\right] = \lambda(\vphi)$ and by Markov's inequality,
	$$\PP\left(Z \leq \frac{1+\lambda(\varphi)}{2}\right) = \PP\left(Z + 1 \leq \frac{1+\lambda(\varphi)}{2} + 1\right) \geq1 - \frac{2(\lambda(\varphi) +1)}{3 + \lambda(\varphi)}\geq \frac{1-\lambda(\vphi)}{4}.$$
	For $t \in [-1,1]$, set $S_t = \{x \in \Spd| \inner{x}{y} = t\}$ and let $\mathcal{H}^{d-2}$ stand for $d-2$-dimensional Hausdorff measure.
	To bound $\int\limits_{H_w^-}\mu_{\vphi}(y)$ we would first like to estimate
	$\frac{\mathcal{H}^{d-2}(S_t\cap H_w^-)}{\mathcal{H}^{d-2}(S_t)}$.\\

	We know that $0 \leq \inner{w}{y} \leq \frac{1-\lambda(\vphi)}{16\sqrt{d}}$. Denote $t_y := \inner{w}{y}$ and fix $t \leq  t_0 := \frac{1+\lambda(\vphi)}{2}$. With no loss of generality, let us write $w = e_1$ and $y = t_ye_1 + \sqrt{1-t_y^2}e_2$. Define now $z = -\sqrt{1-t_y^2}e_1+t_ye_2$.
	We claim that
	\begin{equation}\label{eq:2dpicture}
	\left\{v\in S_t\Big| \frac{\inner{v}{z}}{\sqrt{1-t^2}} \geq \frac{1}{2\sqrt{d}}\right\}\subseteq S_t\cap H_w^-.
	\end{equation}
	 If $v\in S_t$, its projection onto the plane $\mathrm{span}(y,w)$, can be written as $t\cdot y + \sqrt{1-t^2}c\cdot z$, for some $c\in[-1,1]$. So,
	$$\inner{v}{w} = t\cdot t_y - \sqrt{1-t^2}\sqrt{1-t_y^2}c.$$
	Now, whenever
	$$c > \frac{t\cdot t_y}{\sqrt{1-t^2}\sqrt{1-t_y^2}},$$
	we get $\inner{v}{w} < 0$. Also,
	$$ \frac{t\cdot t_y}{\sqrt{1-t^2}\sqrt{1-t_y^2}}\leq \frac{1}{\sqrt{3}}\frac{t_y}{\sqrt{1-t_y^2}}\leq \frac{1}{2\sqrt{d}},$$
	where we have used $ t \leq \frac{1}{2}$ for the first inequality and $t_y \leq \frac{1}{2\sqrt{d}}$ in the second inequality.
	By combining the above displays with $\frac{\inner{v}{z}}{\sqrt{1-t^2}} = c$, \eqref{eq:2dpicture} is established.\\
	 Thus, by taking the marginal of $S_t$ in the direction of $-z$, we see
	\begin{align*}
	\frac{\mathcal{H}^{d-2}(S_t\cap H_w^-)}{\mathcal{H}^{d-2}(S_t)} &\geq \int \limits_{-1}^{-\frac{1}{2\sqrt{d}}}\beta_{d-1}(s)ds\geq \int \limits_{-\frac{1}{\sqrt{d}}}^{-\frac{1}{2\sqrt{d}}}\beta_{d-1}(s)ds\geq \frac{1}{2\sqrt{d}}\beta_{d-1}\left(\frac{1}{\sqrt{d}}\right)\\
	&\geq \frac{1}{2\sqrt{d}}\frac{\Gamma(\frac{d-1}{2})}{\Gamma(\frac{d-2}{2})}\left(1-\frac{1}{d}\right)^{(d-4)/2}\geq \frac{1}{10\sqrt{e}},
	\end{align*}
	where we used $\frac{\Gamma(\frac{d-1}{2})}{\Gamma(\frac{d-2}{2})} \geq \frac{\sqrt{d}}{5},$ valid for any $d \geq 3$. We use the above estimates with Fubini's theorem to obtain:
	\begin{align*}
	\PP\left(X \in H_w^-\right) &= \int\limits_{-1}^1f(t)\mathcal{H}^{d-2}(S_t\cap H_w^-)dt \geq \int\limits_{-1}^{t_0}f(t)\mathcal{H}^{d-2}(S_t\cap H_w^-)dt\\
	&\geq\frac{1}{10\sqrt{e}}\int\limits_{-1}^{t_0}f(t)\mathcal{H}^{d-2}(S_t)dt = \frac{1}{10\sqrt{e}}\PP\left(Z \leq \frac{1+\lambda(\varphi)}{2}\right)\geq\frac{1-\lambda(\vphi)}{70}.
	\end{align*}
\end{proof}
\subsubsection{Mixing}
Recall the random function $g:T \to \Spd$, introduced in Section \ref{sec:perco}, which assignes to the root, $r$, a uniformly random value and for any other $u \in T$, the label $g(u)$ is distributed according to $\vphi(g(\mathrm{parent}(u)),\cdot)d\sigma=: \mu_\vphi(\mathrm{parent}(u))$.\\
Suppose that $v \in T_k$ and let $\{v_i\}_{i=0}^k$ denote the simple path from $r$ to $v$ in $T$. Fix $x_0 \in \Spd,$ for $i = 0,\dots,k$, we now regard,
$$
X_i :=g(v_i)|g(r) = x_0,
$$
as a random walk on $\Spd$. Observe that given $X_{i-1}$, $X_i\sim\mu_\vphi(X_{i-1}).$
The following lemma shows that this random walk is rapidly-mixing.
\begin{lemma} \label{lem:mixing}
	For $w \in \Spd$, let
	$$S(w) = \left\{u \in \Spd: |\inner{u}{w}| \leq \frac{1-\lambda(\varphi)}{16\sqrt{d}}\right\},$$
	and set $k_0 = \frac{\ln\left(\frac{\lambda(\vphi)(1-\lambda(\vphi))}{32 f(1)}\right)}{\ln(\lambda(\vphi))}$.
	Then, if $f$ satisfies the assumptions of Theorem \ref{thm:lowerbound},
	$$\PP(X_{k_0} \in S(w)) \geq \frac{1-\lambda(\vphi)}{32}.$$
\end{lemma}
\begin{proof}
	Note that if 	$U \sim \mathrm{Uniform}(\Spd)$, then
	\begin{equation} \label{eq:uniformmixing}
	\PP(U \in S(w)) = \int\limits_{|t| \leq \frac{1-\lambda(\varphi)}{16\sqrt{d}}}\beta_d(t)dt  \geq 2\frac{\Gamma(\frac{d}{2})}{\Gamma\left(\frac{d-1}{2}\right)}\beta_d\left(\frac{1}{16\sqrt{d}}\right)\frac{1-\lambda(\varphi)}{16\sqrt{d}} \geq \frac{1-\lambda(\varphi)}{16}.
	\end{equation}
	It will then suffice to show that $\PP(X_{k_0} \in S(w))$ can be well approximated by $\PP(U \in S(w))$.
	Since $X_{k_0}$ has density $A^{k_0-1}_\vphi f(\inner{x}{x_0})$, the following holds true,
	\begin{align*}
	\left(\PP(U \in S(w)) - \PP(X_{k_0} \in S(w))\right)^2 &= \left(\int\limits_{S(w)}\left(A_\vphi^{k_0-1}f(\inner{x}{x_0}) - 1\right)d\sigma(x)\right)^2\\
	&\leq \int\limits_{S(w)}\left(A_\vphi^{k_0-1}f(\inner{x}{x_0}) - 1\right)^2d\sigma(x).
	\end{align*}
	We now decompose the density as $f(\inner{x}{x_0}) = \sum \limits_{i = 0}^\infty\lambda_i \psi_i(x)\psi_i(x_0)$. So that
	$$A_\vphi^{k_0-1}f(\inner{x}{x_0}) = \sum \limits_{i = 0}^\infty\lambda_i^{k_0} \psi_i(x)\psi_i(x_0).$$
	We know that $\psi_0 \equiv 1$ with eigenvalue $\lambda_0 = 1$, and we've assumed that $|\lambda_i|\leq \lambda_1 = \lambda(\varphi) $ for every $i \geq 1$. Thus,
	\begin{align*}
	\int\limits_{S(w)}\left(A_\vphi^{k_0-1}f(\inner{x}{x_0}) - 1\right)^2d\sigma(x)
	&= \int\limits_{S(w)}\left(\sum\limits_{i =1}^\infty\lambda_i^{k_0}\psi_i(x)\psi_i(x_0)\right)^2d\sigma(x)\\
	&\leq(\lambda(\vphi))^{2k_0-2}\int\limits_{S_\delta(w)}\sum\limits_{i =1}^\infty(\lambda_i\psi_i(x))^2\sum\limits_{i =1}^\infty(\lambda_i\psi_i(x_0))^2d\sigma(x) \\
	&\leq \lambda(\vphi)^{2k_0-2}f(1)^2.
	\end{align*}
	where in the last inequality we have used $f(1) = \sum\lambda_i\psi_i(y)\psi_i(y)$, which is valid for any $y \in \Spd$.
	Thus, since $k_0 = \frac{\ln\left(\frac{\lambda(\vphi)(1-\lambda(\vphi))}{32 f(1)}\right)}{\ln(\lambda(\vphi))}$, by \eqref{eq:uniformmixing}, we get,
	$$\PP(X_{k_0} \in S(w)) \geq \PP(U \in S(w)) - \frac{1-\lambda(\vphi)}{32} \geq \frac{1-\lambda(\vphi)}{32}.$$
\end{proof}
Since the random walk $X_k$ mixes well, we now use Lemma \ref{lem:eigendps} to show that after enough steps, $X_k$ will be approximately invariant to a given reflection.
\begin{lemma} \label{lem:singlerelfection}
	Let $w,x_0 \in \Spd$. Then,
	\[\mathrm{Law}((g(v))_{v \in T_k}|g(r) = x_0) \in \mathrm{DPS}^k_w\left(1- q^kp^{k}\right),
	\]
	where $p = \left(1-\frac{\ln(\lambda(\vphi))}{\ln\left(\frac{\lambda(\vphi)(1-\lambda(\vphi))}{32 f(1)}\right)}\frac{(1-\lambda(\varphi))^2}{600}\right)$.
\end{lemma}
\begin{proof}
	Let $R =\mathrm{I}_d - 2ww^T$ denote the linear reflection with respect to $w^\perp$. Then, the claim is equivalent to the decomposition,
	$$X_k = P\tilde{X}_k + (1-P)X_k^R,$$
	where $X_k^R$ is invariant to reflections by $R$ and $P \sim \mathrm{Bernoulli}(s_k)$ is independent from $\{\tilde{X}_k,X_k^R\}$ with
 $s_k \leq  \left(1-\frac{\ln(\lambda(\vphi))}{\ln\left(\frac{\lambda(\vphi)(1-\lambda(\vphi))}{32 f(1)}\right)}\frac{(1-\lambda(\varphi))^2}{600}\right)^{k}$. \\

	Consider the case that for some $i = 0,...,k$, $|\langle X_i, w \rangle| \leq \frac{1-\lambda(\vphi)}{16\sqrt{d}}$. In this case, from Lemma \ref{lem:eigendps}, given $X_i$, we have the decomposition,
	$$\mu_\vphi(X_i) = \left(1 - \frac{(1-\lambda(\vphi))}{35}\right)\mu_{\vphi,w} + \frac{(1-\lambda(\vphi))}{35}\mu_{\vphi,w}^s(X_i),$$
	where $\mu_{\vphi,w}^s(X_i)$ is $R$-invariant. \\

	We now generate the random walk in the following way. For $i = 0,\dots,k$, let
	\begin{equation} \label{eq:bernouli}
	P_i \sim \mathrm{Bernoulli}\left(\frac{(1-\lambda(\vphi))}{35}\right),
	\end{equation}
	be an \emph{i.i.d} sequence. Given $X_i$, if $|\langle X_i, w \rangle| > \frac{1-\lambda(\vphi)}{16\sqrt{d}}$ then $X_{i+1} \sim \mu_\vphi(X_i)$.\\

	Otherwise, $|\langle X_i, w \rangle| \leq \frac{1-\lambda(\vphi)}{16\sqrt{d}}$. To decide on the position of $X_{i+1}$ we consider $P_i$. If $P_i = 0$ then $X_{i+1} \sim \mu_{\vphi,w}(X_i)$. Otherwise $P_i = 1$ and we generate $X_{i+1} \sim \mu_{\vphi,w}^s(X_i)$. We denote the latter event by $A_i$ and $A = \cup_{i=0}^{k-1}A_i$. \\

	It is clear that, conditional on $A$, $RX_k \stackrel{law}{=} X_k$. Thus, to finish the proof, if $\bar{A}$ is the complement of $A$, we will need to show
	$$\PP(\bar{A}) \leq \left(1-\frac{\ln(\lambda(\vphi))}{\ln\left(\frac{\lambda(\vphi)(1-\lambda(\vphi))}{32 f(1)}\right)}\frac{(1-\lambda(\varphi))^2}{600}\right)^{k}.$$
	Towards this, let $S(w)$ and $k_0$ be as in Lemma \ref{lem:mixing}. Coupled with \eqref{eq:bernouli}, the lemma tells us that
	$$\PP\left(A_{k_0}\right) \geq \frac{(1-\lambda(\vphi))^2}{600}.$$
	Now, by restarting the random walk from $X_{k_0}$ if needed, we may show,
	$$\PP\left(\bar{A}\right)\leq \sum\limits_{m\leq \frac{k}{k_0}}\PP(\bar{A}_{m\cdot k_0})  \leq \left(1- \frac{(1-\lambda(\vphi))^2}{600}\right)^{\frac{k}{k_0}} \leq \left(1- \frac{(1-\lambda(\vphi))^2}{600k_0}\right)^{k}.$$
	Hence $\mathrm{Law}(X_{k}) \in \mathrm{DPS}(1-p)$ and the claim follows by taking a union bound over all paths.
\end{proof}
\subsubsection{Proving Theorem \ref{thm:lowerbound}}
\begin{proof}
	By Lemma \ref{lem:singlerelfection}, for every $w,x_0 \in \Spd$.
	\[ \mathrm{law}(g(v)_{v\in T_k}|g(r) = x_0) \in \mathrm{DPS}^k_w(1-q^kp^k), \]
	where $p = \left(1-\frac{\ln(\lambda(\vphi))}{\ln\left(\frac{\lambda(\vphi)(1-\lambda(\vphi))}{32 f(1)}\right)}\frac{(1-\lambda(\varphi))^2}{600}\right)$.
	By assumption
	\[ q \leq p^{-1}, \]
	and Lemma \ref{lem:generallower} gives the result.
\end{proof}

\bibliography{SBM}{}
\bibliographystyle{abbrv}

\end{document}

config: arxiv


TITLE: What is the number of inter partitions of an arbitrary positive integer $n$ that consist of only primes?
QUESTION [1 upvotes]: I would like to know that when given a positive integer, how to find the number of sets of only prime numbers that sum up to it.  For example, if $n=13$, one such set comes from $3 + 5 + 5 = 13$.
Is there a formula for this? I am trying for the number $13$, there is $9$ in total but I can only find $8$.

A professional mathematician would ask the problem this way:
What is the number of integer partitions of an arbitrary positive integer $n$ that consist of only primes?

REPLY [3 votes]: Here's some context. In general, the generating function for the number $p_S(n)$ ways to partition an integer $n$ into a sum of elements of a subset $S \subseteq \mathbb{N}$ of the natural numbers is
$$f_S(z) = \prod_{s \in S} \frac{1}{1 - z^s}.$$
If $S$ is finite these are rational functions and closed forms for $p_S(n)$ can be given; for example, if $S = \{ 1, 5, 10, 25 \}$ we are counting the number of ways to make change for $n$ cents using pennies, nickels, dimes, and quarters.
These are very complicated functions if $S$ is infinite. When $S = \mathbb{N}$ we get what is just called the partition function $p_{\mathbb{N}}(n) = p(n)$, with generating function
$$f_{\mathbb{N}}(z) = \frac{1}{(1 - z)(1 - z^2)(1 - z^3) \dots}.$$
The infinite product appearing in the denominator is the Euler function. $p(n)$ has no closed form but Hardy and Ramanujan famously showed that it is asymptotic to
$$p(n) \sim \frac{1}{4n \sqrt{3}} \exp \left( \pi \sqrt{ \frac{2n}{3} } \right)$$
and a complete asymptotic expansion is known and due to Rademacher. I say all this to emphasize that even when $S = \mathbb{N}$ this is a complex and deep problem.
Nevertheless some things can be said. In the context of Flajolet and Sedgewick's Analytic Combinatorics problems of this type can be dealt with using saddle-point asymptotics, which are at least good enough to give asymptotics for the logarithm
$$\boxed{ \log p_{\mathbb{P}}(n) \sim 2\pi \sqrt{ \frac{n}{3 \log n} } }$$
where $\mathbb{P}$ is the primes; this is VIII.26. I don't know the details of the analysis unfortunately.