Continued from last week...
Solution.
In one of my previous sessions, I implemented this map \(f: \mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}\) that I’m looking for in Python as follows:
1
github.com/rruff82/LS-Categories/blob/main/assets/notebooks/numbertheory.pydef from_zig_zag_N(n):
# inverse of reverse_zig_zag
# see also https://en.wikipedia.org/wiki/Pairing_function
w = floor((sqrt(8*n+1)-1)/2)
t = (w*w+w)/2
x = n-t
y = w-x
return (int(x),int(y))The only difference is that I’ll need to swap \(x\) and \(y\) to match the book’s northwest ordering.
Given \(g(x,y)
= \frac{1}{2}(x^2+2xy+y^2+x+3y)
\text{,}\) we can compose with \(f\) one of two ways: \(f \circ g: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}\) or \(g \circ f: \mathbb{N} \rightarrow \mathbb{N}\text{.}\)
Performing the necessary swap from my code above, lets define \(y = n - t\) and \(x = w - y\) where \(w = \lfloor \frac{\sqrt{8n+1}-1}{2} \rfloor\) and \(t = \frac{w^2+w}{2}\text{.}\) Applying these to \(g(x,y)\text{:}\)
\begin{equation*}
\frac{1}{2}(x^2+2xy+y^2+x+3y)
\end{equation*}
\begin{equation*}
= \frac{1}{2}(x+y)(x+y+1)+y
\end{equation*}
\begin{equation*}
= \frac{1}{2}((w-y)+y)((w-y)+y+1)+y
\end{equation*}
\begin{equation*}
= \frac{1}{2}w(w+1)+y
\end{equation*}
\begin{equation*}
= \frac{1}{2}(w)(w+1)+(n - t)
\end{equation*}
\begin{equation*}
= \frac{1}{2}(w)(w+1) + n - \frac{w^2+w}{2}
\end{equation*}
\begin{equation*}
= n
\end{equation*}
That shouldn’t be suprising given that I proved \(g \circ f = 1_\mathbb{N}\) last week using induction. What about the other composition? I’m still not quite confident I’ve established that \(f \circ g = 1_{\mathbb{N} \times \mathbb{N}}\text{.}\)
Maybe it might be helpful to evaluate \(f(n)\) for some small values of \(n\text{.}\) We can think of \(w,t,x,y\) as maps \(\mathbb{N} \rightarrow \mathbb{N}\text{.}\)
For \(n=0\text{:}\)
\begin{equation*}
w(0) = \lfloor \frac{\sqrt{8 \cdot 0+1}-1}{2} \rfloor
= \lfloor \frac{\sqrt{1}-1}{2} \rfloor = \lfloor \frac{0}{2} \rfloor = 0
\end{equation*}
\begin{equation*}
t(0) = \frac{0^2+0}{2} = 0
\end{equation*}
\begin{equation*}
y(0) = n-t(0) = 0-0 = 0
\end{equation*}
\begin{equation*}
x(0) = w(0)-y(0) = 0-0 = 0
\end{equation*}
For \(n=1\text{:}\)
\begin{equation*}
w(1) = \lfloor \frac{\sqrt{8 \cdot 1+1}-1}{2} \rfloor
= \lfloor \frac{\sqrt{9}-1}{2} \rfloor = \lfloor \frac{3-1}{2} \rfloor = 1
\end{equation*}
\begin{equation*}
t(1) = \frac{1^2+1}{2} = \frac{2}{2} = 1
\end{equation*}
\begin{equation*}
y(1) = 1-t(1) = 1-1 = 0
\end{equation*}
\begin{equation*}
x(1) = w(1)-y(1) = 1-0 = 1
\end{equation*}
For \(n=2\text{:}\)
\begin{equation*}
w(2) = \lfloor \frac{\sqrt{8 \cdot 2+1}-1}{2} \rfloor
= \lfloor \frac{\sqrt{17}-1}{2} \rfloor = 1
\end{equation*}
\begin{equation*}
t(2) = 1
\end{equation*}
\begin{equation*}
y(2) = 2-t(2) = 2-1 = 1
\end{equation*}
\begin{equation*}
x(2) = w(2)-y(2) = 1-1 = 0
\end{equation*}
For \(n=3\text{:}\)
\begin{equation*}
w(3) = \lfloor \frac{\sqrt{8 \cdot 3+1}-1}{2} \rfloor
= \lfloor \frac{\sqrt{25}-1}{2} \rfloor = \lfloor \frac{4}{2} \rfloor = 2
\end{equation*}
\begin{equation*}
t(3) = \frac{2^+2}{2} = \frac{6}{2} = 3
\end{equation*}
\begin{equation*}
y(3) = 3-t(3) = 3-3 = 0
\end{equation*}
\begin{equation*}
x(3) = w(3)-y(3) = 2-0 = 2
\end{equation*}
For \(n=4\text{:}\)
\begin{equation*}
w(4) = \lfloor \frac{\sqrt{8 \cdot 4+1}}{2} \rfloor
= \lfloor \frac{\sqrt{33}}{2} \rfloor = 2
\end{equation*}
\begin{equation*}
t(4) = 3
\end{equation*}
\begin{equation*}
y(4) = 4-t(4) = 4-3 = 1
\end{equation*}
\begin{equation*}
x(4) = w(4)-y(4) = 2-1 = 1
\end{equation*}
For \(n=5\text{:}\)
\begin{equation*}
w(5) = \lfloor \frac{\sqrt{8 \cdot 5+1}-1}{2} \rfloor
= \lfloor \frac{\sqrt{41}-1}{2} \rfloor = 2
\end{equation*}
\begin{equation*}
t(5) = 3
\end{equation*}
\begin{equation*}
y(5) = 5-t(5) = 5-3 = 2
\end{equation*}
\begin{equation*}
x(5) = w(5)-y(5) = 2-2 = 0
\end{equation*}
For \(n=6\text{:}\)
\begin{equation*}
w(6) = \lfloor \frac{\sqrt{8 \cdot 6+1}}{2} \rfloor
= \lfloor \frac{\sqrt{49}-1}{2} \rfloor = 3
\end{equation*}
\begin{equation*}
t(6) = \frac{3^2+3}{2} = \frac{12}{2} = 6
\end{equation*}
\begin{equation*}
y(6) = 6-t(5) = 6-6 = 0
\end{equation*}
\begin{equation*}
x(6) = 3-y(6) = 3-0 = 3
\end{equation*}
I’m beginning to see some patterns here. The sequence \(w(n)\) goes \(\{0,1,1,2,2,2,3,3,3,3,4,....\}\) which has \(n+1\) copies of each \(n\text{.}\) The sequence \(t(n)\) goes \(\{0,1,1,3,3,3,6,6,6,6,10,...\}\) are matching \(n+1\) repeated copies of my “triangular numbers” \(\{0,1,3,6,10,...\}\text{.}\) Those numbers are important because they satisfy \(\frac{n(n+1)}{2} = \sum\limits^n_{k=0} k\text{.}\) Each triangular number \(T_k\) is determined by the sum of some consecutive set of natural numbers, so we should have \(T_{k+1} = T_k + k+1\) for all \(k \in \mathbb{N}\text{.}\) What’s unclear to me is where \(w\) comes from.
Given a map \(w = \lfloor \frac{\sqrt{8n+1}-1}{2} \rfloor\text{,}\) we basically have a compound inequality which needs to be satisfied:
\begin{equation*}
\frac{\sqrt{8n+1}-1}{2} \leq w < \frac{\sqrt{8n+1}-1}{2}+1
\end{equation*}
We can rewrite \(\frac{\sqrt{8n+1}-1}{2}+1\) into \(\frac{\sqrt{8n+1}+1}{2}\text{:}\)
\begin{equation*}
\frac{\sqrt{8n+1}-1}{2} \leq w < \frac{\sqrt{8n+1}+1}{2}
\end{equation*}
Multiply everything by \(2\text{:}\)
\begin{equation*}
\sqrt{8n+1}-1 \leq 2 w < \sqrt{8n+1}+1
\end{equation*}
Add \(1\text{:}\)
\begin{equation*}
\sqrt{8n+1} \leq 2 w + 1< \sqrt{8n+1}+2
\end{equation*}
For \(k \geq 1\text{,}\) \(k^2 \geq k\) so our inequality should hold if we square everything:
\begin{equation*}
8n+1 \leq (2w+1)^2 < (8n+1) + 4\sqrt{8n+1} + 4
\end{equation*}
\begin{equation*}
8n+1 \leq 4w^2 + 4w + 1 < 8n+5 + 4\sqrt{8n+1}
\end{equation*}
\begin{equation*}
8n \leq 4w^2 + 4w < 8n+4 + 4\sqrt{8n+1}
\end{equation*}
\begin{equation*}
n \leq \frac{w^2 + w}{2} < n+\frac{1+\sqrt{8n+1}}{2}
\end{equation*}
The expression \(\frac{1+\sqrt{8n+1}}{2}\) is basically \(w+1\text{,}\) so...
\begin{equation*}
n \leq \frac{w^2 + w}{2} < n+w+1
\end{equation*}
This seems very similar to the definition of \(T_{k+1}\) above. Maybe that’s the key to finishing my induction proof from last week?
It’s pretty clear that \(w\) is not invertable since output values repeat for the floor function, but mabye solving \(\omega = \frac{\sqrt{8n+1}-1}{2}\) for \(n\) might give me some clue to go forward.
\begin{equation*}
\omega = \frac{\sqrt{8n+1}-1}{2}
\end{equation*}
\begin{equation*}
2 \omega = \sqrt{8n+1}-1
\end{equation*}
\begin{equation*}
2 \omega + 1 = \sqrt{8n+1}
\end{equation*}
\begin{equation*}
(2 \omega + 1)^2 = (\sqrt{8n+1})^2
\end{equation*}
\begin{equation*}
4 \omega^2 +4\omega + 1 = 8 n + 1
\end{equation*}
\begin{equation*}
4 \omega^2 +4\omega= 8 n
\end{equation*}
\begin{equation*}
\frac{\omega^2 +\omega}{2} = n
\end{equation*}
And our triangular numbers show up again! So our choice of \(w\) is basically defined by the unique inverse of the trianglular numbers in the reals.
The final part of this question asks why the map \(f_1\) can’t be a polynomial, and maybe it’s because those triangular numbers \(T_n\) have a unique inverse in \(\mathbb{R}_{\geq 0}\) that map is non-polynomial in nature.
