OctoInform Beta

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

Lemma 2.2 [Wronskian order bound]: In characteristic zero, hh-dimensional polynomial spaces of degree below dd have root multiplicities at ww distinct points totaling at most h(d−1)+w(h2)h(d-1)+w\binom{h}{2}

The root multiplicities of a polynomial space are bounded.

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 Pd(K)P_d(K) the space of polynomials over KK of degree below dd. For a polynomial ff in the variable XX over KK and a point a∈Ka \in K, the multiplicity mult⁡af\operatorname{mult}_a f of aa as a root of ff is the largest natural number mm such that (X−a)m(X-a)^m divides ff; by convention the zero polynomial has multiplicity 00 at every point and degree 00.

Let VV be a subspace of Pd(K)P_d(K) of dimension hh and aa a point of KK. Take a basis e1,…,ehe_1, \dots, e_h of VV whose multiplicities at aa are pairwise distinct. The question is how large the sum ∑jmult⁡aej\sum_j \operatorname{mult}_a e_j can be, added over ww distinct points of a field of characteristic zero: the lemma bounds it by a quantity in hh, dd and ww alone.

The Claim

Theorem 1. Let KK be a field of characteristic zero, VV an hh-dimensional subspace of Pd(K)P_d(K), and a0,…,aw−1a_0, \dots, a_{w-1} distinct points of KK. For each ii, let ei1,…,eihe_{i1}, \dots, e_{ih} be a basis of VV whose multiplicities at aia_i are pairwise distinct. Then ∑i=0w−1∑j=1hmult⁡aieij≤h(d−1)+w(h2).\sum_{i=0}^{w-1} \sum_{j=1}^{h} \operatorname{mult}_{a_i} e_{ij} \le h(d-1) + w\binom{h}{2}.(1)✦

In the paper, the result reads: at the w=n+1w = n+1 points 0,1,…,n0, 1, \dots, n, one has ∑i=0n∑j=1hdij≤h(d−1)+w(h2)\sum_{i=0}^{n} \sum_{j=1}^{h} d_{ij} \le h(d-1) + w\binom{h}{2}, where its points 0,…,n0, \dots, n stand for a0,…,aw−1a_0, \dots, a_{w-1} and its dijd_{ij} for mult⁡aieij\operatorname{mult}_{a_i} e_{ij}.

What Is Checked

The claim (1) is stated over a field KK of characteristic zero, an hh-dimensional subspace VV of Pd(K)P_d(K), ww distinct points a0,…,aw−1a_0, \dots, a_{w-1} of KK, and at each point aia_i a basis ei1,…,eihe_{i1}, \dots, e_{ih} of VV with pairwise distinct multiplicities at aia_i.

The Wronskian W(f1,…,fh)W(f_1, \dots, f_h) of polynomials f1,…,fhf_1, \dots, f_h over a commutative ring KK is the determinant of the h×hh \times h matrix whose entry in row ii and column jj is the ii-th formal derivative fj(i)f_j^{(i)} of fjf_j: W(f1,…,fh)=det⁡(fj(i))0≤i≤h−1,1≤j≤h.W(f_1, \dots, f_h) = \det\bigl(f_j^{(i)}\bigr)_{0 \le i \le h-1,\; 1 \le j \le h}.(2)✦ When each fjf_j has degree at most DD, deg⁡W(f1,…,fh)≤hD.\deg W(f_1, \dots, f_h) \le hD.(3)✦

Over a field KK of characteristic zero, let f1,…,fhf_1, \dots, f_h be nonzero polynomials whose multiplicities at a point aa are pairwise distinct; then mult⁡aW(f1,…,fh)+(h2)=∑j=1hmult⁡afj.\operatorname{mult}_a W(f_1, \dots, f_h) + \binom{h}{2} = \sum_{j=1}^{h} \operatorname{mult}_a f_j.(4)✦ For a subspace VV of Pd(K)P_d(K), with KK again of characteristic zero, a point a∈Ka \in K and any two bases b1,…,bhb_1, \dots, b_h and b1′,…,bh′b'_1, \dots, b'_h of VV, the Wronskians (2) of the two bases satisfy mult⁡aW(b1′,…,bh′)=mult⁡aW(b1,…,bh).\operatorname{mult}_a W(b'_1, \dots, b'_h) = \operatorname{mult}_a W(b_1, \dots, b_h).(5)✦

Over any field KK, a polynomial ff and a finite set SS of points of KK satisfy ∑a∈Smult⁡af≤deg⁡f.\sum_{a \in S} \operatorname{mult}_a f \le \deg f.(6)✦