Oversampling of polynomials

Suppose $p(z)=c_0+\dots +c_d z^d$ is a polynomial which we can evaluate at the $N$ th roots of unity. By way of normalization, assume that $|p(z)|\le 1$ whenever $z^N=1$ . What is the best upper estimate for $|p|$ on the unit circle, i.e., the smallest number $K(N,d)$ for which we can say $\sup_{|z|=1}|p(z)|\le K(N,d)$ ?

There is no bound at all if $N\le d$ , because $p$ can vanish at all roots of unity and be as large elsewhere as it pleases. So the first nontrivial case is $N=d+1$ . In this case our $p$ is the Lagrange interpolation polynomial with equidistributed nodes on the unit circle. Since its values at the nodes are bounded by 1, the matter reduces to estimating the basis polynomials $\ell_j(z)=\prod_{m\ne j}\frac{z-\zeta_m}{\zeta_j-\zeta_m}$ where $\zeta_m$ are the nodes. This leads to geometrically appealing calculations such as

Denominator — N black dots uniformly distributed on the unit circle

and

Numerator (but not quite) — N black dots uniformly distributed on the unit circle; and a green midpoint

Alexander Overwijk I am not.

After summation we get a partial sum of the harmonic series, and so $K(d+1,d)$ is of order $\log d$ . I’ve seen this result attributed to Marcinkiewicz, specifically to his 1937 paper Sur la divergence de polynomes d’interpolation. However, I could not find anything of the sort in this paper. The estimate is used, without proof, in his other paper in the same issue of the journal: Quelques remarques sur l’interpolation. I’m pretty sure Marcinkiewicz did not consider the estimate new; most likely, Bernstein and Faber did such computations earlier.

Anyway, what happens if $N>d+1$ ? Fast forward to the 21 century. In the 2005 paper On discrete norms of polynomials by Рахманов and Шехтман, the constant $K(d,N)$ is shown to be of order $\log \frac{N}{N-d}+1$ for all $N>d$ . The logarithm matters only if $N/d$ is close to 1; for large values (say, $N\ge 2d$ ) this estimate is simply $K_1\le K(N,d)\le K_2$ with implicit constants $K_1,K_2$ . Keeping $d$ fixed, we should have $K(N,d)\to 1$ as $N\to\infty$ , but the estimate does not tell us this.

Shortly thereafter (2008), T. Sheil-Small obtained a clean estimate $K(N,d) \le \sqrt{\frac{N}{N-d}}$ , which indeed has the property $K(N,d)\to 1$ as $N\to\infty$ . Interestingly, the estimate is sharp when $N=2d$ (and only in this case): a multiple of $z^d+i$ achieves the value $K(2d,d)=\sqrt{2}$ . The extremal polynomial has a zero at the midpoint of every other gap between the $N$ th roots of unity.

And quite recently (2011), В.Н. Дубинин obtained the estimate $K(N,d) \le 1/\cos\frac{\pi d}{2N}$ which is sharp whenever $d$ divides $N$ (and only then). In particular, that $\sqrt{2}$ was secretly $1/\cos \frac{\pi}{4}$ . The polynomial that achieves the value $K(md,d)$ has a zero at the midpoint of every $m$ th gap between the $N$ th roots of unity.

Can one compute $K(N,d)$ when $N$ is not divisible by $d$ ? I don’t want to say it’s impossible, but one would first need to understand the extremal polynomials, and my numerical experiments show no clear pattern. Their zeros do not lie on the unit circle; they are sometimes inside and sometimes outside. So I’m not optimistic.

Oversampling of polynomials

Related

Leave a Reply Cancel reply