Open-access mathematical research insights
About Contact
Home / Erdos Problems / Problem #963

Problem #963: Let $f(n)$ be the maximal $k$ such that in any set...

Let $f(n)$ be the maximal $k$ such that in any set $A\subset \mathbb{R}$ of size $n$ there is a subset $B\subseteq A$ of size $\lvert B\rvert\geq k$...

Problem Statement

Let $f(n)$ be the maximal $k$ such that in any set $A\subset \mathbb{R}$ of size $n$ there is a subset $B\subseteq A$ of size $\lvert B\rvert\geq k$ which is dissociated that is, the sums $\sum_{b\in S}b$ are distinct for all $S\subseteq B$. Estimate $f(n)$ - in particular, is it true that\[f(n)\geq \lfloor \log_2 n\rfloor?\]
Categories: Number Theory

Progress

Erdős noted that the greedy algorithm showed $f(n)\geq \lfloor \log_3 n\rfloor$.

Source: erdosproblems.com/963 | Last verified: January 19, 2026

Stay Updated

Get weekly digests of new research insights delivered to your inbox.