A metric on $\mathbb{N}$

Question

Define a metric on $\mathbb{N}$ by fixing a prime, $p$, and setting $$d(x,y)=\begin{cases} 0 & x=y \\ p^{-k} & \text{otherwise} \end{cases}$$ where $p^k$ is the highest power of $p$ that divides $|x-y|$.

There were a couple easy parts like showing that this is a metric space and finding a sequence which converges to zero, but these last two have me stumped.

(i) Prove or disprove: The space $(\mathbb{N},d)$ is compact. I feel like I need to understand what open sets in this topology will look like first, so I tried to work out how open balls behave. $B(x,2)=\mathbb{N}$ as this contains all numbers since the difference can have $1$ as its largest power of $p$ which divides it, and $2$ is chosen arbitrarily since it is greater than 1. From here I start to get more confused it seems like $B(x,p^{-k})$ is the set of integers of the form $n\equiv x\mod{p^{k+1}}$, but I'm not really sure how to prove this. From here I'm not even sure how to go about making an argument about open covers so if anyone can guide me in the right direction that would be appreciated.

(ii) Prove or disprove: If $p=3$, then the set of prime numbers greater that $101$ is open in $(\mathbb{N})$. This seems very unlikely to me. I can pick an element in this set, $103$, then I don't think I can find an open ball containing $103$ that is a subset of theses primes. I'm basing this off my assumption that the open balls are of the form described above, but I'm not sure how to show this rigorously.

Any tips are greatly appreciated.

Answer 1

(i) Consider the sequence

$$1, 1+p, 1+p+p^2,\ldots, \sum_{i=0}^np^i,\ldots$$

which is clearly Cauchy, but does not converge to any natural number, $n\in\Bbb N$, so $\Bbb N$ is not complete, hence not compact.

---

Proof of non-convergence:

If $n\in\Bbb N$ represent $n$ as a finite sum of powers of $p$, which is possible to do constructively and is called a base $p$ representation of $n$. Then subtracting the finite sum from the infinite one, we see that only some finite power can divide the difference, namely $p^j$ where $j$ is the first non-zero element in the difference of the two sums. Hence the numbers are distance $p^j$ away from one another, and so--since this is positive--they are unequal since in a metric space the axioms include $d(x,y)=0\iff x=y$.

---

(ii) Let $q>101$ be a prime congruent to $a\mod 3^k$. Then we know that there are infinitely many natural numers $n\equiv a\mod 3^k$ (in particular $q+3^k$ is always even) which are not prime, so pick one such $n$ and then

$$n\in B(q,\epsilon)$$

for any $\epsilon >0$, where $k$ is defined as $k(\epsilon)$ such that $p^{-k}<\epsilon\le p^{1-k}$, so not only does each element does not have an open ball around itself wholly contained in the set, none of the primes do. In particular the set is not open.

Answer 2

This metric is called the $p$-adic metric, and has many applications in number theory and other areas of mathematics.

For some intuition: given any number $n \in \mathbb N$, we can write $n$ in base $p$ - i.e. $$n = \sum_{i=0}^Na_ip^i \ \ \ \ 0 \le a_i<p$$If $\displaystyle m = \sum_{n=0}^Nb_ip^i$, then $d(m,n)=p^{-j}$ where $j = \min\{i:a_i - b_i \ne 0\}$.

For example, for $p=3$, $33$ is $110$ in base $3$ and $27$ is $100$ in base $3$. So $d(33,27) = 3^{-1}$.

$B(x,p^{-k})$ is then the set of numbers whose base $p$ representation is the same as that of $x$ from the $k^\text{th}$ position onwards. This is another way of saying the two numbers are congruent modulo $p^k$.

---

(i) With this definition in mind, think about the sequence in base $p$$$1,11,111,1111,\dots$$This is the same sequence suggested by Adam Hughes, but in this notation, it is clearly Cauchy - as for any $\epsilon >0$, we can find $p^{-k}<\epsilon$ and after the $k$ terms, of the sequence, all subsequent terms will agree on the first $k$ digits.

Alternatively, you could consider the sequence $$p,\ p^2 ,\ p^3 , \ldots$$ which we can rewrite as $$1, 10, 100, 1000, \ldots$$ in base $p$. This sequence actually converges to $0$ if you were to extend this metric to $\mathbb Z$!! As such it certainly can't converge in $\mathbb N$, but will be Cauchy. (If you consider $0 \in \mathbb N$ then just subtract $1$ from every term in this sequence.)

(ii) Pick any prime $q$ not equal to $3$. Then $q \equiv \pm 1 \mod 3$ - so in base $3$ we must have $q = a_N\ldots a_1a_0$ where $a_0 \in \{1,2\}$.

Then for any $k$, $$n=q + 3^k$$ is even and hence certainly not prime.

But $n = 10000\ldots 00a_N\ldots a_0$ agrees with $q$ for the first $k$ digits, so we can find composite numbers arbitrarily close to $q$.