==== TABLE OF CONTENTS ====
Metric-Markov-Cotype-Two-of-l1//main.tex
Metric-Markov-Cotype-Two-of-l1//references.bib
===========================

==== BEGIN Metric-Markov-Cotype-Two-of-l1//main.tex ====
\newcommand{\DoNotLoadEpstopdf}{}
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1.08in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage{xcolor}
\usepackage[colorlinks=true,linkcolor=blue!45!black,citecolor=blue!45!black,urlcolor=blue!45!black]{hyperref}
\input{glyphtounicode}
\input{glyphtounicode-cmex}
\pdfgentounicode=1
\pdftrailerid{}
\pdfsuppressptexinfo=15
\hypersetup{pdftitle={Metric Markov Cotype Two of l1},pdfauthor={OpenAI}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\numberwithin{equation}{section}
\newcommand{\R}{\mathbb R}
\newcommand{\N}{\mathbb N}
\newcommand{\E}{\mathbb E}
\newcommand{\Prob}{\mathbb P}
\newcommand{\ind}{\mathbf 1}
\newcommand{\calF}{\mathcal F}
\newcommand{\norm}[1]{\left\lVert #1\right\rVert}
\DeclareMathOperator{\med}{med}
\DeclareMathOperator{\Lip}{Lip}
\title{Metric Markov Cotype Two of $\ell_1$}
\author{OpenAI}
\date{October 5, 2026}

\begin{document}
\maketitle

\begin{abstract}
We prove that the real Banach space $\ell_1$ has metric Markov cotype two,
answering a question of Mendel and Naor. As a consequence, every Lipschitz
map from an arbitrary subset of a real Hilbert space into $\ell_1$ extends
to the whole Hilbert space with a universal multiplicative loss in its
Lipschitz constant, resolving Ball's extension problem for this target.
\end{abstract}

\section{Introduction}
\label{sec:intro}

Metric Markov cotype asks whether the values of a map on a finite
reversible Markov chain can be modified so that their one-step
variation becomes small, while the cost of the modification is
controlled by the original variation over a longer time interval.
The modified values are not prescribed linear averages. This freedom
is essential for the result proved here.

We work first with the real Banach space
\[
 \ell_1=\left\{x=(x(k))_{k\geq1}:\sum_{k\geq1}|x(k)|<\infty\right\},
 \qquad \|x\|_1=\sum_{k\geq1}|x(k)|.
\]
Write $\N=\{1,2,\ldots\}$ and $[n]=\{1,\ldots,n\}$. A stochastic matrix
$A=(a_{ij})_{i,j\in[n]}$ has nonnegative entries and each row sum
equal to one. It is reversible with respect to a probability vector
$\pi=(\pi_i)_{i\in[n]}$ if $\pi_i a_{ij}=\pi_j a_{ji}$ for all
$i,j$. Reversibility implies stationarity, $\pi A=\pi$.
Zero coordinates of $\pi$ are allowed.

\begin{definition}[Mendel--Naor]\label{def:cotype}
A metric space $(X,d)$ has metric Markov cotype two with constant $C>0$
if, for every $n,t\in\N$, every probability vector $\pi$, every
stochastic matrix $A$ reversible with respect to $\pi$, and every
$x_1,\ldots,x_n\in X$, there exist $y_1,\ldots,y_n\in X$ such that
\begin{equation}\label{eq:cotype}
 \sum_i\pi_i d(x_i,y_i)^2
 +t\sum_{i,j}\pi_i a_{ij}d(y_i,y_j)^2
 \leq C^2\sum_{i,j}\pi_i
 \left(\frac1t\sum_{s=1}^t A^s\right)_{ij}d(x_i,x_j)^2.
\end{equation}
The infimum of all such constants is denoted $N_2(X)$.
\end{definition}

This is \cite[Definition~1.2]{MendelNaor13}. Our main result is
the following.

\begin{theorem}\label{thm:main}
The real space $\ell_1$ satisfies
\[
 N_2(\ell_1)\leq12\sqrt{21}.
\]
\end{theorem}

Thus the square of the constant in \eqref{eq:cotype} may be taken
to be $3024$, independently of the number of points, the number of
coordinates, and the time parameter. No optimization of this
numerical constant is intended.

\subsection*{History and significance}
Ball introduced Markov type and cotype in his study of Lipschitz
extension \cite{Ball92}. His Markov cotype condition for Banach
spaces uses specified linear averages, and $\ell_1$ fails that
stronger condition. Ball also proposed a metric definition.
Mendel and Naor developed the Ces\`aro formulation above, proved
its equivalence to Ball's metric definition, and asked explicitly
whether $N_2(\ell_1)$ is finite
\cite[Question~1.15 and Section~7]{MendelNaor13}.
Theorem~\ref{thm:main} answers that question affirmatively.

For $1<p\leq2$, the uniformly convex theory gives
$N_2(\ell_p)\leq C/\sqrt{p-1}$ with a universal constant $C$
\cite{Ball92}; see also \cite[Section~1.1]{MendelNaor13}.
These bounds deteriorate as $p$ decreases to one and do not settle
the endpoint treated here.

There is a second distinction worth making. Using a construction
of Kalton, Mendel and Naor found a closed linear subspace of
$\ell_1$ that fails metric Markov cotype at every finite exponent
\cite[Theorem~1.14]{MendelNaor13}.
This does not rule out Theorem~\ref{thm:main}, because the points
$y_i$ in Definition~\ref{def:cotype} need not belong to a given
subspace containing the original data. Our construction uses
this freedom.

One important consequence concerns extension of Lipschitz maps.
For a map $f$ between metric spaces, $\Lip(f)$ denotes the least
$L\geq0$ such that $d(f(x),f(y))\leq Ld(x,y)$ for all $x,y$ in its
domain. Ball's extension problem asks whether a Lipschitz map from
an arbitrary subset of Hilbert space into $\ell_1$ admits an
extension with a universal multiplicative loss in its Lipschitz
constant. Mendel and Naor explain that an affirmative answer to
their metric Markov cotype question gives such an extension
\cite[Corollary~1.13 and the discussion after Question~1.15]{MendelNaor13}.
The extension problem is also discussed in
\cite[Section~1]{NaorYoung22}. We record the consequence precisely
in Section~\ref{sec:consequences}; the proof of
Theorem~\ref{thm:main} itself is elementary and independent of
extension theorems.

\subsection*{The nonlinear construction}
Finite subsets of $\ell_1$ admit exact representations by weighted
cuts; see \cite{DezaLaurent97}. We retain not only their distances
but also a contractive map back to the given ambient $\ell_1$.
Nonlinear cut smoothing with the cubic $\phi(r)=3r^2-2r^3$
also appears in the work of Cheng, Wang, and Xiang on sharp
metric cotype \cite{ChengWangXiang26}; metric cotype and metric
Markov cotype are different invariants.

The additional ingredient here is a martingale estimate for the
cubic. For a finite family $\mathcal B$ of cuts, the representation
gives binary vectors $z_i\in\{0,1\}^{\mathcal B}$ in a weighted
Hilbert space $H$, with
\[
 \|z_i-z_j\|_H^2=\|x_i-x_j\|_1.
\]
It also gives a map $T$ with $T(z_i)=x_i$ that is contractive for
the weighted $\ell_1$ norm on the cut coordinates. Let
$Q=[0,1]^{\mathcal B}$, and let $\Phi:Q\to Q$ apply $\phi$
coordinatewise. Stop an $A$-walk $(X_s)$ after an independent
nonnegative geometric number $S$ of steps with mean $t$. Writing $\E_i$ for
expectation when the walk starts at $i$, we choose
\[
 h_i=\E_i z_{X_S},\qquad y_i=T(\Phi(h_i)).
\]

For the estimate, start the walk from its stationary law $\pi$
and record stopping as a separate transition after the $S$ walk
steps. Attach $h_j$ to the current index $j$ while alive and
$z_j$ when the walk stops at $j$, keeping that value thereafter.
These values form a martingale. Because $\phi'$ vanishes at the
binary values, a fourth-power Hilbert potential controls the
total squared weighted-$\ell_1$ variation after applying $\Phi$.
Centering at $z_{X_0}$ makes the terminal potential equal to
$\|x_{X_S}-x_{X_0}\|_1^2$. The stopping jump accounts for the
approximation cost, and the expected $t$ preceding jumps account
for the one-step variation. Contractivity of $T$ transfers these
bounds to $\ell_1$.

We prove the cut representation in Section~\ref{sec:cuts} and the
martingale estimate in Section~\ref{sec:flat}. The comparison in
Section~\ref{sec:comparison}, valid in any metric space, converts
the terminal geometric endpoint cost to the Ces\`aro average in
\eqref{eq:cotype}. These ingredients are
assembled in Section~\ref{sec:proof}. The resulting points have a
simple interpretation: each $y_i$ is the expected coordinatewise
median of three independent geometric-walk endpoints started at
$i$. This interpretation is established after the main proof.

\section{Finite cuts and reconstruction}
\label{sec:cuts}

We first replace finitely many vectors in $\ell_1$ by finitely many
binary coordinates. The reconstruction map will allow us to
choose new points in the full ambient space, rather than in the
span of the data. This is the cut representation
\cite[Chapter~4]{DezaLaurent97}, together with the ambient reconstruction
given below.

\begin{lemma}\label{lem:cuts}
Given $x_1,\ldots,x_n\in\ell_1$, either all the points coincide,
or there exist a finite set $\mathcal B$, positive weights
$(w_B)_{B\in\mathcal B}$, binary vectors
$z_i\in\{0,1\}^{\mathcal B}$, and an affine map
$T:\R^{\mathcal B}\to\ell_1$ with the following properties.
For
\[
 \|u\|_{1,w}=\sum_{B\in\mathcal B}w_B|u_B|,
 \qquad
 \|u\|_H^2=\sum_{B\in\mathcal B}w_Bu_B^2,
\]
one has
\begin{align}
 T(z_i)&=x_i,\label{eq:reconstruct}\\
 \|x_i-x_j\|_1
 &=\|z_i-z_j\|_{1,w}=\|z_i-z_j\|_H^2,
 \label{eq:cut-distance}\\
 \|T(u)-T(u')\|_1&\leq\|u-u'\|_{1,w}
 \qquad(u,u'\in\R^{\mathcal B}).\label{eq:contraction}
\end{align}
The space $H$ is $\R^{\mathcal B}$ with the indicated Hilbert norm.
\end{lemma}

\begin{proof}
For each original coordinate $k$, put $v(k)=\min_i x_i(k)$.
For every nonempty proper subset $B\subset[n]$, define the
nonnegative vector
\begin{equation}\label{eq:cut-vector}
 b_B(k)=\left(\min_{i\in B}x_i(k)
                   -\max_{i\notin B}x_i(k)\right)_+.
\end{equation}
Here $r_+=\max\{r,0\}$. The estimates
\[
 |v(k)|\leq\sum_i|x_i(k)|,
 \qquad b_B(k)\leq2\sum_i|x_i(k)|
\]
show that $v,b_B\in\ell_1$. Set $w_B=\|b_B\|_1$ and
retain only subsets with $w_B>0$; these form $\mathcal B$.
There are at most $2^n-2$ of them. Define
\begin{equation}\label{eq:affine-map}
 z_i(B)=\ind_{\{i\in B\}},\qquad
 T(u)=v+\sum_{B\in\mathcal B}u_B b_B.
\end{equation}
The sum is finite, so $T$ takes values in $\ell_1$.

To verify the identities, fix $k$ and list the distinct values
among $x_1(k),\ldots,x_n(k)$ as
$\alpha_1<\cdots<\alpha_m$. For $1\leq r<m$, the upper cut
\[
 B_r=\{i:x_i(k)\geq\alpha_{r+1}\}
\]
has $b_{B_r}(k)=\alpha_{r+1}-\alpha_r$; all other cuts have
$b_B(k)=0$. Thus $T(z_i)(k)$ is $\alpha_1$ plus exactly the
successive gaps below $x_i(k)$, proving \eqref{eq:reconstruct}.
Moreover, the cuts with positive $b_B(k)$ are nested. If
$x_i(k)\geq x_j(k)$, every nonzero term in
$\sum_B(z_i(B)-z_j(B))b_B(k)$ is nonnegative; the reverse
inequality gives the reverse sign. Hence
\[
 |x_i(k)-x_j(k)|
 =\sum_B |z_i(B)-z_j(B)|b_B(k).
\]
Sum over $k$. Since binary differences have equal absolute value
and square, this gives \eqref{eq:cut-distance}. The triangle
inequality applied to \eqref{eq:affine-map} gives
\eqref{eq:contraction}. If $\mathcal B$ is empty, the same
coordinate description shows that all the data coincide.
\end{proof}

\section{A flat map and a quartic potential}
\label{sec:flat}

By \eqref{eq:cut-distance}, squared $\ell_1$ distances between
the original data are fourth powers of Hilbert distances between
their binary encodings. We therefore seek a fourth-power
potential that controls squared increments after the cubic map.

Fix a finite nonempty set $\mathcal B$ and positive weights $w_B$,
and use the two norms from Lemma~\ref{lem:cuts}. Write
$Q=[0,1]^{\mathcal B}$ and let $\langle\cdot,\cdot\rangle_H$
be the weighted Hilbert inner product. Define
\[
 \phi(r)=3r^2-2r^3\quad(0\leq r\leq1),
 \qquad \Phi(u)_B=\phi(u_B)\quad(u\in Q).
\]
The map $\Phi$ takes $Q$ to itself and fixes its binary vertices.
The key estimate controls its squared weighted-$\ell_1$ increment
by a convexity remainder in $H$.

\begin{lemma}\label{lem:flat}
For $u,u'\in Q$ and $e\in\{0,1\}^{\mathcal B}$, put
$a=u-e$, $\delta=u'-u$, and $F_e(u)=\|u-e\|_H^4$. Then
\begin{equation}\label{eq:flat}
 \|\Phi(u')-\Phi(u)\|_{1,w}^2
 \leq108\bigl(F_e(u')-F_e(u)
                   -4\|a\|_H^2\langle a,\delta\rangle_H\bigr).
\end{equation}
\end{lemma}

\begin{proof}
For either bit $d\in\{0,1\}$ and $r\in[0,1]$,
\[
 |\phi'(r)|=6r(1-r)\leq6|r-d|.
\]
Integrating on the segment from $u_B$ to $u'_B$ gives
\begin{align*}
 |\phi(u'_B)-\phi(u_B)|
 &\leq6|\delta_B|\int_0^1|a_B+s\delta_B|\,ds\\
 &\leq6|a_B||\delta_B|+3|\delta_B|^2.
\end{align*}
Summing with weights and applying Cauchy--Schwarz yields
\begin{equation}\label{eq:increment}
 \|\Phi(u')-\Phi(u)\|_{1,w}
 \leq6\|a\|_H\|\delta\|_H+3\|\delta\|_H^2.
\end{equation}

Let $R$ denote the expression in parentheses in \eqref{eq:flat}.
Expanding the fourth power gives the exact identity
\begin{equation}\label{eq:remainder}
 R=2\|a\|_H^2\|\delta\|_H^2
        +\bigl(2\langle a,\delta\rangle_H+\|\delta\|_H^2\bigr)^2.
\end{equation}
In particular, $\|a\|_H^2\|\delta\|_H^2\leq R/2$. Also
\begin{align*}
 \|\delta\|_H^4
 &\leq2\bigl(2\langle a,\delta\rangle_H+\|\delta\|_H^2\bigr)^2
              +8\langle a,\delta\rangle_H^2\\
 &\leq2\bigl(2\langle a,\delta\rangle_H+\|\delta\|_H^2\bigr)^2
              +8\|a\|_H^2\|\delta\|_H^2
 \leq4R.
\end{align*}
Squaring \eqref{eq:increment} and using $(r+s)^2\leq2r^2+2s^2$
therefore gives
\[
 \|\Phi(u')-\Phi(u)\|_{1,w}^2
 \leq72\|a\|_H^2\|\delta\|_H^2+18\|\delta\|_H^4
 \leq36R+72R=108R.
\]
\end{proof}

The linear term in \eqref{eq:flat} disappears on taking a
conditional expectation along a Hilbert-valued martingale. It is
important that the center may depend on the initial state.

\begin{corollary}\label{cor:martingale}
Let $(M_m)_{m\geq0}$ be an $H$-valued martingale with respect to
a filtration $(\calF_m)$, taking values in $Q$ and converging
almost surely to $M_\infty$. If $e$ is an
$\calF_0$-measurable binary vector, then
\begin{align}
 \E\sum_{m=0}^\infty
 \|\Phi(M_{m+1})-\Phi(M_m)\|_{1,w}^2
 &\leq108\bigl(\E\|M_\infty-e\|_H^4
                    -\E\|M_0-e\|_H^4\bigr)\notag\\
 &\leq108\E\|M_\infty-e\|_H^4.
 \label{eq:martingale-energy}
\end{align}
\end{corollary}
\begin{proof}
Apply Lemma~\ref{lem:flat} to each pair $M_m,M_{m+1}$.
The vector $4\|M_m-e\|_H^2(M_m-e)$ is
$\calF_m$-measurable and bounded. Therefore
\[
 \E\bigl[\|M_m-e\|_H^2
       \langle M_m-e,M_{m+1}-M_m\rangle_H\mid\calF_m\bigr]=0.
\]
Taking expectations and summing over $0\leq m<L$ telescopes
the potentials. All potentials are bounded by
$(\sum_Bw_B)^2$, so bounded convergence applies to the terminal
potential as $L\to\infty$. Monotone convergence applies to the
nonnegative jump sum. This proves the first inequality; the
second follows by discarding the initial nonnegative potential.
\end{proof}

\section{Geometric and Ces\`aro endpoint costs}
\label{sec:comparison}

The stopped martingale will produce a geometric average of
endpoint distances. The next estimate converts it to the finite
average in Definition~\ref{def:cotype}. This comparison is part
of the resolvent approach in \cite[Section~7, especially
Lemma~7.1]{MendelNaor13}. We give an elementary version with an
explicit constant; only stationarity, not reversibility, is needed.

\begin{lemma}\label{lem:comparison}
Let $(X_s)_{s\geq0}$ be a stationary Markov chain on $[n]$,
and let $x_1,\ldots,x_n$ lie in a metric space $(X,d)$.
For $t\in\N$, set $p=1/(t+1)$ and $q=1-p$. If $S$ is
independent of the walk and $\Prob(S=s)=pq^s$ for $s\geq0$,
then
\begin{equation}\label{eq:comparison}
 \E d(x_{X_S},x_{X_0})^2
 \leq\frac{28}{t}\sum_{s=1}^t
                 \E d(x_{X_s},x_{X_0})^2.
\end{equation}
\end{lemma}

\begin{proof}
Write
\[
 D(s)=\E d(x_{X_s},x_{X_0})^2,
 \qquad W=\frac1t\sum_{s=1}^t D(s).
\]
The triangle inequality, Minkowski's inequality in $L_2$, and
stationarity imply
\begin{equation}\label{eq:subadditivity}
 \sqrt{D(r+s)}\leq\sqrt{D(r)}+\sqrt{D(s)}
 \qquad(r,s\geq0).
\end{equation}
Consequently $D(t)\leq2D(r)+2D(t-r)$ for $1\leq r\leq t$.
Since $D(0)=0$, averaging gives
\begin{equation}\label{eq:Dt}
 D(t)\leq\frac2t\sum_{r=1}^tD(r)
          +\frac2t\sum_{r=0}^{t-1}D(r)\leq4W.
\end{equation}
If $s=jt+r$ with $j\geq0$ and $0\leq r<t$, repeated use of
\eqref{eq:subadditivity} gives
\begin{equation}\label{eq:blocks}
 D(s)\leq\bigl(j\sqrt{D(t)}+\sqrt{D(r)}\bigr)^2
        \leq2j^2D(t)+2D(r).
\end{equation}

For $J=\lfloor S/t\rfloor$ and $R=S-tJ$, the geometric
second moment yields
\[
 \E J^2\leq\frac{\E S^2}{t^2}
 =\frac{2t^2+t}{t^2}\leq3.
\]
For each $0\leq r<t$,
\[
 \Prob(R=r)=\frac{pq^r}{1-q^t}\leq\frac2t.
\]
Indeed $(1+1/t)^t\geq2$ implies $q^t\leq1/2$, so the
left side is at most $2p=2/(t+1)\leq2/t$.
Thus
\[
 \E D(R)\leq\frac2t\sum_{r=0}^{t-1}D(r)\leq2W.
\]
Take expectations in \eqref{eq:blocks} and use independence
of $S$ and the walk to conclude
\[
 \E d(x_{X_S},x_{X_0})^2=\E D(S)
 \leq2\cdot3\cdot4W+2\cdot2W=28W.
\]
Every step remains valid when $t=1$; then $R=0$.
\end{proof}

\section{The stopped walk and the main theorem}
\label{sec:proof}

We now construct the required points. Fix the data in
Definition~\ref{def:cotype} with $X=\ell_1$. If all $x_i$
coincide, choose $y_i=x_i$. Otherwise use Lemma~\ref{lem:cuts}
to obtain $z_i,H,T$, and use the map $\Phi$ of
Section~\ref{sec:flat}.

Put $p=1/(t+1)$, $q=1-p$, and define
\begin{equation}\label{eq:resolvent}
 h_i=p\sum_{s=0}^\infty q^s(A^s z)_i,
 \qquad (A^s z)_i=\sum_j(A^s)_{ij}z_j.
\end{equation}
This convex combination converges in the finite-dimensional
space $H$ and belongs to $Q$. Equivalently,
$h_i=\E_i z_{X_S}$, where $\E_i$ refers to an $A$-walk started
at $i$ and $S$ is independent with $\Prob(S=s)=pq^s$.
The first-step identity is
\begin{equation}\label{eq:harmonic}
 h_i=pz_i+q\sum_j a_{ij}h_j.
\end{equation}
We take
\begin{equation}\label{eq:y}
 y_i=T(\Phi(h_i)).
\end{equation}
In particular, each $y_i$ belongs to $\ell_1$.

\subsection{A martingale that realizes the two costs}
Start a chain in an alive state with index distributed according
to $\pi$. From an alive state of index $i$, it moves to the
dead state of index $i$ with probability $p$, and to the alive
state of index $j$ with probability $qa_{ij}$. Dead states are
absorbing. Its filtration $\calF_m$ records the initial state
and the first $m$ transitions only.

One realization uses an independent stationary $A$-walk
$(X_s)_{s\geq0}$ and successive independent survival trials,
each successful with probability $q$. Let $S$ be the number of
successful trials before the first failure. Then
$\Prob(S=s)=pq^s$ and $S$ is independent of the walk. There
are $S$ live index transitions followed by one death transition;
the index at death is $X_S$.

Attach the value $h_i$ to the alive state of index $i$ and the
value $z_i$ to its dead state, and let $M_m$ be the attached
value at chain time $m$. Equation~\eqref{eq:harmonic} shows
that $(M_m)$ is an $H$-valued martingale for the indicated
filtration. It lies in $Q$ and is eventually constant almost
surely, with
\[
 M_0=h_{X_0},\qquad M_\infty=z_{X_S}.
\]
The vector $e=z_{X_0}$ is $\calF_0$-measurable and binary.
Corollary~\ref{cor:martingale} and \eqref{eq:cut-distance}
give
\begin{equation}\label{eq:stopped-bound}
 \E\sum_{m=0}^\infty
 \|\Phi(M_{m+1})-\Phi(M_m)\|_{1,w}^2
 \leq108\E\|x_{X_S}-x_{X_0}\|_1^2.
\end{equation}

To compute the left side exactly, set
\[
 B=\sum_i\pi_i\|z_i-\Phi(h_i)\|_{1,w}^2,
 \qquad
 E_A=\sum_{i,j}\pi_i a_{ij}
             \|\Phi(h_i)-\Phi(h_j)\|_{1,w}^2.
\]
At time $m$, the event that the chain is alive has probability
$q^m$ and is independent of $X_m$. Stationarity gives
$\Prob(X_m=i)=\pi_i$ and
$\Prob(X_m=i,X_{m+1}=j)=\pi_i a_{ij}$.
Since $\Phi(z_i)=z_i$, the expected squared jump at time $m$
is $pq^m B+q^{m+1}E_A$. Therefore
\begin{equation}\label{eq:jump-identity}
 \E\sum_{m=0}^\infty
 \|\Phi(M_{m+1})-\Phi(M_m)\|_{1,w}^2
 =B+\frac qp E_A=B+tE_A.
\end{equation}
This identity explains why the killing probability was chosen
to be $1/(t+1)$.

\subsection{Completion of the proof}
\begin{proof}[Proof of Theorem~\ref{thm:main}]
Use the points \eqref{eq:y}. Contractivity of $T$ and the
identity $T(z_i)=x_i$ imply
\begin{align*}
 &\sum_i\pi_i\|x_i-y_i\|_1^2
       +t\sum_{i,j}\pi_i a_{ij}\|y_i-y_j\|_1^2\\
 &\hspace{25mm}\leq B+tE_A
 \leq108\E\|x_{X_S}-x_{X_0}\|_1^2,
\end{align*}
where the last inequality follows from
\eqref{eq:stopped-bound} and \eqref{eq:jump-identity}.
Lemma~\ref{lem:comparison} bounds the last expression by
\[
 108\cdot28\cdot\frac1t\sum_{s=1}^t
                  \E\|x_{X_s}-x_{X_0}\|_1^2.
\]
The stationary walk satisfies
\[
 \frac1t\sum_{s=1}^t\E\|x_{X_s}-x_{X_0}\|_1^2
 =\sum_{i,j}\pi_i\left(\frac1t\sum_{s=1}^t A^s\right)_{ij}
                  \|x_i-x_j\|_1^2.
\]
This is \eqref{eq:cotype} with $C^2=3024$.
\end{proof}

\begin{remark}\label{rem:stationary}
The proof uses reversibility only through $\pi A=\pi$.
Consequently, the same inequality and the same construction
hold for every stationary stochastic matrix, without detailed
balance. No positivity assumption on the individual $\pi_i$
is needed in the argument.
\end{remark}

\subsection{An expected-median interpretation}
The construction has an intrinsic description in the original
coordinates. Let
\[
 G=p\sum_{s=0}^\infty q^s A^s
\]
be the stochastic matrix of geometric endpoints. For fixed $i$,
take independent indices $J_1,J_2,J_3$ with common law
$\Prob(J_a=j)=G_{ij}$. For three real vectors, write
$\med(x,x',x'')$ for their coordinatewise median. This vector
belongs to $\ell_1$, since its coordinatewise absolute value is
at most $|x|+|x'|+|x''|$. Then
\begin{equation}\label{eq:median}
 y_i=\E\,\med(x_{J_1},x_{J_2},x_{J_3}).
\end{equation}
In each original coordinate, the median is at least a given
threshold exactly when at least two of the three values are.
The threshold decomposition in the proof of
Lemma~\ref{lem:cuts} therefore gives the pointwise identity
\[
 \med(x_{J_1},x_{J_2},x_{J_3})
 =v+\sum_{B\in\mathcal B} b_B
       \ind_{\{\#\{a\in[3]:J_a\in B\}\geq2\}}.
\]
Each indicator has expectation
$3h_i(B)^2(1-h_i(B))+h_i(B)^3=\phi(h_i(B))$.
Taking expectations in the finite sum proves \eqref{eq:median}.

\section{Complex scalars and Lipschitz extension}
\label{sec:consequences}

\begin{corollary}\label{cor:complex}
For complex scalars,
$N_2(\ell_1(\mathbb C))\leq12\sqrt{42}$.
\end{corollary}
\begin{proof}
The real-linear bijection
\[
 J:\ell_1(\mathbb C)\longrightarrow\ell_1(\R),\qquad
 Jx=(\Re x(1),\Im x(1),\Re x(2),\Im x(2),\ldots)
\]
satisfies
$\|x\|_1\leq\|Jx\|_1\leq\sqrt2\|x\|_1$.
Apply Theorem~\ref{thm:main} to $Jx_i$ and pull the resulting
points back by $J^{-1}$. The left side of \eqref{eq:cotype}
can only decrease, while its right side increases by at most
a factor of $2$.
\end{proof}

For the extension consequence, recall that a metric space
$(Z,d_Z)$ has \emph{Markov type two} with constant $M>0$ if
\[
 \sum_{i,j}\pi_i(A^t)_{ij}d_Z(u_i,u_j)^2
 \leq M^2t\sum_{i,j}\pi_i a_{ij}d_Z(u_i,u_j)^2
\]
for every $n,t\in\N$, every stochastic matrix $A$ reversible
with respect to a probability vector $\pi$, and every
$u_1,\ldots,u_n\in Z$. Hilbert spaces satisfy this inequality
with $M=1$ \cite{Ball92}; see also \cite[Definition~1.1 and the following
discussion]{MendelNaor13}.

\begin{samepage}
\begin{corollary}\label{cor:extension}
There is a universal constant $K<\infty$ such that, for every
real Hilbert space $\mathcal H$, every subset $S\subseteq\mathcal H$,
and every Lipschitz map $f:S\to\ell_1$, there is an extension
$F:\mathcal H\to\ell_1$ with
$\Lip(F)\leq K\Lip(f)$.
\end{corollary}
\begin{proof}
We use the Lipschitz extension theorem in
\cite[Corollary~1.13]{MendelNaor13}, extending Ball's theorem
\cite{Ball92}. In its Banach-space form, a source with Markov
type two and a dual Banach target with metric Markov cotype two
admit extensions with a constant bounded by a universal multiple
of the two corresponding constants. A Hilbert space has Markov
type two with constant one, and $\ell_1$ is the dual of $c_0$.
Theorem~\ref{thm:main} verifies the remaining hypothesis.
\end{proof}
\end{samepage}

\bibliographystyle{amsplain}
\bibliography{references}
\end{document}
==== END Metric-Markov-Cotype-Two-of-l1//main.tex ====

==== BEGIN Metric-Markov-Cotype-Two-of-l1//references.bib ====
@article{Ball92,
  author = {Ball, Keith},
  title = {{Markov} chains, {Riesz} transforms and {Lipschitz} maps},
  journal = {Geometric and Functional Analysis},
  volume = {2},
  number = {2},
  year = {1992},
  pages = {137--172},
  doi = {10.1007/BF01896971}
}

@article{MendelNaor13,
  author = {Mendel, Manor and Naor, Assaf},
  title = {Spectral calculus and {Lipschitz} extension for barycentric metric spaces},
  journal = {Analysis and Geometry in Metric Spaces},
  volume = {1},
  year = {2013},
  pages = {163--199},
  doi = {10.2478/agms-2013-0003}
}

@book{DezaLaurent97,
  author = {Deza, Michel Marie and Laurent, Monique},
  title = {Geometry of Cuts and Metrics},
  series = {Algorithms and Combinatorics},
  volume = {15},
  publisher = {Springer-Verlag},
  address = {Berlin},
  year = {1997},
  doi = {10.1007/978-3-642-04295-9}
}

@article{NaorYoung22,
  author = {Naor, Assaf and Young, Robert},
  title = {Foliated corona decompositions},
  journal = {Acta Mathematica},
  volume = {229},
  number = {1},
  year = {2022},
  pages = {55--200},
  doi = {10.4310/ACTA.2022.v229.n1.a2}
}

@misc{ChengWangXiang26,
  author = {Cheng, Qingjin and Wang, Yue and Xiang, Bo},
  title = {Sharp metric cotype inequalities for {$L_1$} via nonlinear cut smoothing},
  year = {2026},
  note = {Preprint, arXiv:2609.08749v2, September 9, 2026},
  doi = {10.48550/arXiv.2609.08749}
}
==== END Metric-Markov-Cotype-Two-of-l1//references.bib ====