The inverse, call it \(g\text{,}\) of the isomorphism...
Solution.
We’re given a map \(f: \mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}\) that enumerates pairs of natural numbers in a diagonal order. I had originally defined this in Python as follows:
For the purposes of this problem, we’re really only going to need the first 5 values. Specifically: \(f(0) = (0,0)\text{,}\) \(f(1) = (1,0)\text{,}\) \(f(2) = (0,1)\text{,}\) \(f(3) = (2,0)\text{,}\) \(f(4) = (1,1)\text{,}\) and \(f(5) = (0,2)\text{.}\) We’re given than the inverse map \(g: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\) has a form defined by
\begin{equation*}
g(x,y) = \frac{1}{2}(ax^2+bxy+cy^2+dx+ey)
\end{equation*}
The first part of this question follows from some simple substitions. Reversing our 6 point pairings for \(f\) defines the following pairings for \(g\text{:}\) \(g(0,0) = 0\text{,}\) \(g(1,0) = 1\text{,}\) \(g(0,1) = 2\text{,}\) \(g(2,0) = 3\text{,}\) \(g(1,1) = 4\text{,}\) and \(g(0,2) = 5\text{.}\)
Since we’ve already assumed \(g\) has a specific form, these expressions become the following:
\begin{equation*}
g(0,0) = \frac{1}{2}(a \cdot 0^2+b \cdot 0
\cdot 0 +c \cdot 0^2+d \cdot 0 + e \cdot 0)
= 0
\end{equation*}
Which matches our expected result.
\begin{equation*}
g(1,0) = \frac{1}{2}(a \cdot 1^2+b \cdot 1
\cdot 0 +c \cdot 0^2+d \cdot 1 + e \cdot 0)
= \frac{1}{2}(a + d) = 1
\end{equation*}
Which implies that \(d = 2-a\text{.}\)
\begin{equation*}
g(0,1) = \frac{1}{2}(a \cdot 0^2+b \cdot 0
\cdot 1 +c \cdot 1^2+d \cdot 0 + e \cdot 1)
= \frac{1}{2}(c + e) = 2
\end{equation*}
Which implies that \(e = 4-c\text{.}\)
\begin{equation*}
g(2,0) = \frac{1}{2}(a \cdot 2^2+b \cdot 2
\cdot 0 +c \cdot 0^2+d \cdot 2 + e \cdot 0)
= \frac{1}{2}(4a+2d) = 3
\end{equation*}
With our previous subsititions, \(\frac{1}{2}(4a+2d) = 3 \implies
4a+2(2-a) = 6\) which gives us \(a = d = 1\text{.}\)
\begin{equation*}
g(1,1) = \frac{1}{2}(a \cdot 1^2+b \cdot 1
\cdot 1 +c \cdot 1^2+d \cdot 1 + e \cdot 1)
= \frac{1}{2}(a+b+c+d+e) = 4
\end{equation*}
Applying our previous substitions gives us \(\frac{1}{2}(a+b+c+d+e) = 4 \implies
\frac{1}{2}(b+6) = 4
\text{,}\) which means \(b = 2\text{.}\)
\begin{equation*}
g(0,2) = \frac{1}{2}(a \cdot 0^2+b \cdot 0
\cdot 2 +c \cdot 2^2+d \cdot 0 + e \cdot 2)
= \frac{1}{2}(4c+2e) = 5
\end{equation*}
Applying our substitions gives us \(\frac{1}{2}(4c+2e) = 5 \implies
\frac{1}{2}(4c+2(4-c)) = 5\) which means that \(c = 1\) and \(e = 3\text{.}\)
Having found all our constants, we can define \(g\) as
\begin{equation*}
g(x,y) = \frac{1}{2}(x^2+2xy+y^2+x+3y)
\end{equation*}
For comparison, the Python code I wrote previously went like this:
def zig_zag(n):
last = (0,0)
idx = 0
while idx < n:
yield last
idx += 1
if last[1] == 0:
last = (0,last[0]+1)
else:
last = (last[0]+1,last[1]-1)
def triangular(n):
return int((n+1)*n/2)
def reverse_zig_zag(p):
my_sum = p[0]+p[1]
my_triangle = triangular(my_sum)
return my_triangle+p[0]
I think my implementation is equivalent, only I swapped the order of the arguments \(x,y\text{.}\) My
zig_zag function took repeated “south-east treks” instead.I think the key lies in the fact that \((x+y)(x+y+1) = x^2+2xy+y^2+x+y\text{.}\) Knowing this fact allows us to rewrite \(g\) as follows:
\begin{equation*}
g(x,y) =\frac{1}{2}(x^2+2xy+y^2+x+3y)=
\end{equation*}
\begin{equation*}
= \frac{1}{2}(x^2+2xy+y^2+x+y+2y)
\end{equation*}
\begin{equation*}
= \frac{1}{2}(x^2+2xy+y^2+x+y)+\frac{1}{2}(2y)
\end{equation*}
\begin{equation*}
= \frac{1}{2}(x+y)(x+y+1)+y
\end{equation*}
In my Python code, I had slightly abstracted this by referring to “trianglular numbers” as defined by the expression \(\frac{1}{2}n(n+1)\text{.}\) If we subsitute \(n = x+y\) we get the \(\frac{1}{2}(x+y)(x+y+1)\text{.}\) Since I also swapped the order of the arguments, I needed to add an \(x\) instead of a \(y\) to match up with my ordering of the product.
So what does it mean to prove this \(g\) is “an isomorphism of sets”? Well, we’d need to show \(f \circ g = 1_{\mathbb{N}\times\mathbb{N}}\) and \(g \circ f = 1_{\mathbb{N}}\text{.}\)
I think we might be able to show \(g \circ f = 1_{\mathbb{N}}\) using induction. We know \((g \circ f)(0) = 0\) and \((g \circ f)(1) = 1\) because of how we constructed \(g\text{.}\) If we further assume \((g \circ f)(n) = n\) for \(n > 0\text{,}\) can we prove \((g \circ f)(n+1) = n+1\) also?
Suppose \(f(n) = (x,y)\text{.}\) We can define \(f(n+1)\) as \((y+1,0)\) for \(x = 0\) and \((x-1,y+1)\) for \(x > 0\) to simulate the repeated “northwest treks”.
For \(x = 0\text{,}\) we can simplify \(g\text{:}\)
\begin{equation*}
g(0,y) = \frac{1}{2}(y^2+3y)
\end{equation*}
But \(x=0\) also means that our successor is \((y+1,0)\text{,}\) and we have
\begin{equation*}
g(y+1,0) = \frac{1}{2}((y+1)^2+(y+1))
\end{equation*}
\begin{equation*}
= \frac{1}{2}(y^2+2y+1+y+1)
\end{equation*}
\begin{equation*}
= \frac{1}{2}((y^2+3y)+ (2y+1))
\end{equation*}
\begin{equation*}
= \frac{1}{2}(y^2+3y+2)
\end{equation*}
\begin{equation*}
= \frac{1}{2}(y^2+3y)+1
\end{equation*}
\begin{equation*}
= g(0,y)+1
\end{equation*}
For any \((x,y)\) where \(x > 0\text{,}\) we’d have
\begin{equation*}
g(x-1,y+1) = \frac{1}{2}((x-1)^2+2(x-1)(y+1)+(y+1)^2+(x-1)+3(y+1))
\end{equation*}
\begin{equation*}
= \frac{1}{2}((x-1)^2+2(x-1)(y+1)+(y+1)^2+(x-1)+3(y+1))
\end{equation*}
\begin{equation*}
= \frac{1}{2}( (x^2-2x+1)
+ 2(xy+x-y-1)
+ (y^2 + 2y + 1)
+ x-1 + 3y+ 3)
\end{equation*}
\begin{equation*}
= \frac{1}{2}(
x^2 -2x + 1
+ 2xy+2x-2y-2
+ y^2 + 2y + 1
+ x-1 + 3y+ 3)
\end{equation*}
\begin{equation*}
= \frac{1}{2}(
x^2 + 2xy + y^2
-2x +2x + x
-2y + 2y+ 3y
+ 1 -2
+ 1 -1
+ 3)
\end{equation*}
\begin{equation*}
= \frac{1}{2}(
x^2 + 2xy + y^2
+ x
+ 3y
+ 2)
\end{equation*}
\begin{equation*}
= \frac{1}{2}(
x^2 + 2xy + y^2
+ x
+ 3y) + 1
\end{equation*}
\begin{equation*}
= g(x,y) + 1
\end{equation*}
Having met our induction hypothesis in both cases, we can now confidently say \(g \circ f = 1_\mathbb{N}\text{.}\)
What about the opposite direction? Can we use the same tactic to show \(f \circ g = 1_{\mathbb{N} \times \mathbb{N}}\text{?}\)
We can establish some trivial cases to start with. For \(x = y = 0\) we have \((f \circ g) (0,0) =
f(0) = (0,0)\text{.}\) For \(x = 1, y = 0\) we have \((f \circ g) (1,0) =
f(1) = (1,0)\text{.}\) For \(x = 0, y = 1\) we have \((f \circ g) (0,1) =
f(2) = (0,1)\text{.}\) For \(x = 1, y = 1\) we have \((f \circ g) (1,1) =
f(4) = (1,1)\text{.}\)
Now lets suppose \((f \circ g) (x,y) = (x,y)\text{.}\) If we can prove that \((f \circ g) (x+1,y) = (x+1,y)\text{,}\) \((f \circ g) (x,y+1) = (x,y+1)\text{,}\) and \((f \circ g) (x+1,y+1) = (x+1,y+1)\text{,}\) that should allow us to use induction to prove it for all \(x,y\text{.}\)
Let’s consider \(g(x+1,y)\) first.
\begin{equation*}
g(x+1,y) = \frac{1}{2}((x+1)^2+2(x+1)y+y^2+(x+1)+3y)
\end{equation*}
\begin{equation*}
= \frac{1}{2}(
x^2+2x+1+
2xy+2y+
y^2+x+1+3y)
\end{equation*}
\begin{equation*}
= \frac{1}{2}(
x^2+2xy+y^2
+x+3y + 2(x+y+1))
\end{equation*}
\begin{equation*}
= \frac{1}{2}(
x^2+2xy+y^2
+x+3y) + x+y+1
\end{equation*}
\begin{equation*}
= g(x,y) + x+y+1
\end{equation*}
This result is somewhate interesting because every diagonal has a constant sum given by \(x+y\text{.}\)
Likewise, we can expand \(g(x,y+1)\) as follows:
\begin{equation*}
g(x,y+1) =\frac{1}{2}(x^2+2x(y+1)+(y+1)^2+x+3(y+1))
\end{equation*}
\begin{equation*}
=\frac{1}{2}(
x^2+2xy+2x+y^2+2y+1+x+3y+3)
\end{equation*}
\begin{equation*}
=\frac{1}{2}(
x^2+2xy+y^2+x+3y+2x+2y+1+3)
\end{equation*}
\begin{equation*}
=\frac{1}{2}(
x^2+2xy+y^2+x+3y+2(x+y+3))
\end{equation*}
\begin{equation*}
=\frac{1}{2}(
x^2+2xy+y^2+x+3y)+x+y+2
\end{equation*}
\begin{equation*}
=g(x,y)+x+y+2
\end{equation*}
Well, that’s doubly interesting. It follows from both of those results that \(g(x+1,y) = g(x,y+1)+1\) for all \(x,y\text{.}\)
Let’s consider the last case \(g(x+1,y+1)\text{.}\) Substituting into \(g\text{...}\)
\begin{equation*}
g(x+1,y+1) =\frac{1}{2}((x+1)^2+2(x+1)(y+1)+(y+1)^2+(x+1)+3(y+1))
\end{equation*}
\begin{equation*}
= \frac{1}{2}(
x^2+2x+1
+2(xy+x+y+1)
+y^2+2y+1
+x+1+
3y+3)
\end{equation*}
\begin{equation*}
= \frac{1}{2}(
x^2+2x+1
+2xy+2x+2y+2
+y^2+2y+1
+x+1+
3y+3)
\end{equation*}
\begin{equation*}
= \frac{1}{2}(
x^2+2xy+y^2+x+3y
+2x+2x
+2y+2y
+1+2+1+1+3)
\end{equation*}
\begin{equation*}
= \frac{1}{2}(
x^2+2xy+y^2+x+3y
+4x
+4y
+8)
\end{equation*}
\begin{equation*}
= \frac{1}{2}(
x^2+2xy+y^2+x+3y)
+2x+2y+4
\end{equation*}
\begin{equation*}
= g(x,y)+
2x+2y+4
\end{equation*}
Note that we could also infer \(g(x+1,y+1) = g(x,y+1)+x+y+2\) here based on our previous result. We might even go so far as to say \(g(x+1,y+1)+g(x,y) = g(x,y+1)+g(x+1,y)+1\) for all \(x,y\text{.}\) We can easily verify that \(g(1,1)+g(0,0) = 4+0 = 4\) and \(g(0,1)+g(1,0)+1 = 1+2+1 = 4\) for our initial case.
It feels like this induction is still a little unclear. Essentially, I’m doing this weird thing where I’m inducing over \(n\) such that \(x+y \leq n\) to prove the statement for all \(x,y\text{.}\)
