By OpenAISourceGitHub

Manuscripts from openai/math

Fork
Clone
git clone https://openversions.com/git/index/openai-math.git
Cite
Version link
https://openversions.com/index/openai-math/commit/dfd8c46870b48511e697cbb43a3c8c91d375fa2f
Version identifier (commit hash)
dfd8c46870b48511e697cbb43a3c8c91d375fa2f

Fork to create your own copy with credit to the source. Clone to get a Git copy on your computer.

All papers

Claims

Findings

Polynomial removal fails for ordered binary matrices

There is a fixed 66×6666 \times 66 binary matrix HH for which ordered matrix removal has no polynomial bound, disproving the polynomial ordered binary matrix-removal conjecture; specifically, for every integer h≥1h \ge 1, with nh=(386h+2)2hn_h = (386h+2)2^h and ϵh=(386h+2)−2\epsilon_h = (386h+2)^{-2}, there is a binary nh×nhn_h \times n_h matrix AhA_h such that distH(Ah)≥ϵh\mathrm{dist}_H(A_h) \ge \epsilon_h and NH(Ah)/nh132≤ϵh2−hN_H(A_h)/n_h^{132} \le \epsilon_h 2^{-h}.

For any fixed ρ∈(0,1]\rho \in (0, 1], a canonical tester that independently chooses uniformly random qq-element row and column sets R,C⊆[nh]R, C \subseteq [n_h] and rejects only when Ah[R,C]A_h[R, C] contains an ordered copy of HH has Pr⁡(reject on Ah)≤ϵh2−hq2\Pr(\text{reject on } A_h) \le \epsilon_h 2^{-h} q^2 (and 00 for q<66q < 66), and therefore requires q≥ρϵh−1/22h/2=exp⁡(Ω(ϵh−1/2))q \ge \sqrt{\rho} \epsilon_h^{-1/2} 2^{h/2} = \exp(\Omega(\epsilon_h^{-1/2})) along the sequence ϵh\epsilon_h as h→∞h \to \infty.

For h≥1h \ge 1, m=2hm = 2^h, and n=dhmn = d_h m with dh=386h+2d_h = 386h + 2, every HH-free binary n×nn \times n matrix differs from AhA_h in at least m2m^2 entries, so AhA_h is dh−2d_h^{-2}-far from being HH-free.

For every integer h≥1h \ge 1, every ordered copy of HH in AhA_h maps the pattern entry (s+1,s+1)(s+1, s+1) into Lh=⋃p=0m−1Rh+(p)×Ch+(p)\mathcal{L}_h = \bigcup_{p=0}^{m-1} R_h^+(p) \times C_h^+(p), where ∣Lh∣=m|\mathcal{L}_h| = m, and consequently NH(Ah)≤mn2k−2N_H(A_h) \le m n^{2k-2} and NH(Ah)/n2k≤2−h/dh2N_H(A_h)/n^{2k} \le 2^{-h}/d_h^2.

Every ordered copy of SS in AhA_h uses the row and column anchor groups of a single mode tt (one position from each of that mode's 6464 groups in order), and in every ordered copy of HH in AhA_h, the two body rows belong respectively to R1(t),R2(t)\mathsf{R}_1(t), \mathsf{R}_2(t) and the two body columns belong respectively to C1(t),C2(t)\mathsf{C}_1(t), \mathsf{C}_2(t).

Methods

Explicit construction of a 66x66 binary pattern H (comprising a 64x64 anchor S encoding 5-bit words and a 2x2 body P) and a family of binary-tree-indexed host matrices A_h of order n_h = (386h+2)2^h with 6h modes and a shared leaf level.

Source excerpts

“We specify a binary pattern of size 66 and an ordered binary matrix Ah for each integer h ≥ 1. The pattern consists of a 64 × 64 block and two additional rows and columns. The matrices Ah place copies of that block before positions indexed by a binary tree.” · Show in paper

Cellwise probabilistic sampling of a root-to-leaf tree path together with one representative per anchor and dummy class to lower-bound the edit distance to H-freeness.

Source excerpts

“We first prove the distance bound in Section 3. Fix an arbitrary edited matrix and sample a tree path together with anchor positions and auxiliary “dummy” positions, whose entries against the tree positions are all 1 in the original host. Each axis is partitioned into classes of equal size m = 2h.” · Show in paper

Shattering-based anchor localization and mode-by-mode order/threshold analysis to upper-bound the total number of ordered copies N_H(A_h) by confining them to the leaf diagonal L_h.

Source excerpts

“The anchor matrix S has two complementary features. Its lower-right corner contains every binary word of length five. We will show that non-anchor rows cannot realize all these words on five non-anchor columns. This will force more than 32 positions on at least one axis of any copy to be anchors.” · Show in paper