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](https://meta.stackexchange.com/a/66378/997104), 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.



Products of Mersenne numbers as sums of real numbers
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$


