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.