Erdős problem #1057 — live-page audit, exact census through \(10^9\), and the analytic wall

Date: 2026-07-29 (UTC)

Outcome

[d] I exhaustively classified every integer \(n\le 10^9\) with two complete kernels and obtained

The two kernels agree term by term. An independent Python trial-division enumeration agrees through \(10^6\), every one of the 646 outputs has a fresh factor/Korselt certificate, and the original congruence \(a^n\equiv a\pmod n\) was checked for every base \(a\) for all outputs through \(10^4\).

[a] This finite result neither proves nor refutes an asymptotic assertion with an unspecified \(o(1)\). The open question is therefore not closed.

[b, Lichtman Corollary 1.2] The accepted unconditional lower exponent located in the literature is \(0.3389\). [c] Li's arXiv preprint claims \(0.34\), but the live-page owner explicitly records doubts and does not accept that improvement; I did not attempt to certify the preprint's 44-page sieve argument.

[b, Wright 2020, conditional] A precise sufficient missing theorem is a uniform near-linear least-prime-in-an-arithmetic-progression bound: if there is a fixed \(A\) such that every sufficiently large coprime pair \((a,m)\) has a prime

then Wright's theorem gives

Thus (0.1), or a comparably strong replacement inside the Alford--Granville--Pomerance construction, is an exact analytic wall for a known route. It is a sufficient input, not a claim that it is logically necessary.

Claim labels

• [a] elementary-rigorous: proved here without a conjectural input.
• [b] rigorous-modulo-named-theorem: the named published theorem is used.
• [c] plausible/structural-unverified: heuristic, conjectural, or not

independently certified here.

• [d] computational-only: exact finite computation, with a reproducible

checker.

0. Mandatory live-page audit

[d, live-page observation] I fetched the rendered problem page and its discussion thread through the Bright Data browser path, not direct datacenter curl.

The page at erdosproblems.com/1057, accessed 2026-07-29, showed:

• OPEN;
• 0 claimed proofs for this problem;
• Currently working on this problem: None;
• Interested in collaborating: None;
• two comments;
• page last edited 16 January 2026.

[d, live-page observation] The other displayed markers (Likes, This problem looks difficult, This problem looks tractable, The results ... could be formalisable, and I am working on formalising ...) all showed None. The page lists a formalised statement and OEIS A006931. Therefore the mandated collision/claim stop condition did not trigger.

Current statement, verbatim

Let \(C(x)\) count the number of Carmichael numbers in the interval \([1,x]\). Is it true that \(C(x)=x^{1-o(1)}\)?

Results listed on the live page

The following is a faithful record of the page, not an extrapolation.

• [b, Erdős 1956]

\[ C(x)<x\exp\left(-c\frac{\log x\log\log\log x}{\log\log x}\right) \] for some \(c>0\).

• [c, Pomerance 1989 heuristic]

\[ C(x)=x\exp\left(-(1+o(1)) \frac{\log x\log\log\log x}{\log\log x}\right). \]

• [b, Alford--Granville--Pomerance 1994]

\(C(x)\to\infty\), quantitatively \(C(x)>x^{2/7}\) for large \(x\).

• [b, Harman 2008] \(C(x)>x^{0.33336704}\) for large \(x\).
• [b, Lichtman 2022] The exponent is improved to \(0.3389\).
• [b, Korselt's criterion] A composite \(n\) is Carmichael exactly when

\(n\) is squarefree and \(p-1\mid n-1\) for every prime \(p\mid n\).

• [d, bibliographic observation] The page points to problem A13 in Guy's

collection.

The two comments

[d, live-page observation] Quanyu Tang's 6 January 2026 comment says:

1. Lichtman's arXiv:2211.09641v1, Corollary 1.2, gives \(0.3389\).
2. Runbo Li's arXiv:2308.04458v8, Theorem 10, claims \(0.34\), but Tang had

not verified its details.

[d, live-page observation] Thomas Bloom replied on 16 January 2026 that Lichtman's exponent had been added, but that there was doubt over Li's work, so Li's claimed improvement would be omitted pending independent verification. The site warns that comments are unverified.

1. Primary-source literature check

I searched the exact problem statement, the cited titles, the two arXiv IDs, recent Carmichael-density papers, and recent tabulation papers. I opened the primary texts rather than relying on search snippets.

1.1 Unconditional and heuristic results

1. [b] P. Erdős,

On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201--206. The paper states the displayed upper bound and explicitly says Erdős instead conjectures \(C(x)>x^{1-\varepsilon}\) for every fixed \(\varepsilon>0\) and all sufficiently large \(x\). [d] SHA-256 of the PDF examined: ebf46ddaaf076d96dd7810f6de821133211ae5aaad49967ca27297edffafb3d8.

1. [c] C. Pomerance,

Two methods in elementary analytic number theory, in Number Theory and Applications (1989), 135--161. Its heuristic assumes many primes with suitably smooth \(p-1\), then assumes approximate uniform distribution of subset products modulo a chosen \(L\). It predicts \(C(x)\ge x/L(x)^{1+o(1)}\), where \[ L(x)=\exp\!\left(\frac{\log x\log\log\log x}{\log\log x}\right). \] [d] The scanned PDF was OCR-checked; SHA-256: 9e49a40799d4d3c26ecf0adfbb780a9dddb4d00912b39e2d3b51a0803a8632b5.

1. [b] W. R. Alford, A. Granville, and C. Pomerance,

There are infinitely many Carmichael numbers, Annals of Mathematics 139 (1994), 703--722, DOI 10.2307/2118576. The quantitative bound is \(C(x)>x^{2/7}\) for sufficiently large \(x\).

1. [b] G. Harman,

Watt's mean value theorem and Carmichael numbers, International Journal of Number Theory 4 (2008), 241--248. The live page records the resulting exponent \(0.33336704\).

1. [b] J. D. Lichtman,

Primes in arithmetic progressions to large moduli, and shifted primes without large prime factors, arXiv:2211.09641v1 (2022). Theorem 1.1 gives many primes with \(P^+(p-1)\le p^{0.2844}\); Corollary 1.2 explicitly states that there are at least \(x^{0.3389}\) Carmichael numbers up to sufficiently large \(x\). The exponent comes from \[ 0.4736(1-0.2844)=0.33890816. \] [a] The last multiplication is exact decimal arithmetic. [d] SHA-256 of the PDF examined: 78a22cc13b68ab72a4c7ee4cb60bcb9a57d344a0ea60da36e372abd6763c82c4.

1. [b] D. Larsen,

Bertrand's Postulate for Carmichael Numbers, IMRN 2023, 13072--13098. For every \(\delta>0\), it gives at least \[ \exp\!\left(\frac{\log x}{(\log\log x)^{2+\delta}}\right) \] Carmichael numbers in a specified short interval just above \(x\). [a] This is \(x^{o(1)}\), so by itself it does not improve the positive power \(0.3389\) in the global counting problem.

1.2 Conditional near-solution

[b, conditional] T. Wright, A conditional density for Carmichael numbers, Bulletin of the Australian Mathematical Society 101 (2020), 379--388, proves (0.2) under the near-linear least-prime conjecture (0.1).

[a] Since

Wright's conditional bound implies the requested \(C(X)=X^{1-o(1)}\) (the reverse upper bound \(C(X)\le X\) is trivial).

Wright also isolates two older AGP inputs. In his notation:

• [c] for every \(E<1\), a positive proportion of primes \(p\le x\)

should satisfy \(P^+(p-1)<x^{1-E}\);

• [c] for every \(B<1\), primes should have the stated lower

distribution in residue classes to moduli of size essentially \(x^B\), outside a bounded exceptional set.

[b, AGP/Wright framework] When suitable versions hold at parameters \((E,B)\), the construction gives \(C(X)\gg X^{EB}\). [a] Therefore versions valid for arbitrarily \(E,B\) close to \(1\) would settle #1057. The accepted numerical state is far from this: Lichtman's smooth-shifted-prime input gives \(1-0.2844=0.7156\), while Harman's companion exponent is \(0.4736\), giving the product \(0.33890816\).

1.3 The disputed \(0.34\) claim

[c] R. Li, The number of primes in short intervals and numerical calculations for Harman's sieve, arXiv:2308.04458v8 (revised 16 October 2025), Theorem 10, states

[a] The numerical product is

[c] The substantive unverified input is Li's new \(0.5248\) sieve theorem, not this multiplication. The arXiv paper has eight versions, includes computer-assisted integral estimates, and was not certified in this run. Consistent with the live-page warning, I do not promote its conclusion to a known theorem. [d] SHA-256 of v8 examined: b16c709be1c33506bf9877a1770ab5209664d7460bab9b015e58e2f1095cc816.

1.4 Computation literature

[d] A. Shallue and J. Webster, Advances in tabulating Carmichael numbers, Research in Number Theory 11 (2025), article 8, report exactly 49,679,870 Carmichael numbers below \(10^{22}\). Their published table has

through \(10^3,\ldots,10^9\), independently matching every count recomputed here. Their complete \(10^{22}\) count has effective finite exponent

[a] A finite effective exponent is not an asymptotic exponent and cannot decide the problem.

[d] SHA-256 of the arXiv v3 PDF examined: 4d39890f99d3ebd6d80c6289436a03dc77512dc3fd08d2588ba60c1607d219ed.

[c, honest search negative] My searches found no primary source after Lichtman that both claims and has an independently accepted unconditional exponent above \(0.3389\). This is a report of the search performed, not a proof that no such source exists.

2. Exact finite reduction

2.1 Why only odd composites must be enumerated

[b, Korselt] A Carmichael number is squarefree. [a] If it were even and composite, it would have an odd prime divisor \(p\); then \(p-1\) would be even but would have to divide the odd number \(n-1\), impossible. If there were no odd prime divisor, squarefreeness would force \(n=2\), which is prime. Thus every Carmichael number is an odd composite.

2.2 Lcm form of Korselt

For squarefree \(n\), define

[a] The collection of divisibilities \(p-1\mid n-1\) for every \(p\mid n\) is equivalent to the single condition \(L(n)\mid n-1\). If \(n=mp\) is squarefree with \(p\nmid m\), then

Also \(L(n)\mid\prod_{p\mid n}(p-1)=\varphi(n)<n\), so a 32-bit value is safe through the chosen bound.

2.3 Completeness of the two kernels

[a] Kernel A sieves the smallest odd prime factor of every odd composite. For every odd prime \(p\le\sqrt N\), it marks all odd multiples beginning at \(p^2\). Every odd composite \(n\le N\) has a prime factor at most \(\sqrt n\), so no odd composite is omitted. It then factors each such \(n\), rejects a repeated factor, and checks every Korselt divisibility.

The essential direct logic is:

for every odd composite n <= N:
    x = n
    good = true
    while x > 1:
        p = smallest_prime_factor(x)  # x itself if x is prime
        x = x / p
        if p divides x: reject n      # not squarefree
        if (p-1) does not divide (n-1): reject n
    if good: emit n

[a] Kernel B is an induction using (2.1). It stores zero for a nonsquarefree odd integer and otherwise stores \(L(n)\). It emits a composite precisely when \(L(n)\mid n-1\). This does not re-use Kernel A's sequence of per-factor divisibility decisions.

L(1) = 1
for odd n in increasing order:
    if n is prime:
        L(n) = n-1
    else:
        p = smallest_prime_factor(n)
        m = n/p
        if p divides m or L(m) == 0:
            L(n) = 0
        else:
            L(n) = lcm(L(m), p-1)
            if L(n) divides n-1: emit n

[b, Korselt + the elementary sieve arguments above] Each kernel is a complete census, not merely a candidate search. Their term-by-term agreement is an error check; completeness does not depend on trusting a published list.

3. Exact computation

3.1 Reproducibility

The complete standalone source is runs/erdos1057_wavew030_verify.py. It embeds, compiles, and runs both C++ kernels, and then performs the independent Python audits. It has no network dependency and downloads no sequence.

Run:

python runs/erdos1057_wavew030_verify.py

[d] SHA-256 of the standalone verifier: 2ca0197d18bc13578ffb535320c2452113c8289a296dd55da61cc98b4b62ad08.

3.2 Exact table

Here \(\omega(n)\) is the number of distinct prime factors, \(\alpha(x)=\log C(x)/\log x\), and

Pomerance's more precise heuristic predicts \(h(x)\to1\), but the displayed values are only finite data.

[d]

| \(x\) | \(C(x)\) | \(\omega=3\) | \(\omega=4\) | \(\omega=5\) | \(\omega=6\) | \(\alpha(x)\) | \(h(x)\) | |---:|---:|---:|---:|---:|---:|---:|---:| | \(10^3\) | 1 | 1 | 0 | 0 | 0 | 0.000000000000 | 2.933185377527 | | \(10^4\) | 7 | 7 | 0 | 0 | 0 | 0.211274510004 | 2.195472574346 | | \(10^5\) | 16 | 12 | 4 | 0 | 0 | 0.240823996531 | 2.076319648690 | | \(10^6\) | 43 | 23 | 19 | 1 | 0 | 0.272244742597 | 1.979457683111 | | \(10^7\) | 105 | 47 | 55 | 3 | 0 | 0.288741328439 | 1.933880792918 | | \(10^8\) | 255 | 84 | 144 | 27 | 0 | 0.300817522554 | 1.904949023962 | | \(10^9\) | 646 | 172 | 314 | 146 | 14 | 0.312248057555 | 1.879887651059 |

[d] The newline-separated complete list has SHA-256 3ca5b343bfb3bc0169fc4bd661860e2904691b5c6401e91501c0a9f5bbd22232. Its first ten and last ten terms are:

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341
975303121, 977737321, 977892241, 981567505, 981789337,
985052881, 986088961, 990893569, 993420289, 993905641

3.3 Full verifier output

[d]

PASS: the direct-factor and lcm-recurrence kernels agree term by term
PASS: independent trial-division certificates for all 646 terms
PASS: independent complete Python enumeration through 1,000,000 (43 terms)
PASS: universal a^n == a (mod n) audit through 10,000
LIMIT=1000000000
COUNT=646
LIST_SHA256=3ca5b343bfb3bc0169fc4bd661860e2904691b5c6401e91501c0a9f5bbd22232
CPP_SOURCE_SHA256=42b0bd4f59428a898d12dcf36ec82ce94159216d2dbd81240ea8aaf35628eb4e
FIRST_10=561,1105,1729,2465,2821,6601,8911,10585,15841,29341
LAST_10=975303121,977737321,977892241,981567505,981789337,985052881,986088961,990893569,993420289,993905641
DECADE_TABLE
x,count,omega_distribution,logC_over_logx,h
10,0,-,-,-
100,0,-,-,-
1000,1,3:1,0.000000000000,2.933185377527
10000,7,3:7,0.211274510004,2.195472574346
100000,16,3:12;4:4,0.240823996531,2.076319648690
1000000,43,3:23;4:19;5:1,0.272244742597,1.979457683111
10000000,105,3:47;4:55;5:3,0.288741328439,1.933880792918
100000000,255,3:84;4:144;5:27,0.300817522554,1.904949023962
1000000000,646,3:172;4:314;5:146;6:14,0.312248057555,1.879887651059
LARGEST_GAPS=14399256:440707345->455106601;14190750:368113411->382304161;12361020:727083001->739444021;12155808:902645857->914801665;10643160:672389641->683032801
LARGEST_RATIOS=2.339950372208:2821->6601;1.969696969697:561->1105;1.852218925573:15841->29341;1.564705882353:1105->1729;1.496551724138:10585->15841
ELAPSED_SECONDS=60.292

[d] /usr/bin/time -v measured 65.38 user CPU-seconds, 4.56 system seconds, 60.34 wall-seconds, and peak resident memory 3,910,032 KiB.

4. What exactly remains

4.1 Equivalent asymptotic formulation

[a] Since \(1\le C(x)\le x\) for all sufficiently large \(x\), the question is equivalent to

Equivalently, for every fixed \(\varepsilon>0\), one must prove

for every sufficiently large \(x\) (with the threshold allowed to depend on \(\varepsilon\)).

[a] No finite census can establish the uniform quantifiers in (4.2), and a finite low value of \(C(x)\) cannot falsify them.

4.2 The construction bottleneck

The AGP/Erdős construction chooses an \(L\), finds many primes with \(p-1\mid L\), and then finds many subsets whose prime product is \(1\bmod L\).

• [a] Once such a subset is found, its squarefree product \(n\) satisfies

\(p-1\mid L\mid n-1\) for each \(p\mid n\), so it is Carmichael by Korselt.

• [b, finite-abelian-group subset-product theorems used by AGP] If the

supply of usable primes is sufficiently large relative to the exponent of \((\mathbb Z/L\mathbb Z)^\times\), many identity-product subsets exist.

• [c] The hard part is supplying enough primes \(p\) with highly smooth

\(p-1\), in sufficiently uniform progressions and at sufficiently small size. Treating those primes as randomly distributed is exactly where the heuristic ceases to be a proof.

The accepted record quantifies the loss:

| input in the Harman/Lichtman route | accepted value | value needed asymptotically | |---|---:|---:| | shifted-prime smoothness loss \(\beta\), \(P^+(p-1)\le p^\beta\) | \(0.2844\) [b] | \(\beta=o(1)\) in a strong uniform form [c] | | companion progression exponent | \(0.4736\) [b] | arbitrarily close to \(1\) [c] | | resulting fixed power | \(0.4736(1-\beta)=0.3389\) [b] | \(1-o(1)\) |

[b, conditional] Wright proves that the single strong uniform hypothesis (0.1) is enough to reorganize this construction and reach (0.2). Therefore the precise wall is not the elementary subset-product step or verification of Korselt; it is the absent near-linear, uniform control of primes in residue classes (or an alternative theorem strong enough to replace it).

4.3 Why the present tools stop here

[a] Trial division, sieving, SAT, or a longer finite table cannot produce the quantifier “for every sufficiently large \(x\)” in (4.2). An explicit uniform construction with a proved count, or new analytic distribution theorems for shifted primes/progressions, is required.

[d, measured extrapolation] The two-array census uses about \(4N\) bytes and roughly linear CPU time. Extending the same checker from \(10^9\) to \(10^{10}\) would require about 40 GB and, from the measured run, approximately 0.18--0.25 core-hours (11--15 core-minutes). At a representative \(\$0.03\)--\(\$0.08\) per core-hour the raw CPU charge is below two cents, but the run exceeds the stipulated few-CPU-minute budget and would only reproduce known finite data, so I did not run it.

[d, published cost] Shallue--Webster report 33.1 vCPU-years for just the small-preproduct component of their \(10^{22}\) work, approximately 290,000 core-hours. At the same representative rate that component alone corresponds to roughly \(\$8,700\)--\(\$23,200\), before high-memory/storage costs and the other components. Their existing tabulation already shows why larger finite computation is not the missing asymptotic lemma.

PARTIAL: [d] Exactly 646 Carmichael numbers occur up to \(10^9\), verified by two complete kernels and independent audits; [b] the asymptotic problem remains open, with accepted exponent \(0.3389\) and a uniform near-linear least-prime-in-AP theorem as a sufficient missing input.