The Erdős–Hall question on totient values
From OpenAI Aftermath
Let V(x) count the distinct values of Euler's totient function φ up to x. Erdős and Hall asked whether V(2x)/V(x) → 2 (Erdős problem 416), and Erdős asked whether V(x) has an asymptotic formula. A manuscript dated 25 September 2026 in OpenAI's public mathematics collection (github.com/openai/math) claims an explicit asymptotic equivalent and V(cx)/V(x) → c for every fixed c > 0, with a Lean formalization of the main statements. This page summarizes the published claim and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper, code or a formal proof is not presented here as independent verification.
Background
- As recounted in the introduction of the manuscript:
- Pillai proved that totient values have density zero; Erdős, Erdős and Hall, and Pomerance sharpened the bounds, and Maier and Pomerance determined the leading constant in the exponent. Ford refined this in 1998 to an estimate with bounded multiplicative uncertainty and described the typical prime factorizations of preimages.
- Erdős and Hall asked whether V(cx)/V(x) → c, and Erdős repeated the question. Ford proved that V(cx) − V(x) is of the order of V(x) for fixed c > 1, which does not determine the limiting ratio.
The original result
- Claim. An asymptotic formula for the number of totients gives an asymptotic equivalent for V(x) whose coefficient is a bounded, phase-dependent uniform limit of functions defined from finite arithmetic data, and proves V(cx)/V(x) → c for every fixed c > 0. A companion statement gives asymptotics for the totients v ≤ x whose least preimage lies between kx and (k + 1)x; the coefficient is positive under a stated existence condition, vanishes identically when no totient d has least preimage above kd, and is positive for k = 1, 2.
- Method, as described: starting from Ford's normal structure of preimages, the large prime factors are counted by volume in a simplex while the shorter arithmetic tails are kept exactly, and inclusion–exclusion over the finitely many tails that can give the same value produces the coefficient; quantitative control of all collisions between ordered prefixes converts the volume into a count of distinct values.
- Sources. The manuscript An asymptotic formula for the number of totients at commit
1581d4c. - Formalization, as described by the repository. The scope note states that the formalization constructs the explicit positive main term from finite arithmetic approximants and proves that their ratio tends to one, so that V(cx)/V(x) → c for every fixed c > 0, and gives the companion least-preimage asymptotics with the exact zero case. The Comparator statements are
TotientAsymptotic.leanandTotientCompanionZero.lean.
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 21 October 2026) |
|---|---|---|---|---|
| 2026-09-14 (verified; certified 16 September 2026) | Conjectures.io record for Erdős problem 416, part (i) (solver account JenW1N) | Prior (doubling limit) | A Lean proof that V(2x)/V(x) → 2, the first question of problem 416; the record states that it does not settle every part of the problem. The plasma-ai/erdos wiki attributes the accompanying write-up to L. Kruer and J. Kohlmeyer. | Bounty-platform record: Lean verification passed and review approved. |
| 2026-10-08 | MathVet (GitHub; review of openai/math, tables at repository commit c76f1e4, 14 October 2026) |
Review (fidelity of the formal statement) | Rates the family "full": the headline V(cx)/V(x) → c is stated in terms of V alone, while the explicit main term rests on a large custom apparatus that cannot be checked against a standard object from the statement; records sandboxed Comparator passes for TotientAsymptotic and TotientCompanionZero. |
MathVet states that it does not claim any theorem false and reports what was machine-checked as stated. |
| 2026-10-08 | T. F. Bloom, Erdős problems in the OpenAI proofs (blog post on erdosproblems.com) | Catalogue (remark) | Lists the claim for problem 416, notes that its proof has been formalised and that it appears to use many of the same techniques used by Ford and others in their investigations of V(x). | Blog post; the author states that he had not yet examined the proofs or checked the Lean files and that the post is not an endorsement. |
| 2026-10-10 | cert-machine, openai/math lane K: runs 38040214623 and 38051470892 | Verification (two kernels) | Records that Lean's default kernel and the nanoda kernel accept the TotientCompanionZero solution, in 1,932 s, and the TotientAsymptotic solution, in 2,139 s. |
Repository. |
| 2026-10-10 | LeanMeanBean/417 (GitHub, commit 3620821), An explicit bound for Erdős problem 417 |
Use (conditional) | Using the manuscript's results on V and on least preimages, proves lim sup V(x)/V′(x) < 2.195202, where V′(x) counts the distinct values φ(m) with m ≤ x; convergence of the ratio, asked in Erdős problem 417, is left open. | Two-page note, not refereed; announced in a comment on the blog post above, which states that the write-up was originally generated by AI and then edited by its author. |
| 2026-10-10 to 2026-10-14 | con-leche development journal (task #348) | Verification (second kernel) | In its run over all Comparator challenges of the collection at commit fd4aeeb, the journal's table of exceptions (time-outs, memory, errors) lists neither TotientAsymptotic nor TotientCompanionZero, so both were accepted by con-leche and by Lean's official kernel. |
Development journal. |
| 2026-10-16 | J. Jardine, Lattice24, referee review rank_093 in JJardine919/openai-math-audit (archived at Zenodo 10.5281/zenodo.23422995) | Review (AI-assisted audit) | Reports no gap. Its minor note says that the coverage step rests on the manuscript's transcription of Ford's Theorems 10 and 16, including specific slack factors, which the reviewer could not check against Ford's revised version; a different form would change constants but not the structure of the argument. | Part of an audit that the audit describes as complete. The reviews are published under CC BY 4.0. |
| 2026-10-16 (page last edited) | erdosproblems.com problem 416 (T. F. Bloom) | Catalogue | States that a formalised proof that V(cx)/V(x) → c for every fixed c > 0 is available, linking the collection's Lean statement. | Problem database entry. |
| 2026-10-19 | plasma-ai/erdos wiki, problems 416 and 417 (GitHub, commit bdb2d5d) |
Catalogue (conditional deductions) | Records the doubling limit as proved twice in Lean and the asymptotic formula as a pending claim for problem 416; for problem 417 records deductions conditional on the manuscript, including a reduction of the existence of lim V/V′ to a phase condition on the coefficients, and keeps the problem open. | Wiki maintained by Plasma AI; the deductions are labelled by tier and conditional on the unrefereed manuscript. |
Notes
- The earlier results are due to the authors named in the Background section, as recounted by the manuscript.
- The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.
