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

$\begingroup$ What conditions do you want on C? Is it an arbitrary real matrix? $\endgroup$ – Qiaochu Yuan Feb 11 '10 at 22:42

$\begingroup$ 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... $\endgroup$ – 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_j1/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_{j1},I_1,\ldots,I_{j1}$ 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_{j1}$ 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}$.

1$\begingroup$ 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. $\endgroup$ – George Lowther Feb 12 '10 at 0:48

$\begingroup$ 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. $\endgroup$ – Bjorn Poonen Feb 12 '10 at 1:14

1$\begingroup$ 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. $\endgroup$ – Victor Miller Feb 12 '10 at 1:17

$\begingroup$ 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:) $\endgroup$ – George Lowther Feb 12 '10 at 1:39

$\begingroup$ 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. $\endgroup$ – 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(C^{n})=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^{n}K/2. The set of values of exp(inθ) for which this holds forms a pair of arcs of length r^{ n}K (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 BorelCantelli lemma says that, with probability one, Tr(C^{n})<K only finitely often. So, with probability 1, Tr(C^{n}) diverges to infinity.

$\begingroup$ 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. $\endgroup$ – Victor Miller Feb 12 '10 at 2:01

$\begingroup$ @Victor: A little measure theory shows that your version of George's statement is sufficient to justify his. $\endgroup$ – Bjorn Poonen Feb 12 '10 at 3:19

$\begingroup$ 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. $\endgroup$ – Bjorn Poonen Feb 12 '10 at 3:30

$\begingroup$ @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}$. $\endgroup$ – 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 2by2 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.

$\begingroup$ Is there an elliptic C such that tr(C^n) is dense in (2,2)? $\endgroup$ – Tom LaGatta Feb 11 '10 at 23:23

2$\begingroup$ How do you reduce to the determinant 1 case? $\endgroup$ – David E Speyer Feb 12 '10 at 0:03

$\begingroup$ 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$. $\endgroup$ – Victor Miller Feb 12 '10 at 0:12

$\begingroup$ Victor, if it has complex eigenvalues and r>1 then the traces are 2r^n cos(nt). Does this have to grow with n? $\endgroup$ – George Lowther Feb 12 '10 at 0:17

$\begingroup$ 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 nonzero. 2) $\theta$ is irrational. Then by Weyl's criterion, $\cos(nt)$ is dense in $(1,1)$ $\endgroup$ – Victor Miller Feb 12 '10 at 0:23