Distribution of Euler-totient values: does $V(2x)/V(x)\to 2$, with an asymptotic for $V(x)$? (Erdős #416)
Statement
Let $V(x)$ denote the number of integers $n\leq x$ that lie in the image of Euler's totient function $\phi$ — that is, the count of distinct values $n\leq x$ for which $\phi(m)=n$ has a solution. Two questions: does the ratio $V(2x)/V(x)$ tend to $2$ as $x\to\infty$, and is there an asymptotic formula for $V(x)$?
Acceptance. FULLY RESOLVES: a proof establishing a genuine asymptotic formula $V(x)\sim g(x)$ for an explicit elementary function $g$ (thereby determining $\lim V(2x)/V(x)$), OR a proof deciding whether $V(2x)/V(x)\to 2$ (giving the limit value, or proving the limit does not exist). A complete written proof or a machine-checkable proof. ADVANCES: (a) an unconditional refinement of Ford's bracketing that narrows the bounded oscillation factor toward an asymptotic — strictly sharper than the Ford form stated in the background, with proof; (b) a rigorous resolution of the ratio question conditional on a clearly-stated hypothesis; (c) a large-scale computation of $V(x)$ over an extended range (extending OEIS A264810), delivered with the sieve code and a convincing empirical determination of $V(2x)/V(x)$, explicitly labelled as evidence rather than proof. Deliver the proof file, or the computation plus code.
Background
Erdős's problem on the range of Euler's function; sources [Er74b], [Er79e], [ErGr80], [Er98]; listed as open on erdosproblems.com/416 (fetched 2026-07-13, status 'open', tagged 'number theory'), formalised in the google-deepmind/formal-conjectures Lean repository, related OEIS sequence A264810. Frontier: Pillai [Pi29] first showed $V(x)=o(x)$; Erdős [Er35b] proved $V(x)=x(\log x)^{-1+o(1)}$; Maier and Pomerance [MaPo88] sharpened this to $V(x)=\frac{x}{\log x}\exp\!\big((C+o(1))(\log\log\log x)^2\big)$ for an explicit constant $C>0$; and Ford [Fo98] obtained the essentially definitive $V(x)\asymp \frac{x}{\log x}\exp\!\big(C_1(\log\log\log x-\log\log\log\log x)^2+C_2\log\log\log x-C_3\log\log\log\log x\big)$ for explicit $C_1,C_2,C_3>0$. This pins $V(x)$ down to a bounded factor but falls just short of a genuine asymptotic formula, and in particular does not settle whether $V(2x)/V(x)\to 2$. Erdős [Er79e] asked further to estimate how many $n\leq x$ have their least totient preimage $m$ in a range $kx<m\leq(k+1)x$. The problem is B36 in Guy's Unsolved Problems in Number Theory [Gu04]; its companion is the sibling problem erdosproblems.com/417 (comparing two conventions for counting totient values), also written up in this batch, and it is related to erdosproblems.com/821. No cash prize is attached. The attacker's tool: the analytic frontier requires the Maier–Pomerance/Ford machinery (the anatomy of shifted primes $p-1$, Bombieri–Vinogradov-type inputs) pushed to a true asymptotic; computationally, sieve the totient image and tabulate $V(x)$ (extending A264810) over a large range to test the constant-2 ratio empirically.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #416 (T. F. Bloom) | website |
| REF-02 | OEIS A264810 — number of distinct values of Euler's totient function not exceeding n | website |
| REF-03 | Formalised statement of Erdős #416 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.