MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a polynomial $p(x_1,\ldots, x_k)$ in $k$ variables with maximum degree $n$, and $x_1,\ldots, x_k \in [0,1]$. Suppose $\max_{x \in [0,1]^k} p(x) = 1$, can we get an upper bound on the probability $\mathbb{P}(|p(x)| < \epsilon)$ where we treat the product space $[0,1]^k$ as a natural probability space? Using techniques from this paper: one can show that the above probability is small provided $\epsilon$ is of tower exponential order $e^{-e^n}$. But I need $\epsilon$ to be of poly-exponential order, i.e., $e^{-(nk)^c}$. Looking at the polynomial $x_1^n x_2^n \ldots x_k^n$, one deduce by central limit theorem that $\mathbb{P}(|p(x)| < \epsilon)$ is small provided $\epsilon = \mathcal{O}(e^{-kn})$. But I can't prove that this polynomial has the the highest probability of staying near zero.

If needed, one can also bound $\epsilon$ in terms of the total degree, i.e., the sum of degrees of all the monomial terms in $p$.

share|cite|improve this question
up vote 2 down vote accepted

I believe that the result you want follows from the results in this very cool paper. (see, in particular page 9). There are probably improvements since then...

share|cite|improve this answer
That's exactly the literature I am looking for. Thank you so much! – John Jiang Dec 28 '11 at 21:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.