Erdős Problem 821

References:

• erdosproblems.com/821
• [BaHa98] Baker, R. C. and Harman, G., Shifted primes without large prime factors. Acta Arith. (1998), 331--361.
• [Er35b] Erdős, P., On the normal number of prime factors of $p-1$ and some related problems concerning Euler's $\varphi$-function. Quart. J. Math. (1935), 205-213.
• [Er74b] Erdős, P., Remarks on some problems in number theory. Math. Balkanica (1974), 197-202.
• [Li22] J. D. Lichtman, Primes in arithmetic progressions to large moduli and shifted primes without large prime factors. arXiv:2211.09641 (2022).
• [LuPo11] Luca, Florian and Pollack, Paul, An arithmetic function arising from {C}armichael's conjecture. J. Théor. Nombres Bordeaux (2011), 697--714.

noncomputable def Erdos821.g (n : ℕ) : ℕ

Let $g(n)$ count the number of $m$ such that $\phi(m)=n$.

Equations

• Erdos821.g n = {m : ℕ | m.totient = n}.ncard

theorem Erdos821.erdos_821 : sorry ↔ ∀ ε > 0, {n : ℕ | ↑(g n) > ↑n ^ (1 - ε)}.Infinite

Is it true that, for every $\epsilon>0$, there exist infinitely many $n$ such that $g(n) > n^{1-\epsilon}$?

theorem Erdos821.erdos_821.variants.pillai : Filter.limsup (fun (n : ℕ) => ↑(g n)) Filter.atTop = ⊤

Pillai proved that $\limsup g(n)=\infty$.

theorem Erdos821.erdos_821.variants.erdos : ∃ c > 0, {n : ℕ | ↑n ^ c < ↑(g n)}.Infinite

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

theorem Erdos821.erdos_821.variants.lichtman : ∃ c > 0.71568, {n : ℕ | ↑n ^ c < ↑(g n)}.Infinite

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]).