diff options
| -rw-r--r-- | .gitignore | 14 | ||||
| -rw-r--r-- | topology.bib | 25 | ||||
| -rw-r--r-- | topology.tex | 157 |
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} |