1. First Game: Sets and Functions
Let $X$ be an arbitrary set (e.g. points in space, animals in a zoo.) and let $f: X \rightarrow X$ be some function on $X$. For some $x \in X$, we're gonna look at what happens to the set $\{ x, f(x), f(f(x)), \ldots \}$. We'll call this set the orbit of $x$, and denote it $\text{orb}(x)$. We'll write $f^0(x)$ for $x$, $f^2(x)$ for $f(f(x))$, $f^3(x)$ for $f(f(f(x)))$, et cetera. In this way we have an action of the natural numbers $\mathbb{N}$ on $X$. To be explicit, each $n \in \mathbb{N}$ acts on each $x \in X$ by
$\displaystyle n \mapsto f^n(x)$
It might be worth pointing out that:$\displaystyle n+m \mapsto f^{n+m}(x) = f^n ( f^m(x))$
If $f$ is invertible, then we have an action of the group $\mathbb{Z}$ on $X$. In fact, we can play our game with any group $G$ that acts on $X$, but for now we're only considering $\mathbb{N}$.We're gonna play three games with the pair $(X, f)$. The first has to do with sets and functions, the second with topological spaces and continuous functions, and the third with a measurable space $X$. Each game will get progressively harder, but progressively more rewarding.
So here's the first game: given a set $X$, we have to find an $x \in X$ and a $f: X \rightarrow X$ so that as we cycle through $x$, $f(x)$, $f^2(x)$, \ldots we end up with all of X. Id est, $\text{orb}(x) = X$.
At first glance it may seem impossible to tell without more information about X. But we can already exclude an entire category of sets $X$. Can you see it?
That's right, uncountable sets won't play. $\text{orb}(x) = \{ f^n(x) \; : \; n \in \mathbb{N}\}$, thus its always countable. Let's try it for a really easy set: the natural numbers $\mathbb{N}$ themselves. Can you find a number $n$ and a function $f: \mathbb{N} \rightarrow \mathbb{N}$ such that $\text{orb}(n) = \mathbb{N}$ ?
I hope no one has trouble seeing that $n=0$ and $f(n) = n + 1$ does the trick. What about for the integers $X = \mathbb{Z}$? Can one find a function $f: \mathbb{Z} \rightarrow \mathbb{Z}$ and an integer $n$ such that $\text{orb}(n) = \mathbb{Z}$ ? How about for $\mathbb{Q}$?
Now lets try to finish the game: Can we do this for an arbitrary countably infinite set $X$?
Since $X$ is countably infinite, we know we have a bijection $\phi: X \rightarrow \mathbb{N}$. Let $x \in X$, and choose $\phi$ so that $\phi (x) = 0$. Now remember our function for the natural numbers? We'll rename it $p(n) = n+1$ here. We have something like this:
$\displaystyle X \xrightarrow{\phi} \mathbb{N} \xrightarrow{\phi^{-1}} X$
So we pass into the natural numbers, use the orbit there, and then pass back into $X$. Id est, let $f : X \rightarrow X$ by $f(x)= \phi^{-1} \circ p \circ \phi (x)$. Then $\text{orb}(x) = X$. As it turns out, the condition that there exists an $f: X \rightarrow X$ and an $x \in X$ such that $\text{orb}(x) = X$ is exactly the same condition that X is countably infinite, as $\text{orb}(x)$ puts $X$ in a bijection with the natural numbers. This game was rigged so that we could win!
But while we're at it, let's try a slightly harder game: given a countably infinite set $X$, can we find a function $f: X \rightarrow X$ such that $\text{orb}(x) = X$ for all $x \in X$ ?
No! Can you see why not? Let $x, y \in X$. since $\text{orb}(x) = \text{orb}(y) = X$, there exist numbers $n, m$ such that $f^n(x) = y$ and $f^m(y) = x$. Hence $f^m(f^n(x)) = x$. In other words, $f^{n+m}(x) = x$, meaning the action of the natural numbers on $X$ is periodic, and $|\text{orb}(x)| \leq n+m$. The orbits of an element tell us something special about that element, and unless we're in a finite set, only a few elements can visit the entire set.
2. Second Game: Orbits for Topological Spaces
So as we stated, the last game (finding a function and element such that the orbit is the entire set) was rigged so that we always win. But it's helpful to see just how badly its rigged. In the category of sets, the only ``structure'' we have to preserve is the cardinality of the set. Bijective functions obviously preserve cardinality. Since countably infinite sets are all bijective with the natural numbers by definition they are, in a sense, all the same. The category of countably infinite sets has only one element, $\mathbb{N}$. Anything we prove about $\mathbb{N}$ as a countably infinite set is automatically true for all other countably infinite sets.
So to make the game a bit more interesting, we're going to have to play in a more exciting category. Instead of looking at countably infinite sets, we're going to look at topological spaces. Loosely speaking, a topological space is our most general notion of a space. It gives us a mathematical language for describing when points are ``near each other'', or ``in a neighborhood''. If we say that $X$ is a topological space, we mean that there exists a collection of open subsets $U \subset X$, and these subsets must behave in a particular way. (For more information, see a decent book on topology, like those by Munkres or Armstrong, or talk to students in our General Topology study group.)
Instead of dealing with arbitrary functions $f: X \rightarrow X$, we'll also want a new condition on $f$. Since $X$ is a topological space, we want functions that live on topological spaces, in the same way a linear map lives on vector spaces, or group homomorphism live on groups. These functions are the ``continuous functions''. We require $f: X \rightarrow X$ to be continuous, that is, if $U \subset X$ is open, then $f^{-1} (U) = \{ x \in X : f(x) \in U \}$ must be open, too.
Now that we have $X$ a topological space and $f$ a continuous function (we'll call the pair $(X, f)$ a topological dynamical system), we can get back to our game. When is $\text{orb}(x) = X$ ?
Almost never. Topological spaces (like $\mathbb{R}$ or $\mathbb{C}$) are almost always uncountable, and as we already discussed, this is impossible. So we have to modify our game a bit. If $\text{orb}(x) \neq X$, what is the next best thing? (If you've not taken measure theory, functional analysis, or general topology, you may be forgiven for not knowing.)
In this game, we want $\text{orb}(x)$ to be dense in $X$. If you've never seen dense sets before, think of the rationals $\mathbb{Q}$ sitting in $\mathbb{R}$. In $\mathbb{R}$, the open sets are exactly the open intervals. And any open interval in $\mathbb{R}$ intersects $\mathbb{Q}$. If you've had more analysis, another way to say this is that a subset of $X$ is dense in $X$ if its closure is all of $X$.
So this is the game: given a pair $(X,f)$, $X$ a topological space and $f$ a continuous function, can you find an element $x \in X$ such that $\overline{\text{orb}(x)} = X$ (id est, the closure of $\text{orb}(x)$ is $X$).
This game is a lot harder, and it'll require some new tools. Let me give you a definition and a few lemmas.
Def1 1 Let $(X, f)$ be a topological dynamical system. We call the system minimal if given a closed set $V \subset X$ such that $f(V) = V$, then $V = X$ or $V = \emptyset$. (That is, if the only invariant closed sets are the whole space or the null set.)
Minimality allows us to win the game. Actually, its equivalent to winning; consider the following proposition:
Let $(X, f)$ be a topological dynamical system. The system is minimal if and only if $\overline{\text{orb}(x)} = X$ for all $x \in X$.
Proof: Assume that $(X, f)$ is minimal. $\overline{\text{orb}(x)}$ is clearly closed, invariant under $f$, and non-empty. Thus it must be X. Conversely, assume X is not minimal, and let $V$ be a closed, non-empty $f$-invariant subset of X. Let $x \in V$. Since V is $f$-invariant, $\text{orb}(x) \subset V$, and hence its closure can't be all of X. $\Box$
This game is called Topological Dynamics. Another lemma, not stated here, says that any topological space $X$ has an minimal subsystem. The proof is a simple application of Zorn's lemma. We can actually state (and prove!) a key theorem in the subject:
Thrm 2 (Birkhoff Recurrence Theorem) Let $(X,f)$ be a minimal topological dynamical system. Then there is some $x \in X$ and a sequence $1 \leq n_1 < n_2 < \ldots $ of natural numbers such that $f^{n_k}(x) \rightarrow x$ as $k \rightarrow \infty$.
Proof: Let $x \in X$. Since the system is minimal, we know that $\text{orb}(x)$ is dense in $X$. If there is some $n$ such that $f^n(x)=x$, then we're done. Otherwise, $\text{orb}(x)$ dense means that its closure is the whole space, which means that we can find some sequence $y_k \in \text{orb}(x)$ such that $y_n \rightarrow x$. Naturally, each $y_k = f^{n_k}(x)$. So we're done. $\Box$
Who else plays this game? It's actually been used successfully to prove theorems in number theory. More specifically, it's been used to prove a Ramsey-type problem about colouring the integers. I'll state it.
Thrm 3 (Van der Waerden's Theorem) Suppose that the integers are coloured in r colours. Then for every $k \geq 2$ there is a monochromatic arithmetic progression of length k.
The proof uses a generalization of the above Recurrence Theorem. It also uses compact metric spaces instead of general topological spaces. But, of course, compact metric spaces is a sub-category of topological spaces, and they're much easier to work with (general topological spaces can be quite pathological.)
So we've seen how to make the game more interesting my looking at more exciting categories. We've stated an equivalent condition to winning the game (minimality), and though I haven't shown you any specific examples of the game, I've given you some of the rewards (e.g. Van der Waerden's Theorem) of winning. Let's look at the third game:
3. Third game: Measurable Systems
Now we're going to look at another category of sets and functions. This time $X$ must be a compact metric space. But we want a bit more structure. $X$ must be measurable, that is, for certain ``well behave'' subsets $U \subset X$, we have a function, called a measure, that assigns a ``size'' to U, $\mu(U) \in [0,1]$, and we require the size of the total space to be 1, id est, $\mu(X) = 1$. The subsets for with $\mu$ is defined are called the measurable sets. If you've taken measure theory or probability, then you should recognize that we want $X$ to be a probability space. You can check those courses for more details on this category.
The function $f: X \rightarrow X$ must meet new requirements, too. It must ``live'' on measurable spaces, id est, $f$ must be a measurable map. The definition is similar to that for continuous functions: $f$ is measurable if for all measurable subsets $U \subset X$, $f^{-1}(U)$ is also a measurable set. The measuring function $\mu$ must also be $f$-invariant. That is, $\mu(f^{1}(U) = \mu (U)$.
We call the triple $(X, \mu, f)$ a measure-preserving system. Like in the last two games, we want to know what happens to $\text{orb}(x)$. But things get very subtle here. Like in the last game, we had a condition (minimal systems) that told us when we were onto something. We have a similar condition here:
Def1 4 We call the measure preserving system $(X, \mu, f)$ ergodic if the only $f$-invariant sets have measure 0 or measure 1.
This game is called Ergodic Theory. Who do you think plays it and why? Can you prove a result similar to our proposition on minimality for ergodicity?
At the core, this game is concerned with the statistical study paths of motion of points in some space, whether it be the phase space of a Hamiltonian in physics, or the state spaces of Markov chains (random processes) in statistics.
The idea is to think of the action $n \in \mathbb{N}$ as a particular time, and then $\text{orb}(x) = \{ f^n(x) : n\mathbb{N}\}$ is the time-path of state $x$. This allows us to get a ``time average'' and a ``space average'' of functions on the measure preserving system. Let $\phi: X \rightarrow \mathbb{C}$ be an integrable function.
Def1 5 Let $(X, \mu, f)$ be a measure preserving system. The time average of $\phi$ starting from $x \in X$ is denoted$\displaystyle <\phi>_x = \lim_{n \rightarrow \infty} \frac{1}{n} \sum_{i=0}^{n} \phi(f^i(x))$
Def1 6 The space average of $\phi$ is denoted$\displaystyle \overline{\phi} = \int \phi(x) d\mu$
(This is the integral with respect to the measure $\mu$. If you've not seen this before, talk to someone who has taken measure theory.)
To see think about these definitions, consider a subset $U \in X$, and the indicator function on $A$ (that's the function $I: X \rightarrow \mathbb{C}$, $I(x) = 1$ is $x \in UA$, otherwise $I(x)=0$). The time average of $<I>_x$ is time that the orbit of $x$ will spend in A, while the space average is the probability that a random state $x$ is in $U$.
One of the important results about measure theory is the following theorem:
Thrm 7 For an ergodic measure preserving system $(X, \mu, f)$ and $\phi: X \rightarrow \mathbb{C}$ a measurable function, the limit $<\phi>_x$ exists and is equal to $\overline{\phi}$ for almost all $x \in X$.
Since the two are almost always equal, almost all paths cover the state space in the same way. In other words, this theorem tells us that for a sufficiently large amount of time (id est, a sufficiently large sample) we can learn information about the entire system (or entire population.) Think ``law of large numbers''.
While we can't play too many ergodic games, I do want to give an example.
Let $X = \mathbb{R}^2/\mathbb{Z}^2$, that is, let $X$ be a torus, and let $\alpha \in \mathbb{R}^2$. Let $f: X \rightarrow X$ be the function $f(x) = x + \alpha$. With a bit of work from measure theory, you can show that this is an ergodic measure preserving system.
When $\alpha = (\sqrt{2},\sqrt{3})$ and $x = (0,0)$, then $\text{orb}(x)$ is dense in $X$.
If $\alpha = (\frac{1}{3},\frac{2}{5})$ and $x = (0,0)$, then $\overline{\text{orb}(x)}$ is a finite set of fifteen points.
If $\alpha = (\sqrt{2},\sqrt{2})$ and $x = (0,0)$, then $\text{orb}(x)$ is dense in the subspace $\{ (x,x) : x \in \mathbb{R}/\mathbb{Z} \}$.
These weird facts pop out of a much deeper theorem, Ratner's theorem, that I cannot even state, but it roughly says that orbit closures are ``algebraic sets''. Ratner actually has several related theorems, and these theorems are related to the proof of the Oppenheim conjecture. The Oppenheim conjecture is an important statement about analytic number theory and real quadratic forms in several variables. It was proven using Ergodic theorems on Lie Groups. The proof of this theorem could actually make a third year project.
4. Sources
I lifted material for this talk from several sources, most prominently:
No comments:
Post a Comment