Merge branch 'master' of git:research/least_squares/paper/topology

1 files changed, 294 insertions, 208 deletions

diff --git a/topology.tex b/topology.tex
index 5233c54..3e8ce9b 100644
--- a/topology.tex
+++ b/topology.tex
@@ -1,10 +1,10 @@
-\documentclass[aps,prl,nobibnotes,reprint,longbibliography,floatfix]{revtex4-2}
+\documentclass[a4paper,fleqn]{article}
 
 \usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc}
 \usepackage{amsmath,amssymb,latexsym,graphicx}
 \usepackage{newtxtext,newtxmath}
-\usepackage{bbold,anyfontsize}
+\usepackage{bbold}
 \usepackage[dvipsnames]{xcolor}
 \usepackage[
   colorlinks=true,
@@ -13,35 +13,46 @@
   filecolor=BlueViolet,
   linkcolor=BlueViolet
 ]{hyperref}
+\usepackage[
+  style=phys,
+  eprint=true,
+  maxnames = 100
+]{biblatex}
+\usepackage{anyfontsize,authblk}
+\usepackage{fullpage}
 
-\begin{document}
+\addbibresource{topology.bib}
 
 \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}
+\author{Jaron Kent-Dobias\footnote{\url{jaron.kent-dobias@roma1.infn.it}}}
+\affil{Istituto Nazionale di Fisica Nucleare, Sezione di Roma I, Italy}
+
+\begin{document}
+
+\maketitle
 
 \begin{abstract}
   We consider the set of solutions to $M$ random polynomial equations with
   independent Gaussian coefficients 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 the variances of the
-  coefficients and $\alpha=M/N$. When $\alpha<1$, the average Euler
-  characteristic is subexponential in $N$ but positive, indicating the presence
-  of few connected components. When $1<\alpha<\alpha_\text{\textsc{sat}}$, it
-  is exponentially large in $N$, indicating a shattering transition of the
-  manifold of solutions into many components. Finally, when
-  $\alpha_\text{\textsc{sat}}<\alpha$, the set of solutions vanishes. Some
-  choices of variances produce $\alpha_\text{\textsc{sat}}<1$, and the shattering
-  transition never takes place. We further compute the average logarithm of the
-  Euler characteristic, which is representative of typical manifolds, and find
-  that most of the quantitative predictions agree.
+  this manifold in the limit of large $N$, and find different behavior
+  depending on the scaling of $M$ with $N$. When $\alpha=M/N$ is held constant,
+  the average characteristic is 2 whenever solutions exist. When $M$ is
+  constant, the average characteristic is also 2 up until a transition value
+  $M_\textrm{th}$, above which it is exponentially large in $N$. To better
+  interpret these results, we compute the average number of stationary points
+  of a test function on the solution manifold. In both regimes, this reveals
+  another transition between a regime with few and one with exponentially many
+  stationary points. We conjecture that this transition corresponds to a
+  geometric rather than a topological transition.
 \end{abstract}
 
-\maketitle
+\tableofcontents
+
+\section{Introduction}
 
 Constraint satisfaction problems seek configurations that simultaneously
 satisfy a set of equations, and form a basis for thinking about problems as
@@ -52,8 +63,7 @@ with sets of inequalities, while the last considers a set of equality
 constraints. Inequality constraints are familiar in situations like zero-cost
 solutions in neural networks with ReLu activations and stable equilibrium in the
 forces between physical objects. Equality constraints naturally appear in the
-zero-gradient solutions to overparameterized smooth neural networks and,
-indeed, in vertex models of tissues.
+zero-gradient solutions to overparameterized smooth neural networks and in vertex models of tissues.
 
 In such problems, there is great interest in characterizing structure in the
 set of solutions, which can be influential in how algorithms behave when trying
@@ -65,22 +75,24 @@ solution set.
 
 We consider the problem of finding configurations $\mathbf x\in\mathbb R^N$
 lying on the $(N-1)$-sphere $\|\mathbf x\|^2=N$ that simultaneously satisfy $M$
-nonlinear constraints $V_k(\mathbf x)=0$ for $1\leq k\leq M$. The nonlinear
-constraints are taken to be centered Gaussian random functions with covariance
+nonlinear constraints $V_k(\mathbf x)=V_0$ for $1\leq k\leq M$ and some
+constant $V_0\in\mathbb R$. The nonlinear constraints are taken to be centered
+Gaussian random functions with covariance
 \begin{equation} \label{eq:covariance}
-  \overline{V_i(\mathbf x)V_j(\mathbf x')}=\delta_{ij}f\left(\frac{\mathbf x\cdot\mathbf x'}N\right)
+  \overline{V_i(\mathbf x)V_j(\mathbf x')}
+  =\delta_{ij}F\left(\frac{\mathbf x\cdot\mathbf x'}N\right)
 \end{equation}
-for some choice of $f$. When the covariance function $f$ is polynomial, the
-$V_k$ are also polynomial, with a term of degree $p$ in $f$ corresponding to
+for some choice of function $F$. When the covariance function $F$ is polynomial, the
+$V_k$ are also polynomial, with a term of degree $p$ in $F$ corresponding to
 all possible terms of degree $p$ in $V_k$. In particular, taking
 \begin{equation}
   V_k(\mathbf x)
-  =\sum_{p=0}^\infty\frac1{p!}\sqrt{\frac{f^{(p)}(0)}{N^p}}
+  =\sum_{p=0}^\infty\frac1{p!}\sqrt{\frac{F^{(p)}(0)}{N^p}}
   \sum_{i_1\cdots i_p}^NJ^{(k,p)}_{i_1\cdots i_p}x_{i_1}\cdots x_{i_p}
 \end{equation}
 with the elements of the tensors $J^{(k,p)}$ as independently distributed
 unit normal random variables satisfies \eqref{eq:covariance}. The size of the
-series coefficients of $f$ therefore control the variances in the coefficients
+series coefficients of $F$ therefore control the variances in the coefficients
 of random polynomial constraints.
 
 
@@ -100,14 +112,14 @@ directly.
 This set
 can be written as
 \begin{equation}
-  \Omega=\{\mathbf x\in\mathbb R^N\mid \|\mathbf x\|^2=N,V_k(\mathbf x)=0
-  \;\forall\;k=1,\ldots,M\}.
+  \Omega=\big\{\mathbf x\in\mathbb R^N\mid \|\mathbf x\|^2=N,V_k(\mathbf x)=0
+  \;\forall\;k=1,\ldots,M\big\}
 \end{equation}
 Because the constraints are all smooth functions, $\Omega$ is almost always a manifold without singular points. The conditions for 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.
+unlikely, requiring $NM+1$ independent equations to be simultaneously satisfied.
 This means that different connected components of the set of solutions do not
 intersect, nor are there self-intersections, without extraordinary fine-tuning.
 
@@ -155,6 +167,8 @@ 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.
 
+\section{The average Euler characteristic}
+
 We treat the integral over the implicitly defined manifold $\Omega$ using the
 method of Lagrange multipliers. We introduce one multiplier $\omega_0$ to
 enforce the spherical constraint and $M$ multipliers $\omega_k$ to enforce the vanishing of
@@ -166,94 +180,251 @@ each of the $V_k$, resulting in the Lagrangian
 \end{equation}
 The integral over $\Omega$ in \eqref{eq:kac-rice} then becomes
 \begin{equation} \label{eq:kac-rice.lagrange}
-  \chi=\int_{\mathbb R^N} d\mathbf x\int_{\mathbb R^{M+1}}d\pmb\omega
+  \chi(\Omega)=\int_{\mathbb R^N} d\mathbf x\int_{\mathbb R^{M+1}}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.
 This integral is now in a form where standard techniques from mean-field theory
-can be applied to calculate it. Details of this calculation are reserved in an appendix.
+can be applied to calculate it.
+
+In order for certain Gaussian integrals in the following calculation to be
+well-defined, it is necessary to treat instead the Lagrangian problem above
+with $\pmb\omega\mapsto i\pmb\omega$. This transformation does not effect the
+Dirac $\delta$ functions of the gradient, but it does change the determinant by
+a factor of $i^{N+M+1}$. We will see that the result of the rest of the
+calculation neglecting this factor is real. Since the Euler characteristic is
+also necessarily real, this indicates an inconsistency with this transformation
+when $N+M+1$ is odd. In fact, the Euler characteristic is always zero for
+odd-dimensional manifolds. This is the signature of it in this problem.
+
+To evaluate the average of $\chi$ over the constraints, we first translate the $\delta$ functions and determinant to integral form, with
+\begin{align}
+  \delta\big(\partial L(\mathbf x,\pmb\omega)\big)
+  =\int\frac{d\hat{\mathbf x}}{(2\pi)^N}\frac{d\hat{\pmb\omega}}{(2\pi)^{M+1}}
+  e^{i[\hat{\mathbf x},\hat{\pmb\omega}]\cdot\partial L(\mathbf x,\pmb\omega)}
+  \\
+  \det\partial\partial L(\mathbf x,\pmb\omega)
+  =\int d\bar{\pmb\eta}\,d\pmb\eta\,d\bar{\pmb\gamma}\,d\pmb\gamma\,
+  e^{-[\bar{\pmb\eta},\bar{\pmb\gamma}]^T\partial\partial L(\mathbf x,\pmb\omega)[\pmb\eta,\pmb\gamma]}
+\end{align}
 
-We can solve the saddle point equations in all of these
-parameters save for $m=\frac1N\mathbf x_0\cdot\mathbf x$, the overlap with the
-height axis. The result reduces the average Euler characteristic to
+To make the calculation compact, we introduce superspace coordinates. Define the supervectors
+\begin{equation}
+  \pmb\phi(1)=\mathbf x+\bar\theta_1\pmb\eta+\bar{\pmb\eta}\theta_1+\bar\theta_1\theta_1i\hat{\mathbf x}
+  \qquad
+  \sigma_k(1)=\omega_k+\bar\theta_1\gamma_k+\bar\gamma_k\theta_1+\bar\theta_1\theta_1\hat\omega_k
+\end{equation}
+The Euler characteristic can be expressed using these supervectors as
+\begin{equation}
+  \begin{aligned}
+    \chi(\Omega)
+    &=\int d\pmb\phi\,d\pmb\sigma\,e^{\int d1\,L\big(\pmb\phi(1),\pmb\sigma(1)\big)} \\
+    &=\int d\pmb\phi\,d\pmb\sigma\,\exp\left\{
+      \int d1\left[
+        H\big(\pmb\phi(1)\big)
+        +\frac i2\sigma_0(1)\left(\|\pmb\phi(1)\|^2-N\right)
+        +i\sum_{k=1}^M\sigma_k(1)\Big(V_k\big(\pmb\phi(1)\big)-V_0\Big)
+      \right]
+    \right\}
+  \end{aligned}
+\end{equation}
+Since this is an exponential integrand linear in the functions $V_k$, we can average over the functions to find
+\begin{equation}
+  \begin{aligned}
+    \overline{\chi(\Omega)}
+    =\int d\pmb\phi\,d\pmb\sigma\,\exp\Bigg\{
+      \int d1\left[
+        H(\pmb\phi(1))
+        +\frac{i}2\sigma_0(1)\big(\|\pmb\phi(1)\|^2-N\big)
+        -iV_0\sum_{k=1}^M\sigma_k(1)
+      \right] \\
+      -\frac12\int d1\,d2\,\sum_{k=1}^M\sigma_k(1)\sigma_k(2)F\left(\frac{\pmb\phi(1)\cdot\pmb\phi(2)}N\right)
+    \Bigg\}
+  \end{aligned}
+\end{equation}
+This is a Gaussian integral in the Lagrange multipliers with $1\leq k\leq M$.
+Performing that integral yields
+\begin{equation}
+  \begin{aligned}
+    \overline{\chi(\Omega)}
+    &=\int d\pmb\phi\,d\sigma_0\,\exp\Bigg\{
+      \int d1\left[
+        H(\pmb\phi(1))
+        +\frac{i}2\sigma_0(1)\big(\|\pmb\phi(1)\|^2-N\big)
+      \right] \\
+    &\hspace{5em}-\frac M2V_0^2\int d1\,d2\,F\left(\frac{\pmb\phi(1)\cdot\pmb\phi(2)}N\right)^{-1}
+      -\frac M2\log\operatorname{sdet}F\left(\frac{\pmb\phi(1)\cdot\pmb\phi(2)}N\right)
+    \Bigg\}
+  \end{aligned}
+\end{equation}
+The supervector $\pmb\phi$ enters this expression as a function only of the
+scalar product with itself and with the vector $\mathbf x_0$ inside the
+function $H$. We therefore change variables to the superoperator $\mathbb Q$ and the supervector $\mathbb M$ defined by
+\begin{equation}
+  \mathbb Q(1,2)=\frac{\pmb\phi(1)\cdot\pmb\phi(2)}N
+  \qquad
+  \mathbb M(1)=\frac{\pmb\phi(1)\cdot\mathbf x_0}N
+\end{equation}
+These new variables can replace $\pmb\phi$ in the integral using a generalized Hubbard--Stratonovich transformation, which yields
+\begin{equation}
+  \begin{aligned}
+    \overline{\chi(\Omega)}
+    &=\int d\mathbb Q\,d\mathbb M\,d\sigma_0\,
+    \left[g(\mathbb Q,\mathbb M)+O(N^{-1})\right]
+    \,\exp\Bigg\{
+      N\int d1\left[
+        \mathbb M(1)
+        +\frac{i}2\sigma_0(1)\big(\mathbb Q(1,1)-1\big)
+      \right] \\
+    &\hspace{5em}-\frac M2V_0^2\int d1\,d2\,F(\mathbb Q)^{-1}(1,2)
+      -\frac M2\log\operatorname{sdet}F(\mathbb Q)
+      +\frac N2\log\operatorname{sdet}(\mathbb Q-\mathbb M\mathbb M^T)
+    \Bigg\}
+  \end{aligned}
+\end{equation}
+where $g$ is a function of $\mathbb Q$ and $\mathbb M$ independent of $N$ and
+$M$, detailed in Appendix~\ref{sec:prefactor}. To move on from this expression,
+we need to expand the superspace notation. We can write
+\begin{equation}
+  \begin{aligned}
+    \mathbb Q(1,2)
+    &=C-R(\bar\theta_1\theta_1+\bar\theta_2\theta_2)
+    -G(\bar\theta_1\theta_2+\bar\theta_2\theta_1)
+    -D\bar\theta_1\theta_1\bar\theta_2\theta_2 \\
+    &\qquad
+    +(\bar\theta_1+\bar\theta_2)H
+    +\bar H(\theta_1+\theta_2)
+    -(\bar\theta_1\theta_1\bar\theta_2+\bar\theta_2\theta_2\bar\theta_1)\hat H
+    -\bar{\hat H}(\theta_1\bar\theta_2\theta_2+\theta_1\bar\theta_1\theta_1)
+  \end{aligned}
+\end{equation}
+and
+\begin{equation}
+  \mathbb M(1)
+  =m+\bar\theta_1H_0+\bar H_0\theta_1-\hat m\bar\theta_1\theta_1
+\end{equation}
+The order parameters $C$, $R$, $G$, $D$, $m$, and $\hat m$ are ordinary numbers defined by
+\begin{align}
+  C=\frac{\mathbf x\cdot\mathbf x}N
+  &&
+  R=-i\frac{\mathbf x\cdot\hat{\mathbf x}}N
+  &&
+  G=\frac{\bar{\pmb\eta}\cdot\pmb\eta}N
+  &&
+  D=\frac{\hat{\mathbf x}\cdot\hat{\mathbf x}}N
+  &&
+  m=\frac{\mathbf x_0\cdot\mathbf x}N
+  &&
+  \hat m=-i\frac{\mathbf x_0\cdot\hat{\mathbf x}}N
+\end{align}
+while $\bar H$, $H$, $\bar{\hat H}$, $\hat H$, $\bar H_0$ and $H_0$ are Grassmann numbers defined by
+\begin{align}
+  \bar H=\frac{\bar{\pmb\eta}\cdot\mathbf x}N
+  &&
+  H=\frac{\pmb\eta\cdot\mathbf x}N
+  &&
+  \bar{\hat H}=\frac{\bar{\pmb\eta}\cdot\hat{\mathbf x}}N
+  &&
+  \hat H=\frac{\pmb\eta\cdot\hat{\mathbf x}}N
+  &&
+  \bar H_0=\frac{\bar{\pmb\eta}\cdot\mathbf x_0}N
+  &&
+  H_0=\frac{\pmb\eta\cdot\mathbf x_0}N
+\end{align}
+We can treat the integral over $\sigma_0$ immediately. It gives
 \begin{equation}
-  \bar\chi\propto\int dm\,e^{N\mathcal S_\mathrm a(m)}
+  \int d\sigma_0\,e^{N\int d1\,\frac i2\sigma_0(1)(\mathbb Q(1,1)-1)}
+  =2\pi\,\delta(C-1)\,\delta(G+R)\,\bar HH
 \end{equation}
-where the annealed action $\mathcal S_a$ is given by
-\begin{equation} \label{eq:ann.action}
+This therefore sets $C=1$ and $G=-R$ in the remainder of the integrand, as well
+as setting everything depending on $\bar H$ and $H$ to zero.
+
+\begin{equation}
   \begin{aligned}
-    &\mathcal S_\mathrm a(m)
-    =\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]
+    \operatorname{sdet}(\mathbb Q-\mathbb M\mathbb M^T)
+    &=1+\frac{(1-m^2)D+\hat m^2-2Rm\hat m}{R^2}
+    -\frac6{R^4}\bar H_0H_0\bar{\hat H}\hat H
+    \\
+    &\qquad+\frac2{R^3}\left[
+      (mR-\hat m)(\bar{\hat H}H_0+\bar H_0\hat H)
+      -(D+R^2)\bar H_0H_0
+      +(1-m^2)\bar{\hat H}\hat H
+    \right]
   \end{aligned}
 \end{equation}
-and must be evaluated at a maximum with respect to $m$. This function is
-plotted for a specific covariance function $f$ in Fig.~\ref{fig:action}, where
-several distinct regimes can be seen.
+\begin{equation}
+  \operatorname{sdet}f(\mathbb Q)
+  =1+\frac{Df(1)}{R^2f'(1)}
+  +\frac{2f(1)}{R^3f'(1)}\bar{\hat H}\hat H
+\end{equation}
+\begin{equation}
+  \int d1\,d2\,F(\mathbb Q)^{-1}(1,2)
+  =\left(f(1)+\frac{R^2f'(1)}{D}\right)^{-1}
+  +2\frac{Rf'(1)}{(Df(1)+R^2f'(1))^2}\bar{\hat H}\hat H
+\end{equation}
 
-\begin{figure}
-  \includegraphics{figs/action.pdf}
+\subsection{Behavior with extensively many constraints}
 
-  \caption{
-    The annealed action $\mathcal S_\mathrm a$ of \eqref{eq:ann.action} plotted
-    as a function of $m$ at several values of $\alpha$. Here, the covariance
-    function is $f(q)=\frac12q^2$ and $\alpha_\text{\textsc{sat}}=2$. When
-    $\alpha<1$, the action is maximized for $m^2>0$ and its value is zero. When
-    $1\leq\alpha<\alpha_\text{\textsc{sat}}$, the action is maximized at
-    $m=0$ and is positive. When $\alpha>\alpha_\text{\textsc{sat}}$ there is no
-    maximum.
-  } \label{fig:action}
-\end{figure}
+\subsection{Behavior with finitely many constraints}
 
-First, when $\alpha<1$ the action $\mathcal S_\mathrm a$ is strictly negative
-and has maxima at some $m^2>0$. At these maxima, $\mathcal S_\mathrm a(m)=0$.
-When $\alpha>1$, the action flips over and becomes strictly positive. In the
-regime $1<\alpha<\alpha_\text{\textsc{sat}}$, there is a single maximum at
-$m=0$ where the action is positive. When $\alpha\geq\alpha_\text{\textsc{sat}}$
-the maximum in the action vanishes.
+The correct scaling to find a nontrivial answer with finite $M$ is to scale
+both the covariance functions and fixed constants with $N$ like
+$v_0=\frac1NV_0$, $f(q)=\frac1NF(q)$, so that $v_0$ and $f(q)$ are finite at
+large $N$. With these scalings and $M=1$, this problem reduces to examining the
+levels sets of the spherical spin glasses at energy density $E=v_0$.
 
-This results in distinctive regimes for $\overline\chi$, with an example plotted in Fig.~\ref{fig:characteristic}. If $m^*$ is the maximum of $\mathcal S_\mathrm a$, then
-\begin{equation}
-  \frac1N\log\overline\chi=\mathcal S_\mathrm a(m^*)
-\end{equation}
-When $\alpha<1$, the action evaluates to zero, and therefore $\overline\chi$ is
-positive and subexponential in $N$. When $1<\alpha<\alpha_\text{\textsc{sat}}$, the action
-is positive, and $\overline\chi$ is exponentially large in $N$. Finally, when
-$\alpha\geq\alpha_\text{\textsc{sat}}$ the action and $\overline\chi$ are ill-defined.
+$v_0^{\chi>2}=\sqrt{2f(1)}$
 
-\begin{figure}
-  \includegraphics{figs/quenched.pdf}
+$v_0^{m=0}=2\sqrt{f(1)-\frac{f(1)^2}{f'(1)}}$
 
-  \caption{
-    The logarithm of the average Euler characteristic $\overline\chi$ as a
-    function of $\alpha$. The covariance function is $f(q)=\frac12+\frac12q^3$ and
-    $\alpha_\text{\textsc{sat}}=\frac32$. The dashed line shows the average of
-    $\log\chi$, the so-called quenched average, whose value differs in the
-    region $1<\alpha<\alpha_\text{\textsc{sat}}$ but whose transition points
-    are the same.
-  } \label{fig:characteristic}
-\end{figure}
+\subsection{What does the average Euler characteristic tell us?}
 
-We can interpret this by reasoning about topology of $\Omega$ consistent with
-these results. Cartoons that depict this reasoning are shown in
-Fig.~\ref{fig:cartoons}. In the regime $\alpha<1$, $\overline\chi$ is positive but not
-very large. This is consistent with a solution manifold made up of few large
-components, each with the topology of a hypersphere. The saddle point value
-$(m^*)^2=1-\alpha/\alpha_\text{\textsc{sat}}$ for the overlap with the height axis $\mathbf x_0$ corresponds to the
-latitude at which most stationary points that contribute to the Euler
-characteristic are found. This means we can interpret $1-m^*$ as the typical
-squared distance between a randomly selected point on the sphere and the
-solution manifold.
+It is not straightforward to directly use the average Euler characteristic to
+infer something about the number of connected components in the set of
+solutions. To understand why, a simple example is helpful. Consider the set of
+solutions on the sphere $\|\mathbf x\|^2=N$ that satisfy the single quadratic
+constraint
+\begin{equation}
+  0=\sum_{i=1}^N\sigma_ix_i^2
+\end{equation}
+where each $\sigma_i$ is taken to be $\pm1$ with equal probability. If we take $\mathbf x$ to be ordered such that all terms with $\sigma_i=+1$ come first, this gives
+\begin{equation}
+  0=\sum_{i=1}^{N_+}x_i^2-\sum_{i=N_++1}^Nx_i^2
+\end{equation}
+where $N_+$ is the number of terms with $\sigma_i=+1$. The topology of the resulting manifold can be found by adding and subtracting this constraint from the spherical one, which gives
+\begin{align}
+  \frac12=\sum_{i=1}^{N_+}x_i^2
+  \qquad
+  \frac12=\sum_{i=N_++1}^{N}x_i^2
+\end{align}
+These are two independent equations for spheres of radius $1/\sqrt2$, one of
+dimension $N_+$ and the other of dimension $N-N_+$. Therefore, the topology of
+the configuration space is that of $S^{N_+-1}\times S^{N-N_+-1}$. The Euler
+characteristic of a product space is the product of the Euler characteristics,
+and so we have $\chi(\Omega)=\chi(S^{N_+-1})\chi(S^{N-N_+-1})$.
+
+What is the average value of the Euler characteristic over values of
+$\sigma_i$? First, recall that the Euler characteristic of a sphere $S^d$ is 2
+when $d$ is even and 0 when $d$ is odd. When $N$ is odd, any value
+of $N_+$ will result in one of the two spheres in the product to be
+odd-dimensional, and therefore $\chi(\Omega)=0$, as is always true for
+odd-dimensional manifolds. When $N$ is even, there are two possibilities: when $N_+$ is even then both spheres are odd-dimensional, while when $N_+$ is odd then both spheres are even-dimensional.
+The number of terms $N_+$ with $\sigma_i=+1$ is distributed with the binomial distribution
+\begin{equation}
+  P(N_+)=\frac1{2^N}\binom{N}{N_+}
+\end{equation}
+Therefore, the average Euler characteristic for even $N$ is
+\begin{equation}
+  \overline{\chi(\Omega)}
+  =\sum_{N_+=0}^NP(N_+)\chi(S^{N_+-1})\chi(S^{N-N_+-1})
+  =\frac4{2^N}\sum_{n=0}^{N/2}\binom{N}{2n}
+  =2
+\end{equation}
+Thus we find the average Euler characteristic in this simple example is 2
+despite the fact that the possible manifolds resulting from the constraints
+have characteristics of either 0 or 4.
 
 \begin{figure}
   \includegraphics[width=0.32\columnwidth]{figs/connected.pdf}
@@ -277,126 +448,28 @@ solution manifold.
   } \label{fig:cartoons}
 \end{figure}
 
-When $1<\alpha<\alpha_\text{\textsc{sat}}$, $\overline\chi$ is positive and
-very large. This is consistent with a solution manifold made up of
-exponentially many disconnected components, each with the topology of a
-hypersphere. If this interpretation is correct, our calculation effectively
-counts these components. This is a realization of a shattering transition in
-the solution manifold. Here $m^*$ is zero because for any choice of height
-axis, the vast majority of stationary points that contribute to the Euler
-characteristic are found near the equator. Finally, for
-$\alpha\geq\alpha_\text{\textsc{sat}}$, there are no longer solutions that
-satisfy the constraints. The Euler characteristic is not defined for an empty
-set, and in this regime the calculation yields no solution.
-
-We have made the above discussion assuming that $\alpha_\text{\textsc{sat}}>1$.
-However, this isn't necessary, and it is straightforward to produce covariance
-functions $f$ where $\alpha_\text{\textsc{sat}}<1$. In this case, the picture
-changes somewhat. When $\alpha_\text{\textsc{sat}}<\alpha<1$, the action
-$\mathcal S_\mathrm a$ has a single maximum at $m^*=0$, where it is negative.
-This corresponds to an average Euler characteristic $\overline\chi$ which is
-exponentially small in $N$. Such a situation is consistent with typical
-constraints leading to no solutions and a zero characteristic, but rare and
-atypical configurations having some solutions.
-
-In the regime where $\log\overline\chi$ is positive, it is possible that our
-calculation yields a value which is not characteristic of typical sets of
-constraints. This motivates computing $\overline{\log\chi}$, the average of
-the logarithm, which should produce something characteristic of typical
-samples, the so-called quenched calculation. In an appendix to this paper we
-sketch the quenched calculation and report its result in the replica symmetric
-approximation. This differs from the annealed calculation above only when
-$f(0)>0$. The replica symmetric calculation produces the same transitions at
-$\alpha=1$ and $\alpha=\alpha_\text{\textsc{sat}}$, but modifies the value
-$m^*$ in the connected phase and predicts
-$\frac1N\overline{\log\chi}<\frac1N\log\overline\chi$ in the shattered phase.
-The fact that $\alpha_\text{\textsc{sat}}=f'(1)/f(1)$ is the same in the annealed and
-replica symmetric calculations suggests that it may perhaps be exact. It is also
-consistent with the full RSB calculation of \cite{Urbani_2023_A}.
-
-We check the stability of the replica symmetric solution by calculating the
-eigenvalues of the Hessian of the effective action with respect to the order
-parameters. While for calculations of this kind the meaning of the sign of
-these eigenvalues is difficult to understand directly, in situations where
-there is a continuous \textsc{rsb} transition the sign of one of the
-eigenvalues changes \cite{Kent-Dobias_2023_When}. At the $\alpha_\text{\textsc{rsb}}$ predicted in \cite{Urbani_2023_A} we see no instability of this kind, and instead only observe such an instability at $\alpha_\text{\textsc{sat}}$.
 
 \cite{Franz_2016_The, Franz_2017_Universality, Franz_2019_Critical, Annesi_2023_Star-shaped, Baldassi_2023_Typical}
 
-\begin{acknowledgements}
-  JK-D is supported by a \textsc{DynSysMath} Specific Initiative of the INFN.
-  The authors thank Pierfrancesco Urbani for helpful conversations on these topics.
-\end{acknowledgements}
+\section{Average number of stationary points of a test function}
 
-\bibliography{topology}
+\subsection{Behavior with extensively many constraints}
 
-\paragraph{Details of the annealed calculation.}
+\subsection{Behavior with finitely many constraints}
 
-To evaluate the average of $\chi$ over the constraints, we first translate the $\delta$ functions and determinant to integral form, with
-\begin{align}
-  \delta\big(\partial L(\mathbf x,\pmb\omega)\big)
-  =\int\frac{d\hat{\mathbf x}}{(2\pi)^N}\frac{d\hat{\pmb\omega}}{(2\pi)^{M+1}}
-  e^{i[\hat{\mathbf x},\hat{\pmb\omega}]\cdot\partial L(\mathbf x,\pmb\omega)}
-  \\
-  \det\partial\partial L(\mathbf x,\pmb\omega)
-  =\int d\bar{\pmb\eta}\,d\pmb\eta\,d\bar{\pmb\gamma}\,d\pmb\gamma\,
-  e^{-[\bar{\pmb\eta},\bar{\pmb\gamma}]^T\partial\partial H[\pmb\eta,\pmb\gamma]}
-\end{align}
-for real variables $\hat{\mathbf x}$ and $\hat{\pmb\omega}$, and Grassmann
-variables $\bar{\pmb\eta}$, $\pmb\eta$, $\bar{\pmb\gamma}$, and $\pmb\gamma$.
-With these transformations in place, there is a compact way to express $\chi$
-using superspace notation. For a review of the superspace formalism for
-evaluating integrals of the form \eqref{eq:kac-rice.lagrange}, see Appendices A
-\& B of \cite{Kent-Dobias_2024_Conditioning}. Introducing the Grassmann indices
-$\bar\theta_1$ and $\theta_1$, we define superfields
-\begin{align}
-  \pmb\phi(1)
-  &=\mathbf x+\bar\theta_1\pmb\eta+\bar{\pmb\eta}\theta_1+\hat{\mathbf x}\bar\theta_1\theta_1 
-  \label{eq:superfield.phi} \\
-  \pmb\sigma(1)
-  &=\pmb\omega+\bar\theta_1\pmb\gamma+\bar{\pmb\gamma}\theta_1+\hat{\pmb\omega}\bar\theta_1\theta_1
-  \label{eq:superfield.sigma}
-\end{align}
-with which we can represent $\chi$ by
 \begin{equation}
-  \chi=\int d\pmb\phi\,d\pmb\sigma\,\exp\left\{
-    \int d1\,L\big(\pmb\phi(1),\pmb\sigma(1)\big)
-  \right\}
+  Mv_0^2=\frac4{f''(1)}\left[
+    f'(1)-f(1)-2\frac{f(1)}{f'(1)}f''(1)
+  \right]\left[
+    \frac{f(1)}{f'(1)}f''(1)-2\big(f'(1)-f(1)\big)
+  \right]
 \end{equation}
-We are now in a position to average over the distribution of constraints. Using
-standard manipulations, we find the average Euler characteristic is
+
 \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}
+  Mv_0^2=\frac{f'(1)^2}{f''(1)}
 \end{equation}
 
-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 \notag\\
-   &\quad\times\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}
-This expression is an integral of an exponential with a leading factor of $N$
-over several order parameters, and is therefore in a convenient position for
-evaluating at large $N$ with a saddle point. The order parameter $\mathbb Q$ is
-made up of scalar products of the original integration variables in our
-problem in \eqref{eq:superfield.phi}, while $\mathbb M$ contains their scalar
-project with $\mathbf x_0$, and $\pmb\sigma_0$ contains $\omega_0$ and
-$\hat\omega_0$. 
+\section{Interpretation of our results}
 
 \paragraph{Quenched average of the Euler characteristic.}
 
@@ -439,4 +512,17 @@ where $\Delta f=f(1)-f(0)$ and $\tilde r_d$ is given by
 \end{align}
 When $\alpha\to\alpha_\text{\textsc{sat}}=f'(1)/f(1)$ from below, $\tilde r_d\to -1$, which produces $N^{-1}\overline{\log\chi}\to0$.
 
+\section*{Acknowledgements}
+\addcontentsline{toc}{section}{Acknowledgements}
+JK-D is supported by a \textsc{DynSysMath} Specific Initiative of the INFN.
+The authors thank Pierfrancesco Urbani for helpful conversations on these topics.
+
+\appendix
+
+\section{Calculation of the prefactor of the average Euler characteristic}
+\label{sec:prefactor}
+
+\printbibliography
+\addcontentsline{toc}{section}{References}
+
 \end{document}