diff options
author | Jaron Kent-Dobias <jaron@kent-dobias.com> | 2024-08-27 11:12:03 +0200 |
---|---|---|
committer | Jaron Kent-Dobias <jaron@kent-dobias.com> | 2024-08-27 11:12:03 +0200 |
commit | c0ef21f08ad290bdea74ba39f6002329e4511982 (patch) | |
tree | 2ea5362f08a68fdbb6c729a6c88baff0da6de6b3 | |
parent | b3a46c4867aeca056dc99ab8a44bc782932c4613 (diff) | |
download | SciPostPhys_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.tex | 140 |
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 |