Hipoteza Kakeyi
Wyobraźmy sobie igłę umieszczoną wewnątrz pewnego zbioru na płaszczyźnie. Igłę traktujemy jak odcinek jednostkowy, który możemy dowolnie obracać i przesuwać w obrębie naszego zbioru. Załóżmy, że chcielibyśmy wykonać igłą obrót o – jak wiele miejsca do tego potrzeba?
Oczywiście, możemy umieścić igłę na środku koła o promieniu i obrócić ją bez przesuwania, co wymaga pola równego Po chwili zastanowienia widać, że rozwiązanie to nie jest optymalne. Umieszczając igłę wewnątrz kształtu utworzonego przez trzy łuki deltoidy, przedstawionego na rysunku, a następnie przesuwając i obracając ją tak, aby w każdej chwili stykała się z brzegiem figury w trzech punktach, możemy wykonać pełny obrót przy polu Czy da się jeszcze lepiej?
Pytanie to zadał po raz pierwszy japoński matematyk Soichi Kakeya w 1917 roku. Jak łatwo się przekonać, aby wewnątrz zbioru dało się wykonać pełny obrót igły, musi on zawierać odcinek jednostkowy w każdym kierunku. Własność ta ma sens nie tylko na płaszczyźnie, ale też w przestrzeni dowolnego wymiaru, co motywuje następującą definicję:
Zaskakującej odpowiedzi na pytanie Kakeyi udzielił Abraham Besicovitch w 1919 roku. Okazuje się, że istnieją zbiory o dowolnie małym polu, wewnątrz których można obrócić igłę! Co więcej, można nawet skonstruować zbiory Kakeyi o polu równym zeru. Konstrukcję, opartą o sprytne sklejanie trójkątów o coraz mniejszych polach, można obejrzeć na stronie http://www.math.ucla.edu/ tao/java/Besicovitch.html.
To jednak jeszcze nie koniec. Nawet wśród zbiorów o mierze zero istnieją zbiory „mniejsze” i „większe”. Intuicję z tym związaną formalnie ujmuje pojęcie tzw. wymiaru Minkowskiego, który (mówiąc bardzo ogólnie) mierzy, jak dobrze zbiór wypełnia przestrzeń. Wymiar ten może być liczbą niecałkowitą.
Przykładami zbiorów o niecałkowitym wymiarze Minkowskiego są zbiory samopodobne (fraktale). Maksymalny możliwy wymiar zbioru wynosi
Możemy teraz wrócić do pytania, jak duży w sensie wymiaru Minkowskiego musi być zbiór Kakeyi.
Hipoteza (Hipoteza Kakeyi). Jeśli jest zbiorem Kakeyi w przestrzeni -wymiarowej, to ma wymiar Minkowskiego (i wymiar Hausdorffa) równy
Hipotezę tę udało się dotychczas udowodnić jedynie dla W wyższych wymiarach, pomimo wysiłków wielu matematyków, pozostaje ona problemem otwartym, powiązanym z wieloma działami matematyki, między innymi z analizą harmoniczną i równaniami różniczkowymi cząstkowymi.
Skoro nie potrafimy udowodnić hipotezy Kakeyi w nasuwa się pytanie, czy istnieje jakaś prostsza wersja lub szczególny przypadek problemu, który łatwiej rozwiązać. Zwróćmy uwagę, że do zdefiniowania zbioru Kakeyi potrzebujemy jedynie abstrakcyjnego pojęcia prostej czy odcinka, natomiast nie jest istotne, że mamy do czynienia z liczbami rzeczywistymi. W szczególności możemy rozważać dyskretny wariant problemu, w którym -wymiarową przestrzeń euklidesową zastępujemy przestrzenią nad ciałem skończonym.
Niech będzie ciałem o elementach. Przez będziemy oznaczać zbiór wektorów gdzie z naturalną operacją dodawania po współrzędnych. Zamiast przestrzeni euklidesowej rozważamy więc skończoną przestrzeń o elementach. Prostą w kierunku przechodzącą przez punkt gdzie nazwiemy, podobnie jak w przypadku euklidesowym, zbiór postaci Każda taka prosta zawiera punktów.
Ponieważ nasza przestrzeń jest teraz skończona, bardziej naturalne w definicji zbioru Kakeyi będzie zastąpienie odcinków prostymi.
Aby sformułować hipotezę Kakeyi dla ciał skończonych, potrzebujemy jeszcze dyskretnego odpowiednika wymiaru. W przestrzeni naturalnym odpowiednikiem zbioru wymiaru będzie zbiór mocy rzędu Prowadzi to do następującej hipotezy.
Twierdzenie 1 (Hipoteza Kakeyi dla ciał skończonych). Niech będzie ciałem skończonym o elementach. Dla każdego istnieje taka stała niezależna od że jeśli jest zbiorem Kakeyi, to
Problem ma teraz bardziej kombinatoryczny charakter niż w przypadku euklidesowym, co nie znaczy, że musi być łatwiejszy do rozwiązania. Hipotezę Kakeyi dla ciał skończonych postawiono w 1999 roku. Przez dziesięć lat, pomimo prób wielu matematyków, w tym medalistów Fieldsa, nie udało się jednak jej udowodnić.
W związku z tym wielkim zaskoczeniem okazał się przedstawiony przez Zeeva Dvira w 2009 roku piękny i prosty dowód hipotezy Kakeyi dla ciał skończonych. Dowód, z pewnością zasługujący na miano Dowodu z Księgi, korzysta z tzw. metody wielomianowej, stosowanej już wcześniej w kombinatoryce, a przy tym jest tak elementarny, że daje się zrozumieć z wykorzystaniem podstawowej wiedzy licealnej!
W dowodzie kluczową rolę grają wielomiany nad ciałami skończonymi. Niech będzie wielomianem zmiennych o współczynnikach z Powiemy, że ma miejsce zerowe w punkcie jeśli Stopniem jednomianu postaci nazywamy sumę wykładników: a stopniem wielomianu – największy stopień jednomianu wchodzącego w skład
Przed przystąpieniem do dowodu hipotezy przedstawiamy dwa lematy, których dowód jest ćwiczeniem dla Czytelnika. Nad ciałem nieskończonym (np. ) wielomian zerujący się w każdym punkcie ciała musi być tożsamościowo równy zeru (mieć wszystkie współczynniki zerowe). Zauważmy, że nie jest to prawda nad ciałami skończonymi – dla dowolnego ciała skończonego wielomian jest wielomianem stopnia który zeruje się w każdym punkcie a nie jest tożsamościowo równy zeru. Każdy wielomian o tej własności musi mieć jednak odpowiednio wysoki stopień, o czym mówi następujący lemat.
Lemat 1 (Lemat Schwartza–Zippela). Niech będzie wielomianem zmiennych o współczynnikach z Niech ma stopień Wtedy liczba miejsc zerowych wynosi co najwyżej
Dowód przebiega przez indukcję względem Dla jest to po prostu stwierdzenie, że wielomian jednej zmiennej, mający stopień ma co najwyżej miejsc zerowych. W szczególności, jeśli wielomian ma stopień nie większy niż i zeruje się w każdym punkcie to musi być tożsamościowo równy zeru.
Lemat 2. Niech będzie zbiorem mocy mniejszej niż Wtedy istnieje wielomian w zmiennych stopnia co najwyżej który zeruje się we wszystkich punktach i nie jest tożsamościowo równy zeru.
W dowodzie kluczowa jest obserwacja, że jednomianów w zmiennych stopnia co najwyżej jest dokładnie wobec czego układ równań na współczynniki wielomianu o zadanych właściwościach ma niezerowe rozwiązania.
Mając w ręku powyższe lematy, możemy przystąpić do dowodu hipotezy Kakeyi. Przypuśćmy, że istnieje zbiór Kakeyi o mniej niż elementach. Z Lematu 2 wnioskujemy, że istnieje nietrywialny wielomian stopnia co najwyżej zerujący się w każdym punkcie Zbiór jest zbiorem Kakeyi, więc dla dowolnego niezerowego wektora zawiera on prostą w kierunku czyli zbiór postaci dla pewnego Rozpatrzmy teraz obcięcie wielomianu do prostej w kierunku a więc wielomian jednej zmiennej określony jako
Dla każdego mamy więc zeruje się punkcie Oznacza to, że zeruje się w każdym punkcie ciała a ponieważ (tak jak ) ma stopień co najwyżej więc musi być tożsamościowo równy zeru. Zatem dla każdego mamy
Oznaczmy stopień przez i rozpiszmy na części jednorodne, czyli
gdzie jest wielomianem złożonym z jednomianów stopnia dokładnie Nietrudno sprawdzić, że dla dowolnego wyraz wiodący wielomianu a więc współczynnik przy wynosi Skoro jest równy tożsamościowo zeru, to ma wszystkie współczynniki równe zeru, a więc dla każdego zachodzi Jednak ma stopień więc gdyby nie był tożsamościowo równy zeru, to na mocy lematu Schwartza–Zippela mógłby mieć co najwyżej miejsc zerowych. Stąd wniosek, że Założyliśmy jednak, że wielomian ma stopień czyli w szczególności nie jest tożsamościowo równy zeru – otrzymujemy więc sprzeczność.
Wywnioskowaliśmy zatem, że dowolny zbiór Kakeyi musi mieć moc co z dokładnością do wyrazów niższego rzędu w wynosi Udowodniliśmy więc hipotezę Kakeyi ze stałą
Stosując bardziej wyrafinowany wariant metody wielomianowej – tzw. metodę krotności – można udowodnić hipotezę Kakeyi z asymptotycznie lepszą stałą Z drugiej strony, znane są konstrukcje zbiorów Kakeyi rozmiaru bliskiego dla dostatecznie dużego
Czytelnikowi zainteresowanemu tym zagadnieniem, a w szczególności innymi zastosowaniami metody wielomianowej, polecamy materiały ze strony http://warsztatywww.wikidot.com/www8:kody-ciala-igly przygotowane przez autorów artykułu.