Pairing function monotonic respect to product of arguments Has anyone ever created a "pairing function" (possibly non-injective)
with the property to be nondecreasing wrt to product of arguments, integers n>=2, m>=2. (We can also assume that n and m are bounded by an integer K, if useful) :
n m > n' m'   =>    p(n,m) > p(n',m')  
If yes what does it look like, does it have a name ? 
-Luna
 A: Your second property is simply inconsistent with the nature
of a pairing function, since we want $p(n,m)=p(n',m')\iff
n=n'$ and $m=m'$. That is, a pairing function must be
one-to-one on pairs, but multiplication is not, since
$2\cdot 6=3\cdot 4$.
The first property, however, is easy to arrange as follows
(and there will be continuum many different such
functions). Let me work only with positive integers. 
First, list all the possible product values in order.
For each such product $r$, observe that there are only
finitely many pairs with $nm=r$; list these pairs in any
desired order. Now, concatenate these lists of pairs, and
let $p(n,m)$ be the place of the pair $\langle n,m\rangle$
in your master list. This is a pairing function, since it
is injective on pairs, and it is monotone with respect to
products, since larger products appear later on the master
list.
Finally, note that it is not possible to achieve the property if you allow $0$, since in this case there are infinitely many pairs with product $0=n\cdot 0$, and they cannot all have pairing value before the the other pairs.

Edit. In your comments, you drop the one-to-one requirement, which makes this very far from what would ordinarily be called a pairing function. Nevertheless, the problem now admits the following rather silly solution in the positive integers:  let $p(n,m)=nm$, which has both your stated properties. The "inverse" function is: let $F(r)=r$ and $G(r)=1$. That is, given the product $r$, we return the pair $\langle r,1\rangle$, which of course also has product $r\cdot 1=r$. In otherwords $p(F(r),G(r))=r$, which would seem to be the inverse requirements.
A: To pull this observation out of the comments, suppose we had a pairing function which was monotonic increasing with respect to products of 2 or more integers each larger than 1, and which had nice inverses, say one of them was F(p) and had a nice formula for it which was quickly computable and returned an integer greater than or equal to 2.  If the pairing function did not grow too fast, I could take a large odd number 2n+1, feed 2 and n to the pairing function, and feed 2 and n+ 1 to the pairing function again, and get lower and upper bounds on a range of values to invert with F. If F returns a value, I can test it as a nontrivial factor of my odd number.  With some assumptions on how nice the pairing function and its inverses are, I could make a poly-time factoring algorithm.
Because of this result, I would instead believe that such a pairing function and its inverse are not so nice, either being trivial and not giving useful information, or not being quick or easy to compute the inverse.
Gerhard "Email Me About System Design" Paseman, 2011.07.11
A: How about these unordered pairing functions?
For positive integers as arguments and where argument order doesn't matter:


*

*Here's an unordered pairing function:
$<x, y> = x * y + trunc(\frac{(|x - y| - 1)^2}{4}) = <y, x>$

*For x ≠ y, here's a unique unordered pairing function:
<x, y> = if x < y:
           x * (y - 1) + trunc((y - x - 2)^2 / 4)
         if x > y:
           (x - 1) * y + trunc((x - y - 2)^2 / 4)
       = <y, x>

