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

Erdős problem 416, wave 9g

Access and re-verification date: 2026-07-28 UTC.

0. Mandatory live-page gate

(b) Source-verified. I fetched both https://www.erdosproblems.com/416 and its LaTeX view https://www.erdosproblems.com/latex/416 through the Bright Data cloud browser. I did not infer the problem from the stale tracker metadata.

The current statement, copied verbatim from the live page's LaTeX view, is:

Let $V(x)$ count the number of $n\leq x$ such that $\phi(m)=n$ is solvable. Does $V(2x)/V(x)\to 2$? Is there an asymptotic formula for $V(x)$?

(b) Source-verified. The stop gate did not fire:

Status: OPEN.
Comments: 0 comments on this problem.
Claimed proofs: 0 claimed proofs for this problem.
Interested in collaborating: None.
Currently working on this problem: None.
Likes this problem: None.
This problem looks difficult: None.
This problem looks tractable: None.
The results on this problem could be formalisable: None.
I am working on formalising the results on this problem: None.
Formalised statement?: Yes.
Related OEIS sequence: A264810.
The page says it was last edited 30 September 2025.

All known-result material listed on the live page

(b) Source-verified page record. The page reports:

Pillai [Pi29] proved $V(x)=o(x)$.
Erdős [Er35b] proved

$V(x)=x(\log x)^{-1+o(1)}$.

Maier and Pomerance [MaPo88] proved

\[ V(x)=\frac{x}{\log x} \exp\!\left((C+o(1))(\log\log\log x)^2\right) \] for an explicit $C>0$.

Ford [Fo98] determined the order more precisely:

\[ V(x)\asymp\frac{x}{\log x} \exp\!\left( C_1(\log_3x-\log_4x)^2+ C_2\log_3x-C_3\log_4x\right), \] with explicit positive constants. The page explicitly says this still falls short of both an asymptotic formula and the dyadic limit.

Erdős [Er79e] also asked for the number of $n\leq x$ whose smallest

preimage under $\phi$ lies in $kx<m\leq(k+1)x$.

The page points to Problems 417 and 821 and to Guy's Problem B36.

There are no comments or claimed proofs whose contents need separate assessment.

1. Claim labels

(a) elementary-rigorous: proved here from definitions.
(b) rigorous-modulo-named-theorem/source: either source metadata or a

deduction whose only non-elementary input is the explicitly named theorem.

(c) plausible/structural-unverified: a literature-search miss,

interpretation, or resource estimate; never used as a theorem.

(d) computational-only: an exact finite computation reproduced by the

standalone checker; never promoted to an assertion about the limit.

2. Primary-source and literature audit

Original question

(b) In P. Erdős, Some unconventional problems in number theory, Astérisque 61 (1979), 73--82, NUMDAM primary scan, printed p.79, Erdős defines the number of integers below $X$ that are values of $\phi$, says a genuine asymptotic is uncertain, and asks whether $V(CX)/V(X)\to C$ for every fixed $C>0$. Thus the live page's $C=2$ question is a literal special case of the primary formulation. The scan also contains the further least-preimage question quoted by the live page. Local download SHA-256: 50102c8dd9107825383da9162ed9de4aeeb01aefa40ee8e4084f11e5a0686a9a.

Maier--Pomerance

(b) H. Maier and C. Pomerance, On the number of distinct values of Euler's $\phi$-function, Acta Arith. 49 (1988), 263--275, DOI 10.4064/aa-49-3-263-275. The publisher record confirms the authors, volume, year, pages, and a free primary PDF. Ford's introduction states their theorem in exactly the form recorded by the live page. Local PDF SHA-256: db37b8dc82551890b5dcd6b9b56e17979ef7b8796a63650ec24eac79e32d5c37.

Ford's strongest general result found

(b) K. Ford, The distribution of totients, Ramanujan J. 2 (1998), 67--151. I used the author's corrected and streamlined 2013 version, arXiv:1104.3264v2 and author PDF. The arXiv record explicitly identifies it as an updated version of the 1998 article and records the corrections. Local author-PDF SHA-256: 7b9640bdc81f4306b6b894a677f77bb7d9e3caa17cf148c5790898b09a7a81d0.

Ford's Theorem 1 is

V(x)=F_0(x)e^{O(1)}, \tag{2.1}

where

F_0(x)=\frac{x}{\log x} \exp\!\left\{ C(\log_3x-\log_4x)^2+D\log_3x -(D+\tfrac12-2C)\log_4x \right\}, \tag{2.2}

C=0.817814646400836\ldots,\qquad D=2.176968743559410\ldots .

This verifies the live page's $\asymp$-formula and makes its constants explicit.

(b), important result omitted from the short live-page summary. Ford's Theorem 4 gives short-interval bounds and the explicit consequence

V(cx)-V(x)\asymp_c V(x)\qquad(c>1\text{ fixed}). \tag{2.3}

Immediately after this, Ford writes that Erdős's desired $V(cx)\sim cV(x)$ remains beyond the method. Thus even the strongest directly relevant primary source located does not claim the desired limit.

Later directly adjacent work

(b) A. Contiero and D. Lima, 2-Adic Stratification of Totients, arXiv:2005.05475, studies the subsets of totients with fixed $2$-adic valuation. It proves, in particular, an asymptotic for the first fixed stratum and explicitly cites Ford for the global order of $V(x)$. It does not provide the uniform control over growing strata needed to sum to a global asymptotic. Local PDF SHA-256: 97c3159af7cae7ba3a90e76501a0c016d8a1b3fd5bf8144e0dd288fc7fac303e.

(c) Literature-search miss, not a theorem. I searched the exact phrases “$V(2x)/V(x)$” and “asymptotic formula for $V(x)$,” the title and DOI of Ford's paper, its forward-citation list, recent arXiv full text, and papers on distinct totients and 2-adic strata. I inspected recent candidates rather than inferring relevance from titles. I found work on fixed strata, totient multiplicities, gaps, residue classes, and the different function $\#\{\phi(n):n\leq x\}$, but no later primary source proving $V(cx)\sim cV(x)$, an asymptotic for $V(x)$, or a counterexample. This is an honest search result, not a proof that no such paper exists.

3. An exact primitive-totient reduction

Let

\mathcal T=\{\phi(m):m\geq1\}

be the set of totient values.

Lemma 1: closure under doubling — (a)

If $t=\phi(m)$, then $2t\in\mathcal T$. If $m$ is even, $\phi(2m)=2\phi(m)$. If $m$ is odd, multiplicativity gives $\phi(4m)=\phi(4)\phi(m)=2\phi(m)$.

Call $t\in\mathcal T$ primitive when $t/2\notin\mathcal T$, with a noninteger $t/2$ automatically outside $\mathcal T$. Write

\mathcal P=\{t\in\mathcal T:t/2\notin\mathcal T\},\qquad P(x)=|\mathcal P\cap[1,x]|.

Lemma 2: unique dyadic chains — (a)

There is a disjoint decomposition

\mathcal T=\bigsqcup_{j\geq0}2^j\mathcal P. \tag{3.1}

Indeed, repeatedly halve $t\in\mathcal T$ for as long as the result is still a totient. The process terminates and gives a unique primitive root. Lemma 1 supplies every forward double, and uniqueness follows by cancelling the smaller power of $2$.

Consequently, for every real $x\geq1$,

V(x)=\sum_{j\geq0}P(x/2^j),\qquad P(x)=V(x)-V(x/2), \tag{3.2}

and also

V(2x)-V(x)=P(2x). \tag{3.3}

All sums in (3.2) are finite.

Lemma 3: preimage characterization — (a)

For an integer $t$,

t/2\in\mathcal T \quad\Longleftrightarrow\quad \text{\(t\) has a preimage under \(\phi\) divisible by \(4\)}. \tag{3.4}

For the forward implication, choose $\phi(a)=t/2$. If $a$ is even, then $4\mid2a$ and $\phi(2a)=t$; if $a$ is odd, then $4\mid4a$ and $\phi(4a)=t$. Conversely, if $4\mid m$ and $\phi(m)=t$, the prime-power formula gives $\phi(m/2)=t/2$.

Thus primitive totients are exactly those distinct totient values having no $4$-divisible preimage.

Exact equivalent target — (a)

Equations (3.2)--(3.3) give the equivalences

\boxed{ \frac{V(2x)}{V(x)}\to2 \iff \frac{P(x)}{V(x)}\to\frac12 \iff \frac{P(2x)}{V(x)}\to1 . } \tag{3.5}

In words, the dyadic question is exactly the assertion that asymptotically half of the distinct totients up to $x$ have no preimage divisible by $4$. This is not a heuristic reformulation: it is an exact set-theoretic reduction.

(b) Ford's fixed-$c$ bound (2.3), applied at $c=2$, combines with (3.2) to prove the currently available constant-factor statement

P(x)\asymp V(x). \tag{3.6}

It gives a positive-proportion result for primitive totients, but does not identify the required proportion $1/2$.

4. The precise analytic obstruction and an averaged theorem

Define the bounded Ford error

E(x)=\log\frac{V(x)}{F_0(x)}.

Equation (2.1) is exactly $E(x)=O(1)$. Direct differentiation of (2.2) shows

\frac{F_0(2x)}{F_0(x)}\to2.

Therefore:

Local-error criterion — (b), modulo Ford's Theorem 1

\boxed{ \frac{V(2x)}{V(x)}\to2 \quad\Longleftrightarrow\quad E(2x)-E(x)\to0 . } \tag{4.1}

Ford controls the height of $E$, but not its increment across one fixed multiplicative step. An asymptotic $V(x)\sim A F_0(x)$ would force $E(x)\to\log A$ and would be more than enough; (4.1) isolates the strictly weaker regularity actually needed for the ratio question.

The bounded error does disappear after averaging over a growing number of dyadic steps.

Theorem: geometric block averages converge — (b), modulo Ford's Theorem 1

For every integer-valued $h=h(x)\to\infty$,

\left(\frac{V(2^{h}x)}{V(x)}\right)^{1/h}\longrightarrow2. \tag{4.2}

Equivalently,

\left( \prod_{j=0}^{h-1} \frac{V(2^{j+1}x)}{V(2^jx)} \right)^{1/h}\longrightarrow2. \tag{4.3}

Proof. Put $t=\log x$ and $\ell(t)=\log(F_0(e^t)/e^t)$. Formula (2.2) gives

\ell(t)= -\log t+ C(\log_2t-\log_3t)^2+ D\log_2t-(D+\tfrac12-2C)\log_3t,

so $\ell'(t)\to0$. If $|E|\leq B$ for all sufficiently large arguments, then

\begin{aligned} \frac1h\log\frac{V(2^hx)}{V(x)} ={}&\log2+ \frac{\ell(t+h\log2)-\ell(t)}h\\ &+\frac{E(2^hx)-E(x)}h . \end{aligned}

The last term is at most $2B/h=o(1)$. By the mean-value theorem, the middle term is bounded in absolute value by

\log2\sup_{u\geq t}|\ell'(u)|=o(1).

Exponentiating proves (4.2); telescoping proves (4.3). $\square$

This is genuine scale-averaged regularity, but it allows bounded one-step oscillation and therefore does not settle (4.1).

5. Exact finite census through $2^{25}$

The standalone checker is erdos416_wave9g_reverify.py. It has no network access and contains the full computation kernel.

A proved finite preimage cutoff — (a)

Let $q_i$ be the $i$-th prime and define

A_k=\prod_{i=1}^k(q_i-1),\qquad R_k=\prod_{i=1}^k\frac{q_i}{q_i-1},\qquad K(X)=\max\{k:A_k\leq X\}. \tag{5.1}

n=\prod_{i=1}^k p_i^{a_i},\qquad p_1<\cdots<p_k,

and $\phi(n)\leq X$, then

\prod_{i=1}^k(p_i-1)\leq\phi(n)\leq X.

Since $p_i\geq q_i$, this implies $k\leq K(X)$. Also

\frac n{\phi(n)} =\prod_{i=1}^k\frac{p_i}{p_i-1} \leq\prod_{i=1}^k\frac{q_i}{q_i-1} \leq R_{K(X)}.

Hence every possible preimage is in the certified finite interval

n\leq M(X):=\left\lfloor X R_{K(X)}\right\rfloor . \tag{5.2}

This proves completeness; the program does not guess a multiple of $X$.

For $X=2^{25}=33{,}554{,}432$, the checker independently obtains

\begin{aligned} K&=8,\\ (q_1,\ldots,q_8)&=(2,3,5,7,11,13,17,19),\\ A_8&=1{,}658{,}880,\qquad A_9=36{,}495{,}360>X,\\ R_8&=\frac{323323}{55296}=5.847131799768\ldots,\\ M(X)&=196{,}197{,}186. \end{aligned}

Three independent computational routes — (d)

A classical Eratosthenes product-update sieve computes every

$\phi(n)$ for $1\leq n\leq M(X)$.

Euler's linear totient sieve, with a different recurrence and data

layout, repeats the full computation.

A pure trial-factorization implementation independently checks the exact

image through $512$. This third route does not reuse (5.2): it scans to $2\cdot512^2$ using the elementary universal inequality \[ \phi(n)^2\geq n/2. \tag{5.3} \] To prove (5.3), multiply $\phi(p^a)^2/p^a=p^{a-2}(p-1)^2$ over prime powers. Every odd-prime factor is $>1$; the only factor below $1$ is $1/2$, from $2^1$.

The two full image bitsets agree byte-for-byte. The third route agrees on its entire certified prefix and also verifies the doubling and $4$-divisible-preimage characterization there.

Verified dyadic table — (d)

Here $P(x)=V(x)-V(x/2)$ is the exact primitive count.

| $k$ | $x=2^k$ | $V(x)$ | $P(x)$ | $P(x)/V(x)$ | $V(2x)/V(x)$ | |---:|---:|---:|---:|---:|---:| | 10 | 1,024 | 298 | 135 | 0.453020134 | 1.862416107 | | 11 | 2,048 | 555 | 257 | 0.463063063 | 1.882882883 | | 12 | 4,096 | 1,045 | 490 | 0.468899522 | 1.886124402 | | 13 | 8,192 | 1,971 | 926 | 0.469812278 | 1.899543379 | | 14 | 16,384 | 3,744 | 1,773 | 0.473557692 | 1.898237179 | | 15 | 32,768 | 7,107 | 3,363 | 0.473195441 | 1.912480653 | | 16 | 65,536 | 13,592 | 6,485 | 0.477118893 | 1.923852266 | | 17 | 131,072 | 26,149 | 12,557 | 0.480209568 | 1.926459903 | | 18 | 262,144 | 50,375 | 24,226 | 0.480913151 | 1.932248139 | | 19 | 524,288 | 97,337 | 46,962 | 0.482468126 | 1.936365411 | | 20 | 1,048,576 | 188,480 | 91,143 | 0.483568548 | 1.938985569 | | 21 | 2,097,152 | 365,460 | 176,980 | 0.484266404 | 1.942040169 | | 22 | 4,194,304 | 709,738 | 344,278 | 0.485077592 | 1.945282625 | | 23 | 8,388,608 | 1,380,641 | 670,903 | 0.485935881 | 1.947197715 | | 24 | 16,777,216 | 2,688,381 | 1,307,740 | 0.486441468 | 1.949491534 | | 25 | 33,554,432 | 5,240,976 | 2,552,595 | 0.487045733 | -- |

The values approach the conjectured quantities over this short finite range, but are not monotone throughout the table and are not evidence of a uniform limit by themselves.

External and internal audit checks — (d)

Ford's primary paper prints

\begin{array}{c|rrrr} x&10^6&5\cdot10^6&10^7&25\cdot10^6\\ \hline V(x)&180184&840178&1634372&3946809. \end{array}

The from-scratch census reproduces all four values exactly; they are asserted by the checker but are not input to either sieve algorithm.

The common full-bitset SHA-256 is 5679f205fb01406a2a51660faee0f841b8b11b7468e3618456d41653c27934c3. The completed run used Python 3.12.3, g++ 13.3.0, about 1.0 GB peak resident memory, and under one CPU-minute. The checker also asserts every displayed count and the primitive-chain identities.

Reproduce with:

python3 runs/erdos416_wave9g_reverify.py

6. Exact wall and cost of merely pushing the computation

(a)+(b) The unresolved statement can now be named in three exactly equivalent ways:

$P(x)/V(x)\to1/2$;
asymptotically half of distinct totients have no $4$-divisible

preimage;

the bounded Ford error satisfies $E(2x)-E(x)\to0$.

Ford proves only $P(x)\asymp V(x)$ and $E(x)=O(1)$. Neither statement controls the required constant or the one-step increment. Fixed $2$-adic-stratum results likewise do not supply the uniformity across the growing range of relevant strata.

(c) Resource estimate, not a theorem. With the same dense method, $X=10^9$ has the certified cutoff about $6.11\cdot10^9$. A single 32-bit totient array would use about 24.4 GB, and scaling the measured run predicts several minutes per full sieve and roughly $0.2$ core-hours for the complete double-check plus counting. At $X=10^{12}$, (5.2) is about $6.5\cdot10^{12}$: a dense array alone needs about 26 TB and the work is on the order of $10^2$ core-hours. Segmentation can reduce the array memory but not the need to record or count an enormous image. More importantly, no finite cutoff can establish (4.1).

The useful next step is therefore analytic, not a larger census: prove a local-stability lemma for Ford's bounded error, or equivalently determine the limiting proportion of totient values whose entire preimage avoids multiples of $4$. The block-average theorem shows precisely why growing scale averages are accessible while one fixed dyadic step remains out of reach.

PARTIAL: exact primitive-totient reduction and a Ford-modulo dyadic block-average limit proved; two independent sieves compute $V$ and primitive counts through $2^{25}$, while the one-step error-increment lemma remains open.

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