Markov cotype of ℓ1 and Lipschitz extension

← All digests

Family 332 · Functional analysis
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-25

1. The question

Suppose a function is defined on only part of a Hilbert space, and nearby inputs always have nearby outputs in $\ell_1$, the space of absolutely summable sequences. Can it be extended to every input while increasing its Lipschitz constant by at most one universal factor?

This is Ball’s extension problem for the target $\ell_1$. The factor must work independently of the dimension, the subset, and the function. Extending coordinates separately is not enough: their errors can accumulate when the target norm adds absolute values.

Family 332 claims a positive answer through a random-walk property called metric Markov cotype two. The main theorem says that values assigned to the states of a finite chain can be adjusted to reduce their one-step variation, while paying a controlled cost for moving them.

The adjustment is nonlinear. Rather than taking a prescribed linear average, the manuscript constructs new values using the expected coordinatewise median of three independent random-walk endpoints. This freedom is the feature that allows the proposed result to coexist with earlier negative statements about linear averaging and subspaces.

2. Background and essential definitions

The real Banach space $\ell_1$ consists of sequences $x=(x(k))_{k\geq1}$ with

$$\|x\|_1=\sum_{k\geq1}|x(k)|<\infty.$$

A map $f$ is Lipschitz when some finite $L$ satisfies $d(f(u),f(v))\leq Ld(u,v)$ for all inputs. The least such constant is $\operatorname{Lip}(f)$. An extension agrees with $f$ everywhere on its original domain.

A stochastic matrix $A=(a_{ij})$ has nonnegative entries and rows summing to one. It specifies a finite Markov chain. A probability vector $\pi$ is stationary when $\pi A=\pi$, and reversible when

$$\pi_i a_{ij}=\pi_j a_{ji}.$$

Reversibility implies stationarity. The entry $(A^s)_{ij}$ is the probability of traveling from $i$ to $j$ in $s$ steps.

To define metric Markov cotype two, start with arbitrary points $x_1,\ldots,x_n$ in a metric space and choose a time $t\geq1$. One must find replacement points $y_1,\ldots,y_n$ so that

$$\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 B_{ij}d(x_i,x_j)^2,$$

where

$$B=\frac1t\sum_{s=1}^{t}A^s.$$

The first term is the cost of modifying the data. The second is the remaining one-step variation, multiplied by time. The right side measures the original variation averaged over times one through $t$. One constant $C$ must work for every chain, dataset, and time. Its optimal value is denoted $N_2(X)$.

3. Development history and previous partial results

Ball introduced Markov type and cotype in his work on Lipschitz maps. Markov type controls how far a stationary reversible walk travels relative to its one-step motion. Markov cotype asks for a complementary smoothing operation on the target values.

There are different cotype formulations. Ball’s Banach-space condition uses specified linear averages, and $\ell_1$ fails that stronger condition. His metric formulation allows more freedom. Mendel and Naor developed the time-averaged definition above, established its relationship with Ball’s metric definition, and explicitly asked whether $N_2(\ell_1)$ is finite.

For $1<p\leq2$, uniformly convex theory gives metric Markov cotype two for $\ell_p$, with known bounds deteriorating as $p$ approaches one. Consequently, simply taking an endpoint limit does not settle the $\ell_1$ question.

Mendel and Naor also used a construction of Kalton to find a closed linear subspace of $\ell_1$ failing metric Markov cotype at every finite exponent. This may initially sound incompatible with a positive theorem for the whole space. The distinction is that the replacement points may leave the subspace containing the original data. The metric condition is not automatically inherited by arbitrary subspaces.

Their extension framework already showed why the endpoint question mattered: a positive answer for $\ell_1$ would yield the desired Hilbert-to-$\ell_1$ extension theorem. M1 claims the missing cotype result and then invokes that existing implication, rather than presenting the extension principle itself as new.

4. What the new manuscript claims

For real scalars, M1 states

$$N_2(\ell_1)\leq12\sqrt{21}.$$

Thus $C^2=3024$ works in the defining inequality, independently of the number of data points, sequence coordinates, or time parameter. The manuscript does not claim that this numerical constant is optimal. Zero entries of the stationary probability vector are allowed.

The proof is stated to use only stationarity, so M1 also records the same smoothing inequality and construction for stationary stochastic matrices without detailed balance. Reversibility remains part of the standard definition that the main theorem answers.

A real-linear comparison between complex sequences and their interlaced real and imaginary parts gives the additional bound

$$N_2(\ell_1(\mathbb C))\leq12\sqrt{42}.$$

The main extension consequence is formulated for a real Hilbert space $H$. For every subset $S\subset H$ and every Lipschitz map $f:S\to\ell_1$, M1 states that there is an extension $F:H\to\ell_1$ satisfying

$$F|_S=f, \qquad \operatorname{Lip}(F)\leq K\operatorname{Lip}(f),$$

where $K<\infty$ is universal. The subset need not be finite or convex, and no finite-dimensional hypothesis is imposed on $H$. The extension constant is obtained through the existing extension theorem; the manuscript does not identify its optimal value with the displayed cotype constant.

5. Why the advance matters

Importance: 5/5. The family claims a positive resolution of an explicit metric Markov cotype question and, through it, a universal extension theorem for an important classical target space.

Hilbert spaces express quadratic geometry, whereas $\ell_1$ measures length by adding absolute coordinate contributions. Moving between these geometries is difficult because a coordinatewise construction can lose uniform control. A constant independent of all dimensions and datasets is therefore the substantive conclusion.

The result would also emphasize the power of nonlinear smoothing. Choosing replacement points freely can succeed where a prescribed linear averaging rule fails. The expected-median construction makes that distinction concrete rather than merely existential.

Its compatibility with a bad subspace of $\ell_1$ is equally instructive. Having room in the ambient target can be essential. An extension or smoothing theorem for the whole space need not preserve every linear subspace containing the input data.

6. The main idea

The first step encodes a finite subset of $\ell_1$ by weighted cuts. A cut separates the indices of the data points into two groups. Thresholding each original coordinate produces such cuts, and the coordinate gaps supply nonnegative weights.

After collecting them, each original point $x_i$ has a finite binary encoding $z_i$. For a weighted Hilbert norm and a weighted $\ell_1$ norm on the cut coordinates, the encoding satisfies

$$\|x_i-x_j\|_1 =\|z_i-z_j\|_{1,w} =\|z_i-z_j\|_{H}^{,2}.$$

Binary coordinate differences have equal absolute value and square, explaining the last equality. M1 also retains an affine reconstruction map $T$ with $T(z_i)=x_i$, contractive from the weighted $\ell_1$ norm back to the original ambient $\ell_1$. The construction therefore remembers more than just pairwise distances.

Next, run the chain for an independent geometric number of steps with mean $t$, and average the binary endpoint encoding. Starting at state $i$ gives a vector $h_i$ in the unit cube. Apply the cubic function

$$\phi(r)=3r^2-2r^3 \qquad(0\leq r\leq1)$$

to each coordinate, then reconstruct:

$$y_i=T(\Phi(h_i)).$$

The cubic fixes zero and one and has zero derivative at both endpoints. Its flatness near binary values is central to the estimate. The manuscript uses a fourth-power Hilbert potential to control squared weighted-$\ell_1$ increments after applying $\Phi$.

To accumulate the estimate, M1 forms a martingale from the walk and its stopping event. A martingale is a process whose current value equals the conditional expectation of its next value. While the walk is alive, its attached value is the expected binary endpoint; on stopping, the actual binary endpoint is revealed.

The potential inequality telescopes in expectation because its linear remainder has conditional mean zero. The final stopping jump accounts for the cost of replacing $x_i$ by $y_i$. The expected preceding jumps account for $t$ times the remaining one-step variation. A separate comparison converts the geometric stopping cost to the average over times one through $t$, producing the stated constant.

There is a useful interpretation in the original coordinates. For three independent geometric-walk endpoints started at $i$, take the coordinatewise median of their data vectors and then its expectation. The result is exactly $y_i$. Indeed, if a threshold is exceeded with probability $r$, at least two of three independent samples exceed it with probability $3r^2-2r^3$.

Finally, Hilbert spaces have Markov type two with constant one, and $\ell_1$ is the dual of $c_0$, the space of sequences tending to zero. These facts and the new cotype bound satisfy the hypotheses of the cited extension theorem.

7. Scope, limitations, and open questions

The theorem allows replacement points anywhere in the full target. Requiring them to remain in a prescribed closed subspace, or to equal fixed linear averages, changes the problem and can make the corresponding assertion false.

Metric Markov cotype is also distinct from ordinary metric cotype and from Rademacher cotype, which concerns random signed sums of vectors. A theorem about one invariant cannot be substituted for another merely because their names are similar.

The displayed constants are upper bounds, not sharp values. The extension corollary guarantees existence with universal loss but does not provide an optimized algorithm for arbitrary infinite subsets. Determining optimal constants and effective constructions for concrete finite data remains separate work.

The source’s direct smoothing construction, its stationarity extension, and its Hilbert-space corollary are reported as stated. The mathematical proof is not independently checked here.

8. Sources and further reading

• Ball, Markov chains, Riesz transforms and Lipschitz maps, for the original probabilistic extension framework.
• Mendel and Naor, Spectral calculus and Lipschitz extension for barycentric metric spaces, for the metric cotype question, subspace obstruction, and extension theorem.
• Optional background: Lipschitz continuity and martingales.

Source manuscripts

• M1. OpenAI, Metric Markov Cotype Two of ℓ₁ (October 5, 2026).

Sources consulted on 25 October 2026 at repository revision 1581d4c. Download the manuscript citations.