Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. Let V(x)V(x) be the number of distinct values of Euler's function in [1,x][1,x]. The last clause of Theorem 2.1 of OpenAI, An asymptotic formula for the number of totients, OpenAI Math Release preprint, 25 September 2026 (the preprint link, at the pinned revision of the release repository; the manuscript's author line is "OpenAI", and the release README says the manuscripts were produced by an internal OpenAI model and stand at different stages of verification, not all with Lean formalizations), states that for every fixed real c>0c>0

V(cx)V(x)⟶c(x→∞).\frac{V(cx)}{V(x)}\longrightarrow c\qquad(x\to\infty).

At c=2c=2 this is the first question of Problem 416, answered yes; the theorem covers every positive scale, which is the regular-variation question Erdős and Hall posed beside the problem and Erdős repeated in 1979. The manuscript is carded at its intake card, whose Theorem 2.1 page transcribes the statement. The same theorem's other clauses, an asymptotic equivalent V(x)∼(x/log⁡x) GmA(1;θ)V(x)\sim(x/\log x)\,G_mA(1;\theta) with an explicitly constructed coefficient, are the subject of the separate pending full claim on the second question; this page records only the fixed-scale limit. The proof orders the prime factors of a typical preimage from the largest down, counts a long prefix of them by the volume of a simplex that Ford's normal-structure theorems describe, retains a short arithmetic tail exactly, and controls collisions between prefixes by Maier and Pomerance's layered shifted-prime method in Ford's form; the fixed-scale limit comes from comparing one representation count at the two endpoints xx and cxcx with common parameters, before the arithmetic limit is identified.

Covers. First question only: V(cx)/V(x)→cV(cx)/V(x)\to c for every fixed c>0c>0, so V(2x)/V(x)→2V(2x)/V(x)\to2. The second question stays claimed: whether the manuscript's equivalent is a formula in elementary functions is unsettled, and that claim has its own pending page.

Formalization. The release's Lean tree (folder lean/ at the pinned revision, with the release's pinned Lean and Mathlib) proves OAI.TotientAsymptotic.totient_asymptotic_formula in OAI/NumberTheory/TotientAsymptotic/UnconditionalMain.lean, a conjunction whose fourth conjunct is

lean
∀ c : ℝ, 0 < c → Tendsto (fun x => V (c*x)/V x) atTop (nhds c)

with, in the comparator challenge ComparatorChallenges/TotientAsymptotic.lean,

lean
def IsTotient (v : ℕ) : Prop := ∃ n : ℕ, 0 < n ∧ n.totient = v

def V (x : ℝ) : ℝ := by
  classical
  exact (((Finset.Icc 1 ⌊x⌋₊).filter IsTotient).card : ℝ)

The challenge's configuration TotientAsymptotic.json pins the declaration, with the three companion theorems of the family, permits only the axioms propext, Quot.sound and Classical.choice, and lists no definitions; the release's family note lean/docs/024.md names it as the comparator for the totient-count asymptotics and regular variation. The declaration has no hypotheses, and its VV is the site's count clause for clause: values nn with 1≤n≤⌊x⌋1\le n\le\lfloor x\rfloor, each counted once, and the condition 0<n0<n on the preimage excluding only the value 00. Real x→∞x\to\infty implies the integer version, and V(x)>0V(x)>0 for large xx keeps the quotient meaningful. The external imports are three modules of PrimeNumberTheoremAnd at a pinned commit, patched in the release to remove two unused sorried lemmas.

Depends on. Nothing in this wiki: the proof is self-contained in the manuscript and its Lean tree.

Acceptance. Formalized: this corpus's verification built the solution module and the comparator challenge from the release at the pinned revision, printed the axioms of totient_asymptotic_formula, which were exactly propext, Classical.choice and Quot.sound, and found the comparator fingerprint of the pinned challenge statement identical to the solution's; the result was recorded on 2026-10-07. The statement audit that formalized requires is this corpus's own, of 2026-10-07: it unfolded IsTotient and V, compared the fourth conjunct with the problem page's Statement (the counting function, the scale 22, the direction of the limit, the quantifier over real xx) and judged that it answers the first question yes, with every c>0c>0 as a stronger range. Not reviewed: no outside reviewer, referee or acceptance by the site is recorded; the site labels the problem OPEN and its proof-claims thread does not list the release. Not refereed: the manuscript is an unrefereed release preprint with no arXiv version, attributed by the release to an internal model. An earlier independent formal proof of the c=2c=2 case is the Conjectures.io record, by a different method.