Pairing function: Information from Answers.com

In mathematics a pairing function is a process to uniquely encode two natural numbers into a single natural number.

Any pairing function can be used in set theory to prove that integers and rational numbers have the same cardinality as natural numbers. In theoretical computer science they are used to encode a function defined on a vector of natural numbers f:N^k → N into a new function g:N → N.

1 Definition
2 Cantor pairing function
- 2.1 Inverting the Cantor pairing function
3 References

Definition

A pairing function is a primitive recursive bijection

$\pi:\mathbb{N} \times \mathbb{N} \to \mathbb{N}.$

Cantor pairing function

The Cantor pairing function assigns one natural number to each pair of natural numbers

The Cantor pairing function is a pairing function

$\pi:\mathbb{N} \times \mathbb{N} \to \mathbb{N}$

defined by

$\pi(k_1,k_2) := \frac{1}{2}(k_1 + k_2)(k_1 + k_2 + 1)+k_2.$

When we apply the pairing function to $k 1$ and $k 2$ we often denote the resulting number as $\langle k_1, k_2 \rangle \,.$

This definition can be inductively generalized to the Cantor tuple function

$\pi^{(n)}:\mathbb{N}^n \to \mathbb{N}$

$\pi^{(n)}(k_1, \ldots, k_{n-1}, k_n) := \pi ( \pi^{(n-1)}(k_1, \ldots, k_{n-1}) , k_n) \,.$

Inverting the Cantor pairing function

Suppose we are given z with

$z = \langle x, y \rangle = \frac{(x + y)(x + y + 1)}{2} + y$

and we want to find x and y. It is helpful to define some intermediate values in the calculation:

$w = x + y \!$

$t = \frac{w(w + 1)}{2} = \frac{w^2 + w}{2}$

$z = t + y \!$

where t is the triangle number of w. If we solve the quadratic equation

$w^2 + w - 2t = 0 \!$

for w as a function of t, we get

$w = \frac{\sqrt{8t + 1} - 1}{2}$

which is a strictly increasing and continuous function when t is non-negative real. Since

$t \leq z = t + y < t + (w + 1) = \frac{(w + 1)^2 + (w + 1)}{2}$

we get that

$w \leq \frac{\sqrt{8z + 1} - 1}{2} < w + 1$

and thus

$w = \left\lfloor \frac{\sqrt{8z + 1} - 1}{2} \right\rfloor$ .

So to calculate x and y from z, we do:

$w = \left\lfloor \frac{\sqrt{8z + 1} - 1}{2} \right\rfloor$

$t = \frac{w^2 + w}{2}$

$y = z - t \!$

$x = w - y \!$ .

Since the Cantor pairing function is invertible, it must be one-to-one and onto.

References

Steven Pigeon, "Pairing function" from MathWorld.

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	Cylindrification
	BLS (Cryptography)
	Pairing-based cryptography

	How do you determine if you are given a set of ordered pairs that represent a function? Read answer...
	How can you determine a mathematical function from a series of ordered pairs? Read answer...
	Are nigrosin and malachite green a functional analogous pair of stain? Read answer...

	What is function of complementary base-pairing?
	How the molecular geometry is a function of electron pair geometry?
	How do your muscles function other than in pairs?

Pairing function

Contents

Definition

Cantor pairing function

Inverting the Cantor pairing function

References