\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)<c_1/n\},$
a set of volume
$$c\int_0^{c_1/n}\sin^{d-2}(\phi)d\phi\le {c\over n^{d-1}}.$$
(By abuse of notation we let $c$ refer to a generic constant -- it need not have the same value in all of its instances.)

Hence there are at most 
$$c{(\lambda+j)^{d-2}/n^{d-1}\over 1/n^{d-1}}=c(\lambda+j)^{d-2}
\eqno(13)$$
Fekete points in the strip $S_j.$

It follows that
$$\eqalign{\sum_{b\in F_n\atop b\neq a}{\rm dist}(a,b)^{-d}&=
\sum_{j\ge 1}\sum_{b\in F_n\cap S_j}{\rm dist}(a,b)^{-d}\cr
&\le c\sum_{j\ge 1}(\lambda+j)^{d-2}\left({\lambda+j-1\over n}\right)^{-d}\cr
&=cn^d\sum_{j\ge1}{(\lambda+j)^{d-2}\over (\lambda +j-1)^d}.}$$
Now, we may assume that $\lambda\ge1,$ for if not, $\lambda<1$ and hence
$$n\left({1\over2}{\rm dist}(a,a^*)\right)\le1$$
and so ${\rm dist}(a,a^*)\le 2/n$ and we are done. Making this assumption then, we 
have
$$\lambda+j\le 2(\lambda+j-1),\quad j\ge1,$$
so that
$$\eqalign{\sum_{b\in F_n\atop b\neq a}{\rm dist}(a,b)^{-d}
&\le cn^d\sum_{j\ge1}{(\lambda+j)^{d-2}\over (\lambda +j-1)^d}\cr
&\le cn^d\sum_{j\ge1}{2^{d-2}(\lambda+j-1)^{d-2}\over(\lambda+j-1)^d}\cr
&=cn^d\sum_{j\ge1}{1\over (\lambda+j-1)^2}\cr
&\le cn^d\left\{\int_0^\infty {1\over (\lambda+x)^2}dx+{1\over \lambda^2}\right\}\cr
&=cn^d\left\{{1\over\lambda}+{1\over\lambda^2}\right\}\cr
&\le cn^d{1\over\lambda}\quad\hbox{using again that $\lambda\ge1$}.}$$
Combining this with (12), we have
$$\eqalign{1&\le {c\over n^d}\left\{{n^d\over 2^d\lambda^d}+cn^d{1\over\lambda}
\right\}\cr
&\le c\left\{{1\over \lambda^d}+{1\over \lambda}\right\}\cr
&\le c{1\over\lambda}.}$$
Hence $\lambda\le c$ and we are done. \eop

\sect{4. The Spacing of Fekete Points on the Ball}

We now take $K=B^d\subset\RR^d$ the unit ball. In this case the Dubiner and
Baran distances (cf. [1,2]) are equal and are described as follows. For $a\in B^d,$ i.e., $|a|\le1,$ set 
$$\widetilde{a}:=(a,\sqrt{1-|a|^2})\in S^d\subset R^{d+1}.$$
In other words, $\widetilde{a}$ is $a$ lifted to the circumscribing sphere $S^d.$

Then, for $a,b\in B^d,$ the Dubiner and Baran distances are just the geodesic
spherical distance on $S^d$ between $\widetilde{a}$ and $\widetilde{b},$ i.e.,
$$\eqalign{{\rm dist}_D(a,b)={\rm dist}_B(a,b)&=\cos^{-1}(\widetilde{a}\cdot\widetilde{b)}\cr
&=\cos^{-1}(a\cdot b+\sqrt{1-|a|^2}\sqrt{1-|b|^2}).} $$
We will refer to either of these as ${\rm dist}(a,b).$

We remark that the surface area measure on $S^d$ pulls back under the mapping $a\to\widetilde{a}$ to a measure on $B^d,$ the `surface area' measure,
$$d\mu=c{1\over\sqrt{1-|x|^2}}dx\eqno(14)$$
where $c$ is a normalizing constant.

\proclaim Theorem 3. There are constants $c_1=\pi/2$ and $c_2>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  









