OctoInformBeta

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

Lemma 6.2 [Difference image]: The triples of cyclic differences on the pairwise intersections of three subspaces are those whose restrictions to the common intersection sum to zero

Cyclic differences of symmetric forms obey exactly one constraint.

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

Take three subspaces A1,A2,A3A_1, A_2, A_3 of a vector space EE over a field KK, such as the finite field 𝔽q\mathbb{F}_q with qq elements, and give each AiA_i a symmetric bilinear form. Where two of the subspaces meet, their two forms can be compared, and the difference of the two is a symmetric bilinear form on the intersection. Going round the three pairs in cyclic order gives a triple of such differences. Which triples occur, and, over 𝔽q\mathbb{F}_q with the forms drawn independently and uniformly, how is the triple distributed?

The library answers the first question in two versions: for three forms on the whole of EE, restricted to the intersections, and for three independent forms, one on each AiA_i. For the second question it states a general fact on surjective linear maps between finite vector spaces.

Symmetric Forms and Restriction

Let XX be a vector space over KK. A symmetric bilinear form on XX is a bilinear map B:X×X→KB\colon X\times X\to K with B(x,y)=B(y,x)B(x,y)=B(y,x) for all x,y∈Xx,y\in X, and Sym⁡(X)\operatorname{Sym}(X) is the vector space of these forms.✦

For a linear map f:X→Yf\colon X\to Y between vector spaces over KK, the pullback f*f^{*} along ff is the linear map Sym⁡(Y)→Sym⁡(X)\operatorname{Sym}(Y)\to\operatorname{Sym}(X) given by (f*B)(x,x′)=B(f(x),f(x′))(x,x′∈X).(f^{*}B)(x,x') = B\bigl(f(x),f(x')\bigr) \qquad (x,x'\in X).(1)✦ For a subspace XX of YY, the restriction B|XB|_X of a form B∈Sym⁡(Y)B\in\operatorname{Sym}(Y) is its pullback along the inclusion of XX into YY.

The Three Maps

The pairwise intersections and the common intersection of A1,A2,A3A_1, A_2, A_3 are Q1=A2∩A3,Q2=A3∩A1,Q3=A1∩A2,V=A1∩A2∩A3.Q_1 = A_2\cap A_3,\qquad Q_2 = A_3\cap A_1,\qquad Q_3 = A_1\cap A_2,\qquad V = A_1\cap A_2\cap A_3 .(2) The space VV lies in each QiQ_i, and restriction to VV below is pullback along its inclusions into Q1Q_1, Q2Q_2 and Q3Q_3. The differences live in the vector space T=Sym⁡(Q1)×Sym⁡(Q2)×Sym⁡(Q3)T=\operatorname{Sym}(Q_1)\times\operatorname{Sym}(Q_2)\times\operatorname{Sym}(Q_3).✦

The cyclic difference map Δ\Delta of A1,A2,A3A_1, A_2, A_3 is the linear map Sym⁡(E)3→T\operatorname{Sym}(E)^{3}\to T given by Δ(F1,F2,F3)=((F2−F3)|Q1,(F3−F1)|Q2,(F1−F2)|Q3).\Delta(F_1,F_2,F_3) = \bigl((F_2-F_3)|_{Q_1},\ (F_3-F_1)|_{Q_2},\ (F_1-F_2)|_{Q_3}\bigr).(3) The cyclic difference map Δ′\Delta' of A1,A2,A3A_1, A_2, A_3 on independent forms is the linear map Sym⁡(A1)×Sym⁡(A2)×Sym⁡(A3)→T\operatorname{Sym}(A_1)\times\operatorname{Sym}(A_2)\times\operatorname{Sym}(A_3)\to T given by Δ′(G1,G2,G3)=(G2|Q1−G3|Q1,G3|Q2−G1|Q2,G1|Q3−G2|Q3).\Delta'(G_1,G_2,G_3) = \bigl(G_2|_{Q_1}-G_3|_{Q_1},\ G_3|_{Q_2}-G_1|_{Q_2},\ G_1|_{Q_3}-G_2|_{Q_3}\bigr).(4) The constraint map σ\sigma of A1,A2,A3A_1, A_2, A_3 is the linear map T→Sym⁡(V)T\to\operatorname{Sym}(V) that restricts the three forms of a triple to VV and adds them: σ(D1,D2,D3)=D1|V+D2|V+D3|V.\sigma(D_1,D_2,D_3) = D_1|_V + D_2|_V + D_3|_V .(5)

The Claim

Theorem 1. Let A1,A2,A3A_1, A_2, A_3 be subspaces of a vector space EE over a field KK, and let Δ\Delta, Δ′\Delta' and σ\sigma be the maps (3), (4) and (5). Then im⁡Δ=ker⁡σ,\operatorname{im}\Delta = \ker\sigma ,(6)✦ im⁡Δ′=ker⁡σ,\operatorname{im}\Delta' = \ker\sigma ,(7)✦ and σ(T)=Sym⁡(V).\sigma(T) = \operatorname{Sym}(V).(8)✦ Let further f:U→Wf\colon U\to W be a surjective linear map between finite vector spaces over KK. Then every subset SS of WW satisfies |{x∈U:f(x)∈S}||U|=|S||W|.\frac{\bigl|\{x\in U : f(x)\in S\}\bigr|}{|U|} = \frac{|S|}{|W|}.(9)✦

In the paper, the result reads: for arbitrary subspaces A1,A2,A3A_1, A_2, A_3, with Qi=Aj∩AkQ_i = A_j\cap A_k for (i,j,k)(i,j,k) a cyclic permutation of (1,2,3)(1,2,3) and V=A1∩A2∩A3V = A_1\cap A_2\cap A_3, the image of the cyclic difference map on symmetric forms is {(D1,D2,D3):D1|V+D2|V+D3|V=0}\{(D_1,D_2,D_3) : D_1|_V + D_2|_V + D_3|_V = 0\}, its codimension is b(dim⁡V)b(\dim V), where b(n)=n(n+1)/2b(n)=n(n+1)/2, and independent uniform FiF_i give the uniform law on the image. The library states the codimension through the surjectivity (8) of σ\sigma, and the uniform law through (9), for every surjective linear map between finite vector spaces.

What Is Checked

The claim is stated over the symmetric bilinear forms on a vector space EE over a field and on its subspaces, their restrictions (1), the cyclic difference maps Δ\Delta and Δ′\Delta' of (3) and (4) into the space TT of triples of forms on the pairwise intersections, the constraint map σ\sigma of (5) from TT to the forms on the common intersection VV, and, in (9), surjective linear maps between finite vector spaces.