Fallstudie: Das Existenzproblem von Quasigruppen
Einige mathematische Theoreme können durch kombinatorische Untersuchung gelöst werden. In diesem Artikel konzentrieren wir uns auf das Drawback der Existenz einiger Quasigruppen. Wir werden die Existenz oder Nichtexistenz einiger Quasigruppen anhand von demonstrieren NuCS. NuCs ist ein schneller, zu 100 % in Python geschriebener Constraint-Löser, den ich derzeit als Nebenprojekt entwickle. Es wird unter der veröffentlicht MIT-Lizenz.
Beginnen wir mit der Definition einiger nützlicher Vokabeln.
Gruppen
Zitat aus Wikipedia:
In Mathematik, a Gruppe ist eine Menge mit einer Operation, die jedem Elementpaar der Menge ein Component der Menge zuordnet (wie jede binäre Operation) und die folgenden Einschränkungen erfüllt: Die Operation ist assoziativ, sie hat ein Identitätselement und jedes Component der Die Menge hat ein inverses Component.
Die Menge der ganzen Zahlen (positiv und negativ) bildet zusammen mit der Addition eine Gruppe. Es gibt viele Arten von Gruppen, zum Beispiel die Manipulationen der Zauberwürfel.
Lateinische Quadrate
Ein lateinisches Quadrat ist ein N × N Array gefüllt mit N verschiedene Symbole, die jeweils genau einmal in jeder Zeile und genau einmal in jeder Spalte vorkommen.
Ein Beispiel für ein lateinisches 3×3-Quadrat ist:
Ein Sudoku ist zum Beispiel ein 9×9 Lateinisches Quadrat mit zusätzlichen Eigenschaften.
Quasigruppen
Eine Bestellung M Quasigruppe ist ein lateinisches Größenquadrat M. Das heißt, a m×m Multiplikationstabelle (wir notieren ∗ das Multiplikationssymbol), in der jedes Component einmal in jeder Zeile und Spalte vorkommt.
Das Multiplikationsgesetz muss nicht assoziativ sein. Wenn ja, ist die Quasigruppe eine Gruppe.
Im weiteren Verlauf dieses Artikels konzentrieren wir uns auf das Drawback der Existenz bestimmter Quasigruppen. Die Quasigruppen, an denen wir interessiert sind, sind additionally idempotent A∗a=a für jedes Component A.
Darüber hinaus verfügen sie über zusätzliche Eigenschaften:
- QG3.m-Probleme sind Quasigruppen der Ordnung m, für die (a∗b)∗(b∗a)=a.
- QG4.m-Probleme sind Quasigruppen der Ordnung m, für die (b∗a)∗(a∗b)=a.
- QG5.m-Probleme sind Quasigruppen der Ordnung m, für die ((b∗a)∗b)∗b=a.
- QG6.m-Probleme sind Quasigruppen der Ordnung m, für die (a∗b)∗b=a∗(a∗b).
- QG7.m-Probleme sind Quasigruppen der Ordnung m, für die (b∗a)∗b=a∗(b∗a).
Im Folgenden für eine Quasigruppe der Ordnung Mstellen wir fest 0, …, m-1 die Werte der Quasigruppe (wir möchten, dass die Werte mit den Indizes in der Multiplikationstabelle übereinstimmen).
Lateinische quadratische Modelle
Wir werden das Quasigruppenproblem modellieren, indem wir das lateinische Quadratproblem nutzen. Ersteres gibt es in zwei Geschmacksrichtungen:
- Die LatinSquareProblem,
- Die LatinSquareRCProblem.
Das LatinSquareProblem besagt einfach, dass die Werte in allen Zeilen und Spalten der Multiplikationstabelle unterschiedlich sein müssen:
self.add_propagators(((self.row(i), ALG_ALLDIFFERENT, ()) for i in vary(self.n)))
self.add_propagators(((self.column(j), ALG_ALLDIFFERENT, ()) for j in vary(self.n)))
Dieses Modell definiert für jede Zeile ich und Spalte Jder Wert Farbe(i, j) der Zelle. Wir nennen es das Farbe Modell. Symmetrisch können wir definieren:
- für jede Zeile ich und Farbe Cdie Spalte Spalte(i, c): Wir nennen das das Spalte Modell,
- für jede Farbe C Und Spalte Jdie Reihe Zeile(c, j): Wir nennen das das Reihe Modell.
Beachten Sie, dass wir die folgenden Eigenschaften haben:
- row(c, j) = i <=> coloration(i, j) = c
Für eine gegebene Spalte J, Zeile(., j) Und Farbe(., j) sind inverse Permutationen.
- Zeile(c, j) = i <=> Spalte(i, c) = j
Für eine gegebene Farbe C, Zeile(c, .) Und Spalte(., c) sind inverse Permutationen.
- Farbe(i, j) = c <=> Spalte(i, c) = j
Für eine gegebene Reihe ich, Farbe(i, .) Und Spalte(i, .) sind inverse Permutationen.
Genau das wird vom LatinSquareRCProblem mit Hilfe des ALG_PERMUTATION_AUX-Propagators implementiert (beachten Sie, dass in meinem auch eine weniger optimierte Model dieses Propagators verwendet wurde vorheriger Artikel zum Drawback des Handlungsreisenden):
def __init__(self, n: int):
tremendous().__init__(listing(vary(n))) # the colour mannequin
self.add_variables(((0, n - 1)) * n**2) # the row mannequin
self.add_variables(((0, n - 1)) * n**2) # the column mannequin
self.add_propagators(((self.row(i, M_ROW), ALG_ALLDIFFERENT, ()) for i in vary(self.n)))
self.add_propagators(((self.column(j, M_ROW), ALG_ALLDIFFERENT, ()) for j in vary(self.n)))
self.add_propagators(((self.row(i, M_COLUMN), ALG_ALLDIFFERENT, ()) for i in vary(self.n)))
self.add_propagators(((self.column(j, M_COLUMN), ALG_ALLDIFFERENT, ()) for j in vary(self.n)))
# row(c,j)=i <=> coloration(i,j)=c
for j in vary(n):
self.add_propagator(((*self.column(j, M_COLOR), *self.column(j, M_ROW)), ALG_PERMUTATION_AUX, ()))
# row(c,j)=i <=> column(i,c)=j
for c in vary(n):
self.add_propagator(((*self.row(c, M_ROW), *self.column(c, M_COLUMN)), ALG_PERMUTATION_AUX, ()))
# coloration(i,j)=c <=> column(i,c)=j
for i in vary(n):
self.add_propagator(((*self.row(i, M_COLOR), *self.row(i, M_COLUMN)), ALG_PERMUTATION_AUX, ()))
Quasigruppenmodell
Jetzt müssen wir unsere zusätzlichen Eigenschaften für unsere Quasigruppen implementieren.
Idempotenz wird einfach implementiert durch:
for mannequin in (M_COLOR, M_ROW, M_COLUMN):
for i in vary(n):
self.shr_domains_lst(self.cell(i, i, mannequin)) = (i, i)
Konzentrieren wir uns nun auf QG5.m. Wir müssen umsetzen ((b∗a)∗b)∗b=a:
- das bedeutet: Farbe(Farbe(Farbe(j, i), j), j) = i,
- oder äquivalent: row(i, j) = coloration(coloration(j, i), j).
Der letzte Ausdruck besagt, dass die Farbe(j,i)th Component der jth Spalte ist Zeile(i, j). Um dies durchzusetzen, können wir den ALG_ELEMENT_LIV-Propagator nutzen (oder einen spezielleren ALG_ELEMENT_LIV_ALLDIFFERENT, der so optimiert ist, dass er die Tatsache berücksichtigt, dass die Zeilen und Spalten Elemente enthalten, die alle unterschiedlich sind).
for i in vary(n):
for j in vary(n):
if j != i:
self.add_propagator(
(
(*self.column(j), self.cell(j, i), self.cell(i, j, M_ROW)),
ALG_ELEMENT_LIV_ALLDIFFERENT,
(),
)
)
Ebenso können wir die Probleme modellieren QG3.m, QG4.m, QG6.m, QG7.m.
Beachten Sie, dass dieses Drawback sehr schwierig ist, da der Suchraum groß ist. Für m=10das ist 1e+100.
Die folgenden Experimente werden auf einem MacBook Professional M2 mit Python 3.13, Numpy 2.1.3, Numba 0.61.0rc2 und NuCS 4.6.0 durchgeführt. Beachten Sie, dass die neueren Versionen von NuCS relativ schneller sind als ältere, da Python, Numpy und Numba aktualisiert wurden.
Die folgenden Beweise für die Existenz/Nichtexistenz werden in erhalten weniger als eine Sekunde:
Konzentrieren wir uns jetzt darauf QG5.m nur dort, wo das erste offene Drawback ist QG5.18.
Um noch weiter zu gehen, müsste man zumindest für ein paar Tage eine leistungsstarke Maschine bei einem Cloud-Anbieter mieten!
Wie wir gesehen haben, können einige mathematische Theoreme durch kombinatorische Untersuchung gelöst werden. In diesem Artikel haben wir das Drawback der Existenz/Nichtexistenz von Quasigruppen untersucht. Unter diesen Problemen scheinen einige offene Probleme zugänglich zu sein, was sehr anregend ist.
Einige Ideen zur Verbesserung unseres aktuellen Ansatzes zur Existenz von Quasigruppen:
- Verfeinern Sie das Modell, das immer noch recht einfach ist
- Erkunden Sie ausgefeiltere Heuristiken
- Führen Sie den Code in der Cloud aus (z. B. mit Docker)