Skip to main content
1 of 7
Seva
  • 23k
  • 2
  • 59
  • 141

A famous open conjecture of Paul Erdos, first stated about 80 years ago, is that if all subset sums of an integer set $S\subset[1,n]$ are pairwise distinct, then $|S|<\log_2n+O(1)$ as $n\to\infty$. (Here $\log_2$ denotes the base-$2$ logarithm.) In modern terms, a subset of an abelian group, all of whose subset sums are pairwise distinct, is called dissociated. Similarly to Erdos' original problem, one can ask how large can dissociated subsets of other "natural" sets in abelian groups be; say, you are asking what is the largest possible size of a dissociated subset of the set $\{0,1\}^n\subset{\mathbb R}^n$.

Problems of this sort were studied in a joint paper "On the size of dissociated bases" by Raphy Yuster and myself. We have shown that the sizes of any two maximal dissociated subsets of a given finite subset of an abelian group differ by a logarithmic factor at most. Addressing the specific set $\{0,1\}^n$, we proved that, denoting by $M_n$ the largest size of its dissociated subset, we have $$ (1+o(1))n\log_2 n/\log_2 9 < M_n < (1+o(1))n\log_2 n. $$ It is an open problem to determined the best possible coefficients.

Seva
  • 23k
  • 2
  • 59
  • 141