Oversampling of polynomials

Suppose p(z)=c_0+\dots +c_d z^d is a polynomial which we can evaluate at the Nth 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

N black dots uniformly distributed on the unit circle


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 Nth 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 mth gap between the Nth 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.