Lehmer's Problem

"The following problem arises immediately. If ε is a positive quantity, to find a polynomial of the form

f(x) = x^r + a₁ x^r-1 + ... + a_r
where the a's are integers, such that the absolute value of the product of those roots of f which lie outside the unit circle, lies between 1 and 1 + ε.

"This problem, in interest in itself, is especially important for our purposes. Whether or not the problem has a solution for ε < 0.176 we do not know." -- Derrick Henry Lehmer, 1933.

Mahler's measure of a polynomial f is defined to be the absolute value of the product of those roots of f which lie outside the unit disk, multiplied by the absolute value of the coefficient of the leading term of f. We denote it M(f).

Lehmer's problem, sometimes called Lehmer's question, or Lehmer's conjecture, asks if there exists a constant C > 1 such that every polynomial f with integer coefficients and M(f) > 1 has M(f) C.

Lehmer added the following remark in his 1933 paper (using Ω to denote the measure):

"We have not made an examination of all 10th degree symmetric polynomials, but a rather intensive search has failed to reveal a better polynomial than

x¹⁰ + x⁹ - x⁷ - x⁶ - x⁵ - x⁴ - x³ + x + 1, Ω = 1.176280818.
"All efforts to find a better equation of degree 12 and 14 have been unsuccessful."

Despite extensive searches, Lehmer's polynomial remains the world champion.

This page summarizes what is known today about Lehmer's problem. It includes descriptions of algorithms, histories of searches performed, and various lists of polynomials with small measure.

1. Computational Aspects of Problems on Mahler's Measure, a talk for a short graduate course at the PIMS Workshop on Mahler's Measure of Polynomials, Simon Fraser University, June 2003. (PDF).

2. Computations with Mahler's Measure, or Mahler's Symphony in C++, a talk for graduate students at the MSRI workshop, Excursions in Computational Number Theory, June 2002. (PDF, PostScript).

3. Mahler's Measure of a Polynomial, an introductory talk for graduate students at UCLA, February 1999.
   • Most of the slides are available in PDF or compressed PostScript.
   • Another slide in PDF or PostScript.
   • One last slide is a gif.

Polynomial Searches

A new web interface for searching the known polynomials with degree at most 180 and measure at most 1.3. One may search by degree, measure, height, and number of roots outside the unit circle, and one may request the output as coefficient vectors, or TeX/LaTeX form, or a format suitable for input into a computer algebra system. (Web programming by Gavin Taylor.)

Flat Lists

The old plain text lists of all known polynomials with degree at most 180 and small measure, and the list of known small Salem numbers.

Some Search History

Brief descriptions of algorithms used to search for polynomials with small Mahler's measure, and histories of searches performed.

Records

The top 100 smallest measures known, plus record measures by degree, height, and number of roots outside the unit circle.

Summary

A table showing the number of known polynomials having degree D and k roots outside the unit circle with Mahler's measure less than 1.3.

Limit Points

Small limit points of measures of polynomials.

Special Classes

Information regarding Mahler's measure of various special classes of polynomials.

References

Some references on Lehmer's problem and related problems concerning Mahler's measure.

Please write if you have comments or contributions!