Editing Pairing function (section)

== 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}}