Are there infinitely many n whose totient valence g(n)=#{m:φ(m)=n} exceeds n^{1−ε}? (Erdős #821)
Statement
For a positive integer $n$, let $g(n)$ denote the number of solutions $m$ to $\phi(m)=n$, where $\phi$ is Euler's totient function; thus $g(n)$ is the multiplicity (valence) of $n$ as a totient value, and $g(n)=0$ precisely when $n$ is a nontotient. Is it true that for every $\epsilon>0$ there exist infinitely many $n$ such that $$g(n) > n^{1-\epsilon}?$$
Acceptance. This is an OPEN, proof-shaped asymptotic problem. FULLY RESOLVES: a complete proof — machine-checkable (Lean/Coq; a formal statement already exists in the formal-conjectures repo) preferred, otherwise a full written proof — that for every $\epsilon>0$ there are infinitely many $n$ with $g(n)>n^{1-\epsilon}$; or a disproof, i.e. a proof that for some $\epsilon>0$ only finitely many $n$ satisfy $g(n)>n^{1-\epsilon}$. ADVANCES: prove that $g(n)>n^{\alpha}$ for infinitely many $n$ for some constant $\alpha$ strictly larger than the best value stated in the background (Lichtman's $0.71568\cdots$), with proof; equivalently, strictly improve the underlying count of primes $p\leq x$ with $p-1$ suitably smooth that drives that exponent. A tabulation of large-valence $n$ is a supporting certificate but cannot close the asymptotic question. Deliver the proof, or the improved-exponent result together with its proof.
Background
Posed by Erdős [Er35b, Er74b]; listed as open on erdosproblems.com/821 (fetched 2026-07-21, status 'open'), with a Lean formalisation in DeepMind's formal-conjectures repository. History and frontier: Pillai proved $\limsup_n g(n)=\infty$; Erdős [Er35b] proved $g(n)>n^{c}$ for infinitely many $n$ for some constant $c>0$. The current record is $g(n)>n^{0.71568\cdots}$ for infinitely many $n$, due to Lichtman [Li22], obtained as a consequence of showing there are $\geq x/(\log x)^{O(1)}$ primes $p\leq x$ all of whose prime factors of $p-1$ are $\leq x^{0.2843\cdots}$ (improving earlier exponents, most recently Baker–Harman [BaHa98]). The full conjecture (exponent tending to $1$) would follow from knowing that for every $\epsilon>0$ there are $\gg_\epsilon x/\log x$ primes $p<x$ with all prime factors of $p-1$ below $p^\epsilon$. Luca and Pollack [LuPo11] studied the average size of $g(n)$. Related: Erdős #416; OEIS A014197 tabulates $g(n)$. Attacker's tool: analytic number theory on the count of primes $p$ with $p-1$ smooth (the engine behind Lichtman's exponent); computationally one can tabulate $g(n)$ via A014197 and hunt for $n$ of unusually large valence to probe the exponent empirically.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #821 (T. F. Bloom) | website |
| REF-02 | OEIS A014197 — number of m with Euler phi(m)=n | website |
| REF-03 | Lean formalisation of Erdős #821 (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.