Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 774

Statement. We 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$ .

Let $A\subset \mathbb{N}$ be an infinite set. We call $A$ proportionately dissociated if every finite $B\subset A$ contains a dissociated set of size $\gg \lvert B\rvert$.

Is every proportionately dissociated set the union of a finite number of dissociated sets?

Status. Open.

Source. erdosproblems.com/774, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #774, https://www.erdosproblems.com/774.

References.

[AlEr85] Alon, Noga and Erdős, P., An application of graph theory to additive number theory. European J. Combin. (1985), 201-203.
[NRS24] Ne\v set\v ril, Jaroslav and Rödl, Vojt\v ech and Sales, Marcelo, On Pisier type theorems. Combinatorica (2024), 1211-1232.
[Pi83] Pisier, Gilles, Arithmetic characterizations of Sidon sets. Bull. Amer. Math. Soc. (N.S.) (1983), 87-89.

Formalization. Statement in formal-conjectures.

Current assessment

The integer problem remains open. Pisier's arithmetic characterization identifies proportionate dissociation with harmonic-analysis Sidonicity, so the question is equivalently whether every Sidon subset of the positive integers is a finite union of quasi-independent sets; see Pisier 1983.

The closest negative result is fixed-order. Nešetřil, Rödl, and Sales construct, for every fixed $h$ , a set which is locally proportionally $h$ -free but is not a finite union of $h$ -free sets. Their extraction constant depends on $h$ and their subsets may still have relations with both sides longer than $h$ , so the construction does not give proportional dissociation; see Nešetřil--Rödl--Sales 2024.

Positive results also stop short of the integer question. Hare and Yang show that a Sidon set in a torsion-free group has linearly large subsets avoiding relations with any one fixed coefficient bound. Lewko proves a finite quasi-independent decomposition for every bounded-torsion dual group, with a quantitative prime-power bound, but explicitly excludes the torsion-free group $\mathbb Z$ ; see Hare--Yang 2018 and Lewko 2026.

Grow--Whicher's 15-element example shows that extraction constant $1/2$ does not force a cover by two dissociated classes. The same paper proves the useful finite-to-infinite reduction: over the integers, the covering question is equivalent to a uniform finite covering question (its Problem 2). A negative solution would therefore follow from finite integer sets with one uniform proportional extraction constant and unbounded dissociated covering number, which rapid dilation assembles without cross-block signed relations. Harrison--Ramsey later prove finite-determination results of the same kind for bounded-coefficient independence and for Sidon sets of bounded Sidon constant. No such uniform family is known; see Grow--Whicher 1984 and Harrison--Ramsey 1996.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (128)

Sequences and Densities of Integers Dissociated extraction and coloring Sidon sets are proportionally Sidon with small Sidon constants On partitioning Sidon sets with quasi-independent sets Problèmes ouverts: Théorie analytique des polynômes et analyse harmonique An application of graph theory to additive number theory An application of graph theory to additive number theory The closing problem (p. 203): is Pisier's necessary condition (6) sufficient for a sequence to be a finite union of free subsequences?Vectors of matroids over tracts Arithmetic matroids, Tutte polynomial, and toric arrangements Definition (Section 1.3, p. 4): arithmetic matroids, a matroid with a multiplicity function obeying five axioms Definition (Section 1.4, p. 6): the arithmetic matroid of a list in a finitely generated abelian group, and representability Theorem 2.2 (p. 9): the dual of a representable arithmetic matroid is representable, by an extension of Gale duality Theorem 7.2 (p. 26): a Crapo-type basis-activity expansion of the arithmetic Tutte polynomial of every arithmetic matroid Cuts and flows of cell complexes Theorem 4.11: the calibrated characteristic vector of a bond has torsion coefficients as entries Theorem 5.3: the characteristic flow vector of a circuit has torsion coefficients as entries Minimum partition of a matroid into independent subsets Theorem 1: a matroid splits into k independent sets iff no subset A has |A| > k r(A)Cyclotomic and simplicial matroids Corollary 2: upper bound for the number of Q-bases of Q(ζ_n) among the n-th roots of unity Corollary 9: generating function for Q-independent sets of n-th roots of unity when n = p_1^{m_1}p_2^{m_2}Theorem 1: the cyclotomic matroid μ_n is dual to a direct sum of simplicial matroids Convex Discrete Optimization Lemma 4.2 (p. 29): every nonzero integer kernel vector is a conformal sum of Graver basis elements Problèmes ouverts: Théorie analytique des polynômes et analyse harmonique Question 35 (p. 19): is ψ(n)/φ(n) bounded?Question 36 (p. 19): is n/ψ(n) bounded?Question 38 (p. 20): are all roots of unity a finite union of quasi-independent sets?Question 39 (p. 20): is the set of all roots of unity a Sidon set?Théorème A (p. 20): roots of unity of orders built from a set of primes P Finite unions of quasi-independent sets Equivalence of Problems 1 and 2 for Z (pp. 491–492): the finite-union question over the integers reduces to a uniform finite one Proposition (p. 490): a 15-element set with |F| <= 2|F'| for every subset that is not a union of two quasi-independent sets Sidon sets are proportionally Sidon with small Sidon constants Definition 2 (p. 3): n-degree and n-length independence Lemma 3 (p. 7): power images of a Sidon set in a torsion-free group keep its Sidon constant Proposition 2 (p. 5): proportional n-degree-independent subsets when the first n power images are Sidon Theorem 2 (p. 8): in a torsion-free group, Sidon is proportional n-degree independence for every n and proportional Sidon constant 1 + ε for every ε On partitioning Sidon sets with quasi-independent sets Thin sets of integers in Harmonic analysis and p-stable random Fourier series Lemma 4.5 (p. 20): under q(A) >= c|A|^epsilon, a finite A splits off about |A|^(1-epsilon) disjoint quasi-independent blocks of size about c|A|^epsilon Lemma 4.6 (p. 21): Bourgain's gluing lemma for quasi-independent sets of rapidly growing sizes Theorem 3.1 (p. 9): a p-stationary set is a Sidon set when p < 2 Theorem 3.4 (p. 10): q(A) is comparable to the squared norm of the inclusion of F_2 into the Rademacher norm Theorem 3.5 (p. 13): q(A) is comparable to the p'-th power of the inclusion norm of F_p into the p-stable norm Theorem 4.2 (p. 16): p-stable q-Rider sets are exactly the s-Rider sets with s = 2q'/(2q'-p')Theorem 4.3 (p. 17): six equivalent forms of p-stable q-Riderness, including q(A) >= c|A|^epsilon Theorem 4.4 (p. 19): q(A) >= c|A|^epsilon is equivalent to Lorentz embeddings of the p-stable space Theorem 5.1 (p. 25): s-Rider sets characterized by embeddings of a stable random Fourier space into an exponential Orlicz space

Graph