Skip to content

Erdős Problem #1164

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: proved (not automatically the live result).
Subject areas: probability.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

Erdős Problem #1164. How far from the origin does a long two-dimensional random walk completely cover the lattice?

\[ \frac{(\log R_n)^2}{\log n}\quad\text{and its limiting distribution require source verification.} \]

For simple symmetric random walk S_0=0,S_1,... on Z², let R_n be the radius of the largest Euclidean lattice disc around the origin fully visited by time n (a random variable depending on the path), not a deterministic radius guaranteed on almost every finite walk. Original Erdős–Taylor question asks log R_n scale sqrt(log n); R_n can be zero at small n, so log requires a large-n convention. The live site displays "P(((log R_n)^2/log n)≤x)=e^{-4x}" for all x>0. This is IMPOSSIBLE as a CDF: a cumulative distribution function is nondecreasing, while e^{-4x} is strictly decreasing. Record a source typography conflict; do not invent an inverse-x or survival correction.

A small example

Among 4^7=16384 length-7 planar walks, exactly 112 cover all four axial neighbors (and origin), finite probability 112/16384=7/1024. Covering unit disc cannot happen in fewer than 7 steps. Diagonal-path detours between axial neighbors explain why 24 is incorrect. This is finite evidence only. For any 0<xe^{-4y}, contradicting CDF monotonicity.

What is known

https://www.erdosproblems.com/1164 PROVED, Vardi [Va99,6.76], Erdős–Taylor. Révész [Re90] and Kesten first scale result, Dembo–Peres–Rosen–Zeitouni [DPRZ04] stronger covering-radius law. The original theorem is externally proved, but exact printed CDF/tail and constants require original paper comparison. No GCL advanced probability proof asserted.

GCL's current state

Authenticated source-bound original-issue audit reports the mathematical status, external source attribution and independently tested bounded evidence. The deterministic programme is ci/erdos_compendium_007_phase19_checks.py.

This source return is STATUS_CONFLICT. Neither an original-source proof review, Lean kernel certification, independent critical approval nor protected V2 admission has been completed.

What remains

ERDOS-1164-DPRZ-CDF-FIDELITY-001: inspect original DPRZ04 theorem with exact variable, <= versus >=, normalized constants, Euclidean norm and random-cover radius; correct maintained formula only with theorem-page evidence. Independently repeat finite path count.

Exact CDF expression and source semantics unresolved. General cover-time theorem external.

Sources and claim boundaries

https://www.erdosproblems.com/1164 ; [Va99,6.76],[Re90],[DPRZ04]; exact 112 walk count and CDF monotonicity proved.

Unaccepted editorial manuscript. The exact finite examples are independently checked; all general published claims await primary source fidelity review. A source-notation conflict is not a new theorem.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2435 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction