Roots of Polynomials with Coefficients of 1, -1

Mark Sherry


Contents

Summary

There is interest in determining whether, given a $ S$ , whether there exists a polynomial $ p$ such that all of $ p$ 's coefficients are in $ S$ and $ \alpha$ is one of $ p$ '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 $ \frac{1}{2} \le \left\lvert z \right\rvert \le 2$ . This reduces the search space considerably. What's more, certain symmetries exist: if $ \alpha$ is a root of $ a_0 + a_1 x + a_2 x^2 + \dots$ then $ -\alpha$ is a root to $ a_0 - a_1 x - a_2 x^2 - \dots$ , thus both $ \alpha$ and $ -\alpha$ are roots or neither are. In addition, $ a_0 + a_1 x + \dots = 0 = \overline{a_0} + \overline{a_1x} + \dots$ , and so if $ \alpha$ is a root, then so is $ \overline{\alpha}$ , where $ \overline{\cdot}$ indicates complex conjugate, and if $ \alpha$ is the root of $ a_0 + a_1 x + \dots a_n x^n$ then $ \frac{1}{\alpha}$ is a root of $ a_n + a_{n-1} x + \dots a_0 x^n$ . 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 $ p = a_0 + a_1x + \dots + a_n x^n$ , $ a_i \in \{-1, 1 \}$ , we can determine whether there exists any polynomial whose first $ n+1$ terms match $ p$ 's with $ \alpha$ as a root by considering whether $ \left\lvert p(\alpha) \right\rvert $ is too great as follows: Assume that $ \alpha$ is a root of $ q$ , an $ m$ -degree polynomial. Then

0 $\displaystyle =$ $\displaystyle \left\lvert q(\alpha) \right\rvert$  
  $\displaystyle =$ $\displaystyle \left\lvert \sum_{i=0}^m a_i x^i \right\rvert$  
  $\displaystyle \le$ $\displaystyle \left\lvert \sum_{i = 0}^n a_i x^i \right\rvert + \sum_{i = n+1}^m \left\lvert a_i x^i \right\rvert$  
  $\displaystyle =$ $\displaystyle \left\lvert p(\alpha) \right\rvert + \sum_{i = n+1}^m \left\lvert a_i x^i \right\rvert$  
  $\displaystyle \le$ $\displaystyle \left\lvert p(\alpha) \right\rvert + \sum_{i = n+1}^m \left\lvert x^i \right\rvert$  

Thus for $ \alpha$ to be a root of a polynomial of the appropriate form, there must exist an $ n$ -degree polynomial $ p$ such that $ \left\lvert p(\alpha) \right\rvert \le \frac{\left\lvert x^{n+1} \right\rvert }{1 - \left\lvert x \right\rvert }$ for all $ n$ .

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 $ n$ -th degree polynomial $ p$ doesn't satisfy our criteria, we don't examine its descendants, i.e. those polynomials whose first $ n$ coefficients match $ p$ 's. In this way, we don't have to explore all $ 2^{51} -1 = 2251799813685247$ 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 $ maxdepth$ , 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 $ width/2$ 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 $ 2n$ to a $ 2^n \times 2^n$ image. A polynomial $ a_0 + a_1 x + a_2 x^2 + \dots + a_{2n} x^{2n}$ maps to the point $ (2^{n/2-1} + a_1 \cdot 2^{n/2 - 2} + a_3 \cdot 2^{n/2 - 3} + a_5 \cdot 2^{n/2 ... ... a_2 \cdot 2^{n/2 - 2} + a_4 \cdot 2^{n/2 - 3} + a_6 \cdot 2^{n/2 - 4} + \dots)$ . The $ a_0$ term is ultimately irrelevant, since if $ \alpha$ is a root of $ p$ , then it's also a root of $ -p$ . By assuming that $ a_0 = 1$ in all polynomials, we only examine $ p$ or $ -p$ , not both.

An example of a polynomial map for the point $ 0.45286 + 0.89157i$ 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 $ m$ -degree polynomial doesn't fit the necessary criteria, all of the polynomials starting with the same coefficients are coloured the colour corresponding to $ m$ to indicate the point at which their branch of the tree got pruned.

Examining the polynomial maps, certain properties become evident. For values $ \vert z\vert$ near $ 1$ , almost every polynomial is 'near' it - one has to examine progressively higher degree polynomials to find ones that fail the criteria. As $ z$ approaches the periphery, polynomial families get eliminated more rapidly. Especially near the edges, there are a lot of potential dead-ends, where knowledge of the paths through the tree can reduce the time necessary to verify whether a point is in the interior.

Examining the line $ y=0$ , we discover a number of interesting patterns. As we move towards to edge of the interior from $ z = 0$ , the points corresponding to higher degree polynomials begin to form a line, indicating a large degree of self-similarity in the map. Indeed, an examination of

demonstrates that the top right and bottom left quadrants are extremely self-similar.

As we move further closer to $ z = 1$ , the line begins to bifurcate with increasing rapidity. The image begins to resemble a mosaic.

Moving instead along the line $ x = 0$ , we get a different picture altogether. Instead of two primarily active quadrants, the image is active everywhere with two axes of symmetry.

Along $ x = y$ , however, we find a blend of the two patterns; a hodge-podge in which characteristics can be recognized, but not predicted.

From this we can predict that there are no easy ways to predict the optimal tree search path given an arbitrary point.

A 2-dimensional representation was chosen over a linear one as more data could be presented at once to the viewer; a 1024x1 image could only represent up to 10th degree polynomials.

Source Code and Toys

Available for download is the source code used to generate the fractals and polynomial maps used for this project. Included in the tarball is two C files, a header file specifying a palette and a Makefile. Provided that libpng's library and development files are available in the standard search paths, the programs can be compiled by running make.

The first of the two programs generated is fractdraw, which generates fractal images. It has two optional parameters - size of the image, and recursion depth. By default, the image has a width and height of 1024 pixels and a recursion depth of 50. The image is always square in order to take full advantage of the symmetries. Usage information can be obtained via the -help parameter. Upon completion, a PNG file named fractal.png.

The second of the two programs is polymap, which generates polynomial maps as described above. Unlike fractdraw, it takes no parameters and always generates 1024x1024 images of recursion depth 20. While running, polymap will generate over a quarter million image files, each between 5 and 50 kilobytes in size. Be careful running this program if you don't have several gigabytes of free space and plenty of time - it takes approximately two minutes to compute the maps for a single y value on a P4 1.8 GHz processor. The image files generated will be named in the form poly-$ x$ ,$ y$ .png.

An interactive method of browsing polynomial maps can be found here. Simply move the mouse cursor over the image of the fractal, and the polynomial map corresponding to the point under the cursor will be shown to the right.