The 4M-4 Conjecture is False!

Posted on by Dustin G. Mixon

Congratulations to Cynthia Vinzant for disproving the 4M-4 conjecture! The main result of her 4-page paper is the existence of a 4\times 11 matrix \Phi such that x\mapsto |\Phi x|^2 is injective modulo a global phase factor (indeed, 11<12=4(4)-4). This is not Cynthia’s first contribution to this problem—her recent paper with Conca, Edidin and Hering proves that the conjecture holds for infinitely many M.

cvinzant2

I wanted to briefly highlight the main idea behind this paper: She provides an algorithm that, on input of a 4\times 11 matrix \Phi with complex rational entries, either outputs “not known to be injective” or outputs “injective” along with a certificate of injectivity. The algorithm is fundamentally based on the following characterization of injectivity:

Lemma (Lemma 9 in this paper). \Phi=[\varphi_1\cdots\varphi_N] yields injectivity if and only if the null space of X\mapsto\{\langle X,\varphi_k\varphi_k^*\rangle_\mathrm{HS}\}_{k=1}^N does not contain a nonzero Hermitian matrix of rank \leq2.

Let’s give real coordinates to an arbitrary 4\times 4 Hermitian matrix:

\displaystyle{A_{jk}=\left\{\begin{array}{cl}x_{jj}&\mbox{if }j=k\\ x_{jk}+iy_{jk}&\mbox{if }j<k\\ x_{jk}-iy_{jk}&\mbox{if }j>k\end{array}\right..}

As such, every such matrix has coordinates \{x_{jk}\}_{j\leq k}\cup\{y_{jk}\}_{j<k}\in\mathbb{R}^{16}. By the lemma, we get injectivity if there is a nonzero point in \mathbb{R}^{16} such that the corresponding matrix lies in both the null space from the lemma defined by \Phi and the set of matrices of rank \leq2. Both of these sets can be expressed as algebraic varieties, that is, solutions to systems of polynomial equations (indeed, each equation for the null space is of the form \ell_k:=\langle X,\varphi_i\varphi_i^*\rangle_\mathrm{HS}=0, whereas each equation for the other set is simply a 3\times 3 minor m_{jk} equaling zero). Overall, given a 4\times 11 matrix \Phi, the goal is to certify that there is no real nonzero solution to

m_{jk}=\ell_k=0 \quad \forall j,k. \quad (1)

This algorithm follows two main steps:

Step 1: Certify that (1) has no real solutions with y_{34}\neq0.

Here’s how: Use Grobner bases and elimination to find (certificate) polynomials p_{jk},q_{k}\in\mathbb{Q}[i][x_{11},\ldots,x_{44},y_{12},\ldots,y_{34}] such that

f:=\sum_{j,k}p_{jk}m_{jk}+\sum_kq_k\ell_k\in\mathbb{Q}[x_{34},y_{34}].

Notice that scalar multiples of solutions to (1) are also solutions. As such, y_{34}=1 without loss of generality. One may use Sturm sequences to quickly check that the univariate polynomial f(x_{34},1) has no real roots, thereby concluding this step.

Step 2: Certify that (1) has no nonzero complex solution with y_{34}=0.

Here’s how: Since the desired solution is nonzero, there exists a nonzero coordinate. By scale invariance, this coordinate equals 1 without loss of generality. For each of the 15 coordinates u other than y_{34} (e.g., u=x_{12}), we will certify that there is no nonzero complex solution with y_{34}=0 and u=1. Specifically, use Grobner bases to find (certificate) polynomials r,s,p_{jk},q_k\in\mathbb{Q}[i][x_{11},\ldots,x_{44},y_{12},\ldots,y_{34}] such that

r(u-1)+sy_{34}+\sum_{j,k}p_{jk}m_{jk}+\sum_kq_k\ell_k=1. \quad (2)

This identity implies that (1) has no nonzero complex solution with y_{34}=0 and u=1, thereby concluding this step.

If either of the steps fails to produce the desired certificates, output “not known to be injective.” Otherwise, output “injective” along with all of the certificate polynomials.

Cynthia applied this algorithm to what appears to be a randomly generated matrix \Phi to ultimately disprove part (a) of the 4M-4 conjecture. She also ran the algorithm on perturbations of the last coordinate of the last column of \Phi to peruse the space of injective ensembles. See Figure 3 of the paper for a plot of the acceptable choices for this coordinate.

I wanted to point out a couple of things. First, the philosophy of a certificate is that it’s typically easier to use the certificate to check the purported answer than to prove the answer directly. In this case, one would use the first certificates to compute f and apply Sturm’s theorem, and then use the other certificates to compute identities of the form (2). Presumably, this is more computationally efficient than finding Grobner bases, which are apparently slow to compute in the worst case. Also, the certificate manipulations certainly take polynomial time in the length of the certificate, but it’s unclear how long the certificate actually is (in fact, for the main counterexample, the certificate was apparently too long to include in the paper!) Of course, this has no bearing on the status of the 4M-4 conjecture, but I’m independently interested in certifiable injectivity for phase retrieval. Cynthia made implementations of her algorithm available here, so that will help me investigate further.

The second thing to point out is that the current algorithm is incapable of declaring “not injective.” If the first step fails, you only know that there is some complex solution with y_{34}=1 and x_{34} real. If the second step fails, you only know that there is some complex solution with y_{34}=0 and some other coordinate equal to 1. Indeed, you need a real nonzero solution in order to declare “not injective.”

Now that part (a) of the 4M-4 conjecture is known to be false, we are left with two open problems:

Problem 1. For each M, what is the smallest N for which there exists an M\times N matrix \Phi such that x\mapsto|\Phi x|^2 is injective modulo a global phase factor?

Problem 2. For each M, what is the smallest N for which a generic M\times N matrix \Phi will render x\mapsto|\Phi x|^2 injective modulo a global phase factor?

At the moment, we know the solution to Problems 1 and 2 is N=4M-4 whenever M has the form M=2^k+1 (thanks to Cynthia’s other paper). Cynthia’s new paper now proves that Problem 1 has a different solution when M=4. I still suspect that N=4M-4 is the solution Problem 2 in general, but time will tell. On the other hand, if the answers to Problems 1 and 2 ever differ, then this would be fundamentally different from the real case (in which both answers are known to coincide at N=2M-1).

Congrats again to Cynthia! I asked, and she’ll present this at SampTA this year, so I’ll buy her the beverage I promised when I see her there.

One thought on “The 4M-4 Conjecture is False!”

  1. Pingback: Conjectures from SampTA | Short, Fat Matrices

Leave a comment