# Traces of powers of integral marices

I have encountered the following linear algebra/number theory question in my work (low-dimensional topology), so I thought I should ask the experts.

Let $A \in SL(n,\mathbb{Z})$ be a matrix , $n \geq 3$. One can easily show that there is some $j \in \mathbb{N}$ such that $Tr(A^j) \geq 3$ (proof given at the end). My question is that how long does it take for this to happen?

Question 1 Given $n \geq 3$, is there a number $k \in \mathbb{N}$ (depending only on n) such that for all $A \in SL(n,\mathbb{Z})$ there is some $1 \leq i \leq k$ such that $Tr(A^i) \geq 3$?

Question 2: If the answer to the above question is yes, then how $k$ depends on $n$?

Proof of the claimed fact: Assume the contrary that $Tr(A^i) \leq 2$ for all natural numbers $i$. Let $\lambda_1 , ... , \lambda_n$ be the eigenvalues of $A$, therefore $T_i := Tr(A^i) = \lambda_1 ^i + ... + \lambda_n ^i$. Since $T_i$ are bounded above and $\lambda_1 ... \lambda_n =1$ then we should have $|\lambda_i| = 1$ for each $1 \leq i \leq n$. This implies that all $\lambda_1 , ..., \lambda_n$ are roots of unity (because all of their Galois conjugates are on the unit circle) and therefore for some $j \in \mathbb{N}$ we have $\lambda_1 ^j = ... = \lambda_n ^j = 1$. This implies $T_j \geq n \geq 3$. Contradiction.

PS: Replace the assumption $A \in SL(n,\mathbb{Z})$ by $A \in Sp(2n,\mathbb{Z})$, if it makes things easier.

• Wouldn't it be more natural to ask for $A^i$ to have trace at least $n$? Aug 27, 2016 at 1:30
• @NoamD.Elkies You are right. But I only need the trace in my work to be at least 3 and it is important for me how large is k. Aug 27, 2016 at 1:31
• @ChristianRemling Could you elaborate, please? Aug 27, 2016 at 1:32
• @ChristianRemling I assumed if all the Galois conjugates of an algebraic integer are on the unit circle, then it should be a root of unity. Aug 27, 2016 at 1:35
• Part of the argument is hidden in the sentence "Since $T_i$ are bounded..." and this could be useful for a quantitative statement. In detail, there exist arbitrary large $n$ such that all $\lambda_i^n$ have, say, argument in $[-\pi/4,\pi/4]$, and if some $\lambda_i$ is outside the unit disc, then for large enough $n$ $\lambda_i^n$ is large, so combining we get $n$ with all $\lambda_i^n$ having positive real value and at least one being large. [This part is fine for an arbitrary matrix in $\mathrm{SL}_n(\mathbf{C})$] (...)
– YCor
Aug 27, 2016 at 6:28

Yes: for every $d\ge 3$ and all $A\in\mathrm{GL}_d(\mathbf{Z})$, there exists $n\in\{1,\dots,12^d\}$ such that the trace of $A^n$ is $\ge 3$. (This is probably far from sharp, and I don't know if we can do better than exponential.)

First part: I claim that if $t=(t_1,\dots,t_d)$ is a $d$-tuple in the unit circle, then there exists $n\in\{1,\dots,12^d\}$ such that all $t_1^n\dots t_d^n$ have argument in $[-\pi/6,\pi/6]$.

Indeed otherwise, denote $P_\theta$ as the set of $d$-tuples in the unit circle of argument in $\mathopen]-\theta,\theta\mathclose[$. Then for all $m\neq n$ with $m,n\in\{-12^d/2,\dots,12^d/2\}$, we have $t^{m-n}$ not in $P_{\pi/6}$. Define $V_n=t^nP_{\pi/12}$. Then the $V_i$, for $i\in\{-12^d/2,\dots,12^d/2\}$, are pairwise disjoint. If we endow the torus with the normalized Haar measure, the measure of $P_{\pi\theta}$, for $0\le\theta\le 1$ is equal to $\theta^d$. Hence the measure of $V_i$ is $(1/12)^d$. So $(12^d+1)/12^d\le 1$, that is, $1+12^{-d}\le 1$, contradiction.

I conclude with the following claim. Consider a matrix in $A=\mathrm{GL}_d(\mathbf{R})$ with $d\ge 3$, $|\det(A)|=1$, and all eigenvalues having argument in $[-\pi/6,\pi/6]$. Then the trace of $A$ is $>2$. In particular, if $A$ is integral then its trace is $\ge 3$.

Indeed, let $\lambda_1,\dots,\lambda_d$ be the eigenvalues, of modulus $r_1\ge r_2\ge \dots \ge r_d$ (we can suppose that conjugate eigenvalues are written consecutively). If $r_3\ge 1$, then the trace is $\ge (\sqrt{3}/2)(r_1+r_2+r_3)\ge 3\sqrt{3}/2> 2$.

Now suppose $r_3<1$. Note that $\prod r_i=1$, so $r_1r_2=\prod_{i\ge 3}r_i^{-1}>1$, so $r_2>1/r_1$. If $\lambda_1$ and $\lambda_2$ are real, then the trace is $>r_1+r_2>r_1+r_1^{-1}\ge 2$. If $\lambda_1$ is real and $\lambda_2$ is nonreal, then $r_2=r_3$ and hence the trace is $\ge r_1+2(\sqrt{3}/2)r_2>r_1+r_2>r_1+r_1^{-1}\ge 2$. If $\lambda_1$ is non-real and $\lambda_3$ is real, then $r_1=r_2$ and the trace is $>\sqrt{3}r_1+r_2\ge r_1+r_1^{-1}\ge 2$. Finally if both $\lambda_1$ and $\lambda_3$ are non-real, then $k\ge 4$, $r_1=r_2$, $r_3=r_4$ the trace is $\ge \sqrt{3}(r_1+r_3)$; we have $r_1^2r_3^2\ge 1$ implying $r_3\ge r_1^{-1}$ and hence the trace is $\ge \sqrt{3}(r_1+r_1^{-1})\ge 2\sqrt{3}>3$.

• Do you think a polynomial bound is true? Are there some examples that prevent a linear bound to be true? Aug 27, 2016 at 11:59
• I already wrote that I don't know in the first paragraph of this answer. I indeed doubt that the best bound be exponential, and even linear seems plausible at first sight.
– YCor
Aug 27, 2016 at 13:40

Thue's lemma allows to get an exponential bound for $k(n)$, though it seems to be not sharp. More specifically, idea is the following. We partition the unit circle onto three equal arcs $A,B,C$ and for each $k$ encode a sequence $(\lambda_1^k,\dots,\lambda_n^k)$ by a sequence of $n$ letters A,B,C which correspond to arcs containing arguments of $\lambda_i^k$. By pigeonhole principle two sequences concide for some positive integers $k,m$ not exceeding $3^n+1$. It means that for $h:=|k-m|$ real parts of all numbers $\lambda_i^h$ are positive and at least half of their absolute values, thus $\sum \lambda_i^h\geqslant \sum |\lambda_i|^h/2\geqslant n/2$.

• Thanks for the neat argument! Do you think a polynomial bound is true? Is there any examples that prevent a linear bound to be true? Aug 27, 2016 at 11:54
• I think, actually the growth of $k(n)$ is at most linear. Say, if all absolute values of $\lambda's$ are equal, then $k$ does not depend on $n$ at all. Indeed, it suffice to choose $k$ such that the average distance from the argument of $\lambda_i^k$ to 0 (mod $2\pi$) is less than, say, $1/100$. Aug 27, 2016 at 16:19
• I don't see how k might not depend on n in case that $\lambda$'s have equal norm. For example when the characteristic polynomial of A is $x^n-1$, and n is prime, then for $j<n$ we have $Tr(A^j)=1$. The case that the characteristic polynomial is a product of factor of the form $x^t-1$ is mysterious for me. Am I missing something? Aug 28, 2016 at 3:29
• @Mehdi Oh, you are completely right, and me completely wrong. Aug 28, 2016 at 7:24

The answer to Question 1 is yes, although I don't think I can extract a reasonable bound from the argument I have in mind. First observe that the question reduces to a question about largest (in absolute value) roots of monic integer polynomial of degree $n$ with constant term $1$: namely, it's equivalent to asking whether the smallest possible such roots greater than $1$ in absolute value are bounded away from $1$ in absolute value, with the bound possibly depending on $n$.

If such a polynomial has $k^{th}$ coefficient at least ${n \choose k} r^k$ in absolute value then it must have a root of absolute value at least $r$. It follows that for fixed $r$ and $n$, the set of such polynomials with all roots of absolute value at most $r$ is finite, so the conclusion follows.

• The question is not only about modulus: it's $\sum\lambda_i^n$ and not $\sum|\lambda_i|^n$. So even if $\lambda_i^n$ has real part $\ge 3$, some $\lambda_j^n$ could have a large negative real part and compensate it. I guess (as I said in my comment) that this can be handled, but with some additional arguments.
– YCor
Aug 27, 2016 at 6:36
• @YCor: you're right, this needs an additional argument, but it's not so bad. We can restrict our attention to the roots which tie for largest in absolute value, then pick $n$ so that the $n^{th}$ powers of all of those roots have approximately the same argument. Aug 27, 2016 at 6:38
• Yes, but this requires some elaboration to work quantitatively. The following is true: there is $N=N(n)$ such that for every matrix $M$ in $\mathrm{SL}_n(\mathbf{C})$ and all $k\in\mathbf{Z}$ there exists $k'\in\mathbf{Z}$ such that for every eigenvalue $\lambda$ of $M$, the argument of $\lambda^k$ belongs to $[\pm\pi/4]$. With this in mind, the result follow as soon as you have a uniform lower bound on the spectral radius of matrices in $\mathrm{SL}_n(\mathbf{Z})$ that are not virtually unipotent (i.e. have some eigenvalue that is not root of unity). And this is what you prove.
– YCor
Aug 27, 2016 at 8:12