Problem 528

Let $f(n,k)$ count the number of self-avoiding walks of $n$ steps (beginning at the origin) in $\mathbb{Z}^k$ (i.e. those walks which do not intersect themselves). Determine

C_k=\lim_{n\to\infty}f(n,k)^{1/n}.

Source: erdosproblems.com/528

Geometry

Wiki page

Status

Open

No claim settles this problem.

Open, in the site's label. The accepted partial claims Kesten 1964 and Clisby, Liang and Slade 2007 give the asymptotics of $C_k$ in powers of $1/k$ . Conway and Guttmann 1993 and Alm 1993 bound $2.62\le C_2\le2.696$ . None determines $C_k$ for any $k\ge2$ . Hammersley and Morton [HM54] prove only that the limit exists, and the value of $C_2$ in [JSG16] is a numerical estimate, not a proof, so neither has a claim page.

Al93: Alm, Sven Erick, Upper bounds for the connective constant of self-avoiding walks. Combin. Probab. Comput. (1993), 115-136.
CG93: Conway, A. R. and Guttmann, A. J., Lower bound on the connective constant for square lattice self-avoiding walks. J. Phys. A (1993), 3719-3724.
CLS07: Clisby, Nathan and Liang, Richard and Slade, Gordon, Self-avoiding walk enumeration via the lace expansion. J. Phys. A (2007), 10973-11017.
HM54: Hammersley, J. M. and Morton, K. W., Poor man's Monte Carlo. J. Roy. Statist. Soc. Ser. B (1954), 23-38; discussion 61-75.
JSG16: Jacobsen, Jesper Lykke and Scullard, Christian R. and Guttmann, Anthony J., On the growth constant for square-lattice self-avoiding walks. J. Phys. A (2016), 494004, 18.
Ke63: Kesten, Harry, On the number of self-avoiding walks. J. Mathematical Phys. (1963), 960-969. This paper proves the ratio limit of the walk counts, not an expansion of $C_k$ . The site's commentary credits Kesten under this key with $C_k=2k-1-1/(2k)+O(1/k^2)$ ; that expansion is proved in the sequel, H. Kesten, On the number of self-avoiding walks. II, J. Math. Phys. 5 (1964), no. 8, 1128-1137, DOI 10.1063/1.1704216, to which Clisby, Liang and Slade [CLS07] attribute it.

Problem 528

Status

Proof claims

Discussion