Carmichael numbers: is the count $C(x)=x^{1-o(1)}$? (Erdős #1057)
Statement
A Carmichael number is a composite $n$ such that $a^{n}\equiv a\pmod n$ for every integer $a$ (by Korselt's criterion, equivalently: $n$ is squarefree and $p-1\mid n-1$ for every prime $p\mid n$). Let $C(x)$ count the Carmichael numbers in $[1,x]$. Is it true that $C(x)=x^{1-o(1)}$, i.e. $\log C(x)/\log x\to 1$ as $x\to\infty$?
Acceptance. FULLY RESOLVES (OPEN, proof-shaped): a complete proof that $\log C(x)/\log x\to 1$ (equivalently $C(x)=x^{1-o(1)}$), or a disproof. ADVANCES: an unconditional lower bound $C(x)>x^{\theta}$ with exponent $\theta$ strictly larger than the best stated above ($0.3389$, Lichtman), with proof; OR an improved unconditional upper bound; OR a rigorous conditional resolution under a clearly stated hypothesis; OR extend, with reproducible code, the exact computation of $C(x)$ to a new record $x$ and report $\log C(x)/\log x$ against the Pomerance heuristic. Deliver the proof, the improved exponent with its derivation, or the computation together with the extended data.
Background
Posed by Erdős [Er56c]; listed as open on erdosproblems.com/1057 (fetched 2026-07-21, status 'open'), and problem A13 in Guy's Unsolved Problems in Number Theory [Gu04]. Upper side: Erdős [Er56c] proved $C(x) < x\exp\!\big(-c\,\tfrac{\log x\,\log\log\log x}{\log\log x}\big)$, and Pomerance [Po89] gave a heuristic that this is the true order, $C(x)=x\exp\!\big(-(1+o(1))\tfrac{\log x\,\log\log\log x}{\log\log x}\big)$ — which would confirm $C(x)=x^{1-o(1)}$. Lower side: Alford, Granville, and Pomerance [AGP94] proved $C(x)\to\infty$, in fact $C(x)>x^{2/7}$ for large $x$; Harman [Ha08] improved the exponent to $0.33336704$, and Lichtman [Li22] pushed it to $0.3389$. So the conjectured exponent $1$ remains far above the best proven lower exponent. OEIS A006931 collects Carmichael-number data. A formalised statement exists in the google-deepmind/formal-conjectures Lean repository. No cash prize. Attacker's tool: the lower exponent is improved by analytic number theory (prime-tuple-type inputs feeding the AGP construction), while workstation computation of $C(x)$ over large $x$ tests the Pomerance heuristic empirically.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1057 (T. F. Bloom) | website |
| REF-02 | OEIS A006931 — Carmichael-number data | website |
| REF-03 | Lean formalisation (google-deepmind/formal-conjectures) of Erdős #1057 | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.