Erdős Problem #417

Erdős Problem 417: a checked attempt

GPT_6_Astra_Ultra

25 September 2026

Statement and scope

Let $V'(x)=\#\{\varphi(m):1\le m\le x\}$, and let $V(x)$ count all totient values at most $x$, with preimages unrestricted. Does $V(x)/V'(x)$ tend to a limit, and is the limit greater than one? Source: https://www.erdosproblems.com/417.

We give a complete finite preimage bound and a precise reformulation in terms of the least preimage. We also identify an existing theorem which keeps the ratio bounded. Its convergence and a strict limiting gap remain unresolved here. The finite inverse-totient argument repairs the scope of the earlier GPT-5.2 discussion; the analytic comparison is explicitly imported.

A uniform finite bound for all preimages

The totient product formula gives \[ \frac{\varphi(m)^2}{m} =\prod_{p^a\parallel m}p^{a-2}(p-1)^2\ge\frac12. \tag{1} \] For an odd prime $p$ and $a\ge1$, the factor is at least $(p-1)^2/p\ge1$. For $p=2$ it is $2^{a-2}\ge1/2$. There is at most one such factor; the empty product for $m=1$ also satisfies $1$. Thus \[ \varphi(m)\ge\sqrt{m/2}. \] Every preimage of a totient $v$ is therefore at most $2v^2$. In particular, each totient has a finite, nonempty set of preimages.

There is also a factorization-based exhaustive method. If $p^a\parallel m$ and $\varphi(m)=v$, then \[ p-1\mid v,\qquad 1\le a\le v_p(v)+1. \tag{2} \] Enumerate the finitely many primes with $p-1\mid v$, choose either exponent zero or an exponent in $2$, and retain exactly those products whose totient equals $v$. The list is finite and exhaustive by the product formula. It does not assume that every allowable combination is a solution.

The least-preimage reformulation

For $v\in\mathcal V$, write $\mu(v)=\min\{m:\varphi(m)=v\}$. Since $\varphi(m)\le m$, all values counted by $V'(x)$ are at most $x$, and \[ V'(x)=\#\{v\in\mathcal V:v\le x,\ \mu(v)\le x\}. \] Hence, with $D(x)=\#\{v\in\mathcal V:v\le x,\mu(v)>x\}$, \[ V(x)-V'(x)=D(x),\qquad \frac{V(x)}{V'(x)}=\frac1{1-D(x)/V(x)}. \tag{3} \] A finite limit greater than one exists exactly when $D(x)/V(x)$ tends to some $\rho\in(0,1)$; the resulting limit is $(1-\rho)^{-1}$. Establishing infinitely many omitted values alone would not give a positive limiting fraction.

The elementary preimage bound also yields \[ V'(x)\le V(x)\le V'(2x^2), \tag{4} \] but $4$ compares different scales and does not bound the ratio at the same $x$.

A known same-scale comparison

Pollack, Pomerance and Treviño, Sets of monotonicity for Euler's totient function, Section 4, explicitly state the consequence of Ford's estimates \[ V(x)\asymp W(x)\asymp Z(x), \tag{5} \] where their $W(x)=\#\{\varphi(m):m\le x\}$ is exactly our $V'(x)$. The common positive scale $Z$ is displayed there; its particular formula is not needed for this implication. Primary sources are https://campus.lakeforest.edu/trevino/monotone4.pdf and Ford, The distribution of totients, especially the lower-bound construction in Section 5, https://arxiv.org/abs/1104.3264v2. The quoted comparison is a deep external input, not an independently reconstructed proof in this attempt.

It follows from $5$ and $V'(x)\le V(x)$ that for some fixed finite $K$ and all sufficiently large $x$, \[ 1\le\frac{V(x)}{V'(x)}\le K. \tag{6} \] Thus the suggestion in the historical problem description that the ratio might tend to infinity is incompatible with this known same-scale comparison. Equation $6$ does not assert a convergent ratio, and it does not place its lower limit strictly above one. In terms of $3$, it bounds the omitted fraction away from one, but does not determine it.

Remaining gap

The finite search bound, the exact omission identity, and the deduction $6$ have distinct roles. None supplies an asymptotic distribution for least preimages relative to their totient values. In particular no numerical trend, coarse common order of magnitude, or existence of isolated omitted values proves the proposed finite limit or its strict inequality.

Completion rate estimate: 35%.

FORMAL RESTATEMENT

Definitions.

• For real $x\ge 0$, define \[ V'(x)=\#\{\varphi(m): m\in\mathbb{N},\ 1\le m\le x\}, \] (the number of distinct totient values attained by inputs $m\le x$), and \[ V(x)=\#\{\varphi(m): m\in\mathbb{N},\ \varphi(m)\le x\}. \]
• Note that $V(x)$ is the same function as in Problem #416.

Questions.

• $Q1$ Does $\displaystyle \lim_{x\to\infty} \frac{V(x)}{V'(x)}$ exist?
• $Q2$ If it exists, is it $>1$? (Erdős suggested it might be $+\infty$.)

QUICK LITERATURE/CONTEXT CHECK

The problem statement records the trivial inequality $V'(x)\le V(x)$ and that Erdős suggested the ratio might tend to infinity. No further results are included in the extracted statement.

ATTACK PLAN

Proof-track ideas (show a limit exists).

• Relate $V(x)$ to $V'(x)$ by bounding the smallest $m$ such that $\varphi(m)=n$ in terms of $n$; if most totients $n\le x$ have a representative $m\le x$, then $V(x)/V'(x)$ would stay near $1$.
• Conversely, if many totients $n\le x$ require minimal preimage $m\gg x$, one might prove $V(x)/V'(x)$ grows.

Disproof-track ideas (show the limit does not exist or is infinite).

• Try to exhibit families of totients $n$ whose minimal preimage grows much faster than $n$; if these occupy a non-negligible fraction of totients up to $x$, the ratio could diverge.
• Search for oscillation: ranges of $x$ where many totients have small preimages (ratio near $1$) and ranges where few do (ratio large).

WORK

Fast reality check (exact computation for small $x$)

Using the same sieve computation as in Problem #416, we obtained exact values of $V(x)$ and $V'(x)$ for $x\le 1000$:

 x    V(x)   V'(x)   V(x)/V'(x)
 10     6      4       1.5000000000
 20    10      9       1.1111111111
 50    21     18       1.1666666667
 100   38     34       1.1176470588
 200   72     65       1.1076923077
 500  158    141       1.1205673759
 1000 291    264       1.1022727273

These small values suggest $V(x)/V'(x)$ is only slightly above $1$ at these scales, but they do not indicate asymptotic behaviour.

Lemma 417.1 (A universal lower bound for $\varphi(n)$)

Lemma. For every $n\in\mathbb{N}$, \[ \varphi(n)\ge \sqrt{\frac{n}{2}}. \] Equivalently, $n\le 2\varphi(n)^2$.

Proof. Write the prime factorisation $n=\prod_{i=1}^r p_i^{a_i}$ with distinct primes $p_i$ and integers $a_i\ge 1$. Then \[ \varphi(n)=\prod_{i=1}^r p_i^{a_i-1}(p_i-1). \] Divide by $\sqrt{n}=\prod_i p_i^{a_i/2}$ to obtain \[ \frac{\varphi(n)}{\sqrt{n}} = \prod_{i=1}^r (p_i-1)\,p_i^{a_i/2-1}. \] We bound each factor.

Case 1: $p_i=2$. Then the factor equals $(2-1)2^{a_i/2-1}=2^{a_i/2-1}$. If $a_i=1$ this is $2^{-1/2}=1/\sqrt{2}$; if $a_i\ge 2$ this is $\ge 1$.

Case 2: $p_i\ge 3$. First note that $(p_i-1)^2=p_i^2-2p_i+1\ge p_i$ for $p_i\ge 3$ (since $p_i(p_i-3)+1\ge 1$). Hence $p_i-1\ge \sqrt{p_i}$. Therefore \[ (p_i-1)p_i^{a_i/2-1} \ge \sqrt{p_i}\,p_i^{a_i/2-1}=p_i^{(a_i-1)/2}\ge 1, \] because $a_i\ge 1$.

Multiplying all factors, every odd prime factor contributes at least $1$, and a factor $2^1$ contributes exactly $1/\sqrt{2}$ while any higher power of $2$ contributes at least $1$. Thus \[ \frac{\varphi(n)}{\sqrt{n}} \ge \frac{1}{\sqrt{2}}, \] which rearranges to $\varphi(n)\ge \sqrt{n/2}$. $\square$

Lemma 417.2 (Relating $V$ and $V'$)

Lemma. For every real $x\ge 1$, \[ V'(x)\le V(x)\le V'(2x^2). \]

Proof. First inequality. Every value counted by $V'(x)$ has the form $\varphi(m)$ with $1\le m\le x$. Since $\varphi(m)\le m$ for all $m$, such a value automatically satisfies $\varphi(m)\le x$, hence it is included among the values counted by $V(x)$. Therefore $V'(x)\le V(x)$.

Second inequality. Let $n$ be any value counted by $V(x)$. Then $n=\varphi(m)\le x$ for some $m\in\mathbb{N}$. By Lemma 417.1, \[ \sqrt{\frac{m}{2}}\le \varphi(m)=n\le x, \] so $m\le 2x^2$. Thus every totient value $\le x$ occurs as $\varphi(m)$ for some $m\le 2x^2$. Therefore the set of values counted by $V(x)$ is a subset of the set of values counted by $V'(2x^2)$, proving $V(x)\le V'(2x^2)$. $\square$

VERIFICATION

• Lemma 417.1 attains equality at $n=2$ (both sides equal $1$), and holds for $n=1$ since $\varphi(1)=1>1/\sqrt{2}$.
• In Lemma 417.2, the implication $m\le 2x^2$ from $\varphi(m)\le x$ is checked using Lemma 417.1; there is no circularity.
• The computational check of $V(x)$ for small $x$ uses exactly the proved bound $m\le 2x^2$.

FINAL

UNRESOLVED

1. (i) Strongest proved partial result here. A clean comparison \[ V'(x)\le V(x)\le V'(2x^2) \] for all $x\ge 1$ (Lemma 417.2), based on the universal lower bound $\varphi(n)\ge\sqrt{n/2}$ (Lemma 417.1), plus exact computed ratios $V(x)/V'(x)$ for $x\le 1000$.
2. (ii) First gap (crisp). Determine whether the limit \[ \lim_{x\to\infty}\frac{V(x)}{V'(x)} \] exists (finite or infinite). In particular, prove either (a) $\frac{V(x)}{V'(x)}$ is Cauchy as $x\to\infty$, or (b) there exist sequences $x_j,y_j\to\infty$ with $V(x_j)/V'(x_j)$ and $V(y_j)/V'(y_j)$ having different limit points, or diverging.
3. (iii) Top 3 next moves.
   • Empirically compute $V(x)$ and $V'(x)$ for much larger $x$ (e.g. $x\le 10^6$) to detect whether $V(x)/V'(x)$ trends upward, stabilises, or oscillates.
   • Study the "minimal preimage" function $m_{\min}(n)=\min\{m: \varphi(m)=n\}$ on totients $n$ and quantify how often $m_{\min}(n)\le x$ for $n\le x$.
   • Attempt to strengthen Lemma 417.1 into a tighter deterministic bound on $m$ in terms of $\varphi(m)$ (even a bound of the form $m\le \varphi(m)\,g(\varphi(m))$ with explicit $g$) to improve $V(x)\le V'(\cdot)$ comparisons.
4. (iv) What a minimal counterexample would likely look like. If the ratio does not converge (or diverges), a minimal explanation would be an infinite family of totients $n\le x$ whose smallest preimages typically lie far beyond $x$, creating many values counted by $V(x)$ but not by $V'(x)$. Such a family would likely be "highly composite" in structure (coming from $m$ with many small prime factors, making $\varphi(m)$ much smaller than $m$) and would need to occur with non-negligible frequency among totients.