Recursos
Resumen
You can now explain why a large supply of primes p with only small prime factors in p − 1 forces one totient value to have almost n preimages, and where that supply comes from in the proof of Erdős's conjecture.
The toy case and the pigeonhole idea
Take φ(m) = 72. The numbers 73, 7·13, 5·19 and 3·37 all map to it, because every p − 1 involved (2, 4, 6, 12, 18, 36, 72) is made only of 2s and 3s [0:48]. Since φ is multiplicative, the totient of a squarefree product is the product of the p − 1. Every product therefore lands in a box 2^a·3^b. You get many products and only a few boxes, so some of them have to collide. A prime like 11 (p − 1 = 2·5) can't join, because its 5 falls outside the boxes. Primes whose predecessor has only small prime factors are called smooth shifted primes.
The real count
- Products (pigeons) [1:31]: start with M > X^(1−δ) primes up to X, each with an X^δ-smooth p − 1, and take k = ⌊X^(2δ)⌋. Unique factorization makes the k-subsets give distinct products, at least (M/k)^k > X^((1−3δ)k) of them.
- Values (boxes) [2:11]: each totient is X^δ-smooth and at most X^k. That means it is fixed by an exponent vector over at most X^δ primes, so there are at most (1 + k log X / log 2)^(X^δ) = X^(o(k)) possible values. Longer products do not create more room.
- Divide [2:46]: some n ≤ X^k has g(n) ≥ X^((1−3δ−o(1))k), which is more than n^(1−ε) once 4δ < ε. The argument needs δ arbitrarily small. A fixed smoothness exponent near 0.30 only gave fiber exponents near 0.70.
- Think-first check [4:50]: with k = X^(δ/2), the box count wins and the pigeonhole step says nothing. k must outrun the number of available primes.
Where the primes come from
Theorem 1.2 of the paper gives at least x^(1−o(1)) primes in (2x, 5x] whose p − 1 is x^δ-smooth [3:23]. The proof counts primes 2u + 1, with u built from small primes in many size bands. A first sieve uses congruence counts. The Type II estimate for mn = 2u + 1 then removes the composite values. Splitting u = e·h and applying Cauchy–Schwarz turns the off-diagonal terms into shifted correlations. Those are controlled by a transference theorem for weighted dilation graphs [4:05]: if the idealized operator (independent primes with weights ∝ 1/p) has small norm, then the real divisibility graph has a small high moment, and the shifted sums cancel.
Whenever you meet a popular-values argument, compare two counts: the products you can build from a large supply of primes, and the boxes that smooth predecessors leave for them.