Erdős Problem #1112
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: 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
An increasing sequence is lacunary when its successive terms grow by a factor bounded away from one. Erdős Problem #1112 asks when one can construct a sequence \(A=\{a_1<a_2<\cdots\}\) whose successive gaps all lie in a fixed interval
yet whose sumset formed from \(k\) summands, denoted \(kA\), completely avoids a prescribed sufficiently lacunary sequence \(B\).
A central requirement is the correct order of quantifiers: fix \(d_1,d_2\) and \(k\), then ask whether some gap ratio \(r\) works for every sufficiently separated \(B\) by permitting a suitable \(A\) to depend on \(B\).
A small example
If every gap of \(A\) lies between \(d_1\) and \(d_2\), then telescoping gives
The set \(A\) is therefore relatively numerous, in marked contrast to a geometric sequence such as \(\{2^j\}\). Such bounded-gap sets can nevertheless have structured sumsets whose interaction with widely spaced target values is difficult to control.
For sums of two elements, Erdős and Graham described a positive avoidance construction with gaps 2 or 3 and target ratios at least two. For sums of three elements, Bollobás, Hegyvári and Jin established an obstruction for these same gap constraints, even for targets whose successive ratios can grow arbitrarily rapidly.
What is known
The maintained registry reports that the threshold for two-fold sums with gap interval \([2,3]\) equals two, while no universal ratio exists for three-fold sums with that interval. Other higher-fold and general-gap parameters remain incompletely classified. It is therefore wrong to describe the entire family as either universally true or universally false.
The registry also notes that this precise multi-parameter question is an interpretation of an ambiguous remark in the original Erdős–Graham discussion; its historical provenance is less exact than many numbered Erdős statements.
GCL's current state
Source audit #2383 identifies the already-negative parameter triple, the elementary bounded-gap counting estimates and the original-source ambiguity. It does not claim an independent replay of the 1997 proof or a result across every remaining parameter regime.
What remains
Develop an accurately sourced classification of those \((d_1,d_2,k)\) for which a uniform avoidance ratio exists, while separating proven positive and negative cases. Resolving the original Erdős–Graham wording would also improve historical reliability.
Sources and claim boundaries
- Erdős Problems #1112, revision history: OPEN family with a known negative special case and historical qualifications.
- Bollobás–Hegyvári–Jin (1997), as cited by the registry for the negative threefold-sum specialization; primary pages not independently checked.
- GCL source return #2383: parameter normalization and finite gap lemma; no general theorem certification.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2383 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: HOLD_STATUS_RECONCILIATION.
- 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.