gpt pro 5.2 attempt on Math-5885

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).