Initial commit.

3 files changed, 196 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..9a36fc7
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,14 @@
+*.aux
+*.fdb_latexmk
+*.fls
+*.log
+/*.pdf
+*.synctex.gz
+*.bbl
+*.blg
+*.out
+*.bcf
+*.run.xml
+*.synctex(busy)
+*.toc
+*Notes.bib
diff --git a/topology.bib b/topology.bib
new file mode 100644
index 0000000..dfff5d2
--- /dev/null
+++ b/topology.bib
@@ -0,0 +1,25 @@
+@book{Audin_2014_Morse,
+ author = {Audin, Michèle and Damian, Mihai},
+ title = {Morse theory and {Floer} homology},
+ publisher = {Springer},
+ year = {2014},
+ address = {London},
+ isbn = {9781447154952},
+ series = {Universitext},
+ translator = {Erné, Reinie}
+}
+
+@article{Fyodorov_2004_Complexity,
+ author = {Fyodorov, Yan V.},
+ title = {Complexity of Random Energy Landscapes, Glass Transition, and Absolute Value of the Spectral Determinant of Random Matrices},
+ journal = {Physical Review Letters},
+ publisher = {American Physical Society (APS)},
+ year = {2004},
+ month = {6},
+ number = {24},
+ volume = {92},
+ pages = {240601},
+ url = {https://doi.org/10.1103%2Fphysrevlett.92.240601},
+ doi = {10.1103/physrevlett.92.240601}
+}
+
diff --git a/topology.tex b/topology.tex
new file mode 100644
index 0000000..8c21ee9
--- /dev/null
+++ b/topology.tex
@@ -0,0 +1,157 @@
+\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{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}