# Is there a matrix C so that the trace of C^n is dense in R?

I am looking for a matrix $C$ so that the sequence $tr(C^n)$ is dense in the set of real numbers. Equivalently (in the $2 \times 2$ case), find a complex number $z$ so that the sequence $z^n+w^n$ is dense in $\mathbb{R}$ where $w$ is the conjugate of $z$.

-
What conditions do you want on C? Is it an arbitrary real matrix? –  Qiaochu Yuan Feb 11 '10 at 22:42
Actually, I think the answer to your question is yes, such a matrix does exist in the 2x2 case. Can do something similar to the construction of the Liouville constant. I'll write up a full answer in a mo... –  George Lowther Feb 12 '10 at 0:39

The answer is yes, even in the $2 \times 2$ case. Let $q_1,q_2,\ldots$ be an enumeration of the rational numbers. Let $Q_j$ be the closed interval $[q_j-1/j,q_j+1/j]$. Let $I_0=[0,2\pi]$. Let $z=2e^{i \theta}$ for a $\theta \in I_0$ to be determined.

By induction, we construct positive integers $n_1 < n_2 < \ldots$ and closed intervals $I_0 \supseteq I_1 \supseteq \cdots$ such that for each $j$, the trace $z^{n_j} + \bar{z}^{n_j}$ is in $Q_j$ whenever $\theta \in I_j$. Namely, if $n_1,\ldots,n_{j-1},I_1,\ldots,I_{j-1}$ have been determined already, then for any sufficiently large $n_j$, the set of $\theta$ such that $z^{n_j} + \bar{z}^{n_j}$ is in $Q_j$ is a union of closed intervals such that every real number is within $2\pi/n_j$ of a point inside this union and within $2\pi/n_j$ of a point outside this union, so if $n_j$ is chosen large enough, one such interval in this union will be completely contained in $I_{j-1}$ and we name it $I_j$.

The intersection of a descending chain of closed intervals is nonempty, so we can choose $\theta$ such that $\theta \in I_j$ for all $j$. Then $\lbrace z^n+\bar{z}^n : n \ge 1 \rbrace$ contains an element of $Q_j$ for each $j$, so it is dense in $\mathbb{R}$.

-
Ok, cool. I was about to write something similar as per my comment above, using the binary expansion of theta/pi using the idea behind the construction of the Liouville constant. Think it boils down to the same basic idea as this answer though. –  George Lowther Feb 12 '10 at 0:48
Yes. In fact, your approach has the advantage that it gives a more explicit theta. Sorry for posting my solution just as you were about to post yours. –  Bjorn Poonen Feb 12 '10 at 1:14
Bjorn, very nice! I wonder if it's possible to describe a $z$ that works more explicitly? We know that $\theta = \arg(z)/2\pi$ must be irrational, so it would be interesting to start with a particular case, say $\theta = \sqrt{2}-1$, and see if we can find a value for $|z|$ that works. –  Victor Miller Feb 12 '10 at 1:17
I don't know if picking a z at random like that will work but, according to my response, the chances of it working are zero:) –  George Lowther Feb 12 '10 at 1:39
Bjorn - it still gets a little messy choosing the binary digits correctly. Your answer seems pretty good to me and, as it's way past my bedtime now, I'll leave it at that. –  George Lowther Feb 12 '10 at 1:41

In answer to the question as to whether $\text{tr}(C^n)$ is dense in $(-2,2)$: Choose $z=\exp(2 \pi i \theta)$ where $\theta$ is irrational, and let $C$ be the diagonal matrix with $z$ and $\overline{z}$ on the diagonal. By Weyl's criterion , the fractional parts of $n \theta$ are equidistributed modulo 1, and thus $\{z^n\}$ is dense in the unit circle. From this it follows easily that $\text{Re}(z^n)$ is dense in $(-1,1)$.

-

Bjorn has already answered this question in the affirmative, and shown that such matrices do exist. I'd like to add a further comment here though - 'almost no' matrices satisfy the required property. That is, the collection of 2x2 matrices such that Tr(C^n) is dense in R has zero Lebesgue measure.

We know that Tr(C^n) = a^n + b^n where a,b are the roots of the characteristic polynomial of C. If a and b are both real then it is not possible for C to have the required property. The only possibility is where they are complex conjugates, a = r exp(iθ), b = r exp(-iθ) for r >1. Then, Tr(Cn)=2rcos(nθ). Suppose that θ is uniformly distributed over [-π,π], so that exp(inθ) is uniformly distributed on the unit circle for each n. For any positive K, |Tr(C^n)|<K is equivalent to |cos(nθ)|<r-nK/2. The set of values of exp(inθ) for which this holds forms a pair of arcs of length r -nK (to leading order). So,

$$\mathbb{P}(\vert{\rm Tr}(C^n)\vert\lt K)\approx r^{-n}K/\pi$$

to leading order. Summing over n, this is finite. Then, the Borel-Cantelli lemma says that, with probability one, |Tr(Cn)|<K only finitely often. So, with probability 1, |Tr(Cn)| diverges to infinity.

-
Nice argument, but the way that I read it is that for any fixed $r > 1$ the set of $\theta \in (0,1)$ such that $z = r \exp(2 \pi i \theta)$ has $|\text{Tr}(C^n)|$ is not dense has measure 1. –  Victor Miller Feb 12 '10 at 2:01
@Victor: A little measure theory shows that your version of George's statement is sufficient to justify his. –  Bjorn Poonen Feb 12 '10 at 3:19
Another (related) way of understanding the measure 0 statement: If z=r e^{2 pi i t} gives a dense set of traces, then t must be so well approximated by rational numbers that it is a Liouville number (infinite irrationality measure). The set of Liouville numbers has measure 0: in fact, Khinchin proved the same for the set of real numbers with irrationality measure not 2. –  Bjorn Poonen Feb 12 '10 at 3:30
@Bjorn: Thanks, after a little thought I see it. My mistake was forgetting that we're looking at a subset of $\mathbb{C}$ (or its alternate presentation $\mathbb{R}^+ \times \mathbb{R}/\mathbb{Z}$, and not $\mathbb{R}/\mathbb{Z}$. –  Victor Miller Feb 12 '10 at 3:57

(Oops, the rescaling part is bogus in the below. So this only works for C with determinant 1.)

In the 2-by-2 case, the answer is no. (Something like this argument should go through in general).

After rescaling, we can assume the matrix has determinant 1. If C is elliptic (real trace between -2 and 2), then all powers are elliptic, so that's no good. If it's parabolic (trace equal to -2 or 2), then all powers all parabolic, again no good. If it's loxodromic, the traces of the powers have real part going to infinity with n, and so they can't be dense.

-
Is there an elliptic C such that tr(C^n) is dense in (-2,2)? –  Tom LaGatta Feb 11 '10 at 23:23
How do you reduce to the determinant 1 case? –  David Speyer Feb 12 '10 at 0:03
Here's a way around it: Let $r$ be the absolute value of the largest eigenvalue. If $r > 1$ then the traces are a sequence growing like $r^$ (perhaps times a polynomial in $n$). It's not hard to see that this sequence can't be dense in $\mathbb{R}^n$. If $r < 1$ it's also clear that the sequence can't be. Similarly for $r=1$. –  Victor Miller Feb 12 '10 at 0:12
Victor, if it has complex eigenvalues and r>1 then the traces are 2r^n cos(nt). Does this have to grow with n? –  George Lowther Feb 12 '10 at 0:17
I think yes. Write $t=2 \pi \theta$. There are two cases: 1) $\theta$ is rational -- then $\cos(nt)$ takes on only a finite set of values, and unless $\theta =$ an odd integer$/4$, they are non-zero. 2) $\theta$ is irrational. Then by Weyl's criterion, $\cos(nt)$ is dense in $(-1,1)$ –  Victor Miller Feb 12 '10 at 0:23