OctoInformBeta

OpenAI preprint, September 2026 · §4. Transverse configurations and determinant signs · §4

Lemma 4.1 [Subspaces and symmetric matrices]: The Gaussian binomial, and estimates for the determinant, rank and sign of a uniform symmetric matrix and for the radical of a symmetric form

Counting subspaces and symmetric matrices over a finite field.

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

Lemma 4.1 of the counterexample to Sidorenko’s conjecture is a set of counting estimates over a finite field KK with qq elements, in the section on transverse configurations and determinant signs. How many kk-dimensional subspaces does an nn-dimensional vector space over KK have, and how far is that number from qk(n−k)q^{k(n-k)}? For a symmetric n×nn\times n matrix MM over KK chosen uniformly at random, how likely is MM to be singular, and for odd qq, how evenly is the quadratic character of det⁡M\det M split between 11 and −1-1? What share of the symmetric matrices has a given rank and a given sign, and how rare is a symmetric bilinear form with a large radical?

The library answers each question with an identity or a bound explicit in qq, and the one on rank and sign also with a limit as qq runs through the odd primes.

Subspaces of a Finite Vector Space

Let VV be a vector space over KK of finite dimension nn. The Grassmannian Grk(V)\mathrm{Gr}_k(V), for a natural number kk, is the set of subspaces of VV of dimension kk.✦

For natural numbers DD and kk, the Grassmann correction factor γD,k\gamma_{D,k} is the function of a real variable xx given by γD,k(x)=∏i=0k−11−x−(D−i)1−x−(k−i).\gamma_{D,k}(x)=\prod_{i=0}^{k-1}\frac{1-x^{-(D-i)}}{1-x^{-(k-i)}}.(1)✦

Symmetric Matrices and Their Signs

The space SDS_D of symmetric D×DD\times D matrices over KK consists of the D×DD\times D matrices MM over KK with MT=MM^{T}=M.✦

Probabilities on SnS_n are taken under the uniform law. The uniform mean of a real function ff on a finite set AA is its average |A|−1∑a∈Af(a)|A|^{-1}\sum_{a\in A}f(a), and the probability of an event for MM uniform on SnS_n is the uniform mean of its indicator over SnS_n.✦

The quadratic character χ\chi of KK is the function on KK equal to 00 at 00, to 11 at a nonzero square and to −1-1 at every other element. For MM uniform on SnS_n, the singular probability is the probability Pr⁡(det⁡M=0)\Pr(\det M=0) that MM is singular✦, and the sign probability Pn(ξ)P_n(\xi) of an integer ξ\xi is the probability that χ(det⁡M)=ξ\chi(\det M)=\xi: Pn(ξ)=1|Sn|∑M∈Sn𝟏[χ(det⁡M)=ξ].P_n(\xi)=\frac{1}{|S_n|}\sum_{M\in S_n}\mathbf{1}\bigl[\chi(\det M)=\xi\bigr].(2)✦

A symmetric bilinear form BB on VV is a bilinear form with B(x,y)=B(y,x)B(x,y)=B(y,x) for all x,y∈Vx,y\in V, and 𝒮(V)\mathcal{S}(V) denotes the set of them.✦ The radical of BB is the subspace rad⁡B={x∈V:B(x,y)=0 for all y∈V}\operatorname{rad}B=\{x\in V: B(x,y)=0\text{ for all }y\in V\}, and the radical quotient form of BB is the nondegenerate form B‾\bar B that BB induces on V/rad⁡BV/\operatorname{rad}B, given by B‾(x+rad⁡B,y+rad⁡B)=B(x,y)\bar B(x+\operatorname{rad}B,\,y+\operatorname{rad}B)=B(x,y).✦ The sign of BB is sgn⁡B=χ(det⁡G),\operatorname{sgn}B=\chi(\det G),(3)✦ where GG is the Gram matrix of B‾\bar B in a basis of V/rad⁡BV/\operatorname{rad}B; for B=0B=0 the matrix GG is empty, its determinant is 11, and sgn⁡B=1\operatorname{sgn}B=1. The sign sgn⁡Z\operatorname{sgn}Z of a matrix Z∈SDZ\in S_D is the sign of the bilinear form (x,y)↦xTZy(x,y)\mapsto x^{T}Zy on KDK^{D}.✦

Write b(m)=m(m+1)/2b(m)=m(m+1)/2 for the mmth triangular number. The signed rank layer LD(r,ξ)L_D(r,\xi), for a natural number rr and an integer ξ\xi, is the set of matrices in SDS_D of rank rr and sign ξ\xi✦, and its layer mass is the share of SDS_D it takes up: μD(r,ξ)=|LD(r,ξ)||SD|.\mu_D(r,\xi)=\frac{|L_D(r,\xi)|}{|S_D|}.(4)✦

For an odd prime qq, a prime other than 22, μD(q)(r,ξ)\mu^{(q)}_D(r,\xi) is the layer mass over the field 𝔽q\mathbb{F}_q of integers modulo qq, and a limit as q→∞q\to\infty through the odd primes is the limit along the odd primes in increasing order.✦

The Claim

Theorem 1. Let KK be a finite field with qq elements and VV a vector space over KK of finite dimension nn, and let 0≤k≤n0\le k\le n. The number of kk-dimensional subspaces of VV is the Gaussian binomial coefficient |Grk(V)|=∏a=0k−1qn−qaqk−qa,|\mathrm{Gr}_k(V)|=\prod_{a=0}^{k-1}\frac{q^{n}-q^{a}}{q^{k}-q^{a}},(5)✦ it satisfies |Grk(V)|≤2kqk(n−k)|\mathrm{Gr}_k(V)|\le 2^{k}\,q^{k(n-k)}(6)✦ and qk(n−k)≤|Grk(V)|,q^{k(n-k)}\le|\mathrm{Gr}_k(V)|,(7)✦ and it factors as |Grk(V)|=qk(n−k)γn,k(q).|\mathrm{Gr}_k(V)|=q^{k(n-k)}\,\gamma_{n,k}(q).(8)✦ For natural numbers k≤Dk\le D, the Grassmann correction factor satisfies limx→∞γD,k(x)=1.\lim_{x\to\infty}\gamma_{D,k}(x)=1.(9)✦ For MM uniform on SnS_n, the singular probability satisfies Pr⁡(det⁡M=0)≤nq,\Pr(\det M=0)\le\frac{n}{q},(10)✦ and if moreover n≥1n\ge1, KK has odd characteristic and ξ∈{1,−1}\xi\in\{1,-1\}, the sign probability satisfies |Pn(ξ)−12|≤nq.\Bigl|P_n(\xi)-\frac12\Bigr|\le\frac{n}{q}.(11)✦ For natural numbers r≤Dr\le D and ξ∈{1,−1}\xi\in\{1,-1\}, the layer mass is μD(r,ξ)=|GrD−r(KD)|qb(r)Pr(ξ)qb(D),\mu_D(r,\xi)=\frac{|\mathrm{Gr}_{D-r}(K^{D})|\,q^{b(r)}\,P_r(\xi)}{q^{b(D)}},(12)✦ and normalized by qb(D−r)q^{b(D-r)} it is μD(r,ξ)qb(D−r)=γD,D−r(q)Pr(ξ).\mu_D(r,\xi)\,q^{b(D-r)}=\gamma_{D,D-r}(q)\,P_r(\xi).(13)✦ For natural numbers 0<r≤D0<r\le D and ξ∈{1,−1}\xi\in\{1,-1\}, the layer masses over the fields 𝔽q\mathbb{F}_q, with qq running through the odd primes, satisfy limq→∞μD(q)(r,ξ)qb(D−r)=12.\lim_{q\to\infty}\mu^{(q)}_D(r,\xi)\,q^{b(D-r)}=\frac12.(14)✦ For 0≤u≤n0\le u\le n, the share of symmetric bilinear forms on VV whose radical has dimension at least uu satisfies |{B∈𝒮(V):dim⁡rad⁡B≥u}||𝒮(V)|≤2uqb(u).\frac{\bigl|\{B\in\mathcal{S}(V):\dim\operatorname{rad}B\ge u\}\bigr|}{|\mathcal{S}(V)|} \le\frac{2^{u}}{q^{b(u)}}.(15)✦

In the paper, the result reads: for 0≤k≤n0\le k\le n the number of kk-dimensional subspaces of 𝔽qn\mathbb{F}_q^{n} is ∏a<k(qn−qa)/(qk−qa)=qk(n−k)(1+O(1/q))\prod_{a<k}(q^{n}-q^{a})/(q^{k}-q^{a})=q^{k(n-k)}(1+O(1/q)); for MM uniform on SnS_n with n≥1n\ge1, Pr⁡(M is nonsingular)=1−O(1/q)\Pr(M\text{ is nonsingular})=1-O(1/q) and Pr⁡(χ(det⁡M)=ξ)=12+O(1/q)\Pr(\chi(\det M)=\xi)=\frac12+O(1/q); for 1≤r≤n1\le r\le n, the probability that MM has rank rr and sign ξ\xi is (12+O(1/q))q−b(n−r)(\frac12+O(1/q))\,q^{-b(n-r)}; and for 0≤u≤n0\le u\le n, Pr⁡(dim⁡ker⁡M≥u)=O(q−b(u))\Pr(\dim\ker M\ge u)=O(q^{-b(u)}).

What Is Checked

The claim is stated over the Grassmannians Grk(V)\mathrm{Gr}_k(V) of a vector space over a finite field, the Grassmann correction factor γD,k\gamma_{D,k}, the space SnS_n of symmetric matrices under the uniform law with its singular and sign probabilities, the sign of a symmetric bilinear form through its radical quotient form and the quadratic character, the signed rank layers LD(r,ξ)L_D(r,\xi) with their masses, the limit through the odd primes, and the symmetric bilinear forms 𝒮(V)\mathcal{S}(V) with their radicals.

The library proves that the symmetric D×DD\times D matrices form a subspace of all D×DD\times D matrices over KK, and that the bilinear form (x,y)↦xTZy(x,y)\mapsto x^{T}Zy of a matrix Z∈SDZ\in S_D is symmetric.