Autor: Marcelo Escudeiro Hernandes
Übersetzt von Herbert Glaser, Kristin Landeck und Hans-Georg Weigand (Universität Würzburg)
Nach dem berühmten „Vier-Farben-Satz“ benötigen wir nur 4 Farben, um eine Landkarte so zu färben, dass benachbarte Gebiete nicht dieselbe Farbe haben. Unter Verwendung von Polynomgleichungen und Gröbner-Basen können wir berechnen, wann drei Farben für das Färben einer ausgewählten Landkarte ausreichen.
1. Das Einfärben von Landkarten
Der berühmte Vier-Farben-Satz (1) besagt, dass alle Landkarten, ob in der Ebene oder auf der Kugel, mit vier verschiedenen Farben so gefärbt werden können, dass benachbarte Gebiete nicht dieselbe Farbe haben. Es ist leicht, Landkarten zu entwerfen, die nicht mit drei Farben ausgemalt werden können, und auch solche, bei denen dies möglich ist. Um zu entscheiden, ob drei Farben zum Färben einer speziellen Landkarte ausreichen, analysiert man ein System von Polynomen, das die Landkarte repräsentiert. Jede Farbe wird durch eine komplexe kubische Einheitswurzel und jedes Gebiet wird durch eine Variable so codiert, dass die Variable nur einen der drei Werte annehmen kann, der für eine der drei Farben steht. Somit erhalten wir die Bedingung für jedes Gebiet.
Für zwei Gebiete, vertreten durch und , gilt die Bedingung . Wenn und benachbarte Regionen vertreten, und d benachbarte Regionen nicht die gleiche Farbe haben können, gilt , d.h. . Auf diese Weise kann eine Landkarte mit Gebieten genau dann mit drei Farben gefärbt werden, wenn das System von Polynomgleichungen
(1)
für mindestens eine Lösung besitzt, wobei , angrenzende Gebiete vertreten.
Beispiel 1
Wir betrachten folgende Landkarte:
Ist es möglich diese Landkarte mit Farben auszumalen?
Um diese Frage beantworten zu können, müssen wir überprüfen, ob das polynomiale Gleichungssystem (1) mit und
gelöst werden kann.
2. Systeme von Polynomgleichungen
Viele mathematische Probleme lassen sich mit polynomialen Gleichungssystemen lösen. Wenn die Gleichungen linear sind, können wir sie mit dem Gaußschen Elimininationsverfahren durch ein äquivalentes System ersetzen, dessen Lösung aber einfacher ist. Für nicht lineare Gleichungssysteme beschreiben wir im Folgenden ein analoges Verfahren.
Sei die Menge der Polynome mit komplexen Koeffizienten in den Variablen . Für eine Menge von Polynomen aus beschreiben wir das erzeugende Ideal durch
Ein Satz von David Hilbert <http://www.mat.uniroma1.it/people/manetti/dispense/nullstellen.pdf”>(2), nämlich der Hilbertsche Nullstellensatz besagt, dass das System genau dann eine (komplexe) Lösung besitzt, wenn gilt. Wie kann diese Bedingung überprüft werden?
Es ist einfach zu zeigen, dass die zwei Gleichungssysteme und , mit die gleiche Lösung haben und die Bedingung
(2)
erfüllen.
Die Strategie, um ein System zu lösen, besteht also darin, Polynome zu finden, die die Bedingung (2) erfüllen, und mit denen wir testen können, ob ein gegebenes zu dem Ideal gehört oder nicht. Natürlich sollen die Lösungen von (2) auch einfacher zu berechnen sein.
Die theoretische Existenz einer solchen Menge wurde während der ersten Hälfte des letzten Jahrhunderts von dem Mathematiker Wolfgang Gröbner nachgewiesen. Einige Jahre später entwickelte sein Student Bruno Buchberger einen Algorithmus zur Berechnung dieser Menge, die Gröbner-Basen genannt werden. Der Buchberger Algorithmus ist eines der wichtigsten Werkzeuge in der Algebra.
Wenn das Ideal die Form hat, gilt genau dann, wenn , d.h. ist durch teilbar. Analog gilt genau dann, wenn gilt , Diese Bedingung lässt etwas Ähnliches vermuten, wenn wir durch dividieren. Und in der Tat können wir ein Polynom in mehreren Variablen durch endlich viele Polynome teilen, wenn die Monome in einer besonderen Art und Weise geordnet sind.
3. Gröbner-Basen
Ein Monom aus hat die Form , wobei natürliche Zahlen sind. Das Monom wird mit bezeichnet. Den Divisionsalgorithmus können wir anwenden bei den Ordnungen auf den Monomen aus , für die und gilt, immer dann wenn erfüllt ist.
Ein Beispiel ist die lexikographische Ordnung mit , wenn ein mit derauf existiert, dass und für alle .
Fixiert man eine Ordnung für die Monome, so wird das größte Monom eines Polynoms der Leitterm von genannt und mit .
Eine Gröbner-Basis eines Ideals , bezüglich einer vorgegebenen monomialen Ordnung, ist nach Definition jede beliebige Menge aus Elementen von , wobei der Leitterm eines jeden Elementes von durch den Leitterm eines Elements von teilbar ist. Man kann zeigen, dass jede Gröbner-Basis von die Bedingung (2) erfüllt.
Folglich gilt genau dann, wenn eine Gröbner-Basis von existiert, die eine nicht negative Konstante für alle aus enthält, da gilt.
ist z.B. eine Gröbner-Basis von in Bezug auf jede monomiale Ordnung. Aber ist keine Gröbner-Basis von bezüglich der lexikographischen Ordnung, da nicht durch mit teilbar ist.
Um eine Gröbner-Basis eines Ideals bezüglich einer gewählten monomialen Ordnung zu erhalten, kann man Buchbergers Algorithmus (3) anwenden. Die meisten Computer Algebra System bieten entsprechende Algorithmen an.
Beispielsweise ist eine Gröbner-Basis des Ideals bezüglich der lexikographischen Ordnung.
4. Die Lösung des Problems und andere Anwendungen
Das in Beispiel 1 gegebene System hat bestenfalls eine endliche Anzahl an Lösungen (neun Variable, von denen jede einen von drei Werten anzunehmen kann). Das Problem ist, zu entscheiden, ob das System eine Lösung besitzt und wenn ja, diese zu bestimmen.
Wendet man Buchbergers Algorithmus auf das System in Beispiel 1 an, erhält man folgende Gröbner-Basis bezüglich der lexikographischen Ordnung:
Somit gilt und infolgedessen besitzt das System Lösungen. Die Gleichungen
zeigen: Wir können jede beliebige Farbe für , , und verwenden.
Da die Farben durch die komplexen kubischen Einheitswurzeln codiert sind, besteht unter den Bedingungen , und die einzige Lösung darin, den Variablen Werte (Farben) zuzuweisen, die für , und verschieden sind. Folglich gilt . Aus folgt weiterhin oder . Also können , und verschiedene Farben vertreten, oder es gilt . Somit finden wir abgesehen von Permutationen der Farben alle möglichen Lösungen:
Gröbner-Basen können auch verwendet werden, um mit Idealen umzugehen, um parametrische Gleichungen, die zu impliziten Gleichungen (z.B. für Flächen und Kurven) gehören, in nicht-parametrische Gleichungen umzuwandeln, um das Minimalpolynom algebraischer Zahlen zu berechnen, um Sätze der Euklidischen Geometrie zu beweisen, um Origami-Konstruktionen zu bestätigen und um Sudoku Rätsel zu lösen (siehe (4), (5) und (6)).
Literatur:
(1) http://www.ipv.pt/millenium/Millenium24/12.pdf
(2) http://www.mat.uniroma1.it/people/manetti/dispense/nullstellen.pdf
(3) https://www.risc.jku.at/people/buchberg/papers/1970-00-00-A.english.pdf
(4) Adams, W. and Loustaunau, P., An Introduction to Gröbner Basis, AMS, Providence RI (1994).
(5) Cox, D; Little, J. and O’Shea, D., Ideals, Varieties and Algorithms, 2nd edition, Springer-Verlag, New York, (1996).
(6) Hernandes, M. E., Um Primeiro Contato com Bases de Gröbner, 28°. Colóquio Brasileiro de Matemática, IMPA, Rio de Janeiro, (2011).