1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
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}
|
