OctoInformBeta

OpenAI preprint, September 2026 · §6. Local bounds from the planted law · §6

Lemma 6.1 [Subspace cost]: r′r'-dimensional subspace triples meeting in zero, by pair intersections and span: count and proportion at most 2n+P+3r′2^{n+P+3r'} times an explicit power of qq

Counting triples of subspaces by intersections and span.

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

Let KK be a finite field with qq elements and VV a vector space of dimension dd over KK. Three subspaces U0U_0, U1U_1, U2U_2 of VV of a common dimension r′r' can sit in many relative positions, and a few integers record which one: the dimension of U0∩U1∩U2U_0\cap U_1\cap U_2, the dimensions of the pairwise intersections, and the dimension nn of the span U0+U1+U2U_0+U_1+U_2.

Fix a position in which the three subspaces meet in zero, and take them independently and uniformly at random among the r′r'-dimensional subspaces of VV. The question is how unlikely that position is, as a power of qq; the exponent is the cost of the position.

Subspace Triples and Their Profile

For a natural number kk, the Grassmannian Gr⁡(k,V)\operatorname{Gr}(k,V) is the set of subspaces of VV of dimension kk.✦

For natural numbers r′r', p0p_0, p1p_1, p2p_2, put p=(p0,p1,p2)p=(p_0,p_1,p_2). The set 𝒯(r′;p)\mathcal{T}(r';p) of triples of profile (r′;p)(r';p) is the set of ordered triples (U0,U1,U2)(U_0,U_1,U_2) of subspaces in Gr⁡(r′,V)\operatorname{Gr}(r',V) such that U0∩U1∩U2=0,dim⁡(U0∩U1)=p0,dim⁡(U0∩U2)=p1,dim⁡(U1∩U2)=p2.U_0\cap U_1\cap U_2=0,\quad \dim(U_0\cap U_1)=p_0,\quad \dim(U_0\cap U_2)=p_1,\quad \dim(U_1\cap U_2)=p_2.(1)✦ For a further natural number nn, the set 𝒯n(r′;p)\mathcal{T}_n(r';p) of triples of span profile (r′;p;n)(r';p;n) is the set of triples (U0,U1,U2)(U_0,U_1,U_2) in 𝒯(r′;p)\mathcal{T}(r';p) whose span U0+U1+U2U_0+U_1+U_2 has dimension nn.✦

For natural numbers nn, r′r', p0p_0, p1p_1, p2p_2, the profile exponent E(n,r′;p)E(n,r';p) is the natural number given by (2), each difference being taken as 00 when it would be negative; when r′≤nr'\le n and pi+pj≤r′p_i+p_j\le r' for i≠ji\ne j, no difference is negative. E(n,r′;p)=∑i=02pi(n−pi)+(n−r′)∑0≤i<j≤2(r′−pi−pj).E(n,r';p)=\sum_{i=0}^{2}p_i(n-p_i)+(n-r')\sum_{0\le i<j\le 2}(r'-p_i-p_j).(2)✦

The Claim

Theorem 1. Let dd, nn, r′r', p0p_0, p1p_1, p2p_2 be natural numbers with n≤dn\le d, r′≤nr'\le n and pi+pj≤r′p_i+p_j\le r' for all i≠ji\ne j, and put P=p0+p1+p2P=p_0+p_1+p_2. If KK is a finite field with qq elements and VV is a vector space of dimension dd over KK, then the number of triples in 𝒯n(r′;p)\mathcal{T}_n(r';p) satisfies |𝒯n(r′;p)|≤2n+P+3r′qn(d−n)+E(n,r′;p),|\mathcal{T}_n(r';p)|\le 2^{\,n+P+3r'}\,q^{\,n(d-n)+E(n,r';p)},(3)✦ and their proportion among all ordered triples of r′r'-dimensional subspaces of VV satisfies |𝒯n(r′;p)||Gr⁡(r′,V)|3≤2n+P+3r′q−(d−2r′)P−(p02+p12+p22)−(d−n)(3r′−n−P).\frac{|\mathcal{T}_n(r';p)|}{|\operatorname{Gr}(r',V)|^{3}}\le 2^{\,n+P+3r'}\,q^{-(d-2r')P-(p_0^2+p_1^2+p_2^2)-(d-n)(3r'-n-P)}.(4)✦ The exponents of qq in the two bounds are related by n(d−n)+E(n,r′;p)−3r′(d−r′)=−(d−2r′)P−(p02+p12+p22)−(d−n)(3r′−n−P).n(d-n)+E(n,r';p)-3r'(d-r')=-(d-2r')P-(p_0^2+p_1^2+p_2^2)-(d-n)(3r'-n-P).(5)✦

In the paper, the result reads: for three independent uniformly random r′r'-dimensional subspaces of a dd-dimensional space, the event that they meet in zero, that their pairwise intersections have dimensions p0p_0, p1p_1, p2p_2 and that their span has codimension vv has probability O(q−δP−∑ipi2−vw)O(q^{-\delta P-\sum_i p_i^2-vw}), where δ\delta, vv and ww stand for d−2r′d-2r', d−nd-n and 3r′−n−P3r'-n-P.

What Is Checked

The claim is stated over the Grassmannian Gr⁡(r′,V)\operatorname{Gr}(r',V) of a vector space VV of dimension dd over a finite field with qq elements, the set 𝒯(r′;p)\mathcal{T}(r';p) of ordered triples in it meeting in zero with pairwise intersections of dimensions p0p_0, p1p_1, p2p_2, its subset 𝒯n(r′;p)\mathcal{T}_n(r';p) of triples spanning a subspace of dimension nn, and the profile exponent E(n,r′;p)E(n,r';p), for natural numbers with n≤dn\le d, r′≤nr'\le n and pi+pj≤r′p_i+p_j\le r' for i≠ji\ne j.