Editing Pairing function

{{Short description|Function uniquely mapping two numbers into a single number}}
{{More citations needed|date=August 2021}}

In [[mathematics]], a '''pairing function''' is a process to uniquely encode two [[natural number]]s into a single natural number.

Any pairing function can be used in [[set theory]] to prove that [[integer]]s and [[rational number]]s have the same [[cardinality]] as natural numbers.<ref>{{Harvnb|Pigeon}}: <blockquote>"Pairing functions arise naturally in the demonstration that the cardinalities of the rationals <math>\mathbb{Q}</math> and the nonnegative integers <math>\mathbb{Z}_{\geq 0}</math> are the same, i.e., <math> | \mathbb{Q} | = | \mathbb{Z}_{\geq 0} | =  \aleph_0 </math>, originally due to Cantor."</blockquote></ref>

==Definition==
A '''pairing function''' is a [[bijection]]
:<math>\pi:\mathbb{N} \times \mathbb{N} \to \mathbb{N}.</math>{{sfn|Pigeon}}{{sfn|Lisi|2007}}{{sfn|Regan|1992}}

===Generalization===
More generally, a pairing function on a set <math>A</math> is a function that maps each pair of elements from <math>A</math> into an element of <math>A</math>, such that any two pairs of elements of <math>A</math> are associated with different elements of <math>A</math>,{{sfn|Szudzik|2006}}{{efn|That is, an [[Injective function|injection]] from <math>A^2 \rightarrow A</math>.}} or a bijection from <math>A^2</math> to <math>A</math>.{{sfn|Szudzik|2017}}

Instead of abstracting from the domain, the arity of the pairing function can also be generalized: there exists an n-ary generalized Cantor pairing function on <math>\mathbb{N}</math>.{{sfn|Lisi|2007}}

== Cantor pairing function ==
[[File:Cantor's Pairing Function.svg|alt=A plot of the Cantor pairing function|thumb|The Cantor pairing function assigns one natural number to each pair of natural numbers]]
[[File:Cantor's Pairing Function Plot.svg|alt=A graph of the Cantor pairing function|thumb|Graph of the Cantor pairing function]]
The '''Cantor pairing function''' is a [[primitive recursive function|primitive recursive]] pairing function
:<math>\pi:\mathbb{N} \times \mathbb{N} \to \mathbb{N}</math>
defined by 
:<math>\pi(k_1,k_2) := \frac{1}{2}(k_1 + k_2)(k_1 + k_2 + 1)+k_2</math>
where <math>k_1, k_2\in\{0, 1, 2, 3, \dots\}</math>.{{sfn|Pigeon|loc=Equation 8}}{{bsn|date=November 2024}}

It can also be expressed as <math>\pi(x, y) := \frac{x^2 + x + 2xy + 3y + y^2}{2}</math>.{{sfn|Szudzik|2006}}

It is also strictly monotonic w.r.t. each argument, that is, for all <math>k_1, k_1', k_2, k_2' \in \mathbb{N}</math>, if <math>k_1 < k_{1}'</math>, then <math>\pi(k_1, k_2) < \pi(k_1', k_2)</math>; similarly, if <math>k_2 < k_{2}'</math>, then <math>\pi(k_1, k_2) < \pi(k_1, k_2')</math>.{{Citation needed|date=August 2021}}

The statement that this is the only quadratic pairing function is known as the [[Fueter–Pólya theorem]].<ref>{{harvtxt|Stein|1999|pp=448-452}} cited in {{harvtxt|Pigeon}}.</ref> Whether this is the only polynomial pairing function is still an open question. When we apply the pairing function to {{math|''k''<sub>1</sub>}} and {{math|''k''<sub>2</sub>}} we often denote the resulting number as {{math|⟨''k''<sub>1</sub>, ''k''<sub>2</sub>⟩}}.{{Citation needed|date=August 2021}}

This definition can be inductively generalized to the {{Citation needed span|text=Cantor tuple function|date=August 2021}}
:<math>\pi^{(n)}:\mathbb{N}^n \to \mathbb{N}</math>
for <math>n > 2</math> as
:<math>\pi^{(n)}(k_1, \ldots, k_{n-1}, k_n) := \pi ( \pi^{(n-1)}(k_1, \ldots, k_{n-1}) , k_n)</math>
with the base case defined above for a pair: <math>\pi^{(2)}(k_1,k_2) := \pi(k_1,k_2).</math>{{sfn|Pigeon|loc=Equations 13-7}}

=== Inverting the Cantor pairing function ===
Let <math>z \in \mathbb{N}</math> be an arbitrary natural number. We will show that there exist unique values <math>x, y \in \mathbb{N}</math> such that

:<math> z = \pi(x, y) = \frac{(x + y + 1)(x + y)}{2} + y </math>

and hence that the function {{math|''π(x, y)''}} is invertible. It is helpful to define some intermediate values in the calculation: 
:<math> w = x + y \!</math>
:<math> t = \frac{1}{2}w(w + 1) = \frac{w^2 + w}{2} </math>
:<math> z = t + y \!</math>

where {{math|''t''}} is the [[triangular number|triangle number]] of {{math|''w''}}. If we solve the [[quadratic equation]] 
:<math> w^2 + w - 2t = 0 \!</math>

for {{math|''w''}} as a function of {{math|''t''}}, we get 
:<math> w = \frac{\sqrt{8t + 1} - 1}{2} </math>

which is a strictly increasing and continuous function when {{math|''t''}} is non-negative real. Since 
:<math> t \leq z = t + y < t + (w + 1) =  \frac{(w + 1)^2 + (w + 1)}{2} </math>

we get that 
:<math> w \leq \frac{\sqrt{8z + 1} - 1}{2} < w + 1 </math>

and thus 
:<math> w = \left\lfloor \frac{\sqrt{8z + 1} - 1}{2} \right\rfloor. </math>
where {{math|⌊ ⌋}} is the [[floor function]].
So to calculate {{math|''x''}} and {{math|''y''}} from {{math|''z''}}, we do:
:<math> w = \left\lfloor \frac{\sqrt{8z + 1} - 1}{2} \right\rfloor </math>
:<math> t = \frac{w^2 + w}{2} </math>
:<math> y = z - t \!</math>
:<math> x = w - y. \!</math>

Since the Cantor pairing function is invertible, it must be [[injective function|one-to-one]] and [[surjective function|onto]].{{sfn|Szudzik|2006}}{{Additional citation needed|date=August 2021}}

=== Examples ===

To calculate {{math|''π''(47, 32)}}:
:{{math|47 + 32 {{=}} 79}},
:{{math|79 + 1 {{=}} 80}},
:{{math|79 × 80 {{=}} 6320}},
:{{math|6320 ÷ 2 {{=}} 3160}},
:{{math|3160 + 32 {{=}} 3192}},
so {{math|''π''(47, 32) {{=}} 3192}}.

To find {{math|''x''}} and {{math|''y''}} such that {{math|''π''(''x'', ''y'') {{=}} 1432}}:
:{{math|8 × 1432 {{=}} 11456}},
:{{math|11456 + 1 {{=}} 11457}},
:{{math|{{radic|11457}} {{=}} 107.037}},
:{{math|107.037 − 1 {{=}} 106.037}},
:{{math|106.037 ÷ 2 {{=}} 53.019}},
:{{math|⌊53.019⌋ {{=}} 53}},
so {{math|''w'' {{=}} 53}};
:{{math|53 + 1 {{=}} 54}},
:{{math|53 × 54 {{=}} 2862}},
:{{math|2862 ÷ 2 {{=}} 1431}},
so {{math|''t'' {{=}} 1431}};
:{{math|1432 − 1431 {{=}} 1}},
so {{math|''y'' {{=}} 1}};
:{{math|53 − 1 {{=}} 52}},
so {{math|''x'' {{=}} 52}}; thus {{math|''π''(52, 1) {{=}} 1432}}.{{Citation needed|date=August 2021}}

=== Derivation ===
[[File:Diagonal argument.svg|thumb|right|170px|A diagonally incrementing "snaking" function, from same principles as Cantor's pairing function, is often used to demonstrate the countability of the rational numbers.]]

The graphical shape of Cantor's pairing function, a diagonal progression, is a standard trick in working with [[infinite sequence]]s and [[countability]].{{efn|The term "diagonal argument" is sometimes used to refer to this type of enumeration, but it is ''not'' directly related to [[Cantor's diagonal argument]].{{citation needed|date=August 2021}}}} The algebraic rules of this diagonal-shaped function can verify its validity for a range of polynomials, of which a quadratic will turn out to be the simplest, using the [[method of induction]]. Indeed, this same technique can also be followed to try and derive any number of other functions for any variety of schemes for enumerating the plane.

A pairing function can usually be defined inductively – that is, given the {{math|''n''}}th pair, what is the {{math|(''n''+1)}}th pair? The way Cantor's function progresses diagonally across the plane can be expressed as
:<math>\pi(x,y)+1 = \pi(x-1,y+1)</math>.

The function must also define what to do when it hits the boundaries of the 1st quadrant – Cantor's pairing function resets back to the x-axis to resume its diagonal progression one step further out, or algebraically:
:<math>\pi(0,k)+1 = \pi(k+1,0)</math>.

Also we need to define the starting point, what will be the initial step in our induction method: {{math|''π''(0, 0) {{=}} 0}}.

Assume that there is a quadratic 2-dimensional polynomial that can fit these conditions (if there were not, one could just repeat by trying a higher-degree polynomial). The general form is then
:<math>\pi(x,y) = ax^2+by^2+cxy+dx+ey+f</math>.

Plug in our initial and boundary conditions to get {{math|''f'' {{=}} 0}} and:
:<math>bk^2+ek+1 = a(k+1)^2+d(k+1)</math>,

so we can match our {{math|''k''}} terms to get
:{{math|''b'' {{=}} ''a''}}
:{{math|''d'' {{=}} 1-''a''}}
:{{math|''e'' {{=}} 1+''a''}}.

So every parameter can be written in terms of {{math|''a''}} except for {{math|''c''}}, and we have a final equation, our diagonal step, that will relate them:
:<math>\begin{align}
  \pi(x,y)+1 &= a(x^2+y^2) + cxy + (1-a)x + (1+a)y + 1 \\
    &= a((x-1)^2+(y+1)^2) + c(x-1)(y+1) + (1-a)(x-1) + (1+a)(y+1).
  \end{align}</math>

Expand and match terms again to get fixed values for {{math|''a''}} and {{math|''c''}}, and thus all parameters:
:{{math|''a'' {{=}} {{sfrac|1|2}} {{=}} ''b'' {{=}} ''d''}}
:{{math|''c'' {{=}} 1}}
:{{math|''e'' {{=}} {{sfrac|3|2}}}}
:{{math|''f'' {{=}} 0}}.

Therefore
:<math>\begin{align}
  \pi(x,y) &= \frac{1}{2}(x^2+y^2) + xy + \frac{1}{2}x + \frac{3}{2}y \\ 
    &= \frac{1}{2}(x+y)(x+y+1) + y,
  \end{align}</math>

is the Cantor pairing function, and we also demonstrated through the derivation that this satisfies all the conditions of induction.{{Citation needed|date=August 2021}}

== Shifted Cantor pairing function ==
The following pairing function: <math>\langle i, j\rangle := \frac{1}{2}(i+j-2)(i+j-1) + i</math>, where <math>i, j\in\{1, 2, 3, \dots \}</math>.<ref>{{harvtxt|Hopcroft|Ullman|1979|p=169}} cited in {{harv|Pigeon|loc=Equations 2, 3}}.</ref> is the same as the Cantor pairing function, but shifted to exclude 0 (i.e., <math>i=k_2+1</math>, <math>j=k_1+1</math>, and <math>\langle i, j\rangle - 1 = \pi(k_2,k_1)</math>).{{sfn|Pigeon|loc=Equation 8}} It was used in the popular computer textbook of Hopcroft and Ullman (1979).

== Other pairing functions ==
The function <math>P_2(x, y):= 2^x(2y + 1) - 1</math> is a pairing function.

In 1990, Regan proposed the first known pairing function that is computable in [[linear time]] and with constant space (as the previously known examples can only be computed in linear time if [[Fast multiplication|multiplication can be too]], which is doubtful). In fact, both this pairing function and its inverse can be computed with finite-state transducers that run in real time.{{Clarify|date=August 2021}} In the same paper, the author proposed two more monotone pairing functions that can be [[Online algorithm|computed online]] in linear time and with [[logarithmic space]]; the first can also be computed offline with zero space.{{sfn|Regan|1992}}{{Clarify|reason=What is "zero space"?|date=August 2021}}

In 2001, Pigeon proposed a pairing function based on [[bit-interleaving]], defined recursively as:

:<math>\langle i,j\rangle_{P}=\begin{cases}
T & \text{if}\ i=j=0;\\
\langle\lfloor i/2\rfloor,\lfloor j/2\rfloor\rangle_{P}:i_0:j_0&\text{otherwise,}
\end{cases}</math>

where <math>i_0</math> and <math>j_0</math> are the [[Least Significant Bit|least significant bits]] of ''i'' and ''j'' respectively.{{sfn|Pigeon|loc=Equation 12}}{{bsn|date=November 2024}}

In 2006, Szudzik proposed a "more elegant" pairing function defined by the expression:
:<math>\operatorname{ElegantPair}[x, y] := \begin{cases}
y^2 + x&\text{if}\ x < y,\\
x^2 + x + y&\text{if}\ x \ge y.\\
\end{cases}</math>
Which can be unpaired using the expression:
:<math>\operatorname{ElegantUnpair}[z] := \begin{cases}
\left\{ z - \lfloor\sqrt{z}\rfloor^2, \lfloor\sqrt{z}\rfloor \right\}
& \text{if }z - \lfloor\sqrt{z}\rfloor^2 < \lfloor\sqrt{z}\rfloor,
\\
\left\{ \lfloor\sqrt{z}\rfloor, z - \lfloor\sqrt{z}\rfloor^2 - \lfloor\sqrt{z}\rfloor \right\}
& \text{if }z - \lfloor\sqrt{z}\rfloor^2\geq\lfloor\sqrt{z}\rfloor.
\end{cases}</math>
(Qualitatively, it assigns consecutive numbers to pairs along the edges of squares.) This pairing function orders [[SK combinator calculus]] expressions by depth.{{sfn|Szudzik|2006}}{{Clarify|date=August 2021}}
This method is the mere application to <math>\N</math> of the idea, found in most textbooks on Set Theory,<ref>See for instance {{harvtxt|Jech|2006|p=30}}.</ref>
used to establish <math>\kappa^2=\kappa</math> for any infinite cardinal <math>\kappa</math> in [[Zermelo–Fraenkel set theory|ZFC]].
Define on <math>\kappa\times\kappa</math> the binary relation
:<math>(\alpha,\beta)\preccurlyeq(\gamma,\delta) \text{ if either } \begin{cases}
(\alpha,\beta) = (\gamma,\delta),\\[4pt]
\max(\alpha,\beta) < \max(\gamma,\delta),\\[4pt]
\max(\alpha,\beta) = \max(\gamma,\delta)\ \text{and}\ \alpha<\gamma,\text{ or}\\[4pt]
\max(\alpha,\beta) = \max(\gamma,\delta)\ \text{and}\ \alpha=\gamma\ \text{and}\ \beta<\delta.
\end{cases}</math>
<math>\preccurlyeq</math> is then shown to be a well-ordering such that every element has <math>{}<\kappa</math> predecessors, which implies that <math>\kappa^2=\kappa</math>.
It follows that <math>(\N\times\N,\preccurlyeq)</math> is isomorphic to <math>(\N,\leqslant)</math> and the pairing function above is nothing more than the enumeration of integer couples in increasing order.{{efn|See also [[Talk:Tarski's theorem about choice#Proof of the converse]].}}

==Citations==
===Notes===
{{notelist}}

===Footnotes===
{{reflist}}

===References===
* {{MathWorld|urlname=PairingFunction|author=Steven Pigeon|title=Pairing Function|ref={{SfnRef|Pigeon}}}}{{Sfn whitelist|CITEREFPigeon}}
* {{cite journal|journal=Le Matematiche |first=Meri |last=Lisi |title=Some Remarks on the Cantor Pairing Function |volume=LXII |year=2007 |pp=55-65 |url=https://lematematiche.dmi.unict.it/index.php/lematematiche/article/view/14/13}}
* {{Cite journal|date=December 1992 |title=Minimum-Complexity Pairing Functions|journal=Journal of Computer and System Sciences|language=en|volume=45|issue=3|pages=285–295|doi=10.1016/0022-0000(92)90027-G|issn=0022-0000|doi-access=free|last1=Regan|first1=Kenneth W.}}
* {{Cite web|last=Szudzik|first=Matthew|year=2006|title=An Elegant Pairing Function|url=http://szudzik.com/ElegantPairing.pdf|url-status=live|archive-url=https://web.archive.org/web/20111125104326/http://szudzik.com/ElegantPairing.pdf|archive-date=25 November 2011|access-date=16 August 2021|website=szudzik.com}}
* {{cite arXiv|last=Szudzik|first=Matthew P.|date=1 June 2017|title=The Rosenberg-Strong Pairing Function|class=cs.DM|eprint=1706.04129}}
* {{cite book |first=Thomas |last=Jech |date=2006 |title=Set Theory |edition=The Third Millennium |series=Springer Monographs in Mathematics |doi=10.1007/3-540-44761-X |publisher=Springer-Verlag |isbn=3-540-44085-2}}
* {{cite book
  | last1 = Hopcroft
  | first1 = John E.
  | last2 = Ullman
  | first2 = Jeffrey D.
  | title = [[Introduction to Automata Theory, Languages, and Computation]]
  | publisher = Addison-Wesley
  | edition = 1st
  | year = 1979
  | isbn = 0-201-02988-X
}}
* {{cite book|title=Mathematics: The Man-Made Universe |last=Stein |first=Sherman K. |edition=3rd |publisher=Dover |year=1999 |isbn=9780486404509}}


[[Category:Set theory]]
[[Category:Georg Cantor]]
[[Category:Functions and mappings]]