Erdoes #774 - working report - Erdős Problem a Day

Erdős problem #774 — wave w013

Date: 2026-07-28 (UTC)

0. Mandatory live-page gate

I read the live page through the Bright Data browser path, not through a datacenter curl. The page fetched was https://www.erdosproblems.com/774; I also fetched its LaTeX view and discussion thread.

The gate did not fire:

live status: OPEN;
claimed proofs: 0;
“Currently working on this problem”: None;
“Interested in collaborating”: None;
the page says it was last edited 28 December 2025.

The two displayed comments also contain no solution or active-work claim. Alex Grebennikov (31 October 2025) points to the negative solution of the additive-combinatorial Sidon analogue by Nešetřil–Rödl–Sales; the page says it was updated in response. Dogmachine (7 February 2026) suggests linking the related Pisier problems #846 and #847.

Verbatim live 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?

The page cites [AlEr85][Er92b]. Its notes say that Pisier proved proportional dissociation equivalent to being a Sidon set in the harmonic-analysis sense; the easy converse direction is that a finite union of dissociated sets is proportionately dissociated. It quotes Alon and Erdős as saying that sufficiency “seems unlikely,” while they had no counterexample. It also records the negative Nešetřil–Rödl–Sales result for the different, additive-combinatorial Sidon analogue.

1. Claim labels and notation

Every mathematical claim below is labelled as requested:

(a) elementary-rigorous: a complete proof is given here;
(b) rigorous-modulo-named-theorem: the named primary-source theorem is

stated precisely;

(c) plausible/structural-unverified;
(d) computational-only: exhaustive finite computation, with the

standalone verifier supplied.

For a finite set $F\subset\mathbb N$, put

\alpha(F)=\max\{|D|:D\subseteq F\text{ is dissociated}\},

\rho(F)=\min_{\varnothing\ne B\subseteq F}\frac{\alpha(B)}{|B|}, \qquad \chi_d(F)=\min\{r:F\text{ is a union of }r\text{ dissociated sets}\}.

The literature usually calls the page's “dissociated” sets quasi-independent: they admit no nonzero relation with coefficients in $\{-1,0,1\}$. These are exactly the same objects, because equal distinct subset sums can be cancelled to give such a signed relation, and conversely. This equivalence is (a).

2. Exact finite reduction: what remains

Proposition (finite obstruction principle)

(b), rigorous modulo the de Bruijn–Erdős compactness theorem for finite-edge hypergraphs. Problem #774 has an affirmative answer if and only if

C(\delta):=\sup\{\chi_d(F): F\subset\mathbb N\text{ finite and } \rho(F)\ge\delta\}<\infty \tag{1}

for every $\delta>0$.

This is essentially the finite equivalence already isolated by Grow–Whicher, but the following proof records the exact invariant needed here.

Proof. Make a hypergraph on $A$ whose edges are the finite supports of nonzero signed zero-relations. Its independent sets are precisely the dissociated sets. If every finite subset of $A$ is $C$-colourable, the de Bruijn–Erdős compactness theorem gives a $C$-colouring of all of $A$. Thus (1), applied with the proportionality constant of $A$, implies the desired decomposition.

For the converse, suppose (1) fails at a fixed $\delta$. Choose finite sets $F_t\subset\mathbb N$ with $\rho(F_t)\ge\delta$ and $\chi_d(F_t)>t$. Let $M_1=1$, and inductively choose

M_{t+1}>\sum_{s\le t}M_s\sum_{x\in F_s}x. \tag{2}

Set $A=\bigcup_t M_tF_t$. In a signed relation, take the highest block which occurs. Its contribution is $M_tz$ for an integer $z$. If $z\ne0$, its absolute value is at least $M_t$, larger by (2) than all lower-block contributions combined. If $z=0$, the relation already restricts to a relation in the top block. Descending through the blocks shows:

D\subseteq A\text{ is dissociated} \quad\Longleftrightarrow\quad D\cap M_tF_t\text{ is dissociated for every }t. \tag{3}

Consequently, for every finite $B\subset A$,

\alpha(B)=\sum_t\alpha(B\cap M_tF_t)\ge\delta|B|,

where only finitely many terms occur. Hence $A$ is proportionately dissociated. But every colouring of $A$ restricts to every $M_tF_t$, so $\chi_d(A)\ge\sup_t\chi_d(F_t)=\infty$. This would be a counterexample.

$\square$

Thus the exact missing result is not another qualitative Sidon characterisation. It is either:

(a target for an affirmative solution) prove $C(\delta)<\infty$ in

(1), uniformly over the size and magnitude of $F$; or

(a target for a negative solution) construct finite $F_t$ with one

fixed $\delta>0$, $\rho(F_t)\ge\delta$, and $\chi_d(F_t)\to\infty$.

No uniformity/limit step of this kind is supplied by the computations below, so they do not close the problem.

3. Primary-source literature check

The following are source-verified (b) claims.

Original formulations. Alon and Erdős,

An Application of Graph Theory to Additive Number Theory, European J. Combin. 6 (1985), 201–203, state the question on p. 203 and say they could find no counterexample. [Er92b] is Paul Erdős, Some of my favourite problems in various branches of combinatorics, Le Matematiche 47(2) (1992), 231–240.

Pisier. Gilles Pisier,

Arithmetic characterizations of Sidon sets, Bull. AMS 8 (1983), 87–89, proves that a set is harmonic-analytic Sidon exactly when every finite subset contains a proportionally large quasi-independent subset. This is the equivalence used on the live page.

A directly relevant result omitted from the live notes. David Grow

and William Whicher, Finite Unions of Quasi-Independent Sets, Canad. Math. Bull. 27 (1984), 490–493, give the 15-element example analysed in §4. It has proportionality $1/2$ but is not the union of two quasi-independent sets. They also prove the finite-obstruction equivalence underlying §2.

Later positive evidence and uniformity. K. Harrison and L. T.

Ramsey, On partitioning Sidon sets with quasi-independent sets, Colloq. Math. 69 (1996), 117–131, still state the integer problem as open, produce random examples which are finite unions, and show that an affirmative answer would imply a bound depending on the Sidon constant.

Torsion-free proportional strengthening. Kathryn Hare and Robert

Yang, Sidon Sets are Proportionally Sidon with Small Sidon Constants, Canad. Math. Bull. 62 (2019), 798–809, prove stronger proportional extraction results in torsion-free groups, but explicitly list finite union into quasi-independent sets as unknown.

Nearby negative variants. Jaroslav Nešetřil, Vojtěch Rödl, and

Marcelo Sales, On Pisier Type Theorems, Combinatorica 44 (2024), 1211–1232, state that the full free-set implication remains open. They disprove bounded-$h$ / $B_h$-type variants and prove a bounded-set-size positive theorem for the multiset-union model. Their Theorem 4.1 is the negative additive-combinatorial Sidon analogue mentioned on the live page; it does not control all signed relation lengths simultaneously.

Newest located result. Mark Lewko,

The Sidon Decomposition Problem in Abelian Groups of Bounded Torsion, arXiv:2606.06669v1, submitted 4 June 2026, proves the decomposition for every bounded-torsion dual group. Theorem 1.3 gives, for $G=(\mathbb Z/p^s\mathbb Z)^n$,

\[ \chi_d(F)\le \left\lceil\frac{s\log_2p}{\delta}\right\rceil \quad\text{when }\rho(F)\ge\delta. \tag{4} \]

The paper explicitly says that the analogous problem for $\Gamma=\mathbb Z$ is not addressed and remains the well-known open case.

I searched the exact problem wording, “proportionally quasi-independent,” “finite union of quasi-independent sets,” and the Sidon decomposition problem, including 2024–2026 material. I found no primary source claiming to solve the integer case. That search miss is not a proof that no uncatalogued result exists.

4. Exact computation for the Grow–Whicher obstruction

Let

E=\{3^j+kj:0\le k\le2,\ 1\le j\le5\}

=\{3,4,5,9,11,13,27,30,33,81,85,89,243,248,253\}. \tag{5}

Exact result

(d), exhaustive computation.

\rho(E)=\frac12,\qquad \alpha(E)=8,\qquad \chi_d(E)=3. \tag{6}

There are exactly 7,569 dissociated subsets among the $2^{15}=32,768$ subsets of $E$. The exact induced-subset table is:

| $|B|$ | number of $B$ | min $\alpha(B)$ | max $\alpha(B)$ | $\chi_d=1$ | $\chi_d=2$ | $\chi_d=3$ | |---:|---:|---:|---:|---:|---:|---:| | 1 | 15 | 1 | 1 | 15 | 0 | 0 | | 2 | 105 | 2 | 2 | 105 | 0 | 0 | | 3 | 455 | 2 | 3 | 447 | 8 | 0 | | 4 | 1,365 | 3 | 4 | 1,256 | 109 | 0 | | 5 | 3,003 | 3 | 5 | 2,312 | 691 | 0 | | 6 | 5,005 | 4 | 6 | 2,459 | 2,546 | 0 | | 7 | 6,435 | 4 | 7 | 969 | 5,466 | 0 | | 8 | 6,435 | 5 | 8 | 5 | 6,430 | 0 | | 9 | 5,005 | 5 | 8 | 0 | 5,005 | 0 | | 10 | 3,003 | 6 | 8 | 0 | 3,003 | 0 | | 11 | 1,365 | 6 | 8 | 0 | 1,365 | 0 | | 12 | 455 | 6 | 8 | 0 | 455 | 0 | | 13 | 105 | 7 | 8 | 0 | 105 | 0 | | 14 | 15 | 7 | 8 | 0 | 15 | 0 | | 15 | 1 | 8 | 8 | 0 | 0 | 1 |

In particular, every proper subset of $E$ is 2-colourable, and $E$ itself is the unique 3-chromatic induced subset. This is only minimality inside $E$; it is not a claim of global minimality among all integer sets.

The seven subsets attaining the exact ratio $1/2$ are

E\setminus\{243,248,253\}

and

E\setminus\{x\}\quad (x\in\{11,81,89,243,248,253\}).

The three columns

\{3,9,27,81,243\},\quad \{4,11,30,85,248\},\quad \{5,13,33,89,253\}

are dissociated and partition $E$, giving the upper bound $\chi_d(E)\le3$. This finite assertion is checked directly in the verifier.

For a compact certificate of the lower bound, the exhaustive list of dissociated 8-subsets is exactly:

\begin{aligned} I_1&=\{4,11,27,81,89,243,248,253\},\\ I_2&=\{4,11,30,81,89,243,248,253\},\\ I_3&=\{11,27,81,85,89,243,248,253\},\\ I_4&=\{11,30,81,85,89,243,248,253\},\\ I_5&=\{11,33,81,85,89,243,248,253\}. \end{aligned}

Their complements fail dissociation respectively because

30=3+5+9+13,\quad 27=5+9+13,\quad 9=4+5,\quad 9=4+5,\quad 9=4+5.

Since $\alpha(E)=8$, any hypothetical two-colouring would have a dissociated colour of size 8; the five possibilities above exhaust that colour, and every complementary colour has the displayed collision.

Additional exact diagnostics are (d):

the minimal signed-relation supports have size histogram

$3:8,\ 4:17,\ 5:48,\ 6:81,\ 7:50$;

the span of all signed zero-relation vectors has rank 14 over each of

$\mathbb F_2,\mathbb F_3,\mathbb F_5$.

The second item shows quantitatively why a naive relation-space Rado–Horn attack has little slack even at $\rho=1/2$: on all 15 coordinates its codimension is only one.

How the computation is independently checked

The standalone script is runs/erdos774_wavew013_reverify.py. It uses only the Python standard library and:

builds dissociation masks incrementally from disjoint subset-sum sets;
independently recomputes every mask by explicitly listing all its

subset sums;

computes every $\alpha(B)$ by a max-zeta transform and independently

checks it by enumerating every submask;

exhausts every two-colour split (with colour symmetry removed);
checks the five published 8-subsets and their explicit complement

collisions;

enumerates equal-subset-sum relation vectors and performs from-scratch

modular Gaussian elimination.

Run:

python3 runs/erdos774_wavew013_reverify.py

The audited run ended in VERIFIED in 11.7 seconds, with peak RSS about 142 MB.

5. A sharp concrete one-parameter classification

Define, for an integer $b\ge3$,

E_b=\{b^j+kj:0\le k\le2,\ 1\le j\le5\}. \tag{7}

Classification

\chi_d(E_3)=3,\qquad \chi_d(E_b)=2\quad\text{for every }b\ge4. \tag{8}

The $b=3$ assertion and the finite cases $4\le b\le17$ are (d): the verifier exhausts all two-colour splits and directly rechecks the two parts it finds. For every $b\ge18$, the assertion is (a) with the uniform proof below.

First, no $E_b$ is itself dissociated, since the four distinct elements in

\[ (b+2)+b^2=b+(b^2+2) \]

belong to $E_b$. Thus every two-colour upper bound is exact.

For $b\ge18$, colour the labels $(k,j)$ in

S=\{(0,1),(2,1),(0,2),(2,2),(0,3),(1,3)\} \tag{9}

red and all other nine labels blue. Consider a signed sum and write it as

\sum_{j=1}^5 c_jb^j+d,\qquad c_j=\sum_k\epsilon_{k,j},\qquad d=\sum_{k,j}\epsilon_{k,j}kj. \tag{10}

For red, $|d|\le9<b$. A zero sum therefore has $d=0$ modulo $b$; successive division and reduction modulo $b$, using $|c_j|\le2<b$, forces every $c_j=0$. In columns 1, 2, 3 the only remaining nonzero paired contributions to $d$ would be respectively $\pm2,\pm4,\pm3$. No nonempty signed selection of $2,4,3$ sums to zero, so red is dissociated.

For blue, $|d|\le36$. A zero sum makes $d$ divisible by $b$; put $t=-d/b$. Equation (10), divided by $b$, and reduction modulo $b$ give $c_1=t$, because $|c_1-t|<b$. Repeating gives $c_2=\cdots=c_5=0$. Columns 2 and 3 are singletons, hence their signs vanish. The residual contributions from columns 4 and 5 lie in $\{0,\pm4,\pm8\}$ and $\{0,\pm5,\pm10\}$, respectively. If $c_1=0$, these cannot cancel nontrivially. If $c_1=\pm1$, zero would require their sum to have absolute value $b+1\ge19$, while its absolute value is at most $18$. Hence blue is dissociated. This proves (8) for all $b\ge18$; the remaining fourteen bases are the explicit finite checks printed by the verifier.

This classification explains that the Grow–Whicher obstruction is arithmetically delicate inside its natural template: merely replacing the base 3 by any larger integer destroys the need for the third colour. It does not produce an unbounded-chromatic family.

6. What the 2026 bounded-torsion theorem gives over the integers

There is an immediate quantitative finite corollary of Lewko's Theorem 1.3.

Corollary

(b), rigorous modulo Lewko's Theorem 1.3. If $F\subset\mathbb N$ is finite, $S=\sum_{x\in F}x$, and

s=\left\lceil\log_2(S+1)\right\rceil,

then

\chi_d(F)\le \left\lceil\frac{s}{\rho(F)}\right\rceil. \tag{11}

Indeed, reduce $F$ modulo $q=2^s>S$. Every signed sum has absolute value at most $S<q$, so it vanishes modulo $q$ exactly when it vanishes over $\mathbb Z$. Thus all dissociation and proportionality data are preserved. Apply (4) with $p=2$, exponent $s$, and $n=1$.

For (5), $S=1134$, so $q=2048$, $s=11$, and (11) gives 22 colours, whereas the exact answer is 3. The verifier recomputes all four numbers.

The dependence on $s$, hence on the magnitude of $F$, is precisely why (11) does not imply (1). Removing that dependence is not a cosmetic optimization: it is the missing uniformity in the integer problem.

7. Honest wall

The present verified state is:

(d) the classical $1/2$-proportional example really needs three

dissociated pieces, and its complete induced-subset table is now reproduced independently;

(a)+(d) its natural base-$b$ template has been classified exactly;
(b) the infinite question is exactly the uniform finite bound (1);
(b) the newest bounded-torsion theorem supplies (11), but its bound

grows with the exponent needed to model an integer set.

Three standard routes stall at identifiable points.

Repeatedly remove a dissociated $\delta$-fraction. This gives only

$O_\delta(\log|F|)$ colours, not the size-independent $C(\delta)$ required in (1). This diagnosis is (a).

Reduce modulo $2^s$ and use bounded torsion. Equation (11) retains

$s\asymp\log\sum F$. A modulus-independent replacement for Lewko's local relation-space codimension estimate would suffice for this route, but the 15-point rank computation shows that at $\delta=1/2$ any such estimate must tolerate codimension only $1/15$ on this example. The sufficiency statement is (b) modulo the Rado–Horn support-partition lemma in Lewko; the rank obstruction is (d).

Import the Nešetřil–Rödl–Sales negative construction. Their radix

encoding controls a fixed relation length $h$. Full dissociation requires avoiding every length simultaneously with one bounded number of colours. No fixed-$\delta$, unbounded-$\chi_d$ finite sequence results from their theorem. This boundary is (b) from their stated theorems, not a conjectural extension.

A blind global search cannot repair the uniformity gap. Even restricting to 15-element subsets of $[253]$ gives

$\binom{253}{15}=557{,}855{,}866{,}809{,}479{,}623{,}908{,}600$

candidates. At an unrealistically optimistic $10^6$ candidates per second this is about $1.55\times10^{14}$ core-hours (roughly $\$7.8\times10^{12}$ at $\$0.05$/core-hour). More importantly, no finite magnitude cutoff can establish the uniform statement (1). The useful next target is therefore a structural bound for (1), or a structured fixed-$\delta$ family with growing $\chi_d$, not a larger unstructured enumeration.

PARTIAL: exact 15-point obstruction/table and base-family classification verified; #774 remains equivalent to the unresolved uniform finite bound $C(\delta)<\infty$.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger