Erdoes #417 - working report - Erdős Problem a Day

Erdős problem #417 — wave9g

Accessed, researched, and computed on 2026-07-28. The result is PARTIAL: the existence of the requested limit is not proved, but I prove, rigorously modulo two named theorems of Ford, that

\limsup_{x\to\infty}\frac{V(x)-V'(x)}{V(x)}>0 \quad\text{and hence}\quad \limsup_{x\to\infty}\frac{V(x)}{V'(x)}>1.

Consequently, if the limit in the problem exists, it is strictly greater than $1$. I also give an elementary complete-search bound and exact values through $x=10^7$, with a standalone from-scratch verifier.

Claim labels used below:

[a] elementary-rigorous;
[b] rigorous modulo the named theorem, or a faithful report from the

cited primary/live source;

[c] plausible/structural-unverified;
[d] computational-only, but exact integer computation.

0. Mandatory live-page gate

I fetched the rendered live page, its LaTeX source, and the complete discussion thread through the Bright Data browser. This was done before any mathematical work.

[b] Live status: OPEN. Its tooltip says that it is open and cannot

be resolved by a finite computation.

[b] Claimed proofs: 0.
[b] “Currently working on this problem”: None.
[b] “Interested in collaborating”: None.
[b] There are five comments. None is registered as a proof claim.

Thus none of the mandatory stop conditions was present.

Verbatim live statement

The following is copied verbatim from the live LaTeX view:

Let \[V'(x)=\#\{\phi(m) : 1\leq m\leq x\}\] and \[V(x)=\#\{\phi(m) \leq x : 1\leq m\}.\] Does $\lim V(x)/V'(x)$ exist? Is it $>1$?

Live known result and references

The page's complete mathematical commentary is:

It is trivial that $V'(x)\leq V(x)$. In [Er98] Erdős suggests the limit may be infinite. See also [416].

The live page lists:

[Er79e]: P. Erdős, Some unconventional problems in number theory,

Astérisque 61 (1979), 73–82, MR 556666;

[ErGr80]: P. Erdős and R. Graham, *Old and new problems and results in

combinatorial number theory*, Monographies de L'Enseignement Mathématique (1980), MR 0592420;

[Er98]: P. Erdős, *Some of my new and almost new problems and results in

combinatorial number theory, Number Theory* (Eger, 1996), 169–180, MR 1628841.

The page also links $V$ to OEIS A264810 and $V'$ to A061070. The latter explicitly defines its term at $n$ as $\#\{\phi(j):1\leq j\leq n\}$, so the OEIS meanings agree with the live statement.

All five live comments

The page warns that comments are user-supplied and unverified. I therefore do not treat any of these as a theorem.

BorisAlexeev, 31 August 2025. This initially attributed the

Maier–Pomerance asymptotic to $V'$ and mistakenly interpreted $V$ as counting all arguments $m$ with $\phi(m)\leq x$. It suggested the problem was already solved.

BorisAlexeev, 29 September 2025. This retracted that interpretation:

A264810 counts distinct totient values at most $x$, whereas A070243 counts arguments $m$ with $\phi(m)\leq x$.

Thomas Bloom, 29 September 2025. Bloom confirmed that the present

$V$ agrees with problem #416 and that the estimates of Maier–Pomerance and Ford concern $V$, not the present $V'$.

TheAbandonedThinker, 11 May 2026. This introduced the useful exact

reformulation \[ E(x)=V(x)-V'(x) =\#\{v\leq x:v\in\operatorname{Im}\phi,\ M(v)>x\}, \qquad M(v)=\min\{m:\phi(m)=v\}. \] It proposed $v=2(p-1)$, $p\in(x/3,x/2)$, as candidate hidden totients. Its exclusion of odd preimages is only described as suggested by Brun-type sieve estimates, not proved. The comment also correctly notes that an $x/\log x$ lower bound for $E(x)$ is too small relative to the Maier–Pomerance factor to prove divergence.

TheAbandonedThinker, 13 May 2026. This proposed the more rigid

conditional family $p=6\ell+1$, with $p,\ell$ prime and $p\in(3x/7,x/2)$, giving $v=12\ell$. It explicitly says that the needed infinitude of such prime pairs is unproved. The inverse-tree discussion is therefore not an unconditional result, and I do not use it.

The two 2026 comments disclose AI assistance and accept responsibility for their content. Neither commenter used the live “currently working” marker.

1. Primary-source audit

Original formulations

[b] In section 9 of the scanned

Erdős–Graham monograph, the authors define $q(x)$ to count solvable totient values at most $x$ and $q'(x)$ to count distinct values among $\{\phi(m):m<x\}$. They ask whether $\lim q(x)/q'(x)$ exists and exceeds $1$. This is the present problem, up to harmless endpoint notation.

[b] Erdős's

1979 Astérisque paper asks how many new values occur among $\phi(kX+t)$, $1\leq t\leq X$, and equivalently asks for values whose smallest preimage lies in $(kX,(k+1)X)$. This is the least-preimage viewpoint used below.

[b] The Er98 chapter metadata and DOI

are verified: Paul Erdős, pages 169–180, DOI 10.1515/9783110809794.169. The full chapter is paywalled. Therefore the statement that Erdős suggested an infinite limit is recorded here only as the live page's attribution, not as a firsthand quotation from Er98.

What the classical asymptotics actually count

[b] Maier and Pomerance,

On the number of distinct values of Euler's $\phi$-function, Acta Arith. 49 (1988), 263–275, define $V(x)$ as the number of distinct totient values not exceeding $x$ and prove \[ V(x)=\frac{x}{\log x} \exp\{(C+o(1))(\log_3x)^2\}, \] with explicit $C>0$. This is the present $V$, not $V'$.

[b] Kevin Ford's

The distribution of totients, Ramanujan J. 2 (1998), 67–151, revised as arXiv:1104.3264v2 (2013), defines the same $V(x)$. Its Theorem 1 sharpens the order to \[ V(x)=\frac{x}{\log x} \exp\!\left\{ C(\log_3x-\log_4x)^2+D\log_3x -(D+\tfrac12-2C)\log_4x+O(1) \right\}. \] Ford expressly notes that this still does not give an asymptotic formula or prove $V(cx)\sim cV(x)$.

[b] The current

problem #416 page, also fetched live through Bright Data, records exactly this state: even $V(2x)/V(x)\to2$ remains open.

Search miss

Exact-expression searches for $V(x)/V'(x)$, searches using the least-preimage formulation, title/full-text searches, and inspection of the primary papers above found no later primary source settling #417. An OpenAlex query for works citing Er98 returned 15 records, none with a totient-related title. This is an honest search miss, not a proof that no uncatalogued or differently worded result exists.

The directly relevant result that the live page does not mention is Ford's Theorem 8 about totients all of whose preimages are divisible by a fixed integer. It yields the partial theorem below.

2. Exact least-preimage reformulation

Let

\mathcal T=\operatorname{Im}\phi,\qquad M(v)=\min\{n\geq1:\phi(n)=v\}\quad(v\in\mathcal T),

and put $E(x)=V(x)-V'(x)$.

[a] Since $\phi(n)\leq n$, every value counted by $V'(x)$ is at most $x$, and

V'(x)=\#\{v\in\mathcal T:v\leq x,\ M(v)\leq x\}.

Consequently

E(x)=\#\{v\in\mathcal T:v\leq x<M(v)\}. \tag{2.1}

This is the exact object that must be controlled; multiplicities by themselves are not enough.

3. A positive limsup gap from Ford

3.1 A finite seed, independently checked

Ford defines $V(x;k)$ to count totients at most $x$ all of whose preimages are divisible by $k$. His Theorem 8 says:

If a fixed totient $d$ has every preimage divisible by $k$, then $V(x;k)\gg_{\epsilon}d^{-1-\epsilon}V(x)$ for sufficiently large $x$.

On page 39 of the revised paper, Ford gives

d=2^{18}\cdot257=67\,371\,008

for $k=2,4,8$.

[a,d] The checker independently enumerates every inverse totient of $d$, rather than trusting the list. The complete list is

\begin{split} \phi^{-1}(d)=\{& 135268352,\ 143722624,\ 169085440,\ 179653280,\\ &202902528,\ 215583936,\ 253628160,\ 269479920\}. \end{split}

Every member is in fact divisible by $16$.

Completeness of this enumeration is elementary. If $p^a\Vert n$ and $\phi(n)=d$, then

\phi(p^a)=p^{a-1}(p-1)\mid d.

Thus $p-1\mid d$; every candidate prime is one plus a divisor of $d$. The checker generates every such prime, every allowed exponent, and every compatible product whose totient components multiply to $d$. It verifies the resulting list directly. The same inverse enumerator is cross-checked against a complete brute-force sieve for every target at most $200$.

Let

W(x)=\#\{v\in\mathcal T:v\leq x,\ \text{every preimage of \(v\) is even}\}.

Ford's Theorem 8 and the checked seed give constants $c_0>0$, $x_0$ such that

W(x)\geq c_0V(x)\qquad(x\geq x_0). \tag{3.1}

This use of Ford is [b].

3.2 Dyadic growth

Ford's Theorem 4 implies, in particular, that for every fixed $c>1$,

V(cx)-V(x)\asymp_c V(x).

Taking $c=2$, or taking $y=x$ in the theorem's short-interval form, gives constants $q<1$, $x_1$ such that

V(t/2)\leq qV(t)\qquad(t\geq x_1). \tag{3.2}

This step is [b], rigorous modulo Ford's Theorem 4.

3.3 The telescoping argument

[a] If $v$ is counted by $W(t)-W(t/2)$, then $t/2<v\leq t$ and every preimage $n$ of $v$ is even. For even $n$,

\phi(n)\leq n/2,

so $n\geq2v>t$. Hence $v$ is hidden at threshold $t$, and

W(t)-W(t/2)\leq E(t). \tag{3.3}

Now let

L=\limsup_{t\to\infty}\frac{E(t)}{V(t)}.

For any $\epsilon>0$, sufficiently large $t$ satisfies

E(t)\leq(L+\epsilon)V(t).

Telescoping $W$ down the dyadic scales and using (3.2) and (3.3) gives

\begin{split} W(x) &=O(1)+\sum_{j\geq0} \left(W(x/2^j)-W(x/2^{j+1})\right)\\ &\leq O(1)+(L+\epsilon)\sum_{j\geq0}V(x/2^j)\\ &\leq O(1)+\frac{L+\epsilon}{1-q}V(x). \end{split}

Combining this with (3.1), dividing by $V(x)$, and then letting $\epsilon\to0$, yields

L\geq c_0(1-q)>0. \tag{3.4}

Therefore:

Proposition [b].

\boxed{\displaystyle \limsup_{x\to\infty}\frac{V(x)-V'(x)}{V(x)}>0 }

and consequently

\boxed{\displaystyle \limsup_{x\to\infty}\frac{V(x)}{V'(x)}>1. }

In particular, if $\lim V(x)/V'(x)$ exists (as a finite or extended limit), it is $>1$. This answers the second question conditional only on the existence asked in the first; it does not prove existence.

4. Elementary certificate for exact finite computation

Let $p_1=2,p_2=3,\ldots$ be the primes, and define

A_k=\prod_{i=1}^k(p_i-1),\qquad K(x)=\max\{k:A_k\leq x\},\qquad R(x)=\prod_{i=1}^{K(x)}\frac{p_i}{p_i-1}.

Capture lemma [a]. If $\phi(n)\leq x$, then

n\leq xR(x). \tag{4.1}

Proof. Let $q_1<\cdots<q_r$ be the distinct prime divisors of $n$. Then

\phi(\operatorname{rad}n)=\prod_{i=1}^r(q_i-1)

divides $\phi(n)$, so it is at most $x$. Since $q_i\geq p_i$,

\prod_{i=1}^r(p_i-1)\leq\prod_{i=1}^r(q_i-1)\leq x,

hence $r\leq K(x)$. The function $p/(p-1)$ decreases with $p$, so

\frac n{\phi(n)} =\prod_{i=1}^r\frac{q_i}{q_i-1} \leq\prod_{i=1}^{K(x)}\frac{p_i}{p_i-1}=R(x).

Multiplying by $\phi(n)\leq x$ proves (4.1). $\square$

At $x=10^7$,

K=8,\quad (p_1,\ldots,p_8)=(2,3,5,7,11,13,17,19),

R=\frac{9699690}{1658880}, \qquad \left\lfloor10^7R\right\rfloor=58\,471\,317.

Thus sieving $\phi(n)$ only through $58\,471\,317$ provably captures every totient value at most $10^7$; there is no heuristic truncation.

5. Exact computation

The standalone checker is runs/erdos417_wave9g_verify.py. Run it from the repository root with:

python3 runs/erdos417_wave9g_verify.py

It uses only the Python standard library and performs the following:

computes the certified cutoff (4.1);
sieves $\phi(n)$ from its prime-product formula;
records the least preimage $M(v)$ and whether $v$ has an odd

preimage;

computes $V(x)$, $V'(x)$, $E(x)$, and exact interval extrema;
checks sieve values against the literal coprimality definition of

$\phi$ through $n=500$;

checks the recursive inverse-totient algorithm against brute force for

all targets through $200$;

independently checks all eight preimages of Ford's seed;
asserts a hard-coded regression table and exact rational extrema.

The final regression run took 85.279 CPU seconds and 305,460 KiB peak resident memory on this VM. Its seed-list SHA-256 certificate is 3f7974387336f3f6ada389732b7b8d25afbd5c111584451675f95bd416ce0bdc.

Verified table

All rows are [a,d]: computational integer equalities made exhaustive by the capture lemma.

| $x$ | $V(x)$ | $V'(x)$ | $E(x)$ | $V(x)/V'(x)$ | |---:|---:|---:|---:|---:| | 1 | 1 | 1 | 0 | $1$ | | 2 | 2 | 1 | 1 | $2$ | | 3 | 2 | 2 | 0 | $1$ | | 10 | 6 | 4 | 2 | $3/2$ | | 100 | 38 | 34 | 4 | $19/17$ | | 1,000 | 291 | 264 | 27 | $97/88$ | | 10,000 | 2,374 | 2,160 | 214 | $1187/1080$ | | 100,000 | 20,254 | 18,412 | 1,842 | $10127/9206$ | | 1,000,000 | 180,184 | 163,861 | 16,323 | $180184/163861$ | | 5,000,000 | 840,178 | 763,727 | 76,451 | $840178/763727$ | | 10,000,000 | 1,634,372 | 1,485,793 | 148,579 | $1634372/1485793$ |

Ford's published table gives

V(10^6)=180184,\quad V(5\cdot10^6)=840178,\quad V(10^7)=1634372,

exactly matching the independently generated $V$-column.

The ratio at $10^7$ is approximately $1.099999798088$. This striking proximity to $11/10$ is only numerical; it is not promoted to a conjecture or theorem.

Sharp finite-regime bound

For every integer $x$ with $10^6\leq x\leq10^7$, the exhaustive run proves the sharp bounds

\boxed{ \frac{191304}{174077} \leq \frac{V(x)}{V'(x)} \leq \frac{160981}{146316} }.

The lower equality occurs at $x=1\,065\,149$, and the upper equality at $x=1\,836\,360$. Numerically this is

1.098961953618\ldots\leq V(x)/V'(x) \leq1.100228273053\ldots.

The checker also proves that every totient $v\leq10^7$ has an odd preimage. Thus Ford's all-even class has not yet appeared in this finite range; the asymptotic argument in section 3 is not an extrapolation from the displayed data.

6. Exact remaining wall

The limsup proposition does not control every scale. Ford's Theorem 8 is a cumulative positive-proportion result, and dyadic telescoping only forces large hidden proportions along some unbounded sequence of scales. It gives neither a matching liminf nor convergence.

A precise formulation of what remains is available. Define the probability measure

\mu_x=\frac1{V(x)} \sum_{\substack{v\in\mathcal T\\v\leq x}} \delta_{\left(v/x,\ M(v)/v\right)}

on $(0,1]\times[1,\infty)$. Then [a]

\frac{V'(x)}{V(x)} =\mu_x\{(u,r):ur\leq1\}. \tag{6.1}

The first marginal already contains problem #416:

\mu_x\big((0,t]\times[1,\infty)\big) =\frac{V(tx)}{V(x)}\qquad(0<t\leq1). \tag{6.2}

Thus one sufficient missing theorem is:

Prove weak convergence (with suitable tightness) of the joint measures $\mu_x$, and prove that the limiting measure assigns zero mass to the boundary $ur=1$.

Equation (6.1) would then give the limit in #417. But even convergence of the first marginal in (6.2), which would include $V(2x)/V(x)\to2$, is still open in #416. Moreover, #417 needs the joint distribution of value size and least-preimage ratio; solving #416 alone would not supply that.

This names the exact analytic obstruction. Maier–Pomerance and Ford count totients and describe prime-factor structures of typical preimages, but do not give a limiting law for the least preimage $M(v)$ at multiplicative scale. The suggested $x/\log x$ sieve families in the live comments are also too sparse compared with

V(x)=\frac{x}{\log x}\exp\{(C+o(1))(\log_3x)^2\}.

More finite computation cannot repair this uniformity gap. For perspective, the same elementary certificate at $x=10^8$ requires sieving through $611\,291\,051$. A direct implementation needs roughly 3 GiB including least-preimage arrays; extrapolating the measured Python run gives about 0.25 core-hour, while an optimized C++ implementation should take a small fraction of that. I did not run it because it would not address (6.1)–(6.2) and exceeds the requested few-CPU-minute scope.

PARTIAL: Rigorous modulo Ford (1998/2013), the ratio has limsup strictly above 1, so any existing limit is >1; existence remains open, with exact certified data through $x=10^7$.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger