Real Root Isolation of Polynomials

Let's first list a few properties about polynomials. Given a polynomial \[    f(x) = \alpha_0 + \alpha_1 x + ... + \alpha_n x^n    \]

the Fundamental Theorem of Algebra tells us that there are $n$ complex roots (counted with multiplicity). A root $r$ has multiplicity $k$ if $f(r) = f'(r) = ... = f^{(k)}(r) = 0 \neq f^{(k+1)}(r)$. A root is simple if it has multiplicity one and a polynomial is square-free if all of its roots are simple. The complex roots must come in conjugate pairs and any rational roots must be of the form (factor of $a_0$) / (factor of $a_n$). Also, the ratio $(-1)^k \alpha_{n-k}/\alpha_n$ gives the sum of the products of all $k$-combinations of roots. Lastly, a result of Cauchy is that the magnitude of any root is bounded by $M = 1 +\max \left| a_i/a_n \right|$.

These properties as well as Descartes' rule of signs (stated below) and synthetic division can all be used to find the roots of a polynomial. Other methods include Newton's, Bisection, Secant, Regula Falsi, etc. Below describes two subdivision methods for isolating all the real roots of a square-free polynomial with real coefficients. They work by determining whether an interval contains zero roots, one root, or multiple roots, and then respectively discarding, storing, or subdividing the interval. The methods can be generalized but not without some effort.

Box Method and code

Descartes' Method


_________________________________________________________________________________

Pólya Enumeration

Pólya Counting enables you to count the equivalence classes of group acting on a set. For example, you might want to find the number of ways to color the corners of a square red or blue, respective of symmetry. The permutation group of symmetries is the dihedral group $D_4$. Pólya Counting gives the generating function $$P_{D_4}(r+b,r^2+b^2,r^3+b^3,r^4+b^4) =  r^4 +r^3b + 2r^2b^2 + rb^3 + b^4$$ where the coefficient in front of $r^pb^q$ tells you the number of nonequivalent colorings given that $p$ corners are colored red and $q$ are colored blue. Thus, the total number is of colorings is 6.

This method can be easily applied to PE 281: Pizza Toppings. It can also be used to count the number of non-isomorphic graphs. [code]

I've Tex'd up some notes for my own reference that are accessible in the link below. The proof is only outlined so it is a bit terse but the example problems should be enough to show how the method is used. Polya Counting Notes


_________________________________________________________________________________