OctoInformBeta

OpenAI preprint, September 2026 · §2. Constructing the signed walk · §2.2

§2.2 (displayed): predictor columns (predictor-columns): When the vectors have mass below 11 and at most BB and the steps use distinct fresh columns, the bound is BB

Symmetric steps keep fresh predictor columns within the mass bound.

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 signed walk, the sequence of signed prefix sums of a family of vectors, is constructed with a filter on real matrices. A run takes vectors b0,b1,…b_0, b_1, \dots in ℝι\mathbb{R}^\iota, for a finite set ι\iota of state coordinates, one at a time; the filter steps of the run, defined below, act in turn on a matrix with rows indexed by ι\iota, and each produces a row, its predictor row; the predictor rows of the run form the predictor matrix. The question is how much squared norm a single column of the predictor matrix can collect over a run of any length, measured against the squared norms of the vectors.

The library bounds it in two settings: for a run of symmetric steps, defined below, on any starting matrix, at the columns where that matrix vanishes, and for the predictor rows built from a finite family of vectors.

Filter Steps and Predictor Rows

For a finite set ι\iota, the mass of a vector b∈ℝιb \in \mathbb{R}^\iota is its squared Euclidean norm ∥b∥2=∑i∈ιbi2.\|b\|^2 = \sum_{i \in \iota} b_i^2.(1)✦

The normalizer of a vector b∈ℝιb \in \mathbb{R}^\iota is the real number η(b)\eta(b)✦, and its symmetric contraction is the square real matrix S(b)S(b) indexed by ι\iota, where η(b)=11+1−∥b∥2,S(b)=I−η(b)bb𝖳.\eta(b) = \frac{1}{1 + \sqrt{1 - \|b\|^2}}, \qquad S(b) = I - \eta(b)\, b b^{\mathsf T}.(2)✦

A filter step on real matrices with rows indexed by ι\iota and columns indexed by a set κ\kappa is a triple p=(C,b,j)p = (C, b, j) of a square real matrix CC indexed by ι\iota, a vector b∈ℝιb \in \mathbb{R}^\iota and a column j∈κj \in \kappa, acting on such a matrix RR by pR=CR+bej𝖳,pR = CR + b\, e_j^{\mathsf T},(3)✦ with eje_j the standard basis vector of ℝκ\mathbb{R}^\kappa at jj. The symmetric step of bb into the column jj is the filter step (S(b),b,j)(S(b), b, j).✦ A column of RR is fresh when it is zero, and a list of filter steps has fresh columns for RR when the column of each of its steps is fresh.✦

The predictor rows of a matrix RR along a list L=(p0,…,pℓ−1)L = (p_0, \dots, p_{\ell-1}) of filter steps, with pt=(Ct,bt,jt)p_t = (C_t, b_t, j_t), are the rows m0,…,mℓ−1m_0, \dots, m_{\ell-1} indexed by κ\kappa that the steps produce, one each, as they act in turn on RR: with R0=R,Rt+1=ptRt(0≤t<ℓ),R_0 = R, \qquad R_{t+1} = p_t R_t \quad (0 \le t < \ell),(4)✦ the row mt∈ℝκm_t \in \mathbb{R}^\kappa is the predictor row of the step ptp_t at RtR_t.

The Family Predictor

Let b0,…,bn−1b_0, \dots, b_{n-1} be vectors in ℝι\mathbb{R}^\iota, and index columns by ι⊔{0,…,n−1}\iota \sqcup \{0, \dots, n-1\}: the state coordinates, then one noise coordinate for each vector. The initial matrix (I0)(I \;\; 0) is the real matrix with rows indexed by ι\iota and columns by ι⊔{0,…,n−1}\iota \sqcup \{0, \dots, n-1\} that is the identity on the state columns and zero on the noise columns.✦ Write b=(b0,…,bn−1)b = (b_0, \dots, b_{n-1}). The family of symmetric steps of bb is the list of the symmetric steps of b0,…,bn−1b_0, \dots, b_{n-1}, in this order, the step of bib_i writing into the noise column ii.✦

The noise part of a row mm indexed by ι⊔{0,…,n−1}\iota \sqcup \{0, \dots, n-1\} is the row that vanishes on the state coordinates and agrees with mm on every noise coordinate.✦ The family predictor rows f0,…,fn−1f_0, \dots, f_{n-1} of bb are the noise parts of the predictor rows m0,…,mn−1m_0, \dots, m_{n-1} of (I0)(I \;\; 0) along the family of symmetric steps of bb.✦

The Claim

Theorem 1. Let RR be a real matrix with rows indexed by ι\iota and columns by κ\kappa, and let LL be a list of ℓ\ell symmetric steps (S(bt),bt,jt)(S(b_t), b_t, j_t), 0≤t<ℓ0 \le t < \ell, that has fresh columns for RR, with pairwise distinct columns j0,…,jℓ−1j_0, \dots, j_{\ell-1} and with ∥bt∥2≤1\|b_t\|^2 \le 1 for every tt. Let B≥0B \ge 0 satisfy ∥bt∥2≤B\|b_t\|^2 \le B for every tt. Then for every fresh column kk of RR, the predictor rows m0,…,mℓ−1m_0, \dots, m_{\ell-1} of RR along LL satisfy ∑t=0ℓ−1mt(k)2≤B.\sum_{t=0}^{\ell-1} m_t(k)^2 \le B.(5)✦

Theorem 2. Let b0,…,bn−1b_0, \dots, b_{n-1} be vectors in ℝι\mathbb{R}^\iota with ∥bi∥2<1\|b_i\|^2 < 1 for every ii, and let B≥0B \ge 0 satisfy ∥bi∥2≤B\|b_i\|^2 \le B for every ii. Then at every coordinate k∈ι⊔{0,…,n−1}k \in \iota \sqcup \{0, \dots, n-1\}, the family predictor rows f0,…,fn−1f_0, \dots, f_{n-1} of bb satisfy ∑i=0n−1fi(k)2≤B.\sum_{i=0}^{n-1} f_i(k)^2 \le B.(6)✦

What Is Checked

Both claims are stated over the mass (1), the normalizer and the symmetric contraction (2), the filter steps (3), fresh columns and the predictor rows (4), and the second also over the initial matrix (I0)(I \;\; 0), the family of symmetric steps, noise parts and the family predictor rows.