1
$\begingroup$

Towards the end of this, how do I get

$$ \frac{\sqrt{8z + 1} - 1}{2} < w + 1 $$

Here $w = x + y \geq 0, t = (w^2 + w)/2 , z = t + w, x,y \in \mathbb N_{\geq 0}$.

Thanks.

3 Answers 3

1

In that Wikipedia article it is shown that inverse function to $$f(w)=\frac{w^2+w}2$$ is the function $$f^{-1}(t)=\frac{\sqrt{8t+1}-1}2.$$

These functions are strictly increasing on $[0,\infty)$.

So $$f(w)\le z


I'll add the link to the current revision of the Wikipedia article, so that this post makes sense even in the case the article is changed.

  • 0
    And how did you get $z = f(w) + y < f(w+1)$?2012-10-28
  • 1
    If I understand their proof correctly, you have the sequence $f(0)=0$z$ there is exactly one $w$ such that $f(w)\le z < f(w+1)$. Then you can find $y$ such that $z=f(w)+y$. – 2012-10-28
4

Rather than follow the Wikipedia derivation, I’ve produced my own; it’s essentially the same, but I think that it may be a bit easier to follow.

Let $T_n=\binom{n+1}2=\sum_{k=1}^nk$, the $n$=th triangular number. We can write the pairing function as $$\langle x,y\rangle=\frac{(x+y)(x+y+1)}2+y=T_{x+y}+y\;,$$ making it clear that every $\langle x,y\rangle$ is of the form $T_n+k$ for some $n,k\in\Bbb N$ with $k\le n$.

Lemma. Every natural number has a unique decomposition of this form.

Proof. To prove existence, fix $m\in\Bbb N$, let $n\in\Bbb N$ be maximal such that $T_n\le m$, and let $k=m-T_n$. Then $T_n\le m

To prove uniqueness, suppose that $T_m+i=T_n+k$, where $i\le m$ and $k\le n$, and without loss of generality assume that $m\le n$. Then $$i+\sum_{j=1}^mj=k+\sum_{j=1}^nj\;,$$ so $$i-k=\sum_{j=m+1}^nj\;.\tag{1}$$ If $mi-k\ge m+1$, so $m=n$, $i-k=0$, and $i=k$. $\dashv$

Inverting the pairing function is then simply a matter of calculating the unique $n$ and $k$ such that $z=T_n+k$ and $k\le n$: once $n$ and $k$ are known, just set $y=k$ and $x=n-k$.

From the proof of the lemma it’s clear that finding $n$ and $k$ boils down to finding the maximal $n$ such that $T_n\le z$, i.e., the unique $n$ such that

$$\frac12n(n+1)\le z<\frac12(n+1)(n+2)\tag{1}\;.$$

The first inequality in $(1)$ can be rewritten $n^2+n\le2z$, or $n^2+n-2z\le0$; over $\Bbb R$ this has the solution

$$\frac{-1-\sqrt{1+8z}}2\le n\le\frac{-1+\sqrt{1+8z}}2\tag{2}$$

from the quadratic formula. The first inequality in $(2)$ says nothing useful, since $n\ge 0$ anyway.

Similarly, the second inequality in $(1)$ becomes $n^2+3n+2-2z>0$, with the solution

$$n<\frac{-3-\sqrt{1+8z}}2\quad\text{or}\quad n>\frac{-3+\sqrt{1+8z}}2\;,\tag{3}$$

where the first alternative is plainly impossible. Combining the useful parts of $(2)$ and $(3)$, we see that

$$\frac{-3+\sqrt{1+8z}}2

Let $$\alpha=\frac{-1+\sqrt{1+8z}}2\;;$$ then $(4)$ just says that $\alpha-1

The computation of the inverse is now essentially complete. Given $z\in\Bbb N$, let

$$n=\left\lfloor\frac{-1+\sqrt{1+8z}}2\right\rfloor\;;$$

then $z=\langle x,y\rangle$, where $y=z-T_n=z-\frac12n(n+1)$ and $x=n-y$.

2

Actually \begin{eqnarray*} z<\frac{(w+1)(w+2)}{2}&\Leftrightarrow&2z