### A Proof of Ostrowski’s Theorem

So this coming Friday I’ve been asked to be a backup speaker for the local maths club, in case our current speaker cancels (again). Since I like cake, and I like to be given a fairly sliced piece of cake, I decided to talk about Sperner’s lemma and it’s applications to fair division problems.

This stuff is very well known, and there’s a popular expository article about it here. So I won’t talk too much about that.

On the other hand, something I will talk about is a fantastic related problem with an equally fantastic solution. It goes something like this. Suppose you have a square cake; for which integers ${n}$ can we divide the cake into ${n}$ triangles of equal area?

This was first posed in the American Mathematical Monthly after (I assume) a heated debate during somebody’s birthday celebrations. It was eventually solved by a mathematician named Paul Monsky in 1970, with an astonishingly clever mix of combinatorics and valuation theory.

It’s quite easy to show that you can perform such a division for even ${n}$, and Monsky shows that these are the only ${n}$ for which it is furthermorepossible. You should definitely go read his proof – the crux of the argument relies on colouring the points in ${\mathbb{R}^2}$ with three colours, such that on any given line one finds exactly two of the colours. Monsky then uses Sperner’s lemma – and some very special properties of the colouring he constructs – to conclude.

None of this is too astonishing. What really surprised me, however, is that to construct such a colouring he uses (of all things!) ${p}$-adic valuations on ${\mathbb{R}}$. And while this might seem esoteric, in the half century since he published, nobody seems to have found a more elementary proof!

Another paper on similar colourings of projective planes also finds strong links to non-archimedian valuations, which leads me to believe that there is something very strange going on here! I haven’t read this later paper very closely, but I really should.

In any case, these things have gotten me thinking a lot about different kinds of norms on ${\mathbb{Q}}$. And I felt like sharing a proof of the following well known theorem of Ostrowski:

Theorem 1 Every non-trivial valuation on ${\mathbb{Q}}$ is equivalent to either the standard valuation ${|\cdot|_\infty}$ or one of the ${p}$-adic valuations ${|\cdot|_p}$.

This is pretty cool, and I think it provides some motivation as to why we should care about ${p}$-adic stuff at all. But first, let’s unpack things a little bit. First of all, what is a valuation?

Definition 2 A valuation on a field ${\mathbb{F}}$ is a map ${|\cdot| : \mathbb{F} \rightarrow \mathbb{R}}$ satisfying:

\displaystyle \begin{aligned} |x| &\geq 0 \\ |x| &= 0 \iff x = 0 \\ |xy| &= |x||y| \\ |x + y| &\leq |x| + |y| \end{aligned}

A valuation is non-archimedian if it satisfies the ultrametric inequality:

$\displaystyle |x + y| \leq \max(|x|, |y|)$

We also say that two valuations ${|\cdot|_1}$ and ${|\cdot|_2}$ are equivalent if there exists some ${c \in \mathbb{R}}$ such that ${|\cdot|_1 = |\cdot|_2^c}$, or the valuations generate the same topology on the underlying field.

The standard valuation ${|\cdot|_\infty}$ on ${\mathbb{Q}}$ is given by the Euclidean norm. This valuation is obviously archimedian. On the other hand, for any prime ${p}$, we can construct a non-archimedian valuation on ${\mathbb{Q}}$ as follows:

Any rational can be written in the form ${x = p^n\frac a b}$, where ${\gcd(ab, p) = 1}$. We define the ${p}$-adic valuation of ${x}$ as ${|x|_p = p^{-n}}$. It is not difficult to show that this is indeed a valuation, and that it is non-archimedian.

Ostrowski’s theorem asserts that these are essentially the only valuations we can find on ${\mathbb{Q}}$. We will split the proof into the archimedian and non-archimedian cases; curiously, despite the strange nature of non-archimedian valuations, this second case is actually markedly easier to show. But first, a lemma.

Lemma 3 Suppose ${|\cdot|}$ is a non-trivial valuation on ${\mathbb{Q}}$. Then for any ${m,n \in \mathbb{Z}}$, we have:

$\displaystyle |m| \leq \max(1, |n|)^{\log(m)/\log(n)}$

Proof: Note that ${m = a_0 + a_1n + \dots + a_rn^r}$ for some integers ${0 \leq a_i < n}$ and ${a_r \neq 0}$. We also note that ${|a_i| \leq a_i|1| < n}$, and ${r < \log(m)/\log(n)}$. Hence:

\displaystyle \begin{aligned} |m| &\leq |a_0| + |a_1n| + \dots + |a_rn^r| \\ &\leq n(r+1)\max(1, |n|)^r \\ &\leq n \left(1 + \frac{\log(m)}{\log(n)}\right) \max(1, |n|)^{\log(m)/\log(n)} \end{aligned}

We can now apply the tensor power trick. Replace ${m}$ with ${m^t}$ for some integer ${t}$ and take ${t^{th}}$ roots of both sides:

$\displaystyle |m| \leq n^{1/t} \left(1 + t\frac{\log(m)}{\log(n)}\right)^{1/t} \max(1, |n|)^{\log(m)/\log(n)}$

Taking the limit as ${t \rightarrow \infty}$ concludes the proof. $\Box$

Another useful lemma we will need is the following characterisation of non-archimedian valuations over ${\mathbb{Q}}$:

Lemma 4 ${|\cdot|}$ is a non-archimedian valuation on ${\mathbb{Q}}$ if and only if ${|n| \leq 1}$ for all ${n \in \mathbb{Z}}$.

Proof: The forwards direction is trivial, so suppose ${|n| \leq 1}$ for all ${n \in \mathbb{Z}}$. Now consider some ${x, y \in \mathbb{Q}}$. By the binomial theorem, we have:

\displaystyle \begin{aligned} |(x+y)|^n &= \left|\sum_i {n \choose i} x^i y^{n-i}\right| \\ &\leq \sum_i |x^iy^{n-i}| \\ &\leq (n+1)\max(|x|, |y|)^n \end{aligned}

Taking ${n^{\text{th}}}$ roots of both sides (the tensor power trick again!) concludes the proof. $\Box$

We are now in a position to prove the archimedian side of the proof directly:

Theorem 5 If ${|\cdot|}$ is a non-trivial archimedian valuation on ${\mathbb{Q}}$, then ${|\cdot|}$ is equivalent to ${|\cdot|_\infty}$.

Proof: First of all, we note that ${|n| \geq 1}$ for all ${n \in \mathbb{N}}$, as if this was not the case we would have ${|m| < 1}$ for some ${m}$. By lemma 3, this would imply that ${n \leq 1}$ for all ${n \in \mathbb{Z}}$, contradicting the assumption that ${|\cdot|}$ is archimedian. Consider some ${m, n \in \mathbb{Z}}$. By lemma 3, we have:

\displaystyle \begin{aligned} |m| &\leq \max(1, |n|)^{\log(m)/\log(n)} \\ &\leq |n|^{\log(m)/\log(n)} \end{aligned}

Hence ${|m|^{1/\log(m)} \leq |n|^{1/\log(n)}}$. Note that this expression does not depend on the choice of ${m}$ or ${n}$, thus there exists a constant ${c \in \mathbb{R}}$ such that ${|n|^{1/\log(n)} = c}$ for all ${n>1 \in \mathbb{Z}}$. But then ${|n| = | |n|_\infty | = c^{\log|n|_\infty} = |n|_\infty^{\log(c)}}$ for all such ${n}$, and we are done. $\Box$

Finally, a cute algebraic proof wraps up the non-archimedian part of Ostrowski’s theorem.

Theorem 6 If ${|\cdot|}$ is a non-trivial non-archimedian valuation on ${\mathbb{Q}}$, then ${|\cdot|}$ is equivalent to ${|\cdot|_p}$ for some prime ${p}$.

Proof: Consider the set ${\mathfrak{a} = \{ n \in \mathbb{Z} : |n| < 1 \}}$. This set is non-empty as the valuation is non-trivial. We also know by lemma 4 that ${|n| \leq 1}$ for all ${n \in \mathbb{Z}}$ and so ${\mathfrak{a}}$ is an ideal; in particular, it is a prime ideal. Thus ${\mathfrak{a} = p\mathbb{Z}}$ for some prime ${p}$. Consider some rational ${x = p^n\frac{a}{b}}$, where ${\gcd(p, ab) = 1}$. Then we have:

\displaystyle \begin{aligned} |x| &= |p^n|\cdot\left|\frac{b}{c}\right| = |p|^n \cdot |1| \\ &= e^{n\log|p|} \\ &= p^{-n \cdot (-\frac{\log|p|}{\log(p)})} \\ &= |x|_p^{-\frac{\log|p|}{\log(p)}} \end{aligned}

$\Box$