\count100=1\input at03.tex \title{On the Spacing of Fekete Points} \titwo{for a Sphere, Ball or Simplex} \author{Len Bos, Norm Levenberg and Shayne Waldron} \def\shorttitle{On the Spacing of Multivariate Fekete Points} \def\shortauthor{L.~Bos, N.~Levenberg and S.~Waldron} %************************* ABSTRACT ********************************** \abstract {Suppose that $K\subset\RR^d$ is either the unit ball, the unit sphere or the standard simplex. We show that there are constants $c_1,c_2>0$ such that for a set of Fekete points (maximizing the Vandermonde determinant) of degree $n,$ $F_n\subset K,$ $${c_1\over n}\le \min_{b\in F_n\atop b\neq a} \hbox{dist}(a,b)\le {c_2\over n},\quad\forall a\in F_n$$ where $\hbox{dist}(a,b)$ is a natural distance on $K$ that will be described in the text. } %******************************* BODY ********************************* \sect{1. Introduction.} The Fekete points are a set of good (often excellent) points for polynomial interpolation that are defined for any compact set $K\subset\RR^d.$ In one variable, for $K=[-1,1],$ the Fekete points have been much studied. Fej\'er [5] showed that the set of Fekete points for interpolation by polynomials of degree $n,$ $F_n,$ consists of $-1,+1$ together with the extreme points of the $n$th Legendre polynomial. S\"undermann [8] subsequently showed that the the so-called Lebesgue constants grow $O(\log(n)),$ which is best possible. This confirms that the Fekete points for the interval are indeed excellent interpolation points. From Fej\'er's result in particular, it follows that they are asymptotically nearly equally spaced with respect to the arcsin metric, $${\rm dist}(a,b)=|\cos^{-1}(b)-\cos^{-1}(a)|. \eqno(1)$$ In other words, for each $a\in F_n,$ $$\min_{b\in F_n\atop b\neq a}{\rm dist}(a,b)\approx {c\over n}$$ for some constant $c.$ In contrast, as the Fekete points are more dense near the endpoints (just as are the Chebyshev points, for example), in the usual euclidean distance, there are points $a\in F_n$ for which $$\min_{b\in F_n\atop b\neq a}|b-a|\approx {c\over n^2}.$$ More generally, K\"ovari and Pommerenke[7] have discussed the spacing of complex Fekete points for $K\subset \CC,$ a continuum. In several variables, up to now, very little has been known about the spacing of the Fekete points, and it is the purpose of this note to provide some information on this topic. In order to make these notions more precise, suppose that $K\subset\RR^d$ is a compact set. The polynomials of degree at most $n$ in $d$ real variables, when restricted to $K,$ form a certain vector space which we will denote by ${\cal P}_n(K).$ (For example, if $K=S^{d-1}$ is a sphere, then ${\cal P}_n(K)$ will be the {\it spherical} polynomials. If $K\subset \RR^d$ has a non-empty interior then ${\cal P}_n(K)$ will be all {\it algebraic} polynomials of degree $n$ in $d$ variables.) The space ${\cal P}_n(K)$ has a dimension $N_n:={\rm dim}({\cal P}_n(K)).$ The polynomial interpolation problem for $K$ is then, given a set of $N_n$ distinct points $A_n\subset K$ and a function $f\,:\,K\to\RR,$ to find a polynomial $p\in {\cal P}_n(K)$ such that $$p(a)=f(a),\quad \forall a\in A_n.\eqno(2)$$ In one dimension ($d=1$), there is always a unique solution to the problem (2). However, in higher dimensions ($d>1$), depending on the geometry of the interpolation points $A_n,$ it may be that it is not possible to find a solution to (2). To see why this is so, consider a basis $$B_n=\{P_1,P_2,\cdots, P_{N_n}\}$$ of ${\cal P}_n(K).$ Then any polynomial $p\in {\cal P}_n(K)$ may be written in the form $$p=\sum_{j=1}^{N_n}c_jP_j$$ for some constants $c_j\in\RR.$ Hence the conditions (2) may be expressed as $$p(a)=\sum_{j=1}^{N_n}c_jP_j(a)=f(a),\quad a\in A_n \eqno(3)$$ which are exactly $N_n$ linear equations in $N_n$ unknowns $c_j.$ In matrix form this becomes $$[P(a)]_{P\in B_n,a\in A_n}c=F$$ where $c\in\RR^{N_n}$ is the vector formed of the $c_j$ and $F$ is the vector of function values $f(a),$ $a\in A_n.$ This linear system has a unique solution precisely when the so-called Vandermonde determinant $${\rm vdm}(A_n;B_n):={\rm det}([P(a)]_{P\in B_n,a\in A_n})\neq 0.$$ If this is the case, then the interpolation problem (2) is said to be {\it correct} (or sometimes {\it univsolvent}). Note that ${\rm vdm}(A_n;B_n)= 0$ precisely when the interpolation points $A_n$ all lie on an algebraic variety of degree $n$ and hence the generic situation is that the interpolation problem is indeed correct. We will assume that this is the case throughout. Note further that correctness depends only on the set of interpolation points $A_n$ and {\it not} on the particular basis $B_n$ chosen. Supposing then that the interpolation problem (2) is correct, we may write the interpolating polynomial in so-called Lagrange form as follows. For $a\in A_n$ set $$\ell_a(x):={{\rm vdm}(A_n\backslash\{a\}\cup \{x\};B_n)\over {\rm vdm}(A_n;B_n)}. \eqno(4)$$ A brief explanation of this formula is in order. The numerator is but the Vandermonde determinant with the interpolation point $a\in A_n$ replaced by the variable $x\in\RR^d.$ Then, expanding ${\rm vdm}(A_n\backslash\{a\}\cup \{x\};B_n)$ along the row corresponding to $x,$ we see that $\ell_a(x)$ is a linear combination of the $P_j$ and hence $\ell_a\in {\cal P}_n(K).$ Further, it is easy to see that $\ell_a(b)=\delta_{ab},$ the Kronecker delta, for $b\in A_n.$ The $\ell_a$ are called the Fundamental Lagrange Interpolating Polynomials and using them we may write the interpolant of (2) as $$p(x)=\sum_{a\in A_n}f(a)\ell_a(x).\eqno(5)$$ The mapping $f\to p$ is a projection and hence we sometimes write $p=L_{A_n}(f).$ If we regard both $f,p\in C(K)$ then the operator $L_{A_n}$ has operator norm (as is not difficult to see) $$\|L_{A_n}\|=\max_{x\in K}\sum_{a\in A_n}|\ell_a(x)|.$$ This operator norm (sometimes called the Lebesgue constant) gives a bound on how far the interpolant is from the best uniform polynomial approximant to $f.$ To see this, for any $q\in {\cal P}_n(K),$ write $$\eqalign{\|f-p\|_K&=\|f-L_{A_n}(f)\|_K\cr &=\|f-q-L_{A_n}(f-q)\|_K\cr &\le\|f-q\|_K+\|L_{A_n}(f-q)\|_K\cr &\le\|f-q\|_K+\|L_{A_n}\|_K\|f-q\|_K\cr &=(1+\|L_{A_n}\|)\|f-q\|_K }$$ so that $$\|f-p\|_K\le(1+\|L_{A_n}\|)\inf_{q\in {\cal P}_n(K)}\|f-q\|_K.$$ It follows that the quality of approximation to $f$ provided by the interpolant $p$ is determined by the size of $\|L_{A_n}\|,$ the smaller it is the better. Now, suppose that $F_n\subset K$ is a subset of $N_n$ distinct points for which $A_n=F_n$ maximizes $|{\rm vdm}(A_n;B_n)|.$ Then by (4), each $$\|\ell_a\|_K\le 1, \quad a\in F_n \eqno(6)$$ and hence the corresponding Lebesgue constants are such that $$\|L_{A_n}\|_K\le N_n,$$ i.e., the Lebesgue constants grow polynomially in $n,$ which is the best that is known in general. The set $F_n$ is called a set of Fekete points of degree $n$ for $K$ and provide, for any $K,$ a good (often excellent) set of interpolation points. In this work we will show that for $K\subset\RR^d,$ either a sphere, ball or simplex, and for the appropriate analogue of the arcsin metric (1) there are constants $c_1,c_2>0$ such that $${c_1\over n}\le \min_{b\in F_n\atop b\neq a} \hbox{dist}(a,b)\le {c_2\over n}.$$ Finally, we mention that there is another notion of Fekete points that appears in the literature, i.e., where they maximize some discrete potential function, and the reader should be careful not to confuse such points with the ones we consider here. \sect{2. The Baran and Dubiner Distances} The generalizations of the arcsin distance (1) that we will use are the Baran and Dubiner distances studied in [1,2]. First, we recall for a compact set $K\subset \CC^d$, the function $$V_K(z):=\sup\{\log ({|p(z)|^{1/{\rm deg}(p)}})\,:\,p: \CC^d\to \CC,\, \hbox{deg}(p)\ge 1,\,||p||_K\le1\}$$ is known as the Siciak-Zaharjuta extremal function (see the monograph by Klimek [6] for more detail). If $V_K(z)$ is finite, which it is for all $z\in \CC^d$ when $K=\overline \Omega\subset \RR^d$ where $\Omega$ is a domain, then for any polynomial $p$ and any point $z$, from the definition of $V_K$ we have the Bernstein-Walsh inequality $$|p(z)|\le e^{{\rm deg}(p)V_K(z)}||p||_K. $$ \proclaim Definition 1. Suppose that $K=\overline{\Omega}$ where $\Omega\subset\RR^d$ is a bounded domain. Then $$\delta_B(x;y):=\limsup_{t\to 0^+}{V_K(x+ity)\over t},$$ (for $x\in \Omega$ and $y\in \RR^N$) defined for compacta $K$ for which it is uppersemicontinuous (usc), is the {\it Baran pseudometric for $K$} and $${\rm dist}_B(a,b) =\inf_\gamma \int_0^1 \delta_B(\gamma(t);\gamma'(t))dt$$ where the $\inf$ is taken over all parameteric curves $\gamma\,:\,[0,1]\to K$ with $\gamma(0)=a$ and $\gamma(1)=b,$ is the {\it Baran} distance for $K.$ \vskip6pt We remark, that from the results of [3], $\delta_B$ is continuous for $x\in K^o$ if $K$ is an arbitrary convex body. Moreover, in this case, the limit in the definition of $\delta_B$ exists. \vskip6pt \proclaim Definition 2. Suppose that $K\subset\RR^d$ is compact. Then $${\rm dist}_D(a,b):=\sup_{||p||_K\leq 1, \ {\rm deg}p\geq 1} {1\over {\rm deg}p}|\cos^{-1}(p(b))-\cos^{-1}(p(a))|$$ is the {\it Dubiner} distance on $K$. \vskip6pt Note that ${\rm dist}_B(a,b)$ is only well-defined for compact sets which are the closure of a domain, and hence not for a sphere. However, ${\rm dist}_D(a,b)$ is well-defined for any compact set $K\subset\RR^d,$ including the sphere. It turns out that, when both are well defined, it is always the case that $${\rm dist}_D(a,b)\le {\rm dist}_B(a,b). \eqno(7)$$ For the proof of this and also other properties of these distances we refer the reader to [1,2]. Of importance to us here will be the following general theorem, given by Dubiner [4]. \proclaim Theorem 1 (Dubiner). Suppose that $K\subset \RR^d$ is compact and that $F_n\subset K$ is a set of Fekete points of degree $n.$ Then, for all $a\in F_n,$ $${\pi \over 2}{1\over n}\le \min_{b\in F_n\atop b\neq a} {\rm dist}_D(a,b). \eqno(8)$$ \noindent {\bf Proof.} Consider $p=\ell_a,$ the Lagrange polynomial of degree $n$ for $a.$ Then by (6), $\|\ell_a\|_K\le 1$ and so $p=\ell_a$ is a candidate in the supremum defining the Dubiner distance. Hence, for any $a\neq b\in F_n,$ $$\eqalign{{\rm dist}(a,b)&\ge {1\over n} |\cos^{-1}(\ell_a(b))-\cos^{-1}(\ell_a(a))|\cr &={1\over n}|\cos^{-1}(0)-\cos^{-1}(1)|\cr &={1\over n}{\pi\over 2}.}$$ \eop \sect{3. The Spacing of Fekete Points on the Sphere} We take $K=S^{d-1}\subset\RR^d$ the unit sphere. In this case the Dubiner distance is just the geodesic distance on the sphere (cf. [1]), i.e., for $a,b\in S^{d-1},$ $${\rm dist}_D(a,b)={\rm dist}(a,b)=\cos^{-1}(a\cdot b).$$ \proclaim Theorem 2. There are constants $c_1=\pi/2$ and $c_2>0$ such that if $F_n\subset S^{d-1}$ is a set of Fekete points of degree $n,$ then for all $a\in F_n,$ $${c_1\over n}\le \min_{b\in F_n\atop b\neq a}{\rm dist}(a,b)\le {c_2\over n}.$$ \vskip6pt \noindent {\bf Proof.} The lower bound is given immediately by Theorem 1. To show the upper bound, we will make use of the polynomial provided by the following lemma. \proclaim Lemma 1. There is a constant $c>0$ such that for all integers $n\ge1$ and points $A\in S^{d-1},$ there exists a spherical polynomial $P\in {\cal P}_n(S^{d-1})$ of degree at most $n$ such that (a) $P(A)=1$ and (b) $$|P(x)|\le {c\over n^d}{\rm dist}(A,x)^{-d},\quad x\in S^{d-1}.\eqno(9)$$ \noindent {\bf Proof.} Let $\phi\in[0,\pi]$ be the angle between $x\in S^{d-1}$ and the point $A$ so that $\cos(\phi)=A\cdot x.$ Note that then $\phi={\rm dist}(x,A).$ For $m:=\lfloor n/d\rfloor$ set $$\eqalign{Q(x)&={2\over 2m+1}\left\{{1\over 2}+\cos(\phi)+\cos(2\phi)+\cdots +\cos(m\phi)\right\}\cr &={1\over 2m+1}{\sin\left({2m+1\over2}\phi\right)\over\sin\left({\phi\over2} \right)}.}\eqno(10)$$ Then $P(x):=Q(x)^d$ has the desired properties. \eop \vskip6pt Continuing, fix $a\in F_n$ and let $a^*\in F_n$ be a closest Fekete point to $a.$ Then choose $A\in S^{d-1}$ so that ${\rm dist}(a,A)={1\over2}{\rm dist}(a,a^*).$ In particular, $A\notin F_n.$ Then, for all $b\in F_n,$ $b\neq a,$ $$\eqalignno{{\rm dist}(b,A)&\ge {\rm dist}(b,a)-{\rm dist}(a,A)\cr &={\rm dist}(b,a)-{1\over2}{\rm dist}(a,a^*)\cr &={1\over2}{\rm dist}(b,a)+{1\over2}\{{\rm dist}(a,b)-{\rm dist}(a,a^*)\}\cr &\ge{1\over2}{\rm dist}(b,a)&(11)\cr}$$ as ${\rm dist}(a,b)\ge {\rm dist}(a,a^*)$ by the definition of $a^*.$ Now let $P(x)$ be the polynomial of degree $n$ provided by Lemma 1 for the point $A.$ We may write $$P(x)=\sum_{b\in F_n}P(b)\ell_b(x)$$ so that at $x=A,$ $$1=P(A)=\sum_{b\in F_n}P(b)\ell_b(A).$$ Taking absolute values, it follows that $$\eqalignno{1&\le \sum_{b\in F_n}|P(b)|\qquad\hbox{by (6)}\cr &\le {c\over n^d}\sum_{b\in F_n} {\rm dist}(b,A)^{-d}\qquad\hbox{by (9)}\cr &= {c\over n^d}\left\{{\rm dist}(a,A)^{-d}+\sum_{b\in F_n\atop b\neq a} {\rm dist}(b,A)^{-d}\right\}\cr &={c\over n^d}\left\{2^d{\rm dist}(a,a^*)^{-d}+\sum_{b\in F_n\atop b\neq a} {\rm dist}(b,A)^{-d}\right\}\quad\hbox{by the choice of $A$}\cr &\le {c\over n^d}\left\{2^d{\rm dist}(a,a^*)^{-d}+\sum_{b\in F_n\atop b\neq a} 2^d{\rm dist}(b,a)^{-d}\right\}\quad\hbox{by (11)}\cr &=2^d{c\over n^d}\left\{{\rm dist}(a,a^*)^{-d}+\sum_{b\in F_n\atop b\neq a} {\rm dist}(b,a)^{-d}\right\}.&(12)\cr } $$ To estimate the sum in (12) we partition $S^{d-1}$ it into ``strips'' $$\eqalign{S_0&:=\left\{b\in S^{d-1}\,\mid \, {\rm dist}(b,a)\le {1\over2} {\rm dist}(a,a^*)\right\},\cr S_j&:=\left\{b\in S^{d-1}\,\mid\,{1\over 2}{\rm dist}(a,a^*)+{j-1\over n}< {\rm dist}(a,b)\le {1\over 2}{\rm dist}(a,a^*)+{j\over n}\right\}}$$ where $j$ is such that $\displaystyle{{1\over2}{\rm dist}(a,a^*)+{j-1\over n}<\pi}$ (the maximum distance). It is convenient to denote $$\lambda:=n\left({1\over2}{\rm dist}(a,a^*)\right)$$ so that $$S_j=\left\{b\in S^{d-1}\,\mid\,{\lambda +j-1\over n}<{\rm dist}(a,b)\le {\lambda+j\over n}\right\}.$$ Note that $S_0\cap F_n=\{a\}$ as ${\rm dist}(a,a^*)$ is minimal. Further, for $S_j,$ we may compute its surface `area' as $$\eqalign{V_{d-1}(S_j)&=c\int_{(\lambda +j-1)/n}^{(\lambda+j)/n}\sin^{d-2}(\phi)d\phi\qquad\hbox{for some constant $c$}\cr &=c\left\{{\lambda+j\over n}-{\lambda+j-1\over n}\right\}\sin^{d-2}(\phi_j)\quad\hbox{for a $\phi_j\in [{\lambda+j-1\over n},{\lambda+j\over n}]$}\cr &={c\over n}\sin^{d-2}(\phi_j)\cr &\le {c\over n}\phi_j^{d-2}\qquad\hbox{as $\sin(\theta)\le\theta$}\cr &\le {c\over n}\left({\lambda+j\over n}\right)^{d-2}\quad \hbox{as $\phi_j\le (\lambda+j)/n$}\cr &={c\over n^{d-1}}(\lambda+j)^{d-2}. }$$ But, as there is the minimal spacing, $${\rm dist}(b,b^*)\ge {c_1\over n},$$ for $b\in F_n$ and $B^*\in F_n$ a closest point to $b,$ there are no other Fekete points in the `disk' $\{x\in S^{d-1}\,|\,{\rm dist}(x,b)0$ such that if $F_n\subset B^d$ is a set of Fekete points of degree $n,$ then for all $a\in F_n,$ $${c_1\over n}\le \min_{b\in F_n\atop b\neq a}{\rm dist}(a,b)\le {c_2\over n}.$$ \vskip6pt \noindent {\bf Proof.} The lower bound is given immediately by Theorem 1. To show the upper bound, we will make use of a polynomial analogous to that provided by Lemma 1. We will first need to establish a technical result. \proclaim Lemma 2. Suppose that $q(\phi)$ is the trigonometric polynomial given by (10). Then for $\phi\in [0,\pi],$ $$q(\phi)\ge -1/2.$$ \noindent{\bf Proof.} If $q(\phi)\ge 0$ we need proceed no further, and hence we need only consider $\phi$ for which $q(\phi)\le 0.$ But $$q(\phi)={1\over 2m+1}{\sin\left({2m+1\over2}\phi\right)\over\sin\left({\phi\over2} \right)}$$ and hence it changes sign at $\phi_k:=2k\pi/(2m+1),$ $k=1,2,\cdots m.$ Specifically, $q(\phi)\le 0$ on the intervals $[2k\pi/(2m+1),2(k+1)\pi/(2m+1)]$ for {\sl odd} $k.$ On such an interval, $$\eqalign{|q(\phi)|&\le \left({1\over 2m+1}\right){1\over \sin(k\pi/(2m+1)}\cr &\le \left({1\over 2m+1}\right){1\over (2/\pi)k\pi/(2m+1)},}$$ using the fact that $\sin(\theta)\le {2\over\pi}\theta,$ for $\theta\in [0,\pi/2].$ Hence on the interval $[2k\pi/(2m+1),2(k+1)\pi/(2m+1)],$ $|q(\phi)|\le 1/(2k)\le 1/2.$ \eop \proclaim Lemma 3. There is a constant $c>0$ such that for all integers $n\ge1$ and points $A\in B^d,$ there exists an algebraic polynomial $P$ of degree at most $n$ such that (a) $P(A)=1$ and (b) $$|P(x)|\le {c\over n^{d+1}}{\rm dist}(A,x)^{-(d+1)},\quad x\in B^d.$$ \noindent {\bf Proof.} For a point ${\widetilde x}\in S^d$ write ${\widetilde x}=(x,z)$ where $x\in B^d$ and $z\in\RR.$ Let $Q({\widetilde x})$ be the spherical polynomial on $S^d$ given by (10), where $\phi$ is the angle between ${\widetilde x}\in S^d$ and ${\widetilde A}\in S^d$ and $m=\lfloor n/(d+1)\rfloor.$ Note that for $x\in B^d,$ $Q(x,z)^{d+1}+Q(x,-z)^{d+1}$ is even in $z$ and hence a function of $z^2=1-|x|^2,$ on $S^d.$ Hence $$P(x)=Q(x,z)^{d+1}+Q(x,-z)^{d+1}$$ is an algebraic polynomial in $x.$ We claim that it has (essentially) the required properties. First note that by Lemma 2, $P(A)\ge 1-2^{-(d+1)}>0$ and hence property (a) follows from a constant re-normalization. To see property (b) just note that $$\eqalign{{\rm dist}_{S^d} ((x,\pm z),\widetilde{A})&=\cos^{-1}(x\cdot A \pm z\sqrt{1-|A|^2})\cr &\ge \cos^{-1}(x\cdot A +|z|\sqrt{1-|A|^2})\cr &=\cos^{-1}(x\cdot A +\sqrt{1-|x|^2}\sqrt{1-|A|^2})\cr &={\rm dist}(x,A).}$$ Hence both $Q(x,z)^{d+1}$ and $Q(x,-z)^{d+1}$ are bounded by $${c\over n^{d+1}}{\rm dist}(x,A)^{-(d+1)}.$$ \eop \vskip6pt The proof of Theorem 3 is now exactly the same as for Theorem 2, except in one dimension higher, using the polynomial $P(x)$ provided by Lemma 3. The volumes of the strips $S_j$ are measured using the measure $d\mu$ of (14) to yield (13). We omit the details. \eop \sect{5. The Spacing of Fekete Points on the Simplex} We now take $K=T^d\subset\RR^d$ the standard simplex, i.e., $$T^d:=\{x\in\RR^d\,\mid\, x_i\ge0,\,i=1,\cdots,d,\,\,{\rm and}\,\,\sum_{i=1}^dx_i\le1\}.$$ In this case the Baran distance (cf. [1,2]) is described as follows. For $a\in T^d,$ set $$\widetilde{a}:=(\sqrt{a_1},\sqrt{a_2},\cdots,\sqrt{a_d},\sqrt{1-\sum_{i=1}^da_i})\in S^{d}\subset R^{d+1}.$$ Then, for $a,b\in T^d,$ $$\eqalign{{\rm dist}_B(a,b)&=2{\rm dist}_{S^d}(\widetilde{a},\widetilde{b})\cr &=2\cos^{-1}(\widetilde{a}\cdot \widetilde{b}).}$$ We remark that the surface area measure on $S^d$ pulls back under the mapping $a\to\widetilde{a}$ to a measure on $T^d,$ $$d\mu=c{1\over\sqrt{x_1x_2\cdots x_d(1-\sum_{i=1}^d x_i)}}dx\eqno(15)$$ where $c$ is a normalizing constant. A closed form equation for the Dubiner distance is not known, but one will not be needed here. \proclaim Theorem 4. There are constants $c_1=\pi/2$ and $c_2>0$ such that if $F_n\subset T^d$ is a set of Fekete points of degree $n,$ then for all $a\in F_n,$ $${c_1\over n}\le \min_{b\in F_n\atop b\neq a}{\rm dist}_D(a,b) \le \min_{b\in F_n\atop b\neq a}{\rm dist}_B(a,b)\le {c_2\over n}.$$ \vskip6pt \noindent {\bf Proof.} The lower bound is given immediately by Theorem 1. To show the upper bound, we will again make use a polynomial analogous to that provided by Lemmas 1 and 3. \proclaim Lemma 4. There is a constant $c>0$ such that for all integers $n\ge1$ and points $A\in T^d,$ there exists an algebraic polynomial $P$ of degree at most $n$ such that (a) $P(A)=1$ and (b) $$|P(x)|\le {c\over n^{d+1}}{\rm dist}_B(A,x)^{-(d+1)},\quad x\in T^d.$$ \noindent{\bf Proof.} We let ${\widetilde x}$ denote a point in $S^d.$ Then, let $Q({\widetilde x})$ be the spherical polynomial on $S^d$ given by (10), where $\phi$ is the angle between ${\widetilde x}\in S^d$ and ${\widetilde A}\in S^d$ and $m=\lfloor 2n/(d+1)\rfloor.$ Now, let ${\cal M}$ denote the set of $(d+1)\times(d+1)$ diagonal matrices with $\pm 1$ on the diagonal. There are $\#{\cal M}=2^{d+1}$ elements in ${\cal M}.$ Then, set $${\widetilde P}({\widetilde x}):=\sum_{M\in {\cal M}}Q(M{\widetilde x})^{d+1}.$$ ${\widetilde P}({\widetilde x})$ is a polynomial of degree at most $2n$ in ${\widetilde x}$ that is symmetric under each of the mappings ${\widetilde x}_i\to-{\widetilde x}_i.$ Hence it is actually a polynomial in the ${\widetilde x}_i^2.$ Then, as ${\widetilde x}_i=\sqrt{x_i}$ $1\le i\le d$ and ${\widetilde x}_{d+1}=\sqrt{1-\sum_{i=1}^dx_i},$ $$P(x):={\widetilde P}({\widetilde x})$$ is an algebraic polynomial of degree at most $n$ in $x.$ We claim that $P(x)$ (essentially) satisfies the desired properties. First note that $$\eqalign{P(A)&=\sum_{M\in {\cal M}}Q(M{\widetilde A})^{d+1}\cr &=Q({\widetilde A})^{d+1}+ \sum_{M\in {\cal M}\atop M\neq I}Q(M{\widetilde A})^{d+1}\cr &=1+\sum_{M\in {\cal M}\atop M\neq I}Q(M{\widetilde A})^{d+1}\cr &\ge 1-\sum_{M\in {\cal M}\atop M\neq I}(1/2)^{d+1}\quad\hbox{by Lemma 2}\cr &=1-(2^{d+1}-1)2^{-(d+1)}\cr &=2^{-(d+1)}>0. }$$ Thus property (a) is attained by a renormalization. To see property (b), note that for each $M\in{\cal M}$ and \break $\widetilde{x}:=(\sqrt{x_1},\sqrt{x_2},\cdots,\sqrt{x_d},\sqrt{1-\sum_{i=1}^dx_i})$ $$(M{\widetilde x})\cdot {\widetilde A} \le {\widetilde x}\cdot {\widetilde A}$$ so that, as $\cos^{-1}$ is a decreasing function, $${\rm dist}_{S^d}(M{\widetilde x},{\widetilde A})\ge {\rm dist}_{S^d}({\widetilde x},{\widetilde A}).$$ It follows that for all $M\in{\cal M},$ $$Q(M{\widetilde x})^{d+1} \le {c\over n^{d+1}}{\rm dist}_B(x,A)^{-(d+1)}$$ and hence $P(x)$ satisfies (b). \eop \vskip6pt The proof of Theorem 4 is now exactly the same as for Theorems 2 and 3, using the polynomial $P(x)$ provided by Lemma 4. The volumes of the strips $S_j$ are measured using the measure $d\mu$ of (15) to yield (13). We again omit the details. \eop \vfill \eject %\vskip10pt \References %\ref Baran, M., Bernstein type theorems for compact sets in $\RR^n,$ \JAT~{\bf 69}, %(1992), 156--166. %\ref Baran, M., Bernstein type theorems for compact sets in $\RR^n$ revisited, \JAT~{\bf 79}, %(1994), 190--198. \ref Bos, L., Levenberg, N., and Waldron, S., Metrics associated to multivariate polynomial inequalities, {\sl Advances in Constructive Approximation}, M. Neamtu and E. B. Saff eds., Nashboro Press, Nashville, 2004, 133--147. \ref Bos, L., Levenberg, N., and Waldron, S., Pseudometrics, Distances and Multivariate Polynomial Inequalities, to appear. \ref Burns, D., Levenberg, N., Ma'u, S. and R\'ev\'esz, Sz., Monge-Amp\`ere Measures for Convex Bodies and Bernstein-Markov Type Inequalities, submitted. \ref Dubiner, M., The theory of multidimensional polynomial approximation, J. Anal. Math. {\bf 67}, (1995), 39--116. \ref Fej\'er, L., Bestimmung derjenigen Abszissen eines Intervalles, f\"ur \break welche die Quadratsumme der Grundfunktionen der Lagrangeschen Interpolation im Intervalle ein M\"oglichst kleines Maximum Besitzt, {\sl Annali della Scuola Normale Superiore di Pisa - Classe di Scienze}, Ser. 2, {\bf 1} (1932), 263--276. \ref Klimek, M., {\sl Pluripotential Theory}, Clarendon Press, Oxford, 1991. \ref K\"ovari, T. and Pommerenke, Ch., On the Distribution of Fekete Points, {\sl Mathematika}, {\bf 15} (1968), 70--75. %\ref Kro\'o, A. and R\'ev\'esz, Sz., {\sl On Bernstein and Markov-type %inequalities for %multivariate polynomials on convex bodies}, \JAT~{\bf 99} (1999), 134--152. %\ref Milev, L. and S. R\'ev\'esz, Bernstein's inequality for multivariate %polynomials %on the standard simplex, J. Ineq. Appl. 2005:2 (2005), 145--163. %\ref Sarantoupolos, {\sl Bounds on the derivatives of polynomials on Banach %spaces}, Math. Proc. Cambridge Philos. %Soc. {\bf 110} (1991), 307--312. \ref S\"undermann, B., Lebesgue constants in Lagrangian interpolation at the Fekete points, {\sl Mitt. Math. Ges. Hamb.} {\bf 11} (1983), 204--211. %******************************* ADDRESS ************************* {% Beginning of addresses \bigskip\obeylines Len Bos Department of Mathematics and Statistics University of Calgary Calgary, Alberta Canada T2N 1N4 {\tt lpbos@math.ucalgary.ca} \bigskip Norm Levenberg Department of Mathematics Indiana University Bloomington, IN 47405 USA {\tt nlevenbe@indiana.edu} \bigskip Shayne Waldron Department of Mathematics University of Auckland Private Bag 92019 Auckland, New Zealand {\tt waldron@math.auckland.ac.nz} } %End of addresses \bye