Przeskocz do treści

Delta mi!

Hipoteza Kakeyi

Marcin Kotowski i Michał Kotowski

o artykule ...

  • Publikacja w Delcie: kwiecień 2013
  • Publikacja elektroniczna: 30-03-2013
  • Autor: Marcin Kotowski
    Afiliacja: Institute for Quantum Computing, Waterloo, Kanada
    Autor: Michał Kotowski
    Afiliacja: Institute for Quantum Computing, Waterloo, Kanada
  • Wersja do druku [application/pdf]: (311 KB)

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  math – jak wiele miejsca do tego potrzeba?

obrazek

Oczywiście, możemy umieścić igłę na środku koła o promieniu math i obrócić ją bez przesuwania, co wymaga pola równego math 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 math 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ę:

Definicja 1. Zbiór math  nazwiemy zbiorem Kakeyi, jeśli zawiera on odcinek jednostkowy w każdym kierunku.

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 math wynosi math

Możemy teraz wrócić do pytania, jak duży w sensie wymiaru Minkowskiego musi być zbiór Kakeyi.

Hipoteza (Hipoteza Kakeyi). Jeśli math  jest zbiorem Kakeyi w przestrzeni math-wymiarowej, to math  ma wymiar Minkowskiego (i wymiar Hausdorffa) równy math

Hipotezę tę udało się dotychczas udowodnić jedynie dla math 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  math 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 math-wymiarową przestrzeń euklidesową zastępujemy przestrzenią nad ciałem skończonym.

Niech math będzie ciałemmath elementach. Przez math będziemy oznaczać zbiór wektorów math gdzie math z naturalną operacją dodawania po współrzędnych. Zamiast przestrzeni euklidesowej math rozważamy więc skończoną przestrzeń math o  math elementach. Prostą w kierunku math przechodzącą przez punkt math gdzie math nazwiemy, podobnie jak w przypadku euklidesowym, zbiór postaci math Każda taka prosta zawiera math punktów.

Ponieważ nasza przestrzeń jest teraz skończona, bardziej naturalne w definicji zbioru Kakeyi będzie zastąpienie odcinków prostymi.

Definicja 2. Zbiór math  nazwiemy zbiorem Kakeyi, jeśli zawiera on prostą w kierunku każdego wektora z  math

Aby sformułować hipotezę Kakeyi dla ciał skończonych, potrzebujemy jeszcze dyskretnego odpowiednika wymiaru. W przestrzeni math naturalnym odpowiednikiem zbioru wymiaru math będzie zbiór mocy rzędu math Prowadzi to do następującej hipotezy.

Twierdzenie 1 (Hipoteza Kakeyi dla ciał skończonych). Niech math będzie ciałem skończonym o  math elementach. Dla każdego math istnieje taka stała math niezależna od math że jeśli math  jest zbiorem Kakeyi, to

display-math

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 math będzie wielomianem math zmiennych math o współczynnikach z  math Powiemy, że math ma miejsce zerowe w punkcie math jeśli math Stopniem jednomianu postaci math nazywamy sumę wykładników: math a stopniem wielomianu – największy stopień jednomianu wchodzącego w skład math

obrazek

Przed przystąpieniem do dowodu hipotezy przedstawiamy dwa lematy, których dowód jest ćwiczeniem dla Czytelnika. Nad ciałem nieskończonym (np. math) 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 math wielomian math jest wielomianem stopnia math który zeruje się w każdym punkcie math 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 math będzie wielomianem math zmiennych math o współczynnikach z  math Niech math ma stopień math Wtedy liczba miejsc zerowych math wynosi co najwyżej math

Dowód przebiega przez indukcję względem math Dla math jest to po prostu stwierdzenie, że wielomian jednej zmiennej, mający stopień math ma co najwyżej math miejsc zerowych. W szczególności, jeśli wielomian math ma stopień nie większy niż math i zeruje się w każdym punkcie math to musi być tożsamościowo równy zeru.

Lemat 2. Niech math będzie zbiorem mocy mniejszej niż math Wtedy istnieje wielomian math w zmiennych math stopnia co najwyżej math który zeruje się we wszystkich punktach math  i nie jest tożsamościowo równy zeru.

W dowodzie kluczowa jest obserwacja, że jednomianów w zmiennych math stopnia co najwyżej math jest dokładnie math wobec czego układ równań na współczynniki wielomianu math 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 math  o mniej niż math elementach. Z Lematu 2 wnioskujemy, że istnieje nietrywialny wielomian math stopnia co najwyżej math zerujący się w każdym punkcie math  Zbiór math  jest zbiorem Kakeyi, więc dla dowolnego niezerowego wektora math zawiera on prostą w kierunku math czyli zbiór postaci math dla pewnego math Rozpatrzmy teraz obcięcie wielomianu math do prostej w kierunku math a więc wielomian jednej zmiennej math określony jako

display-math

Dla każdego math mamy math  więc math  zeruje się punkcie math Oznacza to, że math zeruje się w każdym punkcie ciała math a ponieważ (tak jak math) ma stopień co najwyżej math więc musi być tożsamościowo równy zeru. Zatem dla każdego math mamy math

obrazek

Oznaczmy stopień math przez math i rozpiszmy math na części jednorodne, czyli

display-math

gdzie math jest wielomianem złożonym z jednomianów stopnia dokładnie math Nietrudno sprawdzić, że dla dowolnego math wyraz wiodący wielomianu math a więc współczynnik przy math wynosi math Skoro math jest równy tożsamościowo zeru, to ma wszystkie współczynniki równe zeru, a więc dla każdego math zachodzi math Jednak math ma stopień math więc gdyby nie był tożsamościowo równy zeru, to na mocy lematu Schwartza–Zippela mógłby mieć co najwyżej math miejsc zerowych. Stąd wniosek, że math Założyliśmy jednak, że wielomian math ma stopień math czyli w szczególności math nie jest tożsamościowo równy zeru – otrzymujemy więc sprzeczność.

Wywnioskowaliśmy zatem, że dowolny zbiór Kakeyi math  musi mieć moc math  co z dokładnością do wyrazów niższego rzędu w  math wynosi math Udowodniliśmy więc hipotezę Kakeyi ze stałą math

Stosując bardziej wyrafinowany wariant metody wielomianowej – tzw. metodę krotności – można udowodnić hipotezę Kakeyi z asymptotycznie lepszą stałą math Z drugiej strony, znane są konstrukcje zbiorów Kakeyi rozmiaru bliskiego math dla dostatecznie dużego math

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.