we-solve (beta)

Math-839-A1 · revision r1 · on Math-839

Reused writeup on Math-839 (gpt pro 5.2)

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Erdős Problem 528 --- collection record
  2. PROVENANCE AND STATUS
  3. REUSED SOURCE 1
  4. COMPLETION ESTIMATE

Erdős Problem 528 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/528

Saved 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/528.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/528.tex.

FORMAL RESTATEMENT. Fix $k\in\mathbb N$. A self-avoiding walk (SAW) of length $n$ in $\mathbb Z^k$ is a sequence of vertices $(v_0,v_1,\dots,v_n)$ with $v_0=0$, $\|v_{i+1}-v_i\|_1=1$ for each $i$ (nearest-neighbor steps), and all vertices $v_0,\dots,v_n$ distinct. Let $f(n,k)$ be the number of such SAWs. Define \[C_k = \lim_{n\to\infty} f(n,k)^{1/n} \] (if the limit exists). The problem asks to determine $C_k$.

QUICK LITERATURE/CONTEXT CHECK. The problem statement reports that Hammersley--Morton showed $C_k$ exists; it is also stated that $k\le C_k\le 2k-1$. Further asymptotics and numerical bounds for $k=2$ are mentioned in the statement.

ATTACK PLAN.

  • Proof track (existence and basic bounds): Prove submultiplicativity $f(n+m,k)\le f(n,k)f(m,k)$, apply Fekete's lemma to $\log f(n,k)$ to show $\lim (1/n)\log f(n,k)$ exists, hence $C_k$ exists. Prove trivial bounds by explicit constructions and by comparison to non-backtracking walks.
  • Determination track: For fixed $k$, try to compute/estimate $C_k$ by bounding $f(n,k)$ via combinatorial decompositions or expansions (lace expansion, etc.). For large $k$, try asymptotic expansion.
  • Disproof track: Not applicable to existence (existence is known and also follows from the submultiplicativity proof below). "Determine $C_k$" remains open in the exact sense for small $k$.

WORK.

Fast reality check (exact enumeration for small $n$). By brute-force backtracking we computed $f(n,k)$ for $n\le 10$ for $k=2,3$: 

k=2 vals n=0..10: [1, 4, 12, 36, 100, 284, 780, 2172, 5916, 16268, 44100]
  n 10 f^{1/n} 2.913693458576192
k=3 vals n=0..10: [1, 6, 30, 150, 726, 3534, 16926, 81390, 387966, 1853886, 8809878]
  n 10 f^{1/n} 4.948766803773582
(Here $f^{1/n}$ denotes $f(n,k)^{1/n}$.) These approach known approximate values slowly.

Lemma 528.1 (submultiplicativity and existence of $C_k$). For every $k\ge 1$ and all integers $m,n\ge 0$, \[f(n+m,k)\le f(n,k)\,f(m,k). \] Consequently the limit $\lim_{n\to\infty} f(n,k)^{1/n}$ exists (finite) and equals $\inf_{n\ge 1} f(n,k)^{1/n}$.

Proof. Fix $k$. Given a SAW $\omega=(v_0,\dots,v_{n+m})$ of length $n+m$, define its prefix $\omega^{(1)}=(v_0,\dots,v_n)$ (a SAW of length $n$ from the origin) and its suffix translated to the origin \[\omega^{(2)} = (w_0,\dots,w_m),\qquad w_j = v_{n+j}-v_n. \] Because $\omega$ is self-avoiding, the suffix vertices $v_n,\dots,v_{n+m}$ are distinct; hence $(w_0,\dots,w_m)$ are distinct as well, and successive differences are still unit vectors, so $\omega^{(2)}$ is a SAW of length $m$ from the origin.

Thus we have a map \[\Phi: \{\text{SAWs of length }n+m\} \to \{\text{SAWs of length }n\}\times\{\text{SAWs of length }m\} \] given by $\Phi(\omega)=(\omega^{(1)},\omega^{(2)})$. This map is injective: if $\Phi(\omega)=\Phi(\omega')$, then the prefixes coincide and end at the same vertex, and the translated suffixes coincide, so the full sequences coincide. Therefore \[f(n+m,k)\le f(n,k)f(m,k). \]

Define $a_n=\log f(n,k)$ for $n\ge 1$. The inequality is $a_{n+m}\le a_n+a_m$, i.e. $(a_n)$ is subadditive. By Fekete's lemma, \[\lim_{n\to\infty}\frac{a_n}{n} = \inf_{n\ge 1}\frac{a_n}{n}. \] Exponentiating yields existence of $\lim_{n\to\infty} f(n,k)^{1/n}$ and the identity with the infimum. $\square$

Lemma 528.2 (trivial bounds $k\le C_k\le 2k-1$). For every integer $k\ge 1$, \[k\le C_k\le 2k-1. \]

Proof. Lower bound. Consider only walks that at each step increment one coordinate by $+1$ (never stepping in negative directions). There are exactly $k$ choices at each step, hence $k^n$ such walks of length $n$. Any such walk is self-avoiding because every step strictly increases the $\ell_1$-norm and coordinates are nondecreasing, so no vertex repeats. Thus $f(n,k)\ge k^n$ for all $n$, hence $f(n,k)^{1/n}\ge k$ and taking $n\to\infty$ gives $C_k\ge k$.

Upper bound. A self-avoiding walk is in particular non-backtracking: after taking a step, the next step cannot immediately return to the previous vertex, because that would repeat a vertex. The number of non-backtracking walks of length $n$ from the origin is exactly $2k(2k-1)^{n-1}$: there are $2k$ choices for the first step and then at each subsequent step at most $2k-1$ choices (anything except the immediate reverse). Therefore \[f(n,k)\le 2k(2k-1)^{n-1}. \] Taking $n$th roots, \[f(n,k)^{1/n}\le (2k)^{1/n}(2k-1)^{(n-1)/n}. \] Letting $n\to\infty$ yields $C_k\le 2k-1$. $\square$

VERIFICATION.

  • Lemma 528.1: The injection $\omega\mapsto(\omega^{(1)},\omega^{(2)})$ is correct because translation preserves self-avoidance of the suffix and the splitting point is fixed at step $n$.
  • Lemma 528.2 lower bound: monotone "positive-steps-only" walks cannot self-intersect because the $\ell_1$-norm strictly increases by $1$ each step.
  • Lemma 528.2 upper bound: self-avoiding implies non-backtracking, so bounding by the number of non-backtracking walks is valid.

FINAL. UNRESOLVED

(i) Strongest proved partial result: Existence of $C_k$ via submultiplicativity (Lemma 528.1) and the basic bounds $k\le C_k\le 2k-1$ (Lemma 528.2).

(ii) First gap (crisp): Determine $C_k$ explicitly (even for $k=2$) or prove sharper rigorous bounds/asymptotics beyond $k\le C_k\le 2k-1$.

(iii) Top 3 next moves (concrete):

  1. For fixed small $k$ (especially $k=2$), compute $f(n,k)$ for larger $n$ using transfer-matrix or pruning algorithms to tighten numerical bounds on $C_k$.
  2. Prove improved rigorous upper/lower bounds for $C_2$ by constructing families of SAWs for lower bounds and using combinatorial decompositions for upper bounds.
  3. For large $k$, attempt to re-derive the first terms of the $1/k$ asymptotic expansion by bounding the contribution of self-intersections perturbatively.

(iv) Minimal counterexample structure: If one conjectures a specific closed form for $C_k$, a counterexample would consist of a rigorous bound separating $C_k$ from that value; since $C_k$ exists and is deterministic, "counterexamples" here are quantitative separations rather than structural pathologies.

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.