%% chapter-11.tex %% Approximation Theory: Chapter 11 %% Neal L. Carothers %% Bowling Green State University %% Bowling Green, Ohio 43403 %% carother@math.bgsu.edu %% http://www.bgsu.edu/~carother/ \input 680-setup.tex \chaptertitle = {M\"untz Theorems} \centerline{\hfil\tf The M\"untz Theorems\hfil} \vskip-\baselineskip \line{\sc Math 680 \hfil 7/28/94} \noindent For several weeks now we've taken advantage of the fact that the monomials $1,x,x^2,\ldots$ have {\sl dense linear span\/} in $C[\,0,1\,]$. What, if anything, is so special about these particular powers? How about if we consider polynomials of the form $\sum_{k=0}^na_kx^{k^2}$; are they dense, too? More generally, what can be said about the span of a sequence of monomials $(x^{\lambda_n})$, where $\lambda_0<\lambda_1<\lambda_2<\cdots$? Of course, we'll have to assume that $\lambda_0\ge0$, but it's not hard to see that we will actually need $\lambda_0=0$, for otherwise each of the polynomials $\sum_{k=0}^na_kx^{\lambda_k}$ vanishes at $x=0$ (and so has distance at least $1$ from the constant $1$ function, for example). If the $\lambda_n$'s are integers, it's also clear that we'll have to have $\lambda_n\to\infty$ as $n\to\infty$. But what else is needed? The answer comes to us from M\"untz in 1914. (You sometimes see the name Otto Sz\'asz associated with M\"untz's theorem, because Sz\'asz proved a similar theorem at nearly the same time (1916).) \proclaim Theorem. Let\/ $0\le\lambda_0<\lambda_1<\lambda_2<\cdots$. Then, the functions $(x^{\lambda_n})$ have dense linear span in $C[\,0,1\,]$ if and only if\/ $\lambda_0=0$ and\/ $\sum_{n=1}^\infty\lambda_n^{-1}=\infty$. What M\"untz is trying to tell us here is that the $\lambda_n$'s can't get big too quickly. In particular, the polynomials of the form $\sum_{k=0}^na_kx^{k^2}$ are evidently {\sl not\/} dense in $C[\,0,1\,]$. On the other hand, the $\lambda_n$'s don't have to be unbounded; indeed, M\"untz's theorem implies an earlier result of Bernstein from 1912: If $0<\alpha_1<\alpha_2<\cdots0$. Then, $\displaystyle {\rm dist}(x^m,X_n) \ \le \ \prod_{k=1}^n\left|1-{m\over{\lambda_k}}\right|$. \proof We may certainly assume that $m\ne\lambda_n$ for any $n$. Given this, we inductively define a sequence of functions by setting $P_0(x)=x^m$ and $$P_n(x) \ = \ (\lambda_n-m)\,x^{\lambda_n}\int_x^1t^{-1-\lambda_n}\,P_{n-1}(t)\,dt$$ for $n\ge1$. For example, $$P_1(x) \ = \ (\lambda_1-m)\,x^{\lambda_1}\int_x^1t^{-1-\lambda_1}\,t^m\,dt \ = \ -x^{\lambda_1}\,t^{m-\lambda_1}\bigr]_x^1 \ = \ x^m-x^{\lambda_1}.$$ By induction, each $P_n$ is of the form $x^m-\sum_{k=0}^na_kx^{\lambda_k}$ for some scalars $(a_k)$: $$\eqalign{ P_n(x) \ &= \ (\lambda_n-m)\,x^{\lambda_n}\int_x^1t^{-1-\lambda_n}\,P_{n-1}(t)\,dt\cr &= \ (\lambda_n-m)\,x^{\lambda_n}\int_x^1t^{-1-\lambda_n}\, \left[\,t^m-\sum_{k=0}^{n-1}a_kt^{\lambda_k}\right]\,dt\cr &= \ x^m-x^{\lambda_n}+(\lambda_n-m)\,\sum_{k=0}^{n-1}\, {{a_k}\over{\lambda_n-\lambda_k}}\,(x^{\lambda_k}-x^{\lambda_n}).\cr }$$ Finally, $\Vert P_0\Vert=1$ and $\Vert P_n\Vert\le|1-{m\over{\lambda_n}}|\,\Vert P_{n-1}\Vert$, because $$|\lambda_n-m|\,x^{\lambda_n}\int_x^1t^{-1-\lambda_n}\,dt \ = \ {|\lambda_n-m|\over{\lambda_n}}\,(1-x^{\lambda_n}) \ \le \ \left|1-{m\over{\lambda_n}}\right|.$$ Thus, $${\rm dist}(x^m,X_n) \ \le \ \Vert P_n\Vert \ \le \ \prod_{k=1}^n\left|1-{m\over{\lambda_k}}\right|.\eqno\qed$$ The preceding result is due to v.\ Golitschek. A slightly better estimate, also due to v.\ Golitschek (1970), is \ ${\rm dist}(x^m,X_n)\le\prod_{k=1}^n{{|m-\lambda_k|}\over{m+\lambda_k}}$. Now a well-known fact about infinite products is that for positive $a_k$'s, the product $\prod_{k=1}^\infty\bigl|1-a_k\bigr|$ diverges (to $0$\/) if and only if the series $\sum_{k=1}^\infty a_k$ diverges (to $\infty$\/) if and only if the product $\prod_{k=1}^\infty\bigl|1+a_k\bigr|$ diverges (to $\infty$\/). In particular, $\prod_{k=1}^n\bigl|1-{m\over{\lambda_k}}\bigr|\to0$ if and only if $\sum_{k=1}^n{1\over{\lambda_k}}\to\infty$. That is, ${\rm dist}(x^m,X_n)\to0$ if and only if $\sum_{k=1}^\infty{1\over{\lambda_k}}=\infty$. This proves the ``backward'' direction of M\"untz's theorem. We'll prove the ``forward'' direction of M\"untz's theorem by proving a version of M\"untz's theorem for the space $L_2[\,0,1\,]$. For our purposes, $L_2[\,0,1\,]$ denotes the space $C[\,0,1\,]$ endowed with the norm $$\Vert f\Vert_2 \ = \ \left(\int_0^1|f(x)|^2dx\right)^{1/2},$$ although our results are equally valid in the ``real'' space $L_2[\,0,1\,]$ (consisting of square-integrable, Lebegue measurable functions). In the latter case, we no longer need to assume that $\lambda_0=0$, but we do need to assume that each $\lambda_n>-1/2$ (in order that $x^{2\lambda_n}$ be integrable on $[\,0,1\,]$\/). Remarkably, the distance from $f$ to the span of $x^{\lambda_0},x^{\lambda_1},\ldots,x^{\lambda_n}$ can be computed {\sl exactly\/} in the $L_2$ norm. For this we'll need some more notation: Given linearly independent vectors $f_1,\ldots,f_n$ in an inner product space, we call $$G(f_1,\ldots,f_n) \ = \ \left|\matrix{ \langle\,f_1,f_1\,\rangle &\cdots & \langle\,f_1,f_n\,\rangle\cr \vdots & \ddots & \vdots\cr \langle\,f_n,f_1\,\rangle &\cdots & \langle\,f_n,f_n\,\rangle\cr }\right| \ = \ {\rm det}\bigl[\,\langle\,f_i,f_j\,\rangle\,\bigr]_{i,j}$$ the {\sl Gram determinant\/} of the $f_k$'s. \proclaim Lemma. {\rm(Gram)} \ Let $F$ be a finite dimensional subspace of an inner product space $V$, and let $g\in V\setminus F$. Then, the distance $d$ from $g$ to $F$ is given by $$d^{\,2} \ = \ {{G(g,f_1,\ldots,f_n)}\over{G(f_1,\ldots,f_n)}},$$ where $f_1,\ldots,f_n$ is any basis for $F$. \proof Let $f=\sum_{i=1}^na_if_i$ be the best approximation to $g$ out of $F$. Then, since $g-f$ is orthogonal to $F$, we have, in particular, $\langle\,f_j,g\,\rangle=\langle\,f_j,g\,\rangle$ for all $j$; that is, $$\sum_{i=1}^na_i\langle\,f_j,f_i\,\rangle \ = \ \langle\,f_j,g\,\rangle, \quad j=1,\ldots,n.\eqno(\ast)$$ Since this system of equations always has a unique solution $a_1,\ldots,a_n$, we must have $G(f_1,\ldots,f_n)\ne0$ (and so the formula in our Lemma at least makes sense). Next, notice that $$d^{\,2} \ = \ \langle\,g-f,g-f\,\rangle \ = \ \langle\,g-f,g\,\rangle \ = \ \langle\,g,g\,\rangle \ - \ \langle\,g,f\,\rangle;$$ in other words, $$d^{\,2} \ + \ \sum_{i=1}^na_i\langle\,g,f_i\,\rangle = \ \langle\,g,g\,\rangle.\eqno(\ast\ast)$$ Now consider $(\ast)$ and $(\ast\ast)$ as a system of $n+1$ equations in the $n+1$ unknowns $a_1,\ldots,a_n$, and $d^{\,2}$; in matrix form we have $$\left[\ \matrix{ 1 & \langle\,g,f_1\,\rangle &\cdots & \langle\,g,f_n\,\rangle\cr \noalign{\smallskip} 0 & \langle\,f_1,f_1\,\rangle &\cdots & \langle\,f_1,f_n\,\rangle\cr \vdots & \ddots & \vdots & \vdots\cr 0 & \langle\,f_n,f_1\,\rangle &\cdots & \langle\,f_n,f_n\,\rangle\cr }\ \right]\left[\,\matrix{ d^{\,2}\cr \noalign{\smallskip} a_1\cr \vdots\cr a_n\cr }\,\right] \ = \ \left[\,\matrix{ \langle\,g,g\,\rangle\cr \noalign{\smallskip} \langle\,f_1,g\,\rangle\cr \vdots\cr \langle\,f_n,g\,\rangle\cr }\,\right].$$ Solving for $d^{\,2}$ using Cramer's rule gives the desired result; expanding along the first column shows that the matrix of coefficients has determinant $G(f_1,\ldots,f_n)$, while the matrix obtained by replacing the ``$d$ column'' by the right-hand side has determinant $G(g,f_1,\ldots,f_n)$.~\qed \noindent {\bf Note}: By our last Lemma and induction, every Gram determinant is positive! In what follows, we will still use $X_n$ to denote the span of $x^{\lambda_0},\ldots,x^{\lambda_n}$, but now we'll write ${\rm dist\,}_2(f,X_n)$ to denote the distance from $f$ to $X_n$ in the $L_2$ norm. \proclaim Theorem. Let $m$, $\lambda_k>-1/2$ for $k=0,1,2,\ldots$. Then, $${\rm dist\,}_2(x^m,X_n) \ = \ {1\over\sqrt{2m+1}}\,\prod_{k=0}^n{{|m-\lambda_k|}\over{m+\lambda_k+1}}.$$ \proof The proof is based on a determinant formula due to Cauchy: $$\prod_{i,j}(a_i+b_j)\,\left|\,\matrix{ {1\over{a_1+b_1}} & \cdots & {1\over{a_1+b_n}}\cr \vdots & \ddots & \vdots\cr \noalign{\medskip} {1\over{a_n+b_1}} & \cdots & {1\over{a_n+b_n}}\cr }\,\right| \ = \ \prod_{i>j}(a_i-a_j)(b_i-b_j).$$ If we consider each of the $a_i$'s and $b_j$'s as ``variables,'' then each side of the equation is a {\sl polynomial\/} in $a_1,\ldots,a_n,b_1,\ldots,b_n$. (Why?) Now the right-hand side clearly vanishes if $a_i=a_j$ or $b_i=b_j$ for some $i\ne j$, but the left-hand side also vanishes in any of these cases. Thus, the right-hand side divides the left-hand side. But both polynomials have degree $n-1$ in each of the $a_i$'s and $b_j$'s. (Why?) Thus, the left-hand side is a constant multiple of the right-hand side. To show that the constant must be $1$, write the left-hand side as $$\prod_{i\ne j}(a_i+b_j)\,\left|\,\matrix{ 1 & {{a_1+b_1}\over{a_1+b_2}} & \cdots & {{a_1+b_1}\over{a_1+b_n}}\cr \noalign{\medskip} {{a_2+b_2}\over{a_2+b_1}} & 1 & \cdots & {{a_2+b_2}\over{a_2+b_n}}\cr \vdots && \ddots & \vdots\cr \noalign{\medskip} {{a_n+b_n}\over{a_n+b_1}} & \cdots & {{a_n+b_n}\over{a_n+b_{n-1}}} & 1\cr }\,\right|$$ and now take the limit as $b_1\to-a_1$, $b_2\to-a_2$, etc. The expression above tends to $\prod_{i\ne j}(a_i-a_j)$, as does the right-hand side of Cauchy's formula. Now, $\langle\,x^p,x^q\,\rangle = \int_0^1x^{p+q}\,dx={1\over{p+q+1}}$ for $p$, $q>-1/2$, so $$G(x^{\lambda_0},\ldots,x^{\lambda_n}) \ = \ {\rm det}\left(\left[{1\over{\lambda_i+\lambda_j+1}}\right]_{i,j}\right) \ = \ {{\prod_{i>j}(\lambda_i-\lambda_j)^2} \over{\prod_{i,j}(\lambda_i+\lambda_j+1)}},$$ with a similar formula holding for $G(x^m,x^{\lambda_0},\ldots,x^{\lambda_n})$. Substituting these expressions into our distance formula and taking square roots finishes the proof.~\qed Now we can determine exactly when $X$ is dense in $L_2[\,0,1\,]$. For easier comparison to the $C[\,0,1\,]$ case, we suppose that the $\lambda_n$'s are nonnegative. \proclaim Theorem. Let\/ $0\le\lambda_0<\lambda_1<\lambda_2<\cdots$. Then, the functions $(x^{\lambda_n})$ have dense linear span in $L_2[\,0,1\,]$ if and only if\/ $\sum_{n=1}^\infty\lambda_n^{-1}=\infty$. \proof If $\sum_{n=1}^\infty{1\over{\lambda_n}}<\infty$, then each of the products $\prod_{k=1}^n\bigl|1-{m\over{\lambda_k}}\bigr|$ and $\prod_{k=1}^n\bigl|1+{{(m+1)}\over{\lambda_k}}\bigr|$ converges to some nonzero limit for any $m$ not equal to any $\lambda_k$. Thus, ${\rm dist\,}_2(x^m,X_n)\not\to0$, as $n\to\infty$, for any $m\ne\lambda_k$, $k=0,1,2,\ldots$. In particular, the functions $(x^{\lambda_n})$ cannot have dense linear span in $L_2[\,0,1\,]$. Conversely, if $\sum_{n=1}^\infty{1\over{\lambda_n}}=\infty$, then $\prod_{k=1}^n\bigl|1-{m\over{\lambda_k}}\bigr|$ diverges to $0$ while $\prod_{k=1}^n\bigl|1+{{(m+1)}\over{\lambda_k}}\bigr|$ diverges to $+\infty$. Thus, ${\rm dist\,}_2(x^m,X_n)\to0$, as $n\to\infty$, for every $m>-1/2$. Since the polynomials are dense in $L_2[\,0,1\,]$, this finishes the proof.~\qed Finally, we can finish the proof of M\"untz's theorem in the case of $C[\,0,1\,]$. Suppose that the functions $(x^{\lambda_n})$ have dense linear span in $C[\,0,1\,]$. Then, since $\Vert f\Vert_2\le\Vert f\Vert$, it follows that the functions $(x^{\lambda_n})$ must also have dense linear span in $L_2[\,0,1\,]$. (Why?) Hence, $\sum_{n=1}^\infty{1\over{\lambda_n}}=\infty$.~\qed Just for good measure, here's a second proof of the ``backward'' direction for $C[\,0,1\,]$ based on the $L_2[\,0,1\,]$ version. Suppose that $\sum_{n=1}^\infty{1\over{\lambda_n}}=\infty$, and let $m\ge1$. Then, $$\openup2\jot\eqalignno{ \left|\,x^m-\sum_{k=0}^na_kx^{\lambda_k}\,\right| \ & = \ \left|\,{1\over m}\int_0^xt^{m-1}\,dt -\sum_{k=0}^n{{a_k}\over{\lambda_k}}\int_0^xt^{\lambda_k-1}\,dt\,\right|\cr &\le \ \int_0^1\left|\,{1\over m}\,t^{m-1} -\sum_{k=0}^n{{a_k}\over{\lambda_k}}\,t^{\lambda_k-1}\,\right|\,dt\cr &\le \ \left(\int_0^1\left|\,{1\over m}\,t^{m-1} -\sum_{k=0}^n{{a_k}\over{\lambda_k}}\,t^{\lambda_k-1}\, \right|^2dt\right)^{1/2}.\cr }$$ Now the functions $(x^{\lambda_k-1})$ have dense linear span in $L_2[\,0,1\,]$ because $\sum_{\lambda_n>1}{1\over{\lambda_n-1}}=\infty$. Thus, we can find $a_k$'s so that the right-hand side of this inequality is less than some $\eps$. Since this estimate is independent of $x$, we've shown that $$\Max_{\strut 0\le x\le1} \left|\,x^m-\sum_{k=0}^na_kx^{\lambda_k}\,\right|<\eps. \eqno\qed$$ \proclaim Application. Let $0=\lambda_0<\lambda_1<\lambda_2<\cdots$ with $\sum_{n=1}^\infty \lambda_n^{-1}=\infty$, and let $f$ be a continuous function on $[\,0,\infty)$ for which $c=\lim\limits_{t\to\infty}f(t)$ exists. Then, $f$ can be uniformly approximated by finite linear combinations of the exponentials $(e^{-\lambda_nt})_{n=0}^\infty$. \proof The function $g(x)=f(-\log x)$, for $00$, we can find $n$ and $a_0,\ldots,a_n$ such that $$\max_{\strut 0\le x\le1}\left|g(x)-\sum_{k=0}^na_kx^{\lambda_k}\right| \ = \ \max_{\strut 0\le t<\infty}\left|f(t)-\sum_{k=0}^na_ke^{-\lambda_kt}\right| \ < \ \eps.\eqno\qed$$ \bye %% end of chapter-11.tex