Mark Sherry

# Summary

There is interest in determining whether, given a , whether there exists a polynomial such that all of 's coefficients are in and is one of 's roots. Here, I have examined the behaviour polynomials whose coefficients are 1 or -1.

# Finding Roots

From a theorem by Cauchy (1829), we have that in this case the roots of the polynomial lie in the annulus . This reduces the search space considerably. What's more, certain symmetries exist: if is a root of then is a root to , thus both and are roots or neither are. In addition, , and so if is a root, then so is , where indicates complex conjugate, and if is the root of then is a root of . Because of this, we only need to perform computations on one eighth of the annulus, namely the upper-left portion with magnitudes less than 1.

Given a polynomial , , we can determine whether there exists any polynomial whose first terms match 's with as a root by considering whether is too great as follows: Assume that is a root of , an -degree polynomial. Then

 0

Thus for to be a root of a polynomial of the appropriate form, there must exist an -degree polynomial such that for all .

# Building the Fractal

Given a way to remove points from consideration, one might consider graphical representations of what regions roots might be found in. Colouring each point according to the greatest degree polynomial considered, we get the image

The basic algorithm can be described by the following pseudocode:

function checkPolynomial( z, value, n, maxdepth ):
if n == maxdepth:
return n
// Check if this polynomial is giving a value that's too large
if value > |z|^(n+1)/(1 - |z|):
return n
// Still good. Recurse.
result = max{ checkPolynomial( z, value + z^n, n+1, maxdepth ), checkPolynomial( z, value - z^n, n+1, maxdepth ) }
return result

for point in image:
z = convertToScaledComplex(point)
image[point] = checkPolynomial( z, 0, 0, 50 )


We recursively explore all polynomials up to a given degree (in this case 50). If an -th degree polynomial doesn't satisfy our criteria, we don't examine its descendants, i.e. those polynomials whose first coefficients match 's. In this way, we don't have to explore all possible polynomials, which would take prohibitive amounts of time. By doing pruning, with a maximum search depth of 50, the average number of polynomials examined is 38391.741134643555, with a maximum of 279526156. By recording the path taken examining the tree, we can further reduce search times in cases where the point is a root by taking advantage of the fact that frequently neighbouring points are roots to similar polynomials. By stopping our search when we find a path that leads to a valid polynomial of degree , we can thus verify many interior points by examining only 50 polynomials. In fact, through this simple enhancement, the average number of polynomials examined drops to 3806.7528839111328 with the maximum examined 91924667 - one third the maximum for the un-enhanced algorithm. Further improvements could likely be obtained by exploiting locality in two dimensions rather than one, although this would require either a different drawing method than the traditional scan lines, or increased memory overhead to store old search paths (exploiting the symmetry).

# Examining the Polynomial Trees

Insight about the particular polynomial related to a given point and what polynomials it was a 'near' root to can be obtained visually by mapping the space of polynomials of degree to a image. A polynomial maps to the point . The term is ultimately irrelevant, since if is a root of , then it's also a root of . By assuming that in all polynomials, we only examine or , not both.

An example of a polynomial map for the point follows. The colour scale progresses from dark blue to dark purple to light blue to light purple to red to indicate a higher degree polynomial. If an -degree polynomial doesn't fit the necessary criteria, all of the polynomials starting with the same coefficients are coloured the colour corresponding to to indicate the point at which their branch of the tree got pruned.

Examining the polynomial maps, certain properties become evident. For values near , almost every polynomial is 'near' it - one has to examine progressively higher degree polynomials to find ones that fail the criteria. As approaches the periphery, polynomial families get eliminated more rapidly.