%% ================================================================
\section{The random-cycle model and the GK algorithm}

%% ----------------------------------------------------------------
\subsection{The random-cycle model}

We have $N$ points $\vecx_1, \ldots, \vecx_N$ in a cube $[0,L]^d$ in $\R^d$
(nominally, $d=3$) with periodic boundary conditions.  For $\pi \in \SN$, we
have
\bfidx{energy functions}
\begin{align}
\label{eqn:RCM_H}
	H(\pi)
	&= \frac{1}{4\beta} \sum_{i=1}^N \|\vecx_i - \vecxpii\|^2
		+ \sum_{\ell=2}^N \alpha_\ell N_\ell(\pi)
		\qquad \textrm{(cycle weights)}
\end{align}
or
\begin{align}
\label{eqn:RCM_HV}
	H(\pi) &= \frac{1}{4\beta} \sum_{i=1}^N \|\vecx_i - \vecxpii\|^2
		+ \sum_{i<j} V(\vecxi, \vecxpii, \vecxj, \vecxpij)
		\qquad \textrm{(jump-pair interactions)}.
\end{align}

\begin{rem}
We should write $H(\vecx_1, \ldots, \vecx_N, \pi)$.  However, either we work on
a lattice where the $\vecx_i$'s are held fixed, or on the continuum where the
$\vecx_i$'s are integrated out.
\end{rem}

\begin{rem}
For jump-pair interactions, the arrow $\vecxi\mapsto\vecxpii$
interacts with the arrow $\vecxj\mapsto\vecxpij$.
\end{rem}

\begin{defn}
\label{def:lattice}
At present we restrict attention to the \plainidx{lattice points}
$\mcL$\index{$\mathcal{L}$}:
\begin{align*}
	\mcL &= [0,L]^d \cap \Z^d.
\end{align*}
Note that there are $N=L^d$ lattice sites.
\end{defn}

From either of these energy functions we define a \bfidx{probability density}
on $\SN$ via a \bfidx{Gibbs distribution}:
\begin{align}
\label{eqn:RCM_Gibbs_P}
	P(\pi) = \frac{e^{-H(\pi)}}{Z}
\end{align}
where the \bfidx{partition function} is
\begin{align}
\label{eqn:RCM_Gibbs_Z}
	Z &= \sum_{\pi\in\SN} e^{-H(\pi)}.
\end{align}

\begin{defn}
\label{def:ell}
Fixing $\pi\in\SN$, for $\vecx \in \mcL$, $\ell_\pi(\vecx)$ (or simply
$\ell(\vecx)$) is the smallest positive number $a$ such that $\pi^a(\vecx) =
\vecx$.  This is the length of the cycle containing $\vecx$.
\end{defn}

%% ----------------------------------------------------------------
\subsection{The GK algorithm}
\label{sec:GK_algorithm}

The \bfidx{GK algorithm} for sampling from this distribution is as follows:
\begin{itemize}
\item Start with the identity or uniform-random permutation.
\item Sweep through sites $\vecx$ of the lattice in either lexical or
uniform-random order.
\item For each site $\vecx$, do a \bfidx{Metropolis step}:
	\begin{itemize}
	\item Choose a site $\pi(\vecy)$ from among the six nearest
	neighbors of $\pi(\vecx)$.
	\item Propose to change $\pi$ to the permutation $\pi'$ which
		has $\pi'(\vecz)=\pi(\vecz)$ for all $\vecz \ne \vecx, \vecy$
		but $\pi'(\vecx) = \pi(\vecy)$ and $\pi'(\vecy) = \pi(\vecx)$.
		(See figure \ref{fig:gkswap}.)
%		\begin{align*}
%		\pi: &
%		\pcmatrix{
%			\ldots & \vecx      & \ldots & \vecy      & \ldots \\
%			       & \downarrow &        & \downarrow &        \\
%			\ldots & \pi(\vecx) & \ldots & \pi(\vecy) & \ldots \\
%		} &
%		\pi': &
%		\pcmatrix{
%			\ldots & \vecx      & \ldots & \vecy      & \ldots \\
%			       & \downarrow &        & \downarrow &        \\
%			\ldots & \pi(\vecy) & \ldots & \pi(\vecx) & \ldots \\
%		} \\
%		\end{align*}

	\item With probability proportional to $\min\{1, \edh\}$
	where $\Delta H = H(\pi') - H(\pi)$, accept the change.
	(If the change is rejected, $\pi'=\pi$.)
	\end{itemize}
\item After each sweep\footnote{Or after a specified number of sweeps.  This
choice depends on autocorrelation time, which is beyond the scope of this
section.}, obtain a value of random variable(s) for inclusion in computation of
their sample means.
\end{itemize}

\begin{figure}[!htb]
\begin{center}
\psfragscanon
\includegraphics[scale=0.7]{figures/gkswap.eps}
\caption{Metropolis moves for the GK algorithm.
	\label{fig:gkswap}}
\end{center}
\end{figure}

\begin{defn}
\label{defn:GK_trivial}
A GK swap is \bfidx{trivial} if $\vecx = \vecy$.
\end{defn}

%% ----------------------------------------------------------------
\subsection{Explicit construction of the Markov matrix}

For section \ref{sec:GK_correctness} we will need an explicit construction of
the Markov matrix corresponding to the GK algorithm as described in section
\ref{sec:GK_algorithm}.

The Markov perspective on the algorithm is that the distribution $P^{(0)}(\pi)$
of the first permutation is either supported solely on the identity, or uniform
on all $N!$ permutations.  The distribution for subsequent permutations is
\begin{align*}
	P^{(k+1)}(\pi') &= \sum_{\pi \in \SN} P^{(k)}(\pi) M(\pi, \pi')
\end{align*}
or, in matrix/vector notation,
\begin{align*}
	\vecP^{(k+1)} &= \vecP^{(k)} \vecM.
\end{align*}
In this section we precisely describe the matrix $\vecM$; in section
\ref{sec:GK_correctness} we show that $\vecP^{(k)}$ approaches the
Gibbs distribution (equation \ref{eqn:RCM_Gibbs_P}).

The matrix $\vecM$ is $N! \times N!$:
rows are indexed by $\pi_1, \ldots, \pi_{N!}$ and
columns are indexed by $\pi'_1, \ldots, \pi'_{N!}$.
Most of the entries of $\vecM$ are zero:  Metropolis steps change only two
permutation sites whereas most $\pi,\pi'$ differ at more than two sites.

\begin{defn}
For $\pi,\pi'\in\SN$, define
\begin{align*}
	d(\pi,\pi') &= \#\{i=1,2,\ldots,N : \pi(i) \ne \pi'(i)\}.
\end{align*}
\end{defn}

\begin{rem*}
Note that $d(\pi,\pi') \ne 1$ since if two permutations agree on $N-1$
sites, they must agree on the remaining site.
\end{rem*}

\begin{lem}
\label{lem:d_metric}
The function $d(\pi,\pi')$ is a \plainidx{metric} on $\SN$.
\begin{proof}
Symmetry is obvious, as is non-negativity.  For positive definiteness, note
that $d(\pi,\pi')=0$ iff $\pi=\pi'$.  For the triangle inequality, let
$\pi,\pi',\pi'' \in \SN$.  Partition the set $\{1, 2, \ldots, N\}$ into the
four disjoint sets
\begin{align*}
	A &= \{i = 1,2,\ldots,N : \pi(i) =   \pi'(i), \pi'(i) =   \pi''(i)\}, \\
	B &= \{i = 1,2,\ldots,N : \pi(i) =   \pi'(i), \pi'(i) \ne \pi''(i)\}, \\
	C &= \{i = 1,2,\ldots,N : \pi(i) \ne \pi'(i), \pi'(i) =   \pi''(i)\}, \\
	D &= \{i = 1,2,\ldots,N : \pi(i) \ne \pi'(i), \pi'(i) \ne \pi''(i)\}.
\end{align*}
Then $\pi=\pi''$ on all of $A$;
$\pi\ne \pi''$ on all of $B$ and $C$;
and $\pi,\pi''$ may or may not agree on various elements of $D$:
$$
\begin{tabular}{|c||c||c||c|}
\hline $A$ & $B$ & $C$ & $D$ \\
\hline $\pi  = \pi' $ & $\pi  = \pi' $ & $\pi  \ne \pi' $ & $\pi  \ne \pi'$ \\
\hline $\pi' = \pi''$ & $\pi' \ne \pi''$ & $\pi' = \pi''$ & $\pi' \ne \pi''$ \\
\hline $\pi  = \pi''$ & $\pi \ne \pi''$ & $\pi' \ne \pi''$ & Varies \\
\hline
\end{tabular}
$$
That is,
\begin{align*}
	d(\pi, \pi')  &=   \#C + \#D, \\
	d(\pi',\pi'') &=   \#B + \#D, \\
	\#B + \#C &\le d(\pi, \pi'') \le \#B + \#C + \#D.
\end{align*}
Then
\begin{align*}
	d(\pi,\pi'') &\le \#B + \#C + \#D \le \#B + \#C + 2\#D
	= d(\pi,\pi') + d(\pi',\pi'').
\end{align*}
\end{proof}
\end{lem}

\begin{defn}
Lattice sites $\vecx,\vecy$ are \bfidx{nearest-neighbor} if
$\|\vecx-\vecy\| = 1$.
\end{defn}

%\begin{defn}
%For $\pi,\pi' \in \SN$, let
%$$
%	\Delta H = H(\pi') - H(\pi).
%$$
%If we write $\pi',\pi \in \SN$, then we mean
%$$
%	\Delta H = H(\pi) - H(\pi').
%$$
%\end{defn}

\begin{defn}
For $\pi\in\SN$, define
\begin{align*}
	R(\pi) &= \{\pi'\in\SN: d(\pi,\pi')=2 \textrm{ and }
		\|\pi(\vecx)-\pi(\vecy)\|=1\}
\end{align*}
where the $\vecx$ and $\vecy$ are taken to be the two points at which
$\pi,\pi'$ differ.  Then $R(\pi)$ is the set of permutations $\pi'$ reachable
from $\pi$ on a GK swap.
\end{defn}

The Metropolis steps are then described as follows.  For each $\pi\in\SN$,
\begin{align*}
	M(\pi,\pi') &= \begin{cases}
		C\left(1 \wedge e^{-H(\pi')+H(\pi)}\right),
		& \pi' \in R(\pi), \\
		%
		\displaystyle
		1 - \sum_{\pi' \in R(\pi)}
		C\left(1 \wedge e^{-H(\pi')+H(\pi)}\right),
		& \pi=\pi'; \\
		%
		0,
		& \textrm{ otherwise}.
	\end{cases}
\end{align*}

To find out what $C$ is:
\begin{itemize}
\item There are $N$ choices of lattice points $\vecx$.
\item For each $\vecx$, there are 6 choices of $\piy$ which are
nearest neighbors to $\pix$.
\item This double-counts the $3N$ distinct choices of $\pi'$ reachable from
$\pi$ in a single Metropolis step, since choosing $\vecx$ and then $\vecy$
results in the same Metropolis step as choosing $\vecy$ and then $\vecx$.
\end{itemize}

% xxx prove 3N distinct.

We require rows sums to be 1 for stochastic matrices so we may take
\begin{align*}
	C &= \frac{1}{3N}.
\end{align*}
This prefactor of $1/3N$ is the same for all non-zero entries of $\vecM$
for GK Metropolis.  Then
\begin{align}
\label{eqn:GK_M}
	M(\pi,\pi') &= \begin{cases}
		\frac{1}{3N}\left(1 \wedge e^{-H(\pi')+H(\pi)}\right),
		& \pi' \in R(\pi), \\
		%
		\displaystyle
		1 - \sum_{\pi' \in R(\pi)}
		C\left(1 \wedge e^{-H(\pi')+H(\pi)}\right),
		& \pi=\pi'; \\
		%
		0,
		& \textrm{ otherwise}.
	\end{cases}
\end{align}

%% ----------------------------------------------------------------
\subsection{Correctness of the GK algorithm}
\label{sec:GK_correctness}

It is clear that the GK algorithm produces a sequence of permutations, but
with what distribution?  From Markov-chain theory, we know the following:  If
the chain is irreducible, aperiodic, and satisfies detailed balance, then the
chain has the Gibbs distribution (equation \ref{eqn:RCM_Gibbs_P}) as its unique
invariant distribution.

Terminology: \bfidx{detailed balance} is the same as
\bfidx{reversibility}\index{reversible}.  Also, an irreducible, aperiodic chain
on a finite state space is called \bfidx{ergodic}.

Also note from Markov-chain theory that all states in a recurrence class have
the same period.  Thus, if we can show that the chain is irreducible (i.e. the
entire state space is a single recurrence class), then for aperiodicity of the
chain it suffices to show that a single state (e.g. the identity permutation)
has period 1.

\begin{prop}[Irreducibility]
\label{prop:GK_irreducible}
For all $\pi,\pi'$, there is an $n$ such that $M^n(\pi,\pi') > 0$.
That is, any permutation is reachable from any other.
\begin{proof}
This non-trivial result needs to be proved.
%Two-cycles generate $\SN$.
%In the GK algorithm, we don't have all two-cycles in $\SN$, but rather
%only those involving nearest neighbors.  But each site $\pi(\vecy)$ is
%equal to $\pi(\vecx)$ for some $\vecx$, or is a nearest neighbor, or is
%a second-nearest neighbor, etc.
%(This needs to be made precise.)
\end{proof}
\end{prop}

\begin{rem*}
Below we will discuss winding cycles, and the empirical fact that the GK
algorithm reaches them only rarely.  The chain is irreducible but the non-zero
transition probability can still be very small.
\end{rem*}

\begin{defn}
\label{defn:period}
A permutation $\pi$ has \plainidx{period} $p$ if any return to $\pi$ must occur
at multiples of $p$ steps.  Precisely, let $\Pi_n$ be the random variable which
is the $n$th value of the Markov chain.  Then
\begin{align*}
	p = \gcd\{n : P(\Pi_n = \pi \mid \Pi_0 = \pi) > 0\}.
\end{align*}
Furthermore, the chain is said to be aperiodic if all states are aperiodic.
\end{defn}

\begin{prop}[Aperiodicity]
\label{prop:GK_aperiodic}
The GK algorithm's Markov chain is aperiodic.
\begin{proof}
From Markov-chain theory, we know that all states in a recurrence class have
the same period.  Thus, it suffices to show that one state, e.g. the identity,
is aperiodic.  If there is non-zero probability of transitioning from the
identity to itself, the identity is an aperiodic state.  But this in fact the
case:  The identity has zero energy (equations \ref{eqn:RCM_H},
\ref{eqn:RCM_HV}).  Any state proposed as a transition from the identity is
necessarily a two-cycle, for which the distance terms in equation
\ref{eqn:RCM_H},\ref{eqn:RCM_HV} are positive.  The cycle-weight terms or
interaction terms are non-negative.  Thus $\Delta H > 0$, and the GK
Metropolis transition probability is strictly less than 1.  Therefore there is
a non-zero probability of staying at the identity permutation.
\end{proof}
\end{prop}

\begin{prop}[Detailed balance]
\label{prop:GK_DB}
For all $\pi,\pi' \in \SN$,
\begin{align}
\label{eqn:GK_DB}
	P(\pi) M(\pi, \pi') &= P(\pi') M(\pi', \pi).
\end{align}
\begin{proof}
The detailed-balance statement in terms of the Gibbs distribution (equation
\ref{eqn:RCM_Gibbs_P}) and the GK Metropolis transition matrix (equation
\ref{eqn:GK_M}) is
\begin{align*}
	\frac{e^{-H(\pi)}}{Z}
	\left(1 \wedge e^{-H(\pi')} e^{H(\pi)}\right)
	&\maybeeq
	\frac{e^{-H(\pi')}}{Z}
	\left(1 \wedge e^{-H(\pi)} e^{H(\pi')}\right).
\end{align*}
The $Z$'s cancel.
The lemma below shows that $M(\pi,\pi') \ne 0$ iff $M(\pi',\pi) \ne 0$.
If $M(\pi,\pi') = 0$, then detailed balance holds.
If $M(\pi,\pi') \ne 0$, then there are two cases.
If $H(\pi') \le H(\pi)$, then
\begin{align*}
 	e^{-H(\pi)} \left(1\right)
	&=
	e^{-H(\pi')} \left(e^{-H(\pi)} e^{H(\pi')}\right).
\end{align*}
If $H(\pi') > H(\pi)$,
\begin{align*}
	e^{-H(\pi)} \left(e^{-H(\pi')} e^{H(\pi)}\right)
	&=
 	e^{-H(\pi')} \left(1\right).
\end{align*}
In all cases, detailed balance holds.
\end{proof}
\end{prop}

\begin{lem}
\label{lem:nzdb1}
For all $\pi,\pi' \in \SN$,
\begin{align*}
	M(\pi,\pi') \ne 0 \iff M(\pi', \pi) \ne 0.
\end{align*}
\begin{proof}
If $d(\pi,\pi') > 2$, then $M(\pi,\pi') = 0$ and $M(\pi',\pi) = 0$.

If $d(\pi,\pi') = 2$, then $\pi$ and $\pi'$ differ at two sites
$\vecx$ and $\vecy$.  Put
\begin{align*}
	\pi (\vecx) &= \vecu, &
	\pi'(\vecx) &= \vecv, \\
	\pi (\vecy) &= \vecv, &
	\pi'(\vecy) &= \vecu.
\end{align*}
If $\|\vecu-\vecv\| = 1$ then $M(\pi,\pi') \ne 0$ and $M(\pi',\pi) \ne 0$
since $\vecu$ and $\vecv$ are nearest-neighbor lattice sites.
If $\|\vecu-\vecv\| > 1$ then $M(\pi,\pi') = 0$ and $M(\pi',\pi) = 0$
since $\vecu$ and $\vecv$ are not nearest-neighbor lattice sites.

Last, if $\pi=\pi'$, then $M(\pi,\pi') = M(\pi',\pi)$.
\end{proof}
\end{lem}

This lemma completes the proof that the GK algorithm satisfies detailed
balance and thus has the Gibbs distribution as its invariant distribution.

The following proposition is not a correctness result, but rather a sanity
check.  It shows that cycles may grow or shrink upon GK moves.

\begin{figure}[!htb]
\begin{center}
\psfragscanon
\includegraphics[scale=0.7]{figures/gkcycles.eps}
\caption[GK swaps merge disjoint cycles and split single cycles.]
	{GK swaps merge disjoint cycles and split single cycles.
	The left-hand permutation can be reached from the right-hand permutation
	via a GK swap, and vice versa.
	\label{fig:gkcycles}}
\end{center}
\end{figure}

\begin{prop}
\label{prop:GK_join_or_split}
If $\vecx$ and $\vecy$ are in disjoint cycles before a non-trivial GK swap
then they are in the same cycle afterward and vice versa (see figure
\ref{fig:gkcycles}).
\begin{proof}
First suppose that $\vecx$ and $\vecy$ are in disjoint cycles.  Let the
respective cycle lengths be $\ell(\vecx) = a$ and $\ell(\vecy)=b$.
Those cycles are
$$
	\vecx        \mapsto
	\pi(\vecx)   \mapsto
	\pi^2(\vecx) \mapsto
	\ldots       \mapsto
	\pi^{a-1}(\vecx) \mapsto
	\vecx
\qand
	\vecy        \mapsto
	\pi(\vecy)   \mapsto
	\pi^2(\vecy) \mapsto
	\ldots       \mapsto
	\pi^{b-1}(\vecy) \mapsto
	\vecy.
$$
Since these are disjoint cycles, all elements listed are distinct
lattice sites.  After the swap, we have
$$
	\vecy        \mapsto
	\pi(\vecx)   \mapsto
	\pi^2(\vecx) \mapsto
	\ldots       \mapsto
	\pi^{a-1}(\vecx) \mapsto
	\vecx
\qand
	\vecx        \mapsto
	\pi(\vecy)   \mapsto
	\pi^2(\vecy) \mapsto
	\ldots       \mapsto
	\pi^{b-1}(\vecy) \mapsto
	\vecy.
$$
This is a single cycle of length $a+b$, starting with $\vecy$, including
$\vecx$, and returning to $\vecy$.

Second,  suppose that $\vecx$ and $\vecy$ are in the same cycle.
Let $a$ be the smallest positive integer such that $\pi^a(\vecx) = \vecy$;
let $b$ be the smallest positive integer such that $\pi^b(\vecy) = \vecx$.
(These numbers are both positive since the swap is non-trivial, i.e.
$\vecx \ne \vecy$.)
Then we have
$$
	\vecx        \mapsto
	\pi(\vecx)   \mapsto
	\pi^2(\vecx) \mapsto
	\pi^{a-1}(\vecx) \mapsto
	\vecy        \mapsto
	\pi(\vecy)   \mapsto
	\pi^2(\vecy) \mapsto
	\ldots       \mapsto
	\pi^{b-1}(\vecy) \mapsto
	\vecx.
$$
This is a single cycle of length $a+b$; all lattice sites listed are
distinct.  After the swap, we have
$$
	\vecy        \mapsto
	\pi(\vecx)   \mapsto
	\pi^2(\vecx) \mapsto
	\pi^{a-1}(\vecx) \mapsto
	\vecy
\qand
	\vecx        \mapsto
	\pi(\vecy)   \mapsto
	\pi^2(\vecy) \mapsto
	\ldots       \mapsto
	\pi^{b-1}(\vecy) \mapsto
	\vecx.
$$
These are disjoint cycles of length $a$ and $b$, respectively; the first
contains $\vecx$ and the second contains $\vecy$.
\end{proof}
\end{prop}

%% ================================================================
\newpage
\section{The random-cycle model and the worm algorithm}

Here an alternative to the GK algorithm is motivated and proved correct.

%% ----------------------------------------------------------------
\subsection{Winding cycles}

Recall that we have permutations on $[0,L]^3$ with periodic boundary
conditions.  Topologically, this is a 3-torus.  Permutation cycles may wind
around the 3-torus some number of times in the $x$, $y$, and/or $z$ directions.
If a cycle goes around once in the clockwise direction, we want to say it has
sign $+1$; likewise, we want sign $-1$ for the counterclockwise direction.  The
following definition formalizes this intuition.

\begin{defn}
The \bfidx{winding number} $\vecW$ of a permutation is the triple of integers
\begin{align*}
	\vecW = (W_x,W_y,W_z) &=
	\frac{1}{L} \sum_{i=1}^N (\vecxpii - \vecxi).
\end{align*}
We also write
\begin{align*}
	\vecW^2 &= \vecW \cdot \vecW = W_x^2 + W_y^2 + W_z^2.
\end{align*}
\end{defn}

It is found empirically with the GK algorithm that winding cycles are created
with opposite signs, such that permutations have winding number zero.  E.g.
there might be a cycle with $W_x=1$ and another cycle with $W_x=-1$.  The same
problem is observed in PIMC studies.  (References TBD.)

One solution is to modify the GK algorithm to reverse, with probability $1/2$,
the direction of arrows in modified cycles.  This is a partial remedy:  it
results in permutations with even winding numbers.

%[need a histogram here]

The \bfidx{superfluid fraction} is [cite PC87]
\begin{align*}
	f_S &= \frac{\langle \vecW^2 \rangle L^2}{3 \beta N}
	= \frac{\langle \vecW^2 \rangle}{3 \beta L}.
\end{align*}
We use this as an order parameter with which to detect the critical
temperature.

%% ----------------------------------------------------------------
\subsection{PIMC motivation}

Say something here about PIMC, worldlines, and the gist of the PIMC worm
algorithm.  Mention the grand-canonical ensemble.  References TBD.

% xxx
[figures here]

%% ----------------------------------------------------------------
\subsection{Idea of the worm algorithm}

The key selling point of the random-cycle model is that Brownian bridges have
been integrated out.  Most of the complexity of PIMC simulations goes away.  If
I want to adapt a PIMC worm algorithm to the RCM, I need to spend a lot of my
time learning about PIMC, but probably ultimately most of the complexity will
also go away.  Instead, it is simpler to ask:  If we were to have a worm
algorithm for the random-cycle model, what properties would it have?  We
require the following:

\begin{itemize}
\item We have a lattice with a fixed number $N$ of points.  There is no
desire to work in the grand-canonical ensemble.
\item We want the ability to open and close permutation cycles.
(An open cycle is a ``worm''.)
\item Given that, tips of open cycles may wander around the 3-torus before
closing, permitting arbitrary winding numbers.
\end{itemize}

Idea: sometimes open a cycle, then modify it with GK-like steps, then close it
again.  Following PIMC worm, all Metropolis steps involve the worm.  This does
touch all lattice points:  a worm is opened at a site, then modified, then
closed.  Then, a worm is opened somewhere else, and so on.

Question:  Can we leverage our knowledge of permutations?

\begin{figure}[!htb]
\begin{center}
\psfragscanon
\includegraphics[scale=0.7]{figures/worm1.eps}
\caption{Open cycles as permutations on $N+1$ points.
	\label{fig:worm1}}
\end{center}
\end{figure}

Closed cycle:
$$
	\pcmatrix{
		1 & 2 & 3 \\
		2 & 3 & 1 \\
	}
$$
Open cycle:
$$
	\pcmatrix{
		1 & 2 & 3 & {}\\
		2 & 3 & {} & 1 \\
	}
$$
Here, $1\mapsto 2$, $2\mapsto 3$, $3 \mapsto$ nothing, and nothing $\to 1$.
Call that nothing \emph{something} --- the \bfidx{wormhole point}.  It is an
$(N+1)$st point:
$$
	\pcmatrix{
		1 & 2 & 3 & w \\
		2 & 3 & w & 1 \\
	}
$$
Henceforth, the wormhole point will be written as $w$ or $N+1$.  In diagrams,
it will be an open dot while the other $N$ points will be written with filled
dots.  (See figure \ref{fig:worm1}.)

Now we have permutations on $\SNp$.  Given $\pi\in\SN$, \plainidx{inject} $\pi$
into $\SNp$ via $\pi(w)=w$.

\begin{defn}
For $\pi\in\SNp$, we say $\pi$ is a \bfidx{closed permutation}
if $\pi(w)=w$.
We say $\pi$ is an \bfidx{open permutation}
if $\pi(w) \ne w$.
Likewise, a cycle of $\pi$ is open or closed, respectively, if it does
or does not contain $w$.
\end{defn}

\begin{rem*}
The PIMC jargon is that closed permutations are in the \emphidx{$Z$ sector}
(for partition function), while open permutations are in the \emphidx{$G$
sector} (for Matsubara Green's function).
\end{rem*}

The goal is to invent an energy function, Gibbs distribution, and Metropolis
algorithm for these extended permutations in $\SNp$ such that the marginal
distribution on $\SNp$, conditioned on closed permutations, matches the RCM
Gibbs distribution (equation \ref{eqn:RCM_Gibbs_P}).  Then, random variables
will be sampled only at closed permutations.

%% ----------------------------------------------------------------
\subsection{Extended random-cycle model}

Recall that we inject $\pi\in\SN$ into $\SNp$ via $\pi(w)=w$.  The $(N+1)$st
point $w$ is \bfidx{non-spatial}:  it has no distance associated with it.

\begin{defn}
The \bfidx{extended lattice} is\index{$\mathcal{L}'$}
$$
	\mcL' := \mcL \cup \{w\}
$$
\end{defn}

\begin{defn}
For $\pi\in\SNp$, define
\begin{align}
\label{eqn:ERCM_H}
	H'(\pi) &= \frac{1}{4\beta} \sum_{\stackrel{i=1}{\pi(\vecxi) \ne w}}^N
		\|\vecxi - \vecxpii\|^2 + \sum_{\ell=2}^N \alpha_\ell N_\ell(\pi)
		+ \gamma 1_{\SNpc}(\pi).
\end{align}
\end{defn}
Note that this \bfidx{extended energy} agrees with the RCM energy (equation
\ref{eqn:RCM_H}) on closed permutations.  This is used to prove the
marginality condition below.

A small positive $\gamma$ factor is sufficient to establish aperiodicity of the
Markov chain (proposition \ref{prop:worm_aperiodic}).

The \bfidx{extended Gibbs distribution} and \bfidx{extended partition function}
are defined in the obvious way.
\begin{defn}
Let
\begin{align}
\label{eqn:ERCM_Gibbs_P}
	P'(\pi) = \frac{e^{-H'(\pi)}}{Z'}
\end{align}
where the \plainidx{partition function} is
\begin{align}
\label{eqn:ERCM_Gibbs_Z}
	Z' &= \sum_{\pi\in\SNp} e^{-H'(\pi)}.
\end{align}
\end{defn}

%% ----------------------------------------------------------------
\subsection{Proof of marginality}

As long as the energy function for the ERCM and the RCM agree on closed
permutations, the desired marginality condition holds.  This means that either
of the interactions in \ref{eqn:RCM_H} or \ref{eqn:RCM_HV} --- or any other
to-be-invented interaction models --- may use the worm algorithm as long as
they agree on closed permutations.

\begin{prop}[Marginality condition]
\label{prop:marginality}
Let $\SN \into \SNp$ by taking $\pi(w)=w$.
Let $H,H'$ be energy functions on $\SN$ and $\SNp$, respectively,
such that for all $\pi\in\SN$,
\begin{align}
	H(\pi) = H'(\pi).
\end{align}
Let $P,P',Z,Z'$ be as above.  Then for $\pi\in\SN$,
\begin{align}
\label{eqn:marg_P}
	P'(\pi \mid \pi\in\SN) = P(\pi).
\end{align}
\begin{proof}
Let $\pi\in\SN$.  The left-hand side of equation \ref{eqn:marg_P} is, by
definition of conditional expectation,
\begin{align*}
	P'(\pi \mid \pi\in\SN)
	&= \frac{P'(\pi) \;1_{\SN}(\pi)}{P'(\SN)}.
\end{align*}
The numerator is the Gibbs probability for closed permutations, or zero for
open ones:
\begin{align*}
	P'(\pi) \;1_{\SN}(\pi)
	&= \frac{1}{Z'}e^{-H'(\pi)} \;1_{\SN}(\pi)
	= \frac{1}{Z'}e^{-H (\pi)} \;1_{\SN}(\pi)
\end{align*}
since $H$ and $H'$ agree on closed permutations.  The denominator is the total
probability of closed permutations:
\begin{align*}
	P'(\SN)
	&= \frac{1}{Z'} \sum_{\pi \in\SN} e^{-H'(\pi)}
	= \frac{1}{Z'} \sum_{\pi \in\SN} e^{-H(\pi)}.
\end{align*}
Since $\pi\in\SN$, the ratio is
\begin{align*}
	\frac{
		\frac{1}{Z'}e^{-H (\pi)} \;1_{\SN}(\pi)
	}{
		\frac{1}{Z'} \sum_{\pi \in\SN} e^{-H(\pi)}
	}
	&= \frac{
		e^{-H (\pi)} \;1_{\SN}(\pi)
	}{
		\sum_{\pi \in \SN} e^{-H(\pi)}
	} \\
	%
	&= \frac{
		e^{-H (\pi)} \;1_{\SN}(\pi)
	}{
		Z
	} \\
	%
	&= P(\pi).
\end{align*}
\end{proof}
\end{prop}

%As a sanity check, we see whether the marginal density for the $\beta=0$
%case recovers uniform permutations on $\SN$, and whether the marginal density
%for the $\beta=\infty$ case recovers the singleton density on $\SN$ supported
%at the identity permutation.
%
%[Needs to be typed up.]

%% ----------------------------------------------------------------
\subsection{The worm algorithm}

Now that we have the correct Gibbs distribution for the ERCM, the next step
is to devise a Metropolis algorithm to sample from it.  Below,
we will prove correctness.

\begin{figure}[!htb]
\begin{center}
\psfragscanon
\includegraphics[scale=0.7]{figures/wormmoves.eps}
\caption{Metropolis moves for the worm algorithm.
	\label{fig:wormmoves}}
\end{center}
\end{figure}

The \bfidx{worm algorithm} is as follows:
\begin{itemize}

\item Start with the identity or uniform-random closed permutation.

\item The permutation is now closed, so $\pi(w)=w$.  Select a lattice
site $\vecx$ at uniform random.  With probability proportional to $1 \wedge
\edh$, open the permutation by swapping the arrows of $\vecx$ and $w$.
This is called an \bfidx{open} move.
(See figure \ref{fig:wormmoves}.)

%	\begin{align*}
%	\pi: &
%	\pcmatrix{
%		\ldots & \vecx      & \ldots &     w      & \ldots \\
%		       & \downarrow &        & \downarrow &        \\
%		\ldots & \pi(\vecx) & \ldots & \pi(w)=w   & \ldots \\
%	} &
%	\pi': &
%	\pcmatrix{
%		\ldots & \vecx      & \ldots & \vecy      & \ldots \\
%		       & \downarrow &        & \downarrow &        \\
%		\ldots &     w & \ldots & \pi(\vecx) & \ldots \\
%	} \\
%	\end{align*}

\item Now that the permutation is open, do a \bfidx{head swap}, \bfidx{tail
swap}, or \bfidx{close}.

\item Head swap:  Pick a lattice site $\vecx$ nearest-neighbor to the lattice
site $\piiw$.  With probability proportional to $1 \wedge \edh$, swap arrows as
in figure \ref{fig:wormmoves}.  The head swap is trivial if $\vecx = \piiw$,
which happens only if the head swap is rejected.  The head swap would be a
close if $\vecx = w$, but we choose $\vecx$ to be a lattice site.  Thus, the
permutation remains open on a head swap.

% * A trivial head swap is a stay:  if x == piiw.
% * A head swap is a close if x == w.

\item Tail swap:  Pick a lattice site $\pix$ nearest-neighbor to the lattice
site $\piw$.  With probability proportional to $1 \wedge \edh$, swap arrows as
in figure \ref{fig:wormmoves}.  The tail swap is trivial if $\pix = \piw$,
which happens only if the tail swap is rejected.  The tail swap would be a
close if $\pix = w$, but we choose $\pix$ to be a lattice site.  Thus, the
permutation remains open on a tail swap.

% * A trivial tail swap is a say:  if x == w.
% * A tail swap is a close if pi(x) == w.

\item Close: with probability proportional to $1 \wedge \edh$, swap arrows as
in figure \ref{fig:wormmoves}.  The permutation is now closed.

\item Once the permutation is closed --- after an open, some number of
head/tail swaps, and a close, or after a rejected open --- a \bfidx{worm sweep}
has been completed.  At every sweep (or after every specified number of sweeps
as noted in the autocorrelation footnote above), one may obtain a value of
random variable(s) for inclusion in computation of their sample means.

\end{itemize}

\begin{defn}
\label{defn:worm_trivial}
A head swap at $\vecx$ is \bfidx{trivial} if $\vecx = \piiw$;
a tail swap at $\vecx$ is trivial if $\pix = \piw$.
\end{defn}

%% ----------------------------------------------------------------
\subsection{Fibration of $\SNp$ over $\SN$}

The definitions and lemmas in this section facilitate explicit construction
of the Markov matrix, and are necessary for proving correctness of the worm
algorithm.

The key points about the structure of the fibration, formalized by the lemmas
below, are:
\begin{itemize}
\item Each open permutation is one opener move away from a base closed
permutation.  The $N$ open permutations above a base closed permutation $\pi$
are the \plainidx{fiber} over $\pi$.
\item This induces a \plainidx{disjoint partition} of the open permutations
$\SNpc$.
\item Opens and closes stay within fibers; non-trivial head swaps and tail
swaps \plainidx{cross fibers}.
\item For each open permutation, the six non-trivial head swaps and six tail
swaps result in twelve distinct permutations.
\item Head swaps and tail swaps are transitive on fibers.
\end{itemize}

\begin{figure}[!htb]
\begin{center}
\psfragscanon
\includegraphics{figures/fiber4.eps}
\caption[Fibration of $\mcS_4$ over $\mcS_3$.]
	{Fibration of $\mcS_4$ over $\mcS_3$.  Closed permutations (i.e. $\mcS_3$)
	are along the bottom row; open permutations (i.e. $\mcS_4 \setminus
	\mcS_3$) are above the bottom row.  The column, or fiber, above each closed
	permutation $\pi$ contains the open permutations obtained from $\pi$ by an
	opener move.  Arrows modified by opener moves are shown in black.
	\label{fig:fiber4}}
\end{center}
\end{figure}

We first define maps corresponding to worm Metropolis moves.

\begin{defn} The four worm Metropolis moves of figure \ref{fig:wormmoves} may
be viewed in terms of maps.  Throughout, $\vecz \in \mcL \cup \{w\}$.

Let $O: \;\SN\times\mcL \to \SNpc$ send $O(\pi,\vecx) = \pi'$ such that
\begin{align*}
	\pi'(\vecx) &= w, \\
	\pi'(w)     &= \pix, \\
	\pi'(\vecz) &= \pi(\vecz), \quad \vecz \ne \vecx, w.
\end{align*}
Let $C: \;\SNpc \to \SN$ send $C(\pi) = \pi'$ such that
\begin{align*}
	\pi'(\piiw) &= \piw, \\
	\pi'(w)     &= w, \\
	\pi'(\vecz) &= \pi(\vecz), \quad \vecz \ne \piiw, w.
\end{align*}
Let $S: \;\SNpc\times\mcL \to \SNpc$ send $S(\pi,\vecx) = \pi'$ such that
\begin{align*}
	\pi'(\vecx) &= w, \\
	\pi'(\piiw) &= \pix, \\
	\pi'(\vecz) &= \pi(\vecz), \quad \vecz \ne \vecx, \piiw.
\end{align*}
Let $T: \;\SNpc\times\mcL \to \SNpc$ send $T(\pi,\vecx) = \pi'$ such that
\begin{align*}
	\pi'(\vecx) &= \piw, \\
	\pi'(w)     &= \pix, \\
	\pi'(\vecz) &= \pi(\vecz), \quad \vecz \ne \vecx, w.
\end{align*}

\end{defn}

Throughout the proofs of the fibration-structure lemmas, we will use the
following fact.
\begin{lem}
\label{lem:pineq}
If $\vecx \ne \vecy$, then $\pix \ne \piy$ and $\piix \ne \piiy$.
\begin{proof}
%By contrapositive:  if $\pix = \piy$ then $\pii(\pi(\vecx)) = \pii(\pi(\vecy))$
%and so $\vecx = \vecy$.
If $\vecx \ne \vecy$ and $\pix = \piy$, then $\pi$ is not 1-1 which is
a contradiction since $\pi$ is a permutation.
This applies to $\pii$ as well, since $\pii$ is also a
permutation.
\end{proof}
\end{lem}

Now we may prove the fibration-structure lemmas.

\begin{lem}
Each open permutation $\pi$ is one opener move away from a base closed
permuation $\pi'$.  That is,  for all $\pi \in \SNpc$, there exists $\pi' \in
\SN$ such that $C(\pi) = \pi'$.
\begin{proof}
Let $\pi\in\SNp$.  Since $\pi$ is open, $\piw \ne w$ and $\piiw \ne w$.
Let $\veca = \piiw$ and $\vecb = \piw$.  Both are lattice points.
Applying $C$, we have $C(\pi)=\pi'$ where $\pi'(\veca)=\vecb$, $\pi'(w)=w$,
and $\pi'(\vecz)=\pi(\vecz)$ for all remaining lattice points $\vecz \ne
\veca, \vecb$.  Since $\pi'(w)=w$, $\pi'$ is closed.
\end{proof}
\end{lem}

\begin{defn}
For $\pi\in\SN$, $C^{-1}(\pi) \subset \SNpc$ is the \textbf{fiber} of open
permutations over $\pi$.
\end{defn}

\begin{lem}
\label{lem:worm_opens_and_closes}
Opens and closes stay within fibers, and each fiber has $N$ elements.
\begin{proof}
Closes stay within fibers by definition of fiber.  Next, fix $\pi\in\SN$ and
let $\vecx_1, \vecx_2 \in \mcL$.  (These are two different ways to open the
same closed permutation.) Let
$$
	\pi'_1 = O(\pi,\vecx_1), \quad
	\pi'_2 = O(\pi,\vecx_2).
$$
Then $\pi'_1$ and $\pi'_2$ have
$$
	\vecx_1 \mapsto w \mapsto \pi(\vecx_1), \qquad
	\vecx_2 \mapsto w \mapsto \pi(\vecx_2),
$$
respectively, agreeing with $\pi$ at all other lattice points $\vecz$.
Now, $C(\pi'_1)$ and $C(\pi'_2)$ have
$$
	\vecx_1 \mapsto \pi(\vecx_1), w \mapsto w, \qquad
	\vecx_2 \mapsto \pi(\vecx_2), w \mapsto w
$$
respectively, agreeing with $\pi$ at all other lattice points $\vecz$.  But
this means $C(\pi'_1)$ agrees with $C(\pi'_2)$ agree at all points of $\mcL'$,
so $C(\pi'_1) = C(\pi'_2)$.  Thus, $\pi'_1$ and $\pi'_2$ are in the same fiber.

For the last claim, fix $\pi\in\SN$ and enumerate the $N$ lattice points of
$\mcL$ as $\vecx_1, \ldots, \vecx_N$.  We claim that the $N$ permutations
$$
	\pi'_1 = O(\pi,\vecx_1), \ldots, \pi'_N = O(\pi,\vecx_N),
$$
which are all now known to be in the same fiber, are all distinct.  To see
this, fix $i \ne j$ from out of $\{1, 2, \ldots, N\}$.  Then $\pi'_i$ and
$\pi'_j$ have
$$
	\vecx_i \mapsto w \mapsto \pi(\vecx_i), \qquad
	\vecx_j \mapsto w \mapsto \pi(\vecx_j).
$$
Since $\vecx_i \ne \vecx_j$, by lemma \ref{lem:pineq} $\pi(\vecx_i) \ne
\pi(\vecx_j)$.  Since
$$
	\pi'_i(w) = \pi(\vecx_i) \ne \pi(\vecx_j) = \pi'_j(w),
$$
$\pi'_i$ and $\pi'_j$ send $w$ to different points.  Therefore, the
permutations $\pi'_i$ and $\pi'_j$ are distinct.
\end{proof}
\end{lem}

\begin{lem}
This fibration induces a disjoint partition of the open permutations $\SNpc$.
That is, for $\pi'_1, \pi'_2 \in \SN$,
\begin{align*}
	\pi'_1 \ne \pi'_2 \implies
	C^{-1}(\pi'_1) \cap C^{-1}(\pi'_2) &= \emptyset
	\qqand
	\bigcup_{\pi\in\SN} C^{-1}(\pi) = \SNpc.
\end{align*}
\begin{proof}
For the first claim, suppose the intersection is non-empty.  Let $\pi \in\SNpc$
be such that $\pi \in C^{-1}(\pi'_1)$ and $\pi \in C^{-1}(\pi'_2)$.  This means
$C(\pi) = \pi'_1$ and $C(\pi) = \pi'_2$ with $\pi'_1 \ne \pi'_2$, which is a
contradiction since the map $C$ is uniquely defined for all $\pi \in \SNpc$.

For the second claim: there are $N!$ closed permutations.  We know from the
first claim that the $N!$ fibers, one above each closed permutation, are all
disjoint.  From lemma \ref{lem:worm_opens_and_closes}, we know that each fiber
has $N$ elements.  We have accounted for all $N\cdot N! = (N+1)!-N!$ open
permutations, so we must have all of $\SNpc$.
\end{proof}
\end{lem}

%           * * * * * * * * each of height N
%           * * * * * * * *
%           * * * * * * * *
% N! fibers * * * * * * * *
% N! closed . . . . . . . .

\begin{lem}
Non-trivial head swaps and tail swaps (definition \ref{defn:worm_trivial})
cross fibers.
\begin{proof}
First consider head swaps.
Let $\pi,\pi' \in \SNpc$ differ by a non-trivial head swap, namely, there is
$\vecx \ne \piiw$ such that $\pi' = S(\pi, \vecx)$.
Then $\pi$ and $\pi'$ have
$$
	\begin{array}{lccccc}
	\pi:  & \vecx &\mapsto& \pix &\mapsto& \pi^2(\vecx), \\
	\pi': & \piiw &\mapsto& \pix &\mapsto& \pi^2(\vecx), \\
	\end{array}
\qquad
	\begin{array}{lccccc}
	\piiw &\mapsto&    w &\mapsto& \piw, \\
	\vecx &\mapsto&    w &\mapsto& \piw,
	\end{array}
$$
respectively.  Now apply $C$ to each: $C(\pi)$ and $C(\pi')$ have
$$
	\begin{array}{lccccc}
	C(\pi):  & \vecx &\mapsto& \pix &\mapsto& \pi^2(\vecx), \\
	C(\pi'): & \piiw &\mapsto& \pix &\mapsto& \pi^2(\vecx), \\
	\end{array}
\qquad
	\begin{array}{lccccc}
	\piiw &\mapsto&    \piw, \\
	\vecx &\mapsto&    \piw,
	\end{array}
\qquad
	\begin{array}{lccccc}
	w &\mapsto&    w, \\
	w &\mapsto&    w,
	\end{array}
$$
respectively.  Since $\vecx \ne \piiw$, $C(\pi) \ne C(\pi')$.

Next, consider tail swaps.
Let $\pi,\pi' \in \SNpc$ differ by a non-trivial tail swap, namely, there is
$\pix \ne \piw$ such that $\pi' = T(\pi, \vecx)$.
Then $\pi$ and $\pi'$ have
$$
	\begin{array}{lccccc}
	\pi:  & \piix &\mapsto& \vecx &\mapsto& \pix, \\
	\pi': & \piix &\mapsto& \vecx &\mapsto& \piw, \\
	\end{array}
\qquad
	\begin{array}{lccccc}
	\piiw &\mapsto&    w &\mapsto& \piw, \\
	\piiw &\mapsto&    w &\mapsto& \pix, \\
	\end{array}
$$
respectively.  Now apply $C$ to each: $C(\pi)$ and $C(\pi')$ have
$$
	\begin{array}{lccccc}
	C(\pi):  & \piix &\mapsto& \vecx &\mapsto& \pix, \\
	C(\pi'): & \piiw &\mapsto& \vecx &\mapsto& \piw, \\
	\end{array}
\qquad
	\begin{array}{lccccc}
	\piiw &\mapsto&    \piw, \\
	\piiw &\mapsto&    \pix,
	\end{array}
\qquad
	\begin{array}{lccccc}
	w &\mapsto&    w, \\
	w &\mapsto&    w,
	\end{array}
$$
respectively.  Since $\pix \ne \piw$, $C(\pi) \ne C(\pi')$.
\end{proof}
\end{lem}

\begin{lem}
\label{lem:worm_distinct_dozen}
For each open permutation, the six non-trivial head swaps and six non-trivial
tail swaps result in twelve distinct permutations.
\begin{proof}
Fix $\pi\in\SNpc$.
Let $\vecx_1, \ldots, \vecx_6$ be the six nearest-neighbor lattice sites to the
lattice site $\piiw$;
let $\vecy_1, \ldots, \vecy_6$ be the six lattice sites
such that $\pi(\vecy_1), \ldots, \pi(\vecy_6)$ are nearest-neighbor lattices
site to the
lattice site $\piw$.  (See figure \ref{fig:wormmoves}.)

First, we show that the six permutations $S(\pi,\vecx_1), \ldots,
S(\pi,\vecx_6)$ are distinct.  Let $i \ne j$ for $i,j=1, \ldots, 6$; let $\pi_i
= S(\pi,\vecx_i)$ and $\pi_j = S(\pi,\vecx_j)$.  Then $\pi$ has
$$
	\begin{array}{lccccc}
	\pi:   & \vecx_i &\mapsto& \pi(\vecx_i), \\
	\end{array}
\qquad
	\begin{array}{lccccc}
	\vecx_j &\mapsto& \pi(\vecx_j), \\
	\end{array}
\qquad
	\begin{array}{lccccc}
	\piiw &\mapsto& w; \\
	\end{array}
$$
$\pi_i$, and $\pi_j$ have
$$
	\begin{array}{lccccc}
	\pi_i: & \vecx_i &\mapsto& w, \\
	\pi_j: & \vecx_j &\mapsto& w, \\
	\end{array}
\qquad
	\begin{array}{lccccc}
	\piiw &\mapsto& \pi(\vecx_i), \\
	\piiw &\mapsto& \pi(\vecx_j), \\
	\end{array}
$$
respectively.
Since $\vecx_i \ne \vecx_j$, $\pi_i \ne \pi_j$.


Second, we show that the six permutations
$T(\pi,\vecy_1), \ldots, T(\pi,\vecy_6)$ are distinct.
Let $i \ne j$ for $i,j=1, \ldots, 6$; let $\pi_i
= T(\pi,\vecy_i)$ and $\pi_j = T(\pi,\vecy_j)$.  Then $\pi$ has
$$
	\begin{array}{lccccc}
	\pi:   & \vecy_i &\mapsto& \pi(\vecy_i), \\
	\end{array}
\qquad
	\begin{array}{lccccc}
	\vecy_j &\mapsto& \pi(\vecy_j), \\
	\end{array}
\qquad
	\begin{array}{lccccc}
	w &\mapsto& \piw; \\
	\end{array}
$$
$\pi_i$, and $\pi_j$ have
$$
	\begin{array}{lccccc}
	\pi_i: & \vecy_i &\mapsto& \piw, \\
	\pi_j: & \vecy_j &\mapsto& \piw, \\
	\end{array}
\qquad
	\begin{array}{lccccc}
	w &\mapsto& \pi(\vecy_i), \\
	w &\mapsto& \pi(\vecy_j), \\
	\end{array}
$$
respectively.  Since $\vecy_i \ne \vecy_j$, by lemma \ref{lem:pineq}
$\pi(\vecy_i) \ne \pi(\vecy_j)$.  Since $\pi_i,\pi_j$ send $w$ to to different
sites, $\pi_i \ne \pi_j$.

Third, we show that the head-swaps of $\pi$ are distinct from the tail-swaps
of $\pi$.  Fix $\pi\in\SNpc$ and let $i,j \in \{1, \ldots, 6\}$.  Then $\pi$
has
$$
	\begin{array}{lccccc}
	\pi:   & \vecx_i &\mapsto& \pi(\vecx_i), \\
	\end{array}
\qquad
	\begin{array}{lccccc}
	\vecy_j &\mapsto& \pi(\vecy_j), \\
	\end{array}
\qquad
	\begin{array}{lccccc}
	\piiw &\mapsto& w &\mapsto& \piw; \\
	\end{array}
$$
$S(\pi,\vecx_i)$ and $T(\pi,\vecy_j)$ have
$$
	\begin{array}{rccccc}
	S(\pi,\vecx_i): & \piiw &\mapsto& \pi(\vecx_i), \\
	T(\pi,\vecy_j): & \vecy_j &\mapsto& \piw, \\
	\end{array}
\qquad
	\begin{array}{rccccc}
	\vecx_i &\mapsto& w &\mapsto& \piw; \\
	\piiw   &\mapsto& w &\mapsto& \vecy_j; \\
	\end{array}
$$
respectively.  Under these two permutations, $w$ has images $\piw$ and
$\vecy_j$, respectively, and preimages $\vecx_i$ and $\piiw$.  By definition
\ref{defn:worm_trivial}, the non-trivial head swap $S(\pi,\vecx_i)$ has
$\vecx_i \ne \piiw$ and the non-trivial tail swap $T(\pi,\vecy_j)$ has $\piw
\ne \vecy_j$.  Thus, $S(\pi,\vecx_i)$ and $T(\pi,\vecy_j)$ are distinct
permutations.
\end{proof}
\end{lem}

\begin{lem}
Head swaps and tail swaps are transitive on fibers.
\begin{proof}
This needs to be proved.  This key result will establish irreducibility of the
chain.
\end{proof}
\end{lem}

%% ----------------------------------------------------------------
\subsection{Explicit construction of the Markov matrix}

Transition probabilities were described as being proportional to $1 \wedge
\edh$.  We put the constants of proportionality to be:
\begin{itemize}
\item $a$ for head swaps and tail swaps;
\item $b$ for closer moves;
\item $c$ for opener moves.
\end{itemize}
For GK, we chose $C$ solely by the row-normalization condition.  Here, with a
more complicated algorithm, we will choose them to satisfy detailed balance.

The Markov matrix is now $(N+1)! \times (N+1)!$:
\begin{itemize}

\item A closed permutation transitions only to itself, or to any of the $N$
open permutations in the fiber above it.  Thus, there are $N+1$ non-zero
entries in $\pi$'s row of $\vecM$.

\item An open permutation transitions to any of the 12 open permutations
available by head-swapping or tail-swapping, or to itself, or to the closed
permutation at the base of its fiber.  Thus, there are 14 non-zero entries in
$\pi$'s row of $\vecM$.

\end{itemize}

\begin{defn}
For open $\pi$, let
$$
	\{\vecx_1, \ldots, \vecx_6\} = \{\vecx \in \mcL: \|\vecx,\piiw\|=1\}
\qqand
	\{\vecy_1, \ldots, \vecy_6\} = \{\vecy \in \mcL: \|\piy,\piw\|=1\}.
$$
Then define
\begin{align*}
	R_S(\pi) &= \{S(\pi,\vecx_1), \ldots, S(\pi,\vecx_6)\}, \\
	R_T(\pi) &= \{T(\pi,\vecy_1), \ldots, T(\pi,\vecy_6)\}.
\end{align*}
These are the twelve open permutations reachable from $\pi$ via head swaps and
tail swaps, respectively (lemma \ref{lem:worm_distinct_dozen}).
For closed $\pi$, define
\begin{align*}
	R_O(\pi) &= \{O(\pi,\vecx_1), \ldots, O(\pi,\vecx_N)\}.
\end{align*}
These are the $N$ open permutations reachable from $\pi$ via opener moves.
\end{defn}

The entries of the transition matrix are as follows.

If $\pi$ is closed:
\begin{align*}
	M(\pi,\pi') &= \begin{cases}
		\displaystyle
		c\left(1 \wedge e^{-H(\pi')+H(\pi)}\right), &
			\pi' \in R_O(\pi);
			\\
		\displaystyle
		1 - \sum_{\pi' \in R_O(\pi)}
			c\left(1 \wedge e^{-H(\pi')+H(\pi)}\right),
			& \pi'=\pi; \\
		0, & \textrm{ otherwise}.
	\end{cases}
\end{align*}

If $\pi$ is open:
\begin{displaymath}
	M(\pi,\pi') = \begin{cases}
		\displaystyle
		a\left(1 \wedge e^{-H(\pi')+H(\pi)}\right),
			& \pi' \in R_S(\pi); \\
	%
		\displaystyle
		a\left(1 \wedge e^{-H(\pi')+H(\pi)}\right),
			& \pi' \in R_T(\pi); \\
	%
		\displaystyle
		b\left(1 \wedge e^{-H(\pi')+H(\pi)}\right),
			& \pi' = C(\pi); \\
	%
		\displaystyle
		1
		- \sum_{\pi'\in R_S(\pi) \cup R_T(\pi)}
			a\left(1 \wedge e^{-H(\pi')+H(\pi)}\right)
		- b\left(1 \wedge e^{-H(C(\pi))+H(\pi)}\right)
		, & \pi'=\pi; \\
	%
		0, & \textrm{ otherwise}.
	\end{cases}
\end{displaymath}

Row normalization for closed $\pi$: $c(1 \wedge \edh)$ is between 0 and $c$ so
$\sum\textrm{rest}$ is between 0 and $cN$.  Take
\begin{align}
	c &= 1/N.
\end{align}
Row normalization for open $\pi$:
\begin{align}
	12a + b \le 1.
\end{align}

%% ----------------------------------------------------------------
\subsection{Correctness}

\begin{prop}[Irreducibility]
\label{prop:worm_irreducible}
The worm algorithm's Markov chain is irreducible.
\begin{proof}
As for the GK algorithm, this non-trivial result needs to be proved.
\end{proof}
\end{prop}

We mention some partial results.

\begin{prop}
The worm algorithm's Markov chain is irreducible if the GK algorithm's Markov
chain is irreducible.
\begin{proof}
The key point is that the composition of an open, head swap, and close are
precisely a GK swap.  Let $\vecx$ and $\vecy$ be lattice points such that
$\pix$ and $\piy$ are nearest neighbors.  Starting with $\pi$, then applying an
open at $\vecx$, a head swap at $\vecy$, and a close, we have
$$
	\begin{array}{lccccc}
	\pi:                     & \vecx &\mapsto& \pix, \\
	\pi'   = O(\pi,  \vecx): & \vecx &\mapsto& w, \\
	\pi''  = S(\pi', \vecy): & \vecx &\mapsto& \piy, \\
	\pi''' = C(\pi''):       & \vecx &\mapsto& \piy, \\
	\end{array}
\qquad
	\begin{array}{lccccc}
	\vecy &\mapsto& \piy, \\
	\vecy &\mapsto& \piy, \\
	\vecy &\mapsto& w, \\
	\vecy &\mapsto& \pix, \\
	\end{array}
\qquad
	\begin{array}{lccccc}
	w &\mapsto& w;    \\
	w &\mapsto& \pix; \\
	w &\mapsto& \pix; \\
	w &\mapsto& w.
	\end{array}
$$

This shows that, if the GK algorithm is irreducible on $\SN$, the worm
algorithm is irreducible on $\SN$.  But then the worm algorithm is also
irreducible on $\SNp$:  fix an initial and final permutation; close the initial
permutation, if it is open, to obtain a closed permutation; use the preceding
argument to reach the closed permutation which lies under the fiber of the
desired final open permutation; do an open move (see lemma
\ref{lem:worm_opens_and_closes}) if the final permutation is open.
\end{proof}
\end{prop}

\begin{rem}
The worm algorithm has an addtional degree of freedom.  If $\vecx$ and $\vecy$
are nearest-neighbor lattice sites, then the composition of an open at $\vecx$,
a tail swap at $\vecy$, and a close results in a similar swap of the jump
targets of $\vecx$ and $\vecy$:
$$
	\begin{array}{lccccc}
	\pi:                     & \vecx &\mapsto& \pix, \\
	\pi'   = O(\pi,  \vecx): & \vecx &\mapsto& w, \\
	\pi''  = T(\pi', \vecy): & \vecx &\mapsto& w, \\
	\pi''' = C(\pi''):       & \vecx &\mapsto& \piy, \\
	\end{array}
\qquad
	\begin{array}{lccccc}
	\vecy &\mapsto& \piy, \\
	\vecy &\mapsto& \piy, \\
	\vecy &\mapsto& \pix \\
	\vecy &\mapsto& \pix, \\
	\end{array}
\qquad
	\begin{array}{lccccc}
	w &\mapsto& w;    \\
	w &\mapsto& \pix; \\
	w &\mapsto& \piy; \\
	w &\mapsto& w.
	\end{array}
$$
\end{rem}

\begin{prop}[Aperiodicity]
The worm algorithm's Markov chain is aperiodic.
\begin{proof}
\label{prop:worm_aperiodic}
This is essentially the same as in the GK algorithm (proposition
\ref{prop:GK_aperiodic}):  given the small positive $\gamma$ in equation
\ref{eqn:ERCM_H}, an opener move from the identity entails an increase in
energy, and thus a reject of such an opener move occurs with a non-zero
probability.

(This argument applies in the non-interacting case.  For $N_2$ and $N_\ell$, it
also applies.  For $V_{ij}$, we need to check that an opener move from the
identity doesn't decrease energy.)
\end{proof}
\end{prop}

\begin{prop}[Detailed balance]
\label{prop:worm_DB}
The Markov chain of the worm algorithm satisfies detailed balance
with $b=c$.
\begin{proof}
We need
\begin{align*}
\label{eqn:worm_DB}
	P'(\pi) M(\pi, \pi') &= P'(\pi') M(\pi', \pi).
\end{align*}

For closed $\pi$ to closed $\pi'$: If $\pi=\pi'$ then we have detailed balance
trivially.  If $\pi\ne\pi'$ then $M(\pi,\pi')=M(\pi',\pi)=0$ since there are no
transitions between distinct closed permutations.

For closed $\pi$ to open $\pi'$: If $\pi'$ is not in the fiber above $\pi$,
then $M(\pi,\pi')=M(\pi',\pi)=0$ since opens and closes respect fibers (lemma
\ref{lem:worm_opens_and_closes}).  Now suppose $\pi'$ is in the fiber above
$\pi$.  As in the GK algorithm (proposition \ref{prop:GK_DB}), do cases on
$\Delta H$ positive or negative.  If $H'(\pi') \le H'(\pi)$, then
\begin{align*}
	e^{-H'(\pi)} c &= e^{-H'(\pi')} b e^{-H'(\pi)} e^{H'(\pi')}.
\end{align*}
Choose
\begin{align}
	b&=c
\end{align}
to satisfy detailed balance.
The case $H'(\pi') > H'(\pi)$ results in the same $b=c$ condition.

For open $\pi$ to closed $\pi'$: If $\pi$ is not in the fiber above $\pi'$,
then $M(\pi,\pi')=M(\pi',\pi)=0$ (lemma \ref{lem:worm_opens_and_closes}).  If
$\pi$ is in the fiber above $\pi'$, then we recover the $b=c$ condition.

It now remains to consider open $\pi$ transitioning to open $\pi'$.
We assume this to be the case for the rest of the proof.

If $M(\pi,\pi') = 0$ then we claim $M(\pi',\pi)=0$, as in lemma
\ref{lem:nzdb1}.
We have $\pi' \ne \pi$, $\pi' \notin R_S(\pi)$, and $\pi' \notin R_T(\pi)$.
We need to show $\pi \ne \pi'$ (which is obvious), $\pi \notin R_S(\pi')$, and
$\pi \notin R_T(\pi')$.
We prove the contrapositive:
$$
	\pi  \in \{\pi'\} \cup R_S(\pi') \cup R_T(\pi')
	\quad \implies \quad
	\pi' \in \{\pi\} \cup R_S(\pi) \cup R_T(\pi).
$$
If $\pi=\pi'$ then detailed balance is trivially satisfied.
Suppose $\pi\in R_S(\pi')$.
Then for some $\vecx_i$, $i=1,\ldots, 6$,
$\pi'$ and $\pi$ have
$$
	\begin{array}{lccccc}
	\pi':  & \vecx_i &\mapsto& \pi'(\vecx_i), \\
	\pi:   & \vecx_i &\mapsto& w,             \\
	\end{array}
\qquad
	\begin{array}{lccccc}
	\piiw &\mapsto& w &\mapsto& w, \\
	\piiw &\mapsto& w &\mapsto& \pi'(\vecx_i). \\
	\end{array}
$$
The lattice sites $\vecx_i$ and $w$ are nearest neighbors and $\pi',\pi$ agree
at all other sites, so there is a head swap sending $\pi$ to $\pi'$.
The case $\pi\in\R_T(\pi')$ is completely analogous.  This completes the
proof of the claim that $M(\pi,\pi') = 0 \implies M(\pi',\pi)=0$.

If $M(\pi,\pi') \ne 0$ then we claim $M(\pi',\pi) \ne 0$, again as in lemma
\ref{lem:nzdb1}.  The logic is the same as in the contrapositive argument which
was just completed.

The last step is to show detailed balance for open $\pi,\pi'$ where
$M(\pi,\pi') \ne 0$.  Again we do cases on whether the energy decreases
or increases.  If $H'(\pi') \le H'(\pi)$, then equation \ref{eqn:worm_DB}
is
\begin{align*}
 	a e^{-H'(\pi)} \left(1\right)
	&=
	a e^{-H'(\pi')} \left(e^{-H'(\pi)} e^{H'(\pi')}\right).
\end{align*}
If $H'(\pi') > H'(\pi)$, then we have
\begin{align*}
	a e^{-H'(\pi)} \left(e^{-H'(\pi')} e^{H'(\pi)}\right)
	&=
 	a e^{-H'(\pi')} \left(1\right).
\end{align*}
In either case, detailed balance holds.
\end{proof}
\end{prop}

\begin{rem*}
Note that for closed $\pi$, there are $N$ choices of open $\pi'$; for open
$\pi$, there is one choice of closed $\pi'$.  In the software implementation,
the $1/N$ for opens comes in through uniform-random choice of $\vecx\in\mcL$.
The result is that, for closed $\pi$, one may only attempt an open.  For open
$\pi$, one attempts a close $1/N$ of the time, and head or tail swaps each half
the rest of the time, respectively.
\end{rem*}

As a sanity check, we point out that cycles may grow or shrink upon worm moves.

\begin{prop}
\label{prop:worm_join_or_split}
Non-trivial worm head swaps and tail swaps either split one cycle into two,
or join two cycles into one.
\begin{proof}
This is the same as for the GK case (proposition
\ref{prop:worm_join_or_split}), which is strictly an algebraic result: the
non-spatiality of the $w$ point plays no role.
\end{proof}
\end{prop}

%% ================================================================
\newpage
\section{$\Delta H$ computations}

When computing $\Delta H$ for the GK or worm algorithms, it is inefficient to
find $H(\pi')$ and $H(\pi)$ separately, then compute their difference: GK and
worm moves are local, and most of the energy terms are unchanged from $\pi$ to
$\pi'$.  Instead (this is true for Metropolis simulations in general), one
discovers a formula for the energy change in a proposed Metropolis move.  Even
though these minimal energy-change formulas are a software-optimization detail,
they need to be considered carefully lest errors intrude.

We write the energy of equation \ref{eqn:ERCM_H} as
\begin{equation}
\label{eqn:HDVW}
	H = D + V + W
\end{equation}
where $H$ is total energy, $D$ is the distance-related single-jump terms, $V$
is the jump-pair-interaction terms, and $W$ is the worm-dependent terms.  (Note
that $V$ is identically zero if there are no interactions, and $W$ is
identically zero for the GK algorithm.)

%% ----------------------------------------------------------------
\subsection{GK and worm with no interactions}
\label{sec:Delta_D}

Recall that the wormhole point is non-spatial and thus does not participate in
distance computations.  As is clear from figures \ref{fig:gkswap} and
\ref{fig:wormmoves} (on pages \pageref{fig:gkswap} and \pageref{fig:wormmoves},
respectively), the change in distance-related terms is
\begin{align*}
	\Delta D
	&= \|\vecx - \piy\|^2
	+  \|\vecy - \pix\|^2
	-  \|\vecx - \pix\|^2
	-  \|\vecy - \piy\|^2
	& &\quad \textrm{(GK)} \\
%
	\Delta D
	&=-\|\vecx - \pix\|^2
	& &\quad \textrm{(worm open)} \\
%
	\Delta D
	&= \|\piiw - \piw\|^2
	& &\quad \textrm{(worm close)} \\
%
	\Delta D
	&= \|\piiw - \pix\|^2
	-  \|\vecx - \pix\|^2
	& &\quad \textrm{(worm head swap)} \\
%
	\Delta D
	&= \|\vecx - \piw\|^2
	-  \|\vecx - \pix\|^2
	& &\quad \textrm{(worm tail swap)}.
\end{align*}

%% ----------------------------------------------------------------
\subsection{GK and worm with $N_2$ interactions}

The non-spatiality of the wormhole point plays no role in the algebraic notion
of cycle lengths.  Thus, the same $\Delta N_2$ formulas apply to both
algorithms.  The $\Delta D$ is the same as in section \ref{sec:Delta_D}; he we
describe only the $\Delta V$.

Recall the definition of GK swap from section \ref{sec:GK_algorithm}.  The
simplicity of figure \ref{fig:gkswapx} masks a bit of detail: namely, the four
points may not all be distinct.  Thus, there are several cases.  (See figure
\ref{fig:n2cases}.)

\begin{figure}[!htb]
\begin{center}
\psfragscanon
\includegraphics[scale=0.7]{figures/gkswapx.eps}
\caption{GK swap.
	\label{fig:gkswapx}}
\end{center}
\end{figure}

\begin{figure}[!htb]
\begin{center}
\psfragscanon
\includegraphics[scale=0.7]{figures/n2cases.eps}
\caption{Cases for $\Delta N_2$.
	\label{fig:n2cases}}
\end{center}
\end{figure}

\begin{itemize}
\item Case 0: $\pix=\piy$ (and so also $\vecx=\vecy$):  this is a trivial
GK move; $\pi'=\pi$.  $\Delta N_2 = 0$.

\item Case 1: $\vecx=\pix$.
	\begin{itemize}
	\item Case 1a:  $\vecy = \piy$.
		$\Delta N_2 = +1$.
	\item Case 1b:  $\vecy\ne\piy$ but $\vecy=\pi^2(\vecy)$.
		$\Delta N_2 = -1$.
	\item Case 1c:  $\vecy \ne \piy, \pi^2(\vecy)$.
		$\Delta N_2 =  0$.
	\end{itemize}

\item Case 2: $\vecy=\piy$.
	\begin{itemize}
	\item Case 2a:  $\vecx = \pix$.  Same as case 1a.
		$\Delta N_2 = +1$.
	\item Case 2b:  $\vecx\ne\pix$ but $\vecx=\pi^2(\vecx)$.
		$\Delta N_2 = -1$.
	\item Case 2c:  $\vecx \ne \pix, \pi^2(\vecx)$.
		$\Delta N_2 =  0$.
	\end{itemize}

\item Case 3: $\vecx=\piy$.
	\begin{itemize}
	\item Case 3a:  $\pix = \vecy$.
		$\Delta N_2 = -1$.
	\item Case 3b:  $\pi^2(\vecx) = \vecy$.
		$\Delta N_2 = +1$.
	\item Case 3c:  $\vecy \ne \pix, \pi^2(\vecx)$.
		$\Delta N_2 =  0$.
	\end{itemize}

\item Case 4: $\pix=\vecy$.
	\begin{itemize}
	\item Case 4a:  $\piy = \vecx$.  Same as case 3a.
		$\Delta N_2 = -1$.
	\item Case 4b:  $\pi^2(\vecy)=\vecx$.
		$\Delta N_2 = +1$.
	\item Case 4c:  $\vecx \ne \piy, \pi^2(\vecy)$.
		$\Delta N_2 =  0$.
	\end{itemize}

\item Case 5: $\pi^2(\vecx)=\vecx$.
	\begin{itemize}
	\item Case 5a:  $\pi^2(\vecy) = \vecy$.
		$\Delta N_2 = -2$.
	\item Case 5b:  $\pi^2(\vecy)\ne\vecy$.
		$\Delta N_2 = -1$.
	\end{itemize}

\item Case 6: $\pi^2(\vecy)=\vecy$.
	\begin{itemize}
	\item Case 6a:  $\pi^2(\vecx) = \vecx$.  Same as 5a.
		$\Delta N_2 = -2$.
	\item Case 6b:  $\pi^2(\vecx)\ne\vecx$.
		$\Delta N_2 = -1$.
	\end{itemize}

\item Case 7: $\pi^2(\vecx)=\vecy$.
	\begin{itemize}
	\item Case 7a:  $\pi^2(\vecy) = \vecx$.
		$\Delta N_2 = +2$.
	\item Case 7b:  $\pi^2(\vecy)\ne\vecx$.
		$\Delta N_2 = +1$.
	\end{itemize}

\item Case 8: $\pi^2(\vecy)=\vecx$.
	\begin{itemize}
	\item Case 8a:  $\pi^2(\vecx) = \vecy$.
		$\Delta N_2 = +2$.
	\item Case 8b:  $\pi^2(\vecx)\ne\vecy$.
		$\Delta N_2 = +1$.
	\end{itemize}

\item All other cases: $\Delta N_2 = 0$.

\end{itemize}


%% ----------------------------------------------------------------
\subsection{GK and worm with $N_\ell$ interactions}

The non-spatiality of the wormhole point plays no role in the algebraic notion
of cycle lengths.  Thus, the same $\Delta N_2$ formulas apply to both
algorithms.

Recall proposition \ref{prop:GK_join_or_split}:  if $\vecx$ and $\vecy$ are in
separate cycles before the swap, they are in the same cycle afterward, and vice
versa.  Throughout this section, please consult figure \ref{fig:nellcases} for
illumination.

\begin{figure}[!htb]
\begin{center}
\psfragscanon
\includegraphics[scale=0.7]{figures/nellcases.eps}
\caption{Cases for $\Delta N_\ell$.  Sites and arrows not participating
	in changes are shown in grey.
	\label{fig:nellcases}}
\end{center}
\end{figure}

\begin{itemize}
\item Case 0: $\pix=\piy$ (and so also $\vecx=\vecy$):  this is a trivial
GK move; $\pi'=\pi$.  $\Delta N_2 = 0$.

\item Case 1:  $\vecx$ and $\vecy$ are in different cycles, but one of them is
in a one-cycle.

	\begin{itemize}
	\item Case 1a: $\vecx = \pix$:
		$\Delta N_1 = -1$,
		$\Delta N_{\ell_\pi(\vecy)} = -1$,
		$\Delta N_{\ell_\pi(\vecy)+1} = +1$.

	\item Case 1b: $\vecy = \piy$:
		$\Delta N_1 = -1$,
		$\Delta N_{\ell_\pi(\vecx)} = -1$,
		$\Delta N_{\ell_\pi(\vecx)+1} = +1$.
	\end{itemize}

\item Case 2: $\vecx$ and $\vecy$ are in the same cycle, but one is the
jump target of the other.
	\begin{itemize}
	\item Case 2a:  $\vecy = \pix$.
		$\Delta N_{\ell_\pi(\vecx)} = -1$,
		$\Delta N_{\ell_\pi(\vecx)-1} = +1$,
		$\Delta N_1 = +1$.

	\item Case 2a:  $\vecx = \piy$.
		$\Delta N_{\ell_\pi(\vecy)} = -1$,
		$\Delta N_{\ell_\pi(\vecy)-1} = +1$,
		$\Delta N_1 = +1$.
	\end{itemize}

\item Case 3: $\vecx$ and $\vecy$ are in the same cycle, and neither is
the jump target of the other.
Let $a$ be the smallest positive integer such that $\pi^a(\vecx)=\vecy$;
let $b$ be the smallest positive integer such that $\pi^b(\vecx)=\vecx$.
		$\Delta N_{a+b} = -1$,
		$\Delta N_a = +1$,
		$\Delta N_b = +1$.

\item Case 4: $\vecx$ and $\vecy$ are in separate cycles.
	$\Delta N_{\ell_\pi(\vecx)} = -1$,
	$\Delta N_{\ell_\pi(\vecy)} = -1$,
	$\Delta N_{\ell_\pi(\vecx)+\ell_\pi(\vecy)} = +1$.
\end{itemize}

%% ----------------------------------------------------------------
\subsection{GK with $V$ interactions}

Recall from proposition \ref{prop:marginality} that as long as the extended
energy function $H'$ agrees with the energy function $H$ on closed cycles, $P'$
has the correct marginal distribution on closed cycles.  Thus, when writing
energy terms for open cycles, we can choose how to define the energy.  For
$N_2$ and $N_\ell$ (the previous two sections), it is simplest to say that the
non-spatial point $w$ can partcipate in permutation cycles.  For other
interactions that depend on the spatiality of points, it is simplest to say
that $w$ does not participate.  Thus, here we split out GK and worm cases.

The change in energy is simply the contributions from the old arrows
$\vecx\mapsto\pix$ and $\vecy\mapsto\piy$ to all other arrows, along with their
mutual interaction, subtracted from the contributions from the new arrows
$\vecx\mapsto\piy$ and $\vecy\mapsto\pix$ to all other arrows, along with their
mutual interaction.

\begin{align*}
	& \sum_{\vecv \ne \vecx, \vecy} V(\vecx, \piy, \vecv, \piv)
	+ \sum_{\vecv \ne \vecx, \vecy} V(\vecy, \pix, \vecv, \piv)
	+ V(\vecx,\piy, \vecy, \pix) \\
	-&\sum_{\vecv \ne \vecx, \vecy} V(\vecx, \pix, \vecv, \piv)
	- \sum_{\vecv \ne \vecx, \vecy} V(\vecy, \piy, \vecv, \piv)
	- V(\vecx,\pix, \vecy, \piy).
\end{align*}

%% ----------------------------------------------------------------
\subsection{Worm with $V$ interactions}

The non-spatial point has no interactions, so we simply track the creation and
destruction of spatial-to-spatial arrows for the four types of worm move.  (See
figure \ref{fig:wormdeltav}.)

Open:
\begin{align*}
	-\sum_{\vecv \ne \vecx, w} V(\vecx, \pix, \vecv, \piv).
\end{align*}

Close: 
\begin{align*}
	\sum_{\vecv \ne \piiw, w} V(\piiw, \piw, \vecv, \piv).
\end{align*}

Head swap:
\begin{align*}
	&\sum_{\vecv \ne \vecx, \piiw} V(\piiw, \pix, \vecv, \piv)
	- \sum_{\vecv \ne \vecx, \piiw} V(\vecx, \pix, \vecv, \piv).
\end{align*}

Tail swap:
\begin{align*}
	&\sum_{\vecv \ne \vecx, w, \piiw} V(\vecx, \piw, \vecv, \piv)
	- \sum_{\vecv \ne \vecx, w, \piiw} V(\vecx, \pix, \vecv, \piv).
\end{align*}

\begin{figure}[!htb]
\begin{center}
\psfragscanon
\includegraphics[scale=0.7]{figures/wormdeltav.eps}
\caption{Cases for worm $\Delta V$.  Non-spatial arrows (i.e. those
	starting or ending at $w$) are shown in grey.
	\label{fig:wormdeltav}}
\end{center}
\end{figure}

\afterpage{\clearpage} % flush figure queue

%% ================================================================
\newpage
\section{GK/GKU performance results}

Memory requirements (malloc is approximately $124N$ bytes):
$$
\begin{tabular}{|r|r|r|c|}
\hline   L &    VSZ &    RSS & malloc \\
\hline
\hline   8 &    7.7 &    2.6 &  0.065 \\
\hline  10 &    7.7 &    2.8 &  0.126 \\
\hline  12 &    8.2 &    3.1 &  0.217 \\
\hline  18 &   10.5 &    4.9 &  0.727 \\
\hline  20 &   11.6 &    5.8 &  0.997 \\
\hline  40 &   38.5 &   26.2 &      8 \\
\hline  50 &   67.9 &   48.8 &   15.5 \\
\hline  80 &  254.2 &  191.6 &     63 \\
\hline 100 &  488.3 &  371.5 &    124 \\
\hline 200 & 3851.7 & 2950.4 &    992 \\
\hline
\end{tabular}
$$

$$
\begin{tabular}{|l|l|l|l|l|l|}
\multicolumn{6}{c}{GK accumulation time in seconds, no interactions} \\
\hline $T$ & $L=10$   & $L=20$   & $L=30$   & $L=50$    & $L=100$    \\
\hline
\hline 5.0 & 0.320 & 2.525 & 8.586 & 41.240 & 486.680 \\
\hline 5.5 & 0.317 & 2.513 & 8.513 & 40.937 & 446.978 \\
\hline 6.0 & 0.318 & 2.517 & 8.427 & 41.055 & 420.881 \\
\hline 6.5 & 0.317 & 2.484 & 8.320 & 40.115 & 392.840 \\
\hline
\end{tabular}
$$

$$
\begin{tabular}{|l|l|l|l|l|l|}
\multicolumn{6}{c}{GK accumulation time in seconds, $N_2$ interactions} \\
\hline $T$ & $L=10$   & $L=20$   & $L=30$   & $L=50$    & $L=100$    \\
\hline
\hline 5.0 & 0.334 & 2.639 & 8.954 & 43.087 & 503.401 \\
\hline 5.5 & 0.334 & 2.660 & 8.916 & 43.383 & 465.999 \\
\hline 6.0 & 0.336 & 2.628 & 8.885 & 42.754 & 440.559 \\
\hline 6.5 & 0.331 & 2.589 & 8.781 & 42.806 & 408.681 \\
\hline
\end{tabular}
$$

$$
\begin{tabular}{|r|r|r|r|r|}
\multicolumn{5}{c}{GK accumulation time in seconds, $N_\ell$ interactions} \\
\hline $T$ & $L=10$   & $L=20$   & $L=30$   & $L=50$ \\
\hline
\hline 5.0 & 0.641 & 56.745 & 641.560 & 16207.252 \\
\hline 5.5 & 0.558 & 40.981 & 456.305 & 11412.245 \\
\hline 6.0 & 0.459 & 25.271 & 269.707 &  6371.145 \\
\hline 6.5 & 0.382 &  9.184 &  80.708 &  1831.150 \\
\hline
\end{tabular}
$$

%$$
%\begin{tabular}{|r|r|r|r|r|c|c|}
%\multicolumn{7}{c}{GKU total time in seconds, no interactions} \\
%\hline $T$ & $L=10$   & $L=20$   & $L=30$   & $L=50$    & $L=100$  & $L=200$  \\
%\hline
%\hline 5.0 & 0.373 & 22.269 & 225.635 & 10292.521 &     TBD &      TBD \\
%\hline 5.5 & 0.277 & 13.800 & 169.140 &  4004.406 &     TBD &      TBD \\
%\hline 6.0 & 0.263 &  8.241 &  94.213 &  2359.213 &     TBD &      TBD \\
%\hline 6.5 & 0.283 &  4.053 &  23.848 &   688.895 &     TBD &      TBD \\
%\hline 7.0 & 0.206 &  1.621 &   5.320 &    30.887 & 321.056 & 2758.540 \\
%\hline
%\end{tabular}
%$$

%$$
%\begin{tabular}{|r|r|r|r|r|c|c|}
%\multicolumn{7}{c}{GKU total time in seconds, $N_2$ interactions} \\
%\hline $T$ & $L=10$   & $L=20$   & $L=30$   & $L=50$    & $L=100$  & $L=200$  \\
%\hline
%\hline 5.0 & 0.336 & 22.346 & 257.142 & 6833.803 &     TBD &      TBD \\
%\hline 5.5 & 0.309 & 15.702 & 169.145 & 4126.055 &     TBD &      TBD \\
%\hline 6.0 & 0.300 &  8.204 & 100.776 & 3624.519 &     TBD &      TBD \\
%\hline 6.5 & 0.255 &  3.852 &  36.233 &  932.387 &     TBD &      TBD \\
%\hline 7.0 & 0.210 &  1.619 &   5.516 &   32.776 & 335.990 & 2920.219 \\
%\hline
%\end{tabular}
%$$

%$$
%\begin{tabular}{|r|r|r|r|r|c|c|}
%\multicolumn{7}{c}{GKU total time in seconds, $N_\ell$ interactions} \\
%\hline $T$ & $L=10$   & $L=20$   & $L=30$   & $L=50$    & $L=100$  & $L=200$  \\
%\hline
%\hline 5.0 & 0.851 & 103.872 & 1294.662 & 37120.316 &     TBD &      TBD \\
%\hline 5.5 & 0.704 &  76.934 &  916.128 & 21960.325 &     TBD &      TBD \\
%\hline 6.0 & 0.501 &  48.705 &  568.436 & 14515.626 &     TBD &      TBD \\
%\hline 6.5 & 0.372 &  17.895 &  191.350 &  5629.602 &     TBD &      TBD \\
%\hline 7.0 & 0.222 &   2.054 &    6.294 &    34.016 & 349.495 & 3871.029 \\
%\hline
%\end{tabular}
%$$

$$
\begin{tabular}{|r|r|r|r|r|r|r|}
\multicolumn{7}{c}{GKU time in seconds, no interactions} \\
%
\hline
\multicolumn{1}{|c|}{$L$} &
\multicolumn{2}{|c|}{$T=5.0$} &
\multicolumn{2}{|c|}{$T=5.5$} &
\multicolumn{2}{|c|}{$T=6.0$} \\
\hline  {} &   therm & acc & therm & acc & therm & acc \\
\hline
\hline  10 &    0.179 &    0.479 &    0.258 &    0.487 &   0.201 &   0.455 \\
\hline  20 &    1.610 &    3.600 &    1.869 &    3.767 &   1.856 &   3.522 \\
\hline  30 &    5.405 &   12.316 &    6.655 &   12.752 &   8.208 &  11.922 \\
\hline  50 &   25.597 &   71.118 &   24.751 &   70.197 &  41.586 &  64.513 \\
\hline 100 &  207.038 &  638.257 &  287.199 &  620.600 & 379.355 & 558.839 \\
\hline 200 & 2242.074 & 5547.044 & 2197.781 & 5251.805 &     TBD &     TBD \\
\hline
\end{tabular}
$$

$$
\begin{tabular}{|r|r|r|r|r|r|r|}
\multicolumn{7}{c}{GKU time in milliseconds per site, no interactions} \\
%
\hline
\multicolumn{1}{|c|}{$L$} &
\multicolumn{2}{|c|}{$T=5.0$} &
\multicolumn{2}{|c|}{$T=5.5$} &
\multicolumn{2}{|c|}{$T=6.0$} \\
\hline  10 & 0.179000 & 0.479000 & 0.258000 & 0.487000 & 0.201000 & 0.455000 \\
\hline  20 & 0.201250 & 0.450000 & 0.233625 & 0.470875 & 0.232000 & 0.440250 \\
\hline  30 & 0.200185 & 0.456148 & 0.246481 & 0.472296 & 0.304000 & 0.441556 \\
\hline  50 & 0.204776 & 0.568944 & 0.198008 & 0.561576 & 0.332688 & 0.516104 \\
\hline 100 & 0.207038 & 0.638257 & 0.287199 & 0.620600 & 0.379355 & 0.558839 \\
\hline 200 & 0.280259 & 0.693381 & 0.274723 & 0.656476 & TBD & TBD \\
\hline
\end{tabular}
$$




%GKU accumulation time:
%
%$$
%\begin{tabular}{|l|l|l|l|}
%\multicolumn{4}{c}{GK thermalization time in seconds} \\
%\hline      &       $T=5$ &    $T=6$ &    $T=7$ \\
%\hline
%\hline  $L=8$ &  0.106352 & 0.123576 & 0.097257 \\
%\hline $L=12$ &  0.590708 & 0.499113 & 0.305788 \\
%\hline $L=16$ &  3.358411 & 2.301616 & 0.911112 \\
%\hline $L=20$ & 14.237094 & 6.200524 & 1.573818 \\
%\hline
%\end{tabular}
%\qquad
%\begin{tabular}{|l|l|l|l|}
%\multicolumn{4}{c}{GK accumulation time in seconds} \\
%\hline      &       $T=5$ &    $T=6$ &    $T=7$ \\
%\hline
%\hline  $L=8$ &  0.270330 &  0.247423 & 0.228606 \\
%\hline $L=12$ &  1.451112 &  0.922882 & 0.767582 \\
%\hline $L=16$ &  6.615593 &  3.602658 & 2.130185 \\
%\hline $L=20$ & 30.129489 & 11.849287 & 4.006170 \\
%\hline
%\end{tabular}
%$$
%
%$$
%\begin{tabular}{|l|l|l|l|}
%\multicolumn{4}{c}{GK total time} \\
%\hline        &    $T=5$ &    $T=6$ &    $T=7$ \\
%\hline  $L=8$ & 0.195896 & 0.243862 & 0.191281 \\
%\hline $L=10$ & 0.493505 & 0.463685 & 0.400464 \\
%\hline $L=12$ & 1.096127 & 0.816234 & 0.651675 \\
%\hline
%\end{tabular}
%\qquad
%\begin{tabular}{|l|l|l|l|}
%\multicolumn{4}{c}{Worm total time} \\
%\hline        &      $T=5$ &      $T=6$ &     $T=7$ \\
%\hline  $L=8$ &  14.982819 &  16.846777 &  6.301137 \\
%\hline $L=10$ &  59.401972 &  56.671825 & 16.392375 \\
%\hline $L=12$ & 172.733188 & 177.591496 & 30.807275 \\
%\hline
%\end{tabular}
%$$

%% ================================================================
\newpage
\section{Worm performance results}

$$
\begin{tabular}{|l|l|l|l|}
\multicolumn{4}{c}{Average wormspan over the first 100,000 steps} \\
\hline  $L=8$ & $T=6$ & $\gamma=0.00$ & $3.75$ \\
\hline  $L=8$ & $T=6$ & $\gamma=0.05$ & $3.76$ \\
\hline  $L=8$ & $T=7$ & $\gamma=0.00$ & $2.97$ \\
\hline  $L=8$ & $T=7$ & $\gamma=0.05$ & $2.70$ \\
\hline $L=12$ & $T=6$ & $\gamma=0.00$ & $5.42$ \\
\hline $L=12$ & $T=6$ & $\gamma=0.05$ & $5.67$ \\
\hline $L=12$ & $T=7$ & $\gamma=0.00$ & $3.17$ \\
\hline $L=12$ & $T=7$ & $\gamma=0.05$ & $2.83$ \\
\hline
\end{tabular}
$$

Key:

$$
\begin{tabular}{|l|l||l|l|}
\hline OR & open  reject   & OA & open  accept \\
\hline CR & close reject   & CA & close accept \\
\hline HR & HS    reject   & HA & HS    accept \\
\hline TR & TS    reject   & TA & TS    accept \\
\hline
\end{tabular}
$$

$$
\begin{tabular}{|l|cr|cr|cr|}
\hline &\multicolumn{2}{|c|}{$L=8,T=5$} &\multicolumn{2}{|c|}{$L=8,T=6$} &\multicolumn{2}{|c|}{$L=8,T=7$} \\
\hline OR&       18 /     1000 &  1.8\% &       24 /     1000 &  2.4\% &      44 /    1000 &  4.4\% \\
       OA&      982 /     1000 & 98.2\% &      976 /     1000 & 97.6\% &     956 /    1000 & 95.6\% \\
\hline CR&   100411 /   101393 & 99.0\% &    96081 /    97057 & 98.9\% &   32077 /   33033 & 97.1\% \\
       CA&      982 /   101393 &  0.9\% &      976 /    97057 &  1.0\% &     956 /   33033 &  2.8\% \\
\hline HR& 15961944 / 25972671 & 61.4\% & 16565332 / 24763340 & 66.8\% & 6055477 / 8442255 & 71.7\% \\
       HA& 10010727 / 25972671 & 38.5\% &  8198008 / 24763340 & 33.1\% & 2386778 / 8442255 & 28.2\% \\
\hline TR& 15962807 / 25974523 & 61.4\% & 16566337 / 24763404 & 66.8\% & 6049339 / 8435273 & 71.7\% \\
       TA& 10011716 / 25974523 & 38.5\% &  8197067 / 24763404 & 33.1\% & 2385934 / 8435273 & 28.2\% \\
\hline
\end{tabular}
$$

$$
\begin{tabular}{|l|cr|cr|cr|}
\hline &\multicolumn{2}{|c|}{$L=10,T=5$} &\multicolumn{2}{|c|}{$L=10,T=6$} &\multicolumn{2}{|c|}{$L=10,T=7$} \\
\hline OR&        20/    1000& 2.0\%&      22/    1000& 2.2\%&      25/    1000& 2.5\% \\
       OA&       980/    1000&98.0\%&     978/    1000&97.8\%&     975/    1000&97.5\% \\
\hline CR&    186845/  187825&99.4\%&  191624/  192602&99.4\%&   43817/   44792&97.8\% \\
       CA&       980/  187825& 0.5\%&     978/  192602& 0.5\%&     975/   44792& 2.1\% \\
\hline HR&  57665006/93859676&61.4\%&64260327/96069234&66.8\%&16024949/22356771&71.6\% \\
       HA&  36194670/93859676&38.5\%&31808907/96069234&33.1\%& 6331822/22356771&28.3\% \\
\hline TR&  57682628/93884224&61.4\%&64271757/96077436&66.8\%&16029810/22354590&71.7\% \\
       TA&  36201596/93884224&38.5\%&31805679/96077436&33.1\%& 6324780/22354590&28.2\% \\
\hline
\end{tabular}
$$

$$
\begin{tabular}{|l|cr|cr|cr|}
\hline &\multicolumn{2}{|c|}{$L=12,T=5$} &\multicolumn{2}{|c|}{$L=12,T=6$} &\multicolumn{2}{|c|}{$L=12,T=7$} \\
\hline OR&          9/     1000& 0.9\%&       28/     1000& 2.8\%&      35/    1000& 3.5\% \\
       OA&        991/     1000&99.1\%&      972/     1000&97.2\%&     965/    1000&96.5\% \\
\hline CR&     308031/   309022&99.6\%&   302269/   303241&99.6\%&   51515/   52480&98.1\% \\
       CA&        991/   309022& 0.3\%&      972/   303241& 0.3\%&     965/   52480& 1.8\% \\
\hline HR&  163688222/266452382&61.4\%&174797678/261341391&66.8\%&32376214/45156684&71.6\% \\
       HA&  102764160/266452382&38.5\%& 86543713/261341391&33.1\%&12780470/45156684&28.3\% \\
\hline TR&  163690252/266438041&61.4\%&174765344/261325121&66.8\%&32365239/45149085&71.6\% \\
       TA&  102747789/266438041&38.5\%& 86559777/261325121&33.1\%&12783846/45149085&28.3\% \\
\hline
\end{tabular}
$$

Histograms of wormspan (i.e. $\|\piiw - \piw\|$) for open cycles, over the first 100,000 steps,
are in figure \ref{fig:wormspanhisto}.

\begin{figure}[!htb]
\begin{center}
\psfragscanon

\includegraphics[scale=0.35]{figures/histo_L_8_T_6_gamma_0.00.eps}
\includegraphics[scale=0.35]{figures/histo_L_8_T_6_gamma_0.05.eps}
\includegraphics[scale=0.35]{figures/histo_L_8_T_6_gamma_-0.05.eps}

\includegraphics[scale=0.35]{figures/histo_L_8_T_7_gamma_0.00.eps}
\includegraphics[scale=0.35]{figures/histo_L_8_T_7_gamma_0.05.eps}
\includegraphics[scale=0.35]{figures/histo_L_8_T_7_gamma_-0.05.eps}

\includegraphics[scale=0.35]{figures/histo_L_12_T_6_gamma_0.00.eps}
\includegraphics[scale=0.35]{figures/histo_L_12_T_6_gamma_0.05.eps}
\includegraphics[scale=0.35]{figures/histo_L_12_T_6_gamma_-0.05.eps}

\includegraphics[scale=0.35]{figures/histo_L_12_T_7_gamma_0.00.eps}
\includegraphics[scale=0.35]{figures/histo_L_12_T_7_gamma_0.05.eps}
\includegraphics[scale=0.35]{figures/histo_L_12_T_7_gamma_-0.05.eps}

\caption{Histograms for wormspans.
	\label{fig:wormspanhisto}}
\end{center}
\end{figure}

\afterpage{\clearpage} % flush figure queue

%% ================================================================
\newpage
\section{Algorithm modification ideas}

The essential problem is that the configuration space has multiple energy
minima, which are equivalent to probability maxima:  see figure [xxx].  (This
picture should be replicated in the $y$ and $z$ directions as well.)

The GK algorithm creates only permutations with winding numbers equal to 0.
The cycle-reversal extension creates permutations with even winding numbers.
The cycle-reversal move has zero energy change and allows subsequent
permutations to hop across a low double-winding-number barrier.

The worm algorithm was designed to permit cycles with winding numbers of both
parities to be created:  one opens a cycle, allows it to wander around (perhaps
around the torus), and then reclose.  The problem is that the open worm tips
wander around randomly, and fail to reconnect as $L$ increases.

Other ideas:

\begin{itemize}

\item Direct the worm somehow.  At the time the worm is opened, somehow add a
distance weight of $\pm L$ in the $x$, $y$, or $z$ direction which will be
removed by a wrap around the torus, increasing or decreasing that
winding-number component by 1.

\item In analogy with cluster updates for the Ising model, perhaps form a band
around the torus and do a ring of pair swaps somehow --- not just a single GK
swap.

\item Pinch the torus geometry somehow.

\item Temporarily reduce and restore the temperature $T$.

\item Review the PIMC literature again \ldots.

\end{itemize}


%% ================================================================
\newpage
\section{To be filed}

\begin{verbatim}
------------------------------------------------------
* make a separate section 1 for RCM
  - subsection for H/P/Z/etc
  - subsection for winding cycles
  - subsection for wno prb landscape
* RV section?
* in the GK section:
  - GK subsection about wno behavior
* make a GKU section
  - credit Daniel
  - GKU subsection about wno behavior
  - mention CPU penalty w/ xref to perf section
  - new GKU logic -- once per sweep not once per step.  N vs. N^2.
* document all 5 algorithms
  - idea/figures
  - detailed balance
  - step/sweep definitions; when RVs are accumulated (with examples)
* Delta W section for non-directed worm and directed worm
  - make a figure for how dworm creates a winding cycle
* mem stats
* CPU stats for all 5 algorithms
  - GK
  - GKU
  - non-directed worm
  - directed worm
  - hybrid
* compare all RVs (esp. at larger L) for all 5 algorithms.  put up some
  plots.
* gprof RV collection time
* batched means?
\end{verbatim}

\begin{verbatim}
! corrlen x 2
  k coded
  k get some data ...
  - look at reciprocals

! compose sigma o pi:
  - for GK swap, sigma is xposn.
  - for cycrev:
    before:    (>>>>)(..)(.....)
    after:     (<<<<)(..)(.....)
    befinvaft: (....)^2 1's .... :)
  - for band update:  sigma is Wx/Wy/Wz at urand latitude.

! read PIMC worm close
! read ising/perco/mcmc re smallf/smallf

* prove: wx, wy, wz parities are separately conserved.
* check fI for various wx/wy/wz shells

* reorder RVs in mcmc_rvs.h, and all mcmc_rvs.c routines.
* rename verbosity attrs to have a _v or some such.

k Mersenne twister!

! try W = gamma * ell_w

------------------------------------------------------
More FSS refs:

* A. E. Ferdinand and M. E. Fisher, Phys. Rev. 185, 832 (1969);

* D.P. Landau, Phys. Rev. B 13, 2997 (1976)

* K. Binder, Phys. Rev. Lett. 47, 693-696 (1981)

* D.P. Landau and K. Binder, Phys. Rev. B 31, 5946-5953 (1985)

* V. Privman (ed.), Finite-Size Scaling and Numerical Simulations of
  Statistical Systems (World Scientific, Singapore, 1990)

* http://www.fysik.uu.se/cmt/berg/node18.html

* fourth-order cumulants (see my bookshelf!)

* J.M. Yeomans, Statistical Mechanics of Phase Transitions,
  Oxford University Press (1992) 

------------------------------------------------------
More worm refs:

* Alet & Sorensen 2003

* Smakov, Harada, Kawashima 2008

------------------------------------------------------
! get gamma correct for directed worm
  - include wno prints
  - wno is sensitive to gamma?  what is *right* to do?
* allowing only non-trivial wno jumps:
  - gamma too big:  all opens are rejected
  - gamma too small: indefinite worm wander
* with ZHT dsq:
  - search:

    L=20: 0.4 too big
    L=20: 0.? not too big

    L=20: 0.1 maybe OK

    L=20: 0.? not too small
    L=20: 0.0 too small

  - gamma in the middle:  ??  gather data & check L dependence.

* with sqrt method:
  - searching at L=10 ...
  - next: search at L=20 and L=40.

? if worm only, allow zero wnojump; if hybrid, do not ... ?

------------------------------------------------------
* fbb autocorr; alet autocorr?

\end{verbatim}

% ----------------------------------------------------------------
% ! ZCM section for dis.
%   * Non-unique coset reps for even L.  Need for symmetry of Vzw.
%   * Unique coset reps for odd L.  Same math.  Works fine.

% ! GK irr -- TBD.

% k Worm irr -- type up.  :)

% ! Prove 3N distinct.  Needs def'n of pi' = G(pi)?
% * type up:  ZCM/PBC arithmetic as affects symmetry of Vzw.

%% ----------------------------------------------------------------
% * beta=0,inf sanity:  f*ck it.

% For worm, describe how $\supp(\gamma)$ can change.  Also some examples.

% Stopping time for closes ...

% Get closure stats: vary N; vary T above and below T_c.

% ----------------------------------------------------------------
% NTS:
% * Include more closed-only caveats in the code.  Including fcn name changes.
% * Delta H's:
%   * #if 1 in mcrcm.c -> #ifdef CHECK_H
%   * test the C code now that piiy is gone.
%   * test Vzw in particular.
%   * are w zero distances propagated correctly?
% * Elaborate verbally on the figures for Delta Vzw.
