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 can we divide the cake into 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 , and Monsky shows that these are the only for which it is furthermorepossible. You should definitely go read his proof – the crux of the argument relies on colouring the points in 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!) -adic valuations on . 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 . And I felt like sharing a proof of the following well known theorem of Ostrowski:
Theorem 1 Every non-trivial valuation on is equivalent to either the standard valuation or one of the -adic valuations .
This is pretty cool, and I think it provides some motivation as to why we should care about -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 is a map satisfying:
A valuation is non-archimedian if it satisfies the ultrametric inequality:
We also say that two valuations and are equivalent if there exists some such that , or the valuations generate the same topology on the underlying field.
The standard valuation on is given by the Euclidean norm. This valuation is obviously archimedian. On the other hand, for any prime , we can construct a non-archimedian valuation on as follows:
Any rational can be written in the form , where . We define the -adic valuation of as . 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 . 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 is a non-trivial valuation on . Then for any , we have:
Proof: Note that for some integers and . We also note that , and . Hence:
We can now apply the tensor power trick. Replace with for some integer and take roots of both sides:
Taking the limit as concludes the proof.
Another useful lemma we will need is the following characterisation of non-archimedian valuations over :
Lemma 4 is a non-archimedian valuation on if and only if for all .
Proof: The forwards direction is trivial, so suppose for all . Now consider some . By the binomial theorem, we have:
Taking roots of both sides (the tensor power trick again!) concludes the proof.
We are now in a position to prove the archimedian side of the proof directly:
Theorem 5 If is a non-trivial archimedian valuation on , then is equivalent to .
Proof: First of all, we note that for all , as if this was not the case we would have for some . By lemma 3, this would imply that for all , contradicting the assumption that is archimedian. Consider some . By lemma 3, we have:
Hence . Note that this expression does not depend on the choice of or , thus there exists a constant such that for all . But then for all such , and we are done.
Finally, a cute algebraic proof wraps up the non-archimedian part of Ostrowski’s theorem.
Theorem 6 If is a non-trivial non-archimedian valuation on , then is equivalent to for some prime .
Proof: Consider the set . This set is non-empty as the valuation is non-trivial. We also know by lemma 4 that for all and so is an ideal; in particular, it is a prime ideal. Thus for some prime . Consider some rational , where . Then we have: