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

## Lattice points in a disk

The closed disk of radius ${72}$ has area ${\pi \cdot 72^2\approx 16286}$. But it happens to contain only ${16241}$ points with integer coordinates. Here is a picture of one quarter of this disk.

The radius ${72}$ is somewhat notable is that the discrepancy of ${45}$ between the area and the number of integer points is unusually large. Here is the plot of the absolute value of the difference |area-points| as a function of integer radius ${n}$. The curve in red is ${y = 1.858 r^{0.745}}$, which is an experimentally found upper bound for the discrepancy in this range of ${n}$.

On the scale up to ${n=1000}$, the upper bound is ${4.902 r^{0.548}}$, and the radii bumping against this bound are ${449}$ and ${893}$. The exponent ${0.548}$ begins to resemble the conjectural ${0.5+\epsilon}$ in the Gauss circle problem.

Finally, over the interval ${1000\le n\le 3000}$ the upper bound comes out as ${6.607n^{0.517}}$. The exponent ${0.517}$ looks good.

This little numerical experiment in Matlab involved using the convex hull function convhull on log-log scale. The function identifies the vertices of the convex hull, which is a polygon. I pick the side of the polygon lying over the midpoint of the range; this yields a linear upper bound for the set of points. On the normal scale, this line becomes a power function. Matlab code is given below; it’s divided into three logical steps.

##### Find the difference between area and the number of lattice points
a = 1000;
b = 3000;
R = a:b;
E = [];
for n = a:b
[X,Y] = meshgrid(1:n, 1:n);
pts = 4*n + 1 + 4*nnz(X.^2+Y.^2<=n^2);
E = [E, max(1,abs(pts - pi*n^2))];
end
##### Pick a suitable side of log-log convex hull
ix = convhull(log(R), log(E));
k = numel(ix);
while (R(ix(k))<(a+b)/2)
k = k-1;
end
##### Plot the result and output the parameters of the upper bound
R1 = R(ix(k)); E1 = E(ix(k));
R2 = R(ix(k+1)); E2 = E(ix(k+1));
b = log(E1/E2)/log(R1/R2);
a = E1/R1^b;
plot(R, E, '.');
hold on
plot(R, a*R.^b , 'r-');
axis tight
hold off
fprintf('a = %.3f, b = %.3f\n', a, b);