WorksMathematics
An upper bound for the connective constant of the square lattice
Abstract
We prove that the connective constant of the square lattice , the exponential growth rate of the number of -step self-avoiding walks, satisfies . The previous best upper bound, , 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.
Introduction
Let be the number of -step self-avoiding walks on the square lattice that start at the origin. Since , the limit
exists [5]. It is called the connective constant of . Its value is not known; numerical estimates give [7].
Upper bounds for come from counting walks with a bounded memory. Alm [1] proved , and Noonan [13] . Pönitz and Tittmann [14] built finite automata whose states are the last steps of the walk, with the steps that can no longer matter removed, reaching . Couronné [3] added several simplification rules to the automaton of Pönitz and Tittmann and, considering loops of length up to 26, obtained . This was the best upper bound so far. Lower bounds come from counting irreducible bridges; in this way Jensen [8] obtained . On the hexagonal lattice the connective constant is known to be exactly [4].
Theorem 1.1. The connective constant of the square lattice satisfies
Our automaton reads bridges instead of walks. This loses nothing, because for the number of -step bridges that start at the origin the Hammersley–Welsh theorem [6] gives . Here a self-avoiding walk is a bridge if its first cell lies strictly to the left of all its other cells and its last cell lies in its rightmost column. A bridge that starts at the origin, preceded by the cells with and followed by translates of itself, each starting where the previous one ends, forms a two-sided infinite self-avoiding path. We give every bridge this half-line as its history. The automaton may then treat as visited every cell that the walk has not visited but that no two-sided infinite self-avoiding path extending the history and the walk so far can visit, since the walk will never visit it. We call such cells dead.
Figure 1 shows how dead cells arise. The state there is a path of 13 cells ending at the origin, which is the current position; the next step goes to the cell . Each cell marked a has three of its four neighbours in the state, so a path that entered it could not leave it. The cell marked b is enclosed by the state and . The cell marked c is connected to infinity only through the cell ; without it is cut off both from infinity and from the neighbours of outside the state. These are the three tests of Definition 3.1. Section 4 shows that the cells these tests find are dead, although they need not find every dead cell. In general a state is a set of cells, written as a lattice path ending at the current position, each of which is visited or dead. Our construction also uses simplification rules of [3] that put unvisited cells into a state; in our certificate every such cell passes one of the three tests, as the checkers verify.
The automaton is given by a finite certificate: its states, a child or the symbol (no child) for every state and step, and nonnegative integer weights. Distinct -step bridges give distinct paths of length from the start state (Theorem 4.1). The number of paths of length grows at most like , where , the ratio of the certificate, is the largest ratio of the total weight of the children of a state to its weight, over the states of positive weight (Definition 3.2 and Lemma 5.1). Definition 3.2 also restricts the states of weight zero. Hence . For our certificate, is the fraction of Theorem 1.1.
Section 2 introduces the history and the bridges, and Section 3 the automata with dead cells and their certificates. Section 6 explains how we built our certificate, of order 30, and compares its ratio with the values of [3]. Section 7 presents two independently written checkers that verify it in exact integer arithmetic, and Section 8 two formal proofs of Theorem 1.1 in Lean 4, which start from the definition of and formalize every step of the proof.
Bridges
We write and , and for the first coordinate of . An -step self-avoiding walk is a sequence of distinct points of with . It is a bridge if
Let be the number of -step bridges with . The sequence is supermultiplicative. Hammersley and Welsh [6] proved that . Hence (see also [9 Section 3.1])
Let . If is a bridge with , then for , because . Concatenating with translates of itself gives an infinite self-avoiding path that starts with and stays in the half-plane after its first step. Hence the two-sided sequence that runs through from to 0 and then follows this path is a two-sided infinite self-avoiding path. We call the history of the bridge. We call the points of cells. For , a continuation of at time is a sequence of distinct cells with for all , for and for . It visits a cell after time if for some . By the above, continuations exist for every . A continuation at time is also a continuation at every time .
Automata with dead cells
States and steps
3.1. States and steps. Let be the group of the eight symmetries of that fix the origin. A state is a self-avoiding lattice path with , and . We write for its set of cells. The origin is the current position, and the last step of the path is . The three steps of a state are ; the fourth neighbour of the origin is a cell of the state. The start state is the straight path , , of cells, for an even integer , which we call the order of the automaton. The order enters the definitions below only through ; it mainly governs the construction of the automaton (§ 6).
For a finite set , the complement has exactly one infinite connected component (for 4-connectivity). A cell of is connected to infinity in if it lies in this component. This is the case if and only if it is connected, within , to a cell outside the bounding box of .
Definition 3.1. Let be a state, a step with , and . A cell is dead for if
(a) at least three of the four neighbours of lie in ; or
(b) is not connected to infinity in ; or
(c) there is a cell such that, in , the cell is connected neither to infinity nor to any neighbour of outside .

Figure 1. A state of 13 cells, drawn as a path from its first cell (small dot) to the origin (large dot), entered with the last step , and the step . Each marked cell is dead by the test of Definition 3.1 with the same letter, test (c) with the cell .
Certificates
Definition 3.2. A certificate of order consists of a finite set of states that contains , an integer for each , and, for each and each step , an entry that is either the symbol or a state , such that the following hold.
(C1) If the entry for is , then , or is not connected to infinity in .
(C2) If the entry for is a state and , then there is such that every cell of the set lies in or is dead for .
(C3) ; every state with has only children with ; and there is no sequence () of states with in which each is a child of .
Here the children of are the states that occur in its entries. The ratio of the certificate is
where the sum runs over the steps whose entry is a state .
An entry for a step is allowed and need not satisfy any condition. Such an entry is never used by a walk and can only increase the counts below. The set in (C2) contains both and the cell , which is the image of the second-to-last cell
of ; so (C2) requires the cell in the excluded direction of the next state to lie in or to be dead. The automaton graph of a certificate is the directed graph on with one edge from to for each step of whose entry is . A path of length in it is a sequence of edges in which each edge starts at the state where the previous one ends; states and edges may repeat.
Soundness
Theorem 4.1. Let a certificate of order be given. For every , is at most the number of paths of length in the automaton graph that start at .
Proof. Fix an -step bridge with . For the past at time is . A cell is dead at time if no continuation of at time visits it after time . The cells of are dead at time , because the cells of a continuation are distinct. A cell that is dead at time is dead at every later time , because a continuation at time is a continuation at time , and a visit after time is a visit after time .
We define states and isometries of , with , such that
Let and . Then , so (4.1) holds for .
Suppose that and satisfy (4.1), and let . Put , a neighbour of the origin. Let be a continuation of at time . It is also a continuation at time , and it visits after time , so is not dead at time . By (4.1), . In particular , so is a step of . The cells with are not dead at time , by the definition of dead cells, so they avoid . Hence the cells , , form an infinite self-avoiding path that starts at and avoids , and is connected to infinity in . By (C1), the entry of is a state . Let be the first element, in a fixed list of the elements of , that satisfies (C2) for this entry. This choice makes the construction deterministic. Let and . Then and .
We show (4.1) for . Let . Every cell of is dead at time : the cells of were dead at time , and . Let be a cell of . If , then is dead at time . Otherwise is dead for by (C2), and we show that is dead at time . Let be a continuation of at time , and suppose that visits after time . The cells with are not dead at time , so they avoid . Apply , which is an isometry of that maps to . The images of the cells , , form a self-avoiding path that starts at a neighbour of , avoids , passes through and then goes to infinity. In case (a), at most one neighbour of lies outside . If there is none, then can neither start at , which is then not a neighbour of , nor enter . Otherwise let be this neighbour. If is the first cell of , then is a neighbour of , so , all four neighbours of lie in , and cannot leave . If not, enters from a neighbour outside , which can only be (), and it cannot leave , because the other neighbours of lie in and has already visited . In case (b), goes from to infinity in , which is impossible. In case (c), let be the cell of the test and the component of in . The first cell of is a neighbour of outside , so it is not in (it may be ), is finite, and every cell adjacent to but not in lies in . Hence passes through before it reaches and again after it leaves , which contradicts self-avoidance. In each case we have a contradiction, so is dead at time . This proves (4.1) for .
Let be the step used at time . The edges of the automaton graph given by and , for , form a path of length that starts at . The bridge can be recovered from this path: , and is determined by and by the symmetry , which depends only on , and the entry of . Hence distinct bridges give distinct paths, which proves the theorem. □
Remark 4.2. Two monotonicity facts are used in the proof. First, every cell of is dead at time , so a continuation at time avoids after time . Second, if is dead for , then is dead at time , although the tests (a)–(c) look only at : the case analysis uses only that is an infinite self-avoiding path that starts at a neighbour of and avoids . The cells of the past outside play no role; self-avoidance is used at cells outside (the neighbour in case (a), the cell in case (c)).
Counting
Lemma 5.1. Let a certificate have ratio , and let be the number of its states with . The number of paths of length in the automaton graph that start at is at most
If no state has , it is at most .
Proof. For and a state with , let be the number of paths of length from to that visit only states with . Then . This holds for , and
where the outer sums run over states with and the inner sum runs over the steps of whose entry is a state , as in the definition of . Since when , the number of such paths of length is at most . A path that leaves the states with does so at its first edge into a state with , and from then on it only visits states with , by (C3). These states form an acyclic graph with out-degrees at most 3, so the rest of the path has length less than , and there are at most possible rests for each first edge. The first edge into a state with follows a path of some length that stays in , and there are at most 3 choices for it. This gives the bound. □
Proof of Theorem 1.1. By Theorem 4.1 and Lemma 5.1, for the ratio of any certificate, with independent of . By (1), . By the computation of § 7, the files described there define a certificate of order 30 in the sense of Definition 3.2, and its ratio is the fraction in Theorem 1.1, which is larger than 1. □
Construction of the automaton
This section describes how we found the certificate.
Our construction program starts from the start state and explores the states reachable by steps. For a state and a step it lists several candidate children: subsets of together with dead cells, written as paths ending at and placed by a symmetry so that they end at the origin with last step , as in § 3. The size of a path is , the length of the loop obtained by closing it with a shortest lattice path. The candidates come from rules of the kind introduced by Pönitz and Tittmann [14] and Couronné [3]:
old cells are forgotten when the size exceeds the order (Couronné’s parameter plays the role of ); at order 30 the size of the child that keeps all cells may exceed by a bonus of at most 8. The bonus is read from one of two tables at the index ,
which measures how far the path is from a shortest path between its ends, and a test on the shape of the child chooses the table; the README of the archive gives the tables with the build command;
cells cut off by bridge configurations in the sense of [3], which are not related to the bridges of § 2, are recognized as dead;
loops sealed by the walk are treated as blocked regions;
steps into trapped regions get no child.
Couronné also uses a rule based on the enclosure of the oldest cell of a state (Section 4.2 of the arXiv version of [3]). Our section numbers and values from [3] refer to this version. Our program does not use this rule, and gives a step no child only in the two cases allowed by (C1). The small-loop rule of Couronné (Section 3.4 of [3]) requires that neither end of a loop sealed except for one gap cell is the current position, whereas our program allows such an end to be the current position, provided that no neighbour of the current position lies inside the loop; we call this condition the guard. A variant of our program without the guard produces children that violate (C2), as the rejected certificates of Appendix § 10 show.
The program explores the states twice. In the second pass, when it shortens a candidate child, it may stop at any state found in the first pass. It then alternates power iteration, which gives approximate positive weights, with a new choice, for every state and step, of the candidate child of smallest weight. The weights in the certificate are those of the last power iteration, computed before the last new choice of children; that choice can only lower the sums. The ratio is computed exactly from these weights.
Table 1 compares the ratio of our certificate with the values reported in [3]. It does not isolate the effect of dead cells, which would need certificates built with and without them at the same order.
| order | states | bound | |
| [3] | 24 | 79,510,267 | 2.664196283 |
| [3] | 26 | 430,365,791 | 2.662342426 |
| Theorem 1.1 | 30 | 24,887,440,008 | 2.658651241 |
Table 1. Upper bounds from automata: the values reported in [3] and the ratio of our certificate, truncated to nine decimals and accepted by both checkers of § 7.
The certificate and its verification
The checks below concern the certificate itself, so the construction of § 6 need not be trusted. The certificate for Theorem 1.1 has order and 24,887,440,008 states, none with . It is stored in three binary files: the states as 64-bit keys that encode their paths, the entries as indices into the list of states, and the weights as double-precision numbers , from which the checker computes exactly. The README of the archive describes the format.
The checker reads the three files and verifies the following, for every state and every step .
The keys are strictly increasing and decode to self-avoiding paths that end at the origin with last step , the start state is present, every lies in , and every index is smaller than the number of states.
If the entry is , then , or a flood fill from in does not reach the boundary of the bounding box of enlarged by one cell. This is (C1).
If the entry is a child , the checker tries the eight symmetries (the symmetry is not stored) and accepts the entry if for one of them every cell of lies in or passes one of the tests (a)–(c) of Definition 3.1. It does this also when , where Definition 3.2 requires nothing. For (b) it uses a flood fill in to the boundary of the bounding box of enlarged by one cell. For (c) it tries as the cells of one shortest path in from to that boundary; since (b) has failed, such a path exists. A cell outside the bounding box of stays connected to infinity when any one other cell is removed, so a flood fill with removed decides whether is connected to infinity in . Every cell for which (c) holds lies on every path from to the boundary, in particular on the chosen one. This is (C2).
It computes the ratio as an exact fraction in integer arithmetic and checks (C3).
The checker accepts the certificate, and its ratio is the fraction of Theorem 1.1. A second, independently written checker also accepts the certificate, with the same ratio; Appendix A describes it and the tests of both checkers.
Formal verification
Using the Lean 4 proof assistant [11] and the Mathlib library [10], we also proved Theorem 1.1, with the certificate of Section 7. The formal theorem has no hypotheses:
theorem connective_constant_le_unconditional :
∃ μ : ℝ, Tendsto (fun n : ℕ => (sawCount n : ℝ) ^ ((1 : ℝ) / n)) atTop (𝓝 μ) ∧
μ ≤ (105432502045487 : ℝ) / 39656386815908 ∧ μ < 2.6586513
It states that converges to a limit , that and that . Here sawCount n is : a walk is given by its sequence of steps in , its points are the partial sums of its steps, the first being the origin, and sawCount n is the number of step sequences whose points are distinct.
def walk {n : ℕ} (s : Fin n → Fin 4) (i : Fin (n + 1)) : Cell :=
∑ j : Fin n, if (j : ℕ) < (i : ℕ) then dir (s j) else 0
def sawCount (n : ℕ) : ℕ :=
(univ.filter fun s : Fin n → Fin 4 => Function.Injective (walk s)).card
Here Cell is and dir maps 0, 1, 2, 3 to . Apart from Cell, dir, walk and sawCount, the statement uses only definitions from Lean’s core library and from Mathlib.
The formal proof follows the paper. Its definition of a certificate is Definition 3.2 with (C3) replaced by the condition for all ; for such certificates it contains Theorem 4.1 and Lemma 5.1. It also contains the submultiplicativity and the existence of by Fekete’s lemma. In the proof of Theorem 4.1 it uses one continuation of the bridge, the one through the history, the bridge and its translates (Section 2). It replaces (4.1) by the statement that does not visit after time , proved by the case analysis above, and (2.1) by a weaker form of the Hammersley–Welsh inequality,
which suffices because the factor is . The proof splits the walk at the first time at which its first coordinate is smallest and unfolds each of the two parts by reflections. The injection records the split time and the times of the at most reflections in each part. With a step put in front, this gives an injective map from walks to pairs of such a record and a bridge of steps, and there are at most records. With the bound for , this inequality yields .
The certificate is checked by a program written in Lean, and a Lean proof shows that every certificate it accepts satisfies the formal definition with ratio at most . In this first formal proof, the check runs as compiled code, split into theorems proved by native_decide, so its trusted base includes the Lean compiler and interpreter, the C compiler that Lean uses and the Lean runtime. Besides the standard axioms propext, Classical.choice and Quot.sound, the theorem depends on one auxiliary axiom for each compiled check, and the rest of the proof, including the soundness of the checking program and inequality (3), is checked by Lean’s kernel.
A second formal proof of Theorem 1.1, with the same statement, is in the directory lean_k30e/ of the archive. Since it depends only on propext, Classical.choice and Quot.sound, it needs no code generated by Lean’s compiler, and its trusted base is Lean’s kernel, including the kernel’s built-in arithmetic on natural numbers. A proof of this kind for the weaker bound , from an earlier certificate of order 26, is archived at doi:10.5281/zenodo.23636439. Appendix A describes both checks.
Concluding remarks
The bound of Theorem 1.1 remains about 0.02 above the numerical estimate of [7]. In [3], raising the order from 24 to 26 lowers the bound by about 0.002 and multiplies the number of states by about 5.4, and our automaton of order 30 already has about states, for which the first checker of § 7 needs about 1.3 terabytes of memory. The method is thus limited by the size of the automaton. Lowering the bound further at a manageable size therefore needs rules or tests that lower the ratio at a given order, for instance tests that recognize more dead cells.
Details of the checks
The second checker and the tests
The second checker and the tests. The checking logic of the second checker of § 7 was first written from the description of the checked conditions, before its author read the first checker; the version used differs from this first version only in its output and in three changes that can only cause a rejection, which the README of its directory lists. It uses flood fills on rows stored as bit masks, and for (c) it tries as only the cells of the component of in that share a side or a corner with a cell of . No valid is missed. Test (b) has shown that is connected to infinity, and removing a cell leaves connected to infinity in two cases: if none of the eight cells around lies in , because these cells then connect the four neighbours of ; and if lies outside the component of , because removing then does not change that component. The two checkers report the same numbers of entries , of entries with a child and of dead cells of each kind, although they list in different orders, on which the counts of dead cells depend.
A program in Python also checks certificates of order 10, 12 and 14. They were built by the same construction program with the same rules and the default values of its other parameters, without the tables of bonuses used at order 30. Unlike the two checkers, it tries as every cell of the bounding box of enlarged by one cell, and it gives the same ratios as the two checkers. Both checkers accept the certificates of order 10 to 16 built in this way.
Both checkers reject certificates that must fail (those of orders 12, 14 and 16 built without the guard of § 6, and the accepted certificate of order 16 with a child removed or children redirected), and both report a larger ratio after a weight of that certificate is halved.
The formal proofs
The formal proofs. The checking program of the first formal proof checks the conditions of Definition 3.2 for every state, with positive weights and the ratio of Theorem 1.1. Every claim that a cell is not connected to infinity, or in test (c) to a neighbour of , is checked again on the region that the flood fill returns: this region must contain the cell and lie in a bounded box, every unblocked neighbour of its cells must lie in it, and in test (c) it must contain no unblocked neighbour of ; so errors in the flood fills or in the search for cannot lead to an acceptance. Neither the construction of the automaton (§ 6) nor the largest ratio is computed in Lean; the program checks only that for every state .
The certificate enters as data, converted into records that Lean compiles into string constants; the checking program checks whatever records it is given, and the theorem follows if the check succeeds.
The general parts of the proof (the soundness of the checking program, the cover of the states by the compiled checks, Theorem 4.1, Lemma 5.1, the bound from the bound for , and inequality (3)) depend only on the standard axioms.
The second formal proof checks the certificate inside Lean’s kernel. Instead of trying the eight symmetries for a child and the three tests for a dead cell, its checking program reads hints: the symmetry to use, and the test (a), (b) or (c) that applies, with the cell for test (c). The hints are computed beforehand by compiled code but are not trusted, since a wrong hint can only make the check fail; the README of the directory lean-k30e/ describes the structure of this proof and its build. For both formal proofs, the general parts were also accepted by two further implementations of the Lean kernel, nanoda [12] and lean4lean [2].
Data availability
The two checkers, the program in Python, the construction program, the programs for the tests of Appendix § 10, and the Lean files of both formal proofs of § 8 with the programs that generate their data files are archived at doi:10.5281/zenodo.23715897, together with the list of the units of the second formal proof, the SHA-256 checksums of their compiled files, and the compiled public files of its data modules, part modules and root. The three files of the certificate were compressed with xz, the file of entries in four pieces and the file of weights in five; the ten compressed files are archived in five records, doi:10.5281/zenodo.23574056, doi:10.5281/zenodo.23574058, doi:10.5281/zenodo.23574060, doi:10.5281/zenodo.23574062 and doi:10.5281/zenodo.23574064.
Three earlier certificates of ours, of orders 26 and 28, built by an earlier version of the construction program, are also archived, and both checkers accept them. The one of order 28 with 5,792,114,594 states is at doi:10.5281/zenodo.23551536 (keys and weights) and at doi:10.5281/zenodo.23551538 (entries). The other two are at doi:10.5281/zenodo.23548806; they have fewer than states and store the entries as 32-bit indices, with for . The second checker uses 32-bit indices exactly when there are fewer than states. The first checker takes the width from the size of the file of entries. The repository https://github.com/tejasvi/connective-constant-bound/tree/v8 (commit 9a451bfeddf4) also holds the programs and the Lean files.
Use of AI tools
Generative AI tools were used to find and prove the results, to write the programs and the Lean formalization, and to draft the text. The author reviewed the arguments, the programs and the formal statements, and takes responsibility for the content.
References
ORCID: https://orcid.org/0000-0003-4668-3639
References
- [1]S. E. Alm, Upper bounds for the connective constant of self-avoiding walks, Combin. Probab. Comput. 2 (1993), 115–136.DOI
- [2]M. Carneiro, Lean4Lean: verifying a typechecker for Lean, in Lean, arXiv:2403.14064, 2024.arxiv.org/abs/2403.14064
- [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.org/abs/2211.16146
- [4]H. Duminil-Copin and S. Smirnov, The connective constant of the honeycomb lattice equals √(2 + √2), 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.DOI
- [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.DOI
- [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.DOI
- [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.DOI
- [11]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.DOI
- [12]nanoda_lib, a type checker for Lean 4, https://github.com/ammkrn/nanoda_lib.
- [13]J. Noonan, New upper bounds for the connective constants of self-avoiding walks, J. Stat. Phys. 91 (1998), 871–888.DOI
- [14]A. Pönitz and P. Tittmann, Improved upper bounds for self-avoiding walks in Z^d, Electron. J. Combin. 7 (2000), R21.