Products of Mersenne numbers as sums of real numbers

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.

• A related question is discussed in 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. May 27 '21 at 23:57
• Thank you for the reference! I feel very fortunate that a world expert on this topic came across my question :). These results seem to suggest that a superlinear lower bound is quite plausible.
– Ben
May 28 '21 at 1:39
• Moulton is the expert. I just gave him a push. May 28 '21 at 1:41

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