What this research found
A self-avoiding walk is a lattice path that never revisits a site, and it is the standard model of a polymer in a good solvent. No closed form is known for how many such walks of a given length exist, so the counts have to be built one walk at a time. A backtracking search enumerated every self-avoiding walk on the two-dimensional square lattice out to 20 steps, reaching 897,697,164 walks at that length in 6.05 seconds on a single core and matching the published OEIS A001411 sequence exactly at every length.
- All twenty computed counts matched OEIS A001411 exactly, with no mismatches, across values ranging from 4 walks at one step to 897,697,164 at twenty steps.
- Runtime grows geometrically at a factor of 2.686 per additional step over the window from 10 to 20 steps, within 1.8% of the square lattice's connective constant of 2.638. That confirms the cost is set by the sheer number of walks, and works out to roughly 6.7 nanoseconds of wall-clock time per completed walk at 20 steps.
- Memory never becomes the constraint. Backtracking holds only the single partial walk under construction, so the entire working state is an occupancy grid of 1,681 bytes at 20 steps, small enough to sit in the innermost cache.
- Estimating the connective constant from a series only twenty terms long is dominated by finite-size bias. A log-linear fit gives 2.6960 (+2.19%) and the raw ratio of successive counts gives 2.6788 (+1.54%), both biased high against the reference value of 2.638159.
- Dividing out the known correction using the exact planar critical exponent of 43/32 lands on 2.6319, within 0.24% of the reference value. What remains is a small even/odd oscillation between 2.6306 and 2.6389 rather than a systematic drift, which is the signature of the next-order corrections to scaling.
How it was done
The enumerator traversed the tree of partial paths depth-first, marking a site occupied on descent and clearing it on return, so each self-avoidance test was a single lookup into a dense occupancy grid of side 2n+1; because the grid border can never be reached, no bounds checking was needed. The lattice's eight-fold dihedral symmetry cut the search: fixing the first step to the +x direction supplies a factor of four, and splitting the second step into a self-symmetric straight branch and a reflection-doubled turn branch supplies the remaining factor of two, so the total is four times the straight-branch count plus eight times the turn-branch count. Compiling the recursion to native code with Numba is what brought 20 steps within a few seconds. The resulting counts were compared as exact integers against the published sequence, and the series was then used to estimate the connective constant by three independent routes.
Data sources
- OEIS A001411 — number of n-step self-avoiding walks on the square lattice, used as the verification reference
- Jacobsen, Scullard & Guttmann, Journal of Physics A 49:494004 (2016) — high-precision connective constant 2.63815853032790(3)
- Nienhuis, Physical Review Letters 49:1062 (1982) — exact two-dimensional critical exponent 43/32
Limitations
Direct enumeration is capped by its own exponential cost: extrapolating the fitted growth, 25 steps would take on the order of 20 minutes and 30 steps several hours on one core, whereas transfer-matrix methods reach 79 steps by never listing walks individually. A twenty-term series also cannot rival purpose-built long series for pinning down the connective constant, so these estimates validate the scaling form rather than sharpen the accepted value.
How this research was produced
K-Dense Web planned and ran this mathematics investigation end to end — gathering the sources, carrying out the analysis, producing the figures, and drafting the report. The full session transcript, including every intermediate step, is available to view.
