How to show that $\max(a,b)^2+\max(a,b)+a-b$ is bijective?

Question

How can I show that $f:\mathbb{N}^2 \to \mathbb{N}$ given by $$f(a,b)=\max(a,b)^2+\max(a,b)+a-b$$ is bijective? How could I show it to be injective and surjective? Or does it suffice to give a explicit inverse function? If so, what is the process of inversing this function?

Answer 1

It is helpful to consider the following two cases. When $a\leqslant b$, we have $f(a,b)=b^2+a$, and when $b\leqslant a$ we have $f(a,b)=a^2+2a-b$.

So, here is a way of constructing the inverse function $g:\mathbb{N}\rightarrow\mathbb{N}\times\mathbb{N}$. Let $x\in\mathbb{N}$, and let $y:=\lfloor{\sqrt{x}}\rfloor\in\mathbb{N}$ be maximal such that $y^2\leqslant x$; we want to find $(a,b)\in\mathbb{N}\times\mathbb{N}$ such that $f(a,b)=x$. There are two cases to consider; either $x-y^2\leqslant y$, or $x-y^2>y$. In the first case, let $\fbox{$b=y$}$ and $\fbox{$a=x-y^2$}$. Then $a\leqslant b$ and so $$f(a,b)=b^2+a=y^2+(x-y^2)=x,$$ as desired.

In the second case, let $\fbox{$a=y$}$. We want to find a natural number $b\leqslant a$ such that $f(a,b)=x$. By the formula above, this amounts to finding $b\leqslant a$ such that $y^2+2y-b=x$, so we can just let $\fbox{$b=y^2+2y-x$}$. We need to show that $b\geqslant 0$ and that $b\leqslant a$.

For the first claim, suppose for contradiction that $b<0$. Then $y^2+2y-x<0$, so $y^2+2y<x$, so $(y+1)^2=y^2+2y+1\leqslant x$, contradicting maximality of $y$. For the second claim, suppose that $b>a$, ie that $y^2+2y-x> y$. Then we would have $y^2-x>-y$, and so $x-y^2<y$, a contradiction.

Thus, in sum, we define a function $g:\mathbb{N}\rightarrow\mathbb{N}^2$ by $$x\mapsto \begin{cases} (x-y^2,y) & x-y^2\leqslant y \\ (y,y^2+2y-x) & x-y^2>y\end{cases},$$ where $y=\lfloor{\sqrt{x}}\rfloor$ is maximal such that $y^2\leqslant x$.

---

The paragraphs above show that $f\circ g=\operatorname{id}_\mathbb{N}$, so we just need to show that $g\circ f=\operatorname{id}_{\mathbb{N}\times\mathbb{N}}$. To see this, let $(a,b)\in\mathbb{N}\times\mathbb{N}$. We divide into two cases. First suppose $a\leqslant b$, and let $x:=f(a,b)=b^2+a$. To find $g(x)$, we first need to find $y$ maximal such that $y^2\leqslant x$; we claim that $y=b$. Clearly $b^2\leqslant x$, so to show this claim it suffices to show that $(b+1)^2>x$. We have $(b+1)^2-x=2b+1-a\geqslant b+1>0$, as desired, since $a\leqslant b$. Thus indeed $y=b$. Now, $x-y^2=a\leqslant b=y$, so we are in the first case of the definition of $g$, and thus $g(f(a,b))=g(x)=(x-y^2,y)=(a,b)$, as desired.

Hopefully you should now be able to complete the proof that $g(f(a,b))=(a,b)$ when $a>b$, which is very similar. Once this is done we have proven that $f$ and $g$ are mutual inverses, so that $f$ is indeed a bijection.

Answer 2

Having a look at how it is constructed geometrically is really helping understanding that it is a bijection (I will not prove it in details, but rather show you how to find the inverse):

First point is $f(0,0)=0$ then $f(0,1)=1$ then $f(1,1)=2$ then $f(1,0)=3$ , etc..., and then we start again with a new square of greater size. In the end, we map all points of $\mathbb N^2$ in a sequence (i.e. $\mathbb N$).

We can notice that the "jump" occurs at all points of abscissa $0$.

The corresponding index is $f(0,n)=n^2$

Therefore at index $n^2$ we start an horizontal walk of $n$ points where $a\nearrow$ then a vertical walk of $n$ points where $b\searrow$

Starting from a random integer $x$, we start by writing it $\, x=n^2+y\quad$ where $n=\lfloor\sqrt{x}\rfloor$

Our trajectory is $\, \underbrace{(0,n)}_{y=0}\to\underbrace{(1,n)}_{y=1}\to\cdots\underbrace{(n,n)}_{y=n}\to\underbrace{(n,n-1)}_{y=n+1}\to\cdots\to\underbrace{(n,0)}_{y=n+n}$

In term of $(a,b)$ this gives $\begin{cases}(y,n) & y\le n\\(n,n-(y-n)) & y\ge n\end{cases}\quad$ and we have our inverse.

We can eventually gather everything in a single expression

$\, f^{-1}(x)=(\min(y,n),2n-\max(y,n))$

Or fully expanded:

$$f^{-1}(x)=\bigg(\min(x-\lfloor\sqrt{x}\rfloor^2,\lfloor\sqrt{x}\rfloor)\quad,\quad2\lfloor\sqrt{x}\rfloor-\max(x-\lfloor\sqrt{x}\rfloor^2,\lfloor\sqrt{x}\rfloor)\bigg)$$

Answer 3

Hint: We have $ f(a,b) = (a+1)^2-(b+1) $ when $a\ge b$ and $ f(a,b) = b^2+a $ when $a\le b$.

Surjectiveness comes from considering whether $\lfloor \sqrt n \rfloor = \lfloor \sqrt n +0.5 \rfloor$. See OEIS/A063656 and OEIS/A063657. This also provides a recipe for the inverse.