Brenier Map Stability: The Three-Atom Twist in OpenAI’s One-Third Proof

How can moving a tiny amount of probability mass cause a much larger change in the optimal transport map? OpenAI’s Brenier map paper answers with three target atoms. Keep two atoms fixed and move the lightest one sideways. The target distribution barely changes, yet a thin region of the source gets reassigned to destinations roughly one unit apart.

OpenAI proves that for a fixed uniform convex source in dimension at least two, the root-mean-square distance between maps is bounded by a constant times the cube root of the targets’ 2-Wasserstein distance. The three-atom example attains that scale and disproves Cyril Letrouit’s conjectured uniform square-root bound. The distances pair points in different ways. The target distance can choose the cheapest matching between destinations, while the map distance compares where the same source point goes.

1. What Is a Brenier Map, and Why Does Its Stability Matter?

In quadratic optimal transport, a source distribution $\rho$ must be sent to a target distribution $\mu$. A map $T$ does this when its pushforward $T_{\#}\rho$ equals $\mu$. Drawing $x$ from $\rho$ and reporting $T(x)$ gives a sample with law $\mu$. The optimal map minimizes the average squared travel distance $\int_K |x-T(x)|^2\,d\rho(x)$ among maps with that pushforward.

For the source here, Brenier’s theorem identifies the optimal transport map as $T_\mu=\nabla u_\mu$ almost everywhere, where $u_\mu$ is convex. The map is unique up to source-null sets, and adding a constant to the potential leaves the map unchanged. For a target made of atoms, the gradient is piecewise constant. Stability asks how much those assignments can change when the target law changes.

2. The Original Problem: How Much Can an Optimal Transport Map Change?

Take $K\subset\mathbb{R}^d$ compact and convex with nonempty interior, and put $\rho=\mathbf{1}_K\,dx/|K|$, where $|K|$ is its volume. Fix a nonempty compact set $Y$ containing both targets. A coupling $\pi$ is a joint law of target points $y,z$ with marginals $\mu,\nu$. Define the target and map distances as follows.

Here $\Pi(\mu,\nu)$ is the set of all such couplings. For the second distance, the pairing is prescribed by the two maps evaluated at the same $x$. Those evaluations themselves induce a target coupling, so their root-mean-square disagreement is at least $W_2(\mu, u)$. The difficult direction is bounding it from above by a modulus that works across all pairs in the container. A bound that deteriorates as an atom loses mass cannot answer that uniform question.

3. Previous Stability Bounds and the Square-Root Conjecture

Earlier work on optimal transport stability often used $W_1$, the minimum mean travel distance. Delalande and Mérigot obtained a $W_1^{1/6}$ map bound for source densities bounded above and below on a convex domain and targets in a fixed compact set. The manuscript also cites a sharp $W_1^{1/4}$ result by Mérigot. The inequality $W_1\le W_2$ transfers a quarter-power upper bound to $W_2$ with the same power. It gives no route by itself to the stronger cube-root rate at small distances.

Earlier work by Mérigot, Delalande, and Chazal also obtained a dimension-independent exponent of $2/15$ in $W_1$ for a uniform convex source. At the other end of the regularity scale, the paper cites a Lipschitz bound in $W_2$ for uniformly positive Hölder densities on suitably regular, uniformly convex domains. Such density assumptions remove the light atoms that drive the cube example.

Divol, Niles-Weed, and Pooladian had already proved a $W_2^{1/3}$ estimate for regular sources and nondegenerate finite targets, with constants depending on features such as minimum atom mass and site geometry. Letrouit found an obstruction to exponents above one-third for a nonconvex source and conjectured that uniform square-root stability would hold for a uniform convex source. The cube example tests that conjecture with convexity fully in place.

4. OpenAI’s Main Theorem: Sharp One-Third Hölder Stability

Theorem 1.1 of OpenAI’s September 25, 2026 manuscript, Sharp One-Third Stability of Brenier Maps, fixes an integer $d\ge 2$, a compact convex body $K\subset\mathbb{R}^d$ with nonempty interior, its uniform law $\rho$, and a nonempty compact target container $Y\subset\mathbb{R}^d$. There is a finite constant $C(K,Y)$ such that for all Borel probability measures $\mu,\nu$ supported in $Y$,

The constant can depend on the geometry of the source and an enclosing radius for the targets. The stability of optimal transport maps is uniform across arbitrarily small positive atom masses, arbitrarily close sites, and targets with or without densities. The source body may have flat faces, and the compact target container may be nonconvex. The upper bound guarantees the cube-root rate across the class. Sharpness asks whether any larger exponent can work with one finite constant. Proposition 2.2 answers it on a single fixed cube in every dimension covered by the theorem.

5. The Three-Atom Counterexample: A Small Tilt With Large Consequences

Set $K=Y=[-1,1]^d$. Write $e_1,e_2$ for the first two coordinate unit vectors, take $0<a<1/2$, and put $b=a/2$. The paper compares two convex potentials, each a maximum of three affine functions.

Their gradients are optimal maps to their own pushforwards, by Lemma 2.1. The outer planes have slopes $-e_1$ and $e_1$. The middle plane has slope $0$ before the tilt and $be_2$ after it. The central Laguerre cell, where that plane wins, changes from $A_a=\{x\in K:|x_1|<a\}$ to $B_a=\{x\in K:|x_1|<a+bx_2\}$, ignoring null boundaries.

On the slice $x_2=t$, the conditional central mass changes from $a$ to $a+bt$. The positive and negative contributions cancel because $t$ is uniform on $[-1,1]$. The central weight therefore remains $a$ and the two outer weights remain $(1-a)/2$ each. Call the original and tilted target laws $\mu_a$ and $\nu_a$. Above the midline the central cell takes points from the outer cells. Below it the central cell gives points back.

6. Why the Three-Atom Example Rules Out Every Exponent Above One-Third

On the target side, fix both outer atoms and send mass $a$ from $0$ to $be_2$. The squared cost is $ab^2$. Every origin in the first target has second coordinate zero, and the second target puts mass $a$ at second coordinate $b$. That coordinate alone forces squared cost at least $ab^2$ in any coupling. Hence $W_2^2=ab^2$.

On the source side, write $A_a\triangle B_a$ for points in exactly one of the central cells. The intervals on any slice are nested, so the conditional mass in their symmetric difference is $b|t|$. Integrating against the uniform law of $t$ gives $b/2$. The map difference has first coordinate of magnitude one there and zero elsewhere. Its second coordinate has magnitude $b$ throughout $B_a$, whose mass is $a$. The coordinate contributions add as squares, giving $b/2+ab^2$. Substituting $b=a/2$ yields the exact distances.

The ratio of map distance to $W_2^\alpha$ is $2^{\alpha-1}\sqrt{1+a^2}\,a^{(1-3\alpha)/2}$. It diverges as $a$ tends to zero whenever $\alpha>1/3$, including $\alpha=1/2$. The number of atoms and the cube stay fixed. In this same family $W_1=ab=a^2/2$, so the map distance has quarter-power scaling in $W_1$ and cube-root scaling in $W_2$.

7. Laguerre Cells, Convex Potentials, and Prescribed Cell Masses

The positive proof begins with finite targets. For distinct sites $y_i$, let $u_c(x)=\max_i(x\cdot y_i+c_i)$ with intercepts $c_i$. The cell $P_i$ is the part of $K$ where the $i$th affine function wins. Its mass is $M_i=\rho(P_i)$ and its first moment is $B_i=\int_{P_i}x\,d\rho(x)$. The moment includes the mass, so the cell centroid is $B_i/M_i$ for a positive cell.

If two cells meet at a face $F_{ij}$, changing their relative intercepts moves the separating plane. The mass derivative on that face is weighted by $g_{ij}=\int_{F_{ij}}dS/(|K||y_i-y_j|)$, where $dS$ denotes surface measure. For moments the corresponding coefficient integrates $x$ over the face with the same normalization. Lower-dimensional contacts contribute zero. The fixed-site mass derivative in direction $q$ is the weighted graph Laplacian $(Gq)_i=\sum_{j\ne i}g_{ij}(q_i-q_j)$.

Positive cells form a connected face graph. The Laplacian has only constant vectors in its kernel and its range is the zero-sum vectors. For prescribed positive masses $m_i$ summing to one, minimizing a convex objective gives intercepts with $M_i=m_i$. Fixing $\sum_i m_i c_i=0$ removes the common additive shift. The implicit function theorem then gives differentiable intercepts as distinct sites move.

Changing a site adds a term proportional to $x\cdot(v_i-v_j)$ to the face motion for site velocities $v_i,v_j$. It gives the face’s first moment a second role. The coefficient that measures how an intercept change alters a cell moment also appears when site motion changes the mass. This symmetry is what later links the fixed-site estimate to the moving-site problem.

8. The Uniform Cell-Moment Estimate: The Proof’s Key Innovation

The proof now fixes the sites and varies the intercepts in direction $q$. Let dots denote derivatives in that direction and choose $R$ so $K$ lies in the ball of radius $R$ centered at zero. Lemma 4.1 bounds the first-moment derivatives by the mass derivatives with an absolute constant $C_0=162$.

Compare each cell at intercepts $c-sq$ and $c+sq$. If $X_i$ and $Z_i$ are sampled from those two cells, their midpoint lies in the original cell because the intercept perturbations cancel in the affine inequalities. The coupling uses Knothe’s triangular rearrangement to draw the two points using the same sequence of conditional quantiles. The arithmetic–geometric mean inequality on the diagonal derivatives of the midpoint map bounds its density. After weighting by the geometric mean of the two perturbed masses, the midpoint law is dominated by the restriction of $\rho$ to the original cell.

Testing this domination with $R^2-|x|^2$ produces a squared displacement term $|X_i-Z_i|^2/4$. Summing over the cells makes the endpoint integrals reduce to integrals on the whole source. The paper bounds the remaining terms by weighted squared mass changes and controls the moment differences before taking the derivative limit. The permitted step size can depend on the smallest mass. The resulting constant 162 is independent of cell count, masses, and site separation.

The gap between the arithmetic and geometric means of the two masses scales as their squared difference divided by the original cell mass. A Cauchy–Schwarz estimate absorbs the term coupling displacement to mass change.

9. Moving Target Atoms Without Losing Uniform Stability

Choose an optimal coupling of the finite targets and label its distinct pairs by $i$. Each carries mass $m_i$ and moves at velocity $v_i$ along the segment between its two sites. Write $w=W_2(\mu,\nu)$, so $\sum_i m_i|v_i|^2=w^2$. Swapping equal portions of two paired masses would improve the coupling if their endpoint differences had negative inner product. This nonnegative inner product keeps the segments’ moving sites distinct at every interior time, even when sites coincide at an endpoint.

Choose the normalized intercepts to keep each cell at its coupling mass and write $r_i=c_i'(t)$. Since $\sum_i m_i r_i=0$, the Laplacian range supplies an intercept direction $q$ with $(Gq)_i=m_i r_i$. Testing the differentiated mass constraints against that direction gives

Here $DB_i[q,0]$ is the first-moment derivative in the intercept direction with sites fixed. Weighted Cauchy–Schwarz and the cell-moment bound give $\bigl(\sum_i m_i r_i^2\bigr)^{1/2}\le\sqrt{162}\,Rw$.

The implicit function theorem provides differentiability for each particular configuration. The estimate used for stability comes from the mass-weighted calculation above. It requires no uniform bound on the inverse Laplacian, even when small cell faces make its weights poorly conditioned.

10. From Convex Potential Stability to the Sharp One-Third Exponent

On the active cell, the time derivative of the moving potential is $x\cdot v_i+r_i$. The velocity estimates bound its $L^2(\rho)$ norm by $(1+\sqrt{162})Rw$. Each intercept has a finite endpoint limit, and the endpoint maxima give the maps to the original targets, with repeated slopes merged. Integrating the derivative bound over the unit time interval gives

To turn this into a map bound, intersect the source with lines parallel to each coordinate axis. Convexity makes each nonempty slice an interval and makes the directional derivatives monotone along it. A forward difference over a length $h>0$ costs a factor $h^{-2}$ in squared norm. The monotone derivative error and the terminal portion of the slice, where the forward step leaves $K$, together cost a multiple of $h$. Summing the slice estimates gives

Here $L$ bounds the target radii and $P_K$ sums the $(d-1)$-dimensional volumes of the coordinate projections of $K$. For $w>0$, choosing $h=w^{2/3}$ puts both terms at scale $w^{2/3}$. Taking the square root gives the one-third exponent. When $w=0$, the targets coincide and uniqueness gives identical maps almost everywhere.

The sharpness family also checks the potential estimate. After subtracting the common weighted intercept mean, the paper computes $\lVert u_a- ilde{u}_a Vert_{L^2( ho)}^2=(5/16)W_2(\mu_a, u_a)^2$. Thus in this example the loss in exponent occurs when comparing the gradients. The values of the potentials themselves already obey a linear rate.

11. From Finite Targets to General Measures: Proof Scope and Lean Verification

For any target law on $Y$, send each point to a nearest point of a finite $\varepsilon$-net in $Y$, breaking ties by a fixed ordering. Each such discretization costs at most $\varepsilon$ in $W_2$. The uniform finite-target bound makes the associated maps Cauchy in $L^2(\rho)$ as the mesh tends to zero. Supporting inequalities for the convex potentials pass to the limit and identify its gradient as the unique optimal map. The same constant thus applies to discrete, singular, and absolutely continuous targets.

Using the same net for both targets increases their mutual distance by at most twice the mesh radius. This follows by taking any coupling of the original laws, rounding each point in the pair through the same selection, and applying the triangle inequality for the root-mean-square cost. Passing to the limit preserves the estimate for the two limiting maps.

OpenAI’s release announcement describes the broader research program. Its Lean scope note for family 374 reports formal proofs of the uniform one-third estimate and the fixed-cube obstruction for every larger exponent. The Lean comparator statements specify the hypotheses and the two conclusions that the proof modules are checked against. The theorem controls disagreement between exact optimal maps. Rates for nonuniform or changing sources require separate hypotheses. Solver runtime and numerical error are separate questions.

The Brenier map result explains how a vanishing target atom can still drive a substantial change in assignments. The linear control of the potentials survives that degeneration, while the cube geometry shows exactly how much can be lost when passing to their gradients. Follow Binary Verse AI’s coverage of AI-assisted mathematical proofs, including the role of convexity in the logarithmic Brunn–Minkowski proof and the use of Lean in the formalization of Fermat’s Last Theorem.