Search Algorithms

Exhaustive Search

It is possible to determine all polynomials of a given degree D having bounded Mahler measure.

Searches performed using measure bound 1.3:

1980       D ≤ 16         (Boyd)
1989       D = 18,20      (Boyd)
Jan 1996   D = 22         
May 1996   D = 24         
2003       D ≤ 40         (Flammang, Rhin, Sac-Epee, Wu)
2008       D ≤ 44         (Rhin, Mossinghoff, Wu)

Searches performed using measure bound given by the smallest known measure of the given degree:

2008       D ≤ 54         (Rhin, Mossinghoff, Wu)

Height One Search

This strategy checks all polynomials of a given degree D whose coefficients lie in {-1,0,+1}. It is a fact that all integer polynomials with Mahler measure less than 2 divide a polynomial of this form.

Searches performed:

1980       D ≤ 26, reciprocal        (Boyd)
1989       D = 28,30,32, reciprocal  (Boyd)
Jan 1996   D = 34,36, reciprocal
Mar 1996   D = 38, reciprocal
May 1996   D = 40, reciprocal
Sep 1996   odd degree D ≤ 39, reciprocal and antireciprocal,
           even degree D ≤ 40 antireciprocal.

Adjusted Cyclotomic Product Search

In this algorithm, we construct all polynomials of a given degree D that are products of cyclotomic polynomials, with certain restrictions on the maximum multiplicity of each cyclotomic factor. We then adjust some of the coefficients of each such product, e.g., by adding plus or minus 1 to the middle coefficient.

Searches performed:

1995       D ≤ 64         

Sparse Polynomial Search

This strategy checks all reciprocal and antireciprocal polynomials having height one and a fixed number n of nonzero coefficients. All the known small limit points of Mahler measures are realized as limits of Mahler measures of sequences of polynomials having only 6 or 7 nonzero coefficients.

Searches performed (summer, fall 1996):

  n   max D
5,6,7   181
 8,9    131
10,11   101
12,13    75
14,15    55
16,17    47
18,19    43

Petr Lisonek of Simon Fraser University also performed a sparse polynomial search in January 2000, finding 42 new polynomials with measure less than 1.3 and degree between 174 and 180.

A Statistical Method

G. Rhin and J.-M. Sac-Epee generated polynomials with small measure by using a multinormal distribution to generate the coefficient vectors, employing a polynomial of the form xⁿ+1 as the mean of the distribution. This method found 19 additional polynomials with measure less than 1.3 and degree between 174 and 180.

A Method of Descent

G. Rhin and J.-M. Sac-Epee also investigated a method of generating polynomials with small measure in an iterative way. Starting with a seed polynomial, they perturb the coefficients in some specific ways and select the adjustment that reduces the measure most. The process is then repeated.

Return to the Lehmer's Problem home page.