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. :(


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

  • $\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$ – Victor Miller Apr 25 '10 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$ – J. M. is not a mathematician Aug 16 '10 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$ – Adam Hughes Dec 10 '10 at 0:04

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


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.

  • $\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 '10 at 8:19

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.