Counting in N-Dimensions

Notes:

Using the Eclipse IDE, I have created a Java project that implements what is discussed in this post. You can view or download it from my github repository.

For convenience, this article includes the number 0 in the set of natural numbers, \mathbb{N}, which by convention usually does not include the number 0.


Definition: A set S is a countable set if and only if there exists a bijective mapping f: S \to \mathbb{N}, where \mathbb{N} is the set of natural numbers
(i.e. for any pair of elements, a and b in S for which a \neq b, f(a) \neq f(b), and for any element, n in \mathbb{N}, there exists an element c in S, such that f(c) = n).

\begin{array}{c |ccccc} \mathbb{N}^2 & 0 & 1 & 2 & 3 & \dots \\ \hline 0 & (0,0) & (0,1) & (0,2) & (0,3) \\ 1 & (1,0) & (1,1) & (1,2) & (1,3) \\ 2 & (2,0) & (2,1) & (2,2) & (2,3) \\ 3 & (3,0) & (3,1) & (3,2) & (3,3) \\ \vdots & & & & & \ddots \end{array}

By creating a table with rows and columns both labeled by the natural numbers in ascending order, and with entries consisting of these ordered row and height number pairs, each entry can be counted while traversing along the diagonals of the table in such a manner as to yield the following sequence listing the elements of \mathbb{N}^2:

\mathbb{N}^2 = \{(0,0), (1,0), (0,1),(2,0),(1,1),(0,2),(3,0),(2,1), ...\}

The reason for traversing along the diagonals of the table instead of its rows or columns is that, although they grow larger as the process continues, the diagonals are always finite in length. If I needed to count up to a particular ordered pair, I could always reach it in a finite number of steps by counting along the table’s diagonals. On the other hand, the rows and columns of the table are infinite in length. Were I to count along them, I could never get to an element occurring in a subsequent row or column.

Clearly, every possible ordered pair of natural numbers occurs in this sequence exactly once. Since there are an infinite number of possible ordered pairs of natural numbers, the sequence must be infinite in length. In this way, the set \mathbb{N}^2 satisfies the definition of a countable set (a similar argument demonstrates that \mathbb{Q}, the set of rational numbers, is also a countable set).

Repeating this process, the elements of \mathbb{N}^{3} can be counted by constructing a table with rows in \mathbb{N} and with columns in \mathbb{N}^{2}

\begin{array}{c |ccccc} \mathbb{N}^3 & \mathbb{N}^2_{0} & \mathbb{N}^2_{1} & \mathbb{N}^2_{2} & \mathbb{N}^2_{3} & \dots \\ \hline 0 & (0,\mathbb{N}^2_{0}) & (0,\mathbb{N}^2_{1}) & (0,\mathbb{N}^2_{2}) & (0,\mathbb{N}^2_{3}) \\ 1 & (1,\mathbb{N}^2_{0}) & (1,\mathbb{N}^2_{1}) & (1,\mathbb{N}^2_{2}) & (1,\mathbb{N}^2_{3}) \\ 2 & (2,\mathbb{N}^2_{0}) & (2,\mathbb{N}^2_{1}) & (2,\mathbb{N}^2_{2}) & (2,\mathbb{N}^2_{3}) \\ 3 & (3,\mathbb{N}^2_{0}) & (3,\mathbb{N}^2_{1}) & (3,\mathbb{N}^2_{2}) & (3,\mathbb{N}^2_{3}) \\ \vdots & & & & & \ddots \end{array} = \begin{array}{c |ccccc} \mathbb{N}^3 & (0,0) & (1,0) & (0,1) & (2,0) & \dots \\ \hline 0 & (0,0,0) & (0,1,0) & (0,0,1) & (0,2,0) \\ 1 & (1,0,0) & (1,1,0) & (1,0,1) & (1,2,0) \\ 2 & (2,0,0) & (2,1,0) & (2,0,1) & (2,2,0) \\ 3 & (3,0,0) & (3,1,0) & (3,0,1) & (3,2,0) \\ \vdots & & & & & \ddots \end{array}

which gives the sequence of elements in \mathbb{N}^3:

\mathbb{N}^3 = \{(0,0,0), (1,0,0), (0,1,0),(2,0,0),(1,1,0),(0,0,1),(3,0,0),(2,1,0), ...\}

This sequence can in turn be crossed with \mathbb{N} once more to count the elements of \mathbb{N}^{4}, and so on.


If I am given a particular n-tuple, can I find its sequence index number without counting up to it? For instance, at what index in \mathbb{N}^3 does the 3-tuple (13, 5, 7) occur? Obversely, if I am given a particular index number, can I find its corresponding n-tuple? for instance what is the 47th element in the \mathbb{N}^5 sequence?

It is best to first solve the simplest case in \mathbb{N}^2, and then generalize to \mathbb{N}^p

As elements in \mathbb{N}^2 are two-dimensional, this suggests a function of two variables, f: \mathbb{N}\times\mathbb{N} \to \mathbb{N}. As it turns out, it suffices that f be quadratic.

Thus, with as yet unknown constants C_i,

f(x,y) = C_0 x^2 + C_1 y^2 + C_2 xy + C_3 x + C_4 y + C_5

As there are six unknown constants, a system of six equations suffices to determine what they are. We know that (0,0) is the zeroth element in \mathbb{N}^2, (1,0) is the 1st element, (0,1) is the 2nd, and so on…

\begin{array}{c} f(0,2) = C_0 (0)^2 + C_1 (2)^2 + C_2 (0)(2) + C_3 (0) + C_4 (2) + C_5 = 5 \\ f(1,1) = C_0 (1)^2 + C_1 (1)^2 + C_2 (1)(1) + C_3 (1) + C_4 (1) + C_5 = 4 \\ f(2,0) = C_0 (2)^2 + C_1 (0)^2 + C_2 (2)(0) + C_3 (2) + C_4 (0) + C_5 = 3 \\ f(0,1) = C_0 (0)^2 + C_1 (1)^2 + C_2 (0)(1) + C_3 (0) + C_4 (1) + C_5 = 2 \\ f(1,0) = C_0 (1)^2 + C_1 (0)^2 + C_2 (1)(0) + C_3 (1) + C_4 (0) + C_5 = 1 \\ f(0,0) = C_0 (0)^2 + C_1 (0)^2 + C_2 (0)(0) + C_3 (0) + C_4 (0) + C_5 = 0 \\ \end{array}

Solving the system,

\begin{bmatrix}0&4&0&0&2&1\\ 1&1&1&1&1&1\\ 4&0&0&2&0&1\\ 0&1&0&0&1&1\\ 1&0&0&1&0&1\\ 0&0&0&0&0&1 \end{bmatrix} \begin{bmatrix}C_0\\C_1\\C_2\\C_3\\C_4\\C_5\end{bmatrix} = \begin{bmatrix}5\\4\\3\\2\\1\\0\end{bmatrix}

gives C_0 = \frac{1}{2}, C_1 = \frac{1}{2}, C_2 = 1, C_3 = \frac{1}{2}, C_4 = \frac{3}{2}, C_5 = 0.

and so,

\begin{aligned} f(x,y) &= \frac{1}{2}x^2 + \frac{1}{2}y^2 + xy + \frac{1}{2}x + \frac{3}{2}y \\ &= \frac{1}{2}(x+y)(x+y+1)+y \end{aligned}

This is known as the Cantor pairing function.

Not only can this function give the index of a particular 2-tuple, but by composing it recursively, it can give the index of a general n-tuple.

f(x_1,x_2,...,x_n) = f(x_1,f(x_2,f(...,f(x_{n-1},x_n)))

Now I can find the index of (13, 5, 7) in \mathbb{N}^3:

\begin{aligned} f(13,5,7) &= f(13,f(5,7)) \\ &= f(13, \frac{1}{2}(5+7)(5+7+1)+7) \\ &= f(13,85) \\ &= \frac{1}{2}(13+85)(13+85+1)+85 \\ &= 4,936 \end{aligned}

What about the inverse of this function, f^{-1}: \mathbb{N} \to \mathbb{N}^p? Given an index, can I calculate its corresponding n-tuple?

I will first show how to begin with a particular index in \mathbb{N}^2, i, and find the 2-tuple, (x(i),y(i)), that it corresponds to. Observe that the first element of the nth diagonal always begins with (n,0). Now also observe that the nth diagonal of the \mathbb{N}^2 table has n+1 elements. For instance, the 0th diagonal has one element, the 1st diagonal has 2 elements, the 2nd diagonal has 3 elements, and so on. This suggests the following mappings:

\begin{array}{ccccc} f^{-1}(0) & = & f^{-1}(0) & = & (0,0) \\ f^{-1}(0+1) & = & f^{-1}(1) & = & (1,0) \\ f^{-1}(0+1+2) & = & f^{-1}(3) & = & (2,0) \\ f^{-1}(0+1+2+3) & = & f^{-1}(6) & = & (3,0) \\ \vdots & & \vdots & & \vdots \\ f^{-1}(0+1+2+3+...+n) & = & f^{-1}(\frac{n(n+1)}{2}) & = & (n,0) \\ \end{array}

If the ith element is also the \frac{n(n+1)}{2}th element, for some n, then

\begin{array}{c} i = \frac{n(n+1)}{2} \\ \to 0 = n^2 + n - 2i \\ \to n = \frac{ \sqrt{1+8i}-1 }{2} \\ \end{array}

If i is larger than the \frac{n(n+1)}{2}th element, but still in the same diagonal, and hence, at most the \frac{n(n+1)}{2} + nth element

\lfloor\frac{\sqrt{1+8i}-1}{2}\rfloor < n

I can find the x(i) coordinate by substituting for n, this expression into \frac{n(n+1)}{2} + n - i= \frac{n(n+3)}{2} - i. The y(i) coordinate is derived similarly.

\begin{aligned} x(i) &= \frac{\lfloor\frac{\sqrt{1+8i}-1}{2}\rfloor(\lfloor\frac{\sqrt{1+8i}-1}{2}\rfloor+3)}{2} - i \\ y(i) &= i - \frac{\lfloor\frac{\sqrt{1+8i}-1}{2}\rfloor(\lfloor\frac{\sqrt{1+8i}-1}{2}\rfloor+1)}{2}\end{aligned}

I can extend the use of these equations to n-tuples by composing them in the following manner.

\begin{aligned} \mathbb{N}^q_{i} &= \mathbb{N}_{x(i)}\times\mathbb{N}^{q-1}_{y(i)} \\ &=\mathbb{N}_{x(i)}\times\mathbb{N}_{x(y(i))}\times\mathbb{N}^{q-2}_{y(y(i))} \\ &=\mathbb{N}_{x(i)}\times\mathbb{N}_{x(y(i))}\times\mathbb{N}_{x(y(y(i)))}\times\mathbb{N}^{q-3}_{y(y(y(i)))} \\ &= \dots \end{aligned}

Now I can answer the second question, what is the 47th element in the \mathbb{N}^5 sequence?

\begin{aligned} \mathbb{N}^5_{47} &= (\mathbb{N}_{x(47)},\mathbb{N}^{4}_{y(47)}) \\ &=(7,\mathbb{N}^{4}_{2}) \\ &=(7,\mathbb{N}_{x(2)},\mathbb{N}^{3}_{y(2)}) \\ &=(7,0,\mathbb{N}^{3}_{1}) \\ &=(7,0,1, \mathbb{N}^{2}_{0}) \\ &=(7,0,1, \mathbb{N}_{x(0)}, \mathbb{N}_{y(0)}) \\ &=(7,0,1, 0, 0) \end{aligned}


I have created a Java class, RecursiveIntTupleGenerator, that generates these sequences. An instance of this class has a specified number of dimensions, and is initialized to the 0th element of its corresponding sequence. You can view/download the Eclipse project source here.

\begin{tabular}{|l|} \hline RecursiveIntTupleGenerator \\ \hline -x: int \\ -subTuple: RecursiveIntTupleGenerator \\ -savedX: int \\ -dimensions: int \\ \hline +constructor(int numDimensions) \\ +getDimensions() \\ +getVal(int index) \\ +setZero() \\ +next() \\ +toString() \\ ... \\ \hline\end{tabular}

As discussed above, the Cantor pairing function directly associates the natural numbers to the respective natural number n-tuple, and vice versa, but I was also interested in capturing the recursive nature of the n-tuple counting process. This is implemented in the next() method.

	public void next() {
		if (dimensions == 1) {
			x += 1;
		} else {
			if (x > 0) {
				x -= 1;
				subTuple.next();
			} else {
				savedX += 1;
				x = savedX;
				subTuple.setZero();
			}
		}
	}

I’d like to expand on this project in the future. It must be possible to iterate over the integers (including negative numbers) in multiple dimensions just as well as it is possible to iterate over the natural numbers. Also, since this procedure may theoretically carry on indefinitely, it would make more sense to use Java’s BigInteger class instead of just integers.

Being able to generate a sequence of every possible positive whole number n-tuple affords an easy, brute-force solution search for multivariate Diophantine equations, and various other problems in number theory. I put my Java class to the test and verified Lagrange’s four-square theorem for the first 100 whole numbers.

\begin{array}{c} 0 = 0^{2} + 0^{2} + 0^{2} + 0^{2} \\ 1 = 1^{2} + 0^{2} + 0^{2} + 0^{2} \\ 2 = 1^{2} + 1^{2} + 0^{2} + 0^{2} \\ 3 = 1^{2} + 1^{2} + 1^{2} + 0^{2} \\ 4 = 2^{2} + 0^{2} + 0^{2} + 0^{2} \\ 5 = 2^{2} + 1^{2} + 0^{2} + 0^{2} \\ \vdots \\ 95 = 9^{2} + 3^{2} + 2^{2} + 1^{2} \\ 96 = 8^{2} + 4^{2} + 4^{2} + 0^{2} \\ 97 = 9^{2} + 4^{2} + 0^{2} + 0^{2} \\ 98 = 9^{2} + 4^{2} + 1^{2} + 0^{2} \\ 99 = 7^{2} + 7^{2} + 1^{2} + 0^{2} \\ \end{array}

I let my program run longer and verified the theorem for numbers up to 5,000. My program took a much, much longer time to verify the solution, 3,072 = 32^{2} + 32^{2} + 32^{2} + 0^{2}  than it did for any other number in this range. It must take many calls of the next() function to find this solution. Starting from (0,0,0,0), how many times does the next() function have to be called in order to find these four squares that add up to 3,072?

Advertisements

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