Zero location for Polynomials with Random Coefficients 1.1 2007/09/28 05:13:33.882 GMT-5 2007/11/27 22:03:58.301 US/Central C. Sidney Burrus csb@rice.edu C. Sidney Burrus csb@rice.edu location polynomial root zero The zeros of a polynomial with random coefficients cluster around the unit circle in the complex plane. As the degree increases, the roots cluster tighter and tighter to the unit circle. This phenomenon is illustrated here.

Zero Location of Polynomials with Random Coefficients The location of the zeros of polynomials with random coefficients have the remarkable property of being clustered around the unit circle of the complex plane. They are uniformly distributed around the unit circle with a very sharp peak in their radial distribution at one. This has been reported and described in 1966 by Arnold and others , but only with the development of the Lindsey-Fox algorithm have we been able to factor really high degree polynomials and observe the phenomenon. Thousands of multi thousand degree polynomials with random coefficients have been factored and a few multi million degree ones as well. The following plots of the locations of these zeros will illustrate the phenomenon. There is a literature on this subject, but seeing the actual root location is still impressive and informative and aids in developing other factoring strategies. The following figures show the zero locations for random coefficient polynomials of degree 10 through 2000. These were found using Matlab by generating the random coefficients with the “rand” command, then factoring the resulting polynomial with the “roots” command (an eigenvalue method), and finally creating the graphics with the “plot” command. The results are relatively independent of the type of distribution of the random coefficients.

Zero Locations for N=10

Zero Locations for N=20

Zero Locations for N=50

Zero Locations for N=100

Zero Locations for N=200

Zero Locations for N=500

Zero Locations for N=1000

Zero Locations for N=2000

The following figures show histograms of the radial distribution or density of the zeros of polynomials with random coefficients. The random coefficients were generated in Matlab and the factoring was done with the Lindsey-Fox algorithm in Matlab.Although it is not easy to see from these figures, the shapes of the distributions are fairly independent of degree and the width is almost exactly linear with the inverse of the degree. As the degree goes to infinity, the zeros all go to the unit circle!

Number of Zeros at a Radial Distance in the Complex plane, N=100

Number of Zeros at a Radial Distance in the Complex plane, N=1,000

Number of Zeros at a Radial Distance in the Complex plane, N=10,000

Number of Zeros at a Radial Distance in the Complex plane, N=100,000

Number of Zeros at a Radial Distance in the Complex plane, N=1,000,000