Erdős #126 — must Σ prime factors of Π(a+b) beat log n?

Statement

Let $f(n)$ be maximal such that if $A\subseteq\mathbb{N}$ has $|A|=n$ then $\prod_{a\neq b\in A}(a+b)$ has at least $f(n)$ distinct prime factors. Is it true that $f(n)/\log n\to\infty$?

Facts

- Prize $250; status per erdosproblems.com/126 (site-owner belief, verified by direct fetch 2026-07-02): OPEN, explicitly flagged "cannot be resolved with a finite computation." - Falsifiable: no in the finite-computation sense — the question is an asymptotic ($n\to\infty$) growth-rate claim, so no single finite $A$ can settle it either way; a genuine proof or a genuine construction-with-proof (showing $f(n)=O(\log n \cdot \text{polylog})$, i.e. that the ratio does *not* diverge) is needed. - Origin: #126 : [ErTu34] [Er95c] [Er97] [Er97e]. [ErTu34] = P. Erdős & P. Turán, "On a Problem in the Elementary Theory of Numbers," Amer. Math. Monthly 41 (1934), 608–611 — their first joint paper, prompted by a question of Lázár and Grünwald. [Er95c]/[Er97]/[Er97e] are later Erdős problem-list restatements (Octogon Math. Mag. 1995; New Zealand J. Math. 1997; Math. Japonica 1997) repeating the same open question without new results. - Known results / best bounds (all verified): - Erdős–Turán 1934 [ErTu34]: $\log n \ll f(n) \ll n/\log n$. The upper bound is trivial (take $A=\{1,\ldots,n\}$: all pairwise sums lie in $[3,2n-1]$, and the number of distinct primes up to $2n$ is $\Theta(n/\log n)$ by PNT). The precise classical statement (as restated by Füredi–Gyarmati, arXiv:2602.07545, who read and cite it): if $|A|\geq 3\cdot 2^{k-1}$ then $\omega\!\left(\prod_{a\neq b\in A}(a+b)\right)\geq k+1$, giving $f(n)\gg\log_2 n$. - Erdős & Surányi, *Topics in the Theory of Numbers* (Springer, 2003 English ed.) [cited as ref [3] in arXiv:2602.07545]: sharpened the same-order lower bound to hold already for $|A|\geq 2^k+1$ — a better constant, same $\Theta(\log n)$ order. No order-of-growth improvement. - Győry, Stewart & Tijdeman, "On prime factors of sums of integers I," Compositio Math. 59 (1986), 81–88 (numdam.org/item/CM_1986__59_1_81_0): generalized to two different sets — for $A,B\subseteq\mathbb Z^+$ finite, $|A|\geq|B|\geq2$, $\omega\!\left(\prod_{a\in A,b\in B}(a+b)\right)\geq c\log|A|$ for an effectively computable $c>0$. Their proof draws on Baker's theory of linear forms in logarithms (the citing-paper list at numdam.org confirms Baker's "The theory of linear forms in logarithms" (1977) as a cited input) — i.e. effective bounds on Diophantine/S-unit-type equations, not the purely combinatorial Erdős–Turán argument. - Erdős, Stewart & Tijdeman, "Some diophantine equations with many solutions," Compositio Math. 66(1) (1988), 37–56: show the Győry–Stewart–Tijdeman bound is close to sharp — for any $\varepsilon>0$ and large $k$, there exist $A,B$ with $|A|=k$, $|B|=2$, and $\omega\!\left(\prod_{a\in A,b\in B}(a+b)\right) < (1/8+\varepsilon)(\log|A|)^2\log\log|A|$, i.e. an explicit constructive upper bound in the two-set case only polylog above the $c\log|A|$ lower bound. - Győry, Sárközy & Stewart, "On the number of prime factors of integers of the form $ab+1$," Acta Arith. 74 (1996), 365–385: a Diophantine lemma (S-unit-equation flavor) later reused (Füredi–Gyarmati, 2026) to extend the $\log|A|$-order lower bound to $\omega\!\left(\prod_{a\in A,b\in B}f(a,b)\right)$ for a specific class of two-variable polynomials $f\in\mathbb Z[x,y]$. - Füredi & Gyarmati, "Erdős–Turán Theorem and Eulerian Integers," submitted to Acta Arithmetica, arXiv:2602.07545 (7 Feb 2026, read in full): the most recent work in this exact line. They prove the Erdős–Turán-type $\log|A|$-order lower bound in the ring of Eulerian (Eisenstein) integers $E=\{a+b\omega: a,b\in\mathbb Z\}$, $\omega=e^{2\pi i/3}$, for $\omega_E\!\left(\prod_{a\neq b\in A}(a+\rho b)\right)$, any $\rho\in E$ — "our proof utilizes the Law of Cosines alongside the method of Erdős and Turán" (their own words, confirming the classical technique is reused/adapted, not superseded). Via the multiplicative norm $N(a+b\omega)=a^2-ab+b^2$, they derive matching $\Theta(\log|A|)$-order lower bounds for $\omega_{\mathbb N}\!\left(\prod(a^2\pm ab+b^2)\right)$ over rational integers, and pose (their Conjecture 1) a general two-variable-polynomial, two-set version of the Győry–Stewart–Tijdeman theorem, proving it for one special polynomial family (their Theorem 3). They do not address, mention, or improve the order-of-growth question of #126 itself — the paper is entirely about extending the $\log|A|$ lower-bound machinery to new algebraic domains and polynomial families, not about whether $f(n)/\log n\to\infty$ for the original integer self-sumset. - Formalized: Yes — erdosproblems.com marks "Formalised statement? Yes," confirmed via google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/126.lean (statement-only formalization, no proof). - Related problems: no other erdosproblems.com-numbered problem cites [ErTu34] (confirmed via /search_bib/ErTu34, which lists only #126). Checked #125 directly — unrelated (digit-representation sumset density question). No numbered "See also" links appear on the page.

Literature state

Not resolved, and — unusually for a 90-year-old problem — still an active research seam, but the activity is orthogonal to the specific question asked. The core Erdős–Turán bound $\log n\ll f(n)\ll n/\log n$ has stood since 1934, with only a constant-factor sharpening (Erdős–Surányi book) in the interim. The genuinely new activity (Győry–Stewart–Tijdeman 1986, Erdős–Stewart–Tijdeman 1988, Győry–Sárközy–Stewart 1996, and as recently as Füredi–Gyarmati, Feb 2026) consistently generalizes the $\Theta(\log|A|)$-order lower bound to two-set versions, polynomial families, and new number rings (Eisenstein/Eulerian integers) — every one of these papers reproduces or reuses the *same order of growth* ($\log|A|$), never breaking through toward $n/\log n$ or even establishing $f(n)=\omega(\log n)$ for the original single-set problem. No paper found addresses $f(n)/\log n\to\infty$ or its natural weaker cousin $f(n)=o(n/\log n)$ (which Erdős himself, per [Er95c]/[Er97]/[Er97e], says "has never been proved, but perhaps never seriously attacked"). No AI/LLM involvement found: the github.com/teorth/erdosproblems "AI contributions to Erdős problems" wiki page, fetched and grepped in full for "[126]", has zero matches, despite listing dozens of other problems (numbered in the 1000s+) resolved by Aristotle (Harmonic), AxiomProver, and others as recently as June 2026. The 2026-04 OpenAI "Short proofs in combinatorics, probability and number theory II" (arXiv:2604.06609) resolves a different Erdős–Turán-named problem (the discrepancy-theory one, unrelated) — confirmed by reading its abstract, not #126.

Attack surface

- Mode: derivation (literature-resolution turned up nothing; this needs either a genuine new lower-bound proof pushing past $\log n$, or a genuine new construction+proof pinning $f(n)=\Theta(\log n)$-ish, which would *disprove* the "$\to\infty$" claim). Not finite-search — the site is explicit that no finite computation settles this. - Concrete first experiment (derivation, not computation): the most promising lead from the literature is the Erdős–Stewart–Tijdeman 1988 tightness-construction technique (Compositio Math. 66(1), 37–56) — they build explicit two-set examples $A,B$ ($|B|=2$) whose pairwise-sum product is unusually "prime-factor-poor," using S-unit-equation / restricted-prime-factor number constructions. The open derivation question: can that construction technique be adapted from the two-set case ($|B|=2$ fixed) to the single self-set case of #126 to build $A$, $|A|=n$, with $\omega\!\left(\prod_{a\neq b\in A}(a+b)\right) = O(\text{polylog } n)$ (ideally $O(\log n)$)? A successful adaptation would answer #126 in the negative (disprove $f(n)/\log n\to\infty$) and would be a real, citable contribution even if it only reaches a weaker polylog bound. Symmetrically: try to adapt the Füredi–Gyarmati Eisenstein-integer / Law-of-Cosines sector argument (arXiv:2602.07545) back to sharpen the *lower* bound for the plain integer self-sumset case — their six-60°-sector splitting technique is a genuine structural generalization of the original Erdős–Turán dyadic argument and has not yet been pushed for an order-of-growth improvement (only for new algebraic domains). - Oracle: none mechanical — any progress here is a proof (upper-bound construction or lower-bound theorem), verified by ordinary mathematical refereeing/formalization, not by computation. A partial computational sanity-check is possible: for moderate $n$ (say $n\leq 40$–$60$), search over structured candidate sets $A$ (e.g. sets built from a single prime power's residues, or from Sidon/GCD-graph-style constructions used elsewhere in this wiki) to see whether $\omega(\prod(a+b))$ can be pushed suspiciously close to $c\log n$ for small $c$ — this cannot prove the conjecture false, but a "surprisingly poor" empirical family would motivate exactly the derivation direction above, and matches how the extremal examples in Erdős–Stewart–Tijdeman 1988 were originally found (explicit residue/prime-power constructions). - Feasibility: honest read: hard, but genuinely under-attacked — the recommended posture is derivation-by-analogy from very recent (2026) live literature, not blind search. This is not a problem where decades of failed serious attempts prove intractability; Erdős's own remark that $f(n)=o(n/\log n)$ was "perhaps never seriously attacked" is corroborated by the fact that every post-1934 paper in this exact citation family (1986, 1988, 1996, 2026) generalizes the *setting* (two sets, new rings, polynomials) rather than sharpening the *order* for the original single-set problem. The 2026 Füredi–Gyarmati paper is evidence the underlying techniques (Baker-style effective bounds, Eisenstein-integer factorization/sector arguments) are still being actively developed by working number theorists as of this year — a well-informed reading of that paper plus the 1988 tightness-construction paper is the highest-leverage next step, not a blind computational search.

Related

- concept/erdos-turan-prime-factors-theorem — the classical 1934 dyadic/pigeonhole method proving $\log n\ll f(n)$; explicitly reused ("the method of Erdős and Turán") by Füredi–Gyarmati 2026 for the Eisenstein-integer generalization - solved/gyory-stewart-tijdeman-two-set-prime-factors — 1986 two-set generalization ($\omega\geq c\log|A|$), technique: Baker's linear-forms-in-logarithms / effective Diophantine bounds, not the elementary Erdős–Turán argument - solved/erdos-stewart-tijdeman-tightness-construction — 1988 explicit construction showing the two-set log-bound is close to sharp; the adaptation target for a possible #126 disproof - solved/erdos-turan-eulerian-integers — Füredi & Gyarmati, arXiv:2602.07545 (Feb 2026): extends the $\log|A|$-order bound to Eisenstein integers and quadratic forms $a^2\pm ab+b^2$ via a six-sector Law-of-Cosines argument; most recent live work in this exact citation family - concept/baker-linear-forms-in-logarithms — transcendence-theoretic effective bound machinery underlying the Győry–Stewart–Tijdeman line of results - concept/s-unit-equations — restricted-prime-factor Diophantine equations, the tool behind both the GST two-set lower bound and the ETS tightness construction - concept/eisenstein-integers-unique-factorization — the ring $\mathbb Z[\omega]$ and its norm-multiplicativity, used in the 2026 generalization - concept/effective-diophantine-bounds — Győry–Sárközy–Stewart 1996 lemma on prime factors of $ab+1$, reused for polynomial generalizations