Nontrivial Markov Type Forces Superreflexivity

Proof. Choose one edge e_j from each two-element star orbit, 1\leq j\leq r, and let u_j be the coordinate vectors of \Z^r. Give e_j displacement u_j and e_j^* displacement -u_j. A fixed point of star has label zero and is given displacement zero. If r=0, there is nothing to prove.

For an integer R>n, put Q_R=\{-R,\ldots,R\}^r. Lift the chain to S\times Q_R by choosing an edge as before and making the corresponding lattice move. If the move would leave Q_R, remain at the same full state. Every accepted transition satisfies detailed balance under \pi\otimes\operatorname{Unif}(Q_R) by (2.5); rejections add only self-loop probabilities. This is a finite stationary reversible chain.

Define

On an accepted edge its increment is g(e), and on a rejection its increment is zero. The expected one-step cost is therefore at most \E\norm{g(E_1)}^p. If the initial lattice point lies in Q_{R-n}, every possible sequence of n edges is accepted. Couple the lifted walk to the original marked walk by using the same proposed edges until the first rejection. On this interior event the first n edges agree, and the event is independent of the original marked trajectory. Its probability is

Consequently the expected n-step cost of the lifted potential is at least \alpha_R\E\norm{\sum_{i=1}^n g(E_i)}^p. Applying Markov type to \Phi gives

Let R\to\infty. The last assertion follows from finite-dimensional transfer; enlarging the cube does not enlarge the span of the labels.□

Proof of Theorem 1.1. Suppose that X has Markov type p>1 with constant K and is not superreflexive. Lemma 2.1 supplies a spreading invariant norm N with contractive adjacent merging, whose finite coordinate spans embed in X with arbitrarily small distortion. For each n, apply Proposition 2.2 to N. Lemma 2.3, applied through the finite span of these labels, gives

Since n is arbitrary and K is fixed, this contradicts p>1.□

Proof. List all nontrivial ordered comparisons (A_\rho,A'_\rho) of equal-length subtuples, 1\leq\rho\leq R. The assertion is immediate if R=0. Let m_\rho be their common length, and let T_{B,m} denote the increasing m-tuples in \{1,\ldots,B\}. For each chart C, form the vector

where W_B carries the sum norm. It suffices to show that \conv\{v_C\} contains a vector of norm less than \epsilon: its convex coefficients give \nu, and each individual total-variation distance is at most half the resulting norm.

Fix \delta>0 with R\delta<\epsilon. A dual functional of norm at most 1 is a collection f_\rho:T_{B,m_\rho}\to[-1,1]. For each m, color the m-tuples by the list of bins of width at most \delta containing f_\rho for all \rho with m_\rho=m. The number of colors is bounded in terms of R and \delta, independently of the functions and of B. The finite Ramsey theorem therefore supplies a single sufficiently large B such that, for every such collection of functions, there is a set H\subseteq\{1,\ldots,B\} of size |\Lambda| homogeneous for all these colorings. Map \Lambda increasingly onto H. Then

If the compact convex set \conv\{v_C\} had distance at least \epsilon from zero, finite-dimensional separation would give a dual functional of norm 1 whose value on every v_C is at least \epsilon, contradicting the preceding bound. Thus the required convex combination exists.□

Proof. Apply Lemma 3.1 to obtain B and a chart law \nu. The matching condition is

Figure 1 depicts the rank equality needed along one transition.

For one representative of each inverse pair, couple two charts with law \nu so that (3.10) holds with probability at least 1-\epsilon. Such a coupling exists by (3.9). For two laws \mu,\mu' on the same finite set, place mass \min\{\mu(a),\mu'(a)\} at each diagonal pair (a,a) and couple the remaining masses arbitrarily. The matching probability is 1-\TV(\mu,\mu'). Apply this to the laws of C(T_s(D_s)) and C'(D_s), then sample the full charts from their conditional distributions. Denote the resulting coupling by \lambda_s. For the inverse index set

This gives the inverse version of (3.10), with the same success probability.

Discard charts of zero \nu-mass and start C_0 with law \nu. At each step choose a fresh uniform letter s\in\cS, independently of the past. From the current chart C, then choose C' with probability \lambda_s(C,C')/\nu(C) and record (C,s,C'). The first marginal of \lambda_s is \nu, so these conditional probabilities sum to one. Its stationary edge mass is

which is invariant under (C,s,C')^*=(C',s^{-1},C). We have therefore constructed a finite stationary reversible marked chain with independent uniform letters. At stationarity, each step fails (3.10) with probability at most \epsilon.□

Proof. For positive s, define h_s to be affine on the intervals between the following three points, with the indicated values:

Both slopes are positive. Extend by h_s(y+1)=h_s(y)+1, and define h_{s^{-1}}=h_s^{-1}. The complement intervals [\beta_{s^{-1}}+j,\alpha_{s^{-1}}+j+1) map exactly onto [\alpha_s+j,\beta_s+j), proving the set identity for positive letters. Taking complements and inverses proves it for negative letters. At the breakpoints |h_s(y)-y|<2; the difference is affine between breakpoints and periodic. The same displacement bound holds for inverses.

The point 0 lies outside all the arc closures. Reading a reduced word from right to left, the first image lies in the interior of the arc of the rightmost letter. At every subsequent step this arc is disjoint from the inverse arc of the next letter, so the image enters the interior of that letter’s arc. This proves (4.14).□

Proof. We may replace w by its reduced form t_1\cdots t_\ell. Start first at j. Before the first letter the point is outside every arc. If the point before t_i is outside \cA_{t_i}, its inverse image under h_{t_i} belongs to \cA_{t_i^{-1}}; this is disjoint from \cA_{t_{i+1}} because the word is reduced. Thus every indicator \one_{\cA_{t_i}} in (4.17) is zero, giving the first equality.

Starting instead at h_w(0)+j, the point before t_i is h_{t_i\cdots t_\ell}(0)+j. By (4.14) it lies in \cA_{t_i}, so every indicator is one. The sum is \ell-n_-=n_+.□

Proof of Proposition 2.2. Fix a norm N as in the proposition. We first construct labels with a common nonzero norm and normalize them at the end. For k\geq1, put

These numbers are positive, and spreading invariance and the triangle inequality give D_{k+l}\leq D_k+D_l.

Step 1: the finite chart chain. Fix an integer n\geq1, and let

Use the homeomorphisms of Lemma 4.1. The landmarks below record the interval endpoints used by labels and all orbit points needed to follow n steps. The integer shifts provide a margin around the label window. Let \Lambda be the following finite subset of \R, in its usual order:

All displayed shifts j are integers, |w| denotes the length before reduction, the empty word is included, and coincident points are counted only once. For each s use the partial order-preserving bijection

Its inverse is T_{s^{-1}}. Proposition 3.2 gives a finite stationary reversible marked chain on charts; denote its stationary chart law by \nu. Call a transition (C,s,C') good when

Every step is good with probability at least 1-\epsilon.

For positive s, define

and define negative labels by oddness: g(C,s,C')=-g(C',s^{-1},C). Strict increase of the charts and spreading invariance imply

for every transition, good or otherwise.

Step 2: transport along a good trajectory. Consider a trajectory (C_{i-1},s_i,C_i)_{i=1}^n all of whose steps are good, and let w=s_1\cdots s_n have reduced length \ell>0. Put

Since every letter moves every point by less than 2, |h_w(0)|<2n, so -2n\leq m\leq2n-1; and (4.14) gives 0<z<1. For the integers L/4\leq j\leq3L/4, define

These points belong to \Lambda by (5.19), and r_j<t_j<r_{j+1} whenever the indices occur.

For either starting point y_0=j or y_0=z+j, follow y_i=h_{s_i}^{-1}(y_{i-1}). For the first family,

for the second,

The words have length at most n, and the shifts lie in [-2n,L+2n]. Thus all these points belong to \Lambda. Moreover, for every 0\leq i\leq n,

and the whole interval lies in (0,L) for the chosen range of j. Because h_{s_i}(y_i)=y_{i-1}, goodness gives

Step 3: cumulative coefficient sums. Let

Every label has total coefficient sum zero, so F(0)=F(B)=0. For landmarks \alpha<\beta and y, strict increase of a chart gives

This explains the half-open interval convention. Evaluate F at a transported rank C_0(y_0). For a positive step, (5.21), (5.25), and y_{i-1}\in(0,L) therefore give the contribution \one_{\cA_{s_i}}(y_{i-1}). For a negative step the label is read in chart C_i. Since y_i\in(0,L) as well, its contribution is

Thus in both cases the contribution is \chi_{s_i}(y_{i-1}), and

Reduction is applied to this scalar expression; G retains all n original edge labels. Let n_+,n_- be the numbers of positive and negative letters in the reduced word. Lemma 4.2, applied with the integer shifts j and j-m, now gives

Step 4: converting oscillations to norm. Put a=L/4 and b=3L/4. The selected cuts and their prefix sums determine every consecutive block sum:

The last row gives the sum of the block ending at that cut. There are b-a=L/2 inner pairs. Replacing every block by its sum is contractive and yields

The last block is nonempty, since the rank t_b from (5.23) satisfies r_b<t_b\leq B. We control the endpoint contribution by combining the estimate from all oscillations with the estimate from a single level. Subtracting the endpoint array by the triangle inequality and using |V|\leq\ell gives

Independently, partitioning just at an r_j or a t_j gives the arrays (V,-V) and (U,-U). Hence

For nonnegative A,B, \max\{A-B,B/2\}\geq A/3. Together with D_L\leq2D_{L/2}, this proves

Step 5: probability and normalization. The probability that at least one transition fails to be good is at most n\epsilon=1/10, by stationarity and the union bound. Without conditioning on goodness, the letters are independent and uniform in \cS. As letters are appended, the reduced length has conditional expected increment 1/2 when positive, since exactly one of the four letters cancels its last letter; at zero the increment is 1. Thus \E\ell\geq n/2. Since 0\leq\ell\leq n,

With probability at least 1/4-1/10=3/20, all steps are good and \ell\geq n/4. On this event (5.29) gives N(G)\geq nD_L/24. Every edge label has norm D_L>0 by (5.22), so dividing all labels by D_L proves the proposition.□

Proof of Lemma 2.1. By (1.2), there is a nonreflexive Banach space Y finitely representable in X. Identify Y with its canonical image in Y^{**}, and choose v\in B_{Y^{**}} and d>0 with \dist(v,Y)>d.

The first limit will produce a spreading norm N_0, finitely representable in Y, that controls coefficient prefix sums. A second limit averages increasingly fine subdivisions. It preserves these properties and makes the resulting norm N invariant under subdivision. Same-sign merging then preserves N, and convexity gives contractive merging for arbitrary adjacent coefficients.

Step 1: finite triangular arrays. For every integer M\geq1, we construct y_1,\ldots,y_M\in B_Y and f_1,\ldots,f_M\in B_{Y^*} such that

Suppose y_1,\ldots,y_{i-1} have been chosen and let E=\Span\{y_1,\ldots,y_{i-1}\}. The restriction map Y^{**}\to(E^\perp)^* is a quotient map with kernel the canonical copy of E: Hahn–Banach extends every bounded functional on E^\perp\subseteq Y^* to all of Y^* with the same norm, while finite dimensionality gives (E^\perp)^\perp=E. Thus the quotient norm of v+E equals the norm of its restriction to E^\perp. Hence

We may therefore choose f_i\in B_{Y^*}\cap E^\perp with v(f_i)=d, by changing a sign and rescaling if necessary. The finite-dimensional form of Goldstine’s theorem gives y_i\in B_Y with |f_h(y_i)-v(f_h)|\leq M^{-1} for 1\leq h\leq i. Indeed, (v(f_1),\ldots,v(f_i)) belongs to the closure of \{(f_1(y),\ldots,f_i(y)):y\in B_Y\}: otherwise a separating linear functional would give v(f)>\sup_{y\in B_Y}f(y)=\|f\| for some f\in\Span\{f_1,\ldots,f_i\}, contradicting \|v\|\leq1. This proves (A.1) inductively.

Read the vectors in the reverse order. For any subtuple y_{i_1},\ldots,y_{i_m} with i_1>\cdots>i_m, the functional f_{i_j} annihilates the terms after the jth and approximates d on the first j terms. Consequently,

Step 2: a spreading limit. Fix k. For each m\leq k, choose a finite grid in [-1,1]^m with mesh at most k^{-2} in the maximum norm. Color every increasing m-subtuple of the reversed array by the list of the norms of its grid combinations, rounded into intervals of length k^{-1}. The number of colors is finite and independent of M. The finite Ramsey theorem, applied successively for m=1,\ldots,k, shows that, for sufficiently large M=M_k\geq k^3, there is a tuple (x_1^{(k)},\ldots,x_k^{(k)}) on which all these colorings are homogeneous. At each arity, thin a previously homogeneous set; homogeneity from earlier arities persists under this thinning. For fixed m\leq k and a\in[-1,1]^m, the norms of the combinations with coefficients a on any two increasing m-subtuples differ by at most

The additional error follows from the upper bound in (A.2).

Taking a diagonal subsequence over all finite rational coefficient tuples, and then using the common \ell_1 Lipschitz bound, gives limits

The limits are compatible with appending zeros. The vanishing subtuple oscillations give (2.3) for N_0. Passing to the limit in (A.2) yields

The norm axioms pass to the limit, and the lower bound gives positive definiteness. On each fixed coefficient cube the convergence is uniform, by the common Lipschitz bound and compactness. Moreover,

since every coefficient is the difference of two successive prefix sums. Thus the maps a\mapsto\sum_i a_i x_i^{(k)} give linear embeddings of every fixed coordinate span into Y with distortions tending to 1.

Step 3: averaging subdivisions. For positive integers J_1,\ldots,J_m, let F_{\boldsymbol J}a be the array obtained by replacing a_i by J_i copies of a_i/J_i. Write F_J when all multiplicities equal J. If J_i\leq M_i for every i, then

Indeed, in the ith block of length M_i, select a uniformly random J_i-element subset and place a_i/J_i in those positions, with zeros elsewhere. Every resulting array is obtained from F_{\boldsymbol J}a by inserting zeros, so has the same N_0 norm. Its mean is F_{\boldsymbol M}a, and convexity proves the claim.

It follows that

exists. The bounds in (A.3) survive subdivision, because the original prefix sums still occur at the ends of the blocks. Consequently, for every a=(a_1,\ldots,a_m),

Spreading invariance and the norm axioms also pass to the limit. The functions a\mapsto N_0(F_Ja) again have the common \ell_1 Lipschitz bound, so convergence is uniform on every fixed coefficient cube. The lower bound (A.4) also holds for N. Fix a source dimension m and \eta>0. First choose J so that F_J embeds the m-dimensional N span into the mJ-dimensional N_0 span with distortion less than 1+\eta. Indeed, uniform additive convergence on the compact N-unit sphere, together with (A.4), gives uniform relative error. Approximate this now fixed N_0 span in Y with distortion less than 1+\eta, and then embed its finite-dimensional image into X with distortion less than 1+\eta. The composite distortion is less than (1+\eta)^3; letting \eta\downarrow0 proves (iii).

Step 4: consecutive summation. First, N is unchanged by every fixed varying-multiplicity subdivision:

To see this, put J_- =\min_iJ_i and J_+=\max_iJ_i. The composite F_rF_{\boldsymbol J} replaces each a_i by rJ_i equal pieces. Thus, for every r,

by (A.5); let r\to\infty.

If adjacent nonzero coefficients have the same sign and rational ratio, subdivide them into equal pieces. Subdividing their sum into the combined number of pieces gives the identical array. Equation (A.8) shows that merging these coefficients preserves N. Continuity extends this statement to every same-sign pair, and spreading invariance handles zeros.

Fix all other coefficients and fix s\ne0. The function

is convex and is constant, at the merged norm N(\ldots,s,\ldots), on the nondegenerate interval with endpoints 0 and s. A convex function constant on a nondegenerate interval is at least that constant everywhere: a smaller exterior value, together with the farther endpoint, would force the nearer endpoint below that constant. This proves (2.4) when s\ne0. Letting s\to0 proves it for s=0 as well.□