(d + 1)! (m + 1)!

m+d +2

= .

d +1

This auxiliary result helps us to understand the structure of polynomials in d dimensions

better. The ¬rst part of the following result seems to be obvious but requires nevertheless

a proof.

Theorem 2.5

(1) The monomials x ’ x ± , x ∈ Rd , ± ∈ Nd , are linearly independent.

0

m+d

(2) dim πm (R ) = .

d

d

Proof Let us start with the ¬rst property. The proof is by induction on d. For d = 1 this

is obvious, since for any polynomial p(x) = n c j x j the coef¬cients are determined by

j=0

c j = p ( j) (0)/j!. Thus if p is identically zero then all coef¬cients must be zero. Now suppose

everything has been proven for d ’ 1. Suppose that J ⊆ Nd is ¬nite and ±∈J c± x ± = 0.

0

De¬ne Jk := {± ∈ J : ±1 = k}. Then there exists an n ∈ N0 such that J = J0 ∪ · · · ∪ Jn .

This means that

n n

c± x±1 · · · x±d = c± x±2 · · · x±d .

c± x ± =

0= xk

1

d d

1 2

±∈J k=0 ±∈Jk ±∈Jk

k=0

Thus we can conclude from the univariate case that

c± x±2 · · · x±d = 0, 0 ¤ k ¤ n.

d

2

±∈Jk

By the induction hypothesis we have ¬nally c± = 0 for ± ∈ J .

2.2 Multivariate polynomials 21

Next we come to the space dimension. From the ¬rst part we know that it suf¬ces to show

that

m+d

#{± ∈ Nd : |±| ¤ m} = ,

0

d

when #J denotes the number of elements of the set J . This is done by induction on d. For

d = 1 we have

m+1

#{± ∈ N0 : ± ¤ m} = m + 1 = .

1

Assuming the correctness of this statement for d ’ 1 gives us

m d’1

#{± ∈ Nd : |±| ¤ m} = # ±∈ Nd : ±d = k, ±i ¤ m ’ k

0 0

k=0 i=1

m

= #{± ∈ Nd’1 : |±| ¤ m ’ k}

0

k=0

m

m’k+d ’1

=

d ’1

k=0

m+d

= ,

d

where the last equality comes from Lemma 2.4.

In De¬nition 2.1 we formulated certain conditions for a function space to guarantee

unique interpolation. Now we are in a situation to interpret these conditions as conditions

for the points.

De¬nition 2.6 The points X = {x1 , . . . , x N } ⊆ Rd with N ≥ Q = dim πm (Rd ) are called

πm (Rd )-unisolvent if the zero polynomial is the only polynomial from πm (Rd ) that vanishes

on all of them.

For an example take the linear polynomials on R2 . From Theorem 2.5 we know

that dim π1 (R2 ) = 3. Since every bivariate linear polynomial describes a plane in three-

dimensional space this plane is uniquely determined by three points if and only if these

three points are not collinear. Thus three points in R2 are π1 (R2 )-unisolvent if and only if

they are not collinear.

A generalization of this fact is:

Theorem 2.7 Suppose that {L 0 , . . . , L m } is a set of m + 1 distinct lines in R2 and that

X = {x1 , . . . , x Q } is a set of Q = (m + 1)(m + 2)/2 distinct points such that the ¬rst point

lies on L 0 , the next two points lie on L 1 but not on L 0 , and so on, so that the last m + 1 points

lie on L m but not on any of the previous lines L 0 , . . . , L m’1 . Then X is πm (R2 )-unisolvent.

22 Haar spaces and multivariate polynomials

Proof Use induction on m. For m = 0 the result is trivial. Now take p ∈ πm (R2 ) with

p(xi ) = 0, i = 1, . . . , Q;

then we have to show that p is the zero polynomial.

For each i = 0, . . . , m let the equation of the line L i be given by

±i x1 + βi x2 = γi ,

remembering that x is given by (x1 , x2 )T . Suppose now that p interpolates zero data at all

the points xi as stated above. Since p reduces to a univariate polynomial of degree m on

L m that vanishes at m + 1 distinct points on L m , it follows that p vanishes identically on

L m , and so

p(x) = (±m x1 + βm x2 ’ γm )q(x),

where q is a polynomial of degree m ’ 1. But now q satis¬es the hypothesis of the theorem

with m replaced by m ’ 1 and X replaced by an X consisting of the ¬rst (m + 1)m/2 points

of U . By induction, therefore, q ≡ 0, and thus p ≡ 0.

This theorem can be generalized to Rd by using hyperplanes in Rd and induction on d.

Instead of doing so, we restrict ourselves to the following special case. Let

X m = {β ∈ Nd : |β| ¤ m}.

d

0

This set contains by earlier considerations exactly Q = dim πm (Rd ) points.

Lemma 2.8 The set X m is πm (Rd )-unisolvent. Thus polynomial interpolation of degree m

d

is uniquely possible.

Proof We have to show that the only polynomial p ∈ πm (Rd ) with p(±) = 0 for every

± ∈ Nd with |±| ¤ m is p ≡ 0. This is done by induction on the space dimension d. For

0

d = 1 we have a univariate polynomial of degree m with m + 1 zeros, which can only be

the zero polynomial itself. For the induction step from d ’ 1 to d let us write the polynomial

as

m

j

p(x) = p(x, xd ) = p j (x)xd

j=0

with polynomials p j ∈ πm’ j (Rd’1 ). We are ¬nished if we can show that all the p j are zero.

This is done by induction on m ’ j. To be more precise, we will show that pm’ j ≡ 0 for

0 ¤ j ¤ m and pm’i |X d’1 = 0 for j + 1 ¤ i ¤ m. Let us start with j = 0. Setting x =

j

(0, k) for 0 ¤ k ¤ m we see that (0, k) ∈ X m and that the univariate polynomial p(0, ·) has

d