# Gaps between roots of trigonometric polynomials

[Cross-posted from Math.SE because I got no responses there.]

Given a polynomial in $e^{\mathrm{i}k t}$ of the form $$p(t) = \sum_{-n\leq k\leq n} c_k e^{\mathrm{i}k t}$$ with $\bar c_{-k} = c_k$, is there a good way of characterising how close its roots can be in terms of its coefficients?

Clearly this depends on coefficients, for example $1-\epsilon-\cos x$ has roots $\sqrt{\epsilon}$ apart, but for general coefficients, is there any good result? I am secretly hoping for minimum distance of something like $A n^{-1}$ (which is the case for $\sin n x$) for non-almost-degenerate coefficients.

If you know a result for any kind of orthogonal polynomials (like Chebyshev polynomials), that would also be very helpful. Also, I know there are some results for asymptotic distributions of eigenvalues of Toeplitz matrices, but I am interested in a result for a fixed polynomial $p$ and its coefficients, and not just $n\to\infty$.

Edit. I am mainly interested in an algorithm that, given a polynomial as above, computes the shortest gap between two adjacent roots of the polynomial.

The motivation is as follows. The simplest method for calculating a root of a function numerically is the bisection method, which only works so long as you know an interval that brackets a root (an interval on which the function changes sign). In general, calculating all roots of a black-box function is really hard. So without going to more involved algorithms, the simplest algorithm to find all (simple) roots must be this one: find the shortest distance $\delta$ between adjacent roots, sample the function in intervals of length $\delta$, find the root in each interval with a sign change in it. Of course, this doesn't work without knowing $\delta$. This is not a brilliant algorithm, there are better ones out there, but I am interested in finding out how I could make it work.

So the question is: given a trigonometric polynomial with only simple roots, how can I calculate the shortest distance between adjacent roots, so that the above scheme would succeed?

Example. If $t_{1,2}$ are two roots, I can write $$2\max_{[t_1,t_2]}|f(t)| \leq \int_{t_1}^{t_2}|f'(t)|\,dt \leq |t_2-t_1|\max_{[t_1,t_2]}|f'(t)|.$$ So at least $$|t_1-t_2| \geq 2\frac{\max_I |f|}{\max_I |f'|}.$$ Then by Bernstein's inequality, $$\max_I |f'| \leq \|f'\|_\infty \leq n \|f\|_\infty,$$ so $$|t_1-t_2| \geq \frac2m \frac{\max_I|f|}{\max_{[-\pi,\pi]}|f|}.$$ But then I don't know quite how to deal with the right-hand side.

• It is a little bit unclear what exactly you are asking because the word "general" may mean about 100 different things. The most trivial interpretation is that $c_k$ are standard i.i.d. complex Gaussians ($k>0$); show that, with probability close to $1$, .... This certainly has been done but I have no idea if this is even remotely close to what you are looking for except your last sentence shows that the answer is somewhat more likely to be "no" than "yes". Can you elaborate a bit on what you would consider a useful characterization? Aug 9, 2014 at 11:38
• @fedja I edited the question to try and explain myself better. Please let me know if it is still unclear. Aug 11, 2014 at 9:44
• You could also let $z=e^{it}$ and write your trig polynomial function as an algebraic polynomial function $F$ in $z$. Then looking at the discriminant of $F$ maybe helpful. Another possibly unrelated note: Nazarov has proved some generalization of Remez's inequality, that bounds the amount of time a trig polynomial stays around 0 in terms of its degree. Aug 18, 2014 at 3:58