Lots of writing, and new figures.

1 files changed, 162 insertions, 85 deletions

diff --git a/topology.tex b/topology.tex
index 85d1518..65c717e 100644
--- a/topology.tex
+++ b/topology.tex
@@ -1,4 +1,4 @@
-\documentclass[submission, Phys]{SciPost}
+\documentclass{SciPost}
 
 \usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc}
@@ -9,16 +9,23 @@
 
 \urlstyle{sf}
 
+\fancypagestyle{SPstyle}{
+\fancyhf{}
+\lhead{\colorbox{scipostblue}{\bf \color{white} ~SciPost Physics }}
+\rhead{{\bf \color{scipostdeepblue} ~Submission }}
+\renewcommand{\headrulewidth}{1pt}
+\fancyfoot[C]{\textbf{\thepage}}
+}
+
 % Fix \cal and \mathcal characters look (so it's not the same as \mathscr)
 \DeclareSymbolFont{usualmathcal}{OMS}{cmsy}{m}{n}
 \DeclareSymbolFontAlphabet{\mathcal}{usualmathcal}
 
 \hypersetup{
-  colorlinks=true,
-  urlcolor={blue!50!black},
-  citecolor={blue!50!black},
-  filecolor={blue!50!black},
-  linkcolor={blue!50!black}
+    colorlinks,
+    linkcolor={red!50!black},
+    citecolor={blue!50!black},
+    urlcolor={blue!80!black}
 }
 
 \author{\footnote{\url{jaron.kent-dobias@roma1.infn.it}}}
@@ -26,47 +33,32 @@
 
 \begin{document}
 
-\begin{center}{\Large \textbf{
+\pagestyle{SPstyle}
+
+\begin{center}{\Large \textbf{\color{scipostdeepblue}{
   On the topology of solutions to random continuous constraint satisfaction problems\\
-}}\end{center}
+}}}\end{center}
 
-% TODO: write the author list here. Use first name (+ other initials) + surname format.
-% Separate subsequent authors by a comma, omit comma and use "and" for the last author.
-% Mark the corresponding author with a superscript star.
 \begin{center}
-\bf Jaron Kent-Dobias$^*$
+  \textbf{Jaron Kent-Dobias$^\star$}
 \end{center}
 
-% TODO: write all affiliations here.
-% Format: institute, city, country
 \begin{center}
 Istituto Nazionale di Fisica Nucleare, Sezione di Roma I, Italy
-\\
-% TODO: provide email address of corresponding author
-${}^\star$ {\small \sf jaron.kent-dobias@roma1.infn.it}
-\end{center}
-
-\begin{center}
-\today
+\\[\baselineskip]
+$\star$ \href{mailto:jaron.kent-dobias@roma1.infn.it}{\small jaron.kent-dobias@roma1.infn.it}
 \end{center}
 
-% For convenience during refereeing (optional),
-% you can turn on line numbers by uncommenting the next line:
-%\linenumbers
-% You should run LaTeX twice in order for the line numbers to appear.
-
-\section*{Abstract}
-{\bf
-% TODO: write your abstract here.
+\section*{\color{scipostdeepblue}{Abstract}}
+\textbf{\boldmath{%
 We consider the set of solutions to $M$ random polynomial equations with
 independent Gaussian coefficients and a target value $V_0$ on the $(N-1)$-sphere. When solutions
 exist, they form a manifold. We compute the average Euler characteristic of
 this manifold in the limit of large $N$, and find different behavior
 depending on the ratio $\alpha=M/N$. When $\alpha<\alpha_\text{onset}$, the
 average characteristic is 2 and there is a single connected component, while
-for $\alpha_\text{onset}<\alpha<\alpha_\text{shatter}$ a large connected
-component coexists with many disconnected components. When
-$\alpha>\alpha_\text{shatter}$ the large connected component vanishes, and the
+for $\alpha_\text{onset}<\alpha<\alpha_\text{shatter}$ many large connected components coexist. When
+$\alpha>\alpha_\text{shatter}$ the large connected components vanish, replaced by small fragments, and the
 entire manifold vanishes for $\alpha>\alpha_\text{\textsc{sat}}$. In the
 limit $\alpha\to0$ there is a correspondence between this problem and the
 topology of constant-energy level sets in the spherical spin glasses. We
@@ -74,16 +66,45 @@ conjecture that the energy $E_\text{shatter}$ associated with the vanishing of
 the large connected component corresponds to the asymptotic limit of gradient
 descent from a random initial condition.
 }
+}
+
+\vspace{\baselineskip}
+
+%%%%%%%%%% BLOCK: Copyright information
+% This block will be filled during the proof stage, and finilized just before publication.
+% It exists here only as a placeholder, and should not be modified by authors.
+\noindent\textcolor{white!90!black}{%
+\fbox{\parbox{0.975\linewidth}{%
+\textcolor{white!40!black}{\begin{tabular}{lr}%
+  \begin{minipage}{0.6\textwidth}%
+    {\small Copyright attribution to authors. \newline
+    This work is a submission to SciPost Physics. \newline
+    License information to appear upon publication. \newline
+    Publication information to appear upon publication.}
+  \end{minipage} & \begin{minipage}{0.4\textwidth}
+    {\small Received Date \newline Accepted Date \newline Published Date}%
+  \end{minipage}
+\end{tabular}}
+}}
+}
+%%%%%%%%%% BLOCK: Copyright information
 
 
-% TODO: include a table of contents (optional)
+%%%%%%%%%% TODO: LINENO
+% For convenience during refereeing we turn on line numbers:
+%\linenumbers
+% You should run LaTeX twice in order for the line numbers to appear.
+%%%%%%%%%% END TODO: LINENO
+
+%%%%%%%%%% TODO: TOC 
 % Guideline: if your paper is longer that 6 pages, include a TOC
 % To remove the TOC, simply cut the following block
 \vspace{10pt}
 \noindent\rule{\textwidth}{1pt}
-\tableofcontents\thispagestyle{fancy}
+\tableofcontents
 \noindent\rule{\textwidth}{1pt}
 \vspace{10pt}
+%%%%%%%%%% END TODO: TOC
 
 \section{Introduction}
 
@@ -232,8 +253,6 @@ 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.
 
-\subsubsection{Calculation of the average Euler characteristic}
-
 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)
@@ -377,55 +396,6 @@ These transition values of the target $V_0$ correspond with transition values in
 \end{figure}
 
 
-
-
-\subsubsection{How to interpret the average Euler characteristic}
-
-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.
-
 The many positive values the Euler characteristic can take is one problem, but
 a larger one is the many negative values it can take. A manifold with many
 handles will have a very negative Euler characteristic, and our calculation
@@ -439,6 +409,8 @@ that in the complex region, the large-deviation function in $m$ that $\mathcal
 S_\Omega(m)$ represents breaks down due to the vanishingly small probability of
 finding any stationary points.
 
+
+
 \subsection{Complexity of a linear test function}
 
 One way to definitely narrow possible interpretations of the average Euler
@@ -493,6 +465,109 @@ Appendix~\ref{sec:complexity.details}. The result is that, to largest order in
 $N$, the logarithm of the average number of stationary points is the same as
 the logarithm of the average Euler characteristic.
 
+\subsection{How to interpret these calculations}
+
+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{figs/regime_1.pdf}
+  \hspace{-3em}
+  \includegraphics{figs/regime_2.pdf}
+  \hspace{-3em}
+  \includegraphics{figs/regime_3.pdf}
+
+  \caption{
+    \textbf{Behavior of the action in our three nontrivial regimes.} The effective action $\mathcal S_\Omega$ as a function of overlap $m$ with
+    the height axis for our model with $f(q)=\frac12q^3$ and $\alpha=\frac12$
+    at three different target values $V_0$. \textbf{Left: the connected
+    regime.} The action is maximized with $\mathcal S_\Omega(m^*)=0$, and no
+    stationary points are found with overlap less than $m_\text{min}$ with a
+    random point on the sphere. \textbf{Center: the onset regime.} The action
+    is maximized with $\mathcal S_\Omega(m_\text{min})>0$, and is positive up
+    to $m_\text{max}$. No stationary points are found with overlap less than $m_\text{min}$. \textbf{Right: the shattered regime.} The action is
+    maximized with $\mathcal S_\Omega(0)>0$, and is positive up to
+    $m_\text{max}$.
+  }
+\end{figure}
+
+\paragraph{The connected regime: \boldmath{$V_0^2<V_\text{on}$}.}
+
+In our calculation above, $\overline{\chi(\Omega)}=2$ could mean a fine-tuned
+average like this, or it could indicate the presence of manifold homeomorphic
+to $S^{N-M-1}$ for even $N-M-1$. In either case it strongly indicates a single
+connected component, whose few minima and maxima are usually found at the
+latitude $m^*$. Randomly chosen points on the sphere have a typical nearest
+overlap $m^*$ with the solution manifold, but can never have a smaller overlap than
+$m_\text{min}$, indicating that the manifold is extensive.
+
+\paragraph{The onset regime: \boldmath{$V_\text{on}^2<V_0^2<V_\text{sh}$}.}
+
+In this regime $\log\overline{\chi(\Omega)}=O(N)$ but a minimum overlap
+$m_\text{min}>0$ still exists. The minimum overlap indicates that the solution
+manifold is exclusively made up of extensive components, because the existence
+of small components would lead to stationary points near the equator with
+respect to a randomly chosen axis $\mathbf x_0$. The solution manifold is
+homeomorphic to a topological space with large Euler characteristic like the
+product of union of many spheres. In the former case we would have one
+topologically nontrivial connected component, while in the latter we would have
+many simple disconnected components; the reality could be a combination of the
+two. It the framework of this calculation, it is not possible to distinguish between
+these scenarios. In any case, the minima and maxima of the height on the
+solution manifold are typically found at latitude $m_\text{min}$ but are found
+in exponential number up to the latitude $m_\text{max}$.
+
+\paragraph{The shattered regime: \boldmath{$V_\text{sh}^2<V_0^2<V_\text{\textsc{sat}}^2$}.}
+
+Here $\log\overline{\chi(\Omega)}=O(N)$ and the primary contribution to the
+number of stationary points and to the Euler characteristic comes from the
+equator. This indicates the presence of a large number of small disconnected
+components to the solution manifold. While most minima and maxima of the height
+are located at the equator $m=0$, they are found in exponential number up to
+the latitude $m_\text{max}$.
+
 \section{Results}
 
 \subsection{Topology of solutions to many equations and the satisfiability transition}
@@ -545,6 +620,8 @@ topology of the solution manifold.
 
 \subsection{Topology of level sets of the spherical spin glasses and the dynamic threshold}
 
+\cite{Folena_2020_Rethinking, Folena_2021_Gradient}
+
 As indicated earlier, for $M=1$ the solution manifold corresponds to the energy
 level set of a spherical spin glass with energy density $E=\sqrt NV_0$. All the
 results from the previous sections follow, and can be translated to the spin