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.