Dimension of a bounded-total-degree polynomial space ($\dim {\mathcal{P}}_{\le d}(k^n)=\left(\genfrac{}{}{0ex}{}{n+d}{n}\right)$)

The vector space of formal polynomials over a field $k$ in $n$ variables with total degree of a polynomial at most $d$ has the monomial basis $x_1^{a_1}\cdots x_n^{a_n}$ for nonnegative exponents with ${\sum }_i{a}_i\le d$. Introducing a slack exponent and using stars and bars counts $\left(\genfrac{}{}{0ex}{}{n+d}{n}\right)$ basis elements. These are formal polynomials; over a finite field, distinct formal polynomials need not define distinct polynomial functions unless suitable degree restrictions hold.

Evaluation of bounded-degree multivariate polynomials on a finite set defines a linear map $E_P:f\mapsto (f(p){)}_{p\in P}$. Its rank is at most $|P|$ and its kernel is the space of polynomials vanishing on $P$. The rank-nullity theorem gives $\dim \ker E_P\ge \left(\genfrac{}{}{0ex}{}{d+n}{n}\right)-|P|$ for degree at most $d$ in $n$ variables. Dependent point constraints only enlarge the kernel.