How many numbers are needed such that the possible subset sums cover $\{1, \frac{1}{2}, \frac{1}{3},\dots, \frac{1}{2^m}\}$?

Question

For a multiset $N$ of positive numbers, the set of possible subset sums is $f(N)=\{s\in \mathbb{R}: \exists S\in 2^N, s=\sum_{a\in S} a\}$. We say $N$ generates $T$ if $T\subseteq f(N)$. For example, given a three-number set $\{1,2,3\}$, the possible subset sums is $f(\{1,2,3\})=\{1,2,3,4,5,6\}$. Then we say $\{1,2,3\}$ can generate $\{2,3,5,6\}$.

The question is how many numbers are needed to generate $\{1, \frac{1}{2}, \frac{1}{3},\dots, \frac{1}{2^m}\}$? A trivial low bound is $m$ and a trivial upper bound is $2^m$. Is it possible to only use, say $poly(m)$ or $o(2^m)$ numbers?

I think it is possible that a similar question has been studied before. But I don't know the precise name.

Answer 1

The problem itself was studied in this paper and was proved to be $\mathsf{NP}$-complete given the target set $T$ as the input.

For this specific instance $T=\{1,1/2,1/3,\ldots,1/n\}$, we can show that $\Omega(n/\log n)$ numbers are necessary and $O(n\log\log n/\log n)$ numbers suffice. The proofs use the prime number theorem that $\pi(n)\sim n/\ln n$, where $\pi(n)$ is the number of primes $\leq n$.

Lower Bound

We show the lower bound even for generating $T'=\{1/p\mid p\textrm{ prime}, n/2<p\leq n\}$. Note that $|T'|=\pi(n)-\pi(n/2)=\Theta(n/\log n)$.

Suppose $T'$ can be generated by $k<|T'|$ numbers, then each element $1/p\in T'$ corresponds to a vector in $v_p\in\{0,1\}^k$ indicating the subset whose sum is $1/p$. These vectors must be linearly dependent; In fact, if we assign a weight $w_p\in\{0,1,2,\ldots,n/2-1\}$ for each vector and consider the possibilities of the sum $$\sum_{1/p\in T'}w_pv_p\in\{0,1,\ldots,|T'|\cdot (n/2-1)\}^k,$$ we can use the pigeonhole principle to find a collision, as long as $$(n/2)^{|T'|}>(|T'|\cdot n/2)^k,$$ which is satisfied for some $k=\Theta(|T'|)=\Theta(n/\log n)$. The collision means that we have two disjoint subsets $T_1,T_2\subset T'$ and non-zero weights $w'_p\in\{1,2,\ldots,n/2-1\}$ such that $$\sum_{1/p\in T_1}w'_pv_p=\sum_{1/p\in T_2}w'_pv_p\quad\Rightarrow\quad \sum_{1/p\in T_1}w'_p/p=\sum_{1/p\in T_2}w'_p/p.$$ It's easy to see a contradiction here: Multiplying both sides with the products of those $p$ to make them integral, then for each $p$ only one term is not a multiple of $p$ as $w'_p<p$. That means $k\geq\Omega(n/\log n)$.

Upper Bound

Notice that we only need to generate the integral set $\{n!,n!/2,n!/3,\ldots,n!/n\}$. Let the set of smaller primes be $P=\{p\textrm{ prime}\mid p\leq n/\log n\}$, while the remaining ones are larger primes $Q=\{p\textrm{ prime}\mid n/\log n<p\leq n\}$. Note that $|P|=\pi(n/\log n)=O(n/\log^2 n)$.

Let $X$ be the numbers in $\{1,\ldots,n\}$ that are divisible by some $p\in Q$, then using the sum of prime reciprocals we get $$|X|\leq\sum_{p\in Q}\frac{n}{p}=n\cdot O\left(\ln\ln n-\ln\ln(n/\log n)\right)=O(n\log\log n/\log n).$$ For every $i\in X$ we add $n!/i$ to the generating set so that it could be generated trivially. For $i\notin X$, we let $g=\mathrm{gcd}\{n!/i\mid i\notin X\}$ and generate $n!/(ig)$ using powers of $2$. Therefore we only need to bound the largest one, which is $n!/g$.

To do so, first notice that the only prime factors of $n!/g$ are the ones in $P$. For each $p\in P$, the highest power of $p$ that divides $n!/g$ is the highest power of $p$ in any $i\notin X$, which is at most $\lfloor \log_p n\rfloor$. Therefore $$n!/g\leq \prod_{p\in P} p^{\lfloor \log_p n\rfloor}\leq n^{|P|}.$$ So the size of the generating set with binary representation is $$\lfloor\log_2 (n!/g)\rfloor+1=O(|P|\log n)=O(n/\log n).$$