8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – fedja Aug 9 '14 at 11:38
  • $\begingroup$ @fedja I edited the question to try and explain myself better. Please let me know if it is still unclear. $\endgroup$ – Kirill Aug 11 '14 at 9:44
  • $\begingroup$ 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. $\endgroup$ – John Jiang Aug 18 '14 at 3:58
6
+50
$\begingroup$

The technical term for what you want to do is root isolation or root bracketing. One way to approach this to find the minimal distance between the roots, like you are suggesting, and also a large enough bounded interval to contain all the roots. This idea was in fact used early on in the history of root isolation for real polynomials. However, these techniques have gotten more sophisticated with time. I imagine the situation would be similar for trigonometric polynomials.

Here's a reference that seems to discuss root isolation precisely for trigonometric polynomials:

Real zero isolation for trigonometric polynomials, by Achim Schweikard
ACM Transactions on Mathematical Software 18 350-359 (1992)
http://dx.doi.org/10.1145/131766.131775

$\endgroup$
  • $\begingroup$ So IIUC the idea in that paper is to use trigonometric identities to convert it to a problem about an algebraic polynomial; and then apply a root isolation method to that. It seems to assume that the coefficients are integral, rational, or algebraic, though. $\endgroup$ – Kirill Aug 17 '14 at 22:46
  • $\begingroup$ Calculations of root brackets are rational operations, so rational coefficients give rational brackets. The methods should still work if the coefficients are real. On the other hand, you could always just approximate every real coefficient by a rational number within your error tolerance. $\endgroup$ – Igor Khavkine Aug 17 '14 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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