Theorem of Fueter-Pólya

The theorem of Fueter-Pólya , named after Rudolf Fueter and George Pólya , is a theorem from number theory , according to which there are exactly two quadratic, real polynomials in two indeterminates that define a bijective function . These are exactly the polynomials already given by Georg Cantor , which show the equality of and . ${\displaystyle \mathbb {N} ^{2}\rightarrow \mathbb {N} }$ ${\displaystyle \mathbb {N} ^{2}}$ ${\displaystyle \mathbb {N} }$

As early as 1873, Cantor showed that what is known today as the Cantor polynomial, the following polynomial in two of the variables and : ${\displaystyle x}$ ${\displaystyle y}$

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

a bijective mapping is defined, such maps are called pairing functions. Of course, the function that results from swapping the variables is also a pairing function. Fueter had investigated the question of whether there are other quadratic polynomials with this property, and came to the conclusion that this is not the case if one also makes the requirement , as he informed Pólya in a letter. Pólya then found evidence that did not need this additional requirement and published it together with Fueter. ${\displaystyle \mathbb {N} ^{2}\rightarrow \mathbb {N} }$ ${\displaystyle (x,y)\mapsto P(y,x)}$ ${\displaystyle P}$ ${\displaystyle P(0,0)=0}$

Formulation of the sentence

If a quadratic, real polynomial in two variables whose restriction to a bijection is defined, then is ${\displaystyle P}$ ${\displaystyle \mathbb {N} ^{2}}$ ${\displaystyle \mathbb {N} ^{2}\rightarrow \mathbb {N} }$

${\displaystyle P(x,y)={\frac {1}{2}}\left((x+y)^{2}+3x+y\right)}$ or

${\displaystyle P(x,y)={\frac {1}{2}}\left((x+y)^{2}+3y+x\right)}$.

Remarks

For proof

The proof is surprisingly difficult, he uses, among other things, the theorem of Lindemann-Weierstrass about the transcendence of for algebraic numbers different from 0 . An elementary approach can be found in a work by MA Vsemirnov. ${\displaystyle e^{a}}$ ${\displaystyle a}$

Fueter-Pólya conjecture

It is an open problem whether the Fueter-Pólya theorem remains correct if one waives the requirement “quadratic”. That this is so is also known as the Fueter-Pólya conjecture.

Other pairing functions

If one denotes the largest integer , then is ${\displaystyle \lfloor a\rfloor }$ ${\displaystyle \leq a}$

${\displaystyle f(x,y):=\left(\left\lfloor {\frac {x+1}{2}}\right\rfloor +y\right)^{2}+x}$

a bijection . This is not a polynomial restriction as it uses whole number division by 2. ${\displaystyle \mathbb {N} ^{2}\rightarrow \mathbb {N} }$

Higher dimensions

The generalization of the Cantor polynomial in higher dimensions is

${\displaystyle P(x_{1},\ldots ,x_{n})=x_{1}+{\binom {x_{1}+x_{2}+1}{2}}+\ldots +{\binom {x_{1}+\ldots +x_{n}+n-1}{n}}}$

If you multiply these binomial coefficients , you obviously get a polynomial -th degree in indeterminates. It is an open problem whether all -th degree polynomials that define a bijection result from permutation of the variables of this polynomial . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \mathbb {N} ^{n}\rightarrow \mathbb {N} }$ ${\displaystyle P}$

Individual evidence

1. ↑ G. Cantor: A contribution to the theory of manifolds , J. Reine Angew. Math., Volume 84 (1878), pages 242-258, (Cantor's original function treated the set of natural numbers without the zero, the function given here is adapted to include the zero.)
2. ^ Rudolf Fueter, Georg Pólya: Rational counting of grid points , Vierteljschr. Natural science. Ges. Zurich 58 (1923), pages 380-386
3. ↑ Craig Smoryński: Logical Number Theory I , Springer-Verlag 1991, ISBN 3-540-52236-0 , Chapters I.4 and I.5: The Fueter-Pólya Theorem I / II
4. ↑ MA Vsemirnov: Two elementary proofs of the Fuether-Pólya theorem on pairing polynomials, Algebra i Analiz, Volume 13.5 (2001), pages 1–15 (Russian) + Errata: MA Vsemirnov: Two elementary proofs of the Fuether-Pólya theorem on pairing polynomials, Algebra i Analiz, Volume 14.5 (2002), page 240 (Russian)
5. ↑ M. Machtey, P. Young: An Introduction to the General Theory of Algorithms , ISBN 0-444-00226-X , Section 2.1.3
6. ↑ P. Chowla: On some polynomials which represent every natural number exactly once , Norske Vid. Selsk. Forh. Trondheim (1961), Volume 34, Pages 8-9
7. ↑ Craig Smoryński: Logical Number Theory I , Springer-Verlag 1991, ISBN 3-540-52236-0 , Chapter I.4, assumption 4.3