A projection in a C*-algebra is an element p with p = p* = p^2.
For a discrete group G, the reduced group C*-algebra C_r*(G) is the
norm closure of the left regular representation on l^2(G), and its
canonical trace is tau(x) = <x delta_1, delta_1>. The
Kadison--Kaplansky projection conjecture asserts that when G is
torsion-free the only projections in C_r*(G) are 0 and 1. Since
tau lies in [0,1] on projections and tau(p) = 0 only for p = 0,
the conjecture says tau(p) is always 0 or 1. It is usually stated
in the equivalent matrix form: for every N and every projection p
in M_N(C_r*(G)), the unnormalized trace tau_{G,N}(p) is an integer.
The conjecture is false. A finitely generated torsion-free group
is constructed below whose reduced group C*-algebra contains a
projection of trace strictly between 0 and 1/2.
Four tools carry the construction: an expander tower with folded
labels, a nilpotent deck group whose twisted group algebra holds
explicit small-trace projections, a van Kampen argument embedding
the components of a voltage cover into a Cayley graph, and a
finite-rank comparison in the regular representation that turns a
model band into a genuine projection. Groups come first.
A group is a set G with an operation "multiply two elements and
get a third", written gh for g times h, satisfying:
(i) associativity: (gh)k = g(hk) for all g,h,k in G;
(ii) an identity element 1 with 1g = g1 = g for all g;
(iii) every g has an inverse g^-1 with gg^-1 = g^-1g = 1.
Examples:
the integers Z under addition (identity 0)
the nonzero reals under multiplication (identity 1)
invertible n-by-n matrices under usual matrix multiplication
rotations of a regular polygon
Two properties are crucial below.
Finitely generated. There is a finite list S = {s_1,...,s_k} of
elements such that every element of G is a finite product of s_i
and their inverses. For the integers, S = {1} suffices.
Torsion-free. If g^n = 1 for some n >= 1, then g = 1. No
element of the group, other than the identity, is "finite order".
The integers are torsion-free. The group of rotations of a
regular polygon is not: a rotation by 1/n of a full turn has
order n.
The constructed group is finitely generated and
torsion-free, exactly the kind of group the conjecture is about.
Fix a group G. Consider all complex-valued functions on G that
decay fast enough:
l^2(G) = { a : G -> C | sum over g of |a(g)|^2 < infinity }
This is a complex Hilbert space with inner product
<a,b> = sum over g of conj(a(g)) b(g).
For each g in G, let delta_g in l^2(G) be the function that is 1
at g and 0 elsewhere. Then {delta_g : g in G} is an
orthonormal basis of l^2(G).
Each element h of G acts on l^2(G) by left translation:
lambda(h) delta_g = delta{hg}.
The map lambda(h) is a unitary operator, and the map h -> lambda(h)
is a group homomorphism: the group G now sits inside the unitary
group of the Hilbert space.
The group algebra C[G] consists of formal finite sums
x = sum over g of c(g) g, only finitely many c(g) nonzero.
It acts on l^2(G) by the same left-translation formula extended
linearly:
x delta_g = sum over h of c(h) delta{hg}.
The reduced group C*-algebra C_r*(G) is the closure of this space
of operators in the operator norm:
C_r*(G) = completion of { x acting on l^2(G) : x in C[G] }.
Concretely: an element of C_r*(G) is a possibly infinite "sum"
sum c(g) lambda(g) that is a limit, in operator norm, of finite
sums. It is a C*-algebra: an algebra of operators closed under
addition, multiplication, taking adjoints, and taking the norm-
limit.
Why the reduced one? Because l^2(G) gives the "smallest" natural
completion. Every group admits a universal completion too (the
full group C*-algebra), but the reduced one is where the trace
below lives and where the conjecture is usually stated.
Every element x of C_r*(G) has a well-defined "coefficient of
the identity", extracted by pairing against the identity basis
vector:
tau(x) = < x delta_1, delta_1 >.
In the group algebra this reads off c(1) from the formula above.
Properties:
linear over C
tau(xy) = tau(yx) trace property
tau(x* x) >= 0 positivity, and =0 iff x = 0
tau(1) = 1
In words: tau is a "faithful tracial state". A linear functional
that behaves like the identity coefficient in the group algebra.
A fact used twice:
If p is a projection in C_r*(G), then tau(p) is a real number
in [0,1]. And tau(p) = 0 forces p = 0.
Proof: tau(p) = <p delta_1, delta_1> and p = p* p, so
tau(p) = <p delta_1, p delta_1> = ||p delta_1||^2 >= 0. Since
||p|| <= 1, it is at most ||delta_1||^2 = 1. Faithfulness of tau
gives the second part.
A projection is an element p of a C*-algebra with
p* = p and p^2 = p.
Geometrically, p is the orthogonal projection onto its range
subspace pH. The projections 0 and 1 are the trivial ones.
In the group-algebra setting, projections can be invisible to the
group elements themselves: they are infinite operator sums, not
finite combinations. The larger von Neumann closure L(G) is
more forgiving; the smaller C_r*(G) is more rigid.
The conjecture below asks: is C_r*(G) so rigid that for
torsion-free G it only contains 0 and 1.
If A is a C*-algebra and N >= 1 is an integer, then M_N(A), the
algebra of N-by-N matrices with entries in A, is again a
C*-algebra (there is a natural norm). The trace extends by
summing the diagonal:
tau_A,N( (a_ij) ) = sum over j of tau(a_jj),
with NO division by N. This "unnormalized matrix trace" is the
one used throughout. When A = C_r*(G) and a projection p in M_N(A)
is written out, tau_{G,N}(p) is a nonnegative real number; it can
exceed 1 because there are N diagonal entries each at most 1.
The notation tr_id denotes this trace in a large Hilbert
space, "identity trace". It is the same idea, more carefully
stated: pick an orthonormal basis {k_a} of the auxiliary space,
and define Tr(Z) = sum over a of < Z delta_1 (x) k_a, delta_1 (x) k_a >.
It is the honest (non-normalized) sum of diagonal entries, and it
stays finite for the operators in question.
Irving Kaplansky asked, and Richard Kadison recorded in 1955, the
following question.
THE KADISON-KAPLANSKY PROJECTION CONJECTURE.
Let G be a torsion-free discrete group. Then the only
projections in C_r*(G) are 0 and 1.
Equivalently: if p in C_r*(G) satisfies p = p* = p^2, then p = 0
or p = 1. Since tau(p) lies in [0,1] and tau(p) = 0 only for
p = 0, the conjecture is closely tied to a trace quantisation
statement: for a projection p, tau(p) can only be 0 or 1.
There is also a matrix version, which says: for every N and every
projection p in M_N(C_r*(G)), the trace tau_{G,N}(p) is an
integer. (Integer, not merely 0 or 1, because the unnormalized
matrix trace can be any integer in {0,1,...,N}.
The scalar and matrix versions are equivalent, essentially
because an N-by-N matrix projection can be "cut down" by a
full matrix unit to a scalar projection of the same trace in a
slightly larger algebra. That trick (or a variant) is Step 1.
If G has an element g of finite order k, then
p = (1/k) ( 1 + g + g^2 + ... + g^(k-1) )
is a projection in C[G] itself (so certainly in C_r*(G)). Its
trace is 1/k, and it is neither 0 nor 1 whenever k >= 2. So the
conjecture cannot be true for groups with torsion. Torsion-free
is a necessary hypothesis.
Here is the difficulty in one sentence: an element of C_r*(G) is
an infinite operator sum, and it is not obvious, for any
particular infinite sum, whether it is a projection.
Two routes have been tried:
ROUTE 1: K-THEORY AND ASSEMBLY.
The algebraic K_0 group K_0(C_r*(G)) is generated by traces of
projections, modulo relations. If the trace map
tau : K_0(C_r*(G)) -> R
takes only integer values, then any projection has an integer
trace, hence trace 0 or 1, hence is 0 or 1 by faithfulness. So
the conjecture follows from trace-integrality.
Trace-integrality can be attacked through the Baum-Connes
assembly map
mu : K_*^{top}(G) -> K_*(C_r^*(G))
which is a homomorphism from a "topological" (geometry of the
group) K-theory to the operator K-theory. A theorem of Lueck
(Inventiones 149 (2002), 123-152), extended
by Baum-Guentner-Willett (see the local survey
bgw-2016-exactness-kadison-kaplansky.pdf), says: for a
torsion-free group, the canonical trace tau is integral on the
IMAGE of the reduced assembly map. So:
if the assembly map is surjective, the conjecture holds.
Surjectivity (Baum-Connes) is known for sizeable classes:
- countable amenable groups: Higson-Kasparov,
Invent. Math. 144 (2001), 23-74
- hyperbolic groups: Mineyev-Yu (2002, without coefficients;
Lafforgue 2012, with arbitrary coefficients)
- many more: groups acting properly and isometrically on
Hilbert space, on trees, etc.
So the conjecture is established for large classes of groups.
ROUTE 2: THE VON NEUMANN ALGEBRA.
In the larger von Neumann algebra L(G) = weak closure of C_r*(G),
there is a complete dimension theory: Murray and von Neumann
showed that projections have traces that can be any real number
in [0,1]. But C_r*(G) is much smaller than L(G), and its
projections are rare. Known examples inside L(G), such as
Austin's irrational-kernel-dimension operators (2013), do not
immediately give projections inside the smaller C_r*(G).
The paper does NOT try to break the assembly map. It builds an
explicit projection in a specific group's reduced C*-algebra and
computes its trace to be a specific non-integer (between 0 and
1/2). That obviously violates the conjecture, so no assembly
argument can be true for this group: the group must be outside
all known covering classes, and its assembly map must not be
surjective on K_0.
For the same group, a the same methods show that the complex
group ring C[G_proj] has no scalar idempotents other than 0 and
1. So the projection e lies in the C*-completion but
NOT in the algebraic group ring; the gap between the two is where
the answer hides.
THEOREM.
There exist a finitely generated, torsion-free discrete group
G_proj and a projection e in C_r*(G_proj) such that
0 < tau_{G_proj}(e) < 1/2.
In particular e is neither 0 nor 1, and the Kadison-Kaplansky
projection conjecture is false.
That is the entire result. Every one of the remaining pages is
about producing that pair (G_proj, e).
The proof is broken into six steps. Each step gets a Part below.
The steps are logically ordered by dependency, not by their historical order.
STEP 1. Scalar reduction. Suppose a
torsion-free finitely generated group Gamma and a MATRIX
projection p_0 in M_N(C_r*(Gamma)) with
0 < tau_{Gamma,N}(p_0) < 1/2,
then G_proj = Gamma * F_N and a free-product compression formula
give a SCALAR projection e in C_r*(G_proj) with the same
trace. So Step 1 reduces the theorem to producing p_0.
STEP 2. The expander tower. Build an infinite bipartite tower
of finite layers A_i and B_i (i in Z), of growing sizes, with
uniformly expanding incidence operators between adjacent layers.
Two variants Y^0 and Y^# exist, one tuned to expansion, the other
to unique recovery of long paths from their labels; after
deleting a proportionally tiny set of vertices, they agree on
one common graph Y, which has all the good properties at once.
STEP 3. The deck group and the small trace. Build a torsion-
free nilpotent group F whose arithmetic is rich enough to (a)
detect short closed walks, and (b) carry small-trace projections
in its twisted group algebras. The projections come from a
central Fourier transform: parameter t on the circle, a
projection p(t) with trace roughly t^n (delta - t)^n, so that
t -> 0 or t -> delta shrinks the trace.
STEP 4. Realization: choosing voltages and matrices on Y. Put
F-valued voltages on the edges of Y and simultaneously put finite
complex matrices W_e on the edges. Two properties must hold at
once:
(a) the voltage cover P of Y has no short nonbacktracking
closed walks ("girth" hypothesis);
(b) the resulting regular-representation operator T_P on the
cover is within any fixed eta of the model operator
Pi O Pi built out of the tower and the projections p(t).
Both properties are proved by finite probabilistic tests.
STEP 5. The geometry and the group G. Given a cover P
satisfying the girth hypothesis, define
Gamma = < S | label words of all closed walks in P >,
a finitely generated group presented graphically. Show that
every component of P embeds in the Cayley graph of Gamma
(injectivity), that overlaps between different copies are tiny
tree balls, that the leftover Cayley edges form a forest, and
that Gamma is torsion-free.
STEP 6. Transfer to the Cayley graph and trace bound. A
compression + perturbation argument upgrades the approximation
in Step 4 to a separated band in the actual operator T on the
Cayley graph of Gamma. The spectral projection p_0 of that band
sits in M_N(C_r*(Gamma)), is nonzero, and its unnormalized trace
is bounded by a small weighted sum, which tends to zero.
Then concatenate: Step 2 + Step 3 + Step 4 deliver the cover P;
Step 5 turns P into Gamma; Step 6 gives p_0; Step 1 turns p_0
into e over G_proj = Gamma * F_N. Done.
A note on DEPENDENCY ORDER. In the actual writing, one fixes
constants in the order: geometry constants C_* and C_bullet;
the nilpotence data m, E_0, A_*, kappa; the operator accuracy
eta and finite lists; two finite-moment constants C_1, C_2;
and finally ell large enough that all the "for sufficiently
large ell" statements hold. Nothing circular happens; each
part fixes its constants before the next begins. A parameter
ledger recorded with the tower construction spells this out.
Target (REVISED). Produce a finitely generated, torsion-free
Gamma and a projection p_0 in M_N(C_r*(Gamma)) for some integer
N, with 0 < tau_{Gamma,N}(p_0) < 1/2.
Such a construction converts the target into the theorem.
Without it the target is exactly the problem.
Given groups Lambda and H, the free product Lambda * H is the
group of finite alternating products l_1 h_1 l_2 h_2 ... with
each l_i in Lambda and h_i in H, reduced by cancelling adjacent
pairs (l, l^-1) or (h, h^-1). Intuition: Lambda and H placed
side by side, sharing only the identity, and any word in them
gets freely reduced by cancelling adjacent inverses.
The free group F_N on N letters t_1,...,t_N is the free product
of N copies of Z. Every element of K = Lambda * F_N has a
UNIQUE reduced form
gamma v, gamma in Lambda, v a reduced F_N-word.
The set R consists of the identity of K, together with all
reduced NORMAL WORDS of K whose FIRST factor lies in F_N. Every
element k of K has a UNIQUE expression k = gamma v with gamma in
Lambda and v in R. Thus R is a transversal for LEFT Lambda-
orbits in K. (This is the free-product normal form; the
first-letter condition is what makes the expression unique.)
LEMMA. If Lambda <= Gamma is a subgroup, then C_r*(Lambda) sits
inside C_r*(Gamma) as a unital sub-C*-algebra; tau_Gamma extends
tau_Lambda; and the same holds for finite matrix algebras.
Proof. Choose one representative v from every left Lambda-orbit
Lambda v in Gamma. Then l^2(Gamma) is the orthogonal direct sum
of the subspaces l^2(Lambda v). The unitary delta_g -> delta_{gamma v}
(from l^2(Lambda) onto l^2(Lambda v)) conjugates the Lambda-action
on l^2(Lambda) to its restriction to l^2(Lambda v). Therefore
the restriction of the left regular representation of Gamma to
Lambda is a direct sum of copies of the left regular representation
of Lambda. So every x in C[Lambda] has the same operator norm on
l^2(Lambda) as on l^2(Gamma), and the identity diagonal
<x delta_1, delta_1> = tau_Lambda(x) equals the Gamma identity
diagonal. Taking operator-norm closures gives C_r*(Lambda) inside
C_r*(Gamma); tensoring with M_N(C) gives the matrix version.
CONSEQUENCE. If p is a projection in M_N(C_r*(Lambda)), its
image in M_N(C_r*(K)) is also a projection and has the same
matrix trace.
Let p in M_N(C_r*(Lambda)) be a projection with
a = tau_{Lambda,N}(p), 0 < a < 1/2.
Regard p as a matrix over C_r*(K), K = Lambda * F_N. Let
U = ( lambda_K(t_1), ..., lambda_K(t_N) )
be a 1-by-N row of the N free generators' left-translation
unitaries. Two products of U with U* are used.
U U* = sum over j of lambda_K(t_j) lambda_K(t_j)* = N,
because each t_j on the identity contributes the identity, and
the N contributions sum to N. So ||U||^2 = N and the operator
inequality A = p U*U p <= N p holds immediately.
But A is NOT equal to N p. U* U is an N-by-N matrix over
C_r*(K) whose (i,j) entry is lambda_K(t_i^{-1} t_j). Its
diagonal (i = j) is all ones. Its off-diagonal entries (i != j)
are the DISTINCT non-identity words t_i^{-1} t_j in F_N; no two
different pairs (i,j) give the same word. So U* U is far from
a scalar, and it is the free-product structure inside U* U that
produces the constant 1/2 below.
Define
A = p U* U p (an element of p M_N(C_r*(K)) p).
Then A / N is a positive contraction in the corner, bounded
below by c_a^2 / N once section 5.5 is done.
MAIN CLAIM.
(i) A is invertible in the corner p M_N(C_r*(K)) p.
(ii) e = (U p) A^{-1} (p U*) is a projection IN C_r*(K),
with tau_K(e) = a.
The invertibility of A is equivalent to: U is bounded below on
the subspace p l^2(K)^N. Concretely, the claim is
|| U xi || >= c_a ||xi|| for all xi in p l^2(K)^N,
with
c_a = sqrt(1-a) - sqrt(a),
which is strictly positive exactly when a < 1/2. This is the
only place 1/2 enters the whole story.
Proof of the lower bound. Use the free-product normal form.
Write xi in p l^2(K)^N with coordinate functions xi_1,...,xi_N,
and let
m_v = || xi restricted to Lambda v ||^2, sum_v m_v = ||xi||^2.
On the orbit Lambda v, the projection p has, by Cauchy-Schwarz
within that orbit,
|xi_j(v)|^2 <= a_j m_v, a_j = tau_Lambda(p_jj),
because the "column" p delta_{(v,j)} has squared norm exactly
a_j = <p delta_{(v,j)}, delta_{(v,j)}>, and Cauchy-Schwarz on
the orbit gives |xi_j(v)|^2 = |<xi, p delta_{(v,j)}>|^2 <=
a_j * m_v.
GOOD AND BAD. Call v GOOD in coordinate j if the reduced word
of v does not begin with t_j^{-1}, BAD otherwise. Write
xi = xi_g + xi_b.
BAD INPUT. Each bad position determines its bad coordinate j
from the first letter t_j^{-1}. Summing the Cauchy-Schwarz
bound over bad (v,j):
|| xi_b ||^2 <= a || xi ||^2.
GOOD OUTPUT. Left-multiplication by t_j maps a good v to a word
starting with t_j. Outputs for different j are disjoint, and
multiplication within one coordinate is injective. Therefore
|| U xi_g ||^2 = || xi_g ||^2 >= (1 - a) || xi ||^2.
BAD OUTPUT. Different bad inputs, coming from different j's,
can collide on the same output word h. Let J(h) be the set of
coordinates j for which v_{h,j} = t_j^{-1} h is bad. Then
|(U xi_b)(h)|^2 is bounded by
(sum_{j in J(h)} a_j) (sum_{j in J(h)} m_{v_{h,j}})
<= a sum_{j in J(h)} m_{v_{h,j}},
using Cauchy-Schwarz and sum_j a_j = a. The map (h,j) -> v_{h,j}
is injective on bad inputs (first letter determines j, and
h = t_j v_{h,j}), so summing over h gives
|| U xi_b ||^2 <= a || xi ||^2.
ASSEMBLE. Triangle:
|| U xi || = || U xi_g + U xi_b ||
>= sqrt(1-a) ||xi|| - sqrt(a) ||xi||
= (sqrt(1-a) - sqrt(a)) ||xi||.
That is the claimed c_a bound, and c_a > 0 iff a < 1/2.
From the c_a bound, A = p U*U p >= c_a^2 p in the corner. Also
U U* = N, so A <= N p. Hence A / N has spectrum in [c_a^2/N, 1]
on the range of p, and p - A/N has norm <= 1 - c_a^2/N < 1.
The geometric series
A^{-1} = (1/N) sum_{k = 0 to infinity} (p - A/N)^k
converges in the corner p M_N(C_r*(K)) p. Continuous functional
calculus also gives A^{-1/2}.
Set V = U p A^{-1/2} (a 1-by-N row). Then
V* V = A^{-1/2} p U* U p A^{-1/2} = p,
so e = V V* is a projection in C_r*(K). Writing V = (V_1,...,V_N)
and using traciality,
tau_K(e) = sum_j tau_K(V_j V_j*)
= sum_j tau_K(V_j* V_j)
= tau_{K,N}(p) = a.
So e is a scalar projection of trace a, which lies in (0,1/2).
If Lambda is torsion-free and finitely generated, so is K
(adjoining finitely many t_j preserves both).
The trade exchanges "small MATRIX trace over Lambda" for "small SCALAR
trace over Lambda * F_N". Since the scalar form is the actual
conjecture, Step 1 has reduced everything to:
BUILD Gamma finitely generated and torsion-free,
BUILD p_0 in M_N(C_r*(Gamma)) a projection with
0 < tau_{Gamma,N}(p_0) < 1/2.
That is the rest of the proof. Everything after this is the
construction of Gamma and p_0.
The next ingredient is not analytic at all: it is an infinite
bipartite graph, built in layers, whose incidence operators
between adjacent layers are expanders with a UNIFORM spectral gap.
Three properties are wanted at once:
(1) expansion, so that the model operator on the tower has
a spectral gap;
(2) folded labels, so that any nonbacktracking path of
length at least L_i is uniquely determined by its word;
(3) no short cycles after pruning, so that the eventual
voltage cover can have big girth.
Points (1) and (2) pull in different directions. The trick is
to build two variants Y^0 and Y^# on the SAME vertex set with
the SAME labels, get (1) from Y^0 and (2) from Y^#, and delete a
proportionally tiny set of vertices so that the induced graphs
coincide -- the survivor Y has both.
Fix a positive integer ell, eventually large. Let
d = 2^(4 ell),
D = d^2 = 2^(8 ell),
s = 10 ell,
r = 7 ell,
n_0 = 1000,
H_0 = (2 n_0 + 1) s + 1 >~ 20010 ell,
H_i = H_0 + |i| (i in Z).
The two useful pieces of d: 2^r / 2^s = 2^(7 ell) / 2^(10 ell) =
2^(-3 ell) = d^(-3/4), and 2*s - r = log_2 d = 4 ell. These
identities make the degrees below balance.
Every vertex will be a pair of binary strings. For h >= 0 write
h = 2 s q + t with 0 <= t < 2 s, and set
l_A(h) = r + n_0 s + q s + max(t - s, 0),
l_B(h) = n_0 s + q s + min(t, s).
Then l_A(h) + l_B(h) = r + 2 n_0 s + h, and l_A(h) - l_B(h)
-r grows by 1 in one coordinate, then 1 in the other, alternating.
Note l_A(i) + l_B(i) grows with |i|.
For each i in Z, define
A_i = F_2^(l_A(i)) x F_2^(r + 1 + l_B(i)),
B_i = F_2^(l_B(i)) x F_2^(s - r + 1 + l_A(i)).
A vertex is a pair (u,v) of bit strings of the displayed
lengths. The string u is called the INPUT stream, and v the
OUTPUT stream. A quick computation gives the layer sizes
|A_i| = d * 2^(H_i),
|B_i| = 2^(H_i).
So each A-layer is d times as big as the B-layer at the same
index, and both grow like 2^|i| in the distance from 0.
The A-stream is divided into an initial block of length r (call
it block 0), followed by blocks of length s (block 1, 2, 3, ...).
Each B-stream is divided into blocks of length s (block 1, 2, ...).
Order the blocks from the two sides in an interleaved sequence
A,0; B,1; A,1; B,2; A,2; B,3; ...
For every |i-k| <= 1, the active portions of u_A at a vertex of
A_i and u_B at a vertex of B_k form an INITIAL SEGMENT of this
interleaving: at most one block on each side gets "cut off" part
way through.
Fix a pair (i,k) with |i-k| <= 1. On each A_i vertex there are d
SLOTS, indexed by a = (k - i, j) with 1 <= j <= d. On each B_k
vertex there are D_{ik} slots, indexed by c = (i - k, j, b) where
b in F_2^(p - p') for two small integers p, p' defined by
p = r + 1 + l_B(i) - l_B(k), p' = s - r + 1 + l_A(k) - l_A(i).
Direct computation gives
p - p' = 2 s - r + |i| - |k|
= log_2 d + |i| - |k|,
D_{ik} = d * 2^(p - p')
= D * 2^(|i| - |k|), D/2 <= D_{ik} <= 2 D.
At a vertex of A_i, counting all three adjacent pairs (k = i-1,
i, i+1), 3 d slots arise in total. At a vertex of B_k, counting
the same three pairs, at most 6 D.
An edge over the pair (i,k) is a triple (a, c, x) where x is a
bit string in F_2^p. The A-endpoint is (vertex a) and the B
endpoint is (vertex c); the slot pairs are matched by requiring
the same x on both ends. This defines the bipartite graph
between A_i and B_k.
Each slot carries a linear map K from padded input streams
to padded output streams. On a full block of length s (or on
block 0 of length r) K acts by multiplication by an element of
the finite field F_{2^h}, after choosing an identification of
F_2^h with F_{2^h}. Additionally, K may send a linear image of
one block into the FIRST ONE OR TWO bits of the FOLLOWING block
on its own side. Nothing else is coupled.
The slot EVALUATION is
Q = v + K u,
a bit string in the output stream, of a specific padded length.
Both the A-end of an edge and the B-end produce such an
evaluation, and they must agree on the label x of the edge (with
an overlap arranged by the lengths above).
RECOVERY. At an A-vertex with slot a, the input u_A on that side
and the linear map K_a are known. Subtracting K_a u_A from v_A
gives Q_A = v_A - K_a u_A. The edge label x is the first p bits
of Q_A, and the slot c at the other end follows from the "bucket"
data in x. The triangular system then determines the other
endpoint's input u_B, because the couplings run forward in the
block ordering: block N on one side needs only blocks up to N-1 on
the other. With u_B known, v_B = Q_B + K_c u_B.
The same works from the B-vertex to the A-vertex.
For this to define a genuine bijection between ends, two
conditions are needed: the diagonal coefficients on distinct
slots at a vertex must be distinct (so the algebra is invertible),
and the "spill" terms must be small (so blocks are only coupled
to their immediate neighbors). Both are arranged by choosing
the coefficient maps injectively; there are 3d slot names on the
A side and at most (21/2)D slot names on the B side, both smaller
than 2^r and 2^s respectively for large ell, so injections into
the appropriate fields exist.
FOLDED. The labeling is folded: at every vertex, the labels on
the outgoing oriented edges are distinct. This follows from the
slot structure; different slots differ in one of (offset, serial
number, bucket, x).
UNIQUE LONG PATHS. If two nonbacktracking paths of length at
least L_i end or begin at a vertex in layer i, and they read the
same oriented word in a fixed finite alphabet, they coincide as
paths. Reason in one line: the triangular equations
propagate bit by bit along the common word, and the "gate" data
included in each label records the block state sufficiently far
back that a wrong start cannot reproduce the word.
The proof is the content of the "prefix-recovery" lemma, where
the gated deletion rule and the two-layer comparison are laid
out. Nothing earlier in the pruning machinery is used later
except the conclusion.
Y^#. One edge label carries, in addition to its slot data, an
optional "gate" state on the LAST block of the current slot. The
gate condition is a simple XOR of the four immediately preceding
full s-blocks of input. When the gate is OPEN, a permutation is
applied to the last block; when CLOSED, nothing happens. Two
choices of last-block permutations give the label. In Y^#, this
gate is used at every edge, so later blocks (in the interleaved
order) cannot accidentally be read as if they belonged to a
later layer: the gate isolates the current block from the future
contents.
Y^0. Same edges and slots, but the last-block permutation is
applied unconditionally. This gives cleaner analysis of the
incidences: each block is just a random biregular matching.
Both Y^0 and Y^# have the same vertex set and the same label set.
THE EXPANSION LEMMA. Fix Y^0 with its count-normalized closure.
For every pair (i,k) with |i-k| <= 1, the incidence between A_i
and B_k has degrees d and D_{ik}, maps normalized constants to
normalized constants (and adjoints likewise), and on the
orthogonal complements acts with norm at most 1 - chi where
chi = 1/800
is an absolute constant. This is the same constant later used
for the spectral gap of the eventual Cayley operator.
How is such a gap obtained? Each block is built from independent
clusters (one per choice of common key), and each cluster is a
uniform matching between two sets of size 2^t. A matching that
is well chosen has an incidence matrix whose action on constant-
orthogonal spaces shrinks by a definite factor. A local-lemma
argument (the same Erdos-Lovasz style argument as in the usual
expander constructions) shows that the last-block permutations
of Y^0 can be fixed so that ALL blocks, at once, obey the gap.
The gap 1/800 is fixed for concreteness; any positive constant
below 1 would give a slightly different final trace bound.
Y^0 and Y^# do not literally agree edge-by-edge. After deleting
a proportionally tiny set of vertices, they do.
GATE DELETIONS. Delete every vertex in Y^# where some gate is
CLOSED at the point where Y^0 would set its slot. By independence
of the current slot's bits from the preceding inputs, each
specific pair of gated s-blocks being all-zero has probability
2^{-4s}; a union bound over at most 6D slots per vertex gives a
deleted fraction at most
eps_gate = 6 D * 2^(-4 s) = D / 2^(32 ell).
SEPARATION DELETIONS. Delete every vertex whose own u-bits
immediately after an EARLIER cutoff (a smaller layer, but the
same sign and residue of |i| mod K, where K = 32 s) are all zero.
The probability of this at the smaller layer is
2^{-min(H_{i'}, mK/2)} with m = (|i| - |i'|)/K, and the union
bound over all such i' gives a deleted fraction at most
eps_sep <= 2^(-K/2) / (1 - 2^(-K/2)) + 3 * 2^(-H_0).
This is what prevents the zero padding of a smaller-layer vertex
from being read as if it were the same layer.
SHORT-CYCLE DELETIONS. Delete every vertex supporting a
nonempty cyclically nonbacktracking closed path of length at
most g_i = H_i / (100 log_2 d). A counting argument (each cyclic
word corresponds to at most one such path, by unique-path
recovery) bounds the deleted fraction by 2^{-0.9 H_0}.
Total deleted fraction
eps_ell = eps_gate + eps_sep + 2^(-0.9 H_0) -> 0.
Let Y be the induced subgraph on the vertices surviving all three
deletions. It is an induced subgraph of BOTH Y^0 and Y^#, so it
has expansion AND recovery simultaneously. Properties:
(a) For every |i-k| <= 1, the induced Y-block between A_i
and B_k still has degree d and D_{ik} on its sides, has
norm <= 1 - chi on the complements of constants, and
maps constants to constants.
(b) The fraction removed from each A_i and B_i is <= eps_ell.
(c) Labels are folded; positive alphabet size m_ell is
O( d 2^r (1+s)^2 ) = O( d^(11/4) (1+s)^2 ), so
log_2(2 m_ell) = 11 ell + O(log ell).
(d) Every nonbacktracking path beginning at layer i of length
at least L_i = 100 H_i / log_2 d is uniquely determined
by its oriented word.
(e) No nonempty cyclically nonbacktracking closed path in Y
has length at most g_i.
This Y is the combinatorial substrate for the next six parts.
The A- and B-layers will be placed on a cover, then lifted to
the Cayley graph of a group, and only the survivor Y matters from
here on.
The deck group F, whose elements will become the voltages on the
edges of Y, has two jobs.
(a) DETECT short closed walks. Given a short cyclically
nonbacktracking closed walk in the cover, the product of
the voltages along its edges must be nontrivial in F.
That is what makes the cover have big girth.
(b) CARRY small-trace projections. Its twisted group
algebras must contain projections p_theta whose
unnormalized trace is tiny when theta is small.
These pull in opposite directions: (a) wants F rich, (b) wants
F shrinkable by a twist. A nilpotent group built from upper
unitriangular matrices delivers both at once.
Fix an integer m >= 2 (chosen later) and let U_Z be the group of
upper unitriangular m-by-m integer matrices (upper triangular,
diagonal entries 1). U_Z is finitely generated, torsion-free,
nilpotent.
LEMMA (word detector). Let Gamma be a unit-edge graph with
girth greater than g, and let W be a nonempty, cyclically
nonbacktracking closed walk of length at most C g. Assign the
symbol 1 to some edges of the support of W, and generic upper
unitriangular matrices to the rest (with inverses on reversed
edges). Then the resulting word in U_Z is NOT the identity
matrix as long as
m > L(C), L(C) = ceil(3 C B(C)),
B(C) = max(1, ceil(20 C))^2.
Proof. Seven steps, each elementary.
STEP 1 (support has few arcs). Let S be the union of the edges
of W. Each vertex of S has degree at least two: a degree-one
vertex in the closed walk, including at the cyclic closure,
would force W to traverse some edge and immediately reverse it,
a backtrack. Write b = b_1(S) for the first Betti number;
then b >= 1. If every vertex of S has degree two, S is a
single circle; treat it as one arc. Otherwise suppress all
degree-two vertices. Every vertex of the suppressed graph has
degree at least three, so 2e >= 3v. Together with
b = e - v + 1 this gives v <= 2b - 2 and e <= 3b - 3, all
purely combinatorial (no planarity needed). In either case S
decomposes into ARCS, meaning maximal edge paths between branch
points, and the number of arcs is at most 3b.
STEP 2 (a spanning tree with pivots). Call an arc SHORT if
its length is less than g/(3b). The short arcs cannot contain
a circuit: a circuit made entirely of short arcs has length
less than 3b times g/(3b) = g, contradicting girth(S) > g. So
the short arcs form a forest. Extend that forest to a spanning
tree of the arc-graph of S. Every complementary arc is LONG,
with length at least g/(3b). From each long arc delete exactly
one of its original edges, calling it the PIVOT of that arc.
The surviving original edges form a spanning tree T of S:
each long arc of the complement closes one cycle, and that cycle is broken
each one.
STEP 3 (total pivot crossings). Cyclically start W at a
retained vertex of T. Because W is nonbacktracking, it cannot
turn around inside an arc: to leave an arc on the side it
entered, W would have to traverse the last edge back, a
backtrack. So once W enters an arc it traverses that arc
completely, from one end to the other. Each traversal of a
LONG arc crosses exactly one pivot; each traversal of a short
arc crosses none. Let N be the number of long-arc traversals
of W. Each such traversal contributes length at least g/(3b)
to W, so the sum of their lengths is at least N g/(3b). That
sum cannot exceed the total length of W, which is at most Cg.
Therefore N g/(3b) <= Cg, i.e. N <= 3bC. Since each pivot
crossing belongs to one long-arc traversal, the TOTAL number
of pivot crossings of W is at most 3bC <= 3 C B(C) = L(C).
STEP 4 (a nontrivial reduced word). Collapse T to a point.
The result is a bouquet of b circles, with one circle per
pivot label. Collapsing a spanning tree is a homotopy
equivalence, and the image of W is a word on the b pivots. A
nonempty cyclically reduced closed walk in a graph is not
null-homotopic, so this image word is nontrivial in the free
group on the pivots. Free reduction can only shorten a word,
so the reduced length k of the image word is at least one and
at most the number of pivot crossings, hence at most L(C).
STEP 5 (a matrix cannot be trivial). Write the reduced word
in maximal syllables w = x_{j_1}^{a_1} ... x_{j_k}^{a_k}, where
each a_s is nonzero and successive j_s differ. In formal
noncommutative power series, set x_j = 1 + Z_j, using
(1+Z)^a = sum over h >= 0 of binom(a,h) Z^h, which holds also
for a < 0 as a finite expansion modulo Z^m. The monomial
Z_{j_1} ... Z_{j_k} in w has coefficient prod_s a_s, nonzero:
to make that monomial, each syllable must supply exactly one of
its k letters, and no two adjacent syllables share a variable,
so no other contribution reaches that monomial. For
m > k = length(w), put Z_j = sum over { s : j_s = j } of
E_{s, s+1} in M_m(Z). Because the indices 1, 2, ..., k+1 are
strictly increasing, the (1, k+1)-entry of w(1 + Z_j) equals
prod_s a_s. It is nonzero, so w(1 + Z_j) != 1.
STEP 6 (invariance under fixed factors). For strictly upper
triangular X, the inverse of 1 + X is
sum over h = 0 to m-1 of (-X)^h. Every entry of every word in
upper unitriangular matrices and their inverses is therefore a
polynomial in the upper entries of the edge variables, and each
of its monomials uses at most m - 1 such entries. Multiplying
by a fixed upper unitriangular matrix on either side is a
polynomial change of coordinates with polynomial inverse, so
nonidentity is preserved.
STEP 7 (applying it in the tower). Choose m once and for all
with
m > L(201 C_*), L(C) = ceil(3 C B(C)),
B(C) = max(1, ceil(20 C))^2.
A closed walk in Y based in layer i of length at most
C_* H_i / log_2 d stays in layers j with
H_j >= H_i - C_* H_i / log_2 d >= H_i / 2 for large ell.
Property (e) of the pruning ledger says no nonempty cyclically
nonbacktracking closed path in Y based at layer i has length at
most g_i = H_i / (100 log_2 d). So every embedded circuit in
the support of W has length greater than g_i, in particular
greater than g = H_i / (201 log_2 d). With C = 201 C_*, the
length of W is at most C g, so Steps 1 - 6 apply: the
voltage-holonomy word in U_Z is not the identity matrix. This
is uniform in i.
Let n be the real vector space of strictly upper triangular
m-by-m matrices. It has dimension n_f = m(m-1)/2 and is a
nilpotent Lie algebra. Write U = 1 + n for its exponential
group (upper unitriangular matrices with real entries and
diagonal 1).
Build an affine semidirect product E on n. The exact laws are:
(lambda, b, z) * (mu, b', w)
= (lambda + mu . L_{b^-1}, b b',
z + w + mu(b^-1 - 1)),
with lambda a linear functional on n (coordinates lambda_ij),
b in U, and z real. Constants (0, 1, z) are central. Divide
out the subgroup (0, 1, k) for k in Z to get a quotient bar-E
with coordinates (lambda, b).
Restrict to INTEGER coordinates: E_Z and bar-E_Z are the
sublattices where all coordinates of (lambda, b^-1, z) are
integers. Then define the DECK GROUP
F = (E_Z x E_Z) / { ((0, 1, k), (0, 1, -k)) : k in Z }.
Equivalently, F has coordinates (gamma_X, gamma_Y, z) with
gamma_X, gamma_Y in bar-E_Z and z in Z, and multiplication
(gamma_X, gamma_Y, z) * (eta_X, eta_Y, w)
= (gamma_X eta_X, gamma_Y eta_Y,
z + w + c(gamma_X, eta_X) + c(gamma_Y, eta_Y)),
where c is the cocycle measuring the failure of bar-E to be a
group extension. That is the deck group F.
FACTS. F is countable, nilpotent, torsion-free, and finitely
generated. The integer coordinate z is its CENTRAL coordinate.
Projection to the upper unitriangular part of EITHER bar-E_Z
factor is a surjective group homomorphism onto U_Z. That is
what lets F detect short words (7.2).
Conjugate by inversion to get right translations, then Fourier-
transform the central coordinate z: the character z -> e(t z),
with t in the circle T = R/Z. This gives
l^2(F) = L^2( T ; l^2(bar-E_Z) (x) l^2(bar-E_Z) ).
Under this decomposition, a section lift sigma(gamma) acts on the
second bar-E_Z factor with a twisted phase e(t c(...)) depending
on t. The central generator z_0 = (1, 1, 1) acts by the scalar
e(t). The symbol u_t denotes the twisted left action on the first
factor and v_t for the twisted right action on the second. They
commute and are twisted-unitary.
Work first with the continuous bar-E (not bar-E_Z).
Twisted convolution of Schwartz functions
(J *_epsilon K)(h)
= integral over bar-E of J(a) K(a^-1 h)
e(epsilon c(a, a^-1 h)) da,
with twisted involution
J^{*_epsilon}(h) = conj(J(h^-1)) e(-epsilon c(h^-1, h)),
makes Schwartz functions bar-E into a *-algebra. Its twisted
representation
(pi_epsilon(lambda, b) phi)(x) = e(epsilon lambda(x)) phi(A_{b^-1} x)
on L^2(n) is unitary, and integrating a Schwartz function
against it gives a bounded operator.
THE KEY CORRESPONDENCE. SCHWARTZ COEFFICIENT FUNCTIONS on
bar-E are in bijection with SCHWARTZ INTEGRAL KERNELS on n, via
Fourier transform in the first (lambda) variable. The kernel
of pi_epsilon(J) is
K_J(x, y) = (Fourier in lambda of J)(epsilon x, (1+x)(1+y)^-1).
The map J -> K_J is a bijection on Schwartz spaces, an L^2
isometry (with the correct normalization), and preserves twisted
convolution.
Therefore a rank-one Schwartz kernel, such as the Gaussian
projection phig(x) = 2^{n_f/4} exp(-pi |x|^2) of L^2-norm 1,
has a unique preimage
J_epsilon in Schwartz(bar-E), with
J_epsilon * J_epsilon = J_epsilon,
J_epsilon^{*_epsilon} = J_epsilon,
||J_epsilon||_{L^2(bar-E)} = 1.
It is a genuine Schwartz idempotent.
An ACTUAL element of a C*-algebra is needed, not a continuous
object. Sample J_epsilon on Delta_y bar-E_Z.
Let theta be a small nonzero real, epsilon = sign theta,
y = |theta|^{1/m}, and
nu = y^{m n_f} = |theta|^{n_f},
K_theta = sum over gamma in bar-E_Z of
nu J_epsilon(Delta_y gamma) u_theta(gamma).
Riemann-sum estimates for the WEIGHTED rectangular lattice
Delta_y bar-E_Z (cell volume nu) give:
||K_theta||_{coeff,1} <= C,
||K_theta||_{coeff,2} ~ sqrt(nu),
||K_theta^2 - K_theta||_{coeff,1} <= C y,
||K_theta^2 - K_theta||_{coeff,2} <= C y sqrt(nu).
The coeff-1 norm controls the operator norm, so the spectrum of
K_theta lies within C y of {0, 1}. Functional calculus supplies
a genuine projection p_theta with
|| p_theta - K_theta || <= C y,
0 < tr_theta(p_theta) <= C |theta|^{n_f}.
The lower bound 0 < is essential: if p_theta were 0, then
||K_theta|| <= 1/4, but the identity-coefficient of K_theta is
O(sqrt(nu)) = O(|theta|^{n_f/2}), strictly positive for
theta != 0.
One twist gives small trace as theta -> 0. Small trace is wanted
at both ends of a window 0 < t < delta. Add a FINITE
representation R of bar-E_Z on C^N whose central character
carries a rational shift by delta:
q = d^{A_*}, delta = q^{-1}, N = q^{n_f}.
R acts on l^2 of the upper unitriangular matrices mod q:
(R(lambda, b, z) psi)(x)
= e( -(z + lambda(x))/q ) psi( b^-1(1+x) - 1 ).
Its central character is R(0, 1, z) = e(-delta z) 1_N.
Let V_t = u_t (x) R be the tensor of the twisted left action
with R. A diagonal unitary W_t converts V_t into
u_{t-delta} (x) 1_N:
W_t^* V_t(gamma) W_t = u_{t-delta}(gamma) (x) 1_N.
This is twisted absorption: the finite factor R absorbs the
delta shift of the twisted multiplier. Crucially, W_t fixes the
identity-block, so the identity trace of every projection is
multiplied by exactly N.
Now, for 0 < t < delta, BOTH t and t - delta fall in the small-
theta regime. Define
p(t) = p_t (x) p_{t-delta}[V_t],
an equivariant projection. Its identity trace factorizes:
s_p(t) = N * tr_t(p_t) * tr_{t-delta}(p_{t-delta})
<= C N t^{n_f} (delta - t)^{n_f}.
This is small at BOTH ends of the window, because t -> 0 kills
one factor and t -> delta kills the other.
The layers on which the model acts are chosen by a smooth bump h.
Fix a smooth nonnegative h, supported in (-1, 1) and positive on
[-0.7, 0.7], with
sum over i of h(v - i)^2 = 1 for every real v.
For 0 < t < delta define
b(t) = (1/kappa) log_2( t / (delta - t) ),
h_i(t) = h(b(t) - i).
The ACTIVE SET J(t) = { i : h_i(t) != 0 } has at most two
elements, and they are adjacent when there are two. As t runs
from 0 to delta, b(t) runs monotonically from -infinity to
+infinity, so the active layers SWEEP from -infinity to
+infinity. That is the "moving band".
LAYER WEIGHTS. Let
w_i = q^{-1} 2^{-kappa |i|}.
On the support of h_i(t):
t is comparable to q 2^{kappa b} / (1 + 2^{kappa b}),
delta-t is comparable to q / (1 + 2^{kappa b}),
so
t(delta - t) <= 2^kappa q^{-2} 2^{-kappa |i|}.
Multiply by N = q^{n_f} and use the trace bound 7.7:
w_i s_p(t) <= C 2^{kappa n_f} q^{-n_f} 2^{C_bullet H_i}
2^{-kappa n_f |i|}.
Now substitute H_i = H_0 + |i|, the bound H_0 <= h_* log_2 d =
4 ell h_*, and q^{n_f} = d^{A_* n_f}. The result is
w_i s_p(t)
<= C 2^{kappa n_f}
d^{-(A_* n_f - C_bullet h_*)}
2^{-(kappa n_f - C_bullet) |i|}.
The parameters are chosen in the order
E_0 > 10 (C_* + C_bullet + 1),
A_* in N, A_*/m > 10 E_0 h_*,
kappa > 0, kappa/m > 10 (E_0 + A_* + C_bullet + 1).
These ensure A_* n_f > C_bullet h_* (since n_f >= 1 and
A_*/m > 10 E_0 h_* with E_0 > 10 C_bullet) and kappa n_f >
C_bullet. So the two exponents on the right are STRICTLY
POSITIVE, and
mu_ell = sup over t and i in J(t) of w_i * s_p(t) -> 0.
That is the "small weighted trace" the whole program will
convert into p_0 with small trace.
Constants are now set once and never altered again:
C_*, C_bullet from the geometry of the voltage cover;
m = an integer > L(201 C_*);
E_0, A_*, kappa satisfying the displayed inequalities;
theta_0 = small radius for the expansion (7.6);
ell = the last free parameter, chosen large.
Nothing circular: each choice depends only on choices made
earlier.
The combinatorial tower Y exists, the deck group F exists, and the
small-trace projections p(t) exist in the twisted algebras of F.
The next move is to assemble these into an ACTUAL self-adjoint
operator on a voltage cover of Y, with two simultaneous
properties:
GIRTH: the cover has no short nonbacktracking closed
walks;
APPROXIMATION: the cover operator is within eta of the model
operator on the tower, in the FULL regular norm.
Once that is done, the geometry of the voltage cover will turn the cover
into a finitely generated group.
Take the linear space
H^0 = l^2( union of A_i and B_i, i in Z )
(x) l^2(F) (x) C^N.
Let Pi denote orthogonal projection onto the surviving vertices
Y. For 0 < t < delta and each pair (i,k) with |i-k| <= 1, put
O(t)_{A_i B_k} = U^0_{ik} (x) h_i(t) h_k(t) p(t),
where U^0_{ik} is the normalized incidence between the layer
sides in Y^0, h_i(t) is the layer window,
and p(t) is the small-trace projection. Set the
opposite block to the adjoint and all other blocks to 0.
BAND. Let a_i = |A_i|^{-1/2} 1_{A_i} and b_k = |B_k|^{-1/2} 1_{B_k}
be the normalized constant vectors. Define an isometry
V_*(t) zeta
= 2^{-1/2} * ( + ( h_i(t) a_i (x) zeta )_i
+ ( h_i(t) b_i (x) zeta )_i ),
for zeta in the range of p(t). Set E_*(t) = V_*(t) V_*(t)^*.
Then
O(t) E_*(t) = E_*(t), (eigenvalue 1)
||O(t)|| <= 1,
O(t) on (1 - E_*(t)) H^0_t <= (1 - chi) I,
tr_id E_*(t) = tr_id p(t).
Reason: on the diagonal side the U^0_{ik} act as the rank-one
operator |h_i><h_k|; the symmetric two-sided subspace receives
U^0_{ik} and its adjoint, giving eigenvalue 1; the antisymmetric
subspace sits at -1 and does not affect the UPPER trace; and on
the complement of the constants, the U^0_{ik} shrink by 1 - chi.
COMPRESSION TO Y. Cutting out the deleted vertices in Y
costs at most sqrt(beta_ell) in norm on E_*(t), where
beta_ell <= eps_ell -> 0 is the deleted fraction of the tower pruning.
So Pi O(t) Pi still has a band near 1.
Given any fixed eta > 0 and ell large enough, the construction gives
voltages z_e in F on the positive edges e of Y,
matrices W_e in M_N(C) with ||W_e|| <= C_eta,
so that:
(G1) Augmenting each original label (of Y) by its matrix
weight gives a finite positive alphabet of size o(dD).
The label's ORIGINAL part still determines the degree
normalizer D_{ik}.
(G2) The voltage cover P of Y has no nonempty cyclically
nonbacktracking closed walk based in layer i of length
at most C_* H_i / log_2 d.
(G3) Let T_P be the cover's incidence operator, with entries
from B_k to A_i given by
(T_P)_{ab} = (d D_{ik})^{-1/2}
* sum over edges e : a -> b of
W_e * rho(z_e).
Then ||T_P - Pi O Pi|| <= eta in the full regular
norm. Both operators have LAYER WIDTH ONE (only
|i-k| <= 1 is nonzero), so their central Fourier
fields satisfy the same inequality almost everywhere and
||T_P(t)|| <= eta outside 0 < t < delta.
The point of (G3) is that T_P is a FINITE sum of group
translations with matrix coefficients; it is manifestly an
element of M_N(C_r*(Gamma_proj)) once Gamma_proj is defined
from the cover. So T_P is a real object, not an approximation.
The construction has five stages:
(1) FINITE TESTS. Reduce statements about the FULL regular
norm to statements about finitely many block-matrices.
(2) EMPIRICAL LISTS. Replace expectations by M-term empirical
averages that are close in that norm.
(3) COMPACT TEMPLATES. Work with compactly supported smooth
functions J_epsilon^flat from the Schwartz construction, and use finite
log-grid templates of the p(t) window.
(4) TWO-BLOCK CASES. For the small index i < I, use finitely
many templates; for the large index i >= I, use subgroup
factorization modulo q to just one fixed finite list.
(5) ONE DRAW PER EDGE. Fix independent distributions on the
blocks, draw once, and use compactness (or counting) to
find a single sample that satisfies all conditions at
once.
Lemma. Let x >= 2 and let B be a fixed positive exponent. There
is a finite coordinate box B_x in F, of size x^c, such that for
any fixed finite set of group elements g with all coordinates
bounded by x^a, the symmetric difference ratio
|B_x sym-diff B_x g| / |B_x| <= C x^(-B).
Let A be a self-adjoint matrix of convolution sums on
l^2(J) (x) l^2(F) (x) C^n, with J a finite set, whose coefficient
row-and-column sums are bounded by R. Then
||P_x A P_x|| <= ||A|| <= ||P_x A P_x|| + C x^(-B) R,
where P_x retains the deck indices in B_x.
Proof. Use the graded coordinate system on the nilpotent deck
group: every group coordinate carries a positive integer weight
w_a, with only finitely many coordinates and only finitely many
weights, all determined by m. Choose one integer T >= x and put
B_x = prod over coordinates a of [-T^{w_a}, T^{w_a}] cap Z.
Write W for the sum of all weights and D for the number of
coordinates; then D and W are fixed. Thus
|B_x| = prod_a (2 T^{w_a} + 1) <= 3^D T^W <= x^c for a fixed c.
Multiplying f in B_x by g right-shifts each coordinate. In a
coordinate of weight j the shift differs from f's coordinate by
a sum of finitely many graded monomials, each having total
weight between 1 and j and containing at least one coordinate of
g; that coordinate of g is bounded by x^a. The multiplication
polynomials of the group law are fixed, so for a fixed integer P
every such monomial is at most C x^P T^{j-1} in absolute value
once T >= x. Hence a point f whose weight-j coordinate is
farther than C x^P T^{j-1} from both faces of B_x stays inside
B_x after right multiplication by g. The bad region for weight
j has relative measure at most C' x^P / T, and there are D
coordinates, so the union over all weights has relative measure
at most C'' x^P / T. Taking T = ceil(x^{P+B+2}) makes this at
most x^{-B}. Right multiplication is a bijection, so the same
estimate, doubled, bounds the relative size of
B_x sym-diff B_x g by C x^{-B}.
For the norm assertion, let P_s be the projection onto the left
translate s B_x. Right convolution commutes with left
translation, so every P_s A P_s has the same norm as P_x A P_x.
For a finitely supported vector xi,
sum over s in F of ||P_s xi||^2 = |B_x| ||xi||^2,
because any fixed deck index appears in exactly |B_x| translates
s B_x. Average <AP_s xi, P_s xi> over s, dividing by |B_x|. The
coefficient of rho(g) in the resulting operator A_x equals
alpha_x(g) = |B_x intersect B_x g^{-1}| / |B_x|,
and |1 - alpha_x(g)| <= C x^{-B} by the previous step. So the
averaged quadratic form satisfies |<A_x xi, xi>| <= ||P_x A P_x||
||xi||^2. Since the row and column coefficient sums of A are
bounded by R and the same bounds hold after averaging, the scalar
Schur test gives ||A - A_x|| <= C x^{-B} R. Density plus the
quadratic form identity give the claimed two-sided inequality.
Do nothing new for the amplification: the argument never touched
the auxiliary index set, only the deck indices of F.
For a rectangular S : J -> J' of coefficient row sums bounded by
R, apply the above to the self-adjoint block operator
(0 S; S* 0) on J disjoint-union J', whose norm equals ||S||, with
R replaced by 2R.
The key consequence: the full regular norm of a block operator
is determined up to C x^(-B) * (row sum) by ONE finite matrix
test.
Fix M = d^{1/32} = q^{1/(32 A_*)}, a number that grows with ell
but stays much smaller than d.
Lemma. Suppose a finite set of operator-valued distributions on
l^2(F) (x) C^N is given, with all constituent operators
uniformly norm-bounded by B_0, all group coordinates bounded by
q^a, and matrix size N <= q^a. For each fixed epsilon_emp > 0,
and ell large enough, each expectation has an M-term empirical
average within epsilon_emp of itself in the full regular norm,
UNIFORMLY over the finitely many distributions.
Proof. Fix one of the finitely many distributions. Take M
independent samples X_1, ..., X_M and write the empirical
deviation of the mean
Y = M^{-1} sum_{j=1}^{M} (X_j - E X_1).
Each X_j - EX_1 is bounded in norm by 2 B_0, and its coefficient
support lies inside the coordinate box of edge q^a. So the
coefficient row and column sums of Y are bounded by 2 B_0.
Step 1 (finite test). Apply the box lemma with x = q,
exponent B, and operator A = Y. This gives a coordinate box B_q
of size q^{c_0} with
||Y|| <= ||P_q Y P_q|| + C q^{-B} (2 B_0).
Take B large enough that the second term is at most eps_emp / 2
for all large ell; this B is a fixed constant. Set
Y_q = P_q Y P_q and let d_fin <= q^{c_1} be the dimension of the
range of P_q, including matrix indices. It remains to show that
some choice of the M samples makes ||Y_q|| <= eps_emp / 2.
Step 2 (moment expansion). Set Z_j = P_q (X_j - EX_1) P_q. The
Z_j are independent, self-adjoint, with mean zero and
||Z_j|| <= 2 B_0, and
Y_q = M^{-1} sum_{j=1}^{M} Z_j.
For any integer K >= 1,
E Tr(Y_q^{2K})
= M^{-2K} sum_{j_1,...,j_{2K} in {1,...,M}}
E Tr(Z_{j_1} ... Z_{j_{2K}}).
If some index j_0 occurs exactly once among j_1, ..., j_{2K},
that summand is ZERO: condition on all the other Z_j, and by
independence and E Z_{j_0} = 0 the factor Z_{j_0} pulls out of
the trace and vanishes. So only sequences in which every index
used appears at least twice contribute. Such a sequence uses
at most K distinct indices, so the number of surviving
sequences is at most
sum_{a=1}^{K} M^a a^{2K}.
For each one,
|Tr(Z_{j_1} ... Z_{j_{2K}})| <= d_fin (2 B_0)^{2K}. Using
M^a <= M^K and a^{2K} <= K^{2K},
E Tr(Y_q^{2K})
<= d_fin (2 B_0)^{2K} M^{-2K} sum_{a=1}^{K} M^a a^{2K}
<= d_fin (2 B_0)^{2K} K (K^2 / M)^K.
Step 3 (choice of K and the moment bound). Put K = ceil(log_2
q), so K = log_2 q + O(1) and, since M = q^{1/(32 A_*)},
log_2 E Tr(Y_q^{2K})
<= c_1 log_2 q + K log_2(4 B_0^2 K^2 / M) + log_2 K
= c_1 log_2 q + O((log_2 q)(log_2 log_2 q))
- (1/(32 A_*)) (log_2 q)^2.
The negative quadratic term in log_2 q dominates, so
E Tr(Y_q^{2K}) tends to zero super-polynomially fast as ell
grows.
Step 4 (Markov and existence). For any eps_emp > 0,
P( ||Y_q|| > eps_emp / 2 )
<= (2 / eps_emp)^{2K} E Tr(Y_q^{2K}),
and (2/eps_emp)^{2K} grows only polynomially in q. So this
probability tends to zero with ell. Hence for large ell there
exists a sample tuple with ||Y_q|| <= eps_emp / 2 for the chosen
distribution. There are only C(1 + log q) fixed distributions,
and the union bound over them still fails with probability
tending to zero as ell grows. So a single simultaneous choice
exists.
Combining Step 4 with Step 1 gives
ess-sup_t ||E_emp(t) - (h_i h_k p)(t)|| <= eps_emp
UNIFORMLY over the finitely many distributions. This proves the
lemma.
A FINITE list of coefficient templates is needed, uniform in the
layer index. Two replacements make this possible.
COMPACT SUPPORT. The compactness result for Schwartz coefficient
functions says: J_epsilon can be replaced by compactly supported
smooth J_epsilon^flat at arbitrarily small L^1 coefficient cost,
uniformly in the lattice mesh, for small enough ell.
LOG-GRID PARTITION OF UNITY. Let psi_nu(t) be a smooth partition
of unity on 0 < t < delta, pulled back from the natural
log_2 coordinate. For each cell nu on a fixed-grid partition of
each of the two logarithmic charts, its associated magnitude
templates a_nu, b_omega satisfy
|log(a_nu / t)| <= u, |log(b_omega / (delta-t))| <= u,
for a small fixed u = u(epsilon).
For each block (i,k), let T_{ik} be the set of pairs (nu, omega)
whose supports meet h_i h_k. This set has size at most
K_epsilon, independent of i, k, ell. So the block-averaged
operator
sum over (nu,omega) in T_{ik} of
f_{ik,nu,omega}(t)
* L_+(a_nu ; u_t)
* L_-(b_omega ; V_t)
approximates h_i(t) h_k(t) p(t) to error epsilon, uniformly,
where f_{ik,nu,omega} = h_i h_k psi_nu theta_omega.
MASK DECAY. Each f_{ik,nu,omega} is smooth with compact support
and derivatives of size at most C_j w_i^{-j} in the L^1 norm.
Consequently its Fourier coefficients decay:
|hat{f}(n)| <= C_j w_i (1 + |n| w_i)^(-j) for every j >= 1,
so summing over n gives sum |hat{f}(n)| <= C, and truncating at
K_i = ceil(L / w_i) for a small fixed L adds error C_j (1+L)^(1-j).
Replacing the mask by its truncated Fourier series costs a
DETERMINED amount, uniformly in layer.
Blocks with i < I. Here the layer weights h_i force
b_omega^(-1) <= q * 2^{kappa (I+1) + C}. There are only
O(1 + log q) such templates over all such blocks, and their
coordinate supports are bounded by a fixed power of q.
So for i < I, FINITELY MANY ordinary empirical M-lists are used,
one per template.
Blocks with i >= I. Introduce the subgroup
Lambda_q = { (lambda, b) in bar-E_Z :
lambda_ij = (b-1)_ij = 0 mod q }.
Reduction modulo q is a surjective group homomorphism, so
Lambda_q has index Q_q = q^(2 n_f). Choose one representative
v per coset into a set V_q with coordinates in {0,...,q-1}.
Then every gamma is uniquely gamma = yv with y in Lambda_q and
v in V_q. The finite magnetic representation R satisfies
R(sigma(y)) = 1 for y in Lambda_q.
Build the coset average
C_q = Q_q^{-1} sum over v in V_q of
R(sigma(v)) * rho(sigma_Y(v)).
Then for any i >= I, the block template can be replaced by
[ Q_q sum over y in Lambda_q of
b_omega^{n_f} J_-^flat(Delta_{b_omega^{1/m}} y)
rho(sigma_Y(y)) ] * C_q,
i.e. by the SAME empirical list C_q for every large-i block. The
individual sum over y is bounded in coefficient L^1 by a
constant depending only on ell (and on the fact that its mesh in
Lambda_q is FINE, since b_omega^(-1/m) / q >= 2^{2 E_0 H_i} for
large i).
The comparison with the ordinary template uses three facts
jointly: the mesh is much finer than q (subgroup side), the
cocycle phase is nearly constant on cosets (same yv as y), and
the coefficient function is smooth. The upshot is that the
difference in operator norm is o(1) uniformly in the block and
in t.
For each block (i,k), ONE distribution is specified for a single
pair (z, W). Sample the distribution on each undirected edge
independently, keeping the positive-orientation pair and taking
the inverse/adjoint on the reversed edge.
The distribution on one block:
(a) Pick (nu, omega) uniformly in T_{ik}, and pick an integer
n uniformly in {-K_i, ..., K_i}.
(b) Pick x uniformly from a fixed rectangle covering
J_+^flat(Delta_{a_nu^{1/m}} x). Attach sigma_X(x) with
scalar multiplier
n_nu^+ * a_nu^{n_f} * J_+^flat(Delta_{a_nu^{1/m}} x).
(c) If i < I: pick v' from the fixed M-empirical list for
b_omega, and attach sigma(v'), R(sigma(v')), and its
scalar multiplier.
If i >= I: pick y uniformly in the Lambda_q rectangle and
v uniformly in V_q, and attach sigma_Y(y) sigma_Y(v),
R(sigma(v)), and multiplier
n_omega^Lambda * Q_q * b_omega^{n_f}
* J_-^flat(Delta_{b_omega^{1/m}} y).
(d) Multiply the group elements in the indicated order: this
is z. Multiply the scalar multipliers: this is c_e. Keep
the single matrix R(v).
(e) Round c_e to a fixed finite complex grid in the disk of
radius C_epsilon + 1. Set W = c_e^flat * R(v).
The matrix R(v) is unitary, so rounding changes the norm of the
edge weight by at most a prescribed constant. Voltages retain
their full value even if the weight becomes zero.
PROPERTIES OF THE DISTRIBUTIONS.
- Each distribution is FINITE, supported on a finite set.
- The scalar multipliers are uniformly bounded.
- The matrix products are uniformly bounded in norm by
C_eta = C_epsilon + 1.
- The augmented alphabet (original label, matrix weight) has
size O_epsilon(d^{89/32} (1 + log d)^3) = o(d D).
- Term-by-term linearity, plus empirical list cancellation,
plus scalar rounding, gives
sup over t of || E[W rho(z)](t) - h_i(t) h_k(t) p(t) ||
<= epsilon,
uniformly in (i, k).
- Each coordinate of every possible z in a block beginning in
layer i, and of its inverse, is bounded by 2^{C H_i}.
- Every first-factor coordinate interval contains at least
2^{E_0 H_i} points; likewise (for large i) for the
second-factor subgroup intervals.
Fix a nonempty cyclically nonbacktracking base walk w of length
<= C_* H_i / log_2 d, based in layer i. Consider a formal upper
unitriangular matrix on each edge in the support of w.
If SOME block along w has first index j_0 < I, all such first
indices are at most 2 I, so use the first-factor quotient of F
onto U_Z. Otherwise every first index is >= I, and use the
second upper unitriangular quotient.
Either way, some entry of the word (minus identity) is a
nonzero polynomial in the entries of the edge matrices, of
total degree at most m - 1 (because every contributing monomial
has superdiagonal weight <= m - 1).
Assign independent uniform coordinate choices at each edge:
in the first-factor case, from integer intervals of size at
least 2^{E_0 H_j}; in the second-factor case, from a linear
image of the integer Lambda_q points scaled by q. Each
coordinate set has at least 2^{E_0 H_j} points.
SCHWARTZ-ZIPPEL: a nonzero polynomial of total degree r
evaluated on independent uniforms from sets of size at least
L vanishes with probability at most r/L. So a specific walk
has trivial holonomy with probability at most
(m - 1) * 2^{-E_0 min_j H_j}.
The number of walks to test from layer i is at most
(d+1) * 2^{H_i} * sum over 1 <= a <= C_* H_i / log_2 d
of (6D)^a <= 2^{(3 C_* + 3) H_i}.
Since min_j H_j >= (1 - o(1)) H_i and E_0 > 10 (C_* + C_bullet + 1),
the union bound over all such walks is at most C 2^{-2 H_i} for
each layer i, and summing over i gives a bound tending to 0 as
ell -> infinity.
CLOSED LIFTS = CLOSED BASE WALKS. A closed lift projects to a
closed base walk, and nonbacktracking survives; trivial holonomy
depends only on the base walk, not on the lift's starting vertex.
So the tests above exclude every forbidden closed walk in P.
Fix a block (i,k). Let
X_{ik} = sum over positive edges e : a -> b of
( W_e rho(z_e) - E[W_e rho(z_e)] )
be the CENTERED edge sum. The aim is ||X_{ik}|| small, uniformly
in the layers.
MOMENTS. Expand
E[ Tr( hat{X}_{ik}^{2 l} ) ]
where l = ceil(C_2 H_i / log_2 d) is a FIXED even power.
Summands whose walk uses a single undirected edge exactly once
vanish by centering. For the remaining summands, the support has
bounded cycle rank (varying length, bounded b), so the walk-
counting lemma gives at most C_b^l Delta^l walks, with
Delta <= 6D. Because each factor is bounded by 2 C_epsilon and
each compressed test matrix has at most 2^{C_1 H_i} dimensions,
E[Tr(hat{X}_{ik}^{2 l})] <= 2^{C_1 H_i} (C_4 D)^l.
MARKOV AT THRESHOLD epsilon sqrt(d D_{ik}). The finite test in
8.4 contributes a fixed absolute error, which is smaller than
epsilon sqrt(d D_{ik}) / 2 for large ell. Since D/2 <= D_{ik}
<= 2 D, the probability that ||X_{ik}|| exceeds that threshold is
at most
2^{C_1 H_i} (C_5 / d)^l.
Choosing C_2 > 2 (C_1 + 4) gives 2^{(C_1 - C_2/2) H_i} <=
2^{-4 H_i}. Summing over at most three blocks per first index
gives total failure probability tending to 0.
Sum the girth failure bound (8.9) and the block norm failure
bounds (8.10). For large ell the sum is < 1. There is
positive probability of satisfying ALL conditions at once (or,
equivalently, a compactness argument over the countable product
of finite edge distributions stabilises every finite constraint
simultaneously). Fix such an assignment.
Combine the block estimates. Each block's expectation matches
its model block to within epsilon, and each centered deviation
is bounded by epsilon. A width-one block matrix with entries
bounded by epsilon has norm at most 3 epsilon; doubling the
off-diagonal makes it self-adjoint without changing the norm.
Therefore
|| T_P - Pi O Pi || <= 6 epsilon.
Taking epsilon < eta/6 gives (G2) and (G3).
The voltage cover P just sampled is taken (it exists, it has
big girth, and its operator matches the model), and turn it into
a finitely generated torsion-free group Gamma. The Cayley graph
of Gamma will be where the operator T from the theorem lives.
Notation: "M_mark" always means
the number of marked vertices in a plane diagram. It is not the
matrix size m of the unitriangular model. The two are unrelated.
Let z_e in F be the voltage of the positively oriented edge e of
Y. The voltage cover P has vertex set
V(P) = V(Y) x F,
and for every positively oriented edge e : v -> w of Y with
voltage z_e, an edge in P from (v, f) to (w, f z_e). Reversing
gives (w, f) -> (v, f z_e^-1).
Left deck action: delta_a(v, f) = (v, a f). This action is
FREE on V(P), and it is transitive on the lifts of any fixed
base vertex or fixed base path.
GIRTH HYPOTHESIS (what the sampling supplies). There is an absolute
constant C_* such that for every i in Z, no nonempty cyclically
nonbacktracking closed walk in P based in layer i has length at
most C_* H_i / log_2 d.
Let S be the finite positive alphabet of Y. Define
Gamma = < S | label words of all closed walks in P >,
i.e. each closed walk in P contributes its label word as a
relator. This group is finitely generated (S is finite) and is
presented graphically.
The Cayley graph X = Cay(Gamma, S) has the formal vertices g in
Gamma and formal edges (g, sigma) for g in Gamma, sigma in S.
For each connected component C of P, each h in Gamma, and each
fixed base vertex v_0 of C, there is a UNIQUE label-preserving
graph map phi : C -> X with phi(v_0) = h. The path-independence
uses the presentation: any two paths in C from v_0 to a vertex
of C read words that differ by a closed walk, hence by a
relator. The maps phi are not assumed injective at this stage.
It remains to show: every phi is injective on vertices and edges. If
not, a contradiction to minimality follows.
Suppose phi identifies two distinct source vertices. Reading a
source path between them yields a closed image word in X, hence
by the van Kampen Lemma bounds a finite PLANE DIAGRAM with
bounded faces reading relators. Choose among all injectivity
failures one that minimizes, lexicographically, the pair
(J, number of edges),
where J = number of bounded faces, and the diagram's exterior
word is the source path. All source incidences are retained as
part of the diagram.
A REDUCTION LEMMA eliminates obvious slack:
(R1) No bounded face has a freely trivial word (deleting it
would reduce J).
(R2) No edge between two distinct bounded faces has aligned
source incidences (compare before/after deck action and
delete the edge).
(R3) No unmarked vertex of degree one (would be a backtrack,
contradicting edge minimality); no bridge with both
endpoints on a bounded face.
Compress every unmarked degree-two vertex. The result is a
plane graph with ARCS (compressed edges) and marked vertices.
Each arc remembers its whole original edge path.
ARC LENGTH. If an arc on a bounded face has length >= L_i (for
any layer i of an endpoint on the face), then its freely reduced
word determines the projected nonbacktracking path in Y. Both
source lifts of that path then differ by ONE deck transformation,
so the two incidences are aligned -- forbidden by (R2). So
every arc on a bounded face has length < L_i.
FACE CYCLE. If a bounded face had fewer than 20 arcs, its
perimeter would be at most 19 * L_i < 20 L_i = 2000 H_i / log_2 d.
Cancel backtracks, cancel cyclically. Foldedness keeps the
cancellations actual, and the remaining nonempty cyclic path
would contradict the girth hypothesis (2^C_* = 10^4 > 5000).
So each bounded face has at least 20 arcs.
EULER COUNT. Write v for the number of vertices (marked plus
unmarked) and b for the number of arcs. Plane Euler gives
v - b + (J + 1) = 2, i.e. b = v + J - 1. Count the ends of
every arc in two ways. Each arc has two ends, so the sum of
all face lengths is 2b; only bounded faces are counted, and
each has at least 20 arcs by FACE CYCLE, so 20J <= 2b. Each
unmarked vertex has degree at least 3 after suppression by
(R3), so summing degrees over unmarked vertices gives
3(v - M_mark) <= 2b. Substituting v = b - J + 1:
3(b - J + 1 - M_mark) <= 2b, so
b <= 3 J + 3 M_mark - 3.
Combine this with 20J <= 2b (i.e. 10J <= b):
10 J <= b <= 3 J + 3 M_mark - 3, so
7 J <= 3 M_mark - 3.
Therefore J <= (3 M_mark - 3)/7 and
b <= 3 J + 3 M_mark - 3 <= (30/7) M_mark < 6 M_mark.
INJECTIVITY. Take an injectivity failure with M_mark = 1.
The bound b <= 3 J + 3 M_mark - 3 becomes b <= 3 J, and
10 J <= b then forces 10 J <= 3 J, hence J = 0.
The diagram is therefore a single tree, and its exterior word
(= the source path between the two distinct source vertices)
is freely trivial, because there are no bounded faces to read
relators from. In the folded graph Y, a nonbacktracking path
has a freely reduced word: two consecutive labels s, t satisfy
s != t^{-1}, since otherwise the second edge would be the
unique edge at that vertex with label t, forcing it to be the
reverse of the first edge, a backtrack. A freely reduced word
can only be freely trivial if it is empty. So the source path
is empty, meaning its endpoints coincide; that contradicts the
chosen injectivity failure (they were assumed distinct).
Consequently every component map phi is injective, and the same
argument applied to edges handles the edge case. Since phi is
injective, the components of P embed genuinely into
the Cayley graph X.
With a component C, a map phi, and a base vertex fixed,
"indexed copies" of X are defined up to a deck alignment:
(C, phi) ~ (delta_a C, phi delta_a^-1), a in F.
An INDEXED COPY Q therefore remembers its source component and
its source vertices up to this alignment, not just its image.
Adjoin for each indexed copy Q one CONE CENTER c_Q and a spoke
from c_Q to each vertex of Q. Let X-hat be the resulting cone
graph.
THIN TRIANGLES. Lemma (short chain fillings): every edge loop
in X-hat of length n is a sum of at most 12n oriented loops of
length at most 4. From such a filling, every geodesic triangle
in X-hat is D_0-thin, with D_0 = 10^6.
WELL-ORDER. Fix one base point o in X. Order the indexed
copies first by grid distance d_Xhat(c_Q, o), and then by an
enumeration tie-break. For each Q choose one geodesic from
c_Q to o and let u in Q be its first vertex past c_Q. This
"root vertex" u will anchor the trimming ball.
AVOIDANCE. Lemma: if a path in X-hat of length at most L joins
u, x in Q avoiding c_Q, then the INTRINSIC distance in Q
satisfies d_Q(u, x) <= 24 (L + 1) L_i.
BALL CONTAINMENT. For any vertex x in Q that ALSO belongs to
some earlier copy Q', a short path in X-hat from u to x avoids
c_Q, of length <= L* = 4 D_0 + 8. By avoidance,
d_Q(u, x) <= 24 (L* + 1) L_i.
So define
B(Q) = { v in Q : d_Q(u, v) <= R_Q },
R_Q = ceil( 25 (L* + 1) L_i ).
Every earlier-overlap vertex of Q lies in B(Q). The ball B(Q)
is a TREE (else a short cycle in Q, contradicting girth after
proper scaling), and no outside vertex has two incidences into
B(Q).
Define the ASSIGNED DOMAIN of Q by
D_Q = V(Q) minus (union over earlier copies R < Q of V(R)).
These are pairwise disjoint, and V(Q) ∖ D_Q is contained in
B(Q).
Delete from X every edge of Q whose two endpoints both lie in
D_Q (for every Q). The remaining graph is a FOREST.
Reason: if a circuit existed, its image in the Cayley graph
would give a nonzero cycle. Directness of the embedding (below)
means the LATEST copy Q with a nonzero component would have a
cycle supported on the tree B(Q), which forces that component to
be zero -- a contradiction.
There is a canonical bijection
(Q, x) : Q is an indexed copy, x in V(Q)
<--> ( x, v ) : x in Gamma, v in V(Y),
where v is the base vertex under the unique source vertex of the
embedding. In particular, for a fixed x and v there is EXACTLY
ONE incidence at x of type v.
Consequence: the equivariant vertex space
oplus over Q of l^2(V(Q))
is canonically identified with
l^2(Gamma) (x) l^2(V(Y)),
and with a further C^N factor if matrix indices are used.
STABILIZERS. If h in Gamma stabilizes an indexed copy, its
action corresponds to a deck transformation delta_a in F
preserving the representative source component, and the
correspondence h <-> a is an INJECTION. F is torsion-free by
construction, so the stabilizer has no finite-order element.
CONE COMPLEX. Let Z be the two-dimensional cellular complex
obtained by gluing each cone on Q into X. Its augmented chain
complex
0 -> C_2(Z;k) -> C_1(Z;k) -> C_0(Z;k) -> k -> 0
is EXACT for every field k.
Why: X is connected and each cone attached to it, so exactness
at C_0 and k is immediate. For exactness at C_1, take a cycle
of X-hat, its spokes sum to zero per center, and connectedness
of each copy permits replacement of that spoke chain by a finite
combination of edges on Q; then the residual X-cycle is a finite
sum of copy cycles by directness, each of which bounds the two-
cell faces on its own copy. For injectivity at C_2, a finite
sum of triangles determines one edge chain c_Q per copy, and
vanishing of the boundary says boundary(c_Q) = 0 in each copy;
directness forces every c_Q to be zero.
TORSION CONTRADICTION. Suppose Gamma has an element of finite
order. Some power generates a subgroup C_p of prime order p.
Working over k = F_p and using freeness of the cell action
(9.6), every C_j(Z; F_p) is a FREE MODULE over A = F_p[C_p].
The exact chain complex above then gives a FREE RESOLUTION of
the trivial module F_p of length 2 over A.
But F_p[C_p] has a PERIODIC free resolution of INFINITE length:
... -> A --z--> A --z^(p-1)--> A --z--> A --z^(p-1)--> ... -> F_p.
Tensoring the length-2 resolution with F_p over A gives one copy
of F_p in degrees 0, 1, 2, then zero after that. Tensoring the
periodic resolution gives one copy of F_p in EVERY degree. But
any two free resolutions of F_p over A are chain-homotopy
equivalent, so their homology after tensoring with F_p must
coincide. Contradiction.
Therefore Gamma has no nonidentity finite-order element. Gamma
is torsion-free.
Combining the embedding, the disjoint domains with residual
forest, the incidence bijection, and torsion-freeness proves the
geometric theorem: the voltage cover P produces a finitely
generated torsion-free group Gamma with indexed copies whose
geometry is under full control.
The constants are as follows:
D_0 = 10^6,
L* = 4 D_0 + 8 (about 4 * 10^6),
C_* = 10^7 (L* + 1),
C_bullet = 2 * 10^4 (L* + 1).
They are absolute and are fixed BEFORE ell is chosen. This is
what makes the dependency ledger of parameter choices correct.
A cover P now exists whose operator matches the model band.
There is Gamma, finitely generated and torsion-free, with
copies of P covering its Cayley graph. The remaining job: turn
the band on P into a spectral band for the actual FINITE
group-algebra operator T on Gamma, and bound the unnormalized
trace of its upper projection.
The sampled cover operator T_P satisfies
|| T_P - Pi O Pi || <= eta,
where Pi is the projection onto surviving vertices and O is the
model operator, whose band E_*(t) has eigenvalue 1 on the
symmetric constants and eigen-at-most 1 - chi on the orthogonal
complement.
Take ell large enough that beta_ell (deleted fraction) also
satisfies 20 sqrt(beta_ell) <= alpha / 2, where alpha = chi / 1000.
Fix eta <= alpha / 2. Let
theta = C_chi eta, C_chi = 4 / chi, r_0 = chi / 3.
The choices also satisfy theta <= 1/2 and 2^{C_bullet} theta^2 <= 1/2,
which just amounts to eta small enough (a fixed choice).
Both are used repeatedly. Both are stated for a general complex
Hilbert space; the operator content of the transfer to the Cayley graph is the same in
each use.
COMPRESSION LEMMA. Let A = A* be an operator on H with ||A||
<= 2, and let E be a reducing projection (AE = EA) with
|| (A - I) E || <= a, A on (1 - E)H <= (1 - b) I,
where a >= 0 and 0 < b < 1. Let J be any orthogonal projection
with eps := || (1 - J) E || <= 1/2. Then
(a) JE has closed range; write E^J for its range projection.
(b) On J H define B_J = E^J + (J - E^J) A (J - E^J). Then
|| J A J - B_J || <= a + 20 eps, || B_J || <= 2,
B_J on (J - E^J) H <= (1 - b) I.
(c) There is a partial isometry V from E H to E^J H, with
V* V = E, V V* = E^J, and || V - E || <= 2 eps.
(d) If A, E, J commute with a unitary (or projective unitary)
action, then so do V, E^J, and B_J.
(e) If there is an identity trace with Tr(X* X) = Tr(X X*) for
every commuting bounded X, then E and E^J have equal identity
trace.
All statements include the case E = 0.
Proof. For x in E H, use E x = x and ||(1 - J) x||^2 <= eps^2
||x||^2 to get
<x, E J E x> = ||J x||^2 >= (1 - eps^2) ||x||^2.
So (1 - eps^2) E <= E J E <= E on E H, and E J E is invertible
inside the E corner. Define
V = J E (E J E)^{-1/2}
on E H. Then V* V = E by the functional calculus identity
(EJE)^{-1/2} (EJE) (EJE)^{-1/2} = E, and V V* = E^J because the
range of V is J E H. Since the spectrum of E J E lies in
[1 - eps^2, 1], the same calculus gives
|| (E J E)^{-1/2} - E || <= 2 eps^2, so
|| V - E || <= || J E - E || + || J E || * 2 eps^2
<= eps + 2 eps^2 <= 2 eps.
This proves (a) and (c).
For (b): if y in (J - E^J) H, then y is orthogonal to J E H and
y = J y, so <y, E x> = <y, J E x> = 0 for every x; that is,
E y = 0. In particular A E lands in E H and (J - E^J) A E = 0.
Transport A to the E^J corner by V: V* A V = E^J +
V* (A - E) V, so ||V* A V - E^J|| <= a + 2 ||A|| ||V - E|| <= a +
8 eps. And
|| (J - E^J) A V ||
= || (J - E^J) A (V - E) || <= 4 eps,
using (J - E^J) A E = 0. In the orthogonal splitting
J H = E^J H disjoint-union (J - E^J) H, both J A J and B_J are
2-by-2 blocked. Their (1,1) blocks agree on the upper space up
to a + 8 eps; their (1,2) and (2,1) blocks are adjoints of each
other and each of norm at most 4 eps; their (2,2) blocks agree
exactly. Hence
|| J A J - B_J || <= (a + 8 eps) + 2 (4 eps) <= a + 20 eps.
The B_J upper bound follows from the same orthogonal form and
the hypothesis on A, and ||B_J|| <= 2 follows directly.
For (d): every step used the functional calculus on E J E and
the polar decomposition, and both are compatible with any
equivariance A, E, J already share.
For (e): apply the adjoint-square identity
Tr(V* V) = Tr(V V*) to V; the two sides are Tr(E) and Tr(E^J).
PERTURBATION LEMMA. Suppose B = B* has a reducing projection F
with B F = F, and B on (1 - F) H has spectrum in [-2, 1 - b] for
some 0 < b < 1. Let r_0 satisfy 0 < r_0 <= b/2 and r_0 < 1. If
A = A* and ||A - B|| <= u < r_0, then:
(a) The circle C_{r_0} = {z : |z - 1| = r_0} lies in the
resolvent set of both A and B.
(b) Let F_A be the contour projection of A around C_{r_0}. Then
|| F_A - F || <= u / (r_0 - u),
spec(A on F_A H) lies in [1 - u, 1 + u],
spec(A on (1 - F_A) H) lies in [-2 - u, 1 - b + u].
(c) If u < r_0/2, F_A and F are equivalent by a partial isometry
belonging to the algebra generated by them. If A and B commute
with a unitary action, that partial isometry does too, and F_A
and F have equal identity traces.
Proof. Any z on C_{r_0} is at distance at least r_0 from
spec(B), because the complementary spectrum of B is contained in
[-2, 1 - b] and r_0 <= b/2. So || (z - B)^{-1} || <= 1/r_0
there. The Neumann series
(z - A)^{-1} = sum over j >= 0 of
((z - B)^{-1} (B - A))^j (z - B)^{-1}
converges geometrically, because ||(z - B)^{-1}|| ||A - B|| <=
u / r_0 < 1, with sum bound
(1/r_0) / (1 - u/r_0) = 1/(r_0 - u). This proves (a).
The resolvent identity
(z - A)^{-1} - (z - B)^{-1}
= (z - A)^{-1} (A - B) (z - B)^{-1}
integrates around C_{r_0} to give
F_A - F = (1/2 pi i) integral over C_{r_0} of
(z - A)^{-1} (A - B) (z - B)^{-1} dz.
The integrand has norm at most (1/(r_0 - u)) u (1/r_0), and the
circle has length 2 pi r_0, so || F_A - F || <= u/(r_0 - u), which
is the first display of (b). If a real t satisfies
dist(t, spec B) > u, the same Neumann trick shows t is away from
spec A. Since spec B on F H is {1} and spec B on (1 - F) H lies
in [-2, 1 - b], the two interval statements of (b) follow.
For (c): if u < r_0/2 then || F_A - F || <= u/(r_0 - u) < 1. For
y in F H,
|| F_A y || >= (1 - ||F_A - F||) ||y||,
so F_A F is bounded below on F H. Its range is all of F_A H: a
vector x in F_A H orthogonal to F_A F H would satisfy F x = 0
(shift by one line of the same argument), and then
||x|| = ||(F_A - F) x|| <= ||F_A - F|| ||x||, contradiction. So
the polar normalization
F_A F (F F_A F)^{-1/2}
is a partial isometry from F H to F_A H, built from F and F_A
alone, preserving common equivariance. The identity-trace
equality is again the adjoint-square identity.
Let E_P be the spectral projection of T_P obtained by integrating
the resolvent over the circle |z - 1| = r_0 = chi/3. Then
||T_P|| <= 2,
|| (T_P - I) E_P || <= alpha,
T_P on (1 - E_P) H <= (1 - chi + alpha) I.
Proof. Set a = 0 and b = chi in the compression lemma,
with A = O, E = E_*, and J = Pi. Its three hypotheses hold:
|| (O - I) E_* || = 0 because O E_* = E_* (Section 8.1); O on
(1 - E_*)H is at most (1 - chi)I by the same model band; and
eps := || (1 - Pi) E_* || <= sqrt(beta_ell) by the compression
estimate, with sqrt(beta_ell) <= 1/2 for large ell.
The compression lemma gives a projection E_*^Pi (the range of
Pi E_*) on Pi H and an operator B_Pi on Pi H with
|| Pi O Pi - B_Pi || <= 20 sqrt(beta_ell),
B_Pi on (Pi - E_*^Pi)H <= (1 - chi)I.
Since ||O|| <= 1 (Section 8.1) and B_Pi is the direct sum of 1
on E_*^Pi H and (Pi - E_*^Pi)O(Pi - E_*^Pi) on the complementary
corner of Pi H, ||B_Pi|| <= 1.
Extend B_Pi by zero on (1 - Pi)H, obtaining an operator B on H.
The projection E_*^Pi reduces B, and B on (1 - E_*^Pi)H lies
between -1 and 1 - chi. The cover estimate closes the
comparison:
|| T_P - B ||
<= || T_P - Pi O Pi || + || Pi O Pi - B_Pi ||
<= eta + 20 sqrt(beta_ell)
<= alpha/2 + alpha/2 = alpha.
Set u = alpha. Since 0 < u = chi/1000 < chi/3 = r_0 <= chi/2 and
r_0 < 1, the perturbation lemma applies to A = T_P and B.
Let E_P be the contour projection of T_P around C_{r_0}. The
perturbation lemma gives
|| E_P - E_*^Pi || <= u / (r_0 - u), which is small;
spec(T_P on E_P H) lies in [1 - alpha, 1 + alpha];
spec(T_P on (1 - E_P)H) lies in [-1 - alpha, 1 - chi + alpha];
|| T_P || <= ||B|| + u <= 1 + alpha < 2.
The three displays of the statement follow immediately.
For almost every t in the circle T = R / Z,
tr_id E_P(t)
= tr_id p(t) if 0 < t < delta,
= 0 otherwise.
Proof. Work fiberwise in the central Fourier decomposition.
The direct integral respects resolvents and contour integrals,
so E_P(t) is the contour projection of T_P(t) for almost every t.
OUTSIDE THE WINDOW. By the off-window bound, ||T_P(t)|| <= eta < r_0
almost everywhere. So the spectrum of T_P(t) lies in
[-eta, eta], which is at distance r_0 - eta > 0 from C_{r_0},
and the contour integral vanishes.
INSIDE THE WINDOW. Throughout this paragraph fix a t in
(0, delta) at which the above fiberwise identities hold. The
same comparison as 10.2 gives ||T_P(t) - B(t)|| <= alpha, with
B(t) extended by zero off Pi, and the operator
hypotheses are satisfied with a = 0, b = chi, and
u = alpha < r_0/2 = chi/6.
Apply the compression lemma, part (e), to A = O(t),
E = E_*(t), J = Pi. It gives
tr_id E_*(t) = tr_id E_*^Pi(t).
Apply the perturbation lemma, part (c), to A = T_P(t) and
B = B(t). It gives an equivariant partial isometry V(t) with
V(t)* V(t) = E_*^Pi(t) and V(t) V(t)* = E_P(t), so by the
adjoint-square identity of the identity trace,
tr_id E_*^Pi(t) = tr_id E_P(t).
Combining with the model-band trace
(tr_id E_*(t) = tr_id p(t)), this gives
tr_id E_P(t) = tr_id p(t) for 0 < t < delta.
The trace identity for almost every t follows by measure-
theoretic density: both sides are measurable and finite, and
the equalities proved above hold on the full-measure set where
the fiberwise operators are defined.
NONVANISHING. The magnetic shift shows tr_id p(t) is at least a positive
constant times t^{n_f} (delta - t)^{n_f} on 0 < t < delta, so
strictly positive there. The window (0, delta) has positive
measure. Since tr_id E_P(t) = tr_id p(t) on that window, and
tr_id E_P(t) = 0 outside, so tr_id E_P > 0. A projection
with positive identity trace is nonzero, so E_P != 0.
DIAGONAL INVARIANCE. The operator T_P is F-equivariant: its
edge voltages and its matrix weights are unchanged by left
translation. Its resolvent and contour integral are therefore
F-equivariant too. In particular, for every f in F and every
base vertex v of Y,
< E_P delta_{(v,f)}, delta_{(v,f)} >
= < E_P delta_{(v,1)}, delta_{(v,1)} >.
Therefore the C^N-matrix trace of the diagonal of E_P at (v, f)
depends only on the base vertex v.
For a surviving base vertex v, define
e_v = Tr_{C^N}( E_P( (v, 1_F) ) ) >= 0,
the matrix-identity diagonal of E_P at v. Let w_i = 2^{C_bullet H_i}
be the layer weight. Define the weighted size
S = sum over surviving base vertices v of w_{i(v)} * e_v.
LOCALIZATION. Write A_0(t) = Pi O(t) Pi and
Delta(t) = T_P(t) - A_0(t). The cover estimate gives
||Delta(t)|| <= eta. The compression lemma with a = 0 and b = chi,
applied to the model band, gives
||A_0(t) - B(t)|| <= 20 sqrt(beta_ell) <= alpha/2,
where B(t) is the compression-lemma operator on Pi H. B(t) has
spectrum in [-1, 1-chi] together with eigenvalue 1 at the
reducing projection E_*^Pi(t).
Bound the resolvent of A_0(t) on the circle C_{r_0} = { |z - 1|
= r_0 }. Any z on the circle is at distance at least r_0 from
spec B(t), so || (z - B(t))^{-1} || <= 1/r_0. Since
||A_0(t) - B(t)|| <= alpha/2 < r_0, the Neumann series gives
R_0(z,t) := (z - A_0(t))^{-1},
|| R_0(z,t) || <= (r_0 - alpha/2)^{-1} <= C_chi = 4/chi.
The operator A_0(t) is supported on the active layers J(t), so
its resolvent R_0(z,t) equals z^{-1} I on the orthogonal sum of
the other layers and has no matrix entries between that sum and
J(t). The resolvent series for T_P(t) in terms of A_0(t) is
(z - T_P(t))^{-1}
= sum over n >= 0 of R_0(z,t) (Delta(t) R_0(z,t))^n,
and it converges because ||Delta(t) R_0(z,t)|| <= eta C_chi
= theta < 1.
Let k = dist(i, J(t)) and P_i be the projection to both sides of
layer i (including all transverse and matrix coordinates). For
n < k, every layer path touched in P_i R_0(z,t) (Delta R_0)^n
stays outside J(t); each resolvent factor along such a path acts
as z^{-1} I, so by induction on n,
P_i R_0(z,t) (Delta(t) R_0(z,t))^n
= z^{-n-1} P_i Delta(t)^n (n < k).
The contour integral of z^{-n-1} around C_{r_0} is zero because
the circle does not enclose the origin. Therefore
P_i E_P(t) = (1 / 2 pi i) integral over C_{r_0} of
sum_{n >= k} P_i R_0 (Delta R_0)^n dz.
Bound the geometric tail:
|| P_i E_P(t) ||
<= r_0 C_chi sum_{n >= k} theta^n
<= r_0 C_chi theta^k / (1 - theta) <= 4 theta^k,
using theta <= 1/2 and r_0 C_chi = (chi/3) * (4/chi) = 4/3
combined with 1/(1 - theta) <= 2. This is the stated decay in
k = dist(i, J(t)). For k = 0 there is no vanishing segment to
remove; the same bound is valid.
WEIGHTED TRACE BOUND. Fix t in (0, delta). Write tr_id for the
identity trace (sum over base and matrix indices, or over
its central Fourier fiber; the countable amplification is handled
by the adjoint-square identity-trace lemma). Since P_i and E_P(t) are equivariant, the
adjoint-square identity and positivity give
tr_id(P_i E_P(t) P_i)
= tr_id(E_P(t) P_i E_P(t))
<= || P_i E_P(t) ||^2 tr_id(E_P(t))
<= 16 theta^{2 dist(i, J(t))} tr_id p(t).
The middle line uses 0 <= E_P(t) P_i E_P(t) <= ||P_i E_P(t)||^2
E_P(t); the last uses 10.3.
It remains to bound the weighted sum. Since |H_i - H_j| <= |i -
j| for every pair of layer indices, w_i = 2^{C_bullet H_i}
satisfies w_i <= w_j 2^{C_bullet |i - j|}. Assign every integer i
to a closest point of the nonempty finite set J(t); because
|J(t)| <= 2, at most two integers at each positive distance are
assigned to a given j in J(t). Therefore
sum_i w_i theta^{2 dist(i, J(t))}
<= 2 max_{j in J(t)} w_j *
( 1 + 2 sum_{k >= 1} (2^{C_bullet} theta^2)^k )
<= 6 max_{j in J(t)} w_j,
using 2^{C_bullet} theta^2 <= 1/2 and
sum_{k>=1} x^k = x/(1-x) <= 1 when x <= 1/2.
Multiply the per-layer bound by w_i and sum over i. For each t in
the open window,
sum over surviving base vertices v of w_{i(v)} e_v(t)
<= 16 tr_id p(t) sum_i w_i theta^{2 dist(i, J(t))}
<= 96 max_{j in J(t)} w_j tr_id p(t) <= 96 mu_ell,
where e_v(t) is the C^N matrix trace of the v-diagonal of
E_P(t), and mu_ell = sup_{0<t<delta, j in J(t)}
w_j tr_id p(t) is the small weighted trace of the layer window. Off the
window E_P(t) = 0, so the same bound holds trivially.
FIBER AVERAGE. Central Fourier decomposition identifies e_v with
the integral over t of e_v(t). Tonelli's theorem applies to the
nonnegative diagonal, so
S = sum over surviving v of w_{i(v)} e_v
= integral over t in [0,1] of
( sum over surviving v of w_{i(v)} e_v(t) ) dt
<= 96 mu_ell.
Since mu_ell -> 0 as ell -> infinity, S -> 0.
Use the finite alphabet S (original label plus matrix
weight tag). For sigma in S with matrix weight W_sigma and
degree normalizer D_sigma = D_{ik}, define
w_sigma = (d D_sigma)^{-1/2} W_sigma.
The actual Cayley operator is
T = sum over sigma in S of
( w_sigma * lambda(sigma)
+ w_sigma^* * lambda(sigma^{-1}) ) .
T is a finite sum of matrix coefficients times left-translations.
It is self-adjoint and belongs to M_N( C_r*(Gamma) ).
Each indexed copy Q inherits a copy operator T_Q (using only its
own edges) and an upper projection E_Q. The diagonal of E_Q at
a vertex u in Q is e_v where v is u's base vertex (from the
copy diagonal).
BALL TRIMMING. For the assigned domain D_Q and trimming
ball B(Q),
|| 1_{B(Q)} E_Q ||_{HS}^2 <= S.
Proof. On H_Q = l^2(V(Q)) (x) C^N let 1_{B(Q)} be the vertex
projection onto the trimming ball. Since E_Q is an orthogonal
projection, E_Q^* E_Q = E_Q, so
|| 1_{B(Q)} E_Q ||_HS^2
= Tr( E_Q 1_{B(Q)} E_Q )
= Tr( 1_{B(Q)} E_Q 1_{B(Q)} )
= sum over u in B(Q) of tr_{C^N}( E_Q(u, u) ).
The diagonal identity gives
tr_{C^N}( E_Q(u, u) ) = e_{type(u)}
for every u in Q, where type(u) is the base vertex under the
embedding Q -> X. A lift u of the base vertex v lies over the
same layer as v: the layer is preserved by the graph embedding.
The weight estimate for balls says that when the ball B(Q)
lies over layer i, its whole vertex set satisfies
|V(B(Q))| <= w_i = 2^{C_bullet H_i}.
So the number of lifts of a fixed base vertex v in B(Q) is at
most |V(B(Q))| <= w_{i(v)}. Therefore
|| 1_{B(Q)} E_Q ||_HS^2
= sum over u in B(Q) of e_{type(u)}
<= sum over surviving base vertices v of
( # of u in B(Q) with type(u) = v ) e_v
<= sum over surviving base vertices v of w_{i(v)} e_v
= S.
CONSEQUENCE. If S <= 1/4, then the compression of T_Q to
l^2(D_Q) (x) C^N is within alpha + 20 sqrt(S) of an operator
C_Q that satisfies
C_Q = 1 on a projection F_Q equivalent to E_Q,
||C_Q|| <= 2,
C_Q <= (1 - chi + alpha) I on (1 - F_Q) H_Q.
In particular F_Q != 0 whenever E_Q != 0.
Form the orthogonal direct sums
C = oplus_Q C_Q + 0 on unassigned vertices,
T_D = oplus_Q T_Q|_{D_Q} + 0 on unassigned vertices,
F_D = oplus_Q F_Q + 0 on unassigned vertices.
The assigned domains D_Q are disjoint, so both C and T_D are
bounded operators on l^2(Gamma) (x) C^N. From 10.6,
|| T_D - C || <= 2 alpha.
RESIDUAL EDGES. The difference T - T_D is exactly the matrix
adjacency on the residual Cayley edges (edges NOT internal to
any assigned D_Q). By disjointness of the assigned domains those edges form a FOREST.
FOREST NORM LEMMA. A self-adjoint matrix adjacency on a
countable forest of maximum degree m_1 and matrix edge norms at
most w_1 has norm at most 2 w_1 sqrt(m_1).
Proof. Root each connected component of the forest at an
arbitrary vertex and orient every edge from parent to child.
Write B for the half-adjacency from the child coordinate to the
parent coordinate:
(B xi)(x) = sum over children y of x of w_{xy} xi(y),
where w_{xy} is the matrix weight between x and y. Then the
forest adjacency is B + B^*.
Bound B on finite-support vectors. For each vertex x, Cauchy-
Schwarz on the sum over children y of x gives
|| sum over children y of x of w_{xy} xi(y) ||^2
<= ( sum over children y of x of w_1^2 )
* ( sum over children y of x of ||xi(y)||^2 )
<= w_1^2 m_1 * sum over children y of x of ||xi(y)||^2.
Summing over x and using that a nonroot vertex has exactly one
parent,
|| B xi ||^2
<= w_1^2 m_1 * sum over x of sum over children y of x of
|| xi(y) ||^2
= w_1^2 m_1 * sum over nonroot y of || xi(y) ||^2
<= w_1^2 m_1 * || xi ||^2.
So || B xi || <= w_1 sqrt(m_1) || xi ||, i.e. ||B|| <= w_1
sqrt(m_1). Bounded extension lifts this from finitely supported
vectors to all of l^2. Then
|| A || = || B + B^* || <= 2 || B || <= 2 w_1 sqrt(m_1).
The countable number of components and the infinite dimension of
the ambient Hilbert space cause no issue: each vertex has a
finite-distance parent, so B is well defined, and the operator-
norm estimate above is uniform in the tree.
Applied to T - T_D, with m_1 <= 2 |S| and w_1 <= sqrt(2) C_eta /
sqrt(dD):
|| T - T_D || <= 4 C_eta sqrt( |S| / (dD) ) =: f_ell.
Since |S| = o(dD), f_ell -> 0 as ell -> infinity. Increase ell
so f_ell <= alpha.
Then ||T - C|| <= 3 alpha.
Recall C is self-adjoint, equals 1 on F_D, and is at most
1 - chi + alpha on the orthogonal complement of F_D. By 10.7,
||T - C|| <= 3 alpha.
SPECTRUM OF C. Since C = C* and C = 1 on F_D while C <= 1 -
chi + alpha on (1 - F_D)H, the spectrum of C lies in
[-||C||, 1 - chi + alpha] together with the eigenvalue 1 at F_D.
SPECTRUM OF T. Weyl's inequality: the spectral slope of T is at
most ||T - C|| away from the spectrum of C. So
spectrum(T) contained in
(-infinity, 1 - chi + 4 alpha] UNION [1 - 3 alpha, 1 + 3 alpha].
NONVANISHING. Since F_D = oplus_Q F_Q and each F_Q != 0 by the trimming estimate,
the upper interval [1 - 3 alpha, 1 + 3 alpha] is nonempty.
GAP. The number 1 - chi/4 lies strictly between the two
intervals. Indeed with alpha = chi/1000,
1 - chi + 4 alpha = 1 - (996/1000) chi < 1 - chi/4,
1 - chi/4 = 1 - 0.25 chi < 1 - 0.003 chi
= 1 - 3 alpha.
p_0. The spectral indicator
p_0 = 1_{[1 - chi/4, infinity)}(T)
is therefore a well-defined projection. It is nonzero because
its upper band [1 - chi/4, infinity) contains the whole range of
F_D, which is nonzero. It belongs to M_N(C_r*(Gamma)) by the
continuous functional calculus applied to the self-adjoint
element T of that algebra.
This is the subtle part: how to bound the unnormalized trace of
p_0 from above.
Use ALL the indexed copies at once. The equivariant vertex
space is
L = oplus_Q l^2(V(Q)) (x) C^N
= l^2(Gamma) (x) l^2(V(Y)) (x) C^N = H (x) l^2(V(Y))
(incidence identification).
Let E = oplus_Q E_Q. Its identity trace is
Tr_L(E) = S_0 = sum over surviving base vertices v of e_v
<= S < infinity.
So the total upper space of all copies has small trace.
RESTRICTION MAP. Define A : H -> L by
A xi = ( E_Q( xi|_{V(Q)} ) )_Q,
with xi|_{V(Q)} extended by zero outside V(Q) in each copy Q.
BOUNDEDNESS OF A. Split V(Q) = D_Q disjoint-union I_Q, where
I_Q = V(Q) minus D_Q lies inside B(Q). The D_Q are pairwise
disjoint and each E_Q is a contraction, so
sum over Q of || E_Q( xi|_{D_Q} ) ||^2
<= sum over Q of || xi|_{D_Q} ||^2
<= ||xi||^2.
The I_Q parts are governed by the next lemma.
LEMMA (LOST-RESTRICTIONS). With I_Q = V(Q) minus D_Q,
sum over Q of || E_Q( xi|_{I_Q} ) ||^2 <= S ||xi||^2.
Proof. Write v(Q,u) = type_Q(u) for the base type of an incidence
and i(v) for the layer of a base vertex v. For a vector z in C^N
supported at u in V(Q), the copy-diagonal identity (10.3) and
positivity of the diagonal matrix give
|| E_Q( delta_u (x) z ) ||^2
= < E_Q(u,u) z, z >
<= e_{v(Q,u)} ||z||^2.
Since I_Q is finite, Cauchy-Schwarz on its sum gives
|| E_Q( xi|_{I_Q} ) ||^2
<= |B(Q)| * sum over u in I_Q of e_{v(Q,u)} ||xi(u)||^2.
The weight estimate for balls says the whole ball B(Q) has size
at most w_{i(u)} for every vertex u of the ball; and the layer of
a lift u in V(Q) is the layer of its base type v(Q,u). So
|B(Q)| <= w_{i(v(Q,u))} uniformly. Rearranging nonnegative
terms,
sum over Q of || E_Q( xi|_{I_Q} ) ||^2
<= sum over u in Gamma_base of ||xi(u)||^2 *
( sum over { Q : u in I_Q } of
w_{i(v(Q,u))} e_{v(Q,u)} ).
By the incidence bijection, for each fixed group vertex
u and each base vertex v in V(Y) there is exactly one indexed
copy Q with u in V(Q) and type_Q(u) = v. Therefore the
parenthesized sum over Q equals
sum over surviving base vertices v of w_{i(v)} e_v = S.
Substituting,
sum over Q of || E_Q( xi|_{I_Q} ) ||^2
<= S * sum over u in Gamma_base of ||xi(u)||^2
= S ||xi||^2.
Combining the D_Q and I_Q estimates and taking square roots,
|| A xi || <= sqrt(1 + S) ||xi|| <= (1 + sqrt(S)) ||xi||,
so ||A|| <= 1 + sqrt(S). Its kernel K is closed and invariant:
A is equivariant because left Gamma-translation permutes the
indexed copies and the E_Q with them.
For xi in K, E_Q(xi|_{V(Q)}) = 0 for every Q, so
E_Q(xi|_{D_Q}) = - E_Q(xi|_{I_Q}). Norms therefore agree, and
LOST-RESTRICTIONS gives
sum over Q of || E_Q( xi|_{D_Q} ) ||^2
= sum over Q of || E_Q( xi|_{I_Q} ) ||^2
<= S ||xi||^2.
SANDWICH. Use the sum-over-Q bound just obtained: for xi in K,
sum over Q of || E_Q( xi|_{D_Q} ) ||^2 <= S ||xi||^2. The local
spectral estimate gives, for every vector y on a copy Q,
< T_Q y, y > <= (1 - chi + alpha) || y ||^2
+ chi || E_Q y ||^2.
Apply this to the zero-extension of xi|_{D_Q}, sum over the
pairwise disjoint domains, use the S-bound above, and include
the unassigned part via its norm bound (the coefficient
1 - chi + alpha is positive). The forest error f_ell is at
most alpha by 10.7. Therefore
< T xi, xi >
<= (1 - chi + alpha + chi S + f_ell) ||xi||^2
<= (1 - chi + 3 alpha) ||xi||^2,
because S <= 1/1000 and f_ell <= alpha.
On the OTHER HAND, on p_0 H the spectral split gives
< T xi, xi > >= (1 - 3 alpha) ||xi||^2.
Since 1 - 3 alpha > 1 - chi + 3 alpha (with alpha = chi/1000), no
nonzero xi can satisfy both inequalities. Therefore
p_0 H ∩ K = {0}.
KERNEL-COMPLEMENT SIZE. Polar-decompose the restriction map
A = V |A| of 10.9. This gives an equivariant partial isometry
V : H -> L with V* V = P_{K^perp} and V V* the projection onto
the closure of ran A, which is contained in the range of E.
The adjoint-square identity and monotonicity then give
Tr_H( P_{K^perp} ) = Tr_H( V* V )
= Tr_L( V V* )
<= Tr_L( E ) = S_0.
The middle equality uses the adjoint-square identity across
the two Hilbert spaces H and L: V* V acts on H, V V* on L,
and their identity traces match.
INJECTIVITY OF P_{K^perp} ON p_0 H. Because p_0 H ∩ K = {0}, the
map P_{K^perp} : p_0 H -> K^perp is injective. Polar-decompose
it as V' : p_0 H -> K^perp, with V'* V' = p_0 and V' V'* a
projection on K^perp bounded by P_{K^perp}. Then by the adjoint-
square identity and monotonicity,
Tr_H( p_0 ) = Tr_H( V'* V' )
= Tr_H( V' V'* )
<= Tr_H( P_{K^perp} )
<= S_0.
Since S_0 <= S and S < 1/2 (ell well past S <= 1/4), the upper
bound of the trace target follows.
STRICTLY POSITIVE. A nonzero equivariant projection on
l^2(Gamma) x C^N has strictly positive identity trace. If every
identity-diagonal entry were zero, then the projection's columns
at the identity would be zero; equivariance would make every
group translate of those columns zero, forcing the projection
itself to be zero. Since p_0 != 0 and the identity trace
of a nonzero equivariant projection is positive,
Tr_H( p_0 ) > 0.
CONCLUSION. Combining,
0 < tau_{Gamma,N}(p_0) = Tr_H( p_0 ) <= S_0 <= S
< 1/2.
The construction has produced:
a finitely generated torsion-free group Gamma;
a projection p_0 in M_N( C_r*(Gamma) );
with 0 < tau_{Gamma,N}(p_0) < 1/2.
That is EXACTLY the matrix target that the scalar reduction needed.
What has been assembled:
- a finitely generated torsion-free group Gamma;
- an integer N = q^{n_f};
- a matrix projection p_0 in M_N(C_r*(Gamma));
- with 0 < tau_{Gamma,N}(p_0) < 1/2.
That is exactly the "matrix target" that the scalar reduction needs.
Apply Step 1 with Lambda = Gamma and p = the matrix projection
p_0. Let
G_proj = Gamma * F_N
be the free product with the free group on N letters. Since
Gamma is f.g. and torsion-free, so is G_proj. Let t_1,...,t_N be
the free generators, U the row (lambda(t_1),...,lambda(t_N)),
A = p_0 U* U p_0 in the corner, V = U p_0 A^{-1/2}, and
e = V V* in C_r*( G_proj ).
This e is a projection, and by the trace computation,
tau_{G_proj}(e) = tau_{Gamma,N}(p_0) in (0, 1/2).
Therefore e is neither 0 nor 1. Since G_proj is finitely
generated and torsion-free, e is a genuine counterexample to
the Kadison-Kaplansky projection conjecture.
The theorem is proved.
(a) TRACE IS NOT INTEGER ON K_0. The K_0 class [p_0] in
K_0(C_r*(Gamma)) has trace tau_{Gamma,N}(p_0) in (0, 1/2), which
is not an integer. Lueck (Inventiones 149 (2002), 123-152) and
Baum-Guentner-Willett (local file
bgw-2016-exactness-kadison-kaplansky.pdf) prove that the reduced
assembly map with trivial coefficients lands in the integral
part of K_0-trace for torsion-free groups.
Therefore [p_0] lies OUTSIDE the image of the reduced assembly
map for Gamma.
(b) C[G_proj] HAS NO SCALAR IDEMPOTENTS OTHER THAN 0 AND 1.
The complex group ring C[G_proj] has no scalar idempotents other
than 0 and 1: the Bass trace conjecture holds for this group by
the same trace methods. The projection e therefore lies in the
C*-completion C_r*(G_proj) but not in the algebraic group ring
C[G_proj], so the norm closure is strictly larger than the
algebraic ring even at the level of projections.
The stable form of the conjecture, about projections in
M_N(C_r*(G)) for every N, fails already at the matrix projection
p_0; the scalar projection e settles the scalar form.
The argument is an EXISTENCE proof. It does not claim:
- an explicit list of generators of G_proj (only that a finite
set exists, of size swamped by all the layer parameters);
- a useful NUMERICAL BOUND on N = q^{n_f};
- a "short" or "understandable" presentation of G_proj;
- any minimality or optimality of the construction.
Every parameter is chosen in the stated order of parameter fixing, and
"ell large enough" is existence only.
This is the end of the proof.