Lehmer's question, an open question about the Mahler measure of monic integral polynomials, is shown to be equivalent to a question about the complexity growth rate of signed 1-periodic graphs. If G is a d-periodic graph (i.e. G has a co-finite free Z^d-action by automorphisms), then a d-variable polynomial Δ_G can be defined with Mahler measure equal to the logarithmic growth rate γ_G of a complexity defined for the finite quotients of G.

A plane 1-periodic graph determines a link via projection and the medial graph construction. The polynomial Δ_G can be determined from the Alexander polynomial of the link. The complexity growth rate γ_G of any d-periodic graph is at least log 2. An investigation of plane 1- and 2-periodic graphs yields more connections with knot theory including work of A. Champanerkar and I. Kofman.

Both authors are grateful for the support of the Simons Foundation