\section{Introduction}

The hyperbolic Kac--Moody algebra $\mathfrak{e}_{10}$ has been conjectured to generate an underlying symmetry of M-theory~\cite{Julia,Damour:2002cu}  and its (maximal compact) subalgebra $K(\mathfrak{e}_{10})$ (fixed by the Chevalley involution) plays the role of the generalised R-symmetry transformations~\cite{deBuyl:2005zy,Damour:2005zs,deBuyl:2005sch,Damour:2006xu,Kleinschmidt:2007zd}. In the $\mathfrak{e}_{10}$ conjecture the constrained null motion of a spinning particle on the symmetric space $E_{10}/K(E_{10})$ is equivalent to the dynamics of supergravity or even M-theory. This conjecture thus far has only been verified for a finite set of generators of the infinite-dimensional algebra $\mathfrak{e}_{10}$ both in the bosonic and fermionic sector~\cite{Damour:2002cu,Kleinschmidt:2004rg,Kleinschmidt:2004dy,Damour:2005zs,deBuyl:2005sch,Damour:2007dt}. However, it has thus far proved impossible to construct a spinning particle action on $E_{10}/K(E_{10})$ that has one-dimensional local supersymmetry, as was explained at length in Ref.~\cite{Kleinschmidt:2014uwa}.

One major obstacle when constructing a supersymmetric $E_{10}$-model is the disparity between the bosonic and fermionic degrees of freedom that are used: The bosons are associated with the infinitely many directions of the symmetric space $E_{10}/K(E_{10})$ whereas the fermions used in Refs.~\cite{Damour:2005zs,deBuyl:2005sch} were constructed out of a finite-dimensional
(hence unfaithful)
representation of dimension $320$ of the R-symmetry group $K(E_{10})$.\cite{const} It therefore appears necessary to construct larger, preferably infinite-dimensional, fermionic representations of $K(E_{10})$ and this is the topic we will pursue in the present contribution that is partially based on our paper Ref.~\cite{Kleinschmidt:2013eka}.

We develop a new formalism for constructing representations of $K(\mathfrak{e}_{10})$ and exhibit new irreducible examples of dimensions $1728$ and $7040$, respectively. We refer to them as `higher spin representations' although their spin is not necessarily higher from a space-time point of view but rather when viewed from the (truncated)
Wheeler--DeWitt superspace of metrics. This point will be explained in more detail below. We will see that only the ${\bf 7040}$ contains also genuine higher spin fields from the space-time perspective.
Our formalism gives the action of an infinite number of $K(\mathfrak{e}_{10})$ generators that are labelled by the positive real roots of $\mathfrak{e}_{10}$. Since the representations are finite-dimensional and therefore necessarily unfaithful, an infinite number of these generators will be represented by the same operator on the representation space.

Let us emphasize that a proper understanding of the fermionic sector will be
essential for further progress with understanding the role of $E_{10}$ in M-theory,
something that is unlikely in our opinion to be achievable if one restricts attention
to the bosonic sector only. On top of
the (unknown) representation theory of $K(E_{10})$ this might quite possibly require some
novel type of bosonisation, as is suggested by the fact that $E_{10}$ seems to `know everything'
about the fermions of maximal supergravity that we have learnt from supersymmetry
(in particular, the structure of the bosonic and fermionic multiplets). Equally important, the actual \textit{physics} of the quantised theory with fermions is likely to differ very much from that of the purely bosonic system, as is obvious from the example of supersymmetric quantum cosmology investigated in~Ref.~\cite{Damour:2014cba}.

\section{$\mathfrak{e}_{10}$ and $K(\mathfrak{e}_{10})$}

The (split real) Lie algebra $\mathfrak{e}_{10}$ is a hyperbolic Kac--Moody Lie algebra~\cite{Kac}. Its only known definition is in terms of generators and relations. There are $30$ generators $(e_i,f_i,h_i)$ for $i=1,\ldots,10$ and each triple generates an $\mf{sl}(2,\mathbb{R})$ subalgebra of $\mathfrak{e}_{10}$. The full set of defining relations is given by
\begin{align}
[h_i, h_j] &=0,&
[h_i, e_j] &= A_{ij} e_j,&
[h_i, f_j] &= -A_{ij} f_j,&\nonumber\\
{} [e_i,f_j] &= \delta_{ij} h_i,&
(\mathrm{ad}\,e_i)^{1-A_{ij}} e_j &=0,&
(\mathrm{ad}\,f_i)^{1-A_{ij}} f_j &=0.
\end{align}
Here, $A_{ij}$ are the elements of the symmetric Cartan matrix associated with the $\mathfrak{e}_{10}$ Dynkin diagram shown in figure~\ref{fig:e10dynkin}. The Cartan matrix is of Lorentzian signature and there are roots $\alpha$ of the algebra with norms $\alpha^2=2-2k$ for $k\in \mathbb{N}_0$. The roots with $\alpha^2=2$ are called real roots and they have multiplicity one; all others are imaginary and have higher multiplicity.

\begin{figure}
\centerline{\includegraphics[width=8.5cm]{e10dynkin.eps}}
\caption{The Dynkin diagram of $\mathfrak{e}_{10}$ with labelling of nodes.}
\label{fig:e10dynkin}
\end{figure}

The subalgebra $K(\mathfrak{e}_{10})$ is generated by the `compact' combinations
\begin{align}\label{xi}
x_i =e_i - f_i
\end{align}
which are invariant under the Cartan-Chevalley involution
\begin{equation}
\omega(e_i) = - f_i \; , \quad
\omega(f_i) = - e_i \;,\quad
\omega(h_i) = - h_i
\end{equation}
The relations satisfied by these elements are in general not homogeneous (unlike the
standard relations in the Chevalley--Serre presentation for the $e_i$ and $f_i$ above). Depending on whether two nodes $i$ and $j$ are connected by a line in the Dynkin diagram or not one has two cases
\begin{align}
\label{BRels}
\left[x_i, x_j \right] &=0 &&\textrm{if $i$ and $j$ are not connected}\nonumber\\
\left[x_i, \left[ x_i,x_j \right]\right] + x_j &=0 &&\textrm{if $i$ and $j$ are connected}
\end{align}
We will refer to these as the Berman--Serre relations; these relations were studied in a more general context in Ref.~\cite{Berman}. The algebra $K(\mathfrak{e}_{10})$ is then defined as the free Lie algebra over the
generators $\{x_i\}$  subject to the relations \eqref{BRels}. The task of finding representations of $K(\mathfrak{e}_{10})$ is  tantamount to finding matrices or operators that satisfy these relations.

Since all simple generators $x_i$ are associated with real simple roots (of multiplicity one) one can also rephrase these relations more generally for any real roots by considering a generator $J(\alpha)$ for any (positive) real root $\alpha$. Using a basis of simple roots $\alpha_i$ of the root lattice one then has $x_i = J(\alpha_i)$ as particular case. The relations~\eqref{BRels} are then equivalent for real roots $\alpha$ and $\beta$ obeying $\alpha\cdot \beta\in \{-1,0,1\}$
\begin{align}
\label{BR2}
[J(\alpha) , J(\beta) ] &= \epsilon_{\alpha,\beta} J(\alpha+ \beta),&&\textrm{if $\alpha\cdot\beta=- 1$},&\nonumber\\
{}[J(\alpha) , J(\beta) ] &= -\epsilon_{\alpha,-\beta} J(\alpha- \beta),&&\textrm{if $\alpha\cdot\beta= +1$},&\nonumber\\
{}[J(\alpha) , J(\beta) ] &= 0,&&\textrm{if $\alpha\cdot\beta=0$},&
\end{align}
and $\epsilon_{\alpha,\beta}\in \{-1,1\}$ is a certain cocycle on the $\mathfrak{e}_{10}$ root lattice that satisfies
\begin{align}
\epsilon_{\alpha,\beta} = - \epsilon_{\beta,\alpha} = - \epsilon_{-\alpha,-\beta},\quad \epsilon_{\alpha+\beta,-\beta}= \epsilon_{\alpha,\beta}.
\end{align}
The restriction on the inner product in the commutation is to make sure that $\alpha\mp \beta$ is a real root or no root at all, such that one does not have to worry about multiplicities from imaginary roots on the right-hand side. By contrast $\epsilon_{\alpha,\beta}$ can be defined for any pair of elements $(\alpha,\beta)$ of the root lattice.

To the root lattice of $\mathfrak{e}_{10}$ one can also associate elements $\Gamma(\alpha)$ of the $\mf{so}(10)$ Clifford algebra of real $(32\times 32)$ matrices such that \cite{Kleinschmidt:2013eka}
\begin{align}
\label{GR2}
\Gamma(\alpha) \Gamma(\beta)  = \epsilon_{\alpha,\beta} \Gamma(\alpha+\beta) =-\epsilon_{\alpha,-\beta}\Gamma(\alpha-\beta).
\end{align}
With these rules it is then not hard to verify that
\begin{align}
J(\alpha) = \frac12 \Gamma(\alpha)
\end{align}
provides a representation of $K(\mathfrak{e}_{10})$ for all real roots $\alpha$. This $32$-dimensional representation is known as the Dirac-spinor of $K(\mathfrak{e}_{10})$. By choosing a particular basis of the root lattice, called wall basis, one could exhibit\cite{Kleinschmidt:2013eka} that the $x_i$ for $i=1,\ldots,9$ are just the usual spin representation $x_i=\frac12 \Gamma^{i\,i+1}$ of $\mf{so}(10)$ but we will not use this here.

\section{Tensors and spinors on Wheeler--DeWitt mini-superspace}

The space of diagonal spatial metrics in $11$ space-time dimensions is a Lorentzian
ten-dimensional space in the Hamiltonian treatment of general relativity.
This space is actually a finite-dimensional truncation of the full Wheeler--DeWitt
`superspace' ({\it alias} the `moduli space of 10-geometries')
to the finite-dimensional subspace of diagonal scale factors  (the negative direction
that renders this metric indefinite is associated with the scaling mode of the metric).
We choose a basis $e_{\mathtt a}$ for
 this ten-dimensional space (${\mathtt a}, {\mathtt b},\ldots=1,\ldots, 10$) with inner products
\begin{align}
e_{\mathtt a} \cdot e_{\mathtt b} = G_{{\mathtt a}{\mathtt b}}
\end{align}
where $G_{{\mathtt a}{\mathtt b}}$ is the Lorentzian DeWitt superspace metric restricted to the space of
metric scale factors; more explicitly, it follows from the Einstein--Hilbert action that
\begin{equation}\label{Gab}
G_{{\mathtt a}{\mathtt b}} = \delta_{{\mathtt a}{\mathtt b}} - 1 \quad \Rightarrow \qquad
G^{{\mathtt a}{\mathtt b}} = \delta_{{\mathtt a}{\mathtt b}} - \frac19
\end{equation}
This Lorentzian space can be identified with the Lorentzian space spanned by the roots of $\mathfrak{e}_{10}$.
In the remainder we do not require the explicit form of $G_{{\mathtt a}{\mathtt b}}$ of \eqref{Gab}.

Our ansatz for fermionic representations of $K(\mathfrak{e}_{10})$ then consists in considering tensor-spinors $\phi^{{\mathtt a}_1\ldots {\mathtt a}_n}_A = \phi^{({\mathtt a}_1\ldots {\mathtt a}_n)}_A$ that are completely symmetric in their $n$ tensor indices and also carry a spinor index $A=1,\ldots, 32$ of $\mf{so}(10)$. The Dirac-spinor discussed in the preceding section then simply corresponds to $n=0$. We will also consider the case when $\phi^{{\mathtt a}_1\ldots{\mathtt a}_n}_A$ is traceless in its tensor indices. Since the tensor indices are those of a Lorentzian $\mf{so}(1,9)$ space while the spinor index belongs to the Euclidean $\mf{so}(10)$ subalgebra of $K(\mathfrak{e}_{10})$ our approach could be termed hybrid. Certainly one cannot take simple $\Gamma$-traces of $\phi^{{\mathtt a}_1\ldots{\mathtt a}_n}_A$ because ${\mathtt a},{\mathtt b},\dots$ are not
SO(10) indices, so the only option to render the tensor-spinor irreducible is to make it
traceless in its indices ${\mathtt a}_1,{\mathtt a}_2,\dots$.

The generators $J(\alpha)$ of $K(\mathfrak{e}_{10})$ are then given by combinations of an object acting on the tensor indices and gamma matrices acting on the spinor index. More precisely, we make the ansatz
\begin{align}
J(\alpha)\phi^{{\mathtt a}_1\ldots {\mathtt a}_n}_A = -2 X(\alpha)^{{\mathtt a}_1\ldots {\mathtt a}_n}{}_{{\mathtt b}_1\ldots{\mathtt b}_n} \Gamma(\alpha)_{AB} \phi^{{\mathtt b}_1\ldots {\mathtt b}_n}_B.
\end{align}
Due to the known properties~\eqref{BR2} of the $\Gamma(\alpha)$ under commutation, checking the consistency relations~\eqref{GR2} then can be reduced to checking the following conditions on the tensors $X(\alpha)$ for real roots \cite{Kleinschmidt:2013eka}
\begin{align}
\label{BR3}
\left\{ X(\alpha)\,,\, X(\beta) \right\} &= \frac12  X(\alpha\pm \beta),&&\textrm{if $\alpha\cdot\beta=\mp 1$},&\nonumber\\
\left[ X(\alpha)\,,\, X(\beta) \right] &= 0,&&\textrm{if $\alpha\cdot\beta=0$}.&
\end{align}
Note that there is no $\epsilon_{\alpha,\beta}$ in these relations as it is already taken care of by the $\Gamma(\alpha)$. The Dirac-spinor corresponds to the solution $X(\alpha) = \frac14$ to these equations.

Another $K(\mathfrak{e}_{10})$ representation that has been known from supergravity considerations is the case $n=1$ that corresponds to the $D=11$ gravitino and has dimension $320$~\cite{Damour:2005zs,deBuyl:2005sch,Damour:2006xu}. In our language it corresponds to the solution
\begin{align}
X(\alpha)^{\mathtt a}{}_{\mathtt b} = -\frac12 \alpha^{\mathtt a}\alpha_{\mathtt b} + \frac14 \delta^{\mathtt a}_{\mathtt b},
\end{align}
where $\alpha^{\mathtt a}$ are the components of the root $\alpha$ with respect to the basis $e_{\mathtt a}$, i.e., $\alpha=\sum_{{\mathtt a}} \alpha^{\mathtt a} e_{\mathtt a}$. `Typewriter font' indices are raised and lowered with the Lorentzian $G_{{\mathtt a}{\mathtt b}}$.

For the gravitino (or vector-spinor) one can find a rewriting in terms of pure $\mf{so}(10)$ representation by letting\cite{Damour:2009zc}
\begin{align}
\psi^a_A = \sum_B \Gamma^a_{AB} \phi^a_B\quad\quad\textrm{(no sum on $a$)}.
\end{align}
The object on the left is then a standard vector-spinor of $\mf{so}(10)$. A similar simple and explicit rewriting into $\mf{so}(10)$ representations is not known for the new representations we discuss below.

We also note that due to the unfaithfulness of the representations, one obtains (infinite-dimensional) ideals in $K(\mathfrak{e}_{10})$, leading to the result that $K(\mathfrak{e}_{10})$ is not a simple Lie algebra. The quotient Lie algebras $\mf{q}$ of $K(\mathfrak{e}_{10})$ by the ideals of the ${\bf 32}$ and ${\bf 320}$ have been analysed and are given by $\mf{q}_{\bf 32} \cong \mf{so}(32)$ and $\mf{q}_{\bf 320}\cong \mf{so}(288,32)$. It may seem surprising that the `compact' $K(\mathfrak{e}_{10})$ admits a non-compact quotient in the ${\bf 320}$ representation but this is not a contradiction due to the infinite-dimensionality of $K(\mathfrak{e}_{10})$. For the higher spin representations below, the quotients have not been worked out.

\section{Higher spin representations}

In Ref.~\cite{Kleinschmidt:2013eka} two further solutions to~\eqref{BR3} were found that correspond to the values $n=2$ and $n=3$ (corresponding to spin $s=\frac52$ and
$s=\frac72$, respectively\cite{fn:spin}).
These representations go beyond supergravity as there appears
to be no supergravity model from which they would be derivable. For spin $s=\frac52$
($n=2$) the corresponding tensors are given by
\begin{align}
\label{X52}
X(\alpha)^{{\mathtt a}_1{\mathtt a}_2}{}_{{\mathtt b}_1{\mathtt b}_2} = \frac12 \alpha^{{\mathtt a}_1} \alpha^{{\mathtt a}_2} \alpha_{{\mathtt b}_1}\alpha_{{\mathtt b}_2} -\alpha^{({\mathtt a}_1}_{\phantom{{\mathtt a}_1)}} \delta^{{\mathtt a}_2)}_{({\mathtt b}_1} \alpha_{{\mathtt b}_2)}^{\phantom{{\mathtt a}_1)}} + \frac14 \delta^{({\mathtt a}_1}_{{\mathtt b}_1} \delta^{{\mathtt a}_2)}_{{\mathtt b}_2}
\end{align}
and for $n=3$ (spin-$\frac72$) by
\begin{align}
\label{X72}
X(\alpha)^{{\mathtt a}_1{\mathtt a}_2{\mathtt a}_3}{}_{{\mathtt b}_1{\mathtt b}_2{\mathtt b}_3}& =-\frac13 \alpha^{{\mathtt a}_1} \alpha^{{\mathtt a}_2}\alpha^{{\mathtt a}_3} \alpha_{{\mathtt b}_1}\alpha_{{\mathtt b}_2}\alpha_{{\mathtt b}_3}
+\frac32 \alpha^{({\mathtt a}_1} \alpha^{{\mathtt a}_2}\delta^{{\mathtt a}_3)}_{({\mathtt b}_1} \alpha_{{\mathtt b}_2}\alpha_{{\mathtt b}_3)}
-\frac32\alpha^{({\mathtt a}_1}\delta^{{\mathtt a}_2}_{({\mathtt b}_1} \delta^{{\mathtt a}_3)}_{{\mathtt b}_2\phantom{)}}\alpha_{{\mathtt b}_3)}^{\phantom{)}}&\nonumber\\
&\quad +\frac14 \delta^{({\mathtt a}_1}_{({\mathtt b}_1}\delta^{{\mathtt a}_2\phantom{)}}_{{\mathtt b}_2\phantom{)}}\delta^{{\mathtt a}_3)}_{{\mathtt b}_3)}
+\frac1{12}(2-\sqrt{3}) \alpha^{({\mathtt a}_1}  G^{{\mathtt a}_2{\mathtt a}_3)}G_{({\mathtt b}_1{\mathtt b}_2}\alpha_{{\mathtt b}_3)}&\\
&\quad+\frac1{12}(-1+\sqrt{3})\left( \alpha^{({\mathtt a}_1}\alpha^{{\mathtt a}_2}\alpha^{{\mathtt a}_3)}G_{({\mathtt b}_1{\mathtt b}_2}\alpha_{{\mathtt b}_3)}
+\alpha^{({\mathtt a}_1}  G^{{\mathtt a}_2{\mathtt a}_3)}\alpha_{({\mathtt b}_1}\alpha_{{\mathtt b}_2}\alpha_{{\mathtt b}_3)}\right).\nonumber
\end{align}
These expressions can be found and verified analytically. We have also extended the search for solutions of this type for $n\leq 10$ with the ansatz above but have not found any additional
solutions so far.

The spin-$\frac52$ solution as given is of dimension $\frac{10\times 11}{2} \times 32= 1760$. It turns out that this representation is reducible since the subspace spanned by the trace $G_{{\mathtt a}{\mathtt b}} \phi^{{\mathtt a}{\mathtt b}}_A$ is invariant. This trace transforms in the spin-$\frac12$ representation of dimension $32$, leaving an irreducible $1728$-dimensional representation of $K(\mathfrak{e}_{10})$.
By contrast, the spin-$\frac72$ representation of dimension $\frac{10\times 11\times 12}{6}\times 32 = 7040$ is irreducible as given.

In the next two sections, we investigate further properties of the new higher spin representations.

\section{Projectors and Weyl group action}

The $K(\mathfrak{e}_{10})$ generators $J(\alpha)$ are defined for all positive roots $\alpha$ of $\mathfrak{e}_{10}$. As the roots $\alpha$ are space-like elements in a Lorentzian ten-dimensional space, they have a stabiliser of type $\mf{so}(1,8)\subset \mf{so}(1,9)$. This stability algebra can be used to decompose the `polarisation tensor' $X(\alpha)$ into irreducible pieces for a fixed $\alpha$. The irreducible
$\mf{so}(1,8)$ terms are given by projectors $\Pi^{(j)}(\alpha)$,
 such that tensor $X(\alpha)$ can be expressed in terms of these projectors.\cite{fn:proj} This rewriting
greatly facilitates the exponentiation of the corresponding matrices, and
will make it easy to work out the exponentiated (Weyl) group actions.

\subsection{Projectors for spin-$\frac52$}

For $n=2$, the polarisation tensor $X(\alpha)^{{\mathtt a}_1{\mathtt a}_2}{}_{{\mathtt b}_1{\mathtt b}_2}$ lies in the reducible ${\bf 55}$ of $\mf{so}(1,9)$, where we work for simplicity with the reducible representation of dimension $1760$ given in~\eqref{X52}. The decomposition of $X(\alpha)$ under the regularly embedded $\mf{so}(1,8)$ is
\begin{align}
{\bf 55} \rightarrow {\bf 54} \oplus {\bf 1} \rightarrow ({\bf 44} \oplus {\bf 9} \oplus {\bf 1'}) \oplus {\bf 1}.
\end{align}
The splitting of the singlets here has been done in such a way that ${\bf 1}$ corresponds to the $\mf{so}(1,9)$ singlet corresponding to the trace with $G_{{\mathtt a}{\mathtt b}}$.
One can check that the following are complete orthonormal projectors on the various pieces
\begin{align}
\Pi^{({\bf 44})}(\alpha)^{{\mathtt a}_1{\mathtt a}_2}{}_{{\mathtt b}_1{\mathtt b}_2} &= \frac29 \alpha^{{\mathtt a}_1} \alpha^{{\mathtt a}_2} \alpha_{{\mathtt b}_1}\alpha_{{\mathtt b}_2}
   - \alpha^{({\mathtt a}_1} \delta^{{\mathtt a}_2)}_{({\mathtt b}_1} \alpha_{{\mathtt b}_2)}
   + \delta^{({\mathtt a}_1}_{{\mathtt b}_1} \delta^{{\mathtt a}_2)}_{{\mathtt b}_2} &\nonumber\\
&\quad+\frac1{18} \left(\alpha^{{\mathtt a}_1} \alpha^{{\mathtt a}_2} G_{{\mathtt b}_1{\mathtt b}_2} + G^{{\mathtt a}_1{\mathtt a}_2} \alpha_{{\mathtt b}_1} \alpha_{{\mathtt b}_2}\right)
   -\frac19 G^{{\mathtt a}_1{\mathtt a}_2} G_{{\mathtt b}_1{\mathtt b}_2},&\nonumber\\
\Pi^{({\bf 9})}(\alpha)^{{\mathtt a}_1{\mathtt a}_2}{}_{{\mathtt b}_1{\mathtt b}_2} &= -\frac12 \alpha^{{\mathtt a}_1} \alpha^{{\mathtt a}_2} \alpha_{{\mathtt b}_1}\alpha_{{\mathtt b}_2} +  \alpha^{({\mathtt a}_1} \delta^{{\mathtt a}_2)}_{({\mathtt b}_1} \alpha_{{\mathtt b}_2)},\\
\tilde{\Pi}^{({\bf 1})}(\alpha)^{{\mathtt a}_1{\mathtt a}_2}{}_{{\mathtt b}_1{\mathtt b}_2} &= \frac1{10}G^{{\mathtt a}_1{\mathtt a}_2} G_{{\mathtt b}_1{\mathtt b}_2},&\nonumber\\
\tilde{\Pi}^{({\bf 1'})}(\alpha)^{{\mathtt a}_1{\mathtt a}_2}{}_{{\mathtt b}_1{\mathtt b}_2} &= \frac{5}{18} \alpha^{{\mathtt a}_1} \alpha^{{\mathtt a}_2} \alpha_{{\mathtt b}_1}\alpha_{{\mathtt b}_2} -\frac1{18} \left(\alpha^{{\mathtt a}_1} \alpha^{{\mathtt a}_2} G_{{\mathtt b}_1{\mathtt b}_2} + G^{{\mathtt a}_1{\mathtt a}_2} \alpha_{{\mathtt b}_1} \alpha_{{\mathtt b}_2}\right)&\nonumber\\
&\quad    +\frac1{90} G^{{\mathtt a}_1{\mathtt a}_2} G_{{\mathtt b}_1{\mathtt b}_2}.\nonumber
\end{align}
In terms of these, the tensor $X(\alpha)$ takes the form
\begin{align}
X(\alpha)^{{\mathtt a}_1{\mathtt a}_2}{}_{{\mathtt b}_1{\mathtt b}_2}
&= \left( \frac14 \tilde{\Pi}^{({\bf 1})}(\alpha) +\frac14\tilde{\Pi}^{({\bf 1'})}(\alpha)-\frac34 \Pi^{({\bf 9})}(\alpha) +\frac14 \Pi^{({\bf 44})}(\alpha) \right){}^{{\mathtt a}_1{\mathtt a}_2}{}_{{\mathtt b}_1{\mathtt b}_2}.
\end{align}
What is important here is that the coefficients of all projectors are of the form $\frac{2k+1}{4}$ with $k\in\mathbb{Z}$. This implies that when one constructs the `Weyl group' generator
\begin{align}
w_\alpha = e^{\frac{\pi}{2} J(\alpha)}
\end{align}
acting in the representation is idempotent in the eighth power. Weyl group has been put into inverted commas above because this is more correctly an element of a covering of the Weyl group that has been dubbed the spin-extended Weyl group~\cite{Damour:2009zc,GHKW}. Acting on spinor representations, the characteristic feature is that only the eighth power $w_\alpha^8=1\!\!1$ whereas one normally has the fourth power for the covering of the Weyl on bosonic representations~\cite{Kac}.

\subsection{Projectors for spin-$\frac72$}

In this case, the polarisation tensor $X(\alpha)^{{\mathtt a}_1{\mathtt a}_2{\mathtt a}_3}{}_{{\mathtt b}_1{\mathtt b}_2{\mathtt b}_3}$ is in the (reducible) totally symmetric ${\bf 220}$ of $\mf{so}(1,9)$. This decomposes under $\mf{so}(1,8)$ as
\begin{align}
{\bf 220} \rightarrow {\bf 210} \oplus {\bf 10} \rightarrow \left( {\bf 156} \oplus {\bf 44} \oplus {\bf 9} \oplus {\bf 1}\right) \oplus \left({\bf 9} \oplus  {\bf 1}\right).
\end{align}
There are two singlets and two vectors of $\mf{so}(1,8)$ appearing in the decomposition and some associated freedom in constructing the orthonormal projectors. We choose a particular combination of these representations as follows~\cite{ProjNote}
\begin{align}
\Pi^{({\bf 156})}(\alpha)^{{\mathtt a}_1{\mathtt a}_2{\mathtt a}_3}{}_{{\mathtt b}_1{\mathtt b}_2{\mathtt b}_3} &= -\frac1{11} \alpha^{{\mathtt a}_1} \alpha^{{\mathtt a}_2}\alpha^{{\mathtt a}_3} \alpha_{{\mathtt b}_1}\alpha_{{\mathtt b}_2}\alpha_{{\mathtt b}_3}
  +\frac{15}{22}\alpha^{({\mathtt a}_1} \alpha^{{\mathtt a}_2} \delta^{{\mathtt a}_3)}_{({\mathtt b}_1} \alpha_{{\mathtt b}_2}\alpha_{{\mathtt b}_3)}\nonumber\\
&\quad   -\frac32\alpha^{({\mathtt a}_1} \delta^{{\mathtt a}_2}_{({\mathtt b}_1} \delta^{{\mathtt a}_3)}_{{\mathtt b}_2} \alpha_{{\mathtt b}_3)}
 +\delta^{({\mathtt a}_1}_{({\mathtt b}_1} \delta^{{\mathtt a}_2}_{{\mathtt b}_2} \delta^{{\mathtt a}_3)}_{{\mathtt b}_3)}\nonumber\\
&\quad   -\frac3{44}\left(\alpha^{{\mathtt a}_1} \alpha^{{\mathtt a}_2} \alpha^{{\mathtt a}_3} \alpha_{({\mathtt b}_1} G_{{\mathtt b}_2{\mathtt b}_3)} + \alpha^{({\mathtt a}_1} G^{{\mathtt a}_2{\mathtt a}_3)} \alpha_{{\mathtt b}_1}\alpha_{{\mathtt b}_2}\alpha_{{\mathtt b}_3}\right)\nonumber\\
&\quad + \frac3{22}\left( \alpha^{({\mathtt a}_1} \alpha^{{\mathtt a}_2} \delta^{{\mathtt a}_3)}_{({\mathtt b}_1} G_{{\mathtt b}_2{\mathtt b}_3)}
  + G^{({\mathtt a}_1{\mathtt a}_2} \delta^{{\mathtt a}_3)}_{({\mathtt b}_1} \alpha_{{\mathtt b}_2} \alpha_{{\mathtt b}_3)}\right) \nonumber\\
&\quad  -\frac3{11} G^{({\mathtt a}_1{\mathtt a}_2} \delta^{{\mathtt a}_3)}_{({\mathtt b}_1} G_{{\mathtt b}_2{\mathtt b}_3)} +\frac3{22}\alpha^{({\mathtt a}_1} G^{{\mathtt a}_2{\mathtt a}_3)} G_{({\mathtt b}_1{\mathtt b}_2} \alpha_{{\mathtt b}_3)}\nonumber\\
\Pi^{({\bf 44})}(\alpha)^{{\mathtt a}_1{\mathtt a}_2{\mathtt a}_3}{}^{{\mathtt b}_1{\mathtt b}_2{\mathtt b}_3} &= \frac13 \alpha^{{\mathtt a}_1} \alpha^{{\mathtt a}_2}\alpha^{{\mathtt a}_2} \alpha_{{\mathtt b}_1}\alpha_{{\mathtt b}_2}\alpha_{{\mathtt b}_3}
  -\frac32\alpha^{({\mathtt a}_1} \alpha^{{\mathtt a}_2} \delta^{{\mathtt a}_3)}_{({\mathtt b}_1} \alpha_{{\mathtt b}_2}\alpha_{{\mathtt b}_3)}\nonumber\\
&\quad  +\frac32\alpha^{({\mathtt a}_1} \delta^{{\mathtt a}_2}_{({\mathtt b}_1} \delta^{{\mathtt a}_3)}_{{\mathtt b}_2} \alpha_{{\mathtt b}_3)}
   -\frac1{6}\alpha^{({\mathtt a}_1} G^{{\mathtt a}_2{\mathtt a}_3)} G_{({\mathtt b}_1{\mathtt b}_2} \alpha_{{\mathtt b}_3)}\nonumber\\
&\quad
   +\frac1{12}\left(\alpha^{{\mathtt a}_1} \alpha^{{\mathtt a}_2} \alpha^{{\mathtt a}_3} \alpha_{({\mathtt b}_1} G_{{\mathtt b}_2{\mathtt b}_3)} + \alpha^{({\mathtt a}_1} G^{{\mathtt a}_2{\mathtt a}_3)} \alpha_{{\mathtt b}_1}\alpha_{{\mathtt b}_2}\alpha_{{\mathtt b}_3}\right)
\end{align}
for the (unique) two biggest representations,
\begin{align}
\Pi^{({\bf 9})}(\alpha)^{{\mathtt a}_1{\mathtt a}_2{\mathtt a}_3}{}_{{\mathtt b}_1{\mathtt b}_2{\mathtt b}_3} &= -\frac9{22}\alpha^{{\mathtt a}_1} \alpha^{{\mathtt a}_2}\alpha^{{\mathtt a}_3} \alpha_{{\mathtt b}_1}\alpha_{{\mathtt b}_2}\alpha_{{\mathtt b}_3}
  +\frac{9}{11}\alpha^{({\mathtt a}_1} \alpha^{{\mathtt a}_2} \delta^{{\mathtt a}_3)}_{({\mathtt b}_1} \alpha_{{\mathtt b}_2}\alpha_{{\mathtt b}_3)}\nonumber\\
&\quad
   +\frac3{44}\left(\alpha^{{\mathtt a}_1} \alpha^{{\mathtt a}_2} \alpha^{{\mathtt a}_3} \alpha_{({\mathtt b}_1} G_{{\mathtt b}_2{\mathtt b}_3)} + \alpha^{({\mathtt a}_1} G^{{\mathtt a}_2{\mathtt a}_3)} \alpha_{{\mathtt b}_1}\alpha_{{\mathtt b}_2}\alpha_{{\mathtt b}_3}\right)\nonumber\\
&\quad - \frac3{22}\left( \alpha^{({\mathtt a}_1} \alpha^{{\mathtt a}_2} \delta^{{\mathtt a}_3)}_{({\mathtt b}_1} G_{{\mathtt b}_2{\mathtt b}_3)}  + G^{({\mathtt a}_1{\mathtt a}_2} \delta^{{\mathtt a}_3)}_{({\mathtt b}_1} \alpha_{{\mathtt b}_2} \alpha_{{\mathtt b}_3)}\right) \nonumber\\
&\quad  +\frac1{44} G^{({\mathtt a}_1{\mathtt a}_2} \delta^{{\mathtt a}_3)}_{({\mathtt b}_1} G_{{\mathtt b}_2{\mathtt b}_3)}
  -\frac1{88}\alpha^{({\mathtt a}_1} G^{{\mathtt a}_2{\mathtt a}_3)} G_{({\mathtt b}_1{\mathtt b}_2} \alpha_{{\mathtt b}_3)}\nonumber\\
\Pi^{({\bf 9}')}(\alpha)^{{\mathtt a}_1{\mathtt a}_2{\mathtt a}_3}{}_{{\mathtt b}_1{\mathtt b}_2{\mathtt b}_3} &=   \frac1{4} G^{({\mathtt a}_1{\mathtt a}_2} \delta^{{\mathtt a}_3)}_{({\mathtt b}_1} G_{{\mathtt b}_2{\mathtt b}_3)}
  -\frac1{8}\alpha^{({\mathtt a}_1} G^{{\mathtt a}_2{\mathtt a}_3)} G_{({\mathtt b}_1{\mathtt b}_2} \alpha_{{\mathtt b}_3)}
\end{align}
for the vectors and finally for the singlets
\begin{align}
\Pi^{({\bf 1})}(\alpha)^{{\mathtt a}_1{\mathtt a}_2{\mathtt a}_3}{}_{{\mathtt b}_1{\mathtt b}_2{\mathtt b}_3} &= \frac1{12} \alpha^{{\mathtt a}_1} \alpha^{{\mathtt a}_2}\alpha^{{\mathtt a}_3} \alpha_{{\mathtt b}_1}\alpha_{{\mathtt b}_2}\alpha_{{\mathtt b}_3}&\nonumber\\
&\quad   +\frac1{24}(-1-\sqrt{3})\left(\alpha^{{\mathtt a}_1} \alpha^{{\mathtt a}_2} \alpha^{{\mathtt a}_3} \alpha_{({\mathtt b}_1} G_{{\mathtt b}_2{\mathtt b}_3)} + \alpha^{({\mathtt a}_1} G^{{\mathtt a}_2{\mathtt a}_3)} \alpha_{{\mathtt b}_1}\alpha_{{\mathtt b}_2}\alpha_{{\mathtt b}_3}\right)&\nonumber\\
&\quad   +\frac1{24}(2+\sqrt{3})\alpha^{({\mathtt a}_1} G^{{\mathtt a}_2{\mathtt a}_3)} G_{({\mathtt b}_1{\mathtt b}_2} \alpha_{{\mathtt b}_3)}\nonumber\\
\Pi^{({\bf 1}')}(\alpha)^{{\mathtt a}_1{\mathtt a}_2{\mathtt a}_3}{}_{{\mathtt b}_1{\mathtt b}_2{\mathtt b}_3} &= \frac1{12} \alpha^{{\mathtt a}_1}\alpha^{{\mathtt a}_2}\alpha^{{\mathtt a}_3} \alpha_{{\mathtt b}_1}\alpha_{{\mathtt b}_2}\alpha_{{\mathtt b}_3}&\nonumber\\
&\quad   +\frac1{24}(-1+\sqrt{3})\left(\alpha^{{\mathtt a}_1} \alpha^{{\mathtt a}_2} \alpha^{{\mathtt a}_3} \alpha_{({\mathtt b}_1} G_{{\mathtt b}_2{\mathtt b}_3)} + \alpha^{({\mathtt a}_1} G^{{\mathtt a}_2{\mathtt a}_3)} \alpha_{{\mathtt b}_1}\alpha_{{\mathtt b}_2}\alpha_{{\mathtt b}_3}\right)&\nonumber\\
&\quad   +\frac1{24}(2-\sqrt{3})\alpha^{({\mathtt a}_1} G^{{\mathtt a}_2{\mathtt a}_3)} G_{({\mathtt b}_1{\mathtt b}_2} \alpha_{{\mathtt b}_3)}
\end{align}
The tensor $X(\alpha)$ reads as follows in this basis
\begin{align}
X(\alpha)^{{\mathtt a}_1{\mathtt a}_2{\mathtt a}_3}{}_{{\mathtt b}_1{\mathtt b}_2{\mathtt b}_3}
&= \Bigg( \frac54\Pi^{({\bf 1})}(\alpha)-\frac34\Pi^{({\bf 1}')}(\alpha) +\frac14\Pi^{({\bf 9})}(\alpha)+\frac14 \Pi^{({\bf 9}')}(\alpha) &\nonumber\\
&\quad\quad - \frac34\Pi^{({\bf 44})}(\alpha)+\frac14 \Pi^{({\bf 156})}(\alpha) \Bigg){}^{{\mathtt a}_1{\mathtt a}_2{\mathtt a}_3}{}_{{\mathtt b}_1{\mathtt b}_2{\mathtt b}_3}.
\end{align}
Again, it is important that the coefficients of all the orthonormal projectors are of the form $\frac{2k+1}{4}$ such that we are dealing with a genuine fermionic representation of $K(E_{10})$.

\section{Branching under subalgebras}

The infinite-dimensional Lie algebra $K(\mathfrak{e}_{10})$ has infinitely many finite-dimensional
subalgebras.\cite{fn:sub}
Of these are of particular interest to us the following, all of which can be obtained by deleting a single node from the $\mathfrak{e}_{10}$ Dynkin diagram:\\[2mm]
\begin{tabular}{p{3mm}p{30mm}p{30mm}p{50mm}}
$(a)$ & $\mf{so}(10)$ & deleting node $10$ & SUGRA in $D=11$\\
$(b)$ & $\mf{so}(2)\oplus \mf{so}(16)$ & deleting node $2$ & SUGRA in $D=3$\\
$(c)$ & $\mf{so}(9)\oplus \mf{so}(2)$ & deleting node $8$ & IIB SUGRA in $D=10$\\
$(d)$ & $\mf{so}(9)\oplus \mf{so}(9)$ & deleting node $9$ & Doubled SUGRA in $D=10$
\end{tabular}
\vspace{2mm}

The last case requires some explanation. In Ref.~\cite{Kleinschmidt:2004dy} the decomposition of $\mathfrak{e}_{10}$ under its $\mf{so}(9,9)$ subalgebra was studied and shown to correspond to both type IIA and type IIB theory since the Ramond--Ramond potentials occurred in a spinor representation of  $\mf{so}(9,9)$ that can be read either as all even or all odd forms; similarly, the fermions arrange themselves correctly for the two theories~\cite{Kleinschmidt:2006tm}. In investigations of double field theory the same structure appears~\cite{Jeon:2011vx} and we have therefore dubbed this T-duality agnostic decomposition as `doubled SUGRA.'

There are some additional subtleties associated with the global assignment of fermionic and bosonic representations at the group level. More precisely, the $\mf{so}(16)$ is the Lie algebra of $Spin(16)/\mathbb{Z}_2$. The $\mathbb{Z}_2$ is not diagonally embedded in the center $\mathbb{Z}_2\times \mathbb{Z}_2$ but as one of the factors; this entails that the representations ${\bf 16}_v$ and
${\bf 128}_c$ are spinorial (that is, they transform with a factor $(-1)$ upon rotation by $2\pi$),
whereas the ${\bf 128}_s$ is tensorial~\cite{Keurentjes:2003yu}. Moreover, the ${\bf 16}$ spinor of $Spin(9)=[Spin(9)\times Spin(9)]_{\textrm{diag}}$ is identified with the (spinorial) ${\bf 16}_v$ of $Spin(16)$. The diagonal $Spin(9)$ also lies as a regular subgroup in $Spin(9)$ as it corresponds to the dimensional reduction from $D=11$ to $D=10$ (over a spatial direction).

The decompositions of the spin-$\frac12$ and spin-$\frac32$ representations were already given in Ref.~\cite{Kleinschmidt:2006tm}, while the decompositions of the new higher spin
representations under the various subalgebras have not been given previously.
To find the relevant decompositions for spin-$\frac52$ and spin-$\frac72$
is actually rather involved, and can only be done on a computer. The
main problem here is that the $K(E_{10})$ representations are not highest or lowest weight representations (it is not even clear whether $K(E_{10})$ admits any analog of such representations),
so the customary tools of representation theory cannot be applied. However, the subrepresentations obtained after descending to any finite-dimensional subgroup
{\em are} highest or lowest
weight representations, so given any of the above subgroups, one must first identify the
corresponding highest or lowest weights. For instance, for the spin-$\frac72$ representation
this requires (amongst other things) the (simultaneous) diagonalisation of various 7040 $\times$ 7040 matrices.
It seems clear that for yet higher dimensional realisations such a procedure would become impractical very quickly unless better methods are developed.

\subsection{Branching the spin $s=\frac12$ and $s=\frac32$ representations}

These were already understood in previous work \cite{Kleinschmidt:2006tm}.
The fractions $\frac12$ and $\frac32$ in the decompositions $(b)$ and $(c)$ below correspond to the $\mf{so}(2)\cong\mf{u}(1)$ charges. In these cases all the representations form doublets of $\mf{so}(2)$ that can also be thought of as complex one-dimensional representations of $\mf{u}(1)$. This has to be taken into account when checking the dimension count of the decompositions.
\begin{align}
{\bf 32}\quad &\stackrel{a}\longrightarrow \quad {\bf 32}   \nonumber\\[2mm]
        &\stackrel{b}{\longrightarrow} \quad \left(\frac12, {\bf 16}_v\right)  \nonumber\\[2mm]
        &\stackrel{c}{\longrightarrow} \quad \left({\bf 16},\frac12\right)\nonumber\\[2mm]
        &\stackrel{d}{\longrightarrow} \quad ({\bf 16},{\bf 1}) \oplus
              ({\bf 1},{\bf 16})
 \end{align}
and\allowdisplaybreaks{
\begin{align}
{\bf 320} \quad &\stackrel{a}\longrightarrow \quad {\bf 288} \oplus {\bf 32} \nonumber\\[2mm]
     &\stackrel{b}\longrightarrow \quad \left( \frac12,{\bf 128}_c\right)
\oplus \left(\frac12, {\bf16}_v\right)  \oplus \left(\frac32, {\bf16}_v\right)   \nonumber\\[2mm]
        &\stackrel{c}{\longrightarrow} \quad \left({\bf 16}, \frac32\right) \oplus
              \left({\bf 128}, \frac12\right) \oplus
              \left({\bf 16}, \frac12\right)
\nonumber\\[2mm]
  &\stackrel{d}{\longrightarrow} \quad \left({\bf 9}, {\bf 16}\right)\oplus \left({\bf 16}, {\bf 9} \right)
      \oplus  \left({\bf 1}, {\bf 16} \right) \oplus \left({\bf 16}, {\bf 1}\right)
 \end{align}
Since these are the `physical' fermions of maximal supergravity, let us briefly comment on their interpretation.}

The ${\bf 32}$ representation of $K(\mf{e}_{10})$ corresponds to the $32$ supersymmetry generators of maximal supergravity. We see that in the decomposition $(a)$ relevant for $D=11$ supergravity one obtains a single generator consistent with $\mathcal{N}=1$ supersymmetry. In the decomposition $(b)$ one obtains an $\mf{so}(2)$ doublet of sixteen generators (in the vector of $\mf{so}(16)$; the $\mf{so}(2)$ corresponds to the spatial part of the $\mf{so}(1,2)$ Lorentz symmetry of which the doublet is the irreducible spinor and the sixteen components correspond to  $\mf{so}(16)$ R-symmetry of maximal $\mathcal{N}=16$ supersymmetry in $D=3$ dimensions. The decomposition $(c)$ gives an $\mf{so}(2)$ R-symmetry doublet of spinors of the spatial $\mf{so}(9)$ Lorentz symmetry in $D=10$ in agreement with the supersymmetry generators of chiral type IIB supergravity. More specifically,
the appearance of this U(1) effectively `complexifies' the SO(9) representation, in line
with the chirality of the type IIB fermions. The last decomposition $(d)$ is consistent
with a type IIA formulation of doubled supergravity~\cite{Kleinschmidt:2004dy,Jeon:2011vx}.

The decompositions of the ${\bf 320}$ representation of $K(\mf{e}_{10})$ can be interpreted similarly~\cite{Kleinschmidt:2006tm}. For example, the decomposition $(b)$ gives the $128$ physical fermions in $D=3$ together with components associated with the non-propagating gravitino that is needed when formulating $\mathcal{N}=16$ supergravity in $D=3$. We also note again that in the type IIB decomposition $(c)$ one always obtains doublets of the R-symmetry $\mf{so}(2)$, in accord
with the chirality of the underlying fermionic multiplets.

\subsection{Branching of the spin-$\frac52$ representation}

The decomposition under the various subalgebras is
\begin{align}
{\bf 1728} &\stackrel{a}{\longrightarrow} {\bf 1120} \,\oplus \, 2\times {\bf 288}
      \,\oplus \, {\bf32}  \nonumber\\[2mm]
        &\stackrel{b}{\longrightarrow} \left(\frac12 , {\bf 560}_v \right) \oplus
        \left(\frac12 ,{\bf 128}_c \right)
              \oplus 2\times \left(\frac12 , {\bf 16}_v \right) \oplus \left(\frac32 , {\bf 128}_c, \right)
              \oplus \left(\frac32 , {\bf 16}_v \right)  \nonumber\\[2mm]
        &\stackrel{c}{\longrightarrow} \left({\bf 432},\frac12\right) \oplus
        2\times \left({\bf 128},\frac12\right) \oplus 2\times \left({\bf 16},\frac12\right)
              \oplus \left({\bf 128},\frac32\right) \oplus \left({\bf 16},\frac32\right)\nonumber\\[2mm]
        &\stackrel{d}{\longrightarrow} ({\bf 36}, {\bf 16})\,\oplus\,
           ({\bf 16}, {\bf 36})\,\oplus\,
           ({\bf 9}, {\bf 16})\,\oplus\,
           ({\bf 16},{\bf 9})\,\oplus\nonumber\\[2mm]
&\quad\quad\oplus           ({\bf 128}, {\bf 1})\,\oplus\,
           ({\bf 1}, {\bf 128})\,\oplus\,
           ({\bf 1} , {\bf 16}) \, \oplus\,
              ({\bf 16}, {\bf 1})
 \end{align}
From the $\mf{so}(10)$ decomposition we see that the space-time spin of this $K(\mathfrak{e}_{10})$ representation is not really higher than $3/2$ since the ${\bf 1120}$ corresponds to an \textit{anti-}symmetric tensor-spinor of $\mf{so}(10)$ with two tensor indices. The ${\bf 560}_v$ of $\mf{so}(16)$ that arises is the anti-symmetric three-form. Similar to the ${\bf 16}_v$ discussed above, this is actually a spinorial representation with the correct assignment when lifted to the group $Spin(16)/\mathbb{Z}_2$. The ${\bf 432}$ of $\mf{so}(9)$ that arises in case $(c)$ is the tensor-spinor with two antisymmetric indices.

\subsection{Branching of the spin-$\frac72$ representation}

Under the subalgebras listed above, the $K(\mathfrak{e}_{10})$ spin-$\frac72$ representation
of dimension $7040$ decomposes as
\begin{align}
{\bf 7040} &\stackrel{a}{\longrightarrow} {\bf 2400} \oplus {\bf 1440} \oplus 2 \times {\bf 1120} \oplus 3\times {\bf 288}  \oplus 3\times {\bf 32} \nonumber\\[2mm]
              &\stackrel{b}{\longrightarrow} \left(\frac12,{\bf 1920}_s\right)
                   \oplus \left(\frac32,{\bf 560}_v\right) \oplus \left(\frac12,{\bf 560}_v\right)
                   \oplus \left(\frac32,{\bf 128}_c\right) \oplus 2\times \left(\frac12,{\bf 128}_c\right)\nonumber\\
                 &\quad\quad  \oplus \left(\frac52,{\bf 16}_v\right) \oplus 2\times \left(\frac32,{\bf 16}_v\right)
                     \oplus 3\times \left(\frac12,{\bf 16}_v\right)
               \nonumber\\[2mm]
              &\stackrel{c}{\longrightarrow}
                  \left({\bf 768},\frac12\right) \oplus \left({\bf 576},\frac12\right)
                  \oplus \left({\bf 432},\frac32\right) \oplus 2\times \left({\bf 432},\frac12\right)\nonumber\\
               &\quad\quad     \oplus 2\times \left({\bf 128},\frac32\right) \oplus 4\times \left({\bf 128},\frac12\right)
                  \oplus \left({\bf 16},\frac52\right) \oplus 2\times \left({\bf 16},\frac32\right)
                  \oplus 4\times \left({\bf 16},\frac12\right)\nonumber\\[2mm]
              &\stackrel{d}{\longrightarrow}  ({\bf 128}, {\bf 9}) \oplus ({\bf 128}, {\bf 1})
                  \oplus ({\bf 16}, {\bf 84}) \oplus ({\bf 16}, {\bf 36})
                  \oplus 2\times ({\bf 16}, {\bf 9}) \oplus 2\times ({\bf 16}, {\bf 1})\nonumber\\[2mm]
                &\quad\quad\oplus ({\bf 9}, {\bf 128}) \oplus ({\bf 1}, {\bf 128})
                  \oplus ({\bf 84}, {\bf 16}) \oplus ({\bf 36}, {\bf 16})
                  \oplus 2\times ({\bf 9}, {\bf 16}) \oplus 2\times ({\bf 1}, {\bf 16})
 \end{align}
As already mentioned, it is a non-trivial task to work out these decompositions in practice.
As a further test we have also checked that the
further decompositions of the $\mf{so}(2) \oplus \mf{so}(16)$ and $\mf{so}(10)$ representations under
their common $\mf{so}(8)$ subalgebra coincide (for $\mf{so}(16)$ this subalgebra is obtained after
descending first to the diagonal subalgebra $[\mf{so}(8) \oplus \mf{so}(8)]_{\rm diag}$). Similarly, there is another $\mf{so}(8)$ that is common to the $\mf{so}(10)$ decomposition $(a)$, to the type IIB decomposition $(c)$ and to the $\mf{so}(9)\oplus \mf{so}(9)$ decomposition in $(d)$ and that corresponds to the spatial rotations of maximal $D=9$ supergravity. The further branching of $(a)$, $(c)$ and $(d)$ to this common subgroup has been checked to be consistent. Moreover, we have verified that the common $\mf{so}(9)$ of the type IIB decomposition $(c)$ and the T-duality agnostic decomposition $(d)$ gives the same representations.

Let us finally highlight some new features arising here, that have no analog for
spin $s\leq \frac52$.
\begin{itemize}
\item  In the $\mf{so}(10)$ decomposition $(a)$ one sees the ${\bf 2400}$ that corresponds to a tensor-spinor that is antisymmetric in {\em three} tensor indices. The ${\bf 1440}$ is a tensor-spinor with two \textit{symmetric} tensor indices; since the $\mf{so}(10)$ is the spatial rotation group of $D=11$ supergravity, this means that the spin-$\tfrac72$ of $K(\mf{e}_{10})$ contains genuinely higher spin representations also from a space-time perspective!
\item Under the $\mf{so}(2)\oplus \mf{so}(16)$ decomposition $(b)$ one finds the vector-spinor of $\mf{so}(16)$ with $1920$ components. Note that consistent with the spinorial nature of the $K(E_{10})$ representation it is the ${\bf 1920}_s$ where the spinorial double-valued aspect of $Spin(16)/\mathbb{Z}_2$ is carried by the vector index and not by the $s$-type spinor index.
\item The ${\bf 768}$ appearing in the $\mf{so}(9)\oplus \mf{so}(2)$ decomposition $(c)$ is the anti-symmetric three-form tensor-spinor of $\mf{so}(9)$. By contrast the ${\bf 576}$ is a tensor-spinor with two \textit{symmetric} tensor indices and therefore this $K(\mf{e}_{10})$ representation also contains fermionic higher spin fields from the type IIB perspective.
\item The ${\bf 84}$ in the $\mf{so}(9)\oplus\mf{so}(9)$ decomposition $(d)$ is the anti-symmetric three-form of $\mf{so}(9)$; the ${\bf 36}$ is the anti-symmetric two-form already encountered above.
\end{itemize}
We also note that the $\mf{so}(2)$ eigenvalues can become larger and larger the bigger the $K(\mf{e}_{10})$ representation becomes.

\section{Outlook}

There are two pressing questions arising out of our work. The first concerns the possible physical role of the new $K(E_{10})$ representations. In particular, one may wonder whether they are of relevance to overcoming the difficulties in constructing a supersymmetric $E_{10}$ model that were encountered in~Ref.~\cite{Kleinschmidt:2014uwa}. It is conceivable that in order to make progress both
the supersymmetry constraint and the propagating fermions will have to be assigned to representations of $K(E_{10})$ different from the ones used so far (and in particular incorporate
spatial gradients in one form or another). Let us also note that one can easily couple
the new fermion representations to the bosonic $E_{10}/K(E_{10})$ sigma model, namely by adding
a Dirac-like term $\propto \Psi D_t \Psi$ to the bosonic action, where
$D_t \equiv \partial_t + \sum_{\alpha, r} Q^r(\alpha) J^r(\alpha)$ is the $K(E_{10})$ covariant
derivative, and $Q^r(\alpha)$ the $K(\mathfrak{e}_{10})$-connection as computed from the bosonic
sigma model in the standard way.
Of course, there remains the question whether one can define a new supersymmetry
that makes the combined action supersymmetric at least at low levels.

Secondly, the very existence of the two new higher spin representations for $s=\frac52$ and
$s=\frac72$ which cannot be explained from maximal supergravity, strongly suggests
that these constitute only the tip of the iceberg of the unexplored representation theory
of $K(\mathfrak{e}_{10})$. Although our (limited) search for new examples has not been successful so far,
we expect there to exist an infinite tower of such realisations of higher and
higher spin, which are less and less unfaithful with increasing spin, but which can occur
only at `sporadic' values of the spin, because the simultaneous decomposability
under all the subgroups analysed in the foregoing section puts very tight constraints
on such new representations.\cite{fn:cons} We reiterate that working out these decompositions is currently a tedious task due to the lack of general methods for studying the representation theory of $K(\mathfrak{e}_{10})$.
An explicit construction of further examples and, more
ambitiously, a systematic understanding of their structure would afford an
entirely new method to explore the root spaces associated with timelike imaginary
roots, and thus one of the main obstacles towards a better understanding of $\mathfrak{e}_{10}$. One step forward might be the understanding of the decomposition of tensor products of $K(\mathfrak{e}_{10})$ representations.
We thus hope that our investigations help to clarify the structure of this enigmatic
object and maybe also the elusive Kac--Moody algebra $\mathfrak{e}_{10}$ itself.

\section*{Acknowledgements}
AK would like to thank the organisers of the workshop on `Higher Spin Gauge Theories' for putting together a stimulating program as well as the Institute for Advanced Study of Nanyang Technical University for its generous and kind hospitality.


\section{Introduction}

This paper investigates the use of random-graph cuts to obtain empirical estimates of the perimeter of a domain $\Omega \subset D := (0,1)^d$ for $d\geq 2$.
Let $\mathbf{x}_1, \dots, \mathbf{x}_n,\ldots$ denote a sequence of independent random points uniformly distributed on the unit cube $D$  and let $V_n:=\left\{\mathbf{x}_1, \dots, \mathbf{x}_n \right\}$.

The problem of estimating the perimeter of $\Omega$ based on knowing which points of $V_n$ belong to $\Omega$ is a classical question, see \cite{ ArCuFr09, CuFrGy13, CuFrRo07, JinYuk11, Neeman, PatRod08} for recent contributions, and see Subsection \ref{Discussion} below which contains a discussion about related work.  Here we consider an estimator of the perimeter that is based on a geometric graph constructed from the point cloud $V_n$. More precisely, we select $\varepsilon_n>0$, and connect two points in the cloud if they are within distance $\varepsilon_n$ of each other; then we consider an appropriately scaled `cut' determined by the number of edges in the graph that connect points in $\Omega$ with points that belong to $\Omega^c$. This type of estimator is natural to consider, since graph cuts arise as a discretization of the perimeter in many applications such as clustering \cite{ACPP,  BLUV12, HagKah, HeinSetz, KanVemVet04, ShiMalik,  SzlamBresson,  vonLux_tutorial,  WeiChe89}. Our choice of the estimator is therefore based on its use in various statistical and machine learning applications.

We focus on estimating the approximation error of the perimeter of an arbitrary (but fixed) set $\Omega$; the error estimates that we obtain are uniform on a class of sets where certain geometric quantities are controlled (see Remark \ref{remarkUniform} below). One of the important features of our estimator is that it has a small bias. Indeed, the expectation of our estimator provides a second order approximation (in terms of the natural parameter $\varepsilon_n$) of the true perimeter of $\Omega$ under some regularity conditions on the boundary of the set (see \eqref{bias1} below); this turns out to be a sharp estimate for the bias. We also obtain precise estimates for the variance of the estimator; for these estimates to hold, we do not need any regularity assumptions on the boundary of the set $\Omega$ except that it has finite perimeter in the most general sense. Furthermore, we show that our estimator converges a.s. for remarkably sparse graphs (and indeed in settings which are
sparser than for previously considered estimators). The a.s. convergence holds
with no regularity assumptions on $\Omega$ (other than the fact that it has finite perimeter in the
most general sense). Finally, assuming some smoothness on the boundary of $\Omega$, we are able to establish (in the dense graph regime $\frac{1}{n^{1/d}} \ll \varepsilon \ll1$) the asymptotic distribution of the error.
These estimates lead to asymptotic confidence intervals (which we refer to simply as \emph{confidence intervals}) and bounds on the type I and type II errors for hypothesis tests associated to the perimeter of a set.
\normalcolor
\bigskip

\subsection{Set-up and main results}
Let us now be more precise about the setting we consider in this paper. We consider random geometric graphs with vertex set $V_n$ and radius $\varepsilon_n >0$. That is, graphs where
 $\mathbf{x}_i$ and $\mathbf{x}_j$ are connected by an edge if  $||\mathbf{x}_i- \mathbf{x}_j||\leq \varepsilon_n$. The \emph{graph cut} between $A \subseteq V_n$ and $A^c$ is given by
$$ \cut_{\varepsilon_n}(A,A^{c}) := \sum_{\mathbf{x}_i \in A}\sum_ {\mathbf{x}_j \in V \setminus A} \; \mathbf{1}_{ \{ \|\mathbf{x}_i - \mathbf{x}_j\| \leq \varepsilon_n \} }.$$
We define the \emph{graph perimeter} as a rescaling of the graph cut: For any $\Omega \subseteq D$
\begin{equation}
\GPe{\Omega} := \frac{2 }{n (n-1) \varepsilon^{d+1}_n} \cut(V_n \cap \Omega, V_n \cap \Omega^c).
\label{RescaledGraphPerimeter}
\end{equation}
See Figure 1 for an illustration of this construction.
The scaling is chosen so that $\GPe{\Omega}$ becomes a consistent estimator for the true (continuum) perimeter.
\begin{figure}[!h]
\begin{center}
{\includegraphics[width=7cm]{n200eps013.png}
\put(-180,85){\color{red} \LARGE $\Omega$}
\put(-66,85){\color{red} \LARGE $\Omega^c$}}
\caption{Edges  of the cut between $\Omega$ and $\Omega^c$ are represented by bold lines, while other edges are dashed lines. Total number of vertices is $n=200$ and connectivity radius $\varepsilon=0.13$.
}
\end{center}
\label{fig:cut1}
\end{figure}

One of our interests  lies in determining how well does $\GP{\Omega}$ estimate the relative perimeter
of $\Omega$ in $D$. We first investigate for which scaling of $\varepsilon_n$ on $n$ does the convergence hold
almost surely as $n \to \infty$.
In other words, we want to understand the relation between edge-sparsity of random geometric graphs and point-wise convergence of the graph perimeter to the continuum perimeter in the almost sure sense.
We consider this question for a very broad family of sets $\Omega \subset D$, which are only assumed to have finite relative perimeter in $D$ in the general sense of \cite{AFP}.
That is, we define the relative perimeter of $\Omega$ with respect to $D$ to be
\begin{equation} \label{perimeter}
\BV{\Omega} =  \sup \left\{  \int_{\Omega} \divergence(v) \; \mathrm{d} x \: : \; (\forall x \in D ) \;\,  \| v(x)\| \leq 1, \: \:  \:  v \in C^\infty_c(D, \mathbb{R}^d)   \right\}.
\end{equation}
If $\Omega$ has a smooth relative boundary then $\BV{\Omega}$ is nothing but the surface area of
$\partial \Omega \cap D$. We remark that the notion of the perimeter we use is more general than the notion of Hausdorff measure of the boundary, $\mathcal H^{d-1}(\partial \Omega \cap D)$, and than the Minkowski content, which are the ones more typically used in the statistics literature \cite{ArCuFr09, CuFrGy13, CuFrRo07}. In
particular, as we see below, we work with consistent nonparametric estimators in the most general setting available.

As we recall below in (\ref{eq:tri_mean} --\ref{MeanConvergingToPerimeter}), it is known that when  $\varepsilon_n \to 0$ as $n \to \infty$ then the bias of the estimator vanishes in the limit:
\begin{equation} \label{temp1}
\mathbb{E}(\GP{\Omega})  \to \sigma_{d} \BV{\Omega} \qquad \textrm{as } \qquad n \to \infty.
 \end{equation}
The scaling factor $\sigma_{d}$ satisfies
\begin{equation} \label{sigma}
 \sigma_{d}:= \int_{||z|| \leq 1} |z_1| \;\mathrm{d} z = \frac{2s_{d-2} }{(d+1)(d-1)},
\end{equation}
where $z_1$ denotes the first component of the vector $z \in \mathbb{R}^{d}$ and
$s_{d-2}$ is the area of the $(d-2)$-dimensional unit sphere (the boundary of the unit ball in $\mathbb{R}^{d-1}$).
We refer to the normalizing quantity $\sigma_{d}$ as the \emph{surface tension}.

We obtain the following estimates on the deviation of the graph perimeter $\GP{\Omega}$ from its mean.
Let
\begin{equation}\label{eq:rate_def}
f(n, \varepsilon_n) :=
\begin{cases}
\frac{1}{\sqrt{n \varepsilon_n}}  \;  &  \textrm{if } \;\frac{1}{n^{1/d}} \leq \varepsilon_n  \medskip \\
\frac{1}{n \varepsilon_n^{(d+1)/2}}  & \textrm{if } \;\frac{1}{n^{2/(d+1)}} \leq \varepsilon_n \leq \frac{1}{n^{1/d}}.
\end{cases}
\end{equation}

\begin{theorem}
Let $p \geq 1$ and let $\Omega \subseteq D$ be a set with finite perimeter. Assume $\varepsilon_n \to 0$ as $n \to \infty$. Then,
\begin{equation}
 \mathbb{E}(|\GPe{\Omega} - \mathbb{E}(\GP{\Omega})|^p) \leq C_{p,d} \, (  \max\{1,\BV{\Omega}\} f(n,\varepsilon_n))^p
  \label{MomentsTheorem}
\end{equation}
where $C_{p,d} $ is a constant that depends only on $p$ and dimension $d$. In particular, if $n ^{-\frac{2}{(d+1)}} \ll \varepsilon_n \ll 1$, then
$$ \GP{\Omega} \rightarrow   \sigma_{d} \BV{\Omega},  \: \textrm{almost surely as }  n \to \infty.   $$
\label{TheoremGeneral}
\end{theorem}
The last part of the previous theorem follows from \eqref{temp1}, the moment estimates \eqref{MomentsTheorem}, Markov's inequality, and Borel-Cantelli Lemma which imply that
$$ \GPe{\Omega}- \mathbb{E}\left( \GPe{\Omega} \right) \rightarrow 0 \quad \text{a.s.}   $$

\begin{remark}
We note that the a.s. convergence holds for rather sparse graphs (see Figure \ref{fig:cutsp}). Namely the typical degree of a node is
$\omega_d n \varepsilon^d $, where $\omega_d$ is the volume of the unit ball in $d$ dimensions. When
$n ^{-\frac{2}{(d+1)}} \ll \varepsilon_n \ll n^{-\frac{1}{d}}$ the a.s. convergence holds, while the average degree of a vertex converges to zero. The convergence is still possible because the expected number of edges crossing $\partial \Omega$ is still a quantity converging to infinity.
\end{remark}

\begin{figure}
\subfigure[$n=400$ and $\varepsilon=0.045$\normalcolor]{\includegraphics[width=60mm]{n400eps045.png}
}
\label{figureE}
\hspace*{2mm}
\subfigure[$n=1000$ and $\varepsilon=0.027$ ]{ \includegraphics[width=60mm]{n1000eps027.png}
}
\label{figureF}
\caption{Here we illustrate the ``sparse" regime when $1/n^{1/d}  \gg \varepsilon  \gg (1/n)^{2/d+1} $ when the average degree goes to zero. Nevertheless since the number of edges in the cut still increases as $n$ does the convergence of the cut to the perimeter still holds. \normalcolor}
\label{fig:cutsp}
\end{figure}

\begin{remark}
Given that we show the almost-sure consistency of our estimators for any arbitrary (but fixed) set for which the perimeter is finite, our construction provides a universal strongly convergent estimator which was the desired property listed as an open problem in \cite{CuFrGy13} (for the estimator they considered).
\end{remark}

We  turn to estimating the bias of the empirical approximation:
$|\mathbb{E}(\GP{\Omega}) - \sigma_{d} \Pem(\Omega)| $. We first characterize the mean of the graph perimeter, $\mathbb{E}(\GP{\Omega})$, as the \emph{non-local perimeter} $\Pem_{\varepsilon_n}(\Omega)$ of $\Omega,$ defined as
\begin{equation}
 \NLTVenon{\Omega}: = \frac{2}{\varepsilon^{d+1}}\int_{\Omega} \int_{D \backslash \Omega} \mathbf{1}_{\{\|  x -y\| \leq \varepsilon \}} \; \mathrm{d} x \mathrm{d} y .
\label{NonLocalPerimeter}
\end{equation}
The non-local nature of the functional essentially has to do with the fact that it involves averages of finite differences as opposed to a \emph{local} approach where one considers derivatives.  We then proceed to estimate $\left|\Pem_{\varepsilon_n}(\Omega)- \sigma_{d} \Pem(\Omega)\right|$ explicitly. It proves straightforward to check that $\left|  \Pem_{\varepsilon_n}(\Omega)- \sigma_{d} \Pem(\Omega)\right| = O\left(\varepsilon_n  \right)$ for general subsets $\Omega \subseteq D$ with smooth relative boundary. However, we show that the error is actually quadratic in $\varepsilon_n$
\begin{equation} \label{bias1}
|\mathbb{E}(\GP{\Omega}) - \sigma_{d} \Pem(\Omega)| = \left|\Pem_{\varepsilon_n}(\Omega)- \sigma_{d} \Pem(\Omega)\right| = O(\varepsilon_n^2)
\end{equation}
under the extra condition that $\dist ( \Omega, \partial D) >0$. This is the content of the next lemma, whose proof may be found in Appendix \ref{AppendixLemmaBias}.
\begin{lemma} \label{pnlp}
Let $\Omega$ be a set with smooth boundary, such that $\dist(\Omega ,\partial D) >0$. Let $0 < \varepsilon < \dist(\Omega ,\partial D)$ and let $\NLTVenon{\Omega}$ be defined by \eqref{NonLocalPerimeter}. Then
\begin{equation}
\NLTVenon{\Omega}= \sigma_{d} \Pem(\Omega) + O(\varepsilon^2).
\label{errorNonlocal}
\end{equation}
\end{lemma}

\begin{remark}
The assumption $\dist(\Omega, \partial D) >0$ in the above Lemma is needed in order to obtain bias of order $\varepsilon^2$. If $\Omega$ touches the boundary $\partial D$ the error of order $\varepsilon^2$ is not expected, as can be seen for example by considering the rectangle $\Omega := \left\{ x=(x_1,\dots,x_d) \in D \: : \: x_1 \leq 1/2 \right\}$, for which the error is of order $\varepsilon$; in this situation the error is completely due to the region where $\partial \Omega$ meets $\partial D$ transversally.
Thus, in general, for $\Omega \subseteq D$ with smooth relative boundary, the bias is of order $\varepsilon$. On the other hand, the smoothness of the boundary of $\Omega$ is only needed in the previous lemma to guarantee that curvature and its derivatives are well defined. Finally, the constant involved in the term $O(\varepsilon^2)$ depends on the reach of the set $\Omega,$ and the intrinsic curvature of $\partial \Omega$ together with its derivatives; this can be seen from our computations in Appendix \ref{AppendixLemmaBias}.
\end{remark}

Combining the bias and variance of estimates allows us
to obtain the rates of convergence for the error $|\GP{\Omega} - \sigma_{d} \Pem(\Omega)|$.
In particular we estimate  the  `standard deviation'
\begin{equation*}
 \error (n):= \mathbb{E}\left( (\GP{\Omega} - \sigma_{d} \Pem(\Omega))^2    \right)^{1/2},
\end{equation*}
which we may quantify precisely by using the variance-bias decomposition
\begin{equation*}
\begin{split}
\error^2 (n) &= \Var(\GP{\Omega} )  +  \left(   \mathbb{E}(\GP{\Omega}  ) - \sigma_{d} \Pem(\Omega) \right)^2.
\end{split}
\end{equation*}
Using the  special case $p=2$ of Theorem \ref{TheoremGeneral} to estimate the variance and using Lemma \ref{pnlp} to estimate the bias we obtain the following.
\begin{theorem}
\label{th:toter}
Let $\Omega \subset D$ be an open set with smooth boundary.  Assume $n^{-\frac{2}{d+1}} \ll \varepsilon_n \ll 1$ and
consider  $f(n,\varepsilon_n)$  defined via \eqref{eq:rate_def}. The error of approximating $\sigma_{d} \Pem(\Omega)$ by $\GP{\Omega}$ satisfies
\begin{equation*}
\error (n)  =  O ( f(n,\varepsilon_n) + \varepsilon_n).
\end{equation*}
If we furthermore assume that $\Omega$ does not touch the boundary of $D$, that is  $\dist(\Omega, \partial D) >0$, then a better estimate holds:
\begin{equation*}
\error (n)  =  O ( f(n,\varepsilon_n) + \varepsilon_n^2 ).
\end{equation*}
\end{theorem}

A simple calculation using  \eqref{eq:rate_def} allows one to choose a scaling of $\varepsilon_n$ on $n$ so that the error of the approximation is as small as possible. In particular, for a set $\Omega$ which touches the boundary ($\dist(\Omega, \partial D)=0$) the optimal scaling of $\varepsilon_n$ is
\[ \varepsilon_n \sim \begin{cases}
n^{-1/3}  \quad &\textrm{if } d \leq 3 \\
n^{-2/(d+3)}  & \textrm{if } d \geq 3
\end{cases}
\quad \textrm{ giving } \quad
\error(n) =  \begin{cases}
n^{-1/3}  \quad &\textrm{if } d \leq 3 \\
n^{-2/(d+3)}  & \textrm{if } d \geq 3.
\end{cases}
\]
We note that for $d < 3$ the optimal $\varepsilon_n$ is achieved in the  regime $n^{-1/d} \lesssim \varepsilon_n \ll 1$, while if  $d>3$ it is in the sparse regime. If we consider sets $\Omega$ with smooth boundary but such that $\dist(\Omega, \partial D)>0$, then the optimal scaling of $\varepsilon_n$ on $n$ is as follows
\[ \varepsilon_n \sim \begin{cases}
n^{-2/5}  \quad &\textrm{if } d \leq 5 \\
n^{-4/(d+5)}  & \textrm{if } d \geq 5
\end{cases}
\quad \textrm{ giving } \quad
\error(n) =  \begin{cases}
n^{-1/5}  \quad &\textrm{if } d \leq 5 \\
n^{-2/(d+5)}  & \textrm{if } d \geq 5.
\end{cases}
\]
Again we note that the optimal $\varepsilon_n$ is in the sparse regime if $d >5$. This has implications to how well is the perimeter estimated by graph cuts in the graphs
considered in most machine learning applications. Namely if $d \geq 5$ and the graph has average degree bounded from below, that is when  $n^{-1/d} \lesssim \varepsilon_n \ll 1$, then, since the bias bound is sharp, most of the error is due to the bias term.

\begin{remark}
The constant appearing in the moment estimates of Theorem \ref{TheoremGeneral} depends exclusively on the power $p$, the dimension $d$, and the true perimeter of the set $\Omega$; in particular, taking $p=2 $ we see that the estimates for the variance of $\GP{\Omega}$ are uniform on the class of sets $\Omega$ whose perimeter is bounded above by some fixed constant. For general sets with  large perimeter we obtain uniform estimates for moments of relative error $|\GPe{\Omega} - \mathbb{E}(\GP{\Omega})|/\BV{\Omega}$ instead of the absolute error. Thus, by combining Theorem \ref{TheoremGeneral} and the proof of Lemma  \ref{pnlp} one can derive that
the corresponding error estimates for $\lvert \GP{\Omega} - \sigma_d \Pem(\Omega)\rvert$ (either relative or absolute) are uniform on the class of sets $\Omega$ with smooth boundary satisfying the following conditions: The reach of $\Omega$ is bounded below by a fixed positive constant; The distance to the boundary $\partial D$ is bounded below by a fixed positive constant; The curvature and first derivatives of curvature are bounded from above by a fixed constant. This last requirement comes from the $O(\varepsilon^2)$ terms following Taylor's theorem in the proof of our bias estimates.
\label{remarkUniform}
\end{remark}
\normalcolor

 \medskip

We now consider obtaining confidence intervals for the value of the true perimeter $\Pem(\Omega)$ based on the estimator $\frac{1}{\sigma_d}\GPe{\Omega}$. We focus on the dense regime (See Figures \ref{fig:cutd} and \ref{fig:cutcd}), $\frac{1}{n^{1/d}}\ll \varepsilon_n \ll 1$, and first obtain the asymptotic distribution of $\GPe{\Omega}- \mathbb{E}(\GPe{\Omega})$.

\begin{figure}[!h]
\subfigure[$n = 100$, $\varepsilon = 0.17$]{\includegraphics[width=60mm]{n100eps17.png}
}
\label{figureA}
\hspace*{2mm}
\subfigure[$n=300$ and $\varepsilon=0.12$
]{\includegraphics[width=60mm]{n300eps12.png}
}
\label{figureB}
\caption{Here we illustrate the ``very dense" regime, $1 \gg \varepsilon  \gg (\ln(n)/n)^{1/d}$, when the graphs are connected with high probability.
 }
\label{fig:cutd}
\end{figure}

Since the term $\mathbb{E} \left( \GPe{\Omega} \right)= \Pem_{\varepsilon_n}(\Omega)$ depends on the set $\Omega $ itself, which is unknown (we only assume we have an oracle access to it), we need the bias to be negligible compared to the standard deviation of our estimator. This allows us to construct confidence intervals for $\Pem(\Omega)$ without using any additional information about the bias (e.g. upper bounds).  From \eqref{MomentsTheorem} the  standard deviation of $\GPe{\Omega} $  scales as $\frac{1}{\sqrt{n \varepsilon_n}}$ while by \eqref{bias1} the bias scales as $\varepsilon_n^2$; these estimates lead to restrictions on the dimensions for which the bias is negligible with respect to the standard deviation. Namely this is possible for $d=2, 3,$ and $4$.

\begin{theorem}\label{AsympDistribFirstRegime} Let $\Omega\subseteq D$ be an open set with smooth boundary such that $\dist(\Omega, \partial D )>0$. Let $\varepsilon_n$ be such that
$$  \frac{1}{n^{1/d}} \ll \varepsilon_n \ll 1 $$
Then,
$$ \sqrt{\frac{n \varepsilon_n }{4 C_d \Pem(\Omega)}} \left( \GPe{\Omega} - \Pem_{\varepsilon_n}(\Omega)  \right) \overset{w}{\longrightarrow}N(0,1), $$
where $C_d$ is given by
\begin{equation}
C_d:= 2\int_{0}^{1} \left | B_d(0,1) \cap \left\{ x=(x_1,\dots, x_d) \in \mathbb{R}^d \: : \: x_d \geq t \right\} \right |^2 \mathrm{d} t.
\label{Cd}
\end{equation}
If in addition the dimension $d $ is either $2,3$ or $4$ and if
\begin{equation}
\frac{1}{n^{1/d}} \ll \varepsilon_n \ll \frac{1}{n^{1/5}}
\label{conditionBiased}
\end{equation}
then,
\begin{equation}
\sqrt{\frac{n \varepsilon_n }{ 4 C_d \Pem(\Omega)}} \left( \GPe{\Omega} -\sigma_d \Pem(\Omega)  \right) \overset{w}{\longrightarrow}N(0,1).
\label{eqn2}
\end{equation}
\end{theorem}

\begin{figure}
\subfigure[$n=100$ and $\varepsilon=0.12$]{ \includegraphics[width=59mm]{n100eps12.png}
}
\label{figureC}
\hspace*{2mm}
\subfigure[$n=400$ and $\varepsilon=0.07$]{ \includegraphics[width=59mm]{n400eps07.png}
}
\label{figureD}
\caption{Here we illustrate an intermediate, "dense", regime $(\ln(n)/n)^{1/d} \gg \varepsilon   \gg (1/n)^{1/d}$. The average degree still increases, but the graphs are disconnected with high probability.\normalcolor}
\label{fig:cutcd}
\end{figure}

Naturally, the previous theorem implies that one can obtain confidence intervals for the value of $\Pem(\Omega)$ when the dimension $d$ is $2,3$ or $4$. Let us fix $\alpha \in (0, 0.5)$ and let $Z_\alpha $ be the $1-\alpha$ quantile of the standard normal distribution. That is, $Z_\alpha$ is such that
$$ \mathbb{P}\left( N(0,1) \leq Z_\alpha  \right)= 1-\alpha.$$
Then provided that
$$ \frac{1}{n^{1/d}} \ll \varepsilon_n \ll \frac{1}{n^{1/5}},  $$
it follows that with probability converging to $1-\alpha$, $  \Pem(\Omega) \in (a_n^- , a_n^+)$, where
\[  a_n^{\pm} := \frac{1}{\sigma_d}  ( \GPe{\Omega} \pm \sqrt{\frac{4 C_d \Pem(\Omega) }{n\varepsilon_n}} Z_{\alpha/2} ). \]

 For $d \geq 5$, the confidence intervals can not be obtained unless one has some extra quantitative information on the smoothness of $\partial \Omega,$ such as curvature bounds or upper bounds on the bias. Nevertheless, since it is known that the nonlocal perimeter $\Pem_{\varepsilon_n}(\Omega)= \mathbb{E} ( \GPe{\Omega})$ is less than $\sigma_d \Pem(\Omega)$ (see \eqref{PeP}), one can construct a test for the hypothesis that $\Pem(\Omega)$ is \emph{less}  than a certain number $\rho$ without using any quantitative estimates on the smoothness of $\partial \Omega$. In this case, we have automatic upper bounds for the bias and may consider the hypothesis testing of

\begin{equation}
 H_0: \Pem(\Omega) \leq \rho ,  \quad  \text{vs}  \quad  H_A: \Pem(\Omega)> \rho,
 \label{TestPerimeter}
\end{equation}
based on our estimator $\GPe{\Omega}$.
We consider the statistic:
\begin{equation}
l_n := \sqrt{\frac{n \varepsilon_n}{4 C_d \rho}} \left( \GPe{\Omega} - \sigma_d\rho \right).
\label{lnStatistic}
\end{equation}
The test consists on
\begin{equation}
 \text{Accept } H_0 \text{ if } l_n \leq Z_\alpha, \quad \text{reject otherwise. }
 \label{hypothesisTestGPer}
\end{equation}

\begin{proposition} \label{hyprop}
Assume $d \geq 2$ and  $\frac{1}{n^{1/d}}\ll \varepsilon_n \ll 1$. Then, the type I error satisfies
\[ \limsup_{n \rightarrow \infty}  \mathbb{P}_{H_0} \left(  l_n > Z_\alpha  \right)  \leq \alpha, \]
i.e., the type I error is asymptotically below $\alpha$. The  type II error satisfies
\[ \mathbb{P}_{H_A}(l_n \leq Z_\alpha ) = O\left(\frac{1}{\sqrt{n \varepsilon_n}} \right). \]
\end{proposition}

\begin{remark}[Extensions]
The estimates obtained in Theorem \ref{TheoremGeneral} and Theorem \ref{th:toter} are not exclusive to the case where the points are uniformly distributed in the unit cube and to geometric graphs. In fact, with slight modifications to the proofs of Theorem \ref{TheoremGeneral} and Theorem \ref{th:toter}, we can extend these results to more general situations. For example, if the data points are distributed according to some smooth density $p$ that is supported on a regular, bounded domain $D \subset \mathbb{R}^d$ with $p$ bounded below and above by positive constants, then the results  still hold. In this case, the limiting value of $\GPe{\Omega}$ is a \emph{weighted} perimeter $\Pem(\Omega,p^2)$ (see for example \cite{GTS}). Convergence is guaranteed for the same scaling for $\varepsilon_n$ as in the uniform case. The fact that the weight is $p^2$ and not $p$ (as may be a priori expected) ultimately comes from the fact that a graph cut is a double sum.

Furthermore if instead of weights $\mathbf{1}_{\{\| \mathbf{x}_i - \mathbf{x}_j\| \leq \varepsilon_n\}}$ in the definition of the graph cut, one considers edge weights $\eta(\| \mathbf{x}_i - \mathbf{x}_j\| / \varepsilon_n)$ where $\eta$ is nonnegative, integrable and non-increasing, the results still hold, provided we change the surface tension $\sigma_d$ with a surface tension associated to $\eta$ defined as in \cite{GTS}.
\end{remark}

\begin{remark}
The previous results allow us to construct asymptotic confidence intervals for $\Pem(\Omega)$ for an arbitrary set $\Omega$ with smooth boundary and $\dist(\Omega, \partial D) >0$, using the estimator $\GP{\Omega}$. Nevertheless, since very small sets (in the sense of volume) may have very large perimeter the error estimates are not uniform in $\Omega$ and thus the asymptotic confidence intervals may not be of direct practical use. This issue is unavoidable without further assumptions on the set $\Omega$ or a change of framework for testing. One possible way to restrict the class of $\Omega$ considered is pointed out in Remark \ref{remarkUniform}. In the class of sets $\Omega$ to which Remark \ref{remarkUniform} applies, the error of approximation is uniformly controlled.

Alternatively, one may consider the \textit{property testing} framework used in \cite{Neeman,Kothari}, where one could test the property ``the set $\Omega$ is close to a set whose perimeter is less than $\rho$" reliably. In that framework we would not be using the estimator $\GP{\Omega}$ to test whether $\Pem(\Omega)$ is below $\rho$ or not, but rather whether $\Omega$ is \textit{close} to a set whose perimeter is below $\rho$ or not. We notice that in this paper we have taken the classical hypothesis testing approach.

\end{remark}

\emph{Outline.}  In Subsection \ref{sec:out} we establish \eqref{temp1} and give an outline of the argument behind our main results.
We present the proof of Theorem \ref{TheoremGeneral} in Section \ref{sec:2}, while in Subsection \ref{sec:opt} we show that the scaling is sharp (up to logarithmic corrections) in the sense that if $n^{2}\varepsilon^{d+1}_n \to 0$
then $ \GP{\Omega}$ converges in probability to zero and hence does not converge almost surely to the (rescaled) relative perimeter.
In Section \ref{ProofTheoremDistrib} we prove the results on the asymptotic distribution of the error stated in Theorem \ref{AsympDistribFirstRegime}. In Subsection \ref{TestingSec} we study the type I and type II errors of the hypothesis test of Proposition \ref{hyprop}. Finally, Appendix \ref{AppendixLemmaBias} deals with the bias estimate from Lemma \ref{pnlp}.

\subsection{Discussion.}
\label{Discussion} Here we discuss the connections between our work and  related works in the literature. First we relate it to other estimators of perimeter based on a random sample. Then we contrast the type of the convergence and the scaling regimes  considered in this paper with the ones needed for the convergence of graph-cut based machine learning algorithms for clustering and related tasks.

The problem of estimating the perimeter of a set, $\Omega$, based on knowing which points of a random sample $V_n$ belong to $\Omega$, has been considered by a number of works.
Cuevas, Fraiman, and Rodr{\'i}guez-Casaet \cite{CuFrRo07},
considered estimators of the Minkowksi content, which agrees with perimeter for regular enough sets, but is a less general notion of the perimeter than the one we consider, \eqref{perimeter}. Their estimator is based on counting the vertices near the boundary (relative to a parameter $\varepsilon_n$), while we ``count" edges of a graph. The error bound obtained was of order
$O(n^{ -1/2d })$. Pateiro-L\'opez and Rodr\'iguez-Casal \cite{PatRod08} consider a similar estimator and improve the bounds to  $O((\ln n/n)^{1/(d+1)})$ under qualitative regularity conditions (rolling ball conditions).

Cuevas, Fraiman, and Gy{\"o}rfi  \cite{CuFrGy13}, obtain the convergence of estimators similar to those of
\cite{CuFrRo07}, when $\varepsilon_n \gg 1/n^{1/d}$ and under weaker conditions on the regularity of $\Omega$, although still not in the full generality we consider in this paper.

Armend\'ariz, Cuevas, and Fraiman \cite{ArCuFr09} consider a similar set-up to that in \cite{CuFrRo07, PatRod08} but with different sampling rates for $\Omega$ and $\Omega^c$: let $n$ denote the number of sample points in $\Omega$ and $k$ the number of sample points in $\Omega^c$.
Under mild assumptions on the regularity of $\partial \Omega$, and under some conditions on $n$ and $k$ which include  $1 \gg \varepsilon_{n,k} \gg (1 / n^{1/3})$ and $k \gg  (n/\varepsilon_{n,k})^{d/2}$
they obtain the asymptotic distribution of the error, under the same scaling in $n$ and $\varepsilon$ that we consider in Theorem \ref{AsympDistribFirstRegime}.
We notice that our estimator is different, and also that in
\cite{ArCuFr09} a very large number of points $k$ in $\Omega^c$ is needed for the consistency to hold. This allows the authors to obtain the asymptotic distribution of the total error in any dimension, while in our setting we only obtain it in low dimensions.
A further difference between their work and ours, is that we allow for a wider range in $\varepsilon$, namely $1 \gg \varepsilon_n \gg (1 / n)^{2/(d+1)}$.

Jim{\'e}nez and Yukich \cite{JinYuk11} give a different use to the point cloud and instead of considering a parameter $\varepsilon$ to count points close to the boundary of the set or to define a geometric graph, they consider a new estimator based on the Delaunay triangulation induced by the cloud. They obtain results not only on estimating the perimeter of the set, but also integrals of functions over $\partial \Omega$.

Kothari, Nayyeri, and O'Donnell \cite{Kothari} and
 Neeman \cite{ Neeman} consider an estimator essentially based on the following procedure: pick $n$ random points uniformly distributed on $D$  and to each point associate a random direction for a `needle' based at the point with length of order $\sqrt{\varepsilon_n}$; then count how many of the needles touch the boundary of $ \Omega$. Their main motivation is to consider the perimeter estimation from the viewpoint of \textit{property testing} as introduced in \cite{TestingProperties}. In that setting, the idea is to produce an algorithm that requires a small number of samples (essentially independent of the dimension $d$) in order to determine if a given set has a small perimeter or is `far away' from a set that has small perimeter.
The authors show completeness and soundness of the test they design (the notion of completeness and soundness is as in \cite{TestingProperties, Kothari}). The notion of testing used in their work is one of the main differences with our work since we consider the perimeter testing in the more classical framework of hypothesis testing (Proposition \ref{hyprop})\normalcolor. We note that the completeness of \cite{Kothari} is analogous to the type I error, but the soundness is fundamentally different from estimating the type II error.

 %

It is also worth mentioning the work of Belkin, Narayanan and Niyogi \cite{ConvexSets} where they consider an algorithm that requires as few samples as possible in order to estimate the perimeter of a convex body. Their results show that there is an algorithm that uses $O(d^4 \gamma^{-2} )$ samples to obtain an estimator for the true perimeter of the convex set, with an error of approximation of $\gamma$; this statement holds with high probability. We notice the polynomial dependence on dimension in their estimates.

Let us now contrast the type of the convergence and the scaling regimes that we consider in this paper with the ones needed for the convergence of graph-cut based machine learning algorithms for clustering and related tasks.

Graph-cut based algorithms for tasks such as clustering have played an important role in machine learning
\cite{ACPP,  BLUV12, HagKah, HeinSetz, KanVemVet04, ShiMalik,  SzlamBresson,  vonLux_tutorial,  WeiChe89}. Data clustering algorithms are called consistent if as the sample size $n \to \infty$
their outputs converge to a desired partitioning of the underlying measure being sampled.
It is of interest to understand under what scaling of $\varepsilon_n$ on $n$ does the consistency hold. Here we showed that for a \emph{fixed} set $\Omega$ the value of graph perimeter
(and indeed of the graph-cut-based objective functionals such as Cheeger, ratio, or normalized cuts) converges to the perimeter of $\Omega$; this result holds even for rather sparse graphs (Theorem \ref{th:toter}). In particular, partitioning such sparse graphs (as on Figure \ref{fig:cutsp}) does not provide almost  any information about the clusters present in the data. We conclude that the convergence of the graph perimeter of a fixed set towards the continuum perimeter does not provide the needed information on the asymptotic properties of graph-cut based clustering algorithms. To obtain consistency of such algorithms one needs a stronger notion of convergence of graph based functionals towards continuum functionals.
Recently the authors \cite{GTS}, and together with Laurent and Bresson \cite{TSvBLX_jmlr} have developed the appropriate notion of convergence (based on $\Gamma$-convergence from the calculus of variations), and have applied it to consistency of Cheeger, ratio, sparsest, and normalized cut based point cloud clustering.
More specifically, in \cite{TSvBLX_jmlr} it is shown that consistency holds if $ \frac{(\log(n))^{1/d}}{n^{1/d}} \ll \varepsilon \ll 1$ (for $d \geq 3$), in that regime the graphs are connected with high probability as $n \to \infty$.
\normalcolor

\subsection{Outline of the argument} \label{sec:out}

In order to understand the asymptotic behavior of the graph perimeter, following \cite{ACPP} we first define a symmetric kernel $\phi_{\varepsilon}: D \times D \rightarrow (0,\infty)$ by
$$\phi_{\varepsilon_n}(x,y) = \frac{ \mathbf{1}_{\{||x-y|| \leq \varepsilon_n\}}  }{\varepsilon^{d+1}_n}| \mathbf{1}_\Omega(x) - \mathbf{1}_\Omega(y)|.$$
Using the kernel $\phi_{\varepsilon_n}$, we can then write $\GPe{\Omega}$ as
\begin{equation}
 \GPe{\Omega}  =  \frac{2}{n (n-1)}\sum_{i=1}^{n}\sum_{j=i+1}^{n} \phi_{\varepsilon_n}(\mathbf{x}_i,\mathbf{x}_j),
 \label{eq:tri_tv}
\end{equation}
which is a  $\emph{U-statistic}$ in the terminology of
\cite{hoeffding}. A simple computation shows that the mean of this $U$-statistic, is the non-local perimeter $\NLTVenon{\Omega}$ defined in \eqref{NonLocalPerimeter}, that is,
\begin{equation}
\mathbb{E}(\GPe{\Omega}) =  \NLTVe{\Omega} =  \int_{D}\int_{D} \phi_{\varepsilon}(x,y)\; \mathrm{d} x \mathrm{d} y.
\label{eq:tri_mean}
\end{equation}
\normalcolor
Additionally, Remark 4.3 in \cite{GTS} establishes that the non-local perimeter $\NLTVe{\Omega}$ approaches a constant multiple of the relative perimeter of $\Omega$ as the parameter $\varepsilon_n$ goes to zero. More precisely, if $\varepsilon_n \to 0$ as $n \to \infty$ then
\begin{equation}
  \NLTVen{\Omega} \to \sigma_{d} \BV{\Omega} \qquad \textrm{as } n \to \infty
 \label{NonLocalpoint-wiseConv}
\end{equation}
for $\sigma_{d}$ the surface tension \eqref{sigma}. This convergence also follows from the estimates in Appendix \ref{AppendixLemmaBias} in the special case that $\Omega$ has a smooth boundary. Combining \eqref{NonLocalpoint-wiseConv} with \eqref{eq:tri_mean} we conclude that if $\varepsilon_n$ converges to zero as $n \to \infty$ then
\begin{equation}
\mathbb{E}(\GP{\Omega}) \to  \sigma_{d} \BV{\Omega} \qquad \textrm{as } n \to \infty.
\label{MeanConvergingToPerimeter}
\end{equation}
Since the graph perimeter $\GPe{\Omega}$ is a $U$-statistic of order two we can use the general theory of $U$-statistics to obtain moment estimates for $\GPe{\Omega}$. Let us first note that Hoeffding's decomposition theorem for $U$-statistics of order two (see \cite{TheoryUStat}) implies that $\GPe{\Omega}$ can be written as:
\begin{equation}
 \GPem_{n,\varepsilon_n}(\Omega) - \Pem_{\varepsilon_n}(\Omega) = 2 U_{n,1} + U_{n,2},
 \label{CanonicalDecomp}
\end{equation}
where $U_{n,1}$ is a U-statistic of order one ( just a sum of  centered independent random variables) and $U_{n,2}$ is a U-statistic of order two which is \emph{canonical} or completely degenerate (see \cite{TheoryUStat}). In order to define the variables $U_{n,1}$ and $U_{n,2}$, let us introduce the functions
\begin{alignat}{2}
 \bar{\phi}_{\varepsilon_n}(x) &:= \int_{D}\phi_{\varepsilon_n}(x,z) \, \mathrm{d} z , & \quad x &\in D, \notag\\
 g_{n,1}(x)&:= \bar{\phi}_{\varepsilon_n}(x) - \Pem_{\varepsilon_n}(\Omega) , & \quad x & \in D,   \label{CanonicalDecomp1} \\
 g_{n,2}(x,y) &:= \phi_{\varepsilon_n}(x,y) - \bar{\phi}_{\varepsilon_n}(x) - \bar{\phi}_{\varepsilon_n}(y) + \Pem_{\varepsilon_n}(\Omega), & \quad x,y &\in D.   \notag
\end{alignat}
With the previous definitions, we can now define
\begin{align}
\begin{split}
U_{n,1} &= \frac{1}{n}\sum_{i=1}^{n} g_{n,1}(\mathbf{x}_i),   \\
U_{n,2} &= \frac{2}{n(n-1)}\sum_{1\leq i < j \leq n} g_{n,2}(\mathbf{x}_{i},\mathbf{x}_{j}).
\end{split}
\label{CanonicalDecomp2}
\end{align}

We remark that $\int_{D}g_{n,1}(z) \mathrm{d} z =0$ and that $\int_{D}g_{n,2}(x,z)\mathrm{d} z  =0$ for all $x\in D$. Because of this, $U_{n,1}$ and $U_{n,2}$ are said to be canonical statistics of order one and two respectively (see \cite{TheoryUStat}). Now, Bernstein's inequality \cite{bern24} implies that
\begin{equation}
 \mathbb{E}(|U_{n,1}|^p) \leq \frac{C_p}{n^p} \max \left(  A_{n,1}^p , B_{n,1}^p \right),
 \label{MomentsU1}
\end{equation}
where
\begin{equation}
A_{n,1} := || g_{n,1}||_{\infty}, \quad B_{n,1} := \sqrt{n}|| g_{n,1}||_{2}.
\label{ConstantsU1}
\end{equation}
and $C_p$ is a universal constant. See also \cite{GineLatala} for a slight generalization of the previous result.

On the other hand some of the moment estimates in \cite{GineLatala} for canonical $U$-statistics of order two can be used to prove that
\begin{equation}
\mathbb{E}\left(| U_{n,2}|^p \right) \leq  \frac{C_p}{n^{2p}} \max\left(   A_{n,2}^p  , B_{n,2}^p   , C_{n,2}^p  \right),
\label{MomentsUn2}
\end{equation}
where
\begin{equation}
A_{n,2}:= ||g_{n,2}||_{\infty}, \quad B_{n,2} := n || g_{n,2}||_2, \quad (C_{n,2})^2:= n || \int_{D}g_{n,2}^2(\cdot,y )\; \mathrm{d} y   ||_\infty.
\label{ConstantsU2}
\end{equation}
and $C_p$ is a universal constant. From the decomposition \eqref{CanonicalDecomp} it follows that for $p\geq1$
$$ \mathbb{E} \left( | \GPe{\Omega} - \Pem_{\varepsilon_n}(\Omega) |^p \right) \leq  C_p ( \mathbb{E}\left( |U_{n,1}|^p \right) + \mathbb{E}\left( |U_{n,2}|^p \right)  ). $$
Thus in order to obtain the moment estimates for $\GPe{\Omega}$ in Theorem \ref{TheoremGeneral},
we focus on finding estimates for the quantities in \eqref{ConstantsU1} and \eqref{ConstantsU2}.

\begin{remark}
The estimates on $U_{n,1}$ and $U_{n,2}$ exhibit a crossover in the nature when the parameter $\varepsilon_n$ transitions between the sparse ($\frac{1}{n^{2/(d+1)}} \ll \varepsilon_n \ll \frac{1}{n^{1/d}} $ ) and the dense regime ( $\frac{1}{n^{1/d}} \ll \varepsilon_n \ll 1  $).  From the theory of $U$-statistics the crossover in the nature of the bounds, is connected to the different nature of the two components in the canonical decomposition for $U$-statistics. Under the dense regime the biggest source of error comes from the term $U_{n,1}$ while in the sparse regime the biggest source of error comes from the term $U_{n,2}$. The two variables $U_{n,1}$ and $U_{n,2}$ exhibit a different nature. In fact, one can think that $U_{n,1}$ is a global quantity as it is the sum of averages, while $U_{n,2}$ is simply the sum of pure interactions concentrating on the boundary of the set $\Omega$. We believe that there is a deeper geometric and analytic reason for the scaling of the error that appears in the sparse regime ($ \frac{1}{n^{2/(d+1)}} \ll\varepsilon_n \ll \frac{1}{n^{1/d}} $). Moreover, we believe that such understanding would allow us to complete the  study of the asymptotic distribution in Theorem \ref{AsympDistribFirstRegime} for the sparse regime. We expect such distribution to be of the Gaussian chaos type.
\end{remark}
\medskip

The bias estimates in Appendix \ref{AppendixLemmaBias} are obtained by a series of computations whose starting point is writing $\Pem_\varepsilon(\Omega)$ in terms of an iterated integral, the outer one taken over the manifold $\partial \Omega$ and the inner one taken along the normal line to $\partial \Omega$ at an arbitrary point $x \in \partial \Omega$. Such computations show that the first order term of $\Pem_{\varepsilon_n}(\Omega)$ on $\varepsilon_n$ vanishes.

Finally, Theorem \ref{AsympDistribFirstRegime} is obtained by using the canonical decomposition of $U$-statistics and by noticing that in the dense regime $\frac{1}{n^{1/d}}\ll \varepsilon_n \ll 1$, the variable $U_{n,2}$ is negligible in relation to $U_{n,1}$. We make use of the CLT for triangular arrays after computing the variances of the involved variables.

\section{Proof of Theorem \ref{TheoremGeneral}} \label{sec:2}
We first compute the moments of $U_{n,1}$ and so we start  computing the quantities $A_{n,1}$ and $B_{n,1}$ from \eqref{ConstantsU1}. Denote by $T_{\varepsilon}$ the $\varepsilon$-\emph{tube} around $\partial \Omega$, that is,  consider the set
 \begin{equation}
  T_{\varepsilon}:= \left\{ x\in \mathbb{R}^d  \: : \: \dist(x,\partial \Omega) \leq \varepsilon \right\}.
  \label{tube}
  \end{equation}
We also consider the \emph{half tubes} $T_{\varepsilon}^-$ and $T_{\varepsilon}^+$,
\begin{equation}
 T_{\varepsilon}^-:=  \left\{ x\in \Omega  \: : \: \dist(x,\partial \Omega) \leq \varepsilon \right\}, \quad  T_\varepsilon^+:= \left\{ x\in \Omega^c  \: : \: \dist(x,\partial \Omega) \leq \varepsilon \right\}.
 \label{halfTube}
\end{equation}
With these definitions it is straightforward to check that
\begin{equation}
\bar{\phi}_{\varepsilon_n}(x) =
  \begin{cases}
      \hfill |  B_d(x,\varepsilon_n) \cap \Omega |/ \varepsilon_n^{d+1}    \hfill & \text{ if $x \in T_{\varepsilon_n}^+$ } \\
      \hfill | B_d(x,\varepsilon_n) \cap \Omega^c |/ \varepsilon_n^{d+1}    \hfill & \text{ if $x \in T_{\varepsilon_n}^-$ } \\
      \hfill 0 \hfill & \text{ if $x \not \in T_{\varepsilon_n}$ }. \\
  \end{cases}
  \label{phiAverageDef}
\end{equation}
Since $| B_d(x,\varepsilon_n) \cap \Omega|$ and $|  B_d(x,\varepsilon_n)\cap \Omega^c | $ are bounded by $\alpha_d \varepsilon_n^d$, where $\alpha_d$ is the volume of the $d$-dimensional unit ball, we deduce that
$$ A_{n,1} = O\left(\frac{1}{\varepsilon_n}  \right). $$

In order to compute the quantity $B_{n,1}$ we use the following lemma, whose proof may be found in Appendix \ref{AppendixMomentsPhi}.
\begin{lemma}
Let $p \geq 1$ and let $\Omega  \subseteq D$, be a set with finite perimeter. Then, for all $\varepsilon>0$ we have
$$  \int_{D}\bar{\phi}_{\varepsilon_n}^p(x) \mathrm{d} x \leq \frac{\alpha_d^{p-1} \sigma_d}{\varepsilon^{p-1}} \Pem(\Omega).   $$
In particular, taking $p=1$ in the previous expression, we obtain
\begin{equation} \label{PeP}
 \Pem_{\varepsilon}(\Omega) \leq \sigma_d \Pem(\Omega).
\end{equation}
\label{LemmaMomentsAveragephi}
\end{lemma}

Using the previous lemma with $p=2$ we deduce that $ \int_{D}\bar{\phi}_{\varepsilon_n}^2(x) \mathrm{d} x = O\left(\frac{1}{\varepsilon_n} \right)  $, and since
$$ \int_{D} g_{n,1}^2(x) \mathrm{d} x = \int_{D}\bar{\phi}_{\varepsilon_n}^2(x) \mathrm{d} x - \left(\Pem_{\varepsilon_n}(\Omega) \right)^2,  $$
we conclude that
$$B_{n,1}= O \left( \sqrt{\frac{n}{\varepsilon_n}}   \right).  $$
From the previous computations, we deduce that
$$  \mathbb{E}(|U_{n,1}|^p) \leq C_{p,d} \max\{ 1 , \BV{\Omega} \}^{p} \normalcolor \max \left(  \frac{1}{n^p\varepsilon_n^p, } , \frac{1}{n^{p/2} \varepsilon_n^{p/2} }  \right), $$
where \normalcolor$C_{p,d}$ depends on $p$ and $d$, but is independent of the set $\Omega$. If $\frac{1}{n^{2/(d+1)}} \leq \varepsilon_n$, so that in particular $\frac{1}{n \varepsilon_n}$ is $o(1)$, then
\begin{equation}
\mathbb{E}(|U_{n,1}|^p) \leq  \frac{C_{p,d} \max\{ 1 , \BV{\Omega} \}^{p} \normalcolor}{n^{p/2} \varepsilon_n^{p/2} }  .
\label{MomentsUn1Final}
\end{equation}

\begin{remark}
 Later on, in Lemma \ref{LemmaVarianceg}, we provide an explicit computation of $\int_{D}\bar{\phi}_{\varepsilon_n}^2(x) \mathrm{d} x $ up to order $\frac{1}{\varepsilon_n}$ , which is useful when studying the asymptotic distribution of a rescaled version of $U_{n,1}$.
\end{remark}

Now we turn to the task of obtaining moment estimates for $U_{n,2}$. We estimate the quantities $A_{n,2}$, $B_{n,2}$ and $C_{n,2}$ from \eqref{ConstantsU2}. Let us start by estimating $A_{n,2}$. Note that for any $(x,y) \in D \times D$,  $\bar{\phi}_{\varepsilon_n}(x)$ and $\bar{\phi}_{\varepsilon_n}(y)$ are of order $\frac{1}{\varepsilon_n}$  and that $\Pem_{\varepsilon_n}(\Omega)$ is of order one. Thus, it is clear from the definition of $g_{n,2}$ in \eqref{CanonicalDecomp1} that
$$ A_{n,2} = O\left(\frac{1}{\varepsilon_n^{d+1}}\right).  $$
On the other hand, using $\phi_{\varepsilon_n}^2(x,y) = \frac{1}{\varepsilon_n^{d+1}} \phi_{\varepsilon_n}(x,y)$, we obtain that for every $x \in D$,
\begin{align}
\begin{split}
\int_{D}g_{n,2}^2(x,y) \mathrm{d} y = & \int_{D} \phi_{\varepsilon_n}^2(x,y) \mathrm{d} y - \bar{\phi}_{\varepsilon_n}^2(x) + 2 \theta_n \overline{\phi}_{\varepsilon_n}(x) \\
 & -  2 \! \int_{D}\phi_{\varepsilon_n}(x,y)\bar{\phi}_{\varepsilon_n}(y) \mathrm{d} y + \! \int_{D} \bar{\phi}_{\varepsilon_n}^2(y) \mathrm{d} y - \theta_n^2 \\
 = & \frac{1}{\varepsilon_n^{d+1}} \bar{\phi}_{\varepsilon_n}(x) - \bar{\phi}_{\varepsilon_n}^2(x) + 2 \theta_n \overline{\phi}_{\varepsilon_n}(x) \\
&   - 2 \int_{D}\phi_{\varepsilon_n}(x,y)\bar{\phi}_{\varepsilon_n}(y) \mathrm{d} y + \int_{D} \bar{\phi}_{\varepsilon_n}^2(y) \mathrm{d} y -\theta_n^2,
\label{aux1}
\end{split}
 \end{align}
 where we are using $\theta_n := \Pem_{\varepsilon_n}(\Omega)$. From this, it follows that
$$ C_{n,2}=O \left( \sqrt{ \frac{n}{\varepsilon_n^{d+2}} }\right).   $$
Finally, upon integration of \eqref{aux1} and direct computations, we obtain
$$ || g_{n,2}||_{2}^2 = \frac{\theta_n}{\varepsilon_n^{d+1}} - 2 \int_{D}\bar{\phi}_{\varepsilon_n}^2(y)\mathrm{d} y + \theta_n^2,    $$
which implies that
$$ B_{n,2} = O \left(\frac{n}{\varepsilon_n^{(d+1)/2}}   \right). $$
Thus, from \eqref{MomentsUn2} we deduce that
$$ \mathbb{E}(|U_{n,2}|^p) \leq K_{p,d} \max\left( \frac{1}{n^{2p}\varepsilon_n^{p(d+1)}}  ,  \frac{1}{n^p\varepsilon_n^{p(d+1)/2}}, \frac{1}{n^{3p/2}\varepsilon_n^{p(d+2)/2}}  \right), $$
where $K_{p,d} = C_{p,d} ( \max\{1,\BV{\Omega} \} )^{p}$ for $C_{p,d}$ some constant that does not depend on the set $\Omega$\normalcolor. Hence, if $\frac{1}{n^{2/(d+1)}} \leq \varepsilon_n$, we have
\begin{equation}
  \mathbb{E}(|U_{n,2}|^p) \leq  \frac{K_{p,d}}{n^p\varepsilon_n^{p(d+1)/2}}.
  \label{MomentsUn2Final}
\end{equation}
Combining \eqref{MomentsUn1Final} and \eqref{MomentsUn2Final} and using the canonical decomposition \eqref{CanonicalDecomp}, we obtain \eqref{MomentsTheorem}.

 \subsection{Sharpness of the Rate in Theorem \ref{TheoremGeneral}} \label{sec:opt}
A very simple argument shows that the rates for $\varepsilon_n$ that guarantee the almost sure convergence of the graph perimeter to the actual perimeter in Theorem \ref{TheoremGeneral} are optimal in terms of scaling, up to logarithmic corrections.

In fact, suppose $n^{2}\varepsilon^{d+1}_n = o(1)$ and let $e_{n}$ denote the random variable that counts the number of edges that cross in the interface between $\Omega$ and its complement. In other words, we define
$$
e_{n} :=  \varepsilon_n^{d+1}\sum^{n}_{i=1} \sum^{n}_{j=i+1} \phi_{\varepsilon_n}(\mathbf{x}_i,\mathbf{x}_j).
$$
As a consequence, if $\Omega$ has finite perimeter then we have
\begin{equation}
\mathrm{GPer}_{n,\varepsilon_n}(\Omega) = \frac{2}{n (n-1) \varepsilon^{d+1}_n} e_n, \qquad \mathbb{E}(e_n) = \frac{ n (n-1) \varepsilon^{d+1}_n }{2}  \Pem_{\varepsilon_n}(\Omega).
\label{Expecesubn}
\end{equation}

Note that $e_n$ takes integer values in the range $\{0,1,\ldots,N\}$ for $N = n(n-1)/2,$ so that
$$
\mathbb{E}(e_n) = \sum^{N}_{k=1} \; k p^{n}_{k} \qquad p^{n}_{k} := \mathbb{P}( e_{n} = k ).
$$
The fact that $p^{n}_{0} + \cdots + p^{n}_{N} = 1$ implies
$$
\mathbb{E}(e_n) =  \sum^{N}_{k=1} kp^{n}_{k} \geq  \sum^{N}_{k=1} p^{n}_{k}  =(1-p^{n}_{0}).
$$
In particular, from \eqref{Expecesubn} and \eqref{NonLocalpoint-wiseConv} we deduce that if $n^{2}\varepsilon^{d+1}_{n} \to 0$ and $\Omega$ has finite perimeter then
$$
(1-p^{n}_{0}) \leq \mathbb{E}(e_{n}) = o(1).
$$
On the other hand, note that for any given $\gamma>0$ it is true that $\GPem_{n,\varepsilon_n}(\Omega)  > \gamma $ implies that $e_n \not =0$. In turn
$$ \mathbb{P} \left( \GPem_{n,\varepsilon_n}(\Omega)  > \gamma   \right) \leq \mathbb{P}  \left( e_n\not =0  \right)  = 1- p_0^n =o(1).  $$
We conclude that if $n^{2}\varepsilon^{d+1}_{n} \to 0$ then $\GPem_{n,\varepsilon_n}(\Omega) $ converges in probability to zero. Therefore, if $\Omega$ has a non-zero, finite perimeter then $\GPem_{n,\varepsilon_n}(\Omega) $ does not converge to $\sigma_{d} \Pem(\Omega)$ in probability (nor almost surely, either).

\section{Proof of Theorem \ref{AsympDistribFirstRegime}}
\label{ProofTheoremDistrib}

The proof of Theorem \ref{AsympDistribFirstRegime} relies on the following lemma, whose proof may be found in Appendix \ref{AppendixVarianceg}.
\begin{lemma}
Asssume that $\varepsilon_n \rightarrow 0$ as $n \rightarrow \infty$, and that $\Omega \subset D$ is an open set with smooth boundary so that $ \mathrm{dist}(\Omega,\partial D) > 0$. Then
\begin{equation}
\Var(g_{n,1}(X_1))= \frac{C_d \Pem(\Omega)}{\varepsilon_n} + O(1),
\label{Varianceg1}
\end{equation}
where $C_d$ is given by \eqref{Cd}.
\label{LemmaVarianceg}
\end{lemma}

Now we turn our  attention to the proof of Theorem \ref{AsympDistribFirstRegime}.

\begin{proof}[Proof of Theorem \ref{AsympDistribFirstRegime}]
Note that from \eqref{CanonicalDecomp}, \eqref{CanonicalDecomp1} and \eqref{CanonicalDecomp2} we obtain
\begin{align*}
 \sqrt{ \frac{n \varepsilon_n }{4 C_d \Pem(\Omega)} } \left( \GPe{\Omega} - \Pem_{\varepsilon_n}(\Omega)  \right) = & \sqrt{ \frac{ \varepsilon_n }{n C_d \Pem(\Omega)} } \sum_{i=1}^{n} g_{n,1}(\mathbf{x}_i)  \\
 & + \sqrt{ \frac{n \varepsilon_n }{4 C_d \Pem(\Omega)} }U_{n,2}.
\end{align*}
From the moment estimates \eqref{MomentsUn2Final}, we deduce that
\begin{equation}
\sqrt{ \frac{n \varepsilon_n }{4 C_d \Pem(\Omega)} } U_{n,2} \overset{P}{\rightarrow} 0.
\label{SecondOrderStatisticVanishes}
\end{equation}
On the other hand, we note that from \eqref{Varianceg1}
$$  \frac{\error(g_{n,1}(\mathbf{x}_1)) \sqrt{\varepsilon_n} }{\sqrt{C_d \Pem(\Omega)}} \rightarrow 1 , \quad \text{as } n \rightarrow \infty, $$
where $\error(g_{n,1}(\mathbf{x}_1)) $ is the standard deviation of $g_{n,1}(\mathbf{x}_1)$. Lyapunov's condition which is sufficient to allow us to use the central limit theorem for triangular arrays  is easily checked from  Lemma \ref{LemmaMomentsAveragephi}. We deduce that
$$  \sqrt{ \frac{ \varepsilon_n }{n C_d \Pem(\Omega)} } \sum_{i=1}^{n} g_{n,1}(X_i) \overset{w}{\longrightarrow}N(0,1). $$
Combining with \eqref{SecondOrderStatisticVanishes} and the Slutsky's theorem, we obtain the desired result.
Finally, to obtain the last statement in the theorem, we note that from the bias estimates in Lemma \ref{pnlp},
$$  \sqrt{n \varepsilon_n } | \Pem_{\varepsilon_n}(A) - \sigma_d \Pem(A) |  = O(n^{1/2}\varepsilon_n^{5/2})  $$
Under the condition \eqref{conditionBiased}, we conclude that $ \sqrt{n \varepsilon_n } | \Pem_{\varepsilon_n}(A) - \sigma_\eta \Pem(A) | \rightarrow 0$. This implies \eqref{eqn2}.
\end{proof}

\subsection{Application to Perimeter Testing} \label{TestingSec}
Here we prove Proposition \ref{hyprop}.
We assume that $\Omega \subseteq D$ is an open set with smooth boundary such that $\overline \Omega \subset D$. Note that under the null hypothesis,  if $l_n > Z_\alpha$, then,
\begin{equation}
 Z_\alpha <  l_n \leq  \sqrt{\frac{n \varepsilon_n}{4 C_d \Pem(\Omega)}} \left(   \GPe{\Omega} -  \Pem_{\varepsilon_n}(\Omega)  \right),
\end{equation}
where we used that $\Pem_{\varepsilon_n}(\Omega) \leq \sigma_d \Pem(\Omega)$
by Lemma \ref{LemmaMomentsAveragephi}. Thus, using Theorem \ref{AsympDistribFirstRegime}, we deduce that asymptotically, the type I error of our test is
\begin{align*}
  \mathbb{P}_{H_0} \left(  l_n > Z_\alpha  \right) \leq \, & \mathbb{P}\left(  \sqrt{\frac{n \varepsilon_n}{4 C_d \Pem(\Omega)}} \left(   \GPe{\Omega} -  \Pem_{\varepsilon_n}(\Omega)  \right) > Z_\alpha  \right) \\
  & \longrightarrow  \mathbb{P}\left(  N(0,1) > Z_\alpha \right) = \alpha,
\end{align*}
which establishes the first part of Proposition \ref{hyprop}.
In order to compute the type II error of our test, suppose that $\Pem(\Omega)=\rho'$ where $\rho' > \rho$. In that case,
\begin{align}
\begin{split}
\mathbb{P}_{H_A}&\left( l_n \leq Z_\alpha \right)=  \mathbb{P}_{H_A}
\left( \sqrt{\frac{n \varepsilon_n}{4 C_d \rho}} (\sigma_d \rho -
\Pem_{n,\varepsilon_n}(\Omega)  ) \geq - Z_\alpha   \right) \\
&= \mathbb{P}_{H_A} \left( \sqrt{\frac{n \varepsilon_n}{4 C_d \rho}}
(\Pem_{\varepsilon_n}(\Omega) - \Pem_{n,\varepsilon_n}(\Omega)  ) \geq  - Z_\alpha   +
\sqrt{\frac{n \varepsilon_n}{4 C_d \rho}}( \Pem_{\varepsilon_n}(\Omega) - \sigma_d
\rho )  \right),
\end{split}
\end{align}
Now recall that $\lim_{n \rightarrow \infty}\Pem_{\varepsilon_n}(\Omega)=  \sigma_d \Pem(\Omega) = \sigma_d \rho' > \sigma_d \rho $. In particular, we deduce that
$$ \lim_{n \rightarrow  \infty} \sqrt{\frac{n \varepsilon_n}{4 C_d \rho}}(\Pem_{\varepsilon_n}(\Omega) - \sigma_d \rho ) = +\infty.    $$
Thus, for large enough $n$,
$$ - Z_\alpha+\sqrt{\frac{n \varepsilon_n}{4 C_d \rho}}( \Pem_{\varepsilon_n}(\Omega)
- \sigma_d \rho ) \geq \frac{1}{2} \sqrt{\frac{n \varepsilon_n}{4 C_d \rho}}(\sigma_d \rho' - \sigma_d \rho ). $$
Hence, for large enough $n$,
$$ \mathbb{P}_{H_A}\left( l_n \leq Z_\alpha \right) \leq \mathbb{P}_{H_A} \left( \sqrt{\frac{n \varepsilon_n}{4 C_d \rho}} (\Pem_{\varepsilon_n}(\Omega) - \Pem_{n,\varepsilon_n}(\Omega)  ) \geq \frac{1}{2} \sqrt{\frac{n \varepsilon_n}{4 C_d \rho}}( \sigma_d \rho' - \sigma_d \rho ).  \right)     $$
Using the moment estimates from Theorem \ref{TheoremGeneral}, and Markov's inequality, we deduce that
$$ \mathbb{P}_{H_A}(l_n \leq Z_\alpha ) = O\left(\frac{1}{\sqrt{n \varepsilon_n}} \right). $$
That is, the type II error is of order $\frac{1}{\sqrt{n \varepsilon_n}}$.