OctoInform Beta

OpenAI preprint, September 2026 · §2. Rectangular tests from subspace expansion · §2

Proposition 2.1 [Rectangular rank bound]: For q≤Bq\le B, the padded test ∑iAi⊗Ri(t)\sum_i A_i\otimes R_i(t) then has rank at least qNqN, which exceeds (q−1)M(q-1)M when 1≤q1\le q and BΔ<MB\Delta<M

Injective evaluations make rectangular tests injective in low degree.

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

A linear pencil of order qq in nn variables is a q×qq\times q matrix of affine forms, given by coefficient matrices A0,…,AnA_0,\dots,A_n with A0A_0 holding the constants; its homogeneous evaluation at e×ee\times e matrices Z0,…,ZnZ_0,\dots,Z_n is the qe×qeqe\times qe matrix ∑i=0nAi⊗Zi\sum_{i=0}^n A_i\otimes Z_i. Proposition 2.1, the rectangular rank bound, is about one explicit point of a fixed size MM, a power of two defined with the parameters in the next paragraph: the tests T0,…,TnT_0,\dots,T_n, linear maps on polynomials of degree below MM over a field of Laurent series, built from Taylor expansions at distinct points a0,…,ana_0,\dots,a_n. The question is what an injective evaluation, at some point and of some size, forces on ∑iAi⊗Ti\sum_i A_i\otimes T_i: on which qq-tuples of polynomials it must be injective, and how large the rank of its matrix must be.

The parameters are those of the construction for formulas of size ss: w=n+1w=n+1, B=2s+1B=2s+1, Δ=2w3B\Delta=2w^3B, MM the least power of two greater than BΔB\Delta, and N=M−ΔN=M-\Delta.

Pencils Over Laurent Series

Fix a field KK. The Laurent series field F=K((t))F=K((t)) is the field of formal Laurent series in tt with coefficients in KK✦; the polynomial ring K[t]K[t] embeds in it by the ring homomorphism that is the identity on KK and sends tt to tt.✦

The block evaluation of coefficient matrices A0,…,An∈Matq(F)A_0,\dots,A_n\in\mathrm{Mat}_q(F) at Z0,…,Zn∈Mate(F)Z_0,\dots,Z_n\in\mathrm{Mat}_e(F) is their homogeneous evaluation as an FF-linear map ∑iAi⊗Zi\sum_i A_i\otimes Z_i of (Fq)e(F^q)^e: it sends an ee-tuple v=(v1,…,ve)v=(v_1,\dots,v_e) of vectors of FqF^q to the ee-tuple with entries ((∑i=0nAi⊗Zi)v)β=∑i=0n∑δ=1e(Zi)βδAivδ,1≤β≤e.\Big(\Big(\sum_{i=0}^n A_i\otimes Z_i\Big)v\Big)_\beta =\sum_{i=0}^n\sum_{\delta=1}^e (Z_i)_{\beta\delta}\,A_iv_\delta,\qquad 1\le\beta\le e.(1)✦

For M×MM\times M matrices R0,…,RnR_0,\dots,R_n over FF, the Kronecker sum ∑iAi⊗Ri\sum_i A_i\otimes R_i is the qM×qMqM\times qM matrix over FF with rows and columns indexed by the pairs (α,j)(\alpha,j), 1≤α≤q1\le\alpha\le q, 0≤j<M0\le j<M, and entries (∑i=0nAi⊗Ri)(α,j),(γ,k)=∑i=0n(Ai)αγ(Ri)jk.\Big(\sum_{i=0}^n A_i\otimes R_i\Big)_{(\alpha,j),(\gamma,k)} =\sum_{i=0}^n (A_i)_{\alpha\gamma}\,(R_i)_{jk}.(2)✦ For FF-linear maps T0,…,TnT_0,\dots,T_n of FMF^M, the map ∑iAi⊗Ti\sum_i A_i\otimes T_i of (FM)q(F^M)^q sends a qq-tuple f=(f1,…,fq)f=(f_1,\dots,f_q) to the qq-tuple whose α\alpha-th entry is ∑i=0n∑γ=1q(Ai)αγTifγ\sum_{i=0}^n\sum_{\gamma=1}^q (A_i)_{\alpha\gamma}\,T_if_\gamma.

The Taylor Tests

A vector y∈Kmy\in K^m is read as the polynomial ∑j<myjxj\sum_{j<m}y_jx^j, which identifies KmK^m with the space Pm(K)P_m(K) of polynomials of degree below mm, and FmF^m with Pm(F)P_m(F). A KK-linear map EE from KmK^m to Km′K^{m'} extends to the FF-linear map from FmF^m to Fm′F^{m'} with the same matrix, which is also written EE.✦

For a∈Ka\in K, the Taylor coordinate map at aa is the invertible KK-linear map τa\tau_a of PM(K)P_M(K) given by (τap)(x)=p(x+a)(\tau_ap)(x)=p(x+a); it gives the coefficients of pp in the powers of x−ax-a.✦ The reversal JJ of KMK^M is the KK-linear map with (Jy)j=yM−1−j(Jy)_j=y_{M-1-j}✦, and the reversed Taylor coordinate map at aa is JτaJ\tau_a.✦

For natural numbers μ0,…,μm−1\mu_0,\dots,\mu_{m-1}, the weight map WμW_\mu is the FF-linear map of FmF^m that multiplies the jj-th coordinate by tμjt^{\mu_j}.✦ Given also invertible KK-linear maps EE and E′E' of KmK^m, the conjugated weight map E′−1WμEE'^{-1}W_\mu E is the FF-linear map of FmF^m obtained by applying EE, then the weight map WμW_\mu, then the inverse of E′E'.✦

The test at a∈Ka\in K is the conjugated weight map with E=τaE=\tau_a, E′=JτaE'=J\tau_a and μj=j\mu_j=j, the FF-linear map TaT_a of PM(F)P_M(F) that sends (x−a)r(x-a)^r to tr(x−a)M−1−rt^r(x-a)^{M-1-r} for 0≤r<M0\le r<M: Ta=(Jτa)−1diag⁡(1,t,…,tM−1)τa.T_a=(J\tau_a)^{-1}\,\operatorname{diag}\big(1,t,\dots,t^{M-1}\big)\,\tau_a.(3)✦

The Taylor test matrix at aa is the M×MM\times M matrix Rˆa(t)\widehat R_a(t) of polynomials in tt over KK with entries Rˆa(t)jk=∑r=0M−1[xj](x−a)M−1−r[xr](x+a)ktr,0≤j,k<M,\widehat R_a(t)_{jk}=\sum_{r=0}^{M-1}[x^j](x-a)^{M-1-r}\,[x^r](x+a)^k\,t^r, \qquad 0\le j,k<M,(4)✦ where [xj]p[x^j]p is the coefficient of xjx^j in pp; read in FF, it is the matrix of TaT_a in the basis 1,x,…,xM−11,x,\dots,x^{M-1}. The padded test matrix Ra(t)R_a(t) is the M×MM\times M matrix whose columns of index below NN are those of Rˆa(t)\widehat R_a(t) and whose other columns are zero.✦

For points a0,…,ana_0,\dots,a_n of KK, write Ti=TaiT_i=T_{a_i} and Ri(t)=Rai(t)R_i(t)=R_{a_i}(t). The rectangular test is the map ∑iAi⊗Ti\sum_i A_i\otimes T_i on qq-tuples of polynomials of degree below NN, and the padded test is the Kronecker sum ∑iAi⊗Ri(t)\sum_i A_i\otimes R_i(t).

The Claim

Theorem 1. Let KK be a field of characteristic zero and F=K((t))F=K((t)). Let nn, BB, NN, qq and ee be natural numbers with q≤Bq\le B, N≥1N\ge1 and e≥1e\ge1, and put w=n+1w=n+1, Δ=2w3B\Delta=2w^3B and M=N+ΔM=N+\Delta. Let a0,…,ana_0,\dots,a_n be distinct points of KK and A0,…,An∈Matq(F)A_0,\dots,A_n\in\mathrm{Mat}_q(F), and suppose that for some Z0,…,Zn∈Mate(F)Z_0,\dots,Z_n\in\mathrm{Mat}_e(F) the block evaluation ∑iAi⊗Zi\sum_i A_i\otimes Z_i is injective. Then ker⁡(∑i=0nAi⊗Ti)∩PN(F)q={0}\ker\Big(\sum_{i=0}^n A_i\otimes T_i\Big)\cap P_N(F)^q=\{0\}(5)✦ and rank⁡F(∑i=0nAi⊗Ri(t))≥qN.\operatorname{rank}_F\Big(\sum_{i=0}^n A_i\otimes R_i(t)\Big)\ge qN.(6)✦ Whatever the field and the pencil, if 1≤q≤B1\le q\le B and BΔ<MB\Delta<M, then (q−1)M<qN.(q-1)M<qN.(7)✦

In the paper, the result reads: for 1≤q≤B1\le q\le B and A0,…,An∈Matq(ℚ)A_0,\dots,A_n\in\mathrm{Mat}_q(\mathbb{Q}), if for some extension field EE of ℚ\mathbb{Q}, some e≥1e\ge1 and some X1,…,Xn∈Mate(E)X_1,\dots,X_n\in\mathrm{Mat}_e(E) the matrix A0⊗Ie+∑i=1nAi⊗XiA_0\otimes I_e+\sum_{i=1}^n A_i\otimes X_i is invertible, then ∑i=0nAi⊗Ti\sum_{i=0}^n A_i\otimes T_i is injective over F=ℚ((t))F=\mathbb{Q}((t)) and rank⁡ℚ(t)(∑i=0nAi⊗Ri(t))≥qN>(q−1)M\operatorname{rank}_{\mathbb{Q}(t)}\big(\sum_{i=0}^n A_i\otimes R_i(t)\big)\ge qN>(q-1)M, with K=ℚK=\mathbb{Q} and the points ai=ia_i=i.

What Is Checked

The claims (5) and (6) are stated over the Laurent series field F=K((t))F=K((t)) of an arbitrary field KK of characteristic zero, the block evaluation (1) of matrices over FF, the Kronecker sums (2), the tests (3) built from the Taylor coordinate maps, their reversal and the weight map, and the padded test matrices cut from (4) and read in FF through K[t]⊂FK[t]\subset F; the inequality (7) is a statement about natural numbers.

The library also shows that the extension to FF of an invertible KK-linear map between spaces KmK^m and Km′K^{m'} is invertible, with the extension of the inverse as its inverse.✦