Erdős Problem #748
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: number theory.
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
Let f(n) count sum-free subsets A of {1,...,n}: there are no x,y,z∈A with x+y=z, including cases x=y. Cameron–Erdős asked whether f(n)=2^{(1+o(1))n/2}. The answer is PROVED; independent work of Sapozhenko and Green gives the stronger f(n)∼c_{n mod 2} 2^{n/2}, with two parity-dependent positive constants. One must distinguish number of subsets from maximum size of one sum-free set.
A small example
Any subset of the upper half {floor(n/2)+1,...,n} is sum-free: for x,y in that half, x+y>n. Therefore f(n)≥2^{ceil(n/2)}. At n=4 the upper-half set {3,4} yields four sum-free subsets, though other sum-free subsets also exist. The lower bound alone does not establish the asymptotic count.
What is known
Erdős and Cameron conjectured the asymptotic exponent. Green [Gr04] and Sapozhenko [Sa03] independently proved an upper f(n)=O(2^{n/2}), with parity-refined leading constants c_even,c_odd for f(n)/2^{n/2}. The maintained page warns that counting maximal sum-free sets is a SEPARATE problem (#877); applying these counts to maximal families would be invalid. Original journal proofs not reconstructed here.
GCL's current state
The authenticated original source return remains in its original BOUNDED_TASK_DESIGNED state. This is an editorially reviewed explanatory article in protected EC-BULK-005-R7, subject to that PR's protected merge. Original research theorem proofs and any external formalizations are attributed to their authors, not newly GCL-certified. The historical source and proof-review limitations recorded in the return remain applicable.
What remains
ERDOS-748-SUM_FREE_COUNT. Enumerate all subsets for n≤16 with exact x+y=z checks (including doubled x=y), compare with 2^{ceil(n/2)} lower and parity effects, then source-check the Green and Sapozhenko container/entropy proof interface. No new asymptotic claim from finite enumeration.
Sources and claim boundaries
Maintained Problem #748; original GCL issue return. Full historical proof papers and external Lean kernels unreviewed. no independent theorem proof certification.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2019 — 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.