Problem #821: Let $g(n)$ count the number of $m$ such that $\phi(m)=n$

---

Progress

Pillai proved that $\limsup g(n)=\infty$ and Erdős [Er35b] proved that there exists some constant $c>0$ such that $g(n) >n^c$ for infinitely many $n$.

This conjecture would follow if we knew that, for every $\epsilon>0$, there are $\gg_\epsilon \frac{x}{\log x}$ many primes $p<x$ such that all prime factors of $p-1$ are $<p^\epsilon$.

The best known bound is that there are infinitely many $n$ such that\[g(n) > n^{0.71568\cdots},\]obtained by Lichtman [Li22] as a consequence of proving that there are $\geq \frac{x}{(\log x)^{O(1)}}$ many primes $p\leq x$ such that all prime factors of $p-1$ are $\leq x^{0.2843\cdots}$ (which improves a number of previous exponents, most recently Baker and Harman [BaHa98]).

The average size of $g(n)$ was investigated by Luca and Pollack [LuPo11].

See also [416].