Suppose is a polynomial which we can evaluate at the th roots of unity. By way of normalization, assume that whenever . What is the best upper estimate for on the unit circle, i.e., the smallest number for which we can say ?
There is no bound at all if , because can vanish at all roots of unity and be as large elsewhere as it pleases. So the first nontrivial case is . In this case our 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 where are the nodes. This leads to geometrically appealing calculations such as
Alexander Overwijk I am not.
After summation we get a partial sum of the harmonic series, and so is of order . 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 ? Fast forward to the 21 century. In the 2005 paper On discrete norms of polynomials by Рахманов and Шехтман, the constant is shown to be of order for all . The logarithm matters only if is close to 1; for large values (say, ) this estimate is simply with implicit constants . Keeping fixed, we should have as , but the estimate does not tell us this.
Shortly thereafter (2008), T. Sheil-Small obtained a clean estimate , which indeed has the property as . Interestingly, the estimate is sharp when (and only in this case): a multiple of achieves the value . The extremal polynomial has a zero at the midpoint of every other gap between the th roots of unity.
And quite recently (2011), В.Н. Дубинин obtained the estimate which is sharp whenever divides (and only then). In particular, that was secretly . The polynomial that achieves the value has a zero at the midpoint of every th gap between the th roots of unity.
Can one compute when is not divisible by ? 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.