On this website, I will collect results, algorithms, software and tables about expanding and Pisot polynomials. My own interest (at the moment, April 2010) is in enumerating those with integer coefficients, and where some coefficients have been given in advance.
This website is maintained by Christiaan van de Woestijne. Click here to return to my home page.
Because the computations of the programs given below tend to be rather (or very) expensive, I think it is worthwhile to present the already computed results here in the form of tables of polynomials.
Note: to load these files into (for example) MAGMA or KANT, you must first define x (lower case) to be a polynomial variable with integer coefficients.
I use a rather ingenious way of sorting polynomials by increasing complexity. I consider a polynomial more complex if it has more nonzero coefficients, or if its nonzero coefficients correspond to higher degree terms. So, I first sort them lexicographically by support, with highest degree terms first, and only if the supports are equal, I sort by the coefficients in ascending order. (Maybe I should sort in ascending order of modulus, with positive before negative. I'll do that sometime.)
The tables give the exact output of my MAGMA code, after conversion to polynomial notation and sorting. It may be that I produced some code bugs that prevent the code from finding all expanding polynomials. However, I checked by another method that all polynomials given here are in fact expanding.
The following describes my highly optimised (I believe...) MAGMA program for enumeration. The following functions are of interest:
| Name | EnumerateExpandingPolynomials |
| Arguments | Degree: a positive integer |
| LeadingCoefficient: a nonzero integer | |
| ConstantCoefficient: a nonzero integer | |
| Options | Period: a positive integer (default: 1000) |
| Output | - a list of coefficient lists |
| - the time spent in precomputation | |
| - the total (CPU) time spent | |
| Example | > p6n3, ptime, ttime := EnumerateExpandingPolynomials( 6, 1, 3 : Period := 10000 ); |
| Precomputing symmetric polynomials... | |
| Precomputing Schur-Takagi determinants... | |
| Factoring the determinants... | |
| Precomputation done in time 0.040 . | |
| 10000 polynomials tested. now: [ 1, 1, -5, 4, -17, 4, 3 ] | |
| 20000 polynomials tested. now: [ 1, 2, 7, -6, 26, 7, 3 ] | |
| 30000 polynomials tested. now: [ 1, 3, -1, -11, 12, 12, 3 ] | |
| 40000 polynomials tested. now: [ 1, 5, 7, -5, 22, 15, 3 ] | |
| Tested in total: 41294 | |
| > #p6n3; ptime; ttime; | |
| 719 | |
| 0.040 | |
| 2.210 |
| Name | EnumeratePisotPolynomials |
| Arguments | Degree: a positive integer |
| PisotNorm: an integer of modulus at least 2 | |
| TraceBound: a positive integer | |
| Options | Period: a positive integer |
| Output | - a list of coefficient lists |
| - the time spent in precomputation | |
| - the total (CPU) time spent | |
| Remark | Currently, the output does not really give only polynomials with trace at most TraceBound in absolute value. Rather, TraceBound controls some internal quantity that has a somewhat loose relationship to the trace. I hope to improve this in a later version. At any rate, by letting TraceBound grow, you will obtain eventually all monic Pisot polynomials of the given degree and constant coefficient, and every Pisot polynomial occurs only once. |
| Example | > p6nm2, pt, tt := EnumeratePisotPolynomials( 6, -2, 5 ); |
| Precomputing symmetric polynomials... | |
| Precomputing Schur-Takagi determinants... | |
| Factoring the determinants... | |
| Precomputation done in time 0.020 . | |
| Precomputations for constant coefficient 4 | |
| ...done. | |
| Test counter after constant coefficient 4 : 208 | |
| Precomputations for constant coefficient -4 | |
| ...done. | |
| Test counter after constant coefficient -4 : 416 | |
| Precomputations for constant coefficient 5 | |
| ...done. | |
| 1000 polynomials tested. now: [ 3, -2, 5, 12, -2, 5 ] | |
| Test counter after constant coefficient 5 : 1741 | |
| Precomputations for constant coefficient -5 | |
| ...done. | |
| 2000 polynomials tested. now: [ 3, -7, 10, -12, 11, -5 ] | |
| 3000 polynomials tested. now: [ 3, 11, 23, -30, -17, -5 ] | |
| Test counter after constant coefficient -5 : 3066 | |
| Tested in total: 3066 | |
| > #p6nm2; pt; tt; | |
| 34 | |
| 0.020 | |
| 0.210 |
I do all the computations with coefficient lists instead of polynomials, for reasons of speed. However, it is easy to convert: in MAGMA, just say Zx!Reverse( l ) if l is a coefficient list.
Click here for the code (version 4). Please mail me if you do anything with it (use it, change it, like it, etc).