Efficiently stable presentations from error-correcting codes

This paper brings together a wide variety of interesting concepts, in order to rederive a result that formed a key step in the proof of the famous result that MIP${\mathstrut}^*$=RE by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. A description of that result can be found in the editorial introduction to a paper by those authors published in this journal.

The main theorem of this paper is a new kind of stability result concerning group representations. Let $G$ be a group with a presentation $\langle S\mid R\rangle$. That is, $S$ is a set of generators, and $R$ is a set of words in the generators that are equal to the identity. Let $\mu$ be some probability measure on $R$. Let $\mathcal F(S)$ be the free group on $S$ and let $\phi$ be a homomorphism from $\mathcal F(S)$ to the unitary group $U(n)$. That is, we choose a unitary matrix $A_s$ for each $s\in S$, and then
$$\phi(s_1^{m_1}\dots s_r^{m_r})=A_1^{m_1}\dots A_r^{m_r}.$$
We say that $\phi$ is an $(\epsilon,\mu)$-approximate homomorphism if the average of $\|\phi(r)-I\|$ is at most $\epsilon$, where $r$ is chosen randomly from $R$ according to the probability measure $\mu$, and the norm is the normalized Hilbert-Schmidt norm (its square is the sum of the squares of the absolute values of the matrix entries divided by $n$). In other words, we take a random relation in $G$, work out the corresponding unitary matrix, and see how close it is, in a suitable sense, to the identity.

The presentation $\langle S\mid R\rangle$ is then said to be stable if every approximate homomorphism is close to an exact homomorphism – that is, one for which all the relations map to the identity. Here, we say that $\phi$ and $\psi$ are close if $\|\phi(s)-\psi(s)\|$ is on average small for a random $s\in S$.

Note that this definition depends very strongly on the presentation $\langle S\mid R\rangle$ and not just on the group $G$. Previous stability results have tended to be about the entire group, stating, for various notions of closeness, that if $\phi(gh)\approx\phi(g)\phi(h)$ for every $g$ and $h$, then $\phi$ is close to a representation.

For the applications in this paper, it is important to have presentations that are not just stable but also efficient, in the sense of not having too many generators or relations. The main result of the paper is to give an example of a stable presentation of $\mathbb F_2^n$ that has quasipolynomially many generators and relations, a great improvement on more obvious presentations such as taking the $n$ standard basis vectors as generators and specifying for each pair of elements $x,y$ that they commute.

The construction is achieved with the help of coding theory, and in particular the notion of locally testable codes. A binary linear code is a subspace $V$ of $\mathbb F_2^n$ with the property that every non-zero element $v\in V$ has many non-zero coordinates – typically, one asks for there to be a linear number. If every non-zero codeword (that is, element of $V$) has at least $cn$ non-zero coordinates, then for any two distinct codewords $v$ and $w$, their Hamming distance is at least $cn$. Therefore, if we are given a vector $x\in\mathbb F_2^n$ and told that it is the result of taking a codeword $v$ and corrupting it by changing $r$ bits, for some $r<cn/2$, then we can reconstruct $v$.

For this reason we care about the distance to $V$, which can be very hard to calculate or even estimate. However, for specially designed codes, it is tractable. We can think of $V$ as the set of solutions of some linear equations over $\mathbb F_2$. A locally testable code has the remarkable property that the distance from $x$ to $V$ corresponds well to the number of linear equations (from some suitably chosen set of equations that determine $V$) that $x$ fails to satisfy.

The work of this paper, combined with recent work of de la Salle, results in a proof of an important part of the MIP${\mathstrut}^*$=RE breakthrough, with its consequent disproof of the Connes embedding conjecture, that is more accessible, especially to mathematicians not working in complexity theory. A possible motivation to make the effort to understand these ideas better is that there is some hope, as mentioned briefly here and in more detail in the original MIP${\mathstrut}^*$=RE paper, that they could lead to the construction of a non-sofic group, thus resolving another major open problem.