<p>The problem itself was studied in <a href="https://www.cs.unm.edu/%7Esaia/papers/SubsetRep.pdf" rel="noreferrer">this paper</a> and was proved to be <span class="math-container">$\mathsf{NP}$</span>-complete given the target set <span class="math-container">$T$</span> as the input.</p>
<p>For this specific instance <span class="math-container">$T=\{1,1/2,1/3,\ldots,1/n\}$</span>, we can show that <span class="math-container">$\Omega(n/\log n)$</span> numbers are necessary and <span class="math-container">$O(n\log\log n/\log n)$</span> numbers suffice. The proofs use the prime number theorem that <span class="math-container">$\pi(n)\sim n/\ln n$</span>, where <span class="math-container">$\pi(n)$</span> is the number of primes <span class="math-container">$\leq n$</span>.</p>
<h3>Lower Bound</h3>
<p>We show the lower bound even for generating <span class="math-container">$T'=\{1/p\mid p\textrm{ prime}, n/2&lt;p\leq n\}$</span>. Note that <span class="math-container">$|T'|=\pi(n)-\pi(n/2)=\Theta(n/\log n)$</span>.</p>
<p>Suppose <span class="math-container">$T'$</span> can be generated by <span class="math-container">$k&lt;|T'|$</span> numbers, then each element <span class="math-container">$1/p\in T'$</span> corresponds to a vector in <span class="math-container">$v_p\in\{0,1\}^k$</span> indicating the subset whose sum is <span class="math-container">$1/p$</span>. These vectors must be linearly dependent; In fact, if we assign a weight <span class="math-container">$w_p\in\{0,1,2,\ldots,n/2-1\}$</span> for each vector and consider the possibilities of the sum
<span class="math-container">$$\sum_{1/p\in T'}w_pv_p\in\{0,1,\ldots,|T'|\cdot (n/2-1)\}^k,$$</span>
we can use the pigeonhole principle to find a collision, as long as
<span class="math-container">$$(n/2)^{|T'|}&gt;(|T'|\cdot n/2)^k,$$</span>
which is satisfied for some <span class="math-container">$k=\Theta(|T'|)=\Theta(n/\log n)$</span>. The collision means that we have two disjoint subsets <span class="math-container">$T_1,T_2\subset T'$</span> and non-zero weights <span class="math-container">$w'_p\in\{1,2,\ldots,n/2-1\}$</span> such that
<span class="math-container">$$\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.$$</span>
It's easy to see a contradiction here: Multiplying both sides with the products of those <span class="math-container">$p$</span> to make them integral, then for each <span class="math-container">$p$</span> only one term is not a multiple of <span class="math-container">$p$</span> as <span class="math-container">$w'_p&lt;p$</span>. That means <span class="math-container">$k\geq\Omega(n/\log n)$</span>.</p>
<h3>Upper Bound</h3>
<p>Notice that we only need to generate the integral set <span class="math-container">$\{n!,n!/2,n!/3,\ldots,n!/n\}$</span>.
Let the set of smaller primes be <span class="math-container">$P=\{p\textrm{ prime}\mid p\leq n/\log n\}$</span>, while the remaining ones are larger primes <span class="math-container">$Q=\{p\textrm{ prime}\mid n/\log n&lt;p\leq n\}$</span>. Note that <span class="math-container">$|P|=\pi(n/\log n)=O(n/\log^2 n)$</span>.</p>
<p>Let <span class="math-container">$X$</span> be the numbers in <span class="math-container">$\{1,\ldots,n\}$</span> that are divisible by some <span class="math-container">$p\in Q$</span>, then using the <a href="https://en.wikipedia.org/wiki/Mertens%27_theorems#Second_theorem" rel="noreferrer">sum of prime reciprocals</a> we get
<span class="math-container">$$|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).$$</span>
For every <span class="math-container">$i\in X$</span> we add <span class="math-container">$n!/i$</span> to the generating set so that it could be generated trivially. For <span class="math-container">$i\notin X$</span>, we let <span class="math-container">$g=\mathrm{gcd}\{n!/i\mid i\notin X\}$</span> and generate <span class="math-container">$n!/(ig)$</span> using powers of <span class="math-container">$2$</span>. Therefore we only need to bound the largest one, which is <span class="math-container">$n!/g$</span>.</p>
<p>To do so, first notice that the only prime factors of <span class="math-container">$n!/g$</span> are the ones in <span class="math-container">$P$</span>. For each <span class="math-container">$p\in P$</span>, the highest power of <span class="math-container">$p$</span> that divides <span class="math-container">$n!/g$</span> is the highest power of <span class="math-container">$p$</span> in any <span class="math-container">$i\notin X$</span>, which is at most <span class="math-container">$\lfloor \log_p n\rfloor$</span>. Therefore
<span class="math-container">$$n!/g\leq \prod_{p\in P} p^{\lfloor \log_p n\rfloor}\leq n^{|P|}.$$</span>
So the size of the generating set with binary representation is
<span class="math-container">$$\lfloor\log_2 (n!/g)\rfloor+1=O(|P|\log n)=O(n/\log n).$$</span></p>

CC BY-SA 4.0
2024-02-12T08:18:08.107Z
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.
Dmytro Taranovsky
CC BY-SA 4.0
2024-09-12T21:59:37.913Z
Update on the above comment:  We have $Θ(2^{-i}n/\log n)$ primes between $2^{-i-1}n$ and $2^{-i} n$  with $i = O(\log \log n)$, and the base algorithm uses $O(2^i/i ⋅ \log i)$ elements per prime. Integrating over $i$, we get $O(n/\log n ⋅ \log^2 i)$ or $O(n / \log n ⋅ \log^2 \log \log n)$ elements.  Iterating, we get $O(n / \log n ⋅ \log^{(3)} n ⋅ \log^{(4)} n \, ⋅ ... ⋅ \log^{(k)} n ⋅ (\log^{(k+1)} n)^2)$ for every $k$, where $\log^{(k)}$ indicates $k$-fold iteration rather than power.
Dmytro Taranovsky
CC BY-SA 4.0
2024-02-12T00:40:32.923Z
2024-02-12T05:06:01.573Z
2024-02-12T05:06:01.573Z
Wei Zhan
<p>For a multiset <span class="math-container">$N$</span> of positive numbers, the set of possible subset sums is <span class="math-container">$f(N)=\{s\in \mathbb{R}: \exists S\in 2^N, s=\sum_{a\in S} a\}$</span>. We say <span class="math-container">$N$</span> <em>generates</em> <span class="math-container">$T$</span> if <span class="math-container">$T\subseteq f(N)$</span>. For example, given a three-number set <span class="math-container">$\{1,2,3\}$</span>, the possible subset sums is <span class="math-container">$f(\{1,2,3\})=\{1,2,3,4,5,6\}$</span>. Then we say <span class="math-container">$\{1,2,3\}$</span> can generate <span class="math-container">$\{2,3,5,6\}$</span>.</p>
<p>The question is how many numbers are needed to generate <span class="math-container">$\{1, \frac{1}{2}, \frac{1}{3},\dots, \frac{1}{2^m}\}$</span>? A trivial low bound is <span class="math-container">$m$</span> and a trivial upper bound is <span class="math-container">$2^m$</span>. Is it possible to only use, say <span class="math-container">$poly(m)$</span> or <span class="math-container">$o(2^m)$</span> numbers?</p>
<p>I think it is possible that a similar question has been studied before. But I don't know the precise name.</p>

<reference-request><subset-sum>
How many numbers are needed such that the possible subset sums cover $\{1, \frac{1}{2}, \frac{1}{3},\dots, \frac{1}{2^m}\}$?
Mengfan Ma
# How many numbers are needed such that the possible subset sums cover $\{1, \frac{1}{2}, \frac{1}{3},\dots, \frac{1}{2^m}\}$?

(Asked by: username_0 on 2024-02-11)

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.

**Tags:** reference-request, subset-sum

---

## 1 answers

### Answer by username_1 on 2024-02-12. Score: 9 | Accepted answer

The problem itself was studied in [this paper](https://www.cs.unm.edu/%7Esaia/papers/SubsetRep.pdf) 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](https://en.wikipedia.org/wiki/Mertens%27_theorems#Second_theorem) 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).$$

> **Comments:**
> **username_2**: 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.  
> **username_2**: Update on the above comment:  We have $Θ(2^{-i}n/\log n)$ primes between $2^{-i-1}n$ and $2^{-i} n$  with $i = O(\log \log n)$, and the base algorithm uses $O(2^i/i ⋅ \log i)$ elements per prime. Integrating over $i$, we get $O(n/\log n ⋅ \log^2 i)$ or $O(n / \log n ⋅ \log^2 \log \log n)$ elements.  Iterating, we get $O(n / \log n ⋅ \log^{(3)} n ⋅ \log^{(4)} n \, ⋅ ... ⋅ \log^{(k)} n ⋅ (\log^{(k+1)} n)^2)$ for every $k$, where $\log^{(k)}$ indicates $k$-fold iteration rather than power.  

---

