15
$\begingroup$

The following describes an extension of the Descartes Rule of Signs to polynomials with complex coefficients.

First, I need to define the notion of a "sweep"... Given a complex polynomial p(z) := c0 zm0 + c1 zm1 + ... + cn zmn with non-zero ci and strictly increasing mi, let {αi} be the coefficients' "non-decreasing argument sequence": αi = arg ci (mod 2π), and α0 ≤ α1 ≤ ... ≤ αn, with each αi+1i taken as small as possible; then αn0 computes the "angular sweep" --which I'll denote sweep(p)-- of a needle with one end anchored at the origin of the Complex Plane that begins pointing at c0 and then spins counter-clockwise to point at each ci in turn ("stalling in place" when consecutive coefficients have equal arguments).[*]

With this, we have:

The Descartes Rule of Sweeps. The number of positive real roots of p is at most $\lfloor \frac{1}{\pi} sweep(p)\rfloor$.

(The Descartes Rule of Signs represents a special case: each sign change in a polynomial's real coefficient sequence contributes π to the sweep, so that $\frac{1}{\pi}sweep(p)$ exactly counts those sign changes.)

Now, I can prove the Rule of Sweeps using the Descartes Rule of Signs itself, but that approach sheds no light on why the Rule of Signs works (which is what I'm really after). The result seems to be one clever contour away from falling directly out of the Cauchy Argument Principle --and it even seems curiously appropriate that the formula provides a kind of half-winding number from the coefficient sequence-- but apparently I'm not sufficiently clever. :(

Suggestions?

[*] Note: One can also compute a sweep of the coefficients taken in reverse order (or, equivalently, spinning the needle clockwise). Differently-directed sweeps are usually not equal, so we can optimize the bound in the Rule of Sweeps by taking "the" sweep as the minimum of the two directed sweeps.

$\endgroup$
3
  • $\begingroup$ It sounds like you need to use Roueche's theorem in the right way. For example, you could try moving all the non-zero coefficients to the top degrees, since that wouldn't change the sweep. $\endgroup$ Apr 25, 2010 at 19:29
  • $\begingroup$ Don: may I direct your attention to doi.acm.org/10.1145/322077.322084 ; sounds similar to what you're trying to do here. $\endgroup$ Aug 16, 2010 at 9:23
  • $\begingroup$ I really like the part with taking the minimum of the two directions. Very clever, especially given my first idea if I had come across this result would have just done counterclockwise and assumed the other direction was the opposite of it. $\endgroup$ Dec 10, 2010 at 0:04

3 Answers 3

4
$\begingroup$

This paper is related to generalizing Sturm's theorem rather than Descartes' rule of signs, but I think it is relevant: http://arxiv.org/abs/0808.0097

$\endgroup$
0
2
$\begingroup$

The following paper by Jeff Lagarias and Tom Richardson "Multivariate Descartes rule of signs and Sturmfels' challenge problem" http://www.math.lsa.umich.edu/~lagarias/doc/intelligencer.pdf

looks like it has things relevant to your question.

$\endgroup$
1
  • $\begingroup$ It may take me a little time to wrap my mind around the concepts to determine relevancy. I'll note, however, that the provided solution to the "Sturmfels Challenge Problem" (counting non-zero real roots of a specific system of two polynomials in two variables) makes multiple appeals to the original Rule of Signs. It's not clear (to me), then, whether the algebraic machinery described (Newton polytopes and such) requires pre-supposing the original Rule of Signs to actually get anywhere. Such pre-supposing is specifically what I'm trying to avoid. $\endgroup$
    – Blue
    Apr 26, 2010 at 8:19
0
$\begingroup$

Obrechkoff proved the following generalization: Obrechkoff generalization

Tossing the text into Google-translate:

Consider $$f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n = 0 $$ an equation with real coefficients, whose number of sign variations is $V$. Then the number of its roots, whose arguments lie between $-\alpha$ and $\alpha$ $(0 \le \alpha < \frac{\pi}{2})$, the limits $-\alpha$ and $\alpha$ being excluded, does not exceed $V + 2 \left[ \frac{n\alpha}{\pi}\right]$ (where $[x]$ denotes the largest integer contained in $x$) and if it is less, the difference is an even number.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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