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

I'm currently involved in a small (but quite time consuming) project where we are trying to get some decent bound for the number $N(P)$ of real zeroes of a random polynomial $P(x)=\sum_{k=0}^n\xi_k x^k$ where $\xi_k$ are real independent identically distributed random variables satisfying $P(\xi_k=0)=0$ (just to avoid totally idiotic degeneracies) but no other a priori assumptions.

Our current approach uses the inequality $$ \mathcal P\left[\max_{|\alpha|<C\ell}|P(re^{i\alpha})|\le n^{-C}\ell^{Cm}\sum_k|\xi_k|r^k\right]\le e^{-m} $$ for all fixed $r>0$, $0<\ell<1$, $n,m\ge 2$ with some absolute $C>0$, which is not terribly bad and gives the bound $$ \mathcal E N(P)\le C\log^4 n $$ in the end.

However, I suspect that even a stronger bound $$ \mathcal P\left[\max_{|\alpha|<C\ell}|P(re^{i\alpha})|\le n^{-C}\ell^{Cm}\sum_k|\xi_k|r^k\right]\le n^{-m} $$ may hold, which would allow us to shave one logarithm off. I wonder if anybody has any idea of how to get something like this (or better). If you find a counterexample, it'll shed some light on what is going on too. We are currently using the combination of the Turan lemma and the flip-flop around the median technique but all my previous experience shows that using the worst case scenario estimates in the probabilistic setting is never optimal.

To put things in perspective, the bound everybody hopes for should be $\mathcal EN(P)\le C\log n$. It has been proved for many "decent" distributions of $\xi_k$ but if you do not assume anything and require the uniform bound over all distributions (which may be attained at different distributions for different $n$), as in our project, then it looks like the best published bound is $\mathcal EN(P)\le C\sqrt n$ (if somebody knows anything better, I'll be happy to hear it too).

Update: We have finally got $C\log n$ with absolute $C$ in the classical problem (any real i.i.d coefficients) by a different method. However, the question remains because there are interesting situations to which our new approach does not apply but the original one, which gives $\log^4 n$, does.

share|cite|improve this question
Can you give a reference for the $C\sqrt{n}$ bound (or an indication of the proof if it's easy)? A little quick googling turns up lots of literature on the problem, but I didn't immediately find that. – Mark Meckes Dec 12 '12 at 17:38
I'm not sure if it has really appeared in print yet but the result was obtained simultaneously by two pairs of people: Krishnapur and Zeitouni, and Kabluchko and Zaporozhets. Misha Sodin kindly told me the sketch of the proof. Divide by $1-x$. Then the sequence of the coefficients will become $\xi_1,\xi_1+\xi_2,\dots,\xi_1+\dots+\xi_n$, after which it stabilizes. Now just use Descartes' rule of signs and the fact (not sure how well known) that any $n$-step random walk on the line with i.i.d. steps cannot change sign more than $C\sqrt n$ times on average. – fedja Dec 13 '12 at 4:01

Your Answer


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

Browse other questions tagged or ask your own question.