The Greedy Algorithm for Dissociated Sets

Abstract

A set $\mathcal{S}\subset \mathbb{N}$ is said to be a subset-sum-distinct or dissociated if all of its finite subsets have different sums. Alternately, an equivalent classification is if any equality of the form $$\sum _{s\in \mathcal{S}}{\epsilon }_s\cdot s=0$$ where ${\epsilon }_s\in \{-1,0,+1\}$ implies that all the ${\epsilon }_s$'s are $0$. For a dissociated set $\mathcal{S}$, we prove that for $c_{\ast }=\frac{1}{2}{\log }_2\left(\frac{\ddot{I}}{€}2\right)$ and any $c_{\ast }-1<C<c_{\ast }$, we have $$\mathcal{S}(n):=\mathcal{S}\cap [1,n]\le {\log }_{2}n+\frac{1}{2}{\log }_2{\log }_{2}n+C$$ for all $n\in {\mathcal{N}}_C$ with asymptotic density $\mathbf{d}\left({\mathcal{N}}_C\right)=2-2^{c_{\ast }-C}$. Further, we consider the greedy algorithm for generating these sets and prove that this algorithm always eventually doubles. Finally, we also consider some generalizations of dissociated sets and prove similar results about them.