Unusual metrics on the rationals

Suppose one day you get bored of the triangle inequality. You have done so much real analysis that you cannot see anything new and interesting in |a-b| \le |a-z| + |z+b| anymore. But you want to keep doing analysis.

What can we do about this? One solution may be making this inequality more strict, and see where it takes us. For example, you may consider the following: |a-b| \le \max{\{|a-z|,|z-b|\}}. Note that this inequality does not hold under our usual absolute value, for example: 5 = |8 - 3| \not \le \max{ \{ |8-4|, |4-3| \} } = \max{ \{4,1\} } = 4. But does this tweaking of the triangle inequality add anything new? It may not look like it at first, but it is a dream come true:  a sequence is Cauchy if and only if distance of consecutive terms goes to zero! More mathematically: the sequence (a_n)_{n \in \mathbb{N}} is Cauchy \iff |a_n-a_{n+1}| \to 0 as n \to \infty

This is not true in the case of our usual absolute value. For example, the infamous sequence H_n = \sum_{k = 1}^{n} \frac{1}{k} is not Cauchy in the reals \mathbb{R}, for if it were Cauchy, it would converge since the reals numbers are complete. However, the difference between consecutive terms is |1/n| which clearly tends to zero.

Before we dive into the proof of the previous claim, we need to note something: we are talking about convergence in \mathbb{Q} however this would work in any metric space (X,d) where the triangle inequality satisfies d(a,b) \le  \max{\{d(a,z), d(z,b) \}} for any a,b,z \in X. This is because an absolute value on \mathbb{Q} induces a metric by setting d(a,b) = |a-b|.

Theorem: Let | \cdot | be an absolute value on \mathbb{Q} satisfying |a+b| \le \max{ \{ |a|,|b|\} }. Then any sequence (a_n)_{n \in \mathbb{N}} of rational numbers is Cauchy if and only if |a_n-a_{n+1}| \to 0 as n \to \infty.

Proof: ( \implies) Let \epsilon > 0. Since (a_n)_{n \in \mathbb{N}} is Cauchy there exists N \in \mathbb{N} such that for all n,m > N we have |a_n - a_m| < \epsilon. In particular, whenever m = n+1, we obtain  |a_n - a_{n+1}| < \epsilon, which means that |a_n - a_{n+1}| \to 0 as n \to \infty.

( \impliedby ) Let \epsilon > 0. There exists N \in \mathbb{N} such that |a_n - a_{n+1}| < \epsilon for any n > N.
Then, for all m \ge n > N, applying our strict triangle inequality:

\begin{aligned} |a_n - a_m| &= |a_n - a_{n+1} + a_{n+1} - \dots + a_{m-1} -a_{m}| \\  &\le \max{\{|a_n - a_{n+1}|, \dots,  |a_{m-1} -a_{m}| \} } < \epsilon \end{aligned} .

Therefore the sequence is Cauchy.   \square

This is all well and good, however, it makes us wonder whether there is any absolute value on \mathbb{Q} with this strict triangle inequality property. The answer is yes, in fact, there are infinitely many of them, but this is the topic for another post. Until then, to satisfy your curiosity I will write down one such absolute value and I will leave it up to you to check that it is indeed an absolute value:

|x|_3 = \frac{1}{3^{v(x)}}
where v(x) = n is the exponent of 3 whenever we write the rational number as x = 3^n \frac{p}{q}, where p,q are coprime to 3.

Can you suggest a different absolute value?

Advertisements

Topological proof of infinitude of primes

Let’s begin with one of the oldest and most fundamental results in mathematics: there are infinitely many prime numbers. If you’re not aware of what primes are, I’m surprised to find you here. What you should know is that primes are natural numbers that like some pistachios, cannot be split up into smaller bits. Unlike those pistachios, though, we love prime numbers.

In the classic proof of Mr Euclid, we begin by assuming there are finitely many prime numbers, say p_1, p_2, \cdots , p_k for some positive integer k . Then we stick them all together to form the product N = \prod_{i=1}^{k} p_i. It doesn’t look very interesting, but if we consider the number N + 1 we can see that no prime p_i can divide it, for then p_i | 1 and that’s nonsense. Hence, we come to the sad conclusion that our original list of primes \{ p_1, p_2, \cdots , p_n \} must be incomplete. Therefore the number of primes is not bounded by any natural number, and so we must have infinitely many of primes! I’m sure this proof will not come to as a surprise to you, Mr Reader, but I hope the following proof of the same result will catch your fancy like it did to me the very first time I saw it.

This proof uses topology, which at first sight has nothing to do with integers and primes, but the fact that it works tells us how flexible topology can be. All you need to know is the very definition of a topology in terms of open sets, and maybe its alternative definition in terms of closed sets.  If you need a reminder, check here.

We begin by defining a topology on the set of integers \mathbb{Z}. Let N_{a,b} = \{ a + nb : n \in \mathbb{Z} \} for  a,b \in \mathbb{Z} with b > 0  and we will define an set U to be open if U = \emptyset or if for any a \in U  we can find b>0 such that N_{a,b} is contained in U.

This is indeed a topology. The empty set \emptyset and \mathbb{Z} are open. Arbitrary union of open sets is open: if U_{\alpha} is a collection of  open sets indexed by I, then for any a \in \cup_{\alpha \in I} U_{\alpha} we have a \in U_{\alpha} for some \alpha \in I and so there exist b>0 such that N_{a,b} \subseteq U_{\alpha} \subseteq \cup_{\alpha \in I} U_{\alpha}. Finite intersections of open sets  are open: if U,V are open, then for a \in U \cap V we can find b_1, b_2 > 0 such that N_{a,b_1} \subseteq U and N_{a,b_2} \subseteq V. Taking b to be the lowest common multiple of b_1 and b_2 we find N_{a,b} \subseteq U, N_{a,b} \subseteq V and so N_{a,b} must be contained in the intersection of U, V.

Now that we have checked that we have a topology, we can play a bit around with open and closed sets. First we note that N_{a,b} = \mathbb{Z} \setminus \bigcup_{n=1}^{b-1} N_{a+n,b}. Since  the N_{a+i,b} are open, and their finite union is open then N_{a,b} must be closed. Secondly, note that all non-empty open sets must be of infinite size since they contain an infinite set of the form N_{a,b}.

Finally we are ready for the coup de grâce. Every integer n with |n|>1 is divisible by some prime p and therefore we have the equality of sets \mathbb{Z} \setminus \{1,-1\} = \bigcup_{p_{prime}} N_{0,p}. Can you see the trick now? We are looking for a contradiction.

If there were finitely many primes, the set \mathbb{Z} \setminus \{1,-1\} would be closed since it is a finite union of closed sets, which is closed. But then its complement \{1,-1\} must be open, and this is a contradiction since every open set is infinite. Hence there must be infinitely many primes. QED.

This proof was first given by Furstenberg in 1955 when he was still and undergraduate. What a legend! It is substantiably different from the original proof by Euclid, and for this reason it deserves a special place in our list of mathematical farts.