A D V E R T |
I S E M E N T |
| Math Sites: lean ages 13-∞ readme referees parents | >>> MAITH GAMES <<< | all 372 compute stand |
|
LEVEL 2 OF 2 · Amenability, unitarizability, and Ulam stability
Strong Ulam Stability Characterizes Amenability
expertly designed by an internal OpenAI model · released 2026-10-05
· original PDF
IntroductionLet \(G\) be a countable discrete group and let \(H\) be a complex Hilbert space. For a map \(\mu:G\to\mathcal U(H)\) with \(\mu(e)=I\), put \[\operatorname{def}(\mu)=\sup_{g,h\in G}\left\lVert\mu(gh)-\mu(g)\mu(h)\right\rVert.\] The group is strongly Ulam stable if, for every \(\varepsilon>0\), there is \(\delta>0\) such that every such map with \(\operatorname{def}(\mu)\le\delta\) is within \(\varepsilon\), uniformly on \(G\), of a unitary representation on the same space \(H\). All norms are operator norms. The number \(\delta\) must work simultaneously for all Hilbert spaces, including infinite-dimensional ones. A group is amenable if \(\ell^\infty(G)\) admits a positive linear functional \(m\) with \(m(1)=1\) and \(m(L_gf)=m(f)\), where \((L_gf)(x)=f(g^{-1}x)\). Our main result is the following characterization. Theorem 1. A countable discrete group is strongly Ulam stable if and only if it is amenable. Kazhdan proved the implication from amenability to strong Ulam stability [9]; see also [3]. We prove the converse. More precisely, for every nonamenable countable group and every \(\delta>0\), we construct a separable Hilbert space \(H\) and a normalized map \(\mu:G\to\mathcal U(H)\) with \(\operatorname{def}(\mu)<\delta\) such that \[ \sup_{g\in G}\left\lVert\mu(g)-\rho(g)\right\rVert>\frac1{10} \quad\text{for every unitary representation }\rho:G\to\mathcal U(H). \tag{1}\] History and contextThe uniform stability problem asks whether an approximate homomorphism can be corrected without losing uniform control over the group. Kazhdan’s 1982 theorem supplies this correction for amenable groups; his work also gives unstable almost representations of fundamental groups of closed orientable surfaces of genus at least two [9, 3]. Burger, Ozawa, and Thom proved that every group containing a nonabelian free subgroup fails strong Ulam stability [3]. They explicitly asked whether strong Ulam stability characterizes amenability [3]. Alpeev subsequently proved instability for restricted wreath products \(A\wr G\) when \(A\) is a nontrivial countable abelian group and \(G\) is countable and nonamenable [1]. His use of measured equivalence relations reaches examples without nonabelian free subgroups. The inclusion of infinite-dimensional Hilbert spaces is essential. The term Ulam stability, without “strong”, commonly denotes the uniform statement restricted to finite-dimensional unitary groups [3]. Nonamenable groups can satisfy that property. Glebsky, Lubotzky, Monod, and Rangarajan developed asymptotic cohomology and proved finite-dimensional stability for broad classes of higher-rank lattices [6]. Fournier-Facio and Rangarajan applied this theory to wreath products over infinite amenable groups and to Thompson groups [4]. These results concern a different stability property. The failure of the corresponding wreath-product statement for strong stability is explained in [4]. The constructionThe proof starts with a nontrivial minimal strongly proximal action of \(G\) on a compact space, supplied by Furstenberg’s boundary theory [5, 8]. From this action we obtain finite choices of steps in \(G\), each marked \(\mathsf E\) or \(\mathsf F\) at every possible departure point. The marks have two opposing counting properties: all but a small proportion of steps from a fixed point are \(\mathsf E\), whereas all but a small proportion of steps ending at a fixed point are \(\mathsf F\). They also satisfy a compatibility condition along paths: an \(\mathsf E\) step can never be followed by an \(\mathsf F\) step. We use these paths to construct a Hilbert space \(H\) with finitely many levels and a copy at each group element. Fix a set \(\mathcal C\) of at most three translated markings. For each \(p\in\mathcal C\), a unitary circuit \(W_p^{\mathcal C}\) exchanges selected subspaces of successive levels, using edges whose flags differ within \(\mathcal C\) and whose flag in \(p\) is \(\mathsf F\). For a fixed set \(\mathcal C\), the comparisons \(W_q^{\mathcal C}(W_p^{\mathcal C})^{-1}\) compose exactly. In constructing \(\mu\), however, each comparison uses its own pair of markings. The defect estimate therefore requires a bound on how a comparison changes when a third marking is added. After obtaining that bound, we compose pair comparisons with the usual translation representation to define \(\mu\). The main analytic issue is that the two subspaces exchanged at one step have naturally identified coordinates with slightly different inner products. Summing the resulting errors over all layers would give no useful bound. We instead choose the isometry between these inner products to be almost the coordinate identity on the subspace used by the next layer. The change caused by a third marking can then be moved past that layer. After this move, the principal errors act on mutually orthogonal levels, so their norms combine by a maximum rather than a sum. Lemma 5 isolates the isometry construction, and Proposition 7 gives the resulting circuit estimate. Both estimates are independent of the dimensions of the finite coordinate spaces. The obstruction to a genuine representation is a quadratic form. We use two orthonormal bases with opposite signs and a family of anticommuting involutions. The signed basis sums force the form to vanish on vectors obtained from any genuine representation. The initial inner product of our construction makes the same form equal to \(1/2\). Most of the labelled paths transport the final vectors back to these initial vectors, producing the fixed distance bound (1). Section 2 constructs the marks. Section 3 proves the finite-dimensional estimates and the metric-transfer lemmas. Sections 4 and 5 construct the circuits and control their dependence on the markings. Section 6 proves the quadratic-form obstruction and chooses the parameters. ConventionsInner products are conjugate-linear in the first argument. On a coordinate space with a positive matrix \(A\), the notation \((V,A)\) means the inner product \(\left\langle u,v\right\rangle_A=u^*Av\). Unless a metric is indicated, a matrix norm is Euclidean. Metrics between \(\frac12 I\) and \(2I\) make these norms uniformly equivalent. A numerical constant \(C\) may increase from one occurrence to the next; it never depends on the group, the number of labels, or the number of levels. We write an explicit factor \(N\) whenever an estimate sums over \(N\) levels. Flags from a boundary actionWe first convert nonamenability into finite families of labelled steps in \(G\). Each step will carry a flag \(\mathsf E\) or \(\mathsf F\). The construction makes \(\mathsf F\) rare when a departure is fixed and \(\mathsf E\) rare when an arrival is fixed. At the same time, an \(\mathsf E\) step prevents every outgoing step at the next stage from having flag \(\mathsf F\). This last property will allow common parts of two circuits to cancel exactly. A compact \(G\)-space is a boundary if its action is minimal and strongly proximal: every orbit is dense, and the weak-star closure of the orbit of every Radon probability measure contains a point mass. We use the standard boundary characterization of amenability: a nonamenable discrete group admits a non-singleton compact Hausdorff boundary [5]; see also [8]. Fix such a boundary \(K\). Minimality implies that the orbit closure of any probability contains every point mass once it contains one. The space \(K\) has no isolated points. Indeed, if it had an isolated point, minimality would imply that all its points are isolated, so compactness would make \(K\) finite. The uniform probability on \(K\) is invariant, contradicting strong proximality unless \(K\) is a singleton. Consequently, every nonempty open subset of \(K\) contains arbitrarily many pairwise disjoint nonempty open subsets. The following consequence of strong proximality provides the finite lists used at each stage. The requirement at the distinguished point \(\zeta\) is what makes the stages compatible. Lemma 2 (Uniform lists with a prescribed point). Let \(K\) be a compact Hausdorff boundary, let \(U\subseteq K\) be nonempty and open, let \(\zeta\in K\), and let \(0<\beta<1\). There is a finite nonempty list \(s_1,\ldots,s_M\in G\), with repetitions allowed, such that \[s_j^{-1}\zeta\in U\quad(1\leq j\leq M), \qquad \frac{1}{M}\#\{j:s_j^{-1}t\notin U\}<\beta \quad(t\in K).\] Moreover, some open neighborhood \(O\) of \(\zeta\) satisfies \(s_j^{-1}O\subseteq U\) for every \(j\). Proof. Choose \(t_0\in U\) and a continuous function \(f:K\to[0,1]\) with \(f(t_0)=1\) and support contained in \(U\). Consider the family \[\mathcal A=\{f\circ s^{-1}:s\in G,\ s^{-1}\zeta\in U\} \subset C(K,\mathbb R).\] For every Radon probability \(m\) on \(K\), there is \(a\in\mathcal A\) with \[ \int_K a\,dm>1-\frac{\beta}{2}. \tag{2}\] To see this, apply strong proximality and minimality to \(\nu=(m+\delta_\zeta)/2\). Since \(\delta_{t_0}\) belongs to the orbit closure of \(\nu\), some \(s\in G\) satisfies \[\frac12\left(\int_K f(s^{-1}t)\,dm(t) +f(s^{-1}\zeta)\right)>1-\frac{\beta}{4}.\] Both terms in parentheses are at most one, so each exceeds \(1-\beta/2\). In particular, \(s^{-1}\zeta\in U\), which proves (2). We claim that the convex hull of \(\mathcal A\) contains a function strictly larger than \(1-\beta\) everywhere. Otherwise, separate that convex hull from the nonempty open convex set \[\mathcal O=\{q\in C(K,\mathbb R):q(t)>1-\beta\text{ for all }t\in K\}\] by the Hahn–Banach theorem. There is a nonzero continuous real linear functional \(\Lambda\) such that \[\sup_{a\in\mathcal A}\Lambda(a) \leq \inf_{q\in\mathcal O}\Lambda(q).\] This functional is positive. Indeed, if \(u\geq0\) and \(q\in\mathcal O\), then \(q+tu\in\mathcal O\) for every \(t\geq0\); the displayed separation would be impossible if \(\Lambda(u)<0\). A nonzero positive functional satisfies \(\Lambda(1)>0\), so we may normalize it to have \(\Lambda(1)=1\). The Riesz representation theorem then identifies \(\Lambda\) with integration against a Radon probability \(m\). Applying the separation inequality to the constant functions \(q=1-\beta+\varepsilon\) and letting \(\varepsilon\downarrow0\) gives \[\sup_{a\in\mathcal A}\int_K a\,dm\leq1-\beta,\] contradicting (2). Thus a finite convex combination of functions from \(\mathcal A\) exceeds \(1-\beta\) on \(K\). Compactness gives a strictly positive uniform margin. Approximate its coefficients by nonnegative rational coefficients summing to one, closely enough to preserve that margin. Clearing denominators produces a list with \[\frac1M\sum_{j=1}^M f(s_j^{-1}t)>1-\beta\qquad(t\in K).\] Because \(f\) vanishes outside \(U\) and takes values in \([0,1]\), this is the required counting inequality. Finally, \(O=\bigcap_{j=1}^M s_jU\) is an open neighborhood of \(\zeta\) and has the asserted image property. ◻ We now arrange these lists into stages. The two labels at stage \(k\) will be denoted by \(x\in\mathcal X_k\) and \(y\in\mathcal Y_{k-1}\); the corresponding step is \(w\longmapsto w s_k(x,y)\). Proposition 3 (Compatible sparse flags). Let \(G\) be a nonamenable discrete group. For every integer \(N\geq1\) and every \(0<\beta<1\), there are finite nonempty sets \(\mathcal X_1,\ldots,\mathcal X_N\) and \(\mathcal Y_0,\ldots,\mathcal Y_{N-1}\), maps \[s_k:\mathcal X_k\times\mathcal Y_{k-1}\longrightarrow G, \qquad b_k:G\times\mathcal X_k\times\mathcal Y_{k-1} \longrightarrow\{\mathsf E,\mathsf F\},\] with the following properties.
Each alphabet may subsequently be replaced by any positive integer number of copies, independently of the others, while preserving these properties. In particular, its cardinality can be made arbitrarily large and divisible by any prescribed positive integer. Proof. Fix points \(\xi,\zeta\in K\) and choose an integer \(C>1/\beta\). We construct nonempty open sets \(U_0,\ldots,U_N\) and the stage maps backwards, starting with \(U_N=K\). Suppose that \(U_k\) is already chosen. Inside it choose pairwise disjoint nonempty open sets \(U_{k,1},\ldots,U_{k,C}\), and set \(\mathcal X_k=\{1,\ldots,C\}\). For each \(c\in\mathcal X_k\), apply Lemma 2 to \(U_{k,c}\) and the point \(\zeta\). Repeat the resulting lists to give them a common length \(M_k\), and index each list by the same set \(\mathcal Y_{k-1}=\{1,\ldots,M_k\}\). Write its entries as \(s_k(c,y)\). Set \[U_{k-1} =\bigcap_{c\in\mathcal X_k}\ \bigcap_{y\in\mathcal Y_{k-1}}s_k(c,y)U_{k,c}.\] This is an open neighborhood of \(\zeta\), and it satisfies \[ s_k(c,y)^{-1}U_{k-1}\subseteq U_{k,c} \subseteq U_k\qquad(c,y). \tag{3}\] This completes the backward construction. For a step \(w\longmapsto v=w s_k(c,y)\), define \[ b_k(w;c,y)=\mathsf E \quad\Longleftrightarrow\quad v^{-1}\xi\in U_{k,c}, \tag{4}\] and otherwise give it flag \(\mathsf F\). If this step has flag \(\mathsf E\), then \(v^{-1}\xi\in U_k\). For every next-stage label \((c',y')\), equation (3) at stage \(k+1\) gives \[(v s_{k+1}(c',y'))^{-1}\xi =s_{k+1}(c',y')^{-1}v^{-1}\xi\in U_{k+1,c'}.\] This proves (F1). For fixed \(w,c\), apply the counting conclusion of Lemma 2 at the boundary point \(w^{-1}\xi\). The condition for flag \(\mathsf E\) is precisely \(s_k(c,y)^{-1}w^{-1}\xi\in U_{k,c}\), so fewer than a \(\beta\) fraction of \(y\) have flag \(\mathsf F\). This proves (F2). For fixed \(v,y\), the unique departure of the step with first label \(c\) and arrival \(v\) is \(v s_k(c,y)^{-1}\). Its flag is \(\mathsf E\) exactly when \(v^{-1}\xi\in U_{k,c}\). The color sets are disjoint, so at most one of the \(C\) labels has this property. Since \(1/C<\beta\), this proves (F3). Finally, replace any alphabet by its product with a finite nonempty set and pull back the maps \(s_k\) and flags \(b_k\) under the coordinate projections. All counting proportions remain unchanged, and (F1) remains exact. This proves the assertion about cardinalities. ◻ For \(g\in G\), define the translated flags \(p=gb\) by \[p_k(w;x,y)=b_k(g^{-1}w;x,y).\] A configuration will mean such a translate. Every configuration satisfies (F1)–(F3), since left translation carries \(w\longmapsto w s_k(x,y)\) to a step with the same labels. In particular, along any path through the successive stages, the \(\mathsf F\) steps form an initial segment: after its first \(\mathsf E\) step, every remaining step has flag \(\mathsf E\). Frames and metric transfersWe need two kinds of linear algebra with estimates independent of dimension. First, a union of two orthonormal bases will be almost orthonormal on every sufficiently small set of labels; the same construction supplies symmetric involutions with small sparse restrictions. Second, when two inner products differ slightly, we will choose an isometry that changes a prescribed subspace by much less than it changes the whole space. This second choice will prevent errors from adding over all the levels of the construction. All matrices in the first lemma are real; we use their complexifications when forming Hilbert spaces. For a finite set \(E\), write \(P_S\) for the coordinate projection associated with a subset \(S\subseteq E\). Lemma 4 (Sparse restrictions). For every \(0<\eta<1/4\) there is \(0<\beta_0<1/16\) with the following property. If \(0<\beta\leq\beta_0\), then for every sufficiently large integer \(m\) there are unit vectors \((a_x)_{x\in X}\) in \(\mathbb R^m\), where \(|X|=2m\), and signs \(f(x)\in\{1,-1\}\) such that:
Moreover, for every sufficiently large integer \(n\) there is a real orthogonal \(n\times n\) matrix \(O\) such that, on a set \(Y\) of size \(2n\), \[ J=\begin{pmatrix}0&O\\ O^*&0\end{pmatrix}, \qquad Z=\begin{pmatrix}I&0\\0&-I\end{pmatrix} \tag{7}\] satisfy \[ \left\lVert P_SJP_T\right\rVert\leq\eta \quad\text{whenever}\quad |S|,|T|\leq4\beta|Y|. \tag{8}\] In particular, \(J^*=J\), \(J^2=Z^2=I\), \(JZ=-ZJ\), and every diagonal entry of \(J\) is zero. Proof. We give the elementary probabilistic argument, a standard use of concentration for Haar orthogonal matrices; compare [10]. Let \(O\) be Haar distributed on the orthogonal group of \(\mathbb R^m\). For fixed real unit vectors \(u,v\), the random variable \(u^*Ov\) has the distribution of the first coordinate of a uniform point on the unit sphere. Represent that point as \((g_1,\ldots,g_m)/(\sum_jg_j^2)^{1/2}\), where the \(g_j\) are independent standard Gaussians. Conditioning on \(\sum_{j=2}^m g_j^2\) and using the Gaussian tail bound gives, for \(0<t<1\), \[\begin{align*} \mathbb P\{|u^*Ov|>t\} &\leq 2\,\mathbb E\exp\left( -\frac{t^2}{2(1-t^2)}\sum_{j=2}^m g_j^2\right)\\ &=2(1-t^2)^{(m-1)/2} \leq 2\exp\bigl(-(m-1)t^2/2\bigr). \end{align*}\] Put \(q=8\beta<1/2\). For any nonempty coordinate sets \(S,T\) of size at most \(q m\), take \(1/4\)-nets in their real unit spheres, with at most \(9^{|S|}\) and \(9^{|T|}\) points. A bilinear form whose absolute value is at most \(\eta/2\) on these nets has operator norm at most \(\eta\). Indeed, approximating each of a maximizing pair of unit vectors changes the form by at most half its operator norm. The number of subsets of \(\{1,\ldots,m\}\) of size at most \(qm\) is at most \(\exp(mH(q))\), where \[H(q)=-q\log q-(1-q)\log(1-q).\] Thus the probability that some such submatrix \(P_SOP_T\) has norm larger than \(\eta\) is at most \[2\exp\left(2mH(q)+2qm\log9-\frac{m\eta^2}{16}\right) \qquad(m\geq2).\] Choose \(\beta_0\) so small that, for \(q=8\beta_0\), \(2H(q)+2q\log9<\eta^2/32\). The displayed probability is then less than one for all sufficiently large \(m\). Hence there is an orthogonal matrix all of whose submatrices with at most \(qm\) rows and columns have norm at most \(\eta\). Real and complex operator norms agree for these real matrices. Take the two bases to be the standard basis and the columns of this matrix, with signs \(+1\) and \(-1\). For a subset of their union, its Gram matrix minus the identity has block form \[\begin{pmatrix}0&O_{S,T}\\O_{S,T}^*&0\end{pmatrix}.\] Its norm is \(\left\lVert O_{S,T}\right\rVert\), proving (6). Applying the same construction in dimension \(n\) gives (7). Each restriction in (8) has two off-diagonal blocks of the preceding type; they have orthogonal domains and orthogonal ranges, so its norm is the larger of their norms. ◻ We will use the following consequence of (6). For every allowed subset \(S\), symmetric orthonormalization gives the column isometry \[ \widetilde F_S=F_S(F_S^*F_S)^{-1/2}, \qquad \left\lVert\widetilde F_S-F_S\right\rVert\leq C\eta. \tag{9}\] This follows by applying the scalar bound \(|t^{-1/2}-1|\leq C|t-1|\) on \([3/4,5/4]\) to \(F_S^*F_S\). If \(S\subseteq T\) and both subsets are allowed, then \(\widetilde F_S\) and the restriction of \(\widetilde F_T\) to \(\ell^2(S)\) differ by at most \(2C\eta\): both are within \(C\eta\) of \(F_S\). All these bounds hold for every subset simultaneously. We next compare two inner products on the same vector space. A positive operator \(B\) defines \(\langle x,y\rangle_B=\langle x,By\rangle\); the corresponding operator norm is denoted by \(\left\lVert\cdot\right\rVert_B\). The next lemma singles out a subspace \(R\) that the change of coordinates must preserve. Preservation here means that the map takes \(R\) onto \(R\); it need not preserve the original orthogonal complement of \(R\). Lemma 5 (Transfer with a prescribed subspace). Let \(A,B\) be positive operators on a Hilbert space \(E\) such that \[\tfrac12I\leq A,B\leq2I, \qquad A-B=h\Gamma, \qquad \Gamma^*=\Gamma, \qquad \left\lVert\Gamma\right\rVert\leq1, \qquad 0\leq h\leq\tfrac18.\] Let \(P\) be an orthogonal projection commuting with \(B\), set \(R=PE\), and assume \(\left\lVert P\Gamma P\right\rVert\leq\eta\), where \(0\leq\eta\leq1\). There is a specified invertible operator \(S_R\) such that \[ S_R^*AS_R=B,\qquad S_R(R)=R,\qquad \left\lVert S_R-I\right\rVert\leq Ch,\qquad \left\lVert(S_R-I)P\right\rVert\leq Ch\eta. \tag{10}\] The constant \(C\) is absolute, and the estimates also hold in the \(B\)-norm after changing \(C\). If \(R\subseteq R'\) and both projections satisfy these hypotheses, then \[ K=S_{R'}^{-1}S_R \quad\text{satisfies}\quad K^*BK=B,\qquad \left\lVert K-I\right\rVert_B\leq Ch,\qquad \left\lVert(K-I)P\right\rVert_B\leq Ch\eta. \tag{11}\] The construction commutes with orthogonal direct sums and with every orthogonal projection commuting with \(A\), \(B\), and \(P\). Proof. First make the \(B\) inner product Euclidean. Define \[\widehat A=B^{-1/2}AB^{-1/2} =I+hB^{-1/2}\Gamma B^{-1/2}.\] Since \(P\) commutes with \(B\), this change of coordinates preserves \(E=R\oplus R^\perp\). Relative to this decomposition write \[\widehat A=\begin{pmatrix}a&b\\b^*&d\end{pmatrix}, \qquad E_0=d-b^*a^{-1}b.\] The assumptions imply \[\left\lVert\widehat A-I\right\rVert\leq2h, \qquad \left\lVert a-I_R\right\rVert\leq2h\eta.\] In particular, \(a\) and the Schur complement \(E_0\) are positive and invertible. Define \[ Q_R= \begin{pmatrix} a^{-1/2}&-a^{-1}bE_0^{-1/2}\\ 0&E_0^{-1/2} \end{pmatrix}, \qquad S_R=B^{-1/2}Q_RB^{1/2}. \tag{12}\] The same formula applies when either summand is zero, with the empty blocks omitted. Multiplication gives \(Q_R^*\widehat A Q_R=I\), and hence \(S_R^*AS_R=B\). Its first block column also shows that \(S_R(R)=R\). For completeness, the bounds are uniform even when \(E\) is infinite dimensional. We have \(a\geq(1-2h)I_R\) and \(\left\lVert b\right\rVert\leq2h\). Moreover, \[E_0\geq(1-2h)I_{R^\perp},\qquad \left\lVert E_0-I_{R^\perp}\right\rVert \leq2h+\frac{4h^2}{1-2h}.\] The lower bound follows by minimizing \(\langle (x,y),\widehat A(x,y)\rangle\) over \(x\in R\) for fixed \(y\). Functional calculus in these fixed spectral intervals now gives \[\left\lVert Q_R-I\right\rVert\leq Ch, \qquad \left\lVert(Q_R-I)P\right\rVert =\left\lVert a^{-1/2}-I_R\right\rVert\leq Ch\eta.\] Conjugation by \(B^{1/2}\) changes the bounds by at most a factor of two, which proves (10). For nested subspaces, both \(S_R\) and \(S_{R'}\) are isometries from the \(B\) inner product to the \(A\) inner product. Thus \(K\) is \(B\)-unitary. Also \[K-I=S_{R'}^{-1}(S_R-S_{R'}).\] The two terms \(S_R-I\) and \(S_{R'}-I\) are \(O(h)\) on \(E\) and \(O(h\eta)\) on \(R\), since \(R\subseteq R'\). The inverse \(S_{R'}^{-1}\) has uniformly bounded norm, proving (11). Finally, every operation in (12) respects the stated common reducing subspaces. ◻ There is also a choice of isometry from the \(B\) inner product to the \(A\) inner product that does not depend on \(R\): \[ C_{A,B}=A^{-1/2}B^{1/2},\qquad C_{A,B}^*AC_{A,B}=B. \tag{13}\] It respects every common reducing subspace of \(A\) and \(B\). We will use this fixed map for one direction of a unitary exchange, and \(S_R^{-1}\) for the other direction. A unitary exchange between two orthogonal subspaces need not be an involution. The last lemma converts an approximately fixed subspace into an exactly fixed one. Its dimension-free estimate also permits orthogonal sums over all group locations. Lemma 6 (Fixing a subspace exactly). Let \(U\) be a unitary on a Hilbert space \(E\), and let \(P\) be an orthogonal projection. Suppose \[\left\lVert U-I\right\rVert\leq t<\tfrac12, \qquad \left\lVert(U-I)P\right\rVert\leq e\leq\tfrac12.\] There is a unitary \(\widehat U\) that is the identity on \(PE\) and leaves \((I-P)E\) invariant, with \[\left\lVert\widehat U-U\right\rVert\leq3e, \qquad \left\lVert\widehat U-I\right\rVert\leq t+3e.\] The statement holds in arbitrary Hilbert space dimension. Proof. Relative to \(E=PE\oplus(I-P)E\), write \[U=\begin{pmatrix}a&b\\c&d\end{pmatrix}.\] Since \((U^*-I)P=-U^*(U-I)P\), both \((U-I)P\) and \(P(U-I)\) have norm at most \(e\). In particular, \(\left\lVert b\right\rVert,\left\lVert c\right\rVert\leq e\), and \[\left\|U-\begin{pmatrix}I&0\\0&d\end{pmatrix}\right\| \leq2e.\] The compression \(d\) satisfies \(\left\lVert d-I\right\rVert\leq t<1\), so it is invertible even in infinite dimension. Its polar factor \(v=d(d^*d)^{-1/2}\) is therefore unitary. Unitarity of \(U\) gives \(d^*d=I-b^*b\), whence \[\left\lVert v-d\right\rVert =\left\lVert I-(d^*d)^{1/2}\right\rVert \leq1-\sqrt{1-e^2}\leq e^2.\] Taking \(\widehat U=I\oplus v\) proves \(\left\lVert\widehat U-U\right\rVert\leq2e+e^2\leq3e\). The remaining estimate follows by the triangle inequality. ◻ Lemma 6 also applies to the \(B\) inner product in Lemma 5: a projection commuting with \(B\) remains orthogonal for that inner product. Hilbert spaces and unitary circuitsWe now turn the flags of Proposition 3 into unitary circuits. The circuits will move vectors between levels while replacing one orthonormal coordinate factor at a time by a redundant frame. The inner products are chosen so that these replacements accumulate a detectable change between the first and last levels. Labels and inner productsFix an integer \(L\), put \(N=L+1\), and set \[ h=\frac1{2\sqrt L}. \tag{14}\] We take \(L\) larger than the numerical lower bounds required below. In particular, \(h\le1/8\) as in Lemma 5. Let \(\eta>0\) be small and choose \(\beta>0\) as in Lemma 4. Proposition 3 supplies the alphabets and flags for \(N\) stages. By repeating labels, we may arrange that all alphabets have sufficiently large even cardinality for Lemma 4 to apply. Repetition preserves the three flag properties. Write \(\left\lvert\mathcal X_k\right\rvert=2m_k\). For \(x\in\mathcal X_k\), let \(a_{k,x}\in\mathbb R^{m_k}\) be the union of two orthonormal bases, and write \(f_k(x)=1\) or \(-1\) according to its basis. In particular, \[ \sum_{x\in\mathcal X_k}f_k(x)a_{k,x}a_{k,x}^*=0. \tag{15}\] For \(1\le d\le L\), let \(J_d\) and \(Z_d\) be the matrices supplied by Lemma 4 on \(\mathbb R^{\mathcal Y_d}\). Thus \(J_d\) is a symmetric involution, has zero diagonal, and anticommutes with the diagonal parity matrix \(Z_d\). All coordinate spaces will be complexified. The set of full labels is \[\mathcal I=\prod_{k=1}^N\mathcal X_k\times\prod_{d=0}^L\mathcal Y_d.\] Coordinates of \(i\in\mathcal I\) are written \(x_k(i),y_d(i)\). On the formal orthonormal label space \(\mathbb C^{\mathcal I}\) define \[ \gamma_d=f_d(X_d)Z_1\cdots Z_{d-1}J_d, \qquad D=\frac1{\sqrt L}\sum_{d=1}^L\gamma_d. \tag{16}\] This uses the Jordan–Wigner parity-string construction [7]; see also [2]. We check the anticommutation relations directly. Here \(f_d(X_d)\) denotes the diagonal operator on the \(\mathcal X_d\) factor, and each \(Z_j,J_j\) acts on its indicated \(\mathcal Y_j\) factor; omitted factors carry the identity. If \(d<e\), the factors \(J_d\) and \(Z_d\) cause \(\gamma_d\gamma_e=-\gamma_e\gamma_d\), while all other relevant factors commute. Hence \[ \gamma_d^* =\gamma_d,\qquad \gamma_d^2=I,\qquad D^*=D,\qquad D^2=I,\qquad \operatorname{Tr}D=0. \tag{17}\] The last identity follows from the zero diagonal of every \(J_d\). For \(0\le k\le N\), let the coordinate space at level \(k\) be \[E_k=\bigotimes_{j\le k}\mathbb C^{m_j} \otimes\bigotimes_{j>k}\mathbb C^{\mathcal X_j} \otimes\bigotimes_{d=0}^L\mathbb C^{\mathcal Y_d}.\] On \(E_k\) the expression for \(\gamma_d\) still makes sense whenever \(d>k\): its \(\mathcal X_d\) coordinate has not been replaced by a frame. Set \[ G_k=I+h\sum_{k<d\le L}\gamma_d. \tag{18}\] Anticommutation gives \[ \frac12 I\le G_k\le\frac32 I, \qquad G_0=I+\frac12D,\qquad G_L=G_N=I. \tag{19}\] The label vector \(v_i^{(k)}\in E_k\) uses \(a_{j,x_j(i)}\) in factors \(j\le k\), the standard vector \(e_{x_j(i)}\) in factors \(j>k\), and \(e_{y_d(i)}\) in every \(\mathcal Y_d\) factor. Its \(G_k\)-norm is one: every added term in (18) has zero diagonal in some \(\mathcal Y_d\) factor. We will repeatedly use two features of \(G_k\). It is the identity on the compressed factors \(\mathbb C^{m_j}\), \(j\le k\). It commutes with each coordinate projection in \(\mathcal X_j\) for \(j>k\) and in \(\mathcal Y_d\) for \(d\le k\). For the latter assertion, a term surviving in (18) contains only diagonal parity operators on those \(\mathcal Y_d\) factors. Take the Hilbert direct sum \[ H=\bigoplus_{k=0}^N\ \bigoplus_{w\in G}(E_k,G_k), \qquad H_k=\bigoplus_{w\in G}(E_k,G_k). \tag{20}\] It is separable. Left translation of the location \(w\) defines a genuine unitary representation \(U:G\to\mathcal U(H)\). No translation changes a label or a level. The subspaces exchanged by one layerFix a nonempty set \(\mathcal C\) of at most three configurations, and \(p\in\mathcal C\). The use of sets allows repeated translates to be removed without changing any definition. A stage-\(k\) edge is a quadruple \((w,k,x,y)\), with arrival \(v=ws_k(x,y)\). It is switchable for \(\mathcal C\) if its flags are not the same in all configurations of \(\mathcal C\). The layer for \(p\) will exchange exactly the switchable edges flagged \(\mathsf F\) in \(p\). We first choose their endpoint subspaces simultaneously for all \(p\in\mathcal C\). At a fixed arrival \(v\) and fixed \(y\in\mathcal Y_{k-1}\), put \[ S_{k,v,y}^{\mathcal C}= \{x\in\mathcal X_k:\ (vs_k(x,y)^{-1},k,x,y) \text{ is switchable for }\mathcal C\}. \tag{21}\] Every switchable edge is flagged \(\mathsf E\) in some configuration. By the arrival bound (F3), \[ \left\lvert S_{k,v,y}^{\mathcal C}\right\rvert\le\left\lvert\mathcal C\right\rvert\beta\left\lvert\mathcal X_k\right\rvert. \tag{22}\] Let \(F_S:\mathbb C^S\to\mathbb C^{m_k}\) have columns \(a_{k,x}\), \(x\in S=S_{k,v,y}^{\mathcal C}\). Replace these columns by \[ \widetilde F_S=F_S(F_S^*F_S)^{-1/2}, \qquad \widetilde a_{k,v,y,x}^{\mathcal C}=\widetilde F_Se_x. \tag{23}\] The sparse Gram estimate makes this well-defined and gives \[ \widetilde F_S^*\widetilde F_S=I, \qquad \left\lVert\widetilde F_S-F_S\right\rVert\le C\eta. \tag{24}\] For \(S=\varnothing\) there are no columns to adjust. The left subspace of a switchable edge is the coordinate sector at \((k-1,w)\) with \(X_k=x\) and \(Y_{k-1}=y\). Its right subspace, at \((k,v)\), has \(Y_{k-1}=y\) and \(X_k\) in the line spanned by \(\widetilde a_{k,v,y,x}^{\mathcal C}\). Every other tensor factor is unrestricted. For distinct edges these left subspaces are orthogonal; so are these right subspaces. On the right this uses (23) and the fact that \(G_k\) is the identity on the compressed \(X_k\) factor. Both endpoint subspaces have the same residual coordinates after removing the fixed \(X_k\) and \(Y_{k-1}\) factors. Their metrics, denoted \(A_{x,y}\) on the left and \(B_y\) on the right, are the corresponding restrictions of \(G_{k-1}\) and \(G_k\). For \(k\le L\), \[ A_{x,y}=B_y+h\Gamma_{x,y},\qquad \Gamma_{x,y}=f_k(x)Z_1\cdots Z_{k-1}J_k\big|_{Y_{k-1}=y}, \qquad \left\lVert\Gamma_{x,y}\right\rVert=1. \tag{25}\] The right metric \(B_y\) is independent of \(x\). Earlier compressed \(X\) factors carry identity operators throughout. At \(k=N\) both metrics are identity. Metric transfer with priority for the next layerFor \(k\le L\), arrival \(v\), and next coordinate \(z\in\mathcal X_{k+1}\), define \[ R_{k,v,z}^{\mathcal C}= \{t\in\mathcal Y_k:\ q_{k+1}(v;z,t)=\mathsf F \text{ for some }q\in\mathcal C\}. \tag{26}\] The row bound (F2) gives \(\left\lvert R_{k,v,z}^{\mathcal C}\right\rvert\le3\beta\left\lvert\mathcal Y_k\right\rvert\). Let \(P_{k,v}^{\mathcal C}\) be the residual-coordinate projection that, in the sector \(X_{k+1}=z\), selects \(Y_k\in R_{k,v,z}^{\mathcal C}\). It is the identity on all remaining factors. This projection commutes with \(B_y\). Moreover, \[ \left\lVert P_{k,v}^{\mathcal C}\Gamma_{x,y}P_{k,v}^{\mathcal C}\right\rVert\le\eta. \tag{27}\] Indeed, decompose by the future \(X\) coordinates and earlier \(Y\) coordinates. In each block the compression is, up to a sign and identity factors, a compression \(J_k[R,R]\) with \(\left\lvert R\right\rvert\le3\beta\left\lvert\mathcal Y_k\right\rvert\). Lemma 4 applies. Taking a direct sum does not increase the bound. Apply Lemma 5 to obtain a specified isometry \[S_e^{\mathcal C}:(\text{residual coordinates},B_y) \longrightarrow(\text{residual coordinates},A_{x,y})\] for this edge. In the original coordinates it satisfies \[ \left\lVert S_e^{\mathcal C}-I\right\rVert\le Ch,\qquad \left\lVert(S_e^{\mathcal C}-I)P_{k,v}^{\mathcal C}\right\rVert\le Ch\eta. \tag{28}\] At \(k=N\) put \(S_e^{\mathcal C}=I\). We will use \((S_e^{\mathcal C})^{-1}\) for the left-to-right part of the exchange. For its right-to-left part, use the fixed isometry \[ C_{x,y}=A_{x,y}^{-1/2}B_y^{1/2}:(B_y)\longrightarrow(A_{x,y}). \tag{29}\] It is independent of \(\mathcal C\), \(p\), and the priority projection. On the left and right subspaces of an edge, in that order, define \[ M_e^{\mathcal C}= \begin{pmatrix}0&C_{x,y}\\(S_e^{\mathcal C})^{-1}&0\end{pmatrix}. \tag{30}\] Both off-diagonal entries are isometries onto the indicated endpoint, so \(M_e^{\mathcal C}\) is unitary. In general it is not an involution. The distinction is useful: its inverse takes a vector from the right to the left using \(S_e^{\mathcal C}\), whereas its forward right-to-left block is \(C_{x,y}\). The stage-\(k\) layer \(M_{p,k}^{\mathcal C}\) applies (30) on every switchable edge flagged \(\mathsf F\) in \(p\), and is identity on the orthogonal complement of their endpoint subspaces. The orthogonality proved above makes this a unitary, even when infinitely many locations occur. Define \[ W_p^{\mathcal C}=M_{p,N}^{\mathcal C}\cdots M_{p,1}^{\mathcal C}, \qquad V_{qp}^{\mathcal C}=W_q^{\mathcal C}(W_p^{\mathcal C})^{-1}. \tag{31}\] Thus layers are applied in the order \(1,\ldots,N\). Every recipe uses coordinate projections and positive square roots, and depends on group locations only through the flags. Consequently \[ U(g)W_p^{\mathcal C}U(g)^{-1}=W_{gp}^{g\mathcal C}, \qquad U(g)V_{qp}^{\mathcal C}U(g)^{-1}=V_{gq,gp}^{g\mathcal C}. \tag{32}\] This is the covariance needed to turn the pairwise comparisons into an almost representation. The next section establishes that introducing a third configuration changes those comparisons only slightly. Comparing two and three configurationsInside one fixed set \(\mathcal C\), the comparisons compose exactly: \(V_{rq}^{\mathcal C}V_{qp}^{\mathcal C}=V_{rp}^{\mathcal C}\). For the almost representation, however, each comparison will be made using its own pair of configurations. We therefore need the following estimate. Proposition 7. There are numerical constants \(C\) and \(h_0>0\) such that, for the construction of Section 4 with \(h\le h_0\) and \(0<\eta\le1/4\), \[ \left\lVert V_{qp}^{\{p,q\}}-V_{qp}^{\{p,q,r\}}\right\rVert \le Ch+CN\eta+CNh\eta \tag{33}\] for every three configurations \(p,q,r\). The constants do not depend on the cardinalities of any alphabets or on the configurations. The proof has three parts. We first put both constructions in the same arrival frames. Extra exchanges common to \(p\) and \(q\) then cancel exactly. The remaining change is in the priority isometries. Their small errors can be moved to separate levels instead of being summed along a path. Changing the arrival framesWrite \(\mathcal C_2=\{p,q\}\) and \(\mathcal C_3=\{p,q,r\}\). At each arrival sector, \(S_2=S_{k,v,y}^{\mathcal C_2}\subset S_3=S_{k,v,y}^{\mathcal C_3}\). By (24), \[ \left\lVert\widetilde F_{S_2}-\widetilde F_{S_3}|_{\mathbb C^{S_2}}\right\rVert \le C\eta. \tag{34}\] For the moment, replace the pair’s arrival vectors by the corresponding columns of \(\widetilde F_{S_3}\), leaving its edges and priorities unchanged. Denote the resulting layers by \(\overline M_{p,k}\) and circuit by \(\overline W_p\); define \(\overline W_q\) in the same way. We justify the operator-norm cost without summing over columns. For one layer, let \(L\) and \(R\) be the isometric embeddings of the direct sums of its active left and right residual spaces into \(H\). Let \(T\) be the direct sum of its left-to-right transfers, and \(C_0\) the direct sum of the fixed right-to-left transfers. The layer equals \[ I-LL^*-RR^*+LC_0R^*+RTL^*. \tag{35}\] Only \(R\) changes when the arrival frame changes. Its domain uses the metric \(B_y\) on each column, independent of the compressed coordinate \(X_k\). Thus (34), tensored with the residual coordinates and summed orthogonally over \((v,y)\), gives \(\left\lVert R-R'\right\rVert\le C\eta\). Formula (35) then bounds the layer change by \(4\left\lVert R-R'\right\rVert\). The transfers have norm one in their respective metrics, even though they may depend on the column \(x\). It follows by telescoping products of unitaries that \[ \left\lVert W_p^{\mathcal C_2}-\overline W_p\right\rVert\le CN\eta, \qquad \left\lVert W_q^{\mathcal C_2}-\overline W_q\right\rVert\le CN\eta. \tag{36}\] Cancelling the common exchangesAmong edges switchable for \(\mathcal C_3\) but not for \(\mathcal C_2\), those flagged \(\mathsf E\) in both \(p\) and \(q\) are unused by both circuits. The others are flagged \(\mathsf F\) in both and are exchanged by both circuits with exactly the same unitary. Call these the common exchanges. A common exchange in a later layer commutes with every noncommon exchange in an earlier layer. Only adjacent layers could share a level. If the earlier edge is noncommon and is used in one of the two circuits, it is \(\mathsf E\) in one of \(p,q\). By (F1), at its arrival location there is no outgoing \(\mathsf F\) edge in that configuration at the next stage. A later common exchange there is therefore impossible. Their supports at the shared level lie at disjoint group locations. The adjustment of the \(X\) vectors changes no location and hence preserves this disjointness. Within a layer all exchanges commute, being supported on orthogonal subspaces. We may therefore move all common exchanges to the beginning of each circuit, retaining their relative order. There are only finitely many layers; infinite families within a layer are orthogonal direct sums, so this rearrangement does not require an infinite product. We obtain \[ W_p^{\mathcal C_3}=\widehat W_p C_{\mathrm{com}},\qquad W_q^{\mathcal C_3}=\widehat W_q C_{\mathrm{com}},\qquad V_{qp}^{\mathcal C_3}=\widehat W_q\widehat W_p^{-1}. \tag{37}\] Here \(\widehat W_p=\widehat M_{p,N}\cdots\widehat M_{p,1}\) consists of the pair-switchable edges used by \(p\), with the triple’s frames and priorities. Thus \(\widehat M_{p,k}\) and \(\overline M_{p,k}\) now have the same edges, subspaces, and fixed reverse transfers. Only their priority isometries differ. Moving the priority changes past later layersWe compare \(\widehat W_p\) with \(\overline W_p\); the argument for \(q\) is identical. For each active edge the smaller priority projection is contained in the larger one. From (30), \[\begin{pmatrix}0&C_{x,y}\\(S_e^{\mathcal C_3})^{-1}&0\end{pmatrix} \begin{pmatrix}0&S_e^{\mathcal C_2}\\C_{x,y}^{-1}&0\end{pmatrix} =\begin{pmatrix}I&0\\0&(S_e^{\mathcal C_3})^{-1}S_e^{\mathcal C_2}\end{pmatrix}.\] Consequently \[ \widehat M_{p,k}=K_k\overline M_{p,k}, \qquad K_k|_{H_k^\perp}=I,\qquad \left\lVert K_k-I\right\rVert\le Ch. \tag{38}\] These norms are in \(H\), with its given metric. The last estimate follows from Lemma 5 and the uniform metric bounds. For \(k<N\), let \(Q_{k+1}\) be the orthogonal projection onto the departure subspace used by \(\overline M_{p,k+1}\) in \(H_k\). We claim that \[ \left\lVert(K_k-I)Q_{k+1}\right\rVert\le Ch\eta. \tag{39}\] At a fixed location, \(Q_{k+1}\) selects the next coordinates \(X_{k+1},Y_k\). A current arrival subspace selects \(Y_{k-1}\) and a line in the compressed \(X_k\) factor. These projections commute: the conditions concern different coordinates, and \(G_k\) preserves the indicated coordinate sectors. On their intersection the smaller priority contains every next departure, by (26). Lemma 5 bounds \((S_e^{\mathcal C_3})^{-1}S_e^{\mathcal C_2}-I\) there by \(Ch\eta\). On the complement of all current arrival subspaces \(K_k=I\). Their orthogonal direct sum proves (39); no factor counting edges or labels occurs. Set \(Q_{N+1}=0\) for the last layer. Apply Lemma 6 on \(H_k\), taking \(h_0\) sufficiently small. It gives a unitary \(\widetilde K_k\), extended by identity off \(H_k\), such that \[ \widetilde K_kQ_{k+1}=Q_{k+1},\qquad \left\lVert K_k-\widetilde K_k\right\rVert\le Ch\eta,\qquad \left\lVert\widetilde K_k-I\right\rVert\le Ch. \tag{40}\] It commutes with \(\overline M_{p,k+1}\): that layer acts only on its departure subspace \(Q_{k+1}H_k\) and its arrival subspace in \(H_{k+1}\), and \(\widetilde K_k\) is identity on both. It also commutes with all later layers, which act on other levels. Figure 1 depicts the only later layer whose support overlaps \(H_k\). Substitute (38) into the product for \(\widehat W_p\). Replacing each \(K_k\) by \(\widetilde K_k\) costs at most \(CNh\eta\) by telescoping. Move every \(\widetilde K_k\) past the subsequent layers. The corrected unitaries commute with one another because they act on distinct levels. Thus \[ \left\lVert\widehat W_p- (\widetilde K_N\cdots\widetilde K_1)\overline W_p\right\rVert \le CNh\eta, \qquad \left\lVert\widetilde K_N\cdots\widetilde K_1-I\right\rVert =\max_k\left\lVert\widetilde K_k-I\right\rVert\le Ch. \tag{41}\] Together with (36), this proves \[\left\lVert\widehat W_p-W_p^{\mathcal C_2}\right\rVert\le Ch+CN\eta+CNh\eta,\] and the same bound holds for \(q\). Using (37) and telescoping the two factors in \(V_{qp}\) proves Proposition 7. The almost representationReturn to the original configuration \(b\) and define \[ \mu(g)=V_{b,gb}^{\{b,gb\}}U(g). \tag{42}\] When \(g=e\), there is just one configuration and no switchable edge; therefore \(\mu(e)=I\). Equivariance (32) gives \[\mu(g)\mu(t) =V_{b,gb}^{\{b,gb\}}V_{gb,gtb}^{\{gb,gtb\}}U(gt).\] Replace both comparisons here and the comparison in \(\mu(gt)\) by those computed in \(\{b,gb,gtb\}\). Within that common set, \[V_{b,gb}^{\{b,gb,gtb\}}V_{gb,gtb}^{\{b,gb,gtb\}} =V_{b,gtb}^{\{b,gb,gtb\}}.\] Three applications of Proposition 7 yield \[ \operatorname{def}(\mu)\le Ch+CN\eta+CNh\eta. \tag{43}\] The remaining task is to show that the distance from representations does not tend to zero with this bound. Distance from genuine representationsThe map \(\mu\) has small defect by (43). To separate it from genuine representations, we compare labelled vectors at the last and first levels. Most labels are transported between these vectors by \(\mu\), but a quadratic form takes incompatible values on the two families if that transport is performed by a genuine representation. Transport along most pathsFor \(i\in\mathcal I\), abbreviate \(s_k(i)=s_k(x_k(i),y_{k-1}(i))\) and put \[t_0(i)=e,\qquad t_k(i)=s_1(i)\cdots s_k(i),\qquad s_i=t_N(i).\] Let \(u_i\) be \(v_i^{(N)}\) at location \(e\) and level \(N\), and let \(r_i\) be \(v_i^{(0)}\) at location \(e\) and level zero. Both are unit vectors. Lemma 8. For all but a proportion \(2N\beta\) of labels \(i\in\mathcal I\), \[ \left\lVert\mu(s_i)u_i-r_i\right\rVert\le CN\eta+CNh\eta. \tag{44}\] Proof. Give \(\mathcal I\) its uniform product probability measure. Along the forward path \(t_0,\ldots,t_N\), the departure \(t_{k-1}\) depends only on coordinate pairs \((X_j,Y_{j-1})\) with \(j<k\). Conditional on these pairs and on \(X_k\), the coordinate \(Y_{k-1}\) is still uniform. The row bound (F2) therefore makes the probability of an \(\mathsf F\) step at most \(\beta\). A union bound shows that every forward step is \(\mathsf E\) with probability at least \(1-N\beta\). Consider also the path with the same steps and terminal point \(e\). Its stage-\(k\) arrival is \[ a_k(i)=s_N(i)^{-1}s_{N-1}(i)^{-1}\cdots s_{k+1}(i)^{-1} =s_i^{-1}t_k(i). \tag{45}\] Thus \(a_{k-1}s_k=a_k\), and \(a_k\) depends only on the later coordinate pairs. Conditional on these pairs and \(Y_{k-1}\), the arrival bound (F3) makes the probability of an \(\mathsf E\) step at most \(\beta\). Every backward-path step is \(\mathsf F\) with probability at least \(1-N\beta\). Let \(\mathcal I_{\mathrm{good}}\) be the intersection of these two events. We have \[ \left\lvert\mathcal I\setminus\mathcal I_{\mathrm{good}}\right\rvert/\left\lvert\mathcal I\right\rvert\le2N\beta. \tag{46}\] No independence between the two events is needed. For \(i\) in this set, put \(p=s_i b\). Equation (45) and the definition of translation show that the forward path \(t_0,\ldots,t_N\) is entirely \(\mathsf E\) for \(b\) and entirely \(\mathsf F\) for \(p\). All its edges are switchable for \(\{b,p\}\). Let \(z_k\) be the exact label vector \(v_i^{(k)}\) at location \(t_k(i)\). Thus \(z_N=U(s_i)u_i\) and \(z_0=r_i\). At stage \(k\), replacing its factor \(a_{k,x_k(i)}\) by the adjusted arrival vector changes \(z_k\) by at most \(C\eta\), by (24) and (19). The adjusted vector belongs to the active right subspace of the path’s edge. The inverse layer takes it to the left using \(S_e^{\{b,p\}}\). For \(k<N\), its residual coordinates belong to the priority subspace: the next step \((t_k,x_{k+1},y_k)\) is \(\mathsf F\) in \(p\). Equation (28) therefore changes these coordinates by at most \(Ch\eta\). At \(k=N\) the transfer is identity. We conclude that \[\left\lVert(M_{p,k}^{\{b,p\}})^{-1}z_k-z_{k-1}\right\rVert \le C\eta+Ch\eta.\] Telescoping the inverse circuit from \(N\) to \(1\) gives \[\left\lVert(W_p^{\{b,p\}})^{-1}U(s_i)u_i-r_i\right\rVert \le CN\eta+CNh\eta.\] All actual layers are unitary, so the previously incurred errors are not amplified. Finally \(W_b^{\{b,p\}}r_i=r_i\): its first layer does not use the departure sector of the first, \(\mathsf E\)-flagged step, and later layers do not act on level zero. Formula (42) proves the claim. ◻ A quadratic form that vanishes for representationsThe signed frames were chosen to make the following identity hold for every genuine representation, without any assumption that it preserve our tensor factors or levels. Lemma 9. Let \(\rho:G\to\mathcal U(H)\) be a unitary representation, and define unit vectors in \(\mathbb C^{\mathcal I}\otimes H\) by \[\psi=\left\lvert\mathcal I\right\rvert^{-1/2}\sum_{i\in\mathcal I}e_i\otimes\rho(s_i)u_i, \qquad r=\left\lvert\mathcal I\right\rvert^{-1/2}\sum_{i\in\mathcal I}e_i\otimes r_i.\] Then \[ \left\langle\psi,(D\otimes I)\psi\right\rangle=0, \qquad \left\langle r,(D\otimes I)r\right\rangle=\frac12. \tag{47}\] In particular, \(\left\lVert r-\psi\right\rVert\ge1/4\). Proof. For any labels \(i,j\), unitarity and multiplicativity give \[\left\langle\rho(s_i)u_i,\rho(s_j)u_j\right\rangle =\left\langle u_i,\rho(s_i^{-1}s_j)u_j\right\rangle.\] Fix \(d\in\{1,\ldots,L\}\). A nonzero coefficient \((\gamma_d)_{ij}\) pairs labels that agree except possibly in \(Y_d\). Their group products have a common prefix through stage \(d\): \[s_i=P Q_i,\qquad s_j=P Q_j, \qquad s_i^{-1}s_j=Q_i^{-1}Q_j.\] After all coordinates other than \(X_d\) are fixed, the suffixes \(Q_i,Q_j\) are independent of \(X_d\): steps after \(d\) use only \(X_{d+1},\ldots,X_N\). There are linear isometric embeddings \(E_i,E_j:\mathbb C^{m_d}\to H\), also independent of \(X_d\), such that \(u_i=E_i a_{d,x_d}\) and \(u_j=E_j a_{d,x_d}\). Here the metric at level \(N\) is Euclidean. The factor of \((\gamma_d)_{ij}\) that depends on \(X_d\) is exactly \(f_d(x_d)\). Consequently the sum over that coordinate is a fixed scalar multiple of \[\begin{align*} &\sum_{x\in\mathcal X_d} f_d(x) \left\langle a_{d,x},E_i^*\rho(Q_i^{-1}Q_j)E_j a_{d,x}\right\rangle\\ &\hspace{1cm}= \operatorname{Tr}\left(E_i^*\rho(Q_i^{-1}Q_j)E_j \sum_{x\in\mathcal X_d}f_d(x)a_{d,x}a_{d,x}^*\right)=0 \end{align*}\] by (15). Summing all other coordinates proves \(\left\langle\psi,(\gamma_d\otimes I)\psi\right\rangle=0\), and summing \(d\) proves the first identity in (47). The Gram matrix of the vectors \(r_i\) is \(G_0\), since these are the standard label vectors at level zero. Both \(G_0\) and \(D\) are real symmetric. Equations (17) and (19) give \[\left\langle r,(D\otimes I)r\right\rangle =\frac{\operatorname{Tr}(DG_0)}{\left\lvert\mathcal I\right\rvert} =\frac{\operatorname{Tr}(D+\frac12D^2)}{\left\lvert\mathcal I\right\rvert}=\frac12.\] Since \(\left\lVert D\right\rVert=1\) and both vectors have norm one, \[\frac12 \le \left\lVert r-\psi\right\rVert\left\lVert r\right\rVert+\left\lVert\psi\right\rVert\left\lVert r-\psi\right\rVert =2\left\lVert r-\psi\right\rVert.\] This proves the last assertion. ◻ Parameter choice and the main theoremSuppose that \(\rho\) is uniformly within \(\varepsilon\) of \(\mu\). Lemma 8 bounds the transport error on \(\mathcal I_{\mathrm{good}}\); on its complement the error is at most two, because both vectors are unit. The triangle inequality in the orthogonal label sum therefore gives \[ \left\lVert r-\psi\right\rVert \le \varepsilon+CN\eta+CNh\eta+2\sqrt{2N\beta}. \tag{48}\] All constants in this estimate and (43) are numerical. We can now make the parameter order explicit. Proof of Theorem 1. The amenable implication is Kazhdan’s theorem [9]. Suppose that \(G\) is nonamenable, and fix any \(\delta>0\). First choose \(L\) large enough that \(h=1/(2\sqrt L)\) meets every numerical smallness condition above and \(Ch<\delta/2\) in (43). With \(N=L+1\) now fixed, choose \(0<\eta<1/4\) so small that \[CN\eta+CNh\eta<\min\{\delta/2,1/20\}\] for the constants in both (43) and (48). Next choose \[0<\beta<\min\{\beta_0(\eta),\,1/(3200N)\},\] where \(\beta_0(\eta)\) is supplied by Lemma 4. Construct the flags and then enlarge the alphabets to the dimensions required by that lemma. None of the established estimates worsens when the alphabets are enlarged. The resulting normalized map has defect less than \(\delta\). If a genuine representation were uniformly within \(1/10\) of it, (48) would give \[\left\lVert r-\psi\right\rVert<\frac1{10}+\frac1{20}+\frac1{20}=\frac15,\] contrary to Lemma 9. Thus (1) holds for every \(\delta>0\), which rules out strong Ulam stability. ◻
|
| ||||||||
|