Return to Answer

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 always 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 integer values of the $e_k$ is finite, and so the set of possible characteristic polynomials with spectral radius less than $R$ is finite. But as a function of $n$ this argument gives a very bad bound: 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$ 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}.$$

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

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 always 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 integer values of the $e_k$ is finite, and so the set of possible characteristic polynomials with spectral radius less than $R$ is finite.

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

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 always 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 integer values of the $e_k$ is finite, and so the set of possible characteristic polynomials with spectral radius less than $R$ is finite. But as a function of $n$ this argument gives a very bad bound: 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$ 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}.$$

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 always 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 integer values of the $e_k$ is finite, and so the set of possible characteristic polynomials with spectral radius less than $R$ is finite.

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 necessarily depends on $n$; probably you can use a sequence of polynomials like $f_n(x) = x^n - x - 1$, which should have roots pretty close to the $n^{th}$ roots of unity, to see this.

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 always 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 integer values of the $e_k$ is finite, and so the set of possible characteristic polynomials with spectral radius less than $R$ is finite.

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