Two ways to count Euler-totient values: does $V(x)/V'(x)$ converge, and does it exceed 1? (Erdős #417)
Statement
Define two counting functions for the values of Euler's totient function $\phi$: $$V'(x)=\#\{\phi(m) : 1\leq m\leq x\}\qquad\text{and}\qquad V(x)=\#\{\phi(m)\leq x : 1\leq m\},$$ so $V'(x)$ counts the distinct totient values produced by inputs $m\leq x$, while $V(x)$ counts the distinct totient values that are themselves $\leq x$ (over all inputs $m$). Since $\phi(m)\leq m$, every value counted by $V'(x)$ is $\leq x$ and hence also counted by $V(x)$, so trivially $V'(x)\leq V(x)$. Does the limit $\lim_{x\to\infty} V(x)/V'(x)$ exist, and if so is it $>1$?
Acceptance. FULLY RESOLVES: a proof determining whether $\lim_{x\to\infty}V(x)/V'(x)$ exists and, if it does, its value (in particular whether it exceeds $1$), or a proof that the ratio $\to\infty$ as Erdős suspected; written in full or as a machine-checkable proof. ADVANCES: (a) rigorous bounds separating the two counts — e.g. an unconditional proof that $\liminf V(x)/V'(x)>1$, or that $\limsup=\infty$, or any proven monotonicity/growth statement about the ratio; (b) a large-scale sieve computation of $V(x)$ and $V'(x)$ (extending A264810 and A061070) over a substantially larger range than currently tabulated, delivered with the code and a clear empirical picture of the ratio's trend, labelled as evidence. Deliver the proof file, or the computation plus code.
Background
Erdős's problem; sources [Er79e], [ErGr80], [Er98]; listed as open on erdosproblems.com/417 (fetched 2026-07-13, status 'open', tagged 'number theory'), formalised in the google-deepmind/formal-conjectures Lean repository, related OEIS sequences A264810 and A061070. The two functions differ because a small totient value $\leq x$ can require a large preimage $m>x$: $V(x)$ credits such a value while $V'(x)$, which only inspects inputs up to $x$, misses it, so the ratio $V(x)/V'(x)$ measures how much the totient image 'reaches back' from large inputs to small values. In [Er98] Erdős suggests the ratio may in fact tend to infinity. This is the companion of the neighbouring problem erdosproblems.com/416 (the asymptotics of $V(x)$ and the ratio $V(2x)/V(x)$), also written up in this batch; both rest on the deep understanding of the totient image due to Erdős, Maier–Pomerance, and Ford [Fo98]. No cash prize is attached. The attacker's tool: sieve the totient function to compute $V(x)$ and $V'(x)$ over a large range (extending OEIS A264810 and A061070) and track the ratio to gather evidence on convergence versus divergence; the proof frontier needs the analytic anatomy of totient values, in particular controlling those values whose only preimages are large.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #417 (T. F. Bloom) | website |
| REF-02 | OEIS A264810 — number of distinct values of Euler's totient function not exceeding n | website |
| REF-03 | OEIS A061070 — sequence related to counting values of Euler's totient function (Erdős #417) | website |
| REF-04 | Formalised statement of Erdős #417 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.