The Fueter–Pólya theorem, first proved by Rudolf Fueter and George Pólya, states that the only quadratic polynomial pairing functions are the Cantor polynomials.

Introduction

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]

Fueter–Pólya conjecture

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]

Higher dimensions

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]

References