Probability and Measure - A properly Riemann Integrable function is Lebesgue integrable, and the values of the integrals coincide.

This post was inspired by an old argument that I had with Max about one of the P&M example sheets - were the integration signs supposed to represent Lebesgue integration or Riemann integration?

In previous years, Lebesgue integration was alluded to as an extension to Riemann integration, so we of course both suspected that they reduce to the same thing. Still, making the distinction does in fact matter - if we consider the expressions as Riemann integrals, it would not be valid to evaluate them using arguments based on monotone or dominated convergence.

I remember wondering why our lecturer never bothered to formally establish that Riemann integration is indeed a special case of Lebesgue integration. In this post, I hope to do exactly that. It's not quite as easy as you might have expected - there is a crucial subtlety involving null sets.

Recall the definition of Riemann integration, from Analysis I:

Let $f$ be a function of a closed interval, say $[0,1]$.
A partition $T$ of $[0,1]$ is an increasing sequence $0=t_0,t_1,\ldots,t_n=1$, which splits $[0,1]$ into $n$ intervals given by $[t_0,t_1]$, $[t_1,t_2]$, $\ldots$, $[t_{n-1}, t_n]$.

Define the lower sum over the partition $T$ to be $\displaystyle \sum_{i=0}^{n-1} \inf_{[t_i,t_{i+1}]} f$.
Define the upper sum over $T$ to be $\displaystyle \sum_{i=0}^{n-1} \sup_{[t_i,t_{i+1}]} f$.

$f$ is said to be integrable if, taking the supremum over the lower sums, and the infimum over the upper sums, the results both exist and coincide.

Interestingly, when researching this topic on the internet, I discovered that this definition of integration is actually usually called Darboux integration. What is usually called Riemann integration does not obtain upper and lower sums separately, but instead uses what wiki calls a tagged partition - given a partition, you also pick an arbitrary point $t_i$ inside each interval $[a_i,b_i]$ at which to evaluate the function, and then define the integral to be $\sum f(t_i)(b_i - a_i)$.

This is exactly how Dr. Dorrzapf defined Riemann integral when formally justifying more general constructions such as the path-integral in examples classes (although I vaguely remember that he arbitrarily set the tag $t_i$ to $a_i$).

The reason that our analysis lecturer could take such liberties with his impressionable Analysis students is that Darboux integration and Riemann integration are known to be equivalent. And, with the extra perspective gleaned from a beginner's course in measure theory, I think that his decision was fully justified - the upper and lower sum approach is much better preparation for the subsequent construction of Lebesgue integration.

Recall the definition of Lebesgue integration given in P&M. Our measure space is $([0,1], \mu)$, where $\mu$ is Lebesgue measure.

A simple function is a linear combination of indicator functions of measurable sets.

The integral $\mu(1_A)$ of the indicator function $1_A$ of a measurable set $A$ is defined to be $\mu(A)$. We extend this definition linearly to the set of simple functions.

Let $f$ be a non-negative, (Lebesgue) measurable function. The Lebesgue integral $\mu(f)$ is defined to be $\sup_G \mu(g)$, where $G$ is the set of simple functions dominated by $f$.

A general (measurable) function $f$ is said to be integrable if $\mu(|f|)$ is finite, in which case we define $\mu(f)=\mu(f^+)-\mu(f^-)$.

One slight quirk of notation - if $f$ is non-negative and measurable, $\mu(f)$ is defined whether or not $f$ is integrable.

The fundamental property of integration is the following:

If $f \leq g$ for any function $f$, $g$, then $\mu(f) \leq \mu(g)$.

The above property holds by construction for both Lebesgue and Riemann integrals.

Observation. A lower sum can be considered as a step function, i.e. a linear combination of indicator functions of (half-open) intervals.

Throughout the rest of this post, I will use the integral sign $\int$ to denote Riemann integration exclusively.

Corollary. If $f$ is Lebesgue measurable and Riemann integrable, then $f$ is Lebesgue integrable, and $\mu (f) = \int f \mathrm{d}x$.

Proof: $f$ is Riemann integrable, so there certainly exists one valid upper sum, meaning that $f$, and hence $|f|$, is bounded. Since we are in a finite measure space, $\mu(|f|) < \infty$, and so $f$ is Lebesgue integrable.

From the above observation, the set of lower sums can be considered as a subset of the set of simple functions. Let $G$ be the set of simple functions dominated by $f$, as before. Observe that every upper sum dominates $f$, and so every upper sum dominates every simple function in $G$. These two observations imply the following (you could worry about splitting $f$ up into positive and negative parts if you like, but there is zero difficulty involved):

$$\int f \mathrm{d}x = \sup\{\text{lower sums}\} \leq \sup_G \mu(g) = \mu(f) \leq \inf\{\text{upper sums}\} = \int f \mathrm{d}x $$

So $\int f \mathrm{d}x = \mu(f)$, as required. $\square$

This is not quite sufficient to solve the problem as stated. To prove the full statement, we need to know that a Riemann integrable function is Lebesgue measurable. The proof of this result is actually more obscure than I thought it would be, drawing heavily from the properties of Lebesgue measure.

Recall the proof of Carathéodory's extension theorem, in which we construct the set $\mathcal{M}$ of outer-measurable sets. In fact, $M$ is the completion of the original $\sigma$-algebra, where by completion we mean that every subset of a set of zero measure is also measurable. Lebesgue measure is defined as the completion of the Borel measure on $\mathbb{R}$. This completeness property is precisely what we require.

Lemma. In a complete measure space, if $f$ is measurable, and $f=g$ almost everywhere, then $g$ is also measurable.

Proof: Write $\{f=g\}$ and $\{f \neq g\}$ for the sets on which $f=g$ and $f \neq g$ respectively. These are both measurable, and $\{f \neq g \}$ has measure zero, so every subset of it is measurable.

Given a measurable set $A \subseteq \mathbb{R}$, $g^{-1}(A)=(\left.g\right|_{f \neq g})^{-1}(A)\cup(\left.g\right|_{f = g})^{-1}(A)=(\left.g\right|_{f \neq g})^{-1}(A)\cup(\left.f\right|_{f = g})^{-1}(A)$. But $(\left.g\right|_{f \neq g})^{-1}(A)$ is a subset of the null set $\{f \neq g\}$, so is measurable, and $(\left.f\right|_{f = g})^{-1}(A)$ is also measurable.

Hence $g$ is measurable. $\square$

In a non-complete measure space, the above lemma does not hold. If there exists a non-measurable set $Y$ that is a subset of a null set, then for any measurable function $f$, $g \equiv f + \chi_Y$ is equal to $f$ almost everywhere, but is not measurable.

In order to finish off, I'm going to use heavy machinery that I'm not going to prove (it's sufficiently interesting that I plan to revisit it in future, however).

Theorem. (Riemann-Lebesgue) A function $f$ is Riemann integrable $\Leftrightarrow$ $f$ is bounded and continuous almost everywhere.

Corollary. If $f$ is Riemann integrable, then $f$ is (Lebesgue) measurable.

Proof:  By the theorem, $f$ is equal almost everywhere to the function $g$ which is continuous on a measurable set, and zero on its complement. $g$ is clearly measurable, so using completeness of Lebesgue measure, $f$ is also measurable. $\square$

Conclusion. If $f$ is properly Riemann integrable, then $f$ is Lebesgue integrable, and the Riemann and Lebesgue integrals coincide.

Remark: from the discussion above, it is clear that there can exist a function that is Riemann integrable but not Borel measurable.

There are a few more things to say about the link between Riemann integration and Lebesgue integration. Tomorrow, I will post a short entry discussing examples of non-Riemann integrable functions that are Lebesgue integrable, as well as making a few remarks about improper Riemann integrals.

Graph Theory - The Four-Colour Theorem

The Four-Colour Theorem states that the faces of every planar graph can be coloured with four colours, without ever colouring two contiguous faces the same. A first (supposed) proof of the theorem was given in 1976, relying heavily on the output of a specially designed computer program.

This computer-assisted proof of the Four-Colour Theorem was catalytic (maybe even cataclysmic) in the maths world, challenging the sanctity of home-baked proofs traditionally written in sweat and blood. Historically, the meta-mathematical discussion resulting from this event has often been misrepresented - mathematicians did not object to the computer-assisted approach out of elitism or Luddism, but were genuinely uneasy about how they could be sure that the proposed solution actually constituted an acceptable proof. As it turns out, these misgivings were entirely justified - a team of researchers attempting to verify the original proof of the four-colour theorem were unable to decipher and reproduce the method from the 1976 paper, and were forced to come up with their own solution.

The proof of the FCT has been simplified and improved over the years, but still requires significant computer assistance, so it's understandable that it didn't feature in our course. We did however prove the weaker 5-colour theorem, and derived a very attractive equivalent formulation of the FCT. We also introduced and discussed a couple of interesting objects that were designed in an attempt to prove the FCT. One example is the chromatic polynomial $P_G(x)$, equal to the number of colourings of a graph $G$ in $x$ colours (it's a polynomial for combinatorial reasons). However, in an attempt to limit the scope of my post, I will leave the chromatic polynomial for another day.

The chromatic number of a graph $G$, written $\chi(G)$, is the minimum number of colours required to colour the vertices of $G$ such that no two adjacent vertices have the same colour.

Observe that a $k$-colouring of a graph immediately gives a $k$-partition of the vertices of $G$ with no edges within each partition, so colourings are actually highly valuable in practice.

In general, we are interested in the problem of finding an upper bound for $\chi(G)$. The greedy algorithm gives a first stab at this, but usually performs pretty awfully.

Note that the chromatic number is related to vertex-colourings, whereas the FCT concerns face-colourings. The following construction relates the two problems for the class of planar graphs.

The dual graph $G^\prime$ of $G$ is the graph obtained by placing a vertex inside each face of $G$, and linking two vertexes together (in $G^\prime$) whenever the corresponding faces are continguous (in $G$). Visually, we draw one dual edge through each existing edge.

Above is an example of a self-dual graph on 5 vertices. Note that in general, the dual graph of a planar graph may fail to be simple (i.e. there could be could be multiple edges between two vertices, if $G$ has two faces that share multiple edges, or if there is a bridge). One sufficient condition for the dual to be simple is for $G$ to be $3$-connected, which means that removing any two vertices (and their incident edges) would not suffice to disconnect the graph.

Clearly the dual is planar. You can also visually recognise quite easily that the double-dual is naturally isomorphic to the original graph.

Observation. A vertex-colouring of $G$ is equivalent to a face-colouring of the dual graph $G^\prime$.

Thus, proving that $\chi(G) \leq 4$ for every planar graph is equivalent to the usual statement of the FCT, which asserts that every bridgeless plane map can be face-coloured with four colours. (Quick terminological clarification - map indicates that we are referring to the faces of the graph. A plane graph (or map) is a given instance/embedding/realisation of a planar graph (or map), which is an abstract object. A planar graph can have several different plane graphs whose faces have different numbers of edges, although Euler's formula guarantees that the number of faces must remain constant.)

The following, weaker statement can be proven relatively easily from basic principles.

Theorem. (Five-Colour Theorem)

If $G$ is a planar graph, then $\chi(G)\leq 5$.

Proof: Suppose not. Let $G$ be a minimal counterexample.

Recall (from an earlier post) that for any planar graph, the minimum degree $\delta(G)$ satisfies $\delta(G) \leq 5$.

We first consider the case $\delta(G) \leq 4$. Let $v$ be a vertex of degree $\leq 4$. By minimality, we can colour $G-v$ with 5 colours. But $v$ has at most 4 neighbours in $G$, so we can certainly colour $v$ with one of the 5 colours, giving a 5-colouring of $G$.

So we may assume $\delta(G)=5$.
Pick a vertex of degree 5, with neighbours $v_1$, $v_2$, $v_3$, $v_4$, and $v_5$.
$K_5$ is non-planar, so is not a subgraph of $G$. Thus, we can pick $v_i$ and $v_j$ such that $v_iv_j$ is not an edge. We construct a new graph, $G^\prime$, by removing $v$, and identifying $v_i$ and $v_j$.
This graph is planar by construction, so can be 5-coloured by minimality.

But we can use this colouring to colour $G$. In $G$, colour both $v_i$ and $v_j$ the same colour as the identified vertex in $G^\prime$ (every other vertex apart from $v$ can keep its colour). But now the neighbours of $v$ use only 4 colours, so we can use the 5th colour to complete the 5-colouring of $G$. $\square$

Here is a visual example of the construction used in the above proof:

$G$	$G^\prime$

The Four-Colour Theorem improves upon the above result by showing that $\chi(G)\leq4$ for every planar graph $G$. It is a best possible result - the planar graph $K_4$ certainly requires four distinct colours. As remarked above, its proof is everything but elementary. However, there is an interesting reformulation of the problem that we will take a moment to consider.

We define $\chi^\prime(G)$, the edge-chromatic number, to be the minimum number of colours needed to colours the edges of $G$ such that no two adjacent edges are coloured the same.

A cubic graph is a 3-regular graph, meaning that every vertex has exactly three neighbours.

Observation. To prove the FLT (in it's face-colouring form), we may assume that $G$ is cubic.

At any vertex with degree more than three, we can consider instead the graph obtained by introducing a polygonal roundabout. A face-colouring of the latter induces a face-colouring of the former.
Alternatively,  you can make the same observation by considering a triangulation of the dual graph.

Theorem (Tait)

The FCT holds $\Leftrightarrow$ $\chi^\prime(G)=3$ for every cubic planar bridgeless graph $G$.

Proof: Let $G$ be a cubic bridgeless planar graph. We show that $G$ can be face 4-coloured $\Leftrightarrow$ $G$ can be edge 3-coloured.

Consider $\mathbb{Z}_2\times\mathbb{Z}_2$ as an additive group - containing four elements: 00, 01, 10, 11. These will be our four face-colours, and we will find a corresponding edge-colouring using only 01,10 and 11.

Given a face colouring, let each edge be coloured with the sum of the two bordering face colours. Since $G$ is bridgeless, no edge will be coloured 00. Also, no two adjacent edges will get the same colour, as $a+c \neq b+c$ if $a \neq b$ (recall that we are considering cubic graphs, so there are always exactly three edges incident to a given vertex).

Given an edge colouring, we need to find a face 4-colouring. We will do this by vertex-colouring the dual (observe that the dual of a cubic graph is a triangulation). Each edge of the dual crosses exactly one edge in the original graph. For each edge in the dual, record this initial colour (as a label).

Pick a vertex $v_0$ in the dual, and colour it 00. To obtain the final colour for any other vertex $v$, sum up the labels along any path between $v_0$ and $v$.

The sum of the labels around any triangle is 10+01+11=00, and so the sum of the labels around any cycle vanishes. This proves that the sum of the labels along a path between $v$ and $v_0$ is independent of the path, so the above colouring is well-defined. $\square$

In my humble opinion, that proof is pretty damn awesome. Don't you agree?

Credit for the wording of the proofs should go to Prof. Thomason.

Number Theory, Topics in Analysis: Continued fractions and Diophantine approximation

The Number Theory and Topics in Analysis courses complement each other surprisingly well on the topic of continued fractions. In Number Theory, they were introduced ultimately as a means to an end - a technique for solving Pell's equation, and a prime factorisation algorithm. The TinA approach was vastly more contemplative, presenting continued fractions as a (slightly feeble) attempt to understand some aspects of the nature of real numbers.

The rational numbers are dense in the real numbers. Yet there are lots more real numbers than rational numbers. In order to make any sense at all out of this, we need to be less careless. One possible approach is to quantify the cost or effectiveness of a given rational approximation, by measuring the size of the denominator you have to resort to in order to make it happen (compare this to the degree of the polynomials used to uniformly approximate continuous functions).

The results of this idea are ultimately quite surprising. We obtain a hierarchy of types of real number, based on how costly they are to approximate. The real numbers that are hardest to approximate are what we intuitively consider to be the most regular class of reals - the rational numbers themselves. What?

	Class of real numbers	Measure (per unit)	Cardinality	Category	Cost of approximating
Algebraic numbers	Rationals	0	$\aleph_0$	Meagre	Disastrous
	Irrational algebraics	0	$\aleph_0$	Meagre	Meh
Transcendental numbers	Diophantine transcendentals	1	$\mathfrak{c}$	Meagre
	Non-Diophantine transcendentals	0	$\mathfrak{c}$	Residual	Good

The aim of this post is to establish the above results, as well as providing a more general panorama of continued fractions, their properties, and their applications. I will include results and concepts from both courses, so hopefully anybody reading this will enjoy and benefit from a slightly expanded perspective.

Section 0: A word on decimal expansions

We will show later that continued fractions correspond bijectively with real numbers. So, in some sense, they are an alternative way of representing reals, as opposed to the more familiar decimal expansion. The analogy pretty much stops there - as far as I can tell, there is little to gain in comparing the two systems. Still, I want to seize this opportunity to consider formally a couple of properties of decimals that are usually taken for granted, as we will briefly explore some analagous results for continued fractions.

Proposition 0.1 A real number with a repeating decimal expansion is a rational number.

Proof: Let $\alpha = d.d_1d_2d_3\dots d_m\overline{d_{m+1}\dots d_{m+k}}$. Then $10^m\alpha = N + 0.\overline{d_{m+1}\dots d_{m+k}}$, and $10^{m+k}\alpha=M + 0.\overline{d_{m+1}\dots d_{m+k}}$ for some integers $N$, $M$. Thus, $10^{m+k}\alpha - 10^m\alpha = K$ for some integer $K$, giving $\alpha = \frac{K}{10^{m+k}-10^k}$, and so $\alpha \in \mathbb{Q}$. $\square$ (proof found here).

Proposition 0.2 A rational number has a repeating decimal expansion.

Proof: Consider performing the calculation $\frac{p}{q}$ by long division. At each step, the remainder will be in $\{0,1,2,\ldots,q-1\}$. By the pigeonhole principle, a remainder must repeat after $q+1$ steps. But a repeated remainder forces the calculation into a loop. $\square$

Thus, real numbers with repeating decimal expansions correspond to a particular subclass of numbers - the rationals. We will later remark that real numbers with repeating continued fractions also correspond to a interesting subclass - quadratic algebraic numbers.

Section 1: Diophantine approximation

In this section, we consider the problem of finding a rational number close to an arbitrary real number $\alpha$.

As explained in the introduction, we are mainly interested in obtaining lower bounds for the cost. But no lower bound is complete without an upper bound. The following theorem is the much-needed reality check that I'm very surprised didn't come up in TinA - for any real number, the cost is never going to get pathologically bad.

Theorem 1.1 (Dirichlet's theorem) Let $\alpha$ be a real number. For every $N \in \mathbb{N}$ there exists a rational number $\frac{a}{q}$ with $1 \leq q < N$ and $\left| \alpha - \frac{a}{q}\right| \leq \frac{1}{qN}$.

Proof: Consider the fractional part of the $N+1$ distinct numbers $k\theta$, for $0 \leq k \leq N$. Split the unit interval into the $N$ disjoint intervals of length $\frac{1}{N}$ given by $[\frac{j}{N},\frac{j+1}{N}]$, for $0 \leq j < N$.

By the pigeonhole principle, there must be an inteval containing two of the $k\theta$, say $k_1\theta$ and $k_2\theta$, $k_2>k_1$. But then for $q=k_2-k_1$, $|q \theta - a | \leq \frac{1}{N}$ for some integer $a$. By construction, $1\leq q \leq N$. $\square$

Still, let's not get too optimistic about this. With the obvious caveat that any fraction "approximates" its own equivalence class perfectly, rational numbers are awful at approximating other rationals.

Proposition 1.2 If $\alpha = \frac{a}{b} \neq \frac{p}{q}$, then $\left|\alpha - \frac{p}{q}\right| \geq \frac{1}{bq}$.

Proof: $\left|\frac{a}{b}-\frac{p}{q}\right| = \left|\frac{aq-bp}{bq}\right| \geq \frac{1}{bq}$ $\square$

Algebraic numbers are slightly better, but still fairly poor.

Theorem 1.3 (Liouville's theorem) Let $\alpha$ be algebraic. Then $\exists c>0$ (depending on $\alpha$) such that $\left|\alpha - \frac{p}{q}\right| \geq \frac{c}{q^n}$, for every rational $\frac{p}{q}$, where $n$ is the degree of the minimal polynomial over $\mathbb{Z}$.

Proof: In lectures we only assumed that $f$ is an arbitrary polynomial with $\alpha$ as a root. However, using the minimal polynomial gives a better lower bound. Pick $R$ sufficiently large that all of the (real) roots of $f$ are contained inside $[-R+1,R-1]$. $f^\prime$ is continuous on $[-R,R]$, and so bounded, by $M$, say. For every rational $\frac{p}{q} \in [-R,R]$, if $f(\frac{p}{q}) \neq 0$, then $\frac{1}{q^n} \leq \left|f(\frac{p}{q})\right|= \left|f(\frac{p}{q})-f(\alpha)\right| \leq M \left| \frac{p}{q} -\alpha\right|$, by the mean value theorem.

There are only many finitely roots, so $\exists c_0$ such that $|\frac{p}{q}-\alpha| \geq c_0 \geq \frac{c_0}{q^n}$ for all rational roots $\frac{p}{q}$ of $f$ (which we secretly know have to be integers anyway).

Finally, if $\left|\frac{p}{q}\right| \geq R$, then $\left|\frac{p}{q} - \alpha \right| \geq 1 \geq \frac{1}{q^n}$.

So, by taking $c = \min\{\frac{1}{M},1,c_0\}$, we have found the required constant. $\square$

Consider now a new class of real numbers, the diophantine numbers, which we didn't discuss directly in lectures. In order to motivate the definition, recall Roth's theorem, which was stated (incorrectly!) in lectures as an improvement on Liouville's theorem.

Theorem 1.4 (Thue-Siegel-Roth theorem) Let $\alpha$ be algebraic and irrational. Then for all $\varepsilon > 0$, $\exists c > 0$ such that $\left| \alpha - \frac{p}{q}\right| \geq \frac{c}{q^{2+\varepsilon}}$ for any rational number $\frac{p}{q}$.

(In lectures, this was stated as $\forall \varepsilon$, $\exists c$ such that $\forall \alpha \ldots$, which is incorrect - the constant $c$ depends on $\alpha$.)

Definition. Say that $\alpha \in \mathbb{R}$ is Diophantine if $\forall \varepsilon > 0$, $\exists c >0$ such that $\left| \alpha - \frac{p}{q}\right| \geq \frac{c}{q^{2+\varepsilon}}$ for any rational number $\frac{p}{q}$.

In other words, Theorem 1.4 says that every algebraic number is Diophantine. (Note: there may be other names for this class of numbers - they seem to be discussed very little on wiki. My source for this name is Terry Tao's blog. Not to be confused with Diophantine sets, which are discussed on wiki, and are related to recursively enumerable sets.)

Theorem 1.5 The set of Diophantine numbers has full measure, but is meagre.

Proof: This is actually an excellent exercice in both measure theory and linear analysis, so I won't reproduce the proof here, only link to a good exposition of it. $\square$

These results already suffice to establish the table presented in the introduction. Interestingly, we have shown that the set of numbers that you can approximate very well with rationals is small in the sense of measure, but large in the sense of the Baire Category Theorem.

We have also set the stage for a technique for proving transcendentality - if you can prove that a given number violates the Liouville lower bound, or the stronger Roth lower bound, you can deduce that it's transcendental. An example of this is the Liouville number given in lectures, or more generally the uncountable set of Liouville numbers constructed in Example Sheet 4:

Proposition 1.6 For any sequence $a_n$ taking values in $\{1,2\}$, $\sigma = \sum \frac{a_n}{10^{n!}}$ is transcendental.

Open question (that I want to come back to, but haven't had time to think about yet) - are the above Liouville numbers Diophantine?

Section 2: Continued fractions

We will define continued fractions using the continued fraction algorithm, define the convergent sequences $p_n$ and $q_n$ independently, and then proceed to derive the link between the two. This presentation is backwards compared to the one given in TinA, but it avoids all of the tautologies that everyone was complaining about.

Given a real number $\theta$, we obtain a sequence $a_0,a_1,\ldots$ recursively by applying the following algorithm.

Set $a_0=\lfloor \theta \rfloor$.
Define $\alpha_1 = \frac{1}{\theta - a_0}$ (so $\theta = a_0 + \frac{1}{\alpha_1}$).
Define $a_n=\lfloor \alpha_n \rfloor$, and set $\alpha_{n+1}=\frac{1}{\alpha_n - a_n}$.
If we ever encounter $a_n=\alpha_n$, we terminate the process.

We write $[a_0;a_1,a_2,\ldots]$ for the continued fraction with value $\alpha$. The partial continued fractions $[a_0]$, $[a_0;a_1]$, $[a_0;a_1,a_2]$, $\ldots$ are called the convergents of $\alpha$.

By construction, $[a_0;a_1] = a_0 + \frac{1}{a_1}$, $[a_0;a_1,a_2]= \displaystyle a_0 \frac{1}{a_1 + \frac{1}{a_2}}$, etc, so we recover the characteristic tower form of the continued fraction.

Note that $a_n \in \mathbb{N}$, except for $a_0$, which is in $\mathbb{Z}$.

Proposition 2.1 The continued fraction algorithm terminates $\Leftrightarrow$ $\theta$ is rational.

Proof: If the algorithm terminates, then $\theta=[a_0;a_1,\ldots,a_n]$ for some $a_n$. By multiplying out the denominators in the tower form, it is obvious that $\theta$ is rational.

If $\theta$ is rational, then the $\alpha_i$ constructed in the algorithm are also rational. But by construction, their denominators are strictly decreasing, so the process must terminate. $\square$

Obviously, the first thing we want to show is that the convergents converge to $\alpha$ under the Euclidean metric. However, as things currently stand, the partial continued fractions are unwieldy objects. We introduce two intermediate sequences which are easier to manipulate, and which we will show contain all of the information given by the convergents.

Define the sequences:

$p_0 = a_0$	$p_1=a_0a_1+1$	$p_n=a_np_{n-1}+p_{n-2}$
$q_0 = 1$	$q_1=a_1$	$q_n=a_nq_{n-1}+q_{n-2}$

[Note to self: investigate link with Euclidean division algorithm.]

Here are some elementary properties of this sequence, which we will use later on.

Proposition 2.2

1. For each $n \geq 1$, $p_nq_{n-1}-p_{n-1}q_n=(-1)^{n+1}$.
2. $p_n$ and $q_n$ are coprime.

Proof: For the first statement, we induct on $n$.

When $n=1$, $p_1q_0-p_0q_1=a_0a_1+1-a_0a_1=1$.

Suppose the relation holds for $n$, where $n \geq 1$.

Then $p_{n+1}q_n-p_nq_{n+1}=(a_{n+1}p_n+p_{n-1}q_n)q_n - p_n(a_{n+1}q_n+q_{n-1}) = p_{n-1}q_n-p_nq_{n-1}=(-1)^{n+2}$.

The second statement follows directly from the first (think of Bezout). $\square$

Proposition 2.3 $\frac{p_n}{q_n}=[a_0;a_1,\ldots,a_n]$ in its lowest form.

Proof: Let us relax our notation slightly to allow $\alpha_n$, the last term of $[a_0;a_1,\ldots,\alpha_n]$, to be an arbitrary (positive) real number. Under this notation, we can write $[a_0;a_1,\ldots,a_n,\alpha_{n+1}]=[a_0;a_1,\ldots,a_n+\frac{1}{\alpha_{n+1}}]$. This will hopefully make the calculations slightly clearer.

Observe that the claim is true for $n=0,1,2$ (this involves multiplying out the tower form of $[a_0;a_1,\alpha_2]$, and is absolutely trivial).

Assume that the claim is true for $n$.
$$\displaystyle \frac{p_{n+1}}{q_{n+1}} = \frac{\alpha_{n+1}p_n+p_{n-1}}{\alpha_{n+1}q_n+q_{n-1}} = \frac{p_n + \frac{1}{\alpha_{n+1}}p_{n-1}}{q_n+\frac{1}{\alpha_{n+1}}q_{n-1}}= \frac{(a_np_{n-1}+p_{n-2})+\frac{p_{n-1}}{\alpha_{n+1}}}{(a_nq_{n-1}+q_{n-2})+\frac{q_{n-1}}{\alpha_{n+1}}} = \frac{\left(a_n+\frac{1}{\alpha_{n+1}}\right)p_{n-1}+p_{n-2}}{\left(a_n+\frac{1}{\alpha_{n+1}}\right)q_{n-1}+q_{n-2}}=[a_0;a_1,\ldots,a_n+\frac{1}{\alpha_{n+1}}]=[a_0;a_1,\ldots,a_n,\alpha_{n+1}]$$
We used the induction hypothesis in the second-last equality.
We have already shown above that $p_n$, $q_n$ are coprime, so the fraction is necessarily in its lowest form. $\square$

We now know enough to go ahead and prove that continued fractions converge to their value.

Proposition 2.4 If $[a_0;a_1,a_2,\ldots]$ is the continued fraction obtained from $\theta$ using the division algorithm, then $[a_0;a_1,\ldots,a_n] \to \theta$ as $n \to \infty$.

Proof: Using the relaxed notation from the above proposition, we can write $\theta = [a_0;a_1,\ldots,a_n,\alpha_{n+1}]$, which we know is equal to $\frac{\alpha_{n+1}p_n+p_{n-1}}{\alpha_{n+1}q_n+q_{n-1}}$. So:

$$\left| \theta - \frac{p_n}{q_n}\right| = \left|\frac{\alpha_{n+1}p_n+p_{n-1}}{\alpha_{n+1}q_n+q_{n-1}}-\frac{p_n}{q_n}\right| = \frac{|p_nq_{n-1}-p_{n-1}q_n|}{q_n(\alpha_{n+1}q_n+q_{n-1})}=\frac{1}{q_n(\alpha_{n+1}q_n+q_{n-1})}$$

But by considering the recurrence relation, we see that $q_n$ is a strictly increasing sequence of positive integers. The result follows. $\square$

We have now laid the groundwork for our study of Diophantine approximation via continued fractions. We are not just interested in the fact that continued fractions converge to their value, but also in some intriguing features of their convergence. We will show that continued fractions provide the most cost-effective way to converge to any real, and, remarkably, that the continued fraction algorithm necessarily produces every good approximation - in other words, if a given approximation is particularly cheap, it will naturally arise as one of the convergents defined above.

Firstly, we show that, considered absolutely, the convergence is monotone - every convergent gives a better approximation than the last.

Lemma 2.5 For each $n$, $\frac{1}{q_{n+2}} \leq | q_n \theta - p_n | \leq \frac{1}{q_{n+1}}$. This immediately implies that $|q_n\theta - p_n | \leq |q_{n-1} \theta - p_{n-1}|$, which further implies that $|\theta - \frac{p_n}{q_n}| \leq |\theta - \frac{p_{n-1}}{q_{n-1}}|$.

Proof: The key observation is that $a_{n+1} \leq \alpha_{n+1} \leq a_{n+1} + 1$. This gives $q_{n+1} = a_{n+1}q_n + q_{n-1} \leq \alpha_{n+1}q_n + q_{n-1} \leq (a_{n+1}+1)q_n+q_{n-1} = q_{n+1}+q_n \leq a_{n+2}q_{n+1}+q_n = q_{n+2}$.

Recalling that $|q_n \theta - p_n | = \frac{1}{\alpha_{n+1}q_n+q_{n-1}}$, from the proof of the previous proposition, we are done. $\square$

However, the partial continued fractions oscillate around their limit $\theta$, via the following observation.

Lemma 2.6 For each $n$, $\theta - \frac{p_n}{q_n}$ and $\theta - \frac{p_{n-1}}{q_{n-1}}$ have opposite sign.

Proof: Go back to the proof of the above lemma, and observe that without the mod signs, we obtain $\theta - \frac{p_n}{q_n} = \frac{(-1)^n}{q_n(\alpha_{n+1}q_n+q_{n-1})}$. $\square$

As promised, we now prove that the convergents are the best approximants for a fixed cost.

Theorem 2.7 For any integers $p$ and $q$ such that $0 < q < q_n$, $|q\theta - p| \geq |q_n\theta - p_n|$.

Proof: Let $\begin{pmatrix} u \\ v \end{pmatrix} = \begin{pmatrix} q_{n-1} & p_{n-1} \\ q_n & p_n \end{pmatrix}\begin{pmatrix} p \\ q \end{pmatrix}$. Note that this matrix has determinant $\pm 1$, so is invertible (its inverse has integer coefficients). Therefore, we can write $p = up_{n-1}+vp_n$ and $q = uq_{n-1}+vq_n$ for some integers $u,v$.

So, $|q\theta - p| = |uq_{n-1} \theta + v q_n \theta - u p_{n-1} - vp_n | = |u (q_{n-1} \theta - p_{n-1}) + v(q_n \theta - p_n)|$.

However, we assumed that $0 < q < q_n$, so $0 < uq_{n-1} + vq_n < q_n$. This forces $u$ and $v$ to have opposite signs (if $v=0$ then $\frac{p}{q}=\frac{p_n}{q_n}$). Since $q_{n-1}\theta - p_{n-1}$ and $q_n\theta - p_n$ also have opposite signs by the above lemma, we can write:

$|q\theta - p| = |u(q_{n-1}\theta-p_{n-1})|+|v(q_n\theta - p_n)| \geq |q_{n-1}\theta - p_{n-1}|$. $\square$

And finally, if any approximation is particularly cost-efficient, it must in fact be a convergent.

Corollary 2.8 For any integer $p$ and positive integer $q$, if $|\theta - \frac{p}{q}| < \frac{1}{2q^2}$, then $\frac{p}{q}$ is one of the convergents of $\theta$.

Proof: Assume WLOG that $p$ and $q$ are coprime. Pick $n$ such that $q_n \leq q < q_{n+1}$ (recall the $q_n$ are a strictly increasing sequence of positive integers, and $q_0=1$, so we can do this).

Then $\left| \frac{p}{q} -\frac{p_n}{q_n}\right| \leq \left| \theta - \frac{p}{q}\right| + \left| \theta - \frac{p_n}{q_n}\right| < \frac{1}{2q^2} + \frac{1}{q_n}|q\theta - p| < \frac{1}{2qq_n}+\frac{1}{q_n}\frac{1}{2q} \leq \frac{1}{qq_n}$.

So, $\left|\frac{p}{q}-\frac{p_n}{q_n}\right| = \frac{|pq_n-p_nq|}{qq_n} < \frac{1}{qq_n}$, so $|pq_n-p_nq| < 1$.

We conclude that $pq_n-p_nq=0$, so $\frac{p}{q}=\frac{p_n}{q_n}$. $\square$

The whole point of this section was to show that continued fractions do indeed provide insight about Diophantine approximation. The above result achieves this pretty spectacularly.

Section 3: Examples and applications

In general, computing the continued fraction of an arbitrary real is not very interesting - it is simply a matter of transforming the information we possess about that real (usually in the form of a decimal expansion) into the language of continued fractions.

If our chosen real number is rational, the algorithm terminates - which is hardly interestingly. Conversely, we have shown that if our real number is irrational it doesn't. We might therefore naively expect to have to do an infinite amount of work in order to achieve the full expansion. Tripos questions can be nasty, but hopefully not that nasty (even when PTJ is writing the questions).

However, in lectures, we saw the tantalising example of $\sqrt{2}$. Very quickly, the algorithm developped a loop, and so we could observe that the continued fraction expansion must necessarily repeat. On Example Sheet 4, we are asked to calculate the full expansion of $\sqrt{3}$, and so we might hope that something similiar is going to occur.

This generalises. There is a full characterisation of numbers with repeating continued fractions (much like section 0 gives a full characterisation of numbers with repeating decimal expansion), given by the following theorem.

A quadratic irrational is a root of a quadratic equation with integer coefficients. In the Number Fields course, we show that any such number must be of the form $a+b\sqrt{N}$ for some (square-free) integer $N$, and rationals $a$ and $b$.

Theorem 3.1 (Lagrange) For any real number $\theta$, $\theta$ is a quadratic irrational $\Leftrightarrow$ its continued fraction is (eventually) periodic.

For square roots, we can say more. The following theorem gives an excellent error-detecting failsafe for those awkward times when you find yourself needing to calculate the continued fraction of a square root in real time at the supermarket check-out.

Theorem 3.2 Let $N$ be a natural number that is not a square. Then its continued fraction is of the form $[a_0;\overline{a_1,a_2,\ldots,a_2,a_1,2a_0}]$. Thus, it is both periodic and symmetric, and each period ends on twice the integer part.

The proofs of these theorems were not given in my course. However, I have an idea which might suffice to prove a watered-down version of 3.2. Watch this space.

This checks out with the excruciatingly simple example given in TinA: $\sqrt{2} = [1;\overline{2}]$. For the eager beavers out there, you can check that this is coherent with your calculations for $\sqrt{3}$. (On a Number Theory example sheet, we had to calculate $\sqrt{46}$, which is 12-periodic, and thus somewhat sadistic. Side-note: to find a higher period you have to go up to $\sqrt{94}$. Coincidence? I think not.)

One excellent application for which continued fractions are crucial is Pell's equation.

Let $N$ be a natural number that is not a square. Pell's equation is given by:
$$x^2-Ny^2=1$$

Pell's equation is useful for example in Number Fields, where solutions correspond to units of a given real quadratic field extension (the norm of $x+y \sqrt N$ is defined to be $x^2-Ny^2$).

We can use continued fractions to prove that Pell's equation can always be solved. We won't go through the method fully here, as it largely irrelevant to the TinA course, but let us at least make the following observation.

Proposition 3.3 Any solution to Pell's equation must be a convergent of $\sqrt N$.

Proof: $(x - y \sqrt N )(x + y \sqrt N) = 1$. WLOG, we can assume $x$ and $y$ are both positive.
This gives $x-y\sqrt N=\frac{1}{x+y\sqrt N} < \frac{1}{2y\sqrt N}<\frac{1}{2y}$, so $\left |\frac{x}{y} - \sqrt N\right | < \frac{1}{2y^2}$. $\square$

By considering the period of the continued fraction of $\sqrt N$, you can pick out the convergents that give solutions. Dirichlet's Unit Theorem merits a quick shout-out at this point - by pushing this line of reasoning further, you can show that the solutions to Pell's equation (corresponding to non-trivial units in $\mathbb{Q}(\displaystyle \sqrt N)$) form a (cyclic!) group, which is mind-blowingly cool.

A second application of continued fractions also exploits the nice properties of square roots - prime factorisation. This application is sort of technical, so I won't go into it right now, although I am planning a future post dedicated to prime factorisation algorithms.

There is a generalisation of continued fractions called (rather obscurely) "generalised continued fractions". I unfortunately do not have much to say about these at this point in time, other than the $\tan x$ example given in lectures was one of them.

This post has turned out to be massively long, as it was far too ambitious in scope. There are still a few details that I want to investigate in full depth at some point, but it's probably a better idea to do so in another post. I hope that anybody reading enjoyed it, and maybe learned something new.

Footnote: a significant number of these proofs are largely due to my Number Theory lecturer, Dr. Vicky Neale. A couple of them are due to my Topics in Analysis lecturer, Dr. Kovalev.

Linear Analysis: Baire Category Theorem

The Baire Category Theorem is this year's big surprise for analysts (or it would have been, if Dr. Garling hadn't been so enthusiastic about it in Analysis II). Spanning the rift between topology and analysis like a mathematical bifrost, it allows us to link local properties such as openness to global properties such as denseness.

Dense. A set $A \subset X$ is dense in $X$ if $\overline{A}=X$. Equivalently, $A$ is dense in $X$ if $A \cap N \neq \emptyset$ for any non-empty open set $N$ in $X$.
Nowhere dense. A set $A \subset X$ is nowhere dense in $X$ if $\text{int}(\overline{A})=\emptyset$.
Meagre. A meagre set is a countable union of nowhere dense sets.
1st category. Meagre.
2nd category. Not meagre.
Residual set. The complement of a meagre set. 

Theorem 1.1 (Baire Category Theorem I)

In a complete metric space, the intersection of countably many dense, open subsets is still dense.

Proof: Take a sequence of nested open and closed balls, alternatingly. The centres of the closed balls give a Cauchy subsequence, if you shrink the balls fast enough, so there is a limit in the intersection by completeness. Equivalently, the intersection of a sequence of nested compact sets is non-empty in a complete metric space.  $\square$

Theorem 1.2 (Baire Category Theorem II)

In a non-empty complete metric space $X$, the union of countably many closed, nowhere dense sets does not cover the whole space. Equivalently, if $X$ is the union of countably many closed sets, then one of those closed sets contains an open ball.

Proof: (using 1.1) Suppose $X=\bigcup^\infty F_n$, where the $F_n$ are closed. Set $U_n=X\backslash F_n$, which is open. Then $\bigcap^\infty U_n = \emptyset$, so one of the $U_n$ is not dense, from Theorem 1.1, which implies that one of the $F_n$ contains an open ball. $\square$

Proof of 1.1 assuming 1.2: This is fairly easy, using the observation that the complement of a nowhere dense set is a dense set, and vice-versa. In 1.1 we do not assume that $X$ is empty, so observe that if $X$ does happen to be empty, the intersection of any sequence of sets is dense, and so we are done. Suppose $U_n$ is a sequence of dense, open sets. Then $F_n=X\backslash U_n$ is a sequence of nowhere dense, closed sets. $\bigcap U_n = \bigcap (X\backslash F_n)= X\backslash \bigcup F_n \neq \emptyset$, where inequality follows from 1.2. We have currently only found one point in the intersection of the $U_n$, but this is another one of those cases where we are actually already done with no extra effort. Simply consider the subspace of $X$ given by the restriction of $X$ to any open ball to force the point we found to be where we want it. Thus, the intersection of the $U_n$ is in fact still dense. $\square$


Note that if you have any sequence of sets $F_n$ such that $X=\bigcup^\infty F_n$, you can apply BCT to their closures to conclude that they can't all be nowhere dense, strengthening the above statement slightly.

Remark 1.3. The Baire Category Theorem is equivalent to the Axiom of Dependent Choice.

Applications of the Baire Category Theorem

Result	Space	How?
Every complete metric space with no isolated points is uncountable.	Any complete space	Singleton sets are nowhere dense
There exist continuous nowhere differentiable functions.	$C[0,1]$, $\|.\|_\infty$	The set of functions differentiable at some point is meagre. $Y_n = \{f \mid \exists x \in [0,1], \left|\frac{f(y)-f(x)}{y-x}\right| \leq n$, $\forall y \in [0,1]$, $y \neq x\}$
Principle of uniform boundedness	Any Banach space.	$F_n=\{ x \in X \mid \|Tx\| \leq n, \forall T \in \tau\}$
An infinite-dimensional Banach space has uncountable dimension	Any i.d. Banach space	$F_n=\text{span}\{e_1,\ldots,e_n\}$
Open Mapping Theorem	$X$, $Y$ Banach spaces. $T$ surjective, continuous, linear.	$Y=\bigcup^\infty T(nB_x)$
$f(nx) \to 0$ for each $x>0$, then $f(x) \to 0$	$\mathbb{R}$	$F_N=\{x \mid f(nx)\leq \varepsilon$, $\forall n \geq N\}$

Here is some interesting mathematics that we didn't cover in lectures, but which is easily accessible using the notions we have developped. Baire introduced a classification of functions on the real line as a way of measuring how discontinuous they are.

Define the set of Baire class zero functions to be the set of continuous functions. Define the set of Baire class $n$ functions to be the set of functions that are the pointwise limit of a sequence of Baire class $n-1$ functions.

The Baire class $n$ is a vector space^{[citation needed]}. Several of the results that we have encountered (and a couple of extra-curricular, but relevant ones) can be rephrased rather pleasingly in terms of Baire classes, and $G_\delta$ language.

Theorem 1.4 The set of points of discontinuity of a Baire class one function is meagre. (See Ex2Q4+12.)

Theorem 1.5 The set of points of continuity of any function is a $G_\delta$ set. (See Ex2Q11.)

Theorem 1.6 The derivative of a differentiable function is Baire class one.

Culminating in a result which I promised someone on stackexchange I would get around to proving:

Theorem 1.7 The graph of a derivative is connected. (More generally, so is the graph of any function that is simultaneously Baire class one, and Darboux.)

Question: what's an example of a Baire function that is not in any Baire class? Note that some sources extend to the definition of Baire classes to include a countable ordinal in the index. Perhaps the indicator function of a non-measurable set might do the trick?

[I am planning to come back to this post to include proofs of these results, and perhaps add some extra results. Example sheet 2 was a rough time for most of us, but it's incredibly rich - I'm gonna mine it for theorems harder than any Minecrafter ever mined for diamonds.]

Number Theory - Deriving Quadratic Reciprocity

There are allegedly dozens of proofs of quadratic reciprocity. Amazingly, not a single one of them is nice. (The undergraduate's definition of nice is something that can be easily remembered/regurgitated without thinking. All of the proofs of quadratic reciprocity that I have read involve pretty mind-bending arguments.)

This section involves extremely fiddly, annoying (or, put another way, marvellously creative, beautiful) mathematics. We need to be ready to get ours hands dirty, constructing bijections/partitions/relations between residue classes based on obscure/unwieldy properties. Good practice for tripos questions, I guess.

Lemma 1.1 There are exactly $\frac{p-1}{2}$ quadratic residues $\mod p$.

Proof: Take a primitive element, $g$. The quadratic residues are exactly the even powers of $g$.
Proof 2: $(-a)^2=a^2 \mod p$, so there are at most $\frac{p-1}{2}$ quadratic residues. $x^2 \equiv y^2 \mod p$ implies that $x \equiv \pm y \mod p$ (integral domain), so there are at least $\frac{p-1}{2}$ quadratic residues. $\square$

Theorem 1.2 (Euler's criterion) $a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right) \mod p$.

Proof: We will combine both proofs of the above lemma. We can assume $a$ coprime to $p$, as otherwise the claim is obvious (both sides are $0$).
First, note that $a^{p-1}\equiv 1 \mod p$ by Fermat's little theorem. Since we are working in an integral domain, $a^{\frac{p-1}{2}} \equiv \pm 1 \mod p$.
Let $g$ be a primitive element $\mod p$. Then $a=g^i$ for some $i$. If $i=2j$, then $a^{\frac{p-1}{2}}\equiv g^{(p-1)j} \equiv 1 \mod p$. Similarly, if $i$ is odd, then $a^{\frac{p-1}{2}} \equiv -1 \mod p$. Thus we have established that:
$$a^{\frac{p-1}{2}} = \left\{\begin{array}{ll} +1 & \text{if } a \text{ is an even power of } g \\ -1 & \text{if } a \text{ is an odd power of } g \end{array}\right.$$
From proof 1 above, this corresponds exactly to the value of the Legendre symbol $\left(\frac{a}{p}\right)$. $\square$

Proposition 1.3 (Gauss's lemma)

We introduce least absolute value notation for a residue class mod $p$: write $\langle a \rangle$ for the unique integer congruent to $a \mod p$ lying in $[-p/2,p/2]$.

If $p$ is an odd prime, and $a$ is coprime to $p$, then $\left(\frac{a}{p}\right) = (-1)^\gamma$, where $\gamma = \#\{k \in \{1,2,\ldots,\frac{p-1}{2}\} \mid \langle ka \rangle < 0 \}$.

Proof: Observe that $\langle a \rangle, \langle 2a \rangle, \ldots, \langle \frac{p-1}{2}a\rangle$ are $\pm 1, \pm 2, \ldots, \pm \frac{p-1}{2}$ in some order, for some (fixed) choices of sign.

Hence, $(\frac{p-1}{2})!a^{\frac{p-1}{2}} \equiv \langle a \rangle \langle 2a \rangle \dots \langle (\frac{p-1}{2})a \rangle \equiv (-1)^\gamma (\frac{p-1}{2})! \mod p$.

By cancelling, $a^{\frac{p-1}{2}} \equiv (-1)^\gamma \mod p$. By Euler's criterion, $\left(\frac{a}{p}\right) \equiv (-1)^\gamma \mod p$. Since $(-1)^\gamma$ and $\left(\frac{a}{p}\right)$ are in $\{-1,1\}$, congruence implies equality. $\square$

Theorem 1.4 (Quadratic reciprocity)

Let $p$ and $q$ be odd primes. Then $\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}\left(\frac{p}{q}\right)$.

If we assume $p$ and $q$ to be distinct, we can reformulate as $\left(\frac{q}{p}\right)\left(\frac{p}{q}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}$.

Proof: To prove quadratic reciprocity, we use Gauss's lemma to rephrase the above assertion as the geometric problem of counting lattice points (points with integer coefficients in the plane) within specific regions of interest.

By the lemma, $\left(\frac{q}{p}\right)=(-1)^\gamma$, where $\gamma$ is as defined above.
We need to count how many of $\langle q \rangle, \langle 2q \rangle, \ldots, \langle \frac{p-1}{2} q \rangle$ are negative. (Note: we are working mod $p$.)

Observe that setting $\langle kq \rangle = kq - lp$ determines $l$ uniquely.
Thus, $\gamma$ corresponds to the number of lattice points $(k,l)$ within the region $-\frac{p}{2} < kq - lp < 0$. [more justification required]

Analagously, writing $\left(\frac{p}{q}\right)=(-1)^\beta$, Gauss's lemma says that $\beta$ corresponds to the number of lattice points $(k,l)$ within the region $-\frac{q}{2}< lp-kq < 0$.

Drawing the three (parallel) lines $kq-lp=-\frac{p}{2}$, $kq-lp=0$, and $kq-lp=\frac{q}{2}$ splits up the rectangle $0<k<p/2$, $0<l<q/2$ into four regions. From top left to bottom right, let's call them $A$ (a triangle), $B$ and $C$ (rhombuses), and $D$ (a triangle).

The total number of lattice points in the rectangle is $\frac{p-1}{2}\frac{q-1}{2}$ (recall that we are using strict inequality, so excluding those that fall on the axes). To prove quadratic reciprocity, we need the number of lattice points in $B$ and $C$ combined to have the same parity as $\frac{p-1}{2}\frac{q-1}{2}$.

We need two observations to see that this is true.

1. There is a bijection between $A$ and $D$. 
2. None of the lattice points are on any of the three lines that we drew. The lecturer totally failed to discuss this point, but it is crucial - given that we are considering strict inequality, if a lattice point was on one of the lines it wouldn't be counted in any of the regions (and if we were considering non-strict inequality, it would be counted twice). Luckily, this can't happen as $p$ and $q$ are prime. 

Combining these two observations means that $|B|+|C|+2|A| = \frac{p-1}{2}\frac{q-1}{2}$, and so $|B| + |C|$ and $\frac{p-1}{2}\frac{q-1}{2}$ have the same parity. From Gauss's lemma, above, we showed that $\left(\frac{q}{p}\right)\left(\frac{p}{q}\right) = (-1)^\gamma(-1)^\beta=(-1)^{|B|+|C|}$, and the statement of quadratic reciprocity is $\left(\frac{q}{p}\right)\left(\frac{p}{q}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}$, so we are done.

Let's prove 2 first. Suppose a point $(k,l)$ is on the line $kq-lp=0$, and that $k$ is an integer. Then $l=k\frac{q}{p}$, so $l$ isn't an integer. Similarly, if $k$ is an integer, then $l=k\frac{q}{p}+\frac{1}{2}$ isn't, and neither is $l=\frac{q}{p}(k-\frac{1}{2})$. Phew.

For 1, the required bijection is given by $(k,l) \leftrightarrow \left(\frac{p+1}{2}-k, \frac{q+1}{2}-l\right)$ (the same formula works both ways, from $A$ to $D$ and from $D$ to $A$). Visually, you pick up the bottom right triangle, rotate it 180 degrees, and slap it back onto the top right triangle. It doesn't fit together exactly, but instead overlaps egregiously, so it's really quite remarkable that this works. The lecturer left it as an exercice to prove that this bijection indeed does the job (I'm getting the impression that this proof is unlikely to come up in the exam).

The map is clearly injective from the above observation that the formula is self-inverse, i.e. applying it twice recovers the same point. So we only need to check that this map is well-defined, i.e. maps $C$ into $D$, and is surjective. Well-definedness is easy to obtain from definition-chasing. There is no extra work in obtaining surjectivity - it follows from well-definedness in the other direction. So we are done. $\square$

Number Theory - The structure of multiplicative groups of integers

This post aims to establish the basics about multiplicative groups as clearly and as efficiently as possible. I will include the proofs given in lectures to start off with, but I plan to trawl around for better alternatives.

0. Elementary stuff you should know how to prove by now

• Division algorithm for integers/polynomials in an integral domain
• Bezout
• Existence and uniqueness of prime factorisation

1. For $p$ prime, $\left(\mathbb{Z}/p\mathbb{Z}\right)^\times$ is cyclic

In other words, there always exists a primitive element $\mod p$ for $p$ prime. This theorem is very well-known, and feels trivial. It's not - there is a lot of groundwork that simply can't be avoided.

Intermediate results:

1.1 Lagrange's theorem for polynomials

In an integral domain, a polynomial of degree $d$ can have at most $d$ roots.

Proof: 
We induct on the degree of the polynomial.
For $n=1$, write $p(x)=ax+b$, $a \neq 0$.
Suppose there are two distinct solutions, $x$ and $y$. Then, by subtracting, $a(x-y)=0$. In an integral domain, this implies $x=y$.

For the inductive step, the division algorithm for polynomials (which is valid in an integral domain) implies that for any root $x_0$ of a polynomial $p$, $p$ can be factored as $(x-x_0)g(x)$. In an integral domain, the degree of a product of polynomials is the sum of the degrees of the factors. Thus, $p$ has at most one more root than $g$, and so at most $n$ roots in total, by the induction hypothesis. $\square$

1.2 For $p$ prime, $F = \mathbb{Z}/p\mathbb{Z}$ is a field

Proof:
Pick any non-zero element $a$. We need to find an inverse for $a$.
Define a map $\phi_a : F \to F$ by $\phi_a(z)=az$. This is an injection, as $F$ is an integral domain (immediate from the definition of a prime number). An injection from a finite set to itself must necessarily be a surjection. Thus, $ab=1$ for some $b \in F$, proving that $a$ has a multiplicative inverse. $\square$

1.3 The Euler totient function $\phi$ is multiplicative

Note: $\phi$ is not totally multiplicative. E.g. $\phi(2)=1$, $\phi(4)=2$.
We define $\phi(n)$ as the number of positive integers less than $n$ that are coprime to $n$, and observe that Bezout implies that $\phi(n)= \left| (\mathbb{Z}/n\mathbb{Z})^\times \right|$.


Proof:
The Chinese Remainder Theorem gives a bijection (more precisely, an isomorphism) between $\left(\mathbb{Z}/m_1m_2\mathbb{Z}\right)^\times$ and $\left(\mathbb{Z}/m_1\mathbb{Z}\right)^\times\times\left(\mathbb{Z}/m_2\mathbb{Z}\right)^\times$ whenever $m_1$ and $m_2$ are coprime, giving $\phi(m_1m_2)=\phi(m_1)\phi(m_2)$. $\square$

1.4 The Eulier totient function has the property: $\displaystyle \sum_{d \mid n} \phi(d) = n$.

Proof:
We establish the fact that for any multiplicative function $\varphi$, $F(n) = \displaystyle \sum_{d \mid n} \varphi(d)$ is also multiplicative.¹
Let $m$ and $n$ be coprime. Then:
$$F(mn)=\displaystyle \sum_{d \mid m_1} \varphi(d) = \sum_{d_1 \mid m, d_2 \mid n} \varphi(d_1d_2)$$$$ = \sum_{d_1 \mid m, d_2 \mid n} \varphi(d_1)\varphi(d_2) = \left(\sum_{d_1 \mid m} \varphi(d_1)\right)\left(\sum_{d_2 \mid n} \varphi(d_2)\right)$$$$=F(m)F(n)$$
Observe that $\phi(p^k)=p^{k-1}(p-1)$, so $F_\phi(p^k)=1 + (p-1) + \dots + (p^k-p^{k-1}) = p^k$. Thus, $F_\phi(n)=F_\phi(p_1^{n_1}\dots p_k^{n_k})=p_1^{n_1}\dots p_k^{n_k}=n$. $\square$

Proof of 1.

For each divisor $d$ of $p-1$, we show that if there is an element of order $d$, there must in fact be (exactly) $\phi(d)$ elements of order $d$. Thus, if $S_d$ is the set of elements of order $d$, then $|S_d|=\phi(d)$, or $|S_d|=0$. Since $\displaystyle \sum_{d \mid p-1} (\phi(d) - |S_d|) = p-1 - (p-1) = 0$, it follows that $|S_d|=\phi(d)$ for each $d$ dividing $p-1$ (if any of the $|S_d|$ are empty, the above formula can't hold), and so in particular $S_{p-1}$ is non-empty.

Let $a$ be an element of order $d$. By Lagrange's theorem $x^{d} \equiv 1 \mod p$ has at most $d$ solutions. Any element of order $d$ is a solution to this equation. But we can list $d$ distinct solutions: $1,a,a^2,\ldots,a^{d-1}$. Observe that $a^k$ has order $d$ exactly when $(d,k)=1$. Thus, there are exactly $\phi(d)$ elements of order $d$. $\square$

We call the elements of order $p-1$ the primitive roots $\mod p$. From the above, there are $\phi(p-1)$ of them. 

2. For $p$ an odd prime, $\left(\mathbb{Z}/p^k\mathbb{Z})\right)^\times$ is cyclic for any $k$.

We prove this by exhibiting an element of order $p^{k-1}(p-1)$. 
Let $g_1$ be a primitive element of  $\left(\mathbb{Z}/p\mathbb{Z})\right)^\times$.
Compute $g_1^{p-1}-1 \mod p^2$. If it's zero, set $g=g_1+p$. If it's non-zero, set $g=g_1$.
Then $g$ generates $\left(\mathbb{Z}/p^k\mathbb{Z})\right)^\times$.

We have chosen $g$ such that $g^{p-1}=1+bp$, where $b$ is coprime to $p$.
Thus, $g^{p^{k-1}(p-1)}=(1+bp)^{p^{k-1}}=1+bp{p^{k-1} \choose 1}+ \dots \equiv 1 \mod p^{k}$. So the order of $g$ (mod $p^k$) divides $p^{k-1}(p-1)$, and doesn't divide $p-1$.
Noting that $g^{p^{k-2}(p-1)}=(1+bp)^{p^{k-2}}=1+bp{p^{k-2} \choose 1} + (bp)^2{p^{k-2} \choose 2} + \dots \not\equiv 1 \mod p^{k}$, we can conclude that $g$ has order exactly $p^{k-1}(p-1)$, and so $\left(\mathbb{Z}/p^k\mathbb{Z})\right)^\times$ is cyclic. $\square$

3. Reserved space for other relevant results/properties proved on example sheets

---

1 Note to self: it feels like there is something more to be said here. Link to lattices?

Graph Theory - Trees

This post is second in a series of compendium-style posts, intended as an encyclopaedic collection all of the useful properties of a certain class of objects relevant to one of my courses (in this case, graph theory). I realise that this posts are slightly unappealing to read, but they constitute excellent revision.

Today, I'm interested in trees.

Definition. The following give equivalent conditions for a graph $G$ to be a tree:

1. $G$ is connected and acyclic.
2. $G$ is minimally connected.
3. $G$ is maximally acyclic. 
4. $G$ is connected with $e(G)=n-1$.
5. $G$ is acyclic with $e(G)=n-1$.

At first, we start with the first definition. Equivalence of 1,2 and 3 are established via follow-your-nose contradiction arguments. Equivalence of 1, 4 and 5 will come later.

A (finite) graph is connected $\Leftrightarrow$ it contains a spanning tree.

A minimally connected subgraph of $G$ gives a spanning tree. Conversely, a spanning tree is obviously connected, and the supergraph of a connected graph is connected.

Every tree $T$ with $|T|\geq 2$ has at least two leaves.

A leaf is a vertex with exactly one neighbour.

Pick a vertex $x_1$. Consider a maximal path from $x_1$, say $x_1x_2\ldots x_k$. Let $y$ be a neighbour of $x_k$, $y \neq x_{k-1}$. If $y$ is in the path, we have found a cycle. If $y$ is not in the path, we can extend the path to $x_1x_2\ldots x_k y$, contradicting maximality. So $x_k$ is a leaf. 

Now, repeat this argument, starting from $x_k$, to find a second leaf. 

A tree $T$ of order $n$ has size $n-1$. 

We induct on $n$. The base cases $n=1,2$ are clear. Pick a leaf $v$. Then $T-v$ is connected, acyclic, hence a tree, and so $e(T-v)=n-2$ by the induction hypothesis. 

We can use this to prove equivalence of definitions 1,4 and 5, above. 

(Cayley's theorem) There are $n^{n-2}$ labelled trees of order $n$.

We construct a bijection between labelled trees and strings of length $n-2$ over an alphabet of $n$ letters. (The sequence corresponding to a tree is called its Prufer sequence.)

(Algorithm for tree $\rightarrow$ string)

• Select the lowest labelled leaf, record its neighbour, remove it. 
• Repeat previous step until exactly one edge is left, and stop.

This produces a string of length $n-2$ with values in $\{1,\ldots,n\}$.

(Algorithm for string $\rightarrow$ tree)

• Set all vertices to "unused". 
• Select the smallest "unused" vertex that does not appear in the string, mark it "used", and join it to the vertex labelled with the next value in the string. Delete this vertex from the string.
• Repeat previous step until the string ends.
• Finish off by connecting the last two unused vertices.

None of the steps produces a cycle (when we mark a vertex used, none of the branches "behind" it are ever touched again), and we create $n-1$ edges. Thus, by definition 5 above, we have a tree. 

$(4,4,4,4)$	$(4,6,4,5)$

Sanity check: note that each node appears in the sequence $d(v)-1$ times, where $d(v)$ is its degree.

These processes are inverse to each other, and so we have a bijection. There are $n^{n-2}$ possible strings, and so there are equally many possible labelled graphs. $\square$

Things to think about: Can we obtain a description of the number of isomorphism classes (unlabelled graphs) by thinking about the size of the orbit of $(a_1,a_2,\ldots,a_{n-2})$ under the action of $S_{n-2}$ on the set of Prufer sequences given by $(\sigma(a_1),\sigma(a_2),\ldots,\sigma(a_{n-2}))$, for $\sigma \in S_{n-2}$, or is it more complex than that?

Existence of spanning tree $\Leftrightarrow$ Zorn's lemma
Extracurricular result

Assuming Zorn's lemma, every (connected) graph has a spanning tree: consider the set of all subgraphs that are trees, ordered by inclusion. This is obviously chain-complete (the acyclic definition survives unions of chains), and a maximal element corresponds to a spanning tree.

[Proof of the converse omitted currently, as I want to try to come up with a proof myself at some point.]

Graph Theory - Planar graphs

Graph theory is first and foremost about combinatorics, and so graphs certainly could be thought of as abstract objects in their own right, much like groups, or vector spaces. However, their interpretation in terms of ("physical") vertices and edges is highly suggestive, and often provides us with motivation and/or a foothold for an intuitive understanding of the underlying objects.

One (combinatorial) property of graphs that would be almost impossible to dream up without this visualisation is planarity. (A graph is said to be planar if it can be embedded in the Euclidean plane without any of its edges crossing. Thus, in some sense, any planar graph corresponds to a polygonisation of the plane.¹) We can push this topologically motivated program further by defining other flavours of planarity, embedding graphs on various topological surfaces, such as the torus, or the Klein bottle. It's fascinating to take a moment to observe that, in doing so, we are forging a link between topology and combinatorics, two wildly different fields of study. The link closely involves the Euler characteristic of the surface, as we will show in a moment, and raises the question: is the Euler characteristic a topological constant, or a combinatorial one?

This post will contain a collection of results and comments concerning planar graphs. I intend to update it as I work through my notes.

Note that we need at least 3 vertices for planar graphs to become non-trivial.

A maximal planar graph corresponds to a triangulation.

This is a crucial observation. If you have any face of size (number of edges) greater than 4, you can draw in a diagonal to obtain a new graph $G^\prime$ containing $G$. Furthermore, a maximal planar graph is bridgeless, and connected. You can extend any finite planar graph to a maximal planar graph.

There are actually only two non-planar graphs (in the plane).

Every time that a graph fails to be planar, the problem can be traced back to one of two generic cases. There are only two geometric "obstacles" to planarity!


It's fairly obvious that any graph containing a non-planar subgraph can't be planar. We need to extend this concept slightly to "subdivisions". We obtain a subdivision of a graph by replacing one edge with a path of edges spanning several vertices. It's easy to see that any graph containing a subdivision of a non-planar graph can't be planar.

Two simple non-planar graphs are shown above: $K_{3,3}$ and $K_5$. From the above observations, it's immediate that any graph containing a subdivision of $K_{3,3}$ or $K_5$ is necessarily non-planar. The amazing fact is that the converse is also true, by Kuratowski's theorem: $G$ is non-planar $\Leftrightarrow$ $G$ contains a subdivision of $K_5$ or $K_{3,3}$. The proof of Kuratowski's theorem is not included in the course.

Note: To see that $K_5$, and $K_{3,3}$ are indeed non-planar, you can check that they both violate the bound on the edges in terms of the girth given below. You can also argue constructively by drawing them in a methodic fashion.

Euler's formula.

Let $G$ be a connected planar graph with $n$ vertices, $m$ edges, and $f$ faces. Consider any surface of Euler characteristic $E$. Then the following formula holds:

$$n-m+f=E$$

We give a proof for the case $E=2$, corresponding to the Euclidean plane.
Proof: We induct on $m$, for fixed $n$.
$G$ is connected, so contains a spanning tree, which has $n-1$ edges, so $m \geq n-1$.

• If $m=n-1$, then $G$ is equal to its spanning tree, so there is only one face (a tree is acyclic). Thus $n-m+f=n-(n-1)+1=2$, as required.
• If $m>n-1$, then $G$ must contain a cycle. Pick an edge $e$ of any cycle. Then $e$ separates two distinct faces. Also, $G-e$ clearly remains connected. By the induction hypothesis applied to $G-e$, $n-(m-1)+(f-1)=2$, which directly implies the required result for $G$. $\square$

Note: Euler's formula proves that the number of faces of a planar graph is independent of the way that you choose to realise its embedding in the plane (the sizes of the different faces are not!)

There are strong restrictions on the number of edges a planar graph can have.

Let $G$ be a planar graph with $n\geq 3$ vertices, and $m$ edges. Then $m \leq 3n - 6$. This is easy to prove, as when $G$ is a triangulation $2m=3f$, and the result with equality pops right out of Euler's formula (and every planar graph can be extended to a triangulation simply by adding edges).

We can be more precise by obtaining bounds on the number of edges in terms of the girth $g$ (length of the shortest cycle in the graph). Assume G is connected. If G is acyclic (a tree) the number of edges is less than the number of vertices, so assume the graph has a cycle, so that the girth $g\geq3$ is defined. Observe that $2m = \sum i f_i$, where $f_i$ is the number of faces bordered by $i$ edges. (If some face borders both sides of the same edge, we should count that edge twice.) This gives: $2m = \sum i f_i \geq gf$, allowing us to conclude that $m \leq \displaystyle \frac{g}{g-2}(n-2)$ from Euler's formula. Note that substituting $g=3$ recovers the special case obtained above by considering triangulations.

This is a remarkably strong restriction, as in general a graph can have up to $n \choose 2$ $\sim n^2$ edges. So, in some sense, most graphs contain a substructure isomorphic to either $K_{3,3}$ or $K_5$. Maybe we can conceptually draw a link to Ramsey theory here?

There is one more piece of information left to squeeze out of the above, but at this point it's hardly surprising. The minimum degree $\delta(G)$ of a graph is closely linked to the number of edges, so we can easily obtain a (strong) upper bound as a corollary. If $\delta(G) \geq 6$, then $2m \geq 6n$ by the handshaking lemma, contradicting $m \leq3n - 6$ (recall $n\geq 3$). We conclude that planar graphs must satisfy $\delta(G)\leq 5$.

---

1 This may get tricky for infinite/uncountable graphs. Something interesting to think about! See my relevant stackexchange post, which has generated a decent amount of interest.

Linear Analysis - Riesz's lemma

In Linear Analysis, during the chapter discussing finite-dimensional normed spaces, we proved Riesz's lemma:

Let $Y$ be a proper, closed subspace of a normed space $X$. Then $\forall \varepsilon > 0$, $\exists x \in X$, $\|x\|=1$, such that $d(x,Y) > 1 - \varepsilon$.

I find the proof very interesting.

In school, we learn Pythagorus' theorem in all of its (potentially tautological) majesty. From that moment onwards, the name Pythagorus is endowed with a reverent, mystical quality that we revere because as small, impressionable children we were taught to. In France, there's another name that is given equal attention that as far as I know is less widespread in the UK - Thales (of Miletus). Apparently, he used the properties of similar triangles to calculate the height of the pyramids (although I've also heard said that this is another instance of misplaced mathematical credit, and he had nothing to do with the pyramids). Anyway, besides Pythagorus, we are patiently force-fed the théorème de Thalès, i.e. that the ratios of the sides of similar triangles are equal (image courtesy of Wiki)

Going through the proof of Riesz's theorem, it strikes me as very similar to this basic theorem of Euclidean geometry.

Proof of Riesz's lemma:

• We assumed $Y$ proper, so pick $z \in X\backslash Y$. 
• We assumed $Y$ closed, so $d(z,Y)=\inf\{\|x-y\| \mid y \in Y\} > 0$. By definition of infimum, we can pick $y \in Y$ such that $d(z, y)(1 - \varepsilon) < d(z,Y)$.
• Set $x = \displaystyle \frac{z-y}{\|z-y\|}$. Thus $\|x\|=1$. This is the point that we are looking for.
• Write $\lambda =\displaystyle \frac{1}{\|z-y\|}$ for clarity. $d(x,Y)=d(\lambda (z-y), Y) = \inf\{ \| \lambda (z - y) - y^\prime\| \mid y^\prime \in Y\}$. 
• Using the fact that subspaces are closed under scalar multiplication, $d(x,Y) = \inf \{\lambda \| (z-y) - y^\prime \| \mid y^\prime \in Y \}$.
• Using the fact that subspaces are closed under vector addition, $d(x,Y) = \inf\{\lambda\| z - y^\prime \| \mid y^\prime \in Y\}$.
• We conclude that $d(x,Y)=\lambda d(z,Y) > 1 - \varepsilon$, by choice of $y$. $\square$

(Perceived) link with similar triangles

I'm interested in one specific step of the proof: the assertion that for $Y$ a closed vector subspace, $d(\lambda x, Y) = \lambda d(x,Y)$, for $\lambda \in \mathbb{R}$.

 

Look familiar? The above argument with the infimum holds for any subspace. But how analagous is it really? There are a few traps for our intuition here. We haven't assumed that $X$ is a Hilbert space, so we can't assume that the shortest distance from $x$ to $Y$ is along a perpendicular line. That's fine - similar triangles don't have to be right-angled. More subtly, for the shortest distance to be along a line, we're assuming that lines are geodesics in normed spaces. Apparently, they are, but apparently there can be other geodesics too. 

I was sort of hoping we might be able to argue that the similar triangles property holds in this case without using the analytic definition of $d(x,Y)$, but the potential non-uniqueness of geodesics messes that up. There are other complications - recall that there may be multiple closest points in $Y$, since $X$ is not a Hilbert space, and we don't yet have any reason to believe that the closest points to $x$ and $\lambda x$ respectively are colinear in $Y$. Thus it seems that studying this question is out of my reach at the moment (my knowledge of geometry and geodesics is currently rather sketchy).

Normed spaces are sort of paradoxical - it feels to us like they have an extremely nice, rigid structure, yet things can apparently fail in mysterious ways. I certainly catch myself thinking of them intuitively as if they necessarily admitted an inner product (and thus had an orthonormal basis). This section is unfortunately rather inconclusive. 

Important corollary of Riesz's lemma

The unit ball of any infinite dimensional normed space is not compact.

Related problem: Example sheet 1Q12

Show that in the unit ball of every infinite-dimensional normed space, there is a sequence $(x_n)$ with $\|x_n - x_m \| \geq 1$, $\forall n \neq m$. Can $\geq$ be replaced with $>$?

In finite dimensions the unit ball is compact. If Riesz's lemma works for any $\varepsilon > 0$, then it has to work for $\varepsilon = 0$ by compactness. This approach might have been very interesting in infinite-dimensional normed spaces with compact unit balls. However, Riesz's lemma shoots itself in the foot by preventing any such objects from existing. Damn.

 Can $\geq$ be replaced with $>$?

Yes. Our supervisor came up with a proof that doesn't use Hahn-Banach. [more details to come]

Hi. Welcome to my blog. The idea behind this is some sort of revision diary. Of course, ideas mature and morph over time. I'm interested to see how this turns out.

I'm currently doing Part II of the Maths Tripos at Cambridge. It's hard - but I think I'm making it harder than it needs to be. I've been approaching things from the wrong perspective so far, working in the wrong way. The Cambridge Tripos is about Maths. In order to be successful, all you need to do it be legitimately interested in Maths. Not even passionate - just interested, and actively curious. You need to get your hands on things, feel them out, mould them with your own hands. Read things, talk with people, exchange ideas. Get things wrong. Being a genius is not necessary (although I'm told it helps).

I have this half-baked theory that the best way to learn Mathematics is through communication. I guess we'll find out.