OctoInformBeta

OpenAI preprint, September 2026 · §5. Switching leaves and completing the proof

§5 (proof of Proposition 5.1): weighted deficit: Finite incidence families with total leaf weight one and summed row budgets at most 1/1281/128

A good leaf from weighted deficit bounds.

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

The weighted deficit lemma concerns detector losses distributed over a finite family of leaves. Let VV and SS be finite sets of vertices and leaves, respectively, and let R⊆V×SR\subseteq V\times S be an incidence relation. The incidence set B(v)B(v) of a vertex v∈Vv\in V is the set given by B(v)={s∈S:(v,s)∈R}B(v)=\{s\in S:(v,s)\in R\}.

Let av(s)a_v(s) be a real detector value for v∈Vv\in V and s∈Ss\in S, and let wsw_s and eve_v be real leaf weights and vertex budgets. The path deficit D(s)D(s) of a leaf s∈Ss\in S is the sum of its incident detector losses: D(s)=∑v∈Vs∈B(v)(1−av(s)).D(s)=\sum_{\substack{v\in V\\s\in B(v)}}\bigl(1-a_v(s)\bigr).(1)✦

A bad leaf s∈Ss\in S is a leaf with an incident detector value at most one half. The set ℬ\mathcal B of bad leaves is the subset of SS given by ℬ={s∈S:there is v∈V with s∈B(v) and av(s)≤12}.\mathcal B=\left\{s\in S: \text{there is }v\in V\text{ with }s\in B(v) \text{ and }a_v(s)\le\frac12\right\}.(2) The bad leaf mass MbadM_{\mathrm{bad}} is the total weight of the set ℬ\mathcal B in (2): Mbad=∑s∈ℬws.M_{\mathrm{bad}}=\sum_{s\in\mathcal B}w_s.(3)✦

The Claim

Theorem 1. Suppose that the leaf weights are nonnegative and sum to one, and that av(s)≤1a_v(s)\le1 whenever s∈B(v)s\in B(v). Suppose also that the row losses and total budget satisfy ∑s∈B(v)ws(1−av(s))≤5ev(v∈V),∑v∈Vev≤1128.\sum_{s\in B(v)}w_s\bigl(1-a_v(s)\bigr)\le5e_v \quad(v\in V), \qquad \sum_{v\in V}e_v\le\frac1{128}.(4) Then the path deficits and bad leaf mass defined in (1) and (3) satisfy ∑s∈SwsD(s)≤5128,Mbad≤564,there is s*∈S with ws*>0 and av(s*)>12for every v∈V with s*∈B(v).\begin{gathered} \sum_{s\in S}w_sD(s)\le\frac5{128}, \qquad M_{\mathrm{bad}}\le\frac5{64},\\ \text{there is }s_*\in S\text{ with }w_{s_*}>0 \text{ and }a_v(s_*)>\frac12 \quad\text{for every }v\in V\text{ with }s_*\in B(v). \end{gathered}(5)✦

In the paper, the result reads: the block estimate ∑s∈B(v)ws(1−av(s))≤5ev\sum_{s\in B(v)}w_s(1-a_v(s))\le5e_v gives total weighted path deficit at most 5/1285/128 and total weight at most 5/645/64 for leaves with any path detector at most 1/21/2, so, since the leaf weights sum to one, some leaf has every path detector strictly greater than 1/21/2.

What Is Checked

The claim (5) is stated over an arbitrary incidence relation between finite sets, with real detector values and normalized nonnegative leaf weights, under the incident detector bound and the budget estimates (4).