Polynomial Pairing Functions

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.

  • Cantor’s function q
  • The switched version of q

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.

2 thoughts on “Polynomial Pairing Functions”

Leave a comment