Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|cite|improve this question

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.