Erdős Problem #51

Read our full write-up →

Erdős asked whether the least solution of φ(n) = a can exceed a by an unbounded factor. Writing ℓ(a) for that least solution, ℓ(a)/a = ∏ p/(p−1) over the primes dividing ℓ(a), so the question is whether least preimages can carry ever more small primes. Tao expects not; Erdős, in 1979, hoped for something that would imply yes. Ours, first, is an elementary barrier theorem, extending Carmichael's 1907 observation about powers of 2 and Fermat primes. Take a finite set S of primes closed under p ↦ the prime factors of p−1. If ℓ(a)/a stayed below ∏ p/(p−1) over S, there would be infinitely many primes q with every prime factor of q−1 in S. So a negative answer to #51 would give, for some fixed y, infinitely many primes p with p−1 y-smooth, which is not known for any fixed y (for y = 3 these are the Pierpont primes). Ratios below 3 everywhere would give infinitely many Pierpont primes. And if no totient has ℓ(d) > 3d (the case OpenAI's totient preprint leaves open), there are infinitely many primes of the form 2^α3^β5^γ + 1. Second, why the theorem's family does not produce large ratios in practice. We computed the least preimage of every 3-smooth totient 2^X3^Y with X ≤ 120 and 1 ≤ Y ≤ 80 exactly, by two methods: none exceeds 2 + 10⁻²⁰, against a ceiling of 3, because the Pierpont primes the theorem asks for are there. On the theorem's own diagonals the least preimage is one to three such primes. Third, the ratio splits as T·W, with T ≤ 2 coming from powers of 2 and Fermat primes, so #51 asks whether W is unbounded; up to 10⁹ the largest W is 1.584. Fourth, our July chain re-checked by an independent program: 2.044975 at a ≈ 1.8·10¹⁶, the largest ratio we know (the published record search stops at 1.2·10¹¹ with 2.043447). The problem stays open.