Restyled for non-APS, and begin to include new material.

1 files changed, 269 insertions, 37 deletions

diff --git a/topology.tex b/topology.tex
index 5233c54..f8eec7f 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,14 +180,218 @@ 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}
+
+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}
+  \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}
+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.
+
+
+\subsection{Behavior with extensively many constraints}
+
+\subsection{Behavior with finitely many constraints}
+
+\subsection{What does the average Euler characteristic tell us?}
+
+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.
 
 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
@@ -323,12 +541,13 @@ eigenvalues changes \cite{Kent-Dobias_2023_When}. At the $\alpha_\text{\textsc{r
 
 \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}
+
+\subsection{Behavior with extensively many constraints}
 
-\bibliography{topology}
+\subsection{Behavior with finitely many constraints}
+
+\section{Interpretation of our results}
 
 \paragraph{Details of the annealed calculation.}
 
@@ -439,4 +658,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}