Skip to content

Erdős Problem #1166

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 #1166. How many different lattice sites have ever been the random walk's most-visited site by time n?

\[ U_n=\bigcup_{k=0}^nF(k),\quad |U_n|\ll(\log n)^2\text{ eventually a.s.} \]

For the same simple planar random walk and favorites F(k), ask whether union of all DISTINCT sites ever favorite by time n, U_n=∪_{k≤n}F(k), satisfies |U_n|≤(log n)^{O(1)} a.s. eventually. This differs from |F(n)| at a single time. Maximum local time T_n=max_x f_n(x) enters proof.

A small example

Exact enumeration of all 4096 six-step paths gives maximum 7 distinct ever-favorite sites by n6 and maximum ratio |U6|/T6=7. This can exceed eventual constant3 due to early >3 favorites; it does NOT contradict eventual a.s. polylog theorem.

What is known

https://www.erdosproblems.com/1166 PROVED [Va99,6.78], combining Tóth [To01] eventual |F(k)|≤3 a.s. with Erdős–Taylor [ErTa60] T_n≪(log n)^2 a.s. At each maximum local-time LEVEL j, newly favorite sites remain tied while maximum remains j; eventually ≤3 concurrent favorites, so at most three arrivals per level, plus finite early exceptions. Therefore |U_n|≪(log n)^2 a.s. Original proof requires source verification.

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 PARTIAL. Neither an original-source proof review, Lean kernel certification, independent critical approval nor protected V2 admission has been completed.

What remains

ERDOS-1166-FAVORITE-UNION-001: source-lock Tóth01 and ErTa60 exact local-time normalization, prove record-level charging rigorously, and independently reproduce bounded-walk data. Distinguish path-dependent random constant and deterministic coefficient.

Published general result proof not independently replayed, no new theorem claimed.

Sources and claim boundaries

https://www.erdosproblems.com/1166 ; [To01],[ErTa60], #1165; exact bounded enumeration.

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: #2437 — 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