1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Jul 11, 2011 at 2:34
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 11, 2011 at 3:54
  • $\begingroup$ 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 $\endgroup$ Jul 11, 2011 at 6:14
  • $\begingroup$ Forgive my gender presumption. All the Lunas I know are female. Gerhard "Email Me About System Design" Paseman, 2011.07.10 $\endgroup$ Jul 11, 2011 at 6:17
  • $\begingroup$ 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$. $\endgroup$ Mar 10, 2014 at 16:59

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ To drive the point further, you might say monotone with respect to distinct products. Gerhard "Writes With A Sledge Hammer" Paseman, 2011.07.10 $\endgroup$ Jul 10, 2011 at 19:38
  • $\begingroup$ 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. $\endgroup$ Jul 10, 2011 at 22:00
  • $\begingroup$ 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. $\endgroup$
    – Luna
    Jul 10, 2011 at 22:23
  • $\begingroup$ I've realized one can salvage the silly solution in a trivial way, which I've now posted. $\endgroup$ Jul 10, 2011 at 23:18
  • $\begingroup$ 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. $\endgroup$ Jul 11, 2011 at 0:02
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Luna
    Jul 11, 2011 at 9:41
  • $\begingroup$ 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 $\endgroup$ Jul 11, 2011 at 22:44
  • $\begingroup$ 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. $\endgroup$
    – Luna
    Jul 12, 2011 at 10:54
-2
$\begingroup$

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>
    
$\endgroup$
2
  • $\begingroup$ This function does not verify the conditions stated in the question. $\endgroup$ Mar 10, 2014 at 16:51
  • $\begingroup$ @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. $\endgroup$
    – ma11hew28
    Mar 28, 2014 at 21:25

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