Prove Lemma 20.6. Hint: Step 1: Partition [0, 1]d into d-dimensional rectangles A1,...,AK with the following properties:
(i) ‑ Ai α1+···+αd=k k! α1!·...·αd! ∂kf ∂xα1 1 ...∂xαd d (x) 2 dx ≤ c(δ/√c) d/k, (i = 1,...,K);
(ii) supx,z∈Ai ||x − z||∞ ≤ (δ/√c) 1/k (i = 1,...,K); and
(iii) K ≤ ((√c/δ) 1/k + 1)d + (√c/δ) d/k.
To do this, start by dividing [0, 1]d into K˜ ≤ ((√c/δ) 1/k + 1)d equi-volume cubes B1,...,BK˜ of side length (δ/√c) 1/k. Then partition each cube Bi into d-dimensional rectangles Bi,1,...,Bi,li such that, for j = 1,...,li − 1,
Bi,j α1+···+αd=k k! α1! · ... · αd! ∂kf ∂xα1 1 ... ∂xαd d (x) 2 dx = c(δ/√c) d/k,
and, for j = li, Bi,j α1+···+αd=k k! α1! · ... · αd! ∂kf ∂xα1 1 ... ∂xαd d (x) 2 dx ≤ c(δ/√c) d/k.
Step 2: Approximate f on each rectangle Ai by a polynomial of total degree k − 1. Fix 1 ≤ i ≤ K. Use the Sobolev integral identity, see Oden and Reddy (1976), Theorem 3.6, which implies that there exists a polynomial pi of total degree not exceeding k−1 and an infinitely differentiable bounded function Qα(x, y) such that, for all x ∈ Ai,
, for all x ∈ Ai, |f(x) − pi(x)| = Ai 1 ||x − z||d−k 2 α1+···+αd=k Qα(x, z) ∂kf ∂xα1 1 ... ∂xαd d (z) dz.
Use this to conclude
Np((√c0d(k−d) + 1)δ, F, xn 1 ) ≤ Np(δ, TLG, xn 1 ),
where TLG = {TLg : g ∈ G} and G is the set of all piecewise polynomials of total degree less than or equal to k − 1 with respect to a rectangular partition of [0, 1]d consisting of at most K ≤ (2d + 1)(√c/δ) d/k + 2d rectangles. Step 3: Use the results of Chapters 9 and 13 to bound Np(δ, TLG, xn 1 ).