Теорема Минковского
Введение
Теорема Минковского — центральный результат геометрии чисел, связывающий объём симметричных выпуклых множеств и структуру решёток в евклидовом пространстве \(\mathbb{R}^n\). Она даёт простое и мощное условие существования ненулевого вектора решётки внутри множества на основании соотношения объёмов.
В интуитивном смысле теорема утверждает: если множество «слишком большое» по отношению к объёму фундаментального параллелепипеда решётки, то внутри него обязательно найдётся ненулевой вектор этой решётки. Под термином «объём множества» далее понимается \(\operatorname{vol}(S)\).
Классическое формулирование связывает объём множества S с величиной \(2^n \det(L)\), где L — заданная решётка. Практические применения помогают решать задачи о представлении целых чисел как значений квадратичных форм, находить короткие векторы в решётках и оценки в диофантовой аппроксимации.
Определения
множество C называется выпуклым, если для любых двух точек a, b из C и для любого t из отрезка между нулём и единицей справедливо, что точка \(x = t a + (1-t) b,\ \; t\in[0,1]\) принадлежит C.
множество S называется симметричным относительно начала координат, если выполняется равенство \(S = -S\).
решётка L в пространстве определяется как набор целых линейных комбинаций базисных векторов: \(L = \{\sum_{i=1}^n k_i b_i \mid k_i\in\mathbb{Z}\}\).
величина det(L) равна абсолютной величине определителя матрицы базиса B решётки: \(\det(L) = |\det(B)|\). Для стандартной целочисленной решётки это даёт \(\mathbb{Z}^n\).
Формулировка теоремы
Классическая формулировка Минковского звучит так. Пусть S — измеримое выпуклое множество, симметричное относительно начала координат, и L — решётка в пространстве \(\mathbb{R}^n\). Если объём множества S больше чем \(2^n \det(L)\), то множество S содержит ненулевой вектор решётки, то есть существует вектор, удовлетворяющий условию \(\exists v\in L\setminus\{0\}:\; v\in S\).
Особый случай часто используемой формулировки — когда решётка равна целочисленной: для L = \(\mathbb{Z}^n\) условие сводится к сравнению объёма S с \(\operatorname{vol}(S) > 2^n\). Это даёт простой критерий для наличия целого ненулевого вектора в S.
Идея доказательства (схема)
Основная идея доказательства опирается на лемму Бличфельдта: если измеримое множество X имеет объём больше объёма фундаментальной области решётки, то в нём найдутся две точки, совпадающие по проекции на фактор-пространство по решётке. Для применения к Минковскому удобно ввести множество \(S'' = \frac{1}{2}S\) (уменьшить набор вдвое по каждой координате).
После введения S'' получаем соотношение объёмов \(\operatorname{vol}(S'') = \frac{\operatorname{vol}(S)}{2^n}\). Поскольку \(\operatorname{vol}(S'') = \frac{\operatorname{vol}(S)}{2^n}\) превышает \(\det(L) = |\det(B)|\), по лемме Бличфельдта найдутся две различные точки в \(S'' = \frac{1}{2}S\) с разностью, лежащей в решётке: \(\exists x\neq y\in S'':\; x-y\in L\).
Разность этих двух точек принадлежит сумме множеств \(S'' + S'' = S\), которая при симметричности и выпуклости равна исходному множеству S. Отсюда следует, что найденный ненулевой вектор решётки лежит в S: \(z_1 - z_2 \in S\). Это завершает основную конструкцию доказательства.
Следствия и применения
Одно из простых следствий — версия для стандартной решётки: если симметричное выпуклое множество S в \(\mathbb{R}^n\) имеет объём больше чем \(\operatorname{vol}(S) > 2^n\), то S содержит ненулевой целочисленный вектор. Это часто используется в задачах о представлении чисел и поиске решений в целых числах.
Минковский применяют для нахождения коротких векторов в решётке. Рассмотрим шар радиуса r; его объём равен \(\operatorname{vol}(B_r)=\omega_n r^n\). Если \(\operatorname{vol}(B_r)=\omega_n r^n\) превосходит \(2^n \det(L)\), то в шаре есть ненулевой вектор решётки, откуда следует оценка на минимальную длину ненулевого вектора вида \(r \le \left(\frac{2^n \det(L)}{\omega_n}\right)^{\frac{1}{n}}\).
В теории чисел теорема помогает получать простые доказательства существования нетривиальных решений диофантовых неравенств и показывает, что иногда геометрические соображения заменяют сложные арифметические выкладки.
Примеры
Пример 1 (одномерный случай). Пусть рассмотрим интервал I = \(I = (-a,a)\). Для решётки Z (determinant равен единице) объём интервала равен \(2a > 2\). Условие Минковского в этом случае даёт неравенство \(2a > 2\), что эквивалентно \(a>1\). Это означает, что если длина интервала больше двух, внутри обязательно найдётся ненулевой целый точечный вектор.
Пример 2 (дисковая область в двумерном пространстве). Для круга радиуса r объём (площадь) равен \(\pi r^2 > 4\). Для стандартной решётки Z^2 (детерминант равен \(\det(\mathbb{Z}^2)=1\)) условие Минковского принимает вид \(\pi r^2 > 4\). Из этого следует оценка для r: \(r > \sqrt{\frac{4}{\pi}}\). То есть при r больше этого порога диск обязательно содержит ненулевой целочисленный вектор.
Пример 3 (решётка с базисом, растянутым вдвое). Пусть решётка задана вектор-ячейкой размера два по каждой координате, тогда её детерминант равен \(\det(L)=4\). Для круга условие Минковского превращается в \(\pi r^2 > 16\), и минимальное значение радиуса оценивается как \(r > \sqrt{\frac{16}{\pi}}\). Это показывает, как изменение детерминанта решётки влияет на необходимый объём множества для гарантии наличия ненулевой точки решётки внутри.
Упражнения
1) Покажите напрямую в одномерном случае, что теорема Минковского эквивалентна очевидному утверждению о целых точках внутри отрезка, используя понятие детерминанта решётки и объём отрезка.
2) Используя оценку из раздела о коротких векторах, выведите численную оценку для минимальной длины ненулевого вектора в решётке, если известен объём единичного шара и детерминант L.
3) Придумайте пример невыпуклого симметричного множества, для которого объём больше порога Минковского, но теорема не применяется из-за отсутствия выпуклости; проанализируйте, почему выпуклость важна в доказательстве.