OctoInformBeta

OpenAI preprint, September 2026 · §7. The induction · §7

Lemma 7.1: For a nonzero, finitely supported, nonnegative sequence, some ii with Si>0S_i>0 has S0+…+Si+K≤4(K+1)SiS_0+\dots+S_{i+K}\le 4(K+1)S_i; applied with K=200K=200 to the layers’ piece masses

Some positive term controls the prefix sum reaching past it.

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 induction of Section 7 cuts a graph into pieces scale by scale. It starts from a piece PP of order nn and works at layer jj at the scale nθjn^{\theta^j} for a fixed θ<1\theta<1: every piece reached at that layer is split into cycles and boxes, and every box into pieces of large cut expansion and a sparse remainder. Let SjS_j be the total order of the pieces of large cut expansion made at layer jj.✦ The item asks for a layer ii with Si>0S_i>0 whose pieces carry a fixed share of all pieces made in layers 00 through i+200i+200.

The library states the result for every integer K≥0K\ge 0, with i+Ki+K in place of i+200i+200, and, with K=200K=200, for the layers of the induction.

Pieces and Stage Splits

Fix a finite ground set VV. A graph HH on VV is supported on a finite set A⊆VA\subseteq V when every edge of HH has both ends in AA.✦ A piece QQ on VV is a finite set A⊆VA\subseteq V, the vertices assigned to QQ, together with a graph on VV supported on AA; the set AA may hold isolated vertices, and its size |Q||Q| is the order of QQ.✦ For a graph HH on VV, e(H)e(H) is the number of edges of HH, and for a piece QQ on VV, e(Q)e(Q) is the number of edges of the graph of QQ.

A list LL of graphs on VV is an edge partition of a graph GG on VV when every edge of GG is an edge of exactly one member of LL and no member of LL has an edge outside GG, a graph occurring twice in LL counted twice.✦ A cycle graph on VV is a graph on VV whose edges are exactly those of one cycle in it.✦ A graph GG on VV has cut expansion at least hh on a set A⊆VA\subseteq V when |∂GU|≥hmin⁡{|U|,|A\U|}for every U⊆A,|\partial_G U|\ge h\min\{|U|,\,|A\setminus U|\}\quad\text{for every } U\subseteq A,(1)✦ where |∂GU||\partial_G U| is the number of edges of GG with one end in UU and the other in A\UA\setminus U.

A stage split of a piece PP consists of a list of cycle graphs, its cycles; a list of pieces, its boxes; and for every box BB a list of pieces, the pieces of BB, and a graph HBH_B supported on the vertex set of BB, the remainder of BB.✦ The vertex sets of the boxes lie inside that of PP, are nonempty when that of PP is, and together cover it. The pieces of a box BB have pairwise disjoint vertex sets inside that of BB, and their graphs together with HBH_B form an edge partition of the graph of BB. The cycles and the graphs of the boxes form an edge partition of the graph of PP.

A stage split of PP is bounded at scale DD when it has at most |P|/(2D0.01)|P|/(2D^{0.01}) cycles, the orders of its boxes sum to at most (1+2/log⁡D)|P|(1+2/\log D)|P|, with log\log the base 22 logarithm, and every box BB and every piece RR of BB satisfy |B|≤D1.02,2e(HB)|B|≤D0.95,D0.90≤|R|≤D1.02,|B|\le D^{1.02},\qquad \frac{2e(H_B)}{|B|}\le D^{0.95},\qquad D^{0.90}\le |R|\le D^{1.02},(2)✦ the graph of RR having cut expansion at least D0.90D^{0.90} on the vertex set of RR.

A split system ss on VV assigns to every level j≥0j\ge 0 and every piece QQ on VV a stage split s(j,Q)s(j,Q) of QQ.✦

Layers and Piece Mass

For a piece PP of order nn, the induction scale at layer jj is Dj=nθjD_j=n^{\theta^j}✦, with the scale exponent θ=0.95\theta=0.95✦. Given a split system ss, the frontier ℱj\mathcal F_j at layer jj is a list of pieces: ℱ0\mathcal F_0 is PP alone, and ℱj+1\mathcal F_{j+1} is obtained from ℱj\mathcal F_j by splitting every piece QQ of ℱj\mathcal F_j with the stage split s(j,Q)s(j,Q).✦

Layered splitting data for PP at threshold D*D^* consist of a split system ss and a number m≥1m\ge 1 of layers with Dj≥D*D_j\ge D^* for j<mj<m and Dm<D*D_m<D^*, such that for j<mj<m the stage split s(j,Q)s(j,Q) of every piece QQ of ℱj\mathcal F_j is bounded at scale DjD_j, and for j≤mj\le m every piece QQ of ℱj\mathcal F_j has 2e(Q)/|Q|≤Dj2e(Q)/|Q|\le D_j.✦

The vertex mass of a list of pieces is the sum of their orders, a piece counted as often as it occurs.✦ The pieces of level jj of a list LL of pieces are the pieces of all boxes of the stage splits s(j,Q)s(j,Q), QQ in LL.✦ For a piece PP with a split system ss, the piece mass SjS_j of PP at layer jj is the vertex mass of the pieces of level jj of ℱj\mathcal F_j.✦ The pieces from the first kk layers, those of level jj of ℱj\mathcal F_j for j<kj<k, have vertex mass S0+…+Sk−1S_0+\dots+S_{k-1}. The constant 804804 in (4) is 4(K+1)4(K+1) at K=200K=200.✦

The Claim

Theorem 1. Let K≥0K\ge 0 be an integer and (Sj)j≥0(S_j)_{j\ge 0} a sequence of nonnegative reals that vanishes from some index on and is not identically zero. Then some index ii has Si>0S_i>0 and S0+S1+…+Si+K≤4(K+1)Si.S_0+S_1+\dots+S_{i+K}\le 4(K+1)\,S_i.(3)✦ Let PP be a piece with layered splitting data of mm layers at a threshold D*D^*, and let SjS_j be its piece mass at layer jj. If S0+…+Sm−1>0S_0+\dots+S_{m-1}>0, then some layer i<mi<m has Si>0S_i>0 and S0+S1+…+Sk−1≤804Sifor every k≤min⁡{m,i+201}.S_0+S_1+\dots+S_{k-1}\le 804\,S_i\quad\text{for every } k\le\min\{m,\,i+201\}.(4)✦

In the paper, the result reads: if (Sj)j≥0(S_j)_{j\ge 0} is a nonnegative, finitely supported sequence that is not identically zero, there is an index ii with Si>0S_i>0 and ∑j=0i+KSj≤P0Si\sum_{j=0}^{i+K}S_j\le P_0S_i, where K=200K=200 and P0=4(K+1)=804P_0=4(K+1)=804.

What Is Checked

The claim (3) is stated over nonnegative real sequences that vanish from some index on, and (4) over layered splitting data for a piece: a split system whose stage splits are bounded at the induction scales nθjn^{\theta^j}, the frontiers it reaches, and the piece masses of its layers.