ULAM STABILITY CHARACTERIZES AMENABILITY - A STUDY GUIDE

How to read this file. This is a study guide to one research paper: the
proof that a countable discrete group is amenable if and only if it is
strongly Ulam stable. It is written for a patient high-school reader.
Each block starts with "Exercise:" then a short question, then a
self-contained answer. Some answers contain a "Proof:" giving the full
argument. Named results carry a short nickname in parentheses, e.g.
"Lemma (Uniform Lists)" or "Proposition (Compatible Sparse Flags)". The
full statement of each named result is in its own answer. Mathematical
notation is introduced at first use; the symbols you will meet first are
G (a group), e (its identity), H (a Hilbert space), U(H) (the unitary
operators of H), and the operator norm ||.||. All vector spaces are over
the complex numbers. Inner products are conjugate-linear in the first
argument, so <x,y> = sum over i of conj(x_i) y_i; the product <x,y>_A
where A is a positive operator means <x, A y>. A numerical constant
written as C is positive and absolute and may change from line to line;
it never depends on the group, on the number of labels, or on the number
of levels. We write N whenever an estimate sums over N levels. The map
mu always denotes an almost representation, and rho a genuine one.

Exercise: The main theorem. What does the paper prove?
Answer. For a countable discrete group G the following two statements
are equivalent. (i) G is amenable. (ii) G is strongly Ulam stable.
Kazhdan proved (i) implies (ii) in 1982; this paper proves the converse
(ii) implies (i). Concretely, for every nonamenable countable G and
every tolerance delta > 0 there is a separable Hilbert space H and a map
mu: G -> U(H), with mu(e) = I, whose defect is below delta but whose
distance from every genuine unitary representation on H is more than
1/10:
  sup over g in G of || mu(g) - rho(g) || > 1/10  for every rep rho.
So mu is an almost representation that cannot be corrected, no matter
how small we make its defect. This completes the characterization asked
for by Burger, Ozawa and Thom.
Reference: Burger, Ozawa, Thom 2013, On Ulam stability:
https://doi.org/10.1007/s11856-012-0050-z

Exercise: Group. What is a countable discrete group?
Answer. A set G with an associative multiplication, an identity e and
inverses, whose underlying set is countable and carries no extra
structure. In particular no topology or measure is assumed in the
definition of amenability. Left multiplication by g sends h to gh and
gives an action of G on itself. Left translation on functions is
(L_g f)(x) = f(g^{-1}x). Throughout, groups are countable and discrete,
and "amenable" always means "countable discrete amenable".

Exercise: Hilbert space and unitary. What are they?
Answer. A complex Hilbert space H is a complete inner-product space. An
operator u: H -> H is unitary if u is linear and bijective and
preserves inner products, <ux,uy> = <x,y> for all x, y; equivalently
u^* u = u u^* = I. The set U(H) of all unitary operators is a group.
The operator norm is ||u|| = sup of ||ux|| over unit vectors x, equal to
sup of <ux,ux>^{1/2} over ||x|| = 1. Unitary operators have norm 1.

Exercise: Representation. What is a unitary representation?
Answer. A unitary representation of G on H is a group homomorphism
rho: G -> U(H). So rho(gh) = rho(g) rho(h) for all g, h and rho(e) = I.
Representations that differ by conjugation with a single unitary are
the same for our purposes.

Exercise: Almost representation and defect. What is defect(mu)?
Answer. An almost representation is a map mu: G -> U(H) with mu(e) = I
that is only approximately multiplicative. Its defect is
  defect(mu) = sup over (g,h) in G x G of || mu(gh) - mu(g) mu(h) ||.
It is a nonnegative real number (possibly infinite). Small defect means
mu(gh) is uniformly close to mu(g) mu(h) in operator norm, for all pairs
g, h at once.

Exercise: Strong Ulam stable. State the definition precisely.
Answer. A countable discrete group G is strongly Ulam stable if the
following holds. For every eps > 0 there is delta > 0 such that, for
every complex Hilbert space H of any dimension (finite or infinite) and
every mu: G -> U(H) with mu(e) = I and defect(mu) <= delta, there is a
genuine unitary representation rho: G -> U(H) on the same space H with
  sup over g in G of || mu(g) - rho(g) || <= eps.
Three points that matter: the same H must be used for mu and rho; the
approximation must be uniform over all of G, not just on generators; and
delta must work for every Hilbert space at once, infinite-dimensional
ones included.

Exercise: Amenable. What does amenable mean?
Answer. A countable discrete group G is amenable if the Banach space
l^infty(G) of bounded complex functions on G admits a positive linear
functional m with m(1) = 1 and m(L_g f) = m(f) for every g and f. Such
an m is a left-invariant finitely additive probability measure. Examples:
finite groups, abelian groups, solvable groups, groups of subexponential
growth. The free group F_2 on two generators is the standard nonamenable
example. Amenability has many equivalent forms (Folner sets, invariant
means, absence of paradox); the only one we use here is the existence of
a non-singleton boundary, described below.

Exercise: Regular versus strong Ulam stability. Why the adjective?
Answer. "Ulam stability" without "strong" usually means the same
statement with H restricted to finite dimension (Burger-Ozawa-Thom
Definition 2.1). That finite-dimensional statement is satisfied by some
nonamenable groups: higher-rank lattices are stable in this weak sense,
as shown by Glebsky, Lubotzky, Monod and Rangarajan. Strong stability
allows every Hilbert space, including infinite-dimensional ones, and it
is only this stronger property that characterizes amenability. The two
statements genuinely differ; the whole point of the paper is the strong
version.
Reference: Burger, Ozawa, Thom 2013, Definition 2.1:
https://doi.org/10.1007/s11856-012-0050-z

Exercise: Kazhdan. What did Kazhdan prove?
Answer. Kazhdan (1982) proved that every amenable group is strongly
Ulam stable, with a positive constant delta(eps) that works for every
Hilbert space simultaneously. He also exhibited unstable almost
representations of the fundamental groups of closed orientable surfaces
of genus at least two, the first examples of nonamenable groups failing
strong stability.
Reference: Kazhdan 1982, On epsilon-representations:
https://doi.org/10.1007/BF02761236

Exercise: Burger-Ozawa-Thom and Alpeev. What did they settle, and what
remained open?
Answer. Burger-Ozawa-Thom showed that every group containing a
nonabelian free subgroup fails strong Ulam stability (Theorem 1.2 of
their paper), and they asked whether strong Ulam stability characterizes
amenability (page 111). That question is answered by the main theorem
above. Alpeev then proved that restricted wreath products A wr G fail
strong stability when A is a nontrivial countable abelian group and G is
countable nonamenable, using measured equivalence relations; his
examples reach into groups without nonabelian free subgroups, which is a
genuinely different mechanism of failure.
Reference: Alpeev, Lamplighters over non-amenable groups are not
strongly Ulam stable: https://arxiv.org/abs/2009.11738

Exercise: Strategy of the converse. What is the plan of the proof?
Answer. Fix a nonamenable countable G and any tolerance delta > 0. We
build a separable H and an almost representation mu with defect(mu) <
delta. Inside an auxiliary label space we find two self-adjoint unitaries
and two unit vectors r and psi such that (a) <psi, D psi> = 0 holds for
any vector psi = (1/sqrt |I|) sum_i e_i tensor rho(s_i) u_i produced
from a genuine representation rho; (b) <r, D r> = 1/2 holds for the exact
vector r our construction produces; (c) ||r - psi|| >= 1/4 always. If a
genuine rho were within 1/10 of mu, the same transport argument would
force ||r - psi|| < 1/5, contradicting 1/4. Thus mu stays more than 1/10
from every representation. All the rest of the paper is the bookkeeping
needed to make (a), (b), (c) coexist.

Exercise: Furstenberg boundary. What is a boundary of G, and why does
a nonamenable G have one?
Answer. A compact G-space K is a boundary if the action of G is minimal
(every orbit is dense) and strongly proximal (the weak-star closure of
the orbit of every Radon probability measure contains a point mass).
The boundary characterization of amenability says a countable discrete
group is amenable if and only if it admits no non-singleton boundary.
So a nonamenable G admits a compact Hausdorff K with more than one
point. We fix such a K for the rest of the proof. Furstenberg built
these; the modern reference is Kalantar-Kennedy.
Reference: Furstenberg 1973, Boundary theory and stochastic processes
on homogeneous spaces: Proc. Sympos. Pure Math. 26, Amer. Math. Soc.
Reference: Kalantar, Kennedy 2017, Boundaries of reduced C*-algebras of
discrete groups: https://doi.org/10.1515/crelle-2014-0111

Exercise: Uniform lists. What do we extract from the boundary?
Answer. (Lemma (Uniform Lists).) Let K be a compact Hausdorff boundary,
U a nonempty open subset, zeta a point of K, and 0 < beta < 1. There is
a finite nonempty list s_1, ..., s_M in G, repetitions allowed, such
that
  s_j^{-1} zeta is in U for all j (1 <= j <= M),
  #{j : s_j^{-1} t is not in U} / M < beta for every t in K.
Moreover some open neighbourhood O of zeta satisfies s_j^{-1} O is
contained in U for every j.
Intuition: from any starting point t, almost all the listed steps s_j
land inside U; and the distinguished point zeta, together with an
entire neighbourhood of it, is captured by all of them. The "M" is the
length of the list. The bound beta is the failure proportion.

Exercise: Proof of Uniform Lists. Why is the lemma true?
Proof. Choose t_0 in U and a continuous f: K -> [0,1] with f(t_0) = 1
and support(f) contained in U. Put A = { f o s^{-1} : s in G, s^{-1} zeta
in U }, a subset of C(K, R). First claim: for every Radon probability m
on K there is some a in A with int_K a dm > 1 - beta/2. To see it,
apply strong proximality and minimality to the mixed measure (m +
delta_zeta)/2. Some s in G has
  (1/2)( int_K f(s^{-1} t) dm(t) + f(s^{-1} zeta) ) > 1 - beta/4.
Both terms in brackets are <= 1, so each exceeds 1 - beta/2; in
particular f(s^{-1} zeta) = 1, forcing s^{-1} zeta in U. Second claim:
the convex hull of A contains a function strictly larger than 1 - beta
everywhere on K. Suppose the opposite. Separate the convex hull from
the nonempty open convex set of continuous functions that exceed
1 - beta on K, using Hahn-Banach. This gives a nonzero continuous linear
functional Lambda with sup_{a in A} Lambda(a) <= inf_{q in O}
Lambda(q), O the open set above. Lambda is positive: if u >= 0 and q is
in O, then q + t u is still in O for all t >= 0, which contradicts the
separation if Lambda(u) < 0. A nonzero positive functional has
Lambda(1) > 0, so normalize Lambda(1) = 1; the Riesz representation
theorem identifies Lambda with integration against a Radon probability
m. Applying the separation to the constant functions q = 1 - beta + eps
and letting eps -> 0 gives sup_{a in A} int_K a dm <= 1 - beta,
contradicting the first claim. So a finite convex combination of
functions from A exceeds 1 - beta on K. Compactness upgrades ">" to a
strictly positive uniform margin. Approximate the coefficients by
nonnegative rationals summing to 1, close enough to preserve the margin;
clearing denominators gives a list s_1, ..., s_M with
  (1/M) sum_{j=1}^M f(s_j^{-1} t) > 1 - beta for every t in K.
Since f vanishes outside U and takes values in [0,1], this is exactly
the required counting inequality. Finally O = intersection_j s_j U is an
open neighbourhood of zeta with the asserted image property.

Exercise: Compatible sparse flags. State the proposition.
Answer. (Proposition (Compatible Sparse Flags).) Let G be nonamenable.
For every integer N >= 1 and every 0 < beta < 1 there are finite
nonempty alphabets X_1, ..., X_N and Y_0, ..., Y_{N-1}, maps
  s_k: X_k x Y_{k-1} -> G,     b_k: G x X_k x Y_{k-1} -> {E, F},
with the following properties.
(F1) If k < N and b_k(w;x,y) = E, then at v = w s_k(x,y) every
next-stage label is E: b_{k+1}(v;x',y') = E for all x', y'.
(F2) For every k, w, x:
  #{y in Y_{k-1} : b_k(w;x,y) = F} / |Y_{k-1}| <= beta.
(F3) For every k, v, y:
  #{x in X_k : b_k(v s_k(x,y)^{-1}; x, y) = E} / |X_k| <= beta.
The letters stand for "easy" (E) and "forced" (F). F2 says: from a fixed
departure, almost all the ways to move are E. F3 says: into a fixed
arrival, almost all the arrival labels are F. F1 says: after an E step,
nothing can be F. This last property is what makes two circuits cancel.

Exercise: Proof of Compatible Sparse Flags. Where do (F1), (F2), (F3)
come from?
Proof. Fix points xi, zeta in K and pick an integer C > 1/beta.
Construct nonempty open subsets U_0, ..., U_N of K backwards, starting
at U_N = K. Given U_k, choose inside it pairwise disjoint nonempty open
sets U_{k,1}, ..., U_{k,C} and set X_k = {1, ..., C}. For each c in
X_k apply Uniform Lists to U_{k,c} at zeta; repeat the lists so they all
have the common length M_k; index each list by Y_{k-1} = {1, ..., M_k};
call the entry s_k(c, y). Set
  U_{k-1} = intersection over c in X_k, y in Y_{k-1} of s_k(c,y)U_{k,c}.
This is an open neighbourhood of zeta and satisfies, by construction,
  s_k(c,y)^{-1} U_{k-1} is contained in U_{k,c} is contained in U_k, for
  every (c, y).
This finishes the backward construction.
For a step w -> v = w s_k(c,y), set b_k(w; c, y) = E exactly when
v^{-1} xi is in U_{k,c}, and F otherwise.
  (F1): if b_k(w;c,y) = E then v^{-1} xi is in U_k. For every next
label (c', y'), (v s_{k+1}(c',y'))^{-1} xi = s_{k+1}(c',y')^{-1}(v^{-1}
xi), which lies in U_{k+1,c'} by the backward region condition at stage
k+1. So the next flag is E.
  (F2): fix w, c. Apply the counting clause of Uniform Lists at the
boundary point w^{-1} xi. The flag-E condition is exactly
s_k(c,y)^{-1} w^{-1} xi in U_{k,c}, so fewer than a beta fraction of the
y have flag F.
  (F3): fix 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 E exactly when v^{-1} xi
lies in U_{k,c}. The C regions U_{k,c} are disjoint, so at most one of
the C labels can have this property. Since 1/C < beta, this proves (F3).

Exercise: Alphabets larger. Why can we enlarge the alphabets at will?
Answer. 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 are unchanged, and (F1) remains
exact. Thus every alphabet can be made arbitrarily large and a multiple
of any prescribed positive integer, with no loss.

Exercise: Configurations and switchable edges. What are they?
Answer. For g in G define the translated flags p = g b by
p_k(w; x, y) = b_k(g^{-1} w; x, y). A configuration is such a translate.
Every configuration still satisfies (F1)-(F3), because left translation
carries the step w -> w s_k(x,y) to a step with the same labels. Along
any path through successive stages the F steps form an initial segment:
once an E step occurs, every later step is E. A stage-k edge is a
quadruple (w, k, x, y) with arrival v = w s_k(x, y). It is switchable
for a set C of at most three configurations if its flags are not the
same in all configurations of C. The layer built for p in C exchanges
exactly the switchable-for-C edges that are F in p.

Exercise: Sparse restrictions. State the lemma.
Answer. (Lemma (Sparse Restrictions).) For every 0 < eta < 1/4 there is
0 < beta_0 < 1/16 with the following property. If 0 < beta <= beta_0,
then for every sufficiently large integer m there are unit vectors
(a_x)_{x in X} in R^m, with |X| = 2m, and signs f(x) in {1, -1} such
that:
(1) the vectors with either sign form an orthonormal basis, and hence
  sum_{x in X} f(x) a_x a_x^* = 0;
(2) if S is a subset of X with |S| <= 4 beta |X|, the synthesis map
F_S: l^2(S) -> C^m, F_S e_x = a_x, satisfies || F_S^* F_S - I || <= eta.
Moreover, for every sufficiently large integer n there is a real
orthogonal n x n matrix O such that, on a set Y of size 2n, the matrices
  J = [[0, O], [O^*, 0]],      Z = [[I, 0], [0, -I]]
satisfy || P_S J P_T || <= eta whenever |S|, |T| <= 4 beta |Y|. Here P_S,
P_T are the coordinate projections. In particular J^* = J, J^2 = Z^2 =
I, JZ = -ZJ, and every diagonal entry of J is zero.

Exercise: Proof of Sparse Restrictions. Why is the lemma true?
Proof. Haar measure on the orthogonal group O(m). For fixed real unit
vectors u, v, the random variable u^* O v has the distribution of the
first coordinate of a uniform point on the sphere,
(g_1, ..., g_m)/(sum g_j^2)^{1/2}, with independent standard Gaussians.
Conditioning on sum_{j>=2} g_j^2 and using the Gaussian tail bound gives,
for 0 < t < 1,
  P(|u^* O v| > t) <= 2 E exp(-t^2/(2(1-t^2)) sum_{j>=2} g_j^2)
    = 2 (1 - t^2)^{(m-1)/2} <= 2 exp(-(m-1) t^2/2).
Take q = 8 beta < 1/2. For coordinate sets S, T each of size at most qm,
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 <= eta/2 on
these nets has norm <= eta, because approximating a maximizing pair of
unit vectors changes the form by at most half its norm. The number of
subsets of {1, ..., m} of size at most qm is at most exp(m H(q)),
with H(q) = -q log q - (1 - q) log(1 - q). A union bound over all pairs
of subsets and all points of the nets gives: the probability that some
submatrix P_S O P_T has norm larger than eta is at most
  2 exp(2 m H(q) + 2 q m log 9 - m eta^2/16)  for every m >= 2.
Pick beta_0 so small that, for q = 8 beta_0, 2 H(q) + 2 q log 9 <
eta^2/32. Then the probability is < 1 for all sufficiently large m, so
some orthogonal O has all qm-by-qm submatrices of norm <= eta. Take the
two bases to be the standard basis and the columns of O, with signs +1
and -1. For a subset of their union, the Gram matrix minus I has block
form [[0, O_{S,T}], [O_{S,T}^*, 0]], of norm || O_{S,T} ||, proving (2).
The same construction in dimension n produces J and Z. Each restriction
P_S J P_T has two off-diagonal blocks of the preceding kind, with
orthogonal domains and ranges, so its norm is the larger of the two.

Exercise: Symmetric orthonormalization. What does it give?
Answer. For every allowed subset S the column map
F-tilde_S = F_S (F_S^* F_S)^{-1/2}
satisfies F-tilde_S^* F-tilde_S = I and || F-tilde_S - F_S || <= C eta.
This follows by applying |t^{-1/2} - 1| <= C |t - 1| on [3/4, 5/4] to
F_S^* F_S. If S is a subset of T and both are allowed, then F-tilde_S
and the restriction of F-tilde_T to l^2(S) differ by at most 2 C eta:
each is within C eta of F_S. All these bounds hold for every allowed
subset simultaneously.

Exercise: Transfer with a prescribed subspace. State the lemma.
Answer. (Lemma (Transfer with Prescribed Subspace / Priority).) Let
A, B be positive operators on a Hilbert space E such that
  1/2 I <= A, B <= 2 I,
  A - B = h Gamma,  Gamma^* = Gamma,  ||Gamma|| <= 1,  0 <= h <= 1/8.
Let P be an orthogonal projection commuting with B, and set R = PE.
Assume || P Gamma P || <= eta with 0 <= eta <= 1. Then there is a
specified invertible operator S_R with
  S_R^* A S_R = B,  S_R(R) = R,
  || S_R - I || <= C h,  || (S_R - I) P || <= C h eta.
The constant C is absolute; the same estimates hold in the B-norm after
changing C. Preservation is meant as "takes R onto R"; the orthogonal
complement of R need not be preserved. If R is contained in R' and both
projections satisfy the hypotheses, then K = S_{R'}^{-1} S_R satisfies
  K^* B K = B,  || K - I ||_B <= C h,  || (K - I) P ||_B <= C h eta.
The construction commutes with orthogonal direct sums and with every
orthogonal projection commuting with A, B, P.

Exercise: Proof of Priority. How is S_R built?
Proof. First make B standard, using B^{-1/2}. Set
  A-hat = B^{-1/2} A B^{-1/2} = I + h B^{-1/2} Gamma B^{-1/2}.
Since P commutes with B, this change preserves the decomposition
E = R oplus R^perp. Relative to it, write
  A-hat = [[a, b], [b^*, d]],   Esch = d - b^* a^{-1} b (Schur complement).
The hypotheses give || A-hat - I || <= 2 h and || a - I_R || <= 2 h eta.
In particular, a and Esch are positive and invertible. Define
  Q_R = [[a^{-1/2}, -a^{-1} b Esch^{-1/2}], [0, Esch^{-1/2}]],
  S_R = B^{-1/2} Q_R B^{1/2}.
(Drop empty blocks if either summand of E is zero.) Direct
multiplication gives Q_R^* A-hat Q_R = I, hence S_R^* A S_R = B; and
the first block column shows S_R(R) = R.
The bounds are uniform in infinite dimension. We have
a >= (1 - 2 h) I_R, || b || <= 2 h,
Esch >= (1 - 2 h) I_{R^perp}, || Esch - I_{R^perp} || <= 2 h +
4 h^2/(1 - 2 h). The lower bound on Esch comes from minimizing
<(x, y), A-hat(x, y)> over x in R for fixed y. Functional calculus in
these fixed spectral intervals gives
  || Q_R - I || <= C h,  || (Q_R - I) P || = || a^{-1/2} - I_R || <= C h
eta.
Conjugation by B^{1/2} costs at most a factor 2. For the nested
statement, S_R and S_{R'} are both isometries from B to A, so 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, because R is
contained in R'; and S_{R'}^{-1} has uniformly bounded norm.

Exercise: Fixed transfer. What is it, and why do we want it?
Answer. There is one isometry from B to A that does not depend on any
prescribed subspace:
  C_{A,B} = A^{-1/2} B^{1/2},   C_{A,B}^* A C_{A,B} = B.
It respects every common reducing subspace of A and B. We use it for
one direction of a unitary exchange and S_R^{-1} for the other. A
unitary exchange between two orthogonal subspaces need not be an
involution, and we exploit this flexibility.

Exercise: Truncate. State the lemma.
Answer. (Lemma (Fixing a Subspace Exactly / Truncate).) Let U be a
unitary on a Hilbert space E, and let P be an orthogonal projection.
Suppose
  || U - I || <= t < 1/2,   || (U - I) P || <= e <= 1/2.
Then there is a unitary U-hat that is the identity on PE and leaves
(I - P)E invariant, with
  || U-hat - U || <= 3 e,   || U-hat - I || <= t + 3 e.
The statement holds in arbitrary Hilbert dimension.

Exercise: Proof of Truncate. Why does it hold?
Proof. Relative to E = PE oplus (I - P)E write U = [[a, b], [c, d]].
Since (U^* - I) P = -U^* (U - I) P, both (U - I) P and P(U - I) have
norm at most e; in particular || b ||, || c || <= e and
  || U - [[I, 0], [0, d]] || <= 2 e.
The compression d satisfies || d - I || <= t < 1, so d 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
  || v - d || = || I - (d^* d)^{1/2} || <= 1 - sqrt(1 - e^2) <= e^2.
Taking U-hat = I oplus v proves || U-hat - U || <= 2 e + e^2 <= 3 e. The
remaining estimate follows by the triangle inequality.
Note. The same lemma applies in the B-inner product of Lemma (Priority),
because a projection that commutes with B stays orthogonal for that
inner product.

Exercise: Parameters and notation. What are L, N, h, eta, beta?
Answer. Fix a large odd integer L and set N = L+1. (L must be
astronomically large compared to 1/delta, and we only ever use
inequalities "for L large enough".) Set
  h = 1/(2 sqrt L).   Then h <= 1/8 once L >= 4.
Choose eta > 0 very small and choose beta > 0 satisfying Lemma (Sparse
Restrictions); then apply Proposition (Compatible Sparse Flags) with N
stages and this beta, and enlarge the alphabets (still with the same
beta) so all |X_k| and |Y_d| are sufficiently large and even.
The parameters satisfy a strict order: L huge, then eta small, then
beta small enough that (Sparse Restrictions) applies. Keep this order
in mind; it is used again in the final parameter choice.

Exercise: Signed frames. What is (a_{k,x}, f_k(x))?
Answer. Write |X_k| = 2 m_k. For x in X_k we have a unit vector
a_{k,x} in R^{m_k}. The even number 2 m_k of vectors consists of two
copies of each of two orthonormal bases of R^{m_k}, one carrying sign
+1 (those are the f_k(x) = 1) and one carrying sign -1. From Lemma
(Sparse Restrictions) with S = X_k,
  sum_{x in X_k} f_k(x) a_{k,x} a_{k,x}^* = 0,
which is the signed frame cancellation we later use as the obstruction.

Exercise: Anticommuting involutions. What are J_d, Z_d, gamma_d?
Answer. For 1 <= d <= L, Lemma (Sparse Restrictions) on Y_d gives a
symmetric involution J_d with zero diagonal and a diagonal parity matrix
Z_d, with
  J_d^2 = Z_d^2 = I,   J_d Z_d = -Z_d J_d,  and every diagonal entry of
  J_d is zero.
On the formal orthonormal label space C^I (defined next) put
  gamma_d = f_d(X_d) Z_1 Z_2 ... Z_{d-1} J_d,   d = 1, ..., L,
  D = (1/sqrt L) sum_{d=1}^L gamma_d.
Here f_d(X_d) means the diagonal operator on the X_d factor with
diagonal entry f_d(x). This is the Jordan-Wigner construction: the
Z_1 ... Z_{d-1} string forces
  gamma_d^* = gamma_d,  gamma_d^2 = I,  gamma_d gamma_e = -gamma_e
  gamma_d (d != e).
Consequently D is self-adjoint, D^2 = I, and tr D = 0 (the zero diagonal
of each J_d gives tr gamma_d = 0).

Exercise: Full labels and level spaces. What are I and E_k?
Answer. The set of full labels is
  I = (X_1 x X_2 x ... x X_N) x (Y_0 x Y_1 x ... x Y_L).
Coordinates of i in I are written x_k(i) for k = 1, ..., N and y_d(i) for
d = 0, ..., L. For 0 <= k <= N the level-k coordinate space is
  E_k = (tensor over j <= k of C^{m_j}) tensor
        (tensor over j > k of C^{X_j}) tensor
        (tensor over d = 0..L of C^{Y_d}).
So at level k the first k X-factors have already been "compressed" by
the frames a_{k,x} (they are live in C^{m_k}), while the later X-factors
are still literal coordinates. Y_factors are always literal coordinates.
Warning: "E_k" here denotes a level-k coordinate space. It is NOT the
flag value E of Section 2 and NOT the Schur complement of Lemma
(Priority).

Exercise: Level metrics G_k. What is G_k?
Answer. On E_k set
  G_k = I + h sum_{k < d <= L} gamma_d,   h = 1/(2 sqrt L).
Each gamma_d is an involution; distinct ones anticommute, so
(sum_{k<d<=L} gamma_d)^2 = (L - k) I and that sum has norm sqrt(L - k).
Therefore
  1/2 I <= G_k <= 3/2 I,
and the two ends are G_0 = I + (1/2) D and G_L = G_N = I. Each G_k is
positive, self-adjoint and invertible; every metric in sight lies
between 1/2 I and 3/2 I, which is why all operator norms below are
comparable to a constant factor.

Exercise: How does G_k interact with coordinate projections?
Answer. Two features are used constantly. (i) G_k is the identity on
each compressed factor C^{m_j} with j <= k. (ii) G_k commutes with each
coordinate projection in X_j for j > k and in Y_d for d <= k; this is
because every surviving term in G_k involves only diagonal parity
operators on those Y_d factors.

Exercise: Label vectors. What is v_i^{(k)} and what is its G_k-norm?
Answer. Let v_i^{(k)} in E_k be the vector that uses a_{j,x_j(i)} in
factors j <= k of the X-type, the standard vector e_{x_j(i)} in factors
j > k of the X-type, and e_{y_d(i)} in every Y_d factor. Its G_k-norm
is one: every additional term h gamma_d in G_k has zero diagonal in
some Y_d factor (because J_d has zero diagonal), so it annihilates
v_i^{(k)} when paired across that factor. So the label vectors are unit
vectors in the metric G_k.

Exercise: The big Hilbert space H. What is it?
Answer. Take the Hilbert direct sum
  H = direct sum over k = 0, ..., N of direct sum over w in G of (E_k, G_k).
Here (E_k, G_k) means E_k with inner product <u,v>_{G_k} = <u, G_k v>.
Since G is countable and each E_k is a finite tensor product, H is
separable. Left translation of the location w defines a genuine unitary
representation U: G -> U(H); no translation changes a label or a level.
Write H_k for the sub-sum at level k, so H splits as an orthogonal sum of
H_0, ..., H_N.

Exercise: Adjusted frames. What is a-tilde?
Answer. Fix a set C of at most three configurations and p in C. For a
fixed arrival v and y in Y_{k-1}, let
  S = { x in X_k : (v s_k(x,y)^{-1}, k, x, y) is switchable for C }.
By property (F3) of the flags, |S| <= |C| beta |X_k| <= 3 beta |X_k|.
Let F_S: C^S -> C^{m_k} have columns a_{k,x} for x in S. Replace these
columns by the symmetric orthonormalization
  F-tilde_S = F_S (F_S^* F_S)^{-1/2},   a-tilde_{k,v,y,x} = F-tilde_S e_x.
Then F-tilde_S^* F-tilde_S = I and || F-tilde_S - F_S || <= C eta. For
S = empty there are no columns and nothing changes.

Exercise: Left and right subspaces of a switchable edge. What are they?
Answer. Fix C (at most three configurations), k, w, x, y, and let
v = w s_k(x,y). The left subspace is the coordinate sector at (k-1, w)
in which X_k = x and Y_{k-1} = y; all other coordinates are unrestricted.
The right subspace at (k, v) has Y_{k-1} = y and the X_k-line spanned by
the adjusted vector a-tilde_{k,v,y,x}; all other coordinates are
unrestricted. For distinct edges (distinct (x,y) or distinct w, v) the
left subspaces are mutually orthogonal; the same is true of the right
subspaces. Orthogonality on the right uses a-tilde^* a-tilde = I (the
adjusted frame is exactly orthonormal) and the fact that G_k is the
identity on the compressed X_k factor.

Exercise: Edge metrics A_{x,y} and B_y. Where do they come from?
Answer. Left and right subspaces of one edge have the same remaining
coordinates (everything except the fixed X_k and Y_{k-1}); we can
compare them using inner products that only differ in the gamma-strings.
For k <= L, denote by A_{x,y} the restriction of G_{k-1} to the left
subspace and by B_y the restriction of G_k to the right subspace. Because
G_k differs from G_{k-1} precisely by the term h gamma_k, and gamma_k
restricted to Y_{k-1} = y is
  Gamma_{x,y} = f_k(x) Z_1 ... Z_{k-1} J_k |_{Y_{k-1} = y}, ||Gamma|| = 1,
we get
  A_{x,y} = B_y + h Gamma_{x,y};   B_y is independent of x.
Earlier compressed X-factors carry identity throughout. At k = N both
metrics are the identity, so A_{x,y} = B_y = I.

Exercise: Priority projection and priority isometry. What is the point?
Answer. We need an isometry S_e^C: (residual, B_y) -> (residual,
A_{x,y}) that is nearly the identity on the subspace used by the *next*
layer. That is exactly what Lemma (Priority) provides, provided P
compresses Gamma_{x,y} to be small. For arrival v and z in X_{k+1}, set
  R = R_{k,v,z}^C = { t in Y_k : q_{k+1}(v; z, t) = F for some q in C }.
By (F2), |R| <= 3 beta |Y_k|. Let P = P_{k,v}^C be the projection onto
the sector X_{k+1} = z with Y_k in R, times identity on all remaining
factors. Then P commutes with B_y, and by Lemma (Sparse Restrictions)
applied block by block (each block is a compression J_k[R,R] with
|R| <= 3 beta |Y_k|, and direct sums don't increase the bound),
  || P Gamma_{x,y} P || <= eta.
Lemma (Priority) then supplies S_e^C with
  || S_e^C - I || <= C h,   || (S_e^C - I) P || <= C h eta.
At k = N put S_e^C = I. The fixed isometry
  C_{x,y} = A_{x,y}^{-1/2} B_y^{1/2}
is used for the opposite direction: it does not depend on C, p, or P.

Exercise: Exchange and layer. What is M_e^C, and what is M_{p,k}^C?
Answer. On the left oplus right subspace of a switchable edge e, in the
order (left, right), define
  M_e^C = [[0, C_{x,y}], [(S_e^C)^{-1}, 0]].
Both off-diagonal entries are isometries onto the indicated endpoint,
so M_e^C is unitary. It is in general not an involution, which is
deliberate: its inverse takes a vector from the right to the left using
S_e^C, while its forward right-to-left block is C_{x,y}.
The stage-k layer M_{p,k}^C applies M_e^C on every switchable edge
flagged F in p, and is the identity on the orthogonal complement of
their endpoint subspaces. The orthogonality proven above makes this a
unitary, even when infinitely many locations are involved (an orthogonal
direct sum of unitaries).

Exercise: Circuits. What are W_p^C and V_{qp}^C?
Answer. Layers are applied in the order 1, 2, ..., N:
  W_p^C = M_{p,N}^C ... M_{p,1}^C,
  V_{qp}^C = W_q^C (W_p^C)^{-1}.
Every recipe uses only coordinate projections and positive square roots,
and depends on the group locations only through the flags. Therefore
  U(g) W_p^C U(g)^{-1} = W_{gp}^{g C},
  U(g) V_{qp}^C U(g)^{-1} = V_{gq, gp}^{g C}.
This covariance is exactly what lets the pairwise comparisons V_{qp} be
turned into an almost representation.

Exercise: Comparison of two versus three configurations. State the
proposition.
Answer. (Proposition (Comparison).) There are numerical constants C and
h_0 > 0 such that, for the construction of the previous section with
h <= h_0 and 0 < eta <= 1/4,
  || V_{qp}^{{p,q}} - V_{qp}^{{p,q,r}} || <= C h + C N eta + C N h eta,
for every three configurations p, q, r. The constants do not depend on
the alphabet sizes or on the configurations themselves.
Read this as follows: adding a third configuration r changes the pair
comparison V_{qp} by an amount that tends to 0 as h -> 0 and eta -> 0,
uniformly in the group and in the alphabets. This is what makes the
almost representation work: we can freely change the pair {p,q} into
{p,q,r} inside a product without accumulating large errors.

Exercise: Proof of Comparison, part (a). Put both sides in the same
arrival frames.
Proof. Write C_2 = {p, q}, C_3 = {p, q, r}. At every arrival sector
S_2 = S_{k,v,y}^{C_2} is contained in S_3 = S_{k,v,y}^{C_3}, so
  || F-tilde_{S_2} - F-tilde_{S_3}|_{C^{S_2}} || <= C eta,
by the closeness of nested orthonormalizations. Replace for the moment
the pair's arrival vectors by the corresponding columns of
F-tilde_{S_3}, leaving its edges and priorities unchanged; call the new
layers bar-M_{p,k} and the new circuits bar-W_p (and bar-W_q similarly).
Why is the operator norm cost bounded?
For one layer let L, R be the isometric embeddings of the orthogonal
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 - L L^* - R R^* + L C_0 R^* + R T L^*.
When the arrival frame changes only R changes. Its domain uses the
metric B_y on each column, independent of the compressed coordinate
X_k; so the operator-norm change in R is at most C eta, tensored with
the residual coordinates and summed orthogonally over (v, y). The
formula then bounds the layer change by 4 || R - R' ||. All transfers
have norm one in their metrics. Telescoping a product of unitaries
gives
  || W_p^{C_2} - bar-W_p || <= C N eta,
and the same bound for q. So step (a) costs C N eta.

Exercise: Proof of Comparison, part (b). Why do the common exchanges
cancel exactly?
Proof. Among the edges switchable for C_3 but not for C_2, those flagged
E in both p and q are unused by both circuits. The others are flagged F
in both p and q 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 used by, say, p, it is E in p; property (F1) then says no outgoing
edge at its arrival is F in p in the next stage, so no common exchange
can be F in p there. The supports at the shared level lie at disjoint
group locations, and the adjustment of the X vectors changes no
location, so orthogonality is preserved.
Within a layer all exchanges commute (orthogonal supports). So move all
common exchanges to the beginning of each circuit, retaining their
order. Only finitely many layers, and within a layer the common
exchanges form an orthogonal direct sum, so no infinite product is
needed. Get
  W_p^{C_3} = hat-W_p C_com,
  W_q^{C_3} = hat-W_q C_com,
  V_{qp}^{C_3} = hat-W_q hat-W_p^{-1}.
Here hat-W_p = hat-M_{p,N} ... hat-M_{p,1} uses the pair-switchable
edges of p with the triple's frames and priorities. Now hat-M_{p,k}
and bar-M_{p,k} have the same edges, subspaces and fixed reverse
transfers; only their priority isometries differ.

Exercise: Proof of Comparison, part (c). How are the priority changes
moved to separate levels?
Proof. Compare hat-W_p with bar-W_p (the argument for q is identical).
For each active edge the smaller priority projection sits inside the
larger one, and from the definition of M_e^C,
  [[0, C], [S_3^{-1}, 0]] [[0, S_2], [C^{-1}, 0]] = [[I, 0], [0, S_3^{-1} S_2]].
Consequently
  hat-M_{p,k} = K_k bar-M_{p,k},   K_k = I on H_k^perp,
  || K_k - I || <= C h,
by Lemma (Priority) and the uniform metric bounds (between 1/2 I and
3/2 I).
For k < N, let Q_{k+1} be the orthogonal projection onto the departure
subspace used by bar-M_{p,k+1} in H_k. Claim:
  || (K_k - I) Q_{k+1} || <= C h eta.
At a fixed location Q_{k+1} selects the next coordinates (X_{k+1}, Y_k),
while a current arrival subspace selects Y_{k-1} and a line in the
compressed X_k factor; these projections commute (they constrain
different coordinates, and G_k preserves the coordinate sectors). On
their intersection the smaller priority contains every next departure,
by the definition of R_{k,v,z}^C, and Lemma (Priority) bounds
(S_e^{C_3})^{-1} S_e^{C_2} - I there by C h eta. Off the union of the
current arrival subspaces K_k = I. Orthogonality finishes the claim;
no factor counting edges or labels appears. Set Q_{N+1} = 0.
Apply Lemma (Truncate) on H_k, with h_0 small enough. Get a unitary
K-tilde_k on H_k (extended by identity off H_k) with
  K-tilde_k Q_{k+1} = Q_{k+1},
  || K_k - K-tilde_k || <= C h eta,
  || K-tilde_k - I || <= C h.
K-tilde_k commutes with bar-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 K-tilde_k is the identity on both. K-tilde_k also commutes with all
later layers, which act on other levels. (The figure in the paper runs
as follows: at level H_k, K-tilde_k acts only at level k and fixes
Q_{k+1} H_k, so it commutes past the next layer; all subsequent layers
have support disjoint from H_k.) Substitute hat-M_{p,k} = K_k
bar-M_{p,k} into the product for hat-W_p. Replacing each K_k by
K-tilde_k costs at most C N h eta, by telescoping products of unitaries.
Move each K-tilde_k past the subsequent layers: the corrected unitaries
commute with one another because they act on distinct levels. So
  || hat-W_p - (K-tilde_N ... K-tilde_1) bar-W_p || <= C N h eta,
  || K-tilde_N ... K-tilde_1 - I || = max_k || K-tilde_k - I || <= C h.
Together with step (a), this gives
  || hat-W_p - W_p^{C_2} || <= C h + C N eta + C N h eta,
and the same for q. Plug the two factors into V_{qp}, use
  V_{qp}^{C_3} = hat-W_q hat-W_p^{-1},
and telescope again; that proves Proposition (Comparison).

Exercise: The almost representation mu. What is mu, and how good is it?
Answer. Fix a configuration b and set
  mu(g) = V_{b, gb}^{{b,gb}} U(g).
For g = e there is only one configuration and no switchable edge, so
mu(e) = I. Equivariance gives
  mu(g) mu(t) = V_{b,gb}^{{b,gb}} V_{gb,gtb}^{{gb,gtb}} U(gt).
Replace each comparison here, and the one appearing in mu(gt), by the
comparison computed in the three-configuration set {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 (Comparison) give
  defect(mu) <= C h + C N eta + C N h eta.
So mu is an almost representation whose defect we can drive to 0 by
first making h small and then making eta small. This is half of the
theorem: we have an almost representation with arbitrarily small
defect.

Exercise: Transport along most paths. State the lemma.
Answer. (Lemma (Transport).) For all but a proportion 2 N beta of the
labels i in I,
  || mu(s_i) u_i - r_i || <= C N eta + C N h eta.
Here u_i is the label vector v_i^{(N)} at location e and level N, r_i is
v_i^{(0)} at location e and level 0, and s_i = s_1(i) s_2(i) ... s_N(i).
So for almost every label, the almost representation mu, applied to the
full product s_i, transports u_i back to r_i up to a small error.

Exercise: Proof of Transport. Why do "most" paths work?
Proof. Put the uniform product measure on I. Let t_0 = e and
  t_k = s_1(i) s_2(i) ... s_k(i),  s_i = t_N.
Along the forward path t_0, ..., t_N the departure t_{k-1} depends only
on coordinate pairs (X_j, Y_{j-1}) with j < k. Conditional on those pairs
and on X_k, the coordinate Y_{k-1} is still uniform; by (F2), the
probability of an F step is at most beta. By the union bound, every
forward step is E with probability at least 1 - N beta.
Now run the path with the same steps but terminal point e ("backward").
Its stage-k arrival position is
  a_k = s_N^{-1} s_{N-1}^{-1} ... s_{k+1}^{-1} = s_i^{-1} t_k,
so a_{k-1} s_k = a_k, and a_k depends only on the later coordinate pairs.
Conditional on the later pairs and on Y_{k-1}, the arrival bound (F3)
makes the probability of an E step at most beta. By the union bound,
every backward step is F with probability at least 1 - N beta.
Let I_good be the intersection of these two events. Its complement has
proportion at most 2 N beta. (No independence of the two events is
used.) For i in I_good, put p = s_i b. Then the forward path t_0, ...,
t_N is entirely E for b and entirely F for the translate p; so all its
edges are switchable for {b, p}.
Let z_k = v_i^{(k)} at location t_k. So 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 a-tilde changes z_k by at most C eta (frame adjustment plus the
metric bound between 1/2 and 3/2 I). That adjusted vector lives in the
active right subspace of the path's edge, and the inverse layer takes it
to the left using (S_e^{{b,p}}). For k < N the resulting residual
coordinates lie in the priority subspace (the next step (t_k, x_{k+1},
y_k) is F in p), and the edge transfer estimate moves them by at most
C h eta. At k = N the transfer is the identity. Hence
  || (M_{p,k}^{{b,p}})^{-1} z_k - z_{k-1} || <= C eta + C h eta.
Telescoping the inverse circuit from N down to 1 gives
  || (W_p^{{b,p}})^{-1} U(s_i) u_i - r_i || <= C N eta + C N h eta.
All actual layers are unitary, so previous 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 (E-flagged) step, and later layers do
not act on level zero. Combined with mu(g) = W_p W_b^{-1} U(g), this
gives the claimed bound.

Exercise: The quadratic-form witness. State the lemma.
Answer. (Lemma (Quadratic Form Witness).) Let rho: G -> U(H) be a
genuine unitary representation. Define unit vectors in C^I tensor H by
  psi = |I|^{-1/2} sum_{i in I} e_i tensor rho(s_i) u_i,
  r = |I|^{-1/2} sum_{i in I} e_i tensor r_i.
Then
  <psi, (D tensor I) psi> = 0,   <r, (D tensor I) r> = 1/2.
In particular ||r - psi|| >= 1/4.
So any genuine representation produces a vector psi on which the
self-adjoint operator D tensor I takes value 0, while the fixed vector r
gives value 1/2; the two vectors cannot be close.

Exercise: Proof of the Witness. Why are the two values 0 and 1/2?
Proof. For any labels i, j, unitarity and multiplicativity give
  <rho(s_i) u_i, rho(s_j) u_j> = <u_i, rho(s_i^{-1} s_j) u_j>.
Fix d in {1, ..., L}. A nonzero coefficient (gamma_d)_{ij} of gamma_d
pairs labels that agree on all coordinates except possibly Y_d: the
Z_1 ... Z_{d-1} string and f_d(X_d) are diagonal in X and in the earlier
Y's, and J_d only acts on Y_d. From agreement through stage d the group
products have a common prefix P through stage d:
  s_i = P Q_i, s_j = P Q_j, s_i^{-1} s_j = Q_i^{-1} Q_j,
and Q_i, Q_j depend only on the later coordinates X_{d+1}, ..., X_N, not
on X_d. Fix all coordinates other than X_d. Then there are linear
isometric embeddings E_i, E_j: C^{m_d} -> H, also independent of X_d,
with u_i = E_i a_{d,x_d} and u_j = E_j a_{d,x_d}. (The metric at level N
is Euclidean, since G_N = I.) The X_d-dependence of (gamma_d)_{ij} is
exactly the factor f_d(x_d). The sum over X_d therefore equals a fixed
scalar multiple of
  sum_{x in X_d} f_d(x) <a_{d,x}, E_i^* rho(Q_i^{-1} Q_j) E_j a_{d,x}>
  = tr( E_i^* rho(Q_i^{-1} Q_j) E_j  sum_x f_d(x) a_{d,x} a_{d,x}^* )
  = 0
by the signed frame cancellation sum_x f_d(x) a_{d,x} a_{d,x}^* = 0.
Summing over the remaining coordinates proves
<psi, (gamma_d tensor I) psi> = 0 for each d, hence <psi, (D tensor I)
psi> = 0. The Gram matrix of the r_i (which are the standard label
vectors at level zero) is G_0, and both G_0 and D are real symmetric.
  <r, (D tensor I) r> = tr(D G_0)/|I| = tr(D + (1/2) D^2)/|I| = 1/2,
because tr D = 0 and D^2 = I. Since ||D|| = 1 and both vectors have
norm one,
  1/2 = |<r, (D tensor I) r> - <psi, (D tensor I) psi>|
      <= ||r - psi|| (||r|| + ||psi||) = 2 ||r - psi||,
so ||r - psi|| >= 1/4.

Exercise: Final distance. How close can r and psi be?
Answer. Suppose a genuine rho is uniformly within eps of mu. On I_good
the transport error is at most C N eta + C N h eta; on the complement
the error is at most 2 (both vectors unit). By the triangle inequality
in the orthogonal label sum,
  ||r - psi|| <= eps + C N eta + C N h eta + 2 sqrt(2 N beta).
All constants here and in the defect bound are numerical.

Exercise: Parameter choice and the main theorem. How does the proof
finish?
Proof. The amenable implication is Kazhdan's theorem. Suppose G is
nonamenable and fix any delta > 0.
1. Choose L large enough that h = 1/(2 sqrt L) satisfies every smallness
   condition above and C h < delta/2 in the defect bound.
2. With N = L + 1 now fixed, choose 0 < eta < 1/4 so small that
   C N eta + C N h eta < min{delta/2, 1/20} for the constants in both
   the defect bound and the final distance estimate.
3. Choose 0 < beta < min{beta_0(eta), 1/(3200 N)}, with beta_0 from
   Lemma (Sparse Restrictions). Then 2 sqrt(2 N beta) < 1/20, and
   enlarge the alphabets to the sizes required by Lemma (Sparse).
None of the estimates worsens when the alphabets are enlarged.
The resulting map mu has defect < delta. If a genuine representation rho
were uniformly within 1/10 of mu, the final distance estimate would give
  ||r - psi|| < 1/10 + 1/20 + 1/20 = 1/5,
contradicting the witness bound ||r - psi|| >= 1/4. Therefore
  sup over g in G of || mu(g) - rho(g) || > 1/10
for every unitary representation rho of G on H. As delta > 0 was
arbitrary, G is not strongly Ulam stable.

Exercise: Summary. What is the conceptual content of the proof?
Answer. Almost representations correspond to "almost actions" of G by
unitaries. Amenability lets one average the almost action over the
group and repair it. When G has a boundary, however, the boundary lets
one build finite lists of "steps" whose E/F flags have opposite
counting properties at the two ends of every path; these flags drive
circuits that drift the inner product along the levels. A genuine
representation would have to undo all that drift, but a specific
self-adjoint operator (built from two orthonormal bases carrying
opposite signs) takes a fixed nonzero value on the initial vector and
value 0 on anything transported by a genuine representation. The 1/4 gap
between these two values persists no matter how small the defect of mu
is. So strong Ulam stability forces the absence of a boundary, hence
amenability.

Bibliography.
Kazhdan, D. 1982. On epsilon-representations. Israel J. Math. 43,
  315-323. https://doi.org/10.1007/BF02761236
Burger, M., Ozawa, N., Thom, A. 2013. On Ulam stability. Israel J. Math.
  193, 109-129. https://doi.org/10.1007/s11856-012-0050-z
Alpeev, A. Lamplighters over non-amenable groups are not strongly Ulam
  stable. https://arxiv.org/abs/2009.11738
Furstenberg, H. 1973. Boundary theory and stochastic processes on
  homogeneous spaces. Proc. Sympos. Pure Math. 26, Amer. Math. Soc.,
  193-229.
Kalantar, M., Kennedy, M. 2017. Boundaries of reduced C*-algebras of
  discrete groups. J. reine angew. Math. 727, 247-267.
  https://doi.org/10.1515/crelle-2014-0111
Glebsky, L., Lubotzky, A., Monod, N., Rangarajan, B. 2023. Asymptotic
  cohomology and uniform stability for lattices in semisimple groups.
  https://arxiv.org/abs/2301.00476
Fournier-Facio, F., Rangarajan, B. 2024. Ulam stability of lamplighters
  and Thompson groups. Math. Ann. 389, 2469-2497.
  https://doi.org/10.1007/s00208-023-02708-5
Jordan, P., Wigner, E. 1928. Ueber das Paulische Aequivalenzverbot.
  Z. Phys. 47, 631-651. https://doi.org/10.1007/BF01331938
Bravyi, S., Kitaev, A. 2002. Fermionic quantum computation. Ann. Physics
  298, 210-226. https://doi.org/10.1006/aphy.2002.6254
Lyubarskii, Y., Vershynin, R. 2010. Uncertainty principles and vector
  quantization. IEEE Trans. Inform. Theory 56, 3491-3501.
  https://doi.org/10.1109/TIT.2010.2048458