Explicit Bijection from N to NxN

  • #1
1,605
2
for this post, let N = {1, 2, 3, ...}.

Q: explicitly write down a closed form bijection with domain N and range N x N. (no need to prove its a bijection... just write down the formula.)


this may lead you off track, but the way i did it was to first find a formula from N x N to N and then invert it.
let (m, n) be an element of N x N and q = 1/2.
then the map is given by (m,n) |-> x, where
x = q m^2 +q n^2 + m n - q m - 3 q n + 1.
maybe I'm admitting how much i lack in algebra skillz by saying this, but i found it hard to invert this function... i did cheat and used mathematica to do the algebra i asked of it, but it didn't actually find the inverse by itself. i only used it to simplify expressions and isolate variables. i also used this site as a reference: http://www.research.att.com/~njas/sequences/ [Broken] . thus i will say to you that no holds are barred; do it by any means necessary!

for double sums, we have something like this:
S = Sum[ f(m,n) , (m,n) ε NxN ].
if g is a bijection from N to NxN, we can straighten out this sum (assuming convergence of the original, we can add any way we please):
S = Sum[ f(g(x)), x ε N ], turning the double sum into a single sum. the catch is the formula for g ain't pretty so I'm not sure how useful this is... at least one can use single integral formulas to now estimate double sums and predict error although perhaps multivariable error estimates for double sums already exist (they probably do)...

i guess the next step is to find a bijection from N to NxNxN... i get an icky feeling all over when i think about that.
 
Last edited by a moderator:

Answers and Replies

  • #2
let g(x) = (m(x), n(x)) be the desired map from N to NxN.

let be the round function (rather than the usual greatest integer function).

then
m(x) = (2x + [SQRT(2x)] - [SQRT(2x)]^2)/2
n(x) = (2 - 2x + [SQRT(2x)] + [SQRT(2x)]^2)/2

for example, the 666th point in NxN is (36,1) and the millionth point is (1009, 406).
 

Suggested for: Explicit Bijection from N to NxN

Replies
7
Views
830
Replies
7
Views
917
Replies
4
Views
759
Replies
14
Views
959
Replies
6
Views
1K
Replies
3
Views
429
Replies
1
Views
351
Replies
10
Views
511
Back
Top