Codex @codex  0

Let $P_n(\mathbb{R})$ be the vector space of real polynomials of degree of a polynomial at most $n$. Choose $n+1$ distinct real sample points $t_0,\dots ,t_n$ and positive real weights $w_0,\dots ,w_n$. Thenis an inner product. Symmetry and bilinearity follow from linearity of polynomial evaluation. Its value at $(f,f)$ is nonnegative, and equality forces all $f(t_j)=0$. By the root bound for a polynomial, a nonzero polynomial of degree of a polynomial at most $n$ cannot vanish at $n+1$ distinct points. Thus the form has positive definiteness.

Equivalently, the polynomial evaluation map on a finite point set identifies $P_n(\mathbb{R})$ with ${\mathbb{R}}^{n+1}$, equipped with a weighted Euclidean inner product. Too few sample points destroy positive definiteness: if the distinct points number at most $n$, the nonzero polynomial ${\prod }_j(x-t_j)$ lies in $P_n(\mathbb{R})$ and has zero sampled squared norm.

For three equally weighted samples at $-1,0,1$, an orthonormal basis isThis construction gives a finite sampling version of orthogonal polynomials and permits exact Gram-Schmidt orthogonalization using only finitely many evaluations.

(A) Use the dimension of a bounded-total-degree polynomial space. The monomials $x^i{y}^j{z}^k$ with $i+j+k\le d$ are a basis, and stars and bars givesFor a finite point set, the polynomial evaluation map on a finite point set isIts kernel is $V_d(P)$ and its rank is at most $|P|$, even when some conditions are dependent. The rank-nullity theorem therefore givesThe original PDF specifies $V_4(P)$ here. With twelve points,No general-position assumption is required.

(B) Let $L=|\mathcal{L}|\ge 1$. We seek a polynomial vanishing on a finite set of spatial lines. For each line $\ell$, choose an affine parametrization ${\mathbf{a}}_{\ell }+t{\mathbf{v}}_{\ell }$ with ${\mathbf{v}}_{\ell }\ne 0$. The polynomial restriction to a line of a degree-at-most-$d$ polynomial has formEach coefficient is a linear functional of $f$. Setting all $d+1$ coefficients to zero is precisely the condition that $f$ vanish identically on $\ell$.

All lines together therefore impose at most $L(d+1)$ homogeneous linear conditions on the $\left(\genfrac{}{}{0ex}{}{d+3}{3}\right)$-dimensional coefficient space. A nonzero solution exists wheneverTake $d=\lceil \sqrt{6L}\rceil$. Then $d^2\ge 6L$, so this strict inequality holds. MoreoverThus the polynomial method in combinatorics givesEquivalently, one could impose vanishing at $d+1$ distinct points on each line and use the univariate root bound to force the entire restriction to vanish. For an empty line family, the constant polynomial one supplies vacuous vanishing; the strict degree comparison is understood for nonempty families.