Polynomial roots Dan Christensen jdc@uwo.ca
----------------
Contents
--------
1. Some mathematics
2. The symmetries we use
3. The code
1. Some mathematics
-------------------
Defn: Let f be in Z[x]. Define *gcd(f)* to be the gcd
of the coefficients of f. A polynomial f is *primitive*
if it has gcd 1.
Lemma: gcd(fg) = gcd(f) gcd(g)
Cor: If f is in Z[x] and f=gh with g, h in Q[x], then there
exists a rational q such that qg and (1/q)h are both in Z[x].
Cor: If f is irreducible in Z[x], then it is irreducible in
Q[x].
See http://web.usna.navy.mil/~wdj/book/node100.html for some details,
but they are easy.
Defn: An *algebraic number* is a root of a polynomial in Z[x]
(equivalently, Q[x]).
Prop: If a is algebraic, then there is a p(x) in Z[x] such that p(a)
= 0 and p divides any other polynomial having a as a root. This p is
unique up to sign, has gcd 1, is irreducible, and has minimal degree
among all polynomials having p as a root. [This is slightly
non-trivial, but I think it is correct.]
Defn: The p from the proposition is called the *minimal polynomial*
of a. The *degree* of a is the degree of p. The *height* of a is the
*height* of p, which is the maximum of the absolute values of the
coefficients. The *lcm* of a is the lcm of the coefficients of p.
Defn: The *reverse* of p(x) is x^d p(1/x), where d = degree p.
The roots of the reverse are just 1/roots of p. p is irreducible
if and only if its reverse is.
Prop: An irreducible polynomial over Z[x] has no repeated roots.
Pf: Let p in Z[x] be irreducible and let a be a multiple root of p.
Then p(a) = 0 and p'(a) = 0. Also, degree p > 1, so degree p' >= 1.
But p is a scalar multiple of the minimal polynomial of a, which is
a contradiction. //
Note: A Littlewood polynomial (all coefficients +-1, no zero
coefficients) can factor into a product of other Littlewood
polynomials and can have repeated roots:
x^3 + x^2 - x - 1 = (x - 1) * (x + 1)^2
And it can factor into non-Littlewood polynomials:
x^7 + x^6 + x^5 + x^4 - x^3 - x^2 - x - 1 = (x - 1) * (x + 1)^2 * (x^2 + 1)^2
And the coefficients can be larger than 1 in absolute value:
x^5 + x^4 - x^3 + x^2 - x - 1 = (x - 1)*(x^4 + 2*x^3 + x^2 + 2*x + 1)
or
-x^11 - x^10 - x^9 + x^8 + x^7 - x^6 + x^5 - x^4 - x^3 + x^2 + x + 1
= (-1) * (x - 1) * (x + 1)^2 * (x^8 + 2*x^6 - 2*x^5 + 3*x^4 - 2*x^3 + 2*x^2 + 1)
See info at top of genroots-sd.py about -f and -d switches.
Littlewood polynomials with even degree can factor too, e.g.
x^6 + x^5 + x^4 + x^3 - x^2 + x + 1 = (x^3 - x + 1) * (x^3 + x^2 + 2*x + 1)
But can they have repeated roots? Didn't find any up to degree 22
(but method involved comparing string representations).
Couldn't find any multiple roots that weren't very close to
the unit circle with degree <= 26, but did find four non-symmetric
examples of degree 27:
x^27 - x^26 + x^25 - x^24 + x^23 + x^22 - x^21 - x^20 - x^19 + x^18 - x^17 - x^16 - x^15 - x^14 + x^13 + x^12 - x^11 + x^10 - x^9 + x^8 + x^7 - x^6 - x^5 - x^4 - x^3 - x^2 + x + 1
x^27 - x^26 + x^25 - x^24 + x^23 + x^22 - x^21 - x^20 + x^19 - x^18 - x^17 + x^16 - x^15 + x^14 - x^13 + x^12 - x^11 + x^10 + x^9 - x^8 - x^7 - x^6 - x^5 - x^4 - x^3 - x^2 + x + 1
x^27 - x^26 + x^25 + x^24 - x^23 + x^22 + x^21 - x^20 + x^19 - x^18 - x^17 - x^16 - x^15 + x^14 - x^13 - x^12 - x^11 + x^10 - x^9 + x^8 + x^7 - x^6 - x^5 - x^4 - x^3 - x^2 + x + 1
x^27 - x^26 + x^25 + x^24 - x^23 + x^22 + x^21 + x^20 - x^19 - x^18 + x^17 + x^16 - x^15 - x^14 + x^13 + x^12 - x^11 + x^10 - x^9 + x^8 + x^7 - x^6 - x^5 - x^4 - x^3 - x^2 + x + 1
All have x^3-x^2+1 as a factor with multiplicity 2. See message to
John and Sam, Nov 26 2012.
Can one characterize the polynomials in Z[x] that divide into a
Littlewood polynomial? Not all do, because the roots must lie in an
anulus. And by looking at a possible factor of the form a x^2 + b x + c,
can see some clear constraints.
A message John forwarded from Timothy Foo in January 2012 might be
relevant.
2. The symmetries we use
------------------------
If x is a root of a minimal polynomial with coefficients in the
specified range, so are -x, x*, -x*, 1/x, -1/x, 1/x* and -1/x*,
where x* denotes the complex conjugate of x. We put restrictions
on the polynomials to try to ensure we only generate one of these 8.
We probably don't do it perfectly, but get pretty close.
The postscript file that is generated also only has 1 out of 8 of the
roots. It's the postscript driver (possibly internal to the printer)
which does the calculation of the other 7 roots!
3. The code
-----------
The code is available at
http://jdc.math.uwo.ca/roots/polynomial-roots.tar
It generates all roots of irreducible polynomials of degree at most D
whose coefficients are integers between -H and H (the "height"), taking
into account the symmetries above.
The file genroots.sage uses the free software sage and scipy (both
based on python) to generate the roots and write them in a fairly
compact format to a file. 8-fold symmetry is taken into account to
reduce the file size significantly (see below).
Then plotfromfile.py reads the file containing the roots and outputs
postscript.
Both programs have some comments explaining their operation. They
were last tested in February 2006, so they may have suffered some bit
rot.
The postscript that is output is non-standard. gv displays it fine
(turn off antialiasing to speed it up immensely) but it wouldn't print
directly on my home computer connected to an Epson printer (no error
shown). However, if I convert to epsi with
ps2epsi file.ps file.epsi
the latter file prints fine. In fact, the total time to print this
at high quality settings is amazingly short. [Added later: I think
all that is missing is a "showpage" at the end of the .ps files.]
I also tried ps2ps, but it produces a ps file that gv can't read
(and the ps file is *huge*).
Software used
-------------
python: http://python.org/
Overall language used.
sage: http://sagemath.org/
Used to test irreducibility.
scipy: http://scipy.org/
Used to numerically find roots of polynomials.
postscript: http://www-cdf.fnal.gov/offline/PostScript/PLRM2.pdf
The output is a program written in the postscript language.
psyco: http://psyco.sourceforge.net/
Used to speed up the python code, but it's use can be commented out.
Files
-----
genroots.sage Generate the roots and write them to stdout.
plotfromfile.py Read the roots from a file and generate postscript.
ent.py: Simple python module that does gcd calculations.
xcombine.py Simple python module that makes it easy to loop
over various ranges.