show/hide this revision's text 2 rephrasing part of Joel David Hamkins answer and giving an example

Bit interleaving

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 two original numbers resulting paired number is 0100110010b = 306d

This pairing function can be easily decoded in computed and reversed by a constant time.depth (see http://mathworld.wolfram.com/PairingFunction.html, 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)

show/hide this revision's text 1

Bit interleaving seems to be the best solution. The two original numbers can be easily decoded in constant time.

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