Polynomials with restricted support and maximal zeros on a finite Cartesian set

Abstract

Given a finite Cartesian set $S=X \times Y$ and a decreasing set of monomials $\mathcal M$, we call extremal polynomials for $\mathcal M$ over $S$ those that have the maximum number of zeros in $S$ and whose support belongs to $\mathcal M$. Coordinate factorizations give a family of extremal polynomials; we call them canonical. If $\max(\mathcal M)$, taken with respect to divisibility, is a single monomial, all extremal polynomials are canonical. If $|\max(\mathcal M)|=2$, either all extremal polynomials are canonical, or the problem reduces to the case where $\max(\mathcal M)=\{x^{d_x},y^{d_y}\}$. In the latter case, we prove that the existence of noncanonical extremal polynomials depends on finding families of subsets whose elementary symmetric functions agree. This condition is more restrictive than the classical Prouhet--Tarry--Escott problem, which asks for two sets whose elementary symmetric functions agree. We determine the number of triples $(X, Y, h)$, where $h$ is a quadratic noncanonical extremal polynomial. We apply extremal polynomials to coding theory via minimum-weight codewords.