Background: The Descartes Rule of Sweeps and the Descartes Signature
The Descartes Rule of Signs
states, for a polynomial with non-zero real coefficients, that the number of positive roots is no greater than the number of sign changes in the coefficient sequence. The Rule of Sweeps
generalizes this result to cover polynomials with non-real coefficients, and it gives rise to the Descartes signature,
a function that conveys information about potential roots in any direction of the complex plane.
Imagine a needle with one end anchored at the origin and the other end initially pointing in the direction of the trailing coefficient of a polynomial,
, with (non-zero, but not-necessarily-real) complex coefficients. (The trailing coefficient is the coefficient of the term of least degree.) Let the needle sweep—always counter-clockwise—to point in the direction of the second, third, etc. coefficients, "stalling in place" when successive coefficients lie in the same direction, and tracing out a "sweep spiral". The positive sweep
is the total angle swept by the needle; the negative sweep
is the total angle swept by a clockwise-spinning needle (or, equivalently, a counter-clockwise-spinning needle that takes the coefficients in reverse order); these values are usually different, and the sweep
is defined to be the smaller of the two. The sweep plays the role of the sign-change tally from the Descartes Rule of Signs, providing a bound on the number of positive roots of
The Descartes Rule of Sweeps.
The maximum number of positive roots of
, or 1 less if a line through the origin meets the leading and trailing coefficients but misses at least one other.
Note that the first part of the rule of sweeps covers the Descartes rule of signs, since each coefficient sign change contributes
to a polynomial's sweep.
To study the roots in a particular direction of the complex plane, define an auxiliary polynomial
is the degree of the smallest-degree term of
whose coefficients are obtained by "fanning out" the coefficients of
by multiples of
is a positive root of
is a root of
; thus, applying the rule of sweeps to
gives a bound on the number of roots of
that lie in direction
as a parameter ranging from
, the Descartes Signature
—is the function that gives that bound, and thus its graph conveys a comprehensive summary of the potential number of roots of
in all directions. Writing
for the positive, negative, and minimal sweep of
gives the following result:
The maximum number of roots of
is given by
, or 1 less if etc., etc., etc.
Note: Because the Descartes signature depends only on the directions of a polynomial's coefficients, and not on their magnitudes, an infinite family of polynomials share the same signature. For instance,
has the same Descartes signature as
, for any positive numbers
. As a result, a polynomial's signature rarely reveals unambiguous information about its roots; nevertheless, as this Demonstration shows, the signature can be helpful in ruling out entire intervals of
values that cannot serve as directions of roots.
For more information: See "The Descartes Rule of Sweeps and the Descartes Signature" [online PDF]
The Demonstration: The Display Modes sweep spirals
mode shows the coefficients defined by the coefficient angles
settings, and the positive (blue) and negative (red) sweep spirals joining them. When the auxiliary angle
is non-zero, the display illustrates the "fanning out" process that yields the coefficients and spirals of
. The top of the display records the color-coded values of the sweep functions, which give the total angles swept out by the spirals (blue and red), and the minimum of these numbers (purple).
mode shows the graphs of
(red), revealing these to be piecewise linear functions with predictable jumps: the jumps occur when a coefficient of
"catches up with" its predecessor as they fan out; the size of the jump is
times the number of instances of this catching-up that occur.
mode shows the graph of
(black and green). The green dots indicate when the "or 1 less …" aspect of the rule of sweeps has come into play. The top of the display records the value of the Descartes signature function at the current auxiliary angle; this value turns green for "or 1 less ..." values. (See Implementation Caveat
The Demonstration: The Controls sweep spirals / sweep graphs / Descartes signature
: This control selects the display mode (see above).
: Define a polynomial by clicking the checkboxes for the powers to include, and setting the sliders for the direction of the coefficients. (As with the rule of signs, the rule of sweeps ignores the size of the coefficients.)
auxiliary angle ()
: In sweep spirals
mode, this value fans out the polynomial coefficients, with the
-th power coefficient rotating through the angle
. In sweep graphs
and Descartes signature
modes, the value controls a vertical indicator of the
The Demonstration: Things to Try Polynomials of the form
. The Descartes signature clearly identifies
symmetrically-spaced angles (corresponding to the "
-th roots of unity") as the only viable directions for roots.
Polynomials of the form
. Such a polynomial's roots are also roots of unity (except 1 is missing). The Descartes signature is less successful at highlighting them than the preceding example, but the graph is interesting.
The conditions defining the various jumps in the graph involve comparing combinations of numbers against π. This requires a certain amount of computational accuracy, which is undermined by the "play" in the sliders controlling the coefficient and auxiliary angles. The user should therefore not be surprised by errors in the displayed value of
at points of discontinuity.
Likewise, the user should be encouraged to validate the (non-)appearance of "green dots" in Descartes signature
mode. This can be done by moving the auxiliary angle indicator to a suspect location and then to switch back to sweep spirals
mode to verify that the coefficients are (or are reasonably close to being) in their proper configuration.
Note that, for the "or 1 less ..." condition to be considered at all, the polynomial sweep must be a multiple of π (an easy situation to spot, as this happens at the endpoints of the steps in the signature graph); generally speaking, this is enough. For the sweep to be a multiple of π and yet for the "or 1 less ..." condition to fail
, all of the coefficients must be collinear with the origin—for instance, they could be all real—which is fairly unusual.