A bounded polynomial having bounded coefficients: several variables

Question

Consider the multivariate case for the question "Approximation theory reference for a bounded polynomial having bounded coefficients" (Approximation theory reference for a bounded polynomial having bounded coefficients)

I tried to find an upper bound for coefficients for each monomial. I tried two methods:

1. Lagrange interpolation. As in Lemma 4.1 in http://eccc.hpi-web.de/report/2012/037/download .

2. I first only consider the variable $x_1$ and get an upper bound for the coefficients. Now the bound is the upper bound for another polynomial of $x_2,x_3,...,x_n$ and we can repete the above method.

However, using either method above, the upper bound will contain factor $d^n$ or $c^{d*min\{d,n\}}$ where c is a constant, which I think is too large. Is it possible to find a better upper bound?

Answer 1

Bounds in the univariate case, see e.g. here, were established by V.A. Markov in 1892.

S.N. Bernstein has given an extension of the result to the multivariate case in

S.N. Bernstein, On certain elementary extremal properties of polynomials in several variables, Doklady Akad. Nauk SSSR (N.S.) 59 (1948), 833-836.

Unfortunately I do not have access to that paper, but according to MR0023953, the following result is proved. Let $$P(x_{1},\ldots,x_{n})=\sum_{1\leq\alpha_{h}\leq d_{h}} A_{\alpha_{1},\ldots,\alpha_{n}}x_{1}^{\alpha_{1}}\ldots x_{n}^{\alpha_{n}},$$ such that $|P|\leq1$ on the cube $|x_{h}|\leq1$, $1\leq h\leq n$. Then $$|A_{\alpha_{1},\ldots,\alpha_{n}}|\leq\frac{\prod_{h=1}^{n}|B_{\alpha_{h}}^{(d_{h})}|}{\alpha_{1}!\ldots\alpha_{n}!},$$ where $B_{\alpha_{h}}^{(d_{h})}$ is the coefficient of $x^{\alpha_{h}}/\alpha_{h}!$ in the expansion of the Chebyshev polynomial $$T_{m}(x)=\cos(m\cos^{-1}(x))=\sum_{i=0}^{m}B_{i}^{(m)}x^{i}/i!,$$ and $m=d_{h}$ if $d_{h}-\alpha_{h}$ is even and $m=d_{h}-1$ if $d_{h}-\alpha_{h}$ is odd.

For the particular case of homogeneous polynomials $$P_{d}(x_{1},\ldots,x_{n})=\sum_{|\alpha|= d}c_{\alpha}x^{\alpha},$$ of total degree $d$, where $\alpha$ are multi-indices, such that $|P_{d}|\leq1$ on the ball $x_{1}^{2}+\cdots +x_{n}^{2}\leq1$, upper bounds on the coefficients are given in Theorem 2 of

O.D. Kellogg, On bounded polynomials in several variables, Math. Z. 27 (1928), no. 1, 5-64.

namely, the coefficient of the monomial $x_{1}^{k_{1}}\ldots x_{n}^{k_{n}}$ cannot exceed in absolute value $$\frac{d!}{k_{1}!\ldots k_{n}!}.$$

For general (nonhomogeneous) polynomials of total degree $d$, there are also precise bounds on the coefficients $c_{\alpha}$ with $|\alpha|=d$ or $d-1$ (for the case of the ball or the cube).

In that connection, two interesting papers are

M.I. Ganzburg, A Markov-type inequality for multivariate polynomials on a convex body. J. Comput. Anal. Appl. 4 (2002), no. 3, 265-268

H-J. Rack, On V. A. Markov's and G. Szegő's inequality for the coefficients of polynomials in one and several variables. East J. Approx. 14 (2008), no. 3, 319-352,

and the bibliography therein.

Answer 2

We recently needed a result of this form and couldn't find an appropriate paper to cite (some of the papers cited above are hard to locate), so we proved the result. It's actually not too hard to show an upper bound of $d^{O(d)}$ on the magnitude of the largest coefficient of such a polynomial. More precisely, the following is true:

Let $p$ be a real polynomial on $n$ variables of degree $d$ such that for all $x\in[0,1]^n$, $|p(x)|\leq 1$. Then the magnitude of every coefficient of $p$ is upper bounded by $(2d)^{3d}$.

No attempt was made to optimize the constants in the above statement. A full proof of the above statement can be found in Ref. [1] as Theorem 46.

I don't know if the result is tight (up to constants in the exponent), because in the univariate case you can show a better upper bound of $2^{O(d)}$, so there is a gap here.

[1] Shalev Ben-David, Adam Bouland, Ankit Garg, and Robin Kothari. Classical lower bounds from quantum upper bounds, 2018.