OctoInformBeta

Polynomial removal fails for ordered binary matrices

For a binary k×kk\times k pattern HH and a binary n×nn\times n matrix AA, an induced ordered copy of HH is a choice of kk increasing row indices and kk increasing column indices whose entries agree with HH, including both zeros and ones. The number of these copies is denoted by NH(A)N_H(A). A matrix AA is HH-free if NH(A)=0N_H(A)=0. The normalized removal distance dist⁡H(A)\operatorname{dist}_H(A) is the minimum fraction of entries that must be changed, allowing changes in either direction, to make AA HH-free. The polynomial ordered binary matrix-removal conjecture asserts that each fixed HH admits constants cH,CH>0c_H,C_H>0 such that, whenever n≥1n\ge1, 0<ϵ<10<\epsilon<1 and dist⁡H(A)≥ϵ\operatorname{dist}_H(A)\ge\epsilon, one has NH(A)≥cHϵCHn2kN_H(A)\ge c_H\epsilon^{C_H}n^{2k}.

Alon and Ben-Eliezer formulated the polynomial removal question for finite families of binary matrices. The singleton conjecture appears as Conjecture 4.5 in the first arXiv version of Gishboliner and Shapira’s survey.

For integers h≥1h\ge1, write nh=(386h+2)2hn_h=(386h+2)2^h. Write ϵh=(386h+2)−2\epsilon_h=(386h+2)^{-2}. The preprint constructs a fixed binary 66×6666\times66 pattern HH and binary nh×nhn_h\times n_h matrices AhA_h satisfying dist⁡H(Ah)≥ϵh\operatorname{dist}_H(A_h)\ge\epsilon_h and NH(Ah)/nh132≤ϵh2−hN_H(A_h)/n_h^{132}\le\epsilon_h2^{-h} for every h≥1h\ge1. For this HH, no positive constants give a polynomial removal bound. The preprint also derives an exponential lower bound in ϵh−1/2\epsilon_h^{-1/2} for the number of rows and columns sampled independently and uniformly by testers that reject only when the sampled submatrix contains HH, at any fixed positive rejection probability along this sequence; the Lean library does not contain this sampling consequence.

Lean has checked every result of the Lean library MatrixRemoval, so the Lean library is the reference for the statements on these pages. Each result is stated as in the Lean library and linked to its Lean declaration. Where the preprint states a result differently, the preprint’s statement is given beside the Lean library’s statement. The preprint guides only the order and names of the results.