Basic ergodic theory

Consider a ''random'' process where the next state depends on the previous one but in a chaotic manner - say we consider a particle moving in a box. One would expect that as time passes, the trajectory of the particle fills the entire cube, and does so in a uniform way, so that different subsets are visited with frequency comparable to their volume. The path of the particle would then be called ergodic. Ergodic theory offers tools for analyzing dynamical systems, in particular as the time parameter of the system goes to infinity. Central questions are whether any subset of positive measure in our measure space is visited infinitely often, and whether the process is equidistributed, meaning that the measure of the subset tells the probability that the process lies in the subset at a given time.

In this post, we present the basics of ergodic theory, and use them to prove a strong version of Weyl's equidistribution result for the numbers $\gamma,2\gamma,3\gamma...$ modulo $1$ with $\gamma$ irrational. Another application of ergodic theory we present is the fact that almost all real numbers are normal in the sense that each finite sequence of digits occurs with the expected frequency, in each base. We also sketch a proof of the law of large numbers, assuming merely that the iid. random variables have an expectation. We require only the very basics of measure theory.

Eratosthenes-Legendre sieve

In this post, we present the basic idea of sieve methods and derive the simple Eratosthenes-Legendre sieve. Subsequently, there will be posts about more advanced sieve topics and their applications in number theory. Sieve theory offers tools for estimating various quantities in number theory (and also other branches of mathematics), in particular ones related to primes. The first idea of sieve theory was already invented by Eratosthenes around 2200 years ago. He devised a simple but rather efficient algorithm for finding all the primes up to $x$. Unfortunately, Eratosthenes' algorithm is so famous that the generality of the idea behind it is often forgotten. The idea allows us to estimate theoretically the number of primes up to $x$, or more generally many other similar sets of numbers, instead of taking a fixed $x$ such as $10^{10}$ and doing a boring computation. The simple but important idea can be formulated as follows : If we want to compute the number of those elements of a set $A\subset \mathbb{Z_+}$ with $|A|=x$ that have no prime factors below $z$, we should first take all the $x$ numbers, then subtract the number of even ones, subtract the number of multiples of $3$, subtract the number of multiples of $5$, add the number of multiples of $6$ (they were discarded twice), and so forth. The process goes through all the numbers $d$ that divide the product of the primes up to $z$ and whether we subtract or add depends on the parity of the number of prime divisors of $d$. It was probably Legendre who first wrote down this observation as a formula $-$ around 2000 years after Eratosthenes' algorithm $-$ and it is essentially the principle of inclusion and exclusion from combinatorics. Below we briefly discuss sieve methods in general. Then we derive the Eratosthenes-Legendre sieve and present some applications of it.

A very short introduction to Fourier analysis

In later posts, we consider properties of Fourier series (for instance, convergence and divergence results), as well as lacunary trigonometric series and applications of Fourier series to sum identities, combinatorics and number theory. After that, we discuss the Fourier transform in $\mathbb{R}^d$ and phenomena related to it (uncertainty principles, $L^2$ theory, tempered distributions), and applications to the central limit theorem and PDE.

In this post, we say a a bit about Fourier analysis in general. In classical Fourier analysis, we have a function $f:G\to \mathbb{C}$, where $G$ is is usually the integers modulo $N$, that is $\mathbb{Z}_N$, or the real numbers $\pmod 1$, that is $\mathbb{R}/ \mathbb{Z}$, or the whole Euclidean space $\mathbb{R}^d$ ($G$ can also be the integers $\mathbb{Z}$, but that situation is just dual to $G=\mathbb{R}/\mathbb{Z}$). More generally, in harmonic analysis, $G$ could be any locally compact abelian group, and then the analogue of an exponential function would be a homomorphism from $G$ to $\mathbb{C}$. We want to represent the function $f:G\to \mathbb{C}$ as a sum or integral (depending on the domain) of combinations of trigonometric functions. It turns out that a general function, with some mild regularity properties, has such a representation, so many ''linear'' problems concerning arbitrary functions can be reduced to corresponding problems for trigonometric functions (a ''linear'' problem could for instance be a linear PDE, such as the heat equation, which was Joseph Fourier's original motivation, or a problem about arithmetic progressions). We use the trigonometric exponentials $e^{2\pi in x}$ instead of sines and cosines, since otherwise we would have to do everything separately for them. Besides, cosines and sines can be recovered from trigonometric exponentials by taking real and imaginary parts. The representations we are looking for are

$\begin{eqnarray}f(n)&=&\sum_{k\in \mathbb{Z}_N}\hat{f}(k)e^{\frac{2\pi i k}{N}},\quad\quad\,\,\,\,\, \,f:\mathbb{Z}_N\to \mathbb{C}\\f(x)&=&\sum_{n=-\infty}^{\infty}\hat{f}(n)e^{2\pi i n x},\quad \quad f:\mathbb{R}/\mathbb{Z}\to \mathbb{C}\\f(x)&=&\int_{\mathbb{R}^d}\hat{f}(\xi)e^{2\pi i x\cdot\xi}d\xi,\quad \quad f:\mathbb{R}^d\to \mathbb{C},\end{eqnarray}$
where $x\cdot \xi$ is the inner product of two vectors from $\mathbb{R}^d$.

The functions $\hat{f}$ are some coefficient functions, but not just any functions, as these are called the Fourier transform in the continuous case and Fourier coefficients in the discrete case. From the orthogonality relation

$\begin{eqnarray}\int_{0}^{1}e^{2\pi i (m-n)x}dx=\begin{cases} 0, \quad m \neq n\\ 1,\quad m=n,\end{cases}\end{eqnarray}$

(the name comes from the fact that this relation says that the pairwise inner products of distinct functions $e^{2\pi in x}$ are $0$) or from its equivalent for sums it follows, by multiplying both sides of the three equations above by exponentials and integrating (or summing) both sides, that if we formally change the order of integration (or summation), we arrive at

$\begin{eqnarray}\hat{f}(n)&=&\frac{1}{N}\sum_{k\in \mathbb{Z}_N}f(k)e^{-\frac{2\pi i k}{N}},\quad \quad n \in \mathbb{Z}_N\\\hat{f}(n)&=&\int_{0}^1 f(x)e^{-2\pi i n x}dx,\quad\,\,\,\,\,\, n \in \mathbb{Z}\\ \hat{f}(\xi)&=&\int_{\mathbb{R}^d}f(x)e^{-2\pi i x \cdot\xi}dx,\quad \,\,\,\xi \in \mathbb{R}^d\end{eqnarray}$

(in the first case, there is no problem in changing the order of summations). By definition, this is called a Fourier coefficient of $f$ (or the Fourier transform of $f$ in the third case). Notice that these three formulas resemble very much the three representation formulas given above, so the Fourier transform is essentially its own dual operation, and this is of course an important fact. Next we say a few words about the properties of these transforms.