Remez-type inequality for discrete sets (Q1758945): Difference between revisions

Let \(B\subset {\mathbb R}^n\) be a convex body and let \(\Omega\subset B\) be a measurable set. It is known that for any real polynomial \(P(x) = P(x_1,\dots, x_n)\) of degree \(d\) we have \[ \sup_B|P| \leq T_d\left(\frac{1 + (1 - \lambda)^{1/n}}{1 - (1 - \lambda)^{1/n}} \right)\,\sup_{\Omega}|P|. \eqno (1) \] Here \(T_d(t)\) is the \(d\)-th Chebyshev polynomial and \(\lambda=\mu_n(\Omega)/\mu_n(B)\), with \(\mu_n\) being the Lebesgue measure on \({\mathbb R}^n\). The inequality (1) is sharp and when \(n=1\), \(B=[-1,1]\) it coincides with the classical Remez inequality. Further, let \(Q_1^n\subset {\mathbb R}^n\) be the unit cube. A set \(Z\subset Q_1^n\) is called \(d\)-definite if any real polynomial \(P(x) = P(x_1,\dots, x_n)\) of degree \(d\) bounded in absolute value by 1 on \(Z\) is bounded in absolute value by a certain constant \(C(d,Z)\) (not depending on \(P\)) on \(Q_1^n\). The minimum \(R_d(Z)\) of all such constants \(C(d,Z)\) is called the Remez \(d\)-span of \(Z\). The author introduces a geometric invariant \(\omega_d(Z)\) which can be effectively estimated in terms of the metric entropy of \(Z\) and which may be nonzero for discrete and even finite sets \(Z\). It is shown that if \(\omega_d(Z) = \omega > 0\) then \(R_d(Z)\) finite and satisfies \[ R_d(Z)\leq T_d\left(\frac{1 + (1 - \omega)^{1/n}}{1 - (1 - \omega)^{1/n}} \right). \] Several examples of \(d\)-definite sets are given.