Wiki
Wiki

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

Updated


Claim. A set BB of real numbers is dissociated if distinct finite subsets of BB have distinct sums, the empty subset with sum 00 included; for a finite set X⊂RX\subset\mathbb R let d(X)d(X) be the largest size of a dissociated subset of XX, and let f(n)f(n) be as in the problem.

First, every nonempty finite set A⊂RA\subset\mathbb R with nn elements contains a dissociated subset of size at least log⁡2n−log⁡2(log⁡2n+1)\log_2n-\log_2(\log_2n+1), so

f(n)≥log⁡2n−log⁡2(log⁡2n+1)(n≥1).f(n)\ge\log_2n-\log_2(\log_2n+1)\qquad(n\ge1).

Second, every finite set A⊂RA\subset\mathbb R with n=∣A∣≥5n=|A|\ge5 satisfies

d(A)≥log⁡2(n−1)−log⁡2(⌈log⁡2log⁡2n⌉+2+2)−log⁡26,d(A)\ge\log_2(n-1)-\log_2\bigl(\lceil\log_2\log_2n\rceil+2+\sqrt2\bigr)-\log_26,

and consequently f(n)≥log⁡2n−log⁡2log⁡2log⁡2n−4f(n)\ge\log_2n-\log_2\log_2\log_2n-4 for every n≥216n\ge2^{16}.

Third, a nonempty finite set PP of nn positive reals with max⁡P≤43min⁡P\max P\le\frac43\min P has n≤2d(P)−1n\le2^{d(P)}-1; in particular d(P)≥⌊log⁡2n⌋d(P)\ge\lfloor\log_2n\rfloor for such sets.

Covers. The open-ended estimate of f(n)f(n) asked by Problem 963: the lower bound rises from Erdős's greedy bound ⌊log⁡3n⌋\lfloor\log_3n\rfloor to log⁡2n−O(log⁡log⁡n)\log_2n-O(\log\log n) for every nn, and to log⁡2n−log⁡2log⁡2log⁡2n−4\log_2n-\log_2\log_2\log_2n-4 for n≥216n\ge2^{16}. The definite question, whether f(n)≥⌊log⁡2n⌋f(n)\ge\lfloor\log_2n\rfloor for every nn, stays open: the first bound lies strictly below ⌊log⁡2n⌋\lfloor\log_2n\rfloor for every n≥2n\ge2, the second does not decide it, and the third gives the asked bound only for positive sets whose largest element is at most 4/34/3 times the smallest. No upper bound on f(n)f(n) and no sharpness of these bounds is claimed.

Standing. The first bound is L22 at tier 2. Its Lean proof passes the axiom audit, depending only on propext, Classical.choice and Quot.sound with no compiler axiom, and the independent whole-statement fidelity audit and its distinct passing grade are filed on the card. The second and third bounds are L213 and L212 at tier 0: author-recorded by Plasma AI, with complete written proofs and no independent examination or Lean proof; they do not inherit L22's warrant. Catalog acceptance is pending.

Depends on. L22 (tier 2), L213 (tier 0) and L212 (tier 0), which L213 applies to each dyadic block of the absolute values.