OctoInformBeta

OpenAI preprint, September 2026 · §4. Bases within a density-zero class

Lemma 4.4: For X∈𝒞(T)X\in\mathcal{C}(T), a 𝒥0\mathcal{J}_0-positive pool outside or inside XX holds a small PP with fn(X∪P)→+∞f_n(X\cup P)\to+\infty or fn(X\P)→−∞f_n(X\setminus P)\to-\infty

Density-zero changes can send the probes to ±∞\pm\infty..

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 ground sets of the counterexample to the infinite matroid packing/covering conjecture are built from Boolean functions. The set DD is the countable set of pairs (m,f)(m,f) of a natural number mm and a Boolean function f:{0,1}m→{0,1}f\colon\{0,1\}^m\to\{0,1\}.✦ For m≥0m\ge0, the block Dm={m}×{0,1}{0,1}mD_m=\{m\}\times\{0,1\}^{\{0,1\}^m} is the finite subset of DD made of the pairs with first entry mm; it has wm=22mw_m=2^{2^m} elements.✦ The small ground set E0=D×{false,true}E_0=D\times\{\mathrm{false},\mathrm{true}\} is the disjoint union L⊔RL\sqcup R of two copies of DD, the left copy LL given by the second entry false and the right copy RR by true.✦ The doubled block Wm=Dm×{L,R}W_m=D_m\times\{L,R\} is the finite subset of E0E_0 formed by the two copies of DmD_m.✦

Lemma 4.4 belongs to the study of bases within a single class of subsets of E0E_0 modulo the sets of density zero in the doubled blocks. Relative to a fixed set TT, each subset XX of E0E_0 is measured by a sequence of real numbers, its probes. Adding a set of density zero to XX or removing one from it does not leave the class of XX, and the question is how far such a change can move the probes when the set is taken from a given pool GG that is not of density zero.

Densities and Probes

For a subset XX of E0E_0 and m≥0m\ge0, the block density μm(X)\mu_m(X) is the density of XX in the doubled block WmW_m, the size of the trace X∩WmX\cap W_m over the size of the block: μm(X)=|X∩Wm||Wm|.\mu_m(X)=\frac{|X\cap W_m|}{|W_m|}.(1)✦

A subset XX of E0E_0 is small when μm(X)→0\mu_m(X)\to0 as m→∞m\to\infty.✦ The small sets form the ideal 𝒥0\mathcal{J}_0, and a subset of E0E_0 outside 𝒥0\mathcal{J}_0 is 𝒥0\mathcal{J}_0-positive. The class 𝒞(T)\mathcal{C}(T) of a subset TT of E0E_0 is the family of subsets of E0E_0 whose symmetric difference with TT is small: 𝒞(T)={X⊆E0:X△T∈𝒥0}.\mathcal{C}(T)=\{X\subseteq E_0 : X\mathbin{\triangle}T\in\mathcal{J}_0\}.(2)✦

Fix a subset TT of E0E_0. For n≥0n\ge0, the prefix Vn=W0∪…∪Wn−1V_n=W_0\cup\dots\cup W_{n-1} is the finite subset of E0E_0 formed by the first nn doubled blocks, with cn=|Vn|c_n=|V_n| elements.✦ The density difference of a subset XX of E0E_0 at mm is the real number dm(X)=μm(X)−μm(T)d_m(X)=\mu_m(X)-\mu_m(T)✦, and its prefix count difference at nn is the number pn(X)=|X∩Vn|−|T∩Vn|p_n(X)=|X\cap V_n|-|T\cap V_n|✦. The probe fn(X)f_n(X) of XX at nn is the real number formed from pn(X)p_n(X) and the tail supremum and tail infimum of the density differences from nn on: fn(X)=pn(X)+cn(supm≥ndm(X)+infm≥ndm(X)).f_n(X)=p_n(X)+c_n\Bigl(\sup_{m\ge n}d_m(X)+\inf_{m\ge n}d_m(X)\Bigr).(3)✦ The tail error εn(X)\varepsilon_n(X) of XX at nn is the tail supremum of the absolute density differences: εn(X)=supm≥n|dm(X)|.\varepsilon_n(X)=\sup_{m\ge n}|d_m(X)|.(4)✦

The Claim

Theorem 1 (Lemma 4.4). Let TT be a subset of E0E_0, and take the probes relative to TT.

  1. Let X∈𝒞(T)X\in\mathcal{C}(T), and let GG be a 𝒥0\mathcal{J}_0-positive subset of E0\XE_0\setminus X. Then GG contains a small set PP with fn(X∪P)→+∞(n→∞).f_n(X\cup P)\to+\infty\quad(n\to\infty).(5)✦

  2. Let X∈𝒞(T)X\in\mathcal{C}(T), and let GG be a 𝒥0\mathcal{J}_0-positive subset of XX. Then GG contains a small set PP with fn(X\P)→−∞(n→∞).f_n(X\setminus P)\to-\infty\quad(n\to\infty).(6)✦

  3. Let GG be a subset of E0E_0 and δ>0\delta>0 a real number with μm(G)≥δ\mu_m(G)\ge\delta for infinitely many mm, let (bj)j≥0(b_j)_{j\ge0} be a sequence of real numbers with 0<bj≤δ0<b_j\le\delta for every jj and bj→0b_j\to0, and let (Nj)j≥0(N_j)_{j\ge0} be a sequence of natural numbers. Then GG contains a small set PP such that for every jj there is an m≥Njm\ge N_j with μm(P)≥bj.\mu_m(P)\ge b_j.(7)✦

  4. Let XX and PP be disjoint subsets of E0E_0, and let n≤mn\le m be natural numbers. Then pn(X)+cn(μm(P)−2εn(X))≤fn(X∪P).p_n(X)+c_n\bigl(\mu_m(P)-2\varepsilon_n(X)\bigr)\le f_n(X\cup P).(8)✦

What Is Checked

The four statements (5), (6), (7) and (8) are stated over the set DD with its blocks DmD_m, the small ground set E0E_0 with its doubled blocks WmW_m and prefixes VnV_n, the block densities μm\mu_m, the ideal 𝒥0\mathcal{J}_0 of small sets and the classes 𝒞(T)\mathcal{C}(T), and, relative to TT, the density differences dmd_m, the prefix count differences pnp_n, the probes fnf_n built from tail suprema and infima, and the tail errors εn\varepsilon_n.