Erdős Problem #529
Status Open · erdosproblems.comLLM status Open unverified
Erdős problemsTop Open Problems openaigpt pro 5.2 Not reported cataloguedOpenOpenStatement
Fix an integer $k\ge 2$ and $n\ge 1$. Let $\mathsf{SAW}_{k}(n)$ be the set of all length-$n$ nearest-neighbour walks \[ \omega=(\omega_0,\omega_1,\dots,\omega_n),\qquad \omega_0=0\in\mathbb Z^k,\qquad \|\omega_{t+1}-\omega_t\|_1=1, \] that are self-avoiding: $\omega_i\neq \omega_j$ for all $0\le i<j\le n$. Let $\mathbb P_{k,n}$ be the uniform probability measure on $\mathsf{SAW}_{k}(n)$, and let $X_n(\omega):=\omega_n$ be the endpoint. Let $\|\cdot\|$ denote the Euclidean norm on $\mathbb R^k$, and define \[ d_k(n):=\mathbb E_{k,n}\big[\|X_n\|\big]. \] The questions are:
$1$ Is it true that $\displaystyle \lim_{n\to\infty}\frac{d_2(n)}{\sqrt n}=+\infty$?
$2$ Is it true that for each fixed $k\ge 3$ there is a constant $C_k$ such that $d_k(n)\le C_k\sqrt n$ for all $n\ge 1$?
Ambiguities in the literal statement. The phrase "expected distance" is not explicit about the metric; I fix Euclidean norm because it is standard in the self-avoiding walk literature and matches the scaling statements in the problem text. Also "taking $n$ random steps ... conditional on no self intersections" is interpreted as conditioning simple random walk on self-avoidance; Lemma lem:529-uniform shows this is equivalent to the uniform measure on $\mathsf{SAW}_k(n)$.
Restatement from Math-840-A2 r1, with the source manuscript’s qualifications.
Original problem on erdosproblems.com
Statement licence: CC-BY-4.0 · Source file
Contributions 2
Reused writeup on Math-840 (gpt pro 5.2)
Erdős Problem 529 --- collection record
PROVENANCE AND STATUS
Official problem: https://www.erdosproblems.com/529Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/
This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.
Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.
Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/529.tex.
REUSED SOURCE 1
Original attribution:gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/529.tex.Let $d_k(n)$ be the expected distance from the origin after taking $n$ random steps from the origin in $\mathbb{Z}^k$ (conditional on no self intersections) - that is, a self-avoiding walk . Is it true that\[\lim_{n\to \infty}\frac{d_2(n)}{n^{1/2}}= \infty?\]Is it true that\[d_k(n)\ll n^{1/2}\]for $k\geq 3$? Slade [Sl87] proved that, for $k$ sufficiently large, $d_k(n)\sim Dn^{1/2}$ for some constant $D>0$ (independent of $k$). Hara and Slade ([HaSl91] and [HaSl92]) proved this for all $k\geq 5$. For $k=2$ Duminil-Copin and Hammond [DuHa13] have proved that $d_2(n)=o(n)$. It is now conjectured that $d_k(n)\ll n^{1/2}$ is false for $k=3$ and $k=4$, and more precisely (see for example Section 1.4 of [MaSl93]) that $d_2(n)\sim Dn^{3/4}$, $d_3(n)\sim n^{\nu}$ where $\nu\approx 0.59$, and $d_4(n)\sim D(\log n)^{1/8}n^{1/2}$. Madras and Slade [MaSl93] have a monograph on the topic of self-avoiding walks. See also [528] . References [DuHa13] Duminil-Copin, Hugo and Hammond, Alan, Self-avoiding walk is sub-ballistic . Comm. Math. Phys. $2013$, 401--423. [HaSl91] Hara, Takashi and Slade, Gordon, Critical behaviour of self-avoiding walk in five or more dimensions . Bull. Amer. Math. Soc. (N.S.) $1991$, 417--423. [HaSl92] Hara, Takashi and Slade, Gordon, Self-avoiding walk in five or more dimensions. {I}. {T}he critical behaviour . Comm. Math. Phys. $1992$, 101--136. [MaSl93] Madras, Neal and Slade, Gordon, The self-avoiding walk . $1993$, xiv+425. [Sl87] Slade, Gordon, The diffusion of self-avoiding random walk in high dimensions . Comm. Math. Phys. $1987$, 661--683.
FORMAL RESTATEMENT
Fix an integer $k\ge 2$ and $n\ge 1$. Let $\mathsf{SAW}_{k}(n)$ be the set of all length-$n$ nearest-neighbour walks \[ \omega=(\omega_0,\omega_1,\dots,\omega_n),\qquad \omega_0=0\in\mathbb Z^k,\qquad \|\omega_{t+1}-\omega_t\|_1=1, \] that are self-avoiding: $\omega_i\neq \omega_j$ for all $0\le i<j\le n$. Let $\mathbb P_{k,n}$ be the uniform probability measure on $\mathsf{SAW}_{k}(n)$, and let $X_n(\omega):=\omega_n$ be the endpoint. Let $\|\cdot\|$ denote the Euclidean norm on $\mathbb R^k$, and define \[ d_k(n):=\mathbb E_{k,n}\big[\|X_n\|\big]. \] The questions are:$1$ Is it true that $\displaystyle \lim_{n\to\infty}\frac{d_2(n)}{\sqrt n}=+\infty$?
$2$ Is it true that for each fixed $k\ge 3$ there is a constant $C_k$ such that $d_k(n)\le C_k\sqrt n$ for all $n\ge 1$?
Ambiguities in the literal statement. The phrase "expected distance" is not explicit about the metric; I fix Euclidean norm because it is standard in the self-avoiding walk literature and matches the scaling statements in the problem text. Also "taking $n$ random steps ... conditional on no self intersections" is interpreted as conditioning simple random walk on self-avoidance; Lemma Lemma (Conditioning equals uniform measure) shows this is equivalent to the uniform measure on $\mathsf{SAW}_k(n)$.
QUICK LITERATURE/CONTEXT CHECK
The problem statement itself records (i) diffusive scaling $d_k(n)\sim D\sqrt n$ for all $k\ge 5$ ([Sl87,HaSl91,HaSl92]), (ii) sub-ballisticity in $k=2$ ($d_2(n)=o(n)$, [DuHa13]), and (iii) conjectured exponents in $k=2,3,4$ (see [MaSl93]). Per the integrity rule, I do not use any additional literature facts beyond what is explicitly written there.ATTACK PLAN
Proof-track ideas. (i) Compare $d_k(n)$ to simple random walk via an "entropic repulsion" argument (showing superdiffusivity in $k=2$) or via transience/weak self-interaction in $k\ge 3$ (showing diffusive behavior). (ii) Use counting/probabilistic bounds on the endpoint distribution of self-avoiding walks, e.g. lower bounds on the fraction of walks reaching radius $\ge R$.Disproof-track ideas. (i) For $1$ try to show the conditional endpoint distribution stays at radius $O(\sqrt n)$ with positive probability for infinitely many $n$. (ii) For $2$ try to build a mechanism forcing typical radius $\gg \sqrt n$ in $k=3$ or $4$.
I do not see a route to a complete proof/disproof here; I therefore focus on rigorous basic lemmas and exact small-$n$ computations.
WORK
There are exactly $2k$ "straight-line" self-avoiding walks that take the same step direction at every time (choose $\pm e_i$ once and repeat); each has endpoint norm $\|X_n\|=n$. Under the uniform measure, the expected distance is at least $n$ times the probability of landing on one of these $2k$ walks: \[ d_k(n)\ge n\cdot \mathbb P(\text{walk is straight}) = n\cdot \frac{2k}{|\mathsf{SAW}_k(n)|}. \] Combining with the upper bound on $|\mathsf{SAW}_k(n)|$ yields $d_k(n)\ge n(2k-1)^{-(n-1)}$.
Finally, every nearest-neighbour walk satisfies $\|X_n\|\le \sum_{t=0}^{n-1}\|\omega_{t+1}-\omega_t\| = n$ because each step has Euclidean length $1$, hence $d_k(n)\le n$. ∎
FAST REALITY CHECK (exact small-$n$ computation).
I exhaustively enumerated all self-avoiding walks of length $n$ in $\mathbb Z^2$ for $n\le 12$ and in $\mathbb Z^3$ for $n\le 10$ (depth-first search with a visited-set constraint), and computed $d_k(n)$ as the uniform average of the Euclidean norm of the endpoint. The tables include the exact counts $c_n^{(k)}:=|\mathsf{SAW}_k(n)|$ as a sanity check.Dimension $k=2$ (exact for $1\le n\le 12$):
| $n$ | $c^{(2)}_n$ | $d_2(n)$ | $d_2(n)/\sqrt n$ |
| 1 | 4 | 1.000000 | 1.000000 |
| 2 | 12 | 1.609476 | 1.138071 |
| 3 | 36 | 2.046268 | 1.181413 |
| 4 | 100 | 2.557026 | 1.278513 |
| 5 | 284 | 2.951205 | 1.319819 |
| 6 | 780 | 3.390529 | 1.384178 |
| 7 | 2172 | 3.747689 | 1.416493 |
| 8 | 5916 | 4.149886 | 1.467206 |
| 9 | 16268 | 4.487147 | 1.495716 |
| 10 | 44100 | 4.861013 | 1.537187 |
| 11 | 120292 | 5.184254 | 1.563112 |
| 12 | 324932 | 5.537103 | 1.598424 |
Dimension $k=3$ (exact for $1\le n\le 10$):
| $n$ | $c^{(3)}_n$ | $d_3(n)$ | $d_3(n)/\sqrt n$ |
| 1 | 6 | 1.000000 | 1.000000 |
| 2 | 30 | 1.531371 | 1.082843 |
| 3 | 150 | 1.907569 | 1.101335 |
| 4 | 726 | 2.275768 | 1.137884 |
| 5 | 3534 | 2.577424 | 1.152659 |
| 6 | 16926 | 2.884472 | 1.177581 |
| 7 | 81390 | 3.149166 | 1.190273 |
| 8 | 387966 | 3.417774 | 1.208366 |
| 9 | 1853886 | 3.657142 | 1.219047 |
| 10 | 8809878 | 3.899908 | 1.233259 |
In these ranges, the ratio $d_k(n)/\sqrt n$ increases with $n$ (from $1$ at $n=1$ up to about $1.598$ at $n=12$ for $k=2$, and up to about $1.233$ at $n=10$ for $k=3$). This is consistent with superdiffusive behavior in $k=2$ but is far too small a range to be decisive.
VERIFICATION
- Quantifiers: $d_k(n)$ is defined for all $n\ge 1$ and $k\ge 2$; the conjectures are asymptotic in $n$ at fixed $k$.
- Lemma Lemma (Conditioning equals uniform measure): verified that all length-$n$ nearest-neighbour paths have probability $(2k)^{-n}$, so conditioning yields uniformity on $\mathsf{SAW}_k(n)$.
- Lemma Lemma (Crude counting and endpoint bounds): the step-count bound uses only the "no immediate backtrack" restriction, which is implied by self-avoidance.
- Computation: the enumerated counts in $k=2$ match standard initial values ($4,12,36,100,\dots$), serving as an internal consistency check; in $k=3$ the values are similarly internally consistent.
FINAL
UNRESOLVED(i) Strongest proved partial result. The conditioning description is exactly the uniform law on $\mathsf{SAW}_k(n)$ (Lemma Lemma (Conditioning equals uniform measure)); the trivial bounds $n(2k-1)^{-(n-1)}\le d_k(n)\le n$ hold for all $k,n$ (Lemma Lemma (Crude counting and endpoint bounds)); and exact values of $d_k(n)$ were computed for the $(k,n)$ ranges above.
(ii) First gap (crisp statement). Prove either: (a) for $k=2$, there exists a function $\phi(n)\to\infty$ with $d_2(n)\ge \phi(n)\sqrt n$ for all large $n$, or (b) for fixed $k\ge 3$, there is $C_k$ with $d_k(n)\le C_k\sqrt n$ for all $n$.
(iii) Top 3 next moves. 1. Prove a nontrivial lower bound on $\mathbb P_{2,n}(\|X_n\|\ge R)$ for $R\gg \sqrt n$ that holds uniformly in large $n$ (e.g. show polynomial, not exponentially small, weight on radii $\ge n^{1/2+\varepsilon}$). 2. Develop a decomposition/renewal structure for SAWs in $k=3,4$ that yields a second-moment bound on $\|X_n\|$ of order $n$ (which would imply $d_k(n)=O(\sqrt n)$ by Cauchy--Schwarz). 3. Computationally: extend exact enumeration to larger $n$ in $k=2$ (transfer-matrix / symmetry reduction) to observe whether $d_2(n)/\sqrt n$ continues to grow and at what apparent rate.
(iv) Minimal counterexample structure. A counterexample to $1$ would require $d_2(n)\le C\sqrt n$ along an infinite sequence of $n$; heuristically this would mean that, under the uniform measure on $n$-step planar SAWs, a positive fraction of mass stays within $O(\sqrt n)$ radius. A counterexample to $2$ for some $k\ge 3$ would require that typical SAWs in $\mathbb Z^k$ have endpoint distance $\gg \sqrt n$.
COMPLETION ESTIMATE
The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.
gpt pro 5.2 attempt on Math-840
Let $d_k(n)$ be the expected distance from the origin after taking $n$ random steps from the origin in $\mathbb{Z}^k$ (conditional on no self intersections) - that is, a self-avoiding walk . Is it true that\[\lim_{n\to \infty}\frac{d_2(n)}{n^{1/2}}= \infty?\]Is it true that\[d_k(n)\ll n^{1/2}\]for $k\geq 3$? Slade [Sl87] proved that, for $k$ sufficiently large, $d_k(n)\sim Dn^{1/2}$ for some constant $D>0$ (independent of $k$). Hara and Slade ([HaSl91] and [HaSl92]) proved this for all $k\geq 5$. For $k=2$ Duminil-Copin and Hammond [DuHa13] have proved that $d_2(n)=o(n)$. It is now conjectured that $d_k(n)\ll n^{1/2}$ is false for $k=3$ and $k=4$, and more precisely (see for example Section 1.4 of [MaSl93]) that $d_2(n)\sim Dn^{3/4}$, $d_3(n)\sim n^{\nu}$ where $\nu\approx 0.59$, and $d_4(n)\sim D(\log n)^{1/8}n^{1/2}$. Madras and Slade [MaSl93] have a monograph on the topic of self-avoiding walks. See also [528] . References [DuHa13] Duminil-Copin, Hugo and Hammond, Alan, Self-avoiding walk is sub-ballistic . Comm. Math. Phys. $2013$, 401--423. [HaSl91] Hara, Takashi and Slade, Gordon, Critical behaviour of self-avoiding walk in five or more dimensions . Bull. Amer. Math. Soc. (N.S.) $1991$, 417--423. [HaSl92] Hara, Takashi and Slade, Gordon, Self-avoiding walk in five or more dimensions. {I}. {T}he critical behaviour . Comm. Math. Phys. $1992$, 101--136. [MaSl93] Madras, Neal and Slade, Gordon, The self-avoiding walk . $1993$, xiv+425. [Sl87] Slade, Gordon, The diffusion of self-avoiding random walk in high dimensions . Comm. Math. Phys. $1987$, 661--683.
FORMAL RESTATEMENT
Fix an integer $k\ge 2$ and $n\ge 1$. Let $\mathsf{SAW}_{k}(n)$ be the set of all length-$n$ nearest-neighbour walks \[ \omega=(\omega_0,\omega_1,\dots,\omega_n),\qquad \omega_0=0\in\mathbb Z^k,\qquad \|\omega_{t+1}-\omega_t\|_1=1, \] that are self-avoiding: $\omega_i\neq \omega_j$ for all $0\le i<j\le n$. Let $\mathbb P_{k,n}$ be the uniform probability measure on $\mathsf{SAW}_{k}(n)$, and let $X_n(\omega):=\omega_n$ be the endpoint. Let $\|\cdot\|$ denote the Euclidean norm on $\mathbb R^k$, and define \[ d_k(n):=\mathbb E_{k,n}\big[\|X_n\|\big]. \] The questions are:$1$ Is it true that $\displaystyle \lim_{n\to\infty}\frac{d_2(n)}{\sqrt n}=+\infty$?
$2$ Is it true that for each fixed $k\ge 3$ there is a constant $C_k$ such that $d_k(n)\le C_k\sqrt n$ for all $n\ge 1$?
Ambiguities in the literal statement. The phrase "expected distance" is not explicit about the metric; I fix Euclidean norm because it is standard in the self-avoiding walk literature and matches the scaling statements in the problem text. Also "taking $n$ random steps ... conditional on no self intersections" is interpreted as conditioning simple random walk on self-avoidance; Lemma Lemma (Conditioning equals uniform measure) shows this is equivalent to the uniform measure on $\mathsf{SAW}_k(n)$.
QUICK LITERATURE/CONTEXT CHECK
The problem statement itself records (i) diffusive scaling $d_k(n)\sim D\sqrt n$ for all $k\ge 5$ ([Sl87,HaSl91,HaSl92]), (ii) sub-ballisticity in $k=2$ ($d_2(n)=o(n)$, [DuHa13]), and (iii) conjectured exponents in $k=2,3,4$ (see [MaSl93]). Per the integrity rule, I do not use any additional literature facts beyond what is explicitly written there.ATTACK PLAN
Proof-track ideas. (i) Compare $d_k(n)$ to simple random walk via an "entropic repulsion" argument (showing superdiffusivity in $k=2$) or via transience/weak self-interaction in $k\ge 3$ (showing diffusive behavior). (ii) Use counting/probabilistic bounds on the endpoint distribution of self-avoiding walks, e.g. lower bounds on the fraction of walks reaching radius $\ge R$.Disproof-track ideas. (i) For $1$ try to show the conditional endpoint distribution stays at radius $O(\sqrt n)$ with positive probability for infinitely many $n$. (ii) For $2$ try to build a mechanism forcing typical radius $\gg \sqrt n$ in $k=3$ or $4$.
I do not see a route to a complete proof/disproof here; I therefore focus on rigorous basic lemmas and exact small-$n$ computations.
WORK
There are exactly $2k$ "straight-line" self-avoiding walks that take the same step direction at every time (choose $\pm e_i$ once and repeat); each has endpoint norm $\|X_n\|=n$. Under the uniform measure, the expected distance is at least $n$ times the probability of landing on one of these $2k$ walks: \[ d_k(n)\ge n\cdot \mathbb P(\text{walk is straight}) = n\cdot \frac{2k}{|\mathsf{SAW}_k(n)|}. \] Combining with the upper bound on $|\mathsf{SAW}_k(n)|$ yields $d_k(n)\ge n(2k-1)^{-(n-1)}$.
Finally, every nearest-neighbour walk satisfies $\|X_n\|\le \sum_{t=0}^{n-1}\|\omega_{t+1}-\omega_t\| = n$ because each step has Euclidean length $1$, hence $d_k(n)\le n$. ∎
FAST REALITY CHECK (exact small-$n$ computation).
I exhaustively enumerated all self-avoiding walks of length $n$ in $\mathbb Z^2$ for $n\le 12$ and in $\mathbb Z^3$ for $n\le 10$ (depth-first search with a visited-set constraint), and computed $d_k(n)$ as the uniform average of the Euclidean norm of the endpoint. The tables include the exact counts $c_n^{(k)}:=|\mathsf{SAW}_k(n)|$ as a sanity check.Dimension $k=2$ (exact for $1\le n\le 12$):
| $n$ | $c^{(2)}_n$ | $d_2(n)$ | $d_2(n)/\sqrt n$ |
| 1 | 4 | 1.000000 | 1.000000 |
| 2 | 12 | 1.609476 | 1.138071 |
| 3 | 36 | 2.046268 | 1.181413 |
| 4 | 100 | 2.557026 | 1.278513 |
| 5 | 284 | 2.951205 | 1.319819 |
| 6 | 780 | 3.390529 | 1.384178 |
| 7 | 2172 | 3.747689 | 1.416493 |
| 8 | 5916 | 4.149886 | 1.467206 |
| 9 | 16268 | 4.487147 | 1.495716 |
| 10 | 44100 | 4.861013 | 1.537187 |
| 11 | 120292 | 5.184254 | 1.563112 |
| 12 | 324932 | 5.537103 | 1.598424 |
Dimension $k=3$ (exact for $1\le n\le 10$):
| $n$ | $c^{(3)}_n$ | $d_3(n)$ | $d_3(n)/\sqrt n$ |
| 1 | 6 | 1.000000 | 1.000000 |
| 2 | 30 | 1.531371 | 1.082843 |
| 3 | 150 | 1.907569 | 1.101335 |
| 4 | 726 | 2.275768 | 1.137884 |
| 5 | 3534 | 2.577424 | 1.152659 |
| 6 | 16926 | 2.884472 | 1.177581 |
| 7 | 81390 | 3.149166 | 1.190273 |
| 8 | 387966 | 3.417774 | 1.208366 |
| 9 | 1853886 | 3.657142 | 1.219047 |
| 10 | 8809878 | 3.899908 | 1.233259 |
In these ranges, the ratio $d_k(n)/\sqrt n$ increases with $n$ (from $1$ at $n=1$ up to about $1.598$ at $n=12$ for $k=2$, and up to about $1.233$ at $n=10$ for $k=3$). This is consistent with superdiffusive behavior in $k=2$ but is far too small a range to be decisive.
VERIFICATION
- Quantifiers: $d_k(n)$ is defined for all $n\ge 1$ and $k\ge 2$; the conjectures are asymptotic in $n$ at fixed $k$.
- Lemma Lemma (Conditioning equals uniform measure): verified that all length-$n$ nearest-neighbour paths have probability $(2k)^{-n}$, so conditioning yields uniformity on $\mathsf{SAW}_k(n)$.
- Lemma Lemma (Crude counting and endpoint bounds): the step-count bound uses only the "no immediate backtrack" restriction, which is implied by self-avoidance.
- Computation: the enumerated counts in $k=2$ match standard initial values ($4,12,36,100,\dots$), serving as an internal consistency check; in $k=3$ the values are similarly internally consistent.
FINAL
UNRESOLVED(i) Strongest proved partial result. The conditioning description is exactly the uniform law on $\mathsf{SAW}_k(n)$ (Lemma Lemma (Conditioning equals uniform measure)); the trivial bounds $n(2k-1)^{-(n-1)}\le d_k(n)\le n$ hold for all $k,n$ (Lemma Lemma (Crude counting and endpoint bounds)); and exact values of $d_k(n)$ were computed for the $(k,n)$ ranges above.
(ii) First gap (crisp statement). Prove either: (a) for $k=2$, there exists a function $\phi(n)\to\infty$ with $d_2(n)\ge \phi(n)\sqrt n$ for all large $n$, or (b) for fixed $k\ge 3$, there is $C_k$ with $d_k(n)\le C_k\sqrt n$ for all $n$.
(iii) Top 3 next moves. 1. Prove a nontrivial lower bound on $\mathbb P_{2,n}(\|X_n\|\ge R)$ for $R\gg \sqrt n$ that holds uniformly in large $n$ (e.g. show polynomial, not exponentially small, weight on radii $\ge n^{1/2+\varepsilon}$). 2. Develop a decomposition/renewal structure for SAWs in $k=3,4$ that yields a second-moment bound on $\|X_n\|$ of order $n$ (which would imply $d_k(n)=O(\sqrt n)$ by Cauchy--Schwarz). 3. Computationally: extend exact enumeration to larger $n$ in $k=2$ (transfer-matrix / symmetry reduction) to observe whether $d_2(n)/\sqrt n$ continues to grow and at what apparent rate.
(iv) Minimal counterexample structure. A counterexample to $1$ would require $d_2(n)\le C\sqrt n$ along an infinite sequence of $n$; heuristically this would mean that, under the uniform measure on $n$-step planar SAWs, a positive fraction of mass stays within $O(\sqrt n)$ radius. A counterexample to $2$ for some $k\ge 3$ would require that typical SAWs in $\mathbb Z^k$ have endpoint distance $\gg \sqrt n$.