5
$\begingroup$

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.

$\endgroup$

1 Answer 1

9
$\begingroup$

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

$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$ Feb 12 at 8:18

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.