OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Theorem 1.1: An explicit binary pattern of order 6666 has a counterexample sequence with exponentially small relative copy counts

A fixed pattern defeats polynomial 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

Ordered matrix removal compares the density of a fixed induced pattern with the proportion of entries that must change to remove it. A binary matrix of order nn is a matrix A∈{0,1}[n]×[n]A\in\{0,1\}^{[n]\times[n]}, where [n]={0,…,n−1}[n]=\{0,\ldots,n-1\}.✦ Rows and columns have their own increasing selections.

For nonnegative integers ℓ\ell and nn, an increasing index map ff from [ℓ][\ell] to [n][n] is a function between these ordered sets that is strictly increasing.✦ For a binary pattern FF of order ℓ\ell and a binary matrix AA of order nn, an ordered copy (r,c)(r,c) of FF in AA is a pair of increasing index maps that matches every entry, including zeros.✦ The set of ordered copies 𝒞F(A)\mathcal C_F(A) and its cardinality NF(A)N_F(A) are defined by (1). 𝒞F(A)={(r,c):r,c:[ℓ]→[n] strictly increasing,Ar(i),c(j)=Fij for all i,j∈[ℓ]},NF(A)=|𝒞F(A)|.\mathcal C_F(A)= \bigl\{(r,c): r,c:[\ell]\to[n]\text{ strictly increasing},\quad A_{r(i),c(j)}=F_{ij}\text{ for all }i,j\in[\ell]\bigr\}, \qquad N_F(A)=|\mathcal C_F(A)|.(1) A binary matrix AA is FF-free when its ordered copy count NF(A)N_F(A) is zero.✦

The Fixed Pattern and Removal Distance

For nonnegative integers a,ba,b, the binary digit η(a,b)\eta(a,b) is the element of {0,1}\{0,1\} defined in (2). η(a,b)=⌊a2max⁡{5−b,0}⌋mod⁡2.\eta(a,b)= \left\lfloor\frac{a}{2^{\max\{5-b,0\}}}\right\rfloor\bmod 2.(2)✦ The anchor SS is the binary matrix of order s=64s=64 defined by (3), with row and column indices starting at zero. Suv={η(u−32,v−58),32≤u≤63,59≤v≤63,𝟏{u≠v},otherwise.S_{uv}= \begin{cases} \eta(u-32,v-58),&32\le u\le63,\quad59\le v\le63,\\ \mathbf 1_{\{u\ne v\}},&\text{otherwise}. \end{cases}(3)✦

The fixed forbidden pattern HH has order k=66k=66. Its anchor occupies the first 6464 rows and columns, and its body is the binary matrix PP of order two in (4). The matrix EE in that equation has 6464 rows and two columns; its column indices are 0,10,1. The first body index is 6464, corresponding to index 6565 when indices start at one. Euj=𝟏{u=j},P=(1011),H=(SEE𝖳P).E_{uj}=\mathbf 1_{\{u=j\}},\qquad P=\begin{pmatrix}1&0\\1&1\end{pmatrix},\qquad H=\begin{pmatrix}S&E\\E^{\mathsf T}&P\end{pmatrix}.(4)✦

The Hamming distance Ham⁡(A,B)\operatorname{Ham}(A,B) between two binary matrices of the same order is the number of entries in which they differ.✦ For a binary matrix AA of order nn, the minimum HH removal edit count eH(A)e_H(A) is the least Hamming distance from AA to an HH-free binary matrix of order nn.✦ The normalized removal distance dist⁡H(A)\operatorname{dist}_H(A) of a binary matrix AA of positive order nn is its minimum HH removal edit count divided by the square of its order, as in (5). eH(A)=minB∈{0,1}[n]×[n]NH(B)=0Ham⁡(A,B),dist⁡H(A)=eH(A)n2(n≥1).e_H(A)=\min_{\substack{B\in\{0,1\}^{[n]\times[n]}\\N_H(B)=0}} \operatorname{Ham}(A,B),\qquad \operatorname{dist}_H(A)=\frac{e_H(A)}{n^2}\quad(n\ge1).(5)

For each integer h≥1h\ge1, use the parameters in (6). m=2h,dh=386h+2,nh=dhm,εh=dh−2.m=2^h,\qquad d_h=386h+2,\qquad n_h=d_hm,\qquad \varepsilon_h=d_h^{-2}.(6)

The Claim

Theorem 1. For every integer h≥1h\ge1, there is a binary matrix AhA_h of order nhn_h such that dist⁡H(Ah)≥εh,NH(Ah)nh132≤εh2−h.\operatorname{dist}_H(A_h)\ge\varepsilon_h, \qquad \frac{N_H(A_h)}{n_h^{132}}\le\varepsilon_h2^{-h}.(7)✦ For every pair of positive real constants c,Cc,C, there are an integer n≥1n\ge1, a real number 0<ε<10<\varepsilon<1, and a binary matrix AA of order nn such that dist⁡H(A)≥ε,NH(A)n132<cεC.\operatorname{dist}_H(A)\ge\varepsilon, \qquad \frac{N_H(A)}{n^{132}}<c\varepsilon^C.(8)✦

In the paper, the result reads: there is a fixed binary 66×6666\times66 matrix HH such that, for every integer h≥1h\ge1, putting nh=(386h+2)2hn_h=(386h+2)2^h and εh=(386h+2)−2\varepsilon_h=(386h+2)^{-2}, there is a binary nh×nhn_h\times n_h matrix AhA_h with dist⁡H(Ah)≥εh\operatorname{dist}_H(A_h)\ge\varepsilon_h and NH(Ah)/nh132≤εh2−hN_H(A_h)/n_h^{132}\le\varepsilon_h2^{-h}, and consequently no positive constants c,Cc,C give a polynomial removal bound for this fixed HH.

What Is Checked

The claims (7) and (8) are stated over finite binary matrices with their row and column orders, the explicit pattern (4), ordered copy counts (1), and the minimum edit distance (5) to an HH-free matrix.