Erdős Problem #774

Erdős Problem #774

1) ROUND-2 OBJECTIVE

Path (C): obstruction/correction. A full solution is still out of reach, so the most substantive strict advance is to isolate a rigorous obstruction. I show that every fixed-depth truncation of the problem is false: for each fixed $h$, the "$h$-free" analogue has a counterexample. Thus any eventual positive solution of Problem #774 must use unbounded additive relations in an essential way.

2) Round-1 FOUNDATION USED

I use the following Round-1 items.

1. If $A$ is a union of $m$ dissociated sets, then $A$ is proportionately dissociated with constant at least $1/m$.
2. The greedy extraction argument only yields an $O_\delta(\log |B|)$ decomposition for a finite $B\subseteq A$.
3. In the model case $(\mathbb Z/2\mathbb Z)^n$, the analogous statement holds by the matroid-cover criterion.

3) NEW INSIGHT / TOOL (ROUND-2)

The new ingredient is the 2024 theorem of Nešetřil, Rödl, and Sales.

Definition. For $h\ge 1$, a set $X=\{x_i\}_{i\in I}\subset\mathbb N$ is called $h$-free if for all distinct finite index sets $J,J'\subseteq I$ with $|J|\le h$ one has \[ \sum_{j\in J}x_j\ne \sum_{j'\in J'}x_{j'}. \] A dissociated set is therefore a set that is $h$-free for every $h$.

Theorem 3.1 (Nešetřil--Rödl--Sales, 2024). For every integer $h\ge 1$ there exist $\varepsilon_h>0$ and a set $X_h\subseteq\mathbb N$ such that

1. every finite $Y\subseteq X_h$ contains an $h$-free subset $Z\subseteq Y$ with $|Z|\ge \varepsilon_h |Y|$, but
2. $X_h$ is not a union of finitely many $h$-free sets.

4) ATTACK PLAN (ROUND-2)

The Round-1 obstacle was that no uniform finite-cover theorem was known. The new plan is different: instead of trying to prove the full statement, I prove that an entire family of natural proof strategies cannot work.

1. Formalize the bounded-depth truncation of dissociativity via the notion of $h$-free.
2. Apply Theorem 3.1 to show that the "proportionately $h$-free $\Rightarrow$ finite union of $h$-free sets" statement is false for every fixed $h$.
3. Deduce that any eventual positive proof of Problem #774 must exploit relations of arbitrarily large length; no bounded-$h$ surrogate can suffice.

5) WORK (ROUND-2)

I first relate the problem language to the theorem language.

For subsets of $\mathbb N$, the following two notions are equivalent.

1. Distinct subset sums: if $X,Y\subseteq A$ are finite and distinct, then \[ \sum_{x\in X}x\ne \sum_{y\in Y}y. \]
2. Dissociation: there is no nontrivial relation \[ \sum_{a\in A_1} a - \sum_{b\in A_2} b =0 \] with $A_1,A_2\subseteq A$ finite and distinct.

Indeed, cancelling the common terms in two subset sums leaves a nontrivial signed relation with coefficients in $\{ -1,0,1\}$, and conversely any such signed relation separates into two unequal subset sums.

Thus the "free" sets of Pisier-type theorems coincide here with dissociated sets.

Now fix $h\ge 1$. Theorem 3.1 gives a set $X_h\subseteq\mathbb N$ such that every finite $Y\subseteq X_h$ contains an $h$-free subset of size at least $\varepsilon_h|Y|$, but $X_h$ is not a union of finitely many $h$-free sets.

This immediately yields the promised negative result.

Corollary 5.1. For every fixed $h\ge 1$, the $h$-truncated analogue of Problem #774 is false.

Proof. Replace "dissociated" throughout Problem #774 by "$h$-free". Then $X_h$ from Theorem 3.1 is proportionately $h$-free but is not a union of finitely many $h$-free sets. $\square$

This gives a genuine obstruction to proving the original problem by bounded-depth methods.

Corollary 5.2 (bounded-depth obstruction). Any positive solution of Problem #774 must use the full hierarchy of subset-sum relations of unbounded length. In particular, no argument that factors the problem through a fixed $h$-free surrogate can succeed.

Justification. If a proof only needed relations of size at most some fixed $h$, then the same proof would apply to the $h$-free truncation, contradicting Corollary 5.1. $\square$

6) ADVERSARIAL VERIFICATION

There are several possible ways this obstruction could have been overstated, so I check them explicitly.

1. Does Corollary 5.1 disprove Problem #774 itself? No. The property "$h$-free" is strictly weaker than "dissociated", so the counterexamples for fixed $h$ do not directly produce a counterexample to the full problem.

2. Is the obstruction merely heuristic? No. It is a formal theorem: the bounded-depth analogue is false for every fixed $h$.

3. Could the Round-1 model-case positive result in $(\mathbb Z/2\mathbb Z)^n$ conflict with this? No. The model-case uses linear independence in a matroid; Theorem 3.1 concerns subsets of $\mathbb N$ and a different combinatorial structure.

4. What exactly has been ruled out? Not all possible proofs, but every strategy that reduces the problem to a fixed finite level of additive relations.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED)

The original problem remains open, but this round isolates a sharp obstruction: every fixed-depth truncation of the problem is false. Therefore any eventual positive proof must use genuinely unbounded subset-sum structure, not merely a bounded-$h$ approximation.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 45%

9) REFERENCES

[1] T. F. Bloom, Erdős Problem #774, erdosproblems.com/774, accessed 2026-03-07.

[2] J. Nešetřil, V. Rödl, and M. Sales, On Pisier Type Theorems, Combinatorica 44 $2024$, 1211--1232.

Erdős Problem #774: independent continuation

Date: 2026-09-23. Research attempt; no claim of a new published result.

1) TARGET AND SOURCE AUDIT

If every finite subset $B$ of $A\subseteq\mathbb N$ contains a dissociated subset of size at least $\delta|B|$, must $A$ be a finite union of dissociated sets?

All supplied versions considered: 774.tex. The source correctly cites counterexamples to the analogous fixed-$h$-free assertion, where one side of a subset-sum relation has size at most $h$. Its broad claim that every proof using a fixed level is ruled out needs a qualification: a proof may still use additional consequences of the full dissociated-subset hypothesis. I prove the precise compactness condition that a positive argument would need.

2) WORK

A uniform-color compactness lemma.

For a countable set $A$, the following are equivalent for a fixed integer $m\ge1$: \[ A\text{ is a union of }m\text{ dissociated sets}; \qquad \text{for every }h,\ A\text{ is a union of }m\ h\text{-free sets}. \tag{1} \] The forward implication is immediate. For the reverse, enumerate $A=\{a_1,a_2,\ldots\}$. Form a rooted tree whose level-$n$ nodes are $m$-colorings of $\{a_1,\ldots,a_n\}$ with each color class dissociated; edges are restriction. The assumption with $h=n$ supplies at least one such coloring, since every subset-sum equality on these $n$ elements has both sides of size at most $n$. Each node has at most $m$ children. A finitely branching tree with nodes at all depths has an infinite path: recursively select a child with descendants at unbounded depths. Along that path, every finite monochromatic subset-sum relation is excluded at some finite level. The limiting color classes are therefore dissociated.

Thus the exact missing uniformity is the number of colors $m$, independent of $h$. Merely knowing that each truncation has some finite cover $m(h)$ is insufficient for this argument. Equivalently, if $A$ is not a union of $m$ dissociated sets, some finite subset $F$ already cannot be $m$-colored into dissociated sets, and taking $h=|F|$ detects the obstruction at a finite level.

The published fixed-$h$ counterexample does not have the full proportional dissociated-subset property by hypothesis. Consequently it cannot by itself refute an argument using that stronger premise to obtain the uniform $m$ in $1$.

3) ADVERSARIAL VERIFICATION

The compactness proof fixes $m$ before taking the limit; allowing a fresh unbounded color palette at each level would invalidate finite branching. The $h$-free convention permits the other side of the relation to be arbitrarily large, as in the source paper. All constructions here are countable because $A\subseteq\mathbb N$.

4) FINAL

UNRESOLVED. No bound $m=m(\delta)$ uniform in the truncation depth is established. The lemma makes that gap exact and corrects an overbroad proof-obstruction claim, but does not settle the Pisier question.

5) SOURCES CHECKED

Entire supplied source read. Checked Nešetřil--Rödl--Sales, On Pisier Type Theorems, DOI 10.1007/s00493-024-00115-1, Theorem 1.1 and introduction, on 2026-09-23. The theorem supplies the fixed-$h$ counterexamples only.

6) COMPLETION ESTIMATE

This is a conservative subjective measure of progress toward the original question, not a probability of correctness or a claim that the remaining work is routine. COMPLETION: 10%

Problem 774: proportionately dissociated sets vs. bounded unions

1) Formal restatement

A set $A\subseteq\mathbb{N}$ is dissociated if every relation \[ \sum_{i=1}^t \varepsilon_i a_i = 0,\qquad a_i\in A\ \text{distinct},\ \varepsilon_i\in\{-1,0,1\}, \] forces all $\varepsilon_i=0$. (For positive integers, this is equivalent to uniqueness of subset sums.)

Say that $A$ is proportionately dissociated if there exists $\delta>0$ such that every finite $B\subseteq A$ contains a dissociated $C\subseteq B$ with $|C|\ge \delta|B|$.

Assume additionally that $A$ is a union of finitely many dissociated sets. Question: must $A$ in fact be a union of at most $M(\delta)$ dissociated sets for some bound depending only on $\delta$?

2) Quick literature/context check (no more than 8 lines)

• This question is attributed to Pisier and is discussed by Alon--Erdős (it is not settled there).
• The integer/$\mathbb{N}$ case is widely recorded as open.
• The analogous question for $B_2$ (Sidon) sets is known to have a negative answer (per recent notes on the ErdosProblems site).

3) Attack plan

• Note the easy direction: if $A$ is a union of $m$ dissociated sets then it is proportionately dissociated with $\delta\ge 1/m$.
• Examine what the $\delta$-property alone yields via greedy extraction (gives $O_\delta(\log|B|)$ parts for a finite $B$).
• Prove a positive result in a model setting where "dissociated" is matroid-independence (e.g. $(\mathbb{Z}/2\mathbb{Z})^n$), to illustrate why the general integer case is harder.

4) Work

Finite union $\Rightarrow$ proportionality (easy).

If $A=D_1\cup\cdots\cup D_m$ with each $D_i$ dissociated, then for any finite $B\subseteq A$ one of the intersections $B\cap D_i$ has size $\ge |B|/m$, and is dissociated. So $A$ is proportionately dissociated with $\delta\ge 1/m$.

Greedy decomposition gives only logarithmically many dissociated pieces.

Assume $A$ is proportionately dissociated with constant $\delta>0$. Given a finite $B\subseteq A$, pick dissociated $C_1\subseteq B$ with $|C_1|\ge \delta|B|$, remove it, and iterate. After $t$ steps, the remainder has size $\le (1-\delta)^t|B|$, so $B$ can be covered by \[ t=O_\delta(\log|B|) \] dissociated sets. This does not give a uniform bound independent of $|B|$, which is what Problem 774 asks for.

A positive result in a $2$-torsion model case.

Let $G=(\mathbb{Z}/2\mathbb{Z})^n$. In $G$, dissociated sets (in the signed-sum sense) coincide with linearly independent sets over $\mathbb{F}_2$, because $-1\equiv 1\pmod 2$ and a nontrivial signed relation is exactly a nontrivial subset-sum relation.

Suppose $A\subseteq G$ has the property that every finite $B\subseteq A$ contains an independent subset of size at least $\delta|B|$. Then $\mathrm{rank}(B)\ge \delta|B|$ for all finite $B\subseteq A$.

For a finite $B$, the matroid-cover theorem for vector matroids implies that $B$ can be covered by $k$ independent sets iff $|X|\le k\,\mathrm{rank}(X)$ for all $X\subseteq B$. Here $|X|\le (1/\delta)\mathrm{rank}(X)$ holds for all $X\subseteq B$, so taking $k=\lceil 1/\delta\rceil$ gives such a cover. Hence in this model case the desired conclusion holds with \[ M(\delta)\le \left\lceil \frac{1}{\delta}\right\rceil. \]

Why this does not settle the integer case.

For $A\subseteq\mathbb{N}$, dissociated sets do not obviously form the independent sets of a matroid (exchange can fail), so the above matroid-cover argument does not apply directly. The open question is whether the additional additive structure in $\mathbb{N}$, together with proportional dissociation and the assumption of a finite cover, forces a uniform bound.

5) Verification

• The pigeonhole implication "union of $m$ dissociated sets $\Rightarrow$ $\delta\ge 1/m$" is immediate.
• The greedy bound $O_\delta(\log|B|)$ is correct since each extraction removes at least a $\delta$-fraction.
• In $(\mathbb{Z}/2\mathbb{Z})^n$, signed dissociation equals linear independence; the matroid criterion yields the explicit bound $\lceil 1/\delta\rceil$.

6) Final (exactly one label and one sub-label)

LABEL: UNRESOLVED.
SUBLABEL: Gave a model-case positive result (2-torsion groups) and general reductions; the original $\mathbb{N}$ question remains open.

7) Completion estimate

A full resolution would require either constructing a counterexample in $\mathbb{N}$ for some $\delta>0$, or proving a structural theorem that forces a uniform cover bound $M(\delta)$ (likely needing tools beyond greedy decompositions).