Lehmer's Problem
“The following problem arises immediately.
If ε is a positive quantity, to find a polynomial of the form
f(x) = xr +
a1 xr-1 +
… + ar
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
x10 + x9 − x7
− x6 − x5
− x4 − x3 + 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.
Talks on Lehmer's Problem and Mahler's Measure
- 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).
- 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).
- Mahler's Measure of a Polynomial, an introductory talk for
graduate students at UCLA, February 1999.
-
Polynomial Searches
-
A 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.)
-
Text Lists
-
Plain text lists: all known polynomials with degree at most 180 and
measure below 1.3, known small Salem numbers, and additional
lists of all Salem numbers of certain degrees below a particular bound.
-
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!
Michael Mossinghoff
Department of Mathematics
Davidson College
Davidson, North Carolina 28035-6996
mimossinghoff "at" davidson "dot" edu
Last modified June 30, 2011.