OctoInformBeta

OpenAI preprint, September 2026 · §6. One shear and exact coverage

Lemma 6.1: Source patterns have at most 2q2^q vertices in dimension qq, and branching trees admit the same intersection bound

A simultaneous shear for finite closed pattern families.

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

A shear moves labeled vertices by linear combinations of a fixed collection of columns. The intersections of the corresponding translated holes depend on all of these columns, while the same columns must serve every pattern in the family.

Let EE be a real vector space, let TT be an additive commutative group with a translation-invariant probability measure μ\mu, and let π:E→T\pi:E\to T be a surjective additive map. Let α\alpha be a set of labels; for each a∈αa\in\alpha, let the labeled hole Ua⊆TU_a\subseteq T be measurable and let ηa∈(0,∞]\eta_a\in(0,\infty] satisfy μ(Ua)≤ηa\mu(U_a)\le\eta_a.

The translate of A⊆TA\subseteq T by t∈Tt\in T is the set A+tA+t in (1).✦ For a nonnegative integer DD, columns Z=(Z1,…,ZD)Z=(Z_1,\ldots,Z_D) in EE, and an integer qq with 0≤q≤D0\le q\le D, the initial restriction Z≤qZ_{\le q} and the linear column combination bZ(x)b_Z(x) are defined by (1), with the latter taken for x∈ℝDx\in\mathbb R^D. A+t={y∈T:y−t∈A},Z≤q=(Z1,…,Zq),bZ(x)=∑j=1DxjZj.A+t=\{y\in T:y-t\in A\},\qquad Z_{\le q}=(Z_1,\ldots,Z_q),\qquad b_Z(x)=\sum_{j=1}^{D}x_jZ_j.(1)

Source Patterns and Branching Trees

A labeled source pattern in ℝq\mathbb R^q is a nonempty finite set s⊆ℝq×αs\subseteq\mathbb R^q\times\alpha with unique vertex labels and binary suffix fibers.✦ A finite labeled set s⊆ℝq×αs\subseteq\mathbb R^q\times\alpha has unique vertex labels if (x,a),(x,b)∈s(x,a),(x,b)\in s entails a=ba=b.✦ A finite labeled set s⊆ℝq×αs\subseteq\mathbb R^q\times\alpha has binary suffix fibers if, for each coordinate index j∈{1,…,q}j\in\{1,\ldots,q\}, fixing all coordinates later than jj restricts the possible values of coordinate jj to two positions separated by one, as in (2). ∀j∈{1,…,q}∀y∈ℝq∃v∈ℝ,{xj:(x,a)∈s,xk=yk for all k>j}⊆{v,v+1}.\forall j\in\{1,\ldots,q\}\ \forall y\in\mathbb R^q\ \exists v\in\mathbb R, \quad \{x_j:(x,a)\in s,\ x_k=y_k\text{ for all }k>j\} \subseteq\{v,v+1\}.(2)✦

For v∈ℝv\in\mathbb R, the coordinate slice svs_v of a finite labeled set s⊆ℝq+1×αs\subseteq\mathbb R^{q+1}\times\alpha is the subset of ℝq×α\mathbb R^q\times\alpha obtained by retaining the vertices with last coordinate vv and deleting that coordinate, as defined in (3). A family 𝒮=(𝒮q)\mathcal S=(\mathcal S_q) of finite collections of source patterns is closed under coordinate slices below DD if, for q<Dq<D and s∈𝒮q+1s\in\mathcal S_{q+1}, every nonempty slice svs_v belongs to 𝒮q\mathcal S_q.✦ sv={(x,a)∈ℝq×α:((x,v),a)∈s}.s_v=\{(x,a)\in\mathbb R^q\times\alpha:((x,v),a)\in s\}.(3)✦

For a source pattern s⊆ℝq×αs\subseteq\mathbb R^q\times\alpha and columns Z∈EqZ\in E^q, the failure set Hs(Z)⊆TH_s(Z)\subseteq T is the intersection of the translated labeled holes in (4). Hs(Z)=⋂(x,a)∈s(Ua+π(bZ(x))),Z∈Eq.H_s(Z)=\bigcap_{(x,a)\in s}\bigl(U_a+\pi(b_Z(x))\bigr), \qquad Z\in E^q.(4)

A branching pattern aa of depth zero is a leaf labeled by a∈αa\in\alpha. A branching pattern of depth q+1q+1 is either a single branch Mv(p)M_v(p) or a pair of branches Bv(p,r)B_v(p,r), where v∈ℝv\in\mathbb R and p,rp,r have depth qq.✦ For a branching pattern pp, its first and second branches p−,p+p^-,p^+, its leaf count n(p)n(p), and its leaf weight w(p)w(p) are given in (5); leaves are counted with multiplicity. patternfirst branchsecond branchnwa1ηaMv(p)ppn(p)w(p)Bv(p,r)prn(p)+n(r)w(p)w(r)\begin{array}{c|cc|c|c} \text{pattern}&\text{first branch}&\text{second branch}&n&w\\ \hline a&&&1&\eta_a\\ M_v(p)&p&p&n(p)&w(p)\\ B_v(p,r)&p&r&n(p)+n(r)&w(p)w(r) \end{array}(5)

For a branching pattern pp of depth qq and columns Z∈EqZ\in E^q, the failure set Fp(Z)⊆TF_p(Z)\subseteq T is the set defined recursively by (6), where ZZ has q+1q+1 columns in the last two lines. Fa(())=Ua,FMv(p)(Z)=Fp(Z≤q)+π(vZq+1),FBv(p,r)(Z)=(Fp(Z≤q)+π(vZq+1))∩(Fr(Z≤q)+π((v+1)Zq+1)).\begin{aligned} F_a(())&=U_a,\\ F_{M_v(p)}(Z)&=F_p(Z_{\le q})+\pi(vZ_{q+1}),\\ F_{B_v(p,r)}(Z)&= \bigl(F_p(Z_{\le q})+\pi(vZ_{q+1})\bigr) \cap\bigl(F_r(Z_{\le q})+\pi((v+1)Z_{q+1})\bigr). \end{aligned}(6)✦

A family 𝒫=(𝒫q)\mathcal P=(\mathcal P_q) of finite collections of branching patterns is closed under branches below DD if both branches of every p∈𝒫q+1p\in\mathcal P_{q+1} belong to 𝒫q\mathcal P_q whenever q<Dq<D.✦ For either kind of family ℱ\mathcal F, its total number of patterns through dimension DD is Q(ℱ)Q(\mathcal F) in (7). Q(ℱ)=∑q=0D|ℱq|.Q(\mathcal F)=\sum_{q=0}^{D}|\mathcal F_q|.(7)

The Claim

Theorem 1. Let DD be a nonnegative integer and let L*>1L_*>1. For a family 𝒮\mathcal S of source patterns closed under coordinate slices below DD, suppose Q(𝒮)<L*Q(\mathcal S)<L_*. There are columns Z1,…,ZD∈EZ_1,\ldots,Z_D\in E such that every s∈𝒮qs\in\mathcal S_q, for 0≤q≤D0\le q\le D, satisfies (8). μ(Hs(Z≤q))≤L*|s|−1∏(x,a)∈sηa.\mu\bigl(H_s(Z_{\le q})\bigr) \le L_*^{|s|-1}\prod_{(x,a)\in s}\eta_a.(8)✦ For a family 𝒫\mathcal P of branching patterns closed under branches below DD, suppose Q(𝒫)<L*Q(\mathcal P)<L_*. There are columns Z1,…,ZD∈EZ_1,\ldots,Z_D\in E such that every p∈𝒫qp\in\mathcal P_q, for 0≤q≤D0\le q\le D, satisfies (9). μ(Fp(Z≤q))≤L*n(p)−1w(p).\mu\bigl(F_p(Z_{\le q})\bigr)\le L_*^{n(p)-1}w(p).(9)✦ Every source pattern s⊆ℝq×αs\subseteq\mathbb R^q\times\alpha satisfies (10). |s|≤2q.|s|\le 2^q.(10)✦

In the paper, the result reads: for a lattice Λh\Lambda_h in ℝm\mathbb R^m, the torus T=ℝm/ΛhT=\mathbb R^m/\Lambda_h with normalized Haar measure μ\mu and quotient projection πΛh\pi_{\Lambda_h}, measurable Ua⊆TU_a\subseteq T satisfying μ(Ua)≤ηa\mu(U_a)\le\eta_a with ηa>0\eta_a>0, finite families 𝒮q\mathcal S_q of labeled patterns in ℝq\mathbb R^q that are binary by suffixes and closed under last-coordinate slicing for 0≤q≤D0\le q\le D, and L*>max⁡{1,Q(𝒮)}L_*>\max\{1,Q(\mathcal S)\}, there are vectors Z1,…,ZD∈ℝmZ_1,\ldots,Z_D\in\mathbb R^m such that every s∈𝒮qs\in\mathcal S_q satisfies (11). μ(⋂(x,a)∈s(Ua+πΛh(∑j=1qxjZj)))≤L*|s|−1∏(x,a)∈sηa.\mu\!\left(\bigcap_{(x,a)\in s} \left(U_a+\pi_{\Lambda_h}\!\left(\sum_{j=1}^{q}x_jZ_j\right)\right)\right) \le L_*^{|s|-1}\prod_{(x,a)\in s}\eta_a.(11)

What Is Checked

The statements concern real vector spaces with surjective additive maps to commutative groups carrying invariant probability measure, measurable labeled holes with positive bounds, and finite families closed under coordinate slices or pattern branches.