7
$\begingroup$

Let $c_n$ be the number of self-avoiding walks in ${\mathbb Z}^2$ of length $n$. Because $c_n$ is a submultiplcative sequence ($c_{n+m} \leq c_nc_m$ for all $n, m \geq 1$), Fekete's lemma tells us that $\lim_{n \rightarrow \infty} c_n^{1/n}$ exists and equals $\inf c_n^{1/n}$. So we can define the connective constant $\mu = \lim_{n \rightarrow \infty} c_n^{1/n}$ that governs the growth rate of $c_n$, and if we happen to know a particular $c_n$ that gives a rigourous upper bound on $\mu$, namely $\mu \leq c_n^{1/n}$.

On page 10 of Madras and Slade's 1993 book "The self-avoiding walk", a better bound for $\mu$ is given: $ \mu \leq \left(\frac{c_n}{c_1}\right)^\frac{1}{n-1} ~~~~~(n \geq 2). $
This bound is attributed to Alm, but the only reference is to an unpublished manuscript of Ahlberg and Janson from 1980.

Does anyone know a good proof/reference for this bound? It would be implied by submultiplicativity of $a_n := c_{n+1}/c_1$, which in turn would be implied by the inequality $c_{n+m-1}c_1 \leq c_nc_m$ for all $n, m \geq 1$.

2 Answers 2

1

Maybe it's in Sven Erick Alm, Upper bounds for the connective constant of self-avoiding walks, Combin. Probab. Comput. 2 (1993), no. 2, 115–136, MR1249125 (94g:60126). The summary is,

We present a method for obtaining upper bounds for the connective constant of self-avoiding walks. The method works for a large class of lattices, including all that have been studied in connection with self-avoiding walks. The bound is obtained as the largest eigenvalue of a certain matrix. Numerical application of the method has given improved bounds for all lattices studied, e.g., $\mu\lt2.696$ for the square lattice, $\mu\lt4.278$ for the triangular lattice and $\mu\lt4.756$ for the simple cubic lattice.

0

The number $a_n=c_{n+1}/c_1$ represents the number of SA walks of length $n+1$ which make the first step to the right. Thus, $a_n$ counts obstructed SA walks of length $n$ with an obstacle placed to the left of their starting point.

This explains why $a_n$ is submultiplicative - every obstructed walk of length $m+n$ is the concatenation of an obstructed walk of length $m$ with a (rotated) obstructed walk of length $n$, where the obstacle for the second part of the walk is the penultimate vertex of the first part.