# Symmetric pairing function

I am trying to prove that the integer function: $$\pi(a,b) = a + \frac{b(b-1)}{2} \qquad 1\leq a < b$$ is a pairing function; which amounts to showing that it is injective. (My end-goal would be to use it as a symmetric pairing function.)

AFAICS, proving that it is injective amounts to showing that given four integers $$1\leq a and $$1\leq c, the following implication holds: $$a + \frac{b(b-1)}{2} = c + \frac{d(d-1)}{2} \quad\Rightarrow\quad a=c \quad b=d$$

I have a feeling that proving this involves finding two inequalities on $$a$$ and $$c$$ (or $$b$$ and $$d$$), which can only both be true in case of equality. But I am not sure whether this approach is indeed correct, and if so, what these inequalities would be.

So far, using substitution and re-arranging terms, I have reached the following inequalities, which should hold simultaneously: $$d(d-1) + 2c < b(b+1)\\ b(b-1) + 2a < d(d+1)$$ I like these because of the symmetry between $$b$$ and $$d$$, and the assymmetry $$x(x-1)$$ and $$x(x+1)$$, but I am not sure about the next steps needed to conclude.

Edit: it looks like @Brian_Scott solved this in the comments of this post. However I do not understand the proof just yet.. If anyone could please help flesh it out a little bit more, that would be greatly appreciated.

For $$1\leq a< b$$ and $$1\leq c < d$$, suppose: $$a + \frac{b(b-1)}{2} = c + \frac{d(d-1)}{2}$$ and $$(a,b) \neq (c,d)$$.

Wlog assume $$d>b$$ (if they are equal, then $$a=c$$ and we have a contradiction), then:

$$a -c = \frac{d(d-1)-b(b-1)}{2} = \frac{(d-b)(d+b-1)}{2}\geq \frac{(d+b-1)}{2}> \frac{2b-1}{2}=b-\frac{1}{2}>a$$

Therefore $$c < 0$$, and we have a contradiction.

• I can see why $b - 1/2 > a$, which leads to $c < 0$ and a contradiction; but not $b - 1/2 > a-c$, is that a typo? – Sheljohn Jul 16 at 10:52
• $-c\leq -1$ and $a<b$ so $a-c<b-1<b-\frac{1}{2}$. Contradiction because $a-c<a-c$. But yeah, your idea also works. – AO1992 Jul 16 at 10:57

You can prove this via contradiction. Suppose $$\pi(a,b)=\pi(a',b')$$.

First case $$b=b'$$, show this implies $$a=a'$$.

Second case, $$b < b'$$. Hence $$b' \ge b+1$$. This gives you an inequality for $$a-a'$$ which yields a contradiction with the assumption $$a < b$$.

Edit: As $$b' \ge b+1$$ we have $$\frac{b'(b'-1)}{2}-\frac{b(b-1)}{2}\ge \frac{(b+1)b}{2}-\frac{b(b-1)}{2}=b$$. Now if $$\pi(a,b)=\pi(a',b')$$ this gives $$a-a'>b$$ which contradicts $$a where I used that $$b' > b$$ implies $$a' < a$$.

• The part "This gives you an inequality for $a-a'$" in unclear to me, could you please add a bit more detail? – Sheljohn Jul 16 at 10:48
• $b' \ge b+1$ give you an estimate for the difference between the $b$ and $b'$ terms. The $a$ and $a'$ must make up for that difference. – quarague Jul 16 at 10:52
• This gives you $a-a' \geq (b + b' - 1)/2 \geq b$, leading to $a' < 0$, is that what you mean? – Sheljohn Jul 16 at 11:01