Estimates on the Markov Convexity of Carnot Groups and Quantitative Nonembeddability
Chris Gartland














Thanks to Jeremy Tyson for helpful comments in the preparation of this article and to Assaf Naor for suggesting the (non)embeddability corollaries of the main theorems.

















We show that every graded nilpotent Lie group G of step r, equipped with a left invariant metric homogeneous with respect to the dilations induced by the grading, (this includes all Carnot groups with Carnot-Caratheodory metric) is Markov p-convex for all p ∈ [2r,∞). We also show that this is sharp whenever G is a Carnot group with r ≤ 3, a free Carnot group, or a jet space group; such groups are not Markov p-convex for any p ∈ (0,2r). This continues a line of research started by Li who proved this sharp result when G is the Heisenberg group. As corollaries, we obtain new estimates on the non-biLipschitz embeddability of some finitely generated nilpotent groups into nilpotent Lie groups of lower step. Sharp estimates of this type are known when the domain is the Heisenberg group and the target is a uniformly convex Banach space or L^1, but not when the target is a nonabelian nilpotent group.




Estimates on the Markov Convexity of Carnot Groups and Quantitative Nonembeddability
    Chris Gartland
    September 26, 2019
====================================================================================









§ INTRODUCTION



 §.§ Background

In <cit.>, Ribe showed that if two Banach spaces E,F are uniformly homeomorphic, then they are mutually finitely representable; there exists a λ < ∞ such that for any finitely dimensional subspace E_1 of E, there is a subspace F_1 of F whose Banach-Mazur distance from E_1 is at most λ. Properties of Banach spaces that are preserved under mutual finite representability are called local, and many classical properties such as type, cotype, superreflexivity, and p-convexity are local. Recall that a Banach space is said to be p-convex for some p ≥ 2 if there exists an equivalent norm · and K < ∞ such that for every ∈ [0,2],

    sup{(x+y)/2: x,y≤ 1, x-y≥}≤ 1-^p/K

Ribe's theorem implies that these properties are really metric properties, suggesting that each should have a reformulation that involves only the metric structure of the Banach space and not the linear structure. The research program concerned with finding these reformulations is known as the Ribe program. The program was initiated by Bourgain in <cit.> in which he made the first substantial contribution by characterizing superreflexive Banach spaces as those which do not admit biLipschitz embeddings of the binary trees of depth k with uniform control on the biLipschitz distortion. We record here that the biLipschitz distortion (or just distortion) of a map f: X → Y between metric spaces (X,d_X), (Y,d_Y) is the least value of L for which there exists 0<D<∞ so that

    d_X(x,y) ≤ Dd_Y(f(x),f(y)) ≤ Ld_X(x,y)

for all x,y ∈ X, that f is a biLipschitz embedding if its distortion is finite, and that f is a biLipschitz equivalence if it is a biLipschitz embedding and surjective. The biLipschitz distortion of X into Y is the infimal distortion of all maps from X into Y. Another major contribution to the Ribe program is a purely metric reformulation of p-convexity. The metric property Markov p-convexity was originally defined by Lee-Naor-Peres in <cit.> and proved by Mendel-Naor in <cit.> to be a reformulation of p-convexity. Here are the specifics:
 
 
Let {X_t}_t ∈ be a Markov chain on a state space Ω. Given an integer k ≥ 0, we denote by {X̃_t(k)}_t ∈ the process which equals X_t for time t ≤ k and evolves independently (with respect to the same transition probabilities) for time t > k. Fix p > 0. A metric space (M,d) is called Markov p-convex if there is Π < ∞ so that for every Markov chain {X_t}_t ∈ on a state space Ω, and for every f: Ω→ M,

    ∑_k=0^∞∑_t ∈[d(f(X_t),f(X̃_t(t-2^k)))^p]/2^kp≤Π^p ∑_t ∈[d(f(X_t+1),f(X_t))^p]

Set Π_p(M) equal to the least value of Π so that the above inequality holds (whenever it exists). Π_p(M) is called the Markov p-convexity constant of M.


 
A Banach space is p-convex if and only if it is Markov p-convex.


Observe the following fact: if there is a map f: X → Y with biLipschitz distortion L, then Π_p(X) ≤ LΠ_p(Y). Thus, Markov convexity can be used to answer quantitative questions about metric spaces in the Lipschitz category.

We present two such applications, the first on the impossibility of dimension reduction in trace class operators, S_1. From page 2 of <cit.>): A Banach space (X,·_X) admits metric dimension reduction if there exists α < ∞ such that every n-point subset of X biLipschitz embeds with distortion α into a linear subspace of X with dimension n^o(1). This definition is inspired by the famous Johnson-Lindenstrauss Lemma (<cit.>) which implies Hilbert space admits metric dimension reduction. In <cit.>, Naor, Pisier, and Schechtman showed that there is an infinite sequence of n-point subsets of S_1 whose Markov 2-convexity constant is bounded below by a universal constant times √(ln(n)), and that the Markov 2-convexity constant of any d-dimensional linear subspace of S_1 is bounded above by a universal constant times √(ln(n)). Together these imply their main result (Theorem 1, <cit.>): S_1 does not admit dimension reduction. For more on the Ribe program and dimension reduction, see the surveys <cit.> and <cit.>.

Here is a second application of Markov convexity. In the spirit of the Ribe program, Ostrovskii found a purely metric characterization of the Radon-Nikodym property (RNP) of Banach spaces by showing that a Banach space has the RNP if and only if it does not contain a biLipschitz copy of a thick family of geodesics (Corollary 1.5 <cit.>). He asked a natural follow-up question: if a geodesic metric space does not biLipschitz embed into any RNP space, must it contain a biLipschitz copy of a thick family of geodesics? The Heisenberg group is a geodesic metric space that does not biLipschitz embed into any RNP space (see Section 1.2 of <cit.> or Theorem 6.1 of <cit.>), and Ostrovskii showed that in fact it does not contain a biLipschitz copy of a thick family of geodesics, thus negatively answering the question. He accomplished this by proving that any metric space containing a biLipschitz copy of a thick family of geodesics cannot be Markov p-convex for any p > 0 (Theorem 1.5, <cit.>), and applying either of the following results of Li:

 
 

Proposition 7.2 and Theorem 7.4, <cit.>: Every graded nilpotent Lie group of step r is Markov 2(r!)^2-convex. 

Theorem 1.1 and Corollary 1.3, <cit.>: The set of p for which the Heisenberg group is Markov p-convex is exactly [4,∞).




 §.§ Summary of Results
 

This article continues the line of research started by Theorem <ref>. Our main results are:

thm:upperboundmain
Every graded nilpotent Lie group of step r, equipped with a left invariant metric homogeneous with respect to the dilations induced by the grading, is Markov p-convex for every p ∈ [2r,∞).


thm:lowerboundmain
For every p > 0, r ≥ 1, coarsely dense set N  J^r-1(), and R ≥ 3, let B_N(R) := {x ∈ N: d_CC(0,x) ≤ R}. Then

    Π_p(B_N(R)) ≳ln(R)^1/p-1/2r/ln(ln(R))^1/p+1/2r

where the implicit constant can depend on r,p but not on N,R.


Recall that a subset N of a metric space (X,d_X) is coarsely dense if there exists C < ∞ such that X = ∪_x' ∈ N{x ∈ X: d_X(x,x') ≤ C}. See Section <ref> for the definition of J^r-1(). Theorem <ref> is restated and proved at the end of Section <ref>, and similarly for Theorem <ref> at the end of Section <ref>.

We can extend this result to other groups using the notion of subquotients. Recall that a surjective map f: X → Y between metric spaces (X,d_X),(Y,d_Y) is a Lipschitz quotient map with constant C < ∞ if there exists 0<D<∞ such that for all x ∈ X and R > 0,

    B_R(f(x))  f(B_DR(x))  B_CR(f(x))

If such a map f exists we say Y is a Lipschitz quotient of X. X is a Lipschitz subquotient of Y with constant C if there is a metric space Z such that Z embeds isometrically into Y and X is a Lipschitz quotient of Z with constant C, or, equivalently, there is a a metric space Z such that Z is a Lipschitz quotient of Y with constant C and X isometrically embeds into Z. It follows from Proposition 4.1 of <cit.> that if X is a Lipschitz subquotient of Y with constant C then Π_p(X) ≤ C Π_p(Y).

Every free Carnot group of step r ≥ 2 has J^r-1() (in fact every graded nilpotent Lie group of step r with 2-dimensional horizontal layer) as a graded quotient group, and the projection map ^k ↠ dualizes to a graded embedding J^r-1() ↪ J^r-1(^k). See Chapter 14 of <cit.> for background on free Carnot groups and <cit.> for background on the jet spaces groups J^r-1(^k).

 
Let G be a Carnot group of step r that has J^r-1() as a graded subquotient group, for example G may be a free Carnot group, J^r-1(^k), or any Carnot group if r ≤ 3. The set of p > 0 for which G is Markov p-convex is exactly [2r,∞).



This follows from Theorems <ref> and <ref> and the preceding discussion.


Recall that a subgroup Γ≤ G of a Lie group G is a lattice if the subspace topology on Γ is discrete and G/Γ carries a G-invariant, Borel probability measure. 


Let G be a Carnot group of step r that has J^r-1() as a graded subquotient group, for example G may be a free Carnot group, J^r-1(^k), or any Carnot group if r ≤ 3 (by Lemma <ref>). Let Γ≤ G be a lattice equipped with the word metric with respect to a finite generating set (which exists by Theorem 2.21 of <cit.>), and let B_Γ(R) denote the ball of radius R in Γ centered at the identity. Then for any p > 0,

    Π_p(B_Γ(R)) ≳ln(R)^1/p-1/2r/ln(ln(R))^1/p+1/2r




Let G,Γ,p be as above. The inclusion Γ↪ G is a biLipschitz embedding onto a coarsely dense subset when Γ is equipped with the word metric with respect to a finite generating set (this can be proven using Mostow's theorem that lattices in nilpotent Lie groups are cocompact (<cit.>) and applying the fundamental theorem of geometric group theory). Thus it suffices to prove the conclusion for any coarsely dense N” G. Let N” be such a subset. By assumption, there is a Carnot group G' and a graded quotient homomorphism q: G → G' such that  J^r-1() is a graded subgroup of G'. Then q is a Lipschitz quotient map, so there is a constant C < ∞ such that for any R ≥ 3, 

    Π_p(B_N”(R)) ≳Π_p(B_q(N”)(R/C))

Thus it suffices to prove the conclusion for any coarsely dense subset N'  G'. Let N' be such a subset. Fix B >> 1 and let N  J^r-1() be a coarsely dense, B-separated subset (each pair of distinct points in N is separated by a distance at least B - such sets always exist by Zorn's Lemma). Then since J^r-1() is a graded subgroup of G', there is a biLipschitz embedding N → G'. If B is chosen large enough, we map postcompose with a nearest neighbor map G' → N' to obtain another biLipschitz embedding N → N'. Then the conclusion follows from Theorem <ref>.


The following quantitative nonembeddability estimate follows from the previous corollary and Theorem <ref>.


Let G be a Carnot group of step r that has J^r-1() as a graded subquotient group, for example G may be a free Carnot group, J^r-1(^k), or any Carnot group if r ≤ 3. Let Γ≤ G be a lattice equipped with the word metric with respect to a finite generating set, and let B_Γ(R) denote the ball of radius R in Γ centered at the identity. Let G' be any graded nilpotent Lie group of step r' < r. Then we have the following estimate for c_G'(B_Γ(R)), the biLipschitz distortion of B_Γ(R) in G':

    c_G'(B_Γ(R)) ≳ln(R)^1/2r'-1/2r/ln(ln(R))^1/2r'+1/2r

where the implicit constant depends on G and G' but not on R.


Such quantitative nonembeddability estimates have been the subject of much attention for embeddings of Heisenberg groups into certain Banach spaces, see <cit.> and <cit.> for uniformly convex Banach space targets and <cit.> for L^1 targets. In particular, it can be deduced from <cit.> and <cit.> that the biLipschitz distortion of the ball of radius R in a lattice in the Heisenberg group into Hilbert space equals, up to universal factors, √(ln(R)). Thus, our estimates in the previous corollary cannot be sharp when r=2 and r'=1. However, these estimates seem to be the first of their type when the target is allowed to be a nilpotent group of step larger than 1. Other quantitative nonembeddability estimates of between Carnot groups were obtained in <cit.>, but they are of a different flavor. Since our estimates are not sharp for r=2, r'=1, we speculate that they are not sharp for larger values of r,r' either.









Next, we obtain new results on the nonexistence Lipschitz subquotient maps.

 
Let G be a Carnot group of step r that has J^r-1() as a graded subquotient group, for example G may be a free Carnot group, J^r-1(^k), or any Carnot group if r ≤ 3. Let G' be any graded nilpotent Lie group of step r'.


  *  G is not a Lipschitz subquotient of L^p (or any p-convex space) for any p ∈ (1,2r).

  *  If r > r', G is not a Lipschitz subquotient of G'.




These follow from the previous corollary, the fact that Markov p-convexity is preserved under Lipschitz subquotients, Theorem <ref>, and the classical fact that L^p is max(2,p)-convex for p > 1. 


Essentially all of the previously know results of this flavor are proved via Pansu differentiation (<cit.>), which applies when the domain is a (finite dimensional) Carnot group and the target is an RNP Banach space or (finite dimensional) Carnot group (Section 1.2 of <cit.> or Theorem 6.1 of <cit.>, which are stated for biLipschitz maps on the Heisenberg group, but also apply to biLipschitz or Lipschitz quotient maps on any Carnot group of step at least 2). There is also a recent differentiation theorem of Le Donne-Li-Moisala (<cit.>) which applies when the domain is a “scalable" group filtrated by (finite dimensional) Carnot groups and the target is an RNP space. However, there does not seem to be a clear way to deduce Corollary <ref> in full generality from any of these methods.

We may use Markov convexity again to prove nonexistence of subquotient maps onto some “infinite step" graded Lie groups. See Section <ref> for the definitions of inverse limits, J^∞(^k), and the free Carnot group on k generators, F_k^∞.

 
Let G_0 ← G_1 ←… be an inverse system of graded nilpotent Lie groups such that for every r, there is an i with J^r-1() a graded subquotient of G_i, and let G_∞ be the inverse limit group. For example, G_∞ may be J^∞(^k) or F_k^∞. Then G_∞ is not a Lipschitz subquotient of any superreflexive space.



Pisier's renorming theorem, Theorem 11.37 of <cit.>, states that any superreflexive Banach space is p-convex for some p ∈ [2,∞). Thus it suffices to show that G_∞ is not Markov p-convex for any p ∈ (0,∞). For every r ≥ 1, J^r-1() is a Lipschitz subquotient of G_∞, so since Markov p-convexity is preserved under Lipschitz quotients, the conclusion follows from Corollary <ref>.


Finally, we provide a positive result on the existence of embeddings using one of the main results of <cit.>. A metric tree is the vertex set of a weighted graph-theoretical tree equipped with the shortest path metric.

 
If T is a metric tree and T is Markov p-convex, then T biLipschitz embeds into L^p.



If a metric tree T is a Lipschitz subquotient of a graded nilpotent Lie group G of step r, then T biLipschitz embeds into L^p for every p ≥ 2r.



This follows from Theorem <ref>, the fact that Markov convexity is inherited by Lipschitz subquotients, and Theorem <ref>.


We conclude this introduction with the obvious conjecture that Theorems <ref> and <ref> lead to, and another somewhat less obvious conjecture.


Every Carnot group of step r is not Markov p-convex for every p ∈ (0,2r).



For each graded nilpotent Lie group G, the set of p for which G is Markov p-convex is the same as that of the largest Carnot subgroup of G.




§ DISCUSSION OF PROOF METHODS

We engage here in informal discussion of the proofs of Theorem <ref> and <ref>. This discussion is intended to give a brief overview of the proofs for readers with a sufficient background in the relevant topics. For Theorem <ref>, the relevant topics are graded nilpotent Lie algebras, the group structure they inherit via the Baker-Campbell Hausdorff formula, and their graded-homogeneous group quasi-norms. For Theorem <ref>, the relevant topics are Markov convexity of diamond-type graphs, jet space Carnot groups, and Khintchine's inequality. Readers unfamiliar with these topic may find this section unuseful.



 §.§ Discussion of Proof of Theorem <ref>

The method employed by Mendel-Naor to prove that p-convexity of Banach spaces implies Markov p-convexity is to:


  * Invoke the well-known result that p-convex Banach spaces have equivalent norms · satisfying the parallelogram inequality (x^p + x-y^p)/2 - y/2^p ≳x-y/2^p.

  * Prove the 4-point inequality (2d(y,x)^p+d(z,y)^p+d(y,w)^p)/2 - (d(x,w)/2)^p - (d(x,z)/2)^p ≳ d(z,w)^p, where d(x,y) = x-y.

  * Prove the Markov p-convexity inequality, Definition <ref>.


We prove the analogous inequalities for graded nilpotent Lie groups:


  *  Lemma <ref>. Construct a group quasi-norm N satisfying (N(x)^p + N(y^-1x)^p)/2 - (N(y)/2)^p ≳ N(δ_1/2(y)^-1x)^p.

  *  Lemma <ref>. Prove the 4-point inequality (2d(y,x)^p+d(z,y)^p+d(y,w)^p)/2 - (d(x,w)/2)^p - (d(x,z)/2)^p ≳ d(z,w)^p, where d(x,y) = N(y^-1x).

  *  Prove Theorem <ref>. The Markov p-convexity inequality.


The passage from (<ref>) to (<ref>) and from (<ref>) to (<ref>) is exactly the same as in Banach space case. To prove (<ref>), we recursively construct a sequence of homogeneous quasi-norms on the group, and prove that they satisfy (1) inductively. Actually, the following stronger version of (<ref>) (with p=2s, the case p ≥ 2s is taken care of later) is needed for the induction to close, this is Lemma <ref>.

    (N_s(x)^2s+N_s(y^-1x)^2s)/2 - (N_s(y)/2)^2s≳ SN_s(x,y)^2s + D_s(x,y) + N_s(δ_1/2(y)^-1x)^2s

There are two extra terms that appear in this inequality, SN_s(x,y) and D_s(x,y), defined in Definitions <ref> and <ref>. D_s(x,y) is designed to bound (up to constants) the square of any BCH polynomial of degree s (see Definition <ref>), so one may guess how it would be useful to prove (<ref>).

SN_s(x,y) is nearly a positive definite quasi-norm of (x_1,… x_s,y_1, … y_s) (the name SN is meant to suggest that it is a seminorm instead of a norm, since it is not positive definite), but not quite as it vanishes when x_1 = y_1/2 and x_i=y_i=0 for i ≥ 2. However, this is not an issue as we will have an extra y_1 term in the induction, so that y_1 + SN_s(x,y) is genuinely a quasi-norm of (x_1,… x_s,y_1, … y_s). Here are D_s and SN_s for some small s:

    D_3(x,y) = (x_3,y_3)^2 + (x_1,y_1)^2(x_2,y_2)^2 + (x_1,y_1)^2τ^2(x,y)


    D_4(x,y) = (x_4,y_4)^2 + (x_1,y_1)^2(x_3,y_3)^2 + (x_2,y_2)^4


    + (x_1,y_1)^4(x_2,y_2)^2 + (x_2,y_2)^2τ^2(x,y) + (x_1,y_1)^4τ^2(x,y)


    SN_3(x,y) = max(x_1-y_1/2,(x_2,y_2)^1/2,(x_3,y_3)^1/3)

The polynomial τ^2(x,y) is designed to bound the squares of terms coming from the bracket between two vectors from the horizontal layer. For example, in the second Heisenberg group,

    τ^2(x,y) = (x_11y_12-x_12y_11)^2 + (x_13y_14-x_14y_13)^2

We recursively construct the quasi-norms N_s+1 given all the previous quasi-norms by defining N_s+1(x) to be an ℓ^2(s+1) sum of λ_s+1x_s+1^1/(s+1) and the top half of the previously defined quasi-norms, where λ_s+1 is a positive constant chosen small enough (depending on the product structure of the group in question) to make the inequality of Lemma <ref>(<ref>) hold. Specifically, from (<ref>),

    N_2(x) = √(x_1^4+λ_2x_2^2)


    N_s+1(x) = √(λ_s+1x_s+1^2 + ∑_s'= ⌈ (s+1)/2 ⌉^s N_s'^2(s+1)(x))

The reason why we add the top half of the previously defined norms, and the reason for the inclusion SN_s(x,y) term in the inequality, is to help pass from D_s(x,y) to D_s+1(x,y) during the proof of the inductive step. When proving the inductive step, we have terms like 
 (SN_s'(x,y)^2s' + D_s'(x,y))^(s+1)/s', s' ≤ s, appearing to which we apply Lemma <ref> and obtain a term like SN_s'(x,y)^2(s+1-s')D_s'(x,y). This term bounds (x_s+1-s',y_s+1-s')^2D_s'(x,y) exactly when ⌈ (s+1)/2 ⌉≤ s' ≤ s. Then summing (x_s+1-s',y_s+1-s')^2D_s'(x,y) over this range of s' accounts for all the terms in D_s+1(x,y), except for the top-layer term (x_s+1,y_s+1)^2 (since any other term in D_s+1(x,y) contains as a factor a variable from one of the lower half layers, see Lemma <ref> for details), which is accounted for later.



 §.§ Discussion of Proof of Theorem <ref>

We recursively construct a sequence of directed graphs Γ_m and maps from them into the jet space of step r (J^r-1()) to show that it is not Markov p-convex for any p < 2r. The Markov processes we use are standard directed random walks on the graphs. This is very similar to the method used in <cit.>, where something akin to the Laakso-Lang-Plaut diamond graphs were used. The main feature of those graphs G_m is that G_m+1 is obtained from G_i by replaced each edge of G_1 with a copy of G_m. Roughly speaking, Li recursively maps G_m+1 into ^2 by replacing each edge of a distorted image of G_1 by a rotated, distorted copy of the image of G_i. The distortion is done in such a way that the coLipschitz constant (the Lipschitz constant of the inverse map) is on the order of √(m)√(ln(m+1)), and the fact that rotations are isometries of the Heisenberg group affords one uniform control on the Lipschitz constants. One can conclude from this that the Heisenberg group is not Markov p-convex for p < 4 (the 4 coming from the fourth root of m).

Our graphs differ from those in <cit.> in that, to obtain Γ_m+1 from Γ_m, we first glue together many copies of Γ_m together with a small number of copies of a single edge I in series to get a new graph Γ_m+1', and then replace each edge of Γ_1 with a copy of Γ_m+1' (this isn't exactly how our construction is defined, but is close enough to get the main idea). See Definition <ref> for the full details. We will explain the reasoning for this after describing our maps of Γ_m into J^r-1().

Our maps differ from those in <cit.> in that we do not rotate the image of Γ_m before using it to replace the edges of the image of Γ_1, as rotations are not Lipschitz maps in higher step groups like they are in the Heisenberg group. Refer to Figure <ref> throughout this discussion to get an idea of the construction of these maps. Instead of rotating, we simply add (many copies of) the image of Γ_m to a distorted copy of the image of Γ_1 to obtain the mapping of Γ_m+1 into ^2. More specifically, we map each directed path γ in Γ_m+1 to the jet of a function ϕ_γ - a horizontal curve in J^r-1(). The Lipschitz constant of this map is controlled by d^r/d^rxϕ_γ_∞. We still distort the graphs Γ_m with the same asymptotics as in <cit.>, so that the coLipschitz constant is on the order of √(m)√(ln(m+1)) (at least on the pairs of random walks (X^m_t,X̃^m_t(t-2^k)). That we get the 2r^th root of m instead of the fourth root of m comes from the fact that J^r-1() is of step r and the Heisenberg group is of step 2. One potential problem is that the absence of isometric rotations and the fact that (√(m)ln(m))^-1 isn't summable means d^r/d^rxϕ_γ_∞ blows up along some paths, and thus we do not have uniform control on the Lipschitz constant of the map, unlike <cit.>. However, (√(m)ln(m))^-1 is square-summable, and together with the nature of the image of the random walk X^m_t in J^r-1(), this allows us to control [d_CC(X^m_t+1,X^m_t)^p] uniformly in m,t. Loosely, along the random walk in the horizontal layer (which has x- and u_r-1-coordinates), every time one is confronted with a choice of direction to walk in, the choice is to walk 1 unit in the x-direction and +(√(i)ln(i+1))^-1 units in the u_r-1-direction with probability 1/2, or 1 unit in the x-direction and -(√(i)ln(i+1))^-1 units in the u_r-1-direction with probability 1/2 (for some i depending on how far one has walked). Thus, one might expect d_CC(X^m_t+1,X^m_t) to be bounded by a random variable distributed like 1+|∑_i=1^t _i(√(i)ln(i+1))^-1|, where {_i}_i are iid Rademachers, and then Khintchine's inequality implies we should have a uniform bound on [d_CC(X^m_t+1,X^m_t)^p] (which is the real quantity of interest, recall Definition <ref>). Of course, the random walk is not distributed like this, but it turns out that this intuition is correct nonetheless, see Lemmas <ref> and <ref>(<ref>) for the specifics.

Finally, the reason we use many copies of Γ_m in creating Γ_m+1 is so that, compared to the diameter of Γ_m+1, the diameter of the copies of Γ_m is very small, and thus those that replaced opposite edges of Γ_1 don't get too close together, which would ruin the coLipschitz constant. Morally, this “decouples" any interaction between different scales in Γ_m+1.



§ PRELIMINARIES
 
The next two subsections don't follow any particular reference, but ones we recommend are <cit.> for Carnot groups and <cit.> for graded nilpotent groups. We mostly follow <cit.> for the subsection on jet spaces.


 §.§ Graded Nilpotent and Stratified Lie Algebras and their Lie Groups
 
A graded nilpotent Lie algebra (,[·,·]) of step r is a Lie algebra equipped with a grading = ⊕_i=1^r _i, meaning _r ≠ 0, [_i,_j] _i+j if i+j ≤ r, and [_i,_j] = 0 if i+j > r. A stratified Lie algebra (,[·,·]) of step r is a graded nilpotent Lie algebra of step r such that the Lie subalgebra generated by _1 is all of . The grading is called a stratification, _1 is often called the horizontal layer (or stratum), and  is said to be horizontally generated. Whenever a Lie algebra  (not presumed to be equipped with a grading) admits a stratification, it is unique (Lemma 2.16, <cit.>). A graded nilpotent Lie group of step r is a simply connected Lie group whose Lie algebra is graded nilpotent of step r. A graded nilpotent Lie group whose Lie algebra is stratified is a Carnot group. A graded homomorphism or map is a Lie group homomorphism between graded nilpotent Lie groups whose derivative is a graded Lie algebra homomorphism. One graded nilpotent Lie group G' is a graded subgroup of another graded nilpotent Lie group G if there is an injective graded homomorphism from G' into G. One graded nilpotent Lie group G' is a graded quotient group of another graded nilpotent Lie group G if there is a surjective graded homomorphism from G onto G'. One graded nilpotent Lie group G' is a graded subquotient group of another graded nilpotent Lie group G if there is another graded nilpotent Lie group G” such that G” is a graded subgroup of G and G' is a graded quotient group of G”, or, equivalently, there is another graded nilpotent Lie group G” such that G” is a graded quotient group of G and G' is a graded subgroup of G”.

Given a graded nilpotent Lie group G and its Lie algebra , since  is nilpotent and G is simply connected, the exponential map is a diffeomorphism, and thus we can use it to equip  with a graded nilpotent Lie group structure such that it becomes graded isomorphic to G. The Baker-Campbell-Hausdorff formula provides a formula for the group product on  in terms of the Lie algebra structure (Section 2, <cit.>):

    xy = ∑_n > 0(-1)^n+1/n∑_0<p_i+q_i 
     i ≤ i ≤ n C_p,q^-1( x)^p_1( y)^q_1… ( x)^p_n( y)^q_n-1y

where ( x)y = [x,y] and C_p,q = p_1!q_1! … p_n!q_n! (∑_i=1^n p_i+q_i). In this formula and what follows, whenever  is a graded nilpotent Lie algebra, we equip it with the product defined by (<ref>) and simultaneously think of  as a graded nilpotent Lie group and Lie algebra. We will always use juxtaposition to denote the group product.

Every graded nilpotent Lie group G has a canonical family of dilations δ_t: G → G parametrized by t ∈ (0,∞) whose derivative δ_t': → is defined by 

    δ_t'(x) := tx_1 + t^2x_2 + … t^rx_r

where  is the Lie algebra, and x_i ∈_i is the _i-component of x ∈. t ↦δ_t is an automorphic _> 0-action on G. It can be deduced that a Lie group homomorphism θ between graded nilpotent Lie groups is a graded homomorphism if and only if it is δ_t-equivariant, that is, θ(δ_t(x)) = δ_t(θ(x)), where we've abused (and will continue to do so) notation and written δ_t for the dilation on both the domain and codomain.



 §.§ Norms and Metrics
 
Let G be a graded nilpotent Lie group. A homogeneous quasi-norm on G is a continuous function N: G → such that for all x ∈ G and t ∈_> 0,


  * N(x) ≥ 0 (positive semi-definite)

  * N(x^-1) = N(x) (symmetry)

  * N(δ_t(x)) = tN(x) (homogeneity)

If additionally N(x) = 0 implies x = 0, then N is a positive definite homogeneous quasi-norm, and if N(xy) ≤ N(x) + N(y) for all x,y ∈ G (triangle inequality), N is a homogeneous norm. For any two positive definite homogeneous quasi-norms N,N' on G, the continuity, homogeneity, and positive definiteness of N,N', together with the compactness of the unit sphere in ⊕_i=1^r ^(_i), imply that N and N' are biLipschitz equivalent, that is, there is a constant 0 < C < ∞ such that

    C^-1N(x) ≤ N'(x) ≤ CN(x)

for all x ∈ G.

Positive definite homogeneous norms always exist, most famously those considered in <cit.>. Thus any positive definite homogeneous quasi-norm N satisfies the quasi-triangle inequality: there is a 0 < C < ∞ such that for all x,y ∈ G,

    N(xy) ≤ C(N(x) + N(y))


Typically one requires that every homogeneous quasi-norm N satisfies the quasi-triangle inequality. Although it turns out that the quasi-norms we consider in this article do satisfy the quasi-triangle inequality, we only need to know this for positive-definite quasi-norms and thus do not explicitly make this requirement.

There is a bijective correspondence between homogeneous, positive definite quasi-norms N on G and left-invariant, homogeneous quasi-metrics d_N on G via N ↦ d_N defined by

    d_N(x,y) := N(y^-1x)

Positive definiteness of N implies positive definiteness of d_N, symmetry of N implies symmetry of d_N, homogeneity of N implies the homogeneity of d_N (meaning d_N(δ_t(x),δ_t(y)) = td_N(x,y)), and the quasi-triangle inequality of N implies the quasi-triangle inequality of d_N. The left-invariance of d_N is automatic from the definition. N satisfies the triangle inequality if and only if d_N does. The inverse of N ↦ d_N is d ↦ N_d, where N_d(x) := d(0,x). In addition to those determined by the homogeneous, positive definite norms from <cit.>, there are canonical left-invariant, homogeneous metrics on Carnots groups called Carnot-Caratheodory metrics, denoted d_CC. These metrics are also geodesic. See <cit.> or <cit.> for further information.

In what follows, whenever dealing with a graded nilpotent Lie group, we will automatically assume it is equipped with a left-invariant, homogeneous quasi-metric. By the preceding discussion, this quasi-metric is well-defined up to biLipschitz equivalence, so any biLipschitz-invariant property of metric spaces we may well attribute to a graded nilpotent Lie group G knowing only the algebraic structure of its graded Lie algebra. The δ_t-equivariance of graded group maps implies that any graded map between graded nilpotent Lie groups is Lipschitz, and thus graded group embeddings are biLipschitz embeddings, graded quotient maps are Lipschitz quotient maps, and graded group isomorphisms are biLipschitz equivalences.



 §.§ Model Filiform Groups and Jet Spaces over 


We follow <cit.> (especially Example 4.3) throughout this subsection. The model filiform group of step r ≥ 1 is the Carnot group with stratified Lie algebra = ( X ⊕ Y_1) ⊕_i=2^r Y_i, where X,Y_1 is a basis for _1 and Y_i is a basis for _i for 2 ≤ i ≤ r, and the nontrivial bracket relations are given by [X,Y_i] = Y_i+1 for 1 ≤ i ≤ r-1. Clearly, for s ≥ r, there is a canonical Carnot group quotient map from the model filiform group of step s to that of step r. The model filiform group of step 2 is frequently called the Heisenberg group, and the one of step 3 the Engel group. The corresponding Lie algebras are the Heisenberg algebra and Engel algebra.

The jet space over  of step r ≥ 0, denoted J^r-1(), is a certain Carnot group of step r graded isomorphic to the model filiform group of step r. There are also jet space groups J^r-1(^k) over higher dimensional Euclidean space, but we will focus on k=1 in this discussion. As a set, J^r-1() consists of equivalence classes of pairs (x,f) where x ∈ and f ∈ C^r-1(). Two pairs (x,f),(y,g) are equivalent if x = y and f^(k)(x) = g^(k)(y) for all 0 ≤ k ≤ r-1. We define maps π_x,π_i: J^r-1() →, 0 ≤ i ≤ r-1, by π_x([(y,g)]) = y and π_i([(y,g)]) = g^(i)(y). These maps are obviously well-defined and the direct sum map π_x ⊕_i=0^r-1π_r-1-i: J^r-1() →^r is a bijection. For v ∈ J^r-1(), the quantity π_x(v) is referred to as the x-coordinate and π_i(v) as the u_i-coordinate. We equip J^r-1() with a topological vector space structure so that this map is a linear homeomorphism, and from this point on will represent elements of J^r-1() using these coordinates. We will especially represent elements as pairs (y,v) ∈ J^r-1() = ^r so that y ∈, v ∈^r, and π_x((y,v)) = y. Although we won't explicitly use it, the group operation on J^r-1() is given by

    π_x((x,u_r-1,… u_0)*(y,v_r-1,… v_0)) = x+y


    π_i((x,u_r-1,… u_0)*(y,v_r-1,… v_0)) = u_i+v_i + ∑_j=i+1^r-1 u_jy^j-i/(j-i)!

Given y ∈ and g ∈ C^r-1(), we get an element [j^r-1(y)](g) ∈ J^r-1() defined by

    π_x([j^r-1(y)](g)) = y


    π_i([j^r-1(y)](g)) = g^(i)(y)

called the jet of g at y. The following two Lemmas are essentially all we need to know about jet spaces. The first is a special case of <cit.>. Although their lemma is stated for C^r functions, the proof works the same in the case of C^r-1,1 functions.

 
For any [a,b] and ϕ∈ C^r-1,1([a,b]),

    d_CC([j^r-1(b)](ϕ),[j^r-1(a)](ϕ)) ≤(1 + ϕ^(r)_L^∞([a,b]))|b-a|



 
There is a constant c > 0 such that for all (x,u),(x,v) ∈ J^r-1(),

    d_CC((x,u),(x,v)) ≥ c|π_0(u-v)|^1/r



 By left invariance of d_CC and the ball-box theorem (see Corollary 2.2 of <cit.>, there is a constant c > 0 such that for all (x,u),(x,v) ∈ J^r-1(),

    d_CC((x,u),(x,v)) ≥ c|π_0((x,v)^-1(x,u))|^1/r

and by Lemma 3.1 from <cit.>,

    π_0((x,v)^-1(x,u)) = π_0(u-v)



The following lemma will be used to obtain lower bounds on the Markov convexity of Carnot groups of step 2 or 3.

 
Every Carnot group of step 2 or 3 contains the model filiform group of the corresponding step (the Heisenberg or Engel group) as a graded subquotient group.



Let G be a Carnot group of step 2 with stratified Lie algebra = _1 ⊕_2. Since  has step 2, there is a nonzero V_2 ∈_2. Since  is horizontally generated, there exist U,V_1 ∈_1 such that [U,V_1] = V_2. Recall that the Heisenberg algebra has first layer generated by linearly independent vectors X,Y_1, second layer generated by Y_2 ≠ 0, and nontrivial bracket relation [X,Y_1] = Y_2. Then it easily follows that X ↦ U, Y_1 ↦ V_1, Y_2 ↦ V_2 is a graded algebra embedding into . This proves that the Heisenberg group is a graded subgroup of G.

Now assume G is of step 3 with stratified Lie algebra = _1 ⊕_2 ⊕_3. By the grading property, any subspace of _3 is an ideal, and thus there is a graded algebra quotient map onto another step 3 stratified Lie algebra whose third layer is one dimensional. Thus we may assume _3 =  W, W ≠ 0, and prove that the Engel algebra embeds into . Since  is horizontally generated, W = [U_1,[U_2,U_3]] for some U_1,U_2,U_3 ∈_1. First we claim that there is a 2-dimensional subspace of the span of U_1,U_2,U_3 that generates a Lie subalgebra of step 3. After proving the claim, we'll show that this subalgebra must be graded algebra-isomorphic to the Engel algebra. To prove the claim, we'll show that at least one of the following is nonzero:


  *  [U_1,[U_1,U_2]]

  *  [U_1,[U_1,U_3]]

  *  [U_2,[U_2,U_3]]

  *  [U_3,[U_3,U_2]]

  *  [U_1+U_2,[U_1+U_2,U_3]]

  *  [U_1+U_3,[U_1+U_3,U_2]]

Assume that all terms are 0. First let's see that [U_2,[U_3,U_1]] = W.

    0 (<ref>)= [U_1+U_2,[U_1+U_2,U_3]] = [U_1,[U_1,U_3]] + [U_1,[U_2,U_3]] + [U_2,[U_1,U_3]] + [U_2,[U_2,U_3]]


    (<ref>),(<ref>)= W + [U_2,[U_1,U_3]] = W - [U_2,[U_3,U_1]]

Using (<ref>),(<ref>),(<ref>) in place of (<ref>),(<ref>),(<ref>) shows [U_3,[U_1,U_2]] = W.
Putting these together yields:

    [U_1,[U_2,U_3]] + [U_2,[U_3,U_1]] + [U_3,[U_1,U_2]] = 3W ≠ 0

in violation of the Jacobi identity. This proves the claim.

So now the situation is that there are Z_1,Z_2 ∈_1 with [Z_1,[Z_1,Z_2]] = zW for some z ≠ 0. Recall that the Engel algebra has first layer spanned by X,Y_1, second layer by Y_2, and third layer by Y_3 with nontrivial bracket relations [X,Y_1] = Y_2 and [X,Y_2] = Y_3. Let z' ∈ such that [Z_2,[Z_1,Z_2]] = z'W. Then since [Z_1,[Z_1,Z_2]] = zW ≠ 0,
the map from the Engel algebra into  defined by

    X ↦ Z_1,  Y_1 ↦ Z_2 - z'/zZ_1,  Y_2 ↦ [Z_1,Z_2],  Y_3 ↦ zW

is a graded algebra embedding.



The analogue of Lemma <ref> is false for groups of step larger than 3. Let  be the stratified Lie algebra = ⊕_i=1^4 _i with _1 =  X_11⊕ X_12, _2 =  X_2, _3 =  X_31⊕ X_32, _4 =  X_4 and nontrivial brackets [X_11,X_12] = X_2, [X_11,X_2] = X_31, [X_12,X_2] = X_32, [X_11,X_31] = X_4, [X_12,X_32] = X_4. The only graded quotient maps from  onto another step 4 stratified Lie algebra or graded embeddings into  from another step 4 stratified Lie algebra are isomorphisms.




























 §.§ Infinite Step Carnot groups


Given an inverse system of graded nilpotent Lie groups G_1 ρ_1← G_2 ρ_2←…, where each ρ_i is a graded quotient map, we define the inverse limit metric group, G_∞, to be the subgroup of (⊕_i=1^∞ G_i)_∞ consisting of those sequences (x_i)_i=1^∞ for which ρ(x_i+1) = x_i for all i ≥ 1, where (⊕_i=1^∞ G_i)_∞ is the ℓ_∞-sum of the pointed metric spaces (G_i,d_CC,0). G_∞ inherits a left-invariant homogeneous metric from (⊕_i=1^∞ G_i)_∞ (where the dilations δ_t are defined on G_∞ in the obvious way), and each G_i is a Lipschitz quotient of G_∞.


J^∞(^k) is the inverse limit metric group, equipped with the induced δ_t-action, associated to the natural inverse system formed by the jet space groups, J^0(^k) ρ_1← J^1(^k) ρ_2←…. See <cit.> for background on jet space groups. Similarly, F_k^∞ is the inverse limit metric group, equipped with the induced δ_t-action, associated to the natural inverse system formed by the free Carnot groups on k generators, F_k^1 ρ_1← F_k^2 ρ_2←…. See Chapter 14 of <cit.> for background on free Carnot groups.












 §.§ Probabilistic and Convexity Inequalities

In this article, we will often justify an inequality with the phrase “by convexity" or “by the parallelogram law". The convexity inequalities we refer to are almost always of the form

    a^p+b^p/2≥(a+b/2)^p

or

    a^p+b^p ≤(a+b)^p

for p ≥ 1 and a,b ≥ 0. The form of the parallelogram law we most often use is

    u^2 + u-v^2/2 = v/2^2 + u-v/2^2

for u,v in a Hilbert space, which implies the inequality

    u^2 + u-v^2≥v^2/2

We may also use either of these inequalities without explicitly mentioning convexity or the parallelogram law.

We collect here some basic inequalities related to convexity and an additional one on L^p-norms of random variables.

 
For all a,b ≥ 0 and q ≥ 1,

    (a+b)^q ≥ a^q + qa^q-1b




Let a,b,q be as above. The inequality is obviously true if a = 0. Then if a > 0, after dividing each side by a^q and replacing b/a with t, it suffices to prove (1+t)^q ≥ 1 + qt. This inequality is true since the right hand is the linearization of the left hand side at t=0, and the left hand side is a convex function of t. 


 
For each p > 0 and k ≥ 1,

    ∑_t=1^k (2t)^p > k^p+1/2




Let p > 0 and k ≥ 1. Since the function t ↦ (2t)^p is increasing,

    ∑_t=1^k (2t)^p > ∫_0^k (2t)^p dt = 2^p/p+1k^p+1≥ k^p+1/2



The following two lemmas are frequently used in tandem to prove Khintchine's inequality (for example, Proposition 4.5 of <cit.>). We will need them for a similar inequality used in Section <ref>.

 
For all y ∈, cosh(y) ≤exp(y^2/2).



Let y ∈.

    cosh(y) = e^y+e^-y/2 = 1/2∑_k=0^∞y^k+(-y)^k/k! = ∑_k=0^∞y^2k/(2k)!≤∑_k=0^∞(y^2/2)^k/k! = exp(y^2/2)



 
For each p ≥ 1 and 0 < A,B < ∞, there is a constant C = C(p,A,B) < ∞ such that any real-valued random variable Y satisfying the moment generating function subgaussian bound

    [exp(yY)] ≤ Ae^By^2

also satisfies the L^p-norm bound

    [|Y|^p] ≤ C




This is a standard result from the theory of subgaussian random variables whose proof appears in any text on measure concentration. For the sake of completeness we'll include the proof, roughly following the proof of Proposition 4.5 from <cit.>. Let p, A, B, Y be as above. For any t > 0, Markov's inequality and our assumption imply

    (Y ≥ t) = (exp(t/2BY) ≥exp(t^2/2B)) ≤exp(-t^2/2B)[exp(t/2BY)]


    ≤ Aexp(-t^2/2B+t^2/4B) = Aexp(-t^2/4B)

Likewise,

    (Y ≤ -t) ≤ Aexp(-t^2/4B)

giving us

    (|Y| ≥ t) ≤ 2Aexp(-t^2/4B)

We then use the layer cake principle to calculate [|Y|^p]:

    [|Y|^p] = p∫_0^∞ t^p-1(|Y| ≥ t) dt ≤ p∫_0^∞ t^p-12Aexp(-t^2/4B) dt = C(p,A,B) < ∞






§ UPPER BOUND ON MARKOV CONVEXITY OF GRADED NILPOTENT LIE GROUPS

Throughout this section, fix a graded nilpotent Lie algebra (,[·,·]) of step r ≥ 2 with grading ⊕_i=1^r _i and dim(_i) = k_i. Choose an ordered basis U_i,1, … U_i,k_i for each _i and equip  with a Hilbert norm · such that these vectors form an orthonormal basis. We also use · to denote the Euclidean norm on any ^n. Given x ∈, let x_i ∈_i denote its _i-component. Given x_i ∈_i, let x_i,j∈ denote its U_i,j-component. Thus,

    x^2 = ∑_i=1^r x_i^2 andx_i^2 = ∑_j=1^k_i |x_i,j|^2

Consider  as a graded nilpotent Lie group as in Section <ref>. It's easy to see that 0 is the group identity element and x^-1 = -x. Whenever u,v ∈ or u,v ∈^n, we use the notation (u,v)^2 to mean u^2 + v^2.



 §.§ BCH Polynomials

 
For s ≥ 0, a function P: → that is a monomial(polynomial) in the variables x_n,m,y_n,m is a graded-homogeneous monomial(polynomial) of degree s if P(δ_t(x),δ_t(y)) = t^sP(x,y) for all x,y ∈ and t ∈_>0. Clearly, any graded-homogeneous polynomial of degree s must be a sum of graded-homogeneous monomials of degree s.

In this section, a multiset is a finite sequence of positive integers modulo permutations. Disjoint unions I_1 ⊔ I_2 of multisets are defined in the obvious way. Given a multiset I, I_1 denotes the sum of the elements and I_∞ the maximum of the elements. Given a nonzero graded-homogeneous monomial M of degree s, we associate to it a multiset I(M) defined recursively on the number of variables in the monomial by I(M) = {i}⊔ I(M') if M(x,y) = x_i,nM'(x,y) or M(x,y) = y_i,nM'(x,y) for some n ≤ k_i and graded-homogeneous polynomial M' of degree s-i (the base case is I(1) = ∅). By the homogeneity property, it must hold that if M is nonzero and graded-homogeneous of degree s, I(M)_1 = s.

For s ≥ 1, let _s denote the unique multiset with _s_1 = s and _s_∞ = 1 (and _0 = ∅). For each n,m ≤ k_1, let τ_n,m(x,y) := x_1,ny_1,m - x_1,my_1,n. A graded-homogeneous polynomial P of degree s ≥ 2 is of τ-type if P(x,y) = τ_n,m(x,y)M'(x,y) for some n,m ≤ k_1 and graded-homogeneous monomial M' with I(M') = _s-2.

A graded homogeneous polynomial of degree s ≥ 2 of the form ∑_j Q_j (the sum is finite), where each Q_j is of τ-type or a graded-homogeneous monomial of degree s with 1 < I(Q_j)_∞ < s is called a BCH polynomial of degree s.


 
Obviously a sum of BCH polynomials of degree s is another such polynomial. If P is a BCH polynomial of degree s, 1 ≤ i ≤ r, and 1 ≤ j ≤ k_i, x_i,jP(x,y) and y_i,jP(x,y) are BCH polynomials of degree s+i. If P(x,y) is a BCH polynomial of degree s, then so is P(x,δ_t(y)) for any t ∈_>0.



Let M(x,y) = 6x_1,6x_1,1^2y_4,3, P(x,y) = -y_1,2(x_1,1y_1,2-x_1,2y_1,1), Q(x,y) = x_1,1y_1,1, and R(x,y) = y_3,2. M is a graded-homogeneous monomial of degree 7 with I(M) = {1,1,1,4}, P is a graded homogeneous polynomial of degree 3 of τ-type, Q is a graded-homogeneous monomial of degree 2 with I(Q) = {1,1}, and R is a graded homogeneous monomial of degree 3 with I(r) = {3}. M and P are BCH polynomials, but Q and R are not because they are monomials with I(Q)_∞ = 1 and I(R)_∞ = I(R)_1.


We now arrive at a key structural lemma for the group product on graded nilpotent Lie algebras. The rest of this subsection is dedicated to its proof.

 
For all x,y ∈ and 2 ≤ s ≤ r, 
 

[                                 (1)                           (y^-1x)_1                                   =                             x_1-y_1;                                 (2)                           (y^-1x)_s                                   = x_s-y_s +  ∑_j=1^k_sP_s,j(x,y)U_s,j ] 
 

where each P_s,j is a BCH polynomial of degree s.


A trusting reader familiar with the group structure of graded nilpotent Lie algebras induced by the Baker-Campbell-Hausdorff formula may safely skip the rest of this subsection. Before proving the lemma, we need to set some useful notation that allows us to work with nested Lie brackets, and then prove a lemma about these brackets.


Given x,y ∈, i ≥ 1, and ∈{1,2}^i, we recursively define (x,y)^ as follows: for i = 1, (x,y)^ := x if = 1 and (x,y)^ := y if = 2. Assume (x,y)^ has been defined for all ∈{1,2}^i for some i ≥ 1. Let ∈{1,2}^i+1. Then  equals (1,') or (2,') for some ' ∈{1,2}^i. We define (x,y)^ := [x,(x,y)^'] if = (1,') and (x,y)^ := [y,(x,y)^'] if = (2,').



(x,y)^(1,2,2,1) = [x,[y,[y,x]]]. The 1 or 2 in the superscript should be thought of as indicating the first or second component of (x,y) in the nested Lie bracket.


 
For all x,y ∈, 2 ≤ i_1,i_2 ≤ r, and ∈{1,2}^i_1,

    ((x,y)^)_i_2 = ∑_j=1^k_i_2Q_i_2,j(x,y) U_i_2,j

where each Q_i_2,j is a BCH polynomial of degree i_2 if i_1 ≤ i_2 0 if i_1 > i_2.



Let x,y ∈. By the grading property, ((x,y)^)_i_2 = 0 if ∈{1,2}^i_1 and i_1 > i_2. We'll prove the remaining case by induction on i_1.

Proof of base case. The base case is i_1=2. Let ∈{1,2}^2. Then  equals (1,1), (1,2), (2,1), or (2,2). Since (x,y)^(1,1) = (x,y)^(2,2) = 0 and (x,y)^(2,1) = -(x,y)^(1,2), it suffices to only consider = (1,2), in which case (x,y)^ = [x,y]. Let i_2 ≥ 2. We treat the two cases i_2 = 2 and i_2 > 2. First assume i_2 = 2. Then we have

    [x,y]_2 = [x_1,y_1] = [∑_j=1^k_1 x_1,j U_1,j, ∑_j'=1^k_1 y_1,j' U_1,j'] = ∑_j=1^k_1∑_j'=1^k_1 x_1,jy_1,j'[U_1,j,U_1,j']


    = 1/2(∑_n,m=1^k_1 x_1,ny_1,m[U_1,n,U_1,m] + ∑_n,m=1^k_1 x_1,my_1,n[U_1,m,U_1,n])


    = 1/2∑_n,m=1^k_1 (x_1,ny_1,m-x_1,my_1,n)[U_1,n,U_1,m] = 1/2∑_n,m=1^k_1τ_n,m(x,y)[U_1,n,U_1,m]


    = 1/2∑_n,m=1^k_1τ_n,m(x,y) ∑_j=1^k_2 c_j,n,mU_2,j = ∑_j=1^k_2(∑_n,m=1^k_1c_j,n,m/2τ_n,m(x,y))U_2,j

for some c_j,n,m∈. The inner sum is a sum of polynomials of degree 2 of τ-type, and thus a BCH polynomial of degree i_2.

Now we consider the case i_2 > 2.

    [x,y]_i_2 = ∑_n=1^i_2-1[x_n,y_i_2-n] = ∑_n=1^i_2-1[∑_j=1^k_n x_n,j U_n,j, ∑_j'=1^k_i_2-n y_i_2-n,j' U_i_2-n,j']


    = ∑_n=1^i_2-1∑_j=1^k_n∑_j'=1^k_i_2-n x_n,jy_i_2-n,j'[U_n,j,U_i_2-n,j'] = ∑_n=1^i_2-1∑_j=1^k_n∑_j'=1^k_i_2-n x_n,jy_i_2-n,j'∑_m=1^k_i_2 c_m,n,j,j'U_i_2,m


    = ∑_m=1^k_i_2(∑_n=1^i_2-1∑_j=1^k_n∑_j'=1^k_i_2-n c_m,n,j,j'x_n,jy_i_2-n,j')U_i_2,m

for some c_m,n,j,j'∈. Notice that, for each n,j,j', I(x_n,jy_i_2-n,j') = {n,i_2-n}, and so since i_2 > 2 and 1 ≤ n ≤ i_2-1, 1 < I(x_n,jy_i_2-n,j')_∞ < i_2, and thus x_n,j,y_i_2-n,j' is a BCH polynomial of degree i_2. This completes the proof of the base case.

Proof of inductive step. Now assume the lemma holds for some 2 ≤ i_1 < r. Let ∈{1,2}^i_1+1. Then  equals (1,') or (2,') for some ' ∈{1,2}^i_1. Without loss of generality, assume = (1,'). Let i_2 ≥ i_1 + 1.
Then

    ((x,y)^)_i_2 = [x,(x,y)^']_i_2 = ∑_n=1^i_2-1[x_n,((x,y)^')_i_2-n]


    ind hyp=∑_n=1^i_2-1[∑_j=1^k_n x_n,j U_n,j, ∑_j'=1^k_i_2-nP_i_2-n,j'(x,y)U_i_2-n,j']


    = ∑_n=1^i_2-1∑_j=1^k_n∑_j'=1^k_i_2-n x_n,jP_i_2-n,j'(x,y) [U_n,j,U_i_2-n,j']


    = ∑_n=1^i_2-1∑_j=1^k_n∑_j'=1^k_i_2-n x_n,jP_i_2-n,j'(x,y) ∑_m=1^k_i_2c_m,n,j,j'U_i_2,m


    = ∑_m=1^k_i_2(∑_n=1^i_2∑_j=1^k_n∑_j'=1^k_i_2-n c_m,n,j,j'x_n,jP_i_2-n,j'(x,y))U_i_2,m

for some c_m,n,j,j'∈ and BCH polynomials P_i_2-n,j',ℓ of degree i_2-n. This implies x_n,jP_i_2-n,j'(x,y) is a BCH polynomial of degree i_2, as desired.



The Baker-Campbell-Hausdorff formula, (<ref>), implies that there are constants (many can be taken to be 0) {α_}_∈∪_i=2^r{1,2}^i such that

    y^-1x = x - y + ∑_i=2^r ∑_∈{1,2}^iα_(x,y)^

Since 

    (y^-1x)_i = x_i - y_i + ∑_i=2^r ∑_∈{1,2}^iα_((x,y)^)_i

the desired conclusion follows by appealing to Lemma <ref>. 




 §.§ Convex Metrics
 
The goal of this subsection is to prove Theorem <ref>. To do so, we construct a left invariant homogeneous quasi-metric on  that satisfies a certain 4-point inequality. This is the content of Lemma <ref>. All the lemmas and definitions preceding Lemma <ref> exist to prove it.

We next define a graded-homogeneous polynomial of degree 2s that dominates the square of any BCH polynomial of degree s, Lemma <ref>. As a consequence of this we get two domination inequalities involving norms of group products, Lemmas <ref> and <ref>. These types of domination are what will ultimately allow us to prove Lemma <ref>, the key lemma used in the proof of Lemma <ref>.

 
Let

    τ(x,y) := √(∑_n,m ≤ k_1τ^2_n,m(x,y))

so that τ(x,y)^2 ≥τ_n,m(x,y)^2 for every n and m. For each 2 ≤ s ≤ r, define D_s: →_≥ 0 recursively by

    D_2(x,y) := τ^2(x,y) + (x_2,y_2)^2


    D_s+1 := (x_s+1,y_s+1)^2 + ∑_s'=1^⌊ (s+1)/2 ⌋(x_s',y_s')^2D_s+1-s'(x,y)



 
For any 2 ≤ s ≤ r and BCH polynomial P of degree s, there exists 0 < c ≤ 1 such that for all x,y ∈,

    D_s(x,y) - (x_s,y_s)^2 ≥ cP^2(x,y)




The proof is by induction on s. The base case s=2 is clear from the definition of D_2 and BCH polynomial of degree 2. Assume the inequality holds for all s_0 ≤ s for some s < r. Let P be a BCH polynomial of degree s+1. By definition of BCH polynomial, it suffices to prove the inequality assuming P is a monomial with 1 < I(P)_∞ < s+1 or P is of τ-type. First assume P is a monomial with 1 < I(P)_∞ < s+1. There are two subcases to consider: 1 ∈ I(P) and 1 ∉ I(P). Assume the first subcase holds. Then P = x_1,nM(x,y) or P = y_1,nM(x,y) for some n ≤ k_1 and monomial M of degree s with 1 < I(M)_∞ < s+1. Then

    D_s+1(x,y) - (x_s+1,y_s+1)^2 = ∑_s'=1^⌊ (s+1)/2 ⌋(x_s',y_s')^2D_s+1-s'(x,y)


    ≥(x_1,y_1)^2D_s(x,y) ind hyp≥ c(x_1,y_1)^2M^2(x,y) ≥ cP^2(x,y)

Now assume the second subcase holds. Then P(x,y) = x_i,jM(x,y) or P(x,y) = y_i,jM(x,y) for some 1 < i ≤⌊ (s+1)/2 ⌋, j ≤ k_i, and monomial M of degree s+1-i with 1 < I(M)_∞ < s+1. Then

    D_s+1(x,y) - (x_s+1,y_s+1)^2 = ∑_s'=1^⌊ (s+1)/2 ⌋(x_s',y_s')^2D_s+1-s'(x,y)


    ≥(x_i,y_i)^2D_s+1-i(x,y) ind hyp≥ c(x_i,y_i)^2M^2(x,y) ≥ cP^2(x,y)


Now assume P is of τ-type. By definition, since P has degree s+1, this means P(x,y) = τ_n,m(x,y)M'(x,y) for some n,m ≤ k_1 and graded-homogeneous monomial M' with I(M') = _s-1. This implies P(x,y) = x_1,ℓP'(x,y) or P(x,y) = y_1,ℓP'(x,y) for some ℓ≤ k_1, and degree s polynomial P' of τ-type. Then

    D_s+1(x,y) - (x_s+1,y_s+1)^2 = ∑_s'=1^⌊ (s+1)/2 ⌋(x_s',y_s')^2D_s+1-s'(x,y)


    ≥(x_1,y_1)^2D_s(x,y) ind hyp≥ c(x_1,y_1)^2(P')^2(x,y) ≥ cP^2(x,y)



 
Let 2 ≤ s ≤ r. For any t > 0, there is a constant c > 0 such that for all x,y ∈,

    D_s(x,y) - (x_s,y_s)^2 ≥ c(δ_t(y)^-1x)_s - (x_s-t^sy_s)^2




Let t > 0. By Lemma <ref>,

    (δ_t(y)^-1x)_s - (x_s-t^sy_s)^2 Lem <ref>=∑_j |P_s,j(x,δ_t(y))|^2 = ∑_j |P'_s,j,t(x,y)|^2

where each P_s,j is a BCH polynomial of degree s, and by Remark <ref>, each P'_s,j,t is a BCH polynomial of degree s. Then the desired inequality follows from Lemma <ref>.


 
Let 2 ≤ s ≤ r and c > 0. For all sufficiently small λ > 0 (depending on c), for all x,y ∈,

    c(D_s(x,y)-(x_s,y_s)^2) + λ(y^-1x)_s^2 ≥λ/2x_s-y_s^2




Let λ > 0. By Lemma <ref>, there is a constant c' > 0 (independent of x,y) such that

    c(D_s(x,y)-(x_s,y_s)^2) + λ(y^-1x)_s^2 ≥ c'(y^-1x)_s - (x_s-y_s)^2 + λ(y^-1x)_s^2 =: (*)

Thus, if λ≤ c',

    (*) ≥λ(y^-1x)_s - (x_s-y_s)^2 + λ(y^-1x)_s^2 ≥λ/2x_s-y_s^2

where the last inequality follows from the parallelogram law.


 
Let 2 ≤ s ≤ r. There is a constant c > 0 such that for all x,y ∈,

    D_s(x,y) ≥ c(δ_1/2(y)^-1x)_s^2




By Lemma <ref>, it suffices to show

    (δ_1/2(y)^-1x)_s - (x_s-2^-sy_s)^2 + (x_s,y_s)^2 ≥1/8(δ_1/2(y)^-1x)_s^2

Since

    x_s-2^-sy_s^2 ≤ 4(x_s,y_s)^2

it suffices to show

    (δ_1/2(y)^-1x)_s - (x_s-2^-sy_s)^2 + 1/4x_s-2^-sy_s^2 ≥1/8(δ_1/2(y)^-1x)_s^2

This inequality is true by the parallelogram law.


 
There is a constant c > 0 such that for all x,y ∈,

    y_1x_1-y_1/2≥ cτ(x,y)




It suffices to show, for each fixed n,m ≤ k_1, y_1x_1-y_1/2≥ |τ_n,m(x,y)|. By Cauchy-Schwarz,

    y_1x_1-y_1/2≥(y_1,m,-y_1,n)(x_1,n,x_1,m)-(y_1,n,y_1,m)/2


    C-S≥ |y_1,m(x_1,n-y_1,n/2) - y_1,n(x_1,m-y_1,m/2)| = |x_1,ny_1,m - x_1,my_1,n| = |τ_n,m(x,y)|



 
For 2 ≤ s ≤ r, define SN_s: → by

    SN_s(x,y) := max{x_1-y_1/2,(x_2,y_2)^1/2,(x_3,y_3)^1/3, …(x_s,y_s)^1/s}




Using the maximum of the terms is not important here; it could be replaced by any ℓ^p-sum or other such norm. If a different choice of norm was used, the rest of the section would proceed the exact same way except with possibly different values of constants (but still independent of x,y).


 
For each 2 ≤ s ≤ r, there exists a homogeneous quasi-norm N_s and a constant c > 0 such that for all x,y ∈,


  *  
    (N_s(x)^2s+N_s(y^-1x)^2s)/2 - (N_s(y)/2)^2s≥ cSN_s^2s(x,y) + cD_s(x,y) + cN_s(δ_1/2(y)^-1x)^2s


  *  N_s(y) ≥y_1 for all s ≥ 2. Consequently, N_s(y) + SN_s(x,y) ≥ b(x_s',y_s')^1/s' for some b > 0 and all 1 ≤ s' ≤ s.

  *  If N_s(y) = 0, y_i = 0 for all 1 ≤ i ≤ s. In particular, N_r is a positive definite homogeneous quasi-norm.




The proof is by induction on s. The functions N_s we construct will clearly be homogeneous quasi-norms and satisfy (<ref>) and (<ref>), so we will only concern ourselves with proving (<ref>).

Proof of base case: The base case is s = 2. Throughout the proof of the base case, c',c”,c”' denote (small) positive constants that depend on  but not on x,y. Each of the constants may depend on the ones previously appearing, but of course this is compatible with the fact that they are all independent of x,y. Define

    N_2(x) := √(x_1^4 + λx_2^2)

where λ > 0 is to be chosen later. Recalling that SN_2(x,y)^4 = max(x_1-y_2/2^4,(x_2,y_2)^2) ≤x_1-y_2/2^4 + (x_2,y_2)^2 and D_2(x,y) = τ^2(x,y) + (x_2,y_2)^2, we need to show

    (N_2(x)^4+N_2(y^-1x)^4)/2


    ≥ (N_2(y)/2)^4 + cx_1-y_1/2^4 + cτ^2(x,y) + c(x_2,y_2)^2 + cN_2(δ_1/2(y)^-1x)^4

for some λ, c > 0. First let's write out the definitions of some of the terms in the inequality. 
 

[                 N_2(x)^4                        =           x_1^4 + λx_2^2;             N_2(y^-1x)^4                        = x_1-y_1^4 + λ(y^-1x)_2^2;                 N_2(y)^4                        =           y_1^4 + λy_2^2;                          ] 
 

By convexity, parallelogram law, and Lemma <ref>,

    (x_1^4 + x_1-y_1^4)/2 ≥ ((x_1^2 + x_1-y_1^2)/2)^2


    = (y_1/2^2 + x_1-y_1/2^2)^2 = (y_1/2)^4 + 2y_1/2^2x_1-y_1/2^2 + x_1-y_1/2^4


    Lem <ref>≥ (y_1/2)^4 + c'τ^2(x,y) + x_1-y_1/2^4

For some c' > 0. Thus, it suffices to show that for sufficiently small λ,c > 0, 

    c'/2τ^2(x,y) + λx_2^2 + λ(y^-1x)_2^2 + 1/2x_1-y_1/2^4


    ≥ 2^-4λy_2^2 + cτ^2(x,y) + c(x_2,y_2)^2 + cN_2(δ_1/2(y)^-1x)^4

By Lemma <ref>, the following inequality is true for sufficiently small λ > 0:

    c'/4τ^2(x,y) + λ(y^-1x)_2^2 = c'/4(D_2(x,y) - (x_2,y_2)|^2) + λ(y^-1x)_2^2 Lem <ref>≥λ/2x_2-y_2^2

Thus it suffices for the following inequality to hold for λ,c > 0 sufficiently small:

    c'/4τ^2(x,y) + λx_2^2 + λ/2x_2-y_2^2 + 1/2x_1-y_1/2^4


    ≥ 2^-4λy_2^2 + c(x_2,y_2)^2 + cN_2(δ_1/2(y)^-1x)^4

We have

    λx_2^2 + λ/2x_2-y_2^2 ≥λ/2(x_2^2 + x_2-y_2^2)


    = λ/4(x_2^2 + x_2-y_2^2) + λ/4(x_2^2 + x_2-y_2^2) ≥ 2^-4λy_2^2 + c”(x_2,y_2)^2

Thus it remains to show

    c'/4τ^2(x,y) + c”/2(x_2,y_2)^2 + 1/2x_1-y_1/2^4 ≥ cN_2(δ_1/2(y)^-1x)^4

for c > 0 sufficiently small.
By Lemma <ref> we have

    c'/4τ^2(x,y) + c”/2(x_2,y_2)^2 ≥ c”'(τ^2(x,y) + (x_2,y_2)^2) = c”'D_s(x,y) Lem <ref>≥ cλ(δ_1/2(y)^-1x)_2^2

c > 0 sufficiently small, and thus it remains to show

    cλ(δ_1/2(y)^-1x)_2^2 + 1/2x_1-y_1/2^4 ≥ cN_2(δ_1/2(y)^-1x)^4

This is true by definition of N_2. This completes the proof of the base case.

Proof of inductive step: Now assume the statement holds for all 2 ≤ s' ≤ s some 2 ≤ s ≤ r-1. Define N_s+1 by

    N_s+1(x) := √(λx_s+1^2 + ∑_s'=⌈ (s+1)/2 ⌉^s N_s'^2(s+1)(x))

where λ is a (small) positive constant (different λ than in the base case) to be chosen later (independent of x,y). Throughout the remainder of the proof, c_1-c_7 denote (small) positive constants that depend on  but not on x,y. Each of the constants may depend on the ones previously appearing, but of course this is compatible with the fact that they are all independent of x,y. The constant λ will end up depending on c_2 (which in turn depends on c_1), and the subsequent constants will depend on λ.

We now prove the inductive step. In what follows, we adopt some conventions to help make the proof more readable. There are two types of equalities/inequalities we use relating each of the expressions below. The first type is simply using a lemma, definition, inductive hypothesis, or convexity or trivial numerical inequality. Whenever an equality/inequality of this type is used, the particular terms in the expression that change from one to the next are bolded. No other terms change, except for the bolded ones to which the particular lemma, definition, inductive hypothesis, or convexity or trivial numerical inequality apply. Apart from the trivial numerical inequalities, the name of the lemma or definition, “ind hyp", or “convexity" decorates the equality/inequality symbol. The second type of equality/inequality used is always an equality and the equality symbol is decorated with the word “rearrange". This means we use trivialities like commutivity of addition or multiplication, reindexing of a sum, or no symbolic changes at all. Importantly, we also use equalities decorated with “rearrange" to change which terms are bolded in the expression, in preparation for the use of another equality/inequality of the first type. 
 

[                                                                                                                                             (N_s+1(x)^2(s+1)+N_s+1(y^-1x)^2(s+1))/2;                                                                                          ;                                                                                  (<ref>)=                           (λx_s+1^2 + ∑_s'= ⌈ (s+1)/2 ⌉^s N_s'^2(s+1)(x) + (y^-1x)_s+1^2.;                                                                                                                                        .+ ∑_s'= ⌈ (s+1)/2 ⌉^s N_s'^2(s+1)(y^-1x))/2;                                                                                          ;                                                                                rearrange= λ2(x_s+1^2 + (y^-1x)_s+1^2) + (∑_s'= ⌈ (s+1)/2 ⌉^s N_s'^2(s+1)(x) + N_s'^2(s+1)(y^-1x))/2;                                                                                          ;                                                                                convexity≥ λ2(x_s+1^2 + (y^-1x)_s+1^2) + ∑_s'= ⌈ (s+1)/2 ⌉^s (N_s'^2s'(x) + N_s'^2s'(y^-1x)2)^s+1/s' ] 
 


[                                                                                ind hyp (<ref>)≥                                                                     λ2(x_s+1^2 + (y^-1x)_s+1^2);                                                                                                                                      + ∑_s'= ⌈ (s+1)/2 ⌉^s ((N_s'(y)/2)^2s' + c_1SN_s'^2s'(x,y);                                                                                                                                              + c_1D_s'(x,y) + c_1N_s'(δ_1/2(y)^-1x)^2s')^s+1/s';                                                                                                ;                                                                                      Lem <ref>≥                                                                     λ2(x_s+1^2 + (y^-1x)_s+1^2);                                                                                                 + ∑_s'= ⌈ (s+1)/2 ⌉^s ((N_s'(y)/2)^2s' + c_1SN_s'^2s'(x,y) +  c_1N_s'(δ_1/2(y)^-1x)^2s')^s+1/s';                                                                                                                                   + ((N_s'(y)/2)^2s' + c_1SN_s'^2s'(x,y))^s+1-s'/s'c_1D_s'(x,y);                                                                                                ;                                                                                      rearrange=                                                                     λ2(x_s+1^2 + (y^-1x)_s+1^2);                                                                                                 + ∑_s'= ⌈ (s+1)/2 ⌉^s ((N_s'(y)/2)^2s' + c_1SN_s'^2s'(x,y) +  c_1N_s'(δ_1/2(y)^-1x)^2s')^s+1/s';                                                                                                                                   + ((N_s'(y)/2)^2s' + c_1SN_s'^2s'(x,y))^s+1-s'/s'c_1D_s'(x,y);                                                                                                ;                                                                                      convexity≥                                                                     λ2(x_s+1^2 + (y^-1x)_s+1^2);                                                                                                 + ∑_s'= ⌈ (s+1)/2 ⌉^s (N_s'(y)/2)^2(s+1) + c_1SN_s'^2(s+1)(x,y) +  c_1N_s'(δ_1/2(y)^-1x)^2(s+1);                                                                                                                                   + ((N_s'(y)/2)^2s' + c_1SN_s'^2s'(x,y))^s+1-s'/s'c_1D_s'(x,y);                                                                                                ;                                                                                      rearrange=                                                                     λ2(x_s+1^2 + (y^-1x)_s+1^2);                                                                                                 + ∑_s'= ⌈ (s+1)/2 ⌉^s (N_s'(y)/2)^2(s+1) + c_1SN_s'^2(s+1)(x,y) +  c_1N_s'(δ_1/2(y)^-1x)^2(s+1);                                                                                                                                   + ((N_s'(y)/2)^2s' + c_1SN_s'^2s'(x,y))^s+1-s'/s'c_1D_s'(x,y) ]  
 


[                                                                                ind hyp (<ref>)≥                                                                     λ2(x_s+1^2 + (y^-1x)_s+1^2);                                                                                                 + ∑_s'= ⌈ (s+1)/2 ⌉^s (N_s'(y)/2)^2(s+1) + c_1SN_s'^2(s+1)(x,y) +  c_1N_s'(δ_1/2(y)^-1x)^2(s+1);                                                                                                                                                             + c_2(x_s+1-s',y_s+1-s')^2D_s'(x,y) ] 
 


[                                                                                      rearrange=                                                                     λ2(x_s+1^2 + (y^-1x)_s+1^2);                                                                                                 + ∑_s'= ⌈ (s+1)/2 ⌉^s (N_s'(y)/2)^2(s+1) + c_1SN_s'^2(s+1)(x,y) +  c_1N_s'(δ_1/2(y)^-1x)^2(s+1);                                                                                                                                              + ∑_s'=1^⌊ (s+1)/2 ⌋ c_2(x_s',y_s')^2D_s+1-s'(x,y) ] 
 


[                                                                                              ≥                                                                    λ2(x_s+1^2 + (y^-1x)_s+1^2);                                                                                                + c_1SN_s^2(s+1)(x,y) + ∑_s'= ⌈ (s+1)/2 ⌉^s (N_s'(y)/2)^2(s+1) +  c_1N_s'(δ_1/2(y)^-1x)^2(s+1);                                                                                                                                            + ∑_s'=1^⌊ (s+1)/2 ⌋ c_2(x_s',y_s')^2D_s+1-s'(x,y);                                                                                               ;                                                                                     rearrange=                                                                    λ2(x_s+1^2 + (y^-1x)_s+1^2);                                                                                                + c_1SN_s^2(s+1)(x,y) + ∑_s'= ⌈ (s+1)/2 ⌉^s (N_s'(y)/2)^2(s+1) +  c_1N_s'(δ_1/2(y)^-1x)^2(s+1);                                                                                                                                            + ∑_s'=1^⌊ (s+1)/2 ⌋ c_2(x_s',y_s')^2D_s+1-s'(x,y) ] 
 


[                                                                                     Def <ref>=                                                                    λ2(x_s+1^2 + (y^-1x)_s+1^2);                                                                                                + c_1SN_s^2(s+1)(x,y) + ∑_s'= ⌈ (s+1)/2 ⌉^s (N_s'(y)/2)^2(s+1) +  c_1N_s'(δ_1/2(y)^-1x)^2(s+1);                                                                                                                                                           + c_2(D_s+1(x,y) - (x_s+1,y_s+1)^2);                                                                                               ;                                                                                     rearrange=   c_1SN_s^2(s+1)(x,y) + ∑_s'= ⌈ (s+1)/2 ⌉^s (N_s'(y)/2)^2(s+1) +  c_1N_s'(δ_1/2(y)^-1x)^2(s+1);                                                                                                                                                          + c_22(D_s+1(x,y) - (x_s+1,y_s+1)^2);                                                                                                                       c_22(D_s+1(x,y) - (x_s+1,y_s+1)^2) + λ2(x_s+1^2 + (y^-1x)_s+1^2) =: (*) ] 
 

By Lemma <ref>, we can choose λ > 0 sufficiently small so that

    c_2/2(D_s+1(x,y) - (x_s+1,y_s+1)^2) + λ/2(x_s+1^2 + (y^-1x)_s+1^2) Lem <ref>≥λ/4(x_s+1^2+x_s+1-y_s+1^2)


    = λ/8(x_s+1^2+x_s+1-y_s+1^2) + λ/8(x_s+1^2+x_s+1-y_s+1^2)


    ≥λ/16y_s+1^2 + c_3(x_s+1,y_s+1)^2 ≥ 2^-(s+1)λy_s+1^2 + c_3(x_s+1,y_s+1)^2

And thus we get 
 

[                                                                                        (*) ≥ c_1SN_s^2(s+1)(x,y) + ∑_s'= ⌈ (s+1)/2 ⌉^s (N_s'(y)/2)^2(s+1) +  c_1N_s'(δ_1/2(y)^-1x)^2(s+1);                                                                                                                                                      + c_22(D_s+1(x,y) - (x_s+1,y_s+1)^2);                                                                                                                                                     2^-(s+1)λy_s+1^2 + c_3(x_s+1,y_s+1)^2 ] 
 


[                                                                              rearrange=         c_1SN_s^2(s+1)(x,y) + 2^-(s+1)λy_s+1^2 + ∑_s'= ⌈ (s+1)/2 ⌉^s (N_s'(y)/2)^2(s+1);                                                                                         + ∑_s'= ⌈ (s+1)/2 ⌉^s c_1N_s'(δ_1/2(y)^-1x)^2(s+1) + c_22(D_s+1(x,y) - (x_s+1,y_s+1)^2);                                                                                                                                                            + c_3(x_s+1,y_s+1)^2;                                                                                        ;                                                                                (<ref>)=                                               c_1SN_s^2(s+1)(x,y) + (N_s+1(y)/2)^2(s+1);                                                                                         + ∑_s'= ⌈ (s+1)/2 ⌉^s c_1N_s'(δ_1/2(y)^-1x)^2(s+1) + c_22(D_s+1(x,y) - (x_s+1,y_s+1)^2);                                                                                                                                                            + c_3(x_s+1,y_s+1)^2 ] 
 


[                                                                                     rearrange=                                c_1SN_s^2(s+1)(x,y) + c_32(x_s+1,y_s+1)^2 + (N_s+1(y)/2)^2(s+1);                                                                                                                                            + ∑_s'= ⌈ (s+1)/2 ⌉^s c_1N_s'(δ_1/2(y)^-1x)^2(s+1);                                                                                                                                    + c_22(D_s+1(x,y) - (x_s+1,y_s+1)^2) + c_32(x_s+1,y_s+1)^2;                                                                                               ;                                                                                    Def  <ref>≥                                                    c_4SN_s+1^2(s+1)(x,y) + (N_s+1(y)/2)^2(s+1);                                                                                                                                            + ∑_s'= ⌈ (s+1)/2 ⌉^s c_1N_s'(δ_1/2(y)^-1x)^2(s+1);                                                                                                                                    + c_22(D_s+1(x,y) - (x_s+1,y_s+1)^2) + c_32(x_s+1,y_s+1)^2;                                                                                               ;                                                                                     rearrange= (N_s+1(y)/2)^2(s+1) + c_4SN_s+1^2(s+1)(x,y) + ∑_s'= ⌈ (s+1)/2 ⌉^s c_1N_s'(δ_1/2(y)^-1x)^2(s+1);                                                                                                                                    + c_22(D_s+1(x,y) - (x_s+1,y_s+1)^2) + c_32(x_s+1,y_s+1)^2 ] 
 


[                                                                                              ≥ (N_s+1(y)/2)^2(s+1) + c_4SN_s+1^2(s+1)(x,y) + ∑_s'= ⌈ (s+1)/2 ⌉^s c_1N_s'(δ_1/2(y)^-1x)^2(s+1);                                                                                                                                                                               + c_5D_s+1(x,y);                                                                                               ;                                                                                     rearrange=                                   (N_s+1(y)/2)^2(s+1) + c_4SN_s+1^2(s+1)(x,y) + c_52D_s+1(x,y);                                                                                                                           + ∑_s'= ⌈ (s+1)/2 ⌉^s c_1N_s'(δ_1/2(y)^-1x)^2(s+1) + c_52D_s+1(x,y) ] 
 


[                                                                   Lem <ref>≥                 (N_s+1(y)/2)^2(s+1) + c_4SN_s+1^2(s+1)(x,y) + c_52D_s+1(x,y);                                                                              + ∑_s'= ⌈ (s+1)/2 ⌉^s c_1N_s'(δ_1/2(y)^-1x)^2(s+1) + c_6(δ_1/2(y)^-1x)_s+1^2;                                                                             ;                                                                   rearrange=                 (N_s+1(y)/2)^2(s+1) + c_4SN_s+1^2(s+1)(x,y) + c_52D_s+1(x,y);                                                                              + ∑_s'= ⌈ (s+1)/2 ⌉^s c_1N_s'(δ_1/2(y)^-1x)^2(s+1) + c_6(δ_1/2(y)^-1x)_s+1^2;                                                                             ;                                                                     (<ref>)≥                 (N_s+1(y)/2)^2(s+1) + c_4SN_s+1^2(s+1)(x,y) + c_52D_s+1(x,y);                                                                                                                           + c_7N_s+1(δ_1/2(y)^-1x)^2(s+1) ] 



 
There exists a positive definite homogeneous quasi-norm N_r on  and a constant c > 0 (depending on  but not on x,y) such that for all p ≥ r and all x,y ∈,

    (N_r(x)^2p+N_r(y^-1x)^2p)/2 - (N_r(y)/2)^2p≥ c^p/rN_r(δ_1/2(y)^-1x)^2p




Let N_r,c be as in the conclusion of Lemma <ref>. Let p ≥ r. Then by convexity and that lemma,

    (N_r(x)^2p+N_r(y^-1x)^2p)/2 ≥ ((N_r(x)^2r+N_r(y^-1x)^2r)/2)^p/r


    Lem <ref>≥ ((N_r(y)/2)^2r + cN_r(δ_1/2(y)^-1x)^2r)^p/r≥ (N_r(y)/2)^2p + c^p/rN_r(δ_1/2(y)^-1x)^2p



 
There exists a left invariant, homogeneous, positive definite quasi-metric d_N_r on  and a constant c > 0 (depending on  but not on w,x,y,z) such that for all p ≥ r and w,x,y,z ∈, 

    (2d_N_r(y,x)^2p+d_N_r(y,w)^2p+d_N_r(y,z)^2p)/2 - (d_N_r(x,w)/2)^2p - (d_N_r(x,z)/2)^2p≥ c'd_N_r(w,z)^2p




Let N_r,c be as in the previous lemma. Let d_N_r be the metric derived from N_r; d_N_r(x,y) := N_r(y^-1x). By left invariance of the metric, we may assume x = 0. Then by applying the previous lemma to each of the pairs (y,w) and (y,z), we obtain

    (d_N_r(y,0)^2p + d_N_r(y,w)^2p)/2 - (d_N_r(0,w)/2)^2p≥ c^p/rd_N_r(δ_1/2(w),0)^2p


    (d_N_r(y,0)^2p + d_N_r(y,z)^2p)/2 - (d_N_r(0,z)/2)^2p≥ c^p/rd_N_r(δ_1/2(z),0)^2p

Adding these and then using using Hölder, the quasi-triangle inequality, and homogeneity gives

    (2d_N_r(y,0)^2p + d_N_r(y,w)^2p + d_N_r(y,z)^2p)/2 - (d_N_r(0,w)/2)^2p - (d_N_r(0,z)/2)^2p


    ≥ c^p/r(d_N_r(δ_1/2(w),0)^2p + d_N_r(δ_1/2(z),0)^2p) ≥ 2^-2p+1c^p/r(d_N_r(δ_1/2(w),0) + d_N_r(δ_1/2(z),0))^2p


    ≥ c'd_N_r(δ_1/2(w),δ_1/2(z))^2p = 2^-2pc'd_N_r(w,z)^2p

for some c' > 0.


 
Every graded nilpotent Lie group of step r, equipped with a left invariant metric homogeneous with respect to the dilations induced by the grading, is Markov p-convex for every p ∈ [2r,∞).



Markov p-convexity is invariant under biLipschitz equivalence. Thus, we need only show (,d_N_r) is Markov 2p-convex for all p ≥ r, where d_N_r is the quasi-metric from Lemma <ref>. The Markov convexity of d_N_r follows from the 4-point inequality of Lemma <ref> and the proof of Proposition 2.1 in <cit.>.




§ LOWER BOUND ON MARKOV CONVEXITY OF J^R-1()

The goal of this section is to prove Theorem <ref>, which occurs at the conclusion. The strategy is to construct a sequence of directed graphs (see Definition <ref>) with bad Markov convexity properties. These bad properties are manifested by the dispersive nature of random walks on the graphs. This is the content of Lemma <ref>. We then map these graphs into J^r-1() with sufficient control over the distortion (Lemma <ref>) to prove Theorem <ref>.



 §.§ Directed Graphs and Random Walks

Let (N_m)_m=0^∞ be any sequence of integers with N_0 = 0 and N_m+1≥max(1,N_m + ⌈ 2log_2(m+1) ⌉). We'll define a sequence of directed graphs (Γ_m)_m=0^∞. The graphs will be directed from unique source vertex to unique and sink vertex, which we will denote by 0_m and 1_m, respectively. Let diam(Γ_m) be the number of edges in a directed edge path from 0 to 1, which is also equal to the diameter of Γ_m with respect to the shortest path metric. The construction will be such that diam(Γ_m) = 2^N_m.

 
We'll perform the construction and also prove that diam(Γ_m) = 2^N_m by induction. Let Γ_0 be the interval I, that is, a graph with two vertices 0,1 and a single edge connecting them, directed from 0 to 1. Suppose Γ_m has been constructed for some m ≥ 0. We define an intermediate graph Γ_m+1' by gluing together a := 2^N_m+1 - ⌈ 2log_2(m+1) ⌉ - 1 copies of I, then A:= 2^N_m+1-N_m - 2^N_m+1-N_m- ⌈ 2log_2(m+1) ⌉ = 2^-N_m(2^N_m+1-2a) = 2^N_m+1-N_m(1-2^-⌈ 2log_2(m+1) ⌉) copies of Γ_m, then a more copies of I again together in series. The source vertex of this graph is the source vertex of the first copy of I, and the sink vertex is the sink vertex of the last copy of I. The diameter of this graph is

    a ·diam(I) + A ·diam(Γ_m) + a ·diam(I) ind hyp= 2a + 2^N_mA = 2^N_m+1

We then define Γ_m+1 to be two copies of Γ_m+1', denoted +Γ_m+1' and -Γ_m+1', glued together in parallel. Denote the common source vertex 0_m and sink vertex 1_m. The diameter of Γ_m+1 is the same as the diameter of Γ_m+1'. We note that each copy of Γ_m in Γ_m+1 is isometrically embedded; any shortest path between two points in a copy of Γ_m Γ_m+1 completely belongs to Γ_m.

By swapping +Γ_m+1' and -Γ_m+1' in Γ_m+1, we obtain a directed graph involution ι: Γ_m+1→Γ_m+1.

For q_1,q_2 ∈Γ_m, (q_1,q_2) is called a vertical pair if d_m(q_1,0_m) = d_m(q_2,0_m).


For each m ≥ 0, let (X^m_t)_t=0^2^N_m be the standard directed random walk on Γ_m. Let d_m denote the shortest path metric on Γ_m. With full probability, d(X^m_t,0_m) = t for 0 ≤ t ≤ 2^N_m.

See the two right-hand graphs of Figure <ref> for what Γ_1 and Γ_2 look like when N_0 = 0, N_1 = 2, and N_2 = 4. The graphs are drawn in such a way that the direction is from left to right, +Γ_m' lies above the x-axis, and -Γ_m' lies below the x-axis. The source vertices 0_m are both drawn at (0,0), and the sink vertices 1_2 are both drawn at (1,0).

 
For all p > 0 and m ≥ 0,

    ∑_k=0^N_m∑_t=1^2^N_m[d_m(X^m_t,X̃^m_t(t-2^k))^p]/2^kp≥m/82^N_mΠ_i=1^m-1(1-(i+1)^-2)




Let p ≥ 1. The proof is by induction on m. The base case m = 0 is trivially true. Assume the inequality holds for some m ≥ 0. Now we consider the standard random walk X^m+1_t on Γ_m+1. Consider k and t in the range a + 1 ≤ t ≤ 2^N_m+1 - a, 0 ≤ k ≤ N_m, where a = 2^N_m+1-⌈ 2log_2(m+1) ⌉ -1. Then t - 2^k ≥ 2^N_m+1- ⌈ 2log_2(m+1) ⌉ -1 + 1 - 2^N_m≥ 1, so X^m+1_1 and X̃^m+1_1(t-2^k) agree. Then for all subsequent times, with full probability, X^m+1_t and X̃^m+1_t(t-2^k) belong to the same copy of Γ_m+1' in Γ_m+1. Then, after recalling the construction of Γ_m+1' as a number of copies of Γ_m and I glued together, it can be seen that for the range of t in interest, X^m+1_t and X̃^m+1_t(t-2^k) are standard random walks across A = 2^N_m+1-N_m(1-2^-⌈ 2log_2(m+1) ⌉) consecutive copies of Γ_m, which we denote as A · X^m+1_t and A ·X̃^m+1_t(t-2^k). Thus, under our assumptions on k and t, d_m+1(X^m+1_t,X̃^m+1_t(t-2^k)) has the same distribution as d_m(A · X^m_t,A ·X̃^m_t(t-2^k)). Hence we obtain by the inductive hypothesis

    ∑_k=0^N_m∑_t=a+1^2^N_m+1-a[d_m+1(X^m+1_t,X̃^m+1_t(t-2^k))^p]/2^kp = ∑_k=0^N_m∑_t=a+1^2^N_m+1-a[d_m(A · X^m_t,A ·X̃^m_t(t-2^k))^p]/2^kp


    = ∑_k=0^N_m∑_T=1^A (∑_t=a+(T-1)2^N_m+1^a+T2^N_m[d_m(A · X^m_t,A ·X̃^m_t(t-2^k))^p]/2^kp)


    = ∑_k=0^N_m∑_T=1^A ∑_t=1^2^N_m[d_m(X^m_t,X̃^m_t(t-2^k))^p]/2^kpind hyp≥∑_T=1^A m/82^N_mΠ_i=1^m-1(1-(i+1)^-2)


    = 2^N_mAm/8Π_i=1^m-1(1-(i+1)^-2) = 2^N_m+1(1-2^-⌈ 2log_2(m+1) ⌉)m/8Π_i=1^m-1(1-(i+1)^-2)


    ≥ 2^N_m+1(1-(m+1)^-2)m/8Π_i=1^m-1(1-(i+1)^-2) = m/82^N_m+1Π_i=1^m(1-(i+1)^-2)


In summary,

    ∑_k=0^N_m∑_t=a+1^2^N_m+1-a[d_m+1(X^m+1_t,X̃^m+1_t(t-2^k))^p]/2^kp≥m/82^N_m+1Π_i=1^m(1-(i+1)^-2)


Now consider k and t in the range 0 ≤ k ≤ N_m+1-1, 1 ≤ t ≤ 2^k, so that t-2^k ≤ 0. Note that this means this range is disjoint from the one previously considered. Since t-2^k ≤ 0, the random walks X^m+1 and X̃^m+1(t-2^k) evolved independently immediately. Thus, with probability 1/2, X^m+1 and X̃^m+1(t-2^k) belong to different copies of Γ_m+1' in Γ_m+1. This implies that, with probability 1/2, d_m+1(X^m+1_t,X̃^m+1_t(t-2^k)) = 2t. Thus,

    ∑_k=0^N_m+1-1∑ _t=1^2^k[d_m+1(X^m+1_t,X̃^m+1_t(t-2^k))^p]/2^kp≥∑_k=0^N_m+1-1∑ _t=1^2^k(2t)^p/2^kp+1


    Lem <ref>>∑_k=0^N_m+1-12^k(p+1)/2^kp+2 = ∑_k=0^N_m+1-1 2^k-2 = 2^N_m+1-2 - 1/4≥1/82^N_m+1

In summary,

    ∑_k=0^N_m+1-1∑ _t=1^2^k[d_m+1(X^m+1_t,X̃^m+1_t(t-2^k))^p]/2^kp > 1/82^N_m+1


Again, notice that in (<ref>) and (<ref>), the range of t, k we consider are disjoint from each other and are subsets of the range 0 ≤ k ≤ N_m+1, 1 ≤ t ≤ 2^N_m+1. Thus, by adding (<ref>) and (<ref>), we obtain

    ∑_k=0^N_m+1∑_t=1^2^N_m+1[d_m(X^m_t,X̃^m_t(t-2^k))^p]/2^kp > m/82^N_m+1Π_i=1^m(1-(i+1)^-2) + 1/82^N_m+1


    > (m+1/8)2^N_m+1Π_i=1^m(1-(i+1)^-2)

completing the inductive step.


 

    ∑_k=0^∞∑_t=1^2^N_m[d_m(X^m_t,X̃^m_t(t-2^k))^p]/2^kp≳ m2^N_m

for all p > 0.



This follows from Lemma <ref> and the fact that Π_i=1^m-1(1-(i+1)^-2) > Π_i=1^∞(1-(i+1)^-2) > 0 for all m ≥ 0.




 §.§ Mapping the Graphs into J^r-1()
 
 
There exists ϕ∈ C^r-1,1([0,1]) such that


  *  ϕ is symmetric across the line x = 1/2, that is, ϕ(x) = ϕ(1-x) for all x ∈ [0,1/2].

  *  ϕ(x) ≥ (2x)^r for all x ∈ [0,1/2].

  *  [j^r-1(0)](ϕ) = (0,0), and thus by (<ref>), [j^r-1(1)](ϕ) = (1,0).

  *  For every integer 0 ≤ i < 2^r and every x ∈ [i2^-r,(i+1)2^-r), ϕ^(r)(x) = ϕ^(r)(i2^-r) (so ϕ^(r) is constant on intervals of this form).

Since ϕ∈ C^r-1,1([0,1]), ϕ^(r)∈ L^∞([0,1]). We also remark here that whenever dealing with L^∞ functions, we choose representatives that are everywhere (not just almost everywhere) bounded by their norm.



The proof is by induction on r. For the base case r = 1, define

    ϕ(x) := { 2x     x ∈ [0,1/2] 
     2-2x     x ∈ [1/2,1] .

ϕ satisfies (<ref>) - (<ref>).

Now suppose such a function ϕ exists for some r ≥ 1. We'll construct a function ψ that satisfies (<ref>) - (<ref>) for r+1. Define ϕ∈ C^r-1,1([0,1]) by

    ϕ(x) := {ϕ(2x)     x ∈ [0,1/2] 
     -ϕ(2-2x)     x ∈ [1/2,1] .

Then define Φ∈ C^r,1([0,1]) by

    Φ(x) := ∫_0^x ϕ(ξ) dξ

Φ satisfies (<ref>), (<ref>), and (<ref>) by the inductive hypothesis. Note that the inductive hypothesis applied to (<ref>) implies ϕ(x) ≥ 2^r(2x)^r for every x ∈ [0,1/4], and hence

    Φ(x) ≥2^r-1/r+1(2x)^r+1≥1/2(2x)^r+1

Also, since ϕ≥ 0, (which follows from the inductive hypothesis applied to (<ref>) and (<ref>)),

    Φ(x) ≥Φ(1/4) ≥(1/2)^r+2

for all x ∈ [1/4,1/2]. Together, these two inequalities imply

    ψ(x) := 2^r+2Φ(x) ≥ (2x)^r+1

for all x ∈ [0,1/2]. Thus, ψ satisfies (<ref>)-(<ref>), completing the inductive step.


See Figure <ref> for graphs of ϕ and its first two derivatives when r = 3. Note that these graphs are not on the same scale.



 
Let ϕ be the function from Lemma <ref>. Set N_0 = 0, and for m ≥ 1, set N_m := ⌈ Cmlog_2(m+1) ⌉, where C is a sufficiently large constant to be chosen later, so that N_m ≥ r and N_m+1≥max(1,N_m + ⌈ 2log_2(m+1) ⌉). Then there exists a sequence of maps F_m: Γ_m → J^r-1() such that, for all m ≥ 0 and all directed paths γ from 0_m to 1_m in Γ_m, there is a function ϕ_γ∈ C^r-1,1([0,2^N_m]) such that


  *  [j^r-1(0)](ϕ_γ) = (0,0) and [j^r-1(2^N_m)](ϕ_γ) = (2^N_m,0).

  *  After isometrically identifying γ with [0,2^N_m] via q ↦ d_m(q,0_m), F_m restricted to γ equals the jet of ϕ_γ; F_m(t) = [j^r-1(t)](ϕ_γ).

  *  For all vertical pairs (q_1,q_2) ∈Γ_m Γ_m,

    √(m)ln(m+1)|π_0(F_m(q_1)) - F_m(q_2))| ≥ d_m(q_1,q_2)^r


  *  Let γ(X^m) denote the directed path followed by the random walk X^m (so γ(X^m) is itself a path-valued random variable). For all y ∈, and 0 ≤ t < 2^N_m,

    [exp(y(sup_[t,t+1]ϕ^(r)_γ(X^m)))] ≤exp(y^2/2ϕ^(r)_∞^2∑_n=1^m1/nln(n+1)^2)

and

    [exp(y(inf_[t,t+1]ϕ^(r)_γ(X^m)))] ≤exp(y^2/2ϕ^(r)_∞^2∑_n=1^m1/nln(n+1)^2)

and thus there exists a constant B < ∞ (not depending on y, t, or m) such that

    [exp(yϕ^(r)_γ(X^m)_L^∞[t,t+1])] ≤ 2e^By^2


  *  ϕ^(r)_γ_∞≤ 2√(m)ϕ^(r)_∞.

  *  π_0  F_m_∞≤ 2^r(m+1)^Crm+1ϕ_∞.




The proof is by induction on m. The base case m=0 is easy, we simply define F_0 to be the jet of the 0 function on Γ_0 = I. Then (<ref>) - (<ref>) hold. Assume such a sequence of maps F_0, … F_m exist for some m ≥ 0. Set

    K := π_0  F_m_∞

Since N_m+1≥ C(m+1)log_2(m+2), we may (and do) choose C sufficiently large so that

    K ind hyp (<ref>)≤ϕ_∞ 2^r(m+1)^Crm+1≤2^r(N_m+1- ⌈ 2log_2(m+1) ⌉ -1)-1/√(m+1)ln(m+2)


Define ϕ̃∈ C^r-1,1([0,2^N_m+1]) by

    ϕ̃(x) := 2^rN_m+1/√(m+1)ln(m+2)ϕ(2^-N_m+1x)

Note that since N_m+1≥ r, Lemma <ref>(<ref>) tells us:

    ϕ̃^(r)(x) = ϕ̃^(r)(i)

for every integer 0 ≤ i < 2^N_m and every x ∈ [i,i+1). We also have by the chain rule

    ϕ̃^(r)_∞ = ϕ^(r)_∞/√(m+1)ln(m+2)

and additionally

    ϕ̃_∞≤ 2^rN_m+1ϕ_∞≤ 2^r(C(m+1)log_2(m+2)+1)ϕ_∞ = 2^r(m+2)^Cr(m+1)ϕ_∞


We will now define the function F_m+1 on Γ_m+1 = +Γ_m+1' ∪ -Γ_m+1'. Let us first work with +Γ_m+1'. Let γ be a directed path from 0_m to 1_m in +Γ_m+1'. Then by definition of +Γ_m+1', γ consists of a = 2^N_m+1- ⌈ 2log_2(m+1) ⌉ -1 copies of I, then A = 2^-N_m(2^N_m+1-2a) copies of different directed paths γ_i, 1≤ i ≤ A, each belonging to Γ_m and connecting 0_m to 1_m, then a more copies of I glued together in series. Identify γ isometrically with [0,2^N_m+1] via q ↦ d_m+1(q,0_m+1). Under this identification, the first set of copies of I gets identified with the subinterval [0,a], each γ_i gets identified with the subinterval [a+(i-1)2^N_m,a+i2^N_m], and the last set of copies of I gets identified with the subinterval [2^N_m+1-a,2^N_m+1]. We then define

    ϕ_γ := ϕ̃ + f_γ

where f_γ is defined as follows: f_γ is identically 0 on [0,a] ∪ [2^N_m+1-a,2^N_m+1], and f_γ(x) = ϕ_γ_i(x-a-(i-1)2^N_m) on [a+(i-1)2^N_m,a+i2^N_m] (ϕ_γ_i is given to us by the inductive hypothesis). By the inductive hypothesis applied to (<ref>) and Lemma <ref>(<ref>), ϕ_γ∈ C^r-1,1([0,2^N_m+1]) and satisfies (<ref>). It is also clear from this definition, (<ref>), and the inductive hypothesis applied to (<ref>) that

    ϕ_γ^(r)_∞(<ref>)≤ϕ̃^(r)_∞ + max_1 ≤ i ≤ Aϕ_γ_i^(r)_∞(<ref>)≤ϕ^(r)_∞/√(m+1)ln(m+2) + max_1 ≤ i ≤ Aϕ_γ_i^(r)_∞


    ind hyp (<ref>)≤ϕ^(r)_∞/√(m+1)ln(m+2) + 2√(m)ϕ^(r)_∞≤ 2√(m+1)ϕ^(r)_∞

verifying (<ref>). We can finally define F_m+1 on +Γ_m+1' by declaring it to be the jet of ϕ_γ on γ. We need to check that F_m+1 is well-defined. Since every point of +Γ_m+1 is contained in some directed path from 0_m to 1_m, we only need to check what happens when one point belongs to two different paths. Let q ∈ +Γ_m+1' and suppose q ∈γ∩γ' for some directed paths γ,γ' from 0_m+1 to 1_m+1 in +Γ_m+1'. Set t := d(q,0_m+1). There are two cases: t ∈ [0,a] ∪ [2^N_m+1-a,2^N_m+1] or t ∈ [a+(i-1)2^N_m,a+i2^N_m] for some i. Assume the first case holds. Then our definition of F_m+1(q) based on either q ∈γ or q ∈γ' is

    F_m+1(q) = [j^r-1(t)](ϕ̃)

so well-definedness holds in this case. In the other case, our definition of F_m+1(q) based on q ∈γ is, by the inductive hypothesis applied to (<ref>),

    F_m+1(q) = [j^r-1(t)](ϕ̃) + ([j^r-1(t-a-(i-1)2^N_m)](ϕ_γ_i) + (a+(i-1)2^N_m-t,0)


    ind hyp= [j^r-1(t)](ϕ̃) + F_m(q) + (a+(i-1)2^N_m-t,0)

and likewise based on q ∈γ',

    F_m+1(q) = [j^r-1(t)](ϕ̃) + ([j^r-1(t-a-(i-1)2^N_m)](ϕ_γ'_i) + (a+(i-1)2^N_m-t,0)


    ind hyp= [j^r-1(t)](ϕ̃) + F_m(q) + (a+(i-1)2^N_m-t,0)
 
(note that the term (a+(i-1)2^N_m-t,0) is present so that the x-coordinate of the entire expression will be t, and that we identify q as belonging to a copy of Γ_m so that F_m(q) makes sense) so well-definedness holds in this case as well. Thus F_m+1 is well-defined on +Γ_m+1'. We define F_m+1 on -Γ_m+1 by F_m+1(q) = -F_m+1(ι(q)), where ι: +Γ_m+1' → -Γ_m+1' is the involution. It follows from this that if γ is a directed 0_m+1-1_m+1 path in -Γ_m+1', then ϕ_γ = -ϕ_ι(γ). Thus, (<ref>) and (<ref>) are satisfied. It remains to show (<ref>), (<ref>), and (<ref>). Before doing so, let us summarize the discussion on F_m+1 of this paragraph: for q ∈Γ_m+1 and t = d_m+1(q,0_m+1),

    F_m+1(q) = {
    [j^r-1(t)](ϕ̃)     t ∈ [0,a] ∪ [2^N_m+1-a,2^N_m+1] 
        q ∈ +Γ_m+1' 
    
    
    [j^r-1(t)](ϕ̃) 
     + F_m(q) + (a+(i-1)2^N_m-t,0)     t ∈ [a+(i-1)2^N_m,a+i2^N_m] 
         q ∈ +Γ_m+1' 
    
    
    [j^r-1(t)](-ϕ̃)     t ∈ [0,a] ∪ [2^N_m+1-a,2^N_m+1] 
        q ∈ -Γ_m+1' 
    
    
    [j^r-1(t)](-ϕ̃) 
     - F_m(q) - (a+(i-1)2^N_m-t,0)     t ∈ [a+(i-1)2^N_m,a+i2^N_m] 
         q ∈ -Γ_m+1' .




See Figure <ref> for the images of Γ_1 and Γ_2, based on N_0 = 0, N_1 = 2, N_2 = 4, in J^1(). Using (<ref>), we can quickly verify (<ref>):

    π_0  F_m+1_∞(<ref>)≤ϕ̃_∞ + π_0  F_m_∞ind hyp (<ref>)≤ϕ̃_∞ + 2^r(m+1)^Crm+1ϕ_∞


    (<ref>)≤ 2^r(m+2)^Cr(m+1)ϕ_∞ + 2^r(m+1)^Crm+1ϕ_∞≤ 2^r(m+2)^Cr(m+1)+1ϕ_∞

(<ref>) and (<ref>) require more involved arguments.

Proof of (<ref>). Let (q_1,q_2) ∈Γ_m+1Γ_m+1 be a vertical pair. By definition of vertical pair, d_m+1(q_1,0_m+1) = d_m+1(q_2,0_m+1). Let t denote this common value. There are two cases, q_1,q_2 belong to the same copy of Γ_m+1', or they belong to different copies. First assume they belong to the same copy. Without loss of generality say +Γ_m+1'. Then there are two subcases for t: t ∈ [0,a] ∪ [2^N_m+1-a,2^N_m+1] or t ∈ [a+(i-1)2^N_m,a+i2^N_m] for some 1 ≤ i ≤ A. Assume the first subcase holds. Then by construction of +Γ_m+1', q_1, q_2 belong to a copy of I, and thus the equality d_m+1(q_1,0_m+1) = d_m+1(q_2,0_m+1) implies q_1 = q_2, so (<ref>) trivially holds. Assume the second subcase for t. Then

    |π_0(F_m+1(q_1) - F_m+1(q_2))| (<ref>)= |π_0(F_m(q_1) - F_m(q_2))|

and so (<ref>) holds by the inductive hypothesis.

Now assume we are in the second case where q_1,q_2 belong to different copies of Γ_m+1'. Without loss of generality, assume q_1 ∈ +Γ_m+1' and q_2 ∈ -Γ_m+1'. Observe that under this assumption, d_m+1(q_1,q_2) = 2t if t ≤ 2^N_m+1-1 and d_m+1(q_1,q_2) = 2(2^N_m+1-t) if t ≥ 2^N_m+1-1. Because of the symmetry of ϕ̃ about the line x = 2^N_m+1-1, it suffices to only check the case t ≤ 2^N_m+1-1. Let us first record the following inequality:

    π_0([j^r-1(t)](ϕ̃)) ≥(2t)^r/√(m+1)ln(m+2)

which can be proven by

    π_0([j^r-1(t)](ϕ̃)) = ϕ̃(t) = 2^rN_m+1/√(m+1)ln(m+2)ϕ(2^-N_m+1t) Lem <ref>(<ref>)≥(2t)^r/√(m+1)ln(m+2)

Again split into two subcases: t ∈ [0,a] or t ∈ [a,2^N_m+1-1]. In the first subcase we have

    π_0(F_m+1(q_1)) (<ref>)=π_0([j^r-1(t)](ϕ̃)) (<ref>)≥(2t)^r/√(m+1)ln(m+2)

and

    π_0(F_m+1(q_2)) (<ref>)=π_0([j^r-1(t)](-ϕ̃)) (<ref>)≤ -(2t)^r/√(m+1)ln(m+2)

and thus

    |π_0(F_m+1(q_1) - F_m+1(q_2))| ≥2(2t)^r/√(m+1)ln(m+2) = 2d_m+1(q_1,q_2)^r/√(m+1)ln(m+2)

proving (<ref>) in this subcase.

Now assume the second subcase, t ∈ [a,2^N_m+1-1]. Then

    π_0(F_m+1(q_1)) (<ref>)=π_0([j^r-1(t)](ϕ̃) + F_m(q_1) + (a+(i-1)2^N_m-t,0)) = π_0([j^r-1(t)](ϕ̃)) + π_0(F_m(q_1))


    (<ref>)≥π_0([j^r-1(t)](ϕ̃)) - K (<ref>)≥π_0([j^r-1(t)](ϕ̃)) - 2^r(N_m+1- ⌈ 2log_2(m+1) ⌉)-1/√(m+1)ln(m+2)


    (<ref>)≥(2t)^r - 2^r(N_m+1- ⌈ 2log_2(m+1) ⌉)-1/√(m+1)ln(m+2) = (2t)^r - (2a)^r/2/√(m+1)ln(m+2)≥(2t)^r - (2t)^r/2/√(m+1)ln(m+2) = (2t)^r/2√(m+1)ln(m+2)

Similarly,

    π_0(F_m+1(q_2)) ≤ -(2t)^r/2√(m+1)ln(m+2)

and thus

    |π_0(F_m+1(q_1) - F_m+1(q_2))| ≥(2t)^r/√(m+1)ln(m+2) = d_m+1(q_1,q_2)^r/√(m+1)ln(m+2)

proving (<ref>) in this final subcase.

Proof of (<ref>). Let 0 ≤ t < 2^N_m+1 be an arbitrary integer. Again we consider two cases for t: t ∈ [0,a) ∪ [2^N_m+1-a,2^N_m+1) or t ∈ [a,2^N_m+1-a). Assume the first case holds. There are two subcases to consider for γ(X^m+1): γ(X^m+1) belongs to +Γ_m+1' or γ(X^m+1) belongs to -Γ_m+1'. These are complementary events each occuring with probability 1/2. Restricted to the first event, for every x ∈ [t,t+1],

    ϕ^(r)_γ(X^m+1)(x) (<ref>)=ϕ̃^(r)(x) + f_γ(X^m+1)(x) = ϕ̃^(r)(x) (<ref>)=ϕ̃^(r)(t)

where the second equality holds by the definition of f succeeding (<ref>).
Thus,

    sup_[t,t+1]ϕ^(r)_γ(X^m+1) = inf_[t,t+1]ϕ^(r)_γ(X^m+1) = ϕ̃^(r)(t)

Likewise, for the second subcase where we restrict to the event that γ(X^m+1) belongs to -Γ_m+1',

    sup_[t,t+1]ϕ^(r)_γ(X^m+1) = inf_[t,t+1]ϕ^(r)_γ(X^m+1) = -ϕ̃^(r)(t)

Combining these yields

    [exp(y(sup_[t,t+1]ϕ^(r)_γ(X^m+1)))] = 1/2(exp(yϕ̃^(r)(t)) + exp(-yϕ̃^(r)(t)))


    = cosh(yϕ̃^(r)(t)) ≤cosh(yϕ̃^(r)_∞) (<ref>)=cosh(yϕ^(r)_∞1/√(m+1)ln(m+2))


    Lem <ref>≤exp(y^2/2ϕ^(r)_∞^21/(m+1)ln(m+2)^2)

and the same estimate holds for the essential infimum, verifying (<ref>) in this case.

Now consider the second case, t ∈ [a+(i-1)2^N_m,a+i2^N_m] for some 1 ≤ i ≤ A. Again, there are two subcases to consider for γ(X^m+1): γ(X^m+1) belongs to +Γ_m+1' or γ(X^m+1) belongs to -Γ_m+1'. Restricted to the first event, and for the range of t under consideration, X^m+1 is equal in distribution to a copy of X^m (after an appropriate shift in the time parameter), by definition of +Γ_m+1'. Thus, for every x ∈ [t,t+1],

    ϕ^(r)_γ(X^m+1)(x) (<ref>)=ϕ̃^(r)(x) + f_γ(X^m+1)(x) = ϕ̃^(r)(x) + ϕ_γ(X^m)(x') (<ref>)=ϕ̃^(r)(t) + ϕ_γ(X^m)(x')

where x' = x-a-(i-1)2^N_m, and the second equality holds by the definition of f succeeding (<ref>).
Thus,

    sup_[t,t+1]ϕ^(r)_γ(X^m+1) = ϕ̃^(r)(t) + sup_[t',t'+1]ϕ_γ(X^m)


    inf_[t,t+1]ϕ^(r)_γ(X^m+1) = ϕ̃^(r)(t) + inf_[t',t'+1]ϕ_γ(X^m)

where t' =  t-a-(i-1)2^N_m.
Likewise, for the second subcase where we restrict to the event that γ(X^m+1) belongs to -Γ_m+1',

    sup_[t,t+1]ϕ^(r)_γ(X^m+1) = -ϕ̃^(r)(t) - inf_[t',t'+1]ϕ_γ(X^m)


    inf_[t,t+1]ϕ^(r)_γ(X^m+1) = -ϕ̃^(r)(t) - sup_[t',t'+1]ϕ_γ(X^m)


Combining these and using the inductive hypothesis applied to (<ref>) and some basic monotonicity and symmetry properties of cosh yields

    [exp(y(sup_[t,t+1]ϕ^(r)_γ(X^m+1)))]


    = 1/2exp(yϕ̃^(r)(t))[exp(y(sup_[t',t'+1]ϕ^(r)_γ(X^m+1)))]


    + 1/2exp(-yϕ̃^(r)(t))[exp(-y(inf_[t',t'+1]ϕ^(r)_γ(X^m+1)))]


    ind hyp≤1/2exp(yϕ̃^(r)(t))exp(y^2/2ϕ^(r)_∞^2∑_n=1^m1/nln(n+1)^2)


    + 1/2exp(-yϕ̃^(r)(t))exp((-y)^2/2ϕ^(r)_∞^2∑_n=1^m1/nln(n+1)^2)


    = cosh(yϕ̃^(r)(t))exp(y^2/2ϕ^(r)_∞^2∑_n=1^m1/nln(n+1)^2)


    ≤cosh(yϕ̃^(r)_∞)exp(y^2/2ϕ^(r)_∞^2∑_n=1^m1/nln(n+1)^2)


    (<ref>)=cosh(yϕ^(r)_∞1/√(m+1)ln(m+2))exp(y^2/2ϕ^(r)_∞^2∑_n=1^m1/nln(n+1)^2)


    Lem <ref>≤exp(y^2/2ϕ^(r)_∞^21/(m+1)ln(m+2)^2)exp(y^2/2ϕ^(r)_∞^2∑_n=1^m1/nln(n+1)^2)


    = exp(y^2/2ϕ^(r)_∞^2∑_n=1^m+11/nln(n+1)^2)

and the same estimate holds for the infimum, verifying (<ref>) in this case. This completes the inductive step and the proof of the lemma.


 
For every p > 0, r ≥ 1, coarsely dense set N  J^r-1(), and R ≥ 3, let B_N(R) := {x ∈ N: d_CC(0,x) ≤ R}. Then

    Π_p(B_N(R)) ≳ln(R)^1/p-1/2r/ln(ln(R))^1/p+1/2r

where the implicit constant can depend on r,p but not on N,R.



Let p,r,N be as above. Since the Markov convexity constant Π_p is scale-invariant, then by applying a dilation we may assume without loss of generality that every point of J^r-1() is at a distance of at most 1 away from a point of N. Let F_m: Γ_m → J^r-1() be the sequence of maps from Lemma <ref>. Extend the domain of t for the random walks on Γ_m by X^m_t := X^m_0 if t ≤ 0, and X^m_t := X^m_2^N_m if t ≥ 2^N_m. Each {X^m_t}_t ∈ is a Markov process on the state space Γ_m. 

With full probability, d_CC(X^m_t,0_m) = min(max(0,t),2^N_m). Since X̃^m_t(t-2^k) equals X^m_t in distribution, (X^m_t,X̃^m_t(t-2^k)) is a vertical pair with full probability. Then Lemma <ref>(<ref>) applies, and we get the following lower bound for the left hand side of the Markov convexity inequality in Definition <ref>:

    ∑_k=0^∞∑_t ∈[d_CC(F_m(X^m_t),F_m(X̃^m_t(t-2^k)))^p]/2^kpLem <ref>≥∑_k=0^∞∑_t ∈[|π_0(f_m(X^m_t)-f_m(X̃^m_t(t-2^k)))|^p/r]/2^kp


    Lem <ref>(<ref>)≥m^-p/2r/ln(m+1)^p/s∑_k=0^∞∑_t ∈[d_m(X^m_t,X̃^m_t(t-2^k))^p]/2^kpLem <ref>≳ m^-p/2rln(m+1)^-p/rm2^N_m = m^1-p/2r2^N_m/ln(m+1)^p/r

In summary,

    ∑_k=0^∞∑_t ∈[d_CC(F_m(X^m_t),F_m(X̃^m_t(t-2^k)))^p]/2^kp≳m^1-p/2r2^N_m/ln(m+1)^p/r


Now we upper bound the right hand side of the Markov convexity inequality. Since 
 d_CC(F_m(X^m_t+1),F_m(X^m_t)) = 0 whenever t ≤ 0 or t ≥ 2^N_m,

    ∑_t ∈[d_CC(F_m(X^m_t+1),F_m(X^m_t))^p] = ∑_t=0^2^N_m-1[d_CC(F_m(X^m_t+1),F_m(X^m_t))^p] =: (*)

Then

    (*) Lem <ref>(<ref>)=∑_t=0^2^N_m-1[d_CC([j^r-1(t+1)](ϕ_γ(X^m))([j^r-1(t)](ϕ_γ(X^m)))^p]


    Lem <ref>≤∑_t=0^2^N_m-1[(1+ϕ^(r)_γ(X^m)_L^∞[t,t+1])^p]


    ≲∑_t=0^2^N_m-1 1 + [ϕ^(r)_γ(X^m)_L^∞[t,t+1]^p] Lems <ref>,<ref>(<ref>)≲∑_t=0^2^N_m-1 1 = 2^N_m

In summary,

    ∑_t ∈[d_CC(F_m(X^m_t+1),F_m(X^m_t))^p] ≲ 2^N_m


Let π_N: J^r-1() → N be any map so that

    d_CC(x,π_N(x)) ≤ 1

which exists by our initial assumption. We'll use π_N to transfer inequalities (<ref>) and (<ref>) to corresponding inequalities on N. Consider the maps F̅_m: Γ_m → N defined by F̅_m := π_N δ_2m F_m. By Lemma <ref>(<ref>), 

    d_CC(δ_2m(F_m(q_1)),δ_2m(F_m(q_2))) ≥ 2d_m(q_1,q_2) ≥ 4

for any vertical pair (q_1,q_2) ∈Γ_m Γ_m. Combining this with (<ref>) yields

    d_CC(F̅_m(q_1),F̅_m(q_2)) (<ref>)≥ d_CC(δ_2m(F_m(q_1)),δ_2m(F_m(q_2))) - 2


    ≥1/2d_CC(δ_2m(F_m(q_1)),δ_2m(F_m(q_2))) = md_CC(F_m(q_1),F_m(q_2))

for any vertical pair (q_1,q_2). Combining this with (<ref>) yields

    ∑_k=0^∞∑_t ∈[d_CC(F̅_m(X^m_t),F̅_m(X̃^m_t(t-2^k)))^p]/2^kp≳m^p+1-p/2r2^N_m/ln(m+1)^p/r

Next,

    d_CC(F̅_m(X^m_t+1),F̅_m(X^m_t)) (<ref>)≤ d_CC(δ_2m(F_m(X^m_t+1)),δ_2m(F_m(X^m_t))) + 2


    = 2md_CC(F_m(X^m_t+1),F_m(X^m_t)) + 2

Combining this with (<ref>) and (<ref>) yields

    ∑_t ∈[d_CC(F̅_m(X^m_t+1),F̅_m(X^m_t))^p] ≲ m^p2^N_m

For each R ≥ 1, let m(R) denote the largest m so that F̅_m(R)(Γ_m(R))  B_N(R). Then (<ref>) and (<ref>) imply

    Π_p(B_N(R)) ≳m(R)^1/p-1/2r/ln(m(R)+1)^1/r


Now we wish to estimate the quantity m(R). Let m ≥ 0 be arbitrary. Since any two points of Γ_m are connected by a geodesic that is a piecewise directed path, the Lipschitz constant of any map on Γ_m is the maximum of the Lipschitz constants of the map restricted to directed paths. Thus, by Lemmas <ref>(<ref>), <ref>(<ref>), and <ref>, Lip(F_m) ≲√(m). Since diam(Γ_m) = 2^N_m≤ 2^Cmlog_2(m+1)+1 and F_m(0_m) = 0, this implies F_m(Γ_m)  B_J^r-1()(R') with R' ≲ (m+1)^Cm+1/2. Then δ_2m(F_m(Γ_m))  B_J^r-1()(R”) with R”≲ (m+1)^Cm+3/2. Then F̅_m(Γ_m) = π_N(δ_2m(F_m(Γ_m)))  B_J^r-1()(R”+1). This implies, for any R ≥ 1, R ≲ (m(R)+1)^Cm(R)+3/2, where the implied constant is independent of R. This implies m(R) ≳ln(R)/ln(ln(R)) for R ≥ 3. Plugging this into (<ref>) yields

    Π_p(B_N(R)) ≳ln(R)^1/p-1/2r/ln(ln(R))^1/p+1/2r






































amsalpha


