Erdős Problem #694

Erdős Problem 694: ratios of extreme inverse totients

Statement and claim.

A uniform upper bound.

Put $Y=\log(2x^2)$. Uniformly for $m\leq2x^2$, separate the prime factors of $m$ at $Y$. There are at most $\log(2x^2)/\log Y$ distinct prime factors exceeding $Y$, so \[ \prod_{\substack{p\mid m\\p>Y}}(1-1/p)^{-1} \leq\exp\left(\frac{2\log(2x^2)}{Y\log Y}\right)=1+o(1). \] Mertens' theorem handles the smaller primes: \[ \frac m{\phi(m)} \leq(1+o(1))\prod_{p\leq Y}(1-1/p)^{-1} =(e^\gamma+o(1))\log Y =(e^\gamma+o(1))\log\log x. \] For $a=f_{\min}(n)$, $b=f_{\max}(n)$, use \[ \frac ba=\frac b{\phi(b)}\frac{\phi(a)}a \leq\frac b{\phi(b)} \] to obtain the required upper bound.

Two preimages with separated sizes.

Ensuring the common totient is at most $x$.

Scope.

Completion estimate.

1) FORMAL RESTATEMENT

Let $\phi$ denote Euler's totient function. For an integer $n\ge 1$ in the image of $\phi$ (i.e. such that there exists $m\ge 1$ with $\phi(m)=n$), define \[ f_{\max}(n):=\max\{m\ge 1: \phi(m)=n\},\qquad f_{\min}(n):=\min\{m\ge 1: \phi(m)=n\}. \] For $x\ge 1$, define \[ R(x):=\max\Big\{\frac{f_{\max}(n)}{f_{\min}(n)}:\ 1\le n\le x,\ n\in\mathrm{Im}(\phi)\Big\}. \] The task is to investigate the growth of $R(x)$ as $x\to\infty$. The problem statement also mentions Carmichael's question: does there exist $n$ with a unique solution to $\phi(m)=n$ (equivalently $f_{\max}(n)=f_{\min}(n)$)?

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement records that Erdős proved: if there exists $n$ for which $\phi(m)=n$ has exactly one solution, then there are infinitely many such $n$. I do not use external references beyond this remark.

3) ATTACK PLAN

Proof track: relate $m/\phi(m)$ to the prime factors of $m$ and try to compare the largest and smallest preimages for a given $n$.

Disproof/obstruction track: find general mechanisms guaranteeing multiple solutions (e.g. producing $2m$ from an odd solution) and compute small instances to see how large $f_{\max}/f_{\min}$ can get.

I obtain basic structural lemmas and a small computational sanity check; the asymptotic behavior remains open here.

4) WORK

Lemma 694.1 (Odd totients). For $m\ge 1$, $\phi(m)$ is odd if and only if $m\in\{1,2\}$. Equivalently, for every $m\ge 3$, $\phi(m)$ is even.

Proof. If $m=1$ then $\phi(1)=1$ (odd). If $m=2$ then $\phi(2)=1$ (odd).

Conversely, assume $m\ge 3$.

- If $m$ is divisible by $4$, then among the residues modulo $m$, exactly half are odd and exactly half are even, and any even residue is not coprime to $m$. More directly: if $4\mid m$, then $2\mid \phi(m)$ because $\phi(2^t)=2^{t-1}$ is even for $t\ge 2$ and $\phi$ is multiplicative over coprime factors.

- If $m$ is not divisible by $4$, then $m$ has an odd prime factor $p$ (since $m\ge 3$). Write $m=p^a r$ with $p\nmid r$. Then \[ \phi(m)=\phi(p^a)\phi(r)=(p^a-p^{a-1})\phi(r)=p^{a-1}(p-1)\phi(r). \] Since $p$ is odd, $p-1$ is even, so the product is even.

Thus $\phi(m)$ is even for all $m\ge 3$. $\square$

Lemma 694.2 (A mechanism forcing non-uniqueness). If $m$ is odd and $\phi(m)=n$, then $\phi(2m)=n$ and $2m\ne m$. In particular, for such $n$ the equation $\phi(x)=n$ has at least two solutions.

Proof. If $m$ is odd then $\gcd(2,m)=1$, so by multiplicativity of $\phi$ on coprime inputs, \[ \phi(2m)=\phi(2)\phi(m)=1\cdot n=n. \] Also $2m\ne m$ since $m\ge 1$. $\square$

Lemma 694.3 (Ratio formula). If $\phi(m)=n$ then \[ \frac{m}{n}=\prod_{p\mid m}\frac{p}{p-1}, \] where the product is over distinct primes $p$ dividing $m$.

Proof. Write the prime factorization $m=\prod_{p} p^{\alpha_p}$ (finite product). Then the standard totient formula gives \[ \phi(m)=m\prod_{p\mid m}\Big(1-\frac{1}{p}\Big)=m\prod_{p\mid m}\frac{p-1}{p}. \] Rearranging yields $m/\phi(m)=\prod_{p\mid m} p/(p-1)$, and substituting $\phi(m)=n$ gives the claim. $\square$

FAST REALITY CHECK (finite search). A local sieve computation of $\phi(m)$ for $m\le 200000$ and recording, for each $n\le 50000$ encountered, the minimum and maximum $m$ with $\phi(m)=n$, found the largest observed ratio \[ \frac{\max\{m\le 200000: \phi(m)=n\}}{\min\{m\le 200000: \phi(m)=n\}}\approx 5.2133 \] attained at $n=23040$ with min $m=23041$ and max $m=120120$ (within this search range).

5) VERIFICATION

- Lemma 694.1 correctly handles edge cases $m=1,2$ and shows all other totients are even.

- Lemma 694.2 shows that any $n$ admitting an odd preimage cannot be a Carmichael counterexample (unique preimage).

- Lemma 694.3 is an exact identity.

- The computation is explicitly limited to solutions with $m\le 200000$; it is not a proof about the true values of $f_{\max}(n)$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. (a) $\phi(m)$ is odd iff $m\in\{1,2\}$ (Lemma 694.1). (b) If $\phi(m)=n$ has an odd solution $m$, then it has at least two solutions ($m$ and $2m$), so any $n$ with a unique solution must have all solutions even (Lemma 694.2). (c) Any solution satisfies $m/n=\prod_{p\mid m}p/(p-1)$ (Lemma 694.3).

(ii) First gap (crisp). Determine the true asymptotic growth of $R(x)=\max_{n\le x} f_{\max}(n)/f_{\min}(n)$, or even prove that $R(x)\to\infty$ as $x\to\infty$.

(iii) Top 3 next moves. 1. Construct explicit infinite families of $n$ with two solutions $m_{\min},m_{\max}$ whose prime-factor sets force $m_{\max}/m_{\min}$ to grow (using Lemma 694.3 to control $m/n$). 2. Prove general upper/lower bounds relating $f_{\min}(n)$ and $f_{\max}(n)$ to multiplicative structure of $n$ (e.g. how many distinct primes can divide a preimage). 3. Extend computations to larger ranges of $m$ and $n$ to identify plausible extremal $n$ and conjecture the growth rate of $R(x)$.

(iv) Minimal counterexample structure. To make $f_{\max}(n)/f_{\min}(n)$ large, one expects $f_{\min}(n)$ to be close to $n$ (often realized when $n+1$ is prime so that $\phi(n+1)=n$) while $f_{\max}(n)$ has many small prime factors, making $m/\phi(m)=\prod_{p\mid m}p/(p-1)$ large by Lemma 694.3.