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.

  • $\begingroup$ 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. $\endgroup$ May 27 '21 at 23:57
  • $\begingroup$ 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. $\endgroup$
    – Ben
    May 28 '21 at 1:39
  • $\begingroup$ Moulton is the expert. I just gave him a push. $\endgroup$ 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<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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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