# Cuts and a flat cubic

*Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).*

This lesson provides the two tools of the proof in [A stopped walk and the cotype of ℓ₁](a-stopped-walk-and-the-cotype-of-l1.md) [OpenAI-C, Sections 2 and 3]. First, finitely many points of \(\ell_1\) are written as *weighted cuts*: binary vectors \(z_i\) indexed by subsets of the points, with weights, such that \(\ell_1\)-distances become weighted Hamming distances, and with an affine map back into \(\ell_1\) that does not increase distances (Lemma 1.1). Since a weighted Hamming distance between binary vectors is also the square of a weighted Euclidean distance, squared \(\ell_1\)-distances become fourth powers of Hilbert distances. Second, the cubic \(\phi(r)=3r^2-2r^3\), applied to each coordinate of \([0,1]\)-valued vectors, is *flat* at the binary points: its derivative vanishes at \(0\) and \(1\). Lemma 2.1 bounds the squared size of its increments by the second-order remainder of a fourth-power Hilbert potential, and Lemma 3.1 sums these bounds along a harmonic function of a Markov chain, where the first-order terms cancel.

We use the finite Markov chains of [Markov chains and metric Markov cotype](markov-chains-and-metric-markov-cotype.md), Section 1.

## 1. Cuts

The real space \(\ell_1\) consists of the real sequences \(x=(x(k))_{k\ge1}\) with \(\|x\|_1=\sum_k|x(k)|<\infty\). For a finite set \(\mathcal B\) and positive weights \((w_B)_{B\in\mathcal B}\), write for \(u\in\mathbb R^{\mathcal B}\)
\[
\begin{gathered}
\|u\|_{1,w}=\sum_{B\in\mathcal B}w_B|u_B|,\\
\|u\|_H^2=\sum_{B\in\mathcal B}w_Bu_B^2,\\
\langle u,u'\rangle_H=\sum_Bw_Bu_Bu'_B.
\end{gathered}
\]
For binary vectors \(z,z'\in\{0,1\}^{\mathcal B}\), \(|z_B-z'_B|=(z_B-z'_B)^2\), so \(\|z-z'\|_{1,w}=\|z-z'\|_H^2\).

**Lemma 1.1** (cut representation). Let \(x_1,\dots,x_n\in\ell_1\), not all equal. There are a finite set \(\mathcal B\) of nonempty proper subsets of \([n]\), positive weights \(w_B\), the binary vectors \(z_i=(\mathbf 1_{i\in B})_{B\in\mathcal B}\), and an affine map \(T:\mathbb R^{\mathcal B}\to\ell_1\) such that
\[
\begin{aligned}
&T(z_i)=x_i,\\
&\|x_i-x_j\|_1=\|z_i-z_j\|_{1,w}\\
&\quad =\|z_i-z_j\|_H^2,\\
&\|T(u)-T(u')\|_1\\
&\quad \le\|u-u'\|_{1,w}.
\end{aligned}\tag{1.1}
\]

**Proof.** Let \(v(k)=\min_ix_i(k)\) and, for each nonempty proper \(B\subset[n]\),
\[
b_B(k)=\Bigl(\min_{i\in B}x_i(k)-\max_{i\notin B}x_i(k)\Bigr)_+,
\]
where \(r_+=\max\{r,0\}\). Since \(|v(k)|\le\sum_i|x_i(k)|\) and \(0\le b_B(k)\le2\sum_i|x_i(k)|\), \(v\) and \(b_B\) lie in \(\ell_1\). Let \(\mathcal B\) be the set of \(B\) with \(w_B=\|b_B\|_1>0\), and \(T(u)=v+\sum_{B\in\mathcal B}u_Bb_B\).

Fix \(k\), and let \(\alpha_1<\dots<\alpha_m\) be the distinct values among \(x_1(k),\dots,x_n(k)\). If \(B\) is not of the form \(\{i:x_i(k)\ge\alpha\}\), some \(i\in B\) and \(j\notin B\) have \(x_i(k)\le x_j(k)\), and then \(b_B(k)=0\). The sets \(B_r=\{i:x_i(k)\ge\alpha_{r+1}\}\), \(1\le r<m\), have \(b_{B_r}(k)=\alpha_{r+1}-\alpha_r>0\), so they belong to \(\mathcal B\); they are the only \(B\) with \(b_B(k)\neq0\), and they are nested. Hence
\[
\begin{aligned}
&T(z_i)(k)=\alpha_1\\
&\quad +\sum_{r:\,i\in B_r}(\alpha_{r+1}-\alpha_r)=x_i(k),
\end{aligned}
\]
the sum running over the gaps below \(x_i(k)\). If \(x_i(k)\ge x_j(k)\), every \(B_r\) containing \(j\) contains \(i\), so all nonzero terms of \(\sum_B(z_i(B)-z_j(B))b_B(k)\) have the same sign, and \(|x_i(k)-x_j(k)|\) equals \(\sum_B|z_i(B)-z_j(B)|\,b_B(k)\). Summing over \(k\), \(\|x_i-x_j\|_1=\sum_B|z_i(B)-z_j(B)|w_B\). Finally \(\|T(u)-T(u')\|_1=\|\sum_B(u_B-u'_B)b_B\|_1\), which is at most \(\sum_B|u_B-u'_B|\,w_B\). \(\square\)

The map \(T\) takes values in the whole space \(\ell_1\), not only in the span of the data; this is used in the next lesson, where new points are built as \(T\) of non-binary vectors.

## 2. A flat cubic

Fix \(\mathcal B\) and \(w\) as in Section 1, let \(Q=[0,1]^{\mathcal B}\), and let
\[
\begin{gathered}
\phi(r)=3r^2-2r^3\quad(0\le r\le1),\\
\Phi(u)=(\phi(u_B))_{B\in\mathcal B}\quad(u\in Q).
\end{gathered}
\]
Then \(\phi(0)=0\), \(\phi(1)=1\), \(\phi\) is increasing, \(\Phi(Q)\subseteq Q\), and \(\Phi\) fixes the binary vectors. Also \(\phi(h)=3h^2(1-h)+h^3\) is the probability that at least two of three independent events of probability \(h\) occur.

**Lemma 2.1** (flatness; OpenAI). Let \(u,u'\in Q\) and \(e\in\{0,1\}^{\mathcal B}\), and put \(a=u-e\), \(\delta=u'-u\) and \(F_e(u)=\|u-e\|_H^4\). Then the inequality (2.1) holds:
\[
\begin{aligned}
&\|\Phi(u')-\Phi(u)\|_{1,w}^2\\
&\quad\le108\Bigl(F_e(u')-F_e(u)\\
&\qquad-4\|a\|_H^2\langle a,\delta\rangle_H\Bigr).
\end{aligned}
\]

**Proof.** For \(d\in\{0,1\}\) and \(r\in[0,1]\), \(|\phi'(r)|=6r(1-r)\le6|r-d|\). With \(d=e_B\), integrating along the segment from \(u_B\) to \(u'_B\),
\[
\begin{aligned}
&|\phi(u'_B)-\phi(u_B)|\\
&\quad \le6|\delta_B|\int_0^1|a_B+s\delta_B|\,ds\\
&\quad \le6|a_B||\delta_B|+3\delta_B^2.
\end{aligned}
\]
Summing with the weights and using the Cauchy–Schwarz inequality, \(\|\Phi(u')-\Phi(u)\|_{1,w}\) is at most \(6\|a\|_H\|\delta\|_H+3\|\delta\|_H^2\). Let \(R\) be the bracket in (2.1). Expanding \(\|a+\delta\|_H^4=(\|a\|_H^2+2\langle a,\delta\rangle_H+\|\delta\|_H^2)^2\),
\[
\begin{aligned}
R&=2\|a\|_H^2\|\delta\|_H^2\\
&\quad +\bigl(2\langle a,\delta\rangle_H+\|\delta\|_H^2\bigr)^2.
\end{aligned}\tag{2.2}
\]
So \(\|a\|_H^2\|\delta\|_H^2\le R/2\), and
\[
\begin{aligned}
&\|\delta\|_H^4\le2\bigl(2\langle a,\delta\rangle_H+\|\delta\|_H^2\bigr)^2\\
&\quad +8\langle a,\delta\rangle_H^2\le2\bigl(2\langle a,\delta\rangle_H+\|\delta\|_H^2\bigr)^2\\
&\quad +8\|a\|_H^2\|\delta\|_H^2\le4R.
\end{aligned}
\]
Therefore 
\[
\begin{aligned}
&\|\Phi(u')-\Phi(u)\|_{1,w}^2\\
&\quad\le72\|a\|_H^2\|\delta\|_H^2+18\|\delta\|_H^4\\
&\quad\le36R+72R=108R.
\end{aligned}
\]
\(\square\)

The bracket in (2.1) is the potential \(F_e\) minus its linear approximation at \(u\). For the identity map in place of \(\Phi\), no such bound holds near a binary point (Exercise 4.3): the flatness of \(\phi\) at \(0\) and \(1\) is what makes the increments of \(\Phi\) quadratically small there.

## 3. Summing along a harmonic function

Let \((\omega_m)_{m\ge0}\) be a Markov chain on a finite set \(\Sigma\), with transition probabilities \(P(\sigma,\sigma')\) and any initial law. A function \(f:\Sigma\to Q\) is *harmonic* if \(\sum_{\sigma'}P(\sigma,\sigma')f(\sigma')=f(\sigma)\) for every \(\sigma\).

**Lemma 3.1** (telescoping). Let \(f\) be harmonic, \(E\colon\Sigma\to\{0,1\}^{\mathcal B}\) any function, \(M_m=f(\omega_m)\) and \(e=E(\omega_0)\). Then for every \(L\ge1\)
\[
\begin{aligned}
&\sum_{m=0}^{L-1}\mathbb E\|\Phi(M_{m+1})-\Phi(M_m)\|_{1,w}^2\\
&\quad \le108\bigl(\mathbb E\|M_L-e\|_H^4-\mathbb E\|M_0-e\|_H^4\bigr).
\end{aligned}
\]

**Proof.** Apply Lemma 2.1 with \(u=M_m\), \(u'=M_{m+1}\) and take expectations. Summing over the paths, 
\[
\begin{aligned}
&\mathbb P(\omega_0=\sigma_0,\omega_m=\sigma,\omega_{m+1}=\sigma')\\
&\quad=\mathbb P(\omega_0=\sigma_0,\omega_m=\sigma)\,P(\sigma,\sigma').
\end{aligned}
\]
So with \(g(\sigma_0,\sigma)\) defined as \(4\|f(\sigma)-E(\sigma_0)\|_H^2\,(f(\sigma)-E(\sigma_0))\),
\[
\begin{aligned}
&\mathbb E\bigl[\langle g(\omega_0,\omega_m),M_{m+1}-M_m\rangle_H\bigr]\\
&\quad=\sum_{\sigma_0,\sigma}\mathbb P(\omega_0=\sigma_0,\omega_m=\sigma)\\
&\qquad\cdot\Bigl\langle g(\sigma_0,\sigma),\\
&\qquad\qquad\sum_{\sigma'}P(\sigma,\sigma')f(\sigma')-f(\sigma)\Bigr\rangle_H\\
&\quad=0.
\end{aligned}
\]
The remaining terms telescope. \(\square\)

The centre \(e\) may depend on the initial state; in the next lesson it is the binary vector of the starting point of the walk.

## 4. Exercises

**Exercise 4.1** (easy). Work out Lemma 1.1 for two points \(x_1\neq x_2\): which subsets occur, with which weights?

**Exercise 4.2** (easy). Check that \(\phi'(0)=\phi'(1)=0\), that \(\phi\) maps \([0,1]\) onto itself, and that \(\phi(h)\) is the probability that at least two of three independent events of probability \(h\) occur.

**Exercise 4.3** (medium). Show that (2.1) fails for every constant if \(\Phi\) is replaced by the identity: take one coordinate with weight \(1\), \(e=0\), \(u=0\) and \(u'=\varepsilon\).

**Exercise 4.4** (easy). Verify (2.2).

## 5. Solutions

**4.1.** Only \(B=\{1\}\) and \(B=\{2\}\), with \(b_{\{1\}}=(x_1-x_2)_+\) and \(b_{\{2\}}=(x_2-x_1)_+\); one of them may have weight \(0\) and be omitted. Then \(z_1=(1,0)\), \(z_2=(0,1)\) (on the subsets present), and \(\|x_1-x_2\|_1=w_{\{1\}}+w_{\{2\}}\).

**4.2.** \(\phi'(r)=6r(1-r)\geq0\), with \(\phi(0)=0\), \(\phi(1)=1\). Exactly two of three occur with probability \(3h^2(1-h)\), all three with probability \(h^3\), and \(3h^2(1-h)+h^3=3h^2-2h^3\).

**4.3.** With these choices \(a=0\), \(\delta=\varepsilon\), the bracket is \(\varepsilon^4\), while \(\|u'-u\|_{1,w}^2=\varepsilon^2\). The ratio \(\varepsilon^{-2}\) is unbounded. For \(\Phi\), \(\phi(\varepsilon)^2=(3\varepsilon^2-2\varepsilon^3)^2\le9\varepsilon^4\).

**4.4.** 
\[
\begin{aligned}
&F_e(u')=\|a+\delta\|_H^4\\
&\quad=\|a\|_H^4+2\|a\|_H^2(2\langle a,\delta\rangle_H+\|\delta\|_H^2)\\
&\qquad+(2\langle a,\delta\rangle_H+\|\delta\|_H^2)^2;
\end{aligned}
\]
subtract \(F_e(u)=\|a\|_H^4\) and \(4\|a\|_H^2\langle a,\delta\rangle_H\).

## References

- [OpenAI-C] OpenAI, *Metric Markov cotype two of \(\ell_1\)*, OpenAI Math Release preprint, 5 October 2026, Sections 2 and 3. https://github.com/openai/math/tree/main/preprints/Metric-Markov-Cotype-Two-of-l1-October-5-2026