Skip to content

Erdős Problem #362

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

Erdős Problem 362 asks how often a finite set can repeat a subset sum. Let \(A\) be a finite set of \(N\) distinct natural numbers, let \(t\) be a target, and count the subsets \(S\) of \(A\) whose elements add to \(t\). There are \(2^N\) subsets altogether, but the question asks for a uniform upper bound on the largest fibre of the sum map: how many different subsets can land on the same target?

The first assertion predicts the scale \(2^N/N^{3/2}\), with a constant independent of both \(A\) and \(t\). The second assertion asks for the same kind of estimate after restricting to subsets of one prescribed size \(l\), with the stronger scale \(2^N/N^2\) and a constant independent of \(l\) and \(t\). These are concentration questions: the more spread out the available numbers are, the fewer subsets should share a sum, while an unusually structured set can create a large central fibre.

The original issue for this audit is MATH-PROGRAMME #1632, assignment ERDOS-CATALOGUE-0362-S01.

A small example

Take \(A={1,2,3,4}\) and \(t=5\). Exact enumeration gives

\[ \{S\subseteq A:\sum_{n\in S}n=5\}=\{\{1,4\},\{2,3\}\}. \]

Thus the unrestricted fibre has size \(2\). The two-element fibre is the same two sets, also of size \(2\). A direct finite check, using only integer addition and enumeration, produced the list [(1, 4), (2, 3)] in both cases. Here \(2^N/N^{3/2}=16/8=2\), while \(2^N/N^2=16/16=1\); the example therefore illustrates why each theorem needs an unspecified absolute constant. It does not establish an asymptotic bound, uniformity in \(A\), or the second assertion for every \(l\) and \(t\). It is a sanity check on the definitions and on the distinction between the two fibres, not a proof of the Erdős question.

What is known

The primary paper by András Sárközy and Endre Szemerédi, Über ein Problem von Erdős und Moser, Acta Arithmetica 11 (1965), 205–208, is available as the journal’s scanned three-page article. On page 205 it defines the number of representations of a real target by zero-one coefficients for ordered positive real numbers. It records the earlier Erdős–Moser estimate with an extra factor of \((\log N)^{3/2}\) and states their improvement: for every \(\varepsilon>0\) and all sufficiently large \(N\), the maximum fibre is less than \((1+\varepsilon)8/\sqrt{\pi}\) times \(2^N/N^{3/2}\). This is a direct primary resolution of the first question, stronger in its real-number formulation than the natural-number special case.

The maintained problem page attributes the fixed-cardinality assertion to Gábor Halász’s more general multidimensional result, Estimates for the concentration function of combinatorial number theory and probability, Periodica Mathematica Hungarica 8 (1977), 197–211. The bibliographic record and the problem page are accessible, but the primary Halász article itself was not readable within this timebox. The attribution and the claimed order are therefore reported as source evidence, not as an independently checked page-level reading here. Richard Stanley’s 1980 paper, pages 168–184, is a further primary source for the extremal statement that the largest fibre is attained by the centred interval of consecutive integers (with the appropriate parity convention).

GCL's current state

The frozen catalogue packet in the issue points to teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, whose file blob is 4e60263a80af6207aca494d2e1388e44fa372889. Its entry for 362 says informal status proved, reports formal status Lean, and records formalized: yes in the later fields. The live catalogue has the same newer proved (Lean) metadata.

There is an important documentary discrepancy. The live Erdős Problems page, last edited 27 December 2025, says the two assertions are proved but also says “Formalised statement? No.” The pinned Formal Conjectures provider snapshot is commit 85f863718beeec7b58a3a1926ee92e3472bc2020; its ErdosProblems tree contains no 362.lean. Current upstream does contain 362.lean, but both declarations end in by sorry. It formalizes uniform bounds over nonempty Finset ℕ, including sets that may contain zero, and so needs semantic comparison with the positive, distinct source formulation. A by sorry statement shell is not a checked Lean proof and none of this is GCL certification.

What remains

The first classical proof is source-locked enough for a bounded documentary article: the scan, journal metadata, page location, and exact downloaded-paper SHA-256 5e54210d944202a1903fa2d99ed8ec27be67a8f858f59ff95521dae6dd9260 are recorded in this audit. The remaining work is to read and compare Halász’s primary theorem, including its hypotheses and the precise dependence of constants on the fixed cardinality parameter. A successor formal review should also compare the current Lean quantifiers with the primary statement, decide whether allowing zero is harmless, and inspect the linked external Lean development at commit 8822f7ddef30fadbd92e1c6ab4ed897af356af5e without treating that pointer as replay or certification.

The phrase “for any fixed” is also a quantifier issue, not merely an informal qualifier. The first constant is uniform in the set and target; the second must be tested for independence from the chosen cardinality. A future comparison should preserve that order of quantifiers and should not replace an absolute constant by one that secretly depends on \(l\), \(t\), or the particular set.

Sources and claim boundaries

This article distinguishes the primary Sárközy–Szemerédi proof, the maintained site’s report of Halász and Stanley, the catalogue’s metadata, the current by sorry formal statement, and an unverified external Lean proof report. It does not claim a Lean build, independent mathematical certification, publication authority, or acceptance beyond the applicable V2 ledger. The original SOURCE RESULT/1 citation is authenticated original RESULT/1. All catalogue hashes above are frozen packet identifiers; later live metadata is reported as drift rather than silently substituted for the packet.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1632 — 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.

Back to catalogue · Compendium introduction