\subsection{Capacity of the Sherrington--Kirkpartrick Spin Glass}

This part is based on the paper:
O.~Shental and I.~Kanter, ``Shannon capacity of infinite--range
spin--glasses,''  
Technical Report, Bar Ilan University, 2005.
In this work, the authors consider the S--K model with independent Gaussian
coupling coefficients, and they count the number $N(n)$ of meta--stable states in the
absence of magnetic field. A meta-stable state means that each spin is in its
preferred polarization according to the net field that it `feels'. i.e.,
\begin{equation}
s_i=\mbox{sgn}\left(\sum_j J_{ij}s_j\right),~~~~~~i=1,\ldots,n.
\end{equation}
They refer to the limit $\lim_{n\to\infty}[\ln N(n)]/n$ as the capacity $C$
of the S--K model. However, they take an annealed rather than a quenched
average, thus the resulting capacity is somewhat optimistic. The reason that
this work is brought here is that many of the mathematical tools we have
been exposed to are used here. The main result in this work is that
\begin{equation}
C=\ln[2(1-Q(t))]-\frac{t^2}{2}
\end{equation}
where 
\begin{equation}
Q(t)\dfn\frac{1}{2\pi}\int_t^\infty \dd u\cdot e^{-u^2/2}
\end{equation}
and $t$ is the solution
to the equation
\begin{equation}
t=\frac{e^{-t^2/2}}{\sqrt{2\pi}[1-Q(t)]}.
\end{equation}

The authors even address a slighlty more general question: Quite obviously,
the metastability condition is that for every $i$ there exists $\lambda_i > 0$
such that
\begin{equation}
\lambda_is_i=\sum_j J_{ij}s_j.
\end{equation}
But they actually answer the following question:
Given a constant $K$, what is the expected number of states for which
there is $\lambda_i>K$ for each $i$ such that $\lambda_is_i=\sum_j J_{ij}s_j$?
For $K\to-\infty$, one expects $C\to\ln 2$, and for
$K\to\infty$, one expects $C\to 0$. The case of interest is exactly in the
middle, where $K=0$.

Moving on to the analysis, we first observe that for each such state,
\begin{equation}
\int_K^\infty\cdot\cdot\cdot\int_K^\infty\prod_{i=1}^n\left[\dd\lambda_i
\delta\left(\sum_\ell J_{i\ell}s_\ell-\lambda_is_i\right)\right]=1
\end{equation}
thus
\begin{equation}
N(n)=\int_K^\infty\cdot\cdot\cdot\int_K^\infty\prod_{i=1}^n\dd\lambda_i\sum_{\bs}
\left<\prod_{i=1}^n\delta\left(\sum_\ell
J_{i\ell}s_\ell-\lambda_is_i\right)\right>_{\bJ}.
\end{equation}
Now, according to the S--K model, $\{J_{i\ell}\}$ are $n(n-1)/2$ i.i.d.
zero--mean Gaussian RV's with variance $J^2/n$. Thus,
\begin{equation}
\bar{N}(n)=\left(\frac{n}{2\pi
J^2}\right)^{n(n-1)/4}\int_{\reals^{n(n-1)/2}}\dd\bJ
\exp\left\{-\frac{n}{2J^2}\sum_{i>\ell}J_{i\ell}^2\right\}\cdot\sum_{\bs}
\int_K^\infty\cdot\cdot\cdot\int_K^\infty\dd\blambda \cdot\prod_{i=1}^n
\delta\left(\sum_\ell J_{i\ell} s_\ell-\lambda_is_i\right).
\end{equation}
The next step is to represent each Dirac as an inverse Fourier transform
of an exponent
\begin{equation}
\delta(x)=\frac{1}{2\pi}\int_{-\infty}^{+\infty}\dd\omega e^{j\omega
x}~~~~~j=\sqrt{-1}
\end{equation}
which then becomes:
\begin{eqnarray}
\bar{N}(n)&=&\left(\frac{n}{2\pi
J^2}\right)^{n(n-1)/4}\int_{\reals^{n(n-1)/2}}\dd\bJ
\exp\left\{-\frac{n}{2J^2}\sum_{i>\ell}J_{i\ell}^2\right\}\cdot\sum_{\bs}
\int_K^\infty\cdot\cdot\cdot\int_K^\infty\dd\blambda \times\nonumber\\
&&\int_{\reals^n}\frac{\dd\bomega}{(2\pi)^n}
\prod_{i=1}^n\exp\left\{j\omega_i\left(\sum_\ell
J_{i\ell}s_\ell-\lambda_is_i\right)\right\}\nonumber\\
&=&\left(\frac{n}{2\pi
J^2}\right)^{n(n-1)/4}\int_{\reals^{n(n-1)/2}}\dd\bJ\sum_{\bs}
\int_K^\infty\cdot\cdot\cdot\int_K^\infty\dd\blambda \times\nonumber\\
&&\int_{\reals^n}\frac{\dd\bomega}{(2\pi)^n}
\exp\left\{-\frac{n}{2J^2}\sum_{i>\ell}J_{i\ell}^2+j\sum_{i>\ell}J_{i\ell}
(\omega_is_\ell+\omega_{\ell}s_i)-j\sum_i\omega_is_i\lambda_i\right\}
\end{eqnarray}
We now use the Hubbard--Stratonovich transform:
\begin{equation}
\int_\reals\dd x e^{ax^2+bx}\equiv \sqrt{\frac{\pi}{a}}e^{b^2/(4a)}
\end{equation}
with $a=n/(2J^2)$ and $b=\omega_is_\ell+\omega_\ell s_i$:
\begin{equation}
\bar{N}(n)=\sum_{\bs}\int_K^\infty\cdot\cdot\cdot\int_K^\infty\dd\blambda
\int_{\reals^n}\frac{\dd\bomega}{(2\pi)^n}\prod_{i=1}^n
e^{-j\omega_is_i\lambda_i}\prod_{i>\ell}\exp\{-(\omega_is_\ell+\omega_\ell
s_i)^2J^2/(2n)\}.
\end{equation}
Next observe that the summand doesn't actually depend on $\bs$ because each
$s_i$ is multiplied by an integration variable that runs over $\reals$ and
thus the sign of $s_i$ may be absorbed by this integration variable anyhow
(exercise: convince yourself). Thus, all $2^n$ contributions are the same as
that of $\bs=(+1,\ldots,+1)$:
\begin{equation}
\bar{N}(n)=2^n\int_K^\infty\cdot\cdot\cdot\int_K^\infty\dd\blambda
\int_{\reals^n}\frac{\dd\bomega}{(2\pi)^n}\prod_{i=1}^n
e^{-j\omega_i\lambda_i}\prod_{i>\ell}\exp\{-(\omega_i+\omega_\ell
)^2J^2/(2n)\}.
\end{equation}
Now, consider the following identity (exercise: prove it):
\begin{equation}
\frac{J^2}{2n}\sum_{i>\ell}(\omega_i+\omega_\ell)^2=J^2\frac{(n-1)}{2n}\sum_i\omega_i^2+
\frac{J^2}{n}\sum_{i>\ell}\omega_i\omega_\ell,
\end{equation}
and so for large $n$,
\begin{equation}
\frac{J^2}{2n}\sum_{i>\ell}(\omega_i+\omega_\ell)^2\approx
\frac{J^2}{2}\sum_i\omega_i^2+
\frac{J^2}{n}\sum_{i>\ell}\omega_i\omega_\ell\approx
\frac{J^2}{2}\sum_i\omega_i^2+\frac{J^2}{2n}\left(\sum_{i=1}^n\omega_i\right)^2.
\end{equation}
thus
\begin{equation}
\bar{N}(n)\approx 2^n\int_K^\infty\cdot\cdot\cdot\int_K^\infty\dd\blambda
\int_{\reals^n}\frac{\dd\bomega}{(2\pi)^n}\prod_{i=1}^n
\exp\left\{-j\omega_i\lambda_i-\frac{J^2}{2}\sum_{i=1}^n\omega_i^2-\frac{J^2}{2n}
\left(\sum_{i=1}^n\omega_i\right)^2\right\}.
\end{equation}
We now use again the Hubbard--Stratonovich transform
\begin{equation}
e^{a^2}\equiv\int_\reals\frac{\dd t}{2\pi} e^{j\sqrt{2}at-t^2/2}
\end{equation}
and then, after changing variables $\lambda_i\to J\lambda_i$ and 
$J\omega_i\to\omega_i$ (exercise: show that), we get:
\begin{equation}
\bar{N}(n)\approx\frac{1}{\pi^n}\cdot\frac{1}{\sqrt{2\pi}}
\int_{K/J}^\infty\cdot\cdot\cdot\int_{K/J}^\infty\dd\blambda
\int_\reals \dd t e^{-t^2/2}\prod_{i=1}^n\left[\int_\reals\dd\omega_i
\exp\left\{j\omega_i\left(-\lambda_i+\frac{t}{\sqrt{n}}\right)-\frac{1}{2}\sum_{i=1}^n
\omega_i^2\right\}\right]
\end{equation}
which after changing $t/\sqrt{n}\to t$, becomes
\begin{eqnarray}
\bar{N}(n)&\approx&\frac{1}{\pi^n}\cdot\frac{n}{\sqrt{2\pi}}
\int_\reals \dd t
e^{-nt^2/2}\left[\int_{K/\lambda}^\infty\dd\lambda\int_\reals \dd\omega
e^{j\omega(t-\lambda)-\omega^2/2}\right]^n\nonumber\\
&=&\frac{1}{\pi^n}\cdot\frac{n}{\sqrt{2\pi}}
\int_\reals \dd t
e^{-nt^2/2}\left[\sqrt{2\pi}\int_{K/\lambda}^\infty\dd\lambda
e^{-(t-\lambda)^2/2}\right]^n~~~~~\mbox{(again, the H--S identity)}\nonumber\\
&=&\frac{1}{\pi^n}\cdot\frac{n}{\sqrt{2\pi}}
\int_\reals \dd t
e^{-n(t+K/J)^2/2}\left[\sqrt{2\pi}\int_{-\infty}^t\dd\lambda
e^{-\lambda^2/2}\right]^n~~~~~~~t\to t+K/J,~\lambda\to
-\lambda+t+K/J\nonumber\\
&=&\frac{1}{\pi^n}\cdot\frac{n}{\sqrt{2\pi}}
\int_\reals \dd t
e^{-n(t+K/J)^2/2}\cdot [2\pi(1-Q(t))]^n\nonumber\\
&=&\frac{n}{\sqrt{2\pi}}
\int_\reals \dd t
\exp\left\{-\frac{n}{2}(t+K/J)^2+\ln[2(1-Q(t))]\right\}\nonumber\\
&\exe&\exp\left\{n\cdot\max_t\left[\ln(2(1-Q(t))-\frac{(t+K/J)^2}{2}\right]\right\}~~~
\mbox{Laplace integration}\nonumber
\end{eqnarray}
The maximizing $t$ zeroes out the derivative, i.e., it solves the equation
\begin{equation}
\frac{e^{-t^2/2}}{\sqrt{2\pi}[1-Q(t)]}=t+\frac{K}{J}
\end{equation}
which for $K=0$, gives exactly the asserted result about the capacity.
{"config": "arxiv", "file": "1006.1565/sec5-4.tex"}