OctoInform Beta

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

§2 (setting): the parameters (2.1) and the tests Tᵢ, Rᵢ(t) (2.2), (2.3): MM is the least power of two above BΔB\Delta, the test at aa is injective, and Ra(t)R_a(t) has tt-degree at most M−1M-1

Parameters and reversed Taylor tests of the hitting list.

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 hitting list for noncommutative rational formulas in nn variables of size at most ss is built from a few integers computed from nn and ss and from one linear test TiT_i at each point i=0,1,…,ni = 0, 1, \dots, n. The integers fix the dimensions: a power of two MM and a number NN of columns. The test TiT_i acts on polynomials in zz of degree below MM with formal Laurent series in tt as coefficients. Its matrix has entries in the polynomial ring in tt and yields the test matrix Ri(t)R_i(t) of the construction.

The library defines the integers as functions of nn and ss, and the test and its matrices at an arbitrary point aa of an arbitrary field KK, written TaT_a and Ra(t)R_a(t).

Taylor Coordinates and Weights

Let KK be a field and F=K((t))F = K((t)) the field of formal Laurent series in tt over KK.✦ The polynomial embedding ι:K[t]→F\iota : K[t] \to F is the ring homomorphism that fixes KK and sends tt to tt; on matrices it acts entrywise.✦

For a field LL and a natural number mm, Pm(L)P_m(L) is the space of polynomials in zz over LL of degree below mm. The coefficient map πm:Lm→L[z]\pi_m : L^m \to L[z] is the linear map πm(c0,…,cm−1)=∑j=0m−1cjzj,\pi_m(c_0, \dots, c_{m-1}) = \sum_{j=0}^{m-1} c_j z^j,(1)✦ an isomorphism of LmL^m onto Pm(L)P_m(L); through it LmL^m and Pm(L)P_m(L) are identified, and the standard basis of LmL^m becomes 1,z,…,zm−11, z, \dots, z^{m-1}.

For a point a∈Ka \in K, the Taylor coordinates at aa form the linear automorphism τa\tau_a of KmK^m that sends a polynomial ff of degree below mm to its coefficients in powers of z−az-a: f=∑k=0m−1(τaf)k(z−a)k.f = \sum_{k=0}^{m-1} (\tau_a f)_k \, (z-a)^k .(2)✦ The reversal JJ of KmK^m is the linear automorphism that sends xx to the vector with (Jx)k=xm−1−k(Jx)_k = x_{m-1-k}✦, and the reverse Taylor coordinates at aa form the automorphism τarev=Jτa,(τarevf)k=(τaf)m−1−k.\tau_a^{\mathrm{rev}} = J\tau_a, \qquad (\tau_a^{\mathrm{rev}} f)_k = (\tau_a f)_{m-1-k}.(3)✦

A KK-linear map E:Km→Km′E : K^m \to K^{m'} extends to the FF-linear map EF:Fm→Fm′E_F : F^m \to F^{m'} with the same matrix.✦ For natural numbers ω0,…,ωm−1\omega_0, \dots, \omega_{m-1}, the weight map with weights ω\omega is the FF-linear map of FmF^m that multiplies the kk-th coordinate by tωkt^{\omega_k}; with ωk=k\omega_k = k it is Dm=diag(1,t,…,tm−1)D_m = \mathrm{diag}(1, t, \dots, t^{m-1}).✦

The Claim

Definition 1. Let nn and ss be natural numbers. The width is w=n+1,w = n+1,(4)✦ the bound is B=2s+1B = 2s+1✦, the gap is Δ=2w3B\Delta = 2w^3B✦, and the exponent is e=⌊log⁡2(BΔ)⌋.e = \lfloor \log_2 (B\Delta) \rfloor .(5)✦ The power of two MM and the truncation NN are M=2e+1,N=M−Δ.M = 2^{e+1}, \qquad N = M - \Delta .(6) Then MM exceeds BΔB\Delta, BΔ<M,B\Delta < M,(7)✦ is at most twice it, M≤2BΔ,M \le 2B\Delta,(8)✦ and is the least power of two above it: M≤2kfor every natural number k with BΔ<2k.M \le 2^k \quad \text{for every natural number $k$ with $B\Delta < 2^k$}.(9)✦ The truncation is positive, N≥1,N \ge 1,(10)✦ and M=N+Δ.M = N + \Delta .(11)✦

Let KK be a field, F=K((t))F = K((t)) and a∈Ka \in K, and let MM and NN be the numbers above or any natural numbers. The test at aa is the FF-linear map of FMF^M Ta=((τarev)−1)FDM(τa)F,T_a = \big((\tau_a^{\mathrm{rev}})^{-1}\big)_F \, D_M \, (\tau_a)_F ,(12)✦ and it is injective: ker⁡Ta=0.\ker T_a = 0 .(13)✦ The Taylor test matrix Φa(t)∈MatM(K[t])\Phi_a(t) \in \mathrm{Mat}_M(K[t]) has, in row pp and column qq, Φa(t)pq=∑k=0M−1[zp](z−a)M−1−k⋅[zk](z+a)q⋅tk(0≤p,q<M),\Phi_a(t)_{pq} = \sum_{k=0}^{M-1} [z^p](z-a)^{M-1-k} \cdot [z^k](z+a)^q \cdot t^k \qquad (0 \le p, q < M),(14)✦ where [zk]g[z^k]\,g is the coefficient of zkz^k in gg; its image under ι\iota is the matrix of TaT_a in the basis 1,z,…,zM−11, z, \dots, z^{M-1}: ι(Φa(t))=Mat(Ta).\iota\big(\Phi_a(t)\big) = \mathrm{Mat}(T_a) .(15)✦ The test matrix Ra(t)∈MatM(K[t])R_a(t) \in \mathrm{Mat}_M(K[t]) keeps the first NN columns of Φa(t)\Phi_a(t) and replaces the others by zero, Ra(t)pq={Φa(t)pq,q<N,0,q≥N,R_a(t)_{pq} = \begin{cases} \Phi_a(t)_{pq}, & q < N, \\ 0, & q \ge N, \end{cases}(16)✦ and its entries have tt-degree at most M−1M-1: deg⁡tRa(t)pq≤M−1(0≤p,q<M).\deg_t R_a(t)_{pq} \le M-1 \qquad (0 \le p, q < M).(17)✦

In the paper, the result reads: with 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, so that 1≤N<M≤2BΔ1 \le N < M \le 2B\Delta, and with F=ℚ((t))F = \mathbb{Q}((t)), the test Ti:PN(F)→PM(F)T_i : P_N(F) \to P_M(F) sends f=∑kcik(f)(z−i)kf = \sum_k c_{ik}(f)\,(z-i)^k to ∑kcik(f)tk(z−i)M−1−k\sum_k c_{ik}(f)\,t^k(z-i)^{M-1-k}, is injective and has a matrix with entries in ℤ[t]\mathbb{Z}[t] of tt-degree at most N−1N-1, and Ri(t)R_i(t) is TiT_i with M−NM-N zero columns appended.

What Is Checked

The definition is stated over natural numbers nn and ss, a field KK with its field F=K((t))F = K((t)) of formal Laurent series, and a point a∈Ka \in K, and it uses the coefficient map πM\pi_M, the Taylor coordinates τa\tau_a and τarev\tau_a^{\mathrm{rev}}, the reversal JJ, the extension of scalars from KK to FF, the weight map DMD_M and the polynomial embedding ι\iota.

Of these constructions, the library proves that the extension to FF of an invertible KK-linear map is invertible, with the extension of the inverse as its inverse✦, and that the reversal JJ is its own inverse.