Skip to content

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

\[ a^{n-1}\equiv1\pmod n. \]

Let \(C(x)\) count the Carmichael numbers no greater than \(x\). Erdős Problem #1057 asks whether they are sufficiently numerous that

\[ C(x)=x^{1-o(1)}. \]

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

\[ 3-1=2\mid560,\quad 11-1=10\mid560,\quad 17-1=16\mid560. \]

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

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.

Back to catalogue · Compendium introduction