Inverse of a Multivariate Function

Date: 05/30/2002 at 10:17:15
From: Subha
Subject: calculus

Let f: NxN->N such that 

  f(x,y) = 2^x(2y + 1) - 1 

for all natural numbers x, y.  Let the inverse of f, g be given by 
g:N->NxN. Find g.

Date: 05/30/2002 at 13:18:17
From: Doctor Peterson
Subject: Re: calculus

Hi, Subha.

It's important to realize that we are talking about f: NxN->N. That 
is, first, we are dealing with natural numbers (in this case 
apparently taken to mean non-negative integers, judging by the 
behavior of the function), not real numbers; you will not want to use 
logarithms. Second, the inverse has to take a single natural number 
back to the PAIR of natural numbers (x,y) from which f created it; 
we can't just invert with respect to one variable as usual. So the 
question to ask is, how does f manage to take only one pair to any 
given natural number?

The function is carefully designed. Note that x appears only 
in "2^x", which is even, while y appears only in "(2y+1)", which is 
odd, and has no factors of 2. As a result, there is no way to make 
the same product using a different x,y pair! Subtracting 1 from the 
product of these serves only to make the range all of N, since it 
takes (0,0) to 0 rather than to 1.

So if you add the 1 back on, you can find x and y by factoring. Can 
you see how to do this? It will probably be hard to express the 
inverse as a formula, but you probably do not need to do that; an 
algorithm for finding g(z) should be sufficient.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 05/30/2002 at 18:01:53
From: Subha
Subject: calculus

How do I find the factor of f(x,y) by sustituting values for x and y?
Please do tell me how to find the alogorithm to find g(x) which is 
the inverse of f(x,y).

Date: 05/30/2002 at 20:45:06
From: Doctor Peterson
Subject: Re: calculus

Hi, Subha.

Your function is

    f(x,y) = 2^x (2y+1) - 1

Given a value z, you need to find the pair (x,y) for which

    z = f(x,y)

Let's just look at an example, and I'll let you decide how to 
describe the algorithm.

Suppose z is 59. We want

    2^x (2y+1) - 1 = 59

so we add 1 and have

    2^x (2y+1) = 60

Now if we factor 60, we find that

    2^x (2y+1) = 2*2*3*5

What power of 2 do you see here? What is x?

What is the other (odd) factor? What is y in order for this to be 
2y+1?

Now write down a description of what you did to find x and y, and 
that will be the inverse function.

One way you might express the inverse function is something like

    g(z) = (..., ....)

where the "..." would be expressions involving z that give x and y. 
You might invent a function like

    even(x) = highest power of 2 that divides x

and use that to write the expressions.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/