Erdős problem 1 · problems.science

If $A\subseteq\{1, ..., N\}$ with $|A| = n$ is such that the subset sums $\sum_{a\in S}a$ are distinct for all $S\subseteq A$ then $N \gg 2 ^ n.$

Sources

Browse retained paths and inspect the exact material available for this Problem.

8 retained statements2415f78e850a

FormalConjectures/ErdosProblems/

1.lean

Retained formal statement2 of 8

Erdős and Moser [Er56] proved $N \geq (\tfrac{1}{4} - o(1)) \frac{2^n}{\sqrt{n}}.$

[Er56] Erdős, P., _Problems and results in additive number theory_. Colloque sur la ThÉorie des Nombres, Bruxelles, 1955 (1956), 127-137.

FormalConjectures/ErdosProblems/1.leanErdos1.erdos_1.variants.lb3 linesExact file

1∃ o,2  ∃ (_ : o =o[Filter.atTop] 1),3    ∀ (N : ℕ) (A : Finset ℕ), Erdos1.IsSumDistinctSet A N → (1 / 4 - o A.card) * 2 ^ A.card / √↑A.card ≤ ↑N

SolvedStatement only, no proof