Transforming a function $f: \mathbb N^2 \to A$ to a function $f:\mathbb N\to A$ in a zig-zag manner

Question

We know that the rationals are countable since we can list them via zig-zagging:

$$\begin{matrix} \frac{1}{1} && \frac{1}{2} &\color{red}\to &\frac{1}{3} &&\frac{1}{4} & \color{red}\to & \frac{1}{5}\\ \color{red}\downarrow & \color{red}\nearrow && \color{red}\swarrow && \color{red}\nearrow &&\color{red}\swarrow\\ \frac{2}{1} && \frac{2}{2} && \frac{2}{3} \\ & \color{red}\swarrow && \color{red}\nearrow\\ \frac{3}{1}&&\frac{3}{2}&&& \ddots\\ \color{red}\downarrow&\color{red}\nearrow\\ \frac{4}{1} \end{matrix}$$

Now suppose we have a function $f: \mathbb N^2 \to A$ for some set $A$, where we list the outputs of the function in the same way: $$\begin{matrix} f(1,1) && f(1,2) && f(1,3) && f(1,4) && f(1,5)\\ ~\\ f(2,1) && f(2,2) && f(2,3) \\ ~\\ f(3,1) && f(3,2) &&& \ddots\\ ~\\ f(4,1) \end{matrix}$$

Is there a way to define a function $f' : \mathbb N \to A$ such the resulting sequence of outputs travels along this grid in the same way?

$$\begin{matrix} f(1,1) && f(1,2) &\color{red}\to &f(1,3) &&f(1,4)& \color{red}\to & f(1,5)\\ \color{red}\downarrow & \color{red}\nearrow && \color{red}\swarrow && \color{red}\nearrow &&\color{red}\swarrow\\ f(2,1) && f(2,2) && f(2,3) \\ & \color{red}\swarrow && \color{red}\nearrow\\ f(3,1) && f(3,2) &&& \ddots\\ \color{red}\downarrow&\color{red}\nearrow\\ f(4,1) \end{matrix}$$

That is, defining $f'$ in terms of $f$ such that

$$ f'(1) = f(1,1)\\ f'(2) = f(2,1) \\ f'(3) = f(1,2) \\ f'(4) = f(1,3) \\ f'(5) = f(2,2) \\ f'(6) = f(3,1) \\ \vdots$$

Given $n\in\mathbb N$ I need to find a way to map to the corresponding pair in $\mathbb N^2$, expressing this only in terms of $n$, but I'm not sure how to do this. I appreciate any assistance.

Answer 1

Yes, certainly. In particular, the idea of "zig-zagging" is captured by defining a bijection $$g:\mathbb N\rightarrow \mathbb N^2$$ where $g(i)$ is the $i^{th}$ element in the zig-zag. Then, you are looking for the function $$f'=f\circ g.$$ That is, the function defined as $f'(x)=f(g(x))$. Essentially, you are using $g$ to determine the input to $f$, which causes it to zig-zag through the outputs as you desire. This actually gives you a bijection between the set of functions $\mathbb N^2\rightarrow A$ and the set of functions $\mathbb N\rightarrow A$.

You could write $g$ explicitly if you wanted to. For instance, if we let $T_n=\frac{n(n+1)}2=1+\ldots+n$ be the $n^{th}$ triangular number. We could express $g$ by saying, for $0\leq k \leq n$ $$g(T_n+k)=\begin{cases}(n-k,k) & \text{if }n\text{ odd}\\ (k,n-k) & \text{if }n\text{ even.} \end{cases}$$ This assumes you consider $0\in \mathbb N$, but it's easy enough to shift everything to make it work if you don't like zero being a natural number.

---

If we wanted to write $g$ in a single equation, we could do so. In particular, suppose we want to know $g(x)$. We can figure this out based on the previous equation. We first must write $x=T_n+k$, so must determine $n$ and $k$. In particular, $T_n=\frac{1}2(n+1/2)^2-\frac{1}8$, so we can write $n=\lfloor\sqrt{2x+1/4}-1/2\rfloor.$ Then, $k=x-T_n$. We can also write our expression as $$g(T_n+k)=\left(\left(\frac{(-1)^n+1}2\cdot n + (-1)^nk\right),\left(\frac{(-1)^{n+1}+1}2\cdot n + (-1)^{n+1}k\right)\right).$$ Then, blindly substituting everything in gives: $$g(x)=\left(\left(\frac{(-1)^{\lfloor\sqrt{2x+1/4}-1/2\rfloor}+1}2\cdot (\lfloor\sqrt{2x+1/4}-1/2\rfloor)+(-1)^{\lfloor\sqrt{2x+1/4}-1/2\rfloor}\cdot (x+1/8-\frac{1}2(\lfloor\sqrt{2x+1/4}-1/2\rfloor)^2\right),\left(\frac{(-1)^{\lfloor\sqrt{2x+1/4}-1/2\rfloor+1}+1}2\cdot (\lfloor\sqrt{2x+1/4}-1/2\rfloor)+(-1)^{\lfloor\sqrt{2x+1/4}-1/2\rfloor+1}\cdot (x+1/8-\frac{1}2(\lfloor\sqrt{2x+1/4}-1/2\rfloor)^2\right)\right).$$ However, I think it should be fairly clear why I prefer the other way of writing this function. Note that if we want $\mathbb N$ to not include zero, we have to replace every instance of $n$ in the above formula by $n-1$ and then add one to each coordinate afterwards.

Answer 2

It is a problem of ranking i.e.

What is the point with rank $n$ ?

Ranking (a mathematical art arising from Computer Science) is the fact of putting (denumerable) sets (say $X$, seen as a set of data structures) in explicit bijection with $\mathbb{N}$. Two problems then arise for the bijection $g:\mathbb{N}\to X$ (here $X=\mathbb{N}^2$)

A) Given $P\in X$, what is the "rank" of $P$ (i.e. $n\in \mathbb{N}$ s.t. $g(n)=P$) ?

B) Given $n\in \mathbb{N}$ what is the "position of $P$" ?

If you draw your picture, you see that the visits of your zig-zag curve (starting with $\phi(0)=(0,0),\phi(1)=(1,0)$) to the $x$-axis are for $n=0,1,5,6,14,15$ then for points $(2n^2+3n,2n^2+3n+1)$. Now your pattern is clear in 4 paragraphs.

a) Visits to $x$-axis $$ \phi(2n^2+3n)=(2n,0)\ ;\ \phi(2n^2+3n+1)=(2n+1,0) $$ b) Transition $x$-axis to $y$-axis $$ \phi(2n^2+3n+1+k)=(2n+1-k,k)\ ;\ k=0\ldots 2n+1 $$ c) Visits to $y$-axis $$ \phi(2n^2+5n+2)=(0,2n+1)\ ;\ \phi(2n^2+5n+3)=(0,2n+2) $$ d) Transition $y$-axis to $x$-axis $$ \phi(2n^2+5n+3+k)=(k,2n+2-k)\ ;\ k=0\ldots 2n+2 $$ and again because your reach the $x$-axis at rank $$ 2n^2+5n+3+2n+2=2(n+1)^2+3(n+1) $$ and return to (a) section.

Now, giving a rank $N$, to know $\phi(N)$ amounts to position $N$ w.r.t. the following sectors $$ 2n^2+3n<2n^2+3n+1<\cdots <2n^2+5n+2<2n^2+5n+3<\cdots <2(n+1)^2+3(n+1) $$ The positioning can be achieved solving $2n^2+3n-N=0$ and taking the integer part, here $$ n=\lfloor\frac{-3+\sqrt{9+8N}}{4}\rfloor\ . $$

Late edit Above is just to show you in detail where the ideas came from. If you have to compactly answer to the ranking question ($B$), you can, for instance, use the piecewise description of Milo (with $T_n=\frac{n(n+1)}{2}$). Having to compute $g(N)$, you first compute $$ n=\lfloor\frac{-1+\sqrt{1+9N}}{2}\rfloor\ . $$ you then get $k=N-T_n$ and can apply the dichotomy. If you are chasing the single formula you can even have one with "commutators".

Late late edit Here is, just for the fun, my version of commutators ; first use Iverson_bracket to write $g$ and then (I use here [[??]] in order to differentiate it from maths) convert Iverson brackets as follows $$ [[k\mbox{ is odd}]]=k-2\lfloor\frac{k}{2}\rfloor\ ;\ [[k\mbox{ is even}]]=1-k+2\lfloor\frac{k}{2}\rfloor\ . $$