Conference rusure::math

        re .0
        
>>      Pick 10,000 random polynomials of degree 31 all of whose
>>      coefficients are either 0 or 1 (and whose constant term
>>      is 1).
        
        Since you didn't say degree <= 31, I presume that the
        coefficient of x^31 must also be 1.
        
>>      Calculate the roots of these polynomials and plot them in
>>      the complex plane.
        
        Does anyone have a routine that returns all of the roots
        of a 31 degree polynomial? :-)
        
>>      find bounds for the figure.
        
        Let r be a positive real and let z be a complex number
        with absolute value r.  All of the terms of the
        polynomial below the highest degree term can add up to a
        number with absolute value at most r^30 + r^29 + ... + r
        + 1 or (r^31 - 1)/(r - 1).  If r^31 is greater than this
        then z cannot be a zero of the polynomial; the lower
        order terms are not large enough to counteract the z^31
        term.  For small positive r, r^31 is smaller.  It is
        smaller for r near 1.  But r^31 is larger for r=2
        (actually for r >= 2).  So the entire figure would fit
        within the circle given by |z| <= 2.  (The actual r
        cutoff is around 2 - epsilon where epsilon is about 5 *
        10^-10.  This curve is *STEEP* near r=2!)
        
        Did Stan say if this exercise was only interesting for
        degree 31?
        
        Dan
        

    The figure looks much the same for various degrees I tried from 8-31 -
    an annular cloud with a set of negative real roots showing as a spike.
    There's a lot of fine structure in the cloud of roots.  Also there are
    some small magnitude roots around smaller annuli.  The annulus is more
    like a fuzzy "C" than a true annulus.

    It is interesting to see the roots appear, and not to just choose the
    coeffecients at random, but to try observing the pattern with the
    coefficients chosen in binary sequence from either end.

    Just some experimental fooling around; for a theory, perhaps looking
    at the polynomial as the characteristic polynomial for certain classes
    of matrices may give a clue.

    - Jim

	By the way, the bound |z| <= 2 - epsilon(n) for the roots
	z works for all positive integral n, not just n = 31.  If
	you let r=2 then r^n is always one more than
	r^(n-1) + ... + r + 1.  Note that epsilon -> 0 as n -> oo.

	Dan

    I'm not certain of this, but here are tentative bounds...

    The roots lie in a C shaped annular region with a spike of negative
    real roots.  Since the polynomial coefficients can be reversed (because
    all polynomials have 1/0 coefficients and leading and trailing 1
    coefficients) the roots will be bounded by an annular region of radius
    r and 1/r.

    The negative real roots lie in the interval given by the golden ratio,
    the magnitude of the roots of x^2 - x - 1, or (-1.61803, -61803)

    The complex roots lie in C shaped region within an annulus whose
    radius is given magnitude of the largest modulus root of the
    polynomial

	x^8 + x^7 + x^6 + x^4 + x - 1

    a radius around 1.3641995455827725 and its inverse.  I'm not
    certain of the angle of closing of the C, but in the limit with very
    high degree polynomials it would close up.  Because of the circular
    near-symmetry, you could map the unit circle to the real line with a
    fractional linear transformation and get bounds on the resulting
    cluster of roots clustering along the real axis to find how near the C
    is to closing.

    How does this arise?  Some digital filtering problem?  You could view the
    polynomial as the characteristic equation for a recursive filter...

    These results come from looking at the polynomial as a truncated
    infinite series, where you choose the pattern of 1/0 coefficients
    to maximize a certain roots.

    - Jim

        How are you computing the roots of these high degree
        polynomials?  For each polynomial are you getting all of
        its roots?
        
        Dan

    I experimented a bit further and suspect that the bounds on the complex
    annulus around the roots doesn't hold good... in fact, raising the degree
    to the 40's starts to show a dense band of roots along the unit circle
    with a sparser cloud extending outward, and the thickness decreases
    toward the right hand side (opening of the C).

    Basically the idea is that you want to vary the coefficients
    a[k] = { 0, 1 }, and find the set which gives a maximum (or minimum)
    modulus root to get the bounds.  This would be a good fit if the roots
    were evenly distributed in an annulus, but the higher degree cases
    don't seem to follow a simple pattern.

    In the limit you want to find the coefficients so that the analytic
    function

	1 + a[1]*z^-1 + a[2]*z^-2 + ...

    has an extreme root.  For the negative real case it's easy -
    delete the even powers, and the extreme case can only occur with
    all the odd powers contributing, so you can telescope the sum and solve
    a quadratic.

    But for the complex, it's not at all obvious how to choose the a[k]'s,
    so I just varied the leading ones and printed them when a new maximum
    was hit.  It looked like the pattern in decreasing powers was

	1  1 1 0 1 0 0 1 0  1 1 0 1 0 0 1 0  1 1 0 1 0 0 1 0 ...

    and telescoping this leads to an 8'th degree polynomial.  But I saw a
    counterexample that's a little better and it doesn't seem to be a fault
    of roundoff; the polynomials are well-conditioned.

    I computed all the roots for this and stepped the a[k]'s in a binary
    sequence.  One reliable way is to fill in a companion matrix and use an
    unsymmetric eigenvalue finder; I used a QR algorithm in double precision
    from EISPACK.

    Oh well, it couldn't be so simple.  I still think there's a digital
    filter interpretation that would be helpful.

    - Jim