Fueter–Pólya theorem

In 1873, Georg Cantor showed that the so-called Cantor polynomial[1]

${\displaystyle P(x,y):={\frac {1}{2}}((x+y)^{2}+3x+y)={\frac {x^{2}+2xy+3x+y^{2}+y}{2}}=x+{\frac {(x+y)(x+y+1)}{2}}={\binom {x}{1}}+{\binom {x+y+1}{2}}}$

is a bijective mapping from ${\displaystyle \mathbb {N} ^{2}}$ to ${\displaystyle \mathbb {N} }$. The polynomial given by swapping the variables is also a pairing function.

Fueter was investigating whether there are other quadratic polynomials with this property, and concluded that this is not the case assuming ${\displaystyle P(0,0)=0}$. He then wrote to Pólya, who showed the theorem does not require this condition.[2]

The theorem states that the Cantor polynomial is the only quadratic pairing polynomial of ${\displaystyle \mathbb {N} ^{2}}$ and ${\displaystyle \mathbb {N} }$. The conjecture is that these are the only such pairing polynomials. In a 2018 preprint, Pieter Adriaans has put forward a proof that purports to confirm the conjecture.[5]

A generalization of the Cantor polynomial in higher dimensions is as follows:[6]

${\displaystyle P_{n}(x_{1},\ldots ,x_{n})=\sum _{k=1}^{n}{\binom {k-1+\sum _{j=1}^{k}x_{j}}{k}}=x_{1}+{\binom {x_{1}+x_{2}+1}{2}}+\cdots +{\binom {x_{1}+\cdots +x_{n}+n-1}{n}}}$

The sum of these binomial coefficients yields a polynomial of degree ${\displaystyle n}$ in ${\displaystyle n}$ variables. This is just one of at least ${\displaystyle (n-1)!}$ inequivalent packing polynomials for ${\displaystyle n}$ dimensions.[7]