#51: a "no" answer would prove that infinitely many primes p have p−1 built from a fixed finite set of primes — least-preimage ratios bounded below 3 would give infinitely many Pierpont primes, and the absence of 3-seeds infinitely many primes 2^α3^β5^γ + 1; plus exact least preimages for every 3-smooth totient 2^X3^Y with X ≤ 120, Y ≤ 80 (none above 2 + 10⁻²⁰) and the largest ratio we know, 2.044975

The problem (erdosproblems.com/51; [Er95] §9, [Er98]): is there an infinite set of totients a whose least preimages n_a = min{n : φ(n) = a} satisfy n_a/a → ∞? Write ℓ(a) for the least preimage and R(a) = ℓ(a)/a. Since φ(ℓ) = a, R(a) = ℓ/φ(ℓ) = ∏ p/(p−1) over the primes dividing ℓ(a), so the question is whether least preimages can contain ever more small primes; it is equivalent to sup R = ∞. Status: open (database 2025-08-31; Formal Conjectures erdos_51, research open; no proof claims on the page). Opinions differ. Tao (forum, 10 Aug 2025): "Most likely the answer is negative … if n has too many prime factors, it should be possible to swap out some prime factors for others to reduce n while maintaining exactly the same value of φ(n). But it looks very difficult to prove this rigorously with our current analytic number theory technology!" Erdős, in 1979 (Astérisque 61, p. 80), wrote of the largest m′_X with φ(m′_X) ≤ X that is a least preimage, against the largest m_X with φ(m_X) ≤ X: "I hope that m′_X/m_X → 1 but I do not see how to prove this." Since m_X ≫ X log log X and m′_X = max_a≤X ℓ(a), that hope would give some a ≤ X with ℓ(a)/a ≥ m′_X/X → ∞: a yes (our remark; the problem's page does not record it). What is known: the record ratios below 1.2·10¹¹ are the six terms of OEIS A393265 (McCranie, Feb 2026), ending at a = 387,383,296 with R = 2.043447; Ford's propagation lemma (stated as Lemma 7.2 in OpenAI's totient-count preprint, read by AI seats and Lean-replayed here today) turns any single ratio into infinitely many, so lim sup R ≥ 2.043447 (2.044975 with the chain below); and that preprint calls a totient d with ℓ(d) > kd a k-seed, proves a positive proportion of totients have ℓ(v) > kv when one exists, and leaves open whether 3-seeds exist. Labels, as on every entry here: (a) elementary proof · (b) rigorous modulo a named theorem · (c) plausible, unverified · (d) computer-assisted.

The barrier ((a); the case S = {2} is Carmichael's, the rest is ours as far as we found). Call a finite set S of primes φ-closed if p−1 has all its prime factors in S for every p ∈ S (for example {2}, {2, 3}, {2, 3, 5}, {2, 17}, {2, 3, 7}). Let Q_S be the set of primes q ∉ S such that q−1 has all its prime factors in S; for S = {2} they are the Fermat primes 3, 5, 17, 257, 65537 and any unknown ones; for S = {2, 3}, the Pierpont primes 2^α3^β + 1 other than 2 and 3. Put n_K = ∏_p∈S p^K and a_K = φ(n_K).

Theorem. If Q_S is finite, then ℓ(a_K) = n_K for every K with K − 1 > max_p∈S Σ_q∈QS v_p(q−1); in particular R(a_K) = ∏_p∈S p/(p−1).

Proof. Let m = ℓ(a_K). Each prime r | m has r−1 | φ(m) = a_K, whose prime factors lie in S (that is what φ-closed buys); so r ∈ S or r ∈ Q_S, and a prime r ∉ S divides m only once, since r ∤ a_K. Suppose some p ∈ S does not divide m. Since φ(m) = ∏_r^f‖m r^f−1(r−1) and no r equals p, v_p(a_K) = Σ_r|m v_p(r−1) ≤ Σ_r∈S v_p(r−1) + Σ_q∈QS v_p(q−1). But v_p(a_K) = (K−1) + Σ_r∈S v_p(r−1) exactly, so K−1 ≤ Σ_q∈QS v_p(q−1), against the choice of K. So every p ∈ S divides m, and m/φ(m) = ∏_r|m r/(r−1) ≥ ∏_p∈S p/(p−1) = n_K/φ(n_K). Since m ≤ n_K and both have φ-value a_K, equality holds throughout: m has no prime outside S, and matching valuations give m = n_K. ∎

For S = {2} the known Fermat primes give Σ v₂(q−1) = 1+2+4+8+16 = 31, and the theorem says ℓ(2^k) = 2^k+1 for every k ≥ 32 if there are no more Fermat primes. That is Carmichael's 1907 result (we have it through the zbMATH review of Gupta 1981 and OEIS A002181), with the same threshold, and it is sharp: at k = 31 the odd number 3·5·17·257·65537 is smaller. So the theorem is an elementary extension of Carmichael's observation from Fermat primes to any φ-closed set. The idea that #51's swaps run into smooth shifted primes is on the problem's forum already: Kovač (28 Aug 2025) linked them to #203 ("one would use such prime p to replace some powers of 2 and 3 from a. But already these questions seem to be too difficult"). We found the general statement nowhere. (The proof uses φ-closedness only to make a_K S-smooth; any finite S works if Q_S is widened to the primes r with r−1 equal to d times a product of primes from S, for divisors d of the S-free part of ∏(p−1).)

Read backwards (if R(a_K) < ∏_S p/(p−1) for infinitely many K, then Q_S is infinite), the theorem gives:

• A "no" answer to #51 would settle an open question about primes. If sup R < ∞, take y with ∏_p≤y p/(p−1) > sup R. There would be infinitely many primes q with q−1 y-smooth, where y ≥ 3 since sup R > 2. No fixed y is known to have this property. For y = 3 it is the Pierpont-prime question, open (erdosproblems.com/1055, which cites Guy's A18). Any fixed y would also give infinitely many p with P(p−1) < p^ε for every ε. Luca, Menares and Pizarro-Madariaga wrote of that much weaker statement in 2013: "we do not know whether for each ε > 0 arbitrarily small there exist infinitely many primes p with P(p−1) < p^ε". It has since been claimed in an unrefereed OpenAI preprint ("Weighted dilation graphs, smooth shifted primes and totient fibers", September 2026, not the totient-count preprint), still with a bound that grows with p. So the negative answer Tao expects is at least as hard as a fixed-smoothness infinitude theorem for primes. That is consistent with his "very difficult … with our current analytic number theory technology", though the connection is ours, not his.
• Below 3 means infinitely many Pierpont primes. If ℓ(a) < 3a for every totient a (only a = φ(2^K3^K) for infinitely many K is needed), there are infinitely many primes 2^α3^β + 1 ("≤ 3" is not enough). Likewise ℓ(a) < 2.5a throughout forces infinitely many primes 2^α5^β + 1, and ℓ(a) < 2.125a (= 2·17/16) forces infinitely many primes 2^α17^β + 1. The largest ratio known is 2.044975, below all three. ({2, 257} gives only 2.0078, already exceeded, so this list of Fermat cases is complete.)
• The 3-seed question. If no totient has ℓ(d) > 3d, then S = {2, 3, 5} (product 15/4) gives infinitely many primes 2^α3^β5^γ + 1, with γ = 0 allowed, so this would also follow from infinitely many Pierpont primes. With S = {2, 3, q} for a prime q ≥ 5 with q−1 3-smooth, the honest form is a disjunction. Either there are infinitely many Pierpont primes, or for each such q there are infinitely many primes 2^α3^βq^γ + 1 with γ ≥ 1. Read the other way: if the primes 2^α3^β5^γ + 1 are finite in number, a 3-seed exists. Then by the preprint's Theorem 2.2, whose Lean proof we replayed for #416, a positive proportion of totients v have ℓ(v) > 3v. That last step is (b), modulo that theorem. In general a k-seed is forced unless Q is infinite for the first y with ∏_p≤y p/(p−1) > k: y = 5 for k = 3, 7 for k = 4, 13 for k = 5.

The theorem cannot give a yes answer: everything believed about smooth shifted primes says Q_S is infinite whenever |S| ≥ 2. Its use is as a dividing line. A proof that ratios are bounded must produce smooth shifted primes for some fixed y. The most direct route to yes, forcing the trivial preimage of a smooth totient, fails as soon as enough of them exist. Other routes to yes need not use smooth totients at all.

Why the barrier family stays small in practice ((d), three instruments). We computed least preimages exactly for whole families of smooth totients. All their preimages are products of prime powers q^f with q−1 smooth, so ℓ is the cheapest exact cover of the exponent vector. Instrument 1 is a dynamic programme over the whole exponent lattice: a 0/1 knapsack over the primes q outside the base and one power per base prime, with primality by BPSW. BPSW never rejects a prime, so no true preimage is missed. Instrument 2 is a depth-first branch-and-bound over prime powers with exact integers and no lattice. They agree on 600 random lattice points and 80 non-totient points. The hostile computation referee then wrote a third: an exact-integer lattice DP in which every one of the 402 and 2,914 free primes is proved prime by a Lucas–Pocklington certificate from the factorization of q−1, rather than by BPSW. That matters because the bounds below are upper bounds, where a fake prime would make a ratio look smaller. It agrees with instrument 1 on every cell of both lattices, to float noise (4·10⁻¹⁶ relative). Results:

• Every 3-smooth totient 2^X3^Y with X ≤ 120 and 1 ≤ Y ≤ 80 has ℓ(a) < (2 + 10⁻²⁰)a (9,600 totients, 402 Pierpont primes in range). The ceiling for these values is 3 (2^X3^Y+1 is always a preimage). The maximum, 2 + 9.04·10⁻²¹, is attained at every a = 3·2^X with 98 ≤ X ≤ 120, where ℓ = 2^X−65·(3·2⁶⁶ + 1): there is no prime 3·2^j + 1 with 67 ≤ j ≤ 188. It was found by exact arithmetic at all 27 points within 0.01 of 2. Powers of 2 alone give exactly 2 from 2³² onwards (ℓ(2^k) = 2^k+1 for 32 ≤ k < 2³³, since F₅,…,F₃₂ are composite; Carmichael 1907 has the conditional form).
• On the diagonals the theorem uses, the least preimage is a few large primes from Q_S. For S = {2, 3} and 2 ≤ K ≤ 40 the largest R(φ(2^K3^K)) is 13/12, at K = 2. At K = 18 it is the single prime a₁₈ + 1 = 2¹⁸·3¹⁷ + 1 = 33,853,318,889,473. For {2, 3, 5} and K ≤ 20 the largest is 1.0240, and for {2, 3, 7}, {2, 3, 13} and {2, 5} it is at most 1.094; for {2, 17}, 1.328 (17 itself stays in). The trivial covers are worth 3, 3.75, 3.5, 3.25, 2.5 and 2.125. The smooth shifted primes the theorem asks about are plentiful at every size we can reach.
• 5-smooth totients 2^X3^Y5^Z with exponents up to (60, 30, 20) and odd part > 1: the largest ratio is 15/8 + 3·2⁻⁵⁸ at 2⁵⁸·5 (ℓ = 3·5·(5·2⁵⁵ + 1)), and every other cell is at most 1.6000000092. A first draft said "at most 1.875". The float DP cannot see a 10⁻¹⁷ excess, and the referee's exact pass caught it.

Anatomy of the ratio ((a) + (d)). A least preimage is never 2 mod 4 (φ(2m) = φ(m) for odd m). If 4 | ℓ, no Fermat prime F_s = 2^2s + 1 divides ℓ exactly once: 2^eF_s and 2^e+2s have the same φ, and the second is smaller. So R = T·W with T = 2 if 4 | ℓ and otherwise the product of F/(F−1) over Fermat primes dividing ℓ exactly once. That product is below 2: the infinite product ∏_s≥0(1 + 2^−2s) equals exactly 2, and ℓ has finitely many prime factors. W collects everything else. So T ≤ 2, #51 asks whether W is unbounded, and a 3-seed needs W > 3/2. A sieve over every n ≤ 2.5·10⁹ found the least preimage of every totient up to 10⁹. Scanning n upwards, the first hit is the least preimage. It found 139,847,905 totients, exactly V(10⁹) as counted by two other methods in the #416 tick. That count certifies coverage but not ℓ itself: the referee's mutants that scrambled ℓ kept the count. So the referee wrote a different program, a multiplicative knapsack over primes with no scan over n. It reproduces every number below at 10⁹ in 59 seconds, and its record list is byte-identical to the sieve's. It agrees with the sieve on ℓ(a) for every a ≤ 4·10⁷. Only six of the least preimages of totients up to 10⁹ are even (a = 2¹⁶·257·2^j, ℓ = 2^9+j·257², j ≤ 5). Every ratio record from a = 128 on has T = 255/128 (3·5·17) and W ≤ 1.0258 (the first two, 3 and 15, have T = 3/2 and 15/8): 47/46 at 5,888, then ×347/346, then 47/46·257/256 at 387,383,296, where 257 appears squared. The largest W below 10⁹ is 1.583664, at a = 559,789,704 with ℓ = 3³·19³·4787 and T = 1, from cubes of small primes in a value with only 2³. Small 2-adic part means few odd primes in any preimage, so prime powers get forced, but that same smallness keeps T at 1. Large T needs a large 2-adic part, and that lets the odd structure be absorbed by large primes. No case below 10⁹ has both.

The largest ratio we know: 2.044975 ((d), two instruments). Our July working report built a chain: the Fermat primes 3, 5, 17, then primes whose p−1 brings a new large prime factor, 47, 347, 1187, 1367, 5387. It reported each product as the least preimage of its φ-value. Today's branch-and-bound, written independently of the July dynamic programme, confirms all eight stages exactly. The last is ℓ(17,776,474,638,307,328) = 3·5·17·47·347·1187·1367·5387, with R = 2.0449753841 (a = 2¹²·23·173·593·683·2693). The stage before, a = 3,300,496,590,848 with R = 2.0445958, already beats every value below 1.2·10¹¹, so the next term of A393265 lies between 1.2·10¹¹ and 3.3·10¹². Appending one more safe prime does not work: for every safe prime 5,387 < p ≤ 6·10⁶ the value φ(n)·(p−1) has a cheaper preimage, typically three or four primes with ratio about 1.5 (for p = 5,399 it is 3·5387·73,623,323·120,994,817). After 17 each appended prime is a safe prime 2q + 1. Their reciprocals converge (Brun's sieve), so this mechanism alone cannot reach ∞, as the July report noted.

What is ours, and where to look for the hole. Ours: the barrier theorem in this generality and its corollaries (a; the case S = {2} is Carmichael's); the remark that Erdős's 1979 hope implies yes (a); the decomposition T ≤ 2 (a; the swaps are elementary and probably folklore); the exact smooth-family tables (d); the census split by T and W (d; its records agree with A393265); and the confirmation of the July chain (d). Not ours: the records below 1.2·10¹¹ (McCranie), the propagation lemma (Ford), the seed dichotomy (OpenAI), ℓ(2^k) = 2^k+1 beyond 31 (Carmichael), and the observation that the swaps lead to smooth-shifted-prime questions (Kovač, on the forum). Two literature searches found no earlier statement of the general barrier. They covered zbMATH, arXiv, MathOverflow, OEIS, Granville's smooth-numbers survey, the problem's thread and those of #203, #694 and #1055. They did not reach Guy's B36/B39/A18, Carmichael's 1907 paper in the original, or [Er98]. A reader who knows the barrier from somewhere else will find this sentence already saying where we did not look. The two steps a reader should check first are the claim that every prime r | m has r−1 | a_K (it holds for any preimage, since r−1 | φ(r^f) | φ(m)), and the passage from a bound on every a to a bound on infinitely many a_K in the corollaries. Two hostile AI referee seats read the claims before publication. The mathematics seat found no hole, sharpened the theorem to ℓ(a_K) = n_K, supplied Carmichael, Kovač and the 2013 citation, and corrected six sentences. Among them were a false justification offered for a true equivalence, a parenthetical about Fermat primes that could never apply, and a gloss we had put in Tao's mouth. The computation seat reproduced every number with its own programs, planted thirteen bugs, and every one that changes any output was caught by at least one check (three of the thirteen change nothing on our data), and caught the one false inequality noted above. Both reports, and what we changed, are in the bundle. The problem stays open. Artefacts: verification/51/barrier-and-anatomy.