8
$\begingroup$

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$?

$\endgroup$
4
  • $\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$ Feb 5, 2015 at 19:53
  • $\begingroup$ @Goeff can you give a reference for that theorem? $\endgroup$
    – Liam Baker
    Feb 5, 2015 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$ Feb 5, 2015 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$ Feb 5, 2015 at 21:10

3 Answers 3

7
$\begingroup$

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}.$$

$\endgroup$
0
6
$\begingroup$

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.

$\endgroup$
4
  • $\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, 2015 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$ Feb 6, 2015 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, 2015 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$ Feb 6, 2015 at 7:15
5
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.