================================================================
NONTRIVIAL MARKOV TYPE FORCES SUPERREFLEXIVITY
a complete proof, written to be read
================================================================
WHAT THIS DOCUMENT IS. One theorem, proved in full. Every step is
justified. Four standard facts are used from outside; they are listed in
section 0.3, and the only hard one (James-Enflo) is used exactly once and
flagged as a black box. Nothing else is assumed.
HOW TO READ IT. Sections 0-3 are the statement, definitions and plan.
Section 4 builds one special norm N on finite sequences; sections 7-10
build one finite reversible random walk; section 5 is where the hypothesis
"Markov type p" is used; section 11 puts the pieces together.
0. THE THEOREM
0.1 Theorem (proved in section 11). Let X be a real Banach space. If X
has Markov type p for some p > 1, then X is superreflexive (that is, X
carries an equivalent uniformly convex norm).
Two comments.
(a) The hypothesis is sharp. Ordinary Rademacher type is weaker, and it
does not suffice: James constructed nonreflexive Banach spaces of
Rademacher type 2. Markov type tests every finite reversible random walk,
and that is strictly stronger.
(b) The converse is known. Superreflexive spaces admit uniformly convex
(equivalently uniformly smooth) norms of power type p for some p > 1,
by Pisier. Uniform smoothness of power type p implies Markov type p for
1 < p <= 2, by Naor-Peres-Schramm-Sheffield. So for real Banach spaces
superreflexive <=> Markov type p for some p > 1
and Naor's question -- must nontrivial Markov type force an equivalent
uniformly smooth norm? -- has answer yes.
0.2 Notation. X is a real Banach space with norm ||.||. c_00 is the
space of real sequences with finite support, and b_i is its i-th
coordinate vector. An array (a_1,...,a_m) denotes the vector
a_1 b_1 + ... + a_m b_m in c_00, with zeros appended when needed. For a
set A, 1_A is its indicator function, equal to 1 on A and 0 off A.
0.3 The four outside facts.
(P1) Hahn-Banach theorem. Used in 4.2.
(P2) Finite Ramsey theorem. For all integers m, r, s there is B such
that every colouring of the m-element subsets of {1,...,B} with r
colours has a monochromatic subset of size s. Used in 4.3 and 7.2,
always applied a fixed finite number of times in a row.
(P3) Goldstine's theorem, in the one form used: the unit ball of Y is
weak-star dense in the unit ball of Y**, that is, for every v in
the unit ball of Y**, every finite list g_1,...,g_s in Y* and
every delta > 0 there is y in B_Y with |g_h(y) - v(g_h)| <= delta
for each h. Proved in 4.2, so nothing is hidden.
(P4) James-Enflo characterisation (restated in 2.1): X is superreflexive
if and only if every Banach space finitely representable in X is
reflexive. This is a hard theorem of James and Enflo. We use it as
a black box, once, in step 1 of 2.2.
1. DEFINITIONS
1.1 Stationary reversible chain. Let S be a finite set, let P = (P_ij)
be a matrix with P_ij >= 0 and sum_j P_ij = 1 for each i (a Markov chain
on S), and let pi be a probability on S. The chain is stationary and
reversible with law pi if
pi_i P_ij = pi_j P_ji for all i, j in S.
Stationarity means each Z_t has law pi; reversibility means that in
stationarity the pair (Z_0,Z_1) has the same law as (Z_1,Z_0).
1.2 Markov type. X has Markov type p > 0 with constant K if for every
finite stationary reversible chain (Z_t) with law pi, every map f from S
to X and every integer t >= 1,
E || f(Z_t) - f(Z_0) ||^p <= K^p t E || f(Z_1) - f(Z_0) ||^p. (1.1)
Here E is expectation over the chain started in pi. The content of (1.1)
is that the p-th moment of the displacement grows at most linearly in
time, with a constant that is uniform over all chains and all targets f.
A Hilbert space has Markov type 2 with K = 1; this is the model case.
1.3 Superreflexive. X is superreflexive if it carries a norm |.| which
is equivalent to ||.|| (that is, a||x|| <= |x| <= b||x|| for some
constants a, b > 0) and which is uniformly convex: for every eps in
(0,2] there is delta > 0 such that
|x| <= 1, |y| <= 1, |x-y| >= eps imply |(x+y)/2| <= 1 - delta.
This is a property of the space, not of ||.||, since it is preserved
under passing to an equivalent norm.
1.4 Finitely representable. A Banach space Y is finitely representable
in X if for every finite-dimensional subspace E of Y and every eta > 0
there is an injective linear map T from E to X with
||T|| ||T^{-1}|| < 1 + eta.
That number is the distortion of T. So finite representability means:
every finite piece of Y sits inside X up to arbitrarily small distortion.
2. THE JAMES-ENFLO CHARACTERISATION AND THE PLAN
2.1 Theorem (James, Enflo). X is superreflexive if and only if every
Banach space finitely representable in X is reflexive.
2.2 Assume, towards a contradiction, that X has Markov type p > 1 with
constant K and that X is not superreflexive. Four steps.
STEP 1 (section 4, Lemma 4.1: an ordered norm). By 2.1 there is a
nonreflexive Banach space Y finitely representable in X. From Y we build
a norm N on c_00 with three properties:
(i) spreading invariance: for every m and all k_1 < ... < k_m,
N( sum_i a_i b_i ) = N( sum_i a_i b_{k_i} );
in words, inserting zeros between the entries does not change N;
(ii) merging two adjacent entries is contractive:
N(..., a_i + a_{i+1}, ...) <= N(..., a_i, a_{i+1}, ...);
(iii) every finite coordinate span (R^m, N) embeds into X with
distortion as close to 1 as we wish.
STEP 2 (sections 7-10, Proposition 6.1: a finite walk). For every integer
n there are a finite stationary reversible marked chain (definition 5.1)
and an odd labelling g with N(g(e)) = 1 for every edge e, such that
P( N( g(E_1) + ... + g(E_n) ) >= n/24 ) >= 3/20, (2.1)
where E_1,...,E_n are the first n edges of the stationary chain.
STEP 3 (section 5, Lemma 5.2). Markov type controls odd edge labels:
E N( g(E_1) + ... + g(E_n) )^p <= K^p n E N( g(E_1) )^p = K^p n.
The proof needs a finite lattice lift, because an edge label need not be
the difference of the values of a function on the states.
STEP 4 (section 11). Combine (2.1) and step 3:
(3/20)(n/24)^p <= K^p n for every integer n >= 1.
With K fixed and p > 1 this is false for large n. Contradiction. So X is
superreflexive, which is Theorem 0.1.
2.3 The two numbers 24 and 3/20 are crude; any fixed positive constants
would do. What matters is: the displacement grows linearly in n (n/24)
with a probability bounded below by a constant (3/20), while Markov type
gives an upper bound that grows only like a constant times n.
3. ARRAYS AND PREFIX SUMS
3.1 An array is a finite list a = (a_1,...,a_m) of reals, identified
with the element a_1 b_1 + ... + a_m b_m of c_00. Its prefix sums are
A_j = a_1 + ... + a_j, 0 <= j <= m,
and A_m is its total sum.
3.2 Spreading invariance. A norm N on c_00 is spreading invariant if for
every m, every array a and every k_1 < ... < k_m we have
N(sum_i a_i b_{k_i}) = N(sum_i a_i b_i). Equivalently: N is unchanged
when zeros are inserted between the entries. We use this constantly and
usually without comment. Two sample uses: an array with a gap of zeros
has the same N-norm as the compressed array; and the position of the
support inside c_00 never matters.
3.3 Two consequences used repeatedly.
(S1) Block sums. Split {1,...,m} into consecutive blocks and replace
each block by the sum of its entries. If merging adjacent entries is
contractive, the new array has N-norm at most the old one. (Apply (ii)
inside each block, a block of length r taking r-1 merges.)
(S2) Alternating blocks. For k >= 1 put
D_k := N(1,-1,1,-1,...,1,-1) (k pairs of +1,-1).
By homogeneity and spreading invariance, for every real c,
N(c,-c) = |c| D_1,
N of a run of k pairs (+c,-c) = |c| D_k.
Also D_{k+l} <= D_k + D_l: the (k+l)-pair array is the sum of a k-pair
array and an l-pair array sitting further to the right, and that second
array has N-norm D_l by spreading invariance, so the triangle inequality
applies. In particular D_L <= 2 D_{L/2} for even L.
4. THE ORDERED NORM
4.1 Lemma. Let X be a real Banach space that is not superreflexive. Then
there is a norm N on c_00 with properties (i), (ii), (iii) of 2.2.
This is the content of the next four subsections. Step 1 produces a
triangular array inside a nonreflexive space; step 2 turns it into a
spreading norm N_0; step 3 averages subdivisions to get N; step 4 shows
that summing adjacent entries is contractive for N.
4.2 STEP 1: A TRIANGULAR ARRAY.
By the James-Enflo characterisation (2.1) there is a nonreflexive Banach
space Y finitely representable in X. A space is reflexive exactly when it
equals its second dual, so Y is a proper subspace of Y** and we may choose
v in Y** with v not in Y, ||v|| <= 1, d := dist(v,Y) > 0.
CLAIM. For every integer M >= 1 there are y_1,...,y_M in the unit ball
of Y and f_1,...,f_M in the unit ball of Y* with
f_i(y_j) = 0 for j < i, |f_i(y_j) - d| <= 1/M for j >= i. (4.1)
Construction, inductively in i = 1,...,M. Suppose y_1,...,y_{i-1} are
chosen and let E be their span (E = {0} when i = 1). Consider the
restriction map
R: Y** -> (E^perp)*, R(phi) = phi restricted to E^perp,
where E^perp = {g in Y* : g = 0 on E}.
R is surjective. Let g be a bounded functional on E^perp. By Hahn-Banach
(P1) it extends to a functional G on Y* with ||G|| = ||g||. A bounded
functional on Y* is evaluation at some point of Y** (that is what the
second dual is), so G = evaluation at some phi in Y**, and R(phi) = g.
R has kernel E. It is immediate that elements of E vanish on E^perp, so
E is contained in the kernel. Conversely let phi in Y** vanish on E^perp.
Then phi factors through Y*/E^perp, which is isometric to E* (a functional
on E^perp extends, by Hahn-Banach, with the same norm, and restricting a
functional on Y* to E^perp gives back). Since E is finite dimensional it
is reflexive, E** = E, so phi is given by a point of E.
A surjective linear map with kernel E induces an isometry Y**/E -> (E^perp)*.
Therefore
|| R(v) || = dist(v,E) >= dist(v,Y) > d. (4.2)
Choose phi in E^perp with ||phi|| <= 1 and v(phi) > d, which is possible
by (4.2), and put f_i := (d / v(phi)) phi. Then f_i is in E^perp, so
f_i(y_j) = 0 whenever j < i; and ||f_i|| = d / v(phi) <= 1; and
v(f_i) = d.
Now choose y_i. Goldstine (P3), applied to v, to the finitely many
functionals f_1,...,f_i and to delta = 1/M, gives y_i in the unit ball of
Y with
|f_h(y_i) - v(f_h)| = |f_h(y_i) - d| <= 1/M for h = 1,...,i.
For completeness, here is the short proof of that form of Goldstine.
Suppose no point of the unit ball of Y works. Then the point
(d,...,d) = (v(f_1),...,v(f_i)) of R^i is at distance more than 1/M from
the set C = {(f_1(y),...,f_i(y)) : ||y|| <= 1}. The set C is compact and
convex, so a separating functional exists: there are reals c_1,...,c_i
and a number gamma > 0 with
sum_h c_h v(f_h) > gamma + sup_{||y||<=1} sum_h c_h f_h(y).
Write f = sum_h c_h f_h. The supremum is ||f||, by definition of the dual
norm. The left side is v(f), and v(f) <= ||v|| ||f|| <= ||f|| because
||v|| <= 1 and f is in Y*. Contradiction.
This closes the induction and proves (4.1).
CONSEQUENCE OF (4.1). Let 1 <= i_1 < ... < i_m <= M and let a_1,...,a_m
be reals. Then
|| sum_h a_h y_{i_h} || >= d max_{0<=j<=m} | a_{j+1} + ... + a_m |
- (1/M) sum_h |a_h|, (4.3)
|| sum_h a_h y_{i_h} || <= sum_h |a_h|. (4.4)
The second is the triangle inequality together with ||y|| <= 1. For the
first, put t = sum_h a_h y_{i_h} and fix j with 0 <= j < m. The functional
f_{i_{j+1}} has norm at most 1 by (4.1) and annihilates y_{i_1},...,
y_{i_j}, because those indices are smaller than i_{j+1}. On
y_{i_{j+1}},...,y_{i_m} it is within 1/M of d. Hence
f_{i_{j+1}}(t) = sum_{h >= j+1} a_h f_{i_{j+1}}(y_{i_h})
lies within (1/M) sum_{h >= j+1} |a_h| of d (a_{j+1} + ... + a_m). Taking
absolute values, then the maximum over j, then using ||f|| <= 1 gives
(4.3). (The case j = m gives the empty suffix sum 0 and is trivial.)
Note what (4.3) measures: the suffix sums of the coefficient list, read
from the far end. This is exactly why, from now on, coefficients are
paired with the largest available units first.
4.3 STEP 2: A SPREAD-OUT LIMIT N_0.
Fix k. For each m <= k choose a finite set G_m inside the cube [-1,1]^m
such that every point of the cube is within k^{-2} of G_m in the max norm.
COLOURING. Let M be large and use the array y_1,...,y_M from (4.1). An
increasing tuple 1 <= i_1 < ... < i_m <= M is coloured by the list, over
all a in G_m, of the bins of width 1/k containing the numbers
|| sum_h a_h y_{i_{m+1-h}} ||.
So the coefficients a_1,a_2,... are paired with the largest, second
largest, ... of the chosen units, matching (4.3). The number of colours is
at most (ceil(2k)+2) raised to the total number of grid points, and thus
depends only on k, never on M.
ITERATED RAMSEY. The arities in play are m = 1,2,...,k, and the colour
count is fixed. Applying (P2) k times in a row gives a number B_k with
this property: for every M >= B_k and every such colouring of the
increasing tuples of {1,...,M}, there is a set H inside {1,...,M} of size
k such that, for every m <= k, all increasing m-tuples of H have the same
colour. (Induction: Ramsey for arity 1 keeps a large subset; Ramsey for
arity 2 inside that subset keeps a large subset; and so on; the last
arity keeps exactly k points.)
Take M = M_k := B_k in (4.1) and let x^{(k)}_1 < ... < x^{(k)}_k be the
points of H in increasing order.
PROPERTY OF x^{(k)}. For every m <= k, every array a in [-1,1]^m and
every increasing m-tuple of positions i_1 < ... < i_m of {1,...,k},
| || sum_h a_h x^{(k)}_{i_{m+1-h}} || - || sum_h a_h x^{(k)}_{k+1-h} || |
<= 3/k. (4.5)
Proof. Both numbers are at most sum_h |a_h| <= m, by (4.4). Choose a' in
G_m with |a_h - a'_h| <= k^{-2} for every h. The two tuples have the same
colour, so for the array a' the two numbers lie in the same bin of width
1/k, hence differ by at most 1/k. Replacing a' by a changes each of the
two numbers by at most sum_h |a_h - a'_h| <= m k^{-2}, again by (4.4).
Total error at most 1/k + 2m k^{-2} <= 3/k.
DEFINITION. For m <= k and a in R^m put
N_k(a) := || sum_{h=1}^m a_h x^{(k)}_{k+1-h} ||,
that is, coefficients paired with the top m units. Each N_k is a norm on
each R^m with m <= k; it is 1-Lipschitz in the l1 norm of a by (4.4); and
by (4.5) it does not matter which m of the k units are used, up to 3/k.
Also N_k ignores trailing zeros.
THE LIMIT. On each R^m the functions N_k, k >= m, are uniformly bounded
and uniformly Lipschitz, so by Arzela-Ascoli each has a uniformly
convergent subsequence on the compact cube [-1,1]^m. Diagonalising over
m = 1,2,3,... produces a subsequence k_1 < k_2 < ... such that for every
m the restrictions to R^m converge uniformly on [-1,1]^m. Define
N_0(a) := lim_{j -> inf} N_{k_j}(a) for a in R^m, m >= 1.
This is unambiguous (trailing zeros are ignored), and N_0 is a norm: a
uniform limit of norms on each finite-dimensional slice is homogeneous and
subadditive, and it is positive definite by (4.6).
THREE PROPERTIES.
(a) BOUNDS. By (4.5) any placement of the coefficients among the units
gives the same number in the limit, so we may compute N_0 with a_1 on the
smallest chosen unit, a_2 on the next, and so on. In that reading (4.3)
applies directly: the suffix sums of a reversed list are the prefix sums
of a. Letting M = M_{k_j} -> inf, and using (4.4) as well, gives for every
array a with prefix sums A_j = a_1 + ... + a_j
d max_j |A_j| <= N_0(a) <= sum_i |a_i|. (4.6)
In particular N_0(a) >= (d/2) max_i |a_i|, because each a_i = A_i - A_{i-1}
is a difference of two prefix sums.
(b) SPREADING INVARIANCE. By (4.5), moving the entries of a to any other
increasing positions among the k units changes N_k by at most 3/k. Both
versions converge along the same subsequence, and 3/k -> 0. So N_0 is
spreading invariant.
(c) EMBEDDING FINITE SPANS INTO Y. Fix m. For a in the cube, (4.5) gives
| || sum_h a_h x^{(k)}_{k+1-h} || - N_k(a) | <= 3/k,
and along the diagonal subsequence N_{k_j}(a) tends to N_0(a), uniformly on
the cube. So for k in that subsequence the linear map a -> sum_h a_h
x^{(k)}_{k+1-h} from R^m to Y has a norm within 3/k + |N_k(a) - N_0(a)| of
N_0(a), and both error terms go to 0 uniformly. On the N_0-unit sphere,
which is compact and bounded away from the origin by (4.6), the relative
error therefore tends to 0, so the distortion of that map tends to 1.
Every finite coordinate span of N_0 embeds into Y, hence (Y being finitely
representable in X) into X, with distortion as close to 1 as we wish.
4.4 STEP 3: AVERAGING SUBDIVISIONS; THE NORM N.
For positive integers J_1,...,J_m and an array a in R^m, let F_J a be the
array obtained from a by replacing a_i with J_i consecutive copies of
a_i / J_i. When all J_i equal J we write F_J for F_J a.
(a) MONOTONICITY. If J_i <= M_i for every i, then
N_0(F_M a) <= N_0(F_J a). (4.7)
Proof. In block i, which has length M_i, choose a uniformly random subset
of size J_i and put a_i / J_i on it, zeros elsewhere; do this
independently in each block. Every outcome is F_J a with extra zeros
inserted, so has N_0-norm N_0(F_J a) by spreading invariance. The average
of all outcomes is F_M a. Convexity of N_0 gives (4.7).
(b) THE LIMIT. By (4.7), N_0(F_J a) is nonincreasing as J grows. By (4.6)
it is bounded below, since the prefix sums of a still occur, at block
ends, among the prefix sums of F_J a. Hence
N(a) := lim_{J -> inf} N_0(F_J a) (4.8)
exists. It is a norm on c_00. Indeed, on each R^m it is a limit of norms,
and the two bounds survive because the prefix sums of a are among those of
F_J a:
d max_j |A_j| <= N(a) <= sum_i |a_i|. (4.9)
The lower bound gives positive definiteness: N(a) = 0 forces every prefix
sum to vanish, hence a = 0. Homogeneity and the triangle inequality are
inherited from the limit.
(c) SPREADING INVARIANCE. Each N_0(F_J .) is spreading invariant, since
F_J never looks at positions, so the limit is spreading invariant. This is
property (i) of 2.2.
(d) SUBDIVISION INVARIANCE. For every fixed choice of multiplicities J,
N(F_J a) = N(a). (4.10)
Proof. Let J_- be the least and J_+ the greatest of the J_i. The composite
F_r F_J is F_{rJ}, the multiplicities being r J_i. Apply (4.7) twice: with
multiplicities M_i = r J_+ against J_i = r J_i, and with M_i = r J_i
against J_i = r J_-. This gives, for every r >= 1,
N_0(F_{rJ_+} a) <= N_0(F_r F_J a) <= N_0(F_{rJ_-} a).
Let r -> inf. The outer two terms tend to N(a) by the definition (4.8),
since r J_+ and r J_- tend to infinity with r. The middle term tends to
N(F_J a), because F_r F_J a = F_{rJ} a. Hence N(a) = N(F_J a).
(e) MERGING TWO ADJACENT ENTRIES OF THE SAME SIGN PRESERVES N. Let a_i and
a_{i+1} have the same sign with a rational ratio, and let b be the array
obtained by replacing them with the single entry a_i + a_{i+1}. Then
N(b) = N(a).
Proof. Choose positive integers J_i, J_{i+1} with a_i / J_i = a_{i+1} /
J_{i+1} = c, and keep all other multiplicities equal to 1. Then F_J a
consists of a run of J_i + J_{i+1} consecutive copies of c in the two
slots, and F_{J_i + J_{i+1}} b is literally the same array. By (4.10),
N(a) = N(F_J a) = N(F_{J_i+J_{i+1}} b) = N(b).
Continuity of N in the coefficients extends this from rational ratios to
all pairs of the same sign: from (4.9), |N(a) - N(a')| <= sum_i |a_i -
a'_i|. If one of the two entries is zero, then b is a with a zero deleted,
and N(b) = N(a) is spreading invariance.
(f) MERGING ARBITRARY ADJACENT ENTRIES IS CONTRACTIVE. This is property
(ii). Fix all coefficients except two adjacent slots and fix s != 0.
Consider the function of one real variable
f(t) := N(..., t, s - t, ...).
The map t -> (..., t, s-t, ...) is affine and N is a norm, so f is convex.
By (e), f(t) is equal to c := N(..., s, ...) whenever t and s-t have the
same sign, and by continuity this includes t = 0 and t = s. So f is
constant, equal to c, on the interval with endpoints 0 and s.
We claim f(t) >= c for every t. Take s > 0 and t > s, write
s = (1 - s/t) 0 + (s/t) t, and use convexity:
c = f(s) <= (1 - s/t) f(0) + (s/t) f(t) = (1 - s/t) c + (s/t) f(t),
which gives f(t) >= c. The case t < 0 is symmetric. Therefore
N(..., t, s - t, ...) >= N(..., s, ...)
for all real t, which is exactly (ii) with the merged array on the right.
Letting s -> 0 handles the case s = 0.
(g) EMBEDDING FINITE COORDINATE SPANS INTO X. This is property (iii). Fix
a dimension m and eta > 0, and let S be the N-unit sphere of R^m, compact
by (4.9). For a in S the numbers N_0(F_J a) tend to N(a) = 1, and the
functions a -> N_0(F_J a) are 1-Lipschitz in the l1 norm of a, because N_0
is and F_J is l1-nonexpansive. So the convergence is uniform on S. For all
large J, therefore, the linear map a -> F_J a is a (1+eta)-isomorphism
from (R^m, N) onto its image inside (R^{mJ}, N_0). That image is a finite
coordinate span of N_0, so it embeds into Y with distortion below 1+eta by
(c) of 4.3, and then into X with distortion below 1+eta by finite
representability of Y in X. Composing, the distortion is below (1+eta)^3,
and eta is arbitrary.
This proves Lemma 4.1.
5. MARKOV TYPE AND ODD EDGE LABELS
5.1 Marked chains. A finite marked chain consists of
- a finite set S of states;
- a finite set E of oriented edges, each with a source e^- in S, a target
e^+ in S, and a reverse e^* satisfying (e^*)^* = e, (e^*)^- = e^+ and
(e^*)^+ = e^-;
- probabilities q(e) >= 0 for e in E with sum over e with e^- = z of
q(e) equal to 1, for every state z.
So from each state we pick one outgoing edge and then move to its target.
Several distinct edges may join the same ordered pair of states, and they
are counted separately; that is what makes it a marked chain rather than
a chain. The marks are used to carry labels.
A probability pi on S is balanced if
pi(e^-) q(e) = pi(e^+) q(e^*) for every edge e. (5.1)
If (5.1) holds then the state chain is stationary and reversible with law
pi. Stationarity: summing (5.1) over the edges with e^- = z gives
pi(z) * 1 on the left and, on the right, the total mass flowing into z,
so the law is preserved in one step. Reversibility is exactly (5.1) after
replacing e by e^*.
A labelling is a map g from E into a normed space V. It is odd if
g(e^*) = -g(e) for every edge e.
An edge which is its own reverse must then carry the label 0.
5.2 Lemma. Let V be a normed space of Markov type p with constant K. Let
(S, E, q, pi) be a finite balanced marked chain, let g: E -> V be odd, and
let E_1, E_2, ... be the edges chosen by the stationary chain. Then for
every n >= 1,
E || g(E_1) + ... + g(E_n) ||^p <= K^p n E ||g(E_1)||^p. (5.2)
The same conclusion holds if the linear span of the labels, with its norm,
is finitely representable in a space of Markov type p with constant K.
The second sentence is the form used later, and it follows from the first.
Let W be the span of the labels and let T: W -> X be linear with
||w|| <= ||Tw|| <= (1+eta) ||w|| for all w in W.
Markov type in X, applied to the map T o g, gives
(1+eta)^{-p} E || sum_i g(E_i) ||^p <= E || T sum_i g(E_i) ||^p
<= K^p n E || T g(E_1) ||^p <= K^p n (1+eta)^p E ||g(E_1)||^p,
and eta tends to 0.
Proof of (5.2). All labels lie in the finite-dimensional span W, and W
inherits Markov type p with constant K from V because (1.1) quantifies
over all target maps. So suppose V = W is finite dimensional. If g is
identically 0 there is nothing to prove. Otherwise:
STEP A: a lattice lift. Choose one edge e_j out of each two-element orbit
of the involution star, j = 1,...,r. Edges fixed by star carry label 0 and
are ignored. Let u_1,...,u_r be the standard basis of Z^r.
Fix an integer R > n and put Q = {-R,...,R}^r. The lifted chain has state
set S x Q. From (z,a) it chooses an edge e with probability q(e), and then
- if a + v(e) lies in Q, it moves to (e^+, a + v(e));
- otherwise it stays at (z, a),
where v(e_j) = u_j, v(e_j^*) = -u_j, and v(e) = 0 for an edge fixed by
star. A move of the second kind is a rejection, and it is a self-loop at
(z,a).
The lifted chain is stationary and reversible with law pi (x) mu, where mu
is the uniform probability on Q. Indeed an accepted transition satisfies
pi(z) q(e) mu(a) = pi(z') q(e^*) mu(a'),
by (5.1) and by uniformity of mu, and rejections are self-loops. Adding
self-loop probabilities at some states of a stationary reversible chain
leaves it stationary and reversible (the new chain is the old one with
extra laziness).
STEP B: a potential. Define Phi: S x Q -> V by
Phi(z,a) = sum_{j=1}^r a_j g(e_j).
On an accepted transition along e its increment is g(e). Check the three
cases: if e = e_j then the j-th lattice coordinate rises by 1 and the
increment is g(e_j) = g(e); if e = e_j^* then that coordinate falls by 1
and the increment is -g(e_j) = g(e_j^*) because g is odd; if e is fixed
by star the increment is 0 = g(e). On a rejection the increment is 0. So
E ||Phi(Z_1) - Phi(Z_0)||^p
= E [ ||g(E_1)||^p if the first proposed move is accepted ]
<= E ||g(E_1)||^p. (5.3)
STEP C: applying Markov type. Markov type (1.1), applied to the map Phi on
the lifted chain, which is finite and stationary reversible, gives
E ||Phi(Z_n) - Phi(Z_0)||^p <= K^p n E ||Phi(Z_1) - Phi(Z_0)||^p. (5.4)
STEP D: the lower bound. Let the lifted chain start in the stationary law
pi (x) mu. Put Q' = {-R+n,...,R-n}^r and consider the event that the
lattice coordinate of Z_0 lies in Q'.
On that event no rejection occurs during the first n steps. Indeed, each
step changes each lattice coordinate by at most 1, and the coordinate
starts at distance at least n from the boundary of [-R,R].
On that event, consequently, no proposal is refused, so
Phi(Z_n) - Phi(Z_0) = g(E_1) + ... + g(E_n),
where E_1,...,E_n are the edges chosen by the underlying marked chain.
The event has probability
alpha_R = ((2(R-n)+1)/(2R+1))^r,
the count of integers in Q' being 2(R-n)+1 and in [-R,R] being 2R+1, and
the r coordinates being independent. So alpha_R tends to 1 as R -> inf.
The event is independent of the edge trajectory, because the edges are
chosen by the marked chain without reference to the lattice. Hence
E ||Phi(Z_n) - Phi(Z_0)||^p >= alpha_R E ||g(E_1)+...+g(E_n)||^p.
Substitute into (5.4) and then into (5.3):
alpha_R E ||g(E_1)+...+g(E_n)||^p <= K^p n E ||g(E_1)||^p,
and let R -> inf. This proves (5.2).
5.3 Remark. The lattice lift is the only place where a labelling that is
not the gradient of a potential is turned into one. The price is the
boundary of the cube, and it is paid by the factor alpha_R, which vanishes
in the limit. The span of the labels does not grow when R grows, so the
finitely-representable version costs nothing extra.
6. THE FINITE WALK
6.1 Proposition (the walk). Let N be a spreading invariant norm on c_00
for which merging adjacent entries is contractive. For every integer
n >= 1 there are a finite stationary reversible marked chain and an odd
labelling g by vectors of a finite coordinate span such that
N(g(e)) = 1 for every edge e, and (6.1)
P( N(g(E_1) + ... + g(E_n)) >= n/24 ) >= 3/20. (6.2)
6.2 The chain and the dimension of the span may depend on n. Only the two
constants 24 and 3/20 are uniform in n, and they are exactly what enters
section 11.
6.3 The proof takes the next four sections.
section 7 produces a law on strictly increasing charts of a finite
ordered set that is almost invariant under relabelling;
section 8 turns that law into a finite reversible marked chain on
charts, with independent uniform letters;
section 9 builds homeomorphisms of the line and two integer-valued
functions that differ by the reduced length of a word;
section 10 assembles charts, labels and counting, and proves 6.1.
6.4 An aside on why charts. The labels in 6.1 are sums of differences of
coordinate vectors, so their prefix sums are step functions. We need those
step functions, along a trajectory, to be exactly the two interlaced
levels produced in section 9. Charts are the device that lets a moving
point keep a fixed rank, and that is what makes the two levels keep
working along the whole trajectory.
7. CHARTS: AVERAGING ON A FINITE ORDER
7.1 Charts. Let Lambda be a finite set with a total order. A chart is a
strictly increasing map
C: Lambda -> {1, 2, ..., B}
for some integer B. If A is an increasing subtuple of Lambda then C(A) is
the tuple of its values, again increasing, and it is an element of the set
T_{B,m} of increasing m-tuples in {1,...,B}, where m is the length of A.
For two probabilities mu, nu on the same finite set, the total variation
distance is
TV(mu,nu) = (1/2) sum_t |mu(t) - nu(t)|.
Fact used below: if mu, nu are probability laws on a finite set then the
coupling that places mass min(mu(t),nu(t)) at each diagonal pair (t,t) and
couples the remaining mass arbitrarily agrees with probability exactly
1 - TV(mu,nu). Also: the l_1 norm of the difference mu - nu equals
2 TV(mu,nu).
7.2 Lemma (finite-order averaging). For every finite ordered set Lambda and
every eps > 0 there are an integer B and a probability nu on the set of
charts C: Lambda -> {1,...,B} such that whenever A and A' are increasing
subtuples of Lambda of the same length,
TV( law of C(A), law of C(A') ) < eps, (7.1)
both laws being taken under nu.
What this says, in words: the tuple of ranks occupied by A and the tuple
of ranks occupied by A' have almost the same distribution, once the chart
is chosen at random. Section 8 turns exactly this into a coupling that
matches the two tuples with probability at least 1 - eps.
Proof of 7.2. If Lambda has at most one point, take B = 1 and nu the point
mass. Otherwise list all pairs (A_rho, A'_rho), rho = 1,...,R, of distinct
increasing subtuples of Lambda of equal length m_rho. The point of the
proof is that a single chart law has to serve all R pairs at once.
For a chart C put
v_C = ( delta_{C(A_1)} - delta_{C(A'_1)}, ...,
delta_{C(A_R)} - delta_{C(A'_R)} ) (7.2)
in the direct sum W_B of the spaces l_1(T_{B,m_rho}), rho = 1,...,R,
equipped with the sum norm ||w|| = sum_rho ||w_rho||_1.
CLAIM. If some point w of the convex hull K of {v_C} satisfies
||w|| < eps, then (7.1) holds.
Indeed write w = sum_C nu(C) v_C with nu a probability on charts. The
rho-th coordinate of w is mu_rho - mu'_rho, where mu_rho is the law of
C(A_rho) and mu'_rho is the law of C(A'_rho). Since the l_1 norm of
mu_rho - mu'_rho is twice the total variation distance and is at most
||w|| < eps, we get TV(mu_rho, mu'_rho) < eps. So it suffices to find a
point of the convex hull with small norm.
SUPPOSE NOT. Then the compact convex set K is at distance at least eps
from the origin, so the Hahn-Banach separation theorem (applied to K and
the open ball of radius eps) produces a functional f of norm at most 1
with
f(v_C) >= eps for every chart C. (7.3)
DUAL FUNCTIONALS. The dual of a sum of l_1 spaces is the corresponding
sum of l_inf spaces, so f is a family of functions
f_rho: T_{B,m_rho} -> R, sup |f_rho| <= 1.
COLOURING. Fix delta > 0 with R delta < eps. Colour each increasing
m-tuple t in {1,...,B} by the list of bins of width delta containing the
numbers f_rho(t) for all rho with m_rho = m. Use bins [k delta,
(k+1) delta). The number of colours is at most (ceil(2/delta) + 1)^R,
which depends only on R and delta, that is, only on Lambda and eps.
RAMSEY. The arities in play are m = 1,...,max m_rho, finitely many, and
the colour count is fixed. Iterating (P2) as in 4.3 gives B, depending only
on Lambda and delta, with this property: for every colouring as above
there is a set H inside {1,...,B} of size |Lambda| such that any two
increasing m-tuples of H have the same colour, for every m.
Now take B as given and let C: Lambda -> H be the increasing bijection.
For each rho the tuples C(A_rho) and C(A'_rho) are increasing m_rho-tuples
inside H, so they have the same colour, so
|f_rho(C(A_rho)) - f_rho(C(A'_rho))| <= delta.
Summing over rho,
|f(v_C)| <= sum_rho |f_rho(C(A_rho)) - f_rho(C(A'_rho))| <= R delta < eps,
which contradicts (7.3). So K contains a point of norm below eps, and
(7.1) holds. This proves 7.2.
7.3 Two remarks.
(a) The number B grows like a tower of exponentials in |Lambda|. That is
harmless: Lambda will be a fixed finite set for each n, and B depends on
it.
(b) Nothing in 7.2 uses the metric structure of anything. It is a purely
combinatorial statement about a finite order: the ranks of any prescribed
pattern are equidistributed up to eps.
8. REVERSIBLE CHART TRANSPORT
8.1 Setup. Let Lambda be a finite ordered set, S a finite set of letters
carrying a fixed-point-free involution s -> s^{-1}, and for each s in S
given subsets D_s, R_s of Lambda and an order-preserving bijection
T_s: D_s -> R_s, with T_{s^{-1}} = T_s^{-1}.
Read T_s as "when the letter s is played, the landmark a moves to
T_s(a)"; the domain D_s is the set of landmarks for which that move stays
inside Lambda.
8.2 Proposition (reversible chart transport). For every eps > 0 there are
an integer B and a finite stationary reversible marked chain, in the sense
of 5.1, whose states are charts C: Lambda -> {1,...,B} and whose labels
are the letters s in S, such that
(a) the letter of each step is independent of the past and uniform on S;
(b) at a stationary step (C,s,C'), with probability at least 1 - eps,
C'(a) = C(T_s(a)) for every a in D_s. (8.1)
Call a step satisfying (8.1) good. So (b) says: a stationary step is good
with probability at least 1 - eps.
The picture for one letter s: the domain points and their images must
receive the same rank in the two charts.
ranks in chart C: 2 5 9
landmarks: T_s(a1) T_s(a2) T_s(a3)
| | |
v v v
landmarks: a1 a2 a3
ranks in chart C': 2 5 9
Exact equality of all the ranks in the picture is condition (8.1).
Proof.
STEP 1: couplings for a single letter. Let B and nu be given by 7.2 for
this Lambda and this eps. Fix a letter s; the case of s^{-1} is handled by
symmetry at the end.
The subtuples T_s(D_s) and D_s of Lambda have the same length. By (7.1)
the laws, under nu, of the tuples C(T_s(D_s)) and C(D_s) differ in total
variation by less than eps. Couple those two tuples so that they agree
with probability at least 1 - eps, using the diagonal coupling of 7.1.
Now build charts from tuples: given the values of C on T_s(D_s), sample
the rest of C from nu conditioned on those values; given the values of C'
on D_s, sample the rest of C' from nu conditioned on those values,
independently. This produces a probability law lambda_s on pairs (C,C') of
charts with
first marginal of lambda_s = nu = second marginal of lambda_s,
and such that, on the event that the two tuples agree, C(T_s(a)) = C'(a)
for every a in D_s. Hence lambda_s gives (8.1) with probability at least
1 - eps.
For the inverse letter set
lambda_{s^{-1}}(C,C') := lambda_s(C',C). (8.2)
Both marginals are again nu, and the matching condition for s^{-1} is the
matching condition for s read with the two charts exchanged.
STEP 2: the chain. The states are the charts C with nu(C) > 0. From C,
first choose a letter s uniformly in S and independently of everything
else, then choose C' with probability
lambda_s(C,C') / nu(C). (8.3)
These conditional probabilities sum to 1, because the first marginal of
lambda_s is nu. The edge is the triple (C, s, C'); its reverse is
(C', s^{-1}, C), which is again an edge of the chain, by (8.2) and by
positivity. Only finitely many triples carry positive mass, so this is a
finite marked chain.
STEP 3: balance. The mass of the edge (C,s,C') is
m(C,s,C') = (1/|S|) lambda_s(C,C'), (8.4)
because the state C occurs with probability nu(C) and then the transition
has conditional probability (8.3). Reversing the edge,
m(C',s^{-1},C) = (1/|S|) lambda_{s^{-1}}(C',C) = (1/|S|) lambda_s(C,C'),
by (8.2). So m is invariant under reversal, which is exactly the balance
condition (5.1) with pi = nu. By 5.1 the chain is stationary and reversible
with law nu.
STEP 4: goodness. At a stationary step the pair (C,C') has law lambda_s
with s uniform in S and independent of C, by construction. So (8.1) holds
with probability at least 1 - eps. This proves 8.2.
8.3 Remark. The only probabilistic input is 7.2. Everything else in 8.2 is
bookkeeping: a coupling of two laws with the same marginal, made symmetric
under s -> s^{-1}, automatically gives a balanced marked chain.
9. TWO LEVELS FROM REDUCED WORDS
9.1 Words. Let S = {u, v, u^{-1}, v^{-1}}, where u and v are the positive
letters and u^{-1}, v^{-1} the negative ones, with (s^{-1})^{-1} = s. A
word is a finite string in S. It is reduced if no letter is immediately
followed by its inverse. The reduced form of a word is obtained by
scanning from left to right: if the incoming letter is the inverse of the
last letter kept so far, delete that letter; otherwise append the incoming
letter. This is the usual cancellation in the free group on two
generators, and standard cancellation arguments show that deleting
adjacent inverse pairs in any order gives the same final result. The
reduced length is the number of letters left.
9.2 Arcs. Choose numbers
0 < alpha_s < beta_s < 1, s in S,
so that the closed intervals [alpha_s, beta_s], s in S, are pairwise
disjoint. Put
A_s = union over j in Z of [ alpha_s + j , beta_s + j ).
Each A_s is a periodic union of half-open intervals. Because the closed
intervals [alpha_s, beta_s] are pairwise disjoint, the sets A_s and A_t are
disjoint for s != t; more than that, a point of A_s is never even a limit
point of A_t.
9.3 Lemma (the homeomorphisms). There are increasing homeomorphisms h_s of
R, s in S, such that
h_s(y+1) = h_s(y) + 1, h_{s^{-1}} = (h_s)^{-1}, (9.1)
h_s( R \ A_{s^{-1}} ) = A_s, (9.2)
|h_s(y) - y| < 2 for all real y. (9.3)
For a word w = s_1...s_k put h_w = h_{s_1} o ... o h_{s_k}, and let h_w be
the identity for the empty word. If w is nonempty and reduced, then
h_w(0) lies in the interior of A_{s_1}; (9.4)
in particular h_w(0) is not an integer.
Proof. It suffices to define h_s for positive s, and then put h_{s^{-1}} :=
h_s^{-1}; then (9.1) holds by definition and everything else is checked
symmetrically.
So fix a positive letter s. Define h_s on the closed interval
[alpha_{s^{-1}}, alpha_{s^{-1}} + 1] to be the increasing affine map
sending
alpha_{s^{-1}} |-> beta_s - 1,
beta_{s^{-1}} |-> alpha_s,
alpha_{s^{-1}} + 1 |-> beta_s.
The three target values are strictly increasing, because
beta_s - 1 < alpha_s < beta_s (since 0 < alpha_s < beta_s < 1),
so this is well defined and affine pieces have positive slope. Extend to
all of R by (9.1). The extension is continuous at the two ends of the
interval, since beta_s = (beta_s - 1) + 1. So h_s is an increasing
homeomorphism of R.
Now the half-open interval [beta_{s^{-1}} + j, alpha_{s^{-1}} + j + 1) is
mapped by h_s exactly onto [alpha_s + j, beta_s + j). As j runs over Z the
first family of intervals is exactly R \ A_{s^{-1}}, and the second is
exactly A_s. This is (9.2) for positive s; taking inverses gives it for
negative s.
For (9.3), evaluate the displacement h_s(y) - y at the three breakpoints:
it equals beta_s - 1 - alpha_{s^{-1}} at the first and the third, and
alpha_s - beta_{s^{-1}} at the second. Each has modulus less than 2,
because all alpha and beta lie strictly between 0 and 1. Between
breakpoints the displacement is affine, so its modulus is at most the
larger of the two endpoint values; and the whole picture is 1-periodic by
(9.1). The same bounds hold for h_s^{-1}.
For (9.4), first note that 0 lies outside every A_s: each A_s is contained
in the union of the intervals (0,1) + j. Now read the reduced word from
the right,
h_w(0) = h_{s_1}( h_{s_2}( ... h_{s_k}(0) ... ) ).
Step one: 0 lies in R \ A_{s_k^{-1}}, so by (9.2) with s = s_k the point
h_{s_k}(0) lies in the interior of A_{s_k}. Inductively, suppose the
current point lies in the interior of A_{s_i}. Since the word is reduced,
s_{i-1} != s_i^{-1}, so A_{s_i} and A_{s_{i-1}^{-1}} are disjoint (the
closed base intervals are). Hence the current point lies in
R \ A_{s_{i-1}^{-1}}, and (9.2) applied to s = s_{i-1} puts its image in
the interior of A_{s_{i-1}}. After all the steps, h_w(0) lies in the
interior of A_{s_1}, which contains no integer. This proves (9.4).
9.4 The cocycle. Define integer-valued 1-periodic functions on R by
chi_s(y) = 1_{A_s}(y) - c_s, where c_s = 1 if s is negative,
c_s = 0 if s is positive.
The reason for the constant c_s is that it makes the sign flip under
reversal, as follows.
From (9.2): y lies in A_s exactly when h_s^{-1}(y) lies in R \ A_{s^{-1}},
that is, exactly when h_s^{-1}(y) does not lie in A_{s^{-1}}. Hence
1_{A_{s^{-1}}}(h_s^{-1}(y)) = 1 - 1_{A_s}(y). (9.5)
Since c_{s^{-1}} = 1 - c_s,
chi_{s^{-1}}(h_s^{-1}(y)) = 1 - 1_{A_s}(y) - c_{s^{-1}}
= c_s - 1_{A_s}(y) = - chi_s(y). (9.6)
Now fix a word w = s_1 ... s_k and a starting point y_0 = y, and define
y_i = h_{s_i}^{-1}(y_{i-1}), c_w(y) = sum_{i=1}^{k} chi_{s_i}(y_{i-1}).
(9.7)
The final point after the last step is y_k = h_w^{-1}(y).
Two elementary facts, both used later.
(a) PERIODICITY: c_w(y+1) = c_w(y). Indeed (9.1) gives y_i(y+1) = y_i(y)+1
for each i, and chi_s is 1-periodic.
(b) CANCELLATION: if w' is obtained from w by deleting an adjacent inverse
pair, then c_{w'}(y) = c_w(y) and the final points agree.
Proof of (b). It is enough to treat a pair at positions i, i+1 with
s_{i+1} = s_i^{-1}. Write s = s_i. Then, since y_i = h_s^{-1}(y_{i-1}),
y_{i+1} = h_{s^{-1}}^{-1}(y_i) = h_s(y_i) = y_{i-1}.
So the point after the pair equals the point before it, and the two terms
they contribute are
chi_s(y_{i-1}) + chi_{s^{-1}}(y_i) = chi_s(h_s(y_i)) + chi_{s^{-1}}(y_i)
= 0
by (9.6) applied to the letter s and to the point y = h_s(y_i), which
gives chi_{s^{-1}}(y_i) = -chi_s(h_s(y_i)). So the two terms cancel. All
other points and all other terms are unchanged.
This proves (b).
9.5 Lemma (two levels). Let the reduced form of w have length ell > 0,
with n_+ positive and n_- negative letters, so ell = n_+ + n_-. Then for
every integer j,
c_w(j) = - n_-, c_w(h_w(0) + j) = n_+. (9.8)
Proof. By 9.4(b) we may replace w by its reduced form t_1 ... t_ell.
FIRST LEVEL. Start at y_0 = j. Claim: y_{i-1} does not lie in A_{t_i} for
any i. Then every indicator in (9.7) is 0, the sum of the constants c_s is
-n_-, and c_w(j) = -n_-.
Induction on i. y_0 = j is an integer, hence outside A_{t_1}. Suppose
y_{i-1} lies outside A_{t_i}. By (9.2) applied to s = t_i^{-1}, and
h_{t_i^{-1}} = h_{t_i}^{-1},
h_{t_i}^{-1}( R \ A_{t_i} ) = A_{t_i^{-1}},
so y_i = h_{t_i}^{-1}(y_{i-1}) lies in A_{t_i^{-1}}. Since the word is
reduced, t_{i+1} != t_i^{-1}, so A_{t_{i+1}} and A_{t_i^{-1}} are disjoint,
and y_i lies outside A_{t_{i+1}}. This is exactly where reducedness enters.
SECOND LEVEL. Start at y_0 = h_w(0) + j. Claim: y_{i-1} lies in A_{t_i} for
every i. Then every indicator is 1, the sum of the constants is -n_-, and
c_w = ell - n_- = n_+.
First compute the intermediate points. For every i,
y_{i-1} = h_{t_i ... t_ell}(0) + j. (9.9)
For i = 1 this is the definition, since w reduces to t_1...t_ell and the
final point is the image of 0. For the induction step,
y_i = h_{t_i}^{-1}(y_{i-1}) = h_{t_i}^{-1}( h_{t_i...t_ell}(0) + j )
= h_{t_{i+1}...t_ell}(0) + j, using (9.1).
The word t_i ... t_ell is a suffix of a reduced word, hence reduced, so by
(9.4) the point h_{t_i...t_ell}(0) lies in the interior of A_{t_i}. Adding
the integer j keeps it inside A_{t_i}, by periodicity. This proves the
claim and (9.8).
9.6 Two interlaced families. Let w be a word whose reduced form has length
ell > 0, and let
m = floor(h_w(0)), z = h_w(0) - m.
By (9.4) the point h_w(0) is not an integer, so 0 < z < 1. Applying (9.8)
with the integers j and j - m gives
c_w(j) = - n_-, c_w(z + j) = n_+ (9.10)
for every integer j, because h_w(0) + (j - m) = z + j. The two families of
points are interlaced:
j < z + j < j + 1.
The gap between the two levels is
n_+ - (-n_-) = ell,
the reduced length of w. This is the amount that becomes a lower bound for
a norm in section 10. The point of the construction is that the level
structure is periodic and survives cancellation, so it can be transported
by a finite chart along a whole trajectory of length n.
10. CONSTRUCTION OF THE FINITE WALK
This section proves Proposition 6.1.
10.1 Fix the norm N and the integer n. Put
L = 8(n+1), eps = 1/(10n),
and for k >= 1 put
D_k = N(1,-1,1,-1,...,1,-1) (k pairs).
By (S2) of 3.3, N of a run of k pairs (+c,-c) equals |c| D_k, and
D_{k+l} <= D_k + D_l; in particular D_L <= 2 D_{L/2}. Also D_k > 0, since
the k-pair array is nonzero and N is a norm.
STEP 1: THE FINITE CHART CHAIN.
Let Lambda be the following finite set of reals, ordered as usual:
Lambda = { alpha_s + j, beta_s + j : s in S, 0 <= j < L }
U { h_w(0) + j : |w| <= n, -2n <= j <= L + 2n },
where |w| is the length of w before reduction, the empty word is included,
and repeated points are counted once.
For s in S put
D_s = { a in Lambda : h_s(a) in Lambda }, T_s = h_s restricted to D_s.
Then T_s: D_s -> h_s(D_s) is an order-preserving bijection between subsets
of Lambda, and T_{s^{-1}} = T_s^{-1} because h_{s^{-1}} = h_s^{-1}.
Apply Proposition 8.2 to this Lambda, this letter set S, these bijections
and this eps. This gives an integer B and a finite stationary reversible
marked chain on charts C: Lambda -> {1,...,B} with independent uniform
letters, such that a stationary step (C,s,C') is good with probability at
least 1 - eps, where good means
C'(a) = C(h_s(a)) for every a in D_s. (10.1)
Each stationary step is good with probability at least 1 - eps, so by the
union bound and stationarity, the probability that all of the first n
steps are good is at least 1 - n eps = 9/10.
THE LABELLING. For a positive letter s define
g(C,s,C') = sum_{j=0}^{L-1} ( b_{C(alpha_s + j)} - b_{C(beta_s + j)} ), (10.2)
an array of length B: coefficient +1 at the ranks C(alpha_s + j) and -1 at
the ranks C(beta_s + j). For a negative letter set
g(C,s,C') = - g(C', s^{-1}, C). (10.3)
This is odd by construction: reversing an edge and using (10.3) flips the
sign.
Every edge label has N-norm exactly D_L. Look at (10.2): the chart C is
strictly increasing and
alpha_s + j < beta_s + j < alpha_s + (j+1) < beta_s + (j+1)
(because alpha_s <= beta_s and beta_s < alpha_s + 1), so the ranks are
strictly increasing and the coefficient array is the alternating pattern
+1,-1,+1,-1,... with L pluses and L minuses, spread out with zeros between
them. By spreading invariance and homogeneity its N-norm is D_L. For a
negative letter the same holds by (10.3) and oddness. So
N(g(e)) = D_L > 0 for every edge e. (10.4)
STEP 2: TRANSPORT OF RANKS ALONG A GOOD TRAJECTORY.
Suppose all n steps of a trajectory (C_{i-1}, s_i, C_i), i = 1,...,n, are
good, and let w = s_1...s_n have reduced length ell > 0. Put
m = floor(h_w(0)), z = h_w(0) - m.
By (9.4) the point h_w(0) lies in the open arc A_{s_1}, so
0 < z < 1.
For integers j with L/4 <= j <= 3L/4 define the two ranks
r_j = C_0(j), t_j = C_0(z + j). (10.5)
Both are defined: j lies in [0,L) so j is in Lambda; and
z + j = h_w(0) + (j - m),
with |w| = n and j - m in [-2n, L+2n], because |m| < 2n by (9.3) and
L/4 = 2n+2 > 2n. So z + j is in Lambda as well. Since j < z+j < j+1 and
C_0 is strictly increasing,
r_j < t_j < r_{j+1} whenever all the ranks are defined. (10.6)
Now follow the two families of points. In both cases set y_0 equal to j
(family 1) or z + j (family 2), and iterate
y_i = h_{s_i}^{-1}(y_{i-1}), i = 1,...,n.
Explicit formulas, both by induction using (9.1) and h_{s^{-1}} = h_s^{-1}:
family 1: y_i = h_{(s_1 ... s_i)^{-1}}(0) + j,
family 2: y_i = h_{s_{i+1} ... s_n}(0) + j - m.
Consequently, for every i,
|y_i - j| < 2i <= 2n (family 1),
|y_i - (z + j)| < 2i <= 2n (family 2).
The first bound is (9.3) iterated. For the second, write y = h_{s_{i+1}...
s_n}(0); then y_i - (z+j) = y - h_w(0) = y - h_{s_1...s_i}(y), and
|h_{s_1...s_i}(y) - y| < 2i by (9.3) iterated i times.
Since 0 < z < 1 and j >= L/4 = 2n+2, both bounds give
j - 2n < y_i < j + 1 + 2n, hence 0 < y_i < L (10.7)
for every 0 <= i <= n: the lower bound is positive because j > 2n, and
the upper bound is below L because j <= 3L/4 and 3L/4 + 1 + 2n = 8n + 7 <
L = 8n + 8.
Every intermediate point lies in Lambda: in family 1, y_i = h_w'(0) + j
with |w'| = i <= n and j in [-2n, L+2n]; in family 2, y_i = h_w''(0) +
(j - m) with |w''| = n - i <= n and j - m in [-2n, L+2n].
Finally, h_{s_i}(y_i) = y_{i-1}, and both y_i and y_{i-1} lie in Lambda, so
y_i lies in D_{s_i}. Applying the goodness condition (10.1) and iterating,
C_i(y_i) = C_{i-1}(h_{s_i}(y_i)) = C_{i-1}(y_{i-1}),
so that
C_i(y_i) = C_0(y_0) = r_j (family 1) or t_j (family 2). (10.8)
This is the whole purpose of the chart chain: the moving point keeps the
same rank.
STEP 3: PREFIX SUMS OF THE TOTAL LABEL.
Let
G = g(C_0,s_1,C_1) + g(C_1,s_2,C_2) + ... + g(C_{n-1},s_n,C_n),
an array of length B, and let
F(k) = G_1 + ... + G_k, 0 <= k <= B,
be its prefix sums. Each label has total coefficient sum 0 (there are as
many +1 as -1, for positive s in (10.2), and by (10.3) for negative s), so
F(0) = F(B) = 0. (10.9)
THE INDICATOR IDENTITY. Let alpha < beta be elements of Lambda and let y
also be in Lambda. For any chart C,
sum_{a <= C(y)} ( b_{C(alpha)} - b_{C(beta)} )_a = 1_{[alpha,beta)}(y).
Indeed the sum counts the coefficients up to rank C(y): it is 1 if
C(alpha) <= C(y), minus 1 if C(beta) <= C(y), and 0 otherwise; and
comparing ranks is comparing reals, since C is strictly increasing. This is
where the half-open convention [alpha,beta) enters: the value is 1 exactly
when alpha <= y < beta.
THE CONTRIBUTION OF ONE STEP. Evaluate F at the rank C_0(y_0) and split it
into the n contributions of the individual labels.
Positive letter s_i. Read the label in chart C_{i-1}, see (10.2), and use
(10.8). The contribution is
sum_{j=0}^{L-1} 1_{ [alpha_{s_i}+j, beta_{s_i}+j) }(y_{i-1}),
which equals 1_{A_{s_i}}(y_{i-1}), because 0 < y_{i-1} < L by (10.7), so
at most one of the L arcs [alpha+j, beta+j), 0 <= j < L, can contain it.
Negative letter s_i. Read the label in chart C_i by (10.3), use (10.8)
again, and get
- sum_{j=0}^{L-1} 1_{ [alpha_{s_i^{-1}}+j, beta_{s_i^{-1}}+j) }(y_i)
= - 1_{A_{s_i^{-1}}}(y_i),
again because 0 < y_i < L. By (9.5) this equals 1_{A_{s_i}}(y_{i-1}) - 1.
In both cases the contribution is exactly chi_{s_i}(y_{i-1}). Summing over
i,
F(C_0(y_0)) = c_w(y_0). (10.10)
Note where reduction is used: only here, in the scalar quantity c_w.
The array G itself keeps all n original labels.
STEP 4: FROM THE TWO LEVELS TO A NORM BOUND.
Take family 1 and family 2 with L/4 <= j <= 3L/4, and put a = L/4,
b = 3L/4. By (10.10) and Lemma 9.5, with n_+, n_- the letter counts of the
reduced form of w and ell = n_+ + n_-,
F(r_j) = c_w(j) = -n_- =: V, F(t_j) = c_w(z+j) = n_+ =: U, (10.11)
and U - V = ell.
THE CUTS AND THE BLOCK TABLE. Look at the following cuts, in increasing
order:
0, r_a, t_a, r_{a+1}, t_{a+1}, ..., r_{b-1}, t_{b-1}, r_b, B.
All of them are strict: by (10.6) we have r_j < t_j < r_{j+1}; and
r_b < B because the element L + 2n of Lambda is larger than b = 3L/4, so
C_0(b) is not the maximum rank. Also r_a >= 1 because the element alpha_s
of Lambda is smaller than a = L/4.
By (10.9) and (10.11) the prefix sums at the cuts are
cut: 0 r_a t_a r_{a+1} ... t_{b-1} r_b B
F: 0 V U V ... U V 0
block: V ell -ell ell ... -ell -V
where "block" means the sum of G over the block ending at that cut. There
are b - a = L/2 pairs (ell,-ell).
Replacing every block by its sum is contractive by (S1) of 3.3, so
N(G) >= N( V, (ell,-ell) repeated L/2 times, -V ). (10.12)
TWO LOWER BOUNDS. Write the array in (10.12) as A + B' where
A = (V, 0, ..., 0, -V), B' = (0, ell,-ell, ..., ell,-ell, 0).
By (S2), N(A) = |V| D_1 and N(B') = ell D_{L/2}. The triangle inequality in
the form N(B') <= N(A+B') + N(A) gives
N(G) >= ell D_{L/2} - |V| D_1 >= ell ( D_{L/2} - D_1 ), (10.13)
using |V| = n_- <= ell.
Independently, cutting only at 0, r_j and B gives block sums (V,-V), so
N(G) >= |V| D_1; cutting only at 0, t_j and B gives N(G) >= U D_1. Since
|V| + U = n_- + n_+ = ell,
N(G) >= max(|V|,U) D_1 >= (ell/2) D_1. (10.14)
COMBINING. For nonnegative A and B one always has max(A-B, B/2) >= A/3:
if A - B >= A/3 there is nothing to prove, and otherwise B > 2A/3 so
B/2 > A/3. Apply this with A = ell D_{L/2} and B = ell D_1, using (10.13)
and (10.14):
N(G) >= (ell/3) D_{L/2} >= (ell/6) D_L, (10.15)
the last step because D_L <= 2 D_{L/2}.
STEP 5: PROBABILITY AND NORMALISATION.
The letters s_1,...,s_n are independent and uniform in the four-letter set
S, whether or not we condition on goodness. Let ell_k be the reduced length
of s_1...s_k. Given the past, if ell_{k-1} > 0 then exactly one of the four
letters (the inverse of the last letter) decreases the reduced length by 1,
while the other three increase it by 1; if ell_{k-1} = 0 then every letter
increases it by 1. Hence
E[ ell_k | past ] >= ell_{k-1} + 1/2,
and summing, E ell_n >= n/2. Since 0 <= ell_n <= n,
n/2 <= E ell_n <= n/4 + n P(ell_n >= n/4),
so P(ell_n >= n/4) >= 1/4.
Therefore, by the union bound over the two events "all n steps good" and
"ell_n >= n/4",
P( all n steps good and ell_n >= n/4 ) >= 1/4 - 1/10 = 3/20. (10.16)
On that event, with ell = ell_n >= n/4, (10.15) gives
N(G) >= (n/4)(D_L/6) = n D_L / 24. (10.17)
Finally divide every label by the positive constant D_L, which is by
(10.4) the common N-norm of all labels. Dividing labels does not change
the chain; the labelling is still odd; every edge now has label of N-norm
exactly 1; and (10.17) becomes
P( N(g(E_1) + ... + g(E_n)) >= n/24 ) >= 3/20.
This is Proposition 6.1.
11. ENDGAME: PROOF OF THEOREM 0.1
Suppose X is not superreflexive and has Markov type p > 1 with constant K.
Let N be the norm of Lemma 4.1.
Fix an integer n and take the marked chain and the odd labelling g of
Proposition 6.1, applied to this N and this n. All labels lie in a finite
coordinate span W of c_00, which is finite dimensional and equipped with
the restriction of N. By property (iii) of Lemma 4.1, W embeds into X with
distortion as close to 1 as we wish; that is exactly the hypothesis of the
finitely-representable form of Lemma 5.2. Apply it with V = W. For
E_1,...,E_n the first n edges of the stationary chain,
E N( g(E_1) + ... + g(E_n) )^p <= K^p n E N( g(E_1) )^p = K^p n,
(11.1)
because N(g(e)) = 1 for every edge by (6.1).
On the other hand, by (6.2), the same random variable is at least n/24 with
probability at least 3/20, and it is nonnegative, so
E N( g(E_1) + ... + g(E_n) )^p >= (3/20)(n/24)^p. (11.2)
Combine (11.1) and (11.2):
(3/20)(n/24)^p <= K^p n for every integer n >= 1. (11.3)
Divide (11.3) by n:
(3/20) n^{p-1} / 24^p <= K^p.
Since p > 1 the left side tends to infinity as n grows, while the right
side is a fixed number. This is impossible.
Therefore X cannot fail to be superreflexive. This is Theorem 0.1.
11.1 A bookkeeping remark. All the chains used in this deduction are
finite and start in their reversible stationary laws. Their sizes, and the
dimensions of the spans carrying the labels, depend on n. The only
quantity that has to be uniform in n is the Markov type constant K, and
it is: it is a property of X alone.
12. WHAT WAS USED, AND WHAT IS SHARP
12.1 Where each hypothesis enters.
- "X is a Banach space" enters in Lemma 4.1. That is where James-Enflo
supplies a nonreflexive Y, where the second dual and the distance d
come from, and where Hahn-Banach and Goldstine are used.
- "p > 1" enters exactly once, in the last two lines of section 11.
- "K is finite" enters in Lemma 5.2, applied at the start of section 11.
- "the chain, its size and the dimension may depend on n" is essential:
(11.3) has to hold for every n with the same K on the right, and it is
the freedom on the left, not any freedom in K, that produces the
contradiction.
12.2 The constants are crude. Section 10 uses four of them:
L = 8(n+1), which must exceed 2n on both sides of the window (10.7);
eps = 1/(10n), which must sum to at most 1/10 over n steps;
the level gap ell >= n/4, which must have probability at least 1/4;
and D_L <= 2 D_{L/2}, which needs L even.
Any constants with those properties would do. Nothing in the argument
depends on the precise numbers 24 and 3/20.
12.3 The converse. By Naor-Peres-Schramm-Sheffield, a space with an
equivalent uniformly smooth norm of power type p satisfies Markov type p
for 1 < p <= 2; by Pisier, every superreflexive space admits such a norm
for some p > 1. So, for real Banach spaces,
superreflexive
<=> Markov type p for some p > 1
<=> Markov type p for some p with 1 < p <= 2.
Theorem 0.1 supplies the missing direction. Naor's question -- must
nontrivial Markov type force an equivalent uniformly smooth norm? -- has
answer yes.
12.4 Why Rademacher type is not enough. Rademacher type tests only sums
with independent random signs, and James's nonreflexive space of Rademacher
type 2 shows that such sums cannot see nonreflexivity. Markov type tests
every finite reversible walk, and section 10 arranges a walk whose
consecutive summation turns a long reduced word into a linear displacement.
12.5 The argument in one paragraph. If X were not superreflexive, then by
James-Enflo a nonreflexive space Y sits finitely representably inside X;
section 4 turns that into a norm N on finite sequences whose finite pieces
still fit inside X almost isometrically, with zeros insertable for free and
adjacent summation nonexpansive; sections 7-10 give, for every n, a finite
reversible walk whose labels all have N-norm 1 and whose n-step sum has
N-norm at least n/24 with probability at least 3/20; section 5 turns that
into E N(sum)^p <= K^p n; and (3/20)(n/24)^p <= K^p n is impossible for
large n once p > 1.