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$
3
  • 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
    Commented Aug 9, 2014 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
    Commented Aug 11, 2014 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
    Commented Aug 18, 2014 at 3:58

1 Answer 1

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$
2
  • $\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
    Commented Aug 17, 2014 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$ Commented Aug 17, 2014 at 22:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .