Rzutna płaszczyzna zamówienia 12


14

Cel : ustalenie przypuszczenia, że ​​nie ma rzutowej płaszczyzny rzędu 12.

W 1989 r., Korzystając z wyszukiwania komputerowego na kredce, Lam udowodnił, że nie istnieje rzutowa płaszczyzna rzędu 10. Teraz, gdy Boski numer Kostki Rubika został ustalony po zaledwie kilku tygodniach masowych poszukiwań brutalnej siły (plus sprytnej matematyki symetrii), wydaje mi się, że ten długotrwały otwarty problem może być w zasięgu ręki. (A może moglibyśmy użyć takich technik, aby rozwiązać coś matematycznie fundamentalnego.) Mam nadzieję, że to pytanie może służyć jako sprawdzian rozsądku.

Moduł został rozwiązany przez zmniejszenie całkowitego rozmiaru problemu do „tylko” 2 217 093 120 odrębnych testów, które można uruchomić równolegle.

Pytania:

  1. Pokazano kilka specjalnych przypadków nieistnienia. Czy ktoś wie, że jeśli je usuniemy i wyczerpująco przeszukamy resztę, jeśli rozmiar problemu jest zgodny z kolejnością wyszukiwania Cube? (Może za dużo nadziei na to, że ktoś to wie ....)

  2. Jakieś częściowe informacje w tym stylu?

Zmieniono, aby dodać: Zadałem to pytanie na MathOverflow tutaj . Jak dotąd wydaje się, że ze znanych wyników częściowych nie osiągnięto zmniejszenia przestrzeni wyszukiwania. Nadal nie znam wielkości całkowitej przestrzeni wyszukiwania.


czy znasz jakieś dobre referencje dotyczące wspomnianych przez ciebie szczególnych przypadków nieistnienia? A może po prostu ogólne odniesienie / zestaw odniesień dla przypadku rzędu 12?
Daniel Apon,

2
Wygląda to lepiej dla MathOverflow. Czy istnieje silny związek z informatyką teoretyczną? (Z drugiej strony: jak trudno jest zdecydować, biorąc pod uwagę liczbę całkowitą n, czy istnieje rzutowa płaszczyzna rzędu n? Czas wielomianowy? NP-trudny? Gorzej?)
Jeffε

@JeffE, dzięki, zastanawiałem się, czy powinienem tam o to zapytać. Myślę, że może to być zastosowanie TCS do kombinatoryki, ale nie uważam tego za „ważny” wynik, tylko wysoko wiszący owoc, który może być teraz niski z powodu szybkości procesora i chmury. Nie znam odpowiedzi na twój problem decyzyjny. Więc ... Poczekam kilka dni, a następnie opublikuję w MO, linkując tutaj.
Aaron Sterling

Lubię przeformułowanie Jeffa. Może warto to napisać jako kolejne pytanie :)
Suresh Venkat

2
Widzę potencjalne zastosowanie informatyki do kombinatoryki, a nie tylko informatyki teoretycznej , która (według moich własnych uprzedzeń) dotyczy ograniczającego zachowania obliczeń w miarę wzrostu wielkości wejściowej do nieskończoności. Znalezienie liczby Boga było imponującym osiągnięciem technicznym, ale nie jest jasne, czy wymagało to wglądu algorytmicznego, czy też będzie miało jakikolwiek wpływ algorytmiczny. (Chciałbym być poprawiony w tym punkcie.)
Jeffε

Odpowiedzi:


9

(Więcej komentarza niż odpowiedzi :)

Istnieją skończone płaszczyzny rzutowania dla wartości n, które są potęgami liczby pierwszej, i istnieje nieskończenie wiele wartości n, które są wykluczone przez twierdzenie RH Brucka i H. Rysera, które zostało uogólnione, aby blokować projekty Chowli:

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

n = 10, jak stwierdzono, zostało rozwiązane (nie istnieje płaszczyzna) przez wyszukiwanie komputerowe, więc pierwsza wartość n nie wykluczona przez Brucka-Rysera to n = 12. Jednak praca komputera nie dawała nowych wglądów, ponieważ czy są tylko główne samoloty energetyczne. Wydaje się, że potrzebne są nowe matematyczne metody wglądu w powszechnie przyjęte przypuszczenie, że istnieją tylko główne płaszczyzny mocy.


3

Istnieje przypuszczenie, że jeśli sigma (n)> 2n, to nie ma też skończonej płaszczyzny rzutowej (FPP) rzędu n, ani pełnego zestawu odpowiadających sobie kwadratów łacińskich (CMOLS). Gdzie sigma (n) oznacza sumę dodatnich dzielników n, w tym samego n. W rzeczywistości, gdy sigma (n)> 2n oznacza, że ​​n jest liczbą obfitą. a 12 to najmniejsza dostępna liczba. Poniżej podano wszystkie obfite liczby dla 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,

z On Projective Planes of Order 12 autorstwa Muatazza Abdolhadi Bashira i Andrew Rajah

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.