---

Statement

Fix a field $K$, an integer $d\ge0$, and $m\le d+1$ distinct points $z_1,\ldots,z_m\in K^s$. Evaluation at these points is a surjective linear map from the space of polynomials of total degree at most $d$ onto $K^m$. Consequently, if $K$ has $q$ elements, independently uniform choices of $a$ such polynomials vanish at all $m$ points with probability $q^{-am}$.

There is also a coefficient-counting version. Let $K_0\subseteq L$ be fields, let $P_1,\ldots,P_a$ be degree-at-most-$d$ polynomials over $L$, and let $M$ be the number of monomials of degree at most $d$ in $2b$ variables. Suppose all $aM$ coefficients, together with $h$ further scalars, are algebraically independent over $K_0$.

Form a bipartite graph with two copies of $L^b$, joining $x$ on the left to $y$ on the right when $P_j(x,y)=0$ for every $j$. Let $U$ be a finite set of its vertices, and $E$ a set of its edges supported on $U$, with $|E|\le d+1$. If each of the $h$ further scalars is a coordinate of a vertex in $U$, then

$$h+a|E|\le b|U|.$$

Proof

For each $i\ne j$, choose a coordinate where $z_i$ and $z_j$ differ. A linear polynomial in that coordinate can be normalized to take value one at $z_i$ and zero at $z_j$. Multiplying these $m-1$ factors gives a polynomial $L_i$ of degree at most $m-1$ with $L_i(z_j)=\mathbf 1_{i=j}$. Thus $\sum_i v_iL_i$ interpolates any prescribed values $v_i$. The case $m=0$ is the zero-dimensional target and is immediate.

Over a finite field, every fiber of the surjective evaluation map is a translate of its kernel and has the same size. A uniform polynomial therefore has a uniform evaluation vector. Taking $a$ independent polynomials gives the stated probability.

For the coefficient bound, orient every edge from left to right. Distinct edges have distinct $2b$-coordinate evaluation points, even if some vertices on opposite sides have the same coordinate vector. Let $B$ be the subfield of $L$ generated over $K_0$ by all coordinates of vertices in $U$. It is generated by at most $b|U|$ scalars. Interpolation over $B$ shows that, for each $P_j$, its vanishing on $E$ supplies $|E|$ independent linear relations on its $M$ coefficients. The relations for different polynomials occupy separate coefficient blocks. Gaussian elimination therefore expresses all coefficients as $B$-linear combinations of at most $aM-a|E|$ of them. Equivalently, their span over $B$ has dimension at most that number; either formulation also covers redundant generators.

The field generated by $B$ and these remaining coefficient generators contains all $aM+h$ algebraically independent scalars. A field generated by $r$ elements over $K_0$ has transcendence degree at most $r$. Hence

$$aM+h\le b|U|+aM-a|E|,$$

and cancellation proves the claim.

Source and dependencies

This is the explicit interpolation and algebraic-dimension step suppressed in Proposition 2.1 of the exposition. The pinned formal source proves PolynomialSampling.interpolate, evaluation_surjective, and system_probability, lines 2416–2573; LinearRelations.small_generating_set, lines 2610–2643; GenericConstraints.independent_extras_bound, lines 2799–2824; and PolynomialEdgeConstraints.independent_bound, lines 2876–2912.

The field-theoretic input is the elementary transcendence-degree bound for finitely generated fields, used formally through the algebraic-independence matroid. It is not an algebraic-geometric point-counting estimate. No lower bound on field size is needed for the interpolation assertion itself.

Bears on. #571.