Consider the group of matrices $G =\operatorname{GL}(n,\mathbb{Z})$ with integer entries and determinant $\pm 1$. For each matrix $D \in G$, the product of the eigenvalues of $D$ is equal to $\det D =\pm 1$, and so the spectral radius $\rho(D)$, which is the size of the largest eigenvalue, is at least one. Moreover, if $\rho(D) =1$, then all the eigenvalue have size 1 and can be proven to be roots of unity.

My question is this: is there a lower bound $B>1$ such that if $\rho(D) \neq 1$ then $\rho(D) \geq B$? If so, does this $B$ depend on $n$?

  • $\begingroup$ I am not sure of the general case, but I think that if $D \in {\rm GL}(n,\mathbb{Z})$ is not a "signed permutation matrix", ie $DD^{T} \neq I$, a Theorem of Siegel implies that $\rho(DD^{T}) \geq 1.5$. $\endgroup$ – Geoff Robinson Feb 5 '15 at 19:53
  • $\begingroup$ @Goeff can you give a reference for that theorem? $\endgroup$ – Liam Baker Feb 5 '15 at 20:38
  • $\begingroup$ It seems to be Theorem III of "The trace of totally positive and real algebraic integers" by C.L. Siegel, Annals of Maths, 46, 2, (1945), 302-312 $\endgroup$ – Geoff Robinson Feb 5 '15 at 20:45
  • $\begingroup$ You need to use that fact that all eigenvalues of $DD^{T}$ are totally positive algebraic integers, and if one or more of them is not 1, its algebraic conjugates have mean value at least $1.5$. $\endgroup$ – Geoff Robinson Feb 5 '15 at 21:10

Every monic integer polynomial $f(x) \in \mathbb{Z}[x]$ of degree $n$ is the characteristic polynomial of an $n \times n$ matrix, namely its companion matrix. The companion matrix is invertible iff the constant term of $f(x)$ is $\pm 1$. Conversely, every characteristic polynomial of an element of $GL_n(\mathbb{Z})$ has this form. So the question reduces to a question about largest eigenvalues of monic integer polynomials of degree $n$ with constant term $\pm 1$. Let me use "spectral radius" to mean the absolute value of the largest (in absolute value) root of a polynomial to save space.

Now it's clear that a bound of the desired form must exist (depending on $n$). The reason is that if any coefficient $e_k$ of the characteristic polynomial gets large, then at least one of the eigenvalues must be large. More formally, if $e_k$ has absolute value at least ${n \choose k} R^k$, then the spectral radius is at least $R$. Hence, for any $R$, the space of possible coefficients $e_k$ with the appropriate bounds is bounded, and so the set of possible characteristic polynomials with spectral radius less than $R$ is finite. But this argument is very inefficient: it only tells you that the number of such polynomials is at most

$$2 \prod_{i=1}^{n-1} \left( 2 {n \choose k} R^k + 1 \right).$$

For example, when $n = 2$ we are looking at characteristic polynomials of the form $x^2 + kx \pm 1, k \in \mathbb{Z}$. The polynomial $x^2 - x - 1$ has largest eigenvalue the golden ratio

$$\phi = \frac{1 + \sqrt{5}}{2} = 1.618 \dots$$

and the only polynomials that can have smaller largest eigenvalue than this (not equal to $1$ in absolute value) must satisfy $|k| < 2 \phi = 3.236 \dots$. There aren't very many of these and we can just verify by hand that they don't.

The bound must depend on $n$; to see this consider the sequence of polynomials $f_n(x) = x^n - x - 1$. If a root $x_0$ of $f_n(x)$ has absolute value $R = 1 + r \ge 1$ then

$$(1 + r)^n \ge 1 + nr$$

but on the other hand, since $x_0^n = x_0 + 1$ we must have $(1 + r)^n \le 2 + r$. It follows that $2 + r \ge 1 + nr$, so $1 \ge (n - 1) r$, or $r \le \frac{1}{n - 1}$, so

$$R \le 1 + \frac{1}{n - 1}.$$


Lehmer's conjecture (which is what you'll want to Google) says that the spectral radius $R$ of a non-cyclotomic polynomial of degree $n$ satisfies $$ R > 1 + \frac{c}{n} $$ for an absolute constant $c$. There is even a conjecture for the value of $c$ corresponding to a certain 10th degree polynomial. Dobrowolski proved that $$ R > 1 + \frac{c'}{n}\left(\frac{\log\log n}{\log n}\right)^3, $$ and as Doug Lind noted, it is known one can take $c'=1/2$, but no one has improved the form of Dobrowolski's result in more then 30 years. For non-reciprocal polys, Chris Smyth proved Lehmer's conjecture with best possible constant in that case.

  • $\begingroup$ Could you spell out how R is related to the Mahler measure? (I'm doubtless just being a bit slow here) $\endgroup$ – Yemon Choi Feb 6 '15 at 2:30
  • $\begingroup$ @YemonChoi (Exponential) Mahler measure $M(f)$ is the product of $|\lambda|$ over all roots satisfying $|\lambda|>1$. So $M(f)\ge R$, since $R$ is just the largest root. On the other hand, it's highly likely that the smallest value of $M(f)>1$ occurs for a polynomial that has one root $\lambda$ outside the unit circle, one root $\lambda^{-1}$ inside the unit circle, and all other roots on the unit circle. For such polynomials one clearly has $M(f)=R$. $\endgroup$ – Joe Silverman Feb 6 '15 at 4:47
  • $\begingroup$ @JoeSilverman are you saying that Lehmer's Conjecture is equivalent to bounding only the largest eigenvalue from below by $R>1+c/n$? If so, how does one prove that the Mahler measure $M(f)\geq C>1$ from this bound? $\endgroup$ – Liam Baker Feb 6 '15 at 6:50
  • 1
    $\begingroup$ @LiamBaker No, I didn't say that they are equivalent, I very deliberately used the words "highly likely," which means I was making a guess. So my guess is that this is the hardest case, and that a proof of that case would very likely end up being a proof of the full conjecture. But that's all speculation, and I also wouldn't be shocked to be wrong. $\endgroup$ – Joe Silverman Feb 6 '15 at 7:15

Using Qiaochu's terminology, there is an explicit lower bound for the spectral radius $R$ of a non-cyclotomic polynomial of degree $n$, namely $$ R>1+\frac{1}{2n}\Bigl(\frac{\log\log n}{\log n}\Bigr)^3 $$ (see A. Dubickas, On a conjecture of A. Schinzel and H. Zassenhaus, Acta Arith. 63 (1993), 15-20 for a slightly sharper result).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.