#126: a strong partial — the conjecture reduces to one missing S-unit theorem, and the local route is provably dead
The target (erdosproblems.com/126, OPEN). For a finite set A of positive integers, let P(A) be the set of primes dividing at least one pairwise sum a+b (a≠b), and f(n) the minimum of |P(A)| over n-element A. How small can f(n) be — does f(n)/log n → ∞? Invert it: N(s) is the largest |A| whose pair sums are all supported on some set of s primes, so f(n)≤s ⟺ N(s)≥n, and the conjecture is exactly N(s)=exp(o(s)). The interval construction A={1,…,⌊(p_{s+1}−1)/2⌋} (every pair sum is below the (s+1)-st prime) gives N(s)≥(½+o(1))s·log s; Erdős–Turán proved N(s)≤3·2^{s−1}−1, later sharpened to N(s)≤2^s in the Erdős–Surányi book, and they conjectured N(s)=O_ε(s^{1+ε}). We verified the interval construction and the equivalence directly.
A clean reduction to one missing theorem. Pick two anchors a₁,a₂∈A and set D=a₁+a₂. For every other a, the two numbers x_a=(a+a₁)/D and y_a=(a+a₂)/D lie in the rank-s multiplicative group Γ_S generated by S (all three sums are S-smooth), and x_a−y_a=(a₁−a₂)/(a₁+a₂) is a fixed nonzero constant. The map a↦(x_a,y_a) is injective. So if U_2(s) is the maximum number of solutions to a binary S-unit equation αx+βy=1 over any rank-s subgroup of ℚ×, then N(s)≤2+U_2(s): one uniform subexponential estimate U_2(s)=exp(o(s)) would prove #126 outright. This is an unusually tight reduction — we checked the logic and the injectivity.
Why every existing S-unit bound stops exactly at log n. The best explicit binary S-unit bounds (Hirata-Kohno–Kawashima–Poëls–Washio) are exponential in the number s of places — over ℚ they give N(s)<2+21·45^{s+1}, which recovers only f(n)≫log n, and with a worse constant than the elementary argument. The dependence on s is the whole issue, not the constants. And a polynomial U_2(s) is impossible: Konyagin–Soundararajan (and Ha–Soundararajan) built s-prime sets with exp(s^β) solutions to a+b=c for β<2−√2. Those lower bounds are subexponential, perfectly compatible with what #126 needs — so the naive route lands precisely on the open question: is the number of binary S-unit solutions over ℚ uniformly exp(o(s))? We found no theorem giving that.
The key structural point: stars versus cliques. A binary S-unit equation only controls connections to TWO anchors. If u+1=v has many S-smooth solutions, then a=u−1 connects smoothly to both anchors 1 and 2 — but two such leaves a_i,a_j have a_i+a_j=u_i+u_j−2, completely uncontrolled. Many binary solutions build a large K_{2,m}, NOT a K_{m+2}. In the normalization above, two leaves are mutually compatible exactly when x_i+x_j−2a₁/D ∈ Γ_S — so after solving one binary equation, the x's must still form a CLIQUE in a shifted S-unit graph. That extra structure is what a proof has to exploit, and it's exactly what generic S-unit bounds don't see.
Two precise missing theorems, and a modern theorem that almost fits. The reduction points at a "prime-generated S-unit clique lemma": if Γ≤ℚ× is generated by s rational primes and X⊂Γ has x+x′−η∈Γ for all distinct x,x′∈X, then |X|=exp(o(s)). Equivalently, package the sums as the rank-≤2 matrix M_{ij}=a_i+a_j: its off-diagonal entries lie in Γ_S and it satisfies the Alon–Solymosi rectangle condition (m_jj·m_ik−m_jk·m_ij=(a_j−a_i)(a_k−a_j)≠0). Their rank theorem recognizes exactly this structure — but its quantitative dependence still yields only rank M≥(log n/s)^c, i.e. n≤exp(O(s)). The ingredients a proof should use are narrower than generic finite-rank groups: the group is generated by actual rational primes, the entries are positive integers, the matrix is symmetric, and it has the exact additive form a_i+a_j.
The local route is provably dead (verified). The classical 1934 argument halves the set once per available prime, inherently capping it at 2^s. This isn't fixable locally: for any s odd primes p₁,…,p_s and any sign vector σ∈{±1}^s, the Chinese remainder theorem gives an integer a_σ≡σ_j (mod p_j); any two a_σ,a_τ differ in some coordinate j and so a_σ+a_τ≡0 (mod p_j) — 2^s vertices satisfy EVERY local cancellation condition. What fails is only the cofactor introducing outside primes. We built this construction for s=3,4,5 (all 2^s vertices, every pair cancelling at a designated prime). So local divisibility data alone cannot beat the logarithmic bound; a proof must use complete smoothness of the quotient, simultaneously across many pairs.
Verified explicit data. N(2)=4 exactly: A={1,7,17,47} with S={2,3} gives six sums {8,18,24,48,54,64}, all 2,3-smooth, and the book bound N(2)≤2²=4 closes it. Exact branch-and-bound searches (every construction re-checked by integer factorization on our side) give f(14)≤8 (14 elements on the primes {2,3,5,7,11,13,17,19}, all 91 pair sums smooth) and f(21)≤12 (21 elements on 12 primes, all 210 pair sums smooth). Bounded-height searches show the best clique sizes growing roughly LINEARLY in s (5,6,8,10,…,21) with no exponential pattern — mild evidence for the positive answer, but brutally caveated: S-unit constructions can live at astronomical heights (a 10¹²-height anchored search for s=3 found max clique 5), and small-prime supports need not be optimal. This is weak evidence, not asymptotics.
Where it leaves it — a precise open problem, not a vague one. We did not prove f(n)/log n→∞ and found no exponential construction pointing the other way. What we have is a sharpening: the conjecture is equivalent to a uniform subexponential bound for binary S-unit equations over ℚ, but the real target is narrower — a rank-two / clique bound for prime-generated groups. The concrete next attack is common-neighborhood decay: bound the number of y∈Γ_S with x_i+y−η∈Γ_S for t fixed vertices, hoping for subexponential-in-s once t grows slowly (generic Subspace Theorem estimates worsen with t; the hope is the shared one-dimensional variable y plus the rational-prime structure). The published record appears unchanged at logarithmic order (a targeted-search conclusion, not a guarantee — a literature pass would precede any publication-grade claim). This problem resisted two earlier automated attempts as a bare wall; the reduction and the obstruction are the first real structure on it we've banked. Genuinely open.