What is the connective constant of the two dimensional square lattice? (Other lattices can be treated similarly, but not much more is known -- let's keep it simple).

We'll show log 2 ≤ μ ≤ log 3.

To do this, we'll show:

  1. At least 2n-1 distinct self-avoiding walks of length n on the square grid;
  2. No more than 4*3n-2 distinct self-avoiding walks of length n exist on the square grid.
Taking logarithms and limits (more properly, lim infs and lim sups), we shall see the desired bounds on μ.

  1. Consider the subset of ("monotone") paths starting from the origin which only step right or up. Clearly all these paths are self-avoiding, and equally clearly there are 2n-1 of them.

    So there are at least 2n-1 self-avoiding walks.

  2. Now note that any self-avoiding walk never revisits any square, so in particular it never steps back. Thus, a self-avoiding walk has 4 choices for the first step, and at most 3 choices for every step after. (Of course, in practice there will often be fewer than 3 choices for the next step; we're just saying the walk cannot return to where it just came from!)

    So no more than 4*3n-2 self-avoiding walks exist.

Using these techniques in d dimensions, we see that log d ≤ μ ≤ log (2d-1).