\documentclass{article}

\begin{document}
\bibliographystyle{plain}
\title{The Number of Square-Free Self-Avoiding Walks in 2-dimensions.}

\author{Anne E. Edlin}

\maketitle

\begin{abstract}
A walk is self-avoiding if it never meets itself.  A walk can be viewed as a  
word if each step is assigned a `letter'.  A walk is square-free if its word 
contains no subwords of the form $xx$.  This paper proves that the number of 
square-free self-avoiding walks in 2-dimensions of any length is finite. 

The maple packages used to discover this result are available at this papers web 
site {\bf http://www.math.temple.edu/$\sim$anne/sqfrwalk.html}. 
\end{abstract}

\subsection*{Preface}

Throughout this paper walks are viewed as words, written in the form
\newline $[w_1,w_2,\ldots,w_n]$, where each letter, $w_i$ represents one step of 
the walk.  In 2-dimensions we can use the alphabet $\{1,-1,2,-2\}$ as our set of 
possible steps.  Here $1$ represents a step to the right, $-1$ a step to the 
left, $2$ a step up and $-2$ a step down.

We define a factor of a word in the following way.  Given a word $w=[w_1,w_2, 
\ldots ,w_n]$, a {\it factor} of $w$ is any subword of the form $[w_k,w_{k+1}, 
\ldots  ,w_{k+j}]$ where  $1 \leq k \leq n$ and 
$0 \leq j \leq n-1$.

A {\it self-avoiding walk} in 2-dimensions is a path on the 2-dimensional 
lattice that does not visit the same site twice \cite{madras}.  Using our 
notation this is equivalent to a word is self-avoiding if it contains no factors 
for which the number of $1$s and $-1$s are equal and the number of $2$s and 
$-2$s are equal.  My Maple package walk (available from {\bf 
http://www.math.temple.edu/$\sim$anne/sqfrwalk.html}) can be used to derive or 
count the number of self-avoiding walks that avoid an input set of mistakes in 
any given dimension.  


A word is {\it square-free} if it contains no factors of the form $xx$, where 
$x$ is any word. 
My Maple package Squares (available from {\bf
\newline
http://www.math.temple.edu/$\sim$anne/sqfrwalk.html}) can be used to derive
square words on any given alphabet up to the required length.  

\subsection*{The Sequence}
The number of square-free self-avoiding walks for n from 0 to 20 are:

[1, 4, 8, 16, 16, 16, 16, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].

\subsection*{A Non-Computer Proof}

By making our walks self-avoiding we know we must eliminate all immediate back 
steps and all polygons, at the very least.  This means that none of the 
following set of words may appear as a factor of any of our words:
\begin{eqnarray*}
 \{& [1, -1], [2, -2], [-1, 1], [-2, 2], [1, 2, -1, -2], [2, -1, -2, 1], [-1, 
-2, 1, 2], & \\
  &  [-2, 1, 2, -1], [-1, 2, 1, -2], [-2, -1, 2, 1], [1, -2, -1, 2], [2, 1, -2, 
-1] & \}.
\end{eqnarray*}
The fact the walks are also square free eliminates double steps and double 
`corners', that is paths like (right, up, right, up).  So we must also eliminate 
all of the following as factors:
\begin{eqnarray*}
\{& [1, 1], [-1, -1], [2, 2], [-2, -2], [-1, 1, -1, 1], [2, 1, 2, 1], [-2, 1, 
-2, 1], & \\
  & [1, -1, 1, -1], [2, -1, 2, -1], [-2, -1, -2, -1], [1, 2, 1, 2], [-1, 2, -1, 
2], & \\
  & [-2, 2, -2, 2], [1, -2, 1, -2], [-1, -2, -1, -2], [2, -2, 2, -2] &\}.
\end{eqnarray*}

So let us now try to form a square-free self-avoiding walk.  By symmetry it does 
not matter in which direction we start, so let our first step be a $1$.  

Now our second step may not be $-1$ as the walk is self-avoiding, and it can not 
be $1$, because our walk is square-free.  So our next step must be $2$ or $-2$.  
Again by symmetry it does not matter which we chose, so we will pick $2$.

Our walk so far is $[1, 2]$.  Now as before we may not pick $-2$ or $2$, because 
our previous step was $2$, so we must pick $1$ or $-1$.  Both cases are very 
similar so I will only look at the case that the next step is $1$ in this paper. 
 The case when the next step is $-1$ is left to the reader.

We now have $[1,2,1]$.  For our next step I may not pick $-1$ or $1$, because 
the last step was a $1$, and I may not pick $2$, because $[1,2,1,2]$ is a square 
(of $[1,2]$), this means I am forced to pick a $-2$.

Now we have $[1,2,1,-2]$.  From here I may not pick $-2$ or $2$ as usual, and I 
may not pick $-1$, or the last four steps will form a polygon $[2,1,-2,-1]$, and 
so will not be self-avoiding.  Thus I am forced to pick $1$.

I am forced into my next step up until the eighth step.  Here is the position 
after 7 steps:

$[1,2,1,-2,1,2,1]$. See Figure~\ref{seven}.

\begin{figure}[hbt]
\vspace{5mm}
\setlength{\unitlength}{20mm}
\begin{picture}(5,1)
\multiput(1,0)(2,0){2}{\line(1,0){1}}
\multiput(2,0)(1,0){3}{\line(0,1){1}}
\multiput(2,1)(2,0){2}{\line(1,0){1}}
\end{picture}
\caption{A seven step square free self-avoiding walk}
\label{seven}
\end{figure}

Now based on the previous analysis I must chose $-2$ as my next step, but if I 
do this I will have the $[1,2,1,-2]$ twice in succession.  So as I want my walk 
to be square-free I am stuck, and can take no further steps.  Thus for $n\geq8$ 
the number of square-free self-avoiding walks is zero.


\begin{thebibliography}{1}

\bibitem{madras}
Neal Madras and Gordon Slade (1996). \emph{The Self-Avoiding Walk}. Birkhauser, 
Boston.  

\end{thebibliography}

\end{document}