An upper bound for the connective constant of the square lattice

Let μ be the connective constant of self-avoiding walks on the square lattice Z2, the exponential growth rate of the number of n-step self-avoiding walks. We prove μ ≤ 2.6600756. The previous best upper bound, μ ≤ 2.662342426, is due to Couronné. As in the work of Pönitz and Tittmann and of Couronné, the bound comes from a finite automaton whose states remember a bounded part of the past of the walk. Our automaton counts bridges, and, as in Couronné’s automaton, its states may contain cells that the walk has not visited; here these are cells that no infinite self-avoiding continuation of the walk can visit, recognized by three tests that depend only on the state and the step. Distinct bridges, preceded by a fixed infinite history, then give distinct paths in the automaton, so the Hammersley–Welsh theorem turns a bound for the number of paths into a bound for μ. The bound follows from a certificate, consisting of the automaton (4,124,965,633 states) and a vector of integer weights, which a program checks in exact integer arithmetic. The certificate and the programs are archived at doi:10.5281/zenodo.23540769, and the programs are available at github.com/tejasvi/connective-constant-bound.