## Discrete maximum principle for polynomials

The polynomially convex hull of a compact set ${K\subset \mathbb C}$ is defined as the set of all points ${z\in \mathbb C}$ such that the inequality ${|p(z)|\le \sup_K |p|}$ (a form of the maximum principle) holds for every polynomial ${p}$. For example, the polynomially convex hull of a simple closed curve is the union of that curve with its interior region. In general, this process fills up the holes in the set ${K}$, resulting in the complement of the unbounded connected component of ${\mathbb C\setminus K}$.

We can recover the usual convex hull from this construction by restricting ${p}$ to the polynomials of first degree. Indeed, when ${p}$ is linear, the set ${|p|\le M}$ is a closed disk, and we end up with the intersection of all closed disks that contain ${K}$. This is precisely the convex hull of ${K}$.

What if we restrict ${p}$ to the polynomials of degree at most ${n}$? Let’s call the resulting set the degree-${n}$ convex hull of ${K}$, denoted ${K_n}$. By definition, it is contained in the convex hull and contains the polynomially convex hull. To exactly compute ${K_n}$ for general ${K}$ appears to be difficult even when ${n=2}$.

Consider finite sets. When ${K}$ has at most ${n}$ points, we have ${K_n=K}$ because there is a polynomial of degree ${n}$ whose zero set is precisely ${K}$. So, the first nontrivial case is of ${K}$ having ${n+1}$ points. Let us write ${K=\{z_0, \dots, z_n\}}$.

Depending on the location of the points, ${K_n}$ may be strictly larger than ${K}$. For example, if ${K}$ consists of the vertices of a regular ${(n+1)}$-gon, then ${K_n}$ also contains its center. Here is why. By a linear transformation, we can make sure that ${K=\{\zeta^k\colon k=0, \dots, n\}}$ where ${\zeta = \exp(2\pi i/(n+1))}$. For ${j=1, \dots, n}$ we have ${\sum_{k=0}^n \zeta^{kj} = (\zeta^{(n+1)j}-1)/(\zeta^j - 1) = 0}$. Hence, for any polynomial ${p}$ of degree at most ${n}$, the sum ${\sum_{k=0}^n p(\zeta^k)}$ is equal to ${(n+1)p(0)}$. This implies ${|p(0)|\le \max_{0\le k\le n}|p(\zeta^k)|}$, a kind of a discrete maximum principle.

A more systematic approach is to use the Lagrange basis polynomials, that is ${L_j(z) = \prod_{k\ne j} (z-z_k)/(z_j-z_k)}$, which satisfy ${L_j(z_k) = \delta_{jk}}$. Since ${p = \sum_j p(z_j)L_j}$ for any polynomial of degree at most ${n}$, it follows that ${z\in K_n}$ if and only if ${\left|\sum_j c_j L_j(z)\right|\le \max |c_j| }$ holds for every choice of scalars ${c_0, \dots, c_n}$. The latter is equivalent to the inequality ${\sum_j |L_j(z)|\le 1}$.

This leads us to consider the function ${S=\sum_j |L_j|}$, the sum of the absolute values of the Lagrange basis polynomials. (Remark: S is called a Lebesgue function for this interpolation problem.) Since ${\sum_j L_j\equiv 1}$, it follows that ${S\ge 1}$ everywhere. By construction, ${S=1}$ on ${K}$. At a point ${z\notin K}$, the equality ${S(z)=1}$ holds if and only if ${\arg L_j(z)}$ is the same for all ${j}$.

In the trivial case ${K=\{z_0, z_1\}}$, the function ${S(z) = (|z-z_0|+|z-z_1|)/|z_0-z_1|}$ is equal to ${1}$ precisely on the linear segment with endpoints ${z_0, z_1}$. Of course, this only repeats what we already knew: the degree-1 convex hull is the ordinary convex hull.

If ${K=\{x_0, \dots, x_n\}}$ with ${x_0<\cdots real and ${n\ge 2}$, then ${K_n=K}$. Indeed, if ${x\in K_n\setminus K}$, then ${x}$ lies in the convex hull of ${K}$, and therefore ${x_{j-1} for some ${j}$. The basis polynomial ${L_j}$ is positive at ${x}$, since it is equal to ${1}$ at ${x_j}$ and does not vanish outside of ${K}$. Since a polynomial changes its sign at every simple zero, it follows that ${L_{j+1}(x) < 0}$. Well, there is no ${L_{j+1}}$ if ${j=n}$, but in that case, the same reasoning applies to ${L_{j-2}(x)<0}$. In any case, the conclusion is that ${\arg L_k(x)}$ cannot be the same for all ${k}$.

At this point one might guess that the vertex set of a regular polygon is the only kind of finite sets that admit a nontrivial discrete maximum principle for polynomials. But this is not so: the vertices of a rhombus work as well. Indeed, if ${K=\{a, -a, ib, -ib\}}$ with ${a, b>0}$, then ${L_j(0)>0}$ for all ${j}$, hence ${S(0)=1}$.

The vertices of a non-square rectangle do not work: if ${K}$ is the set of these vertices, the associated function ${S}$ is strictly greater than 1 on the complement of ${K}$.

Are there any other finite sets that support a discrete maximum principle for polynomials?

## 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

and

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.