Satz von Fueter-Pólya

Satz der Zahlentheorie
(Weitergeleitet von Cantor-Polynom)

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 definieren. Diese sind genau die bereits von Georg Cantor angegebenen Polynome, die die Gleichmächtigkeit von und zeigen.

Bereits 1873 hat Cantor gezeigt, dass durch das heute so genannte Cantor-Polynom, das folgende Polynom in zwei den Variablen und :

,

eine bijektive Abbildung definiert ist[1], solche Abbildungen nennt man Paarungsfunktionen. Selbstverständlich ist die Funktion , die aus 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 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

Bearbeiten

Ist   ein quadratisches, reelles Polynom in zwei Variablen, dessen Einschränkung auf   eine Bijektion   definiert, so ist

  oder
 .

Bemerkungen

Bearbeiten

Zum Beweis

Bearbeiten

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

Fueter-Pólya-Vermutung

Bearbeiten

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

Bearbeiten

Bezeichnet man mit   die größte ganze Zahl  , so ist

 

eine Bijektion  .[5] Hier handelt es sich nicht um die Einschränkung eines Polynom, da ganzzahlige Division durch 2 verwendet wird.

Höhere Dimensionen

Bearbeiten

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

 

Wenn man diese Binomialkoeffizienten ausmultipliziert, erhält man offenbar ein Polynom  -ten Grades in   Unbestimmten. Es ist ein offenes Problem, ob sich alle Polynome  -ten Grades, die eine Bijektion   definieren, durch Permutation der Variablen dieses Polynoms   ergeben.[7]

Einzelnachweise

Bearbeiten
  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