Projektive Ordnungsebene 12

14

Ziel : Stellen Sie die Vermutung auf, dass es keine projektive Ordnungsebene 12 gibt.

Im Jahr 1989 bewies Lam mittels Computersuche auf einem Cray, dass es keine projektive Ebene der Ordnung 10 gibt. Jetzt, da Gottes Zahl für Rubiks Würfel nach nur wenigen Wochen massiver Brute-Force-Suche (plus kluger Symmetriemathematik) ermittelt wurde, scheint mir dieses langjährige offene Problem in greifbare Nähe zu rücken. (Und vielleicht könnten wir solche Techniken verwenden, um etwas mathematisch Grundlegendes zu lösen.) Ich hoffe, diese Frage kann als Vernunftsprüfung dienen.

Der Cube wurde gelöst, indem die Gesamtgröße des Problems auf "nur" 2.217.093.120 verschiedene Tests reduziert wurde, die parallel ausgeführt werden konnten.

Fragen:

  1. Es wurden mehrere Sonderfälle des Nichtvorhandenseins gezeigt. Weiß jemand, ob wir diese entfernen und den Rest erschöpfend durchsuchen, ob die Problemgröße in der Größenordnung der Würfelsuche liegt? (Vielleicht zu viel zu hoffen, dass jemand das weiß ....)

  2. Irgendwelche Teilinformationen in dieser Richtung?

Bearbeitet, um hinzuzufügen: Ich habe diese Frage zu MathOverflow hier gestellt . Bisher sieht es so aus, als würde aus den bekannten Teilergebnissen keine Platzreduzierung erzielt. Die Größe des gesamten Suchraums ist mir noch nicht bekannt.

open-problem Aaron Sterling
quelle
Kennen Sie gute Referenzen für die von Ihnen genannten Sonderfälle? Oder vielleicht nur eine allgemeine Referenz / ein Satz von Referenzen für den Fall der Bestellung 12?
Daniel Apon
2
Dies scheint besser für MathOverflow geeignet zu sein. Gibt es eine starke Verbindung zur theoretischen Informatik? (Auf der anderen Seite: Wie schwer ist es, angesichts einer ganzen Zahl n zu entscheiden, ob eine projektive Ebene der Ordnung n existiert? Polynomialzeit? NP-hart? Schlimmer?)
Jeff
@ JeffE, danke, ich habe mich gefragt, ob ich es stattdessen dort fragen soll. Ich denke, es könnte eine Anwendung von TCS für die Kombinatorik sein, aber ich sehe es nicht als "wichtiges" Ergebnis, sondern nur als hochhängende Frucht, die jetzt aufgrund der Prozessorgeschwindigkeit und der Cloud möglicherweise niedrighängend ist. Ich kenne die Antwort auf Ihr Entscheidungsproblem nicht. Also ... ich werde ein paar Tage warten und dann auf MO posten und hier verlinken.
Aaron Sterling
Ich mag Jeffs Neuformulierung. Vielleicht lohnt es sich, dies als weitere Frage zu veröffentlichen :)
Suresh Venkat
2
Ich sehe die potenzielle Anwendung der Informatik auf die Kombinatorik, nur nicht die theoretische Informatik, bei der es (nach meinen eigenen Vorurteilen) um das einschränkende Verhalten der Berechnung geht, wenn die Eingabegröße auf unendlich ansteigt. Gottes Zahl zu finden war eine beeindruckende technische Leistung, aber es ist nicht klar, ob es algorithmische Einsichten erforderte oder ob es algorithmische Auswirkungen haben wird. (Ich würde gerne in diesem Punkt korrigiert werden.)
Jeffs

Antworten:

9

(Mehr ein Kommentar als eine Antwort :)

Es gibt endliche projektive Ebenen für Werte von n, die Potenzen einer Primzahl sind, und es gibt unendlich viele Werte von n, die durch einen Satz von RH Bruck und H. Ryser ausgeschlossen sind, der verallgemeinert wurde, um Entwürfe von Chowla zu blockieren:

http://en.wikipedia.org/wiki/Bruck%E2%80%93Chowla%E2%80%93Ryser_theorem

n = 10 wurde, wie gesagt, durch eine Computersuche gelöst (es gibt kein Flugzeug), so dass der erste von Bruck-Ryser nicht ausgeschlossene Wert von n n = 12 ist. Die Computerarbeit schien jedoch keine neuen Erkenntnisse zu liefern ob es nur die Prime Power Flugzeuge gibt oder nicht. Notwendig scheinen neue mathematische Methoden zu sein, um einen Einblick in die weit verbreitete Vermutung zu erhalten, dass nur die Primärenergieebenen existieren.

Joseph Malkevitch
quelle
3

Es gibt eine Vermutung, dass es, wenn Sigma (n)> 2n ist, weder eine endliche projektive Ebene (FPP) der Ordnung n noch einen vollständigen Satz von zueinander orthogonalen lateinischen Quadraten (CMOLS) gibt, der ihr entspricht. Wobei Sigma (n) die Summe der positiven Teiler von n einschließlich n selbst bezeichnet. In der Tat, wenn Sigma (n)> 2n bedeutet, dass n eine häufige Zahl ist. und 12 ist die kleinste vorhandene Anzahl. Das Folgende sind alle häufigen Zahlen für 1> n> 500: 12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, 96, 100, 102, 104, 108, 112, 114, 120, 126, 132, 138, 140, 144, 150, 156, 160, 162, 168, 174, 176, 180, 186, 190, 196, 198, 200, 204, 210, 216, 220, 222, 224, 228, 234, 240, 246, 252, 258, 260, 264, 270, 272, 276, 280, 282, 294, 300, 304, 306, 308, 312, 318, 320, 324, 330, 336, 340, 342, 348, 350, 352, 354, 360, 364,

aus On Projective Planes of Order 12 von Muatazz Abdolhadi Bashir und Andrew Rajah

Bashir
quelle