Erdős Problem #52
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, additive combinatorics.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
Erdős and Szemerédi ask whether addition and multiplication cannot both remain highly compressible on a large finite set of integers. For \(A=\{a_1,\dots,a_n\}\), write
The conjecture is that, for every \(\varepsilon>0\),
The original paper uses positive integers in increasing order and counts \(a_i+a_j\) and \(a_i a_j\) with \(i\le j\). Because the operations are commutative, this is exactly the same set-counting convention as the usual sumset/product-set notation.
A small example
The formulation change from positive integers to arbitrary integers is harmless asymptotically. Let \(A\subset\mathbb Z\) have \(n>1\) elements. At least one of
has at least \((n-1)/2\) elements. Call that positive set \(B\). Then \(B+B\) is either a subset of \(A+A\) or the negation of such a subset, and \(BB\subseteq AA\). Hence
A concrete example is
Its product set is
so \(|A_nA_n|=2n-1\). The off-diagonal sums \(2^i+2^j\) have distinct binary representations with two \(1\)’s, while diagonal sums are powers of two. Therefore
This example verifies directly that strong multiplicative structure forces substantial additive growth; it is illustrative, not a proof of the conjecture.
What is known
The 1983 paper defines \(f(n)\) to be the largest integer guaranteed for every \(n\)‑element positive-integer set. Its Theorem 1 proves
for positive constants \(c_1,c_2\).
The lower bound already proves genuine expansion: at least one of the two sets has more than a fixed power strictly larger than \(n\). The upper bound shows that the conjectured near-quadratic guarantee was not a trivial consequence of the number of available pairs. Erdős and Szemerédi explicitly say that the near-quadratic claim was far beyond their proof.
They also formulate higher-fold analogues involving \(k\)‑fold sums and products. Those variants are outside the exact two-operation statement audited here and should not be conflated with Problem 52.
Cushman’s 2026 arXiv revision states, for every finite \(A\subset\mathbb R\),
The exponent equals
This applies directly to integer sets because every integer set is a real set. It substantially improves the historical lower-bound exponent, but it does not approach the conjectured exponent \(2-\varepsilon\). The source is a primary author preprint; its theorem statement is evidence for the interface, not an independently checked proof.
Chang’s primary paper gives a useful extreme case: if the product set is only linear in size, then the sumset is quadratic in size. This confirms the basic rigidity principle but leaves open the difficult intermediate regime where both sets may have superlinear yet subquadratic growth.
GCL's current state
As of 2026-10-12, the maintained catalogue status is OPEN. GCL source assignment and evidence. This is an editorial source audit, not GCL proof certification or mathematical acceptance.
Source lock is ready. The original conjecture remains unresolved; the missing advance is not a single identified elementary lemma but a mechanism improving the exponent from approximately \(1.3356\) to \(2-\varepsilon\). The Cushman proof requires a separate expert audit before any certification claim.
What remains
Input. A finite nonempty \(A\subset\mathbb Z\), \(n=|A|\), and fixed \(\eta>0\).
Target. Audit and formally instantiate the Cushman statement as
Method.
- Record the exact theorem quantifiers and hypotheses from the v2 preprint.
- Specialize its finite-real-set hypothesis to \(A\subset\mathbb Z\).
- Independently verify the sign-reduction lemma above for compatibility with Erdős–Szemerédi’s positive-integer formulation.
- Check
- Compare the resulting exponent with \(2-\varepsilon\) without claiming resolution.
Acceptance test. Every theorem hypothesis must be satisfied for arbitrary finite integer \(A\); the dependence of constants on \(\eta\) must be explicit; no positivity, nonzero, or convexity assumption may be silently introduced.
Falsification hooks. Reject the interface if the primary theorem has an omitted hypothesis, if the exponent is misreported, or if its quantifier order does not yield an \(\eta\)‑dependent uniform bound.
Stopping rule. Stop after the statement-level specialization and arithmetic check, or immediately report the precise discrepancy. Do not attempt to certify the preprint proof or launch a Solve campaign.
Sources and claim boundaries
Maintained problem #52; pinned catalogue revision 536408716724a2402bdfa7c1d764bf83d64a8c89.
The original source assignment records the catalogue status as open, with last update 2026-05-28; the live problem page likewise says the page was last edited 28 May 2026. The statement is marked formalized, but formalization is not a proof or certification.
The primary source is P. Erdős and E. Szemerédi, “On sums and products of integers,” Studies in Pure Mathematics, Birkhäuser, 1983, pp. 213–218. Their Theorem 1 defines \(f(n)\) as the minimum guaranteed number of distinct pairwise sums/products and proves, for absolute \(c_1,c_2>0\),
They explicitly state the \(n^{2-\varepsilon}\) assertion as a conjecture. Original paper PDF
A primary recent source is Adam Cushman, A Note on the Sum-Product Problem and the Convex Sumset Problem, arXiv v2, revised 29 January 2026. Its stated theorem for every finite \(A\subset\mathbb R\) is
for every \(\eta>0\). Since \(\mathbb Z\subset\mathbb R\), this gives the same lower bound for the integer problem. The preprint statement was checked, but its proof was not independently audited here; it is not treated as certification. Cushman preprint
Reused only the supplied issue.json/live.html packet and publicly accessible primary mathematical sources. No sibling returns, campaign results, or cooperative evidence were inspected. No post, commit, certification, novelty claim, or award claim was made.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1321 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: DEFER_UNTIL_NEW_MECHANISM.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.