number-theory – Maths to Share

The fundamental theorem of arithmetic states that every natural number can be factorized uniquely as a product of prime numbers. The word “uniquely” here means unique up to rearranging. The theorem means that if you and I take the same number $n$ and I write $n = p_1p_2\ldots p_k$ and you write $n = q_1q_2\ldots q_l$ where each $p_i$ and $q_i$ is a prime number, then in fact $k=l$ and we wrote the same prime numbers (but maybe in a different order).

Most people happily accept this theorem as self evident and believe it without proof. Indeed some people take it to be so self evident they feel it doesn’t really deserve the name “theorem” – hence the title of this blog post. In this post I want to highlight two situations where an analogous theorem fails.

Situation One: The Even Numbers

Imagine a world where everything comes in twos. In this world nobody knows of the number one or indeed any odd number. Their counting numbers are the even numbers $\mathbb{E} = \{2,4,6,8,\ldots\}$ . People in this world can add numbers and multiply numbers just like we can. They can even talk about divisibility, for example $2$ divides $8$ since $8 = 4\cdot 2$ . Note that things are already getting a bit strange in this world. Since there is no number one, numbers in this world do not divide themselves.

Once people can talk about divisibility, they can talk about prime numbers. A number is prime in this world if it is not divisible by any other number. For example $2$ is prime but as we saw $8$ is not prime. Surprisingly the number $6$ is also prime in this world. This is because there are no two even numbers that multiply together to make $6$ .

If a number is not prime in this world, we can reduce it to a product of primes. This is because if $n$ is not prime, then there are two number $a$ and $b$ such that $n = ab$ . Since $a$ and $b$ are both smaller than $n$ , we can apply the same argument and recursively write $n$ as a product of primes.

Now we can ask whether or not the fundamental theorem of arthimetic holds in this world. Namely we want to know if their is a unique way to factorize each number in this world. To get an idea we can start with some small even numbers.

$2$ is prime.
$4 = 2 \cdot 2$ can be factorized uniquely.
$6$ is prime.
$8 = 2\cdot 2 \cdot 2$ can be factorized uniquely.
$10$ is prime.
$12 = 2 \cdot 6$ can be factorized uniquely.
$14$ is prime.
$16 = 2\cdot 2 \cdot 2 \cdot 2$ can be factorized uniquely.
$18$ is prime.
$20 = 2 \cdot 10$ can be factorized uniquely.

Thus it seems as though there might be some hope for this theorem. It at least holds for the first handful of numbers. Unfortunately we eventually get to $36$ and we have:

$36 = 2 \cdot 18$ and $36 = 6 \cdot 6$ .

Thus there are two distinct ways of writing $36$ as a product of primes in this world and thus the fundamental theorem of arithmetic does not hold.

Situtation Two: A Number Ring

While the first example is fun and interesting, it is somewhat artificial. We are unlikely to encounter a situation where we only have the even numbers. It is however common and natural for mathematicians to be lead into certain worlds called number rings. We will see one example here and see what an effect the fundamental theorem of arithmetic can have.

Consider wanting to solve the equation $x^2+19=y^3$ where $x$ and $y$ are both integers. One way to try to solve this is by rewriting the equation as $(x+\sqrt{-19})(x-\sqrt{-19}) = y^3$ . With this rewriting we have left the familiar world of the whole numbers and entered the number ring $\mathbb{Z}[\sqrt{-19}]$ .

In $\mathbb{Z}[\sqrt{-19}]$ all numbers have the form $a + b \sqrt{-19}$ , where $a$ and $b$ are integers. Addition of two such numbers is defined like so

$(a+b\sqrt{-19}) + (c + d \sqrt{-19}) = (a+c) + (b+d)\sqrt{-19}$ .

Multiplication is define by using the distributive law and the fact that $\sqrt{-19}^2 = -19$ . Thus

$(a+b\sqrt{-19})(c+d\sqrt{-19}) = (ac-19bd) + (ad+bc)\sqrt{-19}$ .

Since we have multiplication we can talk about when a number in $\mathbb{Z}[\sqrt{-19}]$ divides another and hence define primes in $\mathbb{Z}[\sqrt{-19}]$ . One can show that if $x^2 + 19 = y^3$ , then $x+\sqrt{-19}$ and $x-\sqrt{-19}$ are coprime in $\mathbb{Z}[\sqrt{-19}]$ (see the references at the end of this post).

This means that there are no primes in $\mathbb{Z}[\sqrt{-19}]$ that divides both $x+\sqrt{-19}$ and $x-\sqrt{-19}$ . If we assume that the fundamental theorem of arthimetic holds in $\mathbb{Z}[\sqrt{-19}]$ , then this implies that $x+\sqrt{-19}$ must itself be a cube. This is because $(x+\sqrt{-19})(x-\sqrt{-19})=y^3$ is a cube and if two coprime numbers multiply to be a cube, then both of those coprime numbers must be cubes.

Thus we can conclude that there are integers $a$ and $b$ such that $x+\sqrt{-19} = (a+b\sqrt{-19})^3$ . If we expand out this cube we can conclude that

$x+\sqrt{-19} = (a^3-57ab^2)+(3a^2b-19b^3)\sqrt{-19}$ .

Thus in particular we have $1=3a^2b-19b^3=(3a^2-19b^2)b$ . This implies that $b = \pm 1$ and $3a^2-19b^2=\pm 1$ . Hence $b^2=1$ and $3a^2-19 = \pm 1$ . Now if $3a^2 -19 =-1$ , then $a^2=6$ – a contradiction. Similarly if $3a^2-19=1$ , then $3a^2=20$ – another contradiction. Thus we can conclude there are no integer solutions to the equation $x^2+19=y^3$ !

Unfortunately however, a bit of searching reveals that $18^2+19=343=7^3$ . Thus simply assuming that that the ring $\mathbb{Z}[\sqrt{-19}]$ has unique factorization led us to incorrectly conclude that an equation had no solutions. The question of unique factorization in number rings such as $\mathbb{Z}[\sqrt{-19}]$ is a subtle and important one. Some of the flawed proofs of Fermat’s Last Theorem incorrectly assume that certain number rings have unique factorization – like we did above.

References

The lecturer David Smyth showed us that the even integers do not have unique factorization during a lecture of the great course MATH2222.

The example of $\mathbb{Z}[\sqrt{-19}]$ failing to have unique factorization and the consequences of this was shown in a lecture for a course on algebraic number theory by James Borger. In this class we followed the (freely available) textbook “Number Rings” by P. Stevenhagen. Problem 1.4 on page 8 is the example I used in this post. By viewing the textbook you can see a complete solution to the problem.

One of the great results of the 19th century German mathematician Georg Cantor is that the sets $\mathbb{N}$ and $\mathbb{N} \times \mathbb{N}$ have the same cardinality. That is the set of all non-negative integers $\mathbb{N} = \{0,1,2,3,\ldots\}$ has the same size as the set of all pairs on non-negative integers $\mathbb{N} \times \mathbb{N} = \{(m,n) \mid m,n \in \mathbb{N} \}$ , or put less precisely “infinity times infinity equals infinity”.

Proving this result amounts to finding a bijection $p : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ . We will call such a function a pairing function since it takes in two numbers and pairs them together to create a single number. An example of one such function is

$p(m,n) = 2^m(2n+1)-1$

This function is a bijection because every positive whole number can be written uniquely as the product of a power of two and an odd number. Such functions are of practical as well as theoretical interest. Computers use pairing functions to store matrices and higher dimensional arrays. The entries of the matrix are actually stored in a list. When the user gives two numbers corresponding to a matrix entry, the computer uses a pairing function to get just one number which gives the index of the corresponding entry in the list. Thus having efficiently computable pairing functions is of practical importance.

Representing Pairing Functions

Our previous example of a pairing function was given by a formula. Another way to define pairing functions is by first representing the set $\mathbb{N} \times \mathbb{N}$ as a grid with an infinite number of rows and columns like so:

We can then represent a pairing function as a path through this grid that passes through each square exactly once. Here are two examples:

The way to go from one of these paths to a function from $\mathbb{N} \times \mathbb{N}$ to $\mathbb{N}$ is as follows. Given as input a pair of integers $(m,n)$ , first find the dot that $(m,n)$ represents in the grid. Next count the number of backwards steps that need to be taken to get to the start of the path and then output this number.

We can also do the reverse of the above procedure. That is, given a pairing function $p : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ , we can represent $p$ as a path in the grid. This is done by starting at $p^{-1}(0)$ and joining $p^{-1}(n)$ to $p^{-1}(n+1)$ . It’s a fun exercise to work out what the path corresponding to $p(m,n) = 2^m(2n+1)-1$ looks like.

Cantor’s Pairing Function

The pairing function that Cantor used is not any of the ones we have seen so far. Cantor used a pairing function which we will call $q$ . When represented as a path, this is what $q$ looks like:

Surprisingly there’s a simple formula that represents this pairing function $q$ which we will now derive. First note that if we are at a point $(k,0)$ , then the value of $q(k,0)$ is $1+2+3+\ldots+(k-1)+k= \frac{1}{2}k(k+1)$ . This is because to get to $(k,0)$ from $(0,0) = q^{-1}(0)$ , we have to go along $k$ diagonals which each increase in length.

Now let $(m,n)$ be an arbitrary pair of integers and let $k = m+n$ . The above path first goes through $(k,0)$ and then takes $n$ steps to get to $(m,n)$ . Thus

$q(m,n)= q(k,0)+n=\frac{1}{2}k(k+1)+n=\frac{1}{2}(n+m)(n+m+1)+n$

And so Cantor’s pairing function is actually a quadratic polynomial in two variables!

Other Polynomial Pairing Functions?

Whenever we have a pairing function $p$ , we can switch the order of the inputs and get a new pairing function $\widetilde{p}$ . That is the function $\widetilde{p}$ is given by $\widetilde{p}(m,n)=p(n,m)$ . When thinking of pairing functions as paths in a grid, this transformation amounts to reflecting the picture along the diagonal $m = n$ .

Thus there are at least two quadratic pairing functions, Cantor’s function $q$ and its switched cousin $\widetilde{q}$ . The Fueter–Pólya theorem states these two are actually the only quadratic pairing functions! In fact it is conjectured that these two quadratics are the only polynomial pairing functions but this is still an open question.

Thank you to Wikipedia!

I first learnt that the sets $\mathbb{N}$ and $\mathbb{N} \times \mathbb{N}$ have the same cardinality in class a number of years ago. I only recently learnt about Cantor’s polynomial pairing function and the Fueter–Pólya theorem by stumbling across the Wikipedia page for pairing functions. Wikipedia is a great source for discovering new mathematics and for checking results. I use Wikipedia all the time. Many of these blog posts were initially inspired by Wikipedia entries.

Currently, Wikipedia is doing their annual fundraiser. If you are a frequent user of Wikipedia like me, I’d encourage you to join me in donating a couple of dollars to them: https://donate.wikimedia.org.

Category: number-theory

Why is the fundamental theorem of arithmetic a theorem?