Skip to content

Erdős Problem #820

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory.

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.

The question in plain language

For n>=1 let H(n)=least l>=3 for which some integers 2<=k=2 is IMPLICIT in the maintained statement: allowing k=1 makes its reported H(1)=3 false (k=1,l=2 gives gcd(0,1)=1). Ask whether H(n)=3 infinitely often and obtain fine two-sided growth estimates with exponents near c/loglog n.

A small example

An independently checked exact search 2<=k<l for n=1..10 gives H values [3,3,3,6,3,18,3,6,3,12]. For n=4, the least witness at l=6 is k=5: gcd(5^4-1,6^4-1)=gcd(624,1295)=1; no smaller l works. This finite computation cannot establish infinitely many n.

What is known

Maintained https://www.erdosproblems.com/latex/820, read 2026-10-14; original Erdős [Er74b] proves infinitely-often lower H(n)>exp(n^{c/(loglog n)^2}); van Doorn public comment SKETCHES a stronger infinitely-often lower exp(n^{c/loglog n}), not an independently verified theorem. The catalogue's proposed matching upper/lower logarithmic exponents and whether gcd(2^n-1,3^n-1)=1 infinitely often remain OPEN. Historical 1974 source not independently read.

The restriction \(2\leq k<l\) is necessary to match the maintained sequence. Without it, at \(n=1\), the pair \((k,l)=(1,2)\) gives \(\gcd(0,1)=1\) and would make \(H(1)=2\) instead of the reported 3. With positive bases at least two, \(H(n)=3\) is equivalent to \(\gcd(2^n-1,3^n-1)=1\). The infinitely-often lower and eventual upper growth questions have different quantifiers and remain OPEN.

The normalized definition consistent with the maintained numerical sequence is

$$

H(n)=\min\left{l\geq3:\exists\,2\leq k<l,\ \gcd(k^n-1,l^n-1)=1\right}.

$$

For \(l=3\) only \(k=2\) is possible, so \(H(n)=3\) exactly when \(\gcd(2^n-1,3^n-1)=1\). The growth proposal has two different quantifiers: an infinitely-often lower bound and an eventual upper bound.

GCL's current state

The original authenticated RESULT/1 source return has historical disposition STATUS_CONFLICT. This status and the original research exceptions are preserved, not silently converted into a theorem verdict. The maintained Erdős source and source-specific mathematical definitions were reviewed, and this article is editorially reviewed as a source-exception-annotated explanation under EC-BULK-005-R10, effective only after the exact-hash protected admission merges.

Source interpretation and unresolved mathematical qualification: The base domain must enforce 2<=k<l; published infinitely-often lower bounds are not the proposed exact exponential growth law.

The explanation is accepted for publication of established background, examples, and explicitly attributed current claims. It does not establish or formally certify the disputed original theorem, external model-assisted proof, historical interpretation, or any unreplayed Lean kernel file. Original source-fidelity and proof-review research holds remain.

What remains

Implement exact gcd search returning minimal l and witness k for n<=10 and assert no earlier l has a witness. Audit whether the original 1974 text imposes k>=2 and review van Doorn sketch independently before promoting its strength; distinguish necessary infinite-n from finite numerics.

Critical review must independently verify the original primary theorem, hypotheses, quantitative constants and simple examples. Finite source tests and website publication do not establish mathematical proof certification or independent editorial admission.

Sources and claim boundaries

  • Erdős problem #820, maintained LaTeX and original authenticated source return, checked 14 October 2026.
  • Pinned teorth/erdosproblems revision 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, Git blob 4e60263a80af6207aca494d2e1388e44fa372889. The source comment contains original bibliography and limits of direct proof inspection.
  • Editorial acceptance: NONE. Protected merge: NONE. Real-browser MathJax: NOT VERIFIED. Lean/new theorem certification: NOT CLAIMED.

Qualified editorial critical review: R10 source-exception dossier. The source-semantic exception is visible and its original research hold remains. Publication classification: REVIEWED EXPLANATORY ARTICLE WITH UNRESOLVED SOURCE/PROOF QUALIFICATIONS. Independent theorem proof or Lean certification: NOT CLAIMED.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2091 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • 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