Erdoes #528 - working report - Erdős Problem a Day

Erdős problem 528 — wave w044

Access and research date: 2026-07-31 (UTC).

Claim labels:

[a] elementary-rigorous — a complete elementary argument is given here;
[b] rigorous-modulo-named-theorem — the named result was checked in the cited primary source;
[c] plausible/structural-unverified — heuristic or extrapolation, not a theorem;
[d] computational-only — an exact finite exhaustive computation, with no unproved asymptotic inference.

0. Mandatory live-page gate

[d, page observation] I fetched the rendered live page erdosproblems.com/528 through the Bright Data browser path, not direct datacenter curl. I separately fetched the LaTeX view and the discussion thread.

The following is the verbatim current statement from the page's LaTeX view:

Let $f(n,k)$ count the number of self-avoiding walks of $n$ steps (beginning at the origin) in $\mathbb{Z}^k$ (i.e. those walks which do not intersect themselves). Determine\[C_k=\lim_{n\to\infty}f(n,k)^{1/n}.\]

The live page showed:

status: OPEN;
claimed proofs: 0;
Currently working on this problem: None;
Interested in collaborating: None;
likes: None;
This problem looks difficult: None;
This problem looks tractable: None;
The results on this problem could be formalisable: None;
I am working on formalising the results on this problem: None;
formalised statement: No;
related OEIS entries: A387897 and A156816.

Thus the mandatory stop condition did not trigger.

Everything else mathematical on the live page

The known-results text, verbatim from the LaTeX view, is:

The constant $C_k$ is sometimes known as the connective constant. Hammersley and Morton \cite{HM54} showed that this limit exists, and it is trivial that $k\leq C_k\leq 2k-1$.
Kesten \cite{Ke63} proved that $C_k=2k-1-1/2k+O(1/k^2)$, and more precise asymptotics are given by Clisby, Liang, and Slade \cite{CLS07}.
Conway and Guttmann \cite{CG93} showed that $C_2\geq 2.62$ and Alm \cite{Al93} showed that $C_2\leq 2.696$. Jacobsen, Scullard, and Guttmann \cite{JSG16} have computed the first few decimal places of $C_2$, showing that\[C_2 = 2.6381585303279\cdots.\]See also [529].

The bibliography displayed by that view is:

[Al93] Sven Erick Alm, *Upper bounds for the connective constant of

self-avoiding walks*, Combin. Probab. Comput. (1993), 115–136.

[CG93] A. R. Conway and A. J. Guttmann, *Lower bound on the connective

constant for square lattice self-avoiding walks*, J. Phys. A (1993), 3719–3724.

[CLS07] Nathan Clisby, Richard Liang, and Gordon Slade, *Self-avoiding

walk enumeration via the lace expansion*, J. Phys. A (2007), 10973–11017.

[HM54] J. M. Hammersley and K. W. Morton, Poor man's Monte Carlo,

J. Roy. Statist. Soc. Ser. B (1954), 23–38; discussion 61–75.

[JSG16] Jesper Lykke Jacobsen, Christian R. Scullard, and Anthony J.

Guttmann, On the growth constant for square-lattice self-avoiding walks, J. Phys. A (2016), article 494004.

[Ke63] Harry Kesten, On the number of self-avoiding walks,

J. Mathematical Phys. (1963), 960–969.

The page has exactly one comment. The discussion thread gives, verbatim:

$C_2$ is remarkably close to A156816, noted there as a remarkable coincidence.

It was posted by TerenceTao at 17:04 on 9 September 2025. The site labels comments as unverified. There are no other comments or proof claims.

1. Primary-source literature audit

Original question and existence

[b] Erdős's original article exists and the cited page is correct:

P. Erdős, Some unsolved problems, Magyar Tud. Akad. Mat. Kutató Int.

Közl. 6 (1961), 221–254, repository scan.

Printed page 254 asks for the number of non-self-intersecting random-walk paths and says that the limit was known to exist but that sharper information was unavailable even in dimension two. The downloaded scan has SHA-256 6f6dac75cb03edcaf1d7e13509ea9001937248cea1fd5e932b386a6a0a7a1007.

[b] The Hammersley–Morton paper is real, with DOI 10.1111/j.2517-6161.1954.tb00145.x. For this report no black box is actually needed: section 2 gives the standard one-line submultiplicativity proof of existence.

A citation correction

[b] The page's mathematical large-d assertion is correct, but its [Ke63] citation appears to point to the wrong member of Kesten's two-paper sequence. Kesten's 1963 paper DOI 10.1063/1.1704022 is the ratio-limit paper. The abstract of On the number of self-avoiding walks II (1964), DOI 10.1063/1.1704216, explicitly states

C_d=2d-1-\frac1{2d}+O(d^{-2}).

Clisby–Liang–Slade also cite the 1964 paper, their reference [42], for this formula. This is a bibliographic correction, not a challenge to the result.

What is rigorously known beyond the live-page summary

[b] Hara and Slade, The self-avoiding-walk and percolation critical points in high dimensions, Combin. Probab. Comput. 4 (1995), 197–215, prove that the inverse-dimension asymptotic expansion exists to all orders.

[b] Clisby, Liang, and Slade, Self-avoiding walk enumeration via the lace expansion, DOI 10.1088/1751-8113/40/36/003, give the rigorous expansion through the $(2d)^{-11}$ term with error $O((2d)^{-12})$. They also enumerate $f(n,d)$ through $n=24$ for arbitrary dimension (by computing dimensions through 12); their machine-readable tables agree with every value recomputed below. Therefore the finite table in this report is an independent small verifier and a vehicle for the bounds, not a new record-length enumeration.

[b] The square-lattice exact enumeration was subsequently extended to 79 steps by Jensen, A new transfer-matrix algorithm for exact enumerations: self-avoiding walks on the square lattice.

The current rigorous $d=2$ interval is tighter than the page says

[b] Jensen, Improved lower bounds on the connective constants for two-dimensional self-avoiding walks, DOI 10.1088/0305-4470/37/48/001, proves

\[ 2.625622<C_2. \]

This improves the Conway–Guttmann value still displayed on the live page.

[b] Couronné, New Upper Bound for the Connective Constant for square-lattice Self-Avoiding Walks, J. Stat. Phys. 192 (2025), article 153, arXiv:2211.16146, proves

C_2\leq 2.662342426.

The peer-reviewed article was published on 31 October 2025; its introduction also identifies $2.625622$ as the best rigorous lower bound. Thus the page's Alm upper bound is stale.

[d, numerical only] Jacobsen–Scullard–Guttmann, On the growth constant for square-lattice self-avoiding walks, report

\[ C_2=2.63815853032790(3) \]

as a numerical estimate obtained by transfer-matrix extrapolation. It lies inside the rigorous interval above but is not an exact evaluation or a proof of those digits.

[b] He, Upper bounds for the connective constant of weighted self-avoiding walks, J. Phys. A 58 (2025), 505003, extends Alm's matrix method to anisotropic weights. Section 3.3 explicitly checks that on the isotropic line the resulting values reproduce Alm's unweighted bounds, so this recent paper does not supersede Couronné's unweighted $d=2$ bound.

[c, literature-search limitation] Exact-title, DOI, arXiv, and recent-bound searches found no primary source claiming an exact value of the hypercubic connective constant in any fixed dimension $d\geq2$. This is an honest search miss, not a theorem that no such source can exist. The live page's OPEN status is consistent with the 2025 paper.

2. Elementary setup

Write $c_n^{(d)}=f(n,d)$ and $c_0^{(d)}=1$.

Existence of the limit

[a] Splitting an $(m+n)$-step SAW after step $m$, translating the tail to the origin, injects it into a pair consisting of an $m$-step SAW and an $n$-step SAW. Hence

c_{m+n}^{(d)}\leq c_m^{(d)}c_n^{(d)}.

Fekete's elementary subadditivity lemma applied to $\log c_n^{(d)}$ gives

C_d=\lim_{n\to\infty}(c_n^{(d)})^{1/n} =\inf_{n\geq1}(c_n^{(d)})^{1/n}. \tag{2.1}

In particular,

c_n^{(d)}\geq C_d^n\qquad(n\geq0). \tag{2.2}

A fixed-first-edge upper bound

[a] By lattice symmetry, the number of $N$-step SAWs whose first directed edge is prescribed is $c_N^{(d)}/(2d)$. Take a long SAW, retain its first edge, and split its remaining steps into blocks of $N-1$. Each block, together with the directed edge immediately before it, is an $N$-step SAW with prescribed first edge. Global avoidance can only remove possibilities. A bounded final remainder does not affect exponential growth, so

C_d\leq \left(\frac{c_N^{(d)}}{2d}\right)^{1/(N-1)}. \tag{2.3}

This proof is included so that no finite-count inequality is imported from the literature.

3. Canonical-axis enumeration

Exact dimension polynomial

Call an abstract SAW canonical if coordinate axes are numbered in their order of first appearance and the first step on each new axis is positive. Let $a_{n,j}$ be the number of canonical $n$-step SAWs that use exactly $j$ axes.

[a] Every actual SAW using $j$ axes has a unique canonical form. Conversely, a canonical walk can be embedded by choosing an ordered injection of its axes into the $d$ physical axes and independently choosing the initial sign of each axis. Therefore

c_n^{(d)} =\sum_{j=0}^{\min(n,d)} a_{n,j}\,2^j(d)_j, \qquad (d)_j=d(d-1)\cdots(d-j+1). \tag{3.1}

This is an identity for every $n,d$, not an interpolation guess.

[d] A depth-first search that introduces only the next canonical axis computed the following exact rows:

| $n$ | $a_{n,0},a_{n,1},\ldots,a_{n,n}$ | |---:|:---| | 0 | 1 | | 1 | 0, 1 | | 2 | 0, 1, 1 | | 3 | 0, 1, 4, 1 | | 4 | 0, 1, 12, 9, 1 | | 5 | 0, 1, 35, 56, 16, 1 | | 6 | 0, 1, 97, 304, 167, 25, 1 | | 7 | 0, 1, 271, 1560, 1455, 391, 36, 1 | | 8 | 0, 1, 739, 7713, 11536, 4947, 786, 49, 1 | | 9 | 0, 1, 2033, 37606, 86708, 55608, 13555, 1422, 64, 1 | | 10 | 0, 1, 5512, 180783, 629624, 581145, 203845, 31990, 2381, 81, 1 |

The core recursion is:

def dfs(depth, used_axes):
    a[depth][used_axes] += 1
    if depth == N:
        return
    for axis in range(used_axes):
        for sign in (-1, 1):
            try_step_if_unvisited(axis, sign, depth, used_axes)
    # First use of a new axis is canonicalized to the positive direction.
    step_on_new_axis(used_axes)
    dfs(depth + 1, used_axes + 1)
    undo_new_axis_step(used_axes)

The standalone verifier contains the complete implementation. It also uses a separate, ordinary fixed-dimension DFS—without canonical axes—to compare all counts for $d=1,n\leq10$, $d=2,n\leq10$, and $d=3,n\leq8$.

4. Closed forms for three support strata

The enumeration suggests, and the next argument proves uniformly in $n$, the top three falling-factorial coefficients.

Theorem

[a] For $n\geq3$,

\boxed{ \begin{aligned} a_{n,n}&=1,\\ a_{n,n-1}&=(n-1)^2,\\ a_{n,n-2} &=\frac{3n^4-20n^3+48n^2-55n+36}{6}. \end{aligned}} \tag{4.1}

Consequently, the three highest support terms of (3.1) have a closed form for every $n$:

\begin{aligned} c_n^{(d)} ={}&2^n(d)_n +(n-1)^2\,2^{n-1}(d)_{n-1}\\ &+\frac{3n^4-20n^3+48n^2-55n+36}{6}\, 2^{n-2}(d)_{n-2}\\ &+\text{terms supported on at most \(n-3\) axes}. \end{aligned} \tag{4.2}

Proof

[a] If every step uses a new axis there is one canonical walk, proving the first line.

With $n-1$ axes, one axis occurs twice. Choose its two positions and the sign of its second occurrence. Of the $2\binom n2$ signed choices, exactly $n-1$ are an adjacent positive/negative reversal. Total repeat excess is one, so no longer loop is possible. Thus

a_{n,n-1}=2\binom n2-(n-1)=(n-1)^2.

With $n-2$ axes, the multiplicities have one of two types.

One axis occurs three times. There are $4\binom n3$ signed choices.

If exactly one of the two gaps between its occurrences is zero, only two rather than four sign choices avoid an immediate reversal; if both gaps are zero, only one survives. There are $(n-2)(n-3)$ triples with exactly one adjacent gap and $n-2$ fully consecutive triples. Hence the good count is \[ T_n=4\binom n3-2(n-2)(n-3)-3(n-2). \tag{4.3} \]

Two axes occur twice. There are $P=3\binom n4$ pair partitions of

the four repeated positions and four sign choices. The number of incidences of a pair occupying adjacent positions is $I=(n-1)\binom{n-2}{2}$. The number of partitions in which both pairs are adjacent is $D=(n-2)(n-3)/2$. Weighting a configuration with zero, one, or two adjacent pairs by $4,2,1$, respectively, leaves $4P-2I+D$ choices. There remain exactly $n-3$ uncounted bad walks: four consecutive steps with the interlaced pairing and both return signs negative, i.e. a square. Thus \[ U_n=12\binom n4-2(n-1)\binom{n-2}{2} +\frac{(n-2)(n-3)}2-(n-3). \tag{4.4} \]

Why is this exclusion complete? A repeated vertex creates a contiguous closed subwalk. If that subwalk uses $r$ axes, those axes contribute at least $r$ to the global repeat excess, which here is only two. Thus $r\leq2$. With one axis only a two-step reversal is possible; with two axes and total excess two, the only remaining non-backtracking loop is a four-step square.

Finally, simplifying $T_n+U_n$ gives the third line of (4.1). This also independently explains the last three entries in every computed row.

5. An injective layer construction

Let

G_d(z)=\sum_{m\geq0}c_m^{(d)}z^m.

Construction lemma

[a] For $d\geq2$, take any finite SAW in a copy of $\mathbb Z^{d-1}$ at height zero, step once in $+e_1$, take another translated $(d-1)$-dimensional SAW at height one, step in $+e_1$, and continue. Each height layer is visited only once, so different layers are disjoint and every resulting walk is self-avoiding. The vertical steps uniquely delimit the horizontal blocks, so the encoding is injective.

A horizontal block of length $m$ followed by its vertical delimiter has generating function contribution $c_m^{(d-1)}z^{m+1}$. Therefore the generating function of all complete block sequences is

S_d(z)=\frac1{1-zG_{d-1}(z)}. \tag{5.1}

If the series $G_{d-1}$ becomes singular before $zG_{d-1}(z)=1$, use that earlier singularity; otherwise use the first positive solution of the equation. In either case, coefficientwise inclusion gives a rigorous lower bound on $C_d$.

For $d=2$,

G_1(z)=1+2z+2z^2+\cdots=\frac{1+z}{1-z}.

Equation $zG_1(z)=1$ has root $\sqrt2-1$, proving the explicit bound

C_2\geq1+\sqrt2. \tag{5.2}

A certified recursive finite-data version

Suppose a rational number $b_{d-1}<C_{d-1}$ is already certified. Equation (2.2), together with the exact coefficients through $N=10$, gives the coefficientwise lower series

Q_{d-1}(z)= \sum_{m=0}^{10}c_m^{(d-1)}z^m+ \frac{(b_{d-1}z)^{11}}{1-b_{d-1}z} \ \leq\ G_{d-1}(z) \tag{5.3}

where the inequality is coefficientwise. Let $r_d\in(0,1/b_{d-1})$ be the unique zero of

zQ_{d-1}(z)-1. \tag{5.4}

Then (5.1) implies

C_d\geq r_d^{-1}. \tag{5.5}

To certify a displayed rational $b_d<r_d^{-1}$, it is enough to evaluate (5.4) exactly at $z=1/b_d$ and obtain a positive value. The verifier does this with fractions.Fraction, so no floating-point root is trusted.

6. Exact small case and certified bounds

[d] Evaluating (3.1), using (2.3) with $N=10$, and recursively using (5.3) gives the following table. Every decimal is treated as an exact rational: the lower signs in (5.4) and the upper ninth-power inequalities are checked by integer arithmetic.

| $d$ | $c_{10}^{(d)}$ | certified $b_d<C_d$ | certified $C_d<u_d$ | |---:|---:|---:|---:| | 2 | 44,100 | 2.4142135623 | 2.8128927751 | | 3 | 8,809,878 | 4.1451927623 | 4.8439769908 | | 4 | 276,750,536 | 5.9560363295 | 6.8812367202 | | 5 | 3,527,691,690 | 7.7550838845 | 8.9067893310 | | 6 | 26,583,605,772 | 9.5316423919 | 10.9239927854 | | 7 | 142,019,952,830 | 11.2877043031 | 12.9360703828 | | 8 | 595,065,468,048 | 13.0260261228 | 14.9449292322 | | 9 | 2,080,586,127,186 | 14.7488369050 | 16.9516734234 | | 10 | 6,323,384,122,580 | 16.4578610691 | 18.9569664283 |

[a+d] These independently certified intervals strictly improve both elementary page bounds $d\leq C_d\leq2d-1$ for every displayed dimension. They are not claimed to beat the literature frontier. In particular, for $d=2$ the primary-source interval

2.625622<C_2\leq2.662342426

is much stronger, and Hara–Slade–Sokal's loop-erasure bounds are much stronger than this elementary construction in dimensions 3 through 6.

7. Reproduction and independent checks

The complete standard-library verifier is erdos528_wavew044_reverify.py. Run from the repository root:

python runs/erdos528_wavew044_reverify.py

It performs all of the following from scratch:

canonical-axis DFS through $n=10$;
independent ordinary DFS in $d=1,2,3$;
exact checks of all three formulas in (4.1);
exhaustive generation of every layer-block sequence through total

length seven, checking self-avoidance, injectivity, and the coefficients of $1/(1-z(1+4z+12z^2))$;

exact Fraction certificates for all 18 bound endpoints.

The recorded run ended:

Independent direct-DFS checks: d=1 through n=10, d=2 through n=10, d=3 through n=8: PASS
Closed support-stratum formulas through n=10: PASS
Layer-family coefficients through length 7: [1, 1, 5, 21, 53, 197, 661, 2085]
ALL CHECKS PASSED
elapsed=2.19 sec maxrss=13660 KB

8. Exact remaining wall

[a] Nothing above determines a fixed $C_d$. Formula (4.2) controls the strata using $n,n-1,n-2$ axes. For fixed $d$, all three terms are identically zero once $n>d+2$, so they cannot influence the $n\to\infty$ limit. Finite exact counts give rigorous bounds but no uniform tail identity.

The missing lemma can be stated precisely:

Determine the dominant singularity of $G_d(z)=\sum_{n\geq0}c_n^{(d)}z^n$, or produce a finite-state/algebraic identity with a rigorously controlled remainder whose first singularity is exactly that of $G_d$.

That singularity is $1/C_d$. The layer construction only bounds it from one side, and the fixed-memory automaton bounds it from the other. The high-d lace expansion is asymptotic in $d$; even all its coefficients do not by themselves give an exact value at a fixed small integer $d$ without a summation or uniformity theorem.

[b, published computation cost] Couronné's preprint reports 430,365,791 automaton states, a 12.86 GB child-list file, 32 GB RAM, and one week for the loop-size-26 computation yielding the current $d=2$ upper bound. That is already far outside the allowed few-minute run.

[c] The state counts from loop sizes 24 to 26 grow by a factor about 5.4. A naive loop-size-28 extension would therefore be on the order of 2.3 billion states and roughly 70 GB of child-list storage, plausibly several weeks or hundreds to thousands of core-hours before independent certification. This is a resource estimate, not a theorem, and such a run would still tighten only an upper bound rather than determine $C_2$.

PARTIAL: Proved a uniform injective layer reduction, closed forms for the top three axis-support coefficients for every n, and independently certified exact n<=10 polynomials and strict two-sided bounds for dimensions 2 through 10; the exact fixed-d singularity remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger