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

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