\section{Introduction.} \label{Intro} 
The complexity of a finite graph is often defined as the number of its spanning trees.  Here we consider graphs with integer edge weights and take a different approach, defining  complexity to be the order of the torsion subgroup of the abelian group presented by the Laplacian matrix of the graph. When $G$ is connected and all edge weights are $1$, the complexity as we define it is the number of spanning trees of the graph. However, for general  edge-weighted graphs, the two notions of complexity are different. 

Our main objects of study are \emph{$d$-periodic graphs}, infinite graphs $G$ on which $\mathbb Z^d, \ d \ge 1$, acts freely by graph automorphisms such that integer edge weights are preserved and the quotient graph $\overline G$ is finite. Our motivation comes from two sources:  knot theory, where finite graphs with edge weights $\pm 1$ correspond to diagrams of knots and links, and Lehmer's question concerning the roots of integral polynomials. 

For $d$-periodic graphs a Laplacian operator is defined (see \cite{Ke11}), described by a matrix with variables $x_1^{\pm 1}, \ldots, x_d^{\pm 1}$ and denoted here by $L_G$. We call its determinant the \emph{Laplacian (determinant) polynomial} $D_G = D_G(x_1, \ldots, x_d)$. (For finite graphs the term Laplacian polynomial is often used for the characteristic polynomial of the integer Laplacian matrix.) When $D_G \ne 0$, we use the main result of \cite{LSW90} to characterize the Mahler measure of $D_G$ as the complexity growth rate of the finite quotient graphs lying between $G$ and $\overline G$. When all edge weights of $G$ are $1$, we recover a consequence of a more general result of Lyons \cite{Ly05} (see also \cite{BL12}). We show that Lehmer's question is equivalent to a question about graph complexity growth rates of 1-periodic graphs with edge weights equal to $\pm 1$.  

A 1-periodic \emph{plane graph} $G$ (that is, a graph embedded in the plane) determines an infinite link by the medial construction.  Its quotient by the $\mathbb Z$-action can be regarded as a (finite) link in an unknotted thickened annulus. The Alexander polynomial of the complement determines the Laplacian polynomial of $G$. We follow with some speculations about Lehmer's question and links.  

In the last section we present useful results about unweighted $d$-periodic graphs. They will not surprise some experts. However, as far as we know they do not appear in previous literature. 

  \bigskip




\ni {\bf Acknowledgements.} It is the authors' pleasure to thank Abhijit Champanerkar, Eriko Hironaka, Matilde Lalin and Chris Smythe for helpful comments and suggestions. 

\section{Complexity of finite graphs.} 



Consider a finite graph $G$ with vertex set $V(G)=\{v_1, \ldots, v_n\}$ and edge set $E(G)=\{e_1, \ldots, e_m\}$. The graph  is allowed to have multiple edges. Loops will not affect affect results here and can be ignored. We assume also that the edges $e \in E(G)$ have \emph{weights} $w_e \in \mathbb Z$. (Generally $w_e$ will be $1$ or $-1$.) The graph $G$ is \emph{unweighted} if every weight is $1$.




The \emph{adjacency matrix} of $G$ is the $n \times n$ matrix 
$A = (a_{i, j})$ such that $a_{i, j}$ is the sum of the weights of edges between $v_i$ and $v_j$, for $i \ne j$. Diagonal entries of $A$ are zero. Define ${\delta}= ({\delta}_{i, j})$ to be the $n \times n$ diagonal matrix with ${\delta}_{i,i}= \sum_j a_{i,j}.$



\begin{definition} \label{complexity} The \emph{Laplacian matrix} $L_G$ of a finite graph $G$ is ${\delta} - A$. The abelian group presented by $L_G$ is the \emph{Laplacian group} of $G$, denoted by ${\cal L}_G$. The \emph{(torsion) complexity} ${\kappa}_G$ is the order of the torsion subgroup $T{\cal L}_G$
\end{definition}

When $G$ is connected and unweighted, the nullity of the Laplacian matrix $L_G$ is equal to 1 (see \cite{GR01}), and hence the Laplacian group ${\cal L}_G$ decomposes as the direct sum of $\mathbb Z$ and the torsion subgroup $T{\cal L}_G$. In this case, the Matrix Tree Theorem \cite{Tu84} implies that ${\kappa}_G$ is equal to the number of spanning trees of $G$.

More generally we  define \emph{tree complexity}  $\tau_G$ of a connected graph $G$ by
\begin{equation*} \tau_G =\bigg \vert \sum_{T} \prod_{e \in E(T)} w_e\bigg \vert, \end{equation*}
where the summation is taken over all spanning trees of $G$. If $G$ not connected, then we define $\tau_G$ to be the product of the tree complexities of its connected components. Again by \cite{Tu84}, we have $\tau_G = {\kappa}_G$ if and only if $\tau_G$ is nonzero; for connected $G$ this common value is equal to any $(n-1) \times (n-1)$ principal minor of $L_G$. However,  the following example shows that $\tau_G$ can vanish while ${\kappa}_G$ is positive. 


\begin{figure}
\begin{center}
\includegraphics[height=2 in]{milnor}
\caption{Graph $G$ with $\tau_G=0$ and ${\kappa}_G = 9$}
\label{milnor}
\end{center}
\end{figure}

\begin{example}  Consider the connected graph $G$ in Figure \ref{milnor}. Unlabeled edges here and throughout will be assumed to have weight $1$. The Laplacian matrix $L_G$ is square of size $8$. (See Example \ref{circ} below for a quick way to find $L_G$.) A routine calculation shows that any principal $7 \times 7$ minor of $L_G$ vanishes, and hence $\tau_G=0$.   However, the absolute value of the greatest common divisors of the $6 \times 6$ minors of $L_G$ is 9. Hence ${\kappa}_G =9$. 
\end{example} 






\section{$d$-Periodic graphs.} We regard $\mathbb Z^d$ as the multiplicative abelian group freely generated by $x_1, \ldots, x_d$. We denote the Laurent polynomial ring $\mathbb Z[\mathbb Z^d] = \mathbb Z[x_1^{\pm 1}, \ldots, x_d^{\pm 1}]$ by ${\cal R}_d$. As an abelian group ${\cal R}_d$ is generated freely by monomials $x^{\bf s} = x_1^{s_1} \ldots x_d^{s_d}$, where ${\bf s} = (s_1, \cdots, s_d) \in \mathbb Z^d$. 

Let $G$ be a graph that is  \emph{$d$-periodic}. By this we mean that $G$ has a cofinite free $\mathbb Z^d$-action by automorphisms that preserves edge weights. (By \emph{cofinite} we mean the quotient  graph $\overline G$ is finite. The action is \emph{free} if the stabilizer of any edge or vertex is trivial.) Such a graph $G$ is necessarily locally finite. The vertex set $V(\overline G)$ and the edge set $E( \overline G)$ consist of finitely many vertex orbits $\{v_{1, {\bf s}}\mid {\bf s} \in \mathbb Z^d\}, \ldots, \{v_{n,{\bf s}}\mid {\bf s} \in \mathbb Z^d\}$ and weighted-edge orbits $\{e_{1, {\bf s}}\mid {\bf s} \in \mathbb Z^d\}, \ldots, \{e_{m, {\bf s}}\mid {\bf s} \in \mathbb Z^d\}$, respectively. The $\mathbb Z^d$-action is determined by 
\begin{equation} x^{{\bf s}'} \cdot v_{i, {\bf s}} = v_{i, {\bf s}+ {\bf s}'}, \quad \quad   x^{{\bf s}'} \cdot e_{j, {\bf s}} = e_{j, {\bf s}+ {\bf s}'},\end{equation}
where $1\le i \le n,\ 1 \le j \le m$ and ${\bf s}, {\bf s}' \in \mathbb Z^d$. (When $G$ is embedded in some Euclidean space with $\mathbb Z^d$ acting by translation, it is usually called a \emph{lattice graph}. Such graphs arise frequently in physics, for example in studying crystal structures.)

When $d>1$ we can think of $G$ as covering a graph $\overline G$ in the $d$-torus ${\mathbb T}^d = \mathbb R^d/\mathbb Z^d$.  When $d=1$, $G$ covers a graph $\overline G$ in the annulus ${\mathbb S}^1 \times I$. In either case the cardinality  $|V(\overline G)|$ is equal to the number $n$ of vertex orbits of $G$, while $|E(\overline G)|$ is the number $m$ of edge orbits. The projection map is given by $v_{i, {\bf s}} \mapsto v_i$ and $e_{j, {\bf s}} \mapsto e_j$.


If $\Lambda \subset \mathbb Z^d$ is a subgroup, then the intermediate covering graph in $\Bbb R^d/\Lambda$ will be denoted by $G_\Lambda$.  The subgroups $\Lambda$ that we will consider have index $r < \infty$, and hence $G_\Lambda$ will be a finite $r$-sheeted cover of $\overline G$ in the $d$-dimensional torus  $\Bbb R^d/\Lambda$.


Given a $d$-periodic graph $G$, the Laplacian matrix is defined to be the $n \times n$-matrix $L_G = {\delta} - A$, where now $A = (a_{i,j})$ is the \emph{weighted adjacency matrix} with each non-diagonal entry $a_{i, j}$  equal to the sum of  monomials $c_e x^{\bf s}$ for each edge $e \in E( \overline G)$ between $v_{i, \bf{0}}$ and $v_{j, {\bf s}}$. (Again, ignoring loops, each diagonal entry of $A$ is zero.) The matrix ${\delta}=({\delta}_{i,j})$ is the same diagonal matrix that we associate to $\overline G$. 

The matrix $L_G$ presents a finitely generated ${\cal R}_d$-module, the \emph{Laplacian module} of $G$.
The \emph{Laplacian (determinant) polynomial} $D_G$ is the determinant of $L_G$. Examples can be found in \cite{LSW14}.

The following is a consequence of the main theorem of \cite{Fo93}. It is made explicit in Theorem 5.2 of \cite{Ke11}. 

\begin{prop}\label{poly} \cite{Ke11} Let $G$ a $d$-periodic graph. Its Laplacian polynomial has the form \begin{equation}\label{polys} D_G = \sum_F\  \prod_{e \in E(F)} c_e \prod_{\rm Cycles\ of\ F} (2-w -w^{-1}),\end{equation} where  the sum is over all cycle-rooted spanning forests $F$ of $\overline G$, and $w, w^{-1}$ are the monodromies of the two orientations of the cycle. \end{prop} 

A \emph{cycle-rooted spanning forest} (CRSF) of $\overline G$  is a subgraph of $G$  containing all of $V$ such that each connected component has exactly as many vertices as edges and therefore has a unique cycle. The element $w$ is the monodromy of the cycle, or equivalently, its homology in $H_1({\mathbb T}^d; \mathbb Z) \cong \mathbb Z^d$.
See \cite{Ke11} for details. 

A $d$-periodic graph need not be connected. In fact, it can have countably many connected components. Nevertheless, the number of  $\mathbb Z^d$-orbits of components, henceforth called \emph{component orbits}, is necessarily finite. 

\begin{prop} \label{components}  If $G$ is a $d$-periodic graph with component orbits $G_1, \ldots, G_t$, then \break $D_G = D_{G_1}\cdots D_{G_t}$. \end{prop}

\begin{proof} After suitable relabeling, the Laplacian matrix for $G$ is a  block diagonal matrix with diagonal blocks equal to the 
Laplacian matrices for $G_1, \ldots, G_s$. The result follows immediately. 
\end{proof}

\begin{prop} \label{zeropoly} Let $G$ a $d$-periodic graph. Its Laplacian polynomial $D_G$ is identically zero if $G$ contains a closed component. The converse statement is true when $G$ is unweighted.
\end{prop} 

\begin{proof} If $G$ contains a closed component, then some component orbit $G_i$ consists of closed components.  We have $D_{G_i}=0$ by \ref{poly}, since all cycles of $\overline{G_i}$ have monodromy 0. By Proposition \ref{components}, $D_G$ is identically zero. 

Conversely, assume $G$ is unweighted and no component is closed. Each component of $\overline G$ must contain a nontrivial cycle. We can extend this collection of cycles to a cycle rooted spanning forest $F$ with no additional cycles.  The corresponding summand  in \ref{poly} has positive constant coefficient. Since every summand has nonnegative constant coefficient,  $D_G$ is not identically zero. 


\end{proof} 





\begin{definition} \label{mahler} The \emph{Mahler measure} of a nonzero polynomial 
$f(x_1, \ldots, x_d) \in {\cal R}_d$ is 
\begin{equation*} M(f) =\exp \int_0^1 \ldots \int_0^1 \log|f(e^{2\pi i \theta_1}, \ldots, e^{2\pi i \theta_d})| d\theta_1 \cdots d\theta_d. \end{equation*}

\end{definition} 

\begin{remark} (1)  The integral in Definition \ref{mahler} can be singular, but nevertheless it converges. 
(See \cite{EW99} for two different proofs.)  If $u_1, \ldots, u_d$ is another basis for $\mathbb Z^d$, then $f(u_1, \ldots, u_d)$ has the same logarithmic Mahler measure as $f(x_1, \ldots, x_d)$.  \smallskip

(2) When $d=1$, Jensen's formula shows that $M(f)$ can be described in a simple way. If $f(x) = c_s x^s+ \cdots c_1 x + c_0$, $c_0c_s \ne 0$, then
\begin{equation*} M(f) = |c_s| \prod_{i=1}^s \max\{\log |\lambda_i|, 1\},\end{equation*}
where $\lambda_1, \ldots, \lambda_s$ are the roots of $f$. \smallskip

(3) If $f, g \in {\cal R}_d$, then $M(fg) = M(f)M(g)$. Moreover, $M(f) =1$ if and only if $f$ is a unit or a unit times a product of 1-variable cyclotomic polynomials, each evaluated at a monomial of ${\cal R}_d$
(see \cite{Sc95}). 




\end{remark}




\begin{theorem}(cf. \cite{Ly05}) \label{limit} If $G$ is a $d$-periodic graph with nonzero Laplacian polynomial $D_G$,  then  
\begin{equation}  \limsup_{\langle \Lambda \rangle \to \infty} \frac{1}{|\mathbb Z^d/\Lambda|} \log {\kappa}_{G_\Lambda}=
\log M(D_G), \end{equation}
where $\Lambda$ ranges over all finite-index subgroups of $\mathbb Z^d$, and $\langle \Lambda \rangle$  denotes the minimum length of a nonzero vector in $\Lambda$. When $d=1$,  the limit superior can be replaced by an ordinary limit. 
\end{theorem}



\begin{remark} \label{remarks} (1) The condition $\langle \Lambda \rangle \to \infty$ ensures that fundamental region of $\Lambda$ grows in all directions. 

(2) If $G$ is unweighted,  ${\kappa}_{G_\Lambda}= \tau_{G_\Lambda}$ for every $\Lambda$. In this case, Theorem \ref{limit} is proven in \cite{Ly05} with the limit superior replaced by ordinary limit. 

(3) When $d=1$, the finite-index subgroups $\Lambda$ are simply $\mathbb Z/r\mathbb Z$, for $r >0$. In this case, we write $G_r$ instead of $G_\Lambda$. 


(4) When $d>1$,  a recent result of V. Dimitrov \cite{Di16} asserts that the limit superior in Theorem \ref{limit} is equal to the ordinary limit along sequences of sublattices $\Lambda$ of the form $N\cdot \mathbb Z^d$, where $N$ is a positive integer. 

 \end{remark} 
 
 
 \begin{figure}
\begin{center}
\includegraphics[height=3 in]{circ}
\caption{1-Periodic graph $G$ with $\tau_{G_r}=0$ for all $r \ge 1$}
\label{circulantdiagram}
\end{center}
\end{figure}


Before proving Theorem \ref{limit} we give an example that demonstrates the need for defining graph complexity as we do. 

\begin{example} \label{circ} Consider the 1-periodic graph $G$ in Figure \ref{circulantdiagram}. As before, unlabeled edges are assumed to have weight $1$. Generators for the Laplacian module are indicated. The Laplacian matrix is 
$$L_G= \begin{pmatrix} 0 &  1-x^{-1} & 1 & -x^{-1} \\ 1-x & 0 & 1 & -1 \\
1 & 1 & -2 & 0 \\ -x & -1 & 0 & 2 \end{pmatrix},$$ and 
$D_G(x) = 9 (x-2+x^{-1}).$  



The quotient  $G_2$ is the finite graph in Example \ref{milnor}. The  Laplacian matrix of any $G_r$ is easily described as a block matrix where $x$ is replaced by the companion (permutation) matrix for $x^r -1$. It is conjugate to a the diagonal block matrix ${\rm Diag}[L_G(1), \ldots, L_G(\zeta^{r-1})]$, where $\zeta$ is a primitive $r$th root of unity. The matrix $L_G(1)$ is the $4 \times 4$ Laplacian matrix of $\bar G$, 
$$ L_{\bar G}= \begin{pmatrix} 0 &  0 & 1 & -1\\ 0 & 0 & 1 & -1 \\
1 & 1 & -2 & 0 \\ -1 & -1 & 0 & 2 \end{pmatrix},$$ which has nullity 2. 
Hence the tree complexity $\tau_{G_r}$ vanishes for every $r$. Nevertheless, by Theorem \ref{limit} the (torsion) complexity ${\kappa}_{G_r}$ is nontrivial and has exponential growth rate equal to $9$. One can verify directly that the Laplacian subgroup ${\cal L}_{G_r}$ is 
isomorphic to $\mathbb Z^2 \times (\mathbb Z/ 3^{r-1}\mathbb Z)^2.$\end{example} 

We proceed with the proof of Theorem \ref{limit}. 
 
 \begin{proof} The proof that we present is a direct application of a  theorem of D. Lind, K. Schmidt and T. Ward (see \cite{LSW90} or  Theorem 21.1 of \cite{Sc95}). We review the ideas for the reader's convenience. 
 
Recall that the Laplacian module ${\cal L}_G$ is the finitely generated module over the ring ${\cal R}_d$ with presentation matrix equal to the $n \times n$ Laplacian matrix $L_G$. We let  ${\mathbb T}$ be the additive circle group $\mathbb R/\mathbb Z$, and we consider the Pontryagin dual group $\widehat {\cal L}_G= {\rm Hom}({\cal L}_G, {\mathbb T})$. We regard ${\cal L}_G$ as a discrete topological space. Endowed with the compact-open topology,
 $\widehat{\cal L}_G$ is a compact $0$-dimensional space. Moreover, the module actions of $x_1, \ldots, x_d$ determine commuting homeomorphisms $\sigma_1, \ldots, \sigma_d$ of $\widehat {\cal L}_G$. Explicitly, $(\sigma_j \rho)(a) = \rho(x_j a)$ for every $a \in {\cal L}_G$. Consequently, $\widehat {{\cal G}}_G$ has a $\mathbb Z^d$-action $\sigma: \mathbb Z^d \to \text{Aut}(\widehat {\cal L}_G)$. 
 
 
 
 

The pair $(\widehat {\cal L}_G, \sigma)$ is an algebraic dynamical system, well defined up to topological conjugacy (that is, up to a homeomorphism of $\widehat {\cal L}_G$ respecting the $\mathbb Z^d$ action). In particular its periodic point structure is well defined.  

Topological entropy $h(\sigma)$ is a well-defined quantity associated to $(\widehat {\cal L}_G, \sigma)$, a measure of complexity of the $\mathbb Z^d$-action $\sigma$. We refer the reader to \cite{LSW90} or \cite{Sc95} for the definition.



For any subgroup $\Lambda$ of $\mathbb Z^d$, a $\Lambda$-periodic point is a member of $\widehat {\cal L}_G$ that is fixed by every element of $\Lambda$. The set of $\Lambda$-periodic points is a finitely generated abelian group isomorphic to the Pontryagin dual group ${\rm Hom}({\cal L}_G/\Lambda {\cal L}_G), {\mathbb T})$. 


The group ${\cal L}_G/\Lambda {\cal L}_G$ is the Laplacian module of the quotient graph $G_\Lambda$. As a finitely generated abelian group, it decomposes 
as $\mathbb Z^{\beta_\Lambda} \oplus T({\cal L}_G/\Lambda {\cal L}_G)$, where $\beta_\Lambda$ is the 
rank of ${\cal L}_G/\Lambda {\cal L}_G$ and $T( \cdots )$ denotes the (finite) torsion subgroup. The Pontryagin dual group consists of $P_\Lambda = |T({\cal L}_G/\Lambda {\cal L}_G)|$ tori each of dimension $\beta_\Lambda$. By Theorem 21.1 of \cite{Sc95}, the topological entropy $h(\sigma)$ is:  \begin{equation*} h(\sigma) = \limsup_{\langle \Lambda \rangle \to \infty}  \frac{1}{|\mathbb Z^d/\Lambda|} \log P_\Lambda =\limsup_{\langle \Lambda \rangle \to \infty}  \frac{1}{|\mathbb Z^d/\Lambda|} \log {\kappa}_\Lambda.  \end{equation*}
Since the matrix $L_G$ that presents ${\cal L}_G$ is square, $h(\sigma)$ can be computed also as the logarithm of the Mahler measure $M(\det L_G)$ (see Example 18.7(1) of \cite{Sc95}).  The determinant of $L_G$ is, by definition, the Laplacian polynomial $D_G$. Hence the proof is complete. 
\end{proof}


\section{Lehmer's question} In \cite{Le33} D.H. Lehmer 
asked the following yet unresolved question. 

\begin{question} \label{LQ} Do there exist  integral polynomials with Mahler measures arbitrarily close but not equal to 1? 

\end{question} 

Lehmer discovered the polynomial $x^{10} + x^9 - x^7 - x^6 - x^5 - x^4 - x^3 +x +1,$ which has Mahler measure equal to $1.17628...$, but he could do no better. Lehmer's question remains unanswered despite great effort including extensive computer-aided searches \cite{Bo80, Bo81, MS12, Mo98, Ra94}.

Topological and geometric perspectives of Lehmer's question have been found \cite{Hi03}.  In \cite{SW07} we showed that Lehmer's question is equivalent to a question about Alexander polynomials of fibered hyperbolic knots in the lens spaces $L(n, 1), n>0$. (Lens spaces arose from the need to consider polynomials $f(x)$ with $f(1) =n \ne 1$.) 
Here we present another, more elementary equivalence, in terms of graph complexity. 


We will say that a Laurent polynomial $f(x) \in {\cal R}_1$ is \emph{palindromic} if 
$f(x^{-1}) = f(x)$. 
By a theorem of C. Smyth \cite{Sm71} it suffices to restrict our attention to palindromic polynomials when attempting to answer Lehmer's question.  

\begin{prop} \label{realized} A polynomial $D(x)$ is the Laplacian polynomial of a 1-periodic graph if and only if it has the form $(x-2+x^{-1})^2 f(x)$, where $f(x)$ is a palindromic polynomial. 
\end{prop}

\begin{proof} The Laplacian polynomial $D(x)$ of any $1$-periodic graph is palindromic. This is easy to see from the symmetry of the matrix $L_G$. Since the row-sums of $L_G$ become zero when $x=1$, it follows also that $x-1$ divides $D(x)$. (Both observations  follow also from Proposition \ref{poly}.) 
Palindromicity requires that the multiplicity of $x-1$ be even. Hence $D(x)$ has the form $(x-2+x^{-1})^2 f(x)$, where $f(x)$ is palindromic. 

In order to see the converse assertion, consider any polynomial of the form $p(x)=(x-2-x^{-1})^2f(x)$, where $f(x)$ is palindromic. A straightforward induction on the degree of $f(x)$ shows that we can pair each term $\pm x^s$ with $\pm x^{-s}$, and then write $p(x)$
as a sum of terms $\pm(x^s-2+x^{-s})$. Then $p(x)$ is the Laplacian polynomial of a 1-periodic graph, constructed as in the following example. 
\end{proof} 

\begin{example} \label{circulant} Multiplying Lehmer's polynomial $f(x)= x^{10} + x^9 - x^7 - x^6 - x^5 - x^4 - x^3 +x +1$ by the unit $x^{-5}$ and then by $x-2+x^{-1}$ yields
$x^6-x^5-x^4+x^2+x^{-2}-x^{-4}-x^{-5}+x^{-6},$
which in turn can be written as 
$$(x^2-2+x^{-2}) -(x^4-2+x^{-4})-(x^5-2+x^{-5})+ (x^6 -2 + x^{-6}).$$
This the Laplacian polynomial of a 1-periodic graph $G$. The quotient graph $\overline G$ is easily described. It has a single vertex, two edges with weight $+1$ and two with $-1$. The $(+1)$-weighted edges wind twice and six times, respectively,  around the annulus in the direction corresponding to $x$. The $(-1)$-weighted edges wind four and five times, respectively, in the opposite direction.
\end{example} 



\begin{theorem} \label{LQ} Lehmer's question is equivalent to the following. 
Given $\epsilon >0$, does there exist a 1-periodic graph $G$ such that 
$$1 < \lim_{r \to \infty}  (\tau_{G_r})^{1/r} < 1+\epsilon?$$ 
\end{theorem}

\begin{proof} When investigating Lehmer's question it suffices to consider polynomials of the form $(x-2+x^{-1})f(x)$, where $f(x)$ is  palindromic and irreducible. By Proposition \ref{realized} any such polynomial is realized as the Laplacian polynomial of a 1-periodic graph $G$ with a single vertex orbit. As in Example \ref{circ} the Laplacian matrix $L_{G_r}$ of any finite quotient $G_r$ can be obtained from $(x-2+x^{-1})f(x)$ by substituting for $x$ the companion matrix for $x^r-1$. Hence the nullity of $L_{G_r}$ is 1 provided that $f(x)$ is not a cyclotomic polynomial (multiplied by a unit), a condition that we can assume without loss of generality. 
Hence $\kappa_{G_r} = \tau_{G_r}$ for each $r$ (see discussion following Definition \ref{complexity}.) Theorem \ref{limit} completes the proof. 

\end{proof}

\begin{remark}

(1) The conclusion of Theorem \ref{LQ} does not hold if we restrict ourselves to unweighted graphs. By Theorem \ref{absolute} below,  the Mahler measure of the Laplacian polynomial of any 1-periodic graph with all edge weights equal to 1 is at least 2. \bigskip

(2) If a 1-periodic graph $G$ as in Example \ref{circulant} can be found with $M(D_G)$ less than Lehmer's value $1.17628...$, then by results of  \cite{Mo08} some edge of $\overline G$ must wind around the annulus at least 29 times. \end{remark}

The cyclic 5-fold cover of the graph in Example \ref{circulant} contains the complete graph on 5 vertices, and hence it is nonplanar.  Hence we ask: 

\begin{question} \label{question1} Is Theorem \ref{LQ} still true if we require that the graphs $G$ be planar?  
\end{question}


\section{Laplacian polynomials of plane 1-periodic graphs} A finite plane graph determines a diagram of a \emph{medial link} by a simple procedure in which each edge of the graph is replaced by two arcs as in Figure \ref{convention1}. 
If the graph is unweighted then the resulting diagram is alternating as in Example  \ref{gridlinks} below. (The reader is invited to sketch the medial link associated to Figure \ref{milnor}. It is a non-alternating boundary link. According to \cite{Co70} it was introduced by J. Milnor and is the first link known to have zero Alexander polynomial.) 

It is well known that the Laplacian matrix of a finite plane graph $G$ is an unreduced Goeritz matrix of the associated link \cite{Go33}. The reduced matrix, obtained by deleting a row and column, presents the first homology group of the 2-fold cyclic cover of ${\mathbb S}^3$ branched over the link. (See \cite{Re74, Tr85, Li97} for additional details.)
 
When $G$ is a 1- or 2-periodic graph we apply the same construction to produce a diagram $\cal D$ of an infinite link $\ell$. It has a finite quotient diagram $\overline \cal D$ modulo the induced $\mathbb Z$- or $\mathbb Z^2$-action on $G$. 

For $d=1$ we regard $\overline \cal D$ in an annulus where it describes a link $\overline \ell = \overline \ell_1 \cup \cdots  \cup \overline \ell_\mu$ in a solid unknotted torus $V$. The complement $({\rm int} V) \setminus \overline \ell$ is homeomorphic to the ${\mathbb S}^3 \setminus \hat \ell$, where  $\hat \ell$ is the link $\overline \ell \cup C$ formed by the union of $\overline \ell$ with a meridian $C$ of $V$. The meridian acquires an orientation induced by the infinite cyclic action on $\cal D$.  The following result relates the Laplacian polynomial $D_G$ to the Alexander polynomial $\Delta_{\hat \ell}$.

\begin{figure}
\begin{center}
\includegraphics[height=1  in]{convention}
\caption{Medial link construction for $(\pm 1)$-edge weighted graphs}
\label{convention1}
\end{center}
\end{figure}

\begin {theorem} \label{alex} Let $G$ be a plane 1-periodic graph and $\hat \ell$ the encircled link $\overline \ell \cup C$. Then 
$$D_G(x) \  {\buildrel \cdot \over =}\   (x-1)\ \Delta_{\hat \ell}(-1, \ldots, -1, x),$$
where ${\buildrel \cdot \over =}$  indicates equality up to multiplication by units in $\mathbb Z[x^{\pm 1}]$. 

\end{theorem} 

\begin{proof} We abbreviate $\Delta_{\hat \ell}(-1, \ldots, -1, x)$ by $F(x)$ and compute it via Fox calculus. Such a calculation can be done using the link group 
$\pi_1(\mathbb R^3 \setminus \hat \ell)$ and augmentation homomorphism $\phi: \mathbb Z[ \pi_1(\mathbb R^3 \setminus \hat \ell) ] \to \mathbb Z[x^{\pm 1}]$ that maps a meridian of $C$ to $x$ and meridians of $\overline \ell$ to $-1$. Instead we will make use of $\pi_1(\mathbb R^3 \setminus \ell)$, an infinite-index subgroup of $\pi_1(\mathbb R^3\setminus \hat \ell)$. It has a countable Dehn presentation associated to the diagram $\cal D$. The presentation has generators $a_\nu, b_\nu, \ldots, \nu \in \mathbb Z$ corresponding to bounded regions together with a generator $u$ corresponding to one of the two unbounded regions of $\cal D$. (The second unbounded region, called the \emph{base region}, is labeled zero.) Here $a_\nu, b_\nu, \ldots$ is short-hand for the families $\{ x^\nu a x^{-\nu}\}, \{ x^\nu b x^{-\nu}\}, \ldots$, indexed by $\nu \in \mathbb Z$. The generators $a, b, \ldots$ are arbitrary but fixed orbit representatives. We regard $u$ as $\{u_\nu \mid u_\nu = u_{\nu +1}\}$. 

We recall that Dehn generators are related to the more-familiar Wirtinger generators once an orientation of the link $\ell$ is given. A Dehn generator corresponds to a loop that begins at a base-point above the plane, pierces the plane in the region of the Dehn generator, and returns through the base region. While the Dehn presentation requires no orientation of $\ell$, the restriction of the augmentation homomorphism $\phi$ to $\mathbb Z[\pi_1(\mathbb R^3 \setminus \ell)]$ is determined only with coefficients modulo 2. For this, we checkerboard color the diagram $\cal D$ with black and white in such a way that black regions contain the vertices of $G$. Under the augmentation homomorphism \emph{white generators} $a_\nu = x^\nu a x^{-\nu}$, those corresponding to white regions, map to $x^\nu$. \emph{Black generators},  those belonging to black regions, map to $-x^\nu$. 

Relations of the Dehn presentation correspond to crossings of $\cal D$, as in Figure \ref{convention}. The relation arising from the crossing at the top of the diagram is 
$a b^{-1} =c d^{-1}$ while the crossing at the bottom we may write as   $bd^{-1}= ac^{-1}$.  Like the generators, the relations come in countable families. Applying Fox calculus to relations, we obtain $a_\nu + b_\nu = c_\nu + d_\nu$ (top) and $b_\nu + d_\nu= a_\nu + c_\nu $ (bottom). We denote the collection of  Dehn relations by ${\cal R}$. 

\begin{figure}
\begin{center}
\includegraphics[height=2.5  in]{dehn}
\caption{Dehn relations}
\label{convention}
\end{center}
\end{figure}

Fix a black region of $\cal D$ (vertex of $G$) and identify it with the generator $a$ in Figure \ref{convention}. When we can add the relations involving $a$, the white generators cancel in pairs and we are left with the Laplacian relation of $G$ at the vertex. Note that this collection ${\cal R'}$ of Laplacian relations is a consequence of ${\cal R}$. 

Consider the dual graph $G^*$ and choose a spanning tree $T^*$ rooted at the base region of $\cal D$. Each edge of $T^*$ crosses a unique edge of $G$, and hence $T^*$ corresponds to a subset  ${\cal R}_0$ of ${\cal R}$.  Using these relations we can express each white generator in terms of black generators. Lemma \ref{lem} below will show that the remaining relations in ${\cal R}$ are consequences of ${\cal R}_0 \cup {\cal R'}$. Once we use the relations ${\cal R}_0$ to eliminate white generators and rewrite the remaining relations, we see the presentation of ${\cal L}_G$ given by the Laplacian matrix $L_G$. Since the polynomial $F(x)$ 
is the $0$th determinantal invariant of the module divided by $x-1$, the proof is complete. 





\end{proof} 
 
\begin{lemma} \label{lem} Let $G$ be a plane 1-periodic graph, and let ${\cal R, R'}$  be the Dehn and Laplacian relations of the link diagram resulting as above from the medial construction. Let ${\cal R}_0$ be the Dehn relations corresponding to the edges of a spanning tree for the dual graph $G^*$ rooted at the base region of $\cal D$. Then any Dehn relation in ${\cal R} \setminus {\cal R}_0$  is a consequence of ${\cal R}_0 \cup {\cal R'}$.\end{lemma} 

\begin{proof} Any Dehn relation in ${\cal R} \setminus {\cal R}_0$ corresponds to an edge of $G^*$ not contained in $T^*$. Adding the edge to $T^*$ results in a unique cycle ${\gamma}$. We proceed by induction on the number of vertices of $G$ enclosed by ${\gamma}$. 

If ${\gamma}$ encloses a single vertex, then, as in the proof of Theorem \ref{alex}, the relations corresponding to the edges of ${\gamma}$ add together to give the Laplacian relation at the vertex. 


If ${\gamma}$ encloses more than one vertex, then it can be decomposed as 
a union of cycles ${\gamma}_1$ and ${\gamma}_2$ with edges of $G$ in common such that each cycle encloses fewer vertices than ${\gamma}$. The sum of the Dehn relations corresponding to the edges of ${\gamma}$ is equal to the addition of the sums coming from ${\gamma}_1$ and ${\gamma}_2$, the relations  corresponding to common edges canceling in pairs. By the induction hypothesis the later is a consequence of ${\cal R}_0 \cup {\cal R'}$.

\end{proof}



Question \ref{question1} might be approached by reversing the process of transforming a plane 1-periodic graph $G$ to an encircled link $\hat \ell$. Given any link $\hat \ell$ with an unknotted component $C$,  the Mahler measure of $\Delta_{\hat \ell}(x, -1, \ldots, -1)$ is the Mahler measure of some 1-periodic plane graph. (Neither the extra factor of $x-1$ nor the orientation of $C$ will affect the Mahler measure.)  However, the classification of Alexander polynomials of links with an unknotted component is a difficult problem that has been only partly solved \cite{Ki79, Co82, Tr82}

\section{Unweighted $d$-periodic graphs} We present some results about unweighted $d$-periodic graphs. They will not surprise some experts, but, as far as we know, they have not appeared elsewhere. In particular, we will show that our restatement of Lehmer's question in Theorem \ref{LQ} is not valid if we restrict ourselves to unweighted graphs. \bigskip

{\sl Graphs considered in this section are unweighted. }\bigskip


We call the limit in Theorem \ref{limit} the {\it complexity growth rate} of $G$, and denote it by ${\gamma}_G$.  Its relationship to the {\it thermodynamic limit} or {\it bulk limit} defined for a wide class of unweighted lattice graphs is discussed in  \cite{LSW14}. 

Denote by $R= R(\Lambda)$ a fundamental domain of $\Lambda$. Let $G\vert_R$ be the full unweighted subgraph of $G$ on vertices $v_{i, {\bf s}},\ {\bf s} \in R$. We denote by $\ell_R$ the corresponding medial link. 

 If  $G\vert_R$ is connected for each $R$, then $\{\tau_{G_\Lambda}\}$ and $\{\tau_{G\vert_R}\}$ have the same exponential growth rates. (See Theorem 7.10 of \cite{LSW14} for a short, elementary proof. A more general result is Corollary 3.8 of \cite{Ly05}.) The bulk limit is defined by ${\gamma}_G/|V(\overline G)|$. 

\begin{example} The \emph{$d$-dimensional grid graph} $\Bbb G_d$ is the unweighted graph with  vertex set $\mathbb Z^d$ and edges 
from $(s_1, \ldots, s_d)$ to $(s_1', \ldots, s_d')$ if $|s_i -s_i'|=1$ and $s_j = s_j',\ j \ne i$, for every $1 \le i \le d$.  Its Laplacian polynomial is 
\begin{equation*} D(\Bbb G_d) = 2d -x_1-x_1^{-1}- \cdots - x_d-x_d^{-1}. \end{equation*}
When $d=2$, it is a plane graph. The graphs links $\ell_R$ are indicated in Figure \ref{gridlinks} for $\Lambda = \langle x_1^2, x_2^2 \rangle$ on left and $\Lambda= \langle x_1^3, x_2^3 \rangle$ on right.

\begin{figure}
\begin{center}
\includegraphics[height=2 in]{gridlinks2}
\caption{Graphs $(\Bbb G_2)_R$ and associated links, $\Lambda = \langle x_1^2, x_2^2 \rangle$ and $\langle x_1^3, x_2^3 \rangle$}
\label{gridlinks}
\end{center}
\end{figure}

\end{example} 


The {\it determinant} of a link $\ell$, denoted here by ${\rm det}(\ell)$, is the absolute value of its 1-variable Alexander polynomial evaluated at $-1$.   
It follows from the Mayberry-Mott theorem \cite{BM54} that if $\ell$ is an alternating link that arises by the medial construction from a finite plane graph, edge weights $\pm 1$ allowed, then ${\rm det}(\ell)$ is equal to the tree complexity of the graph (see Appendix A.4 in \cite{BZ85}).
The following corollary is an immediate consequence of Theorem \ref{limit}.  It has been proven independently by Champanerkar and Kofman \cite{CK16}. 


\begin{cor}\label{detgrowth} Let $G$ be a connected $d$-periodic unweighted plane graph, $d =1$ or $2$. Then $$\lim_{\langle \Lambda \rangle \to \infty}  \frac{1}{\vert \mathbb Z^d/\Lambda\vert} \log {\rm det}(\ell_R) = 
{\gamma}_{D_G}.$$ \end{cor}

\begin{remark} (1) In \cite{CKP15} the authors consider as well more general sequences of links.  When $G = \Bbb G_2$, their results imply that:

$$\lim_{\langle \Lambda \rangle \to \infty} \frac{2 \pi}{c(\ell_R)} \log {\rm det}(\ell_R)=  v_{oct},$$
where $c(\ell_R)$ is the number of crossings of $\ell_R$ and $v_{oct} \approx 3.66386$ is the volume of the regular ideal octohedron.\bigskip

(2) If Question \ref{question1} has an affirmative answer then Lehmer's question becomes a question about link determinants. 

\end{remark} 



Grid graphs are the simplest unweighted $d$-periodic graphs,  as the 
following theorem shows. 

\begin{theorem} \label{min} Assume that $G$ is an unweighted connected $d$-periodic graph.  Then ${\gamma}_G\ge {\gamma}_{\Bbb G_d}$.
\end{theorem} 

\begin{remark} The conclusion of Theorem \ref{min} does not hold without the hypothesis that $G$ is connected. Consider the 2-periodic graph $G$ consisting of 
countably many copies of $\Bbb G_1$ obtained from $\Bbb G_2$ by removing all vertical edges. Then ${\gamma}_G =0$ while ${\gamma}_{\Bbb G_2} > 0$. \end{remark}


The following lemma, needed for the proof of Corollary \ref{absolute}, is of independent interest. 

\begin{lemma} \label{nonincreasing} The sequence of complexity growth rates ${\gamma}_{D_{\Bbb G_d}}$ is nondecreasing. 
\end{lemma} 

Doubling each edge of $\Bbb G_1$ results in a graph with Laplacian polynomial $2(x-2+x^{-1})$, which has Mahler measure $2 M (x-2+x^{-1}) = 2$. The following corollary states that this is minimum nonzero complexity growth rate. 

\begin{cor} \label{absolute} (Complexity Growth Rate Gap) Let $G$ be any unweighted $d$-periodic graph with Laplacian polynomial $D_G$. If ${\gamma}_G \ne 0$, then 
$${\gamma}_G \ge \log 2.$$
\end{cor}



Although $D_{\Bbb G_d}$ is relatively simple, the task of computing its Mahler measure is not. It is well known and not difficult to see that ${\gamma}_{\Bbb G_d} \le \log 2d$. We will use a theorem of N. Alon \cite{Al90} to show that ${\gamma}_{\Bbb G_d}$ approaches $\log 2d$ asymptotically. 

\begin{theorem} \label{gridlim} (1) ${\gamma}_{\Bbb G_d} \le \log 2d$, for all $d \ge 1$.\\ 
(2) $\lim_{d \to \infty} {\gamma}_{\Bbb G_d}- \log 2d = 0.$ \end{theorem}

Asymptotic results about the Mahler measure of certain families of polynomials have been obtained elsewhere. However, the graph theoretic methods that we employ to prove Theorem \ref{min} are different from techniques used previously. \bigskip


Now suppose $H$ is a subgraph of $G$ consisting of one or more connected components of $G$, such that the orbit of $H$ under $\mathbb Z^d$ is all of $G$.  Let 
$\Gamma < \mathbb Z^d$ be the stabilizer of $H$.  Then $\Gamma\cong \mathbb Z^{d'}$ for some $d'\le d$, and its action on $H$ can be regarded as a cofinite free action of $\mathbb Z^{d'}$.   Consider the limit $${\gamma}_H=\lim_{\<\Lambda\>\to\infty} \frac{1}{|\Gamma/\Lambda|} \log {\kappa}_{H_\Lambda}$$
where $\Lambda$ ranges over finite-index subgroups of $\Gamma$.

\begin{lemma}\label{new} Under the above conditions we have ${\gamma}_G={\gamma}_H$.
\end{lemma}

\begin{proof}
Let $\Lambda$ be any finite-index subgroup of $\mathbb Z^d$.  Then $H$ is invariant under $\Lambda\cap{\cal G}$. The image of $H$ in the quotient graph $G_\Lambda$ is isomorphic to  $H_{\Lambda\cap{\cal G}}$.  

Note that the quotient $\overline H$ of $H$ by the action of ${\cal G}$ is isomorphic to $\overline G$, since the $\mathbb Z^d$ orbit of $H$ is all of $G$.  Since $G_\Lambda$ is a $|\mathbb Z^d /\Lambda|$-fold cover of $\overline G$ and $H_{\Lambda\cap{\cal G}}$ is a $|{\cal G}/(\Lambda\cap{\cal G})|$-fold cover of $\overline H$, $G_\Lambda$ comprises $k=|\mathbb Z^d /\Lambda| / |{\cal G}/(\Lambda\cap{\cal G})|$ mutually disjoint translates of a graph that is isomorphic to $H_{\Lambda\cap{\cal G}}$. Hence ${\kappa}_{G_\Lambda}={\kappa}_{H_{\Lambda\cap{\cal G}}}^k$ and
$$\frac{1}{|\mathbb Z^d /\Lambda|} \log {\kappa}_{G_\Lambda}= \frac{1} {|{\cal G}/(\Lambda\cap{\cal G})|} \log {\kappa}_{H_{\Lambda\cap{\cal G}}}.$$
Since $\<\Lambda\cap{\cal G}\>\to\infty$ as $\<\Lambda\>\to\infty$, we have ${\gamma}_G={\gamma}_H$.
\end{proof}



\noindent {\it Proof of Theorem \ref{min}.}  
Consider the case in which $G$ has a single vertex orbit. Then for some $u_1,\ldots, u_m\in \mathbb Z^d$, with $m \ge d$, the edge set $E(G)$ consists of edges from $v$  to $u_i \cdot v$ for each $v\in V$ and $i=1,\ldots,m$.  Since $G$ is connected, we can assume after relabeling that $u_1, \ldots, u_d$ generate a finite-index subgroup of $\mathbb Z^d$. Let $G'$ be the be the $\mathbb Z^d$-invariant subgraph of $G$ with edges from $v$  to $u_i \cdot v$ for each $v\in V$ and $i=1,\ldots,d$.  Then $G'$ is the orbit of a subgraph of $G$ that is isomorphic to $\Bbb G_d$, and so by Lemma \ref{new}, ${\gamma}(\Bbb G_d)={\gamma}(G')\le{\gamma}(G)$.

We now consider a connected graph $G$ having vertex families $v_{1, {\bf s}}, \ldots, v_{n, {\bf s}}$, where $n >1$. Since $G$ is connected, there exists an edge $e$ joining $v_{1, {\bf 0}}$ to some $v_{2, {\bf s}}$. Contract the edge orbit $\mathbb Z^d \cdot e$ to obtain a new graph $G'$ having cofinite free $\mathbb Z^d$-symmetry and complexity growth rate no greater than that of $G$.
Repeat the procedure with the remaining vertex families so that only $v_{1, {\bf s}}$ remains. The proof in the previous case of a graph with a single vertex orbit now applies. {$\vrule height4pt depth0pt width4pt$} \\


\noindent {\it Proof of Lemma \ref{nonincreasing}.}  Consider the grid graph $\Bbb G_d$. Deleting all edges 
in parallel to the $d$th coordinate axis yields a subgraph $G$ consisting of countably many mutually disjoint translates of $\Bbb G_{d-1}$. By Lemma \ref{new},   ${\gamma}_{\Bbb G_{d-1}}={\gamma}_G  \le {\gamma}_{\Bbb G_d}$. 
{$\vrule height4pt depth0pt width4pt$} \\

\noindent {\it Proof of Corollary \ref{absolute}.}  By Lemma \ref{new} it suffices to consider a connected $d$-periodic graph $G$ with ${\gamma}_G$ nonzero. Note that ${\gamma}_{\Bbb G_1} =0$ while ${\gamma}_{\Bbb G_2} \approx 1.165$ is greater than $\log 2$.  By Theorem \ref{min} and Lemma \ref{nonincreasing} we can  assume that $d=1$. 

If $G$ has an orbit of parallel edges, we see easily that ${\gamma}_G \ge \log 2$.  Otherwise, we proceed as in the proof of  Theorem \ref{min}, contracting edge orbits to reduce the number of vertex orbits  without increasing the complexity growth rate.  If at any step we obtain an orbit of parallel edges, we are done; otherwise we will obtain a graph $G'$ with a single vertex orbit and no loops. 
If $G'$ is isomorphic to $\Bbb G_1$ then $G$ must be a tree; but then ${\gamma}_G=0$, contrary to our hypothesis. So $G'$ must have at least two edge orbits.  
Deleting excess edges, we may suppose $G'$ has exactly two edge orbits. 

The Laplacian polynomial $D_{G'}$ has the form $4-x^r-x^{-r}- x^s-x^{-s}$, for some positive integers $r, s$. Reordering the vertex set of $G'$, we can assume without loss of generality that $r=1$. The following calculation is based on an idea suggested to us by Matilde Lalin. 


$$\log M(D_{G'}) = \int_0^1 \log \vert 4- 2 \cos( 2 \pi \theta)-2 \cos(2 \pi s \theta) \vert \ d\theta$$

$$=\int_0^1 \log \vert  2(1-\cos  (2 \pi \theta)) + 2(1 - \cos(2 \pi s \theta)) \vert \ d\theta$$

$$=\int_0^1 \log  \bigg( 4\sin^2(\pi \theta) + 4\sin^2(\pi s \theta) \bigg) \ d\theta.$$

\ni Using the inequality $(u^2+v^2) \ge 2 u v$, for any nonnegative $u, v$, we have:

$$\log M(D_{G'}) \ge \int_0^1 \log \bigg( 8 \vert \sin( \pi \theta)\vert\  \vert \sin( \pi s \theta) \vert \bigg)\ d\theta$$

$$= \log 8 + \int_0^1 \log \vert \sin(  \pi \theta) \vert \ d\theta + \int_0^1 \log \vert \sin( \pi s \theta) \vert \ d\theta$$

$$= \log 8 + \int_0^1 \log \sqrt{\frac{1-\cos(2 \pi \theta)}{2}}\ d \theta + \int_0^1 \log \sqrt{\frac{1-\cos(2  \pi s\theta)}{2}}\ d \theta$$

$$=\log 8 + \int_0^1 \frac{1}{2} \log \bigg(\frac{2 - 2 \cos(2 \pi \theta)}{4}\bigg)\ d \theta +   \int_0^1 \frac{1}{2} \log \bigg(\frac{2 - 2 \cos(2 \pi s \theta)}{4}\bigg)\ d \theta$$


$$= \log 8 + \frac{1}{2}m(2 - x -x^{-1}) -\frac{1}{2} \log 4 + \frac{1}{2}m(2 - x^s - x^{-s})- \frac{1}{2} \log 4$$

$$= 3\log 2 + 0 - \log 2 +0 -\log 2 = \log 2.$$
{$\vrule height4pt depth0pt width4pt$}\\

Our proof of Theorem \ref{gridlim} depends on the following result of Alon. 

\begin{theorem}\label{lowerbound}\cite{Al90}   If $G$ is a finite connected $\rho$-regular unweighted graph, then 
$$\tau_G \ge [\rho(1-\epsilon(\rho))]^{|V(G)|},$$ 
where $\epsilon(\rho)$ is a nonnegative function with $\epsilon(\rho)\to\infty$ as $\rho\to\infty$.
\end{theorem}



\noindent{\it Proof of Theorem \ref{gridlim}.} (1) The integral representing the logarithm of the Mahler measure of $D_{\Bbb G_d}$ can be written
$$\int_0^1 \cdots \int_0^1 \log \bigg\vert2d - \sum_{i=1}^d 2 \cos(2 \pi \theta_i)\bigg\vert d\theta_1\cdots d\theta_d$$
$$= \log 2d + \int_0^1 \cdots \int_0^1 \log \bigg\vert1+\sum_{i=1}^d \frac{ \cos( 2 \pi \theta_i)}{d}\bigg\vert d\theta_1\cdots d\theta_d$$
$$= \log 2d + \int_0^1 \cdots \int_0^1 -\sum_{k=1}^\infty \frac{(-1)^k}{k}\bigg( \frac{\sum_{i=1}^d \cos(2 \pi \theta_i)}{d} \bigg)^k d\theta_1\cdots d\theta_d.$$
By symmetry, odd powers of $k$ in the summation contribute zero to the integration. Hence 
$$\log(D_{\Bbb G_d})= \log 2d - \int_0^1 \cdots \int_0^1 \sum_{k=1}^\infty \frac{1}{2k}\bigg( \frac{\sum_{i=1}^d \cos(2 \pi \theta_i)}{d} \bigg)^{2k} d\theta_1\cdots d\theta_d \le \log 2d.$$






(2) Let $\Lambda$ be a finite-index subgroup of $\mathbb Z^d$. Consider the quotient graph $(\Bbb G_d)_\Lambda$. The cardinality of its vertex set is $|\mathbb Z^d/\Lambda|$. The main result of \cite{Al90}, cited above as Theorem \ref{lowerbound}, implies that 
$$\tau_{(\Bbb G_d)_\Lambda} = \bigg((2 d) (1 - \mu(d))\bigg)^{|\mathbb Z^d/\Lambda|},$$
where $\mu$ is a nonnegative function such that $\lim_{d\to \infty} \mu(d) =0$.  
Hence 
$$\lim_{d \to \infty}  \bigg (\frac{1}{|\mathbb Z^d/\Lambda|} \log \tau_{(\Bbb G_d)_\Lambda} - \log 2 d\bigg ) = \lim_{d\to \infty} \log (1-\mu(d)) =0.$$
Theorem \ref{limit} completes the proof.  
{$\vrule height4pt depth0pt width4pt$} \\

\begin{remark} One can evaluate $\log M(D(\Bbb G_d))$ numerically and obtain an infinite series representing
${\gamma}_{\Bbb G_d} - \log 2d$. However, showing rigorously that the sum of the series approaches zero as $d$ goes 
to infinity appears to be difficult. (See \cite{SW00}, p. 16 for a heuristic argument.) 
\end{remark} 

 
