## 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

-
The latest version of the question can be realized affirmatively by any constant function $p(n,m)=5$, say, with "inverse" functions any desired functions at all. – Joel David Hamkins Jul 11 2011 at 2:34
In an earlier comment (under Joel's answer), I wrote "I'd encourage Luna to think about exactly what's wanted and then edit the question accordingly." Since then, the question has been edited but, as Joel pointed out, it still has a trivial answer. To prod Luna a bit more to clean up the question, I've voted to close. – Andreas Blass Jul 11 2011 at 3:54
The construction of the inverses of such a (strictly increasing on products) pairing function would be tantamount to a factorization table. One can be built in theory, but it is unlikely to be used in practice, and certainly a nice version would solve many instances of the factorization decision problem. I think Luna should make her intent more visible, and I may suggest closing even if she does. Gerhard "Hopes He Got It Wrong" Paseman, 2011.07.10 – Gerhard Paseman Jul 11 2011 at 6:14
Forgive my gender presumption. All the Lunas I know are female. Gerhard "Email Me About System Design" Paseman, 2011.07.10 – Gerhard Paseman Jul 11 2011 at 6:17

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.

-
 To drive the point further, you might say monotone with respect to distinct products. Gerhard "Writes With A Sledge Hammer" Paseman, 2011.07.10 – Gerhard Paseman Jul 10 2011 at 19:38 If you drop the one-to-one requirement, then of course you could just use $p(n,m)=nm$, which has both your requested properties (although I would resist calling any non-injective function a pairing function)...but I see, you will object that the "inverse" function involves factoring, and you want a "closed-form" for the inverse. – Joel David Hamkins Jul 10 2011 at 22:00 Right. Ideally, i'd like to "touch" with a parametric curve n=F(p), m=G(p) the various pairs of integers in the plane (n,m), n>=2, m>=2 (and possibly less than an integer upper bound) "visited" in such a way that the product nm does not decrease. I can imagine, in my mind, this curve must probably have some "zig-zag" shape (like some sinusoidal with increasing waves), but i am having hard time figuring out the 2 formulas for F(p), G(p). I was actually wondering if anyone has already studied and written down them. It would seem like a classical problem, and perhaps already treated and solved. – Luna Jul 10 2011 at 22:23 I've realized one can salvage the silly solution in a trivial way, which I've now posted. – Joel David Hamkins Jul 10 2011 at 23:18 Luna's last comment, though rather vague, seems to be reinstating the requirement that the pairing function should be one-to-one. Otherwise, the "curve" will have many points corresponding to a single parameter value. The question seems to be a moving target and Joel has shot down two versions of it. I'd encourage Luna to think about exactly what's wanted and then edit the question accordingly. – Andreas Blass Jul 11 2011 at 0:02