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= 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 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,
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
<= E || Phi(Z_n) - Phi(Z_0) ||^p
<= K^p n E || g(E_1) ||^p.
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.
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.
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,
TV( law of C(A), law of C(A') ) < eps,
both laws taken under nu.
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)} ),
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 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
1_{A_{s^{-1}}}( h_s^{-1}(y) ) = 1 - 1_{A_s}(y),
and since c_{s^{-1}} = 1 - c_s,
chi_{s^{-1}}( h_s^{-1}(y) ) = - chi_s(y).
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
c_w(y) = chi_{s_1}(y_0) + chi_{s_2}(y_1) + ... + chi_{s_k}(y_{k-1}).
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.
Lemma (two levels). Let the reduced form of w have length ell > 0, with n+
positive and n- negative letters, so ell = n+ + n-. Then for every integer
j,
c_w(j) = - n-, c_w( h_w(0) + j ) = n+.
Proof. By the cancellation property the word may be replaced by its
reduced form t_1 ... t_ell.
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}}.
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.
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
c_w(j) = - n-, c_w(z + j) = n+
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.
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
D_k = N(1,-1,1,-1,...,1,-1) with k pairs.
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.
The landmarks are the points the charts have to keep track of:
Lambda = { alpha_s + j, beta_s + j : s in S, 0 <= j < L }
union { h_w(0) + j : |w| <= n, -2n <= j <= L + 2n },
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
C'(a) = C(h_s(a)) for every a in D_s
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.
The labels are arrays indexed by the ranks of a chart. For a positive
letter define
g(C,s,C') = sum over 0 <= j < L of
( b_{C(alpha_s + j)} - b_{C(beta_s + j)} ),
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,
g(C,s,C') = - g(C', s^{-1}, C).
Every edge label has N-norm exactly D_L, for the following reason. A chart
is strictly increasing and
alpha_s + j < beta_s + j < alpha_s + j + 1 < beta_s + j + 1,
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.
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.
For integers j with L/4 <= j <= 3L/4 put
r_j = C_0(j), t_j = C_0(z + j).
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,
r_j < t_j < r_{j+1}.
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
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,
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,
j - 2n < y_i < j + 1 + 2n, hence 0 < y_i < L.
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,
C_i(y_i) = C_{i-1}(y_{i-1}) = ... = C_0(y_0).
This rank identity is what lets a moving point be read in a fixed chart.
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.
One identity controls those prefix sums. For points alpha < beta and y of
Lambda and any chart C,
sum over a <= C(y) of ( b_{C(alpha)} - b_{C(beta)} )_a
= 1 if alpha <= y < beta, else 0,
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,
F(C_0(y_0)) = c_w(y_0).
The reduced length enters only here, in the scalar sum c_w; the array G
keeps all n labels.
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
F(r_j) = - n- =: V, F(t_j) = n+ =: U, U - V = ell.
Take a = L/4 and b = 3L/4 and list the 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 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
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
so there are L/2 = b - a inner pairs (ell,-ell).
Replacing each block by its sum is contractive, by the merging property
applied inside the blocks, so
N(G) >= N( V, ell, -ell, ell, -ell, ..., ell, -ell, -V ).
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
N(G) >= ell D_{L/2} - |V| D_1 >= ell (D_{L/2} - D_1),
since |V| = n- <= ell.
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,
N(G) >= max(|V|,U) D_1 >= (ell/2) D_1.
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},
N(G) >= (ell/3) D_{L/2} >= (ell/6) D_L.
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
E[ ell_k | past ] >= ell_{k-1} + 1/2,
and summing gives E ell_n >= n/2. Since 0 <= ell_n <= n,
n/2 <= E ell_n <= n/4 + n Prob{ ell_n >= n/4 },
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
N(G) >= (n/4)(1/6) D_L = (n/24) D_L.
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
Prob{ N( g(E_1) + ... + g(E_n) ) >= n/24 } >= 3/20.
So every edge label has N-norm 1, and the sum over n steps reaches n/24
with probability at least 3/20.
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,
E N( g(E_1) + ... + g(E_n) )^p <= K^p n E N( g(E_1) )^p = K^p n.
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
(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.