Rozważmy następujący problem. Mamy danych wiele -wymiarowych wektorów: takich że sumują się one do wektora zerowego, czyli Podkreślmy, że liczba wektorów może być dużo większa niż Załóżmy dodatkowo, że długości wszystkich wektorów są nie większe niż 1. Dla danego ciągu wektorów rozważmy podróż tym ciągiem w przestrzeni w której startujemy z zera a potem kolejno przesuwamy się o o o itd., a na końcu o Oczywiście na koniec całej podróży wrócimy do zera, ale w międzyczasie możemy od tego zera odsunąć się bardzo daleko. Pytanie brzmi, czy dla dowolnych wektorów istnieje takie ich poprzestawianie, inaczej permutacja żeby podróż tym ciągiem wektorów nigdy nie oddalała się znacząco od zera. Mówiąc bardziej precyzyjnie, czy dla dowolnego wymiaru istnieje taka stała że dla dowolnego ciągu wektorów nie dłuższych niż 1 i sumujących się do istnieje ich permutacja taka, że dla dowolnego zachodzi Nim przejdziemy do rozwiązania, zachęcam Ambitnego Czytelnika do samodzielnej próby odpowiedzenia na to pytanie albo przynajmniej postawienia hipotezy i obstawienia ewentualnej wartości

Dla wymiaru stosunkowo łatwo jest wykazać, że wystarczy. Konstruujemy ciąg wektorów tak, żeby wartość bezwzględna nigdy nie przekroczyła 1. Postępujemy w następujący sposób. Zaczynamy od ciągu pustego. Powiedzmy, że skonstruowaliśmy już ciąg który spełnia nasze warunki dla początkowych wyrazów. Załóżmy bez straty ogólności, że Skoro suma wszystkich wektorów wynosi 0, a suma wektorów już wybranych do ciągu jest nieujemna, to suma wektorów niewybranych jest niedodatnia. A więc istnieje tam jakiś wektor niedodatni, tego właśnie wybieramy jako Postępując w ten sposób do końca, otrzymamy ciąg o wymaganych własnościach. Łatwo też zauważyć, że jest wybrana optymalnie, ciąg nie da się ułożyć lepiej.

Dla wyższych wymiarów sprawa nie jest tak oczywista i mimo bardzo prostego sformułowania ma za sobą długą historię badań. Już w roku 1914 niemiecki matematyk Ernst Steinitz (znany m.in. z twierdzenia o dopełnianiu zbioru liniowo niezależnych wektorów do bazy) udowodnił, że dla dowolnego stała spełnia zadane warunki. Dlatego wspomniany fakt zwany jest lematem Steinitza. Sytuacja staje się jednak ciekawsza, gdy rozważymy inne, nieco dziwniejsze sposoby mierzenia wielkości wektora. Takie funkcje, przyporządkowujące wektorowi z liczbę mierzącą w pewien rozsądny sposób jego wielkość, zwane są normami. Popularne przykłady norm to: długość wektora (zwana normą euklidesową), suma wartości bezwzględnych jego współrzędnych czy też maksymalna wartość bezwzględna jego współrzędnych (zwana normą maksimum), ale istnieją też inne, bardziej wymyślne normy. W ogólności norma to funkcja przyporządkowująca wektorowi wartość spełniająca trzy proste warunki:

1)

wtedy i tylko wtedy, gdy to wektor zerowy,

2)

norma skaluje się liniowo, czyli dla dowolnego oraz

3)

dla dowolnych

Z faktu, że dla normy euklidesowej wystarcza, wynika łatwo, że dla dowolnej normy taka stała istnieje, nie wynika jednak w żaden sposób, jak duża jest ta stała. W roku 1931 Borgström wykazał, że dla dowolnej normy optymalna stała jest nie większa niż Aż do roku 1978 najlepsza znana stała wciąż była wykładnicza względem Dopiero wtedy, w 1978 roku, Sergey Sevastianov opublikował w rosyjskim czasopiśmie w Nowosybirsku dowód uzasadniający, że dla dowolnej normy wystarczy. Praca miała dwie strony, przy czym dowód głównego wyniku zajmował w zasadzie jedną stronę, co jest oczywiście nadzwyczajne w wypadku rozwiązania znanego problemu tak długo otwartego. Przetłumaczoną na angielski wersję można znaleźć, wpisując w wyszukiwarce Google frazę "Value of the Steinitz constant". Mniej więcej rok lub dwa lata temu artykuł ten wpadł mi w ręce, ponieważ wynik jest związany z moimi zainteresowaniami naukowymi. Uważam, że dowód jest wyjątkowy. Pál Erdős, jeden z najwybitniejszych matematyków XX wieku często odwoływał się do Księgi, w której Bóg trzyma wszystkie najelegantsze dowody twierdzeń matematycznych. Zainspirowani tym powiedzeniem dwaj matematycy, Eigner i Ziegler, wydali znakomitą książkę "Dowody z Księgi", którą szczerze polecam każdemu Czytelnikowi. Dowód, o którym mówię, być może również mógłby trafić do takiej Księgi. Mimo że ja i moi koledzy rozumiemy każdy krok tego dowodu z osobna, to nie wiemy, skąd bierze się taki sposób rozumowania, niespotykany nigdzie indziej w naszej dziedzinie. Wydaje się, że za tym rozumowaniem stoi pewna intuicja geometryczna, ale nie wiemy, jaka to jest intuicja. Wierzę, że dogłębne zrozumienie idei ukrytych w tym dowodzie może przyczynić się do kolejnych ciekawych wyników. Kto wie, może ktoś z Czytelników pomoże?

Przedstawiam dowód z oryginalnej pracy Sevastianova nieco przeze mnie zmodyfikowany. Poniżej ustalamy dowolnie wybraną normę wektora którą oznaczamy Przypomnijmy, że naszym celem jest udowodnienie następującego twierdzenia.

Załóżmy, że inaczej wniosek jest trywialny. Udowodnimy następujący lemat.

Zobaczmy najpierw, jak z lematu wynika twierdzenie 1. Dla dowolnego zbiór ma dokładnie jeden element, nazywamy go Pozostałych elementów ciągu dowolnie przypisujemy na Dla nierówność z twierdzenia jest oczywista, załóżmy Mamy

gdzie druga i ostatnia równość wynikają wprost z lematu. Wystarczy więc udowodnić lemat.

Pokażemy istnienie zbiorów oraz wag spełniających warunki lematu przez indukcję po Zacznijmy od bazy indukcji dla Wówczas ustalamy oraz dla każdego które, jak łatwo sprawdzić, spełniają warunki. Aby wykonać krok indukcyjny z do załóżmy, że mamy zdefiniowany zbiór oraz wagi a chcemy zdefiniować zbiór oraz wagi Niech

Rozważmy następujący układ równań i nierówności z zmiennymi : dla dowolnego oraz Zbiór rozwiązań tego układu jest niepusty, gdyż, jak nietrudno sprawdzić, rozwiązaniem jest W ogólności dla każdego układu równań i nierówności liniowych w zbiór rozwiązań jest wielościanem, o ile jest ograniczony. Co więcej, okazuje się, że w każdym wierzchołku tego wielościanu dokładnie nierówności staje się równościami. Nietrudno w to uwierzyć, bo skoro mamy do czynienia z wierzchołkiem, to liczba równości powinna być równa wymiarowi przestrzeni, a równości mamy już gotowe z równań. Zachęcamy Czytelników do precyzyjnego wykazania tego faktu. Wybierzmy więc dowolny wierzchołek wielościanu zawierającego rozwiązania naszego układu równań. W układzie mamy równości (równość jest w istocie równością na każdej z współrzędnych) oraz nierówności. A zatem w wierzchołku spełnionych jest dodatkowych równości spośród nierówności Chcemy wykazać, że istnieje takie, że Jedyny przypadek, w którym nie jest to natychmiastowe, to gdy każda ze wspomnianych równości jest postaci Wiemy jednak, że wówczas suma pozostałych zmiennych jest równa więc każda z nich musi być równa jeden. A więc tak czy inaczej istnieje takie, że Definiujemy więc oraz Nietrudno sprawdzić, że istotnie wszystkie warunki są spełnione, co kończy dowód lematu.

Czy oprócz ładnego dowodu i ciekawej historii oszacowanie na stałą w lemacie Steinitza przydaje się do czegoś? Tak, zdecydowanie, przykładem może być ta praca arxiv.org/abs/1707.00481 opublikowana na konferencji SODA w 2018 roku, jednej z najlepszych światowych konferencji informatycznych. Gwoli ścisłości należy przyznać, że użyta jest tam konkretna norma: norma maksimum oznaczana przypomnijmy, że przypisuje ona wektorowi maksimum z wartości bezwzględnych jego współrzędnych. A więc do tego konkretnego zastosowania wystarczyłby już oryginalny wynik Steinitza z 1914 roku. Faktycznie, z tego, że dla zachodzi ( oznacza długość euklidesową wektora ), oraz tego, że wystarcza dla normy euklidesowej, wynika, że wystarcza dla normy maksimum. Ja przedstawię pokrótce inne zastosowanie, które wydaje mi się również interesujące, a może być też bardzo użyteczne.

Tunelem pomiędzy punktem a o promieniu nazwijmy zbiór, który zawiera odcinek pomiędzy a oraz punkty, które są oddalone od tego odcinka o co najwyżej gdzie odległość mierzymy normą maksimum. Precyzyjnie rzecz biorąc, taki tunel to zbiór

Po pierwsze zauważmy, że z twierdzenia 1 prosto wynika następujący wniosek.

Zachęcamy Czytelnika do samodzielnego wykazania wniosku, dowód jest nietrudny. Jesteśmy już gotowi do sformułowania twierdzenia.

Zauważmy, że ograniczenie na normę rozwiązania nie zależy od liczby równań a jedynie od liczby zmiennych i wielkości liczb i to jest właśnie główna siła twierdzenia 2. Aby udowodnić twierdzenie 2, oznaczmy kolumny macierzy jako wektory oraz Wówczas równanie przyjmuje postać Rozważmy pewne rozwiązanie tego układu, które istnieje zgodnie z założeniem twierdzenia 2. Zawiera ono wektorów wektorów itd., aż w końcu wektorów Zgodnie z wnioskiem istnieje taka permutacja tych wektorów, że cała podróż z punktu 0 do punktu ciągiem odbywa się wewnątrz tunelu z 0 do o promieniu Taki tunel zawiera się cały w -wymiarowej kostce o boku na potrzeby dowodu twierdzenia 2 wystarczy nam takie zgrubne oszacowanie. Zauważmy, że jeśli w trakcie naszej podróży odwiedzimy dwa razy ten sam punkt, to możemy tę podróż skrócić, pomijając pętlę wychodzącą i wracającą do tego samego punktu, nie zmieni to oczywiście celu podróży. Postępując w ten sposób, możemy skrócić podróż ciągiem do takiej podróży, która każdy punkt w kostce o boku odwiedza co najwyżej jeden raz. Punktów o współczynnikach całkowitych w kostce jest nie więcej niż a więc nasza podróż będzie miała co najwyżej tyle kroków. Nietrudno zauważyć, że dowolna taka podróż natychmiast daje rozwiązanie równania gdzie co kończy dowód twierdzenia 2.