OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1.1

§1.1 (proof of Theorem 1.2): positive-forward, negative-reverse order: Positive terms in order, then negative ones reversed: unsigned prefix sums within BB and signed ones within DD keep new prefix sums within (B+D)/2(B+D)/2

Reordering a zero-sum sequence by sign averages its prefix 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

Steinitz-type bounds ask for an order of vectors with zero sum in which every prefix sum is short, and vector balancing gives signs under which every signed prefix sum is short. The lemma turns a signing into an order, for vectors in any real normed space EE attached to the terms of a sequence. Take a set AA, a map v:A→Ev \colon A \to E, a sign function ε:A→{−1,1}\varepsilon \colon A \to \{-1, 1\} and a finite sequence (a0,…,aN−1)(a_0, \dots, a_{N-1}) of elements of AA. For k≤Nk \le N, the unsigned prefix sum SkS_k and the signed prefix sum TkT_k of the sequence (a0,…,aN−1)(a_0, \dots, a_{N-1}) are Sk=∑i<kv(ai),Tk=∑i<kε(ai)v(ai).S_k = \sum_{i<k} v(a_i), \qquad T_k = \sum_{i<k} \varepsilon(a_i)\, v(a_i).(1)

The Signed Reordering

The signed reordering of a finite sequence (a0,…,aN−1)(a_0, \dots, a_{N-1}) of elements of a set AA, with respect to a sign function ε\varepsilon on AA, is the sequence of the same terms that lists first those of sign 11, in increasing order of index, and then those of sign −1-1, in decreasing order of index.✦ With i0<…<iP−1i_0 < \dots < i_{P-1} the indices ii with ε(ai)=1\varepsilon(a_i) = 1 and j0<…<jQ−1j_0 < \dots < j_{Q-1} those with ε(ai)=−1\varepsilon(a_i) = -1, it is (b0,…,bN−1)=(ai0,…,aiP−1,ajQ−1,…,aj0).(b_0, \dots, b_{N-1}) = (a_{i_0}, \dots, a_{i_{P-1}}, a_{j_{Q-1}}, \dots, a_{j_0}).(2)✦

The Claim

Theorem 1. Let EE be a real normed space, AA a set, v:A→Ev \colon A \to E a map, ε:A→{−1,1}\varepsilon \colon A \to \{-1, 1\} a sign function, (a0,…,aN−1)(a_0, \dots, a_{N-1}) a finite sequence of elements of AA, and BB, DD real numbers. Suppose that the total SNS_N is zero and that the prefix sums (1) satisfy ∥Sk∥≤B\|S_k\| \le B and ∥Tk∥≤D\|T_k\| \le D for every k≤Nk \le N. Then the signed reordering (b0,…,bN−1)(b_0, \dots, b_{N-1}) of (2) satisfies, for every k≤Nk \le N, ∥∑i<kv(bi)∥≤B+D2.\Bigl\| \sum_{i<k} v(b_i) \Bigr\| \le \frac{B + D}{2}.(3)✦

In the paper, the result reads: put the indices of positive sign in order and then the indices of negative sign in reverse order; when the total is zero, every prefix sum of the new order has norm at most (β+Cd)/2(\beta + C\sqrt{d})/2, with β\beta and CdC\sqrt{d} in the roles of BB and DD.

What Is Checked

The claim (3) is stated over the signed reordering (2) of a finite sequence of elements of a set, each carrying a vector of a real normed space and a sign, under a zero total and the bounds BB on the unsigned and DD on the signed prefix sums (1).