# Enumerating expanding and Pisot polynomials

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.

### Tables

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.)

You want expanding polynomials of degree and norm ?

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.

### Software

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).

Last changed by Christiaan van de Woestijne on 12 April, 2010.