OctoInformBeta

OpenAI preprint, September 2026 · §4. A transport inequality

Lemma 4.1: Under the slot signature property, (H‾p−H‾d)2(\bar H_p-\bar H_d)^2 is at most κ\kappa times the slot graph energy of HH and times its transport energy

Two energies bound the gap between root means.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

From §3 to §6 the library works with a finite set Γ\Gamma, lists of disjoint pairs of elements of Γ\Gamma, and a positive function ff on the subsets of Γ\Gamma in place of the paper’s polynomial fqf_q. A multiaffine polynomial in variables indexed by Γ\Gamma is identified with its coefficient function on the subsets of Γ\Gamma, and the matroids enter only through the hypothesis that ff has the slot signature property (defined below).

Lemma 4.1 compares two weighted families of sets. Fix a subset AA of Γ\Gamma, two distinct elements pp and dd outside it, and a list PP of mm pairs (xt,yt)(x_t, y_t) of other elements. Adding one element of each pair to A∪{p}A \cup \{p\} gives 2m2^m sets, doing the same to A∪{d}A \cup \{d\} gives 2m2^m more, and ff weights them. The question is how far apart the ff-weighted means of a real function HH on the two families can be, against the Dirichlet energy of HH on a graph of single exchanges joining them: the comparison a Poincaré inequality makes, with a gap between two means in place of a variance.

Slot Totals and the Signature Property

The indicator vector 𝟏E\mathbf 1_E of a finite set E⊆ΓE \subseteq \Gamma is the vector of ℝΓ\mathbb R^\Gamma with entry 11 on EE and 00 elsewhere✦, and the pair direction of a pair (x,y)(x, y) is 𝟏{x,y}\mathbf 1_{\{x, y\}}✦. For vectors a1,…,aka_1, \dots, a_k of ℝΓ\mathbb R^\Gamma, the iterated derivative Da1Da2⋯DakfD_{a_1} D_{a_2} \cdots D_{a_k} f of ff applies the directional derivatives along ak,…,a1a_k, \dots, a_1 in turn, acting on coefficient functions.✦

The slot total of ff along a list P=((x1,y1),…,(xm,ym))P = ((x_1, y_1), \dots, (x_m, y_m)) of pairs of elements of Γ\Gamma is the iterated derivative along the pair directions, ∂Pf=D𝟏{x1,y1}⋯D𝟏{xm,ym}f.\partial_P f = D_{\mathbf 1_{\{x_1, y_1\}}} \cdots D_{\mathbf 1_{\{x_m, y_m\}}} f .(1)✦ When the pairs are disjoint and avoid a set AA, its value ∂Pf(A)\partial_P f(A) is the sum of ff over the sets obtained from AA by adding one element of each pair. The list PP is fresh for a set B⊆ΓB \subseteq \Gamma when the 2m2m entries of its pairs are distinct and none lies in BB.✦

The face Hessian of a real function gg on the subsets of Γ\Gamma at a subset AA is the symmetric matrix ∇A2g\nabla^2_A g indexed by Γ\A\Gamma \setminus A with zero diagonal and off-diagonal entries (∇A2g)ij=g(A∪{i,j})(i≠j).(\nabla^2_A g)_{ij} = g(A \cup \{i, j\}) \qquad (i \ne j).(2)✦ A bilinear form BB on a real vector space has one positive direction when, for every vector ee with B(e,e)>0B(e, e) > 0, every vector vv with B(v,e)=0B(v, e) = 0 has B(v,v)≤0B(v, v) \le 0; for a symmetric form this is the condition of at most one positive eigenvalue.✦ A function ff on the subsets of Γ\Gamma has the slot signature property when, for every list PP of pairs of elements of Γ\Gamma and every subset AA of Γ\Gamma, the bilinear form of the face Hessian ∇A2(∂Pf)\nabla^2_A(\partial_P f) has one positive direction.✦

The Slot Graph

Besides AA and PP, fix a finite family of roots ei∈Γe_i \in \Gamma, i∈Ii \in I, and a function W:Γ→ℝW : \Gamma \to \mathbb R of multipliers. The slot vertex set 𝒳\mathcal X is the set of subsets of Γ\Gamma obtained from AA by adding one element ztz_t of each pair and then one more element uu, either a root or the element z‾t\bar z_t of a pair that was not taken: 𝒳={A∪{z1,…,zm,u}:(zt,z‾t)∈{(xt,yt),(yt,xt)},u∈{ei:i∈I}∪{z‾1,…,z‾m}}.\mathcal X = \bigl\{ A \cup \{z_1, \dots, z_m, u\} : (z_t, \bar z_t) \in \{(x_t, y_t), (y_t, x_t)\},\ u \in \{e_i : i \in I\} \cup \{\bar z_1, \dots, \bar z_m\} \bigr\}.(3)✦ For a single pair (x,y)(x, y) and the roots pp and dd, its sets are A∪{p,x}A \cup \{p, x\}, A∪{p,y}A \cup \{p, y\}, A∪{d,x}A \cup \{d, x\}, A∪{d,y}A \cup \{d, y\} and A∪{x,y}A \cup \{x, y\}.

Two subsets SS and TT of Γ\Gamma are exchange adjacent when one is obtained from the other by exchanging one element: there are a set KK and distinct elements a,b∉Ka, b \notin K with S=K∪{a},T=K∪{b}.S = K \cup \{a\}, \qquad T = K \cup \{b\}.(4)✦

The missing multiplier mW(S)m_W(S) of a subset SS of Γ\Gamma is the sum of WW over the roots in SS plus W(xt)W(x_t) for each pair (xt,yt)(x_t, y_t) contained in SS: mW(S)=∑i∈I,ei∈SW(ei)+∑t:xt,yt∈SW(xt).m_W(S) = \sum_{i \in I,\ e_i \in S} W(e_i) + \sum_{t :\ x_t, y_t \in S} W(x_t).(5)✦

The slot graph energy of a real function HH on the subsets of Γ\Gamma is its Dirichlet energy on the exchange graph, which joins the exchange adjacent sets of 𝒳\mathcal X, with conductance the smaller of mW(S)f(S)m_W(S) f(S) and mW(T)f(T)m_W(T) f(T) on the edge from SS to TT: D𝒳(H)=12∑S,T∈𝒳S,T exchange adjacentmin⁡{mW(S)f(S),mW(T)f(T)}(H(S)−H(T))2.D_{\mathcal X}(H) = \frac12 \sum_{\substack{S, T \in \mathcal X \\ S,\, T \text{ exchange adjacent}}} \min\{m_W(S) f(S),\, m_W(T) f(T)\}\, \bigl(H(S) - H(T)\bigr)^2 .(6)✦ For a choice of the elements ztz_t in (3), the clique energy of HH on the sets A∪{z1,…,zm,u}A \cup \{z_1, \dots, z_m, u\}, with uu running over the roots and z‾1,…,z‾m\bar z_1, \dots, \bar z_m, is the Dirichlet energy of HH on the complete graph on these sets, with the weight ff and the multiplier W(u)W(u) at each set. The transport energy 𝒯(H)\mathcal T(H) of a real function HH on the subsets of Γ\Gamma is the sum of these clique energies over the 2m2^m choices of the elements ztz_t.

The Claim

Take pp and dd as the roots.✦ The means of a real function HH at the roots are its ff-weighted means on the sets obtained from A∪{p}A \cup \{p\} and from A∪{d}A \cup \{d\} by adding one element of each pair, written with slot totals: H‾p=∂P(fH)(A∪{p})∂Pf(A∪{p}),H‾d=∂P(fH)(A∪{d})∂Pf(A∪{d}).\bar H_p = \frac{\partial_P(fH)(A \cup \{p\})}{\partial_P f(A \cup \{p\})}, \qquad \bar H_d = \frac{\partial_P(fH)(A \cup \{d\})}{\partial_P f(A \cup \{d\})}.(7) The root coefficient κ\kappa of ff at AA, pp and dd with multipliers WW is κ=1spW(p)+1sdW(d)+2spsd∑t=1mvtW(xt),\kappa = \frac{1}{s_p W(p)} + \frac{1}{s_d W(d)} + \frac{2}{s_p s_d} \sum_{t=1}^{m} \frac{v_t}{W(x_t)},(8)✦ where sp=∂Pf(A∪{p})s_p = \partial_P f(A \cup \{p\}), sd=∂Pf(A∪{d})s_d = \partial_P f(A \cup \{d\}), vt=∂P\tf(A∪{p,d})v_t = \partial_{P \setminus t} f(A \cup \{p, d\}), and P\tP \setminus t is the list PP without its tt-th pair.

Theorem 1. Let ff be a positive function on the subsets of Γ\Gamma with the slot signature property, AA a subset of Γ\Gamma, pp and dd distinct elements of Γ\Gamma outside AA, and PP a list of pairs (xt,yt)(x_t, y_t) fresh for A∪{p,d}A \cup \{p, d\}. Let WW be a positive function on Γ\Gamma with W(xt)=W(yt)W(x_t) = W(y_t) for every tt, and HH a real function on the subsets of Γ\Gamma. With pp and dd as the roots, the means (7) and the root coefficient (8) satisfy (H‾p−H‾d)2≤κD𝒳(H)(\bar H_p - \bar H_d)^2 \le \kappa\, D_{\mathcal X}(H)(9)✦ and (H‾p−H‾d)2≤κ𝒯(H).(\bar H_p - \bar H_d)^2 \le \kappa\, \mathcal T(H).(10)✦

In the paper, the result reads: with the ground set VV partitioned into a fixed included set BB, a fixed excluded set CC, the singleton slots {p}\{p\} and {d}\{d\} and two-element slots E1,…,EmE_1, \dots, E_m, where |B|+1+m=n|B| + 1 + m = n, with multipliers Wh>0W_h > 0 on the slots hh and the exchange graph on 𝒳\mathcal X with conductances min⁡{Wh(S)f(S),Wh(S′)f(S′)}\min\{W_{h(S)} f(S), W_{h(S')} f(S')\}, h(S)h(S) being the slot attached to SS, one has (H‾p−H‾d)2≤(1/(spWp)+1/(sdWd)+(2/(spsd))∑tvt/Wt)D𝒳(H)(\bar H_p - \bar H_d)^2 \le \bigl(1/(s_p W_p) + 1/(s_d W_d) + (2/(s_p s_d)) \sum_t v_t / W_t\bigr) D_{\mathcal X}(H). The library states it with the missing multiplier mW(S)m_W(S) in the place of Wh(S)W_{h(S)}.

What Is Checked

Both inequalities are stated over the slot totals (1) along a list of pairs fresh for A∪{p,d}A \cup \{p, d\}, the slot signature property of ff with its face Hessians (2) and forms with one positive direction, the means (7), the root coefficient (8), and two energies: the slot graph energy (6) on the exchange graph of the slot vertex set (3), built from exchange adjacency (4) and the missing multiplier (5), and the transport energy.