By instantiating $\code$ using the Reed-Muller code from Section <ref> we obtain an efficient qubit test.  Because we do not know if $G(h_\bRM)$ is Abelian, we need to introduce an additional test for the relations $\{R_k^\com\}$ in (<ref>). The resulting test is described in Figure <ref>. It is a variant of a test first introduced in [36] (with a flawed analysis). This paper (together with the work on which our analysis relies) corrects this. In the next section we detail an important application of this test in the work <ref>.

Let $h_\bRM\in \F_2^{M\times N}$ be the parity check matrix for $\code_\bRM$ considered in Section <ref>. Here, $N=q^{m+1}$ and $M=q^{m+2}(1+m)$. Let $\mu_R$ be the distribution on relations (<ref>) described in Section <ref>. Execute either of the following tests with probability $1/4$ each.

* Code test: Identical to that in Figure <ref>.

* (Anti-)commutation test: Identical to that in Figure <ref>.

* Consistency test: Identical to that in Figure <ref>.

* Pairwise commutation test: Sample $(i,i')\in \{1,\ldots,N\}^2$ according to the distribution $\mu_R$, conditioned on choosing a relation from $R_k^\com$, and $W\in \{X,Z\}$ uniformly at random.
Let $\omega=(E_\code e_{i}, E_\code e_{i'})$.
Sample a pair of questions $(x_c,y_c)$ as in the commutation game. If either question is $x_{X,0}$ or $x_{Z,0}$, replace it with $(W,\var,i)$ or $(W,\var,i')$ respectively. Otherwise, send the original question together with $\omega$, i.e. $(x_c,\omega)$ or $(y_c,\omega)$ respectively. Accept if and only if the players' answers are accepted in the commutation game.

The quantum low-degree test, obtained by adapting the braiding test from Figure <ref> to the $[q^{m+1},t(d+1)^m,D']_2$ code $\code_\bRM$.

Let $\code_\bRM$ be the $[q^{m+1},t(d+1)^m,D']_2$ Reed-Muller from Section <ref>, and $M=(h_\bRM,\nu_\bRM)$ the $(d+2)$-local tester for $\code_\bRM$ described in Figure <ref>. Then the associated braiding test (Figure <ref>) is a $(k,\delta')$-qubit test with error function $\delta' = \poly(m,d,t)\cdot\poly(\eps,q^{-1})$.

Let $\strategy$ be a synchronous strategy that succeeds in the braiding test with probability at least $1-\eps$. Then in particular the strategy succeeds with probability at least $1-4\eps/3$ in the braiding test over $\code_\bRM$. Since $(\code_\bRM,M)$ is not known to be abelian, we cannot apply Theorem <ref> directly. However, we can follow its proof.

The completeness part of the proof follows in a straightforward manner, since the measurement operators $P^{(W,\var,i)}$ and $P^{(W,\var,i')}$ defined in the proof pairwise commute, for any pair $(i,i')\in \{1,\ldots,N)^2$.

For the soundness part, we first define the same pair of strategies $\strategy^X$ and $\strategy^Z$ for $G_{\code_\bRM,M}$. Applying Proposition <ref>, we deduce an $O(d\eps)$-homomorphism of the presentation (<ref>) of $G(h_\bRM)$. However, we are interested in constructing an approximate homomorphism of the presentation (<ref>), which in addition contains the relations $R_k^\com$. The fact that $x_i \mapsto \widehat{P}^{(W,\var,i)}$ satisfies these relations, on average and according to the distribution $\mu_R$, follows from success in the pairwise commutation test executed as part of the Pauli braiding test (Figure <ref>). Thus we obtain that $x_i \mapsto \widehat{P}^{(W,\var,i)}$ is an $(O(d\eps),\mu_R)$-homomorphism of the presentation (<ref>). Applying Theorem <ref>, and similarly to the proof of Theorem <ref> we obtain a pair of POVMs $\{\tilde{P}^W_u\}_{u\in\F_2^N}$, for $W\in\{X,Z\}$, such that defining $\tilde{P}^{W,i}_b = \sum_{u:u_i=b} \tilde{P}^W_u$ these operators satisfy (<ref>), with right-hand side $\delta_2 = \delta(O(d\eps))$, with $\delta$ the soundness function from Theorem <ref>. From here on the proof proceeds exactly as the proof of Theorem <ref>.

§.§ Dimension bounds

The next proposition states a simple consequence of a qubit test, which is that strategies with a high enough success probability must have a large dimension. This consequence is used in [27].

Let $G = (\mX,\mu,\mA,D)$ denote a $(k,\delta(\eps))$-qubit test. Then all synchronous strategies $\strategy$ in $(\mM,\tau)$ for $G$ that succeed with probability $1 - \eps$ must satisfy

\[
\dim(\mM) \geq \Big( 1 + O(\sqrt{\delta(\eps)}) + \frac{\delta(\eps)}{1 - \delta(\eps)}\Big)^{-1} 2^k~.
\]

If $\mM$ is infinite-dimensional, then we are done. Suppose instead it were finite-dimensional. Then $\mM$ must be (isomorphic to) a direct sum of finite-dimensional matrix algebras. Without loss of generality we assume that $\mM = M_{d}(\C)$ with the dimension-normalized trace $\tau = \frac{1}{d} \Tr$.

By the soundness property of qubit tests, the strategy $\strategy$ is $(\delta(\eps),\tilde{\mu})$-close to a strategy $\strategy'$ on an algebra $(M_{2^k}(\C) \otimes \mN,\tr_{2^k} \otimes \tau')$ for some tracial algebra $(\mN,\tau')$ where $\tr_{2^k} = 2^{-k} \Tr$. For notational brevity we write $\mR = M_{2^k}(\C) \otimes \mN$ and $\tau^{\mR} = \tr_{2^k} \otimes \tau'$. By definition there exists a projection $P \in \mM_\infty$ of finite trace and a partial isometry $w \in P \mM_\infty 1_\mM$ satisfying

* $\mR = P \mM_\infty P$.

* $\max \left \{ \tau(1_\mM - w^* w), \tau^{\mR} (P - w w^*) \right \} \leq \delta(\eps)$.

* $\tau^{\mR} = \tau_\infty/\tau_\infty(P)$.

For $u \in \F_2^k$ let $\sigma^Z_u$ denote the projection

\[
\sigma^Z_u = 2^{-k} \sum_{a \in \F_2^k} (-1)^{a \cdot u} \sigma^Z(a)~.
\]

It is easy to verify that $\{\sigma^Z_u \otimes I_\mN \}_{u \in \F_2^k}$ is a projective measurement in $\mR$ and furthermore $\tau^{\mR}(\sigma^Z_u \otimes I_\mN) = 2^{-k}$. Applying <Ref> we get that there exists a projective measurement $\{Q_u\}_{u \in \F_2^k}$ on $\mM$ such that

\[
\sum_u \| Q_u - w^* (\sigma^Z_u \otimes I_\mN) w \|_2^2 \leq 56\, \delta(\eps)~.
\]

Applying <Ref> we get

\[
\sum_u \tau \Big ( \Big| Q_u - w^* (\sigma^Z_u \otimes I_\mN) w\Big| \Big) \leq O(\sqrt{\delta(\eps)})~.
\]

Then we have

\begin{align*}
\sum_u \Big| \tau(Q_u) - 2^{-k} \Big| &\leq \sum_u \Big | \tau(w^* (\sigma^Z_u \otimes I_\mN) w) - 2^{-k} \Big| + \tau \Big ( \Big| Q_u - w^* (\sigma^Z_u \otimes I_\mN) w\Big| \Big) \\
&= O(\sqrt{\delta(\eps)}) + \sum_u \Big | \tau_\infty (w w^* (\sigma^Z_u \otimes I_\mN)) - 2^{-k} \Big| \\
&= O(\sqrt{\delta(\eps)}) + \sum_u \Big | \tau_\infty (P (\sigma^Z_u \otimes I_\mN)) - 2^{-k} \Big| + \Big | \tau_\infty((P - ww^*)(\sigma^Z_u \otimes I_\mN)) \Big|
%	&\leq O(\sqrt{\delta(\eps)}) + \sum_u \| P - ww^* \| \tau_\infty( |  \sigma^Z_u \otimes I_\mN |)
\end{align*}

Notice that $\tau_\infty (P (\sigma^Z_u \otimes I_\mN)) = \tau_\infty (\sigma^Z_u \otimes I_\mN) = 2^{-k}$, and that $ww^* \leq P$ and thus $\tau_\infty((P - ww^*)(\sigma^Z_u \otimes I_\mN))$ is a nonnegative real number. Therefore the sum in the last line simplifies to

\[
\sum_u \tau_\infty((P - ww^*)(\sigma^Z_u \otimes I_\mN)) = \tau_\infty((P - ww^*) P) = \tau_\infty(P - ww^*) \leq \tau_\infty(P) \cdot \delta(\eps)~.
\]

On the other hand the proof of <Ref> shows that $\tau_\infty(P) \leq \frac{1}{1 - \delta(\eps)}$, and thus

\[
\sum_u \Big| \tau(Q_u) - 2^{-k} \Big| \leq O(\sqrt{\delta(\eps)}) + \frac{\delta(\eps)}{1 - \delta(\eps)}~.
\]

By averaging, there exists a $u \in \F_2^k$ such that

\[
\tau(Q_u) = \frac{1}{d} \Tr(Q_u) \leq  \Big( 1 + O(\sqrt{\delta(\eps)}) + \frac{\delta(\eps)}{1 - \delta(\eps)}\Big) 2^{-k}~.
\]

Rearranging, this implies that $d$, the dimension of $\mM$, satisfies

\[
d \geq \Big( 1 + O(\sqrt{\delta(\eps)}) + \frac{\delta(\eps)}{1 - \delta(\eps)}\Big)^{-1} 2^k
\]

as desired.

§ LOWER BOUNDS ON THE MODULUS OF STABILITY OF (<REF>)

In this Appendix we prove Lemma <ref>, and deduce some corollaries from it.
Before diving into the proof, we first sketch the idea behind it.
We provide a method for translating every graph $([k],E\subseteq{\binom{[k]}{2}})$ into a collection of order $2$ unitaries $A_1,...,A_k$ (actually, permutations) that satisfy that

\begin{equation}\label{eq:commuting_or_not}
\forall ij\in \binom{[k]}{2}\ \colon\ \ \|A_iA_j-A_jA_i\|_\tau^2=\begin{cases}
2 & ij\in E,\\
0 & ij\notin E.
\end{cases}
\end{equation}

Therefore, these unitaries correspond to an $(\nicefrac{|E|}{\binom{k}{2}},\mu_R)$-approximate representation of (<ref>). For any pair $ij\in E$ we have $\|A_iA_j-A_jA_i\|_\tau^2=2$, and thus the unitaries $A_i$ and $A_j$ would need to be changed  by some constant amount to make them commute. Thus, to fix the $A_i$'s into a genuine representation of $\Z_2^k$, we would need to move them by at least a constant times the proportion of the largest   matching which embeds in $E$. Hence, by choosing a graph which is already a  matching with $c$ edges, we deduce the Lemma.

We begin by describing our construction. Given a graph $([k],E)$, the permutations $\{A_i\}_{i=1}^k$ act on  the set $\field^{[k]\cup E}$, namely bit strings  indexed by the vertices and edges of the graph. Now, each $A_i$ flips the $i^{\rm th}$ bit. Furthermore, it conditionally flips the  $ij^{\rm th}$  bit for $ij\in E$ where $i<j$, if the $j^{\rm th}$ bit is $1$. Namely, the $A_i$'s act as a NOT gate on the $i^{\rm th}$ bit composed with CNOT gates on all the $ij^{\rm th}$ bits, where $i<j$ and $ij\in E$. Now, all of these permutations are of order $2$. Equation (<ref>) is deduced by noting that  $A_iA_j=A_jA_i$ when $ij$ is not an edge, and that $A_iA_jA_iA_j$ has no fixed points when $ij$ is an edge — this is because $A_iA_jA_iA_j$ must flip the $ij^{\rm th}$ bit.
The von Neumann algebra $\mM$ containing the $A_i$'s is the one acting on $\complex^{\field^{[k]\cup E}}$ with its standard normalized trace $\tau^\cM(X)=\frac{1}{2^{k+|E|}}\Tr(X)$.

A version of this construction (viewed in a different way) was used by Kozlov–Meshulam [32] to upper bound the Cheeger constant of the $k$-dimensional hypercube — see Section 4.1 therein.

The map $x_i\mapsto A_i\in \cM$ is a $(\nicefrac{|E|}{\binom{k}{2}},\mu_R)$-approximate representation of $\Z_2^k$ with respect to the presentation (<ref>).

With probability $\frac{1}{2}$, $\mu_R$ samples an involution relation, which is always satisfied by the  $A_i$'s. Furthermore,

\[
\Expectation_{i\neq j\in [k]}\left[\Vert A_iA_jA_iA_j-\Id_\mM\Vert_\tau^2\right]=\frac{1}{\binom{k}{2}}\sum_{ij\in E}\Vert A_iA_jA_iA_j-\Id_\mM\Vert_\tau^2=\nicefrac{2|E|}{\binom{k}{2}}.
\]

By combining these two observations, we deduce the claim.

Assume the largest matching in $E$ contains $c$ edges. Then, for every collection $\{B_i\}_{i=1}^k$ of order $2$ unitaries which pairwise commute in $\mN=P\mM_\infty P$, and  every partial isometry $w=PU\Id_\mM\in P\mU(\mM_\infty)\Id_\mM$, we have

\[
\Expectation_{i\in [k]} \Vert A_i-w^* B_iw\Vert_\tau^2 \geq  \frac{c}{16k}
\]

\[
\tau^\mM(\Id_\mM-w^*w)\geq  \frac{c}{16k}.
\]

In particular, there is no genuine representation of $\Z_2^k$ that is $(\frac{c}{16k},\mu_S)$-close to the $A_i$'s.

Recall that given our von Neumann algebra $\mM$, the algebra $\mM_\infty$ acts on the Hilbert space $\complex^{\field^{[k]\cup E}}\otimes \complex^\Z$. Let $\{e_v\otimes e_t\mid v\in \field^{[k]\cup E},t\in \Z\}$ be the standard basis of this Hilbert space.
Let $\{B_i\}_{i=1}^k$ be order $2$ unitaries which pairwise commute in $\mN=P\mM_\infty P $, and assume  there is a partial isometry $w=PU\Id_\mM\in P\mU(\mM_\infty)\Id_\mM$ and  $0<\eps\leq 3-2\sqrt{2}\approx 0.17$ such that

\[
\Expectation_{i\in [k]} \Vert A_i-w^* B_iw\Vert_\tau^2\ ,\qquad  \tau^\mM(\Id_\mM-w^*w)\leq  \eps.
\]

This is a slightly weaker condition than for the $B_i$'s to be $(\eps,\mu_S)$-close to the $A_i$'s, as in Definition <ref>. Furthermore, we can assume without loss of generality that $U=\Id_\infty$, otherwise we replace $\mN$ by $U^*\mN U$ and $P$ by $U^* PU$. Thus, we are given that

\[
\Expectation_{i\in [k]} \Vert A_i-\Id_\mM  B_i\Id_\mM\Vert_\tau^2\ ,\qquad  \tau^\mM(\Id_\mM-\Id_\mM P\Id_\mM)\leq  \eps,
\]

\[
\begin{split}
\Vert \Id_\mM-\Id_\mM P\Id_\mM\Vert_\tau^2 &=\tau^{\mM}(\Id_\mM\underbrace{-2\Id_\mM P\Id_\mM+\Id_\mM P^2\Id_\mM}_{=-\Id_\mM P\Id_\mM})\leq \eps.
\end{split}
\]

Let $ij\in E$. By (<ref>), we have

\begin{align*}
\sqrt{2}&=\Vert A_iA_jA_iA_j-\Id_\mM\Vert_\tau\\
&\leq \Vert A_iA_jA_iA_j-\Id_\mM P\Id_\mM\Vert_\tau+\Vert \Id_\mM P\Id_\mM-\Id_\mM\Vert_\tau\\
&\leq \Vert A_iA_jA_iA_j-\Id_\mM B_iB_jB_iB_j\Id_\mM\Vert_\tau+\sqrt\eps\\
&\leq \Vert \Id_\mM(A_i-B_i)A_jA_iA_j\Vert_\tau+\Vert \Id_\mM B_i(A_j-B_j)A_iA_j\Vert_\tau\\
&+\Vert \Id_\mM B_iB_j(A_i-B_i)A_j\Vert_\tau+\Vert \Id_\mM B_iB_jB_i(A_j-B_j)\Id_\mM\Vert_\tau+\sqrt\eps\\
\end{align*}

Since the $A$'s are unitaries in $\mM$, and by abusing notation and denoting $\Vert X \Vert_\tau=\tau_\infty(X^*X)$, we have

\begin{align*}
(\heartsuit)&= \Vert \Id_\mM(A_i-B_i)\Id_\mM\Vert_\tau+\Vert \Id_\mM B_i(A_j-B_j)\Id_\mM\Vert_\tau\\
&+\Vert \Id_\mM B_iB_j(A_i-B_i)\Id_\mM\Vert_\tau+\Vert \Id_\mM B_iB_jB_i(A_j-B_j)\Id_\mM\Vert_\tau\\
&\leq \Vert (A_i-B_i)\Id_\mM\Vert_\tau+\Vert (A_j-B_j)\Id_\mM\Vert_\tau
+\Vert (A_i-B_i)\Id_\mM\Vert_\tau+\Vert (A_j-B_j)\Id_\mM\Vert_\tau\\
\end{align*}

\begin{align*}
\Vert (A_i-B_i)\Id_\mM\Vert_\tau^2=  \Vert \Id_\mM(A_i-B_i)\Id_\mM\Vert_\tau^2+\Vert (\Id_\infty-\Id_\mM)(A_i-B_i)\Id_\mM\Vert_\tau^2,
\end{align*}

and since $(\Id_\infty -\Id_\mM)A_i=0$ and $\Id_\mM A_i=A_i\Id_\mM$, we have

\begin{align*}
\Vert (\Id_\infty-\Id_\mM)(A_i-B_i)\Id_\mM\Vert_\tau^2= \Vert (\Id_\infty-\Id_\mM)B_i\Id_\mM\Vert_\tau^2=\Vert (\Id_\infty-\Id_\mM)B_iA_i\Id_\mM\Vert_\tau^2.
\end{align*}

Here the second equality is because by definition,

\begin{align*}
\Vert(\Id_\infty-\Id_\mM)B_i\Id_\mM\Vert_\tau^2=\sum_{\substack{v'\in \field^{[k]\cup E} \\ j\neq 1}}\sum_{v\in \field^{[k]\cup E}} |(e_{v'}\otimes e_j)^*B_1e_v\otimes e_1|^2=(\diamondsuit)\;,
\end{align*}

but since $A_i$ permutes $\{e_v\otimes e_1\}_{v\in \field^{[k]\cup E}}$, we have

\begin{align*}
(\diamondsuit)=\sum_{\substack{v'\in \field^{[k]\cup E} \\ j\neq 1}}\sum_{v\in \field^{[k]\cup E}} |(e_{v'}\otimes e_j)^*B_iA_ie_v\otimes e_1|^2=\Vert (\Id_\infty-\Id_\mM)B_iA_i\Id_\mM\Vert_\tau^2\;.
\end{align*}

Now, for every $v\in \field^{[k]\cup E}$, we have

\[
1-|(e_v\otimes e_1)^*B_iA_ie_v\otimes e_1|^2\leq |1-(e_v\otimes e_1)^*B_iA_ie_v\otimes e_1|^2\leq \Vert \Id_\mM(\Id_\infty-B_iA_i)e_v\otimes e_1\Vert_2^2.
\]

On the other hand, since $B_iA_i$ is a contraction,

\begin{align*}
1-|(e_v\otimes e_1)^*B_iA_ie_v\otimes e_1|^2
&\geq \Vert B_iA_i e_v\otimes e_1\Vert_2^2-|(e_v\otimes e_1)^*B_iA_ie_v\otimes e_1|^2\\
&=\sum_{(v',j')\neq (v,1)}|(e_{v'}\otimes e_j)^*B_iA_ie_v\otimes e_1|^2\\
&\geq \Vert (\Id_\infty-\Id_\mM)B_iA_i e_v\otimes e_1\Vert_2^2\;.
\end{align*}

Therefore, by averaging the combined inequalities over $v\in \field^{[k]\cup E}$, we get

\[
\Vert (\Id_\infty -\Id_\mM)B_iA_i\Id_\mM\Vert_\tau^2\leq  \Vert \Id_\mM(\Id_\infty-B_iA_i)\Id_\mM\Vert_\tau^2=\Vert A_i-\Id_\mM B_i\Id_\mM\Vert_\tau^2\;.
\]

=1/2^k+1∑_v∈^k+1 ∑_v'∈^k+1
j'≠1 |(e_v'⊗e_j)^*B_1 e_v⊗e_1|^2.

Plugging all of this back to $(\spadesuit)$, we get

\begin{align*}
(\sqrt{2}-\sqrt\eps)^2&\leq (\spadesuit)^2\\
&\leq 8\Vert(A_i-B_i)\Id_\mM\Vert_\tau^2+8\Vert(A_j-B_j)\Id_\mM\Vert_\tau^2\\
&\leq 16 \Vert \Id_\mM (A_i-B_i)\Id_\mM\Vert_\tau^2+16 \Vert \Id_\mM (A_j-B_j)\Id_\mM\Vert_\tau^2.
\end{align*}

and since we assumed $\eps<3-2\sqrt{2}$, we have $\sqrt{2}-\sqrt\eps> 1$ and

\[
\Vert \Id_\mM (A_i-B_i)\Id_\mM\Vert_\tau^2+ \Vert \Id_\mM (A_j-B_j)\Id_\mM\Vert_\tau^2> \nicefrac{1}{16}.
\]

Now, let $i_1j_1,...,i_cj_c$ be the edges of a maximal  matching in $E$. Then,

\[
k\eps \geq \sum_{i\in [k]}\Vert \Id_\mM (A_i-B_i)\Id_\mM\Vert_\tau^2\geq \sum_{t=1}^c\Vert \Id_\mM (A_{i_t}-B_{i_t})\Id_\mM\Vert_\tau^2+ \Vert \Id_\mM (A_{j_t}-B_{j_t})\Id_\mM\Vert_\tau^2>\nicefrac{c}{16}.
\]

This finishes the proof.

By combining Claims <ref> and <ref> applied to a graph which is a mathcing with $c$ edges, we deduce Lemma <ref>.

§.§ The $L^\infty$ analogue

As discussed in the introduction (see Remark <ref>), it is more common in stability literature to use a $L^\infty$ analogue of Definition <ref>, where the notion of almost-homomorphism and closeness are both measured by taking a supremum over relations and generators respectively, as opposed to averaging according to distributions $\mu_R,\mu_S$.
Let us recall the exact definition. We say that a homomorphism $\rho\colon \mF(S)\to \mU(\mM)$ is an $(\eps,\infty)$-approximate representation if

\[
\forall r\in R\ \colon \ \ \|\rho(r)-\Id_\mM\|_\tau^2\leq \eps.
\]

Furthermore, homomorphisms $\rho\colon \mF(S)\to \mU(\mM),\varphi\colon \mF(S)\to \mU(\mN)$ are $(\delta,\infty)$-close if there exists an isometry $w\in P\mM_\infty \Id_\mM$ such that

\[
\forall s\in S\colon\ \ \|\rho(s)-w^*\varphi(s)w\|_\tau^2\leq \delta.
\]

The goal of this subsection of the appendix is to provide a somewhat general procedure to convert lower bounds on the modulus of stability with respect to $\mu_S,\mu_R$ into a lower bound on the $L^\infty$ modulus of stability.

Let $\langle S\colon R\rangle$ be a presentation of a group $\Gamma$, and let $\mu_S, \mu_R$ be fully supported distributions over the generators and relations respectively.
Let $\sigma\in \textrm{Sym}(S)$ be a permutation of the generators.
Then, $\sigma$ extends (by the universal property of the free group) to an automorphism of $\mF(S)$ which we still denote by $\sigma$ as well.
The automorphism group of the presentation  $\langle S\colon R\rangle$ is the subgroup of permutations in $\textrm{Sym}(S)$ that preserve $R$. Namely,

\[
\Phi=\textrm{Aut}(\langle S\colon R\rangle )=\left\{ \sigma \in \textrm{Sym}(S)\mid R=\sigma(R) \right\}.
\]

Assume $R=\bigsqcup R_i$ is the decomposition of $R$ into orbits of $\Phi$, and assume $\mu_R$ is uniform over orbits. Let $\rho\colon \mF(S)\to \mU(\mM)$ be an $(\eps,\mu_R)$-approximate representation of $\Gamma$. Define $\rho'\colon \mF(S)\to \mU(\bigoplus_{\alpha\in \Phi}\mM)$ as follows:

\[
\forall s\in S\ \colon \ \ \rho'(s)=\bigoplus_{\alpha\in \Phi} \rho(\alpha(s)).
\]

We denote by $\mM_\Phi=\bigoplus_{\alpha\in \Phi}\mM\subseteq \mM_\infty$ and by $\mM_\alpha$ the copy of $\mM$ at the $\alpha\in \Phi$ position.Note that $\mM_\Phi$ embeds in $\mM_\infty$, e.g. in the coordinates $1,...,|\Phi|$, and inherits a trace from it by defining

\[
\tau^{\mM_\Phi}(\bigoplus A_\alpha)=\frac{\tau_\infty(\bigoplus A_\alpha)}{\tau_\infty(\Id_{\mM_\Phi})}=\frac{1}{|\Phi|}\sum_{\alpha\in \Phi}\tau^\mM(A_\alpha)=\Expectation_{\alpha\in \Phi}\tau^\mM(A_\alpha).
\]

To be consistent, whenever we use $\|X\|_\tau^2$ it means

Let $w_i=\mu_R(R_i)$, namely the probability that $\mu_R$ samples a relation from the orbit $R_i$. Since we assumed $\mu_R$ is uniform over orbits, and since $\Phi$ acts transitively on each orbit, we know that

\[
\forall r\in R_i\ \colon \ \ \Expectation_{\alpha\in \Phi}f(\alpha(r))=\Expectation_{r'\in R_i}f(r)
\]

for any function $f\colon \mF(S)\to \complex$. Therefore,

\[
\begin{split}
\forall r\in R_i\ \colon \ \  \frac{w_i}{|\Phi|}\|\rho'(r)-\Id_{\mM_\Phi}\|_\tau^2&=w_i\Expectation_{\alpha\in \Phi} \|\rho(\alpha(r))-\Id_\mM\|_\tau^2\\
&=w_i\Expectation_{r'\in R_i} \|\rho(r')-\Id_\mM\|_\tau^2\\
&\leq \sum_j w_j\Expectation_{r'\in R_j} \|\rho(r')-\Id_\mM\|_\tau^2\\
&=\Expectation_{r\sim \mu_R}\|\rho(r)-\Id_\mM\|_\tau^2\leq \eps.
\end{split}
\]

\[
\forall r\in R\ \colon\ \frac{1}{|\Phi|}\|\rho'(r)-\Id_{\mM_\Phi}\|_\tau^2\leq \max({\nicefrac{1}{w_i}})\cdot\eps,
\]

which in turn means that $\rho'$ is a $(\max_i\{{\nicefrac{1}{w_i}}\}\cdot\eps,\infty)$-approximate representation — since

which is the relevant parameter to consider.

Any $(\eps,\mu_R)$-approximate representation of $\langle S\colon R\rangle$, where $\mu_R$ is uniform over orbits of $\Phi=\textrm{Aut}(\langle S\colon R\rangle)$, can be transformed into a $(\max_i\{{\nicefrac{1}{w_i}}\}\cdot\eps,\infty)$-approximate representation.

By applying this construction on the example from Claim <ref>, the resulting $\rho'$ is a $(\nicefrac{2|E|}{\binom{k}{2}},\infty)$-approximate representation of (<ref>). This is because $\Phi=\textrm{Sym}(S)$, and there are two  orbits — the commutation relations and the involutions — where $\mu_R$ is supprted equally on each of them. Namely, $w_{commutation}=w_{involution}=\nicefrac{1}{2}$.

Recall that our goal is to translate $L^1$ lower bounds into $L^\infty$ lower bounds. Namely, we would like to deduce that, if every genuine representation of $\Gamma$ is $(\delta,\mu_S)$-far from $\rho$, then every genuine representation of $\Gamma$ is $(\delta',\infty)$-far from $\rho'$, for $\delta'=C\delta$.  Since $\mu_S$ was assumed to be fully supported, the $L^\infty$ distance is lower bounded by the $L^1$-distance, and being $(\delta',\mu_S)$-far from $\rho'$ implies being $(\delta',\infty)$-far from it. Thus, we can forget about the $L^\infty$ notion of distance and lower bound our usual notion of distance.

To that end, assume that every genuine representation of $\Gamma$ is $(\delta,\mu_S)$-far from $\rho$. Namely, for every genuine representation $\varphi\colon \Gamma\to \mU(\mN)$, where $\mN=P\mM_\infty P$, and every isometry $w\in P\mM_\infty \Id_\mM$, we have

\[
\max\left\{\Expectation_{s\sim \mu_S} \|\rho(s)-w^*\varphi(s)w\|_\tau^2\ ,\ \tau^\mM(\Id_\mM-w^*w)\right\}\geq \delta.
\]

Let $\varphi'\colon \Gamma\to \mU(\mN)$ be a genuine representation of $\Gamma$ which is $(\delta',\mu_S)$-close to $\rho'$, i.e. it satisfies

\[
\frac{1}{|\Phi|}\Expectation_{s\sim \mu_S} \|\rho'(s)-w^*\varphi'(s)w\|_\tau^2\ ,\ \tau^{\mM_\Phi}(\Id_{\mM_\Phi}-w^*w)\leq  \delta',
\]

where  again  $\|X\|_\tau^2=\tau_\infty(X^*X)$.
As before, we can assume $w=PI_{\mM_\Phi}$. Then,

\[
\begin{split}
\Expectation_{\alpha\in \Phi}\Expectation_{s\sim \mu_S} \|\rho(\alpha(s))-\Id_{\mM_\alpha}\varphi'(s)\Id_{\mM_\alpha}\|_\tau^2&=\frac{1}{|\Phi|}\Expectation_{s\sim \mu_S}\sum_{\alpha\in \Phi}\|\Id_{\mM_\alpha}\rho'(s)\Id_{\mM_\alpha}-\Id_{\mM_\alpha}\varphi'(s)\Id_{\mM_\alpha}\|_\tau^2 \\
&\leq \frac{1}{|\Phi|}\Expectation_{s\sim \mu_S}\|\rho'(s)-\Id_{\mM_\Phi}\varphi'(s)\Id_{\mM_\Phi}\|_\tau^2\leq \delta'.
\end{split}
\]

In particular, by Markov's inequality, for at least two thirds of the $\alpha\in \Phi$ we have

\[
\Expectation_{s\sim \mu_S} \|\rho(\alpha(s))-\Id_{\mM_\alpha}\varphi'(s)\Id_{\mM_\alpha}\|_\tau^2\leq 3\delta'.
\]

\[
\begin{split}
\delta'&\geq \tau^{\mM_\Phi}(\Id_{\mM_\Phi}-\Id_{\mM_\Phi}P\Id_{\mM_\Phi})\\
\end{split}\;,
\]

and for at least two thirds of the $\alpha\in \Phi$ we have

\[
\tau^{\mM_\alpha}(\Id_{\mM_\alpha}-\Id_{\mM_\alpha}P\Id_{\mM_\alpha})\leq 3\delta'.
\]

Hence, $\delta'\geq \frac{\delta}{3}$, and we deduce that every genuine representation of $\Gamma\cong \langle S\colon R\rangle$ is at least $(\nicefrac{\delta}{3},\infty)$-away from $\rho'$.

The transformation $\rho\mapsto\rho'$ we described  translates a $(\eps,\mu_R)$-approximate representation into a $((\max{\nicefrac{1}{w_i}})\cdot\eps,\infty)$-approximate representaion, and if every genuine representation of $\Gamma$ is $(\delta,\mu_S)$-far from $\rho$, then every genuine representation is $(\nicefrac{\delta}{3},\infty)$-far from $\rho'$.

By applying this corollary to the construction from the beginning of the appendix, we conclude that the $L^\infty$ modulus of stability of the presentation (<ref>) is $\Omega(k\eps)$.

[1]
Rotem Arnon-Friedman, Renato Renner, and Thomas Vidick.
Simple and tight device-independent security proofs.
SIAM Journal on Computing, 48(1):181–225, 2019.

[2]
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy.
Proof verification and the hardness of approximation problems.
J. ACM, 45(3):501–555, may 1998.

[3]
Oren Becker and Michael Chapman.
Stability of approximate group actions: uniform and probabilistic.
Journal of the European Mathematical Society, 2022.

[4]
Lewis Bowen, Michael Chapman, Alex Lubotzky, and Thomas Vidick.
Subgroup tests and the aldous–lyons conjecture.
preprint, 2023.

[5]
László Babai, Lance Fortnow, and Carsten Lund.
Non-deterministic exponential time has two-prover interactive
Computational complexity, 1:3–40, 1991.

[6]
László Babai, Albert J Goodman, William M Kantor, Eugene M Luks, and
Péter P Pálfy.
Short presentations for finite groups.
Journal of Algebra, 194(1):79–112, 1997.

[7]
Oren Becker and Alexander Lubotzky.
Group stability and property (t).
Journal of Functional Analysis, 278(1):108298, 2020.

[8]
Andrea Coladangelo, Alex B Grilo, Stacey Jeffery, and Thomas Vidick.
Verifier-on-a-leash: new schemes for verifiable delegated quantum
computation, with quasilinear resources.
In Annual International Conference on the Theory and
Applications of Cryptographic Techniques, pages 247–277. Springer, 2019.

[9]
Richard Cleve, Peter Hoyer, Benjamin Toner, and John Watrous.
Consequences and limits of nonlocal strategies.
In Proceedings. 19th IEEE Annual Conference on Computational
Complexity, 2004., pages 236–249. IEEE, 2004.

[10]
Michael Chapman and Alex Lubotzky.
Stability of homomorphisms, coverings and cocycles I:
preprint, 2023.

[11]
Michael Chapman and Alex Lubotzky.
Stability of homomorphisms, coverings and cocycles II: Examples,
Applications and Open problems.
preprint, 2023.

[12]
Richard Cleve, Li Liu, and William Slofstra.
Perfect commuting-operator strategies for linear system games.
Journal of Mathematical Physics, 58(1), 2017.

[13]
Richard Cleve and Rajat Mittal.
Characterization of binary constraint system games.
In Automata, Languages, and Programming: 41st International
Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings,
Part I 41, pages 320–331. Springer, 2014.

[14]
Rui Chao, Ben W Reichardt, Chris Sutherland, and Thomas Vidick.
Overlapping qubits.
In 8th Innovations in Theoretical Computer Science Conference
(ITCS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.

[15]
MARCUS DE CHIFFRE, LEV GLEBSKY, ALEXANDER LUBOTZKY, and ANDREAS THOM.
Stability, cohomology vanishing, and nonapproximable groups.
Forum of Mathematics, Sigma, 8:e18, 2020.

[16]
Marcus De Chiffre, Narutaka Ozawa, and Andreas Thom.
Operator algebraic approach to inverse and stability theorems for
amenable groups.
Mathematika, 65(1):98–118, 2019.

[17]
Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes.
Locally testable codes with constant rate, distance, and locality.
In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory
of Computing, STOC 2022, page 357–374, New York, NY, USA, 2022.
Association for Computing Machinery.

[18]
Mikael de la Salle.
Orthogonalization of positive operator valued measures.
arXiv preprint arXiv:2103.14126, 2021.

[19]
Mikael de la Salle.
Spectral gap and stability for groups and non-local games.
arXiv preprint arXiv:2204.07084, 2022.

[20]
William Timothy Gowers and Omid Hatami.
Inverse and stability theorems for approximate representations of
finite groups.
Sbornik: Mathematics, 208(12):1784, 2017.

[21]
Robert Guralnick, Willim Kantor, Martin Kassabov, and Alex Lubotzky.
Presentations of finite simple groups: a quantitative approach.
Journal of the American Mathematical Society, 21(3):711–774,

[22]
Lev Glebsky.
Almost commuting matrices with respect to normalized hilbert-schmidt
arXiv preprint arXiv:1002.3082, 2010.

[23]
Lev Glebsky and Luis Manuel Rivera.
Almost solutions of equations in permutations.
Taiwanese Journal of Mathematics, 13(2A):493–500, 2009.

[24]
PR Halmos.
Some unsolved problems of unknown depth about operators on hilbert
Proceedings of the Royal Society of Edinburgh Section A:
Mathematics, 76(1):67–76, 1976.

[25]
Don Hadwin and Tatiana Shulman.
Stability of group relations under small Hilbert-Schmidt
Journal of Functional Analysis, 275(4):761–792, 2018.

[26]
Adrian Ioana.
Stability for product groups and property ($\tau$).
Journal of Functional Analysis, 279(9):108729, 2020.

[27]
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen.
MIP$^{*}$= RE.
arXiv preprint arXiv:2001.04383, 2020.

[28]
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen.
Quantum soundness of the classical low individual degree test.
arXiv preprint arXiv:2009.12982, 2020.

[29]
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen.
Communications of the ACM, 64(11):131–138, 2021.

[30]
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen.
Quantum soundness of testing tensor codes.
In 2021 IEEE 62nd Annual Symposium on Foundations of Computer
Science (FOCS), pages 586–597. IEEE, 2022.

[31]
David Kazhdan.
On $\varepsilon$-representations.
Israel Journal of Mathematics, 43:315–323, 1982.

[32]
Dmitry N Kozlov and Roy Meshulam.
Quantitative aspects of acyclicity.
Research in the Mathematical Sciences, 6:1–32, 2019.

[33]
Se-Jin Kim, Vern Paulsen, and Christopher Schafhauser.
A synchronous game for binary constraint systems.
Journal of Mathematical Physics, 59(3), 2018.

[34]
Julia Kempe and Thomas Vidick.
Parallel repetition of entangled games.
In Proceedings of the forty-third annual ACM symposium on Theory
of computing, pages 353–362, 2011.

[35]
Anand Natarajan and Thomas Vidick.
A quantum linearity test for robustly verifying entanglement.
In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory
of Computing, pages 1003–1015, 2017.

[36]
Anand Natarajan and Thomas Vidick.
Low-degree testing for quantum states, and a quantum entangled games
pcp for qma.
In 2018 IEEE 59th Annual Symposium on Foundations of Computer
Science (FOCS), pages 731–742. IEEE, 2018.

[37]
Anand Natarajan and Tina Zhang.
Bounding the quantum value of compiled nonlocal games: from CHSH to
BQP verification.
arXiv preprint arXiv:2303.01545, 2023.

[38]
Pavel Panteleev and Gleb Kalachev.
Asymptotically good quantum and locally testable classical ldpc
In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory
of Computing, STOC 2022, page 375–388, New York, NY, USA, 2022.
Association for Computing Machinery.

[39]
Connor Paddock, Vincent Russo, Turner Silverthorne, and William Slofstra.
Arkhipov's theorem, graph minors, and linear system nonlocal games.
arXiv preprint arXiv:2205.04645, 2022.

[40]
Ronitt Rubinfeld and Madhu Sudan.
Robust characterizations of polynomials with applications to program
SIAM Journal on Computing, 25(2):252–271, 1996.

[41]
Jacob Schwartz.
Fast probabilistic algorithms for verification of polynomial
Journal of the ACM, 27(4):701–717, 1980.

[42]
William Slofstra.
The set of quantum correlations is not closed.
In Forum of Mathematics, Pi, volume 7, page e1. Cambridge
University Press, 2019.

[43]
William Slofstra and Thomas Vidick.
Entanglement in non-local games and the hyperlinear profile of
In Annales Henri Poincaré, volume 19, pages 2979–3005.
Springer, 2018.

[44]
Stanislaw Ulam.
A collection of mathematical problems.
Interscience Tracts in Pure and Applied Mathematics, no. 8,
Interscience Publishers, New York-London, 1960.

[45]
Thomas Vidick.
MIP$^*=$RE, a negative resolution to Connes' embedding problem
and Tsirelson's problem.
Notes prepared for the ICM'22, available at
<http://users.cms.caltech.edu/ vidick/notes/ICM.pdf>.

[46]
John Von Neumann.
Approximative properties of matrices of high finite order.
Portugaliae mathematica, 3(1):1–62, 1942.

[47]
Dan Voiculescu.
Asymptotically commuting finite rank unitary operators without
commuting approximants.
Acta Sci. Math.(Szeged), 45(1-4):429–431, 1983.

[48]
Umesh Vazirani and Thomas Vidick.
Fully device independent quantum key distribution.
Communications of the ACM, 62(4):133–133, 2019.

[49]
Richard Zippel.
Probabilistic algorithms for sparse polynomials.
In Symbolic and Algebraic Computation, pages 216–226,