Metric Markov cotype two of ℓ₁

Source and verification

This article explains family 332 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

Overview

Metric Markov cotype asks whether values assigned to a reversible chain can be moved a controlled distance so that their one-step variation decreases. Family 332 claims that real ${\ell }_1$ has metric Markov cotype two, with a universal constant. Its construction smooths threshold cuts using a cubic polynomial; the new values can also be described as expected coordinatewise medians of three random endpoints. (OpenAI, 2026)

🏷️ Preliminaries: the modification inequality

Let $A=(a_{ij})$ be a finite stochastic matrix reversible with respect to a probability vector $\pi$. Thus $a_{ij}\ge 0$, row sums are one, and ${\pi }_i{a}_{ij}={\pi }_j{a}_{ji}$. Zero stationary weights are allowed.

Given points $x_1,\dots ,x_n$ in a metric space and $t\ge 1$, define their average endpoint cost

$$\begin{array}{c}{R}_t(x)\\ =\frac{1}{t}\sum _{s=1}^t\sum _{i,j}{\pi }_i(A^s{)}_{ij}d(x_i,x_j{)}^2.\end{array}$$

Metric Markov cotype two with constant $C$ means that there exist new points $y_i$ with

$$\begin{array}{c}\sum _i{\pi }_{i}d(x_i,y_i{)}^2\\ +t\sum _{i,j}{\pi }_i{a}_{ij}d(y_i,y_j{)}^2\\ \le C^2{R}_t(x).\end{array}$$

The first term pays for moving the data; the second penalizes variation of the new data on one chain step.

The $y_i$ are not required to be linear averages or to remain in a linear subspace containing the $x_i$. That freedom is essential.

Manuscript claim

For real ${\ell }_1$ with its usual norm, the least metric Markov cotype-two constant satisfies

$$N_2({\ell }_1)\le 12\sqrt{21}.$$

Equivalently, the squared constant may be taken to be $3024$, independently of the number of states, coordinates, and time. The source does not claim numerical optimality. (OpenAI, 2026)

A closed subspace of ${\ell }_1$ may fail metric Markov cotype: witnesses available in the whole space may leave the subspace. This property is not inherited automatically by subspaces.

🏷️ Threshold cuts and an ambient reconstruction

For finitely many real scalars, sort their values. Their pairwise distances are sums of gaps across threshold cuts. Applying this to every coordinate of $x_1,\dots ,x_n\in {\ell }_1$ and grouping identical cuts gives a finite collection $\mathcal{B}$ of subsets of the state set, with positive weights $w_B$.

Write $z_i(B)=1$ when $i\in B$ and zero otherwise. Then

$$\begin{array}{c}\Vert z_i-z_j{\Vert }_H^2=\Vert x_i-x_j{\Vert }_1,\\ \Vert u{\Vert }_H^2=\sum _B{w}_B{u}_B^2.\end{array}$$

The square on the Hilbert norm is important: binary coordinate differences have equal absolute value and square.

The cut construction also retains an affine reconstruction $T$ with $T(z_i)=x_i$ and

$$\begin{array}{c}\Vert T(u)-T(v){\Vert }_1\le \Vert u-v{\Vert }_{1,w},\\ \Vert u{\Vert }_{1,w}=\sum _B{w}_B|u_B|.\end{array}$$

This returns modified cut coordinates to the original ambient ${\ell }_1$. A distance representation alone would not provide that map.

🏷️ Geometric stopping and cubic smoothing

Let $p=1/(t+1)$ and $q=1-p$. Stop an $A$-walk after an independent number $S$ of steps with $\mathbb{P}(S=s)=p{q}^s$, $s\ge 0$. Its mean is $q/p=t$.

The expected cut vector from state $i$ is

$$h_i=p\sum _{s=0}^{\infty }{q}^s(A^{s}z{)}_i.$$

It lies in the cut cube and satisfies

$$h_i=p{z}_i+q\sum _j{a}_{ij}{h}_j.$$

Instead of reconstructing this linear average directly, apply

$$\begin{array}{c}\varphi (r)=3r^2-2r^3,\\ \Phi (u{)}_B=\varphi (u_B),\\ y_i=T(\Phi (h_i)).\end{array}$$

The cubic fixes zero and one and has derivative zero at both. Its flatness at binary endpoints provides the quantitative gain.

🏷️ A fourth-power potential pays for both costs

Attach $h_i$ to an alive state of index $i$. With probability $p$ it dies at $i$ and acquires value $z_i$; otherwise it moves according to $A$ and remains alive. The first-step identity makes the attached values $(M_k)$ a Hilbert-valued martingale, terminating at $z_{X_S}$.

For a binary reference vector $e$, put $F_e(u)=\Vert u-e{\Vert }_H^4$. The manuscript’s cubic estimate is

$$\begin{array}{c}\Vert \Phi (u^{\prime })-\Phi (u){\Vert }_{1,w}^2\le 108{\mathcal{R}}_e(u,u^{\prime }),\\ {\mathcal{R}}_e(u,u^{\prime })=F_e(u^{\prime })-F_e(u)\\ -⟨\nabla F_e(u),u^{\prime }-u{⟩}_H.\end{array}$$

The quantity ${\mathcal{R}}_e$ is a convexity remainder. Conditional expectation kills the linear term for martingale increments, so the potential differences telescope.

Take $e=z_{X_0}$, which is known at the initial time. The terminal potential equals $\Vert x_{X_S}-x_{X_0}{\Vert }_1^2$. Define

$$\begin{array}{rl}B& =\sum _i{\pi }_i\Vert z_i-\Phi (h_i){\Vert }_{1,w}^2,\\ E& =\sum _{i,j}{\pi }_i{a}_{ij}\Vert \Phi (h_i)-\Phi (h_j){\Vert }_{1,w}^2.\end{array}$$

At time $k$, death contributes $p{q}^{k}B$ and a live transition contributes $q^{k+1}E$. Summing gives the exact identity

$$\sum _{k\ge 0}(p{q}^{k}B+q^{k+1}E)=B+tE.$$

Thus stopping pays for the modification, while the expected $t$ live steps pay for the new one-step energy.

Contractivity of $T$ transfers these two costs to the desired points. The source’s geometric-to-finite-time comparison gives

$$\mathbb{E}\Vert x_{X_S}-x_{X_0}{\Vert }_1^2\le 28R_t(x).$$

Combining the two lemmas yields $108\cdot 28=3024$. The cubic remainder bound and the endpoint comparison are the estimates underlying this proof outline.

🏷️ Expected medians and Lipschitz extension

For fixed $i$, let $J_1,J_2,J_3$ be independent geometric-walk endpoints started at $i$. A threshold is exceeded by their coordinatewise median exactly when at least two endpoints exceed it. If the single-endpoint probability is $r$, this event has probability

$$3r^2(1-r)+r^3=\varphi (r).$$

Consequently

$$y_i=\mathbb{E}\mathrm{med}(x_{J_1},x_{J_2},x_{J_3}).$$

This explains the cubic and the nonlinear nature of the construction.

Using the Mendel–Naor extension theorem, the manuscript deduces that 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. This consequence uses an additional extension theorem; the constant-one Kirszbraun conclusion is not asserted.

The proof of the cotype inequality actually uses stationarity rather than full detailed balance, as the manuscript notes. Reversibility remains part of the usual definition.

🏷️ Key steps and proof outlines

Binary cuts convert the geometry into a quartic potential

For finitely many data points in ${\ell }_1$, decompose each coordinate into its intervals between successive coordinate values. Each interval defines a cut of the index set, with a nonnegative weight. Combining identical cuts gives binary vectors $z_i$ in a finite weighted Hilbert space $H$ such that

$$\Vert z_i-z_j{\Vert }_H^2=\Vert x_i-x_j{\Vert }_1.$$

There is also an affine reconstruction map $T$ that sends $z_i$ to $x_i$ and contracts the weighted ${\ell }_1$ norm. The distinction between these two norms is deliberate: the input squared metric distance becomes a fourth power in $H$, while reconstructed increments are controlled in weighted ${\ell }_1$. (OpenAI, 2026)

Flat endpoints make a cubic map compatible with fourth powers

Set $\varphi (r)=3r^2-2r^3$ on $[0,1]$ and apply it coordinatewise as $\Phi$. It fixes both bits and has zero derivative there. For a binary endpoint $e$, put $a=u-e$ and $\delta =u^{\prime }-u$. Since $|{\varphi }^{\prime }(r)|\le 6|r-e_B|$ in coordinate $B$, integration and weighted Cauchy–Schwarz give

$$\Vert \Phi (u^{\prime })-\Phi (u){\Vert }_{1,w}\le 6\Vert a{\Vert }_H\Vert \delta {\Vert }_H+3\Vert \delta {\Vert }_H^2.$$

The convexity remainder of $F_e(u)=\Vert u-e{\Vert }_H^4$ has the exact identity

$$\begin{array}{rl}{R}_e& =F_e(u^{\prime })-F_e(u)-4\Vert a{\Vert }_H^2⟨a,\delta {⟩}_H\\ & =2\Vert a{\Vert }_H^2\Vert \delta {\Vert }_H^2+(2⟨a,\delta {⟩}_H+\Vert \delta {\Vert }_H^2{)}^2.\end{array}$$

Thus $\Vert a{\Vert }^2\Vert \delta {\Vert }^2\le R_e/2$ and $\Vert \delta {\Vert }^4\le 4R_e$. Squaring the increment bound yields $\Vert \Phi (u^{\prime })-\Phi (u){\Vert }_{1,w}^2\le 108R_e$. This calculation explains both the nonlinear smoothing and its explicit constant.

A killed walk turns the remainder into the two desired costs

Let $p=1/(t+1)$, $q=1-p$, and stop the Markov walk after an independent geometric number $S$ of transitions. The resolvent values

$$h_i=p\sum _{s\ge 0}{q}^s(A^{s}z{)}_i$$

satisfy $h_i=p{z}_i+q{\sum }_j{a}_{ij}{h}_j$. This identity says that the process which currently reports $h_i$, then either dies and reports $z_i$ or moves to the next state and reports its $h$ value, is a martingale. After death it remains constant.

Apply the quartic remainder estimate with the initial binary point as center. The linear term has conditional mean zero, so the potentials telescope. Death jumps contribute the cost between $\Phi (h_i)$ and $z_i$; surviving jumps contribute the edge cost between $\Phi (h_i)$ and $\Phi (h_j)$. Summing survival probabilities produces the coefficient $q/p=t$ on the latter. Reconstruction by $T$ gives the desired points $y_i=T\Phi (h_i)$ and can only decrease these costs.

Geometric time is compared with the required finite average

Write $D(s)=\mathbb{E}d(x_{X_s},x_{X_0}{)}^2$ for a stationary walk and $W=t^{-1}{\sum }_{s=1}^{t}D(s)$. Minkowski and stationarity give $\sqrt{D(r+s)}\le \sqrt{D(r)}+\sqrt{D(s)}$. Averaging the resulting inequality $D(t)\le 2D(r)+2D(t-r)$ gives $D(t)\le 4W$.

Write $S=Jt+R$, with $0\le R<t$. Then $D(S)\le 2J^{2}D(t)+2D(R)$. The geometric second moment gives $\mathbb{E}{J}^2\le 3$, while $\mathbb{P}(R=r)\le 2/t$ gives $\mathbb{E}D(R)\le 2W$. Consequently $\mathbb{E}D(S)\le 28W$. Combining this with the quartic estimate gives the reported constant $108\cdot 28=3024$.

The cubic also has a probabilistic interpretation: $\varphi (r)$ is the probability that at least two of three independent Bernoulli variables with parameter $r$ equal one. Thus the construction is a median-type nonlinear average. Ordinary linear smoothing would not have the endpoint flatness used in the remainder estimate. The extension consequence then uses the cited metric Markov cotype extension theorem with its stated hypotheses.

See Also

• Markov type bounds displacement without moving the given values; it is a different invariant.
• Rademacher cotype concerns independent signed sums and should not be substituted for metric Markov cotype.

🏷️ Manuscripts and verification scope

• Metric Markov Cotype Two of ${\ell }_1$ — pinned manuscript and companion source.

No family scope page was present at lean/docs/332.md in the pinned snapshot. This does not establish that all related formalization code is absent. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Metric Markov Cotype Two of ℓ₁.