Erdős #52 — the sum-product problem for integers

Statement

Let $A$ be a finite set of integers. Is it true that for every $\epsilon>0$ $$\max(\lvert A+A\rvert,\lvert AA\rvert)\gg_\epsilon \lvert A\rvert^{2-\epsilon}?$$ (I.e. is the sum-product exponent for $\mathbb{Z}$ equal to $2$: either the sumset or the productset of a finite set of integers must be almost as large as it can possibly be, $\lvert A\rvert^{2-o(1)}$?)

Facts

- Prize \$250; status open on erdosproblems.com/52, explicitly marked "cannot be resolved with a finite computation" (site-owner belief) — the exponent question is asymptotic over all $\lvert A\rvert$. - Falsifiable: no — a finite counterexample only disproves a *specific* exponent claim asymptotically as $\lvert A\rvert\to\infty$; the conjecture itself needs a genuine proof (or an infinite-family disproof, as has now happened for the real/complex analogue — see below). - Origin: Erdős and Szemerédi, "On sums and products of integers" [ErSz83], Studies in Pure Mathematics (1983), 213–218 (MR 820223); restated in [Er77c] [Er80,p.112] [ErGr80] [Er91] [Er92c] [Er95] [Er97] [Er97e] [Va99,1.26]. - Known bounds for $\mathbb{Z}$/$\mathbb{R}$ (the exponent $1+c$ in $\max(\lvert A+A\rvert,\lvert AA\rvert)\gg\lvert A\rvert^{1+c-o(1)}$, per thomasbloom.org/notes/sumproduct.html, cross-checked numerically): - Erdős–Szemerédi 1983 [ErSz83]: first non-explicit $c>0$, plus a matching-shape upper bound $\lvert A\rvert^2\exp(-c\log\lvert A\rvert/\log\log\lvert A\rvert)$. - Nathanson 1997: $c=1/31$; Chen 1999: $c=1/5$; Elekes 1997: $c=1/4$ (via the Szemerédi–Trotter incidence theorem — the historically first strong exponent, opened the incidence-geometry route); Solymosi 2005: $c\approx0.2727$; Solymosi 2009 ("Bounding multiplicative energy by the sumset," Adv. Math., MR 2538014) [So09d]-style elementary geometric (no Szemerédi–Trotter) argument pushed $c=1/3$, i.e. exponent $4/3$ — long the reference bound; then Konyagin–Shkredov 2015/2016, Shakan 2019, Rudnev–Stevens 2022, Bloom 2025 (arXiv:2501.09470, "Control and its applications in additive combinatorics" [Bl25]) incrementally pushed $c$ up to $1270/951\approx1.33543-1=0.33543$. - Current record: Adam Cushman, "A Note on the Sum-Product Problem and the Convex Sumset Problem," arXiv:2512.13849 [Cu25] (2025) — exponent $4/3+10/4407=1962/1469-o(1)\approx1.3356$ for both integers and reals; verified numerically identical fractions. - Full sourced table of the exponent history (Nathanson→Cushman) at http://thomasbloom.org/notes/sumproduct.html, citing a 2016 Granville–Solymosi survey [GrSo16] for proof-technique overviews. - Complex numbers / quaternions: exponent $4/3+c$ (non-explicit $c>0$), Basit & Lund, "An improved sum-product bound for quaternions," SIAM J. Discrete Math. (2019) [BaLu19], MR 3974028. - Finite fields $\mathbb{F}_p$ (assuming $\lvert A\rvert<p^{c'}$): current record exponent $5/4+o(1)$, Mohammadi & Stevens, "Attaining the exponent $5/4$ for the sum-product problem in finite fields," Int. Math. Res. Not. (2023) [MoSt23], MR 4565644. (Garaev showed some size restriction is necessary, via $A\subseteq\mathbb{F}_p$, $\lvert A\rvert=N$ with $\max(\lvert A+A\rvert,\lvert AA\rvert)\ll p^{1/2}N^{1/2}$.) - Higher-fold generalization ($m\geq2$: $\max(\lvert mA\rvert,\lvert A^m\rvert)\gg\lvert A\rvert^{m-o(1)}$), conjectured by Erdős–Szemerédi [ErSz83] and Erdős [Er91]: DISPROVED for $A\subset\mathbb{R}$ by Bloom, Sawin, Schildkraut, Zhelezov, "The sum-product conjecture is false for real numbers," arXiv:2605.28781 [BSSZ26] (27 May 2026) — for any $k\geq3$ they build arbitrarily large $A\subset\mathbb{R}$ with $\max(\lvert kA\rvert,\lvert A^{(k)}\rvert)\leq\lvert A\rvert^{C\log k/\log\log k}$. - Related problems (per erdosproblems.com "See also"): erdos/53 — a *weaker* consequence of #52 (for every $k$, eventually $\gg\lvert A\rvert^k$ integers are sum-or-product of distinct elements), asked by Erdős–Szemerédi [ErSz83], and SOLVED by Mei-Chu Chang, "The Erdős–Szemerédi problem on sum set and product set," Annals of Math. (2003) [Ch03]. erdos/808 — a *stronger* graph-restricted version ("for any dense enough graph $G$ on $A$, restricted sums/products along $G$ still explode"), DISPROVED by Alon, Ruzsa, Solymosi, "Sums, products, and ratios along the edges of a graph," Publ. Mat. (2020) [ARS20], MR 4047560 — they exhibit $G$ with $\gg n^{5/3-o(1)}$ edges yet $\max(\lvert A+_GA\rvert,\lvert A\cdot_GA\rvert)\ll\lvert A\rvert^{4/3+o(1)}$ (they do prove the general lower bound $\gg m^{3/2}n^{-7/4}$ in terms of edge count $m$). erdos/818 — a special case (if $\lvert A+A\rvert\ll\lvert A\rvert$ then $\lvert AA\rvert\gg\lvert A\rvert^2/(\log\lvert A\rvert)^C$), SOLVED by Solymosi, "Bounding multiplicative energy by the sumset," Adv. Math. (2009) [So09d] in the strong form $\lvert AA\rvert\gg\lvert A\rvert^2/\log\lvert A\rvert$. - Sequence OEIS A263996: smallest possible cardinality of the union of pairwise sums and products from a set of $n$ positive integers (exact small-$n$ values, e.g. $n=10\to30$, $n=11\to34$, per Bui, Clevenger et al. arXiv:2601.21828 "The sum-product problem for small sets II," extending Clevenger–Havard–Heard–Lott–Wilson for $k\leq9$). - Formalized in Lean: yes — google-deepmind/formal-conjectures/FormalConjectures/ErdosProblems/52.lean (statement present per erdosproblems.com; not independently inspected for sorry status in this pass).

Literature state

Not resolved for the stated integer case — the core conjecture $\max(\lvert A+A\rvert,\lvert AA\rvert)\gg_\epsilon\lvert A\rvert^{2-\epsilon}$ for $A\subset\mathbb{Z}$ remains open, with the best lower-bound exponent stuck at $\approx1.3356$ (Cushman 2025, arXiv:2512.13849) against the target $2$ — essentially unmoved in shape since Erdős–Szemerédi 1983, only the constant $c$ in $1+c$ has crept up (Elekes $1/4$ → Solymosi $1/3$ → ... → Cushman $\approx0.3356$), a research program spanning >40 years and dozens of papers.

Major recent development — the analogous conjecture is FALSE for reals. On 27 May 2026, Thomas Bloom, Will Sawin, Carl Schildkraut, and Dmitrii Zhelezov posted "The sum-product conjecture is false for real numbers," arXiv:2605.28781 [BSSZ26], constructing arbitrarily large $A\subset\mathbb{R}$ (elements = algebraic integers in a number field of degree $\asymp\log\lvert A\rvert$) with $\max(\lvert A+A\rvert,\lvert AA\rvert)\leq\lvert A\rvert^{2-c}$ for an absolute constant $c>0$, and simultaneously disproving the higher-fold "many sums and products" conjecture. This is confirmed directly by Thomas Bloom in the erdosproblems.com/forum/discuss/52 thread (comment, 06 Jun 2026): the disproof stands, and — crucially — the site's problem-52 remarks now explicitly state "the original conjecture is false for sets of reals" and that "there is likely nothing special about the integers." The integer case (i.e. the literal statement of #52) is left untouched and open — the reals/complex construction relies on algebraic-integer structure (units, discriminants, class-field towers) unavailable to plain rational integers, so this does not resolve #52 itself, but it strongly clarifies that #52's truth (if true) must depend on arithmetic structure specific to $\mathbb{Z}$, not a generic "additive vs. multiplicative energy" trade-off — a significant conceptual narrowing.

AI-system involvement (documented, from the forum thread, erdosproblems.com/forum/discuss/52): - The BSSZ26 real-number disproof states in its own introduction (per erdosproblems.com discussion) that the authors "were inspired to revisit the possibility of disproving the sum-product conjecture ... by the recent OpenAI counterexample to the unit distance conjecture" — i.e. Erdős Erdős #90 — the unit distance conjecture (disproved 2026) — see Alon, Bloom, Gowers, Litt, Sawin, Shankar, Tsimerman, Wang, Wood, "Remarks on the disproof of the unit distance conjecture," arXiv:2605.20695 (20 May 2026), a short human-verified digest of an OpenAI-generated construction disproving Erdős #90's $n^{1+O(1/\log\log n)}$ upper-bound conjecture, using ideas "attributed to Ellenberg–Venkatesh, Golod–Shafarevich, and Hajir–Maire–Ramakrishna" (class-field-tower / algebraic-number-theory machinery). BSSZ26 note their own construction "required far less number theoretic input." - Independently, around 4–6 June 2026, both Anthropic ("Claude Mythos," per Nat Sothanaphan's forum post, 04 Jun 2026) and OpenAI (GPT-5.5, via a shared chat referenced by Boris Alexeev) separately produced disproofs of the *real* case. Thomas Bloom confirmed directly in the thread (06 Jun 2026): "Both the Anthropic and OpenAI proofs you link to are correct, and essentially the same (except for cosmetic differences) as the construction we gave in [BSSZ26]" — i.e. both AI systems independently rediscovered the human result post-publication, not a novel result. (Some process concerns were raised in the thread about OpenAI's public framing/verification transparency around this.) - Separately, "old-bielefelder" reports using ChatGPT 5.5 (long-thinking) unassisted to *improve* the explicit small constant $c$ in BSSZ26's real-number disproof from $c=0.00000089$ (as sketched by the human authors) to $c=0.000719$ — a genuine, if narrow, LLM-driven quantitative improvement to a real theorem, confirmed by Thomas Bloom in-thread. - No AI system is credited anywhere in the sources found with progress on the still-open *integer* case (#52 as literally stated), nor on the lower-bound exponent-race for $\mathbb{Z}/\mathbb{R}$ (Elekes→Solymosi→...→Cushman), which remains pure human incidence-geometry/additive-energy work.

Attack surface

- Mode: literature-resolution + derivation (not finite-search — asymptotic over all $\lvert A\rvert$, explicitly flagged non-finite by the site). - Concrete first experiment: this is not directly finite-searchable, but two scoped sub-experiments are: (1) study whether the BSSZ26 algebraic-integer / number-field construction (arXiv:2605.28781) has *any* residue when restricted to $A\subset\mathbb{Z}$ — i.e. formally check (a small, well-defined lemma-chase) exactly which step requires non-rational algebraic integers, to sharpen the informal "why $\mathbb{Z}$ should behave differently from $\mathbb{R}$" intuition into a citable obstruction; (2) push the small-case exact computation (OEIS A263996 / arXiv:2601.21828 SAT/ILP style search, currently at $n=11$) one or two steps further to look for structural hints in the extremal near-geometric-progression sets, feeding SAT/CP-SAT-based finite counterexample search and verification machinery already used elsewhere in this wiki. - Oracle: none for the asymptotic conjecture itself (not finite); for the sub-experiments — exact small-$n$ computation is directly checkable against OEIS A263996, and a Lean formalization of the BSSZ26 "why not $\mathbb{Z}$" obstruction either compiles or doesn't. - Feasibility: honest read — famous, hard, and a 40+ year exponent-race with world-class incidence-geometry specialists actively working it (the erdosproblems.com forum shows Terence Tao, Thomas Bloom, and others "currently working on this problem" as of the fetch date). Direct resolution is far out of reach. The one clearly tractable, high-value contribution in reach is *not* the exponent race itself, but formalizing/tracking the BSSZ26 real-number disproof and its stated inspiration chain (unit-distance Erdős #90 — the unit distance conjecture (disproved 2026) disproof → sum-product-for-reals disproof), since this is exactly the kind of "derivation across analogous problems via shared number-theoretic machinery" this wiki is built to catalogue — and it is the one place in this problem's history where AI systems (OpenAI, Anthropic) have documented, human-confirmed involvement, making it a natural test case for our own derivation pipeline.

Related

- erdos/53 — weaker consequence of #52 (density of sum-or-product values), SOLVED by Chang 2003 [Ch03] via Freiman-type sumset-structure arguments — a template for "prove the weaker corollary first" as a route into #52's structure. - erdos/808 — strengthened, graph-restricted version of #52, DISPROVED by Alon–Ruzsa–Solymosi 2020 [ARS20] — shows the "always sum-product growth" intuition breaks once you allow adversarial restriction of which pairs are summed/multiplied; a cautionary analog for how additive/multiplicative structure can be locally decoupled. - erdos/818 — special case of #52 (small sumset forces large productset), fully SOLVED by Solymosi 2009 [So09d] using the elementary geometric multiplicative-energy argument that also gave the long-standing $4/3$ exponent record for the main problem — the single most directly reusable "winning technique" adjacent to #52. - Erdős #90 — the unit distance conjecture (disproved 2026) — the unit distance problem; its 2026 AI-assisted disproof (arXiv:2605.20695, algebraic-number-field/class-field-tower construction) directly *inspired* BSSZ26's real-number sum-product disproof (arXiv:2605.28781) — the clearest documented case of technique-transfer between two Erdős problems in this dataset. - Incidence geometry: Szemerédi–Trotter theorem, the crossing lemma, and Zarankiewicz-type bounds — Szemerédi–Trotter-based route (Elekes 1997) that first broke exponent $1+1/4$; superseded but foundational. - concept/multiplicative-energy-geometric-argument — Solymosi's elementary (no Szemerédi–Trotter) geometric bound on multiplicative energy by the sumset [So09d], giving exponent $4/3$ and fully solving erdos/818; the ancestor of the current $c\approx0.3356$ record chain (Konyagin–Shkredov, Shakan, Rudnev–Stevens, Bloom, Cushman). - Unbounded-degree number-field grids via infinite class-field towers (Golod–Shafarevich + point-counting) — large-degree number-field / algebraic-integer constructions (Golod–Shafarevich class-field towers, Ellenberg–Venkatesh point-counting, Hajir–Maire–Ramakrishna tame towers) used to disprove both the unit-distance conjecture Erdős #90 — the unit distance conjecture (disproved 2026) and the real/complex sum-product conjecture [BSSZ26]; the key open question for #52 is whether any residue of this technique constrains or illuminates the integer case. - SAT/CP-SAT-based finite counterexample search and verification — proposed mechanism for extending exact small-$n$ computation of OEIS A263996 (currently $n\leq11$, arXiv:2601.21828) to look for extremal structure hints. - Lean 4 formalization of constructions and conditional reductions (Erdős-problem context) — google-deepmind/formal-conjectures project; #52 has a Lean statement per erdosproblems.com, a concrete target for tracking/formalizing the BSSZ26 real-case disproof and its non-applicability to $\mathbb{Z}$.