On the Size of Dissociated Bases

Vsevolod F. Lev, Raphael Yuster


We prove that the sizes of the maximal dissociated subsets of a given finite subset of an abelian group differ by a logarithmic factor at most. On the other hand, we show that the set $\{0,1\}^n\subseteq\mathbb{Z}^n$ possesses a dissociated subset of size $\Omega(n\log n)$; since the standard basis of $\mathbb{Z}^n$ is a maximal dissociated subset of $\{0,1\}^n$ of size $n$, the result just mentioned is essentially sharp.

Full Text: