Are there any pairing functions computable in constant time (AC⁰) - MathOverflow

Are there any pairing functions computable in constant time (AC⁰)

2010-04-07T17:24:02Z

Are there any known reversible pairing functions $f: \mathbb N \times \mathbb N \to \mathbb N$ that can be computed in constant time (FAC⁰)?

Answer by Joel David Hamkins for Are there any pairing functions computable in constant time (AC⁰)

2010-04-07T17:38:11Z

The pairing function f(a,b) = (a + b)(a + b + 1)/2 + a is the one that arises by drawing diagonals on the natural number lattice, and marching down them from upper left to lower right. See the picture here.

To compute f(a,b), one needs to perform some additions and a multiplication, which seems to be quadratic time in the length of a and b, that is, in log(a)+log(b), which would seem to be constant time in max(a,b), but I'm not sure if this would be what you meant.

In that book, it is noted that Polya has proved that any surjective polynomial pairing function is equal to this function or to its dual form f(b,a). (And someone gave a talk here at CUNY a few weeks ago on precisely this fact.) So if this function is not acceptable to you, then you will find no polynomial surjective function.

But here is another function, which seems to be a little faster to compute. Suppose that a and b are given to me in their binary representation. Now, I just interleave their binary digits, using 0's if the digits of one of them runs out. This is surely a pairing function, and I can compute it linear time of the lengths of the input.

Answer by Niall Murphy for Are there any pairing functions computable in constant time (AC⁰)

2010-04-08T16:28:04Z

Interleaving the binary encodings of the two numbers a and b seems to be the best solution:

For example the encoding of
a = 20d = 10100b
b = 5d = 101b
We interleave the bits starting with the least significant bits (we pad shorter numbers with 0's so they are the same length).
The resulting paired number is 0100110010b = 306d

This pairing function can be computed and reversed by a constant depth (depth 1?) circuit and so is in FAC⁰.

See:
- http://mathworld.wolfram.com/PairingFunction.html
- Pigeon, P. Contributions à la compression de données. Ph.D. thesis. Montreal, Université de Montréal, 2001. (page 115)