Erdős Problem #1057
Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
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.
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
A Carmichael number is a composite positive integer that behaves like a prime in one important modular-arithmetic test: for every integer \(a\) relatively prime to \(n\), it satisfies
Let \(C(x)\) count the Carmichael numbers no greater than \(x\). Erdős Problem #1057 asks whether they are sufficiently numerous that
This means that \(\log C(x)/\log x\) approaches \(1\) as \(x\) grows. Merely knowing that infinitely many Carmichael numbers exist does not answer it.
A small example
Consider \(561=3\cdot11\cdot17\). Its prime factors are distinct, and
By Korselt's criterion, this makes \(561\) a Carmichael number. The same exact test verifies \(1105=5\cdot13\cdot17\) and \(1729=7\cdot13\cdot19\): for each prime divisor \(p\), \(p-1\) divides \(n-1\). We independently checked these factorizations and divisibilities. Three examples demonstrate the concept but reveal little about the asymptotic count \(C(x)\).
What is known
Erdős's 1956 paper On Pseudoprimes and Carmichael Numbers gave an upper bound smaller than \(x\). Alford, Granville and Pomerance proved in 1994 that infinitely many Carmichael numbers exist and obtained a lower bound of order \(x^{2/7}\) for sufficiently large \(x\). Later improvements include a lower-bound exponent \(0.3389\) attributed to Lichtman's work on primes in arithmetic progressions.
These are major results, but an exponent strictly below \(1\) cannot establish the desired \(x^{1-o(1)}\) conclusion. The canonical catalogue therefore still marks the problem open. A further reported exponent \(0.34\) has been disputed in the site's history and is not adopted here as established.
GCL's current state
The authenticated source audit #2328 checks the finite Carmichael examples, identifies the published and conjectured bounds, and reads the frozen Lean statement.
The Lean source correctly expresses the main question in terms of the limit of \(\log C(x)/\log x\). Its literature-labelled auxiliary claims and main conjecture still include unproved placeholders. No GCL proof replay or independent certification is asserted.
What remains
The open problem requires a lower bound approaching \(x^{1-\varepsilon}\) for every fixed \(\varepsilon>0\) at sufficiently large \(x\), or a counterexample to this growth law. A bounded next investigation is to pin the exact original and later lower-bound papers, compare their stated exponents and hypotheses, and verify Korselt's criterion computationally at a reproducible finite cutoff. Finite enumeration must not be extrapolated into an asymptotic proof.
Sources and claim boundaries
- Erdős Problem #1057, statement and dated status notes.
- Alford, Granville and Pomerance (1994), There Are Infinitely Many Carmichael Numbers, Annals of Mathematics 139, 703–722.
- Lichtman, arXiv:2211.09641, improved results bearing on Carmichael-number lower bounds.
- Frozen formal-conjectures statement.
- Authenticated GCL source audit #2328, partial source evidence, not proof certification or editorial admission.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2328 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- 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.