An upper bound for the connective constant of the square lattice

A mix of human-written and AI-generated textHuman understanding: all partsmath.CO — Combinatoricsmath-ph — Mathematical Physicsmath.PR — Probability

Contributed by Tejasvi Singh Tomar ↗

Version 1 / Nov 15, 2026 / CC BY 4.0

Abstract

We prove that the connective constant μ\mu of the square lattice Z2\mathbb{Z}^2, the exponential growth rate of the number of nn-step self-avoiding walks, satisfies μ≤2.6586513\mu\le2.6586513. The previous best upper bound, μ≤2.662342426\mu\le2.662342426, is due to Couronné. Like the bounds of Pönitz and Tittmann and of Couronné, ours comes from a finite automaton that remembers a bounded part of the past of the walk. The new idea is to count bridges. Since they can all be preceded by the same infinite history, the automaton may treat as visited the unvisited cells that no infinite self-avoiding continuation can reach, and three tests on the current state and the next step recognize such cells. The bound is checked in exact integer arithmetic and proved in the Lean proof assistant.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23715896

References

  1. S. E. Alm, Upper bounds for the connective constant of self-avoiding walks , Combin. Probab. Comput. 2 (1993), 115--136.
  2. M. Carneiro, Lean4Lean: verifying a typechecker for Lean, in Lean , arXiv:2403.14064, 2024.arXiv
  3. O. Couronné, New upper bound for the connective constant for square-lattice self-avoiding walks , J. Stat. Phys. 192 (2025), 153; arXiv:2211.16146.arXiv
  4. H. Duminil-Copin and S. Smirnov, The connective constant of the honeycomb lattice equals 2+2\sqrt{2+\sqrt2} , Ann. of Math. (2) 175 (2012), 1653--1665.
  5. J. M. Hammersley and K. W. Morton, Poor man's Monte Carlo , J. Roy. Statist. Soc. Ser. B 16 (1954), 23--38.
  6. J. M. Hammersley and D. J. A. Welsh, Further results on the rate of convergence to the connective constant of the hypercubical lattice , Quart. J. Math. Oxford Ser. (2) 13 (1962), 108--110.
  7. J. L. Jacobsen, C. R. Scullard and A. J. Guttmann, On the growth constant for square-lattice self-avoiding walks , J. Phys. A 49 (2016), 494004.
  8. I. Jensen, Improved lower bounds on the connective constants for two-dimensional self-avoiding walks , J. Phys. A 37 (2004), 11521--11529.
  9. N. Madras and G. Slade, The Self-Avoiding Walk , Birkhäuser, Boston, 1993.
  10. The mathlib Community, The Lean mathematical library , in: Proc. 9th ACM SIGPLAN Int. Conf. Certified Programs and Proofs (CPP 2020), 2020, 367--381.
Show all 14 referencesShow fewer references
  1. L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language , in: Automated Deduction -- CADE 28, Lecture Notes in Comput. Sci. 12699 , Springer, 2021, 625--635.
  2. nanoda_lib , a type checker for Lean 4, https://github.com/ammkrn/nanoda_lib.link
  3. J. Noonan, New upper bounds for the connective constants of self-avoiding walks , J. Stat. Phys. 91 (1998), 871--888.
  4. A. Pönitz and P. Tittmann, Improved upper bounds for self-avoiding walks in Zd\Z^d , Electron. J. Combin. 7 (2000), R21.

Version history

  1. v1 · 10 pagesSubmitted by Tejasvi Singh TomarPublished on Zenodo: https://doi.org/10.5281/zenodo.23715896CurrentNov 15, 2026