Self-avoiding walk displacement: does $d_2(n)/\sqrt{n}\to\infty$ and $d_k(n)\ll\sqrt{n}$ for $k\geq3$? (Erdős #529)
Statement
Let $d_k(n)$ be the expected distance from the origin of a self-avoiding walk of $n$ steps on the integer lattice $\mathbb{Z}^k$ — that is, the average Euclidean displacement $\lvert X_n\rvert$ taken uniformly over all $n$-step nearest-neighbour walks that start at the origin and never revisit a vertex. Two questions: (i) is it true that $$\lim_{n\to\infty}\frac{d_2(n)}{n^{1/2}}=\infty?$$ and (ii) is it true that $$d_k(n)\ll n^{1/2}\quad\text{for all } k\geq 3?$$
Acceptance. FULLY RESOLVES: a rigorous proof of (i), that $d_2(n)/n^{1/2}\to\infty$ (for instance a proof of a super-diffusive lower bound such as the conjectured $d_2(n)=n^{3/4+o(1)}$), together with a rigorous proof of (ii), that $d_k(n)\ll n^{1/2}$ for every $k\geq 3$. A machine-checkable proof is preferred, otherwise a complete written proof; a numerical estimate alone does NOT resolve. ADVANCES: (a) a rigorous new bound on $d_k(n)$ for some $k\in\{2,3,4\}$ that strictly improves the best bound stated in the background (e.g. any rigorous super-$\sqrt{n}$ lower bound for $d_2$, or a rigorous $d_3(n)\ll n^{1/2}$), with proof; (b) a reproducible high-precision numerical determination of the exponent $\nu_k$ for $k=2,3,4$ with quantified error bars that improves on published estimates, together with the simulation or enumeration code. Deliver the proof file, or the simulation code plus measured exponents plus a full error analysis.
Background
Asked by Erdős [Er61, p.254]. In high dimensions the walk is diffusive: Slade [Sl87] proved that for $k$ sufficiently large $d_k(n)\sim D\,n^{1/2}$ with $D>0$ independent of $k$, and Hara and Slade [HaSl91, HaSl92] extended this to all $k\geq 5$ via the lace expansion. For $k=2$, Duminil-Copin and Hammond [DuHa13] proved the sub-ballistic bound $d_2(n)=o(n)$. It is conjectured (see the Madras–Slade monograph [MaSl93], §1.4) that the answer to (ii) is in fact NO for $k=3,4$, with $d_2(n)\sim D\,n^{3/4}$ (Flory exponent $3/4$, tied to $\mathrm{SLE}_{8/3}$), $d_3(n)\sim n^{\nu}$ with $\nu\approx 0.59$, and $d_4(n)\sim D(\log n)^{1/8}n^{1/2}$ (a logarithmic correction at the upper critical dimension $4$). Thus $k\geq 5$ is settled and the open frontier is exactly $k=2,3,4$; see also site problem #528 (erdosproblems.com/528). No cash prize is attached. Listed as open on erdosproblems.com/529 (fetched 2026-07-13, status 'open', tagged 'geometry | probability'). This studies the mean-displacement exponent and is closely related to — but distinct from — the venue problems on the self-avoiding-walk connective constant $\mu$ (which measures the growth rate of the NUMBER of self-avoiding walks on the square and cubic lattices), a different quantity. The attacker's tool: high-precision Monte Carlo (the pivot algorithm) and exact enumeration to estimate the exponents $\nu_k$ for $k=2,3,4$, plus rigorous lace-expansion and hyperscaling arguments; only $k\geq 5$ has a proof and the low-dimensional cases are proof-shaped.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #529 (T. F. Bloom) | website |
| REF-02 | Wikipedia — Self-avoiding walk | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.