Some writing.

1 files changed, 84 insertions, 34 deletions

diff --git a/topology.tex b/topology.tex
index 84b871d..de4576c 100644
--- a/topology.tex
+++ b/topology.tex
@@ -34,33 +34,77 @@
   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.
+  characteristic, which is representative of typical manifolds. We compare
+  these results with the analogous calculation for the topology of level sets
+  of the spherical spin glasses, whose connected phase has a negative Euler
+  characteristic indicative of many holes.
 \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
+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
+\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)
+\end{equation}
+for some choice of $f$.
+When the covariance function $f$ is polynomial, the $V_k$ are also polynomial, with terms 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_{i_1\cdots i_p}^NJ^{(k,p)}_{i_1\cdots i_p}x_{i_1}\cdots x_{i_p}
+\end{equation}
+and each of the elements of the tensors $J^{(k,p)}$ as independently
+distributed with a unit normal distribution satisfies \eqref{eq:covariance}.
+
+
+This problem or small variations thereof have attracted attention recently for
+their resemblance to encryption, optimization, and vertex models of confluent
+tissues \cite{Fyodorov_2019_A, Fyodorov_2020_Counting,
+  Fyodorov_2022_Optimization, Urbani_2023_A, Kamali_2023_Dynamical,
+  Kamali_2023_Stochastic, Urbani_2024_Statistical, Montanari_2023_Solving,
+Montanari_2024_On}. In each of these cases, the authors studied properties of
+the cost function
+\begin{equation}
+  \mathcal C(\mathbf x)=\frac12\sum_{k=1}^MV_k(\mathbf x)^2
+\end{equation}
+which achieves zero cost only for configurations that satisfy all the
+constraints. Here we dispense with defining a cost function, and instead study
+the set of solutions directly.
+
+The set of solutions to our nonlinear random constraint satisfaction problem
+can be written as
+\begin{equation}
+  \Omega=\{\mathbf x\in\mathbb R^N\mid \|\mathbf x\|^2=N,0=V_k(\mathbf x)
+  \;\forall\;k=1,\ldots,M\}
+\end{equation}
+$\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.
-
-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.
+This means that different connected components of the set of solutions do not
+intersect, nor are there self-intersections, without extraordinary fine-tuning.
+
+The Euler characteristic $\chi$ of a manifold is a topological invariant \cite{Hatcher_2002_Algebraic}. It is
+perhaps most familiar in the context of connected compact orientable surfaces, where it
+characterizes the number of handles in the surface: $\chi=2(1-\#)$ for $\#$
+handles. For general $d$, the Euler characteristic of the $d$-sphere is $2$ if $d$ is even and 0 if $d$ is odd. The canonical method for computing the Euler characteristic is done by
+defining a complex on the manifold in question, essentially a
+higher-dimensional generalization of a polygonal tiling. Then $\chi$ is given
+by an alternating sum over the number of cells of increasing dimension, which
+for 2-manifolds corresponds to the number of vertices, minus the number of
+edges, plus the number of faces.
 
 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
+statistics of stationary points of a function $H:\Omega\to\mathbb R$ \cite{Audin_2014_Morse}. For
+functions $H$ without any symmetries with respect to the manifold, the surfaces
+of gradient flow between adjacent stationary points form a complex. The
+alternating sum over cells to compute $\chi$ becomes an alternating sum over
+the count of stationary points of $H$ with increasing index, or
 \begin{equation}
   \chi=\sum_{i=0}^N(-1)^i\mathcal N_H(\text{index}=i)
 \end{equation}
@@ -69,20 +113,27 @@ 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}
+\begin{equation} \label{eq:kac-rice}
   \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.
 
+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
+each of the $V_k$, resulting in the Lagrangian
 \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)
+  +\sum_{k=1}^M\omega_kV_k(\mathbf x)
 \end{equation}
+The integral over $\Omega$ in \eqref{eq:kac-rice} then becomes
 \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)
+  \chi=\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.
@@ -104,7 +155,7 @@ Using standard manipulations, we find
 \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
+symmetry with the underlying manifold, i.e., that it $H$ satisfies the Smale condition. 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
@@ -117,25 +168,13 @@ $\mathbb M(1)=\frac1N\phi(1)\cdot\mathbf x_0$, the result is
   \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 \\
-    &+N\int d1\,\left[
-      (1+\hat\beta\bar\theta_1\theta_1)\mathbb M(1)+\frac12\sigma_0(1)\big(\mathbb Q(1,1)-1\big)
+    &\quad+N\int d1\,\left[
+      \mathbb M(1)+\frac12\sigma_0(1)\big(\mathbb Q(1,1)-1\big)
     \right]
   \Bigg\}
 \end{align}
 
 \begin{equation}
-  0=\int d2\,(\mathbb Q(1,2)-\mathbb M(1)\mathbb M(2)^T)(1+\bar\theta_2\theta_2\hat\beta)+\mathbb M(1)
-\end{equation}
-
-\[
-  D=\beta R
-  \quad
-  \beta=-\frac{m+\sum_aR_{1a}}{\sum_aC_{1a}}
-  \quad
-  \hat m=0
-\]
-
-\begin{equation}
   \begin{aligned}
     &\frac1N\log\overline\chi
     =\frac12\Bigg[
@@ -152,8 +191,19 @@ $\mathbb M(1)=\frac1N\phi(1)\cdot\mathbf x_0$, the result is
 \end{equation}
 
 
+
+\begin{equation}
+  D=\beta R
+  \qquad
+  \beta=-\frac{m+\sum_aR_{1a}}{\sum_aC_{1a}}
+  \qquad
+  \hat m=0
+\end{equation}
+
+
 \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}
 
 \bibliography{topology}