Erdős Problem #1064
Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: proved (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.
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
Euler's totient function \(\phi(n)\) counts the integers from \(1\) to \(n\) that are relatively prime to \(n\). Compare the original value with the totient of the smaller integer \(n-\phi(n)\).
Erdős Problem #1064 asks for two apparently contrasting facts:
yet
Here “almost all” means that the proportion of positive integers satisfying the first strict inequality approaches \(1\) as the cutoff tends to infinity. A density-one statement can coexist with an infinite exceptional set.
A small example
For \(n=30\), we have \(\phi(30)=8\), and \(n-\phi(n)=22\), with \(\phi(22)=10\). Thus \(8<10\): \(30\) is an exception to the inequality that normally holds.
There is an explicit infinite family of exceptions. For every integer \(k\ge1\) take \(n=15\cdot2^k\). Then
Since \(n-\phi(n)=11\cdot2^k\), the reversed strict inequality holds for every member of this unbounded family. These equalities follow directly from the totient formula for coprime prime powers and were independently checked at finite values of \(k\).
A complete totient sieve for \(1\le n\le200{,}000\) finds \(194{,}833\) strict-greater cases, \(175\) equalities and \(4992\) strict-less cases. This finite frequency is not a proof that the limiting density is one.
What is known
This problem is proved in the literature. Luca and Pomerance, On some problems of Mąkowski–Schinzel and Erdős concerning the arithmetical functions \(\phi\) and \(\sigma\), Colloquium Mathematicum 92 (2002), 111–130, prove the density-one inequality and a stronger result allowing a lower-order error term. Earlier work by Grytczuk, Luca and Wójtowicz established relevant intermediate results.
The original problem appeared as Erdős's P.294 in Canadian Mathematical Bulletin 23 (1980), page 505. Its full original scan was not independently checked in this audit, so historical exact-wording equivalence remains open for editorial review.
GCL's current state
The authenticated source audit #2335 cites the primary published density-one result, the historical question and a frozen Lean formulation. The elementary infinite exceptional family and the stated \(200{,}000\)‑integer classification were independently recomputed.
The original pinned formal-conjectures file contains unproved theorem bodies. A newer external formal proof has been reported for the infinitude variant, but no independent GCL kernel replay or equivalence certification has been performed.
What remains
The external mathematical question is settled; the remaining GCL obligations are documentary and verification tasks. Acquire and hash-lock the original 1980 problem and complete 2001/2002 published proofs, compare every hypothesis and density quantifier, and replay the external Lean infinitude proof against a pinned environment. Do not infer the analytic density theorem from the explicit infinite family or the finite numerical proportion.
Sources and claim boundaries
- Erdős Problem #1064, current statement and proved-status reference.
- Luca and Pomerance (2002), journal article, Colloquium Mathematicum 92, 111–130; primary published result.
- Pinned formal-conjectures transcription, not proof certification.
- Authenticated GCL source return #2335, bounded source research and explicit checks, not independent certification or protected editorial admission.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2335 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.