{"id":228,"date":"2012-07-20T03:59:33","date_gmt":"2012-07-20T08:59:33","guid":{"rendered":"http:\/\/daylateanddollarshort.com\/bloog\/?p=228"},"modified":"2012-07-24T19:14:33","modified_gmt":"2012-07-25T00:14:33","slug":"the-descartes-rule-of-sweeps","status":"publish","type":"post","link":"http:\/\/daylateanddollarshort.com\/bloog\/the-descartes-rule-of-sweeps\/","title":{"rendered":"The Descartes Rule of Sweeps"},"content":{"rendered":"\n

Something about\u00a0Descartes’ Rule of Signs<\/a>\u00a0had bothered me ever since my exposure to it in high school.<\/p>\n

As you know, the Rule of Signs runs something like this:<\/p>\n

For a polynomial with non-zero real coefficients, the number of positive roots is, at most, the number of sign changes in the coefficient sequence (ordered by power); more specifically, the difference between the number of positive roots and the number of coefficient sign changes is even.<\/p><\/blockquote>\n

For instance, the polynomial<\/p>\n

$$p(x) = x^5 + 2 x^4 – x – 2$$<\/p>\n

has a coefficient sequence \\(\\{1,2,-1,-2\\}\\) with one sign change, so that \\(p\\) has a single positive root.<\/p>\n

The Rule is a curious and far-from-obvious result, and the oft-cited\u00a0proof at Cut the Knot<\/a>\u00a0is effective, but not terribly insightful. It’s not clear\u00a0why<\/em>\u00a0the Rule works. That’s bothersome, of course, but not what bothered me.<\/p>\n

We can also use the Rule to get information about the number of\u00a0negative<\/em>\u00a0roots of a polynomial; we define an auxiliary polynomial that reverses the sign of \\(x\\) … for instance:<\/p>\n

$$q(x) := p(-x) = -x^5+2x^4+x-2$$<\/p>\n

The negative roots of \\(p\\) are the negatives of the positive roots of \\(q\\), and there are either two of those, or none, since \\(q\\) has two coefficient sign changes.<\/p>\n

At this point, we have accounted-for three, or maybe just one, of the roots of \\(p\\). The\u00a0Fundamental Theorem of Algebra<\/a>\u00a0tells us that there should be a total of five. Clearly, none of the roots is zero; but, if we’ve exhausted positive, negative, and zero candidates, then what’s left?\u00a0Non-real complex numbers<\/em>, of course (in conjugate pairs).<\/p>\n

That’s what bothered me.<\/p>\n

Not that I have anything against complex numbers; quite the contrary! The thing is that, while the Descartes Rule of Signs forces us to confront the complex numbers as a fact —and ultimately, a completion— of algebraic life, it won’t address non-reals in any specificity. We get an idea of how many roots lie in either direction along the real axis, but no information about roots along, say, the imaginary axis. That doesn’t seem fair.<\/p>\n

On one level, the limitation is understandable. Consider the trick that allows us to count negative roots of \\(p\\); tweaking this to count roots of along the “positive” imaginary axis would require us to a new auxiliary polynomial thusly …<\/p>\n

$$r(x) := p\\left(\\frac{x}{i}\\right) = p(-i x) = -i x^5 + 2 i x^4 + i x – 2$$<\/p>\n

… and then simply to count sign changes: from “\\(-i\\)” to “\\(2i\\)” is one; from “\\(2i\\)” to “\\(i\\)” doesn’t count; and then from “\\(i\\)” to “\\(-2\\)”—\u00a0Hey, waydaminnit!<\/em>\u00a0The notion of “sign change” from “\\(i\\)” to “\\(-2\\)” doesn’t make any sense! … and so, we give up and go home.<\/p>\n

Of course, that defeatist attitude runs contrary to the proper mathematical philosophy toward apparent nonsense; our instincts should be to\u00a0make sense<\/em> out of what we encounter. Besides, to turn away now is to ignore one of the fundamental conceptual insights of complex algebra: a sign change isn’t the result of a\u00a0discrete flip<\/em>\u00a0across the origin, but rather the result of a\u00a0continuous half-turn<\/em>\u00a0about it. Hmmm …<\/p>\n

Adapting the notion of “sign change” to apply to the transition from “\\(i\\)” to “\\(-2\\)” in a coefficient sequence would seem to be very-nearly obvious: measure the “angular sweep” … which in this case is a quarter-turn (in the standard direction), or \\(\\pi\/2\\). Does this help?<\/p>\n

I’ll cut to the chase: Yes. Yes, it does help.<\/em><\/p>\n

We compute the angular sweep of polynomial \\(r\\) thusly: “\\(-i\\)” to “\\(2i\\)” is a sweep of \\(\\pi\\); from “\\(2i\\)” to “\\(i\\)” doesn’t count; and then from “\\(i\\)” to “\\(-2\\)” is a sweep of \\(\\pi\/2\\). All together, that’s a total sweep of \\(3\\pi\/2\\).<\/p>\n

In the original Rule of Signs, each sign change contributes one to the tally of possible positive roots; it also contributes \\(\\pi\\) to this angular sweep value. Thus, according to Descartes,\u00a0the tally of possible positive roots is exactly equal to the number of half-turns in the sweep.<\/em>\u00a0 (And the Rule admits that the tally may be off by an even number … An even number of half-turns is some number of full circles; we’re used to this kind ofmeasurement when measuring angles! Coincidence?) When the angular sweep lies between half-turns, we (very reasonably) round down; In the case of polynomial \\(r\\), the rounded-down count of half-turns in the sweep is one, so the tally of possible positive roots —equivalently, the tally of \\(p\\)’s roots along the positive imaginary axis— is also exactly one. And, in point of fact, \\(p\\) has \\(i\\) as its sole “positive imaginary” root.<\/p>\n

To look for roots along the “negative imaginary” axis, we construct yet another auxiliary polynomial:<\/p>\n

$$s(x) := p\\left(\\frac{x}{-i}\\right) = p(ix) = i x^5 + 2 x^4 – i x – 2$$<\/p>\n

The angular sweep from “\\(i\\)” to “\\(2\\)” is \\(3\\pi\/2\\); from “\\(2\\)” to “\\(-i\\)” is another \\(3\\pi\/2\\); from “\\(-i\\)” to “\\(-2\\)” is yet another \\(3\\pi\/2\\). \u00a0That’s a total sweep of \\(9\\pi\/2\\), which covers four half-turns. We happen to know that the polynomial \\(p\\) has a single root —namely, \\(-i\\)— along the negative imaginary axis, so the root count is certainly bounded above by the half-turn tally, although it doesn’t differ from that tally by an even number.<\/p>\n

Interestingly, if we sweep from coefficient to coefficient in the clockwise<\/em> direction, \\(s\\)’s angular sweep is \\(\\pi\/2 + \\pi\/2 + \\pi\/2 = 3\\pi\/2\\), which covers a single half-turn, and thus accurately predicts the sole negative-imaginary root of \\(p\\). It makes sense that we should consider oppositely-directed sweeps —and (again, very reasonably) adopt the smaller value as “the” angular sweep— because a polynomial knows nothing of our bias toward counter-clockwise rotations.<\/p>\n

In any case … We now have a version of the Rule of Signs that does justice to the non-reals.<\/p>\n

My note “The Descartes Rule of Sweeps and the Descartes Signature”<\/a> explores these ideas in more depth; in particular, the “Signature” provides a holistic approach to seeking roots in a given direction of the complex plane. Unfortunately, my proof of the Rule of Sweeps is based directly on the Rule of Signs; consequently, we still<\/em> don’t really know why<\/em> this all works. (That’s my current source of bother in this area.)<\/p>\n

The Open Question<\/strong>:<\/p>\n

What is the independent proof of the Rule of Sweeps that establishes the conceptual intuition for believing it?<\/p><\/blockquote>\n

The sweep notion —with its rotational aspect and its quotients by \\(\\pi\\)— seems awfully-closely tied to winding numbers and Cauchy’s Integral Formula<\/a>. I get the sense that we’re one clever contour integral away from enlightenment … but apparently I’m insufficiently clever.<\/p>\n

For interactive engagement with this stuff, see my “Descartes Signature Explorer”<\/a> at the Wolfram Demonstrations Project<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

Something about\u00a0Descartes’ Rule of Signs\u00a0had bothered me ever since my exposure to it in high school. As you know, the Rule of Signs runs something like this: For a polynomial with non-zero real coefficients, the number of positive roots is, at most, the number of sign changes in the coefficient sequence (ordered by power); more […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6,11],"tags":[],"class_list":["post-228","post","type-post","status-publish","format-standard","hentry","category-misc-math","category-open-question"],"_links":{"self":[{"href":"http:\/\/daylateanddollarshort.com\/bloog\/wp-json\/wp\/v2\/posts\/228","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/daylateanddollarshort.com\/bloog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/daylateanddollarshort.com\/bloog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/daylateanddollarshort.com\/bloog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/daylateanddollarshort.com\/bloog\/wp-json\/wp\/v2\/comments?post=228"}],"version-history":[{"count":10,"href":"http:\/\/daylateanddollarshort.com\/bloog\/wp-json\/wp\/v2\/posts\/228\/revisions"}],"predecessor-version":[{"id":266,"href":"http:\/\/daylateanddollarshort.com\/bloog\/wp-json\/wp\/v2\/posts\/228\/revisions\/266"}],"wp:attachment":[{"href":"http:\/\/daylateanddollarshort.com\/bloog\/wp-json\/wp\/v2\/media?parent=228"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/daylateanddollarshort.com\/bloog\/wp-json\/wp\/v2\/categories?post=228"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/daylateanddollarshort.com\/bloog\/wp-json\/wp\/v2\/tags?post=228"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}