\section{Introduction}
Constraint satisfaction problems (CSPs) are widely used in AI, with applications in optimization, control, and planning \cite{russell2003artificial}.
While many classes of CSPs are intractable in the worst case~\cite{cook1971complexity}, many real-world CSP instances are easy to solve in practice~\cite{vardi2014boolean}.
As a result, there has been significant interest in understanding the average-case complexity of CSPs from multiple communities, such as AI, theoretical computer science, physics, and combinatorics~\cite{biere2009handbook}.

Random CSPs are an important model for studying the average-case complexity of CSPs. Past works have proposed several distributional models for random CSPs \cite{molloy2003models,creignou2003generalized}. An interesting feature arising from many models is a phase transition phenomenon that occurs as one changes the ratio of number of constraints, $m$, to the number of variables, $n$. Empirical results \cite{mitchell1992hard} show that for many classes of CSPs, randomly generated instances are satisfiable with probability near 1 when $m/n$ is below a certain threshold. For $m/n$ larger than a threshold, the probability of satisfiability is close to 0. The statistical physics, computer science, and mathematics communities have focused much attention on identifying these threshold locations \cite{achlioptas2005rigorous,biere2009handbook}.

Phase transitions for common classes of CSPs such as $k$-SAT and $k$-XORSAT are very well-studied. For $k$-SAT, researchers struggled to find tight lower bounds on the satisfiability threshold until the breakthrough work of \citeauthor{achlioptas2002asymptotic}, which provided lower bounds a constant factor away from the upper bounds. Later works closed this gap for $k$-SAT \cite{coja2013going,coja2016asymptotic}.  More recently, \citeauthor{Dudek2016CombiningTK} \shortcite{Dudek2016CombiningTK} also studied the satisfiability threshold for a more general CSP class, namely $k$-CNF-XOR, where both $k$-SAT and $k$-XORSAT constraints can be used. The results and analyses from these works, however, are all specific to the constraint classes studied.

In this paper, we provide new lower bounds on the location of the satisfiability threshold that hold for general boolean CSP classes. We focus on the setting where CSPs are generated by a single constraint type, though our analysis can extend to the setting with uniform mixtures of different constraint functions. We extend techniques from \cite{achlioptas2004threshold} and build on \cite{creignou2003generalized}, which proposes a distributional model for generating CSPs and provides lower bounds on the satisfiability threshold for these models. The significance of our work is that \textit{our bounds hold for all functions that could be used to generate random CSP instances}. The lower bounds from \cite{creignou2003generalized} are also broadly applicable, but they are looser than ours because they do not depend on constraint-specific properties. Our lower bounds are often tight (within a constant factor of upper bounds for many CSP classes) because they depend on specific properties of the Fourier spectrum of the function used to generate the random CSPs. Since these properties are simple to compute for any constraint function, our lower bounds are broadly applicable too.

The Fourier analysis of boolean functions \cite{o2014analysis} will be vital for obtaining our main results. Expressing functions in the Fourier basis allows for clean analyses of random constraints \cite{friedgut1999sharp,barak2015beating,achim2016beyond}. Our use of Fourier analysis is inspired by the work of \citeauthor{achim2016beyond} \shortcite{achim2016beyond}, who analyze the Fourier spectra of random hash functions used as constraints in CSP-based model counting. We show that the Fourier spectrum of our constraint-generating function controls the level of spatial correlation in the set of satisfying assignments to the random CSP. If the Fourier spectrum is concentrated on first and second order coefficients (corresponding to ``low frequencies''), this correlation will be very high, roughly increasing the variance of the number of solutions to a random CSP and decreasing the probability of satisfiability. In related work, \citeauthor{montanari2011reconstruction} \shortcite{montanari2011reconstruction} also use Fourier analysis to provide tight thresholds in the case where odd Fourier coefficients are all zero.

\section{Notation and Preliminaries}
\label{sec:notation}
In this section, we will introduce the preliminaries necessary for presenting our main theorem. First, we formally define our distribution for generating random CSPs, inspired from \cite{creignou2003generalized}.

We will use $n$ and $m$ to denote the number of variables and number of constraints in our CSPs, respectively. We will also let $f : \{-1, 1\}^k \rightarrow \{0, 1\}$ denote a binary function and refer to $f$ as our constraint function. Often we use the term ``solution set of $f$'' to refer to the set $\{u : f(u) = 1\}$. Using the constraint function $f$, we create constraints by applying $f$ to a signed subset of $k$ variables.

\begin{definition} [Constraint]
Let $I = (i_1, \ldots, i_k)$ be an ordered tuple of $k$ indices in $[n]$, and let $s$ be a sign vector from $\{-1, 1\}^k$. Given a vector $\sigma \in \{-1, 1\}^n$, we will define the vector $\sigma_{I, s}$ of size $k$ as follows:
\begin{equation}
\label{eq:sigmaIs}
\sigma_{I, s} = (s_1\sigma_{i_1}, \ldots, s_k\sigma_{i_k})
\end{equation}
Now we can denote the application of $f$ to these indices by $f_{I, s}(\sigma) = f(\sigma_{I, s})$. We call $f_{I, s}$ a constraint, and we say that $\sigma \in \{-1, 1\}^n$ satisfies the constraint $f_{I, s}$ if $f_{I, s}(\sigma) = 1$.
\end{definition}
The definition of a CSP generated from $f$ follows.
\begin{definition} [CSP generated from $f$]
We will represent a CSP with $m$ constraints and $n$ variables generated from $f$ as a collection of constraints $C_f(n, m) = \{f_{I_1, s_1}, \ldots, f_{I_m, s_m}\}$. Then $\sigma \in \{-1, 1\}^n$ satisfies $C_f(n, m)$ if $\sigma$ satisfies $f_{I_j, s_j}$ for $j = 1, \ldots, m$.
\end{definition}
\begin{example} [3-SAT]
Let $f : \{-1, 1\}^3 \rightarrow \{1, 0\}$ where $f(u) = 0$ for $u = (-1, -1, -1)$ and $f(u) = 1$ for all other $u$. Then $f$ is the constraint function for the 3-SAT problem.
\end{example}
With these basic definitions in place, we are ready to introduce the model for random CSPs.
\subsection{Random CSPs}
\label{sec:randcsp}
We discuss our model for randomly generating  $C_f(n, m)$, and formally define a ``satisfiability threshold.''

To generate instances of $C_f(n, m)$, we simply choose $I_1, \ldots, I_m$ and $s_1, \ldots, s_m$ uniformly at random. For completeness, we sample without replacement, i.e. there are no repeated variables in a constraint, and no duplicate constraints. However, sampling with replacement does not affect final results. For the rest of this paper we abuse notation and let $C_f(n, m)$ denote a randomly generated CSP instance following this model.

Now we formally discuss satisfiability thresholds. We let $r = m/n$. For many constraint functions $f$, there exist thresholds $r_{f,\text{sat}}$ and $r_{f,\text{unsat}}$ such that
\begin{align*}
\lim_{n \rightarrow \infty} \Pr[C_f(n, rn) \ \text{is satisfiable}] =
\begin{cases}
1 \ \text{if} &\ r < r_{f,\text{sat}}\\
0 \ \text{if} &\ r > r_{f,\text{unsat}}
\end{cases}
\end{align*}
In general, it is unknown whether $r_{f,\text{sat}} = r_{f,\text{unsat}}$, but for some problems such as $k$-SAT (for large $k$) and $k$-XORSAT, affirmative results exist \cite{ding2015proof,pittel2016satisfiability}. If $r_{f,\text{sat}} = r_{f,\text{unsat}}$, then we say that the random CSP $C_f(n, m)$ exhibits a sharp threshold in $m/n$.

We are concerned with finding lower bounds $r_{f,\text{low}}$ on $r_{f,\text{unsat}}$ such that there exists a constant $C > 0$ independent of $n$ so that for sufficiently large $n$,
\begin{equation}
\label{eq:rflower}
\Pr[C_f(n, rn) \ \text{is satisfiable}] > C \ \text{for all} \ r < r_{f,\text{low}}
\end{equation}
For CSP classes with a sharp threshold, \eqref{eq:rflower} implies that
\begin{align*}
\lim_{n \rightarrow \infty} \Pr[C_f(n, rn) \ \text{is satisfiable}] = 1 \ \text{for all} \ r < r_{f,\text{low}}
\end{align*}
We also wish to find upper bounds $r_{f,\text{up}}$ such that
\begin{align*}
\lim_{n \rightarrow \infty} \Pr[C_f(n, rn) \ \text{is satisfiable}] = 0 \ \text{for all} \ r > r_{f,\text{up}}
\end{align*}
For an example of these quantities instantiated on a concrete example, refer to the experiments in Section \ref{sec:experiments}.

We provide a value for $r_{f,\text{up}}$ which was derived earlier in \cite{creignou2003generalized}. \citeauthor{dubois2001upper} \shortcite{dubois2001upper} and \citeauthor{creignou2007expected} \shortcite{creignou2007expected} provide methods for obtaining tighter upper bounds, but the looser values that we use are sufficient for showing that $r_{f,\text{low}}$ is on the same asymptotic order as $r_{f,\text{unsat}}$ for many choices of $f$.

The bound $r_{f,\text{low}}$ depends on both the symmetry and size of the solution set of $f$. The more assignments $u \in \{-1, 1\}^k$ such that $f(u) = 1$, the more likely it is that each constraint is satisfied. Increased symmetry reduces the variance in the number of solutions to $C_{f}(n, rn)$, so solutions are more spread out among possible CSPs in our class and the probability that $C_f(n, rn)$ will have a solution is higher. We will formally quantify this symmetry in terms of the Fourier spectrum of $f$, which we introduce next.

\subsection{Fourier Expansion of Boolean Functions}
We discuss basics of Fourier analysis of boolean functions. For a detailed review, refer to \cite{o2014analysis}. We define the vector space $\mathcal{F}_k$ of all functions mapping $\{-1, 1\}^k$ to $\mathbb{R}$. The set $\mathcal{F}_k$ has the inner product $\langle f_1, f_2 \rangle = \sum_{u \in \{-1, 1\}^k} f_1(u)f_2(u)/2^k$ for any $f_1, f_2 \in \mathcal{F}_k$.

This inner product space has orthonormal basis vectors $\chi_S$, where the parity functions $\chi_S$ follow $\chi_S(u) = \prod_{i \in S} u_i$ for all $S \subseteq [k]$, subsets of the $k$ indices. Because $(\chi_S)_{S \subseteq [k]}$ forms an orthonormal basis, if we write
\begin{equation}
\label{eq:hatfS}
\hat{f}(S) = \langle f, \chi_S \rangle = \frac{1}{2^k} \sum_{u \in \{-1, 1\}^k} f(u)\chi_S(u)
\end{equation}
then we can write $f$ as a linear combination of these vectors: $f = \sum_{S \subseteq [k]} \hat{f}(S) \chi_S$. We note that when $S = \emptyset$, the empty set, $\hat{f}(\emptyset)$ is simply the average of $f$ over $\{-1, 1\}^k$. We will refer to the coefficients $(\hat{f}(S))_{S \subseteq [k]}$ as the Fourier spectrum of $f$. Since these coefficients are well-studied in theoretical computer science \cite{o2014analysis}, the Fourier coefficients of many boolean functions are easily obtained.

\begin{example} [3-SAT]
\label{ex:3satfourier}
For $3$-SAT, $\hat{f}(\emptyset) = 7/8$. $\hat{f}(\{1\}) = \hat{f}(\{2\}) = \hat{f}(\{3\}) = 1/8$, and $\hat{f}(\{1, 2\}) = \hat{f}(\{2, 3\}) = \hat{f}(\{1, 3\}) = -1/8$.
\end{example}

Representing $f$ in the Fourier bases will facilitate our proofs, providing a simple way to express expectations over our random CSPs. The Fourier spectrum can also provide a measure of ``symmetry'' in $f$ - if some values of $\hat{f}(S)$ are high where $|S| = 1$, then satisfying assignments to $f$ are more skewed in the variable corresponding to $S$. We will show how this impacts satisfiability in Section \ref{sec:boundexplained}.

\begin{figure*}
\centering
\begin{tabular}{|c | c | c| c|}
\hline
\Tstrut
CSP class ($f$) & Best lower bound on $r_{f,\text{unsat}}$ & Our bound $r_{f,\text{low}}$ & Upper bound $r_{f,\text{up}}$\\ \hline
\Tstrut
$k$-XORSAT & 1 & $\frac{1}{2}$ & 1\\
\Tstrut
$k$-SAT & $2^k\ln 2 - \frac{1 + \ln 2}{2} - o_k(1)$ & $2^{k - 1} - O(k)$ & $2^k \ln 2$\\
\Tstrut
$k$-NAESAT & $2^{k - 1} \ln 2 - \frac{\ln 2}{2} - \frac{1}{4} - o_k(1)$ & $2^{k - 2} - \frac{1}{2}$ & $2^{k - 1}\ln 2$ \\
\Tstrut
$k$-MAJORITY & ? & $\frac{\frac{1}{2} - k\binom{k - 1} {\frac{k - 1}{2}}^2 2^{-2k +1}}{1 + k\binom{k - 1}{\frac{k - 1}{2}}^2 2^{-2k+ 2}} = 0.111 - o_a(1)$ & $1$  \\
\Tstrut
$a$-MAJ $\otimes 3$-MAJ & ? & $\frac{\frac{1}{2} - 3a\binom{a - 1}{\frac{a - 1}{2}}^2 2^{-2a - 1}}{1 + 3a\binom{a - 1}{\frac{a - 1}{2}}^2 2^{-2a - 2}} = 0.177 - o_a(1)$ & $1$\\
\Tstrut
$k$-MOD-3 & ? & $\frac{1}{4} - o_k(1)$ & $\frac{\ln 2}{\ln 3} + o_k(1)$\\
\Tstrut
OR$_b \otimes$ XOR$_a$ & ? & $2^{b - 1} - 1/2$ & $2^{b - 1} \ln 2$\\
\hline
\end{tabular}
\caption{We compare the best known lower bounds on the satisfiability threshold to our lower and upper bounds. For $k$-XORSAT \cite{pittel2016satisfiability}, $k$-SAT \cite{ding2015proof}, and $k$-NAESAT \cite{coja2012catching}, the numbers listed are known as exact sharp threshold locations. For the last four, we do not know of existing lower bounds. $\otimes$ is the composition operator for boolean functions, and we define these functions in Section \ref{sec:figfunc}.}
\label{fig:bounds}
\end{figure*}

\section{Main Results}
\label{sec:mainresult}
We provide simple formula for $r_{f,\text{up}}$. A similar result is in \cite{creignou2003generalized}, and the full proof is in the appendix.
\begin{proposition}
\label{prop:upper}
For all constraint functions $f$, let
\begin{align*}
r_{f,\text{up}} = \frac{\log 2}{\log 1/\hat{f}(\emptyset)} < \frac{\log 2}{1 - \hat{f}(\emptyset)}
\end{align*}
If $r \ge r_{f,\text{up}}$, $\lim_{n \rightarrow \infty} \Pr[C_f(n, rn) \ \text{is satisfiable}] = 0$.
\end{proposition}
\begin{proof} [Proof Sketch]
We compute the expected solution count for $C_f(n, rn)$. The expected solution count will scale with $\hat{f}(\emptyset)$, since  $2^k \hat{f}(\emptyset)$ is simply the number of $u \in \{-1, 1\}^k$ where $f(u) = 1$ and therefore governs how easily each constraint will be satisfied. If $r > r_{f,\text{up}}$, the expected solution count converges to 0 as $n \rightarrow \infty$, so Markov's inequality implies that the probability that a solution exists goes to 0.
\end{proof}

Next, we will present our value for $r_{f,\text{low}}$. First, some notation: let $U = \{u \in \{-1, 1\}^k : f(u) = 1\}$, and let $A$ be the $k \times |U|$ matrix whose columns are the elements of $u$. We will use $A^+$ to denote the Moore-Penrose pseudoinverse of $A$. For a reference on this, see \cite{barata2012moore}. Finally, let $\boldsymbol{1}$ be the $|U|$-dimensional vector of 1's.
\begin{example} [$3$-SAT] For $3$-SAT, $k = 3$ and $|U| = 7$, and we can write $A$ as follows (up to permutation of its columns):
\begin{align*}
A =
\left[
\begin{array} {r r r r r r r}
1 & 1 & 1 & 1 & -1 & -1 & -1\\
1 & 1 & -1 & -1 & 1 & 1 & -1\\
1 & -1 & 1 & -1 & 1 & -1 & 1
\end{array}
\right]
\end{align*}
where columns of $A$ satisfy the $3$-SAT constraint function.
\end{example}
The following main theorem provides the \textit{first computable equation for obtaining lower bounds that are specific to the constraint-generating function $f$.}

\begin{theorem}
\label{thm:main}
For all constraint functions $f$, let
\begin{align*}
r_{f,\text{low}} = \frac{1}{2} \frac{c}{1 - c} \text{ where } c = \hat{f}(\emptyset) - \frac{\boldsymbol{1}^T A^+ A \boldsymbol{1}}{2^k}
\end{align*}
If $r < r_{f,\text{low}}$, then there exists a constant $C>0$ such that $\lim_{n \rightarrow \infty} \Pr[C_f(n, rn) \ \text{is satisfiable}] > C$.
\end{theorem}

The lower bound $r_{f,\text{low}}$ is an increasing function of $c$ which is dependent on two quantities. First, with higher values of $\hat{f}(\emptyset)$, $C_f(n, rn)$ will have more satisfying assignments on average, so $c$ and the threshold value will be higher. Second, $c$ depends on the level of symmetry in the solution set of $f$, which we will show is connected to the Fourier spectrum of $f$. We explain this dependence in Section \ref{sec:boundexplained}.

In comparison, \citeauthor{creignou2003generalized} \shortcite{creignou2003generalized} obtain lower bounds which depend only on the arity of $f$. While we cannot make an exact comparison because \citeauthor{creignou2003generalized} use a different random CSP ensemble, for reference, they provide the general lower bound of $1/(ke^k - k)$ expected constraints per variable for functions of arity $k$. Our bounds are much tighter because of their specificity while remaining simple to compute. To demonstrate, we instantiate our bounds for some example constraint functions in Figure \ref{fig:bounds}. Whereas their bounds are exponentially decreasing in $k$, our bounds are constant or increasing in $k$ for the functions shown.

\subsection{Constraint Functions in Figure \ref{fig:bounds}}
\label{sec:figfunc}
We define the constraint functions in Figure \ref{fig:bounds}. Unless specified otherwise, they will be in the form $f : \{-1, 1\}^{k} \rightarrow \{0, 1\}$.
\begin{enumerate}
\item $k$-SAT: $f(u) = 0$ if $u$ is the all negative ones vector, and $f(u) = 1$ otherwise.
\item $k$-XORSAT: $f(u) = \mathbbm{1}(\chi_{[k]}(u) = -1)$
\item $k$-NAESAT: $f(u) = 0$ if $u$ is the all negative ones or all ones vector, and $f(u) = 1$ otherwise.
\item $k$-MAJORITY: Defined when $k$ is odd, $f(u) = 1$ if more than half of the variables of $u$ are $1$.
\item $a$-MAJ $\otimes$ $3$-MAJ: Defined when $a$ is odd, where $f : \{-1, 1\}^{3a} \rightarrow \{0, 1\}$. Defined as the composition of $a$-MAJORITY on $a$ groups of $3$-MAJORITY, as follows:
\begin{align*}
f(u_1, \ldots, u_{3a}) =\\ f_{a-\text{MAJ}}(f_{3-\text{MAJ}}(u_1, u_2, u_3), \ldots, \\ f_{3-\text{MAJ}}(u_{3a - 2}, u_{3a -1}, u_{3a}))
\end{align*}
\item $k$-MOD-3: $f(u) = 1$ when the number of 1's in $u$ is divisible by $3$, and 0 otherwise.
\item OR$_b \otimes$ XOR$_a$: In this case, $f : \{-1, 1\}^{ab} \rightarrow \{0, 1\}$, and $f$ is the composition of a OR over $b$ groups of XORs over $a$ variables, as follows:
\begin{align*}
f(u_{1}, \ldots, u_{ab}) =\\
f_{\text{OR}_b}(f_{\text{XOR}_a}(u_1, \ldots, u_a), \ldots,\\
f_{\text{XOR}_{a}}(u_{ab - a + 1}, \ldots, u_{ab}))
\end{align*}
\end{enumerate}

While the last four constraint functions have not been analyzed much in the existing CSP literature, these types of general constraints are of practical interest because of \cite{achim2016beyond}, which performs probabilistic inference by solving CSPs based on arbitrary hash functions. For example, \citeauthor{achim2016beyond} \shortcite{achim2016beyond} show that MAJORITY constraints are effective in practice for solving probabilistic inference problems.
\subsection{Connecting Bounds with Fourier Spectrum}
\label{sec:boundexplained}
We explain how the Fourier spectrum can help us interpret Theorem \ref{thm:main}. We first show the connection between $c$ and the Fourier spectrum.
Let $\hat{f}_{S : |S| = 1}$ be the $k$-dimensional vector whose entries are Fourier coefficients of $f$ for size 1 sets. Let $B$ be the $k \times k$ matrix with diagonal entries $B_{ii} = \hat{f}(\emptyset)$ and off-diagonal entries $B_{ij} = \hat{f}(\{i, j\})$ for $i \ne j$.
\begin{example} [3-SAT]
Following the coefficients in Example \ref{ex:3satfourier}, for $3$-SAT, $\hat{f}_{S : |S| = 1} = (1/8, 1/8, 1/8)$ and
\begin{align*}
B = \left[
\begin{array} {r r r}
7/8 & -1/8 & -1/8\\
-1/8 & 7/8 & -1/8\\
-1/8 & -1/8 & 7/8
\end{array}
\right]
\end{align*}
\end{example}
\begin{lemma}
\label{lem:fourierc}
When the rows of $A$ are linearly independent, $c = \hat{f}(\emptyset) - \hat{f}_{S : |S| = 1}^T B^{-1} \hat{f}_{S : |S| = 1}$.
\end{lemma}

From this lemma, we see that larger values of $c$ correspond to smaller $\hat{f}_{S : |S| = 1}$. These terms will measure the amount of ``symmetry'' in the solution set for $f$.
The matrix $B$ and vectors $\hat{f}_{S : |S| = 1}$ are easily obtained for many $f$ since Fourier coefficients are well-studied \cite{o2014analysis}.

Figure \ref{fig:bounds} shows how $\hat{f}(\emptyset) - c$ and $f$ relate. Since $k$-SAT has a mostly symmetric solution set, $\hat{f}_{k-\text{SAT}}(\emptyset) - c = O(k/2^{2k})$ since $c = 1 - 2^{-k} - O(k/2^{2k})$, which is small compared to $\hat{f}_{k-\text{SAT}}(\emptyset)$. The solution set of $k$-NAESAT is completely symmetric as if $f_{k-\text{NAESAT}}(x) = 1$, then $f_{k-\text{NAESAT}}(-x) = 1$. Thus, $f_{k-\text{NAESAT}}$ has 0 weight on Fourier coefficients for sets with odd size so we can compute that $\hat{f}_{k-\text{NAESAT}}(\emptyset) - c = 0$. $k$-MAJORITY, however, is less symmetric, as shown by larger first order coefficients. Here, the bound in Figure \ref{fig:bounds} gives
$\lim_{k \rightarrow \infty} \hat{f}_{k-\text{MAJORITY}}(\emptyset) - c = 1/\pi$, which is large compared to $\hat{f}_{k-\text{MAJORITY}}(\emptyset) \approx 1/2$.

\section{Proof Strategy}
Our proof relies on the second moment method, which has been applied with great success to achieve lower bounds for problems such as $k$-SAT \cite{achlioptas2004threshold} and $k$-XORSAT \cite{dubois20023}. The second moment method is based on the following lemma, which can be derived using the Cauchy-Schwarz inequality:
\begin{lemma}
\label{lem:secondmomentmethod}
Let $X$ be any real-valued random variable. Then
\begin {equation}
\label{eq:secondmom}
Pr[X \ne 0] = \Pr[|X| \ne 0] \ge \frac{\text{E}[|X|]^2}{\text{E}[X^2]} \ge \frac{\text{E}[X]^2}{\text{E}[X^2]}
\end {equation}
\end{lemma}
If $X$ is only nonzero when $C_f(n, rn)$ has a solution, we obtain lower bounds on the probability that a solution exists by upper bounding $\text{E}[X^2]$. For example, we could let $X$ be the number of solutions to $C_f(n, rn)$. However, as shown in \cite{achlioptas2004threshold}, this choice of $X$ fails in most cases. Whether two different assignments satisfy $C_f(n, rn)$ is correlated: if the assignments are close in Hamming distance and one assignment is satisfying, it is more likely that the other is satisfying as well. This will make $\text{E}[X^2]$ much larger than $\text{E}[X]^2$, so \eqref{eq:secondmom} will not provide useful information. Figure \ref{fig:failure} demonstrates this failure for $k$-SAT. \citeauthor{achlioptas2004threshold} \shortcite{achlioptas2004threshold} show formally that the ratio $\text{E}[X]^2/\text{E}[X^2]$ will decrease exponentially (albeit at a slow rate). On the other hand, $k$-NAESAT is ``symmetric'', so the second moment method works directly here. In the plot, $\text{E}[X]^2/\text{E}[X^2]$ for $3$-NAESAT stays above a constant. This also follows formally from our main theorem as well as \cite{achlioptas2002asymptotic}. We formally define our requirements on symmetry in \eqref{eq:derivhalf0}.

We circumvent this issue by weighting solutions to reduce correlations before applying the second moment method. As in \cite{achlioptas2004threshold}, we use a weighting which factors over constraints in $C_f(n, rn)$ and apply the second moment method to the random variable
\begin{equation}
\label{eq:X}
X = \sum_{\sigma \in \{-1, 1\}^n} \prod_{c \in C_f(n, rn)}w(\sigma, c)
\end{equation}
where $C_f(n, rn)$ is a collection of constraints $\{f_{I_1, s_1}, \ldots, f_{I_m, s_m}\}$ and the randomness in $X$ comes over the choices of $I_j, s_j$. Now we can restrict our attention to constraint weightings of the form $w(\sigma, f_{I, s}) = w(\sigma_{I, s})$. In the special case where $w(\sigma_{I, s}) = f(\sigma_{I, s})$, $X$ will simply represent the number of solutions to $C_f(n, rn)$. In general, we require $w(\sigma_{I, s}) = 0$ whenever $f(\sigma_{I, s}) = 0$. This way, if $X \ne 0$, then $C_f(n, rn)$ must have a solution.

For convenience, we assume that the index sets $I_1, \ldots, I_m$ are sampled with replacement. They are chosen uniformly from $[n]^k$. We also allow constraints to be identical. In the appendix, we justify why proofs in this setting carry over to the without-replacement setting in Section \ref{sec:randcsp} and also provide full proofs to the lemmas presented below.

\begin{figure*}
\centering
\subfloat[$\text{E}{[X]}^2/\text{E}{[X^2]}$ vs. $n$ for $3$-SAT and $3$-NAESAT. $X$ is the solution count, $r = 1$.]
{\includegraphics[width=0.32\textwidth]{naesat_sat_plot_n_max_600_k_3_r_1_num_n_30_n_min_1.png}
\label{fig:failure}
}
\subfloat[$g_w(\alpha)$ when $f$ is $k$-XORSAT and $w = f$.]{\includegraphics[width=0.32\textwidth]{g_w_xor_plot_k_max_12_k_min_4.png}
\label{fig:g_w}}
\subfloat[$\psi_r(\alpha)$ with $f$ as $5$-NAESAT and $w = f$.]{\includegraphics[width=0.32\textwidth]{psi_r_plot_num_r_3_k_5_r_max_13_0_r_min_1_0.png}
\label{fig:psi}}
\caption{For concreteness, we provide sample plots of the relevant quantities in our proofs.}
\end{figure*}

In this setting, we will compute the first and second moments of the $X$ chosen in \eqref{eq:X} in terms of the Fourier spectrum of $w$.
\begin{lemma}
\label{lem:firstmomentsq}
The squared first moment of $X$ is given by
\begin{equation}
\label{eq:E[X]sq}
\text{E}[X]^2 = 2^{2n}(\hat{w}(\emptyset)^2)^{rn}
\end{equation}
\end{lemma}
\begin{proof}
We can expand $\text{E}[X]$ as follows:
\begin{align}
\text{E}[X] &= \sum_{\sigma \in \{-1, 1\}^n} \text{E}\left[\prod_{j = 1}^{rn}w(\sigma_{I_j, s_j})\right] \notag \\
&= \sum_{\sigma \in \{-1, 1\}^n} \text{E}[w(\sigma_{I, s})]^{rn} \label{eq:EXint}
\end{align}
where we used the fact that constraints are chosen independently. Now we claim that for any $u \in \{-1, 1\}^k$,
\begin{align*}
\Pr[\sigma_{I, s} = u] = \frac{1}{2^k}
\end{align*}
This follows from the fact that we choose $s$ uniformly over $\{-1, 1\}^k$ and our definition of $\sigma_{I, s}$ in \eqref{eq:sigmaIs}. Thus,
\begin{align*}
\text{E}[w(\sigma_{I, s})] &= \sum_{u \in \{-1, 1\}^k} w(u)\Pr[\sigma_{I, s} = u]\\
&= \frac{1}{2^k}\sum_{u \in \{-1, 1\}^k} w(u)\\
&= \hat{w}(\emptyset)
\end{align*}
Plugging back into \eqref{eq:EXint} gives the desired result.
\end{proof}
Next, we will compute the second moment $\text{E}[X^2]$.
\begin{lemma}
\label{lem:secmoment}
Let $g_w(\alpha) = \sum_{S \subseteq [k]} (2\alpha - 1)^{|S|} \hat{w}(S)^2$. The second moment of $X$ is given by
\begin{equation}
\label{eq:E[Xsq]}
\text{E}[X^2] = 2^n \sum_{j = 0}^n {n \choose j} g_w(j/n)^{rn}
\end{equation}
\end{lemma}

The function $g_w(\alpha)$ is similar to the noise sensitivity of a boolean function \cite{o2003computational} and measures the correlation in the value of $w$ between two assignments $\sigma$, $\tau$ which overlap at $\alpha(\sigma, \tau) n$ locations. As a visual example, Figure \ref{fig:g_w} shows how $g_w(\alpha)$ changes for $k$-XORSAT with varying $k$. The key of our proof is showing that $\text{E}[w(\sigma_{I, s})w(\tau_{I, s})] = g_w(\alpha(\sigma, \tau))$ for a random constraint $f_{I, s}$.

We will now write $\text{E}[X]^2$ in terms of $g_w$. Since $g_w(1/2) = \hat{w}(\emptyset)^2$, plugging this into \eqref{eq:E[X]sq} gives us
\begin{equation}
\label{eq:e[X]sqing}
\text{E}[X]^2 = 2^{2n} g_w(1/2)^{rn}
\end{equation}
This motivates us to apply the following lemma from \cite{achlioptas2004threshold}, which will allow us to translate bounds on $g_w(\alpha)$ into bounds on $\text{E}[X]^2/\text{E}[X^2]$:
\begin{lemma}
\label{lem:achlioptaslem}
Let $\phi$ be any real, positive, twice-differentiable function on $[0, 1]$ and let
\begin{align*}
S_n = \sum_{j = 0}^{n} {n \choose j} \phi(j/n)^n
\end{align*}
Define $\psi$ on $[0, 1]$ as $\psi(\alpha) = \frac{\phi(\alpha)}{\alpha^{\alpha}(1 - \alpha)^{1 - \alpha}}$.
If there exists $\alpha_{\max} \in (0, 1)$ such that $\psi(\alpha_{\max}) > \psi(\alpha)$ for all $\alpha \ne \alpha_{\max}$, and $\psi''(\alpha_{\max}) < 0$, then there exist constants $B, C > 0$ such that for all sufficiently large $n$,
\begin{equation}
\label{eq:lemachlioptasres}
B \psi(\alpha_{\max})^n \le S_n \le C \psi(\alpha_{\max})^n
\end{equation}
\end{lemma}
To apply the lemma, we can define $\phi_r(\alpha) = g_w(\alpha)^r$ and $\psi_r(\alpha) = \frac{\phi_r(\alpha)}{\alpha^{\alpha}(1 - \alpha)^{1 - \alpha}}$. Then from \eqref{eq:e[X]sqing}, we note that
\begin{equation}
\psi_r(1/2)^n = 2^n(g_w(1/2)^r)^n = \text{E}[X]^2/2^n
\label{eq:psiE[X]sq}
\end{equation}
On the other hand, from \eqref{eq:E[Xsq]},
\begin{equation}
\sum_{j = 0}^n {n \choose j} \phi_r(j/n)^n = \text{E}[X^2]/2^n
\label{eq:psiE[Xsq]}
\end{equation}
so if the conditions of Lemma \ref{lem:achlioptaslem} hold for $\alpha_{\max} = 1/2$, we recover that $\text{E}[X]^2/\text{E}[X^2] \ge C$ for some constant $C > 0$.

One requirement for $\psi_r(\alpha)$ to be maximized at $\alpha = 1/2$ is that $\psi_r'(1/2) = 0$. Expanding $\psi_r'(1/2)$ gives $2g_w(1/2)^{r - 1}(rg_w'(1/2)) = 0$.
Since $g_w(1/2) = \hat{w}(\emptyset)^2 > 0$, we thus require
\begin{equation}
\label{eq:derivhalf0}
g_w'(1/2) = 2\sum_{S \subseteq [k] : |S| = 1} \hat{w}(S)^2 = 0
\end{equation}
In order to satisfy \eqref{eq:derivhalf0}, we need $\hat{w}(S) = 0$ for all $S \subseteq [k]$ where $|S| = 1$. To use Lemma \ref{lem:achlioptaslem}, we would like to choose $w$ such that \eqref{eq:derivhalf0} holds. We discuss how to choose $w$ to optimize our lower bounds in the appendix. In the next section, we will provide $r$ so that the conditions of Lemma \ref{lem:achlioptaslem} hold at $\alpha = 1/2$ for arbitrary $w$ when \eqref{eq:derivhalf0} is satisfied.

\subsection{Bounding the Second Moment For Fixed $w$}
We give a general bound on $r$ in terms of our weight function $w$ so that the conditions of Lemma \ref{lem:achlioptaslem} are satisfied for $\alpha = 1/2$. For now, the only constraint we place on $w$ is that \eqref{eq:derivhalf0} holds. The next lemma lets us consider only $\alpha \in [1/2, 1]$.
\begin{lemma}
\label{lem:alphagehalf}
Let $\alpha \ge 1/2$. Then $g_w(\alpha) \ge g_w(1 - \alpha)$.
\end{lemma}
This lemma follows because $g_w(\alpha)$ is a polynomial in $(2\alpha - 1)$ with nonnegative coefficients, and $(2\alpha - 1) > 0$ for $\alpha > 1/2$.

Now we can bound $\psi_r(\alpha)$ for $\alpha \in [1/2, 1]$. Combined with Lemma \ref{lem:alphagehalf}, the next lemma will give conditions on $r$ such that $\psi_r(1/2) > \psi_r(\alpha)$ for all $\alpha \in [0, 1]$.

\begin{lemma}
\label{lem:rbound}
Let the weight function $w$ satisfy \eqref{eq:derivhalf0}. If
\begin{equation}
\label{eq:rcond}
r \le \frac{1}{2}\frac{\hat{w}(\emptyset)^2}{\sum_{S : |S| \ge 2} \hat{w}(S)^2}
\end{equation}
$\psi_r(1/2) > \psi_r(\alpha)$ for $\alpha \in [0, 1]$ and $\psi_r''(1/2) < 0$.
\end{lemma}
Figure \ref{fig:psi} shows how $r$ controls the shape of the function $\psi_r(\alpha)$. As $r$ increases, $\psi_r''(1/2)$ becomes positive and $\psi_r(\alpha)$ will no longer attain a local maximum in that region. The key step in proving Lemma \ref{lem:rbound} is rearranging $\psi_r(1/2) > \psi_r(\alpha)$ and simplify calculations by using approximations for the logarithmic terms that appear.

Our bound on $r$ compares the average of $w$ over $\{-1, 1\}^k$ with the correlations between $w$ and the Fourier basis functions. If $w$ has strong correlations with the other Fourier basis functions, two assignments which are equal at $\alpha n$ variables will likely either be both satisfying or both not satisfying as $\alpha$ approaches $1$. This increases $\text{E}[X^2]$ but not $\text{E}[X]^2$ and makes Lemma \ref{lem:secondmomentmethod} provide a trivial bound if $r$ is too large. Thus, if $w$ has strong correlations with the Fourier basis functions, we must choose smaller $r$ as reflected by \eqref{eq:rcond}.

To get the tightest bounds, we wish to maximize the expression in \eqref{eq:rcond}. Although we prove our lemma for general $w$ requiring only \eqref{eq:derivhalf0}, we also need $w(u) = 0$ whenever $f(u) = 0$ to apply our lemma to satisfiability. Recalling our definition of $X$ in \eqref{eq:X}, this condition ensures that $C_f(n, rn)$ has a solution whenever $X \ne 0$. Thus,
\begin{equation}
\label{eq:wlambdaf}
w(u) = \lambda(u) f(u)
\end{equation}
for some $\lambda : \{-1, 1\}^k \rightarrow \mathbb{R}$. If we disregard \eqref{eq:derivhalf0}, choosing $\lambda(u) = 1$ would maximize the bound on $r$ in \eqref{eq:rcond}. The additional requirement of \eqref{eq:derivhalf0} for the second moment method to succeed can be viewed as a ``symmetrization penalty'' on $r$. In the appendix, we discuss how to choose $w$ to optimize our bound on $r$ while satisfying \eqref{eq:derivhalf0} and \eqref{eq:wlambdaf}.

\begin{figure*}
\centering
\subfloat[$a=2,b=4$]{
\includegraphics[scale=0.32]{tribes_num_r_20_n_30_num_groups_4_num_trials_50_group_size_2}}
\subfloat[$a=2,b=5$]{
\includegraphics[scale=0.32]{tribes_num_r_20_n_20_num_groups_5_num_trials_50_group_size_2}}
\caption{Proportion of CSPs satisfiable out of 50 trials vs. $r$ for tribes functions. We show our bounds for reference.}
\label{fig:experiments}
\end{figure*}

\subsection{Proving the Main Theorem}
\label{sec:mainproof}
We will combine our lemmas to prove Theorem \ref{thm:main}.
\begin{proof} [Proof of Theorem \ref{thm:main}]
We wish to apply the second moment method on $X$ defined in \eqref{eq:X}, where $w$ is a function we use to weigh assignments to individual constraints. We choose $w$ as described in the full version of the paper, which satisfies both \eqref{eq:derivhalf0} and \eqref{eq:wlambdaf}. Since $w$ satisfies \eqref{eq:wlambdaf}, $\Pr[C_f(n, rn) \ \text{is satisfiable}] \ge \Pr[X \ne 0] \ge \text{E}[X]^2/\text{E}[X^2]$
by Lemma \ref{lem:secondmomentmethod}. Now we will use Lemma \ref{lem:rbound} to show that the conditions for Lemma \ref{lem:achlioptaslem} are satisfied for $\phi_r = g_w(\alpha)^r$ and $r$ satisfying \eqref{eq:rcond}.
For our choice of $w$, it follows from the  derivations in the appendix that the RHS of \eqref{eq:rcond} becomes
\begin{align*}
r < r_{f,\text{low}} = \frac{1}{2} \frac{c}{1 - c} \ \text{where} \ c = \hat{f}(\emptyset) - \frac{\boldsymbol{1}^T A^+ A \boldsymbol{1}}{2^k}
\end{align*}
where $A$ is defined in Section \ref{sec:mainresult}. There is a slight technicality in directly applying Lemma \ref{lem:achlioptaslem} because $\phi_r$ might not be nonnegative for $\alpha < 1/2$; we discuss this in the appendix. Now using \eqref{eq:psiE[X]sq} and \eqref{eq:psiE[Xsq]}, and applying Lemma \ref{lem:achlioptaslem}, we can conclude that there exists $C > 0$ such that
\begin{align*}
\Pr[C_f(n, rn) \ \text{is satisfiable}] \ge \text{E}[X]^2/\text{E}[X^2] \ge C
\end{align*}
for sufficiently large $n$ and all $r < r_{f,\text{low}}$.
\end{proof}
There remains a question of what $r_{f,\text{low}}$ we can hope achieve using a second moment method proof where $X$ is defined as in \eqref{eq:X}. The following lemma provides some intuition for this:
\begin{lemma}
\label{lem:maxr}
In order for the conditions of Lemma \ref{lem:achlioptaslem} to hold at $\alpha_{\max} = 1/2$ for $X$ in the form of \eqref{eq:X} and any choice of $w$ satisfying \eqref{eq:wlambdaf}, we require
\begin{equation}
\label{eq:maxr}
r < \log 2 / \log \frac{1}{\hat{f}(\emptyset) - \frac{\boldsymbol{1}^T A^+ A \boldsymbol{1}}{2^k}} \le r_{f,\text{up}} = \frac{\log 2}{\log \frac{1}{\hat{f}(\emptyset)}}
\end{equation}
\end{lemma}

The difference of $\boldsymbol{1}^T A^+ A \boldsymbol{1}/2^k$ in the lower logarithm compared to $r_{f,\text{up}}$ can be viewed as a ``symmetrization penalty'' necessary for our proof to work.
While Lemma \ref{lem:maxr} does not preclude applications of the second moment method that do not rely on Lemma \ref{lem:achlioptaslem}, consider what happens for $r$ that do not satisfy \eqref{eq:maxr}. For these $r$, the function $\psi_r(\alpha)$ must obtain a maximum at some $\alpha^* \in [0, 1], \alpha^* \ne 1/2$. If it also happens that $\phi_r(\alpha)$ is nonnegative and twice differentiable on $[0, 1]$, and $\psi_r''(\alpha^*) < 0$, then conditions of Lemma \ref{lem:achlioptaslem} hold, and applying it to $\alpha_{\max} = \alpha^*$ along with \eqref{eq:lemachlioptasres}, \eqref{eq:psiE[X]sq}, and \eqref{eq:psiE[Xsq]} will actually imply that
\begin{align*}
\frac{\text{E}[X]^2}{\text{E}[X^2]} \le \frac{1}{B} \left(\frac{\psi_r(1/2)}{ \psi_r(\alpha^*)}\right)^n
\end{align*}
for some constant $B > 0$, which gives us an exponentially decreasing, and therefore trivial lower bound for the second moment method. Therefore, we believe that \eqref{eq:maxr} is near the best lower bound on $r_{f,\text{unsat}}$ that we can achieve by applying the second moment method on $X$ in the form of \eqref{eq:X}.

\section{Experimental Verification of Bounds}
\label{sec:experiments}
We empirically test our bounds with the goal of examining their tightness. For our constraint functions, we will use tribes functions. The tribes function takes the disjunction of $b$ groups of $a$ variables and evaluates to 1 or 0 based on whether the following formula is true:
\begin{align*}
\text{TRIBES}_{a, b}(x_1, \ldots, x_{ab}) = \vee_{i = 0}^{b - 1} \left(\wedge_{j = 1}^a x_{ia + j}\right)
\end{align*}
where $+1$ denotes true and $-1$ denotes false. For our experiments, we randomly generate CSP formulas based on $\text{TRIBES}_{a, b}$. We use the Dimetheus\footnote{https://www.gableske.net/dimetheus} random CSP solver to solve these formulas, or report if no solution exists. We show our results in Figure \ref{fig:experiments}. As expected, our values for lower bounds $r_{f,\text{low}}$ are looser than the upper bounds $r_{f,\text{up}}$.

\section{Conclusion}
Using Fourier analysis and the second moment method, we have shown general bounds on $m/n$, the ratio of constraints to variables; for $m/n$ below these bounds, there is constant probability that a random CSP is satisfiable. We demonstrate that our bounds are easily instantiated and can be applied to obtain novel estimates of the satisfiability threshold for many classes of CSPs. Our bounds depend on how easy it is to symmetrize solutions to the constraint function. We provide a heuristic argument to approximate the best possible lower bounds that our application of the second moment method can achieve; these bounds differ from upper bounds on the satisfiability threshold by a ``symmetrization penalty.'' Thus, an interesting direction of future research is to determine whether we can provide tighter upper bounds that account for symmetrization, or whether symmetrization terms are an artificial product of the second moment method.

\section{Acknowledgements}
This work was supported by the Future of Life Institute
(grant 2016-158687) and by the National Science Foundation (grant 1649208).

\bibliographystyle{aaai}


\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}