OctoInformBeta

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

Lemma 4.5: For I⊆YI \subseteq Y in 𝒞(T)\mathcal{C}(T) with ℓT(I)≤−1\ell_T(I) \le -1 and ℓT(Y)>0\ell_T(Y) > 0, some BB of 𝒞(T)\mathcal{C}(T) between them has −1<ℓT(B)≤0-1 < \ell_T(B) \le 0

Interpolation inside a density-zero class by lower limits of probes.

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

In a matroid, an independent set II inside a spanning set YY extends to a base BB with I⊆B⊆YI \subseteq B \subseteq Y. Lemma 4.5 is an interpolation of the same shape for subsets of a doubled countable ground set E0E_0 that differ from a fixed set TT by a set of density zero. Such sets are compared with TT through ℓT(X)\ell_T(X), the lower limit of the counting probes of XX against TT.

The library states the lemma for the probes of TT and, beside it, an interpolation theorem for an arbitrary sequence of real functions on the subsets of ℕ\mathbb{N}. It also states the interpolation in three cases (a finite lower limit at II, a finite lower limit at YY, and infinite limits of opposite signs at the two ends) and a deletion stage, which removes finitely many elements from a set lying between two given sets.

Blocks, Densities and Classes

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 of DD is the set {m}×{0,1}{0,1}m\{m\}\times\{0,1\}^{\{0,1\}^m} of the pairs with first entry mm; it is finite and has wm=22mw_m=2^{2^m} elements.✦ The ground set E0=D×{false,true}E_0=D\times\{\mathrm{false},\mathrm{true}\} is the disjoint union L⊔RL\sqcup R of a left copy LL of DD, the pairs with second entry false, and a right copy RR, those with second entry true.✦ The doubled block Wm=Dm×{L,R}W_m=D_m\times\{L,R\} is the finite subset of E0E_0 lying over DmD_m on both sides.✦

Given a finite subset ss of a set α\alpha, the density of a subset XX of α\alpha in ss is |X∩s|/|s||X\cap s|/|s|, where X∩sX\cap s is the trace of XX on ss.✦ The block density 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|}.(1)✦ A subset XX of E0E_0 is small when δm(X)→0\delta_m(X)\to 0 as m→∞m\to\infty; the small sets form the ideal 𝒥0\mathcal{J}_0.✦ The class 𝒞(T)\mathcal{C}(T) of a subset TT of E0E_0 is the family of subsets XX of E0E_0 with X△T∈𝒥0X\mathbin{\triangle}T\in\mathcal{J}_0.✦

Probes and Lower Limits

Fix a subset TT of E0E_0. 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.✦ The prefix count difference of a subset XX of E0E_0 is pn(X)=|X∩Vn|−|T∩Vn|p_n(X)=|X\cap V_n|-|T\cap V_n|✦, and its density difference at mm is dm(X)=δm(X)−δm(T)d_m(X)=\delta_m(X)-\delta_m(T)✦. The probe fn(X)f_n(X) of XX relative to TT is the real number that adds to pn(X)p_n(X) the sum of the tail supremum and the tail infimum of the density differences from nn on, scaled by cnc_n: 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).(2)✦

For a sequence g=(gn)n≥0g=(g_n)_{n\ge 0} of real functions on the subsets of a set α\alpha, the lower limit of gg at a subset XX of α\alpha is the extended real number ℓg(X)=liminfn→∞gn(X)∈[−∞,+∞],\ell_g(X)=\liminf_{n\to\infty} g_n(X)\in[-\infty,+\infty],(3)✦ and ℓT(X)\ell_T(X) is the lower limit at XX of the probes (2). A subset XX of α\alpha lies in the window of gg when −1<ℓg(X)≤0-1<\ell_g(X)\le 0.✦

Conditions on an Interval

For subsets I⊆YI\subseteq Y of a set α\alpha, the interval [I,Y][I,Y] is the family of sets XX with I⊆X⊆YI\subseteq X\subseteq Y. A sequence gg of real functions on the subsets of α\alpha is monotone on [I,Y][I,Y] when gn(A)≤gn(B)g_n(A)\le g_n(B) for every nn and all A⊆BA\subseteq B in [I,Y][I,Y]. A sequence gg of real functions on the subsets of α\alpha rises by at most one per inserted element on [I,Y][I,Y] when gn(B)≤gn(A)+1g_n(B)\le g_n(A)+1 for every nn and all A⊆BA\subseteq B in [I,Y][I,Y] with B⊆A∪{e}B\subseteq A\cup\{e\} for some element ee. A sequence gg of real functions on the subsets of α\alpha has a lower limit that shifts exactly by finite additions on [I,Y][I,Y] when ℓg(B)=ℓg(A)+|B\A|for all A⊆B in [I,Y] with B\A finite.\ell_g(B)=\ell_g(A)+|B\setminus A|\quad\text{for all } A\subseteq B \text{ in } [I,Y] \text{ with } B\setminus A \text{ finite}.(4)✦ A sequence gg of real functions on the subsets of α\alpha is frequently negative on the finite extensions of II when every set ZZ of [I,Y][I,Y] with Z\IZ\setminus I finite has gn(Z)<0g_n(Z)<0 for infinitely many nn.

Two sets XX and ZZ of natural numbers agree below mm when every x<mx<m lies in XX exactly when it lies in ZZ.✦ A sequence gg of real functions on the subsets of ℕ\mathbb{N} is cylinder-continuous on [I,Y][I,Y] when for every jj and every ε>0\varepsilon>0 there is an mm such that |gn(X)−gn(Z)|<εfor all n<j and all X,Z∈[I,Y] that agree below m.|g_n(X)-g_n(Z)|<\varepsilon\quad\text{for all } n<j \text{ and all } X,Z\in[I,Y] \text{ that agree below } m.(5)✦

The Claim

Theorem 1. Let TT be a subset of E0E_0, and let I⊆YI\subseteq Y be sets of the class 𝒞(T)\mathcal{C}(T) with ℓT(I)≤−1\ell_T(I)\le -1 and ℓT(Y)>0\ell_T(Y)>0. Then some set BB of 𝒞(T)\mathcal{C}(T) satisfies I⊆B⊆Y,−1<ℓT(B)≤0.I\subseteq B\subseteq Y,\qquad -1<\ell_T(B)\le 0.(6)✦

In the paper, the result reads: there is a set BB in the family ℬ−(T)\mathcal{B}^-(T) of the paper with I⊆B⊆YI\subseteq B\subseteq Y.

Theorem 2. Let gg be a sequence of real functions on the subsets of ℕ\mathbb{N} and I⊆YI\subseteq Y sets of natural numbers. Suppose that gg is cylinder-continuous and monotone on [I,Y][I,Y], rises there by at most one per inserted element, and has a lower limit that shifts exactly by finite additions on [I,Y][I,Y]. If ℓg(I)≤−1\ell_g(I)\le -1 and ℓg(Y)>0\ell_g(Y)>0, then some set BB satisfies I⊆B⊆Y,−1<ℓg(B)≤0.I\subseteq B\subseteq Y,\qquad -1<\ell_g(B)\le 0.(7)✦

Theorem 3. Let gg be a sequence of real functions on the subsets of a set α\alpha and I⊆YI\subseteq Y subsets of α\alpha such that the lower limit of gg shifts exactly by finite additions on [I,Y][I,Y], with ℓg(I)≤−1\ell_g(I)\le -1 and ℓg(Y)>0\ell_g(Y)>0. If ℓg(I)>−∞,\ell_g(I)>-\infty,(8)✦ or if ℓg(I)=−∞andℓg(Y)<+∞,\ell_g(I)=-\infty\quad\text{and}\quad\ell_g(Y)<+\infty,(9)✦ then some set BB with I⊆B⊆YI\subseteq B\subseteq Y has −1<ℓg(B)≤0-1<\ell_g(B)\le 0.

Theorem 4. Let gg be a sequence of real functions on the subsets of ℕ\mathbb{N} and I⊆YI\subseteq Y sets of natural numbers. Suppose that gg is cylinder-continuous and monotone on [I,Y][I,Y], rises there by at most one per inserted element, and is frequently negative on the finite extensions of II, and that gn(Y)>0g_n(Y)>0 for all large nn. Then some set ZZ with I⊆Z⊆YI\subseteq Z\subseteq Y satisfies gn(Z)≤0 for infinitely many n,and, for every ε>0,gn(Z)≥−1−ε for all large n.\begin{aligned} &g_n(Z)\le 0 \text{ for infinitely many } n,\\ &\text{and, for every } \varepsilon>0,\ g_n(Z)\ge -1-\varepsilon \text{ for all large } n. \end{aligned}(10)✦

Theorem 5. Let gg be a sequence of real functions on the subsets of ℕ\mathbb{N} and I⊆X⊆YI\subseteq X\subseteq Y sets of natural numbers. Suppose that gg is cylinder-continuous on [I,Y][I,Y], rises there by at most one per inserted element, and is frequently negative on the finite extensions of II. Then for every j≥0j\ge 0 and every ε>0\varepsilon>0 some set ZZ with I⊆Z⊆XI\subseteq Z\subseteq X and X\ZX\setminus Z finite satisfies gn(Z)≤0 for some n≥j,|gn(X)−gn(Z)|<ε for all n<j,and either Z=X or gn(Z)≥−1 for all n≥j.\begin{aligned} &g_n(Z)\le 0 \text{ for some } n\ge j,\qquad |g_n(X)-g_n(Z)|<\varepsilon \text{ for all } n<j,\\ &\text{and either } Z=X \text{ or } g_n(Z)\ge -1 \text{ for all } n\ge j. \end{aligned}(11)✦

What Is Checked

The claim (6) is stated over the doubled blocks WmW_m of E0E_0, the ideal 𝒥0\mathcal{J}_0 of small sets with the class 𝒞(T)\mathcal{C}(T), and the probes (2) of TT with their lower limit ℓT\ell_T; the claims (7) to (11) are stated over an arbitrary sequence of real functions on the subsets of ℕ\mathbb{N}, or of any set in (8) and (9), through its lower limit (3), the exact shift (4), cylinder continuity (5), monotonicity and the bound on single insertions.