1
$\begingroup$

For a positive integer set $m \in \mathbb{N}_{+}^k$, we define the set of subset sums $$ M = \left\{ \sum_{i \in I} m_i \mid I \subseteq \{1,\dots,k\} \right\}. $$

Given a finite set of positive integers $C \subset \mathbb{N}_+$, what is the minimal $k$ and the corresponding $m$ such that $$ M \supseteq C \textrm{ ? } $$ Let's define $n = \max(C)$. It is easy to see that $k \leq \log_2 ( n +1)$ as $M = \{1,\dots,n\}$ for $m = [1, 2, 4, 8, \dots, 2^{k-1}]$. Also, a solution can be recovered by iterative elimination of $C$. For example: $$\begin{eqnarray}\require{cancel} C = [1, 2, 3, 5, 6, 7, 8, 9, 10, 12, 13, 14] \\ [1, 2, \cancel{3}, 5, 6, 7, 8, 9, 10, 12, 13, 14] \\ [1, 2, 5, \cancel{7}, \cancel{8}, 9, 10, 12, 13, 14] \\ [1, 2, 5, 9, \cancel{10}, \cancel{12}, 13, 14] \\ [1, 2, 5, 9, 13, \cancel{14}], \end{eqnarray}$$ which is viable, but non-optimal compared to $m = [1, 2, 5, 7]$. Is this a known problem and is there an efficient method to find minimal $m$?

$\endgroup$
3
  • $\begingroup$ Are you requiring that the generating set m be a proper subset of C? If not, the log (of the largest element of C) bound should work similarly for C. Gerhard "Or Is That Too Easy?" Paseman, 2018.04.30. $\endgroup$ Apr 30, 2018 at 15:19
  • $\begingroup$ @GerhardPaseman All set relations are not necessarily proper. I clarified this above. The bound works but, it is by no means tight, right? $\endgroup$
    – Jiro
    Apr 30, 2018 at 15:30
  • $\begingroup$ I am not an expert here. I think the bound is asymptotically tight. Guy's Unsolved Problems In Number Theory should be a good launching point to research this problem. I can't recall any good search terms right now . Gerhard "Ask Me After Some Coffee" Paseman, 2018.04.30. $\endgroup$ Apr 30, 2018 at 15:38

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.