summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJaron Kent-Dobias <jaron@kent-dobias.com>2024-08-27 11:12:03 +0200
committerJaron Kent-Dobias <jaron@kent-dobias.com>2024-08-27 11:12:03 +0200
commitc0ef21f08ad290bdea74ba39f6002329e4511982 (patch)
tree2ea5362f08a68fdbb6c729a6c88baff0da6de6b3
parentb3a46c4867aeca056dc99ab8a44bc782932c4613 (diff)
downloadSciPostPhys_18_158-c0ef21f08ad290bdea74ba39f6002329e4511982.tar.gz
SciPostPhys_18_158-c0ef21f08ad290bdea74ba39f6002329e4511982.tar.bz2
SciPostPhys_18_158-c0ef21f08ad290bdea74ba39f6002329e4511982.zip
A little more writing, and adopting more of the scipost submission style.
-rw-r--r--topology.tex140
1 files changed, 90 insertions, 50 deletions
diff --git a/topology.tex b/topology.tex
index d0b986e..85d1518 100644
--- a/topology.tex
+++ b/topology.tex
@@ -21,36 +21,69 @@
linkcolor={blue!50!black}
}
-\title{
- On the topology of solutions to random continuous constraint satisfaction problems
-}
-
-\author{Jaron Kent-Dobias\footnote{\url{jaron.kent-dobias@roma1.infn.it}}}
+\author{\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 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
- 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
- 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.
-\end{abstract}
-
-\tableofcontents
+\begin{center}{\Large \textbf{
+ On the topology of solutions to random continuous constraint satisfaction problems\\
+}}\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$^*$
+\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
+\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.
+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
+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
+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.
+}
+
+
+% TODO: include a table of contents (optional)
+% 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}
+\noindent\rule{\textwidth}{1pt}
+\vspace{10pt}
\section{Introduction}
@@ -252,7 +285,7 @@ This integral can be evaluated by a saddle point method. For reasons we will
see, it is best to extremize with respect to $R$, $D$, and $\hat m$, leaving a
new effective action of $m$ alone. This can be solved to give
\begin{equation}
- D=-\frac{m+R^*(m)}{1-m^2} \qquad \hat m=0
+ D=-\frac{m+R^*}{1-m^2}R^* \qquad \hat m=0
\end{equation}
\begin{equation}
\begin{aligned}
@@ -288,15 +321,26 @@ understood as the latitude on the sphere where most of the contribution to the
Euler characteristic is made.
The action $\mathcal S_\Omega$ is extremized with respect to $m$ at $m^*=0$ or $m^*=-R^*$.
-In the latter case, $m^*$ takes the value
+In the latter case, $m*$ takes the value
\begin{equation}
m^*=\pm\sqrt{1-\frac{\alpha}{f'(1)}\big(V_0^2+f(1)\big)}
\end{equation}
-and $\mathcal S_\Omega(m^*)=0$. However, when
+and $\mathcal S_\Omega(m^*)=0$. If this solution was always well-defined, it would vanish when the argument of the square root vanishes for
+\begin{equation}
+ V_0^2>V_{\text{\textsc{sat}}\ast}^2\equiv\frac{f'(1)}\alpha-f(1)
+\end{equation}
+However, when
\begin{equation}
V_0^2>V_\text{on}^2\equiv\frac{1-\alpha+\sqrt{1-\alpha}}\alpha f(1)
\end{equation}
-$R^*(m^*)$ becomes complex and the solution is no longer valid. Likewise, when
+$R^*(m^*)$ becomes complex and the solution is no longer valid. Since
+\begin{equation}
+ V_\text{on}^2-V_{\text{\textsc{sat}}\ast}^2
+ =\frac{f'(1)-f(1)}\alpha-\frac{\sqrt{1-\alpha}}\alpha f(1)
+\end{equation}
+If $f(q)$ is linear, then $f'(1)=f(1)$ and $V_\text{on}^2>V_{\text{\textsc{sat}}\ast}^2$, so the
+
+Likewise, when
\begin{equation}
V_0^2<V_\text{sh}^2\equiv\frac{2(1+\sqrt{1-\alpha})-\alpha}{\alpha}f(1)\left(1-\frac{f(1)}{f'(1)}\right)
\end{equation}
@@ -567,19 +611,17 @@ To make the calculation compact, we introduce superspace coordinates. Define the
\sigma_k(1)=\omega_k+\bar\theta_1\gamma_k+\bar\gamma_k\theta_1+\bar\theta_1\theta_1i\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(\pmb\phi(1),\pmb\sigma(1))} \\
- &=\int d\pmb\phi\,d\pmb\sigma\,\exp\left\{
- \int d1\left[
- H\big(\pmb\phi(1)\big)
- +\frac12\sigma_0(1)\left(\|\pmb\phi(1)\|^2-N\right)
- +\sum_{k=1}^M\sigma_k(1)\Big(V_k\big(\pmb\phi(1)\big)-V_0\Big)
- \right]
- \right\}
- \end{aligned}
-\end{equation}
+\begin{align}
+ &\chi(\Omega)
+ =\int d\pmb\phi\,d\pmb\sigma\,e^{\int d1\,L(\pmb\phi(1),\pmb\sigma(1))} \\
+ &=\int d\pmb\phi\,d\pmb\sigma\,\exp\left\{
+ \int d1\left[
+ H\big(\pmb\phi(1)\big)
+ +\frac12\sigma_0(1)\left(\|\pmb\phi(1)\|^2-N\right)
+ +\sum_{k=1}^M\sigma_k(1)\Big(V_k\big(\pmb\phi(1)\big)-V_0\Big)
+ \right]
+ \right\} \notag
+\end{align}
Since this is an exponential integrand linear in the functions $V_k$, we can average over the functions to find
\begin{equation}
\begin{aligned}
@@ -590,7 +632,7 @@ Since this is an exponential integrand linear in the functions $V_k$, we can ave
+\frac12\sigma_0(1)\big(\|\pmb\phi(1)\|^2-N\big)
-V_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)
+ -\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}
@@ -618,8 +660,7 @@ function $H$. We therefore change variables to the superoperator $\mathbb Q$ and
\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}
+\begin{align}
\overline{\chi(\Omega)}
&=\int d\mathbb Q\,d\mathbb M\,d\sigma_0\,
\left[g(\mathbb Q,\mathbb M)+O(N^{-1})\right]
@@ -627,13 +668,12 @@ These new variables can replace $\pmb\phi$ in the integral using a generalized H
N\int d1\left[
\mathbb M(1)
+\frac12\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)
+ \right] \notag \\
+ &\hspace{3em}-\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}
+\end{align}
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