diff 7123e31..2d5618e markov_type_superreflexivity_v2.txt
diff --git a/markov_type_superreflexivity_v2.txt b/markov_type_superreflexivity_v2.txt
index 26278d5..c6827f2 100644
--- a/markov_type_superreflexivity_v2.txt
+++ b/markov_type_superreflexivity_v2.txt
@@ -1,1455 +1,878 @@
-================================================================
-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.
+The Markov type inequality tests every finite reversible random walk at
+once. Let S be a finite set, P a transition matrix on S with stationary
+law pi satisfying pi_i P_ij = pi_j P_ji for all i,j in S, and write
+Z_0, Z_1, Z_2, ... for the chain started in pi. A real Banach space X has
+Markov type p > 0 with constant K < infinity when, for every such chain,
+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.
+
+The left side measures how far a walk of length t travels, the right side
+measures one step. The inequality says that the p-th moment of the
+displacement grows at most linearly in time, with one constant K serving
+all walks and all targets. Keith Ball introduced the condition to prove
+Lipschitz extension theorems, and the only structure it sees is a
+reversible random walk, so it is a metric condition even when the target
+is a Banach space.
+https://doi.org/10.1007/BF01896971
+
+Superreflexivity is a linear notion with a purely metric characterization.
+A norm |.| on X is equivalent to ||.|| when a||x|| <= |x| <= b||x|| for
+some a,b > 0, and uniformly convex when for every eps in (0,2] there is
+delta > 0 such that |x| <= 1, |y| <= 1 and |x-y| >= eps together force
+|(x+y)/2| <= 1 - delta. The space is superreflexive when some equivalent
+norm is uniformly convex. Uniform convexity is due to Clarkson, who used
+it to study duality of L^p spaces. Robert C. James introduced the class and
+identified it with reflexivity of every space finitely representable in
+X; Per Enflo identified it with the existence of a uniformly convex
+renorming.
+https://doi.org/10.1090/S0002-9947-1936-1501880-4
+https://doi.org/10.4153/CJM-1972-089-7
+https://doi.org/10.1007/BF02762802
+
+Theorem. Every real Banach space of Markov type p for at least one
+p > 1 is superreflexive.
+
+The converse also holds, so the statement is a characterization. Uniform
+smoothness of power type p forces Markov type p for 1 < p <= 2, by
+Naor, Peres, Schramm and Sheffield; Gilles Pisier showed that every
+superreflexive space carries an equivalent uniformly smooth norm of power
+type p for some p > 1; and Markov type is invariant under equivalent
+norms. Hence a real Banach space is superreflexive exactly when it has
+Markov type p for some p > 1, which answers a question of Assaf Naor:
+whether nontrivial Markov type can exist without an equivalent uniformly
+smooth norm.
+https://arxiv.org/pdf/math/0410422
+refs/npss-2006.pdf
+https://doi.org/10.1007/BF02760337
+https://arxiv.org/pdf/1205.5993
+refs/naor-ribe-2012.pdf
+
+Rademacher type, the weaker cousin, does not suffice. James constructed a
+nonreflexive space of Rademacher type 2, so sums with independent random
+signs cannot detect nonreflexivity, while reversible walks can.
+https://doi.org/10.1007/BF02760825
+
+The Ribe program asks which linear properties of a Banach space have
+metric counterparts. Ribe's theorem, that a uniform homeomorphism between
+Banach spaces makes each of them finitely representable in the other,
+supplies the original example, and the program built on it collects a
+series of such counterparts: Bourgain's criterion through the distortion
+of finite binary trees, the diamond graph criterion of Johnson and
+Schechtman, Markov convexity as a test for tree embeddability in the work
+of Lee, Naor and Peres, and the Markov convexity characterization of
+superreflexivity by Mendel and Naor. Markov type joins that list.
+https://doi.org/10.1007/BF02385837
+https://doi.org/10.1007/BF02766125
+https://doi.org/10.1142/S1793525309000114
+https://doi.org/10.1007/s00039-008-0689-0
+https://arxiv.org/pdf/0803.1697
+refs/mendel-naor-2013.pdf
+
+The proof runs by contradiction in four moves, and only four facts are
+taken from outside: the Hahn-Banach theorem, the finite Ramsey theorem,
+the finite-dimensional form of Goldstine's theorem, and the James-Enflo
+characterization, the only hard one, used exactly once. Suppose X has
+Markov type p > 1 with constant K and is not superreflexive. The
+characterization supplies a nonreflexive Banach space Y finitely
+representable in X, and the first construction turns Y into a norm N on
+the space c_00 of finite real sequences. That norm is unchanged when
+zeros are inserted between entries, replacing two adjacent entries by
+their sum never increases it, and every finite coordinate span of it
+embeds into X with distortion as close to 1 as desired. The second
+construction produces, for each integer n, a finite stationary reversible
+random walk with labels: every step label has N-norm 1, and the sum of the
+labels over n steps has N-norm at least n/24 with probability at least
+3/20. A lattice lift converts the labels into increments of a function of
+the state, so Markov type applies and bounds the p-th moment of that sum
+by K^p n. The two bounds give (3/20)(n/24)^p <= K^p n for every n, which
+fails for large n once p > 1.
+
+Write c_00 for the real sequences with finite support and b_i for the i-th
+coordinate vector, so that a finite list a = (a_1,...,a_m) of reals names
+the vector a_1 b_1 + ... + a_m b_m, with zeros appended when more room is
+needed. Its prefix sums are A_j = a_1 + ... + a_j for 0 <= j <= m. A norm
+N on c_00 is spreading invariant when
+
+ N(sum_i a_i b_i) = N(sum_i a_i b_{k_i}) for k_1 < ... < k_m,
+
+that is, when inserting zeros between the entries of a list changes
+nothing.
+
+Lemma (ordered norm). Let X be a real Banach space that is not
+superreflexive. Then c_00 carries a spreading invariant norm N with two
+further properties: merging two adjacent entries never increases the norm,
+
+ N(a_1,...,a_{i-1},a_i + a_{i+1},a_{i+2},...,a_m)
+ <= N(a_1,...,a_{i-1},a_i,a_{i+1},...,a_m),
+
+and for every m and every eta > 0 the space R^m with norm N embeds
+linearly into X with distortion below 1 + eta.
+
+The construction is a concrete version of the equal-sign-additive
+sequences of Brunel and Sucheston, where merging adjacent coefficients of
+the same sign preserves the norm; convexity then extends the contraction
+to coefficients of opposite sign. Ostrovskii records the finite
+representability form and its uses in metric embedding theory.
+https://doi.org/10.1016/0022-1236(76)90041-0
+https://doi.org/10.4153/CMB-2014-049-9
+https://doi.org/10.1016/j.jfa.2017.03.017
+
+Four steps give the lemma: a triangular array inside a nonreflexive space,
+a limit that spreads the array out, an averaging of subdivisions, and the
+merging properties.
+
+Step one. By the James-Enflo characterization there is a nonreflexive
+Banach space Y finitely representable in X. A nonreflexive space is a
+proper subspace of its second dual, so there are v in Y** and d > 0 with
+||v|| <= 1 and dist(v,Y) > d. Fix an integer M >= 1. Vectors y_1,...,y_M
+in the unit ball of Y and functionals f_1,...,f_M in the unit ball of Y*
+will be built so that
+
+ f_i(y_j) = 0 for j < i, |f_i(y_j) - d| <= 1/M for j >= i.
+
+Suppose y_1,...,y_{i-1} are already chosen, let E be their span, and let
+E^perp = {g in Y* : g = 0 on E}. Restriction to E^perp maps Y** onto
+(E^perp)* with kernel E: Hahn-Banach extends a bounded functional on
+E^perp to one on Y* of the same norm, and a functional that vanishes on
+E^perp comes from a point of E, since E is finite dimensional and hence
+reflexive. The quotient norm of v modulo E therefore equals the norm of
+its restriction to E^perp, so
+
+ || v restricted to E^perp || = dist(v,E) >= dist(v,Y) > d,
+
+and there is phi in E^perp with ||phi|| <= 1 and v(phi) > d. Put
+f_i = (d / v(phi)) phi. Then f_i vanishes on E, has norm at most 1, and
+satisfies v(f_i) = d.
+
+Goldstine's theorem in its finite form gives y_i. The point
+(v(f_1),...,v(f_i)) of R^i lies in the closure of the set of points
+(f_1(y),...,f_i(y)) with y in the unit ball of Y: otherwise a separating
+functional would produce f = sum_h c_h f_h with v(f) > ||f||, contradicting
+||v|| <= 1. So there is y_i in the unit ball of Y with |f_h(y_i) - d| <= 1/M
+for h = 1,...,i. This closes the induction.
+
+A consequence of the induction is used constantly. For increasing indices
+i_1 < ... < i_m and reals a_1,...,a_m put t = sum_h a_h y_{i_h}. For each
+j with 0 <= j < m the functional f_{i_{j+1}} has norm at most 1,
+annihilates y_{i_1},...,y_{i_j} and is within 1/M of d on
+y_{i_{j+1}},...,y_{i_m}. Hence f_{i_{j+1}}(t) lies within
+(1/M) sum_{h>j} |a_h| of d (a_{j+1} + ... + a_m), and
+
+ ||t|| >= d max_{0<=j<m} |a_{j+1} + ... + a_m|
+ - (1/M) sum_h |a_h|,
+
+while the triangle inequality and ||y|| <= 1 give ||t|| <= sum_h |a_h|.
+Read from the far end, where a_1 sits on the largest of the chosen
+vectors, the lower bound controls the prefix sums of the list a.
+
+Step two. Fix k, and for each m <= k choose a finite set G_m inside the
+cube [-1,1]^m that is k^{-2}-dense for the max norm. Let M be large and
+colour every increasing m-tuple of indices 1 <= i_1 < ... < i_m <= M by
+the list of bins of width 1/k holding the numbers
+
+ || sum_h a_h y_{i_{m+1-h}} || for a in G_m,
+
+so that the coefficients a_1, a_2, ... sit on the largest, second largest,
+... units, and the bound above controls prefix sums of a. There are
+finitely many colours, and their number depends on k alone.
+
+The finite Ramsey theorem, applied once for each arity m = 1,...,k inside
+the set surviving the previous application, produces a number B_k such
+that, for every M >= B_k and every colouring of this kind, there are k
+indices x_1 < ... < x_k in {1,...,M} with the following property: for
+every m <= k, every array a in the cube [-1,1]^m and every increasing
+m-tuple of those indices, the number || sum_h a_h x_{i_{m+1-h}} || differs
+from the number obtained from the top m indices by at most 3/k. The 3/k
+comes from two errors: a grid point a' within k^{-2} of a in each
+coordinate has the same colour, so gives numbers within 1/k, and moving
+from a' to a changes each of the two numbers by at most sum_h |a_h - a'_h|
+<= m k^{-2}.
+
+Step three. Take M = B_k and define, for m <= k and a in R^m,
+
+ N_k(a) = || sum_{h=1}^m a_h x_{k+1-h} ||,
+
+pairing a_1 with the largest of the k chosen vectors. Each N_k is a norm
+on each of these spaces, it is 1-Lipschitz for the l1 distance because
+||x_j|| <= 1, and the previous paragraph says that replacing the top m
+indices by any other increasing m-tuple of the chosen k changes the value
+by at most 3/k. On each R^m the norms are uniformly bounded and uniformly
+Lipschitz, so a diagonal subsequence converges uniformly on the cube
+[-1,1]^m for all m at once. The limit
+
+ N_0(a) = lim_j N_{k_j}(a)
+
+is a norm on c_00 in the sense that it is defined on each finite list and
+ignores trailing zeros. The bounds pass to the limit, so
+
+ d max_j |A_j| <= N_0(a) <= sum_i |a_i|
+
+for every list a with prefix sums A_j, and in particular
+N_0(a) >= (d/2) max_i |a_i|, since each entry is a difference of two
+prefix sums. Spreading invariance of N_0 follows from the 3/k estimate:
+both placements converge along the same subsequence, and 3/k tends to 0.
+
+The same estimate gives the embeddings. On the N_0-unit sphere of R^m,
+which is compact and bounded away from the origin by the lower bound, the
+map a -> sum_h a_h x_{k+1-h} has norm within 3/k of N_0 uniformly, so for
+large k its distortion is arbitrarily close to 1. Every finite coordinate
+span of N_0 therefore embeds into Y, and hence into X, with distortion as
+close to 1 as desired.
+
+Step four subdivides entries. For positive integers J_1,...,J_m and a list
+a of length m, let F_J a be the list obtained by replacing a_i with J_i
+consecutive copies of a_i/J_i, and write F_J for the case in which all
+multiplicities equal J. If J_i <= M_i for every i then N_0(F_M a) is at
+most N_0(F_J a). In block i of the longer list choose a uniformly random
+subset of size J_i, put a_i/J_i on that subset and zeros elsewhere, and do
+this independently in each block. Every outcome is F_J a with extra zeros
+inserted, so every outcome has N_0-norm N_0(F_J a), the mean of the
+outcomes is F_M a, and convexity of N_0 gives the inequality.
+
+The numbers N_0(F_J a) decrease as J grows and stay bounded below, since
+the prefix sums of a survive at block ends, so the limit
+
+ N(a) = lim_{J -> infinity} N_0(F_J a)
+
+exists. It is a norm on c_00: on each finite list it is a limit of norms,
+homogeneity and subadditivity pass to limits, and the two-sided bound
+survives as
+
+ d max_j |A_j| <= N(a) <= sum_i |a_i|,
+
+which also makes it positive definite. It is spreading invariant because
+each N_0(F_J .) is. It is invariant under subdivision as well: for every
+fixed choice of multiplicities, N(F_J a) = N(a). With J_- and J_+ the
+least and the greatest multiplicity, and r any positive integer,
+monotonicity gives
+
+ N_0(F_{rJ_+} a) <= N_0(F_r F_J a) <= N_0(F_{rJ_-} a),
+
+the outer terms tend to N(a) as r grows, and the middle term, whose
+multiplicities are r J_i, tends to N(F_J a).
+
+Merging two entries of the same sign preserves the norm. Take a_i and
+a_{i+1} positive with a rational ratio, choose positive integers with
+a_i/J_i = a_{i+1}/J_{i+1} = c, and keep all other multiplicities equal to
+1. Then F_J a is a run of J_i + J_{i+1} copies of c in those two slots,
+which is exactly F b for the list b obtained by replacing the two entries
+with a_i + a_{i+1}, so subdivision invariance gives N(b) = N(a).
+Continuity extends the identity to every pair of positive entries, and
+the case of two negative entries follows by changing all signs. An entry
+equal to zero is removed by spreading invariance.
+
+Merging arbitrary adjacent entries is contractive. Fix all entries except
+two adjacent slots and a real number s, and let f(t) be the N-norm of the
+list whose two free slots hold t and s - t. The assignment t -> (..., t,
+s - t, ...) is affine and N is a norm, so f is convex, and the preceding
+paragraph makes f equal to N(..., s, ...) on the segment between 0 and s.
+For s > 0 and t > s, writing s = (1 - s/t) 0 + (s/t) t and using convexity,
+
+ N(...,s,...) = f(s) <= (1 - s/t) f(0) + (s/t) f(t)
+ = (1 - s/t) N(...,s,...) + (s/t) f(t),
+
+so f(t) >= N(...,s,...). For t < 0 the roles of the two slots are
+exchanged, and s = 0 follows by continuity. Hence
+
+ N(..., a_i + a_{i+1}, ...) <= N(..., a_i, a_{i+1}, ...),
+
+which is the contraction required.
+
+The embeddings survive the last step. A finite coordinate span of N is the
+image under a subdivision map F_J of a finite coordinate span of N_0, and
+F_J is a (1 + eta)-isomorphism for the two norms once J is large, since
+N_0(F_J a) converges to N(a) uniformly on the unit sphere and the maps are
+uniformly Lipschitz. Composing with the embeddings of N_0 gives linear
+embeddings of the span into X with distortion as close to 1 as desired.
+
+A marked chain has a finite set S of states, a finite set E of oriented
+edges, maps e -> e^- and e -> e^+ from E to S, an involution e -> e^* of E
+with (e^*)^* = e, (e^*)^- = e^+ and (e^*)^+ = e^-, and probabilities
+q(e) >= 0 with sum over the edges leaving a state z equal to 1, for every
+z. Running the chain means choosing an edge leaving the current state and
+moving to its target. Several distinct edges may join the same ordered
+pair of states, which is what makes the chain marked rather than plain,
+and the marks carry labels. A probability pi on S is balanced when
+
+ pi(e^-) q(e) = pi(e^+) q(e^*) for every edge e,
+
+and then the state chain is stationary and reversible with law pi:
+summing the balance over the edges leaving z gives stationarity, and
+balance itself, read with e^* in place of e, is reversibility. A labelling
+g from E to a normed space V is odd when g(e^*) = -g(e) for every edge, so
+an edge equal to its own reverse carries label 0.
+
+An edge label need not be the difference of the values of a function on the
+states, and Markov type only controls differences of that form. A lattice
+lift supplies the missing potential, at the cost of a boundary.
+
+Lemma (odd edge labels). Let X be a real Banach space of Markov type p with
+constant K, and let V be a finite-dimensional normed space such that, for
+every eta > 0, there is a linear map T from V to X with
+||v|| <= ||Tv|| <= (1+eta)||v|| for every v in V. Let a finite balanced
+marked chain be given, with an odd labelling g from its edges to V, and let
+E_1, E_2, ... be the edges it chooses when started in the balanced law.
+Then for every n >= 1,
+
+ E || g(E_1) + ... + g(E_n) ||^p <= K^p n E || g(E_1) ||^p.
+
+Proof. The inequality is invariant under scaling, and if g vanishes
+identically there is nothing to prove. Otherwise choose one edge e_j from
+each two-element orbit of the involution, j = 1,...,r, and let u_1,...,u_r
+be the standard basis of Z^r. Give e_j the displacement u_j, give e_j^* the
+displacement -u_j, and give an edge fixed by the involution displacement 0.
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
+set S x Q. From (z,a) it proposes an edge e with probability q(e); if
+a + u(e) lies in Q it moves to (e^+, a + u(e)), and otherwise it stays at
+(z,a). A move of the second kind is a refusal. Every accepted transition
+satisfies
+
+ pi(z) q(e) mu(a) = pi(z') q(e^*) mu(a')
+
+with mu the uniform probability on Q, by balance and by uniformity of mu,
+and refusals are self-loops, so the lifted chain is stationary and
+reversible with law pi (x) mu.
+
+Define the potential Phi from S x Q to V by Phi(z,a) = sum_j a_j g(e_j).
+On an accepted transition along an edge e its increment is g(e): if e is
+e_j the j-th coordinate rises by 1 and the increment is g(e_j), if e is
+e_j^* that coordinate falls by 1 and the increment is -g(e_j) = g(e_j^*),
+and if e is fixed by the involution both the increment and the label are
+0. On a refusal the increment is 0. Hence the expected p-th power of the
+one-step increment is at most E||g(E_1)||^p.
+
+Now start the lifted chain in its stationary law. If the lattice
+coordinate of the initial state lies in Q' = {-R+n,...,R-n}^r, no refusal
+can occur during the first n steps, since each step changes each coordinate
+by at most 1 and the coordinate starts at distance at least n from the
+boundary. On that event the first n edges of the lifted chain and of the
+marked chain agree, and the displacement of the potential is exactly
+g(E_1) + ... + g(E_n). The event is independent of the labelled trajectory
+and 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):
+which tends to 1 as R grows. Markov type, applied to Phi on the lifted
+chain, gives
- alpha_R E ||g(E_1)+...+g(E_n)||^p <= K^p n E ||g(E_1)||^p,
+ alpha_R E || g(E_1) + ... + g(E_n) ||^p
+ <= E || Phi(Z_n) - Phi(Z_0) ||^p
+ <= K^p n E || g(E_1) ||^p.
-and let R -> inf. This proves (5.2).
+Let R tend to infinity. The same inequality holds for the target X by
+applying Markov type there to the composition of Phi with T, and then
+letting eta tend to 0.
-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.
+A chart of a finite ordered set Lambda is a strictly increasing map C from
+Lambda into {1,...,B}, and the rank of a point a of Lambda is C(a). For
+probability laws mu and mu' on a finite set, the total variation distance
+is half the sum of |mu - mu'| over the points, and the coupling that puts
+mass min(mu(t), mu'(t)) on each diagonal pair (t,t) makes the two
+coordinates agree with probability exactly 1 minus that distance.
-6. THE FINITE WALK
+Lemma (finite order averaging). For every finite ordered set Lambda and
+every eps > 0 there are an integer B and a probability law nu on charts of
+Lambda such that, whenever A and A' are increasing subtuples of Lambda of
+the same length,
-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
+ TV( law of C(A), law of C(A') ) < eps,
- N(g(e)) = 1 for every edge e, and (6.1)
+both laws taken under nu.
- 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
+Proof. List the pairs (A_rho, A'_rho), rho = 1,...,R, of distinct
+increasing subtuples of equal length, and let m_rho be that length. 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.
+ delta_{C(A_R)} - delta_{C(A'_R)} ),
+
+an element of the direct sum of the spaces of functions of sum zero on the
+increasing m_rho-tuples of {1,...,B}, with the l_1 norm in each summand
+and the sum of those norms as the norm of the direct sum.
+
+If some convex combination of the points v_C has norm below eps, its
+coefficients give the required law nu: the rho-th coordinate of the
+combination is the difference of the two laws in question, and the l_1
+norm of that difference is twice the total variation distance, which is
+therefore below eps.
+
+Suppose instead that the compact convex set of all convex combinations
+stays at distance at least eps from the origin. Hahn-Banach separation
+gives a functional f of norm at most 1 with f(v_C) >= eps for every chart
+C. The dual of a sum of l_1 spaces is a sum of spaces of bounded
+functions, so f is a finite family of functions f_rho from the increasing
+m_rho-tuples to [-1,1].
+
+Fix delta > 0 with R delta < eps, and colour every increasing m-tuple t of
+{1,...,B} by the list of intervals [k delta, (k+1) delta) that contain the
+numbers f_rho(t), over all rho with m_rho = m. There are finitely many
+colours, and their number depends only on R and delta.
+
+The finite Ramsey theorem is then applied once for each arity m, each time
+inside the set produced by the previous application. The result is a
+number B such that, for every colouring of this kind coming from any such
+family of functions, there is a set H inside {1,...,B} with as many points
+as Lambda whose increasing m-tuples all have the same colour, for every
+arity m at once. Let C be the increasing bijection from Lambda onto H. For
+each rho the tuples C(A_rho) and C(A'_rho) are increasing m_rho-tuples of
+H, hence receive the same colour, hence
+
+ | f_rho(C(A_rho)) - f_rho(C(A'_rho)) | <= delta,
+
+and summing over rho gives |f(v_C)| <= R delta < eps, which contradicts
+f(v_C) >= eps. So the convex hull does contain a point of norm below eps,
+and the required law exists.
+
+Nothing in the argument uses metric structure. The number B is a tower of
+exponentials in the size of Lambda, which is harmless, since Lambda is
+fixed while the chart law is chosen.
+
+The averaging lemma becomes a random walk on charts. Let Lambda be a finite
+ordered set and S a finite set of letters carrying a fixed-point-free
+involution s -> s^{-1}. For each letter s let D_s and R_s be subsets of
+Lambda with an order-preserving bijection T_s from D_s to R_s, and suppose
+T_{s^{-1}} is the inverse of T_s. Read T_s as the place where a landmark a
+moves when the letter s is played, the domain D_s being the set of
+landmarks whose move stays inside Lambda.
+
+Proposition (reversible chart transport). For every eps > 0 there are an
+integer B and a finite stationary reversible marked chain whose states are
+charts of Lambda into {1,...,B}, whose edge labels are the letters, and
+which has two properties: the letter of a step is independent of the past
+and uniform on S, and a step taken in the stationary law satisfies
+
+ C'(a) = C(T_s(a)) for every a in D_s
+
+with probability at least 1 - eps. Call such a step good.
+
+Proof. Take B and nu from the averaging lemma, with this Lambda and this
+eps, and handle one letter s first, the inverse being treated by symmetry
+at the end. The tuples T_s(D_s) and D_s have the same length, so their
+images under a chart of law nu have laws at total variation distance below
+eps. Couple those two tuple-valued random variables so that they agree
+with probability at least 1 - eps, using the diagonal coupling. Then
+extend each to a full chart: given the values of the first chart on
+T_s(D_s), sample the rest from nu conditioned on those values, and
+independently, given the values of the second chart on D_s, sample the
+rest from nu conditioned on those values. The result is a law lambda_s on
+pairs of charts with both marginals equal to nu, and with
+
+ C'(a) = C(T_s(a)) for all a in D_s
+
+holding with probability at least 1 - eps. For the inverse letter put
+lambda_{s^{-1}}(C,C') = lambda_s(C',C), which has the same marginals and
+the same agreement probability.
+
+Now build the chain. Its states are the charts of positive nu-mass. From a
+state C, first choose a letter s uniformly in S, independently of
+everything else, and then choose the next chart C' with probability
+lambda_s(C,C') / nu(C). These conditional probabilities sum to 1, because
+the first marginal of lambda_s is nu. The edge is the triple (C,s,C'), and
+its reverse is (C',s^{-1},C), which is again an edge since lambda_s has
+positive mass exactly where its reversed version does. The mass of the
+edge is
+
+ m(C,s,C') = (1/|S|) lambda_s(C,C'),
+
+because the chart C occurs with probability nu(C) and the conditional
+probability of the transition is lambda_s(C,C')/nu(C). Reversing the edge
+gives
+
+ m(C',s^{-1},C) = (1/|S|) lambda_{s^{-1}}(C',C)
+ = (1/|S|) lambda_s(C,C') = m(C,s,C'),
+
+so the mass is invariant under reversal, which is the balance condition.
+The chain is therefore stationary and reversible with law nu, and at a
+stationary step the pair of charts has law lambda_s with s uniform and
+independent of C, so the step is good with probability at least 1 - eps.
+
+The walk needs a mechanism by which a moving point keeps a fixed rank
+while the chart changes, and a way to read the reduced length of the
+letters played. Both come from increasing homeomorphisms of the line built
+out of four disjoint arcs.
+
+Let S = {u, v, u^{-1}, v^{-1}}, with u and v positive letters and their
+inverses negative, and let the involution exchange each letter with its
+inverse. Choose numbers 0 < alpha_s < beta_s < 1 whose closed intervals
+[alpha_s, beta_s] are pairwise disjoint, and put
+
+ A_s = union over integers j of [alpha_s + j, beta_s + j).
+
+A word is a finite string of letters. It is reduced when no letter is
+immediately followed by its inverse, and the reduced form of a word is
+obtained by scanning from left to right: delete the last letter kept when
+its inverse arrives, and append the incoming letter otherwise. Deletions
+in any order lead to the same reduced word, which is the usual
+cancellation in the free group on two generators. The reduced length is
+the number of letters that survive.
+
+Lemma (arcs and words). There are increasing homeomorphisms h_s of the
+line, one for each letter, such that
+
+ h_s(y+1) = h_s(y) + 1, h_{s^{-1}} is the inverse of h_s,
+
+ h_s( R \ A_{s^{-1}} ) = A_s,
+
+ | h_s(y) - y | < 2 for every real y,
+
+and if the nonempty word w = s_1 ... s_k is reduced, then h_w(0) lies in
+the interior of A_{s_1}, where h_w is the composition h_{s_1} o ... o
+h_{s_k}. In particular h_w(0) is not an integer.
+
+Proof. Define h_s for a positive letter s and then put h_{s^{-1}} equal to
+its inverse. On the closed interval from alpha_{s^{-1}} to
+alpha_{s^{-1}} + 1 let h_s be the increasing affine map that takes
+
+ alpha_{s^{-1}} to beta_s - 1,
+ beta_{s^{-1}} to alpha_s,
+ alpha_{s^{-1}} + 1 to beta_s.
+
+The three target values increase, because beta_s - 1 < alpha_s < beta_s
+when 0 < alpha_s < beta_s < 1, so the map is well defined with positive
+slopes. Extending by the periodicity relation gives a continuous
+increasing map of the line, since beta_s = (beta_s - 1) + 1 at the two
+ends of the interval, and its inverse is continuous.
+
+The identity of sets follows from the shape of that map. Each half-open
+interval [beta_{s^{-1}} + j, alpha_{s^{-1}} + j + 1) is carried exactly
+onto [alpha_s + j, beta_s + j), and as j runs over the integers the first
+family fills the complement of A_{s^{-1}} while the second fills A_s.
+Taking inverses gives the identity with s^{-1} in place of s.
+
+The displacement bound is checked at the three breakpoints, where the
+displacement equals beta_s - 1 - alpha_{s^{-1}} at the first and third and
+alpha_s - beta_{s^{-1}} at the second, all of modulus less than 2, and
+between breakpoints the displacement is affine, so its modulus is at most
+the larger of the two endpoint values. Periodicity extends the bound to
+the whole line, and the same bound holds for the inverse maps.
+
+For the last assertion, note first that 0 lies outside every A_s, since
+each A_s sits inside the union of the intervals (0,1) + j. Read the
+reduced word from the right: h_w(0) = h_{s_1}( ... h_{s_k}(0) ... ). Now 0
+lies in the complement of A_{s_k^{-1}}, so the set identity with s = s_k
+places h_{s_k}(0) in the interior of A_{s_k}. If a point lies in the
+interior of A_{s_i} and the word is reduced, then s_{i-1} differs from
+s_i^{-1}, so the point lies outside A_{s_{i-1}^{-1}}, because the closed
+base intervals are pairwise disjoint, and the set identity with
+s = s_{i-1} places its image in the interior of A_{s_{i-1}}. After the
+last step h_w(0) lies in the interior of A_{s_1}, and an interior point of
+A_{s_1} cannot be an integer.
+
+A word acts on points, and a periodic counting function follows it. Put
+c_s = 1 for a negative letter and c_s = 0 for a positive one, and define
+
+ chi_s(y) = 1 if y lies in A_s, else 0, minus c_s.
-The reason for the constant c_s is that it makes the sign flip under
-reversal, as follows.
+The constant is there to make the counting function flip sign under
+reversal. The set identity gives the flip at once: a point y lies in A_s
+exactly when h_s^{-1}(y) lies outside A_{s^{-1}}, so
-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),
- 1_{A_{s^{-1}}}(h_s^{-1}(y)) = 1 - 1_{A_s}(y). (9.5)
+and since c_{s^{-1}} = 1 - c_s,
-Since c_{s^{-1}} = 1 - c_s,
+ chi_{s^{-1}}( h_s^{-1}(y) ) = - chi_s(y).
- 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 iterate
+y_i = h_{s_i}^{-1}(y_{i-1}), so that the point after the whole word is
+y_k = h_w^{-1}(y). Define
-Now fix a word w = s_1 ... s_k and a starting point y_0 = y, and define
+ c_w(y) = chi_{s_1}(y_0) + chi_{s_2}(y_1) + ... + chi_{s_k}(y_{k-1}).
- y_i = h_{s_i}^{-1}(y_{i-1}), c_w(y) = sum_{i=1}^{k} chi_{s_i}(y_{i-1}).
- (9.7)
+Two facts about this sum matter. It is periodic, c_w(y+1) = c_w(y),
+because each h_s commutes with translation by an integer and each chi_s is
+1-periodic. And it is unchanged when an adjacent inverse pair is deleted
+from the word: if s_{i+1} = s_i^{-1} = s^{-1}, then y_{i+1} = h_s(y_i) and
+also y_{i-1} = h_s(y_i), so the two points coincide, and the two terms
+contributed by the pair are chi_s(h_s(y_i)) + chi_{s^{-1}}(y_i) = 0 by the
+sign flip. Every other point and every other term is untouched.
-The final point after the last step is y_k = h_w^{-1}(y).
+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,
-Two elementary facts, both used later.
+ c_w(j) = - n-, c_w( h_w(0) + j ) = n+.
-(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.
+Proof. By the cancellation property the word may be replaced by its
+reduced form t_1 ... t_ell.
-(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.
+Start at y_0 = j. The claim is that y_{i-1} lies outside A_{t_i} for every
+i, so every indicator in the sum vanishes and the constants contribute
+-n-. The claim is proved by induction. An integer lies outside A_{t_1}.
+If y_{i-1} lies outside A_{t_i}, then y_i = h_{t_i}^{-1}(y_{i-1}) lies in
+A_{t_i^{-1}}, by the set identity applied with s = t_i^{-1}, and since the
+word is reduced t_{i+1} differs from t_i^{-1}, so the sets A_{t_{i+1}} and
+A_{t_i^{-1}} are disjoint and y_i lies outside A_{t_{i+1}}.
-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}),
+Start now at y_0 = h_w(0) + j. The claim is that y_{i-1} lies in A_{t_i}
+for every i, so every indicator equals 1 and the sum is ell - n- = n+.
+Here y_{i-1} = h_{t_i ... t_ell}(0) + j for every i, by induction on i
+from the definition and the periodicity relation, and the word
+t_i ... t_ell is a suffix of a reduced word, hence reduced, so by the
+interior property h_{t_i...t_ell}(0) lies in the interior of A_{t_i}.
+Adding the integer j keeps it there by periodicity.
- y_{i+1} = h_{s^{-1}}^{-1}(y_i) = h_s(y_i) = y_{i-1}.
+The two families are interlaced. Let m be the integer part of h_w(0) and
+let z = h_w(0) - m, so 0 < z < 1 because h_w(0) is not an integer. The two
+formulas above, applied with j and with j - m, give
-So the point after the pair equals the point before it, and the two terms
-they contribute are
+ c_w(j) = - n-, c_w(z + j) = n+
- chi_s(y_{i-1}) + chi_{s^{-1}}(y_i) = chi_s(h_s(y_i)) + chi_{s^{-1}}(y_i)
- = 0
+for every integer j, and the points satisfy j < z + j < j + 1. The gap
+between the two levels is n+ + n- = ell, the reduced length.
-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).
+Fix a norm N satisfying the ordered-norm lemma and fix an integer n >= 1.
+Put L = 8(n+1) and eps = 1/(10n), and for k >= 1 put
-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,
+ D_k = N(1,-1,1,-1,...,1,-1) with k pairs.
- c_w(j) = - n_-, c_w(h_w(0) + j) = n_+. (9.8)
+Each D_k is positive, since N is a norm and the list is nonzero, and
+spreading invariance together with the triangle inequality gives
+D_{k+l} <= D_k + D_l, so D_L <= 2 D_{L/2} and N of a run of k pairs
+(+c,-c) equals |c| D_k.
-Proof. By 9.4(b) we may replace w by its reduced form t_1 ... t_ell.
+The landmarks are the points the charts have to keep track of:
-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_-.
+ Lambda = { alpha_s + j, beta_s + j : s in S, 0 <= j < L }
+ union { h_w(0) + j : |w| <= n, -2n <= j <= L + 2n },
-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},
+with |w| the length of the word before reduction, the empty word included,
+and repeated points counted once. For a letter s let D_s be the set of
+points a of Lambda with h_s(a) in Lambda, and let T_s be h_s restricted to
+D_s. Then T_s is an order-preserving bijection from D_s onto its image, and
+T_{s^{-1}} is its inverse, so chart transport applies with this Lambda and
+this letter set. It gives an integer B and a finite stationary reversible
+marked chain on charts of Lambda into {1,...,B} whose letters are
+independent and uniform and whose stationary steps satisfy
- h_{t_i}^{-1}( R \ A_{t_i} ) = A_{t_i^{-1}},
+ C'(a) = C(h_s(a)) for every a in D_s
-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.
+with probability at least 1 - eps. Call such a step good. Each stationary
+step is good with probability at least 1 - eps, so all of the first n steps
+are good with probability at least 1 - n eps = 9/10.
-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_+.
+The labels are arrays indexed by the ranks of a chart. For a positive
+letter define
-First compute the intermediate points. For every i,
+ g(C,s,C') = sum over 0 <= j < L of
+ ( b_{C(alpha_s + j)} - b_{C(beta_s + j)} ),
- y_{i-1} = h_{t_i ... t_ell}(0) + j. (9.9)
+a list of length B with entry +1 at the rank of alpha_s + j and -1 at the
+rank of beta_s + j, and for a negative letter define g by oddness,
-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).
+ g(C,s,C') = - g(C', s^{-1}, C).
-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).
+Every edge label has N-norm exactly D_L, for the following reason. A chart
+is strictly increasing and
-9.6 Two interlaced families. Let w be a word whose reduced form has length
-ell > 0, and let
+ alpha_s + j < beta_s + j < alpha_s + j + 1 < beta_s + j + 1,
- m = floor(h_w(0)), z = h_w(0) - m.
+so the 2L ranks appearing in the sum are distinct and the list is
+(1,-1,1,-1,...,1,-1) in rank order, that is, a run of L pairs written
+without the zeros in between. Spreading invariance removes the zeros, and
+the negative letters give the same number by oddness.
-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
+Follow a trajectory C_0, s_1, C_1, ..., s_n, C_n all of whose steps are
+good, and let w = s_1 ... s_n have reduced length ell > 0. Put
+m = floor(h_w(0)) and z = h_w(0) - m. Since each letter moves each point by
+less than 2, the point h_w(0) has modulus below 2n, so -2n <= m <= 2n - 1,
+and z lies strictly between 0 and 1 because h_w(0) is not an integer.
- c_w(j) = - n_-, c_w(z + j) = n_+ (9.10)
+For integers j with L/4 <= j <= 3L/4 put
-for every integer j, because h_w(0) + (j - m) = z + j. The two families of
-points are interlaced:
+ r_j = C_0(j), t_j = C_0(z + j).
- j < z + j < j + 1.
+Both points belong to Lambda: the first because j lies between 0 and L,
+and the second because z + j = h_w(0) + (j - m) with |w| = n and
+j - m between -2n and L + 2n. Since j < z + j < j + 1 and C_0 increases,
-The gap between the two levels is
+ r_j < t_j < r_{j+1}.
- n_+ - (-n_-) = ell,
+Now follow two families of points through the trajectory. In the first
+family y_0 = j, in the second y_0 = z + j, and in both cases
+y_i = h_{s_i}^{-1}(y_{i-1}) for i = 1,...,n. Induction with the
+periodicity relation gives
-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.
+ y_i = h_{(s_1 ... s_i)^{-1}}(0) + j first family,
+ y_i = h_{s_{i+1} ... s_n}(0) + j - m second family,
-10. CONSTRUCTION OF THE FINITE WALK
+and therefore |y_i - j| < 2i in the first family and
+|y_i - (z + j)| < 2i in the second, because each h_s displaces a point by
+less than 2. With L/4 = 2n + 2 and 3L/4 = 6n + 6 this gives, for every i
+from 0 to n,
-This section proves Proposition 6.1.
+ j - 2n < y_i < j + 1 + 2n, hence 0 < y_i < L.
-10.1 Fix the norm N and the integer n. Put
+Every point y_i lies in Lambda, being a shifted orbit point of a word of
+length at most n. Since h_{s_i}(y_i) = y_{i-1} and both points lie in
+Lambda, and since the step is good,
- L = 8(n+1), eps = 1/(10n),
+ C_i(y_i) = C_{i-1}(y_{i-1}) = ... = C_0(y_0).
-and for k >= 1 put
+This rank identity is what lets a moving point be read in a fixed chart.
- D_k = N(1,-1,1,-1,...,1,-1) (k pairs).
+Let G be the sum of the n labels along the trajectory, an array of length
+B, and let F(k) = G_1 + ... + G_k for 0 <= k <= B be its prefix sums. Each
+label has total sum 0, since the +1 and -1 entries balance, so
+F(0) = F(B) = 0.
-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.
+One identity controls those prefix sums. For points alpha < beta and y of
+Lambda and any chart C,
-STEP 1: THE FINITE CHART CHAIN.
+ sum over a <= C(y) of ( b_{C(alpha)} - b_{C(beta)} )_a
+ = 1 if alpha <= y < beta, else 0,
-Let Lambda be the following finite set of reals, ordered as usual:
+because the sum counts entries up to the rank of y, and comparing ranks is
+comparing points. This is where the half-open intervals pay off. The
+contribution of the i-th label to F(C_0(y_0)) is therefore exactly
+chi_{s_i}(y_{i-1}). For a positive letter the label is read in chart
+C_{i-1} and the contribution is the indicator of A_{s_i} at y_{i-1},
+since 0 < y_{i-1} < L leaves room for at most one of the L arcs. For a
+negative letter the label is read in chart C_i and the contribution is
+minus the indicator of A_{s_i^{-1}} at y_i, which equals the indicator of
+A_{s_i} at y_{i-1} minus 1. Summing over i,
- Lambda = { alpha_s + j, beta_s + j : s in S, 0 <= j < L }
- U { h_w(0) + j : |w| <= n, -2n <= j <= L + 2n },
+ F(C_0(y_0)) = c_w(y_0).
-where |w| is the length of w before reduction, the empty word is included,
-and repeated points are counted once.
+The reduced length enters only here, in the scalar sum c_w; the array G
+keeps all n labels.
-For s in S put
+Apply this with y_0 = j and with y_0 = z + j, and let n+ and n- be the
+letter counts of the reduced form of w. The two-level lemma gives
- D_s = { a in Lambda : h_s(a) in Lambda }, T_s = h_s restricted to D_s.
+ F(r_j) = - n- =: V, F(t_j) = n+ =: U, U - V = ell.
-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}.
+Take a = L/4 and b = 3L/4 and list the cuts in increasing order:
-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
+ 0, r_a, t_a, r_{a+1}, t_{a+1}, ..., r_{b-1}, t_{b-1}, r_b, B.
- C'(a) = C(h_s(a)) for every a in D_s. (10.1)
+All of them are distinct. The inequalities r_j < t_j < r_{j+1} come from
+the interlacing, the two ends are strict because C_0(a) >= 1 and because
+the point L + 2n of Lambda is larger than b, so C_0(b) is not the largest
+rank. With F(0) = F(B) = 0 the prefix sums at the cuts, and the sums of G
+over the blocks between consecutive cuts, are
-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.
+ cut 0 r_a t_a r_{a+1} ... t_{b-1} r_b B
+ F 0 V U V ... U V 0
+ block sum V ell -ell ell ... -ell -V
-THE LABELLING. For a positive letter s define
+so there are L/2 = b - a inner pairs (ell,-ell).
- g(C,s,C') = sum_{j=0}^{L-1} ( b_{C(alpha_s + j)} - b_{C(beta_s + j)} ), (10.2)
+Replacing each block by its sum is contractive, by the merging property
+applied inside the blocks, so
-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
+ N(G) >= N( V, ell, -ell, ell, -ell, ..., ell, -ell, -V ).
- g(C,s,C') = - g(C', s^{-1}, C). (10.3)
+Write that array as the sum of A = (V,0,...,0,-V) and
+B' = (0,ell,-ell,...,ell,-ell,0). Then N(A) = |V| D_1 and N(B') =
+ell D_{L/2}, so the triangle inequality in the form
+N(B') <= N(G) + N(A) gives
-This is odd by construction: reversing an edge and using (10.3) flips the
-sign.
+ N(G) >= ell D_{L/2} - |V| D_1 >= ell (D_{L/2} - D_1),
-Every edge label has N-norm exactly D_L. Look at (10.2): the chart C is
-strictly increasing and
+since |V| = n- <= ell.
- alpha_s + j < beta_s + j < alpha_s + (j+1) < beta_s + (j+1)
+Cutting instead only at 0, r_j, B gives block sums (V,-V), so
+N(G) >= |V| D_1; cutting only at 0, t_j, B gives N(G) >= U D_1. Since
+|V| + U = n- + n+ = ell,
-(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) >= max(|V|,U) D_1 >= (ell/2) D_1.
- N(g(e)) = D_L > 0 for every edge e. (10.4)
+For nonnegative A and B, max(A - B, B/2) >= A/3: if A - B >= A/3 there is
+nothing to prove, and otherwise B > 2A/3 and B/2 > A/3. Applying this with
+A = ell D_{L/2} and B = ell D_1, and using D_L <= 2 D_{L/2},
-STEP 2: TRANSPORT OF RANKS ALONG A GOOD TRAJECTORY.
+ N(G) >= (ell/3) D_{L/2} >= (ell/6) D_L.
-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
+It remains to see how large the reduced length is. The letters are
+independent and uniform in the four-letter set, with or without
+conditioning 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 incoming
+letters cancels the last one and the other three increase the length by 1,
+while if ell_{k-1} = 0 every letter increases it by 1. So
- m = floor(h_w(0)), z = h_w(0) - m.
+ E[ ell_k | past ] >= ell_{k-1} + 1/2,
-By (9.4) the point h_w(0) lies in the open arc A_{s_1}, so
+and summing gives E ell_n >= n/2. Since 0 <= ell_n <= n,
- 0 < z < 1.
+ n/2 <= E ell_n <= n/4 + n Prob{ ell_n >= n/4 },
-For integers j with L/4 <= j <= 3L/4 define the two ranks
+so Prob{ell_n >= n/4} >= 1/4. The steps are good with probability at least
+9/10, so with probability at least 1/4 - 1/10 = 3/20 all n steps are good
+and ell >= n/4 at the same time. On that event
- r_j = C_0(j), t_j = C_0(z + j). (10.5)
+ N(G) >= (n/4)(1/6) D_L = (n/24) D_L.
-Both are defined: j lies in [0,L) so j is in Lambda; and
+Dividing every label by the positive number D_L leaves the chain unchanged,
+keeps the labelling odd, makes every edge label have N-norm 1, and turns
+the last display into
- z + j = h_w(0) + (j - m),
+ Prob{ N( g(E_1) + ... + g(E_n) ) >= n/24 } >= 3/20.
-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,
+So every edge label has N-norm 1, and the sum over n steps reaches n/24
+with probability at least 3/20.
- r_j < t_j < r_{j+1} whenever all the ranks are defined. (10.6)
+Suppose now that X is not superreflexive and has Markov type p > 1 with
+constant K. Take the norm N of the ordered-norm lemma, fix an integer n,
+and take the marked chain and odd labelling just built for this N and this
+n. All labels lie in a finite coordinate span W of c_00 with the
+restriction of N. That span is finite dimensional, and by the third
+property of N it embeds into X with distortion as close to 1 as
+wanted, which is exactly the hypothesis of the odd-label lemma. Applying
+that lemma with target X and with V = W, and using that every edge label
+has N-norm 1,
-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
+ E N( g(E_1) + ... + g(E_n) )^p <= K^p n E N( g(E_1) )^p = K^p n.
- 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.
+On the other hand the sum is at least n/24 with probability at least 3/20
+and is never negative, so its p-th moment is at least (3/20)(n/24)^p.
+Therefore
-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.
+ (3/20)(n/24)^p <= K^p n
+
+for every integer n >= 1, that is,
+
+ (3/20) n^{p-1} / 24^p <= K^p.
+
+Since p > 1 the left side tends to infinity with n while the right side is
+fixed. This is impossible, so X is superreflexive.
+
+Three remarks on what entered where. The hypothesis p > 1 is used exactly
+once, in the last display; for p = 1 the inequalities are consistent, and
+indeed no contradiction is available. The finiteness of K is used once,
+when the odd-label lemma is applied. Everything else in the argument is
+quantitative in n but not in K: the walk constructed for a given n has
+size depending on n, its labels live in a span whose dimension depends on
+n, and only the constant K has to serve all n at once. The numbers 24 and
+3/20 are crude. They come from L = 8(n+1), from eps = 1/(10n) whose n-fold
+sum must stay below 1/10, from the level gap ell >= n/4 whose probability
+is at least 1/4, and from D_L <= 2 D_{L/2}; any constants with those four
+properties would serve.
+
+The hypothesis cannot be weakened to Rademacher type. Sums with
+independent random signs are blind to nonreflexivity, as James's
+nonreflexive space of Rademacher type 2 shows, while reversible walks see
+it. The distinction is quantitative: the walk built from the charts
+converts a random reduced word of length about n into a displacement of
+norm about n, whereas Markov type allows displacements of norm at most
+about the square root of the number of steps in the p-th moment sense. A
+linear rate and a square-root rate cannot coexist for large n.
+
+The same circle of ideas gives the metric characterization. Superreflexive
+spaces carry equivalent uniformly smooth norms of power type p for some
+p > 1, such norms give Markov type p for 1 < p <= 2, and the present
+argument gives superreflexivity back from Markov type p for any p > 1. So
+for real Banach spaces
+
+ superreflexive, Markov type p for some p > 1,
+ Markov type p for some 1 < p <= 2
+
+are equivalent, and a question of Naor about nontrivial Markov type without
+an equivalent uniformly smooth norm has a negative answer. Two further
+metric criteria for the same class sit nearby: the distortion of finite
+binary trees, due to Bourgain, and the distortion of diamond graphs, due
+to Johnson and Schechtman, while Markov convexity of Lee, Naor and Peres
+asks a related but different question about trees and was shown by Mendel
+and Naor to characterize superreflexivity as well.