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.