\section{Introduction}

\begin{figure}[t]
\centering
\begin{minipage}{.45\textwidth}
    \centering
    \vskip 0.6cm
    \includegraphics[width=\textwidth]{coords2.pdf}
    \caption{Cartoon illustrating the coordinate system used in this work, assuming a Euclidean geometry. The outer dashed box indicates $\mathbb{R}^D$, whilst the gray plane represents $\mathbb{R}^{D-1}$, containing the Cartesian coordinates $\{x_1,\ldots,x_{D-1}\}$. The position vector $\bvec r\in\mathbb{R}^D$ can be expressed in hyperspherical coordinates $\{r,\theta_1,\ldots,\theta_{D-1}\}$, where $r$ is a radial coordinate. $\theta_{K-1}$ is defined as angle between the \resub{$\hat{\bvec x}_{K}$} axis and the projection of $\bvec r$ into the subspace $\mathbb{R}^{K}$, as shown for $\theta_{D-1}$ and $\theta_{D-2}$. The angles obey the restrictions $\theta_K\in[0,\pi)$ for $K>1$, and $\theta_1\in[0,2\pi)$. \resub{Each angle can be associated with an angular momentum index $\ell_{K-1}$, encoding} the orbital angular momentum in the subspace $\mathbb{R}^K$ \resub{in which only the first $K$ Cartesian coordinates are varied} (\S\ref{sec: single-basis}). $\ell_1$ gives the azimuthal angular momentum \resub{in the subspace containing $\{x_1,x_2,x_3\}$}, and $\ell_{D-1}$ gives the total angular momentum.}
    \label{fig: coords}
\end{minipage}%
\quad
\begin{minipage}{.44\textwidth}
    \centering
    \includegraphics[width=\textwidth]{npcfs3.pdf}
    \caption{Sketch of the decomposition underlying our NPCF algorithm, visualized for $N=4$ in a \resub{2D spherical geometry}. On the left, we show the \resub{(rotation-averaged)} 4PCF defined by three \resub{distances, $r^1$, $r^2$, $r^3$, and two angles $\hat{\bvec r}^1\cdot\hat{\bvec r}^2$, $\hat{\bvec r}^2\cdot\hat{\bvec r}^3$}, relative to a primary position $\bvec s$; na\"ive 4PCF estimation from $n$ particles proceeds by \resub{summing over each of the possible $n^4$ sets of points}. On the right, we show our decomposition, factorizing the 4PCF into three functions of two positions, $a_{\vec{\ell}}(\bvec s;r)$, which may be independently estimated from the data-set, \resub{requiring consideration of only $n^2$ pairs of particles}.
    Each function depends on a side length $r^i$ and a set of angular momentum indices $\vec{\ell}^i$; the latter specifies \resub{$\hat{\bvec r}^i$} in the hyperspherical harmonic basis. This permits \resub{the NPCF components to be estimated by an algorithm} with $\mathcal{O}(n^2)$ complexity.}
        \label{fig: npcfs}
 \end{minipage}
 \end{figure}

\section{Single-Particle Basis}\label{sec: single-basis}
We begin by discussing the angular basis for functions of one position in $\mathbb{M}^D$, hereafter referred to as the `single-particle' basis. In \S\ref{sec: npoint-basis}, the basis will allow construction of a joint basis of $(N-1)$ positions onto which the NPCF can be projected.

\subsection{Constant-Curvature Metric}\label{subsec: metric}
To form an efficient angular basis, we require the underlying manifold to be (a) homogeneous, and (b) isotropic. This leads to the well-known line-element
\begin{eqnarray}\label{eq: metric}
    \resub{d\Sigma^2_{\mathbb{M}^D}  =  dr^2+\chi_k^2(r)\left\{d\theta_{D-1}^2+\sin^2\theta_{D-1}\left[d\theta_{D-2}^2+\sin^2\theta_{D-2}\left(d\theta_{D-3}^2+\cdots\right)\right]\right\}}
\end{eqnarray}
\citep[e.g.,][]{1990MNRAS.247...57C}, adopting hyperspherical coordinates $\bvec r\equiv\{r,\theta_1,\ldots,\theta_{D-1}\}$.\footnote{\resub{Note that some conventions label the $\theta$ coordinates in the opposite order.}} In this parametrization, $r$ is a radial coordinate, whilst the $\theta_i$ are angular variables, with $\theta_1\in[0,2\pi)$ (often denoted by $\phi$ in $D=3$) and $\theta_j\in[0,\pi)$ for $j>1$. A sketch of the coordinates is shown in Fig.\,\ref{fig: coords} for a Euclidean geometry. \eqref{eq: metric} is a \textit{constant-curvature} metric, specified by \resub{$\chi_k(r) = \sin\left(r\sqrt{k}\right)/\sqrt{k}$ if $|k|>0$ and $\chi_k(r) = r$ else.}
Here, $k>0$ gives the $D$-sphere, $\mathbb{S}^D$, $k<0$ leads to the hyperbolic geometry $\mathbb{H}^D$, and $k=0$ results in a Euclidean geometry $\mathbb{R}^D$.
Such manifolds are ubiquitous in the physical sciences; for instance, this describes the spatial part of the Friedmann-Lema\^itre-Robertson-Walker metric for an expanding Universe \citep{1984ucp..book.....W}.

\subsection{\resub{Hyperspherical Harmonics}}\label{subsec: hypersphericals}
A convenient basis for the constant-curvature space $\mathbb{M}^D$ is formed from the set of \textit{harmonic} functions $H:\mathbb{M}^D\to\mathbb{C}$. These satisfy the \textit{Laplace-\resub{Beltrami}} equation
\begin{eqnarray}\label{eq: laplace-bertrami-eq}
    \Delta H(\bvec r) \equiv \frac{1}{\sqrt{|g|}}\partial_i \left(\sqrt{|g|}\;g^{ij}\partial_j H(\bvec r)\right) = 0,
\end{eqnarray}
where $H$ is twice continuously differentiable, $g$ is the metric (with $|g| = \mathrm{det}\left[g_{ij}\right]$), $i\in\{1,2,\ldots,D\}$ and we have assumed the Einstein summation convention. \resub{Assuming the metric of \eqref{eq: metric}, \eqref{eq: laplace-bertrami-eq} permits a separable solution of the form $H(\bvec r)=R(r)Y(\hat{\bvec r})$, where $\hat{\bvec r} = \{\theta_1,\ldots,\theta_{D-1}\}$. The angular part of this must satisfy the following eigenfunction equation for constant $\lambda_{D-1}$:}
\begin{eqnarray}\label{eq: eigenfunction-S-D-1}
    \Delta_{\mathbb{S}^{D-1}}Y(\hat{\bvec r}) = -\lambda_{D-1} Y(\hat{\bvec r}),
\end{eqnarray}
where $\Delta_{\mathbb{S}^{D-1}}$ is the Laplace-\resub{Beltrami} operator on the $(D-1)$-sphere, given explicitly in \eqref{eq: eigenfunction-eqns}. The corresponding solutions are the \textit{hyperspherical harmonics} on $\mathbb{S}^{D-1}$ \citep[e.g.,][]{cooper1963,cohl2011,2012arXiv1205.3548F}. \resub{Since the harmonic functions are separable, the hyperspherical harmonics form an angular basis for \textit{any} function on $\mathbb{M}^{D}$, regardless of the spatial curvature $k$.}\footnote{This is additionally seen by noting that \eqref{eq: metric} can be written $d\Sigma^2_D = dr^2 + \chi_k^2(r)d\Omega_{D-1}^2$, where $d\Omega_{D-1}^2$ is the line element on the $(D-1)$-sphere.} Physically, this decomposition is guaranteed since we have assumed the metric to be homogeneous and isotropic, enforcing invariance under the rotation group $SO(D)$ about any origin.

\resub{For a given dimension $D$, the hyperspherical harmonics, denoted $Y_{\ell_1\ldots\ell_{D-1}}(\hat{\bvec r})$, may be obtained by solving \eqref{eq: eigenfunction-S-D-1} recursively, as detailed in Appendix \ref{appen: hyperspherical}. These depend on a
set of $(D-1)$ integers, $\{\ell_k\}$, which are related to angular momentum (cf.\,\S\ref{sec: single-basis}\ref{subsec: ang-mom-single}), and satisfy} the selection rules
\begin{eqnarray}\label{eq: selection-rules}
    -\ell_2 \leq \ell_1 \leq \ell_2, \quad \ell_{K-1} \leq \ell_{K} \leq \ell_{K+1} \quad (2\leq K\leq D-1).
\end{eqnarray}
\resub{In two- and three-dimensions, the hyperspherical harmonics take a simple form:}
\begin{eqnarray}
    \resub{Y_{\ell_1}(\theta_1) = \frac{1}{\sqrt{2\pi}}\,e^{i\ell_1\theta_1}, \qquad Y_{\ell_1\ell_2}(\theta_1,\theta_2) = \sqrt{\frac{2\ell_2+1}{4\pi}\frac{(\ell_2+\ell_1)!}{(\ell_2-\ell_1)!}}\,e^{i\ell_1\theta_1}P_{\ell_2}^{-\ell_1}(\cos\theta_2),}
\end{eqnarray}
\resub{for associated Legendre polynomials $P_\ell^{m}$. The $D=3$ functions are the usual spherical harmonics (in the Condon-Shortley convention), made clear by the identification $(\ell_1,\ell_2)\to(m,\ell)$, $(\theta_1,\theta_2)\to(\phi,\theta)$, where $\phi$ is the azimuthal angle. The explicit form of the hyperspherical harmonics for general $D$ is given in \eqref{eq: hypersph-def}.}

\subsection{Connection to Angular Momentum Eigenstates}\label{subsec: ang-mom-single}

In 3D, the theory of angular momentum is centered around two operators, $\widehat{L}^2$ and $\widehat{L}_3$, which respectively give the total angular momentum and that projected onto the $\hat{\bvec x}_3$ axis. Both may be constructed from the vector operator $\widehat{\bvec L} = \bvec r \times \bvec p$, where $p_j = -i(\partial/\partial x^j)$ is the linear momentum in $\mathbb{R}^3$. For $D\neq 3$, we cannot define a cross-product, thus we instead start from the \textit{tensorial}
angular momentum operator, following \citep{louck1960}:
\begin{eqnarray}\label{eq: ang-mom-operator}
    \widehat{\mathsf L}_{ij} = x_ip_j - x_jp_i, \quad i\neq j \in \{1,2,\ldots, D\}
\end{eqnarray}
where $\{x_1,\ldots,x_D\}$ is a Cartesian coordinate chart.\footnote{Since $\mathbb{M}^D$ and $\mathbb{R}^D$ share the same angular parametrization, and angular momentum is independent of radial coordinates, we may work in a Euclidean space for the purposes of this section.} These operators are antisymmetric ($\widehat{\mathsf L}_{ij} = -\widehat{\mathsf L}_{ji}$) and form the Lie algebra $\mathfrak{so}(D)$, \textit{i.e.} \resub{that of the rotation group in $D$ dimensions}. Of particular interest is $\widehat{\mathsf L}_{12}$; when applied to some state, this gives the \resub{azimuthal angular momentum in the subspace containing $\{x_1,x_2,x_3\}$}, just as for $\widehat{L}_3$ in $D=3$.

To fully define the rotational properties of a \resub{single-particle function in $D$-dimensional space}, we must specify not only its total angular momentum, but also \resub{that} projected into lower-dimensional subspaces. \resub{These} can be obtained from the operators
\begin{eqnarray}\label{eq: k-dim-ang-mom}
    \widehat{\mathcal L}^2_{K} \equiv \sum_{i=1}^{K}\sum_{j=i+1}^K(\widehat{\mathsf L}_{ij})^2,
\end{eqnarray}
for $K\geq 3$. Here, $\widehat{\mathcal L}^2_3 \equiv (\widehat{\mathsf L}_{12})^2+(\widehat{\mathsf L}_{13})^2+(\widehat{\mathsf L}_{23})^2$ gives the angular momentum in the subspace \resub{$\{x_1,x_2,x_3,0,\ldots,0\}$ of} $\mathbb{R}^D$, $\widehat{\mathcal L}^2_4$ gives that in the subspace \resub{$\{x_1,x_2,x_3,x_4,0,\ldots,0\}$} \textit{et cetera.} $\widehat{\mathcal L}_{D}^2$ is the \resub{total} angular momentum operator, analogous to $\widehat{L}^2$ in the three-dimensional theory.

As shown in \citep[][Ch.\,3]{louck1960}, a complete set of commuting angular momentum operators is given by $\{\widehat{\mathsf{L}}_{12}$, $\widehat{\mathcal{L}}_3^2, \ldots, \widehat{\mathcal{L}}_{D}^2\}$. Moreover, the hyperspherical harmonics of \S\ref{sec: single-basis}\ref{subsec: hypersphericals} are simultaneous eigenfunctions of these, satisfying\footnote{This occurs since the $K$-dimensional Laplace-\resub{Beltrami} operator of \eqref{eq: eigenfunction-eqns} (which the hyperspherical harmonics are eigenfunctions of) is related to the $K$-dimensional total angular momentum operator by $\Delta_{\mathbb{S}^{K-1}} = -\widehat{\mathcal L}_K^2$.}
\begin{eqnarray}\label{eq: single-particle-eigenfun}
    \widehat{\mathsf L}_{12} Y_{\ell_1\ldots\ell_{D-1}}(\hat{\bvec r}) &=& \ell_1\,Y_{\ell_1\ldots\ell_{D-1}}(\hat{\bvec r}), \qquad \widehat{\mathcal L}^2_{K} Y_{\ell_1\ldots\ell_{D-1}}(\hat{\bvec r}) = \ell_{K-1}(\ell_{K-1}+K-2)\,Y_{\ell_1\ldots\ell_{D-1}}(\hat{\bvec r}) \quad (3\leq K\leq D).
\end{eqnarray}
We may thus associate $\ell_{K-1}$ with the orbital angular momentum in the subspace \resub{comprising} the first $K$ Cartesian coordinates (for $K\geq 3)$, and $\ell_1$ with that projected onto the $\hat{\bvec x}_3$ axis. Such an interpretation also justifies the conditions in \eqref{eq: selection-rules}; projections of the angular momentum into lower-dimensional spaces must have equal or \resub{lesser} magnitudes than the total angular momentum in $D$ dimensions.

For later use, we introduce abstract notation for the angular momentum basis functions, \resub{writing $Y_{\ell_1\ldots\ell_{D-1}}(\hat{\bvec r}) \to \ket{\ell_1\ldots\ell_{D-1}}$ in Dirac (or bra-ket) notation.}\footnote{The Hilbert space formed from these states is an infinite-dimensional representation of the rotation group $SO(D)$. Practically, the eigenvalue $\ell_{D-1}$ represents the behavior in $SO(D)$, whilst the values of $\ell_{K-1}$ with $K<D$ specify the rotation's action in a lower-dimensional subgroup $SO(K)$.} In total, there are $\binom{\ell_{D-1}+D-3}{D-3}(2\ell_{D-1}+D-2)/(D-2)$ eigenstates corresponding to a given total angular momentum $\ell_{D-1}$ if $D\geq 3$, and one if $D=2$ \citep[Eq.\,3.37]{louck1960}. \resub{For a suitably defined inner product, the basis functions are orthonormal} \citep{higuchi1987,cohl2011,2012arXiv1205.3548F}:
\begin{eqnarray}
    \int_{\mathbb{S}^{D-1}}d\Omega_{D-1}Y^*_{\ell_1^{}\ldots\ell^{}_{D-1}}(\hat{\bvec r})Y_{\ell_1'\ldots\ell'_{D-1}}(\hat{\bvec r}) \equiv \braket{\ell_1^{}\ldots\ell^{}_{D-1}}{\ell_1'\ldots\ell'_{D-1}} = \delta^{\rm K}_{\ell_1^{}\ell_1'}\ldots \delta^{\rm K}_{\ell_{D-1}^{}\ell_{D-1}'},
\end{eqnarray}
where the Kronecker delta, $\delta^{\rm K}_{ij}$, is unity if $i=j$ and zero otherwise. \resub{Furthermore, they form} a complete basis on $\mathbb{S}^{D-1}$, such that, for any $h:\mathbb{S}^{D-1}\to\mathbb{C}$
\begin{eqnarray}\label{eq: 1d-basis-decomp}
     \ket{h} = \sum_{\ell_1\ldots\ell_{D-1}}\braket{\ell_1\ldots\ell_{D-1}}{h}\ket{\ell_1\ldots\ell_{D-1}} \quad \leftrightarrow \quad ,h(\hat{\bvec r}) = \sum_{\ell_1\ldots\ell_{D-1}}h_{\ell_1\ldots\ell_{D-1}}Y_{\ell_1\ldots\ell_{D-1}}(\hat{\bvec r})
\end{eqnarray}
where the summation \resub{runs} over all angular momentum indices allowed by the selection rules of \eqref{eq: selection-rules}. \resub{The} basis coefficients $h_{\ell_1\ldots\ell_{D-1}}=\braket{\ell_1\ldots\ell_{D-1}}{h}$ may be obtained via orthonormality. Since the angular part of $\mathbb{M}^D$ is just the $(D-1)$-sphere $\mathbb{S}^{D-1}$ (\S\ref{sec: single-basis}\ref{subsec: metric}), \textbf{any one-particle function on $\mathbb{M}^D$ can be decomposed into this basis}; in general, the coefficients retain dependence on the radial coordinate $r$.

\section{$(N-1)$-Particle Basis}\label{sec: npoint-basis}
We now utilize the mathematics of angular momentum addition to generalize the angular basis of \S\ref{sec: single-basis} to functions of $(N-1)$ positions, \textit{i.e.} $f:\left(\mathbb{M}^D\right)^{\otimes (N-1)}\to\mathbb{C}$.

\subsection{Angular Momentum Addition}\label{subsec: ang-mom-add}
To begin, we consider the combination of two angular basis functions on the $(D-1)$-sphere. For convenience, we will work in the Dirac representation and denote the set of angular momentum indices by $\vec{\ell}\equiv\{\ell_1,\ldots,\ell_{D-1}\}$, with superscripts used to distinguish between particles. Given single-particle states $\ket{\vec{\ell}^1}$ and $\ket{\vec{\ell}^2}$, the simplest two-particle state is $\ket{\vec{\ell}^1,\vec{\ell}^2} \equiv \ket{\vec{\ell}^1}\ket{\vec{\ell}^2}$, which exists in the product space $\mathbb{S}^{D-1}\otimes\mathbb{S}^{D-1}$. This is a simultaneous eigenstate of angular momentum operators for the first and second particles, $\widehat{\mathsf L}_{ij}^{(1)}$ and $\widehat{\mathsf L}_{ij}^{(2)}$
(cf.\,\S\ref{sec: single-basis}\ref{subsec: ang-mom-single}).
Whilst the product states $\ket{\vec{\ell}^1,\vec{\ell}^2}$ do form a basis on $\mathbb{S}^{D-1}\otimes\mathbb{S}^{D-1}$ (sometimes called the `uncoupled basis' \citep{2020arXiv200205011T}), it is not an efficient one, since (a) we require $2(D-1)$ angular momentum indices to specify the state, which, as shown below, is considerably more than necessary, and (b) the indices are not straightforwardly connected to the \resub{joint} rotation properties of the two-particle state.

A more appropriate basis is wrought by considering the \resub{combined} angular momentum operator $\widehat{\mathsf L}_{ij}^{(12)} \equiv \widehat{\mathsf L}_{ij}^{(1)} + \widehat{\mathsf L}_{ij}^{(2)}$, which specifies the properties of some two-particle function, $f(\bvec r^1,\bvec r^2)$, under joint rotations of $\bvec r^1$ and $\bvec r^2$ about a common origin. As in \S\ref{sec: single-basis}\ref{subsec: ang-mom-single}, $\widehat{\mathsf L}_{ij}^{(12)}$ may be used to construct a set of commuting angular momentum operators, whose eigenstates can be written $\ket{\vec{L}}\equiv\ket{L_1\ldots L_{D-1}}$. Here, $L_{K-1}$ specifies the \resub{combined} angular momentum projected into the $K$-dimensional subspace \resub{in which the first $K$ Cartesian coordinates are varied} (for $K\geq 3$), and $L_1$ gives that projected onto the $\hat{\bvec x}_3^1,\hat{\bvec x}_3^2$ axes. Similarly to the single-particle state, the $\vec{L}$ indices must obey the selection rules of \eqref{eq: selection-rules}.

Two-particle states of definite combined angular momentum are formed by summing over products of one-particle states, just as in the 3D case (e.g.,\,\citep{biedenharn_louck_carruthers_1984,1988qtam.book.....V}, see also \citep{2014arXiv1412.5829S,2019PhRvC..99c4320T,2020arXiv200205011T} for a \resub{discussion with more general $D$}). \resub{Explicitly, they are given by}
\begin{eqnarray}\label{eq: ang-mom-add-N=3}
    \boxed{\ket{\ell_{D-1}^{1}\;\ell_{D-1}^2;\vec{L}} = \sum_{\ell_1^{1}\ldots\ell^{1}_{D-2}}\sum_{\ell_2^2\ldots\ell^2_{D-2}}\cg{\vec{\ell}^1}{\vec{\ell}^2}{\vec{L}} \ket{\vec{\ell}^1}\ket{\vec{\ell}^2},}
\end{eqnarray}
where $\cg{\vec{\ell}^1}{\vec{\ell}^2}{\vec{L}}$ is a Clebsch-Gordan (hereafter CG) coefficient \citep[e.g.,][]{VanIsacker1991}. This is often referred to as the `coupled basis' \citep{2020arXiv200205011T}. To uniquely define the state, we must specify (a) the combined angular momentum eigenvalues $\vec{L}$, and (b) the total angular momentum of the first and second particle, $\ell_{D-1}^1$ and $\ell_{D-1}^2$. Importantly, \eqref{eq: ang-mom-add-N=3} involves a sum over $\{\ell_1^i,\ldots,\ell_{D-2}^i\}$, \textit{i.e.} the projection of the particles' angular momentum into lower-dimensional subspaces. Due to this, the combined state is specified by only $(D+1)$ indices, which, for $D>3$, is significantly fewer than the $2(D-1)$ required for $\ket{\vec{\ell}^1,\vec{\ell}^2}$.

Practically, one must know the CG coefficients $\cg{\vec{\ell}^1}{\vec{\ell}^2}{\vec{L}}$ in order to form the \resub{coupled basis} of \eqref{eq: ang-mom-add-N=3}.\footnote{The CG coefficients used in this work are those of the $SO(D)\supset SO(D-1)\supset \cdots\supset SO(2)$ reduction.} These have been studied in depth \citep[e.g.,][]{biedenharn1961,biedenharn_louck_carruthers_1984,1988qtam.book.....V,VanIsacker1991,Louck2006,2010JMP....51i3518C} and may be simplified by techniques such as Racah's factorization lemma \citep{Racah1965}. One route to their computation is via \eqref{eq: ang-mom-add-N=3}; starting from a state of maximal combined angular momentum, $\ket{\ell_{D-1}^{1}\ell_{D-1}^2;\vec{\ell}^1+\vec{\ell}^2} \equiv \ket{\vec{\ell}^1 }\ket{\vec{\ell}^2}$ (wherein the two angular momentum vectors in $\mathbb{R}^{D}$ are aligned), ladder operators may be applied iteratively to obtain states of lower angular momentum, whose weightings give the CG coefficients. \resub{As in \citep{1988qtam.book.....V,biedenharn_louck_carruthers_1984}, the explicit forms for the CG coefficients in $D=2$ and $D=3$ are given by}
\begin{eqnarray}\label{eq: CG-examples}
    \resub{\cg{\ell^1}{\ell^2}{L} = \delta^{\rm K}_{(\ell^1+\ell^2)L}, \qquad \cg{\ell^1_1\ell^1_2}{\ell_1^2\ell_2^2}{L_1L_2} = (-1)^{-\ell_2^1+\ell_2^2-L_1}\sqrt{2L_2+1} \tj{\ell_2^1}{\ell_2^2}{L_2}{\ell_1^1}{\ell_1^2}{-L_1},}
\end{eqnarray}
\resub{where the $2\times 3$ matrix is a Wigner 3-$j$ symbol \citep[e.g.,][\S34]{NIST:DLMF}. The $D=4$ case is similar \citep[see][]{biedenharn1961,VanIsacker1991,2006JPhA...39.3099M}, but includes a Wigner 9-$j$ symbol.}

CG coefficients satisfy certain orthogonality conditions, including
\begin{eqnarray}\label{eq: CG-orthonorm}
    \sum_{\ell^{1}_1\ldots\ell_{D-2}^{1}}\sum_{\ell^2_1\ldots\ell^2_{D-2}}\cg{\vec{\ell}^1}{\vec{\ell}^2}{\vec{L}}\cg{\vec{\ell}^1}{\vec{\ell}^2}{\vec{L}'} = \delta^{\rm K}_{L_1^{}L_1'}\times \cdots\times \delta^{\rm K}_{L_{D-1}^{}L_{D-1}'}.
\end{eqnarray}
Coupled with the orthonormality of the one-particle states $\ket{\vec{\ell}}$ (Eq.\,\ref{eq: N-1-particle-orthonormality}), this ensures that the combined-angular-momentum basis is orthonormal, \textit{i.e.}
\begin{eqnarray}
    \braket{\resub{l^1_{D-1} l^2_{D-1};\vec{L}'}}{\ell^1_{D-1}\ell_{D-1}^2;\vec{L}} = \left(\delta^{\rm K}_{L^{}_1L_1'}\cdots\delta^{\rm K}_{L^{}_{D-1}L'_{D-1}}\right)\times\left(\delta^{\rm K}_{\ell^1_{D-1}l^1_{D-1}}\delta^{\rm K}_{\ell_{D-1}^2l_{D-1}^2}\right).
\end{eqnarray}
Furthermore, $\cg{\vec{\ell}^1}{\vec{\ell}^2}{\vec{L}}$ is non-zero only if the \resub{following conditions} are satisfied:
\begin{eqnarray}\label{eq: addition-triangle-conditions}
    L_1 = \ell^{1}_1 + \ell^2_1, \quad |\ell^{1}_K-\ell^2_K|\leq L_K \leq \ell^{1}_K+\ell^2_K, \quad \resub{(2\leq K\leq D-1)}.
\end{eqnarray}
The first constraint occurs since $L_1$ is the eigenvalue corresponding to $\widehat{\mathsf L}^{(12)}_{12}$, which is linear in $\widehat{\mathsf L}_{12}^{(1)}$ and $\widehat{\mathsf L}_{12}^{(2)}$ (cf.\,addition of $m$ indices in 3D), and the second is due to the triangle inequality, recalling that $L_K$ corresponds to the magnitude of the angular momentum in the subspace $\mathbb{R}^{K}$. In particular, the constraints fix the total combined angular momentum, $L_{D-1}$, to be no greater than $\ell_{D-1}^1+\ell_{D-1}^2$.

\subsection{Combined Angular Momentum Basis}
By repeated application of the angular momentum addition rule (Eq.\,\ref{eq: ang-mom-add-N=3}), we may build up an $(N-1)$-particle state of definite combined angular momentum. \resub{First, we combine $\ket{\vec{\ell}^1}$ and $\ket{\vec{\ell}^2}$ to form the two-particle state $\ket{\ell^1_{D-1}\ell^2_{D-1};\vec{\ell}^{12}}$, which is then combined with $\vec{\ell}^3$ to form the three-particle state $\ket{\ell^1_{D-1}\ell^2_{D-1}\ell^{12}_{D-1}\ell^{3}_{D-1};\vec{\ell}^{123}}$, \textit{et cetera}.}
\resub{In full, we obtain the} $(N-1)$-particle basis function
\begin{eqnarray}\label{eq: combined-ang-mom-states}
    \boxed{
    \ket{\L;\vec{L}} = \sum_{[\vec{\ell}^1][\vec{\ell}^2]\ldots[\vec{\ell}^{N-1}]}C^{\L;\vec{L}}_{\vec{\ell}^1\vec{\ell}^2\ldots\vec{\ell}^{N-1}}\ket{\vec{\ell}^1}\ket{\vec{\ell}^2}\cdots\ket{\vec{\ell}^{N-1}},}
\end{eqnarray}
summing over all intermediate angular momenta $\ell_{k}^i$ with $k<(D-1)$, as denoted by $[\vec{\ell}^i]$.\footnote{For $D=3$, our basis functions match the coupled representation of $SU(2)$ discussed in \citep{2020arXiv200205011T} in the context of quantum chemistry.}
\resub{The combined state in \eqref{eq: combined-ang-mom-states} is specified by} the set of total angular momentum indices $\L \equiv \{\ell^1_{D-1},\ell_{D-1}^2,\ell_{D-1}^{12},\ell^3_{D-1},\resub{\ell^{123}_{D-1},\ell^4_{D-1}},\ldots,\ell_{D-1}^{12\ldots(N-2)},\ell_{D-1}^{{N-1}}\}$ and \resub{involves the coupling coefficients}
\begin{eqnarray}\label{eq: Coupling-C}
    C^{\L;\vec{L}}_{\vec{\ell}^1\vec{\ell}^2\ldots\vec{\ell}^{{N-1}}} = \sum_{[\vec{\ell}^{12}]\ldots[\vec{\ell}^{12\ldots(N-2)}]}\cg{\vec{\ell}^1}{\vec{\ell}^2}{\vec{\ell}^{12}}\cg{\vec{\ell}^{12}}{\vec{\ell}^3}{\vec{\ell}^{123}}\cdots\cg{\vec{\ell}^{12\ldots(N-2)}}{\vec{\ell}^{N-1}}{\vec L},
\end{eqnarray}
\resub{which is a product of CG symbols.} We have additionally set $\vec{\ell}^{12\ldots (N-1)}\equiv \vec{L}$, representing the combined angular momentum eigenvalues. Note that \eqref{eq: combined-ang-mom-states} contains a sum over both the primary indices $\ell^{i}$ (which define the single-particle states) and intermediates, e.g., $\ell^{12\ldots}$ (within the coupling definitions), but not those corresponding to total angular momenta, \textit{i.e.} $\ell_{D-1}$.

The meaning of \eqref{eq: combined-ang-mom-states} is straightforward; an $(N-1)$-particle state with \resub{combined angular momentum} $\vec{L}$ can be obtained as a sum of product states, weighted by $(N-2)$ CG coefficients. To define the state uniquely, we must specify not only the total angular momentum $\ell_{D-1}$ of each single-particle state, but also the total angular momentum of the intermediate states, e.g., $\ell_{D-1}^{12}$ arising from the coupling of $\ket{\vec{\ell}^1}$ and $\ket{\vec{\ell}^2}$. In total, the state is specified by $(2N+D-5)$ indices; again significantly fewer than the $(N-1)(D-1)$ required for the product state $\ket{\vec{\ell}^1}\cdots\ket{\vec{\ell}^{N-1}}$.

A particularly interesting state is that of \resub{zero} combined angular momentum, \textit{i.e.} $\vec{L} = \vec 0$.\footnote{For $\mathbb{M}^D = \mathbb{R}^3$, our treatment of the $\vec{L} = \vec 0$ states exactly follows that of \citep{2020arXiv201014418C}.} From \eqref{eq: combined-ang-mom-states}, this is simply
\begin{eqnarray}\label{eq: zero-ang-mom-states}
    \boxed{\ket{\L;\vec{0}} = \sum_{[\vec{\ell}^1]\ldots[\vec{\ell}^{N-1}]}C^{\L;\vec 0}_{\vec{\ell}^1\ldots\vec{\ell}^{{N-1}}}\ket{\vec{\ell}^1}\ket{\vec{\ell}^2}\cdots\ket{\vec{\ell}^{N-1}}.}
\end{eqnarray}
Unlike the general state (Eq.\,\ref{eq: combined-ang-mom-states}), this is \resub{involves} only $(N-4)$ intermediate couplings $\vec{\ell}^{12\ldots}$, since the final CG coefficient in \eqref{eq: Coupling-C} fixes $\ell^{12\ldots(N-2)}_1 = -\ell_1^{N-1}$ and $\ell^{12\ldots(N-2)}_K = \ell_K^{N-1}$ for $K>1$. In total, \resub{this requires $(2N-5)$ indices to fully specify}, regardless of dimension.

\subsection{$(N-1)$-Particle Basis Properties}\label{subsec: multi-basis-properties} The $(N-1)$-particle basis functions of Eqs.\,\ref{eq: combined-ang-mom-states}\,\&\,\ref{eq: zero-ang-mom-states} have analogous properties to those of the single-particle basis (cf.\,\S\ref{sec: single-basis}\ref{subsec: ang-mom-single}). Using \eqref{eq: CG-orthonorm}, we can show orthonormality:
\begin{eqnarray}\label{eq: N-1-particle-orthonormality}
    \braket{\resub{\L';\vec{L}'}}{\L;\vec{L}} = \delta^{\rm K}_{\L\L'}\delta^{\rm K}_{\vec{L}\vL'}
\end{eqnarray}
requiring equality of \resub{both} the combined angular momentum vectors ($\vec{L}$ and $\vec{L}'$) and all components of $\L$ and $\L'$.
Since the \resub{angular momentum} states form a complete basis, any $(N-1)$-particle function $h:\left(\mathbb{S}^{D-1}\right)^{\otimes (N-1)}$ \resub{can be decomposed into a sum of basis states:}
\begin{eqnarray}\label{eq: general-basis-decomp}
    \ket{h} = \sum_{\vec{L}}\sum_{\L}\braket{\resub{\L;\vec{L}}}{h}\ket{\L;\vec{L}} \quad \leftrightarrow \quad h(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{N-1}) = \sum_{\vec{L}}\sum_{\L} h_\L^{\vec{L}}\P_\L^{\vec{L}}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{N-1})
\end{eqnarray}
summing over both combined angular momentum indices $\vec{L}$ and the indices contained within $\L$ (analogously to Eq.\,\ref{eq: 1d-basis-decomp}). The basis components are denoted by $\braket{\resub{\L;\vec{L}}}{h}\equiv h_{\L}^{\vec{L}}$. For the second equality, we switch to wavefunction notation, with the basis functions defined as (cf.\,Eq.\,\ref{eq: combined-ang-mom-states})
\begin{eqnarray}\label{eq: N-1-particle-basis-wavefunction}
    \boxed{\P_\L^{\vec{L}}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{N-1}) = \sum_{[\vec{\ell}^1][\vec{\ell}^2]\ldots[\vec{\ell}^{N-1}]}C^{\L;\vec{L}}_{\vec{\ell}^1\vec{\ell}^2\ldots\vec{\ell}^{N-1}}Y_{\vec{\ell}^1}(\hat{\bvec r}^1)Y_{\vec{\ell}^2}\resub{(\hat{\bvec r}^2)}\cdots Y_{\vec{\ell}^{N-1}}(\hat{\bvec r}^{N-1}),}
\end{eqnarray}
where $Y_{\vec{\ell}}(\hat{\bvec r})$ are the hyperspherical harmonics of \S\ref{sec: single-basis}\ref{subsec: hypersphericals}. Since $\mathbb{S}^{D-1}$ is the angular part of $\mathbb{M}^D$, \textbf{the directional dependence of any $(N-1)$-particle function in $\mathbb{M}^D$ can be expanded in the separable form of Eq.\,\ref{eq: general-basis-decomp}.}

If the function $h$ appearing in \eqref{eq: general-basis-decomp} has rotational symmetry, a simpler decomposition is possible. In particular, we assume it to be invariant under rotations drawn from \resub{the subspace $\{x_1,\ldots,x_K,0,\ldots,0\}$ of $SO(D)$.}
\resub{An example of this would be azimuthal symmetry in $D=3$; here, the system is invariant under rotations about one axis only. To obey rotational symmetry in $K$ dimensions, the basis functions must satisfy}
\begin{eqnarray}
    \widehat{\mathcal L}^2_K \ket{\L;\vec{L}} = 0 \quad \Rightarrow \quad L_i=0, \quad  \forall \,i < K,
\end{eqnarray}
where $\widehat{\mathcal L}^2_{K}$ is the combined angular momentum operator (Eq.\,\ref{eq: k-dim-ang-mom}).\footnote{This occurs since any basis function with $L_K\neq 0$ has non-zero combined angular momentum in the $K$-dimensional subspace, violating rotational invariance.} In this instance, only basis functions of the form $\ket{\L;0\ldots 0\; L_K\ldots L_{D-1}}$ enter into \eqref{eq: general-basis-decomp}, \resub{reducing the number of basis coefficients from approximately $\left(\ell_{D-1}^{\rm max}\right)^{2N+D-5}$ to $\left(\ell_{D-1}^{\rm max}\right)^{2N+D-K-5}$, for maximum multipole $\ell_{D-1}^{\rm max}$}. If $h$ is invariant under spatial rotations about \textit{any} axis (\textit{i.e.} it is isotropic), \resub{only the $\vec{L} = \vec 0$ state is required}. In this case
\begin{eqnarray}\label{eq: iso-basis-expansion}
    \ket{h} &=& \sum_{\L} \braket{\L;\vec0}{h} \ket{\L;\vec 0} \quad \leftrightarrow \quad h(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{N-1}) = \sum_{\L}h_{\L}^{\vec 0} \P_\L^{\vec 0}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{N-1}),
\end{eqnarray}
for components $h_{\L}^{\vec 0}\equiv \braket{\resub{\L;\vec 0}}{h}$, which may be determined via orthonormality. \textbf{The directional dependence of any \resub{isotropic} $(N-1)$-particle function in $\mathbb{M}^D$ can be expanded in the separable form of Eq.\,\ref{eq: iso-basis-expansion}.}

\resub{For $N=3$ and $N=4$, the isotropic basis functions take the explicit forms:}
\begin{eqnarray}
    \P_{\ell_{D-1}}^{\vec 0}(\hat{\bvec r}^1,\hat{\bvec r}^2) &=& \sum_{\ell_1\ldots\ell_{D-2}} Y_{\ell_1\ell_2\ldots\ell_{D-1}}(\hat{\bvec r}^1)Y_{(-\ell_1)\ell_2\ldots\ell_{D-1}}(\hat{\bvec r}^2),\\\nonumber
    \P_{\ell^1_{D-1}\ell^2_{D-1}\ell^3_{D-1}}^{\vec 0}(\hat{\bvec r}^1,\hat{\bvec r}^2,\hat{\bvec r}^3) &=& \sum_{\ell_1^1\ldots\ell^1_{D-2}}\sum_{\ell^2_1\ldots\ell^2_{D-2}}\sum_{\ell_1^3\ldots\ell^3_{D-2}}\cg{\vec{\ell}^1}{\vec{\ell}^2}{(-\ell^3_1)\ell_2^3\ldots\ell_{D-1}^3}Y_{\ell_1^1\ldots\ell^1_{D-1}}(\hat{\bvec r}^1)Y_{\ell_1^2\ldots\ell^2_{D-1}}(\hat{\bvec r}^2)Y_{\ell_1^3\ldots\ell^3_{D-1}}(\hat{\bvec r}^3).
\end{eqnarray}
\resub{noting that the final CG coefficient is of the form $\cg{\vec{\ell}^{12\ldots(N-2)}}{\vec{\ell}^{N-1}}{\vec 0}$, which enforces $\ell^{12\ldots(N-2)}_1+\ell^{N-1}_1=0$ and $\ell^{12\ldots(N-2)}_K=\ell^{N-1}_K$ for $K>1$. This is a natural extension of the Legendre polynomials to $D$ dimensions; indeed the $D=3$ case recovers the Legendre polynomial $\mathcal{L}_{\ell_2}(\hat{\bvec r}^1\cdot\hat{\bvec r}^2)$ rescaled by $(-1)^{\ell_2}(4\pi)/\sqrt{2\ell_2+1}$ \citep[cf.][]{2020arXiv201014418C}.}

\resub{Finally, we note} the properties of the basis functions under complex conjugation and parity inversion:
\begin{eqnarray}\label{eq: basis-parity-conj}
    \left[\P_\L^{\vec L}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{{N-1}})\right]^* &=& (-1)^{L_{D-1}-L_{1}}(-1)^{\ell^1_{D-1}+\cdots+\ell^{N-1}_{D-1}}\P_\L^{\vec 0}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{{N-1}}) \\\nonumber
    \mathbb{P}\left[\P_\L^{\vec L}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{{N-1}})\right] &=& (-1)^{\ell_{D-1}^1+\cdots+\ell_{D-1}^{{N-1}}}\P_\L^{\vec 0}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{{N-1}}),
\end{eqnarray}
using \eqref{eq: complex-conj-hypersph}, noting that the CG coefficients enforce $\ell_1^1+\ell_1^2+\cdots+\ell_1^{N-1}+L_1=0$. For $\vec{L}=\vec 0$, this implies that even-(odd-)parity basis functions are purely real (imaginary).

\section{An Efficient Correlation Function Estimator}\label{sec: NPCF-estimator}
Armed with the $(N-1)$-particle angular basis of \S\ref{sec: npoint-basis}, we now proceed to construct an \resub{efficient} estimator for the $N$-point correlation function \resub{components}. For full generality, we do not assume the NPCF to have any rotational symmetry; such symmetries set various basis components to zero, as discussed in \S\ref{sec: npoint-basis}\ref{subsec: multi-basis-properties}.

\subsection{Derivation}
Assuming statistical homogeneity, the NPCF defined in \eqref{eq: zeta-def} is a function of $(N-1)$ points on $\mathbb{M}^D$, and may thus be expanded in the combined angular momentum basis of \S\ref{sec: npoint-basis} (cf.\,Eq.\,\ref{eq: zeta-basis-decomp-intro}):
\begin{eqnarray}\label{eq: zeta-basis-decomp}
    \boxed{\zeta(\bvec r^1,\ldots,\bvec r^{N-1}) = \sum_{\vec{L}}\sum_{\L} \zeta^{\vec{L}}_\L(r^1,\ldots,r^{N-1})\P_{\L}^{\vec L}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{N-1}),}
\end{eqnarray}
where the basis states, $\P_\L^{\vec{L}}$, are defined in \eqref{eq: N-1-particle-basis-wavefunction}. As before, we sum both over $\vec{L}$, which specifies the properties of the NPCF under joint rotations of all $(N-1)$ direction vectors (with only $\vec{L} = \vec 0$ required if the NPCF is isotropic), and $\L \equiv \{\ell^1_{D-1},\ell_{D-1}^2,\ell_{D-1}^{12},\ell^3_{D-1},\resub{\ell^{123}_{D-1},\ell^4_{D-1}},\ldots,\ell_{D-1}^{{N-1}}\}$, which defines the relative orientations of the direction vectors. In this form, the NPCF is fully specified by the \resub{basis coefficients} $\zeta^{\vec{L}}_\L$, which are functions only of the radial parameters $r^i$.

Due to the parity properties of the basis functions (Eq.\,\ref{eq: basis-parity-conj}), basis coefficients with even (odd) $\sum_{i=1}^{N-1} \ell_{D-1}^i$ represent even-parity (odd-parity) NPCF contributions; furthermore, they are purely real (imaginary) if the random field $X$ is real-valued and $\vec{L} = \vec 0$. Parity-odd isotropic basis functions occur only for $N>D$; at lower orders, a parity transformation is equivalent to a rotation, under which the basis functions are invariant.

The basis coefficients can be extracted from \eqref{eq: zeta-basis-decomp} via an inner product:
\begin{eqnarray}\label{eq: zeta-basis-coeff}
    \zeta_\L^{\vec{L}}(r^1,\ldots,r^{N-1}) \equiv \braket{\L;\vec{L}}{\zeta} =  \int_{\left(\mathbb{S}^{D-1}\right)^{\otimes (N-1)}}d\Omega_{D-1}^1\cdots d\Omega_{D-1}^{N-1}\,\left[\zeta(\bvec r^1,\ldots,\bvec r^{N-1})\P_\L^{\vec L,*}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{N-1})\right],
\end{eqnarray}
where the integral is over $(N-1)$ copies of the angular space. As in \eqref{eq: NPCF-estimator-full}, the NPCF may be estimated as a product of $N$ random fields, integrated over space; inserted into \eqref{eq: zeta-basis-coeff} this yields
\begin{eqnarray}\label{eq: NPCF-estimator-basis-1}
    \hat\zeta^{\vec{L}}_\L(r^1,\ldots,r^{N-1}) = \frac{1}{V_D}\int_{\mathbb{M}^D} d^D\bvec s \int_{\left(\mathbb{S}^{D-1}\right)^{\otimes (N-1)}}d\Omega_{D-1}^1\cdots d\Omega_{D-1}^{N-1}\,\left[X(\bvec s)X(\bvec s+\bvec r^1)\cdots X(\bvec s+\bvec r^{N-1})\P_\L^{\vec L,*}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{N-1})\right].
\end{eqnarray}
Finally, we insert the explicit forms of the $(N-1)$-particle basis functions (Eq.\,\ref{eq: N-1-particle-basis-wavefunction}), which \resub{yields}
\begin{eqnarray}\label{eq: NPCF-mult-estimator}
    \boxed{\hat\zeta^{\resub{\vec L}}_\L(r^1,\ldots,r^{N-1}) = \frac{1}{V_D}\sum_{[\vec{\ell}^1]\ldots[\vec{\ell}^{N-1}]}C^{\L;\vec{L}}_{\vec{\ell}^1\ldots\vec{\ell}^{N-1}}\int_{\mathbb{M}^D} d^D\bvec s\,\left[X(\bvec s)a_{\vec{\ell}^1}(\bvec s;r^1)\cdots a_{\vec{\ell}^{N-1}}(\bvec s;r^{N-1})\right],}
\end{eqnarray}
defining the functions
\begin{eqnarray}\label{eq: alm-def}
    a_{\vec{\ell}}(\bvec s;r) \equiv \int_{\mathbb{S}^{D-1}}d\Omega_{D-1}\,X(\bvec s+\bvec r)Y^*_{\vec{\ell}}(\hat{\bvec r}).
\end{eqnarray}
\resub{Importantly, the angular integrals are now fully decoupled.}

\resub{Usually, the NPCF statistic is binned in radius via a set of $(N-1)$ top-hat filters, $\Theta^{b^K}(r^K)$, which are equal to $1$ if $r^K$ is in bin $b^K$ and zero else. In this case, $\hat\zeta_{\L}^{\vec{L}}(r^1,\ldots,r^{N-1})$ is replaced by its binned form $\hat\zeta_{\L}^{\vec{L},\vec b}$, where $\vec b \equiv\{b^1,\ldots,b^{N-1}\}$. This is again estimated using \eqref{eq: NPCF-mult-estimator}, defining the bin integrated functions
\begin{eqnarray}\label{eq: alm-bin-def}
    a_{\vec{\ell}}^{b}(\vec s) = \frac{1}{v_b}\int_{\mathbb{M}^D}d^D\bvec r\,X(\bvec s+\bvec r)Y_{\vec{\ell}}^*(\hat{\bvec r})\Theta^b(r),
\end{eqnarray}
where $v_b \equiv \int_{\mathbb{M}^D}d^D\bvec r$ is the bin volume. Assuming a fixed maximum multipole $\ell_{D-1}^{\rm max}$ and some number of bins $N_b$, this ensures that only a finite number of $a_{\vec{\ell}}^{b}(\bvec s)$ coefficients (asymptotically, $N_b\times\left(\ell_{D-1}^{\rm max}\right)^{N-1}$) need to be estimated at each position $\bvec s$. If one wished to reconstruct the full correlator $\zeta(\bvec r^1,\ldots,\bvec r^{N-1})$ from the set of measured basis coefficients, this truncation would lead to an approximation error. In practice, this can be avoided by projecting the theory model in the same manner as the data; then, using a low $\ell_{D-1}^{\rm max}$ will lead only to a slight loss of information, depending on the model in question.}

Estimation of the NPCF basis components reduces to two operations: (1) computing \resub{$a_{\vec{\ell}}^b(\bvec s)$ for each radial bin $b$} and angular momentum eigenvalue set $\vec{\ell}$ of interest,
and (2) performing a spatial integral over $\bvec s$, alongside a sum over the lower-dimensional angular momentum eigenvalues \resub{$[\vec{\ell}^i]\equiv\{\ell^i_1,\ldots,\ell^i_{D-2}\}$}, subject to the coupling rules of \eqref{eq: selection-rules}\,\&\,\eqref{eq: addition-triangle-conditions}. Computationally, this is \resub{much} more efficient than a direct implementation of \eqref{eq: NPCF-estimator-basis-1}. A cartoon indicating this procedure for $N=4$ is shown in Fig.\,\ref{fig: npcfs}.

\subsection{Application to Discrete Data}\label{subsec: discrete-estimator}
\resub{For discrete data, the random field $X$ can be represented as a (weighted) sum of Dirac deltas, as in \eqref{eq: NPCF-estimator-intro-discrete}. Inserting this definition} into \eqref{eq: NPCF-mult-estimator} leads to the following estimator \resub{for the NPCF basis coefficients in bins $\vec b$}:
\begin{eqnarray}\label{eq: NPCF-estimator-discrete}
    \resub{\hat\zeta_\L^{\vec{L},\vec b}} &=& \frac{1}{V_D}\sum_{j=1}^n \resub{w^j}\sum_{[\vec{\ell}^1]\ldots[\vec{\ell}^{N-1}]}C^{\L;\vec{L}}_{\vec{\ell}^1\ldots\vec{\ell}^{N-1}}\left[\resub{a^{b^1}_{\vec{\ell}^1}(\bvec y^j)\cdots a_{\vec{\ell}^{N-1}}^{b^{N-1}}(\bvec y^j)}\right],\quad    a_{\vec{\ell}}^{b}(\bvec y^j) = \frac{1}{v_b}\sum_{k=1}^n\,w^kY^*_{\vec{\ell}}(\widehat{\bvec y^k-\bvec y^j})\Theta^{b}\left(\left|\bvec y^k-\bvec y^j\right|\right).
\end{eqnarray}
Practically, the \resub{$a_{\vec{\ell}}^b(\bvec y^j)$} functions may be computed by summing over $n$ points, $\{\bvec y^k\}$, weighted by a hyperspherical harmonic and a \resub{binning function} in the separation vector $\bvec y^k-\bvec y^j$. Since the functions must be estimated at the location of each primary particle, $\bvec y^j$, \textbf{the algorithm has complexity $\mathcal{O}(n^2)$} \resub{(with respect to $n$), for any choice of $D$ or $N$}. This is \resub{significantly} faster than the na\"ive NPCF estimator of \eqref{eq: NPCF-estimator-intro-discrete}, \resub{inserting the basis functions}
\begin{eqnarray}\label{eq: B-hypersph}
    \resub{B(\bvec r^1,\ldots,\bvec r^{N-1})\equiv \P_{\vec\Lambda}^{\vec{L}}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{N-1})\Theta^{b^1}(r^1)\cdots\Theta^{b^{N-1}}(r^{N-1}),}
\end{eqnarray}
\resub{showing the utility of our hyperspherical harmonic decomposition.}

\resub{Although the scaling with $n$ is independent of $D$ and $N$, we do expect the computational cost of a full NPCF measurement to increase in higher-dimensional scenarios. In part, this occurs since the number of intermediate $[\vec{\ell}^i]$ summations in \eqref{eq: NPCF-estimator-discrete} is a strong function of $D$ and $N$. In total, we must sum over approximately $(D-1)(N-1)$ indices, each of which is bounded by $\ell^{\rm max}_{D-1}$, thus the computation time is asymptotically $\propto\left(\ell^{\rm max}_{D-1}\right)^{(D-1)(N-1)}$. Since this summation must be done once per primary particle $\bvec y^j$, we expect the algorithm to scale linearly with $n$ if this process dominates over $a_{\vec{\ell}}^b$ computation. Secondly, the number of basis vectors at fixed $\ell^{\rm max}_{D-1}$ is exponential in $D$ and $N$. Asymptotically, this scales as $N_b^{N-1}\times \left(\ell_{D-1}^{\rm max}\right)^{2N-4}\times \left(\ell_{D-1}^{\rm max}\right)^{D-1}$ (counting elements of $\vec b, \vec \Lambda$ and $\vec L$ respectively, using $N_b$ radial bins per dimension). Although this is a strong scaling, it is generic to any higher-point basis (and usually referred to as the `curse of dimensionality'). In the presence of certain symmetries, the number of basis functions is significantly reduced: for example, isotropy demands that $\vec{L}=\vec 0$, reducing the scaling to $N_b^{N-1}\times \left(\ell_{D-1}^{\rm max}\right)^{2N-5}$, independent of $D$. In the below, we will always compare na\"ive and efficient estimators projected onto the same basis, thus this factor appear in the ratio of computation times.}

\subsection{Application to Gridded Data}\label{subsec: gridded-estimator}
Our \resub{estimators may} also be applied to continuous data discretized on some regular grid, which is of use for the analysis of hydrodynamic simulations, for example. For this, we first rewrite \resub{$a_{\vec{\ell}}^b(\bvec s;r)$} (Eq.\,\ref{eq: alm-bin-def}) as
\begin{eqnarray}
    \resub{a_{\vec{\ell}}^b(\bvec s) = \int_{\mathbb{M}^{D}}d^D\bvec r\,X(\bvec s+\bvec r)Y^*_{\vec{\ell}}(\hat{\bvec r})\Theta^b(r) \equiv (-1)^{\ell_{D-1}}\int_{\mathbb{M}^{D}}d^D\bvec r\,X(\bvec s-\bvec r)\left[Y_{\vec{\ell}}(\hat{\bvec r})\Theta^b(r)\right],}
\end{eqnarray}
\resub{relabelling variables and utilizing the conjugate properties of hyperspherical harmonics (Eq.\,\ref{eq: complex-conj-hypersph}).}
For gridded data in Euclidean space, \textit{i.e.} with $\mathbb{M}^D = \mathbb{R}^{D}$, this may be straightforwardly computed using the $D$-dimensional FFT. Explicitly:
\begin{eqnarray}
    \resub{a_{\vec{\ell}}^b(\bvec s) = (-1)^{\ell_{D-1}}\mathrm{FFT}^{-1}\left[\mathrm{FFT}(X)\mathrm{FFT}(Y_{\vec{\ell}}\;\Theta^b)\right].}
\end{eqnarray}
where $\mathrm{FFT}^{-1}$ is the inverse FFT. These operations have complexity $\mathcal{O}(n_{\rm g}\log n_{\rm g})$ for $n_{\rm g}$ grid points. Following computation of the various $a_{\vec{\ell}}^{b}(\bvec s)$ terms, the \resub{estimator for the NPCF components} can be constructed from \eqref{eq: NPCF-mult-estimator} as a simple sum in $D$ dimensions. \textbf{The full estimator has complexity $\mathcal{O}(n_{\rm g}\log n_{\rm g})$}, which is again much faster than the na\"ive $\mathcal{O}(n_{\rm g}^N)$ \resub{result. The above procedure may also be applied to the discrete data-sets discussed in \S\ref{subsec: discrete-estimator}, via a non-uniform FFT \citep{nuFFT}.

\section{Applications}\label{sec: applications}
We now consider a number of physical scenarios in which the above methods can be employed, \resub{and give numerical examples. For this purpose, we provide a \textsc{Julia} implementation of the two main algorithms discussed above (\ref{eq: NPCF-estimator-intro-discrete}\,\&\,\ref{eq: NPCF-estimator-discrete}).\footnote{\href{https:/github.com/oliverphilcox/NPCFs.jl}{GitHub.com/oliverphilcox/NPCFs.jl}} This can compute the NPCF of discrete particles with $N\in\{2,3,4,5\}$, using Cartesian geometries with $D \in\{2,3,4\}$ or spherical geometries with $D=2$ and is fully parallelized.}

\begin{figure}[t]
    \subfloat[4PCF in $\mathbb{S}^2$]{%
      \includegraphics[width=0.47\textwidth]{timings_N4_D2.pdf}
    }
    \hfill
    \subfloat[5PCF in $\mathbb{R}^3$]{%
       \includegraphics[width=0.46\textwidth]{timings_N5_D3.pdf}
    }
    \caption{\resub{Timing comparison of the na\"ive NPCF estimator with that introduced in this work. In the first case, the NPCF is estimated by counting sets of $N$ particles, via \eqref{eq: NPCF-estimator-intro-discrete}, weighting by the relevant basis functions (\S\ref{sec: npoint-basis}). The new estimators exploit hyperspherical harmonic decompositions to reduce the estimator to a sum over pairs. Here, we show results for a variety of choices of $n$, for both 4PCF estimation on the two-sphere (left), and 5PCF estimation in 3D Cartesian space (right). As expected, the runtime of na\"ive estimator scales as $n^N$ (as indicated by the red dotted lines), but the new estimators scale as $n^2$ for the 4PCF, or $n$ for the 5PCF. The latter scaling arises since we are dominated by the sum over intermediate momenta $[\vec\ell^i]$, rather than the sum over pairs; at larger $n$, we expect a quadratic scaling with $n$. All computations were performed in \textsc{Julia} using 16 CPUs, and we have verified that the measured NPCF components agree to machine precision}.}
    \label{fig: npcf-timings}
\end{figure}

\subsection{Cosmic Microwave Background}
Cosmic Microwave Background (CMB) radiation encodes a snapshot of the Universe at the epoch of recombination, around $380,000$ years after the Big Bang. This may be probed using microwave satellites such as \textit{WMAP} and \textit{Planck}, which map the CMB temperature fluctuations as a function of direction; such observations have been used to place strong constraints on cosmological parameters such as the matter density and Universe's expansion rate \citep[e.g.,][]{2011ApJS..192...18K,2020A&A...641A...6P}.

In this \resub{setting}, the random field in question is the fractional temperature fluctuation on the 2-sphere, $\Theta:\mathbb{S}^2\to\mathbb{R}$, \textit{i.e.} $\mathbb{M}^D = \mathbb{S}^2$. Conventionally, $\Theta$ is expanded in $D=3$ spherical harmonics as \resub{$\Theta(\phi,\theta;\hat{\bvec n}) = \sum_{\lambda=0}^\infty\sum_{\mu=-\lambda}^{\lambda}\Theta_{\lambda\mu}Y_{\lambda\mu}(\phi,\theta)$}, using spherical polar coordinates $\phi\in[0,2\pi)$, $\theta\in[0,\pi)$ relative to some pole on the sphere at position vector $\hat{\bvec n}$. The statistical properties of $\Theta$ are then characterized in terms of the spherical harmonic coefficients \resub{$\Theta_{\lambda\mu}$ (often denoted $a_{\lambda\mu}^T$)}. To apply the techniques of this work, we instead expand the temperature fluctuations using the $D=2$ hyperspherical harmonics (\S\ref{sec: single-basis}\ref{subsec: hypersphericals}), \textit{i.e.}
\begin{eqnarray}
    \Theta(\bvec r;\hat{\bvec n}) = \sum_{\ell=0}^\infty \Theta_\ell(\theta)Y_{\ell}(\phi) \equiv \frac{1}{\sqrt{2\pi}}\sum_{\ell=0}^\infty \Theta_\ell(\theta)e^{i\ell\phi},
\end{eqnarray}
identifying $\ell$ as the total angular momentum and $\theta$ as the radial coordinate relative to $\hat{\bvec n}$, which acts as an origin on $\mathbb{S}^2$.\footnote{Here, $\theta$ measures the arc-lengths of great-circles through two points on the 2-sphere, as viewed in $\mathbb{R}^3$.} This is a convenient basis for computing higher-order clustering statistics on the two-sphere, since (a) it avoids the need for an embedding space, and (b), it provides a natural split into isotropic and anisotropic correlators.

As in \eqref{eq: zeta-def}, the temperature NPCF is defined as a statistical average over $\Theta$:
\begin{eqnarray}\label{eq: cmb-NPCF-def}
    \zeta(\bvec r^1,\ldots,\bvec r^{N-1}) = \mathbb{E}_\Theta\left[\Theta(\bvec 0;\hat{\bvec n})\Theta(\bvec r^1;\hat{\bvec n})\cdots \Theta(\bvec r^{N-1};\hat{\bvec n})\right];
\end{eqnarray}
by statistical homogeneity, this is independent of the choice of origin $\hat{\bvec n}$. \eqref{eq: cmb-NPCF-def} may be expanded \resub{in the basis of \eqref{eq: general-basis-decomp}}, where the $D=2$ basis functions take the form
\begin{eqnarray}
    \resub{\P^{L}_{\ell^1\ldots\ell^{N-1}}}(\phi^1,\ldots,\phi^{N-1}) &=& (2\pi)^{-(N-1)/2}\mathrm{exp}\left[i(\ell^1\phi^1+\cdots+\ell^{N-1}\phi^{N-1})\right],
\end{eqnarray}
\resub{with $\ell^1+\cdots+\ell^{N-1} = L$, where $L=0$ for isotropic correlators}. Note that no intermediate angular momenta need to be specified due to the coupling rules of \eqref{eq: addition-triangle-conditions}. As in \eqref{eq: NPCF-mult-estimator}, we may form an $\mathcal{O}(n^2)$ estimator \resub{for the NPCF coefficients}:
\begin{eqnarray}
    \zeta_{\ell^1\ldots\ell^{N-1}}^{L}(\theta^1,\ldots,\theta^{N-1}) &=& \frac{1}{4\pi}\int_{\mathbb{S}^2} d\Omega_2\,\left[\Theta(\hat{\bvec n})a_{\ell^1}(\hat{\bvec n};\theta^1)\cdots a_{\ell^{N-1}}(\hat{\bvec n};\theta^{N-1})\right],\\\nonumber
    a_{\ell}(\hat{\bvec n};\theta) &\equiv& \frac{1}{\sqrt{2\pi}}\int_0^{2\pi} d\phi\, \Theta(\phi,\theta;\hat{\bvec n})e^{i\ell\phi}.
\end{eqnarray}
The first integral is over all possible choices of origin $\hat{\bvec n}$, whilst the second is over a circle centered at $\hat{\bvec n}$ with radial parameter $\theta$ \resub{(which may be discretized into bins, as before)}.

Such estimators are straightforward to implement and allow efficient computation of the higher-order CMB NPCFs, albeit in a basis somewhat different to that usually adopted. We caution that the $\ell$ indices play a different \resub{role} to those of the \resub{$\lambda$} indices appearing in the standard spherical harmonic expansion of $\Theta$. In our basis, $\ell$ represents angular momentum around an origin \textit{on} the 2-sphere, whilst \resub{$\lambda$} is with reference to the origin \textit{of} the 2-sphere in the embedding space $\mathbb{R}^3$. In practice, this allows us to restrict to \resub{much} smaller $\ell$ than used conventionally.\footnote{CMB fluctuations have characteristic angular scale $r_s(z_*)/d_A(z_*)$ where $r_s$ is the sound horizon in comoving coordinates, $d_A$ is the angular diameter distance and $z_*$ is the redshift at the end of the baryon drag epoch. This imprints a characteristic angular momentum scale $L\sim \pi d_A(z_*)/r_s(z_*)\gg 1$. In our basis, $\ell$ corresponds to the ratio of two polygon sides on $\mathbb{S}^2$ and is thus $\mathcal{O}(1)$.} We further note that the CMB contains also \resub{polarization} fluctuations. These may be analyzed using an extension of the above formalism, replacing the hyperspherical harmonics with spin-weighted hyperspherical harmonics \citep[e.g.,][]{2012PhRvD..86l5013D,2016JMP....57i2504B}.

\resub{To give a sense of how the above algorithms work in CMB contexts, we consider a simple problem: estimating the isotropic 4PCF of randomly placed points on the two-sphere. This corresponds to the above scenarios with $N=4$, $D=2$ and a spherical geometry. For this test, we generate a set of $n$ evenly distributed points, and compute the coefficients $\zeta_{\ell^1\ell^2\ell^3}^{0,b^1b^2b^3}$, using $10$ radial bins per dimension with $\cos\theta\in[-0.5,0.5)$ and $\ell_{\rm max}=4$. This leads to a total of $35$ ($120$) angular (radial) components. Timing results for the computation using both the na\"ive and quadratic estimators (projecting the 4PCF onto the same basis functions in both cases) are shown in Fig.\,\ref{fig: npcf-timings}(a) for a variety of choices of $n$, using our public \textsc{Julia} code. As expected, the runtime scales as $n^4$ for the na\"ive estimator, which leads to unwieldy computation times even for a few thousand particles. For the estimators introduced in this work, the runtime scales as $n^2$ for large $n$, as expected from the algorithm's complexity.

\subsection{Hydrodynamic Turbulence}\label{subsec: hydro-turb}
NPCFs have found significant use in the study of hydrodynamical turbulence. Being a chaotic process, the evolution of the velocity and density fields in a turbulent flow cannot be treated deterministically; rather, they must be analyzed statistically. Furthermore, the density fields of turbulent media are known to be close to log-normal \citep{1994ApJ...423..681V}, implying that the higher-order NPCFs functions contain a wealth of information, particularly concerning the sonic and Alfv\'enic Mach numbers \citep[e.g.,][]{2007ApJ...658..423K,2009ApJ...693..250B,2010ApJ...708.1204B,2018ApJ...862..119P}.

\resub{One of the simplest observables} is the turbulent density field, $\rho:\mathbb{R}^3\to\mathbb{R}$, whose $N$-point function is defined in \eqref{eq: zeta-def}. In the absence of any external forcing, we expect the NPCF to be statistically isotropic, thus it can be expanded via \eqref{eq: iso-basis-expansion} in terms of the $D=3$ basis functions \resub{with $\vec{L}=\vec 0$. As shown in \S\ref{sec: single-basis}\ref{subsec: hypersphericals},} the corresponding one-particle basis functions are just the usual spherical harmonics, $Y_{m\ell}(\hat{\bvec r})$, and their coupling can be expressed in terms of Wigner 3-$j$ symbols.

As before, we may form $\mathcal{O}(n^2)$ estimators \resub{for the NPCF coefficients} via \eqref{eq: NPCF-mult-estimator}. \resub{As an example, the isotropic 5PCF estimator becomes (ignoring radial binning for clarity)}
\begin{eqnarray}\label{eq: D=3-NPCF}

    \zeta^{\vec 0}_{\ell^1\ell^2\ell^{12}\ell^3\ell^4}(r^1,r^2,r^3) &=& \frac{1}{V_3}(-1)^{\ell^1+\ell^2+\ell^3+\ell^4}\sum_{m^1m^2m^3m^4} (-1)^{\ell^{12}-m^{12}}\sqrt{2\ell^{12}-1}\tj{\ell^1}{\ell^2}{\ell^{12}}{m^1}{m^2}{-m^{12}}\tj{\ell^{12}}{\ell^3}{\ell^4}{m^{12}}{m^3}{m^4}\nonumber\\
    &&\,\times\,\int_{\mathbb{R}^3} d\bvec s\,\left[\rho(\bvec s)a_{m^1\ell^1}(\bvec s;r^1)a_{m^2\ell^2}(\bvec s;r^2)a_{m^3\ell^3}(\bvec s;r^3)a_{m^4\ell^4}(\bvec s;r^4)\right],
\end{eqnarray}
where $V_3$ is the volume of the space, \resub{$m^{12}\equiv m^1+m^2$, and $a_{m\ell}(\bvec s; r) = \int_{\mathbb{S}^2}d\Omega_2\,\rho(\bvec s+\bvec r)Y^*_{m\ell}(\hat{\bvec r})$.}
Introducing spin-weighted (or vector) spherical harmonics, the approach may be extended to tensorial correlators, such as those of the velocity field.

\resub{Fig.\,\ref{fig: npcf-timings}(b) presents a practical demonstration of the isotropic 5PCF estimator, applied to $n$ discrete points in 3D. We consider ten radial bins in $[0.1,0.4]$ for uniformly distributed data in a periodic cube of length $1$, and fix $\ell_{\rm max}=4$. In this case, the 5PCF is specified by four radial bin indices and five angular multiplets, as in \eqref{eq: D=3-NPCF}. This gives a total of $210$ radial and $585$ angular components. As before, we find that the runtime of the na\"ive estimator scales as $n^N$, which quickly becomes computationally prohibitive. For the NPCF estimator of this work, the runtime appears to be linear in $n$, rather than quadratic: this occurs since the work is dominated by the $m^i$ summations (cf.\,\S\ref{sec: NPCF-estimator}\ref{subsec: discrete-estimator}), though we expect the $n^2$ scaling to dominate for denser samples. In all cases however, our approach is significantly faster than that of the na\"ive estimator. We note that our algorithm can be further accelerated by gridding the data, and making use of Fourier transforms.}

\subsection{Large-Scale Structure}
The large-scale distribution of matter in the late Universe follows a weakly non-Gaussian distribution and is commonly analyzed using $N$-point statistics \citep[e.g.,][]{2001ASPC..252..201P}. The underlying space is expected to be flat, homogeneous, and isotropic, and is thus described by the metric of \eqref{eq: metric} with $k=0$ and $D=3$.\footnote{Our methodology applies similarly to $k\neq 0$, though there is significant evidence implying that the Universe is flat \citep{2020A&A...641A...6P}. Additionally, our methods can be used to compute \resub{projected} correlation functions in $\mathbb{R}^2$, requiring the $D=2$ basis functions, as demonstrated in \citep{2015MNRAS.454.4142S} for the 3PCF.} A common task in cosmology is the estimation of isotropic NPCFs for the galaxy overdensity field, $\delta_g:\mathbb{R}^3\to\mathbb{R}$; this proceeds identically to \S\ref{sec: applications}\ref{subsec: hydro-turb}, except that the data are discrete. Full discussion of this (including implementation in the \textsc{encore} code\footnote{\href{https://GitHub.com/oliverphilcox/encore}{GitHub.com/oliverphilcox/encore}}) is presented in our companion work \citep{npcf_algo}, and allows information to be extracted from the high-order NPCFs, which are otherwise computationally prohibitive to measure.

Due to the effects of redshift-space distortions \citep[e.g.,][]{1987MNRAS.227....1K}, observed galaxy distributions are \resub{not} isotropic, implying that the decomposition of \eqref{eq: iso-basis-expansion} does not capture all possible NPCF information. However, the statistics are invariant under rotations about an (assumed fixed) line-of-sight, here set to $\hat{\bvec x}^3$. For a full treatment, we must instead expand the NPCF using Eq.\,\ref{eq: general-basis-decomp}, keeping only terms with $L_1=0$ (cf.\,\S\ref{sec: npoint-basis}\ref{subsec: multi-basis-properties}):
\begin{eqnarray}
    \zeta(\bvec r^1,\ldots,\bvec r^{N-1}) = \sum_{L=0}^\infty \sum_{\L} \zeta_\L^{0L}(r^1,\ldots,r^{N-1})\P^{0L}_{\L}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{N-1}),
\end{eqnarray}
writing $L \equiv L_2$. As an example, the 3PCF becomes
\begin{eqnarray}
    \zeta(\bvec r^1,\bvec r^2) &=& \sum_{L=0}^\infty \sum_{\ell^1\ell^2}\zeta^{0L}_{\ell^1\ell^2}(r^1,r^2)\P^{0L}_{\ell^1\ell^2}(\hat{\bvec r}^1,\hat{\bvec r}^2), \\\nonumber
    \P^{0L}_{\ell^1\ell^2}(\hat{\bvec r}^1,\hat{\bvec r}^2) &=& (-1)^{\ell^2-\ell^1}\sqrt{2L+1}\sum_m \tj{\ell^1}{\ell^2}{L}{m}{-m}{0} Y_{\ell^1m}(\hat{\bvec r}^1)Y_{\ell^2-m}(\hat{\bvec r}^2).
\end{eqnarray}
\cite[cf.\,][]{2018MNRAS.478.1468S,2019MNRAS.484..364S}. Such statistics may be estimated via \eqref{eq: NPCF-mult-estimator}, as before. The above decomposition provides a complete basis for the redshift-space 3PCF \citep[analogous to][]{2019MNRAS.484..364S} and extends naturally to higher orders, \resub{which have not previously been discussed.

\section{Summary}

Many areas of research require computation of clustering statistics from continuous or discrete random fields. Perhaps the most prevalent statistic is the $N$-point correlation function (NPCF), defined as the statistical average over $N$ fields in different spatial locations. If the random field is Gaussian-distributed, only the 2PCF is of interest; in the general case, all correlators have non-trivial forms. Given a set of $n$ particles, a na\"ive estimator \resub{for the NPCF components in some basis} has $\mathcal{O}(n^N)$ complexity \resub{with respect to $n$}. As $N$ increases, this rapidly becomes computationally infeasible to apply: alternative methods must be sought if one wishes to unlock the information contained within higher-order NPCFs.

This work considers NPCF estimation on isotropic and homogeneous manifolds in $D$ dimensions. Under these assumptions (which encompass spherical, flat, and hyperbolic geometries), we show that any function of one position can be expanded in hyperspherical harmonics; a $D$-dimensional analog of the conventional spherical harmonics. These are also eigenstates of the angular momentum operators; utilizing the mathematics of angular momentum addition, we can construct basis functions involving $(N-1)$ points on  $\mathbb{S}^{D-1}$ as a sum over products of $(N-1)$ hyperspherical harmonics. This forms a natural angular basis for the NPCF, particularly if the random field is statistically isotropic. The decomposition allows construction of an NPCF estimator that separates into a product of $(N-1)$ spatial integrals; \textbf{this has $\mathcal{O}(n^2)$ \resub{complexity}} \resub{(with respect to $n$)}, or $\mathcal{O}(n_{\rm g}\log n_{\rm g})$ using FFTs with $n_{\rm g}$ grid-points. \resub{The algorithms have been validated numerically using a new \textsc{Julia} implementation; in all scenarios tested, we find our approach to yield significantly faster measurements of the NPCF coefficients in our angular momentum basis.}

Such techniques will allow high-order correlation functions to be computed from data, allowing more complete analysis of phenomena ranging from fluid turbulence to galaxy clustering. \resub{Furthermore, since the algorithm can be applied to scenarios with $D\neq 3$, we may consider also the computation of NPCFs on the surface of spheres (relevant e.g., for atmospheric physics), or in higher-dimensional atomic treatments with $D=6$ \citep[e.g.,][]{cooper1963}.}
These ideas may be extended further; a case of particular interest is in the correlation functions of random fields with non-zero spin; these are required to describe the statistics of \resub{tensor} fields such as turbulent velocities and CMB polarization.

\acknow{We thank David Spergel for encouraging us to write this paper, as well as Robert Cahn, Simone Ferraro, Jiamin Hou,  \resub{Bhuv Jain, Adam Lidz}, Moritz M\"unchmeyer, \resub{Shivam Pandey}, Ue-Li Pen, \resub{Cristiano Sabiu}, Frederik Simons, Sauro Succi, and Wen Yan for insightful discussions. \resub{We are additionally indebted to the anonymous referees for insightful feedback.} OP acknowledges funding from the WFIRST program through NNG26PJ30C and NNN12AA01C \resub{and thanks the Simons Foundation for additional support}.
}

\showacknow

\section{Introduction}

\section{$N$-point Correlation Functions}\label{sec: NPCF-intro}
\oliver{should this section really be first? probably just put in the final section, and add some to the introduction with definition and why they're hard to measure. Note we don't need to assumme isotropy}
Consider a complex-valued random field $\delta:\mathbb{Q}^{D}\to\mathbb{C}$, where $\mathbb{Q}^D$ is some $D$-dimensional space. In \S\ref{sec: metric-space}, we will specialize to the Euclidean, spherical, or hyperbolic spaces, $\mathbb{Q}\in\{\mathbb{R},\mathbb{S},\mathbb{H}\}$. The $N$-point correlation function, $\zeta$, of $\delta$ is given by an expectation over $N$ copies of $\delta$ at different locations:\footnote{Within cosmology, it is common to define the NPCF as a spatial average instead of a statistical one. This is only true if the field in question is homogeneous, as discussed below.}
\begin{eqnarray}
    \zeta:\mathbb{Q}^{D\times N} &\to& \mathbb{C}\nonumber
\end{eqnarray}
\begin{equation}\label{eq: zeta-def}
    \boxed{\zeta(\bvec r^1,\ldots,\bvec r^{N-1};\bvec s) = \mathbb{E}\left[\delta(\bvec s)\delta(\bvec s+\bvec r^1)\ldots\delta(\bvec s+\bvec r^{N-1})\right]},
\end{equation}
where $\bvec s$ and $\bvec r^i$ are absolute and relative position vectors in $\mathbb{Q}^D$ and $\mathbb{E}$ represents an expectation over realizations of $\delta$.\footnote{Note that the NPCF contains both a `connected' and `disconnected' contribution, with the latter factorizing into a product of lower-point functions. If the lower-point functions are also measured, only the connected contribution adds additional information.} \eqref{eq: zeta-def} can be rewritten as a functional integral:
\begin{eqnarray}
    \zeta(\bvec r^1,\ldots,\bvec r^{N-1};\bvec s) &=& \int \mathcal{D}\delta\,\left[\delta(\bvec s)\delta(\bvec s+\bvec r^1)\ldots\delta(\bvec s+\bvec r^{N-1})\right]
\end{eqnarray}
where the measure satisfies $\int \mathcal{D}\delta = 1$. If the underlying space $\mathbb{Q}^D$ is homogeneous, and the field $\delta$ is \textit{statistically} homogeneous (such that any realization-averaged statistic of $\delta$ is invariant under translations $\delta(\bvec s)\to\delta(\bvec s+\bvec s')$ for some $\bvec s'\in \mathbb{Q}^D$), $\zeta$ must be independent of $\bvec s$, affording significant simplification. This reduces the number of degrees-of-freedom of $\zeta$ to $D\times (N-1)$.

Furthermore, we consider the case when the random field is statistically \textit{isotropic}, as is the space $\mathbb{Q}^D$. Denoting a $D$-dimensional rotation by $R$ (which is an element of the $SO(D)$ group), statistical isotropy implies
\begin{eqnarray}\label{eq: isotropy-NPCF}
    \zeta(R\bvec r^1,\ldots,R\bvec r^{N-1}) = \zeta(\bvec r^1,\ldots,\bvec r^{N-1})\,, \quad \forall\,R
\end{eqnarray}
\textit{i.e.} the NPCF is invariant under joint rotation of all $(N-1)$ spatial vectors $\bvec r^i
$.\footnote{Strictly, this is a rotation about origin the $\bvec s$, since $\{\bvec r^i\}$ are here \textit{relative} position vectors. By homogeneity, rotational symmetry applies about any origin $\bvec s$ however.} In this case, $\zeta$ is strictly an \textit{isotropic} $N$-point correlation function. Isotropy reduces $\zeta$'s degrees-of-freedom by the number of independent $D$-dimensional rotations (equal to the number of generators of $SO(D)$), $D(D-1)/2$. NPCFs may be further extended to the case where $\delta$ is \textit{not} statistically isotropic (which occurs for example with the line-of-sight distortions in observed galaxy distributions); we briefly mention this in \S\ref{sec: NPCF-estimator}.\oliver{use $\cdots$ for products?}

Statistical homogeneity allows us to estimate $\zeta$ as a spatial average over $\mathbb{Q}^D$:
\begin{eqnarray}\label{eq: NPCF-estimator-full}
    \boxed{\hat\zeta(\bvec r^1,\ldots,\bvec r^{N-1}) = \frac{1}{V^D}\int_{\mathbb{Q}^D} d^D\bvec s\,\left[\delta(\bvec s)\delta(\bvec s+\bvec r^1)\ldots\delta(\bvec s+\bvec r^{N-1})\right]},
\end{eqnarray}
where we integrate over all choices of origin $\bvec s$, with volume $V^D = \int_{\mathbb{Q}^D}d^D\bvec s$. Such an estimator is justified by the ergodic theorem, and is unbiased, \textit{i.e.} $\mathbb{E}[\hat\zeta] = \zeta$ for expectation operator $\mathbb{E}$. \eqref{eq: NPCF-estimator-full} may be further averaged over rotations $R$, assuming statistical isotropy.

Estimating $\zeta$ via \eqref{eq: NPCF-estimator-full} na\"ively requires simultaneous consideration of $N$ copies of $\delta$. This point is evident if one assumes $\delta$ to formed of a discrete set of $n$ positions, $\{\bvec x^j\}$:
\begin{eqnarray}\label{eq: discrete-delta}
    \delta(\bvec r) = \sum_{j=1}^n w^j\delta_{\rm D}(\bvec r-\bvec x^j)
\end{eqnarray}
allowing for arbitrary weights $\{w^j\}$ with $\bvec x^j\in \mathbb{Q}^D, w^j\in\mathbb{C}$ and utilizing the Dirac delta function $\delta_{\rm D}$. Inserting \eqref{eq: discrete-delta} into \eqref{eq: NPCF-estimator-full} leads to the discrete estimator
\begin{eqnarray}\label{eq: NPCF-estimator-discrete-naive}
    \hat\zeta(\bvec r^1,\ldots,\bvec r^{N-1}) &=& \frac{1}{n}\sum_{j=1}^n w^j\left[\delta(\bvec x^j+\bvec r^1)\ldots\delta(\bvec x^j+\bvec r^{N-1})\right]\\\nonumber
    &=& \frac{1}{n^N}\sum_{j=1}^n\sum_{k_1=1}^n\ldots\sum_{k_{N-1}=1}^n w^jw^{k_1}\ldots w^{k_{D-1}}\left[\delta_{\rm D}(\bvec r^1+\bvec x^j-\bvec x^{k_1})\ldots \delta_{\rm D}(\bvec r^{D-1}+\bvec x^j-\bvec x^{k_{D-1}})\right],
\end{eqnarray}
expanding all density fields via \eqref{eq: discrete-delta} in the second line. \eqref{eq: NPCF-estimator-discrete-naive} is a sum over $n^N$ points in $\mathbb{Q}^D$, with the Dirac delta functions enforcing constraints such as $\bvec x^j-\bvec x^{k-1} = \bvec r^1$. Importantly, this algorithm has complexity $\mathcal{O}(n^N)$, which is infeasible for large $n$.\footnote{Our discussion applies similarly to continuous data discretized onto some grid. Thence, $n$ is replaced by the total number of grid points in $\mathbb{Q}^D$.} In the remainder of this article, we explore how basis decompositions can be used to rewrite \eqref{eq: NPCF-estimator-full} into a form whose implementation has $\mathcal{O}(n^2)$ complexity.

\section{Constructing a Basis in $D$ Dimensions}\label{sec: metric-space}

\oliver{could add some diagram as in Frye+12}

\subsection{Constant-Curvature Metric}
To simplify the NPCF estimator of \eqref{eq: NPCF-estimator-full}, we first consider the form of the underlying manifold $\mathbb{Q}^D$. As above, we assume the space to be (a) homogeneous, and (b) isotropic, leading to the well-known spatial metric \citep[e.g.,][]{1990MNRAS.247...57C}
\begin{eqnarray}\label{eq: metric}
    d\Sigma^2_{\mathbb{Q}^D}  =  dr^2+\chi_k^2(r)\left[d\theta_1^2+\sin^2\theta_1\left(d\theta_2^2+\cdots\right)\right],
\end{eqnarray}
adopting hyperspherical coordinates $\bvec r\equiv\{r,\theta_1,\ldots,\theta_{D-1}\}$. In this parametrization, $r$ is a radial coordinate, whilst $\{\theta_i\}$ are angular variables, with $\theta_1\in[0,2\pi)$ and $\theta_j\in[0,\pi)$ for $j>1$. \eqref{eq: metric} is a \textit{constant-curvature} metric, specified by the curvature parameter $k$, which determines $\chi^2_k(r)$: \oliver{too many words?}
\begin{eqnarray}
    \chi_k^2(r) = \begin{cases} \frac{1}{\sqrt{k}}\sin \left(r\sqrt{k}\right), & k > 0\\ \,r, & k = 0 \\ \frac{1}{\sqrt{|k|}}\sinh \left(r\sqrt{|k|}\right), & k<0. \end{cases}
\end{eqnarray}

Three types of spaces are encoded by \eqref{eq: metric} depending on the sign of $k$. For $k>0$, we obtain the $D$-sphere, $\mathbb{S}^D$, whilst $k<0$ gives the hyperbolic geometry $\mathbb{H}^D$.\oliver{shorten this!} Finally, a space of zero curvature is simply the Euclidean geometry $\mathbb{R}^D$. In fact, these are the only three metric spaces allowed by the assumptions of homogeneity and isotropy in $D$ dimensions. Manifolds of these types are ubiquitous in the physical sciences. For instance, with the addition of a time coordinate, this describes the Friedmann-Lema\^itre-Robertson-Walker metric of a curved expanding Universe \citep{1984ucp..book.....W}.

\subsection{Harmonic Basis}
A convenient basis for the constant-curvature space $\mathbb{Q}^D$ is that of the \textit{harmonic} functions. These satisfy
\begin{eqnarray}\label{eq: laplace-bertrami-eq}
    f: \mathbb{Q}^D \to \mathbb{C}, \quad \Delta f(\bvec r) \equiv \nabla \cdot \nabla f(\bvec r) = 0
\end{eqnarray}
for Laplace-Bertrami operator $\Delta$ and twice continuously differentiable $f$. \eqref{eq: laplace-bertrami-eq} is the analog of the Laplace equation for a general (pseudo-)Riemannian manifold, and can be written explicitly in terms of the \oliver{don't need to specify spatial} spatial metric $g$:
\begin{eqnarray}
    \Delta f(\bvec r) = \frac{1}{\sqrt{|g|}}\partial_i \left(\sqrt{|g|}\;g^{ij}\partial_j f\right) = 0,
\end{eqnarray}
where $|g| \equiv \mathrm{det}\left(g_{ij}\right)$ is the determinant of the metric and $\partial_i \equiv \partial / \partial r^i$ \oliver{$i = 1,...,D$ here, also this is unclear wrt length $r$, use $x$?}. With the metric of \eqref{eq: metric}, we obtain \oliver{note how we do this}
\begin{eqnarray}
    \frac{1}{\chi_k^{D-1}(r)}\partial_r \left(\chi^{D-1}_k(r)\partial_rf(\bvec r)\right) + \frac{1}{\chi_k^2(r)\sin^{D-2}\theta_1}\partial_{\theta_1}\left(\sin^{D-2}\theta_1\,\partial_{\theta_1}f(\bvec r)\right)+\cdots +  \frac{1}{\chi_k^{2}(r)\sin^{2}\theta_1\cdots \sin^{2}\theta_{D-2}}\partial_{\theta_{D-1}}^2f(\bvec r) = 0
\end{eqnarray}
noting that $\sqrt{|g|} = \chi_k^{D-1}(r)\,\sin^{D-2}\theta_1\,\ldots\sin\theta_{D-2}$. If one assumes a separable eigenfunction $f(\bvec r) = R(r)Y(\hat{\bvec r})$ (using the notation $\hat{\bvec r} \equiv \{\theta_1,\ldots,\theta_{D-1}\}$), we require
\begin{eqnarray}\label{eq: eigenfunction-eqns}
    \chi_k^{3-D}(r)\partial_r \left(\chi^{D-1}_k(r)\partial_r R(r)\right) &=& \lambda R(r),\\\nonumber
    \frac{1}{\sin^{D-2}\theta_1}\partial_{\theta_1}\left(\sin^{D-2}\theta_1\,\partial_{\theta_1}Y(\hat{\bvec r})\right)+\cdots +  \frac{1}{\sin^2\theta_1\cdots \sin^{2}\theta_{D-2}}\partial_{\theta_{D-1}}^2Y(\hat{\bvec r}) &=& -\lambda Y(\hat{\bvec r})
\end{eqnarray}
for constant $\lambda\in\mathbb{C}$. The second line above can be written as an eigenfunction equation:
\begin{eqnarray}\label{eq: eigenfunction-S-D-1}
    \Delta_{\mathbb{S}^{D-1}}Y(\hat{\bvec r}) = -\lambda Y(\hat{\bvec r}),
\end{eqnarray}
where $\Delta_{\mathbb{S}^{D-1}}$ is the Laplace-Bertrami operator on the $(D-1)$-sphere. The corresponding solutions $Y(\hat{\bvec r})$ are the \textit{hyperspherical harmonics} on $\mathbb{S}^{D-1}$ \citep[e.g.,][]{cohl2011,2012arXiv1205.3548F}. \oliver{looks like we've already solved the equation here. Too much repetition with the below.}

The meaning of \eqref{eq: eigenfunction-S-D-1} is straightforward; \textbf{the angular parts of the harmonic basis functions on $\mathbb{Q}^{D}$ are the harmonic functions on $\mathbb{S}^{D-1}$}, \textit{regardless} of the spatial curvature $k$. Curvature acts only the radial coordinate $r$, through the function $\chi^2_k(r)$ appearing in the metric of \eqref{eq: metric}. This may be additionally seen by noting that \eqref{eq: metric} can be written $d\Sigma^2_D = dr^2 + \chi_k^2(r)d\Omega_{D-1}^2$, where $d\Omega_{D-1}^2$ is the $(D-1)$-sphere metric. Physically, this occurs since we have assumed the metric to be homogeneous and isotropic, such that it is invariant under $SO(D-1)$ rotations about any point.

\subsection{Hyperspherical Harmonics}
We now consider the angular basis functions $Y(\hat{\bvec r})$ (which solve \eqref{eq: eigenfunction-S-D-1}) in more detail. To facilitate this, we first note that the Laplace-Bertrami operator on the $K$-sphere $\mathbb{S}^K$ may be written in terms of that on the $(K-1)$-sphere:
\begin{eqnarray}\label{eq: laplace-bertrami-sph}
    \Delta_{\mathbb{S}^{K}}Y(\hat{\bvec r}) = \sin^{1-K}\theta_{K}\,\frac{\partial}{\partial \theta_{K}}\left(\sin^{K-1}\theta_{K}\frac{\partial Y(\hat{\bvec r})}{\partial \theta_{K}}\right)+\sin^{-2}\theta_{K}\,\Delta_{\mathbb{S}^{K-1}}Y(\hat{\bvec r})
\end{eqnarray}
\oliver{this equation is very similar to the previous and the below, can we omit some of them?}
where $\mathbb{S}^{K}$ is parametrized by $\{\theta_1,\ldots,\theta_{K}\}$. \eqref{eq: eigenfunction-S-D-1} can then be solved iteratively, by assuming $Y{(K-1)}$ to be valid, then inserting into \eqref{eq: laplace-bertrami-sph} to find the next order solution. This leads to
\begin{eqnarray}\label{eq: hypersph-eqn}
    &&Y^{(K)}(\theta_1,\ldots,\theta_{K}) = \Theta_{K}(\theta_{K})Y^{(K-1)}(\theta_1,\ldots,\theta_{K-1}),\\\nonumber
    &&\sin^{1-K}\theta_{K}\,\frac{\partial}{\partial \theta_{K}}\left(\sin^{K-1}\theta_{K}\,\frac{\partial \Theta_{K}(\theta_{K})}{\partial \theta_{K}}\right)-\lambda_{K-1}\sin^{-2}\theta_{K}\,\Theta_{K}(\theta_{K}) = - \lambda_{K}\Theta_K(\theta_K),
\end{eqnarray}
writing the eigenvalue for the $K$-sphere as $\lambda_{K}$. To close the hierarchy, we require the basis functions on the $1$-sphere:
\begin{eqnarray}\label{eq: 1-sphere-basis}
    \frac{\partial^2 \Theta_1(\theta_1)}{\partial \theta_{1}^2} &=& - \lambda_{1}\Theta_1(\theta_1) \quad \Rightarrow \quad \Theta_1(\theta_1) = \frac{1}{\sqrt{2\pi}}e^{-i\ell_1\theta_1}
\end{eqnarray}
setting $\lambda_1 = \ell_1^2$ with $\ell_1\in\mathbb{Z}$ enforced by recalling that $\Theta_1$ must be invariant under $\theta_1\to\theta_1+2\pi$. The higher-order functions are obtained by solving the Sturm-Liouville problem in \eqref{eq: hypersph-eqn}, which can be written in terms of the general Legendre equation \citep{higuchi1987}. Our desired solution for the $(D-1)$-sphere basis functions $Y(\bvec r)$ becomes:
\begin{empheq}[box=\fbox]{align}\label{eq: hypersph-def}
    Y_{\ell_1\ldots\ell_{D-1}}(\theta_1, \ldots,\theta_{D-1}) &\equiv \Theta_1(\theta_1)\times\Theta_2(\theta_2)\times\cdots\times\Theta_{D-1}(\theta_{D-1}),\\\nonumber
    \Theta_K(\theta_K) &= \sqrt{\frac{2\ell_K+K-1}{2}\frac{(\ell_K+\ell_{K-1}+K-2)!}{(\ell_K-\ell_{K-1})!}}\sin^{1-K/2}\theta_K\,P_{\ell_K-1+K/2}^{-(\ell_{K-1}-1+K/2)}\left(\cos\theta_{K}\right),
\end{empheq}
for $K\in\{2,\ldots,D-1\}$, where $P_L^M(x)$ is an associated Legendre polynomial \citep[e.g., ][\S14.3]{nist_dlmf}. The basis functions of \eqref{eq: hypersph-def} are specified by a set of $(D-1)$ integers, $\{\ell_1,\ldots,\ell_{D-1}\}$, which satisfy:
\begin{eqnarray}
    -\ell_2 \leq \ell_1 \leq \ell_2 \quad \ell_{k-1} \leq \ell_{k} \leq \ell_{k+1} \quad (k>1),
\end{eqnarray}
and are related to $\lambda_K$ by $\lambda_K = -\ell_K(\ell_K+K-1)$. \oliver{this sentence seems out of place - do we discuss ang mom here?} The integers $\ell_K$ describe the angular momentum of the state $Y_{\ell_1\ldots\ell_{D-1}}$, as discussed below.\oliver{explain more of what ell, m actually mean in 3D}

\oliver{add connection to ang. mom. before properties?} A number of properties are of note \citep{higuchi1987,cohl2011,2012arXiv1205.3548F}. Firstly, the basis functions are orthonormal according to the inner product $\left(u,v\right) = \int_{\mathbb{S}^{D-1}}d\Omega_{D-1}u^*(\hat{\bvec r})v(\hat{\bvec r})$, such that
\begin{eqnarray}
    \left(Y_{\ell_1^{}\ldots\ell^{}_{D-1}},Y_{\ell_1'\ldots\ell'_{D-1}}\right) = \delta^{\rm K}_{\ell_1^{}\ell_1'}\times \cdots\times\delta^{\rm K}_{\ell_{D-1}^{}\ell_{D-1}'}
\end{eqnarray}
where the Kronecker delta $\delta^{\rm K}_{ij}$ is unity if $i=j$ and zero otherwise. Secondly, the hyperspherical harmonics form a complete basis on $\mathbb{S}^{D-1}$, such that, for any $h:\mathbb{S}^{D-1}\to\mathbb{C}$
\begin{eqnarray}
    h(\hat{\bvec r}) = \sum_{\ell_{D-1}=0}^\infty \sum_{\ell_{D-2}=0}^{\ell_{D-1}}\ldots\sum_{\ell_2=0}^{\ell_3}\sum_{\ell_1=-\ell_2}^{\ell_2}h_{\ell_1\ldots\ell_{D-1}}Y_{\ell_1\ldots\ell_{D-1}}(\hat{\bvec r}),
\end{eqnarray}
\oliver{need to discuss why we get the telescoping structure of $\ell$; maybe we need to mention angular momentum earlier}
where the harmonic coefficients are defined as $h_{\ell_1}\ldots\ell_{D-1} \equiv \left(Y_{\ell_1\ldots\ell_{D-1}},h\right)$. Under complex conjugation, we obtain
\begin{eqnarray}\label{eq: complex-conj-hypersph}
    Y_{\ell_1\ell_2\ldots\ell_{D-1}}^*(\hat{\bvec r}) = (-1)^{\ell_1}Y_{(-\ell_1)\ell_2\ldots\ell_{D-1}}.
\end{eqnarray}
Parity inversion, denoted by $\mathbb{P}$, sends $\bvec r\to-\bvec r$ and thus $\theta_1\to\pi+\theta_1$, $\theta_k\to\pi-\theta_k$ for $k>1$. Its action on the hyperspherical harmonics is given by
\begin{eqnarray}\label{eq: parity-hypersph}
    \mathbb{P}\left[Y_{\ell_1\ldots\ell_{D-1}}(\hat{\bvec r})\right] = (-1)^{\ell_{D-1}}Y_{\ell_1\ldots\ell_{D-1}}(\hat{\bvec r}),
\end{eqnarray}
verifiable by noting that $\mathbb{P}[\Theta_1(\theta_1)]=(-1)^{\ell_1}\Theta_1(\theta_1)$ and $\mathbb{P}[\Theta_{K}(\theta_K)] = (-1)^{\ell_K-\ell_{K-1}}$.

Finally, we give the explicit forms of the hyperspherical harmonics for $D=2$, $3$ and $4$, which are respectively complete bases for $\mathbb{S}^1$, $\mathbb{S}^2$ and $\mathbb{S}^3$:
\begin{eqnarray}
    (D=2) & \quad Y_{\ell_1}(\theta_1) &= \frac{1}{\sqrt{2\pi}}e^{i\ell_1\theta_1},\\\nonumber
    (D=3) & \quad Y_{\ell_1\ell_2}(\theta_1,\theta_2) &= \sqrt{\frac{2\ell_2+1}{4\pi}\frac{(\ell_2+\ell_1)!}{(\ell_2-\ell_1)!}}e^{i\ell_1\theta_1}P_{\ell_2}^{-\ell_1}(\cos\theta_2),\\\nonumber
    (D=4) & \quad Y_{\ell_1\ell_2\ell_3}(\theta_1,\theta_2,\theta_3) &= \sqrt{\frac{(2\ell_2+1)(2\ell_3+2)}{8\pi}\frac{(\ell_2+\ell_1)!}{(\ell_2-\ell_1)!}\frac{(\ell_3+\ell_2+1)!}{(\ell_3-\ell_2)!}}e^{i\ell_1\theta_1}P_{\ell_2}^{-\ell_1}(\cos\theta_2)\sin^{1/2}\theta_3\,P^{-(\ell_2+1/2)}_{\ell_3+1/2}(\cos\theta_3)
\end{eqnarray}
with the $D=4$ case matching \citep{Akhoon2014}. The $D=3$ functions are just the usual spherical harmonics, made clear by the identification $(\ell_1,\ell_2)\to(m,\ell)$, $(\theta_1,\theta_2)\to(\phi,\theta)$, with$\phi$ the azimuthal angle.

\subsection{Connection to Angular Momentum in $D$ Dimensions}
The basis functions discussed above can also be seen as arising from the theory of orbital angular momentum in $D$-dimensional space. This formalism will allow construction of the $N$-point basis functions \oliver{make clear these are different from what we have?} in \S\ref{sec: iso-basis}, thus we briefly outline it below.

Consider the space $\mathbb{R}^{D}$, in which the $(D-1)$-sphere can be embedded. As in \cite{louck1960}, we define the generalized angular momentum operators
\begin{eqnarray}
    \widehat{L}_{ij} = x_ip_j - x_jp_i \quad i\neq j \in \{1,2,\ldots, D\}
\end{eqnarray}
where $\{x_1,\ldots,x_D\}$ is a Cartesian coordinate chart and $p_j = -i(\partial/\partial x^j)$ is the linear momentum operator. Noting that $\widehat{L}_{ij} = -\widehat{L}_{ji}$, these operators form the Lie algebra $\mathfrak{so}(D)$, which is just the algebra of the rotation group in $D$ dimensions. Considering the subspace $\mathbb{R}^3\subset\mathbb{R}^D$ defined by $\{x_1,x_2,x_3\}$, the expectation value of $\widehat{L}_{12}$ gives the angular momentum contribution along the $x_3$ axis. We additionally define \oliver{this is confusing}
\begin{eqnarray}
    \widehat{L}^2_{K} \equiv \sum_{i=1}^{K}\sum_{j=i+1}^K\widehat{L}^2_{ij}
\end{eqnarray}
for $K\leq D$ \oliver{explain lower bound for this - clarify what we're summing over}. The expectation value of $\widehat{L}^2_K$ yields the angular momentum projected onto the subspace $\mathbb{R}^K$ defined by $\{x_1,\ldots,x_K\}$. In particular, $\widehat{L}^2_{D}$ is the total angular momentum operator.\oliver{does this notation work? $L_3$ $3$ is very different to $12$ in $L_{12}$}

Much as the spherical harmonics in $D=3$ are simultaneous eigenfunctions of $\widehat{L}_{12}$ and $\widehat{L}_3^2 \equiv \widehat{L}_{12}^2+\widehat{L}_{13}^2+\widehat{L}_{23}^2$ \oliver{need brackets round these}, the hyperspherical harmonic functions of \eqref{eq: hypersph-def} are simultaneous eigenfunctions of $\widehat{L}_{12}$, $\widehat{L}^2_3$, $\widehat{L}^2_4,\ldots,\widehat{L}^2_{D}$.\oliver{mention that $L_{12}$ refers to coordinate axis explicitly, and what $L^2_4$ etc. refer to}\footnote{We refer the reader to \cite{louck1960} for an in-depth treatment of the theory of angular momentum in $D$ dimensions.} This occurs since the Laplace-Bertrami operator (Eq.\,\ref{eq: laplace-bertrami-sph}) specifying the angular basis functions is related to the total angular momentum operator by $\Delta_{\mathbb{S}^{D-1}} = -\widehat{L}_D^2$.\oliver{does this actually give the forms for the subspace ells etc.} The integers $\{\ell_i\}$ specifying the basis functions are the eigenvalues of the angular momentum operators:
\begin{eqnarray}\label{eq: single-particle-eigenfun}
    \widehat{L}_{12} Y_{\ell_1\ldots\ell_{D-1}}(\hat{\bvec r}) &=& \ell_1\,Y_{\ell_1\ldots\ell_{D-1}}(\hat{\bvec r}), \\\nonumber
    \widehat{L}^2_{K} Y_{\ell_1\ldots\ell_{D-1}}(\hat{\bvec r}) &=& \ell_{K-1}(\ell_{K-1}+K-2)\,Y_{\ell_1\ldots\ell_{D-1}}(\hat{\bvec r}) \quad (3\leq K\leq D)
\end{eqnarray}
\citep[Ch.\,3]{louck1960}. The first eigenvalue, $\ell_1$, is the analog of the $z$-component of angular momentum in $\mathbb{R}^3$, whilst all higher eigenvalues specify the total angular momentum in a subspace $\mathbb{R}^K$. The last eigenvalue is of particular importance since it specifies the total angular momentum $\ell_{D-1}(\ell_{D-1}+D-2)$, \textit{i.e.} the expectation value of $\widehat{L}^2_D$. In total, there are
\begin{eqnarray}
    \begin{cases}1 & D=3\\\nonumber
    \frac{2\ell_{D-1}+D-2}{D-2}\binom{\ell_{D-1}+D-3}{D-3} & D>3 \end{cases}
\end{eqnarray}
states for $D\geq 3$ corresponding to a given total angular momentum $\ell_{D-1}$ \citep[Eq.\,3.37]{louck1960}. \oliver{note that we only project onto one 3D space etc.}

Given the above relation, we introduce abstract notation for the angular momentum basis functions $Y_{\ell_1\ldots\ell_{D-1}}(\hat{\bvec r})$. In Dirac (or bra-ket) notation, an angular momentum state is labelled by a set of integers, such that
\begin{eqnarray}
    Y_{\ell_1\ldots\ell_{D-1}} \to \ket{\ell_1\ldots\ell_{D-1}}
\end{eqnarray}
with the inner product becoming
\begin{eqnarray}
    \int_{\mathbb{S}^{D-1}}d\Omega_{D-1}Y^*_{\ell_1\ldots\ell_{D-1}}(\hat{\bvec r})Y_{\ell_1'\ldots\ell_{D-1}'}(\hat{\bvec r}') \quad \leftrightarrow \quad  \left\langle\left.\ell^{}_1\ldots\ell^{}_{D-1}\right|\ell'_1\ldots\ell'_{D-1}\right\rangle.
\end{eqnarray}
The Hilbert space of hyperspherical harmonic functions in $D$ dimensions forms an infinite-dimensional representation of the rotation group $SO(D)$. The eigenvalue $\ell_{D-1}$ represents the behavior in $SO(D)$, whilst the values of $\ell_K$ with $K<D-1$ specify the rotation's action in the lower dimensional subgroups $SO(K)$.\footnote{Specifically, $\ell_1$ gives the rotation about the $x^3$ axis, $\ell_2$ gives the rotation projected onto the subspace described by $\{x_1,x_2,x_3\}$, $\ell_3$ gives that of the $\{x_1,x_2,x_3,x_4\}$ subspace \textit{et cetera.}} This is sufficient to fully specify the orbital angular momentum state.

\section{Isotropic Basis Functions of $(N-1)$ Positions}\label{sec: iso-basis}
In \S\ref{sec: metric-space} we have provided a detailed discussion of the hyperspherical harmonic functions which form a basis for the angular part of a single-variable function in the homogeneous and isotropic space of interest, $\mathbb{Q}^D$.\oliver{shorten the preceeding} We now generalize this to functions of $(N-1)$ positions, \textit{i.e.} $f:\mathbb{Q}^D\otimes\mathbb{Q}^D\otimes\cdots\otimes\mathbb{Q}^D\to\mathbb{C}$. This allows construction of a set of basis functions of definite combined angular momentum which will be used in \S\ref{sec: NPCF-estimator}.

\subsection{Addition of Angular Momentum}\label{subsec: ang-mom-add}
We begin by considering the combination of two angular basis functions on the $(D-1)$-sphere. \oliver{probably can use the word particle consistently} Our building block is the product state
\begin{eqnarray}\label{eq: product-state-N=3}
    \ket{\vec{\ell}^1}\ket{\vec{\ell}^2} \quad \leftrightarrow \quad Y_{\vec{\ell}^1}(\bvec r^1)Y_{\vec{\ell}^2}(\bvec r^2)
\end{eqnarray}
in the Dirac and wavefunction representations, defining $\vec{\ell}\equiv\{\ell_1\ldots\ell_{D-1}\}$ for brevity and using superindices to distinguish between positions. The product state exists in the space $\mathbb{S}^{D-1}\otimes\mathbb{S}^{D-1}$ and is a simultaneous eigenstate of angular momentum operators constructed from $\widehat{L}_{ij}^{(1)} \equiv \widehat{L}_{ij}\otimes 1$ and $\widehat{L}_{ij}^{(2)}\equiv 1\otimes \widehat{L}_{ij}$ where $1$ is the identity operator.\oliver{make clear that (1) + (2) are particle numbers} We may additionally define an operator corresponding to the \textit{combined} angular momentum in the product space; this is given by
\begin{eqnarray}\label{eq: combined-ang-mom}
    \widehat{\bvec L}_{ij} \equiv \widehat{L}^{(1)}_{ij} +  \widehat{L}^{(2)}_{ij}.
\end{eqnarray}
As in \S\ref{sec: metric-space}, the tensorial operator above may be used to define the total angular momentum operator, $\widehat{\bvec L}^2_{D}$ as well as its lower-dimensional equivalents $\widehat{\bvec L}^2_K$ and $\widehat{\bvec L}_{12}$. The latter gives the angular momentum in the $\mathbb{R}^3\times\mathbb{R}^3$ subspace projected onto the $(x_3^1, x_3^2)$ axes. In general, the product state \eqref{eq: product-state-N=3} is \textit{not} an eigenvector of the angular momentum operators constructed from $\widehat{\bvec L}_{ij}$; it is thus \textit{not} a state of definite combined angular momentum.\oliver{probably better to go straight to the combined ang mom states} Given that the angular momenta of states $1$ and $2$ are quantized and $\widehat{\bvec L}_{ij}$ is linear in the two particles, states of definite combined angular momentum must exist.

A general two-particle state on $\mathbb{S}^{D-1}\otimes\mathbb{S}^{D-1}$ can be constructed as a sum of product states:
\begin{eqnarray}
    \sum_{\ell^{}_1\ldots\ell^{}_{D-2}}\sum_{\ell^1_1\ldots\ell^2_{D-2}}A_{\vec{\ell},\vec{\ell}^1}\ket{\vec{\ell}^1}\ket{\vec{\ell}^2}
\end{eqnarray}
for some set of coefficients $A_{\vec{\ell}^1,\vec{\ell}^2}$ and angular momentum coefficients $\vec{\ell}^1$ and $\vec{\ell}^2$ or the two particles. Note that we do \textit{not} sum over $\ell^1_{D-1}$ or $\ell^2_{D-1}$, \textit{i.e.} we keep the total angular momentum of each particle fixed, but allow its projections onto the lower-dimensional subspaces, $\mathbb{S}^{K}$ with $K<D-1$, to vary.\oliver{the preceding is an important point and should be stressed} The states of definite combined angular momentum can be written in this form; denoting the combined angular momentum quantum numbers by $\vec{L} \equiv \{L_1\ldots L_{D-1}\}$, we obtain
\begin{eqnarray}\label{eq: ang-mom-add-N=3}
    \boxed{\ket{\ell_{D-1}^{1}\ell_{D-1}^2;\vec{L}} = \sum_{\ell_1^{1}\ldots\ell^{1}_{D-2}}\sum_{\ell_2^2\ldots\ell^2_{D-2}}\cg{\vec{\ell}^1}{\vec{\ell}^2}{\vec{L}} \ket{\vec{\ell}^1}\ket{\vec{\ell}^2},}
\end{eqnarray}
where the coupling coefficients are given by (real) \textit{Clebsch-Gordan} coefficients, $\cg{\vec{\ell}^1}{\vec{\ell}^2}{\vec{L}}$, and the total angular momentum eigenvalues $\ell^{1}_{D-1}$ and $\ell^2_{D-1}$ are needed to uniquely define the state. By construction, the combined state in \eqref{eq: ang-mom-add-N=3} is an eigenfunction of the combined angular momentum operators, as in \eqref{eq: single-particle-eigenfun}, with $\widehat{L}\to\widehat{\bvec L}$ and $\ell\to L$.
The form of the combined angular momentum operator in \eqref{eq: combined-ang-mom} places constraints on the allowed values of $\vec{\ell}^1$ and $\vec{\ell}^2$: in particular,
\begin{eqnarray}\label{eq: addition-triangle-conditions}
    L_1 = \ell^{1}_1 + \ell^2_1, \quad |\ell^{1}_k-\ell^2_k|\leq L_k \leq \ell^{1}_k+\ell^2_k
\end{eqnarray}
for $2\leq k \leq D-1$. The first constraint occurs since $L_1$ is the eigenvector of $\widehat{\bvec L}_{12}$, which is linear in $\widehat{L}_{12}^{(1)}$ and $\widehat{L}_{12}^{(2)}$, and the second is true via the triangle inequality, recalling that $L_K$ corresponds to the angular momentum projected into the subspace $\mathbb{R}^{K}$.

A crucial piece of \eqref{eq: ang-mom-add-N=3} are the Clebsch-Gordan coefficients $\cg{\vec{\ell}^1}{\vec{\ell}^2}{\vec{L}}$, which are here those of the $SO(D)\supset SO(D-1)\supset \cdots\supset SO(2)$ reduction. These have been studied in depth \citep[e.g.,][]{biedenharn1961,1988qtam.book.....V,VanIsacker1991,Louck2006,2010JMP....51i3518C} and may be simplified by techniques such as Racah's factorization lemma \citep{Racah1965}. One route to their computation is via \eqref{eq: ang-mom-add-N=3}; starting from a state of maximal angular momentum
\begin{eqnarray}
    \ket{\ell_{D-1}^{1}\ell_{D-1}^2;\vec{\ell}^1+\vec{\ell}^2} = \ket{\vec{\ell}^1 }\ket{\vec{\ell}^2}
\end{eqnarray}
(whence the two angular momentum vectors in $\mathbb{R}^{D}$ are aligned), ladder operators may be applied iteratively to obtain states of lower angular momentum, whose coefficients give the Clebsch-Gordan coefficients. Aside from enforcing the triangle conditions in \eqref{eq: addition-triangle-conditions}, the Clebsch-Gordan coefficients must satisfy certain orthogonality conditions, including
\begin{eqnarray}\label{eq: CG-orthonorm}
    \sum_{\ell^{1}_1\ldots\ell_{D-2}^{1}}\sum_{\ell^2_1\ldots\ell^2_{D-2}}\cg{\vec{\ell}^1}{\vec{\ell}^2}{\vec{L}}\cg{\vec{\ell}^1}{\vec{\ell}^2}{\vec{L}'} = \delta^{\rm K}_{L_1^{}L_1'}\times \cdots\times \delta^{\rm K}_{L_{D-1}^{}L_{D-1}'}.
\end{eqnarray}
Coupled with the orthonormality of the one-particle states $\ket{\vec{\ell}}$, \eqref{eq: CG-orthonorm} ensures that the combined angular momentum basis is orthonormal, \textit{i.e.}
\begin{eqnarray}
    \braket{\vec{L}';l^1_{D-1} l^2_{D-1}}{\ell^1_{D-1}\ell_{D-1}^2;\vec{L}} = \delta^{\rm K}_{L^{}_1L_1'}\times\cdots\times\delta^{\rm K}_{L^{}_{D-1}L'_{D-1}}\times\delta^{\rm K}_{\ell^1_{D-1}l^1_{D-1}\delta^{\rm K}_{\ell_{D-1}^2l_{D-1}^2}
\end{eqnarray}
Finally, we give the explicit forms of the Clebsch-Gordan coefficients for $D\in\{2,3,4\}$:
\begin{eqnarray}\label{eq: CG-examples}
    (D=2) &\quad \cg{\ell^1}{\ell^2}{L} &= \delta^{\rm K}_{(\ell^1+\ell^2)L},
    \\\nonumber
    (D=3) &\quad \cg{\ell^1_1\ell^1_2}{\ell_1^2\ell_2^2}{L_1L_2} &= (-1)^{-\ell_2^1+\ell_2^2-L_1}\sqrt{2L_2+1} \tj{\ell_2^1}{\ell_2^2}{L_2}{\ell_1^1}{\ell_1^2}{-L_1}\\\nonumber
    (D=4) &\quad \cg{\ell_1^1\ell_2^1\ell_3^1}{\ell_1^2\ell_2^2\ell_3^2}{L_1L_2L_3} &= (-1)^{-\ell^1_2+\ell^2_2-L_1}(L_3+1)\sqrt{(2\ell^1_2+1)(2\ell^2_2+1)(2L_2+1)},\\\nonumber
    &&\,\times\,\tj{\ell_2^1}{\ell_2^2}{L_2}{\ell_1^1}{\ell_1^2}{-L_1}\begin{Bmatrix}\ell_3/2^1 & \ell_3^2/2 & L_3/2\\ \ell_3^1/2 & \ell_3^2/2 & L_3/2 \\ \ell_2^1 & \ell_2^2 & L_2\end{Bmatrix},
\end{eqnarray}
where the $2\times 3$ and $3\times 3$ matrices are respectively Wigner 3-$j$ and 9-$j$ symbols \citep[e.g.,][\S34]{nist_dlmf}. The $D=3$ should be familiar from any standard angular momentum text \citep[e.g.,][]{1988qtam.book.....V,Louck2006}, and the results for $D=4$ are given in \citep{biedenharn1961,VanIsacker1991,2006JPhA...39.3099M}.\footnote{Note that the Clebsch-Gordan coefficients for $D=4$ can be written in terms of the $D=3$ Wigner 3-$j$ and 9-$j$ symbols; the former is true via Racah's factorization lemma, and the latter occurs since $SO(4)$ is a double cover of $SO(3)\times SO(3)$ \citep{VanIsacker1991}. Further, note that the $D=4$ coefficients are non-zero only if $\ell_2^1+\ell_2^2+L_2$ is even.}

\subsection{Total Angular Momentum States}
Given the single-particle basis functions of \S\ref{sec: metric-space} and the rules for combining basis functions of \S\ref{sec: iso-basis}\ref{subsec: ang-mom-add}, we may construct basis functions involving $(N-1)$ positions. As before, we start with the product of $(N-1)$ basis states in $D$ dimensions:
\begin{eqnarray}
    \ket{\vec{\ell}^1}\ket{\vec{\ell}^2}\ldots\ket{\vec{\ell}^{N-1}},
\end{eqnarray}
using superindices to denote the different basis states, as before. We build up a state of definite combined angular momentum by applying \eqref{eq: ang-mom-add-N=3} $(N-2)$ times:
\begin{eqnarray}\label{eq: ang-mom-addition-N-1-times}
    \ket{\ell^1_{D-1}\ell_{D-1}^2;\vec{\ell}^{12}} &=& \sum_{\ell^1,\ell^2}\cg{\vec{\ell}^1}{\vec{\ell}^2}{\vec{\ell}^{12}}\ket{\vec{\ell}^1}\ket{\vec{\ell}^2},\\\nonumber
    \ket{\ell^1_{D-1}\ell_{D-1}^2\ell_{D-1}^{12}\ell_{D-1}^{3};\vec{\ell}^{123}} &=& \sum_{\ell^1,\ell^2,\ell^3}\sum_{\ell^{12}}\cg{\vec{\ell}^1}{\vec{\ell}^2}{\vec{\ell}^{12}}\cg{\vec{\ell}^{12}}{\vec{\ell}^3}{\vec{\ell}^{123}}\ket{\vec{\ell}^1}\ket{\vec{\ell}^2}\ket{\vec{\ell}^3},\\\nonumber
    &\cdots &\\\nonumber
    \ket{\ell^1_{D-1}\ell_{D-1}^2\ell_{D-1}^{12}\ell^3_{D-1}\ldots\ell_{D-1}^{{N-1}};\vec{L}} &=& \sum_{\ell^1\ldots\ell^{{N-1}}}\sum_{\ell^{12}\ldots\ell^{12\ldots(N-2)}}\cg{\vec{\ell}^1}{\vec{\ell}^2}{\vec{\ell}^{12}}\cg{\vec{\ell}^{12}}{\vec{\ell}^3}{\vec{\ell}^{123}}\ldots\cg{\vec{\ell}^{12\ldots(N-2)}}{\vec{\ell}^{N-1}}{\vec{L}}\\\nonumber
    &&\quad\quad\,\times\,\ket{\vec{\ell}^1}\ket{\vec{\ell}^2}\ldots\ket{\vec{\ell}^{N-1}},
\end{eqnarray}
where each summation is over all components of $\ell$ except the total angular momentum $\ell_{D-1}$. Note that we sum over both primary angular momentum coefficients $\ell^{i}$ (which enter the single-particle states) and intermediates, e.g., $\ell^{12\ldots}$. In the final line, we have set $\vec{\ell}^{12\ldots (N-1)}\equiv \vec{L}$. The meaning of \eqref{eq: ang-mom-addition-N-1-times} is straightforward; we may form a combined state with eigenvalues $\vec{L}$ as a sum of product states weighted by $(N-2)$ Clebsch-Gordan coefficients. To define the combination state uniquely, we must specify not only the total angular momentum $\ell_{D-1}$ of each single-particle state, but also the total angular momentum of the intermediate states, e.g., $\ell_{D-1}^{12}$ arising from the coupling of $\ket{\vec{\ell}^1}$ and $\ket{\vec{\ell}^2}$. In total, the state is specified by $(2N-4)$ numbers alongside $\vec{L}$, which contains $(D-1)$ coefficients. Using \eqref{eq: CG-orthonorm}, the states can be shown to be orthonormal:
\begin{eqnarray}
    \braket{\vec{L}';l_{D-1}^1l_{D-1}^2l_{D-1}^{12}\ldots l_{D-1}^{N-1}}{\ell_{D-1}^1\ell_{D-1}^2\ell_{D-1}^{12}\ldots \ell_{D-1}^{N-1};\vec{L}} = \delta^{\rm K}_{L_1^{}L_1'}\ldots\delta^{\rm K}_{L_{D-1}^{}L_{D-1}'}\times \delta^{\rm K}_{\ell_{D-1}^1 l_{D-1}^1}\ldots \delta^{\rm K}_{\ell_{D-1}^{{N-1}}l_{D-1}^{{N-1}}}
\end{eqnarray}
requiring both $\vec{L} = \vec{L}'$ and equality of all total angular momenta $\ell_{D-1}$ and intermediates. Since the combined angular momentum basis is complete, \textbf{the directional dependence of any $(N-1)$-parameter function on $\mathbb{Q}^D$ can be expanded in the separable form of Eq.\,\ref{eq: ang-mom-addition-N-1-times}.}

A state of particular interest to this work is that of zero combined angular momentum, \textit{i.e.} $L_{D-1} = 0$ (and thus, by the selection rules of \eqref{eq: addition-triangle-conditions}, $\vec{L} = \vec 0$). From \eqref{eq: ang-mom-addition-N-1-times}, this can be written
\begin{eqnarray}\label{eq: zero-ang-mom-states}
    \boxed{\ket{\L;\vec{0}} = \sum_{\ell^1\ldots\ell^{{N-1}}}C^{\L}_{\vec{\ell}^1\ldots\vec{\ell}^{{N-1}}}\ket{\vec{\ell}^1}\ket{\vec{\ell}^2}\ldots\ket{\vec{\ell}^{N-1}}}
\end{eqnarray}
where we have defined $\L = \{\ell_{D-1}^1\ell_{D-1}^2\ell_{D-1}^{12}\ldots\ell_{D-1}^{{N-1}}\}$ for brevity, and written the coupling coefficients as
\begin{eqnarray}\label{eq: Coupling-C}
    \boxed{C^{\L}_{\vec{\ell}_1\ldots\vec{\ell}_{{N-1}}} = \sum_{\ell^{12}\ldots\ell^{12\ldots(N-2)}}\cg{\vec{\ell}^1}{\vec{\ell}^2}{\vec{\ell}^{12}}\cg{\vec{\ell}^{12}}{\vec{\ell}^3}{\vec{\ell}^{123}}\ldots\cg{\vec{\ell}^{12\ldots(N-2)}}{\vec{\ell}^{N-1}}{\vec 0},}
\end{eqnarray}
involving a sum over $(N-3)$ intermediate couplings $\vec l^{12\ldots}$ (with fixed $\ell^{12\ldots}_{D-1}$). Note that the final Clebsch-Gordan coefficient fixes the final intermediate angular momentum to $\ell^{12\ldots(N-2)}_1 = -\ell^{N-1}$ and $\ell^{12\ldots(N-2)}_k = \ell_k^{N-1}$ for $k>1$, thus reducing the number of independent intermediate couplings to $(N-4)$. As above, states with zero combined total angular momentum must be orthonormal, which, in the notation of \eqref{eq: zero-ang-mom-states}, leads to
\begin{eqnarray}
    \braket{\vec 0; \L}{\L'; \vec 0} = \delta^{\rm K}_{\L^{}\L'},
\end{eqnarray}
where the Kronecker symbol enforces that all elements of $\L$ and $\L'$ are equal. We further note that the formulation of \eqref{eq: zero-ang-mom-states} exactly follows that of \citep{2020arXiv201014418C} for $D=3$.

\subsection{Isotropic Basis}
\oliver{do we actually need to specify to isotropy?}
We now demonstrate the utility of the above argument. Let us consider a function $f$ defined on $(N-1)$ copies of $\mathbb{Q}^D$. Since the combined angular momentum states of \eqref{eq: ang-mom-addition-N-1-times} form a basis in the product space $\mathbb{S}^{D-1}\otimes\cdots \mathbb{S}^{D-1}$, the function can be written
\begin{eqnarray}\label{eq: general-basis-decomp}
    \ket{f} = \sum_{\vec{L}}\sum_{\L}\braket{\vec{L};\L}{f}\ket{\L;\vec{L}},
\end{eqnarray}
which is an expansion both in combined angular momentum parameters $\vec{L}$ and the possible single-particle and intermediate total angular momenta contained in $\L$. If the function is invariant under spatial rotations (as well as the underlying manifold), then the decomposition can \textit{only} involve the $\vec{L} = \vec 0$ state.
In this case, we may write \eqref{eq: general-basis-decomp} in the form of \eqref{eq: zero-ang-mom-states}
\begin{eqnarray}\label{eq: iso-basis-expansion}
    \ket{f} &=& \sum_{\L} \braket{\vec 0;\L}{f} \ket{\L;\vec 0}\\\nonumber
    f(\bvec r^1,\ldots,\bvec r^{N-1}) &=& \sum_{\L}f_{\L}^{\vec 0}(r^1,\ldots,r^{{N-1}}) \P_\L^{\vec 0}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{N-1}),
\end{eqnarray}
where we have switched to the more familiar wavefunction notation in the second line, defining the $(N-1)$-particle basis functions
\begin{eqnarray}\label{eq: iso-basis-wavenumber}
    \boxed{\P_\L^{\vec 0}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{{N-1}}) = \sum_{\ell^1\ldots\ell^{N-1}} C_{\vec{\ell}^1\ldots\vec{\ell}^{N-1}}^{\L} Y_{\vec{\ell}^1}(\hat{\bvec r}^1)\ldots Y_{\vec{\ell}^{N-1}}(\hat{\bvec r}^{N-1})}
\end{eqnarray}
in terms of the hyperspherical harmonics functions of \eqref{eq: hypersph-def}. $\ket{\L;\vec 0}$, or equivalently $\P_{\L}^{\vec 0}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{N-1})$, are the desired $(N-1)$-point \textit{isotropic basis} functions. These have several important properties: (1) they are a complete angular basis (and a Hilbert space) for rotationally-invariant $(N-1)$-point functions in $\mathbb{Q}^D$, (2) they are \textit{separable} in position vectors $\{\hat{\bvec r}^i\}$, (3) they are indexed by a finite set of integers $\L$, whose values obey triangle relations (specifically that $|\ell_{D-1}^{1\ldots (k-1)}-\ell_{D-1}^{k}|\leq \ell_{D-1}^{1\ldots k} \leq \ell_{D-1}^{1\ldots (k-1)}+\ell_{D-1}^{k}$). Under complex conjugation and parity inversion, we find
\begin{eqnarray}\label{eq: iso-basis-parity-conj}
    \P_\L^{\vec 0,*}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{{N-1}}) = (-1)^{\ell^1_{D-1}+\ldots+\ell^{N-1}_{D-1}}\P_\L^{\vec 0}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{{N-1}}) \\\nonumber
    \mathbb{P}\left[\P_\L^{\vec 0}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{{N-1}})\right] = (-1)^{\ell_{D-1}^1+\ldots+\ell_{D-1}^{{N-1}}}\P_\L^{\vec 0}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{{N-1}})
\end{eqnarray}
using \eqref{eq: complex-conj-hypersph} and \eqref{eq: parity-hypersph}, noting that the Clebsch-Gordan coefficients enforce $\ell_1^1+\ell_1^2+\cdots+\ell_1^{N-1}=L_1=0$.
Further properties for the case $D=3$ are discussed in \citep{2020arXiv201014418C}, but are not of relevance to the discussion below.

Before continuing, we give the explicit forms for the first non-trivial cases; $N=3$ and $N=4$. For $N=3$, the Clebsch-Gordan coefficient enforces $\ell_1^1 = -\ell_1^2$ and $\ell_k^1 = \ell_k^2$ for $k>1$, thus the basis functions are formed from only one set of angular momentum coefficients $\vec{\ell}_1\equiv \vec{\ell}$:
\begin{eqnarray}
    \P_{\ell_{D-1}}^{\vec 0}(\hat{\bvec r}^1,\hat{\bvec r}^2) = \sum_{\ell_1\ldots\ell_{D-2}} Y_{\ell_1\ell_2\ldots\ell_{D-1}}(\hat{\bvec r}^1)Y_{(-\ell_1)\ell_2\ldots\ell_{D-1}}(\hat{\bvec r}^2) \equiv \sum_{\ell_1\ldots\ell_{D-2}} (-1)^{\ell_1}Y_{\ell_1\ell_2\ldots\ell_{D-1}}(\hat{\bvec r}^1)Y^*_{\ell_1\ell_2\ldots\ell_{D-1}}(\hat{\bvec r}^2)
\end{eqnarray}
using the complex conjugate relation of \eqref{eq: complex-conj-hypersph}. This is a natural extension of the Legendre polynomials to $D$-dimensions; indeed the $D=3$ case recovers the Legendre polynomial $\mathcal{L}_{\ell_2}(\hat{\bvec r}^1\cdot\hat{\bvec r}^2)$ rescaled by $(-1)^{\ell_2}(4\pi)/\sqrt{2\ell_2+1}$. For $N=4$, the situation is similar:
\begin{eqnarray}
    \P_{\ell^1_{D-1}\ell^2_{D-1}\ell^3_{D-1}}^{\vec 0}(\hat{\bvec r}^1,\hat{\bvec r}^2,\hat{\bvec r}^3) = \sum_{\ell_1^1\ldots\ell^1_{D-2}}\sum_{\ell^2_1\ldots\ell^2_{D-2}}\sum_{\ell_1^3\ldots\ell^3_{D-2}}\cg{\vec{\ell}^1}{\vec{\ell}^2}{(-\ell^3_1)\ell_2^3\ldots\ell_{D-1}^3}Y_{\ell_1^1\ldots\ell^1_{D-1}}(\hat{\bvec r}^1)Y_{\ell_1^2\ldots\ell^2_{D-1}}(\hat{\bvec r}^2)Y_{\ell_1^3\ldots\ell^3_{D-1}}(\hat{\bvec r}^3).
\end{eqnarray}
This depends on a single Clebsch-Gordan coefficient (e.g., Eq.\,\ref{eq: CG-examples}) and there is no need to  an intermediate angular momentum of the form $\ell_{D-1}^{12}$.

If the function $f$, is \textit{not} invariant under joint spatial rotations, the more general decomposition of \eqref{eq: general-basis-decomp} can be used, expanding in terms of the definite combined angular momentum states $\ket{\L;\vec{L}}$, which is a complete basis. In many scenarios, we must consider functions with \textit{partial} rotational symmetry, \textit{i.e.} those invariant under the rotations drawn from $SO(K)\subset SO(D)$ with $K<D$. Defining coordinates such that the rotationally invariant subspace incorporates the first $K$ coordinates in the embedding space $\mathbb{R}^{D}$, the relevant basis functions must satisfy
\begin{eqnarray}
    \widehat{\bvec L}^2_K \ket{\L;\vec{L}} = 0 \quad \Rightarrow \quad \ell_i=0 \quad  \forall \,i < K,
\end{eqnarray}
where $\widehat{\bvec L}_{ij}$ is the combined angular momentum operator of \eqref{eq: combined-ang-mom}. In this instance, we may expand $f$ using the basis functions $\ket{\L;0\ldots 0 L_K\ldots L_{D-1}}$ and proceed as above. A typical example of this is azimuthal symmetry, whereupon $f$ is invariant under joint rotations varying only $\theta_1^i$ for $i=1,\ldots,(N-1)$.

\section{An Efficient Correlation Function Estimator}\label{sec: NPCF-estimator}
In the above sections, we have defined an angular momentum basis for $(N-1)$ points in the constant curvature space $\mathbb{Q}^D$. Armed with such a decomposition, we may proceed to the main result: an efficient estimator for the statistical correlation functions $\zeta$. We will principally consider the estimation of rotationally invariant correlators here; the approach may be generalized to states of non-zero total angular momentum, as discussed above.

\subsection{General Form}
Our starting point is the $N$-point correlation function definition of \eqref{eq: zeta-def}. Assuming invariance under joint spatial rotations (\textit{i.e.} that \eqref{eq: isotropy-NPCF} holds) the NPCF may be expanded in the basis of isotropic functions, as in \eqref{eq: iso-basis-expansion}
\begin{eqnarray}
    \boxed{\zeta(\bvec r^1,\ldots,\bvec r^{N-1}) = \sum_{\L} \zeta_\L(r^1,\ldots,r^{N-1})\P_{\L}^{\vec 0}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{N-1}),}
\end{eqnarray}
where the basis states are defined in \eqref{eq: iso-basis-wavenumber}. In this form, the NPCF is fully specified by the basis coefficients $\zeta_\L$, depending only on the radial parameters $r^i$ and the integers $\L = \{\ell_{D-1}^1\ell_{D-1}^2\ell_{D-1}^{12}\ell_{D-1}^3\ldots\ell_{D-1}^{N-1}\}$, which specify the state. Given the parity properties of the basis function (Eq.\,\ref{eq: iso-basis-parity-conj}), basis coefficients with even (odd) $\ell_{D-1}^1+\cdots+\ell_{D-1}^{N-1}$ (not including intermediates $\ell_{D-1}^{12\ldots}$ in the sum) represent even-parity (odd-parity) contributions to the NPCF. Furthermore, if the random fields $\delta$ are real-valued, even-parity contributions are purely real, whilst odd parity-contributions are purely imaginary due to the complex-conjugate properties of $\P_\L^{\vec 0}$. It can be shown that parity-odd basis functions occur only for $N>D$; for lower-point functions, a parity transformation is equivalent to a rotation, under which the basis functions are invariant.

By orthonormality, the basis coefficients can be extracted via an inner product:
\begin{eqnarray}
    \zeta_\L(r^1,\ldots,r^{N-1}) = \int_{\mathbb{S}^{D-1}\otimes\cdots\otimes\mathbb{S}^{D-1}}d\Omega_{D-1}^1\ldots d\Omega_{D-1}^{N-1}\,\left[\zeta(\bvec r_1,\ldots,\bvec r^{N-1})\P_\L^{\vec 0,*}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{N-1})\right],
\end{eqnarray}
where the integral is over $(N-1)$ copies of the angular space. Inserting the na\"ive NPCF estimator of \eqref{eq: NPCF-estimator-full} as a spatial integral over $N$ random fields $\delta$ gives
\begin{eqnarray}\label{eq: NPCF-estimator-basis-1}
    \hat\zeta_\L(r^1,\ldots,r^{N-1}) = \frac{1}{V_D}\int_{\mathbb{Q}^D} d^D\bvec s \int_{\mathbb{S}^{D-1}\otimes\cdots\otimes\mathbb{S}^{D-1}}d\Omega_{D-1}^1\ldots d\Omega_{D-1}^{N-1}\,\left[\delta(\bvec s)\delta(\bvec s+\bvec r^1)\ldots\delta(\bvec s+\bvec r^{N-1})\P_\L^{\vec 0,*}(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{N-1})\right].
\end{eqnarray}

At this point, \eqref{eq: NPCF-estimator-basis-1} certainly does not seem like a significant simplification of the na\"ive estimator of \eqref{eq: NPCF-estimator-full}. However, recalling that the angular basis functions $\P_\L^{\vec 0}$ are separable in $\hat{\bvec r}^i$, significant simplification is possible. Inserting the isotropic basis function definition of \eqref{eq: iso-basis-wavenumber} and simplifying leads to
\begin{eqnarray}\label{eq: NPCF-estimator-basis-2}
    \hat\zeta_\L(r^1,\ldots,r^{N-1}) &=& \frac{1}{V_D}\sum_{\ell^1\ldots\ell^N}\mathcal{E}(\L)C^\L_{\vec{\ell}^1\ldots\vec{\ell}^N}\int_{\mathbb{Q}^D} d^D\bvec s\,\delta(\bvec s)\left[\int_{\mathbb{S}^{D-1}}d\Omega_{D-1}^1\,\delta(\bvec s+\bvec r^1)Y_{\vec{\ell}^1}(\hat{\bvec r}^1)\right]\\\nonumber
    &&\quad\times\ldots\times\left[\int_{\mathbb{S}^{D-1}}d\Omega_{D-1}^{N-1}\,\delta(\bvec s+\bvec r^{N-1})Y_{\vec{\ell}^{N-1}}(\hat{\bvec r}^{N-1})\right],
\end{eqnarray}
where we have defined the parity function $\mathcal{E}(\L) = (-1)^{\ell_{D-1}^1+\cdots+\ell_{D-1}^{N-1}}$, which does not involve intermediate angular momenta. Defining the harmonic functions
\begin{eqnarray}\label{eq: alm-def}
    \boxed{a_{\vec{\ell}}(\bvec s;r) \equiv \int_{\mathbb{S}^{D-1}}d\Omega_{D-1}\,\delta(\bvec s+\bvec r)Y_{\vec{\ell}}(\hat{\bvec r}),}
\end{eqnarray}
\eqref{eq: NPCF-estimator-basis-2} can be written succinctly as
\begin{eqnarray}\label{eq: NPCF-estimator-basis-3}
    \boxed{\hat\zeta_\L(r^1,\ldots,r^{N-1}) = \frac{1}{V_D}\sum_{\ell^1\ldots\ell^{N-1}}\mathcal{E}(\L)C^\L_{\vec{\ell}^1\ldots\vec{\ell}^{N-1}}\int_{\mathbb{Q}^D} d^D\bvec s\,\left[\delta(\bvec s)a_{\vec{\ell}^1}(\bvec s;r^1)\ldots a_{\vec{\ell}^{N-1}}(\bvec s;r^{N-1})\right].}
\end{eqnarray}
The NPCF basis components can thus be estimated by first constructing $a_{\vec{\ell}}(\bvec s;r)$ for each radial parameter $r$ and angular momentum eigenvalue set $\vec{\ell}$ of interest, then performing a single spatial integral, in addition to a sum over the lower-dimensional angular momentum eigenvalues $\ell^i_1\ldots\ell^i_{D-2}$ subject to the coupling rules. Computationally, this is \textit{much} more efficient than computing the integral of \eqref{eq: NPCF-estimator-basis-1} directly in $\mathbb{Q}^{D}\otimes \mathbb{S}^{D-1}\otimes\cdots\otimes\mathbb{S}^{D-1}$ space.

\subsection{Discrete Data}
As discussed in \S\ref{sec: NPCF-intro}, a common application of correlation functions is to discrete data, \textit{i.e.} a set of points randomly distributed in the space $\mathbb{Q}^D$. In this case, the random field can be represented as a sum over $n$ Dirac Delta functions as in \eqref{eq: discrete-delta}, and the NPCF estimator becomes a sum:
\begin{eqnarray}\label{eq: NPCF-estimator-discrete}
    \hat\zeta_\L(r^1,\ldots,r^{N-1}) &=& \frac{1}{n}\sum_{\ell^1\ldots\ell^{N-1}}\mathcal{E}(\L)C^\L_{\vec{\ell}^1\ldots\vec{\ell}^{N-1}}\sum_{i=1}^n w^i\,\left[a_{\vec{\ell}^1}(\bvec x^i;r^1)\ldots a_{\vec{\ell}^{N-1}}(\bvec x^i;r^{N-1})\right],\\\nonumber
    a_{\vec{\ell}}(\bvec x^i;r) &=& \frac{1}{n}\sum_{j=1}^n\,w^jY_{\vec{\ell}}(\widehat{\bvec x^j-\bvec x^i})\delta^{\rm D}\left(r-\left|\bvec x^j-\bvec x^i\right|\right),
\end{eqnarray}
where $w^j\in\mathbb{C}$ for $j=1,\ldots,n$ are particle weights. To compute the $a_{\vec{\ell}}(\bvec x^i;r)$ functions appearing above, we perform a sum over $n$ points, $\{\bvec x^j\}$, weighted by a hyperspherical harmonic function. Whilst \eqref{eq: NPCF-estimator-discrete} involves a Dirac function, in most practical contexts, one will only compute the NPCF averaged over some finite bins in the radial coordinate, In this case, the Dirac delta will be replaced by a binning function, restricting the sum to be only over $j$ particles whose separation from $\bvec x^i$ falls in some allowed range.

To compute the NPCF, we must estimate $a_{\vec{\ell}}(\bvec x^i;r)$ at each of $n$ point locations $\bvec x^i$. Since each requires a sum over at most $n$ particles, \textbf{the total algorithm has complexity $\mathcal{O}(n^2)$}, regardless of $D$ or $N$. This is \textit{significantly} faster than the na\"ive NPCF estimator of \eqref{eq: NPCF-estimator-full}, which scaled as $\mathcal{O}(n^N)$, showing the utility of our basis decomposition.

\subsection{Gridded Data}
The NPCF estimator of \eqref{eq: NPCF-estimator-basis-3} applies also to continuous data discretized on some grid. Such a set-up is common in the physical sciences, describing, for example, hydrodynamic simulations. In this case, it is useful to write the harmonic functions $a_{\vec{\ell}}(\bvec s;r)$ in the following form:
\begin{eqnarray}
    a_{\vec{\ell}}(\bvec s;r) = \int_{\mathbb{Q}^{D}}d^D\bvec r\,\delta(\bvec s+\bvec r)Y_{\vec{\ell}}(\hat{\bvec r})\delta^{\rm D}(r-|\bvec r|) \equiv (-1)^{\ell_{D-1}}\int_{\mathbb{Q}^{D}}d^D\bvec r\,\delta(\bvec s-\bvec r)\left[Y_{\vec{\ell}}(\hat{\bvec r})\delta^{\rm D}(r-|\bvec r|)\right] \equiv (-1)^{\ell_{D-1}}\left\{\delta\ast\left[Y_{\vec{\ell}}\delta^{\rm D}\right]\right\}(\bvec s),
\end{eqnarray}
where we have first promoted the integral over $\mathbb{S}^{D-1}$ to one over $\mathbb{Q}^D$ by inserting a Dirac delta function in the radial coordinate $r$. For the second equality, we replace $\bvec r\to-\bvec r$, and make use of the parity relation for hyperspherical harmonics (Eq.\,\ref{eq: parity-hypersph}), before noting that this is simply a convolution, here denoted by $\ast$.

For gridded data in flat-space, \textit{i.e.} with $\mathbb{Q}^D = \mathbb{R}^{D}$, convolutions can be straightforwardly applied using the $D$-dimensional Fast Fourier Transform (FFT). Explicitly:
\begin{eqnarray}
    a_{\vec{\ell}}(\bvec s;r) = (-1)^{\ell_{D-1}}\mathrm{FFT}^{-1}\left[\mathrm{FFT}(\delta)\mathrm{FFT}(Y_{\vec{\ell}}\;\delta^{\rm D})\right],
\end{eqnarray}
where $\mathrm{FFT}$ and $\mathrm{FFT}^{-1}$ are the forward and reverse FFT. These operations have complexity $\mathcal{O}(N_g\log N_g)$ for $N_g$ grid points. Following computation of the various $a_{\vec{\ell}}(\bvec s;r)$ terms, the NPCF estimator can be constructed by \eqref{eq: NPCF-estimator-basis-3} as a simple sum in $D$ dimensions; the full estimator thus has complexity $\mathcal{O}(N_g\log N_g)$, which is again much faster than the na\"ive scaling of $\mathcal{O}(N_g^N)$.

\section{Applications}\label{sec: applications}
We consider a number of physical scenarios in which the above methods can be employed.

\subsection{Cosmic Microwave Background}
Cosmic Microwave Background (CMB) radiation encodes a snapshot of the Universe at the epoch of recombination, around $380,000$ years after the Big Bang. This may be probed using microwave satellites such as \textit{WMAP} and \textit{Planck}, which map the CMB temperature fluctuations as a function of direction; such observations have been used to place strong constraints on cosmological parameters such as the matter density and expansion rate \citep[e.g.,][]{2011ApJS..192...18K,2020A&A...641A...6P}.

In this instance, the random field in question is the fractional temperature fluctuation on the 2-sphere, $\Theta:\mathbb{S}^2\to\mathbb{R}$, \textit{i.e.} $\mathbb{Q}^D = \mathbb{S}^2$. Conventionally, this is expanded in $D=3$ spherical harmonics as
\begin{eqnarray}\label{eq: standard-CMB}
    \Theta(\phi,\theta) = \sum_{L=0}^\infty \sum_{M=-L}^L \Theta_{LM} Y_{LM}(\phi,\theta),
\end{eqnarray}
using spherical polar coordinates $\phi\in[0,2\pi)$, $\theta\in[0,\pi)$, (corresponding to $\theta_1$ and $\theta_2$ in our notation) and the statistical properties are characterized as a function of the harmonics $\Theta_{LM}$ (often denoted $a_{LM}^T$). To apply the techniques of this work, we consider an alternate parametrization in terms of the $D=2$ hyperspherical harmonics, writing
\begin{eqnarray}
    \Theta(\phi,\theta) = \frac{1}{\sqrt{2\pi}}\sum_{\ell=0}^\infty \Theta_\ell(\theta)e^{i\ell\phi},
\end{eqnarray}
with $\ell\in\{0,1,\ldots\}$ (Eq.\,\ref{eq: 1-sphere-basis}). Here, we identify $\theta$ as the \textit{radial} coordinate,\footnote{The $\theta$ coordinate is equivalent to the arc-lengths of great-circles through two points in $\mathbb{S}^2$, as viewed in $\mathbb{R}^3$.}  and $\ell$ as the total angular momentum. This is a more convenient basis for computing higher-order clustering statistics in $\mathbb{S}^2$ (without working in harmonic space), since (a) it avoids the need for an embedding space, and (b), assuming statistical isotropy, any correlator should be independent of the polar angle $\phi$ given some origin.

In this case, the CMB $N$-point correlator has the definition
\begin{eqnarray}
    \zeta(\hat{\bvec n}^1,\ldots,\hat{\bvec n}^{N-1}) = \mathbb{E}\left[\Theta(\hat{\bvec n}^0)\Theta(\hat{\bvec n}^0+\hat{\bvec n}^1)\ldots \Theta(\hat{\bvec n}^0+\hat{\bvec n}^{N-1})\right],
\end{eqnarray}
which is independent of the choice of origin $\hat{\bvec n}^0$. The basis functions are defined by \eqref{eq: iso-basis-wavenumber}:
\begin{eqnarray}
    \P^{0}_{\ell^1\ldots\ell^{N-1}}(\phi^1,\ldots,\phi^{N-1}) = (2\pi)^{-(N-1)/2}\mathrm{exp}\left[i(\ell^1\phi^1+\cdots+\ell^{N-1}\phi^{N-1})\right],
\end{eqnarray}
depending on $(N-1)$ polar angles $\phi$ (relative to an origin $\hat{\bvec n}^0$), and involving no intermediate angular momenta. By rotational invariance, $\ell^1+\cdots+\ell^{N-1} = 0$. The angular decomposition gives
\begin{eqnarray}
    \zeta(\hat{\bvec n}^1,\ldots,\hat{\bvec n}^{N-1}) = \sum_{\ell^1\ldots\ell^{N-1}}\zeta_{\ell^1\ldots\ell^{N-1}}(\theta^1,\ldots,\theta^{N-1})\P^0_{\ell^1\ldots\ell^{N-1}}(\phi^1,\ldots,\phi^{N-1}),
\end{eqnarray}
giving the $\mathcal{O}(n^2)$ estimators as in \eqref{eq: NPCF-estimator-basis-3}:
\begin{eqnarray}
    \zeta_{\ell^1\ldots\ell^{N-1}}(\theta^1,\ldots,\theta^{N-1}) &=& \frac{1}{4\pi}\int_{\mathbb{S}^2} d\Omega_2\,\left[\Theta(\hat{\bvec n})a_{\ell^1}(\hat{\bvec n};\theta^1)\ldots a_{\ell^{N-1}}(\hat{\bvec n};\theta^{N-1})\right],\\\nonumber
    a_{\ell}(\hat{\bvec n};\theta') &=& \frac{1}{\sqrt{2\pi}}\int_0^{2\pi} d\phi'\, \Theta(\phi',\theta';\hat{\bvec n})e^{i\ell\phi'}
\end{eqnarray}
where $\Theta(\phi',\theta';\hat{\bvec n})$ indicates the value of $\Theta$ at coordinates $(\phi',\theta')$ relative to the origin at $\hat{\bvec n}$.

Such estimators are straightforward to implement and allow efficient computation of the higher-point functions, albeit in a basis somewhat different to that usually adopted. Notably the $\ell$ coefficients are different to the $L$ coefficients in the parametrization of \eqref{eq: standard-CMB}. In our basis, $\ell$ represents angular momentum around an origin \textit{on} the 2-sphere, whilst the conventional $L$ is with reference to the origin of the 2-sphere in the embedding space $\mathbb{R}^3$. In practice, this means that we may restrict to \textit{much} smaller $\ell$ than used conventionally.\footnote{CMB fluctuations have characteristic angular scale $r_d/d_A(z_*)$ where $r_d$ is the sound horizon in comoving coordinates and $d_A(z_*)$ is the distance to the surface of last scattering. This imprints a characteristic angular momentum scale $L\sim \pi d_A(z_*)/r_d\gg 1$. In our basis, $\ell$ corresponds to the ratio of two polygon sides on $\mathbb{S}^2$ and is thus $\mathcal{O}(1)$.} We further note that the CMB contains also \textit{polarization} fluctuations which possess non-zero spin. These may be analyzed using an extension of the above formalism, for example by replacing hyperspherical harmonics with spin-weighted hyperspherical harmonics \citep[e.g.,][]{2012PhRvD..86l5013D,2016JMP....57i2504B}.

\subsection{Hydrodynamic Turbulence}\label{subsec: hydro-turb}
An additional application of clustering statistics lies in analysis of turbulence. Being a chaotic process, the evolution of the velocity and density fields in a turbulent flow cannot be treated deterministically; rather they must be analyzed statistically. Furthermore, the density fields of turbulent media are known to be close to log-normal \citep{1994ApJ...423..681V}, implying that the higher-point functions contain a wealth of information, particularly concerning the sonic and Alfv\'enic Mach numbers \citep[e.g.,][]{2007ApJ...658..423K,2009ApJ...693..250B,2010ApJ...708.1204B,2018ApJ...862..119P}.

Perhaps the simplest observable is the turbulent \textit{density} field, $\delta:\mathbb{R}^3\to\mathbb{R}$, with the $N$-point function:
\begin{eqnarray}
    \zeta(\bvec r^1,\ldots,\bvec r^{N-1}) = \mathbb{E}\left[\delta(\bvec s+\bvec r^1)\cdots\delta(\bvec s+\bvec r^{N-1})\right],
\end{eqnarray}
using the spherical coordinate chart $\bvec r = \{r,\phi,\theta\}$, where $\phi$ is the azimuthal angle and $r$ the radius. In the absence of any external forcing, we expect the NPCF to be isotropic, thus it can be expanded in the $D=3$ basis functions of \S\ref{sec: iso-basis}, giving:
\begin{eqnarray}
    \zeta(\bvec r^1,\ldots,\bvec r^{N-1}) = \sum_\L \zeta_{\L}(r^1,\ldots,r^{N-1})\P_\L(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{N-1})
\end{eqnarray}
where the basis functions are
\begin{eqnarray}
    \P_\L(\hat{\bvec r}^1,\ldots,\hat{\bvec r}^{N-1}) = \sum_{\ell^{12}\ldots\ell^{12\ldots{N-2}}}C^\L_{m^1\ldots m^{N-1}}Y_{\ell^1m^1}(\hat{\bvec r}^1)\ldots Y_{\ell^{N-1}m^{N-1}}(\hat{\bvec r}^{N-1})
\end{eqnarray}
parametrized by $\L = \ell^1\ell^2\ell^{12}\ldots\ell^{N-1}$. In this instance, the single-particle basis functions are just the usual spherical harmonics, and we have written $\vec{\ell} = (m \ell)$ for ease of interpretation. As an example, the isotropic 3PCF and 4PCF estimators become:
\begin{eqnarray}\label{eq: D=3-NPCF}
    (N=3) \quad& \zeta_{\ell}(r^1,r^2) &= \frac{1}{V}\sum_{m=-\ell}^\ell Y\int_{\mathbb{R}^3} d\bvec s\,\left[\delta(\bvec s)a_{m\ell}(\bvec s;r^1)a_{(-m)\ell}(\bvec s;r^2)\right], \\\nonumber
    (N=4) \quad & \zeta_{\ell^1\ell^2\ell^3}(r^1,r^2,r^3) &= \sum_{m^1m^2m^3} \tj{\ell^1}{\ell^2}{\ell^3}{m^1}{m^2}{m^3}\int_{\mathbb{R}^3} d\bvec s\,\left[\delta(\bvec s)a_{m^1\ell^1}(\bvec s;r^1)a_{m^2\ell^2}(\bvec s;r^2)a_{m^3\ell^3}(\bvec s;r^3)\right]\\\nonumber
    & a_{m\ell}(\bvec s; r) &= \int_{\mathbb{S}^2}d\Omega_2\,\delta(\bvec s+\bvec r)Y_{\ell m}(\hat{\bvec r})
\end{eqnarray}
where $V$ is the volume of the space. This approach was used to facilitate efficient computation of the density 3PCF in \citep{2018ApJ...862..119P}. It may similarly be extended to density fields in other dimensions, and additionally tensorial velocity correlators, via spin-weighted harmonic functions.

\subsection{Large-Scale Structure}
The large-scale three-dimensional distribution of matter in the late Universe is weakly non-Gaussian distribution and commonly analyzed using $N$-point statistics \citep[e.g.,][]{2001ASPC..252..201P}. In this case, the underlying space is expected to be homogeneous and isotropic, and, assuming zero spatial curvature \citep{2020A&A...641A...6P}, well described by \eqref{eq: metric} with $k=0$ and $D=3$, \textit{i.e.} it is $\mathbb{R}^3$.\footnote{The below applies similarly to $k\neq 0$, though there is significant evidence implying that the Universe is Euclidean \citep{2020A&A...641A...6P}.} A typical task in cosmology is computation of the isotropic correlation functions of the galaxy overdensity field, $\delta_g:\mathbb{R}^3\to\mathbb{R}$; this proceeds identically to \S\ref{sec: applications}\ref{subsec: hydro-turb}, except that the data are discrete. Basis decompositions of the above form allow information to be extracted from the high-order NPCFs, which are otherwise computationally prohibitive to measure. A full discussion of the utility of isotropic basis functions in large scale structure (including implementation via the \textsc{encore} code\footnote{\href{https://github.com/oliverphilcox/encore}{github.com/oliverphilcox/encore}}) is presented in our companion work \citep{npcf_algo}.\footnote{Our approach may additionally be used to compute \textit{projected} correlation functions in $\mathbb{R}^2$. This requires only $D=2$ basis functions.}

One additional feature of the galaxy correlation functions is of interest here. Due to the effects of redshift-space distortions \citep[e.g.,][]{1987MNRAS.227....1K,1998ASSL..231..185H}, the observed galaxy distributions are not isotropic, but instead have a preferred axis along the (assumed fixed) line of sight. For this reason, the isotropic functions of \eqref{eq: iso-basis-wavenumber} do not form a complete basis. Instead, we may use the angular momentum states $\ket{\L;L_1L_2}$ with $L_1=0$; these are isotropic about the $x^3$ axis, here taken as the line-of-sight. Such basis functions are given in $D=3$ as
\begin{eqnarray}
    \P^{L}_{\L} = \sum_{m^1\ldots m^{N-1}}{}^LC^{\L}_{m^1\ldots m^{N-1}}Y_{\ell^1m^1}(\hat{\bvec r}^1)\ldots Y_{\ell^{N-1}m^{N-1}}(\hat{\bvec r}^{N-1})
\end{eqnarray}
again labelling $\vec{\ell} = \{m\ell\}$, with modified coupling constants ${}^LC^{\L}_{m^1\ldots m^{N-1}}$, which follow \eqref{eq: Coupling-C} with $\vec 0 \to \{0L\}$. As an example, the 3PCF becomes \cite[cf.\,][]{2018MNRAS.478.1468S}
\begin{eqnarray}
    \zeta(\bvec r^1,\bvec r^2) &=& \sum_{L=0}^\infty \sum_{\ell^1\ell^2}\zeta^{L}_{\ell^1\ell^2}(r^1,r^2)\P^{L}_{\ell^1\ell^2}(\hat{\bvec r}^1,\hat{\bvec r}^2)\\\nonumber
    \P^{L}_{\ell^1\ell^2}(\hat{\bvec r}^1,\hat{\bvec r}^2) &=& \sum_m \tj{\ell^1}{\ell^2}{L}{m}{-m}{0} Y_{\ell^1m}(\hat{\bvec r}^1)Y_{\ell^2-m}(\hat{\bvec r}^2).
\end{eqnarray}
The associated estimator is given by \eqref{eq: D=3-NPCF} with just a redefinition of the coupling constants, and has complexity $\mathcal{O}(n^2)$, as before. The above decomposition provides a complete basis for the redshift-space 3PCF and extends naturally to higher orders.

\section{Summary}

Many areas of research require computation of clustering statistics of a field, whether continuous of discrete. Perhaps the most prevalent statistic is the $N$-point correlation function (NPCF), defined as the statistical average over $N$ fields in different spatial locations. If the random field is Gaussian-distributed, only the 2PCF is of interest; in the general case, all the moments have non-trivial forms. Given a set of $n$ particles, a na\"ive estimator for the NPCF has $\mathcal{O}(n^N)$ complexity, which becomes computationally infeasible: alternative methods must be sought if one wishes to unlock the information contained within the higher-point functions.

This work considers estimation of the NPCF on an isotropic and homogeneous manifold in $D$ dimensions. Under these assumptions (which encompass spherical, flat and hyperbolic spaces), we show that any function of one position can be expanded in \textit{hyperspherical harmonics}; an analog of the conventional spherical harmonics defined on $\mathbb{S}^{D-1}$. These are also eigenfunctions of the angular momentum operators; utilizing the mathematics of angular momentum addition, we can form basis functions involving $(N-1)$ points on  $\mathbb{S}^{D-1}$ as a sum over products of $(N-1)$ hyperspherical harmonics. These form a natural angular basis for the NPCF, particularly if the NPCF is rotationally invariant. With this decomposition, we can form an NPCF estimator that separates into a product of $(N-1)$ spatial integrals, and can be computed in $\mathcal{O}(n^2)$ time, regardless of $D$, $N$ and the spatial curvature.

Such techniques will allow high-dimensional correlation functions to be computed from data, allowing more complete analysis of phenomena such as fluid turbulence and galaxy clustering. Indeed, application of these ideas to large-scale structure cosmology (on $\mathbb{R}^3$) is presented in detail in our accompanying work \citep{npcf_algo}, and will facilitate a number of analyses such as a measurement of non-Gaussianity in the 4PCF of the late Universe \citep{4pcf_boss} and constraints on cosmological parity violation. These ideas may be extended further; a case of particular interest is in the correlation functions of random fields of non-zero spin. Turbulent velocities and CMB polarization require spin-1 and spin-2 fields, and the above methodology can be naturally extended to handle such complications.

\acknow{We thank David Spergel for encouraging us to write this paper, as well as Robert Cahn, Frederik J. Simons and Sauro Succi for insightful discussions. OP acknowledges funding from the WFIRST program through NNG26PJ30C and NNN12AA01C.
}

\showacknow

\section{Methods}
\subsection{Definitions}
Consider a random field $\delta:\mathbb{Q}^N\to\mathbb{C}$ where $\mathbb{Q}^D$ is some $D$-dimensional manifold equipped with a Riemannian manifold. We define the $N$-point correlation function (hereafter NPCF) of $\delta$ as
\begin{eqnarray}\label{eq: NPCF-statistic}
    \zeta(\bvec r^1,\ldots,\bvec r^{N-1};
    \bvec s) = \av{\delta(\bvec s+\bvec r^1)\ldots\delta(\bvec s+\bvec r^{N-1})}
\end{eqnarray}
where $\av{\ldots}$ indicates an average over realizations of $\delta$ and $\bvec r\in \mathbb{Q}^N$ is a coordinate chart. Assuming the space to be statistically homogeneous (such that the expectation of any random field $\mathbb{Q}^N$ is translation-invariant), the NPCF is independent of $\bvec s$, and thus a function of only $(N-1)$ $D$-dimensional vectors $\bvec r^i$.

\subsection{Constant-Curvature Geometry}

We further assume that $\mathbb{Q}^D$ is an isotropic space of constant-curvature. In this case, the manifold permits a spatial Riemannian metric of the form
\begin{eqnarray}\label{eq: D-dim-metric}
    d\Sigma^2_{D} = dr^2+\chi_k^2(r)\left\{d\theta_1^2+\sin^2\theta_1\left[d\theta_2^2+\sin^2\theta_2\left(d\theta_3^2+\ldots\right)\right]\right\}
\end{eqnarray}
in hyperspherical coordinates $\bvec r \equiv \{r, \theta_1,\ldots,\theta_{D-1}\}$ for curvature parameter $k$. Here $r$ is a radial coordinate and $\theta_{i}$ are angular variables. $\chi^2_k(r)$ is defined by
\begin{eqnarray}
    \chi_k^2(r) = \begin{cases} \frac{1}{\sqrt{k}}\sin \left(r\sqrt{k}\right), & k > 0\\ \,r, & k = 0 \\ \frac{1}{\sqrt{|k|}}\sinh \left(r\sqrt{|k|}\right), & k<0. \end{cases}
\end{eqnarray}
For $D=3$, we recognize this as the constant-curvature solution to the cosmological Friedmann-Robertson-Walker equations expressed in hyperspherical coordinates with $\theta_1\equiv\theta$, $\theta_2\equiv\phi$. The sign of $k$ sets the topology of the space; $k>0$, $k=0$ and $k<0$ give the hyperbolic, flat and spherical spaces $\mathbb{H}^{D}$, $\mathbb{R}^D$ and $\mathbb{S}^D$ respectively.

A convenient basis for the constant-curvature space may be deduced by considering the eigenfunctions of the Laplace-Bertrami operator, $\Delta$, a generalization of the Laplace operator beyond $\mathbb{R}^3$. Given a metric $g_{ij}$, eigenfunctions $f(\bvec r)$ must satisfy
\begin{eqnarray}
    \Delta f \equiv \frac{1}{\sqrt{|g|}}\partial_i \left(\sqrt{|g|}g^{ij}\partial_j f\right) = 0
\end{eqnarray}
where $|g|$ is the metric determinant and $\partial_i$ is a partial derivative with respect to the $i$-th coordinate. Inserting \eqref{eq: D-dim-metric} leads to the partial differential equation
\begin{eqnarray}
    \frac{1}{\chi_k^{D-1}(r)}\partial_r \left(\chi^{D-1}_k(r)\partial_r f\right) + \frac{1}{\chi_k^2(r)\sin^{D-2}\theta_1}\partial_{\theta_1}\left(\sin^{D-2}\theta_1\partial_{\theta_1}f\right)+\ldots +  \frac{1}{\chi_k^{2}(r)\sin^{2D-4}\theta_1\ldots \sin^{2}\theta_{D-2}}\partial_{\theta_{D-1}}^2f = 0
\end{eqnarray}
noting that $\sqrt{|g|} = \chi_k^{D-1}(r)\sin^{D-2}\theta_1\ldots\sin\theta_{D-2}$. Assuming a separable eigenfunction $f(\bvec r) = R(r)Y(\hat{\bvec r})$, we require
\begin{eqnarray}\label{eq: eigenfunction-eqns}
    \frac{1}{\chi_k^{D-3}(r)}\partial_r \left(\chi^{D-1}_k(r)\partial_r R(r)\right) &=& \lambda R(r)\\\nonumber
    \frac{1}{\sin^{D-2}\theta_1}\partial_{\theta_1}\left(\sin^{D-2}\theta_1\partial_{\theta_1}Y(\hat{\bvec r})\right)+\ldots +  \frac{1}{\sin^{2D-4}\theta_1\ldots \sin^{2}\theta_{D-2}}\partial_{\theta_{D-1}}^2Y(\hat{\bvec r}) &=& -\lambda Y(\hat{\bvec r})
\end{eqnarray}
for some scalar $\lambda$. The LHS of the second equation is simply equal to $\Delta_{\mathbb{S}^{D-1}}Y(\hat{\bvec r})$, where $\Delta_{\mathbb{S}^{D-1}}$ is the Laplace-Bertrami operator on the $(D-1)$-sphere $\mathbb{S}^{D-1}$. This may be additionally seen by noting that the metric \eqref{eq: D-dim-metric} can be written $d\Sigma^2_D = dr^2 + \chi_k^2(r)d\Omega_{D-1}^2$, where $d\Omega_{D-1}^2$ is the $(D-1)$-sphere metric. Notably, the angular solutions are \textit{independent} of the curvature parameter $k$. Physically, this corresponds to the notion that, for a homogeneous and isotropic space, spherical symmetry is respected about any given point, regardless of curvature.

\subsection{$D$-Dimensional Spherical Harmonics}

Furthermore, \eqref{eq: eigenfunction-eqns} may be written in terms of the $(D-1)$-dimensional angular momentum operator $\widehat{\bvec L}_{D-1}^2$ as
\begin{eqnarray}
    \Delta_{\mathbb{S}^{D-1}}Y(\hat{\bvec r}) = - \widehat{\bvec L}_{D-1}^2 Y(\hat{\bvec r}) \equiv -\lambda Y(\hat{\bvec r})
\end{eqnarray}
\oliver{mention that these are spherical harmonics}
The eigenfunctions of $\widehat{\bvec L}_{D-1}^2$ satisfy $\widehat{\bvec L}_{D-1}^2 Y^\ell(\hat{\bvec r}) = \ell(\ell+D-2)Y^\ell(\hat{\bvec r})$ where the integer $\ell$ is a principal angular momentum quantum number. We require $(D-1)$ indices to fully specify the basis-function, $Y$, henceforth denoted as $Y^\ell_{\ell_{D-2}\ldots\ell_1}(\hat{\bvec r})$.

This is the analog to the standard result $\widehat{\bvec L}_{2}^2 Y_{\ell m}(\hat{\bvec r}) = \ell(\ell+1)Y_{\ell m}(\hat{\bvec r})$ in 3D space; there $\ell_1 = m$ is the spin quantum number. \oliver{give explicit forms for $D=2,3,4$?}

A general $D$-dimensional function $g(\bvec x)$ in a constant-curvature space can be expanded into this basis
\begin{eqnarray}\label{eq: constant-curvature-expansion}
    g(\bvec r) = \sum_{\ell}\sum_{\ell_1\ldots\ell_{D-2}} g^\ell_{\ell_{D-2}\ldots\ell_1}(r)Y^\ell_{\ell_{D-2}\ldots\ell_1}(\hat{\bvec r})
\end{eqnarray}
subject to some restrictions on $\ell_{i}$.

For $D=3$ the basis functions are straightforward:
\begin{eqnarray}
    (D = 2) &\quad Y_\ell(\theta) = e^{i\ell \theta}\\\nonumber
    (D = 3) &\quad Y_{\ell_1\ell_2}(\theta_1,\theta_2) = P_{\ell_1}^{\ell_2}(\cos\theta_1)e^{i\ell_2\theta_2}
\end{eqnarray}
where $P_\ell^m$ is the associated Legendre polynomial. Identifying $(\ell_1,\ell_2) \equiv(\ell,m)$, $(\theta_1,\theta_2)\equiv(\theta,\phi)$ we recognize the $D=3$ case as the usual spherical harmonics on the two-sphere in the Condan-Shotley phase \oliver{(true?)}.

The $D = 3$ case is just the usual spherical harmonics with $\ell_1$

\subsection{Isotropic $N$-point Basis Functions}
We now consider forming a basis for the NPCF statistic \eqref{eq: NPCF-statistic}. Firstly, we note that the NPCF exists in a space involving $(N-1)$ copies of $\mathbb{Q}^D$, and thus, by \eqref{eq: constant-curvature-expansion}, we can expand
\begin{eqnarray}
    \zeta(\bvec r^1,\ldots,\bvec r^{N-1}) &=& \sum_{\L}\zeta_{\L}(r^1,\ldots,r^{N-1})Y^\ell_{\ell_i}(\hat{\bvec r}^1)\ldots Y^\ell_{\ell_i}(\hat{\bvec r}^N)
\end{eqnarray}

Now, we enforce that the NPCF be invariant under rotations.
\oliver{extend to N-point basis functions here?}

\subsection{NPCF Estimator}

\begin{eqnarray}
    \zeta_\L(r^1,\ldots,r^{N-1}) &=& \int d\bvec s\,\delta(\bvec s)\prod_{i=1}^{N-1}\int d\hat{\bvec r}^i\,\delta(\bvec s+\bvec r^i)Y^\ell_{\ell_i}(\hat{\bvec r}^i) \equiv \int \delta(\bvec s)\prod_{i=1}^{N-1}a^\ell_{\ell_i}(\bvec s)
\end{eqnarray}
\oliver{integrals need to be in correct volume}
where
\begin{eqnarray}
    a^\ell_{\ell_i}(\bvec s) &=& \int d\hat{\bvec r}^i\,\delta(\bvec s+\bvec r^i)Y^\ell_{\ell_i}(\hat{\bvec r}^i)
\end{eqnarray}
If $\delta$ is a discrete field it can be represented as a weighted sum over $n$ Dirac delta functions:
\begin{eqnarray}
    \delta(\bvec r) = \sum_{j=1}^n  w_j\,\delta_{\rm D}(\bvec r-\bvec r^j)
\end{eqnarray}
for some weights $\{w_j\}$. This gives the straightforward form for the NPCF estimator:
\begin{eqnarray}
    \zeta_\L(r^1,\ldots,r^{N-1}) &=& \sum_{j=1}^n w_j \prod_{i=1}^{N-1}a_{\ell_i}^{\ell}(\bvec r^j)\\\nonumber
    a^\ell_{\ell_i}(\bvec s) &=& \sum_{j=1}^n\,w_jY^\ell_{\ell_i}(\widehat{\bvec r^j-\bvec s})
\end{eqnarray}
Each $a^{\ell}_{\ell_i}(\bvec s)$ function is a sum over $n$ points and must be computed at $n$ locations $\bvec s \in \{\bvec r^j\}$, thus the algorithm has complexity $\mathcal{O}(n^2)$. Furthermore, it may be applied to data on some grid \oliver{does this work in general geometries?}

\section{Applications}
\subsection{Cosmic Microwave Background}
Here we require $\mathbb{Q}^D = \mathbb{S}^2$. Parametrizing by $\bvec r = \theta, \phi$ where $\phi$ is a polar angle and $\theta$ a `radial' parameter on the sphere (equivalent to the angle swept out by a great circle connecting two points as viewed in the embedding space $\mathbb{R}^3$), we obtain the $D=2$ spherical harmonics:
\begin{eqnarray}
    Y_\ell(\phi) = e^{i\ell\phi}
\end{eqnarray}
whose rotational symmetry requires $\ell \in \{0,1,\ldots\} \equiv\mathbb{N}_0$. The $N$-point isotropic basis function is thus
\begin{eqnarray}
    \P_{\ell_1\ldots\ell_N}(\phi_1,\ldots,\phi_N) = e^{i(\ell_1\phi_1+\ldots+\ell_N\phi_N)}
\end{eqnarray}
with $\sum_{i=1}^N \ell_i = 0$ to ensure invariance under rotations. The 2-sphere NPCF can be expressed in this basis as
\begin{eqnarray}
    \zeta(\bvec r^1,\ldots,\bvec r^{N-1}) &\equiv& \sum_{\ell_1+\ldots+\ell_{N-1}=0}\zeta_{\ell_1\ldots \ell_{N-1}}(\theta_1,\ldots,\theta_{N-2})e^{i\ell_1\phi_1}\ldots e^{i\ell_{N-1}\phi_{N-1}}
\end{eqnarray}
with the components described by $(N-2)$ independent angular momentum numbers $\ell_i$. The estimator is given as above, with the harmonic coefficients
\begin{eqnarray}
    a_{\ell}(\theta,\phi) = \int_{0}^{2\pi}d\phi\,e^{i\ell\phi}\delta(\bvec n)
\end{eqnarray}
\oliver{is this true?}

\subsection{Large Scale Structure}

\subsection{Hydrodynamics}

\subsection{Other}
NB: 4D spherical harmonics represent wavefunction of hydrogen atom in mommentum space

\section{Rough}

The hyperspherical harmonics are defined as the degree $\ell_{D-1}$ homogeneous harmonic polynomials on the unit sphere $\mathbb{S}^{D-1}$
\begin{eqnarray}\label{eq: Ylm-def}
    Y_{\vec{\ell}}(\hat{\bvec r}) &\equiv& Y_{\ell_1\ldots\ell_{D-1}}(\theta_1,\ldots,\theta_{D-1}) = \frac{1}{\sqrt{2\pi}}e^{i\ell_1\theta_1}P_{\ell_2}^{-\ell_1}(\cos\theta_2)\times \sin^{1/2}(\theta_3)P^{-(\ell_2+1/2)}_{\ell_3+1/2}(\cos\theta_3)\times\ldots\\\nonumber
    &&\,\times\,\sin^{(3-D)/2}\theta_{D-1} P^{-(\ell_{D-2}+(D-3)/2)}_{\ell_{D-1}+(D-3)/2}(\cos\theta_{D-1})\\\nonumber
    &&\,\times\,\sqrt{\frac{2\ell_2+1}{2}\frac{2\ell_3+2}{2}\ldots\frac{2\ell_{D-1}+D-2}{2}\times\frac{(\ell_2+\ell_1)!}{(\ell_2-\ell_1)!}\frac{(\ell_3+\ell_2+1)!}{(\ell_3-\ell_2)!}\ldots\frac{(\ell_{D-1}+\ell_{D-2}+D-3)!}{(\ell_{D-1}-\ell_{D-2})!}}
\end{eqnarray}
where $\theta_1\in[0,2\pi)$ and $\theta_{j}\in[0,\pi)$ for $j \in \{2,\ldots,D-1\}$. Here, $P_\ell^m(x)$ are associated Legendre polynomials. Additionally $\ell_1\in\{-\ell_2,\ldots,\ell_2\}$ and  $\ell_{2}\leq\ell_3\leq\ldots\leq \ell_{D-1}$.
This is an irreducible representation of $SO(D)$ and satisfy $\Delta_{\mathbb{S}^{D-1}}Y_{\vec{\ell}}(\hat{\bvec r}) = -\ell_{D-1}(\ell_{D-1}+D-2)$. They are eigenvalues of $L_{(D-1)(D-2)}$, $L^2_{D-2}, \ldots, L^2_1$ \oliver{true}

In particular, the lowest dimensional cases give
\begin{eqnarray}
    (D=2) & \quad Y_{\ell_1}(\theta_1) &= \frac{1}{\sqrt{2\pi}}e^{i\ell_1\theta_1}\\\nonumber
    (D=3) & \quad Y_{\ell_1\ell_2}(\theta_1,\theta_2) &= \sqrt{\frac{2\ell_2+1}{4\pi}\frac{(\ell_2+\ell_1)!}{(\ell_2-\ell_1)!}}e^{i\ell_1\theta_1}P_{\ell_2}^{-\ell_1}(\cos\theta_2)\\\nonumber
    (D=4) & \quad Y_{\ell_1\ell_2\ell_3}(\theta_1,\theta_2,\theta_3) &= \sqrt{\frac{(2\ell_2+1)(2\ell_3+2)}{8\pi}\frac{(\ell_2+\ell_1)!}{(\ell_2-\ell_1)!}\frac{(\ell_3+\ell_2+1)!}{(\ell_3-\ell_2)!}}e^{i\ell_1\theta_1}P_{\ell_2}^{-\ell_1}(\cos\theta_2)\sin^{1/2}(\theta_3)P^{-(\ell_2+1/2)}_{\ell_3+1/2}(\cos\theta_3)
\end{eqnarray}
The $D=3$ case is simply the conventionally normalized spherical harmonic, made clear by identifying $(\ell_1,\ell_2)\equiv(m,\ell)$, $(\theta_1,\theta_2)\equiv(\phi,\theta)$.

Total angular momentum operator is $\widehat{\bvec L}_{D}^2 = \sum_{j<i} \widehat{L}_{ij}^2$ where $\widehat{L}_{ij} = \hat{x}_i\hat{p}_j - \hat{x}_j\hat{p}_i$ is the orbital angular momentum operator in the embedding space $\mathbb{R}^{D}$ and $i,j = 1,2,\ldots D$. The hyperspherical harmonic function satisfies $\widehat{\bvec L}^2 Y_{\vec{\ell}}(\hat{\bvec r}) = \ell_{D-1}(\ell_{D-1}+D-2)Y_{\vec{\ell}}(\hat{\bvec r})$, \textit{i.e.} $\ell_{D-1}$ specifies the total angular momentum of the state. Furthermore, $Y_{\vec{\ell}}(\hat{\bvec r})$ is an eigenvector of the operator $\widehat{L}_{23}$ with eigenvalue $\ell_{1}$ (which is the multidimensional analog of the spherical harmonic spin $m$), an eigenvector of $\widehat{\bvec L}_{3}^2\equiv \widehat{L}_{12}^2+\widehat{L}_{13}^2+\widehat{L}_{23}^2$ with eigenvalue $\ell_2(\ell_2+1)$, an eigenvector of $\widehat{\bvec L}_{4}^2\equiv \widehat{\bvec L}_3^2+\widehat{L}_{14}^2+\widehat{L}_{24}^2+\widehat{L}_{34}^2$ with eigenvalue $\ell_3(\ell_3+2)$, \textit{et cetera}.

The hyperspherical harmonics are orthonormal:
\begin{eqnarray}
    \int_{\mathbb{S}^{D-1}} d\Omega_{D-1} Y_{\vec{\ell}}(\hat{\bvec r})Y_{\vec{\ell}'}^*(\hat{\bvec r}) = \delta^{\rm K}_{\ell^{}_1\ell_1'}\ldots \delta^{\rm K}_{\ell^{}_{D-1}\ell_{D-1}'}
\end{eqnarray}
with the conjugate defined via
\begin{eqnarray}
    Y_{\ell_1\ell_2\ldots\ell_{D-1}}^*(\hat{\bvec r}) = (-1)^{\ell_1} Y_{(-\ell_1)\ell_2\ldots\ell_{D-1}}^*(\hat{\bvec r}),
\end{eqnarray}
easily verified by \eqref{eq: Ylm-def} and the symmetries of associated Legendre polynomials.

Since the basis of hyperspherical harmonics is complete, we can expand a product of two functions of the same argument as a sum:
\begin{eqnarray}
    Y_{\vec{\ell}}(\hat{\bvec r})Y_{\vec{\ell}'}(\hat{\bvec r}) = \sum_{\vec{\ell}''} \mathcal{G}_{\vec{\ell}\,\vec{\ell}'\,\vec{\ell}''}Y^*_{\vec{\ell}''}(\hat{\bvec r}), \quad \mathcal{G}_{\vec{\ell}\,\vec{\ell}'\,\vec{\ell}''} \equiv \int_{\mathbb{S}^{D-1}} d\Omega_{D-1} Y_{\vec{\ell}}(\hat{\bvec r})Y_{\vec{\ell}'}(\hat{\bvec r})Y_{\vec{\ell}''}(\hat{\bvec r})
\end{eqnarray}
defining $\mathcal{G}_{\vec{\ell}\,\vec{\ell}'\,\vec{\ell}''}$ by orthonormality; this is the hyperspherical analog of the usual Gaunt integral.

We can also consider the behavior of $Y_{\vec{\ell}}(\hat{\bvec r})$ under rotations. Defining $R$ as a simultaneous rotation of all angular coordinates, \textit{i.e.} $\hat{\bvec r} \to R\hat{\bvec r}$, we may write
\begin{eqnarray}
    Y_{\vec{\ell}}(R\hat{\bvec r}) = \sum_{\vec{\ell}'} \mathcal{D}_{\vec{\ell}\vl'}(R)Y_{\vec{\ell}'}(\hat{\bvec r})
\end{eqnarray}
where we have notated that the rotated state $Y_{\vec{\ell}}(R\hat{\bvec r})$ can be written in terms of the basis functions at $\hat{\bvec r}$ by orthonormality. The matrices $\mathcal{D}_{\vec{\ell}\vl'}(R)$ are analogs of the Wigner $\mathcal{D}$-matrix in 3D-space, and are defined by
\begin{eqnarray}
    \mathcal{D}_{\vec{\ell}\,\vec{\ell}'}(R) = \int_{\mathbb{S}^{D-1}}d\Omega_{D-1}Y^{}_{\vec{\ell}}(\hat{\bvec r})Y_{\vec{\ell}'}^*(R\hat{\bvec r})
\end{eqnarray}
Since the rotation group is orthogonal, $\mathcal{D}_{\vec{\ell}\,\vec{\ell}'}(R)$ is unitary. Note also that $\mathcal{D}_{\vec{\ell}\,\vec{\ell}'}(R) \propto \delta^{\rm K}_{\ell_{D-1}^{}\ell_{D-1}'}$, since the total angular momentum is invariant under rotations.

Now consider the product states. We may form a composite state from the product of two hyperspherical harmonics as
\begin{eqnarray}\label{eq: prod-two-states}
    P_\L(\hat{\bvec r}^1,\hat{\bvec r}^2) = \sum_{\vec{\ell}_1\vec{\ell}_2}C^\L_{\vec{\ell}_1\vec{\ell}_2} Y_{\vec{\ell}_1}(\hat{\bvec r}^1)Y_{\vec{\ell}_2}(\hat{\bvec r}^2)
\end{eqnarray}
where the state is indexed by some set of coefficients $\L$ and $C^\L_{\vec{\ell}_1\vec{\ell}_2}$ are coupling coefficients. Recalling that $Y_{\vec{\ell}}(\hat{\bvec r})$ is an eigenfunction of the $D$-dimensional angular momentum operators, we recognize this as a problem of angular-momentum addition in $D$-dimensions. In particular, given two states $\ket{\vec{\ell}_1}$ and $\ket{\vec{\ell}_2}$, we can form the composite state
\begin{eqnarray}
    \ket{\vec{\ell}_1,\vec{\ell}_2;\vec L} = \sum_{\vec{\ell}_1\vec{\ell}_2}\left(\vec{\ell}_1,\vec{\ell}_2|\vec L\right)\ket{\vec{\ell}_1}\ket{\vec{\ell}_2}
\end{eqnarray}
\oliver{check summation - what do we sum over - can't be everything!}, where the parentheses indicate the Clebsch-Gordan coefficient of the group $SO(D)$. This is an eigenfunction of $D$-dimensional angular momentum operators constructed from $\widehat{L}^{(1)}_{ij}+\widehat{L}^{(2)}_{ij}$ in the space $SO(D)\otimes SO(D)$.

This sets the coupling constant in \eqref{eq: prod-two-states}. \oliver{can we write this in terms of Gaunt integrals?} In general, the form of these is set by the theory of angular momentum in $D$ dimensions; see [REFS]. For $D=2,3,4$, we obtain [REFS for D=4!]
\begin{eqnarray}
    (D=2) &\quad (\ell,\ell'|L) &= \delta^{\rm K}_{\ell+\ell',L}
    \\\nonumber
    (D=3) &\quad (\ell_1\ell_2,\ell_1'\ell_2'|L_1L_2) &= (-1)^{-\ell_2+\ell_2'-L_1}\sqrt{2L_2+1} \tj{\ell_2}{\ell_2'}{L_2}{\ell_1}{\ell_1'}{-L_1}\\\nonumber
    (D=4) &\quad (\ell_1\ell_2\ell_3,\ell_1'\ell_2'\ell_3'|L_1L_2L_3) &= (-1)^{-\ell_2+\ell_2'-L_1}(L_3+1)\sqrt{(2\ell_2+1)(2\ell_2'+1)(2L_2+1)}\tj{\ell_2}{\ell_2'}{L_2}{\ell_1}{\ell_1'}{-L_1}\begin{pmatrix}\ell_3/2 & \ell_3'/2 & L_3/2\\ \ell_3/2 & \ell_3'/2 & L_3/2 \\ \ell_2 & \ell_2' & L_2\end{pmatrix}
\end{eqnarray}
The second set are the usual Clebsch-Gordan coefficients, made clearer by the identification $(\ell_1,\ell_2)=(m,\ell)$. The $3\times2$ and $3\times 3$ matrices are Wigner 3-$j$ and 9-$j$ symbols. Note that $\ell_1+\ell_1'=L_1$ is enforced in all cases (since $\ell_1$ is the eigenvector of the $\widehat{L}_{23}$ operator, which adds linearly in the combined state), and that the $D=4$ case can be written in terms of the $D=3$ Wigner 3-$j$ and 9-$j$ symbols; this occurs since $SO(4)$ is a double-cover of $SO(3)\times SO(3)$. \oliver{see e.g. \citep{biedenharn1961} and Meremianin and \citep{VanIsacker1991}}

\oliver{note what the product-states depend on}
e.g.
\begin{eqnarray}
    \ket{\ell_2,\ell_2';L_1,L_2} = \sum_{\ell_1\ell_1'}\left(\ell_1\ell_2,\ell_1'\ell_2'|L_1L_2\right)\ket{\ell_1\ell_2}\ket{\ell_1'\ell_2'}
\end{eqnarray}

\oliver{show why the product states are invariant under rotations}

\section{Summary and Discussion}