Skip to content

Erdős Problem #774

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (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

Imagine a collection of distinct positive integers in which no two different selections have the same sum. Such a set is dissociated: its members carry distinguishable subset sums. For instance, powers of two are dissociated because binary expansion identifies exactly which powers were chosen.

Erdős Problem #774 asks whether the following apparently weaker guarantee is actually enough to partition an infinite set into finitely many dissociated pieces: every finite sample contains a dissociated subset occupying at least some fixed positive fraction of that sample. Crucially, the fraction must be the same for every finite sample, regardless of its size.

This remains OPEN. The analogous question about ordinary Sidon sets, where only sums of two distinct selected elements are controlled, was answered negatively in 2024. That does not answer this stronger subset-sum question.

A small example

The set \(B=\{1,2,3\}\) is not dissociated, because

\[ 1+2=3. \]

But its subset \(\{1,2\}\) is dissociated, and \(B\) can be partitioned into the two dissociated sets \(\{1,2\}\) and \(\{3\}\). In this tiny example the largest dissociated subset has size \(2\) out of \(3\).

By contrast, every set of distinct powers of two is dissociated. Each finite subset has a unique binary-encoded sum. A full infinite set \(\{1,2,4,8,\ldots\}\) therefore needs only one dissociated class.

Neither example resolves the difficult case: arbitrarily large finite samples from a single infinite set whose dissociated fraction stays bounded below while the number of colours needed to separate all additive relations may grow without bound.

What is known

A set \(D\) is dissociated if the subset-sum map is injective, or equivalently if its elements have no nontrivial relation

\[ \sum_{d\in D}\varepsilon_d d=0,\qquad \varepsilon_d\in\{-1,0,1\}, \]

where only finitely many coefficients are nonzero. To see the equivalence, put positive-coefficient elements on one side of the equality and negative-coefficient elements on the other; conversely cancel the common elements of two subsets with equal sums.

An infinite set \(A\) is proportionately dissociated if there is one constant \(\delta>0\) so that every finite \(B\subset A\) has a dissociated subset \(D\) satisfying

\[ |D|\geq\delta |B|. \]

Alon and Erdős state this necessary condition as equation (6) on p. 203 of their 1985 paper. They called dissociated sets free and observed that the converse was doubtful, but that they had no counterexample.

Why is the condition necessary? If \(A\) is covered by \(r\) dissociated sets, any finite \(B\) is covered by their intersections with \(B\). One intersection contains at least \(|B|/r\) elements by pigeonhole. Since every subset of a dissociated set is dissociated, one may take \(\delta=1/r\).

The question is whether this simple reasoning can be reversed.

Gilles Pisier's 1983 work, Arithmetic characterizations of Sidon sets, is credited by the maintained catalogue with proving that proportional dissociation characterizes Sidon sets in the harmonic-analysis sense. This sense describes Fourier-series interpolation and is not the same as the classical additive \(B_2\) condition on two-term sums. The full original Pisier proof was not inspected for this manuscript.

Nešetřil, Rödl, and Sales proved in On Pisier Type Theorems, Combinatorica 44 (2024), 1211–1232, that the analogous finite-union implication fails for additive \(B_h\) sets with \(h\geq2\). Their counterexamples have a positive-fraction \(B_h\) subset inside every finite sample but cannot be partitioned into finitely many \(B_h\) sets. Their published abstract directly supports that result; the complete construction has not been reproduced here. Since dissociation forbids relations involving arbitrary numbers of terms, a \(B_h\) counterexample is not automatically a counterexample to #774.

A useful mathematical reformulation

Construct a hypergraph with vertex set \(A\). Its hyperedges are the inclusion-minimal supports of nonzero signed relations with coefficients from \(\{-1,0,1\}\). A set of vertices is independent exactly when it is dissociated. A colouring is proper when no hyperedge is monochromatic, so a colouring with \(r\) colours is exactly a partition into at most \(r\) dissociated sets.

The hypotheses of #774 then say that every finite induced subhypergraph has an independent set occupying at least the fraction \(\delta\) of its vertices. The conclusion would say that the entire infinite hypergraph has finite chromatic number.

There is a useful compactness equivalence: for any fixed positive integer \(r\), the entire hypergraph has an \(r\) colouring if and only if every finite induced subhypergraph has an \(r\) colouring. One direction follows by restriction; the other follows by compactness of finite-colour assignments. Consequently, a negative answer to #774 would require, for every \(r\), some finite sample that needs more than \(r\) dissociated colour classes, while every finite sample still has an independent set of relative size at least \(\delta\).

A positive independent-set fraction does not by itself visibly bound the chromatic number in general hypergraphs. The missing issue is whether the special arithmetic signed-relation structure forces more than the generic hypergraph axioms.

GCL's current state

The original authenticated RESULT/1 source return records BOUNDED_TASK_DESIGNED and retains the original mathematical qualifications. This is an editorially reviewed explanatory article in the EC-BULK-005-R9 protected batch, effective only when that exact-hash transaction merges. The corresponding maintained Erdős statement and its bibliography were inspected. This editorial decision does not certify any full original theorem proof, independent external formalization, or Lean kernel check.

Preserved source-review qualifications: open main dissociation not same as nrs24 bh analogue; hereditary independence ratio vs uniform chromatic bound; finite compactness reduction not a solution. See the immutable 128-case critical review record for the complete source-return caveats.

What remains

Verify the original theorem and precise Fourier-analytic definitions in Pisier (1983) and the later Erdős (1992) restatement. Inspect the actual Nešetřil–Rödl–Sales construction to determine whether its fixed-length sum relations can be extended without destroying the proportional dissociation hypothesis.

Finite executable checks should calculate subset-sum uniqueness, maximum dissociated subfamilies and minimum dissociated colour counts for small explicit integer sets. They validate the definitions, but no bounded enumeration can settle the infinite colouring question. The central mathematical obligation is either a uniform chromatic bound from the hereditary independence ratio, specialized to signed integer relations, or an explicit infinite arithmetic counterexample.

Sources and claim boundaries

Editorial source decision: R9 critical review, REVIEWED as a source-grounded explanation only. All open mathematical questions, primary-proof fidelity obligations, and external formalization caveats remain separate.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2045 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: PROTECTED_READY_BACKLOG.
  • 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.

Back to catalogue · Compendium introduction