Least multivariate chebyshev polynomials on diagonally determined sets

We consider a new multivariate generalization of the classical monic (univariate) Chebyshev polynomial that minimizes the uniform norm on the interval [−1,1]. Let Π∗𝑛 be the subset of polynomials of degree at most 𝑛 in 𝑑 variables, whose homogeneous part of degree 𝑛 has coefficients summing up to 1. The problem is determining a polynomial in Π∗𝑛 with the smallest uniform norm on a set Ω ⊂ℝ𝑑, which we call a least Chebyshev polynomial (associated with Ω). Our main result solves the problem for Ω belonging to a nontrivial class of sets that we call diagonally determined, and establishes the remarkable result that a least Chebyshev polynomial can be given via the classical, univariate, Chebyshev polynomial. In particular, the solution can be independent of the dimension. Diagonally determined sets include centered balls in ℝ𝑑 in any norm, but can be nonconvex and even nonsimply connected. We also introduce a computational procedure, based on semidefinite programming hierarchies, to detect if a given semialgebraic set is diagonally determined.