From c0ef21f08ad290bdea74ba39f6002329e4511982 Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Tue, 27 Aug 2024 11:12:03 +0200 Subject: A little more writing, and adopting more of the scipost submission style. --- topology.tex | 140 ++++++++++++++++++++++++++++++++++++++--------------------- 1 file 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