Products of Mersenne numbers as sums of real numbers

Question

A Mersenne number is a number of the form $2^k-1$ for some $k \in \mathbb{N}$. Consider the set of $2^n-1$ products of Mersenne numbers $$M_n=\left\{ \prod_{k\in S} (2^k-1) : S \subseteq [n], S\neq \emptyset\right\}.$$

Question: What is the minimum $r \in \mathbb{N}$ for which there exists $\alpha_1,\dots, \alpha_r \in \mathbb{R}$ such that for all $S \subseteq [n]$ there exists $T \subseteq [r]$ for which $\sum_{a \in T} \alpha_a = \prod_{k\in S} (2^k-1)$?

Known so far: A linear lower bound.

One can prove that for any $S \neq R \subseteq [n]$, it holds that $\prod_{k\in S} (2^k-1) \neq \prod_{k\in R} (2^k-1)$, so $M_n$ consists of $2^n-1$ distinct numbers. Since subset sums of a set of $r$ real numbers can take at most $2^r$ values, it follows that $r \geq n$. Can we prove a superlinear lower bound?

Our intuition is that there should be a superlinear lower bound, because the numbers in $M_n$ are somewhat "spread out." For example, they range from 1 to $\sim2^{n^2}$, and if you place the elements of $M_n$ in strictly increasing order $$1=m_1 <\dots < m_{2^n-1}\sim 2^{n^2},$$ then it is not hard to prove that $\frac{m_{i+1}}{m_{i}}\leq 3$ for all $i=1,\dots, 2^n-2$.

Where this question comes from

We arrived at this question because a superlinear lower bound would give us new lower bounds on the "stabilizer rank" of $n$ copies of the quantum T-state, which would have important implications for classical simulation of quantum circuits.

To avoid posting an XY question, I briefly mention that the above question is a reduction from the following: We would like a lower bound on $c \in \mathbb{N}$ for which there exists a $\{0, \pm 1, \pm i\}$-valued matrix $A \in \mathbb{C}^{2^n-1 \times c}$ for which $M_n$, viewed as a $2^n-1$-dimensional vector, lies in the image of $A$. A lower bound for the main question of this post would imply a lower bound for the question in this paragraph, but not necessarily the other way around.

Answer 1

We can indeed get a superlinear lower bound. I prove a lower bound of $\tilde\Omega(n^2+n)$ (ignoring log factors). I thank Gerry Myerson for pointing out the following helpful reference in the comments:

Moulton, David. (2001). Representing Powers of Numbers as Subset Sums of Small Sets. Journal of Number Theory - J NUMBER THEOR. 89. 193-211. 10.1006/jnth.2000.2646.

I borrow heavily from the proof of Theorem 1 in the cited work.

Claim: There exists a subset $N_n \subseteq M_n$ of size $l=\Omega(n^2+n)$ for which $2<\frac{n_{i+1}}{n_i}\leq 3$ for all $i=1,\dots, l$, where $n_1 <\dots<n_l$ are the elements of $N_n$ in increasing order.

Proof: Let $n_1=1$, and proceed inductively. If $n_i=\prod_{k \in S} (2^k-1)$, and $2 \notin S$, then let $n_{i+1}=\prod_{k \in S \cup \{2\}} (2^k-1)$, so $n_{i+1}/n_{i}=3$. More generally, if $1,\dots, t \in S$, but $t+1 \notin S$, then let $T=S \setminus\{t\} \cup \{t+1\}$, and let $n_{i+1}=\prod_{k \in T} (2^k-1)$. Then $$\frac{n_{i+1}}{n_{i}}= \frac{2^{t+1}-1}{2^t-1},$$ which satisfies the desired bounds.

Since $n_{i+1}/n_i \leq 3$ for all $i$, we can continue constructing these sets inductively as long as $3^l \leq \prod_{k \in [n]} (2^k-1)$. It is easy to check that $\prod_{k \in [n]} (2^k-1) \geq 2^{\binom{n+1}{2}-1}$, so we can choose $l=\Omega(n^2+n)$. This proves the claim. $\square$

Now, suppose that, in the language of the cited work, $b=(b_1,\dots, b_d)^T\subseteq \mathbb{R}^d$ is a representation of $N_n$. So there exist $\{0,1\}$-valued vectors $c_1,\dots, c_l\in \{0,1\}^d$ for which $n_i=c_i^T b$ for all $i \in [l]$.

Suppose there exists $u_1,\dots, u_l, v_1, \dots, v_l \in \{0,1\}$ such that

$$ \sum_{j=1}^l u_j c_j = \sum_{j=1}^l v_j c_j. $$ Then applying $b^T$ to both sides gives $$ \sum_{j=1}^l u_j n_j = \sum_{j=1}^l v_j n_j. $$ Observe that this implies $u_j=v_j$ for all $j=1,\dots, l$. Indeed, it suffices to prove that $n_{j+1} > n_1+\dots+ n_{j}$ for all $j \in [l]$, which we prove by induction. The base case $j=1$ is trivial. For larger $j$, we have $n_1+\dots+ n_{j}<2 n_{j} < n_{j+1}$. The first inequality is the induction hypothesis, and the second uses properties of $N_n$.

Now, there are at most $2^l-1$ choices of $u_1,\dots, u_l \in \{0,1\}$, excluding the case $u_1=\dots = u_l = 1$. Since each $c_j$ is a $\{0,1\}$-valued $d$-dimensional vector, each of these $2^l-1$ linear combinations has $d$ coordinates, each of which must be less than $l$. So there are $l^d$ possible linear combinations. If every single possibility occurred, then every standard basis vector $e_i$ would occur, and hence would have to be equal to some vector $c_i$, so we would get $d \geq l$, which would prove the desired lower bound.

Otherwise, there are at most $l^d-1$ possible values for these $2^l-1$ linear combinations. We have proven that these all must be distinct, so we must have $l^d-1 \geq 2^l-1$, i.e. $d \geq \frac{l}{log_2(l)}=\tilde\Omega(n^2+n)$. This completes the proof. $\square$