Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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|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

 
discard

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.