Wiki
Wiki

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

Updated

Every seven positive reals contain a dissociated four-set


Theorem. Every seven distinct positive real numbers contain a dissociated four-set. Thus the maximum size of a positive set of dissociation dimension at most three is exactly six.

Suppose otherwise. Use the established relation-preserving integer realization, and divide out the largest common power of two. Write the resulting set as P=O⊔EP=O\sqcup E, its odd and even parts, with OO nonempty. Appending an odd element to a dissociated subset of EE shows d(E)≤2d(E)\le2. The established positive dimension-two bound gives ∣E∣≤3|E|\le3; equality requires E={u,v,u+v}E=\{u,v,u+v\}.

Also ∣O∣≤4|O|\le4. To see this directly, take its three largest elements a<b<ca<b<c. For any additional x<ax<a, dependence of the four positive odd elements forces c=x+a+bc=x+a+b or x+c=a+bx+c=a+b. Hence x=∣c−a−b∣x=|c-a-b|, permitting at most one additional element. Thus ∣O∣=4|O|=4 and ∣E∣=3|E|=3.

Write O={a<b<c<d}O=\{a<b<c<d\}. Its dependence has one of the forms

d=a+b+c,a+d=b+c.(1)d=a+b+c,\qquad a+d=b+c. \tag{1}

For each e∈Ee\in E, join two members x,yx,y of OO when e=x+ye=x+y or e=∣x−y∣e=|x-y|. Every three vertices contain an edge: otherwise those three odd numbers together with ee would be dissociated, since any relation must use exactly two of the odd numbers, by parity.

This graph is triangle-free. For x<y<zx<y<z, if x+z=ex+z=e, the pair x,yx,y is not an edge. If z−x=ez-x=e, the differences on x,yx,y and y,zy,z are both less than ee, so those two edges would require x+y=y+z=ex+y=y+z=e, impossible. A triangle-free graph on four vertices meeting every triple contains a perfect matching: if it had no disjoint edges, all its edges would form a star or contain a triangle, and a star leaves an independent triple.

The three perfect matchings give the following possible common sum-or-difference labels for their two pairs:

d=a+b+ca+b, a+c, b+ca+d=b+cb−a, c−a, b+c.(2)\begin{array}{c|c} d=a+b+c& a+b,\ a+c,\ b+c\\ a+d=b+c& b-a,\ c-a,\ b+c. \end{array} \tag{2}

These follow by substituting (1) into the sums and positive differences of the three pairs of pairs. Disjoint positive pairs cannot share two such labels, since their sum and positive difference uniquely determine a pair. Every e∈Ee\in E belongs to the indicated triple, so the three-element set EE equals it. In the first row its largest element is strictly less than the sum of the other two; in the second it is strictly greater. Neither row is an additive triple, contradicting E={u,v,u+v}E=\{u,v,u+v\}.

Sharpness is witnessed by

P={1,3,4,5,7,8}.P=\{1,3,4,5,7,8\}.

Its triple {1,3,5}\{1,3,5\} is dissociated. Every four-subset contains one of the additive triples

{1,3,4}, {1,4,5}, {3,4,7}, {1,7,8}, {3,5,8},\{1,3,4\},\ \{1,4,5\},\ \{3,4,7\},\ \{1,7,8\},\ \{3,5,8\},

except {1,3,5,7}\{1,3,5,7\} and {4,5,7,8}\{4,5,7,8\}, which have equal pair sums. Thus d(P)=3d(P)=3.

Consequence and limitation

The established odd dimension-four bound ∣O∣≤8|O|\le8, together with this theorem for the even part, gives

d(P)≤4⟹∣P∣≤14.d(P)\le4\Longrightarrow |P|\le14.

This improves the earlier bound fifteen. The proof shows why separate odd/even extremal bounds can overcount: their equality configurations may be incompatible. No general joint parity inequality ∣O∣+∣E∣≤2d(O∪E)−1|O|+|E|\le2^{d(O\cup E)}-1 has been proved.