OctoInformBeta

OpenAI preprint, September 2026 · §2. The construction and the rank obstruction · §2.4 to §2.5

Regular representation matrices and the line certificate: Left regular matrices U(g)U(g), block matrices YiY_i, product Lagrange polynomials of a grid, incidence of punctured lines, rank-one weights and block diagonal matrices

The matrices and lines of the rank obstruction.

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

The labels are the elements ii of a finite index set II, and rr is the number of values each of the indices u,vu, v takes, so that u,v∈{0,…,r−1}u, v \in \{0, \dots, r-1\}. Let KK be the complex with vertices OO, VV, WW, and let GG be the group with one generator for each edge of KK; among the edges are the xiuvx_{iuv} from VV to WW, one for each label ii and each pair of indices u,vu, v. The rank obstruction is the test of GG against its finite quotients by linear algebra: a finite quotient QQ sends the r2r^2 generators xiuvx_{iuv} of a label to elements giuvg_{iuv} of QQ, and the left regular representation of QQ turns them into one square matrix for that label.

The labels are also lines in P=𝔽qhP = \mathbb{F}_q^{h}, with h=20h = 20 and qq a prime. Label ii has a mark aia_i in the grid ShS^h, where S⊂𝔽qS \subset \mathbb{F}_q has ⌊q/100⌋\lfloor q/100 \rfloor elements, and a direction viv_i, which together give a line ℓi\ell_i of PP punctured at aia_i. Each mark aia_i is a node of the grid ShS^h, and the product Lagrange polynomial faif_{a_i} of the grid at aia_i is defined in Definition 1. The matrices of the labels are combined in two ways, both defined below: into the weighted matrix ww𝖳⊗Zw w^{\mathsf T} \otimes Z, with the rank-one matrix ww𝖳w w^{\mathsf T} of a weight vector ww, and into the block diagonal matrix.

Lines and Block Matrices

Let kk be a field and TT a set; the construction takes k=𝔽qk = \mathbb{F}_q and T={1,…,h}T = \{1, \dots, h\}, so that kT=Pk^T = P. The affine line through a point a∈kTa \in k^T in direction v∈kTv \in k^T is parametrized by the map k→kTk \to k^T that sends a scalar λ\lambda to the point a+λva + \lambda v with coordinates (a+λv)t=at+λvt(t∈T).(a + \lambda v)_t = a_t + \lambda\, v_t \qquad (t \in T).(1)✦ The image of this map is the line ℓ(a,v)={a+λv:λ∈k}\ell(a, v) = \{a + \lambda v : \lambda \in k\} through aa in direction vv.

Let JJ, J′J', XX, X′X' be sets. A block matrix M=(Muv)M = (M_{uv}), with u∈Ju \in J, v∈J′v \in J' and each block MuvM_{uv} an X×X′X \times X' matrix, is the (J×X)×(J′×X′)(J \times X) \times (J' \times X') matrix with entries M(u,x),(v,y)=(Muv)x,y.M_{(u,x),(v,y)} = (M_{uv})_{x,y}.(2)✦

The Definition

Definition 1. Let QQ be a finite group and RR a semiring. The left regular permutation matrix of an element g∈Qg \in Q is the Q×QQ \times Q matrix U(g)U(g) over RR with entries U(g)x,y={1if x=gy,0otherwise,x,y∈Q.U(g)_{x,y} = \begin{cases} 1 & \text{if } x = g y, \\ 0 & \text{otherwise,} \end{cases} \qquad x, y \in Q.(3)✦ For elements guvg_{uv} of QQ indexed by u,vu, v in a set JJ, the regular block matrix of the array (guv)(g_{uv}) is the block matrix of (2), with rows and columns indexed by J×QJ \times Q, Y=(U(guv))u,v∈J,Y = \bigl(U(g_{uv})\bigr)_{u, v \in J},(4)✦ and the block matrix YiY_i of a label ii is the one of the array (giuv)u,v(g_{iuv})_{u,v}, with J={0,…,r−1}J = \{0, \dots, r-1\}.

Let kk be a field, TT a finite set and SS a finite subset of kk. The product Lagrange polynomial of the grid STS^T at a point a∈kTa \in k^T is the function faf_a on kTk^T given by fa(x)=∏t∈T∏s∈S,s≠atxt−sat−s.f_a(x) = \prod_{t \in T} \, \prod_{s \in S,\ s \neq a_t} \frac{x_t - s}{a_t - s}.(5)✦ When kk is finite, the punctured line through a∈kTa \in k^T in direction v∈kTv \in k^T is the set of points of ℓ(a,v)\ell(a, v) other than aa, ℓ(a,v)\{a}={a+λv:λ∈k}\{a}.\ell(a, v) \setminus \{a\} = \{\, a + \lambda v : \lambda \in k \,\} \setminus \{a\}.(6)✦ For a finite set II of labels, each label ii with a mark ai∈kTa_i \in k^T and a direction vi∈kTv_i \in k^T, the set I(z)I(z) of labels incident to a point z∈kTz \in k^T is I(z)={i∈I:z∈ℓ(ai,vi)\{ai}}.I(z) = \{\, i \in I : z \in \ell(a_i, v_i) \setminus \{a_i\} \,\}.(7)✦

Let II, XX and X′X' be sets. Let KK be a set with a multiplication. For a vector w=(wi)i∈Iw = (w_i)_{i \in I} of elements of KK and an X×X′X \times X' matrix ZZ with entries in KK, the weighted matrix ww𝖳⊗Zw w^{\mathsf T} \otimes Z is the (I×X)×(I×X′)(I \times X) \times (I \times X') matrix with entries (ww𝖳⊗Z)(i,x),(j,y)=wiwjZx,y.(w w^{\mathsf T} \otimes Z)_{(i,x),(j,y)} = w_i\, w_j\, Z_{x,y}.(8)✦ For X×X′X \times X' matrices MiM_i, one for each i∈Ii \in I, the block diagonal matrix ⨁i∈IMi\bigoplus_{i \in I} M_i is the (I×X)×(I×X′)(I \times X) \times (I \times X') matrix with entries (⨁i∈IMi)(i,x),(j,y)={(Mi)x,yif i=j,0otherwise.\Bigl(\bigoplus_{i \in I} M_i\Bigr)_{(i,x),(j,y)} = \begin{cases} (M_i)_{x,y} & \text{if } i = j, \\ 0 & \text{otherwise.} \end{cases}(9)✦

In the paper, the result reads: U(g)U(g) is the regular permutation matrix of gg on a finite quotient QQ, Yi=(U(giuv))u,vY_i = (U(g_{iuv}))_{u,v} by its equation (2.7), Z(z)=∑i∈I(z)YiZ(z) = \sum_{i \in I(z)} Y_i, the fif_i are the product Lagrange polynomials on ShS^h, and H(z)=f(z)f(z)𝖳H(z) = f(z) f(z)^{\mathsf T} with f(z)=(fi(z))if(z) = (f_i(z))_i, where the paper’s fif_i is the page’s faif_{a_i}. With the weight w=(fai(z))iw = (f_{a_i}(z))_i and Z=Z(z)Z = Z(z), the weighted matrix of (8) is H(z)⊗Z(z)H(z) \otimes Z(z).

What Is Checked

The definitions are stated over a finite group QQ and a semiring RR of coefficients for UU and the regular block matrices, with the array (guv)(g_{uv}) over any index set JJ; over a field kk, a finite set TT and a finite subset SS of kk for faf_a; over a finite field kk and a finite set II of labels for the punctured lines and the sets I(z)I(z); and over arbitrary index sets for the weighted and block diagonal matrices. The library proves that UU is a homomorphism from QQ to the multiplicative monoid of Q×QQ \times Q matrices over RR: U(gh)=U(g)U(h)U(gh) = U(g)\,U(h) for all g,h∈Qg, h \in Q, and U(1)U(1) is the identity matrix.