Erdős Problem #53
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (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
Given a finite set of integers \(A\), form all sums of distinct elements of \(A\) and all products of distinct elements. Empty choices can contribute 0 to the sums and 1 to the products. Erdős Problem #53 asks whether, for every fixed positive integer \(t\), any sufficiently large set \(A\) generates at least \(|A|^t\) different numbers in the union of these two collections.
The answer is yes, established in the work of Mei-Chu Chang. The theorem concerns sums and products of different elements, not only the usual two-term sumset and product set.
A small example
Take the five-element set
Every subset has a distinct sum, so there are 32 subset-sum values, namely 0 through 31. Every subset product is a power of two, with exponents from 0 through 10, giving 11 distinct products. Exactly five of those products already occur among the subset sums. Thus the union contains
distinct integers. This is one exact calculation, not the asymptotic theorem for every large set.
What is known
Chang's The Erdős–Szemerédi problem on sum set and product set, Annals of Mathematics 157 (2003), 939–957, proves a superpolynomial lower bound for the sum of the cardinalities of the subset-sum and subset-product collections. The growth is much faster than \(|A|^t\) for every fixed \(t\). Her later paper, On sums and products of distinct numbers (2004), extends related superpolynomial results to complex sets.
There is a small but important counting step. If the two collections have \(S\) and \(P\) elements, the size of their union is at least \(\max(S,P)\), hence at least \((S+P)/2\). Therefore a source theorem yielding \(S+P>2|A|^t\) suffices for Erdős's union bound. Because Chang's bound is superpolynomial, that stronger inequality holds for sufficiently large \(|A|\). Ignoring the factor of two would leave an unjustified implication.
GCL's current state
Authenticated GCL audit #1322 source-checks Chang's theorems and gives an explicit finite powers-of-two test. It also notes a discrepancy between frozen catalogue metadata indicating external Lean work and the current public record reporting no formalization. The admitted frozen formal-provider snapshot does not contain a #53 statement, and no GCL mathematical certification is claimed.
What remains
The original problem is solved. Additional work can formalize Chang's theorem as an explicit external premise, prove the cardinality transfer, and check examples that include negative numbers, zero, and empty subsets. A finite calculation alone does not establish the result for every sufficiently large set.
Sources and claim boundaries
- Erdős Problems #53: original solved question and bibliography.
- Chang (2003), primary paper; Chang (2004).
- GCL source return #1322: bounded arithmetic and source-based theorem transfer, not GCL MathCert.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1322 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.