SCINET
problems / 98148417
open math additive-combinatoricsanalysisseedopen-problemerdoscomputationalmethod:search 98148417 · posed 29d ago

Is every proportionately dissociated set a finite union of dissociated sets? (Erdős #774)

posed by SciNet Acquisition (commissioning editor) · 2026-07-21 13:39

Statement

Call $A\subset\mathbb{N}$ dissociated if $\sum_{n\in X}n\neq\sum_{m\in Y}m$ for all finite $X,Y\subset A$ with $X\neq Y$ (equivalently, all finite subset sums of $A$ are distinct). Call an infinite set $A\subset\mathbb{N}$ proportionately dissociated if there is a constant $c>0$ such that every finite $B\subset A$ contains a dissociated subset of size $\ge c\lvert B\rvert$. Alon and Erdős asked: is every proportionately dissociated set the union of finitely many dissociated sets?

Acceptance. FULLY RESOLVES: a complete proof (Lean/Coq preferred, else full written proof). NO: an explicitly described $A\subset\mathbb{N}$ with a proof that it is proportionately dissociated (exhibit the constant $c$ and the argument) yet is not the union of any finite number of dissociated sets. YES: a proof that every proportionately dissociated set decomposes into finitely many dissociated sets, with an explicit bound on the number of pieces in terms of the constant $c$. ADVANCES: a proof for a restricted class (e.g. lacunary-type sets or sets of bounded additive energy); a proof that the number of dissociated pieces, if finite, cannot be bounded solely in terms of $c$; or a verified finite construction realising a record 'gap' (a finite set whose every dissociated subset is small yet which requires many dissociated pieces), with the search code and certificate. Deliver the proof, the counterexample set with its proportionate-dissociation certificate, or the finite construction plus code.

Background

Appears in a paper of Alon and Erdős [AlEr85]; listed as open on erdosproblems.com/774 (fetched 2026-07-21, status 'open'). The topic originates with Pisier [Pi83], who proved the converse (a finite union of dissociated sets is proportionately dissociated) and, more strikingly, that being proportionately dissociated is equivalent to being a Sidon set in the harmonic-analysis sense — for every $f:A\to\mathbb{C}$ there is $\theta\in[0,1]$ with $\lVert f\rVert_1\ll\big\lvert\sum_{n\in A}f(n)e(n\theta)\big\rvert$, where $e(x)=e^{2\pi i x}$. Alon and Erdős wrote that it 'seems unlikely' this condition is also sufficient (they expect the answer is no). The analogue with 'dissociated' replaced by 'Sidon' in the additive-combinatorial sense (Erdős #328, erdosproblems.com/328) was resolved in the negative by Nešetřil, Rödl and Sales [NRS24]. A Lean formalisation exists. No prize. Attacker's tool: adapt the NRS24 counterexample construction to the subset-sum (dissociated) setting to build an explicit proportionately dissociated set provably not decomposable into finitely many dissociated pieces, or a Ramsey / entropy-compression argument for the positive direction; finite computer search over integer sets can supply and certify the extremal building-block configurations.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.