Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
I have found the function by Pigeon described at mathworld.wolfram.com/PairingFunction.html Its recursive nature naively puts it out of constant time. –  Niall Murphy Apr 7 '10 at 18:35
2  
Could you define FAC^0? Do you mean that each bit of the result is AC^0? –  François G. Dorais Apr 7 '10 at 22:18
    
(I removed [set-theory] and added [complexity-theory].) –  François G. Dorais Apr 7 '10 at 23:14
    
(I TeXed OP's math notation, because OP's times symbol was mis-sized.) –  Theo Johnson-Freyd Apr 8 '10 at 2:42
    
François, FAC⁰ is the set of functions computable by FO-uniform constant depth Boolean circuits (using AND, OR and NOT gates). So yes, each bit can be computed in AC⁰. (sorry didn't define this before hand) –  Niall Murphy Apr 8 '10 at 9:06

2 Answers 2

up vote 3 down vote accepted

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 FAC0.

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)

share|improve this answer

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.

share|improve this answer
    
Unfortunately multiplication with two variables is known not to be in AC⁰ (though multiplication by a constant is in AC⁰). Is it the case that pairing functions must always be polynomial? If so then the only way it would be possible to compute such a function in constant time would be via some number theory tricks? –  Niall Murphy Apr 7 '10 at 18:34
2  
Niall, pairing functions need not be polynomial. I expect, for example, that the binary-digit-interleaving function is not polynomial. –  Joel David Hamkins Apr 7 '10 at 18:47
2  
I can't think of a reasonable definition of FAC^0 that interleaving bits does not satisfy. –  François G. Dorais Apr 7 '10 at 22:40
    
After thinking a bit more its clear the interleaving pairing function is computed easily in FAC⁰. However, the problem is now to make it uniform. (i.e each circuit with $n$ input gates should compute the pairing function for all pairs of numbers whose concatenated binary encodings are length $n$) e.g 10d=1010b, 4d=100b gives input 1010100. How to tell where one number ends and the other begins? One idea is to encode one number backwards so the most sig. bits are at the ends of the string. Then interleave the bits from the ends and use the first $n$ bits of these as the answer. –  Niall Murphy Apr 8 '10 at 9:20
    
@Niall: Why does the input have to be concatenated? You might as well have the input interleaved, no? It seems that your definition also has problems with the "1st bit of the second number" function. –  François G. Dorais Apr 8 '10 at 14:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.