Home > Analysis, TeX/LaTeX > The Cantor Pairing Function

The Cantor Pairing Function

The objective of this post is to construct a pairing function, that presents us with a bijection between the set of natural numbers, and the lattice of points in the plane with non-negative integer coordinates.

\pi\colon \mathbb{N} \cup \{ 0 \} \to \big( \mathbb{N} \cup \{ 0 \} \big)^2.

We will accomplish this by creating the corresponding map (and its inverse), that takes each natural number z and drops it at a location in the lattice, as the following diagram suggests:

gCpf

That is: the zero goes at the origin, and then we populate the two positions in the diagonal x+y=1. Then we populate the three positions in the diagonal x+y=2, and so on. Note that by doing so, when we are done populating the last n+1 positions of the n–th diagonal, we have placed 1+2+3+\dotsb+(n+1) = \tfrac{(n+1)(n+2)}{2} natural numbers (including the zero!) in the lattice.

In particular, note that the triangular numbers t_n = 1 + 2 + \dotsb + n occupy all the positions in the x–axis, precisely where this one intersects the lines x+y=n.

This is the key ingredient to construct the required bijection: Given a natural number z \in \mathbb{N}, there is a unique value n = n(z) such that t_n \leq z < t_{n+1} (since the sequence of triangular numbers is strictly increasing). The number z then belongs to the intersection of the lattice with the diagonal line x+y=n, and it only remains to know how far from the x–axis: the offset z-t_n actually indicates the y coordinate of the position of z in the lattice. We can now find the precise position of z by solving the following simple system of two equations with two variables:

\left\{ \begin{array}{rl} x+y &= n(z)\\ y &= z - t_{n(z)} \end{array}\right.

Or simply put, the coordinates are given by x=n(z)-z+t_{n(z)}, y=z-t_{n(z)}. The question remaining is, of course, how to find the value of n(z).

We need to look for the value of n such that

\displaystyle{\frac{n(n+1)}{2}} \leq z < \displaystyle{\frac{(n+1)(n+2)}{2}}.

One way to accomplish this is to find the closest natural number n to the solution of either side of the inequalities above, say n^2 + n -2z = 0. By choosing this side, an appropriate expression for this value is given by

n(z) = \big\lfloor \frac{-1+\sqrt{1+8z}}{2} \big\rfloor.

We have successfully computed for each natural number z \in \mathbb{N} \cup \{ 0 \} a unique position in the lattice \big( \mathbb{N} \cup \{ 0 \}\big)^2. The construction is also such that for each position (x,y) in the previous lattice, there is a unique natural number that can be sent to that position. The corresponding expression will lead us to the construction of the inverse function \pi^{-1} \colon \big( \mathbb{N} \cup \{ 0 \} \big)^2 \to \mathbb{N} \cup \{ 0 \}. The key is again the same system of equations as before:

Given (x,y), we find n=x+y. This leads us to compute the corresponding t_n, and the second equations gives us

z = y + t_n = y + \displaystyle{\frac{n(n+1)}{2}} = \underbrace{y + \displaystyle{\frac{(x+y)(x+y+1)}{2}}}_{\pi^{-1}(x,y)}.

Miscellaneous

Antoine Flattot suggests using this construction to find a proof that the natural numbers are also in bijection with the rational numbers, and thus they both have the same cardinality. How would the reader go about it?

Also, by using either function above we can obtain elegant diagrams in \LaTeX with the tikz package, showing graphically the structure of the location assignments. For example, with the choice of \pi, we could write a simple function to assign all z+1 positions from 0 to z, including arrows pointing the direction in which the sequence progresses:

\def\gCpf#1{
% Compute the maximum width of the box that contains all values
% from 0 to #1
\pgfmathparse{0.5+floor(0.5*(sqrt(8*#1+1)-1))}
\let\width\pgfmathresult
% Generate a grid with the corresponding width
\draw (-0.25cm,-0.25cm) grid[step=2cm,ultra thin,gray] 
	(2*\width cm+0.25cm, 2*\width cm+0.25cm);
\foreach \x in {0,...,\width} {
	\draw[gray,ultra thin] (2*\x,0.2cm-0.25cm) -- 
		(2*\x, -0.2cm-0.25cm) node[below] 
		{\large$\boldsymbol{\x}$};
	\draw[gray,ultra thin] (0.2cm-0.25cm,2*\x) -- 
		(-0.2cm-0.25cm,2*\x) node[left] 
		{\large$\boldsymbol{\x}$};
% First node, always at the origin
\filldraw(0,0) circle (2pt);
\draw(10pt,8pt) node{\large$0$};

% For each number z between 1 and #1...
\foreach \n in {1,..., #1}
{
	% Compute the diagonal number n(z) and the previous
	\pgfmathparse{floor(0.5*(sqrt(8*\n+1)-1))}
	\let\thisn\pgfmathresult
	\pgfmathparse{floor(0.5*(sqrt(8*\n-7)-1))}
	\let\prevn\pgfmathresult
	%Compute the triangular number t_n and the previous
	\pgfmathparse{0.5*(\thisn^2+\thisn)}
	\let\thist\pgfmathresult
	\pgfmathparse{0.5*(\prevn^2+\prevn)}
	\let\prevt\pgfmathresult
	% Compute the y coords of this and the previous
	\pgfmathparse{\n-\thist}
	\let\thisy\pgfmathresult
	\pgfmathparse{\n-1-\prevt}
	\let\prevy\pgfmathresult
	% Compute the x coords of this and the previous
	\pgfmathparse{\thisn-\thisy}
	\let\thisx\pgfmathresult
	\pgfmathparse{\prevn-\prevy}
	\let\prevx\pgfmathresult
	% Done.  Let's place the nodes at their locations
	\node (this) at (2*\thisx,2*\thisy) [inner sep=6pt] {};
	\node (prev) at (2*\prevx,2*\prevy) [inner sep=6pt] {};
	\draw (2*\thisx cm+10pt,2*\thisy cm+8pt) node{\large$\n$};
	\filldraw (2*\thisx cm,2*\thisy cm) circle (2pt);
	% If the node belongs in the x-axis, receive a red arrow
	% Otherwise, a black arrow
	\ifthenelse{\lengthtest{\thisy cm = 0 cm}}{
		\draw[->,thick,red] (prev) -- (this);
	}{
		\draw[->] (prev) -- (this);
	}
}

Note that the \LaTeX libraries calc and ifthen need to be loaded previously, to be able to handle some of the commands.

Advertisements
  1. Anonymous
    June 8, 2011 at 7:17 am

    Nice and thanks!

  2. godel10
    May 18, 2012 at 5:51 am

    How do you use this code? I am compiling it (putting the code inside the begindocument), but it is not working. Is it possible you link to a file which can be directly compiled?

    • May 18, 2012 at 9:43 am

      The code creates a function of one variable. This variable controls how many integers to show. Put that function in your preamble, make sure that the packages tikz, calc and ifthen are loaded, and call the function with any value inside of your document. Something like this:

      \documentclass{amsart}
      \usepackage{tikz, calc, ifthen}
      
      \def\gCpf#1{
       %the rest of my code goes here...
      }
      
      \begin{document}
      \begin{tikzpicture}
      \gCp{30}
      \end{tikzpicture}
      \end{document}
      
  3. August 31, 2012 at 6:48 pm

    Very nice! I am writing a set of notes, and I would like to include a graph produced using this code. Would this be possible, and if so, is there anything specific you’d like me to include in the acknowledgments (besides your name and a link to this entry)?

    • August 31, 2012 at 8:53 pm

      Thanks! Feel free to use anything you see in my blog. As far as I am concerned, everything I post is open source. You don’t need to cite or acknowledge if you don’t want, either.

      The only request: if you can improve my code, or get something even better-looking, or a nice application, I would love to hear about it.

  4. August 31, 2012 at 9:46 pm

    Many thanks!

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: