OctoInformBeta

OpenAI preprint, September 2026 · §3. Pruning two families of pairs

Four maps with NL = AB: NLNL passes through the conflict points ZZ, ABAB through HH; for all coefficients, rank⁡L+rank⁡N≤rank⁡NL+|Z|\operatorname{rank} L + \operatorname{rank} N \le \operatorname{rank} NL + |Z|

Coefficients supported on the arcs make NLNL equal to ABAB..

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

Take a relation →\to on a set XX and two finite families ℛ\mathcal{R} and 𝒞\mathcal{C} of pairs of points of XX. A pair (p,j)∈ℛ(p, j) \in \mathcal{R} and a pair (i,s)∈𝒞(i, s) \in \mathcal{C} conflict when p→ip \to i and s→js \to j. Besides its two pairs, a conflict has two more points in X×XX \times X: the point (i,j)(i, j), which takes its first coordinate from (i,s)(i, s) and its second from (p,j)(p, j), and the point (p,s)(p, s), which does the opposite.

There are two routes from (p,j)(p, j) to (i,s)(i, s): through (i,j)(i, j), changing first pp into ii and then jj into ss, or through (p,s)(p, s), making the same two changes in the other order. A step from pp to ii carries a real coefficient apia_{pi} and a step from jj to ss a real coefficient bsjb_{sj}, so that each route becomes a product of two linear maps, a map from ℝℛ\mathbb{R}^{\mathcal{R}} to ℝ𝒞\mathbb{R}^{\mathcal{C}}. The question is whether the two products agree, and how the rank of the product through the points (i,j)(i, j) compares with the ranks of its two factors.

Conflict Points and the Four Maps

The sets ZZ and HH of ℛ\mathcal{R} and 𝒞\mathcal{C} are the finite subsets of X×XX \times X formed by the points (i,j)(i, j) and the points (p,s)(p, s) of their conflicts: Z={(i,j):p→i and s→j for some (p,j)∈ℛ and (i,s)∈𝒞},Z = \{(i, j) : p \to i \text{ and } s \to j \text{ for some } (p, j) \in \mathcal{R} \text{ and } (i, s) \in \mathcal{C}\},(1)✦ H={(p,s):p→i and s→j for some (p,j)∈ℛ and (i,s)∈𝒞}.H = \{(p, s) : p \to i \text{ and } s \to j \text{ for some } (p, j) \in \mathcal{R} \text{ and } (i, s) \in \mathcal{C}\}.(2)✦

A family a=(axy)x,y∈Xa = (a_{xy})_{x, y \in X} of real coefficients is supported on →\to when it vanishes off the arcs, the pairs (x,y)(x, y) with x→yx \to y: axy=0for all x,y∈X with x↛y.a_{xy} = 0 \quad \text{for all } x, y \in X \text{ with } x \not\to y.(3)✦

For families aa and bb of real coefficients, the maps L:ℝℛ→ℝZL : \mathbb{R}^{\mathcal{R}} \to \mathbb{R}^{Z} and N:ℝZ→ℝ𝒞N : \mathbb{R}^{Z} \to \mathbb{R}^{\mathcal{C}}, the two steps through ZZ, and B:ℝℛ→ℝHB : \mathbb{R}^{\mathcal{R}} \to \mathbb{R}^{H} and A:ℝH→ℝ𝒞A : \mathbb{R}^{H} \to \mathbb{R}^{\mathcal{C}}, the two steps through HH, are the real matrices with rows indexed by the target and columns by the source whose entries are L(i,j),(p,j′)=δjj′api,N(i′,s),(i,j)=δi′ibsj,L_{(i,j),(p,j')} = \delta_{jj'}\, a_{pi}, \qquad N_{(i',s),(i,j)} = \delta_{i'i}\, b_{sj},(4) B(p′,s),(p,j)=δp′pbsj,A(i,s),(p,s′)=δss′api,B_{(p',s),(p,j)} = \delta_{p'p}\, b_{sj}, \qquad A_{(i,s),(p,s')} = \delta_{ss'}\, a_{pi},(5) where δ\delta is the Kronecker delta.

The Claim

Theorem 1. Let →\to be a relation on a set XX, let ℛ\mathcal{R} and 𝒞\mathcal{C} be finite families of pairs of points of XX, with sets ZZ and HH as in (1) and (2), and let aa and bb be families of real coefficients, with matrices LL, NN, BB and AA as in (4) and (5). If aa and bb are supported on →\to, then NL=AB.NL = AB.(6)✦ Whether or not they are, rank⁡L+rank⁡N≤rank⁡(NL)+|Z|.\operatorname{rank} L + \operatorname{rank} N \le \operatorname{rank} (NL) + |Z|.(7)✦

What Is Checked

The claim is stated over a relation →\to on a set XX, two finite families ℛ\mathcal{R} and 𝒞\mathcal{C} of pairs of its points, their sets ZZ and HH of conflict points, families aa and bb of real coefficients, the condition (3) that they be supported on →\to, and the four matrices LL, NN, BB and AA of (4) and (5).