OctoInformBeta

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

Lemma 4.1: Adding a point raises fnf_n by at most one, adding kk points raises it by kk eventually, and complementing XX and TT negates it

Normalized probes vanish in a density-zero class, and the probes are monotone.

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

Subsets of a countable ground set E0E_0, the disjoint union of a left and a right copy of a countable set DD, are measured by their density in the finite blocks into which E0E_0 is cut, and a set of density zero counts as negligible. Fix a subset TT of E0E_0. Real-valued probes compare a subset XX of E0E_0 with TT, on single blocks and on initial runs of blocks. The lemma is about their limits when XX differs from TT by a negligible set, and about how the probes respond to enlarging XX and to complementing XX and TT together.

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 {m}Γ—{0,1}{0,1}m\{m\} \times \{0,1\}^{\{0,1\}^m} of DD; it has wm=22mw_m = 2^{2^m} elements.✦ The ground set is E0=DΓ—{L,R}=LβŠ”RE_0 = D \times \{L, R\} = L \sqcup R, and for each mm the doubled block Wm=DmΓ—{L,R}W_m = D_m \times \{L, R\} is a finite subset of E0E_0.✦

For a finite subset ss of a set AA and a subset XX of AA, the density of XX in ss is the ratio |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.✦ A subset XX of E0E_0 is small when its block density tends to 00, limmβ†’βˆž|X∩Wm||Wm|=0,\lim_{m \to \infty} \frac{|X \cap W_m|}{|W_m|} = 0,(1)✦ and the small sets form the ideal π’₯0\mathcal{J}_0. For a subset TT of E0E_0, the class π’ž(T)\mathcal{C}(T) of TT is the set 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)✦

The Probes

For nβ‰₯0n \ge 0, the prefix VnV_n is the finite subset of E0E_0 made of the first nn doubled blocks, and cnc_n is its number of elements: Vn=W0βˆͺβ‹―βˆͺWnβˆ’1,cn=|Vn|.V_n = W_0 \cup \cdots \cup W_{n-1}, \qquad c_n = |V_n|.(3)✦

Relative to a subset TT of E0E_0, the density difference dm(X)d_m(X) and the count difference pn(X)p_n(X) of a subset XX of E0E_0 are the real numbers dm(X)=|X∩Wm||Wm|βˆ’|T∩Wm||Wm|,d_m(X) = \frac{|X \cap W_m|}{|W_m|} - \frac{|T \cap W_m|}{|W_m|},(4)✦ pn(X)=|X∩Vn|βˆ’|T∩Vn|.p_n(X) = |X \cap V_n| - |T \cap V_n|.(5)✦

The probe fn(X)f_n(X) of XX relative to TT is the real number built from pn(X)p_n(X) and from 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).(6)✦ Where the set TT must be shown, these are written dmT(X)d_m^T(X), pnT(X)p_n^T(X) and fnT(X)f_n^T(X).

The Claim

Theorem 1. Let TT and XX be subsets of E0E_0, with complements Tc=E0\TT^c = E_0 \setminus T and Xc=E0\XX^c = E_0 \setminus X.

  1. If XX lies in π’ž(T)\mathcal{C}(T), then limmβ†’βˆždm(X)=0\lim_{m \to \infty} d_m(X) = 0(7)✦ and limnβ†’βˆžpn(X)cn=0.\lim_{n \to \infty} \frac{p_n(X)}{c_n} = 0.(8)✦

  2. If XβŠ†YβŠ†E0X \subseteq Y \subseteq E_0, then for every nβ‰₯0n \ge 0 fn(X)≀fn(Y).f_n(X) \le f_n(Y).(9)✦

  3. For every element ee of E0E_0 and every nβ‰₯0n \ge 0, fn(Xβˆͺ{e})≀fn(X)+1.f_n(X \cup \{e\}) \le f_n(X) + 1.(10)✦

  4. If XβŠ†YβŠ†E0X \subseteq Y \subseteq E_0 and Y\XY \setminus X is finite, then for all sufficiently large nn fn(Y)=fn(X)+|Y\X|.f_n(Y) = f_n(X) + |Y \setminus X|.(11)✦

  5. For every nβ‰₯0n \ge 0, fnTc(Xc)=βˆ’fnT(X).f_n^{T^c}(X^c) = -f_n^{T}(X).(12)✦

In the paper, the result reads: for XX and YY in π’ž(T)\mathcal{C}(T), (1) dm(X)β†’0d_m(X) \to 0 and pn(X)/cnβ†’0p_n(X)/c_n \to 0; (2) XβŠ†YX \subseteq Y implies fn(Y)βˆ’fn(X)β‰₯|(Y\X)∩Vn|f_n(Y) - f_n(X) \ge |(Y \setminus X) \cap V_n|; (3) adding or deleting one element changes every probe fnf_n by at most one, and a finite modification of XX into YY with net change bb gives fn(Y)=fn(X)+bf_n(Y) = f_n(X) + b for all large nn; (4) fnTc(Xc)=βˆ’fnT(X)f_n^{T^c}(X^c) = -f_n^T(X) and ℬ+(Tc)={Bc:Bβˆˆβ„¬βˆ’(T)}\mathcal{B}^+(T^c) = \{B^c : B \in \mathcal{B}^-(T)\}, for the paper’s families β„¬βˆ’(T)\mathcal{B}^-(T) and ℬ+(T)\mathcal{B}^+(T).

What Is Checked

The claim is stated over the doubled blocks WmW_m of E0E_0 and their prefixes VnV_n, the block density, the class π’ž(T)\mathcal{C}(T) modulo the ideal π’₯0\mathcal{J}_0 of small sets, and the probes dmd_m, pnp_n and fnf_n relative to TT.