OctoInform Beta

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

Lemma 2.4 [Small-subspace expansion]: In characteristic zero, the images of U⊆PN(F)U \subseteq P_N(F) of dimension k∈[1,B]k \in [1, B] under tests at ww distinct points span more than (w−1)k(w-1)k dimensions

Small subspaces expand under reverse Taylor tests.

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 KK be a field and F=K((t))F = K((t)) the field of formal Laurent series over KK, the series ∑j≥j0cjtj\sum_{j \ge j_0} c_j t^j with coefficients cj∈Kc_j \in K and an integer j0j_0.✦ For a natural number dd and L∈{F,K}L \in \{F, K\}, Pd(L)P_d(L) is the space of polynomials in the variable XX over LL of degree below dd. Fix a natural number MM; each point a∈Ka \in K gives a reverse Taylor test TaT_a, an FF-linear map of PM(F)P_M(F) into itself.

Take natural numbers w≥1w \ge 1 and N≤MN \le M, a subspace U⊆PN(F)U \subseteq P_N(F) of dimension kk, and distinct points a0,…,aw−1a_0, \dots, a_{w-1} of KK. The images TaiUT_{a_i}U span a subspace of PM(F)P_M(F) of dimension at most wkwk. The question is how far below wkwk that dimension can fall when k≤Bk \le B. Here BB is a natural number, Δ=2w3B\Delta = 2w^3B and N=M−ΔN = M - \Delta.

For hitting lists of noncommutative rational formulas of size ss in nn variables, the tests are taken at the points 0,1,…,n0, 1, \dots, n of ℚ\mathbb{Q}, so that w=n+1w = n + 1, and the dimension bound is B=2s+1B = 2s + 1.

The Reverse Taylor Tests

The coefficient map identifies KMK^M with PM(K)P_M(K), sending xx to ∑j=0M−1xjXj\sum_{j=0}^{M-1} x_j X^j; through it a subspace of KMK^M is a space of polynomials in K[X]K[X], and FM=PM(F)F^M = P_M(F) likewise.✦

The lift of a KK-linear map P:Kι→KκP \colon K^\iota \to K^\kappa, for finite index sets ι\iota and κ\kappa, is the FF-linear map Fι→FκF^\iota \to F^\kappa with the same matrix, again written PP.✦ When PP is invertible, its lift is invertible, with the lift of P−1P^{-1} as inverse.✦ A weight ee on an index set ι\iota attaches a natural number eie_i to each index ii, and its weight map DeD_e is the FF-linear map of FιF^\iota that multiplies the entry at ii by teit^{e_i}.✦ For a weight ee on ι\iota and invertible KK-linear maps EinE_{\mathrm{in}} and EoutE_{\mathrm{out}} of KιK^\iota, the conjugated weight map of ee is the FF-linear map Eout−1DeEinE_{\mathrm{out}}^{-1} D_e E_{\mathrm{in}} of FιF^\iota, with both maps acting on FιF^\iota through their lifts.✦

The Taylor coordinates at a point a∈Ka \in K form the KK-linear automorphism τa\tau_a of KMK^M that sends a polynomial ff of degree below MM to its Taylor coefficients (c0,…,cM−1)(c_0, \dots, c_{M-1}) at aa, the ones with f=∑jcj(X−a)jf = \sum_j c_j (X - a)^j.✦ The coordinate reversal JJ of KMK^M is the automorphism with (Jx)j=xM−1−j(Jx)_j = x_{M-1-j}✦, and the reverse Taylor coordinates at aa form the automorphism JτaJ\tau_a.✦ The reverse Taylor test at aa is the FF-linear map Ta=(Jτa)−1DeτaT_a = (J\tau_a)^{-1} D_e\, \tau_a of FMF^M, the conjugated weight map with weights ej=je_j = j; on Taylor coefficients cj∈Fc_j \in F at aa it reads Ta(∑j=0M−1cj(X−a)j)=∑j=0M−1tjcj(X−a)M−1−j.T_a\Bigl(\sum_{j=0}^{M-1} c_j (X-a)^j\Bigr) = \sum_{j=0}^{M-1} t^j c_j \,(X-a)^{M-1-j}.(1)✦

Integral Vectors and Reduction

A Laurent series x∈Fx \in F is integral when it has no terms of negative degree, so that it lies in 𝒪=K[[t]]\mathcal{O} = K[[t]]✦, and a vector over FF is integral when all its entries are.✦ The reduction x‾∈K\bar x \in K of a series x∈Fx \in F is its coefficient of t0t^0, its reduction mod tt when xx is integral✦; the reduction x‾∈Kι\bar x \in K^\iota of a vector x∈Fιx \in F^\iota is taken entry by entry.✦

The reduction U‾\bar U of a subspace UU of FιF^\iota is the KK-subspace of KιK^\iota spanned by the set of reductions x‾\bar x of the integral vectors x∈Ux \in U.✦

The order of vanishing ord⁡af\operatorname{ord}_a f of a nonzero polynomial f∈K[X]f \in K[X] at a point a∈Ka \in K is the multiplicity of aa as a root of ff.

The Claim

Theorem 1. Let KK be a field of characteristic zero and F=K((t))F = K((t)). Let w≥1w \ge 1, N≥1N \ge 1 and BB be natural numbers, Δ=2w3B\Delta = 2w^3B and M=N+ΔM = N + \Delta, and let a0,…,aw−1a_0, \dots, a_{w-1} be distinct points of KK. Let U⊆PN(F)U \subseteq P_N(F) be a subspace of dimension kk over FF with 1≤k≤B1 \le k \le B, and let WW be a subspace of PM(F)P_M(F) that contains TaiUT_{a_i}U for every i=0,…,w−1i = 0, \dots, w-1. Then dim⁡FW>(w−1)k.\dim_F W > (w-1)k.(2)✦

In the paper, the result reads: for every kk-dimensional subspace U⊆PN(F)U \subseteq P_N(F) with 1≤k≤B1 \le k \le B, dim⁡F(∑i=0nTiU)>(w−1)k\dim_F\bigl(\sum_{i=0}^{n} T_iU\bigr) > (w-1)k, where F=ℚ((t))F = \mathbb{Q}((t)) and TiT_i is the test at the point ii.

Taking K=ℚK = \mathbb{Q}, ai=ia_i = i and W=∑iTaiUW = \sum_i T_{a_i}U in (2) gives this form.

What Is Checked

The claim is stated over the Laurent series field FF of a field KK of characteristic zero, the subspaces of FM=PM(F)F^M = P_M(F) with their dimension over FF, and the reverse Taylor tests (1) at distinct points of KK, built from the Taylor coordinates, the coordinate reversal and the weight map.

On reduction mod tt, the library has two further results. Let ee be a weight on an index set ι\iota and AA a natural number, let x∈Fιx \in F^\iota be an integral vector with an index jj such that ej≤Ae_j \le A and xj¯≠0\overline{x_j} \neq 0, and let λ∈F\lambda \in F be nonzero with λDex\lambda D_e x integral. Then (λDex)i¯=0for every i∈ι with ei>A.\overline{(\lambda D_e x)_i} = 0 \quad \text{for every } i \in \iota \text{ with } e_i > A.(3)✦ For a subspace UU of FιF^\iota with ι\iota finite and a KK-linear map PP from KιK^\iota to a vector space VV over KK, there is a subspace U′U' of UU with dim⁡FU′=dim⁡KP(U‾)\dim_F U' = \dim_K P(\bar U)(4)✦ such that x‾=0\bar x = 0 for every integral vector x∈U′x \in U' with P(x‾)=0P(\bar x) = 0.

Three further results concern the reductions of subspaces of FMF^M. If UU is a subspace of FMF^M contained in PN(F)P_N(F), then U‾⊆PN(K).\bar U \subseteq P_N(K).(5)✦ Let a∈Ka \in K, let UU and WW be subspaces of FMF^M with TaU⊆WT_aU \subseteq W, let f1,…,fkf_1, \dots, f_k be a basis of U‾\bar U whose orders of vanishing ord⁡afj\operatorname{ord}_a f_j are pairwise distinct, and let g1,…,glg_1, \dots, g_l be a basis of W‾\bar W with the same property. Then k(M−1)≤∑j=1kord⁡afj+∑j=1lord⁡agj,k(M-1) \le \sum_{j=1}^{k} \operatorname{ord}_a f_j + \sum_{j=1}^{l} \operatorname{ord}_a g_j,(6)✦ and, for every natural number AA, #{j:ord⁡afj≤A}≤#{j:ord⁡agj≥M−1−A}.\#\{j : \operatorname{ord}_a f_j \le A\} \le \#\{j : \operatorname{ord}_a g_j \ge M-1-A\}.(7)✦

The last result is an inequality between natural numbers. Let w≥1w \ge 1, N≥1N \ge 1, kk with 1≤k≤B1 \le k \le B, and ll be natural numbers and M=N+ΔM = N + \Delta; the first inequality of the display below then forces the second. wk(M−1)≤k(N−1)+w(k2)+l(M−1)+w(l2)implies(w−1)k<l.wk(M-1) \le k(N-1) + w\binom{k}{2} + l(M-1) + w\binom{l}{2} \quad\text{implies}\quad (w-1)k < l.(8)✦