Satz von Fueter-Pólya

Der Satz von Fueter-Pólya, benannt nach Rudolf Fueter und George Pólya, ist ein Satz aus der Zahlentheorie, nach dem es genau zwei quadratische, reelle Polynome in zwei Unbestimmten gibt, die eine bijektive Funktion ${\displaystyle \mathbb {N} ^{2}\rightarrow \mathbb {N} }$ definieren. Diese sind genau die bereits von Georg Cantor angegebenen Polynome, die die Gleichmächtigkeit von ${\displaystyle \mathbb {N} ^{2}}$ und ${\displaystyle \mathbb {N} }$ zeigen.

Bereits 1873 hat Cantor gezeigt, dass durch das heute so genannte Cantor-Polynom, das folgende Polynom in zwei den Variablen ${\displaystyle x}$ und ${\displaystyle y}$:

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

eine bijektive Abbildung ${\displaystyle \mathbb {N} ^{2}\rightarrow \mathbb {N} }$ definiert ist^[1], solche Abbildungen nennt man Paarungsfunktionen. Selbstverständlich ist die Funktion ${\displaystyle (x,y)\mapsto P(y,x)}$, die aus ${\displaystyle P}$ durch die Vertauschung der Variablen entsteht, ebenfalls eine Paarungsfunktion. Fueter war der Frage nachgegangen, ob es weitere quadratische Polynome mit dieser Eigenschaft gibt, und kam zu dem Ergebnis, dass das nicht der Fall ist, wenn man zusätzlich die Forderung ${\displaystyle P(0,0)=0}$ stellt, wie er Pólya in einem Brief mitteilte. Pólya fand dann einen Beweis, der diese zusätzliche Voraussetzung nicht benötigt, und veröffentlichte dies gemeinsam mit Fueter.^[2]

Formulierung des Satzes

Ist ${\displaystyle P}$ ein quadratisches, reelles Polynom in zwei Variablen, dessen Einschränkung auf ${\displaystyle \mathbb {N} ^{2}}$ eine Bijektion ${\displaystyle \mathbb {N} ^{2}\rightarrow \mathbb {N} }$ definiert, so ist

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

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

Bemerkungen

Zum Beweis

Der Beweis ist überraschend schwierig, er verwendet unter anderem den Satz von Lindemann-Weierstraß über die Transzendenz von ${\displaystyle e^{a}}$ für von 0 verschiedene, algebraische Zahlen ${\displaystyle a}$.^[3] Ein elementarer Zugang findet sich in einer Arbeit von M. A. Vsemirnov.^[4]

Fueter-Pólya-Vermutung

Es ist ein offenes Problem, ob der Satz von Fueter-Pólya richtig bleibt, wenn man auf die Voraussetzung „quadratisch“ verzichtet. Dass dies so sei, ist auch als Fueter-Pólya-Vermutung bekannt.

Andere Paarungsfunktionen

Bezeichnet man mit ${\displaystyle \lfloor a\rfloor }$ die größte ganze Zahl ${\displaystyle \leq a}$, so ist

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

eine Bijektion ${\displaystyle \mathbb {N} ^{2}\rightarrow \mathbb {N} }$.^[5] Hier handelt es sich nicht um die Einschränkung eines Polynom, da ganzzahlige Division durch 2 verwendet wird.

Höhere Dimensionen

Die Verallgemeinerung des Cantor-Polynoms in höheren Dimensionen lautet^[6]

${\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}}}$

Wenn man diese Binomialkoeffizienten ausmultipliziert, erhält man offenbar ein Polynom ${\displaystyle n}$-ten Grades in ${\displaystyle n}$ Unbestimmten. Es ist ein offenes Problem, ob sich alle Polynome ${\displaystyle n}$-ten Grades, die eine Bijektion ${\displaystyle \mathbb {N} ^{n}\rightarrow \mathbb {N} }$ definieren, durch Permutation der Variablen dieses Polynoms ${\displaystyle P}$ ergeben.^[7]

Einzelnachweise

1. G. Cantor: Ein Beitrag zur Mannigfaltigkeitslehre, J. Reine Angew. Math., Band 84 (1878), Seiten 242–258, (Cantors ursprüngliche Funktion behandelte die Menge der natürlichen Zahlen ohne die Null, die hier angegebene Funktion ist so angepasst, dass sie die Null mit einbezieht.)
2. Rudolf Fueter, Georg Pólya: Rationale Abzählung der Gitterpunkte, Vierteljschr. Naturforsch. Ges. Zürich 58 (1923), Seiten 380–386
3. Craig Smoryński: Logical Number Theory I, Springer-Verlag 1991, ISBN 3-540-52236-0, Kapitel I.4 und I.5: The Fueter-Pólya Theorem I/II
4. M. A. Vsemirnov: Zwei elementare Beweise des Fuether-Pólya-Theorems über Paarungspolynome, Algebra i Analiz, Band 13,5 (2001), Seiten 1–15 (russisch) + Errata: M. A. Vsemirnov: Zwei elementare Beweise des Fuether-Pólya-Theorems über Paarungspolynome, Algebra i Analiz, Band 14,5 (2002), Seite 240 (russisch)
5. M. Machtey, P. Young: An Introduction to the General Theory of Algorithms, ISBN 0-444-00226-X, Abschnitt 2.1.3
6. P. Chowla: On some Polynomials which represent every natural number exactly once, Norske Vid. Selsk. Forh. Trondheim (1961), Band 34, Seiten 8–9
7. Craig Smoryński: Logical Number Theory I, Springer-Verlag 1991, ISBN 3-540-52236-0, Kapitel I.4, Vermutung 4.3