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

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 ?


share|improve this question
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 '11 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 '11 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 '11 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 '11 at 6:17
Dear @Luna: If you allow non-injective functions, as is the case in the current version of this post, this question admits the trivial answer $p(n,m) = nm$. –  Ricardo Andrade Mar 10 at 16:59
add comment

closed as unclear what you're asking by Noah S, Chris Godsil, Stefan Kohl, Andrey Rekalo, Willie Wong Mar 31 at 7:58

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

3 Answers

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.

share|improve this answer
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 '11 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 '11 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 '11 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 '11 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 '11 at 0:02
show 4 more comments

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

share|improve this answer
Looking at Cantor pairing function: (en.wikipedia.org/wiki/Pairing_function) i think it's natural to ask if one could build (a similar) parametric curve (the inverse would suffice for most practical problems), preserving the preorder inducted by the product nm. Since this could would provide many benefits, my question was whether this has been studied, has a name and a solution. Anyway, from the first answers, i can imagine that the answer may not be affirmative. And also that the problem may not be so easy to solve. –  Luna Jul 11 '11 at 9:41
I agree that it is tempting to ask questions like the one you presented. On the other hand, I have seen several attempts (which I do not like) to ask about something that was a (often thinly) disguised version of a quick solution to an NP-hard problem, which often evoked the notion "you do the work and we will share the credit". I won't say that you ever intended such; I will say that from my point of view, your question seems close to such thinly disguised questions. Regardless, I wish you success in your continued studies. Gerhard "Email Me About System Design" Paseman, 2011.07.11 –  Gerhard Paseman Jul 11 '11 at 22:44
So we have managed, by introducing further assumptions, to allow the original question to evoke an hypothetical line of attack to more difficult problems. Given the upgrade, i guess, at this point we can be excused of our inability to contribute on the specific technical point. In fact, mathematicians had better not to touch the hard problems, if they want to get tenure. Better to turn on philosophy, creative speculations or relatively easy problems. –  Luna Jul 12 '11 at 10:54
add comment

How about these unordered pairing functions?

For positive integers as arguments and where argument order doesn't matter:

  1. Here's an unordered pairing function:

    $<x, y> = x * y + trunc(\frac{(|x - y| - 1)^2}{4}) = <y, x>$

  2. 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>
share|improve this answer
This function does not verify the conditions stated in the question. –  Ricardo Andrade Mar 10 at 16:51
@RicardoAndrade you may be correct. I do not understand the conditions. But, perhaps these functions can help others come up with the answers they're seeking. –  MattDiPasquale Mar 28 at 21:25
add comment

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