OctoInformBeta

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

The rank obstruction: For large qq and many labels, a group with surviving rectangles and two Cartesian blocks at each point off an exceptional set is not residually finite

Rank bounds that no finite quotient can meet.

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 GG be a group and II a finite set of labels, and give each label ii an r×rr \times r array (giuv)(g_{iuv}) of elements of GG, with uu and vv running over 0,…,r−10, \dots, r-1. Each label also carries a punctured affine line in 𝔽qh\mathbb{F}_q^h, for a prime qq and a dimension hh. When can such a group fail to be residually finite? Its tool is the left regular representation of a finite quotient QQ of GG, which turns each array into a matrix over ℝ\mathbb{R} or 𝔽q\mathbb{F}_q; the library bounds the ranks of these matrices and of their sums over the labels whose lines pass through a point, except at a set EE of exceptional points of 𝔽qh\mathbb{F}_q^h.

Rectangles and Block Matrices

An r×rr \times r array g=(guv)g = (g_{uv}) of elements of a group has surviving rectangles when each of its rectangular words is nontrivial: for all u≠u′u \neq u' and v≠v′v \neq v', guvgu′v−1gu′v′guv′−1≠1.g_{uv}\,g_{u'v}^{-1}\,g_{u'v'}\,g_{uv'}^{-1} \neq 1.(1)✦

Let QQ be a finite group and RR a semiring. The left regular permutation matrix U(g)U(g) of an element gg of QQ is the permutation matrix over RR, with rows and columns indexed by QQ, of left multiplication by gg on QQ.✦ The map g↦U(g)g \mapsto U(g) is a homomorphism from QQ to the square matrices over RR indexed by QQ.

The regular block matrix Y(g)Y(g) of an r×rr \times r array g=(guv)g = (g_{uv}) of elements of QQ is the square matrix over RR, with rows and columns indexed by the pairs (u,x)(u, x) with x∈Qx \in Q, whose block in position (u,v)(u, v) is U(guv)U(g_{uv}): Y(g)=(U(guv))u,v.Y(g) = \bigl(U(g_{uv})\bigr)_{u,v}.(2)✦ For arrays gi=(giuv)g_i = (g_{iuv}), one for each label ii, the block matrix of label ii is Yi=Y(gi)Y_i = Y(g_i).

Cartesian Blocks

A Cartesian block bb with parameter rr is a finite set of labels together with positive integers sb,tb≥rs_b, t_b \ge r and a bijection i↦(αb(i),βb(i))i \mapsto (\alpha_b(i), \beta_b(i)) from bb onto ℤ/sb×ℤ/tb\mathbb{Z}/s_b \times \mathbb{Z}/t_b.✦

A family of r×rr \times r arrays (giuv)(g_{iuv}) in a group, one for each label, obeys the block relations on a Cartesian block bb when there are elements Lu,jL_{u,j} of the group, for j∈ℤ/sbj \in \mathbb{Z}/s_b, and Rv,kR_{v,k}, for k∈ℤ/tbk \in \mathbb{Z}/t_b, such that for every label ii of bb and all u,vu, v giuv=Lu,αb(i)+v−1Rv,βb(i)+u.g_{iuv} = L_{u,\,\alpha_b(i)+v}^{-1}\,R_{v,\,\beta_b(i)+u}.(3)✦

Punctured Lines and Certificates

Let KK be a finite field. The affine line ℓ\ell through a point aa of KhK^h in a direction vv is the image of x↦a+xvx \mapsto a + xv✦, and the punctured line ℓ\{a}\ell \setminus \{a\} is the set of its points other than aa.✦ Give each label ii a mark aia_i and a direction viv_i in KhK^h, with line ℓi\ell_i. The incidence set I(z)I(z) of a point zz of KhK^h is the set of labels ii with z∈ℓi\{ai}z \in \ell_i \setminus \{a_i\}.✦

The grid Lagrange polynomial λa\lambda_a of a point a=(a1,…,ah)a = (a_1, \dots, a_h) of KhK^h, for a subset SS of KK, is the function on KhK^h given, for z=(z1,…,zh)z = (z_1, \dots, z_h), by λa(z)=∏t=1h∏w∈S\{at}zt−wat−w.\lambda_a(z) = \prod_{t=1}^{h} \prod_{w \in S \setminus \{a_t\}} \frac{z_t - w}{a_t - w}.(4)✦

Over an arbitrary field KK, take a finite set PP of points and an assignment z↦I(z)z \mapsto I(z) of a set of labels to each point. A line certificate for this incidence is a family of weight vectors fz∈KIf_z \in K^I, one for each point zz of PP, such that for all labels ii, jj, kk ∑z:i∈I(z)fz(j)fz(k)=−δijδik.\sum_{z \,:\, i \in I(z)} f_z(j)\,f_z(k) = -\delta_{ij}\,\delta_{ik}.(5)

For a weight vector f∈KIf \in K^I and a matrix ZZ over KK, the weighted matrix ff𝖳⊗Zf f^{\mathsf T} \otimes Z is the Kronecker product of the rank-one matrix ff𝖳f f^{\mathsf T} with ZZ: its block in position (i,j)(i, j) is f(i)f(j)Zf(i)\,f(j)\,Z.✦ For matrices MiM_i over KK of one size, one for each label ii, the block diagonal matrix ⨁iMi\bigoplus_i M_i has MiM_i as its diagonal block in position (i,i)(i, i) and zero blocks elsewhere.✦

The Claim

Theorem 1. Let QQ be a finite group and g=(guv)g = (g_{uv}) an r×rr \times r array of elements of QQ. Over every semiring, tr⁡(Y(g)Y(g)𝖳)=r2|Q|.\operatorname{tr}\bigl(Y(g)\,Y(g)^{\mathsf T}\bigr) = r^2\,|Q|.(6)✦ If gg has surviving rectangles, then over every commutative ring tr⁡((Y(g)Y(g)𝖳)2)=(2r3−r2)|Q|,\operatorname{tr}\Bigl(\bigl(Y(g)\,Y(g)^{\mathsf T}\bigr)^2\Bigr) = (2r^3 - r^2)\,|Q|,(7)✦ over the real numbers r|Q|≤2rank⁡ℝY(g),r\,|Q| \le 2 \operatorname{rank}_{\mathbb{R}} Y(g),(8)✦ and over 𝔽q\mathbb{F}_q, for every prime q>rq > r, r|Q|≤4rank⁡𝔽qY(g).r\,|Q| \le 4 \operatorname{rank}_{\mathbb{F}_q} Y(g).(9)✦

For arrays (giuv)(g_{iuv}) in QQ, one for each label, with block matrices YiY_i over a field KK: if the arrays obey the block relations on a Cartesian block bb, then rank⁡K(∑i∈bYi)≤|Q|,\operatorname{rank}_K \Bigl(\sum_{i \in b} Y_i\Bigr) \le |Q|,(10)✦ and if a set AA of labels is the disjoint union of two Cartesian blocks, on each of which the arrays obey the block relations, then rank⁡K(∑i∈AYi)≤2|Q|.\operatorname{rank}_K \Bigl(\sum_{i \in A} Y_i\Bigr) \le 2\,|Q|.(11)✦

Over a finite field KK, every polynomial pp of degree less than |K|−1|K| - 1 satisfies ∑x∈Kp(x)=0.\sum_{x \in K} p(x) = 0.(12)✦ Take a subset SS of KK with 2h(|S|−1)<|K|−12h(|S| - 1) < |K| - 1, and give each label ii of a finite set II a mark ai∈Sha_i \in S^h and a direction vi≠0v_i \neq 0, distinct labels having distinct marks. Then the grid Lagrange weights fz(j)=λaj(z)f_z(j) = \lambda_{a_j}(z) form a line certificate for the incidence z↦I(z)z \mapsto I(z) on KhK^h: for all labels ii, jj, kk, ∑z∈ℓi\{ai}λaj(z)λak(z)=−δijδik.\sum_{z \in \ell_i \setminus \{a_i\}} \lambda_{a_j}(z)\,\lambda_{a_k}(z) = -\delta_{ij}\,\delta_{ik}.(13)✦

Suppose ff is a line certificate over a field KK for an incidence z↦I(z)z \mapsto I(z) on a finite set PP, and MiM_i, for i∈Ii \in I, are matrices over KK of one size. Then ∑z∈Pfzfz𝖳⊗(∑i∈I(z)Mi)=−⨁i∈IMi\sum_{z \in P} f_z f_z^{\mathsf T} \otimes \Bigl(\sum_{i \in I(z)} M_i\Bigr) = -\bigoplus_{i \in I} M_i(14)✦ and ∑i∈Irank⁡Mi≤∑z∈Prank⁡(∑i∈I(z)Mi).\sum_{i \in I} \operatorname{rank} M_i \le \sum_{z \in P} \operatorname{rank} \Bigl(\sum_{i \in I(z)} M_i\Bigr).(15)✦

When moreover K=𝔽qK = \mathbb{F}_q for a prime q>rq > r, EE is a set of exceptional points in PP, and (giuv)(g_{iuv}) are arrays in a finite group QQ with surviving rectangles whose block matrices satisfy rank⁡𝔽q(∑i∈I(z)Yi)≤2|Q|\operatorname{rank}_{\mathbb{F}_q} \bigl(\sum_{i \in I(z)} Y_i\bigr) \le 2\,|Q| at every point z∉Ez \notin E, the number of labels is bounded by r|I|≤4(2|P|+r|E|).r\,|I| \le 4\,\bigl(2\,|P| + r\,|E|\bigr).(16)✦

If GG is a residually finite group and (giuv)(g_{iuv}) are arrays in GG with surviving rectangles, indexed by a finite set of labels, then there are a finite group QQ and a homomorphism φ:G→Q\varphi \colon G \to Q such that, for every label ii and all u≠u′u \neq u' and v≠v′v \neq v', φ(giuv)φ(giu′v)−1φ(giu′v′)φ(giuv′)−1≠1.\varphi(g_{iuv})\,\varphi(g_{iu'v})^{-1}\,\varphi(g_{iu'v'})\,\varphi(g_{iuv'})^{-1} \neq 1.(17)✦

Let GG be any group and q>rq > r a prime, with SS, the marks ai∈Sha_i \in S^h and the directions vi≠0v_i \neq 0 as above over K=𝔽qK = \mathbb{F}_q, so that 2h(|S|−1)<q−12h(|S| - 1) < q - 1, and let EE be a set of exceptional points of 𝔽qh\mathbb{F}_q^h. Suppose the arrays (giuv)(g_{iuv}) in GG have surviving rectangles and, at every point z∉Ez \notin E, the incidence set I(z)I(z) is the disjoint union of two Cartesian blocks on each of which the arrays obey the block relations. If r|I|>4(2qh+r|E|),r\,|I| > 4\,\bigl(2q^h + r\,|E|\bigr),(18)✦ then GG is not residually finite.

What Is Checked

The claims are stated over the left regular permutation matrices U(g)U(g) of a finite group and the regular block matrices Y(g)Y(g) built from them, arrays with surviving rectangles, Cartesian blocks and their block relations, the punctured lines ℓi\{ai}\ell_i \setminus \{a_i\} with the incidence sets I(z)I(z), the grid Lagrange polynomials λa\lambda_a, and the weighted and block diagonal matrices.