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

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.

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. 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. 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. 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).$$

• To improve the upper bound, you can apply the algorithm recursively for every prime $p$ in $Q$ (grouping numbers divisible by $p$). I have not worked out the recurrence relation. Feb 12 at 8:18