OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

§1 (setting): induced ordered copies, removal distance and the conjecture: Induced containment and arbitrary binary entry changes for a fixed pattern HH of order 6666

Ordered copies and the cost of removal.

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 ordered removal problem compares induced containment with the cost of eliminating a pattern by changing entries. Rows and columns have separate orders, and their selections need not coincide. Write In={0,…,n−1}I_n=\{0,\ldots,n-1\} for the index set of a matrix of order nn, with I0=⌀I_0=\varnothing.

The Definition

Definition 1. A binary matrix AA of order nn is a function belonging to the set ℬn\mathcal B_n in (1). ℬn={A:In×In→{0,1}}.\mathcal B_n=\{A:I_n\times I_n\longrightarrow\{0,1\}\}.(1)✦

An increasing index map f:Iℓ→Inf:I_\ell\longrightarrow I_n is a function that preserves strict order, as in (2). ℐ(ℓ,n)={f:Iℓ→In:i<j⇒f(i)<f(j)}.\mathcal I(\ell,n)= \{f:I_\ell\longrightarrow I_n: i<j\ \Longrightarrow\ f(i)<f(j)\}.(2)✦

For F∈ℬℓF\in\mathcal B_\ell and A∈ℬnA\in\mathcal B_n, an induced ordered copy (r,c)(r,c) of FF in AA is a pair of increasing row and column maps that matches every entry of FF, including zeros, as in (3). 𝒞F(A)={(r,c)∈ℐ(ℓ,n)×ℐ(ℓ,n):Ar(i),c(j)=Fij for all i,j∈Iℓ}.\mathcal C_F(A)= \{(r,c)\in\mathcal I(\ell,n)\times\mathcal I(\ell,n): A_{r(i),c(j)}=F_{ij}\text{ for all }i,j\in I_\ell\}.(3)✦

For F∈ℬℓF\in\mathcal B_\ell and A∈ℬnA\in\mathcal B_n, the ordered copy count NF(A)N_F(A) is the number of induced ordered copies of FF in AA, as in (4). NF(A)=|𝒞F(A)|.N_F(A)=|\mathcal C_F(A)|.(4)✦

A matrix A∈ℬnA\in\mathcal B_n is FF-free when it satisfies (5). A is F-free⇔NF(A)=0.A\text{ is }F\text{-free}\quad\Longleftrightarrow\quad N_F(A)=0.(5)✦

The Hamming distance D(A,B)D(A,B) between matrices A,B∈ℬnA,B\in\mathcal B_n is the number of entries at which they differ, as in (6). D(A,B)=|{(i,j)∈In×In:Aij≠Bij}|.D(A,B)=|\{(i,j)\in I_n\times I_n:A_{ij}\ne B_{ij}\}|.(6)✦

The binary digit η(a,b)\eta(a,b), for nonnegative integers a,ba,b, is the element of {0,1}\{0,1\} specified by (7). η(a,b)=⌊a2max⁡{5−b,0}⌋mod⁡2.\eta(a,b)= \left\lfloor\frac{a}{2^{\max\{5-b,0\}}}\right\rfloor\bmod 2.(7)✦

The anchor SS is the binary matrix of order s=64s=64 defined in (8), with u,v∈I64u,v\in I_{64}. Suv={η(u−32,v−58),32≤u and 59≤v,1,(u<32 or v<59) and u≠v,0,otherwise.S_{uv}=\begin{cases} \eta(u-32,v-58),&32\le u\text{ and }59\le v,\\ 1,&(u<32\text{ or }v<59)\text{ and }u\ne v,\\ 0,&\text{otherwise}. \end{cases}(8)✦

Let e0,e1e_0,e_1 be the coordinate unit vectors indexed by I64I_{64}, and let P=(1011)P=\bigl(\begin{smallmatrix}1&0\\1&1\end{smallmatrix}\bigr). The fixed forbidden pattern HH is the binary matrix of order k=66k=66 in (9), whose lower right body is PP. H=(Se0e1e0𝖳10e1𝖳11).H=\begin{pmatrix} S&e_0&e_1\\ e_0^{\mathsf T}&1&0\\ e_1^{\mathsf T}&1&1 \end{pmatrix}.(9)✦

The minimum removal edit count MH(A)M_H(A) of A∈ℬnA\in\mathcal B_n is the minimum Hamming distance to an HH-free binary matrix, as in (10). MH(A)=min⁡{D(A,B):B∈ℬn,NH(B)=0}.M_H(A)=\min\{D(A,B):B\in\mathcal B_n,\ N_H(B)=0\}.(10)✦

The removal distance dist⁡H(A)\operatorname{dist}_H(A) of A∈ℬnA\in\mathcal B_n is the normalized edit count in (11), with value 00 when n=0n=0. dist⁡H(A)=MH(A)n2.\operatorname{dist}_H(A)=\frac{M_H(A)}{n^2}.(11)✦

In the paper, the result reads: for a binary pattern FF of order ℓ\ell and a binary matrix AA of order nn, an ordered copy selects independently increasing rows r0<⋯<rℓ−1r_0<\cdots<r_{\ell-1} and columns c0<⋯<cℓ−1c_0<\cdots<c_{\ell-1} with Ari,cj=FijA_{r_i,c_j}=F_{ij} at every cell, including zeros, NF(A)N_F(A) counts these choices, FF-freeness means NF(A)=0N_F(A)=0, dist⁡F(A)\operatorname{dist}_F(A) is the minimum number of arbitrary binary entry changes producing an FF-free matrix divided by n2n^2, and the polynomial removal conjecture asks for constants cF,CF>0c_F,C_F>0 such that, for every integer n≥1n\ge1, every 0<ε<10<\varepsilon<1, and every such AA with dist⁡F(A)≥ε\operatorname{dist}_F(A)\ge\varepsilon, one has NF(A)≥cFεCFn2ℓN_F(A)\ge c_F\varepsilon^{C_F}n^{2\ell}.

What Is Checked

The definitions range over square binary matrices of every nonnegative integer size and use the fixed pattern HH of order 6666 for the removal distance.