polynomial bijections from NxN to N

W. Edwin Clark

unread,

Oct 14, 2002, 3:32:48 PM10/14/02

to

The polynomial f(n,m) = (n+m-1)*(n+m-2)/2 + m
is a bijection from N x N to N where N is the
set of positive integers. Interchanging n and
m we get another such polynomial. Are there
any others? How about other nicely described
bijections?

Edwin Clark

------------------------------------------------------------
W. Edwin Clark, Math Dept, University of South Florida,
http://www.math.usf.edu/~eclark/
------------------------------------------------------------

Zdislav V. Kovarik

unread,

Oct 14, 2002, 8:12:36 PM10/14/02

to

On Mon, 14 Oct 2002, W. Edwin Clark wrote:

> The polynomial f(n,m) = (n+m-1)*(n+m-2)/2 + m
> is a bijection from N x N to N where N is the
> set of positive integers. Interchanging n and
> m we get another such polynomial. Are there
> any others? How about other nicely described
> bijections?

> Edwin Clark

F(m,n) = 2^(m-1) * (2*n - 1)

Cheers, ZVK(Slavek)

W. Edwin Clark

unread,

Oct 14, 2002, 10:08:56 PM10/14/02

to

"Zdislav V. Kovarik" wrote:

>
> F(m,n) = 2^(m-1) * (2*n - 1)
>
> Cheers, ZVK(Slavek)

That's a great bijection! Thanks very much!

Edwin

Dale R Worley

unread,

Oct 15, 2002, 9:20:18 AM10/15/02

to

"Zdislav V. Kovarik" <kov...@mcmail.cis.mcmaster.ca> writes:
> F(m,n) = 2^(m-1) * (2*n - 1)

It's a nice formula, but it's not a polynomial. (Is it possible to do
a similar trick using a polynomial?)

Dale

Edwin Clark

unread,

Oct 16, 2002, 1:27:26 PM10/16/02

to

I wrote:

> The polynomial f(n,m) = (n+m-1)*(n+m-2)/2 + m
> is a bijection from N x N to N where N is the
> set of positive integers. Interchanging n and
> m we get another such polynomial. Are there
> any others? How about other nicely described
> bijections?

Alec Mihailovs informed me that Fueter and Polya proved that the only
quadratic polynomials with real coefficients which give a bijection from
NxN to N are the two mentioned above. But I guess the possibility
of non-quadratic polynomials remains open?

--Edwin

Christian Ohn

unread,

Oct 16, 2002, 1:27:32 PM10/16/02

to

W. Edwin Clark wrote:
>
> The polynomial f(n,m) = (n+m-1)*(n+m-2)/2 + m
> is a bijection from N x N to N where N is the
> set of positive integers. Interchanging n and
> m we get another such polynomial. Are there
> any others?

In [1], R. Fueter and G. Polya showed that these two are the only such
polynomials of degree 2

In [2], J.S. Lew and L. Rosenberg showed that there are no other such
polynomials of degree less than 5.

I don't know whether the problem has since been settled in full.

[1] R. Fueter and G. Polya, "Rationale Abzahlung der Gitterpunkte,"
Vierteljschr. Naturforsch. Gesellsch. Zurich, 58 (1923), 280-386.

[2] J.S. Lew and L. Rosenberg, "Polynomial indexing of integer lattice
points, I and II," J. Number Theory 10 (1978), 192-214 and 215-243.

--
Christian Ohn
e-mail: christian|dot|ohn|at|univ|hyphen|valenciennes|dot|fr