\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{fleqn}
%\def\#R21{\#R21}
\def\mud{\mu^{(d)}}
\def\mudk{\mu^{(d,k)}}
\def\mudkn{\mu^{(d,k)}(n)}
\def\fdn{f^{(d)}(n)}
\def\fdkn{f^{(d,k)}(n)}
\def\gdn{g^{(d)}(n)}
\def\gdkn{g^{(d,k)}(n)}
\def\Fdz{F^{(d)}(z)}
\def\Fdkz{F^{(d,k)}(z)}
\def\Fz{F^{(d,4)}(z)}
\def\Gdz{G^{(d)}(z)}
\def\Gdkz{G^{(d,k)}(z)}
\def\Giz#1{G^{(d,4)}_{#1}(z)}
\def\Adk{A^{(d,k)}}
\hsize=6in
\vsize=8.5in
\begin{document}
\pagestyle{myheadings}
\markright{\textsc{the electronic journal of combinatorics \textbf{7}
(2000), \#R21\hfill}}
\thispagestyle{empty}
\title{Improved Upper Bounds for Self-Avoiding Walks in $\mathbb{Z}^{d}$}
\author{Andr\'{e} P\"{o}nitz and Peter Tittmann\\Hochschule
Mittweida\\09648 Mittweida\\Technikumplatz 17\\Germany\\[1ex]
{\small e-mail: \texttt{peter@htwm.de}, \texttt{poenitz@htwm.de}}%
%e-mail: peter@htwm.de, poenitz@htwm.de%
\vspace{2ex}}
\date{\small Submitted: June 7, 1999; Accepted: April 13, 2000\\
AMS Classification: 82B41, 05A15\vspace{2ex}}
\maketitle
\begin{abstract}
New upper bounds for the connective constant of self-avoiding walks in a
hypercubic lattice are obtained by automatic generation of finite automata for
counting walks with finite memory. The upper bound in dimension two is 2.679192495.
\end{abstract}
\section{Introduction}
Counting self-avoiding walks in a hypercubic lattice $\mathbb{Z}^{d}$ is one of
the hardest open problems in combinatorics. Walks of length up to 51 have been
enumerated by \emph{Conway} and \emph{Guttmann} \cite{CG} with considerable
computational effort. Obviously, the number $\fdn$ of self-avoiding walks of
length $n$ in $d$ dimensions is at least $d^n$ by allowing only steps in each
positive direction. On the other hand, a lower bound of $2d(2d-1)^{n-1}$ can be
obtained by counting walks without immediate reversals. The \emph{connective
constant} $\mud = \lim_{n\to\infty}\sqrt[n]{\fdn}$ is therefore bounded by the
trivial bounds $d$ and $2d$. Tighter rigorous bounds for $\mud$ are presented in
the famous book by \emph{Madras} and \emph{Slade} \cite{MS}. The latest
improvements in the field can be found in \cite{NO} achieving upper
bounds of 2.6939 and 4.7476 in two and three dimensions, respectively, by an
application of the \emph{Goulden-Jackson} cluster method \cite{GJ}.
In this paper, we improve these bounds to 2.6792 and 4.7387, respectively,
without using the Principle of Inclusion and Exclusion employed by
\emph{Goulden} and \emph{Jackson}. The main idea is as follows. Let $k$,
$n$ be integers and $k$ even. Define $\gdkn$ to be the number of walks of
length $n$ in dimension $d$ that have at least one loop of length $k$ or
less. Given a fixed $k$, we construct a finite automaton $\Adk$ to
generate the numbers $\gdkn$.
Since a self-avoiding walk does not contain loops of any length, we can
obtain an upper bound for the number $\fdn$ of self-avoiding walks by simply
subtracting $\gdkn$ from the total number of walks of length $n$ -- i.e.
$(2d)^n$.
The ordinary generating function $\Gdkz = \sum_n \gdkn\,z^n$ can be derived by
solving a system of equations created from the automaton's state transfers. The
resulting function is always a rational function whose asymptotic behavior is
determined by the root of smallest modulus of the denominator polynomial. This
root can be obtained by iterating the automaton itself in order to avoid
processing of huge matrices.
\section{The Automaton}
We demonstrate the construction of the automata $\Adk$ in the special
case $k=4$ and unspecified $d$. The state set of the automaton is defined
as follows.
The initial state 0 corresponds to the unique walk of length zero. The
final state $\omega$ represents walks that have a complete loop of length
up to $k=4$ (i.e. 2 or 4, since there must be an even number of steps in
the loop). This state is absorbing (and the only absorbing state of the
automaton for that matter) since a walk with a loop never loses this
property. All other states represent classes of walks that exhibit a
certain pattern in their last few steps. We construct them one by one,
always trying to keep the automaton as small as possible. In order to
extend the walk of length zero by one step, we can go in each of the $2d$
possible directions. This could be handled by $2d$ different states.
However, all these different situations can be characterized the same way:
We have a walk whose history can't contribute to a loop of length up to 4.
In this case this is simply be because there is no history at all, but
later there will be other walks in state 1 as well. Therefore we create
only one new state 1 to represent all those walks \emph{of any length $n$}
whose first $n-1$ steps cannot contribute to a loop of length less or equal
to 4. Obviously, all the $2d$ ways out of state 0 lead to state 1. We
will see later that this classification preserves all necessary details for
our purpose.
Suppose, our walk is in state 1. There are three possibilities to continue:
(1.1) The next step is an immediate return, thus closing a loop of length 2
and transfering us directly to state $\omega$. (1.2) We proceed in the same
direction. Consider the previous step. In order to make this step part of
a loop we have to walk back to its start somehow. In case of an immediate
return we would close a loop of length 2 that does not use the previous
step; in any other case we are not able to finish the loop with four steps
or less. In any case, the previous step is not part of the first loop of
length 2 or 4 for any continuation of our walk, so it is not really
neccessary to preserve the information that the previous step was taken at
all -- except for its contribution of 1 for the total length of the walk of
course. But this means we are effectively transfered back to state 1 again.
(1.3) In the remaining $2d-2$ cases the walk turns into another dimension.
We represent this configuration by a new state 2.
Suppose now, we have a walk in state 2. This time there are four ways to
continue: (2.1) Immediate return transfering the walk to state $\omega$.
(2.2) A step in the same direction as the previous step, transfering us
back to state 1 for the same reasons as mentioned above under (1.2).
(2.3) A step in the opposite direction to the second last step, transfering
as to a new state 3 representing all those walks whose last three steps
form a $U$-shape. (2.4) A step in any other of the remaining $2d-3$
directions, transfering again to state 2 for similar reasons as above.
Last but not least, the possible transfers from state 3 are: (3.1)
Immediate return closing a loop of length 2 or a step to the start of the
third last step closing a loop of length 4 -- both transfering to state
$\omega$. (3.2) A step in the same direction as the previous step,
transfering us back to state 1 again. (3.3) A step in any other of the
remaining $2d-3$ directions, all transfering to state 2.
\begin{figure}
\centering
\resizebox*{0.8\textwidth}{0.38\textheight}{\includegraphics{automat.eps}}
\caption{The automaton $A^{(d,4)}$.}
\end{figure}
\begin{table}[tbp] \centering
\begin{tabular}
[c]{|ll|ll|}\hline
0\unitlength1mm \begin{picture}(4,4) \put(2,2){\circle*{1.5}} \end{picture} &
$1(2d)$ & 11\unitlength1mm \begin{picture}(14,14) \put(2,2){\circle*{1.5}}%
\put(2,2){\line(1,0){8}} \put(10,2){\line(0,1){8}} \put(10,10){\line
(1,1){3.6}} \put(13.6,13.6){\line(0,-1){8}} \end{picture} & $3,9,13(2d-5),18$\\
1\unitlength1mm \begin{picture}(10,4) \put(2,2){\circle*{1.5}} \put
(2,2){\line(1,0){8}} \end{picture} & $2,3(2d-2)$ & 12\unitlength1mm
\begin{picture}(18,10) \put(2,2){\circle*{1.5}} \put(2,2){\line(1,0){16}}%
\put(18,2){\line(0,1){8}} \put(18,10){\line(-1,0){8}} \end{picture} &
$3,13(2d-4),19$\\
2\unitlength1mm \begin{picture}(18,4) \put(2,2){\circle*{1.5}} \put
(2,2){\line(1,0){16}} \end{picture} & $2,7(2d-2)$ & 13\unitlength1mm
\begin{picture}(14,14) \put(2,2){\circle*{1.5}} \put(2,2){\line(1,0){8}}%
\put(10,2){\line(0,1){8}} \put(10,10){\line(-1,0){8}} \put(2,10){\line
(1,1){3.6}} \end{picture} & $3,4,6(2d-5),11,20$\\
3\unitlength1mm \begin{picture}(10,10) \put(2,2){\circle*{1.5}} \put
(2,2){\line(1,0){8}} \put(10,2){\line(0,1){8}} \end{picture} & $3,4,5,6(2d-4)$ & 14\unitlength1mm \begin{picture}(10,18) \put(2,2){\circle
*{1.5}} \put(2,2){\line(1,0){8}} \put(10,2){\line(0,1){16}} \put
(10,18){\line(-1,0){8}} \put(2,18){\line(0,-1){8}} \end{picture} &
$3,13(2d-4)$\\
4\unitlength1mm \begin{picture}(10,18) \put(2,2){\circle*{1.5}} \put
(2,2){\line(1,0){8}} \put(10,2){\line(0,1){16}} \end{picture} & $2,6(2d-4),7,8$ & 15\unitlength1mm \begin{picture}(18,10) \put(10,2){\circle
*{1.5}} \put(10,2){\line(1,0){8}} \put(18,2){\line(0,1){8}} \put
(18,10){\line(-1,0){16}} \put(2,10){\line(0,-1){8}} \end{picture} &
$3,4,6(2d-4)$\\
5\unitlength1mm \begin{picture}(10,10) \put(2,2){\circle*{1.5}} \put
(2,2){\line(1,0){8}} \put(10,2){\line(0,1){8}} \put(10,10){\line(-1,0){8}%
}\end{picture} & $3,9,13(2d-4)$ & 16\unitlength1mm \begin{picture}%
(14,14) \put(2,2){\circle*{1.5}} \put(2,2){\line(1,0){8}} \put(10,2){\line
(0,1){8}} \put(10,10){\line(1,1){3.6}} \put(13.6,13.6){\line(-1,0){8}}%
\put(5.6,13.6){\line(-1,-1){3.6}} \end{picture} & $3,9,13(2d-5)$\\
6\unitlength1mm \begin{picture}(14,14) \put(2,2){\circle*{1.5}} \put
(2,2){\line(1,0){8}} \put(10,2){\line(0,1){8}} \put(10,10){\line(1,1){3.6}%
}\end{picture} & $3,4,6(2d-5),10,11$ & 17\unitlength1mm \begin{picture}%
(14,14) \put(2,2){\circle*{1.5}} \put(2,2){\line(1,0){8}} \put(10,2){\line
(0,1){8}} \put(10,10){\line(1,1){3.6}} \put(13.6,13.6){\line(-1,0){8}}%
\put(5.6,13.6){\line(0,-1){8}} \end{picture} & $3,4,6(2d-5),16$\\
7\unitlength1mm \begin{picture}(18,10) \put(2,2){\circle*{1.5}} \put
(2,2){\line(1,0){16}} \put(18,2){\line(0,1){8}} \end{picture} & $3,4,6(2d-4),12$ & 18\unitlength1mm \begin{picture}(14,14) \put(2,2){\circle
*{1.5}} \put(2,2){\line(1,0){8}} \put(10,2){\line(0,1){8}} \put(10,10){\line
(1,1){3.6}} \put(13.6,13.6){\line(0,-1){8}} \put(13.6,5.6){\line(-1,0){8}%
}\end{picture} & $3,4,6(2d-5),11$\\
8\unitlength1mm \begin{picture}(10,18) \put(2,2){\circle*{1.5}} \put
(2,2){\line(1,0){8}} \put(10,2){\line(0,1){16}} \put(10,18){\line(-1,0){8}%
}\end{picture} & $3,4,6(2d-4),14$ & 19\unitlength1mm \begin{picture}%
(18,10) \put(2,2){\circle*{1.5}} \put(2,2){\line(1,0){16}} \put(18,2){\line
(0,1){8}} \put(18,10){\line(-1,0){16}} \end{picture} & $2,7(2d-3)$\\
9\unitlength1mm \begin{picture}(18,10) \put(10,2){\circle*{1.5}}%
\put(10,2){\line(1,0){8}} \put(18,2){\line(0,1){8}} \put(18,10){\line
(-1,0){16}} \end{picture} & $2,7(2d-3),15$ & 20\unitlength1mm
\begin{picture}(14,14) \put(2,2){\circle*{1.5}} \put(2,2){\line(1,0){8}}%
\put(10,2){\line(0,1){8}} \put(10,10){\line(-1,0){8}} \put(2,10){\line
(1,1){3.6}} \put(5.6,13.6){\line(0,-1){8}} \end{picture} & $3,4,6(2d-5),16$\\
10\unitlength1mm \begin{picture}(14,14) \put(2,2){\circle*{1.5}}%
\put(2,2){\line(1,0){8}} \put(10,2){\line(0,1){8}} \put(10,10){\line
(1,1){3.6}} \put(13.6,13.6){\line(-1,0){8}} \end{picture} &
$3,4,6(2d-5),16,17$ & &\\\hline
\end{tabular}
\caption{States and transfers of the automaton $A^{(d,6)}$. This
incorporates already the simplifications by symmetry mentioned in the text.
The comma-seperated numbers are the state numbers of the successor states,
a number followed by another number in parantheses indicates several
directions leading to the same successor.
Transfers to the final state $\omega$ are not shown.
\label{tab1}} \end{table}%
The automaton can be translated directly into a system of equations for the
generating function. Let $\Giz{i}$ be the
ordinary generating function for the number of walks in state $i$ and $z$ a
formal variable representing one step of a walk. Then:
\begin{eqnarray*}
\Giz{0} &=& 1\\
\Giz{1} &=& z\,\left[2d\Giz{0}+\Giz{1}+ \Giz{2}+ \Giz{3}\right] \\
\Giz{2} &=& z\,\left[ (2d-2)\Giz{1}+(2d-3)\left(\Giz{2}+\Giz{3}\right)\right] \\
\Giz{3} &=& z\,\left[ \Giz{2} \right] \\
\Giz{\omega} &=& z\,\left[2d\Giz{\omega}+\Giz{1}+ \Giz{2}+ \Giz{3}\right] \\
\end{eqnarray*}%
{}From this we obtain easily
\begin{eqnarray*}
\Fz&=&\frac{1+2z+2z^2-z^3+2z^3d}{1-2zd+2z-2z^2d+2z^2-z^3}
\end{eqnarray*}
The roots of the denominator polynomial $1-2zd+2z-2z^2d+2z^2-z^3$ can be
found explicitly yielding some rather ugly explicit algebraic expression
depending on $d$. In any case, numerical approximations of the roots for
specific values of $d$ are found easily, and so are the inverses of the
roots of smallest modulus giving us the entries of first line of table
\ref{tab3}.
The manual construction of automata for walks with memory greater than
eight is no longer feasable, since the number of states increases
exponentially. Fortunately, automating the generation of states and
transfer matrices is straightforward as the following algorithm shows:
\begin{enumerate}
\item Initalize a \emph{set of untreated states} with state 0 as the only
element, an empty \emph{set of treated states}, and an empty \emph{set of
transfers}.
\item Choose any untreated state $s$, remove it from the set. This state
represents a certain class of walks $w_i$ with individual lengths $l_i$
whose first $l_i-l$ steps cannot contribute to loop of length less or equal
to the memory $k$ and whose last $l$ steps are identical. These last $l$
steps form a walk by their own that could be considered as a representative
$r$ of the state. Because of the limited memory $k$, all of these walks will
behave exactly the same in the future, and thus it is sufficient to identify
the state with its representative and to keep track of the number of walks in
the state instead of all the walks themselves.
\item Construct all possible successors of the state by iterating through
all $2d$ possible directions. In each iteration, augment $r$ by a single step
in the corresponding direction, leading to an augmented walk $a$. If there is
any possibility to form a loop of length less or equal to $k$ starting with
$a$, then $a$ is the representative of a successor state $t$ of $s$.
If $t$ is a state we have not seen so far, put it in the set of untreated
states. In any case, keep track of the transfer from $s$ to $t$ in the set
of transfers. If there is \emph{no} possibility to form a loop of length
less or equal to $k$ starting with $a$, then we start removing steps from
the beginning of $a$ until we arrive at a walk $a'$ that could be the first
part of such a loop. Note that this procedure terminates since the length of
$a$ is finite at the beginning, shrinks by 1 in each iteration, and the empty
walk surely is extentable to a loop
within $k$ steps. Now the walk $a'$ is a representative of some state $t'$
that is handled exactly like the state $t$ in the other case.
\item Put state $s$ into the set of treated states. If the
set of untreated states is not empty, go to 2, otherwise go to 5.
\item We now have collected all necessary states in the set of treated
states and all transfers in the set of transfers, thus the automaton is built.
Note that the outer loop terminates since there is a (generous) upper bound of
$(2d)^k$ to the number of possible states and every iteration of the loop
deals with one of them.
\end{enumerate}
This base algorithm can be improved by combining sets of similar states. These
improvements are not strictly necessary for the subsequent theoretical
examinations. For practical computations, however, they are indispensable
since they reduce the size of the automata thus saving valuable memory and
increasing general performance.
One possibility is to exploit symmetry in the states. If one walk uses only
the first $j