# Bounded polynomial having coefficients that are bounded linearly in degree and number of variables

Let $P(\mathbf{x})$ be a bounded multivariate polynomial of degree at most $d$ (for my purposes it can be either coordinate degree or total degree) over $[-1,1]^n$, and assume $|P(\mathbf{x})| \leq 1$. In A bounded polynomial having bounded coefficients: several variables it is discussed that the coefficients of such a polynomial can be very large (more or less exponential in d and n).

My question is if it is possible to have a bound that grows at most linearly in d and n by adding some basic assumptions on $P$, e.g. a bounded lipschitz constant, or bounded 1st and 2nd order partial derivatives?

• The answer is no even for polynomials of one variable. Take a second antiderivative of Chebyshev polynomial. – Oleg Eroshkin Jun 11 '18 at 20:24
• I'm not sure I follow -- how is the second antiderivative related to the coefficients? or is it some counter example? Do you mind adding a bit more detail? Thanks for your help! – Or Sharir Jun 12 '18 at 6:44
• Consider the solution of differential equation $f''=T_n(x)$ with $f'(0)=f(0)=0$. It's a polynomial of degree $n+2$ with leading coefficient $2^{n-1}/n(n+1)$. Clearly on $[-1,1]$ we have $|f(x)|\leq1/2$ and $|f'(x)|\leq 1$, $|f(x)|\leq 1$. This trivial construction shows, that you need to put restrictions on $\sim n/\ln n$ derivatives to get a non-exponential bounds on coefficients. – Oleg Eroshkin Jun 12 '18 at 11:50