OctoInformBeta

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

Lemma 4.3: For each T⊆E0T \subseteq E_0, in ℬ−(T)\mathcal{B}^-(T) and ℬ+(T)\mathcal{B}^+(T), trading one element of a member for one outside it gives a member

Both local rules at TT contain TT and are antichains.

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

Fix a subset TT of the ground set E0=L⊔RE_0 = L \sqcup R, two copies of a countable set DD cut into finite blocks. Attached to TT are two families of subsets of E0E_0, a lower rule ℬ−(T)\mathcal{B}^-(T) and an upper rule ℬ+(T)\mathcal{B}^+(T). Their members differ from TT by a set of density zero, and they are selected by a count of their elements against those of TT over the first nn blocks, as nn grows. The question is whether these families behave near TT like the set of bases of a matroid: whether TT is a member, and whether each is an antichain closed under trading one element of a member for one outside it.

Blocks and Densities

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 a natural number mm, the block DmD_m is the finite subset of DD made of the pairs with first entry mm: Dm={m}×{0,1}{0,1}m,|Dm|=wm=22m.D_m = \{m\} \times \{0,1\}^{\{0,1\}^m}, \qquad |D_m| = w_m = 2^{2^m}.(1)✦

The 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 holds the pairs with second entry false, the right copy RR those with second entry true.✦ For a natural number mm, the doubled block Wm=Dm×{L,R}W_m = D_m \times \{L, R\} is the finite subset of E0E_0 formed by both copies of DmD_m.✦

The density of a set XX in a finite set ss is |X∩s|/|s||X \cap s| / |s|, the share of the elements of ss that lie in XX.✦ The density δm(X)\delta_m(X) of a subset XX of E0E_0 at mm is its density in the doubled block WmW_m: δm(X)=|X∩Wm||Wm|.\delta_m(X) = \frac{|X \cap W_m|}{|W_m|}.(2)✦

A subset XX of E0E_0 is small when δm(X)\delta_m(X) tends to 00 as m→∞m \to \infty, and the small subsets of E0E_0 form the ideal 𝒥0={X⊆E0:δm(X)→0 as m→∞}.\mathcal{J}_0 = \{X \subseteq E_0 : \delta_m(X) \to 0 \text{ as } m \to \infty\}.(3)✦ Two subsets XX and TT of E0E_0 are equivalent modulo small sets when their symmetric difference X△TX \mathbin{\triangle} T is small.✦

The Probes

For n≥0n \ge 0, 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, and cn=|Vn|c_n = |V_n| is its number of elements.✦ For subsets TT and XX of E0E_0, the prefix count difference pn(X)p_n(X) and the density difference dm(X)d_m(X) of XX relative to TT are the real numbers pn(X)=|X∩Vn|−|T∩Vn|,dm(X)=δm(X)−δm(T).p_n(X) = |X \cap V_n| - |T \cap V_n|, \qquad d_m(X) = \delta_m(X) - \delta_m(T).(4)

The probe fn(X)f_n(X) of a subset XX of E0E_0 relative to TT is the number obtained by adding to pn(X)p_n(X) the product of cn=|Vn|c_n = |V_n| with the sum of the tail supremum and the 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).(5) The lower limit ℓT(X)\ell_T(X) of XX is the lower limit of its probes, taken in the extended reals: ℓT(X)=liminfn→∞fn(X)∈[−∞,+∞].\ell_T(X) = \liminf_{n \to \infty} f_n(X) \in [-\infty, +\infty].(6)✦

The Local Rules

For a subset TT of E0E_0, the local lower rule ℬ−(T)\mathcal{B}^-(T) is the family of subsets of E0E_0 that are equivalent to TT modulo small sets and whose lower limit lies in the half-open interval (−1,0](-1, 0]: ℬ−(T)={X⊆E0:X△T∈𝒥0 and −1<ℓT(X)≤0}.\mathcal{B}^-(T) = \{X \subseteq E_0 : X \mathbin{\triangle} T \in \mathcal{J}_0 \text{ and } -1 < \ell_T(X) \le 0\}.(7)✦

The local upper rule ℬ+(T)\mathcal{B}^+(T) at a subset TT of E0E_0 is the family of subsets of E0E_0 whose complement lies in the local lower rule at the complement of TT: ℬ+(T)={X⊆E0:E0\X∈ℬ−(E0\T)}.\mathcal{B}^+(T) = \{X \subseteq E_0 : E_0 \setminus X \in \mathcal{B}^-(E_0 \setminus T)\}.(8)✦

Given a Boolean σ\sigma, the local rule ℬσ(T)\mathcal{B}^\sigma(T) at TT is ℬ−(T)\mathcal{B}^-(T) when σ\sigma is false and ℬ+(T)\mathcal{B}^+(T) when σ\sigma is true.✦

The Claim

Theorem 1. Let TT be a subset of E0E_0. Then T∈ℬ−(T);T \in \mathcal{B}^-(T);(9)✦ the local lower rule is an antichain: if XX and YY are members of ℬ−(T)\mathcal{B}^-(T) with X⊆YX \subseteq Y, then X=Y;X = Y;(10)✦ and it is closed under swaps: if BB is a member of ℬ−(T)\mathcal{B}^-(T), e∈Be \in B and f∈E0\Bf \in E_0 \setminus B, then (B\{e})∪{f}∈ℬ−(T).(B \setminus \{e\}) \cup \{f\} \in \mathcal{B}^-(T).(11)✦ Likewise, for each Boolean σ\sigma, T∈ℬσ(T);T \in \mathcal{B}^\sigma(T);(12)✦ if XX and YY are members of ℬσ(T)\mathcal{B}^\sigma(T) with X⊆YX \subseteq Y, then X=Y;X = Y;(13)✦ and if BB is a member of ℬσ(T)\mathcal{B}^\sigma(T), e∈Be \in B and f∈E0\Bf \in E_0 \setminus B, then (B\{e})∪{f}∈ℬσ(T).(B \setminus \{e\}) \cup \{f\} \in \mathcal{B}^\sigma(T).(14)✦

In the paper, the result reads: each of ℬ−(T)\mathcal{B}^-(T) and ℬ+(T)\mathcal{B}^+(T) contains TT, is an antichain, and is preserved by finite modifications that add and delete equally many elements.

The library states the swap of a single element, (11) and (14); a finite modification that deletes kk elements of a member and adds kk elements outside it is kk such swaps in succession.

What Is Checked

The claims (9), (10), (11), (12), (13) and (14) are stated over an arbitrary subset TT of E0=D×{false,true}E_0 = D \times \{\mathrm{false}, \mathrm{true}\} and the local rules (7) and (8), built on the blocks (1), the densities (2), the ideal 𝒥0\mathcal{J}_0 of small sets (3), and the probes (4) and (5) with their lower limit (6).