OctoInformBeta

OpenAI preprint, September 2026 · §2. A fixed pattern and its tree matrices

§2 (setting): the anchor S, the body P and the fixed pattern H: A five-bit rectangle and two unit signatures specify the matrix HH

An anchor and its fixed forbidden pattern.

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 fixed forbidden pattern for ordered matrix removal has an anchor and a 2×22\times2 body. For a nonnegative integer nn, a binary matrix BB of size nn is an n×nn\times n matrix with entries in {0,1}\{0,1\}, whose rows and columns are indexed by 0,…,n−10,\ldots,n-1.✦ Write s=64s=64 for the anchor size and k=66k=66 for the pattern size.

The Definition

Definition 1. For nonnegative integers a,ba,b, the binary digit ηb(a)∈{0,1}\eta_b(a)\in\{0,1\} is defined by (1): ηb(a)=⌊a2max⁡{5−b,0}⌋mod⁡2.\eta_b(a)= \left\lfloor\frac{a}{2^{\max\{5-b,0\}}}\right\rfloor\bmod 2.(1)✦

The anchor S∈{0,1}s×sS\in\{0,1\}^{s\times s} is the binary matrix given by (2), for 0≤u,v<s0\le u,v<s: S(u,v)={ηv−58(u−32),32≤u≤63,59≤v≤63,𝟏{u≠v},otherwise.S(u,v)= \begin{cases} \eta_{v-58}(u-32),&32\le u\le63,\quad59\le v\le63,\\ \mathbf{1}_{\{u\ne v\}},&\text{otherwise}. \end{cases}(2)✦

For a binary matrix B:R×C→{0,1}B:R\times C\to\{0,1\}, rows r1,r2∈Rr_1,r_2\in R and columns c1,c2∈Cc_1,c_2\in C, the body relation Body⁡B(r1,r2;c1,c2)\operatorname{Body}_B(r_1,r_2;c_1,c_2) is the four-entry condition (3), which also defines the body matrix PP: Body⁡B(r1,r2;c1,c2)⇔(B(r1,c1)B(r1,c2)B(r2,c1)B(r2,c2))=P:=(1011).\operatorname{Body}_B(r_1,r_2;c_1,c_2) \quad\Longleftrightarrow\quad \begin{pmatrix} B(r_1,c_1)&B(r_1,c_2)\\ B(r_2,c_1)&B(r_2,c_2) \end{pmatrix} =P:= \begin{pmatrix} 1&0\\ 1&1 \end{pmatrix}.(3)✦

Let e1,e2∈{0,1}se_1,e_2\in\{0,1\}^{s} be the unit vectors supported at coordinates 00 and 11, respectively. The fixed forbidden pattern H∈{0,1}k×kH\in\{0,1\}^{k\times k} is the block matrix in (4): H=(Se1e2e1𝖳e2𝖳P).H= \begin{pmatrix} S&\begin{matrix}e_1&e_2\end{matrix}\\ \begin{matrix}e_1^{\mathsf T}\\e_2^{\mathsf T}\end{matrix}&P \end{pmatrix}.(4)✦

In the paper, the result reads: set s=64s=64 and ηb(a)=⌊a/25−b⌋mod⁡2\eta_b(a)=\lfloor a/2^{5-b}\rfloor\bmod2 for 0≤a<320\le a<32 and 1≤b≤51\le b\le5; the anchor satisfies S(u,v)=ηv−59(u−33)S(u,v)=\eta_{v-59}(u-33) when 33≤u≤6433\le u\le64 and 60≤v≤6460\le v\le64, and S(u,v)=𝟏{u≠v}S(u,v)=\mathbf{1}_{\{u\ne v\}} otherwise; with e1,e2e_1,e_2 the first two unit vectors, HH is the block matrix with top row blocks S,e1,e2S,e_1,e_2, bottom-left rows e1𝖳,e2𝖳e_1^{\mathsf T},e_2^{\mathsf T}, and lower-right body P=(1011)P=\left(\begin{smallmatrix}1&0\\1&1\end{smallmatrix}\right), and has size 6666.

What Is Checked

The anchor and fixed pattern are binary matrices on their ordered index sets, and the body relation is defined for binary matrices on arbitrary row and column sets.