\documentclass[aps,prl,nobibnotes,reprint,longbibliography,floatfix]{revtex4-2}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath,amssymb,latexsym,graphicx}
\usepackage{newtxtext,newtxmath}
\usepackage{bbold,anyfontsize}
\usepackage[dvipsnames]{xcolor}
\usepackage[
  colorlinks=true,
  urlcolor=BlueViolet,
  citecolor=BlueViolet,
  filecolor=BlueViolet,
  linkcolor=BlueViolet
]{hyperref}

\begin{document}

\title{
  On the topology of solutions to random continuous constraint satisfaction problems
}

\author{Jaron Kent-Dobias}
\email{jaron.kent-dobias@roma1.infn.it}
\affiliation{Istituto Nazionale di Fisica Nucleare, Sezione di Roma I, Rome, Italy 00184}

\begin{abstract}
  We consider the set of solutions to $M$ random polynomial equations on the
  $(N-1)$-sphere. When solutions exist, they form a manifold. We compute the
  average Euler characteristic of this manifold, and find different behaviors
  depending on $\alpha=M/N$. When $\alpha<1$, the average Euler characteristic
  is subexponential in $N$ but positive, indicating the presence of few
  simply-connected components. When $1\leq\alpha<\alpha_\mathrm a^*$, it is
  exponentially large in $N$, indicating a shattering transition in the space
  of solutions. Finally, when $\alpha_\mathrm a^*\leq\alpha$, the number of
  solutions vanish. We further compute the average logarithm of the Euler
  characteristic, which is representative of typical manifolds.
\end{abstract}

\maketitle

$\Omega=\{\mathbf x\in\mathbb R^N\mid \|\mathbf x\|^2=N,0=V_k(\mathbf x)\text{ for all $1\leq k\leq M$}\}$.

$\Omega$ is almost always a manifold without singular points due to
intersections. The conditions of a singular point are that
$0=\frac\partial{\partial\mathbf x}V_k(\mathbf x)$ for all $k$. This is
equivalent to asking that the constraints $V_k$ all have a stationary point at
the same place. When the $V_k$ are independent and random, this is vanishingly
unlikely, requiring $NM$ independent equations to be simultaneously satisfied.

The Euler characteristic $\chi$ of a manifold is a topological invariant. It is
perhaps most familiar in the context of connected compact 2-manifolds, where it
characterizes the number of holes in the surface: $\chi=2(1-\#)$ for $\#$
holes.

Morse theory offers another way to compute the Euler characteristic using the
statistics of stationary points of function $H$ defined on the manifold. For
function $H$ without any symmetries with respect to the manifold, the surfaces
of gradient flow between adjacent stationary points form a complex, i.e., a
higher-dimension polygonization of the surface. The standard counting argument
to compute $\chi$ of vertices minus edges plus faces generalizes to an
alternating sum over the counts of stationary points that make up the complex,
or
\begin{equation}
  \chi=\sum_{i=0}^N(-1)^i\mathcal N_H(\text{index}=i)
\end{equation}
Conveniently, we can express this abstract sum as an integral over the manifold
using a small variation on the Kac--Rice formula for counting stationary
points. Since the sign of the determinant of the Hessian matrix of $H$ at a
stationary point is equal to its index, if we count stationary points including
the sign of the determinant, we arrive at the Euler characteristic, or
\begin{equation}
  \chi=\int_\Omega d\mathbf x\,\delta\big(\nabla H(\mathbf x)\big)\det\operatorname{Hess}H(\mathbf x)
\end{equation}
When the Kac--Rice formula is used to \emph{count} stationary points, the sign
of the determinant is a nuisance that one must take pains to preserve
\cite{Fyodorov_2004_Complexity}. Here we are correct to exclude it.

\begin{equation}
  L(\mathbf x,\pmb\omega)
  =H(\mathbf x)+\frac12\omega_0\big(\|\mathbf x\|^2-N\big)
  +\sum_{k=1}^M\omega_iV_k(\mathbf x)
\end{equation}
\begin{equation}
  \chi=\int_{\mathbb R^N} d\mathbf x\,d\pmb\omega\,\delta\big(\partial L(\mathbf x,\pmb\omega)\big)\det\partial\partial L(\mathbf x,\pmb\omega)
\end{equation}
where $\partial=[\frac\partial{\partial\mathbf x},\frac\partial{\partial\pmb\omega}]$ is the vector of partial derivatives
with respect to all $N+M+1$ variables.
\begin{equation}
  \chi=\int d\pmb\phi\,d\pmb\sigma\,\exp\left\{
    \int d1\,L\big(\pmb\phi(1),\pmb\sigma(1)\big)
  \right\}
\end{equation}
Using standard manipulations, we find
\begin{equation}
  \begin{aligned}
    \overline{\chi}&=\int d\pmb\phi\,d\sigma_0\,\exp\Bigg\{
      -\frac M2\log\operatorname{sdet}f\left(\frac{\phi(1)^T\phi(2)}N\right) \\
      &\qquad+\int d1\,\left[
        H\big(\phi(1)\big)+\frac12\sigma_0(1)\big(\|\phi(1)\|^2-N\big)
      \right]
    \Bigg\}
  \end{aligned}
\end{equation}
Now we are forced to make a decision about the function $H$. Because $\chi$ is
a topological invariant, any choice will work so long as it does not share some
symmetry with the underlying manifold. Because our manifold of random
constraints has no symmetries, we can take a simple height function $H(\mathbf
x)=\mathbf x_0\cdot\mathbf x$ for some $\mathbf x_0\in\mathbb R^N$ with
$\|\mathbf x_0\|^2=N$. $H$ is a height function because when $\mathbf x_0$ is
used as the polar axis, $H$ gives the height on the sphere.

With this choice made, we can integrate over the superfields $\pmb\phi$.
Defining two order parameters $\mathbb Q(1,2)=\frac1N\phi(1)\cdot\phi(2)$ and
$\mathbb M(1)=\frac1N\phi(1)\cdot\mathbf x_0$, the result is
\begin{align}
  \overline{\chi}&=\int d\mathbb Q\,d\mathbb M\,d\sigma_0\,\exp\Bigg\{
    \frac N2\log\operatorname{sdet}(\mathbb Q-\mathbb M\mathbb M^T)
    -\frac M2\log\operatorname{sdet}f(\mathbb Q) \notag \\
    &\qquad+N\int d1\,\left[
      \mathbb M(1)+\frac12\sigma_0(1)\big(\mathbb Q(1,1)-1\big)
    \right]
  \Bigg\}
\end{align}

\begin{equation}
  \begin{aligned}
    &\frac1N\log\overline\chi
    =\frac12\Bigg[
      \log\left(
        \frac{\frac{f'(1)}{f(1)}(1-m^2)-1}{\alpha-1}
      \right) \\
    &\hspace{4em} -\alpha\log\left(
        \frac{\alpha}{\alpha-1}\left(
          1-\frac1{\frac{f'(1)}{f(1)}(1-m^2)}
        \right)
      \right)
    \Bigg]
  \end{aligned}
\end{equation}

\begin{figure}
  \includegraphics[width=0.49\columnwidth]{figs/connected.pdf}
  \hfill
  \includegraphics[width=0.49\columnwidth]{figs/shattered.pdf}

  \caption{
    Cartoon of the topology of the CCSP solution manifold implied by our
    calculation. The arrow shows the vector $\mathbf x_0$ defining the height
    function. The region of solutions is shaded orange, and the critical points
    of the height function restricted to this region are marked with a red
    point. For $\alpha<1$, there are few simply connected regions with most of
    the minima and maxima contributing to the Euler characteristic concentrated
    at the height $m_\mathrm a^*$. For $\alpha\geq1$, there are many simply
    connected regions and most of their minima and maxima are concentrated at
    the equator.
  }
\end{figure}

\begin{acknowledgements}
  JK-D is supported by a \textsc{DynSysMath} Specific Initiative of the INFN.
\end{acknowledgements}

\bibliography{topology}

\appendix

\section{Euler characteristic of the spherical spin glasses}

We can compare this calculation with what we expect to find for the manifold
defined by $V(\mathbf x)=E$ for a single function $V$. This corresponds to the
energy level set of a spherical spin glass.

\end{document}