Целочисленная решётка
Целочисленная решётка — это структура в геометрии чисел и линейной алгебре, представляющая собой множество точек в евклидовом пространстве, координаты которых целочисленны относительно некоторого базиса. Наиболее простой и часто рассматриваемый пример — стандартная решётка \(\mathbb{Z}^n\) с натуральным базисом \(e_1,\dots,e_n\). В общем виде целочисленную решётку можно определить как множество всех целочисленных линейных комбинаций базисных векторов: \(L=\left\{\sum_{i=1}^n a_i b_i\mid a_i\in\mathbb{Z}\right\}\). Такие множества возникают при изучении диофантовых уравнений, структур симметрии и периодических орнаментов.
Практическое значение целочисленных решёток велико: они служат моделью для задач приближения, криптографии на решётках, теории кодов, а также для описания кристаллических решёток в физике. Важная числовая характеристика решётки — объём её фундаментального параллелепипеда, который выражается через определитель матрицы базиса и часто называется индексом или детерминантом решётки: \(\det(L)=|\det(B)|\). Геометрические алгоритмы на решётках опираются на понятия расстояния и нормы; расстояние между точками оценивают через евклидову норму вида \(\|x\|=\sqrt{x_1^2+\dots+x_n^2}\), что важно при решении задачи ближайшего соседа и при сокращении базиса.
Примеры. 1) Стандартная целочисленная решётка в двумерном пространстве — это \(\mathbb{Z}^n\) при n=2; её матрица базиса для стандартного базиса выглядит как \(B=\begin{pmatrix}1&0\\0&1\end{pmatrix}\), детерминант равен единице. 2) Нетривиальная целочисленная решётка может задаваться базисом, отличным от ортонормированного; например базис с матрицей \(B''=\begin{pmatrix}2&1\\0&1\end{pmatrix}\) порождает решётку с другим геометрическим расположением узлов и детерминантом, равным объёму фундаментального параллелепипеда. На рисунке показана схема двумерной решётки и её фундаментальный параллелепипед:.