19.1. ОПРЕДЕЛЕНИЕ. Решеткой в $$n$$ -мерном векторном пространстве над полем вещественных чисел $$\mathbb R $$ или над полем рациональных чисел $$\mathbb Q $$ называется свободный $$\mathbb Z $$ -модуль $$L$$ ранга $$n$$, т.е. существует базис $$b_1,\dots,b_n$$ пространства $$\mathbb R ^n$$ (соответственно $$\mathbb Q ^n$$ ), такой, что$$\begin{equation*} L=\sum\limits ^n_{i=1}\mathbb Z b_i = \biggl\{ \sum\limits ^n_{i=1} r_i b_i\ |\ r_i \in\mathbb Z ,\quad 1\leq i\leq n \biggr\}. \end{equation*}$$ В этом случае $$n$$ называется рангом решетки, а множество векторов $$b_1,\dots,b_n$$ - ее базисом.
19.2. ОПРЕДЕЛЕНИЕ. Детерминантом $$d(L)$$ решетки $$L$$ называется положительное число, определяемое формулой$$\begin{equation*} d(L) = |\det (b_1 , b_2 ,\dots, b_n )|, \end{equation*}$$ для некоторого базиса $$b_1,b_2,\dots, b_n$$ решетки $$L$$.
19.3. УПРАЖНЕНИЕ. Показать, что определение 19.2 является корректным, т.е. $$d(L)$$ не зависит от выбора базиса решетки $$L$$.
Прежде чем дать определение редуцированного базиса решетки, нам необходимо напомнить процесс ортогонализации Грама-Шмидта. Векторы $$b_i^*$$ $$\smu{2}(1\leq i\leq n)$$ и вещественные числа $$\mu_{i,j}$$ $$(1\leq j< i\leq n)$$ определяются по индукции формулами
$$b_i^*=b_i-\sum\limits _{j=1}^{i-1} \mu_{i,j}b_j^*,$$ $$\mu_{i,j}=\frac{(b_i , b_j^* )}{(b_j^* ,b_j^* )}.$$Отметим, что $$b_i^*$$ - проекция вектора $$b_i$$ на ортогональное дополнение к пространству $$\sum\limits\limits _{j=1}^{i-1}\mathbb R b_j$$ в пространстве $$\sum\limits\limits _{j=1}^i \mathbb R b_j$$ и что $$\sum\limits\limits _{j=1}^i \mathbb R b_j = \smash[t]{\sum\limits\limits _{j=1}^i} \mathbb R b_j^*$$ для $$1 \leq i \leq n$$. Таким образом векторы $$b_1^*,\dots, b_n^*$$ образуют ортогональный базис пространства $$\mathbb R ^n$$.
В дальнейшем символ $$|\ |$$ используется как для обозначения абсолютной величины вещественных или комплексных чисел, так и для обозначения евклидовой длины вектора в вещественном векторном пространстве.
19.4. УПРАЖНЕНИЕ. Показать, что$$\begin{equation*} |\det (b_1^*,\dots, b_n^*)| = d(L) = \prod _{i=1}^n |b_i^* |. \end{equation*}$$
$$\begin{equation*} |\det (b_1^*,\dots, b_n^*)| = d(L) = \prod _{i=1}^n |b_i^* |. \end{equation*}$$ Показать, что для любого базиса $$b_1,\dots, b_n$$ решетки $$L$$ выполняется неравенство Адамара $$\begin{equation} d(L) \leq \prod _{i=1}^n |b_i |. \end{equation}$$
19.6. ОПРЕДЕЛЕНИЕ. Базис $$b_1,\dots, b_n$$ решетки $$L$$ называется редуцированным редуцированным, если выполняются неравенства$$\begin{equation} |\mu_{i,j}| \leq 1/2 \text{ для }1\leq j\leq i\leq n \end{equation}$$ и$$\begin{equation} |b_i^* + \mu_{i,i-1}b_{i-1}^*|^2 \geq \frac34|b_{i-1}^*|^2\quad\text{для}\quad 1 < i \leq n. \end{equation}$$
Векторы $$b_i^*+ \mu_{i,i-1}b^*_{i-1}$$ и $$b_{i-1}^*$$ имеют простой геометрический смысл - это проекции векторов $$b_i$$ и $$b_{i-1}$$ на ортогональное дополнение к пространству $$\sum\limits^{i-2}_{j=1} \mathbb R b_j$$ в $$\sum\limits _{j=1}^i\mathbb R b_j$$. Константа 3/4 выбирается в значительной мере произвольно: вместо нее можно взять любое фиксированное вещественное число $$y$$, удовлетворяющее условию $$1/4 < y < 1$$.
Грубо говоря, редуцированный базис состоит из "почти ортогональных" векторов, расположенных в порядке "почти неубывания длин".
Использование редуцированных базисов решеток для целей факторизации многочленов основано на следующем свойстве таких базисов: если $$b_1 ,\dots,b_n$$ - редуцированный базис решетки $$L$$, то$$\begin{equation*} |b_1|^2\leq 2^{n-1}|x|^2 \end{equation*}$$ для любого вектора $$x \in L$$. К доказательству этого свойства и его обобщений мы сейчас и переходим.
19.7. ПРЕДЛОЖЕНИЕ. Пусть $$b_1,\dots, b_n$$ - редуцированный базис решетки $$L$$ в $$\mathbb R ^n$$ и векторы $$b_1^*,\dots,b^*_n$$ получены из этого базиса процессом ортогонализации Грама - Шмидта. Тогда$$|b_j|^2\leq 2^{i-1}\cdot |b_i^*|^2\quad\text{для}\quad 1\leq j\leq i\leq n,$$ $$d(L)\leq \prod_{i=1}^n |b_i|\leq 2^{n(n-1)/4}\cdot d(L),$$ $$|b_1|\leq 2^{(n-1)/4}\cdot d(L)^{1/n}.$$
ДОКАЗАТЕЛЬСТВО. Сначала докажем формулу (19.6). Из формул (19.4) и (19.5) получаем$$\begin{equation} |b_i^*|^2\geq \left(\frac34-\mu^2_{i,i-1}\right)\cdot |b^*_{i-1}|^2\geq\frac12\cdot |b_{i-1}^*|^2 \end{equation}$$ для $$1 < i \leq n$$, откуда по индукции выводится неравенство$$\begin{align*} |b_i|^2 = |b_i^* |^2 + \sum\limits ^{i-1 }_{j=1} \mu_{i,j}^2 |b_j^* |^2 \\ \leq |b_i^*|^2+\sum\limits _{j=1}^{i-1 }\frac 14 \cdot 2^{i-j } |b_i^* |^2 \\ = \left(1 + \frac 14(2^i - 2)\right)\cdot |b_i^* |^2 \\ \leq 2^{i-1}\cdot |b_i^* |^2. \end{align*}$$
Из этих формул следует, что$$\begin{equation*} |b_j|^2\leq 2^{j-1}\cdot |b_j^* |^2 \leq 2^{i-1 } \cdot |b_i^* |^2 \end{equation*}$$ для $$1\leq j\leq i\leq n$$. Таким образом, формула (19.6) доказана.
Для доказательства формулы (19.7) достаточно воспользоваться упражнением 19.4 и неравенствами$$|b_i^* | \leq |b_i | \leq 2^{(i-1)/2 } \cdot |b_i^* |.$$ Полагая $$j=1$$ в формуле (19.6) и перемножив левые и правые части этой формулы для $$i$$ от 1 до $$n$$, получим неравенство (19.8). Этим заканчивается доказательство предложения 19.7.
19.8. УПРАЖНЕНИЕ. Показать, что если в формуле (19.5) заменить 3/4 на некоторое вещественное число $$y$$, $$1/4<y<1$$, то появляющиеся в формулах (19.6), (19.7) и (19.8) степени числа 2 заменятся на такие же степени числа $$4/(4y-1)$$.
19.9. ПРЕДЛОЖЕНИЕ. Пусть $$b_1,\dots, b_n$$ - редуцированный базис решетки $$L$$. Тогда для любого ненулевого вектора $$x \in L$$ выполняется неравенство$$\begin{equation*} |b_1 |^2 \leq 2^{n-1}\cdot |x|^2 . \end{equation*}$$
ДОКАЗАТЕЛЬСТВО. Любой вектор $$x \in L$$ может быть выражен через векторы базиса $$b_1,\dots,b_n$$ с целыми коэффициентами $$r_i$$, а через векторы $$b^*_1,\dots,b_n^*$$ - в виде линейной комбинации с вещественными коэффициентами $$r'_i$$, т.е.$$x=\sum\limits^n_{i=1}r_{ibi} = \sum\limits ^n_{i=1} r_i'b_i^*.$$ Если $$i$$ - наибольший индекс, для которого $$r_i\ne 0$$, то $$|r'_i|=|r_i|\geq 1$$. Таким образом,$$\begin{equation*} 2^{n-1 }|x|^2\geq 2^{n-1}{r'}^2_i\cdot |b_i^*|^2\geq 2^{n-1 }|b_i^*|^2 \geq 2^{i-1 }|b_i^*|^2\geq |b_1|^2. \end{equation*}$$
Последние два неравенства вытекают из формулы (19.6).
Обобщением полученного результата является следующее
19.10. ПРЕДЛОЖЕНИЕ. Пусть $$b_1, \dots, b_n$$ - редуцированный базис решетки $$L$$, $$x_1, \dots, x_t$$ - линейно независимые векторы решетки $$L$$. Тогда для любого $$j$$ от 1 до $$t$$ выполняется неравенство$$\begin{equation*} |b_j |^2 \leq 2^{n-1 } \cdot \max \{ |x_1|^2, \dots, |x_t |^2\} . \end{equation*}$$
ДОКАЗАТЕЛЬСТВО. Выразим векторы $$x_j$$ через элементы базиса $$b_i$$:$$x_j=\sum\limits^n_{i=1} r_{ij}b_i,$$ где $$r_{ij}\in\mathbb Z $$ $$(1\leq i\leq n)$$ для $$1\leq j\leq t$$. Для каждого фиксированного $$j$$ через $$i(j)$$ обозначим наибольшее значение $$i$$, для которого $$r_{ij} \ne 0$$. Перенумеруем векторы $$x_j$$ так, чтобы числа $$i(j)$$ не убывали, т.е. $$i(1) \leq i(2) \leq \dots \leq i(t)$$. Из доказательства предыдущего предложения можно получить неравенство$$\begin{equation} |x_j |^2\geq |b_{i(j)}^*|^2\quad\text{для всех $j$ от 1 до $t$.} \end{equation}$$
Покажем, что $$j \leq i(j)$$ для всех $$j$$ от 1 до $$t$$. Если это неравенство для некоторого $$j$$ не выполняется, то все векторы $$x_1 ,\dots, x_j$$ принадлежат подпространству $$\mathbb R b_1 + \mathbb R b_2 + \dots + \mathbb R b_{j-1}$$, что противоречит линейной независимости векторов $$x_1, \dots, x_t$$. Воспользовавшись неравенством $$j \leq i(j)$$ и формулами (19.6) и (19.10), получаем для всех $$j$$ от 1 до $$t$$ неравенство$$\begin{align*} |b_j |^2 \leq 2^{i(j)-1 } \cdot |b_{i(j)}^* |^2 \\ \leq2^{n-1 } \cdot |b^*_{i(j)} |^2 \\ \leq 2^{n-1 } \cdot |x_j |^2 . \end{align*}$$
Этим доказательство предложения 19.10 заканчивается.
В этом параграфе рассмотрим алгоритм построения редуцированного базиса решетки, полученный в работе . Определение решетки и редуцированного базиса приведены в параграфе 19. Там же описаны основные свойства редуцированных базисов, которые понадобятся нам в алгоритмах факторизации многочленов.
Ниже сформулирован и обоснован алгоритм построения редуцированного базиса решетки. Построение редуцированного базиса ведем, последовательно присоединяя очередной ( $$k$$ -ый) элемент исходного базиса решетки и редуцируя базис подрешетки, натянутой на векторы с 1-го по $$k$$ -ый. Алгоритм содержит два основных шага: на одном из них мы из присоединяемого вектора вычитаем целые кратные векторов, уже включенных в редуцированный базис, чтобы обеспечить выполнение условия (19.4). При этом длина редуцированной части базиса не меняется. Второй шаг, направленный на выполнение условия 19.5, сводится к перестановке добавляемого вектора с последним вектором, уже включенным в редуцированный базис, при такой перестановке длина редуцированной части базиса уменьшается на 1. Переменная $$k$$ указывает номер элемента, который пытаемся присоединить к редуцированной части базиса, т.е. редуцированная часть базиса содержит в каждый момент $$k-1$$ вектор. Начальное значение $$k$$ равно 2, т. к. любой базис решетки, порождаемой одним вектором, является редуцированным (условия (19.4) и (19.5) выполняются автоматически, поскольку нет различных индексов).
В описании алгоритма редуцирования базиса пользуемся типом данных "решетка". В отличие от принятых ранее обозначений, здесь значения индексов принадлежат отрезку $$1..n$$ (а не $$0..n-1$$ ), т.е.
$$\begin{equation} \text{решетка: запись(\=ранг == $n$: $\mathbb Z +$} \\ \text{\qquad базис: \=вектор $b$ элементов типа (вектор элементов }\\ \text{ \qquad \qquad типа $\mathbb R $ или $\mathbb Q $ с индексом $1..n$) }\\ \text{\qquad \qquad с индексом $1..n$} \end{equation}$$А33. АЛГОРИТМ (редуцирование-базиса).
$$\begin{equation} \text{Дано:\qquad $L$ - решетка, задаваемая исходным базисом}\\ \text{Надо: \qquad $L$ - решетка, задаваемая редуцированным базисом}\\ \text{Обозначения:\quad $n$ == $L$.ранг}\\ \text{\qquad $b$ == $L$.базис}\\ \text{Переменные:\quad $\mu$-нижняя треугольная матрица коэффициентов,}\\ \text{\qquad \qquad вычисляемых по формулам (19.1) и (19.2)}\\ \text{\qquad $B$-вектор элементов типа $\mathbb R $ с индексом $1..n$} \end{equation}$$Элементы вектора $$B$$ представляют собой квадраты длин соответствующих векторов из ортогонального базиса $$b^*$$, вычисляемого по формулам (19.1) и (19.2).
$$\begin{equation*} \text{Начало}\\ \text{начальная установка $(L, \mu , B)$}\\ \text{$k := 2$}\\ \text{цикл пока $k \leq n$}\\ \text{\qquad обеспечить выполнение условия (19.4) для $i=k$ и $j=k-1$}\\ \text{\qquad если условие (19.5) не выполнено, то}\\ \text{\qquad \qquad переставить $k$-ый элемент базиса $b$ с $(k-1)$-м}\\ \text{\qquad \qquad если$k > 2$ то}\\ \text{\qquad \qquad \qquad $k := k-1$}\\ \text{\qquad \qquad конец если}\\ \text{\qquad иначе}\\ \text{\qquad \qquad цикл для $j$ от $k-2$ до $1$ шаг $-1$} \\ \text{\qquad \qquad \qquad обеспечить выполнение условия (19.4) для $k,j$}\\ \text{\qquad \qquad конец цикла}\\ \text{\qquad \qquad $k := k+1$}\\ \text{\qquad конец если}\\ \text{конец цикла}\\ \text{Конец} \end{equation*}$$Детализируем предложенный алгоритм.
А34. АЛГОРИТМ (начальная-установка).
$$\begin{equation*}\\ \text{Дано:\quad $L$-решетка}\\ \text{Надо: \qquad $\mu$ - нижняя треугольная матрица коэффициентов, }\\ \text{\qquad \qquad вычисляемых по формулам (19.1) и (19.2).}\\ \text{\qquad $B$ - вектор элементов типа $\mathbb R $ с индексом $1..n$. Элементы }\\ \text{вектора $B$ представляют собой квадраты длин }\\ \text{соответствующих векторов из ортогонального }\\ \text{базиса $b1$, вычисляемого по формулам (19.1) и (19.2).}}\\ \text{Переменные:\quad $b1$ - вектор элементов типа (вектор элементов типа }\\ \text{\qquad $\mathbb R $ с индексом $1..n$) с индексом $1..n$}\\ \text{Обозначения: \qquad $n$ == $L$.ранг }\\ \text{\qquad $b$ == $L$.базис \ исходный базис решетки } \\ \text{\qquad $(a,b)$ == скалярное произведение векторов}\\ \text{Начало}\\ \text{цикл для $q$ от $1$ до $n$}\\ \text{\qquad $b1[q] := b[q]$}\\ \text{\qquad цикл для $l$ от $1$ до $q-1$}\\ \text{\qquad \qquad $\mu [q,l] := \dfrac{(b[q],b1[l])}{B[l]}$}\\ \text{\qquad \qquad $b1[q] := b1[q] - \mu [q,l]\cdot b1[l]$}\\ \text{\qquad конец цикла}\\ \text{\qquad $B[q] := (b1[q],b1[q])$}\\ \text{конец цикла}\\ \text{Конец} \end{equation*}$$Отметим, что в предлагаемой версии алгоритма переменная $$b1$$ (двумерный массив, соответствующий ортогональному базису $$b^*$$ ) локальна, в остальной части алгоритма этот базис в явном виде не используется. Применяется вектор $$B$$, элементы которого представляют собой квадраты длин ортогонального базиса, что позволяет значительно экономить память, используемую основной программой (вместо двумерного массива хранится одномерный). При этом нужно проследить, как изменяются компоненты вектора $$B$$ при различных выполняемых преобразованиях, что сделано при описании соответствующих предписаний.
А35. АЛГОРИТМ (обеспечить-выполнение-условия-(19.4)).
$$\begin{equation*}\\ \text{Дано:\quad $L$-решетка} \\ \text{\qquad $\mu$- матрица "проекций"}\\ \text{\qquad $k>j$ - индексы}\\ \text{Надо: \qquad $\mu$-треугольная матрица коэффициентов,}\\ \text{\qquad \qquad вычисляемых по формулам (19.1) и (19.2).}\\ \text{Переменные:\quad $r$ - целое}\\ \text{Начало}\\ \text{если $| \mu [k,j]| > 1/2$ то}\\ \text{\qquad $r :=$ ближайшее целое к $\mu [k,j]$}\\ \text{\qquad $b[k] := b[k] - r\cdot b[j]$}\\ \text{\qquad цикл для $i$ от $1$ до $j-1$}\\ \text{\qquad \qquad $\mu [k,i] := \mu [k,i] - r\cdot \mu [j,i]$}\\ \text{\qquad конец цикла}\\ \text{\qquad $\mu [k,j] := \mu [k,j] - r$}\\ \text{конец если}\\ \text{Конец} \end{equation*}$$Элементы нижней треугольной матрицы $$\mu$$ вычисляются по формулам (19.2). В данном алгоритме меняем только вектор с индексом $$k$$. При этом меняется только $$k$$ -ая строка матрицы $$\mu$$, из нее вычитается $$j$$ -ая строка матрицы $$(\mu -E)$$, умноженная на $$r$$. ( $$E$$ - единичная матрица.)
Прежде чем переходить к формулировке алгоритма перестановки $$k$$ -го элемента базиса с $$(k-1)$$ -м, выведем соответствующие формулы. Пусть $$b_1,\dots, b_n$$ - текущий базис, ему соответствует ортогональный базис $$b^*$$ и нижняя треугольная матрица $$\mu$$. Элементы нового базиса обозначим буквой $$c$$ с соответствующим индексом, соответствующий ортогональный базис - $$c^*$$, нижнюю треугольную матрицу - $$\nu$$. Вычислить элементы базиса $$c$$ не представляет труда:$$\begin{equation*} c_{k-1 } = b_k,\quad c_k = b_{k-1 },\quad c_i = b_i\quad\text{для}\quad i \neq k,k-1. \end{equation*}$$
Переходим к вычислению ортогонального базиса. Как отмечалось выше, левая часть равенства (19.5) представляет собой квадрат длины ортогонального дополнения $$i$$ -го вектора к подпространству, порожденному векторами с 1-го по $$(i-2)$$ -ой.
Таким образом,$$\begin{equation} c_{k-1 }^* = b_k^* + \mu _{k,k-1 } b^*_{k-1 }. \end{equation}$$
Для вычисления $$c_k^*$$ спроектируем $$b_{k-1 }^*$$ на ортогональное дополнение к $$\mathbb R c_{k-1 }^*$$. Получим$$\nu_{k,k-1} = \frac{(b_{k-1}^*, c_{k-1}^* )}{(c_{k-1}^*,c_{k-1}^*)}\notag \\ = \mu_{k,k-1} | b_{k-1}^* |^2/| c_{k-1}^* |^2$$ $$c_k^* = b_{k-1}^* - \nu_{k,k-1} c_{k-1}^*.$$ $$c_i^* = b_i^*\quad\text{для}\quad i \neq k-1,k.$$
Для вычисления коэффициентов $$\nu$$ нам понадобится выразить старый ортогональный базис через новый. Из соотношений (20.2), (20.3) и (20.4) получаем$$b_{k-1}^*= \nu_{k,k-1 } c_{k-1 }^* + c_k^*$$ $$b_k^* = (1 - \mu_{k,k-1 }\nu_{k,k-1})c_{k-1}^*- \mu_{k,k-1}c_k^*\notag\\ =(| b_k^*| ^2/| c_{k-1 }^* | ^2)\cdot c_{k-1}^* - \mu_{k,k-1} c_k^*.$$
Подставив соотношения (20.1)-(20.7)в формулу (19.1) и приведя подобные члены, получим для $$i > k$$$$\nu_{i,k-1}= \mu _{i,k-1 }\nu_{k,k-1 }+ \mu _{i,k } | b_k^*| ^2/| c_{k-1 }^* | ^2,$$ $$\nu_{i,k} = \mu _{i,k-1}- \mu_{i,k }\mu_{k,k-1 }.$$
Наконец,$$\nu_{k-1,j}=\mu_{k,j},\qquad \nu_{k,j} = \mu _{k-1,j }\quad\text{для}\quad 1\leq j<k-1 ;$$ $$\nu_{i,j} =\mu_{i,j}\quad\text{для}\quad 1\leq j<i\leq n,\quad \{i,j\} \cap \{k-1,k\} = \emptyset.$$
Реализация полученных формул описывается следующим алгоритмом:
А36. АЛГОРИТМ (переставить- $$k$$ -ый-элемент-базиса- $$b$$ - $$с$$ - $$(k - 1)$$ -м).
$$\begin{equation*} \text{Дано:\quad $k\in\mathbb Z $, } \\ \text{\qquad $L$ - решетка, } \\ \text{\qquad $\mu$ - нижняя треугольная матрица коэффициентов, вычисляемых по формулам (19.1) и (19.2),} } \\ \text{\qquad $B$ - вектор элементов типа вещественное число с индексом $1..n$. }\\ \text{Элементы вектора $B$ - это квадраты длин соответствующих векторов из} \\ \text{ортогонального базиса $b1$, вычисляемого по формулам (19.1) и (19.2).} \\ \text{Надо:\qquad $L, \mu , B$ } \\ \text{\qquad В векторе $L$.базис поменялись местами два элемента. } \\ \text{ \qquad Соответствующие изменения произошли с элементами матрицы $\mu$ и вектора $B$.} } \\ \text{Обозначения:\quad $n == L$.ранг } \\ \text{\qquad $b == L$.базис }\\ \text{Переменные:\quad \qquad $BB, \mu\mu$ - вещественные числа } \\ \text{Начало} \\ \text{$\mu \mu := \mu [k,k-1]$ } \\ \text{$BB := B[k] + \mu\mu^2 \cdot B[k-1]$} \\ \text{$\mu [k,k-1] :=\dfrac{\mu\mu \cdot B[k-1]}{BB}$} \\ \text{$B[k] :=\dfrac{B[k-1]\cdot B[k]}{BB}$ } \\ \text{$B[k-1] := BB$ } \\ \text{$\begin{pmatrix} b[k-1] \\ b[k]\end{pmatrix} := \begin{pmatrix} b[k] \\ b[k-1]\end{pmatrix}$ } \\ \text{цикл для $i$ от $1$ до $k-2$ } \\ \text{\qquad $\begin{pmatrix} \mu [k-1,i] \\ \mu [k,i] \end{pmatrix} := \begin{pmatrix} \mu [k,i] \\ \mu [k-1,i] \end{pmatrix}$ } \\ \text{конец цикла } \\ \text{цикл для $i$ от $k+1$ до $n$ } \\ \text{\qquad $\begin{pmatrix} \mu [i,k-1] \\ \mu [i,k] \end{pmatrix} := \begin{pmatrix} 1 \mu [k,k-1] \\ 0 1 \end{pmatrix} \begin{pmatrix} 0 1 \\ 1 -\mu\mu \end{pmatrix} $ } \text{$\begin{pmatrix} \mu [i,k-1] \\ \mu [i,k] \end{pmatrix}$ } \\ \text{конец цикла} \\ \text{Конец} \end{equation*}$$Переходим к обоснованию алгоритма A33 построения редуцированного базиса решетки. Оно состоит из доказательства двух утверждений. Во-первых, докажем, что если алгоритм завершит свою работу, то в результате получим редуцированный базис данной решетки. Во-вторых, докажем, что для любого исходного базиса решетки алгоритм после конечного числа шагов закончит работу.
Для доказательства первого утверждения заметим, что мы выполняем над элементами базиса только элементарные преобразования, которые переводят базис $$\mathbb Z $$ -модуля в другой базис того же самого $$\mathbb Z $$ -модуля, т. к. и перестановка элементов базиса и прибавление к одному из элементов целого кратного другого - обратимые операции. Таким образом, в любой момент времени $$b$$ представляет собой базис исходной решетки. Элементы этого базиса с 1-го по $$(k-1)$$ -ый представляют собой редуцированный базис подрешетки, порожденной этими элементами, т. к. для них выполнены условия (19.4) и (19.5). Когда мы производим преобразования вектора $$b[k]$$, направленные на то, чтобы для него выполнялись условия (19.4), эти преобразования никак не отражаются на векторах с 1-го по $$(k-1)$$ -ый, а если мы производим перестановку $$k$$ -го элемента базиса с $$(k-1)$$ -ым, то уменьшаем длину редуцированной части базиса на 1 (если она больше 1; меньше 1 длина редуцированной части базиса быть не может) и одновременно уменьшаем значение $$k$$. Для векторов с 1-го по $$(k-1)$$ -ый снова выполнены условия (19.4) и (19.5). Таким образом, если алгоритм завершил свою работу, то получившийся базис - редуцированный базис исходной решетки $$L$$.
Прежде чем перейти к доказательству второго утверждения, приведем несколько определений и задач различной степени сложности.
20.1. УПРАЖНЕНИЕ. Пусть $$m(L) =\min \{ | x| ^2: x \in L, x\neq 0\}$$. Показать, что для любой решетки $$L$$ выполняется неравенство $$m(L) > 0$$.
Введем обозначение$$\begin{equation} d_i =\det ((b_j , b_l ))_{1\leq j,l\leq i }\text { для } 0 \leq i \leq n. \end{equation}$$
20.2. УПРАЖНЕНИЕ. Показать, что для всех $$i$$ от 1 до $$n$$ выполняется равенство $$d_i =\prod\limits_{j=1 }^i| b_j^*| ^2$$.
Для всех $$i > 0$$ числа $$d_i$$ могут быть
интерпретированы как квадраты
20.3. УПРАЖНЕНИЕ. Показать, что каждая такая решетка содержит ненулевой вектор $$x$$, удовлетворяющий неравенству$$\begin{equation*} | x| ^2 \leq (4/3)^{(i-1)/2}\cdot d_i^{1/i}. \end{equation*}$$
Переходим теперь к доказательству второй части утверждения о корректности алгоритма построения редуцированного базиса. Пусть$$\begin{equation*} D=\prod\limits_{j=1}^{n-1}d_i. \end{equation*}$$
Из упражнения 20.2 следует, что значение $$D$$ меняется только тогда, когда изменяется хотя бы один из векторов $$b_i^*$$. Это может произойти только при перестановке двух векторов базиса. При этом новое значение $$| b_{i-1 }^* |$$ равно $$| b_i^* + \mu _{i\,i-1 }b_{i-1 }^* |$$, что по условию меньше, чем 3/4 от прежнего значения этой величины. Таким образом, при каждой выполняемой перестановке элементов базиса значение величины $$D$$ умножается на положительное число, меньшее 3/4. Из упражнений 20.1-20.3 следует, что $$D$$ ограничено снизу некоторой положительной величиной, следовательно, перестановка элементов выполняется в алгоритме только конечное число раз, обозначим его $$m$$. При каждом выполнении перестановки значение $$i$$ уменьшается на 1, при выполнении команд, следующих за ключевым словом "иначе" в алгоритме, значение $$i$$ увеличивается на 1. Начальное значение $$i$$ равно 2, алгоритм продолжает работу до тех пор, пока $$i \leq n$$, следовательно, ситуация "иначе" встречается $$m+n-1$$ раз, т.е. тело цикла "пока" выполняется конечное число раз. Таким образом, алгоритм завершает работу после выполнения конечного числа шагов. Ниже мы оценим это число для случая, когда все координаты исходного базиса решетки - целые числа.
Итак, переходим к оценке сложности алгоритма построения редуцированного базиса решетки в предположении, что все координаты исходного базиса являются целыми числами. Именно такой случай нам понадобится для получения алгоритма факторизации полиномиальной сложности. Наша цель сейчас - доказательство следующего предложения.
20.4. ПРЕДЛОЖЕНИЕ. Пусть $$L \subset \mathbb Z ^n$$ - решетка с базисом $$b_1,\dots, b_n$$ и предположим, что задано положительное число $$B\ge2$$ , такое, что для любого вектора $$b_i$$ из исходного базиса решетки выполняется неравенство $$|b_i|^2 \leq B$$. Тогда алгоритм построения редуцированного базиса, описанный выше, требует для своего выполнения $$O(n^4\log B)$$ арифметических операций над целыми числами, двоичная длина которых представляет $$O(n\log B)$$. Таким образом, для построения редуцированного базиса достаточно $$O(n^6\log^3B)$$ бинарных операций.
ДОКАЗАТЕЛЬСТВО. Перед началом работы алгоритма величины $$d_i$$, определенные формулами (20.12) удовлетворяют неравенству $$d_i\leq B^i$$, что легко следует из упражнения 20.2. Таким образом, перед началом работы алгоритма $$D \leq B^{n(n-1)/2}$$. Из определения $$D$$ легко следует, что в случае, когда $$L \subset \mathbb Z ^n$$, $$D$$ - неотрицательное целое число, которое не может обратиться в нуль, в силу линейной независимости векторов, составляющих базис решетки. Таким образом, $$D\ge1$$ во все время работы алгоритма. Выше отмечалось, что при перестановках элементов базиса, выполняемых алгоритмом построения редуцированного базиса, величина $$D$$ убывает не медленнее геометрической прогрессии со знаменателем 3/4, следовательно, таких перестановок выполняется $$O(\log B^{n(n-1)/2}) = O(n^2\log B)$$. Мы оценили, таким образом, сколько раз в головной программе, в цикле "пока" встречается ситуация "то" в условии "если". Из доказательства конечности времени работы алгоритма следует, что ситуация "иначе" встречается также $$O(n^2 \log B)$$ раз. Итак, тело цикла в основном алгоритме выполняется $$O(n^2 \log B)$$ раз. Внутренний цикл в ситуации "иначе" дает еще один множитель $$n$$ для алгоритма A35, который выполняется таким образом $$O(n^3\log B)$$ раз. Переходим теперь к оценке сложности отдельных предписаний алгоритма A33.
В предписании "начальная-установка" два вложенных цикла дают $$O(n^2)$$ повторений тела цикла, в котором встречаются векторные операции: скалярное произведение векторов, умножение вектора на число, вычитание векторов, что дает еще один множитель $$n$$. При этом арифметические операции выполняются над рациональными числами. Сложность выполнения операций над этими числами оценим несколько позже.
Количество арифметических операций в алгоритме A35, как легко видеть, равно $$O(n)$$, такое же количество операций в алгоритме A36. Сравнивая количество проходов через отдельные ветви алгоритма, получаем, что количество арифметических операций в алгоритме представляется величиной $$O(n^4\log B)$$, что и утверждалось в первой части предложения.
Оценим теперь сложность выполнения арифметических операций, выполняемых над рациональными числами в процессе работы алгоритма A33. Прежде всего, опишем множество значений, которые могут принимать знаменатели всех встречающихся во время вычислений рациональных чисел. Покажем, что в качестве знаменателей всех встречающихся чисел могут быть использованы только числа $$d_i$$, вычисляемые по формулам (20.12), а именно:$$| b_i^*| ^2= \frac{d_i}{d_{i-1 }}, (1 \leq i \leq n),$$ $$d_{i-1 }b_i^* \in L \subset \mathbb Z ^n, (1 \leq i \leq n),$$ $$d_j\mu _{ij }\in \mathbb Z , (1 \leq j < i \leq n).$$
Первое из этих соотношений следует из упражнения 20.2.
Для доказательства второго соотношения выразим векторы $$b_i^*$$ с неопределенными коэффициентами $$y_{ij }$$ через исходный базис:$$\begin{equation*} b_i^* = b_i - \sum\limits _{j=1 }^{i-1}y_{ij } b_j . \end{equation*}$$
Неизвестные коэффициенты с фиксированным первым индексом $$i$$ определяются из системы линейных уравнений$$\begin{equation*}\label{20.16} (b_i ,b_l ) = \sum\limits _{j=1 }^{i-1}y_{ij }(b_j ,b_l ) \end{equation*}$$
Решая систему (20.16) методом Крамера, воспользовавшись формулой (20.12) получаем, что $$d_{i-1 }y_{ij }\in \mathbb Z $$ для всех допустимых значений индексов. Отсюда уже вытекает соотношение (20.14).
Воспользовавшись соотношениями (19.2), (20.13) и (20.14), получаем цепочку равенств$$\begin{align*} d_j \mu _{ij }= d_j \frac{(b_i ,b_j^*)}{(b_j^*,b_j^*)}= d_{j-1 }(b_i ,b_j^*) =(b_i ,d_{j-1 }b_j^*) \in Z, \end{align*}$$ чем заканчивается доказательство соотношения (20.15).
Посмотрим теперь, как меняются величины $$d_i$$ в процессе работы алгоритма. В начале работы алгоритма они вычисляются по формулам (20.12). В процессе работы эти величины меняются только при перестановке элементов базиса (в алгоритме A36 ). В этом случае $$d_{k-1 }$$ заменяется (в обозначениях (20.1)-(20.5)) на$$d_{k-1 } \cdot\frac{| c_{k-1 }^* | ^2}{| b_{k-1 }^* | ^2} = d_{k-2 } \cdot | c_{k-1}^* | ^2,$$ значения $$d_i$$ при $$i\neq k-1$$ не меняются. При этом все значения $$d_i$$ остаются целыми и во все время работы алгоритма удовлетворяют неравенствам $$d_i^i \leq B$$. Таким образом, мы оценили множество чисел, которые могут появляться в вычислениях в качестве знаменателей.
Для оценки числителей достаточно найти верхнюю грань для величин $$|b_i^*|^2$$, $$|b_i|^2$$ и $$|\mu_{ij}|$$. Первая из этих величин оценивается просто: в начале работы алгоритма выполняются неравенства $$| b_i^*| ^2 \leq | b_i | ^2 \leq B$$. В процессе работы величина $$\max\{ | b_i^*|^2: 1 \leq i \leq n\}$$ не возрастает, для доказательства чего достаточно заметить, что изменение векторов $$b_i^*$$ происходит только при перестановке элементов базиса, при этом выполняются неравенства $$| c_{k-1 }^*|^2<\frac34 | b_{k-1 }^* | ^2$$ и $$| c_k^*| ^2 \leq | b_{k-1 }^*| ^2$$, поскольку $$c_k^*$$ - проекция вектора $$b_{k-1 }^*$$. Таким образом, во все время работы алгоритма $$| b_k^*| ^2 \leq B$$. Оценка величин $$| b_i | ^2$$ и $$\mu _{ij}$$ существенно сложнее. Чтобы получить ее, докажем, что всякий раз в точке проверки условия окончания цикла "пока" выполняются следующие неравенства:
$$|b_i|^2 \leq nB \text{ для } i \neq k;$$ $$|b_k|^2 \leq n^2(4B)^n, \text{ если }k \neq n+1;$$ $$|\mu_{ij}|\leq 1/2 \text{ для } 1 \leq j < i < k;\\$$ $$|\mu_{ij}|\leq(nB^j)^{1/2} \text{ для } 1\leq j<i,\ i > k;$$ $$|\mu_{kj}|\leq2^{n-k}(nB^{n-1})^{1/2} \text{ для } 1\leq j<k, \text{ если } k \neq n+1.$$При доказательстве этих неравенств пользуемся следующим соотношением:$$\begin{equation} \mu _{ij }^2 \leq \frac{|b_i|^2}{|b_j^*|^2} =\frac{d_{j-1 }| b_i |^2}{d_j} \leq B^{j-1}| b_i | ^2. \end{equation}$$
Перед первым выполнением тела цикла неравенства (20.17) и (20.18) следуют из неравенства $$|b_i|^2\leq B$$, которое выполняется по определению $$B$$. Вместе с (20.22) это неравенство дает соотношение $$| \mu _{ij } | \leq B^{j/2}$$, откуда следует (20.19) и (20.20), а учитывая, что $$B 2$$, и (20.21). Таким образом, перед первым выполнением тела цикла неравенства (20.17)-(20.21) справедливы.
Предположим теперь, что неравенства (20.17)-(20.21) выполнены перед началом выполнения тела цикла, и покажем, что эти неравенства будут выполнены и в конце тела цикла, т.е. перед выполнением следующего цикла. Неравенство (20.19) совпадает с (19.4), которое выполняется для текущего $$k$$ все время работы алгоритма A33, в том числе и в начале цикла. Выполнение неравенства (20.17) для $$i < k$$ следует из соотношений (19.1), (20.19) и неравенства $$| b_i^*| ^2 < B$$. Покажем, что из (20.17) для $$i>k$$ и из неравенства (20.21) следуют неравенства (20.18) и (20.20). Доказательство (20.18) сводится к разложению $$b_k$$ в сумму по формуле (19.1), применению неравенства (20.21) и вычислению суммы геометрической прогрессии. Неравенство (20.20) непосредственно вытекает из (20.22) и (20.17).
Итак, покажем, что если перед началом выполнения тела цикла справедливы неравенства (20.17)-(20.21), то и после его выполнения неравенства (20.17) и (20.21) также имеют место. Отдельно рассмотрим два случая: работа алгоритма осуществляется по ветви "то", т.е. два вектора меняются местами; второй случай - алгоритм идет на ветвь "иначе", т.е. осуществляется выполнение условия (19.4) для всех $$j < k$$.
В первом случае множество векторов $$\{ b_i :i< k\}$$ не изменилось (мы поменяли местами $$k$$ -ый вектор с $$(k-1)$$ -ым и уменьшили после этого $$k$$ на 1). Во втором случае множество $$\{ b_i: i>k\}$$ векторов, для которых нам нужно доказать неравенство (20.17), заменилось на собственное его подмножество. Этим заканчивается индуктивный шаг для неравенства (20.17).
Переходим к оценке $$\mu _{kj }$$ (если $$k \neq n+1$$ ). Снова в теле цикла может выполняться одна из двух серий команд, причем в конце каждой серии значение переменной $$k$$ меняется, либо увеличиваясь, либо уменьшаясь на 1. Значение $$k$$ увеличивается, когда алгоритм идет по второй ветви, т.е. достигается выполнение условия (19.4) для всех $$j < k$$ (отдельно, до цикла достигается это условие для $$j=k-1$$, в цикле - для $$j < k-1$$ ). Эти операции никак не влияют на $$\mu _{ij}$$, если $$i > k$$, в частности, при $$i=k+1$$. На следующем шаге значение $$k$$ увеличивается на 1, и неравенства (20.21) следуют из (20.20), которые выполняются на предыдущем этапе.
Значение $$k$$ уменьшается на 1, если в теле цикла выполняется перестановка векторов, при этом после ее выполнения новые значения коэффициентов $$\mu _{kj}$$ совпадают со старыми значениями (с учетом замены $$k$$ на $$k-1$$ ). Остается только проследить, как изменилось значение коэффициентов $$\mu _{kj }$$, когда до перестановки векторов мы добивались выполнения условия (19.4) для $$\mu _{k\,k-1 }$$. При этом к $$k$$ -ой строке матрицы $$\mu$$ прибавлялась ( $$k-1$$ )-я строка, умноженная на $$r$$, где $$| r| < 2| \mu _{k\,k-1 }|$$. Учитывая, что $$| \mu _{k-1\,j }| < 1/2$$, получаем$$ | \mu _{kj }- r \mu _{k-1\,j }| \leq | \mu_{kj }| + | \mu _{k\,k-1 }| \leq \\ \text{(по индуктивному предположению)} \\ \leq 2^{n-k+1}(nB^{n-1})^{1/2}. $$
Поскольку новое значение $$k$$ на 1 меньше старого, получаем требуемую формулу, доказательство неравенств (20.17)-(20.21) закончено.
Для завершения доказательства предложения 20.4 нам осталось только оценить значения, получающиеся на промежуточных этапах алгоритма. Заметим, что при выполнении алгоритма A35 значения коэффициентов $$\mu$$ не более, чем удваиваются. Поскольку в одном теле основного цикла алгоритм A35 выполняется не более, чем $$k-1$$ раз, то
$$| \mu _{ij }| \leq 2^{n-1}(nB^{n-1})^{1/2}\text{ для } j < k-1,$$откуда, воспользовавшись формулами (19.1), ортогональностью векторов $$b_i^*$$, неравенствами $$| b_i^*| < B$$ получаем неравенства $$| b_i | ^2 \leq n^2(4B)^n$$ для $$1\leq i\leq n$$. Остается перемножить границы для знаменателей и для абсолютных величин, прологарифмировать и выделить главную часть, чтобы получить оценки, фигурирующие в предложении 20.4.
19.1. ОПРЕДЕЛЕНИЕ. Решеткой в $$n$$ -мерном векторном пространстве над полем вещественных чисел $$\mathbb R $$ или над полем рациональных чисел $$\mathbb Q $$ называется свободный $$\mathbb Z $$ -модуль $$L$$ ранга $$n$$, т.е. существует базис $$b_1,\dots,b_n$$ пространства $$\mathbb R ^n$$ (соответственно $$\mathbb Q ^n$$ ), такой, что$$\begin{equation*} L=\sum\limits ^n_{i=1}\mathbb Z b_i = \biggl\{ \sum\limits ^n_{i=1} r_i b_i\ |\ r_i \in\mathbb Z ,\quad 1\leq i\leq n \biggr\}. \end{equation*}$$ В этом случае $$n$$ называется рангом решетки, а множество векторов $$b_1,\dots,b_n$$ - ее базисом.
19.2. ОПРЕДЕЛЕНИЕ. Детерминантом $$d(L)$$ решетки $$L$$ называется положительное число, определяемое формулой$$\begin{equation*} d(L) = |\det (b_1 , b_2 ,\dots, b_n )|, \end{equation*}$$ для некоторого базиса $$b_1,b_2,\dots, b_n$$ решетки $$L$$.
19.3. УПРАЖНЕНИЕ. Показать, что определение 19.2 является корректным, т.е. $$d(L)$$ не зависит от выбора базиса решетки $$L$$.
Прежде чем дать определение редуцированного базиса решетки, нам необходимо напомнить процесс ортогонализации Грама-Шмидта. Векторы $$b_i^*$$ $$\smu{2}(1\leq i\leq n)$$ и вещественные числа $$\mu_{i,j}$$ $$(1\leq j< i\leq n)$$ определяются по индукции формулами
$$b_i^*=b_i-\sum\limits _{j=1}^{i-1} \mu_{i,j}b_j^*,$$ $$\mu_{i,j}=\frac{(b_i , b_j^* )}{(b_j^* ,b_j^* )}.$$Отметим, что $$b_i^*$$ - проекция вектора $$b_i$$ на ортогональное дополнение к пространству $$\sum\limits\limits _{j=1}^{i-1}\mathbb R b_j$$ в пространстве $$\sum\limits\limits _{j=1}^i \mathbb R b_j$$ и что $$\sum\limits\limits _{j=1}^i \mathbb R b_j = \smash[t]{\sum\limits\limits _{j=1}^i} \mathbb R b_j^*$$ для $$1 \leq i \leq n$$. Таким образом векторы $$b_1^*,\dots, b_n^*$$ образуют ортогональный базис пространства $$\mathbb R ^n$$.
В дальнейшем символ $$|\ |$$ используется как для обозначения абсолютной величины вещественных или комплексных чисел, так и для обозначения евклидовой длины вектора в вещественном векторном пространстве.
19.4. УПРАЖНЕНИЕ. Показать, что$$\begin{equation*} |\det (b_1^*,\dots, b_n^*)| = d(L) = \prod _{i=1}^n |b_i^* |. \end{equation*}$$
$$\begin{equation*} |\det (b_1^*,\dots, b_n^*)| = d(L) = \prod _{i=1}^n |b_i^* |. \end{equation*}$$ Показать, что для любого базиса $$b_1,\dots, b_n$$ решетки $$L$$ выполняется неравенство Адамара $$\begin{equation} d(L) \leq \prod _{i=1}^n |b_i |. \end{equation}$$
19.6. ОПРЕДЕЛЕНИЕ. Базис $$b_1,\dots, b_n$$ решетки $$L$$ называется редуцированным редуцированным, если выполняются неравенства$$\begin{equation} |\mu_{i,j}| \leq 1/2 \text{ для }1\leq j\leq i\leq n \end{equation}$$ и$$\begin{equation} |b_i^* + \mu_{i,i-1}b_{i-1}^*|^2 \geq \frac34|b_{i-1}^*|^2\quad\text{для}\quad 1 < i \leq n. \end{equation}$$
Векторы $$b_i^*+ \mu_{i,i-1}b^*_{i-1}$$ и $$b_{i-1}^*$$ имеют простой геометрический смысл - это проекции векторов $$b_i$$ и $$b_{i-1}$$ на ортогональное дополнение к пространству $$\sum\limits^{i-2}_{j=1} \mathbb R b_j$$ в $$\sum\limits _{j=1}^i\mathbb R b_j$$. Константа 3/4 выбирается в значительной мере произвольно: вместо нее можно взять любое фиксированное вещественное число $$y$$, удовлетворяющее условию $$1/4 < y < 1$$.
Грубо говоря, редуцированный базис состоит из "почти ортогональных" векторов, расположенных в порядке "почти неубывания длин".
Использование редуцированных базисов решеток для целей факторизации многочленов основано на следующем свойстве таких базисов: если $$b_1 ,\dots,b_n$$ - редуцированный базис решетки $$L$$, то$$\begin{equation*} |b_1|^2\leq 2^{n-1}|x|^2 \end{equation*}$$ для любого вектора $$x \in L$$. К доказательству этого свойства и его обобщений мы сейчас и переходим.
19.7. ПРЕДЛОЖЕНИЕ. Пусть $$b_1,\dots, b_n$$ - редуцированный базис решетки $$L$$ в $$\mathbb R ^n$$ и векторы $$b_1^*,\dots,b^*_n$$ получены из этого базиса процессом ортогонализации Грама - Шмидта. Тогда$$|b_j|^2\leq 2^{i-1}\cdot |b_i^*|^2\quad\text{для}\quad 1\leq j\leq i\leq n,$$ $$d(L)\leq \prod_{i=1}^n |b_i|\leq 2^{n(n-1)/4}\cdot d(L),$$ $$|b_1|\leq 2^{(n-1)/4}\cdot d(L)^{1/n}.$$
ДОКАЗАТЕЛЬСТВО. Сначала докажем формулу (19.6). Из формул (19.4) и (19.5) получаем$$\begin{equation} |b_i^*|^2\geq \left(\frac34-\mu^2_{i,i-1}\right)\cdot |b^*_{i-1}|^2\geq\frac12\cdot |b_{i-1}^*|^2 \end{equation}$$ для $$1 < i \leq n$$, откуда по индукции выводится неравенство$$\begin{align*} |b_i|^2 = |b_i^* |^2 + \sum\limits ^{i-1 }_{j=1} \mu_{i,j}^2 |b_j^* |^2 \\ \leq |b_i^*|^2+\sum\limits _{j=1}^{i-1 }\frac 14 \cdot 2^{i-j } |b_i^* |^2 \\ = \left(1 + \frac 14(2^i - 2)\right)\cdot |b_i^* |^2 \\ \leq 2^{i-1}\cdot |b_i^* |^2. \end{align*}$$
Из этих формул следует, что$$\begin{equation*} |b_j|^2\leq 2^{j-1}\cdot |b_j^* |^2 \leq 2^{i-1 } \cdot |b_i^* |^2 \end{equation*}$$ для $$1\leq j\leq i\leq n$$. Таким образом, формула (19.6) доказана.
Для доказательства формулы (19.7) достаточно воспользоваться упражнением 19.4 и неравенствами$$|b_i^* | \leq |b_i | \leq 2^{(i-1)/2 } \cdot |b_i^* |.$$ Полагая $$j=1$$ в формуле (19.6) и перемножив левые и правые части этой формулы для $$i$$ от 1 до $$n$$, получим неравенство (19.8). Этим заканчивается доказательство предложения 19.7.
19.8. УПРАЖНЕНИЕ. Показать, что если в формуле (19.5) заменить 3/4 на некоторое вещественное число $$y$$, $$1/4<y<1$$, то появляющиеся в формулах (19.6), (19.7) и (19.8) степени числа 2 заменятся на такие же степени числа $$4/(4y-1)$$.
19.9. ПРЕДЛОЖЕНИЕ. Пусть $$b_1,\dots, b_n$$ - редуцированный базис решетки $$L$$. Тогда для любого ненулевого вектора $$x \in L$$ выполняется неравенство$$\begin{equation*} |b_1 |^2 \leq 2^{n-1}\cdot |x|^2 . \end{equation*}$$
ДОКАЗАТЕЛЬСТВО. Любой вектор $$x \in L$$ может быть выражен через векторы базиса $$b_1,\dots,b_n$$ с целыми коэффициентами $$r_i$$, а через векторы $$b^*_1,\dots,b_n^*$$ - в виде линейной комбинации с вещественными коэффициентами $$r'_i$$, т.е.$$x=\sum\limits^n_{i=1}r_{ibi} = \sum\limits ^n_{i=1} r_i'b_i^*.$$ Если $$i$$ - наибольший индекс, для которого $$r_i\ne 0$$, то $$|r'_i|=|r_i|\geq 1$$. Таким образом,$$\begin{equation*} 2^{n-1 }|x|^2\geq 2^{n-1}{r'}^2_i\cdot |b_i^*|^2\geq 2^{n-1 }|b_i^*|^2 \geq 2^{i-1 }|b_i^*|^2\geq |b_1|^2. \end{equation*}$$
Последние два неравенства вытекают из формулы (19.6).
Обобщением полученного результата является следующее
19.10. ПРЕДЛОЖЕНИЕ. Пусть $$b_1, \dots, b_n$$ - редуцированный базис решетки $$L$$, $$x_1, \dots, x_t$$ - линейно независимые векторы решетки $$L$$. Тогда для любого $$j$$ от 1 до $$t$$ выполняется неравенство$$\begin{equation*} |b_j |^2 \leq 2^{n-1 } \cdot \max \{ |x_1|^2, \dots, |x_t |^2\} . \end{equation*}$$
ДОКАЗАТЕЛЬСТВО. Выразим векторы $$x_j$$ через элементы базиса $$b_i$$:$$x_j=\sum\limits^n_{i=1} r_{ij}b_i,$$ где $$r_{ij}\in\mathbb Z $$ $$(1\leq i\leq n)$$ для $$1\leq j\leq t$$. Для каждого фиксированного $$j$$ через $$i(j)$$ обозначим наибольшее значение $$i$$, для которого $$r_{ij} \ne 0$$. Перенумеруем векторы $$x_j$$ так, чтобы числа $$i(j)$$ не убывали, т.е. $$i(1) \leq i(2) \leq \dots \leq i(t)$$. Из доказательства предыдущего предложения можно получить неравенство$$\begin{equation} |x_j |^2\geq |b_{i(j)}^*|^2\quad\text{для всех $j$ от 1 до $t$.} \end{equation}$$
Покажем, что $$j \leq i(j)$$ для всех $$j$$ от 1 до $$t$$. Если это неравенство для некоторого $$j$$ не выполняется, то все векторы $$x_1 ,\dots, x_j$$ принадлежат подпространству $$\mathbb R b_1 + \mathbb R b_2 + \dots + \mathbb R b_{j-1}$$, что противоречит линейной независимости векторов $$x_1, \dots, x_t$$. Воспользовавшись неравенством $$j \leq i(j)$$ и формулами (19.6) и (19.10), получаем для всех $$j$$ от 1 до $$t$$ неравенство$$\begin{align*} |b_j |^2 \leq 2^{i(j)-1 } \cdot |b_{i(j)}^* |^2 \\ \leq2^{n-1 } \cdot |b^*_{i(j)} |^2 \\ \leq 2^{n-1 } \cdot |x_j |^2 . \end{align*}$$
Этим доказательство предложения 19.10 заканчивается.
В этом параграфе рассмотрим алгоритм построения редуцированного базиса решетки, полученный в работе . Определение решетки и редуцированного базиса приведены в параграфе 19. Там же описаны основные свойства редуцированных базисов, которые понадобятся нам в алгоритмах факторизации многочленов.
Ниже сформулирован и обоснован алгоритм построения редуцированного базиса решетки. Построение редуцированного базиса ведем, последовательно присоединяя очередной ( $$k$$ -ый) элемент исходного базиса решетки и редуцируя базис подрешетки, натянутой на векторы с 1-го по $$k$$ -ый. Алгоритм содержит два основных шага: на одном из них мы из присоединяемого вектора вычитаем целые кратные векторов, уже включенных в редуцированный базис, чтобы обеспечить выполнение условия (19.4). При этом длина редуцированной части базиса не меняется. Второй шаг, направленный на выполнение условия 19.5, сводится к перестановке добавляемого вектора с последним вектором, уже включенным в редуцированный базис, при такой перестановке длина редуцированной части базиса уменьшается на 1. Переменная $$k$$ указывает номер элемента, который пытаемся присоединить к редуцированной части базиса, т.е. редуцированная часть базиса содержит в каждый момент $$k-1$$ вектор. Начальное значение $$k$$ равно 2, т. к. любой базис решетки, порождаемой одним вектором, является редуцированным (условия (19.4) и (19.5) выполняются автоматически, поскольку нет различных индексов).
В описании алгоритма редуцирования базиса пользуемся типом данных "решетка". В отличие от принятых ранее обозначений, здесь значения индексов принадлежат отрезку $$1..n$$ (а не $$0..n-1$$ ), т.е.
$$\begin{equation} \text{решетка: запись(\=ранг == $n$: $\mathbb Z +$} \\ \text{\qquad базис: \=вектор $b$ элементов типа (вектор элементов }\\ \text{ \qquad \qquad типа $\mathbb R $ или $\mathbb Q $ с индексом $1..n$) }\\ \text{\qquad \qquad с индексом $1..n$} \end{equation}$$А33. АЛГОРИТМ (редуцирование-базиса).
$$\begin{equation} \text{Дано:\qquad $L$ - решетка, задаваемая исходным базисом}\\ \text{Надо: \qquad $L$ - решетка, задаваемая редуцированным базисом}\\ \text{Обозначения:\quad $n$ == $L$.ранг}\\ \text{\qquad $b$ == $L$.базис}\\ \text{Переменные:\quad $\mu$-нижняя треугольная матрица коэффициентов,}\\ \text{\qquad \qquad вычисляемых по формулам (19.1) и (19.2)}\\ \text{\qquad $B$-вектор элементов типа $\mathbb R $ с индексом $1..n$} \end{equation}$$Элементы вектора $$B$$ представляют собой квадраты длин соответствующих векторов из ортогонального базиса $$b^*$$, вычисляемого по формулам (19.1) и (19.2).
$$\begin{equation*} \text{Начало}\\ \text{начальная установка $(L, \mu , B)$}\\ \text{$k := 2$}\\ \text{цикл пока $k \leq n$}\\ \text{\qquad обеспечить выполнение условия (19.4) для $i=k$ и $j=k-1$}\\ \text{\qquad если условие (19.5) не выполнено, то}\\ \text{\qquad \qquad переставить $k$-ый элемент базиса $b$ с $(k-1)$-м}\\ \text{\qquad \qquad если$k > 2$ то}\\ \text{\qquad \qquad \qquad $k := k-1$}\\ \text{\qquad \qquad конец если}\\ \text{\qquad иначе}\\ \text{\qquad \qquad цикл для $j$ от $k-2$ до $1$ шаг $-1$} \\ \text{\qquad \qquad \qquad обеспечить выполнение условия (19.4) для $k,j$}\\ \text{\qquad \qquad конец цикла}\\ \text{\qquad \qquad $k := k+1$}\\ \text{\qquad конец если}\\ \text{конец цикла}\\ \text{Конец} \end{equation*}$$Детализируем предложенный алгоритм.
А34. АЛГОРИТМ (начальная-установка).
$$\begin{equation*}\\ \text{Дано:\quad $L$-решетка}\\ \text{Надо: \qquad $\mu$ - нижняя треугольная матрица коэффициентов, }\\ \text{\qquad \qquad вычисляемых по формулам (19.1) и (19.2).}\\ \text{\qquad $B$ - вектор элементов типа $\mathbb R $ с индексом $1..n$. Элементы }\\ \text{вектора $B$ представляют собой квадраты длин }\\ \text{соответствующих векторов из ортогонального }\\ \text{базиса $b1$, вычисляемого по формулам (19.1) и (19.2).}}\\ \text{Переменные:\quad $b1$ - вектор элементов типа (вектор элементов типа }\\ \text{\qquad $\mathbb R $ с индексом $1..n$) с индексом $1..n$}\\ \text{Обозначения: \qquad $n$ == $L$.ранг }\\ \text{\qquad $b$ == $L$.базис \ исходный базис решетки } \\ \text{\qquad $(a,b)$ == скалярное произведение векторов}\\ \text{Начало}\\ \text{цикл для $q$ от $1$ до $n$}\\ \text{\qquad $b1[q] := b[q]$}\\ \text{\qquad цикл для $l$ от $1$ до $q-1$}\\ \text{\qquad \qquad $\mu [q,l] := \dfrac{(b[q],b1[l])}{B[l]}$}\\ \text{\qquad \qquad $b1[q] := b1[q] - \mu [q,l]\cdot b1[l]$}\\ \text{\qquad конец цикла}\\ \text{\qquad $B[q] := (b1[q],b1[q])$}\\ \text{конец цикла}\\ \text{Конец} \end{equation*}$$Отметим, что в предлагаемой версии алгоритма переменная $$b1$$ (двумерный массив, соответствующий ортогональному базису $$b^*$$ ) локальна, в остальной части алгоритма этот базис в явном виде не используется. Применяется вектор $$B$$, элементы которого представляют собой квадраты длин ортогонального базиса, что позволяет значительно экономить память, используемую основной программой (вместо двумерного массива хранится одномерный). При этом нужно проследить, как изменяются компоненты вектора $$B$$ при различных выполняемых преобразованиях, что сделано при описании соответствующих предписаний.
А35. АЛГОРИТМ (обеспечить-выполнение-условия-(19.4)).
$$\begin{equation*}\\ \text{Дано:\quad $L$-решетка} \\ \text{\qquad $\mu$- матрица "проекций"}\\ \text{\qquad $k>j$ - индексы}\\ \text{Надо: \qquad $\mu$-треугольная матрица коэффициентов,}\\ \text{\qquad \qquad вычисляемых по формулам (19.1) и (19.2).}\\ \text{Переменные:\quad $r$ - целое}\\ \text{Начало}\\ \text{если $| \mu [k,j]| > 1/2$ то}\\ \text{\qquad $r :=$ ближайшее целое к $\mu [k,j]$}\\ \text{\qquad $b[k] := b[k] - r\cdot b[j]$}\\ \text{\qquad цикл для $i$ от $1$ до $j-1$}\\ \text{\qquad \qquad $\mu [k,i] := \mu [k,i] - r\cdot \mu [j,i]$}\\ \text{\qquad конец цикла}\\ \text{\qquad $\mu [k,j] := \mu [k,j] - r$}\\ \text{конец если}\\ \text{Конец} \end{equation*}$$Элементы нижней треугольной матрицы $$\mu$$ вычисляются по формулам (19.2). В данном алгоритме меняем только вектор с индексом $$k$$. При этом меняется только $$k$$ -ая строка матрицы $$\mu$$, из нее вычитается $$j$$ -ая строка матрицы $$(\mu -E)$$, умноженная на $$r$$. ( $$E$$ - единичная матрица.)
Прежде чем переходить к формулировке алгоритма перестановки $$k$$ -го элемента базиса с $$(k-1)$$ -м, выведем соответствующие формулы. Пусть $$b_1,\dots, b_n$$ - текущий базис, ему соответствует ортогональный базис $$b^*$$ и нижняя треугольная матрица $$\mu$$. Элементы нового базиса обозначим буквой $$c$$ с соответствующим индексом, соответствующий ортогональный базис - $$c^*$$, нижнюю треугольную матрицу - $$\nu$$. Вычислить элементы базиса $$c$$ не представляет труда:$$\begin{equation*} c_{k-1 } = b_k,\quad c_k = b_{k-1 },\quad c_i = b_i\quad\text{для}\quad i \neq k,k-1. \end{equation*}$$
Переходим к вычислению ортогонального базиса. Как отмечалось выше, левая часть равенства (19.5) представляет собой квадрат длины ортогонального дополнения $$i$$ -го вектора к подпространству, порожденному векторами с 1-го по $$(i-2)$$ -ой.
Таким образом,$$\begin{equation} c_{k-1 }^* = b_k^* + \mu _{k,k-1 } b^*_{k-1 }. \end{equation}$$
Для вычисления $$c_k^*$$ спроектируем $$b_{k-1 }^*$$ на ортогональное дополнение к $$\mathbb R c_{k-1 }^*$$. Получим$$\nu_{k,k-1} = \frac{(b_{k-1}^*, c_{k-1}^* )}{(c_{k-1}^*,c_{k-1}^*)}\notag \\ = \mu_{k,k-1} | b_{k-1}^* |^2/| c_{k-1}^* |^2$$ $$c_k^* = b_{k-1}^* - \nu_{k,k-1} c_{k-1}^*.$$ $$c_i^* = b_i^*\quad\text{для}\quad i \neq k-1,k.$$
Для вычисления коэффициентов $$\nu$$ нам понадобится выразить старый ортогональный базис через новый. Из соотношений (20.2), (20.3) и (20.4) получаем$$b_{k-1}^*= \nu_{k,k-1 } c_{k-1 }^* + c_k^*$$ $$b_k^* = (1 - \mu_{k,k-1 }\nu_{k,k-1})c_{k-1}^*- \mu_{k,k-1}c_k^*\notag\\ =(| b_k^*| ^2/| c_{k-1 }^* | ^2)\cdot c_{k-1}^* - \mu_{k,k-1} c_k^*.$$
Подставив соотношения (20.1)-(20.7)в формулу (19.1) и приведя подобные члены, получим для $$i > k$$$$\nu_{i,k-1}= \mu _{i,k-1 }\nu_{k,k-1 }+ \mu _{i,k } | b_k^*| ^2/| c_{k-1 }^* | ^2,$$ $$\nu_{i,k} = \mu _{i,k-1}- \mu_{i,k }\mu_{k,k-1 }.$$
Наконец,$$\nu_{k-1,j}=\mu_{k,j},\qquad \nu_{k,j} = \mu _{k-1,j }\quad\text{для}\quad 1\leq j<k-1 ;$$ $$\nu_{i,j} =\mu_{i,j}\quad\text{для}\quad 1\leq j<i\leq n,\quad \{i,j\} \cap \{k-1,k\} = \emptyset.$$
Реализация полученных формул описывается следующим алгоритмом:
А36. АЛГОРИТМ (переставить- $$k$$ -ый-элемент-базиса- $$b$$ - $$с$$ - $$(k - 1)$$ -м).
$$\begin{equation*} \text{Дано:\quad $k\in\mathbb Z $, } \\ \text{\qquad $L$ - решетка, } \\ \text{\qquad $\mu$ - нижняя треугольная матрица коэффициентов, вычисляемых по формулам (19.1) и (19.2),} } \\ \text{\qquad $B$ - вектор элементов типа вещественное число с индексом $1..n$. }\\ \text{Элементы вектора $B$ - это квадраты длин соответствующих векторов из} \\ \text{ортогонального базиса $b1$, вычисляемого по формулам (19.1) и (19.2).} \\ \text{Надо:\qquad $L, \mu , B$ } \\ \text{\qquad В векторе $L$.базис поменялись местами два элемента. } \\ \text{ \qquad Соответствующие изменения произошли с элементами матрицы $\mu$ и вектора $B$.} } \\ \text{Обозначения:\quad $n == L$.ранг } \\ \text{\qquad $b == L$.базис }\\ \text{Переменные:\quad \qquad $BB, \mu\mu$ - вещественные числа } \\ \text{Начало} \\ \text{$\mu \mu := \mu [k,k-1]$ } \\ \text{$BB := B[k] + \mu\mu^2 \cdot B[k-1]$} \\ \text{$\mu [k,k-1] :=\dfrac{\mu\mu \cdot B[k-1]}{BB}$} \\ \text{$B[k] :=\dfrac{B[k-1]\cdot B[k]}{BB}$ } \\ \text{$B[k-1] := BB$ } \\ \text{$\begin{pmatrix} b[k-1] \\ b[k]\end{pmatrix} := \begin{pmatrix} b[k] \\ b[k-1]\end{pmatrix}$ } \\ \text{цикл для $i$ от $1$ до $k-2$ } \\ \text{\qquad $\begin{pmatrix} \mu [k-1,i] \\ \mu [k,i] \end{pmatrix} := \begin{pmatrix} \mu [k,i] \\ \mu [k-1,i] \end{pmatrix}$ } \\ \text{конец цикла } \\ \text{цикл для $i$ от $k+1$ до $n$ } \\ \text{\qquad $\begin{pmatrix} \mu [i,k-1] \\ \mu [i,k] \end{pmatrix} := \begin{pmatrix} 1 \mu [k,k-1] \\ 0 1 \end{pmatrix} \begin{pmatrix} 0 1 \\ 1 -\mu\mu \end{pmatrix} $ } \text{$\begin{pmatrix} \mu [i,k-1] \\ \mu [i,k] \end{pmatrix}$ } \\ \text{конец цикла} \\ \text{Конец} \end{equation*}$$Переходим к обоснованию алгоритма A33 построения редуцированного базиса решетки. Оно состоит из доказательства двух утверждений. Во-первых, докажем, что если алгоритм завершит свою работу, то в результате получим редуцированный базис данной решетки. Во-вторых, докажем, что для любого исходного базиса решетки алгоритм после конечного числа шагов закончит работу.
Для доказательства первого утверждения заметим, что мы выполняем над элементами базиса только элементарные преобразования, которые переводят базис $$\mathbb Z $$ -модуля в другой базис того же самого $$\mathbb Z $$ -модуля, т. к. и перестановка элементов базиса и прибавление к одному из элементов целого кратного другого - обратимые операции. Таким образом, в любой момент времени $$b$$ представляет собой базис исходной решетки. Элементы этого базиса с 1-го по $$(k-1)$$ -ый представляют собой редуцированный базис подрешетки, порожденной этими элементами, т. к. для них выполнены условия (19.4) и (19.5). Когда мы производим преобразования вектора $$b[k]$$, направленные на то, чтобы для него выполнялись условия (19.4), эти преобразования никак не отражаются на векторах с 1-го по $$(k-1)$$ -ый, а если мы производим перестановку $$k$$ -го элемента базиса с $$(k-1)$$ -ым, то уменьшаем длину редуцированной части базиса на 1 (если она больше 1; меньше 1 длина редуцированной части базиса быть не может) и одновременно уменьшаем значение $$k$$. Для векторов с 1-го по $$(k-1)$$ -ый снова выполнены условия (19.4) и (19.5). Таким образом, если алгоритм завершил свою работу, то получившийся базис - редуцированный базис исходной решетки $$L$$.
Прежде чем перейти к доказательству второго утверждения, приведем несколько определений и задач различной степени сложности.
20.1. УПРАЖНЕНИЕ. Пусть $$m(L) =\min \{ | x| ^2: x \in L, x\neq 0\}$$. Показать, что для любой решетки $$L$$ выполняется неравенство $$m(L) > 0$$.
Введем обозначение$$\begin{equation} d_i =\det ((b_j , b_l ))_{1\leq j,l\leq i }\text { для } 0 \leq i \leq n. \end{equation}$$
20.2. УПРАЖНЕНИЕ. Показать, что для всех $$i$$ от 1 до $$n$$ выполняется равенство $$d_i =\prod\limits_{j=1 }^i| b_j^*| ^2$$.
Для всех $$i > 0$$ числа $$d_i$$ могут быть
интерпретированы как квадраты
20.3. УПРАЖНЕНИЕ. Показать, что каждая такая решетка содержит ненулевой вектор $$x$$, удовлетворяющий неравенству$$\begin{equation*} | x| ^2 \leq (4/3)^{(i-1)/2}\cdot d_i^{1/i}. \end{equation*}$$
Переходим теперь к доказательству второй части утверждения о корректности алгоритма построения редуцированного базиса. Пусть$$\begin{equation*} D=\prod\limits_{j=1}^{n-1}d_i. \end{equation*}$$
Из упражнения 20.2 следует, что значение $$D$$ меняется только тогда, когда изменяется хотя бы один из векторов $$b_i^*$$. Это может произойти только при перестановке двух векторов базиса. При этом новое значение $$| b_{i-1 }^* |$$ равно $$| b_i^* + \mu _{i\,i-1 }b_{i-1 }^* |$$, что по условию меньше, чем 3/4 от прежнего значения этой величины. Таким образом, при каждой выполняемой перестановке элементов базиса значение величины $$D$$ умножается на положительное число, меньшее 3/4. Из упражнений 20.1-20.3 следует, что $$D$$ ограничено снизу некоторой положительной величиной, следовательно, перестановка элементов выполняется в алгоритме только конечное число раз, обозначим его $$m$$. При каждом выполнении перестановки значение $$i$$ уменьшается на 1, при выполнении команд, следующих за ключевым словом "иначе" в алгоритме, значение $$i$$ увеличивается на 1. Начальное значение $$i$$ равно 2, алгоритм продолжает работу до тех пор, пока $$i \leq n$$, следовательно, ситуация "иначе" встречается $$m+n-1$$ раз, т.е. тело цикла "пока" выполняется конечное число раз. Таким образом, алгоритм завершает работу после выполнения конечного числа шагов. Ниже мы оценим это число для случая, когда все координаты исходного базиса решетки - целые числа.
Итак, переходим к оценке сложности алгоритма построения редуцированного базиса решетки в предположении, что все координаты исходного базиса являются целыми числами. Именно такой случай нам понадобится для получения алгоритма факторизации полиномиальной сложности. Наша цель сейчас - доказательство следующего предложения.
20.4. ПРЕДЛОЖЕНИЕ. Пусть $$L \subset \mathbb Z ^n$$ - решетка с базисом $$b_1,\dots, b_n$$ и предположим, что задано положительное число $$B\ge2$$ , такое, что для любого вектора $$b_i$$ из исходного базиса решетки выполняется неравенство $$|b_i|^2 \leq B$$. Тогда алгоритм построения редуцированного базиса, описанный выше, требует для своего выполнения $$O(n^4\log B)$$ арифметических операций над целыми числами, двоичная длина которых представляет $$O(n\log B)$$. Таким образом, для построения редуцированного базиса достаточно $$O(n^6\log^3B)$$ бинарных операций.
ДОКАЗАТЕЛЬСТВО. Перед началом работы алгоритма величины $$d_i$$, определенные формулами (20.12) удовлетворяют неравенству $$d_i\leq B^i$$, что легко следует из упражнения 20.2. Таким образом, перед началом работы алгоритма $$D \leq B^{n(n-1)/2}$$. Из определения $$D$$ легко следует, что в случае, когда $$L \subset \mathbb Z ^n$$, $$D$$ - неотрицательное целое число, которое не может обратиться в нуль, в силу линейной независимости векторов, составляющих базис решетки. Таким образом, $$D\ge1$$ во все время работы алгоритма. Выше отмечалось, что при перестановках элементов базиса, выполняемых алгоритмом построения редуцированного базиса, величина $$D$$ убывает не медленнее геометрической прогрессии со знаменателем 3/4, следовательно, таких перестановок выполняется $$O(\log B^{n(n-1)/2}) = O(n^2\log B)$$. Мы оценили, таким образом, сколько раз в головной программе, в цикле "пока" встречается ситуация "то" в условии "если". Из доказательства конечности времени работы алгоритма следует, что ситуация "иначе" встречается также $$O(n^2 \log B)$$ раз. Итак, тело цикла в основном алгоритме выполняется $$O(n^2 \log B)$$ раз. Внутренний цикл в ситуации "иначе" дает еще один множитель $$n$$ для алгоритма A35, который выполняется таким образом $$O(n^3\log B)$$ раз. Переходим теперь к оценке сложности отдельных предписаний алгоритма A33.
В предписании "начальная-установка" два вложенных цикла дают $$O(n^2)$$ повторений тела цикла, в котором встречаются векторные операции: скалярное произведение векторов, умножение вектора на число, вычитание векторов, что дает еще один множитель $$n$$. При этом арифметические операции выполняются над рациональными числами. Сложность выполнения операций над этими числами оценим несколько позже.
Количество арифметических операций в алгоритме A35, как легко видеть, равно $$O(n)$$, такое же количество операций в алгоритме A36. Сравнивая количество проходов через отдельные ветви алгоритма, получаем, что количество арифметических операций в алгоритме представляется величиной $$O(n^4\log B)$$, что и утверждалось в первой части предложения.
Оценим теперь сложность выполнения арифметических операций, выполняемых над рациональными числами в процессе работы алгоритма A33. Прежде всего, опишем множество значений, которые могут принимать знаменатели всех встречающихся во время вычислений рациональных чисел. Покажем, что в качестве знаменателей всех встречающихся чисел могут быть использованы только числа $$d_i$$, вычисляемые по формулам (20.12), а именно:$$| b_i^*| ^2= \frac{d_i}{d_{i-1 }}, (1 \leq i \leq n),$$ $$d_{i-1 }b_i^* \in L \subset \mathbb Z ^n, (1 \leq i \leq n),$$ $$d_j\mu _{ij }\in \mathbb Z , (1 \leq j < i \leq n).$$
Первое из этих соотношений следует из упражнения 20.2.
Для доказательства второго соотношения выразим векторы $$b_i^*$$ с неопределенными коэффициентами $$y_{ij }$$ через исходный базис:$$\begin{equation*} b_i^* = b_i - \sum\limits _{j=1 }^{i-1}y_{ij } b_j . \end{equation*}$$
Неизвестные коэффициенты с фиксированным первым индексом $$i$$ определяются из системы линейных уравнений$$\begin{equation*}\label{20.16} (b_i ,b_l ) = \sum\limits _{j=1 }^{i-1}y_{ij }(b_j ,b_l ) \end{equation*}$$
Решая систему (20.16) методом Крамера, воспользовавшись формулой (20.12) получаем, что $$d_{i-1 }y_{ij }\in \mathbb Z $$ для всех допустимых значений индексов. Отсюда уже вытекает соотношение (20.14).
Воспользовавшись соотношениями (19.2), (20.13) и (20.14), получаем цепочку равенств$$\begin{align*} d_j \mu _{ij }= d_j \frac{(b_i ,b_j^*)}{(b_j^*,b_j^*)}= d_{j-1 }(b_i ,b_j^*) =(b_i ,d_{j-1 }b_j^*) \in Z, \end{align*}$$ чем заканчивается доказательство соотношения (20.15).
Посмотрим теперь, как меняются величины $$d_i$$ в процессе работы алгоритма. В начале работы алгоритма они вычисляются по формулам (20.12). В процессе работы эти величины меняются только при перестановке элементов базиса (в алгоритме A36 ). В этом случае $$d_{k-1 }$$ заменяется (в обозначениях (20.1)-(20.5)) на$$d_{k-1 } \cdot\frac{| c_{k-1 }^* | ^2}{| b_{k-1 }^* | ^2} = d_{k-2 } \cdot | c_{k-1}^* | ^2,$$ значения $$d_i$$ при $$i\neq k-1$$ не меняются. При этом все значения $$d_i$$ остаются целыми и во все время работы алгоритма удовлетворяют неравенствам $$d_i^i \leq B$$. Таким образом, мы оценили множество чисел, которые могут появляться в вычислениях в качестве знаменателей.
Для оценки числителей достаточно найти верхнюю грань для величин $$|b_i^*|^2$$, $$|b_i|^2$$ и $$|\mu_{ij}|$$. Первая из этих величин оценивается просто: в начале работы алгоритма выполняются неравенства $$| b_i^*| ^2 \leq | b_i | ^2 \leq B$$. В процессе работы величина $$\max\{ | b_i^*|^2: 1 \leq i \leq n\}$$ не возрастает, для доказательства чего достаточно заметить, что изменение векторов $$b_i^*$$ происходит только при перестановке элементов базиса, при этом выполняются неравенства $$| c_{k-1 }^*|^2<\frac34 | b_{k-1 }^* | ^2$$ и $$| c_k^*| ^2 \leq | b_{k-1 }^*| ^2$$, поскольку $$c_k^*$$ - проекция вектора $$b_{k-1 }^*$$. Таким образом, во все время работы алгоритма $$| b_k^*| ^2 \leq B$$. Оценка величин $$| b_i | ^2$$ и $$\mu _{ij}$$ существенно сложнее. Чтобы получить ее, докажем, что всякий раз в точке проверки условия окончания цикла "пока" выполняются следующие неравенства:
$$|b_i|^2 \leq nB \text{ для } i \neq k;$$ $$|b_k|^2 \leq n^2(4B)^n, \text{ если }k \neq n+1;$$ $$|\mu_{ij}|\leq 1/2 \text{ для } 1 \leq j < i < k;\\$$ $$|\mu_{ij}|\leq(nB^j)^{1/2} \text{ для } 1\leq j<i,\ i > k;$$ $$|\mu_{kj}|\leq2^{n-k}(nB^{n-1})^{1/2} \text{ для } 1\leq j<k, \text{ если } k \neq n+1.$$При доказательстве этих неравенств пользуемся следующим соотношением:$$\begin{equation} \mu _{ij }^2 \leq \frac{|b_i|^2}{|b_j^*|^2} =\frac{d_{j-1 }| b_i |^2}{d_j} \leq B^{j-1}| b_i | ^2. \end{equation}$$
Перед первым выполнением тела цикла неравенства (20.17) и (20.18) следуют из неравенства $$|b_i|^2\leq B$$, которое выполняется по определению $$B$$. Вместе с (20.22) это неравенство дает соотношение $$| \mu _{ij } | \leq B^{j/2}$$, откуда следует (20.19) и (20.20), а учитывая, что $$B 2$$, и (20.21). Таким образом, перед первым выполнением тела цикла неравенства (20.17)-(20.21) справедливы.
Предположим теперь, что неравенства (20.17)-(20.21) выполнены перед началом выполнения тела цикла, и покажем, что эти неравенства будут выполнены и в конце тела цикла, т.е. перед выполнением следующего цикла. Неравенство (20.19) совпадает с (19.4), которое выполняется для текущего $$k$$ все время работы алгоритма A33, в том числе и в начале цикла. Выполнение неравенства (20.17) для $$i < k$$ следует из соотношений (19.1), (20.19) и неравенства $$| b_i^*| ^2 < B$$. Покажем, что из (20.17) для $$i>k$$ и из неравенства (20.21) следуют неравенства (20.18) и (20.20). Доказательство (20.18) сводится к разложению $$b_k$$ в сумму по формуле (19.1), применению неравенства (20.21) и вычислению суммы геометрической прогрессии. Неравенство (20.20) непосредственно вытекает из (20.22) и (20.17).
Итак, покажем, что если перед началом выполнения тела цикла справедливы неравенства (20.17)-(20.21), то и после его выполнения неравенства (20.17) и (20.21) также имеют место. Отдельно рассмотрим два случая: работа алгоритма осуществляется по ветви "то", т.е. два вектора меняются местами; второй случай - алгоритм идет на ветвь "иначе", т.е. осуществляется выполнение условия (19.4) для всех $$j < k$$.
В первом случае множество векторов $$\{ b_i :i< k\}$$ не изменилось (мы поменяли местами $$k$$ -ый вектор с $$(k-1)$$ -ым и уменьшили после этого $$k$$ на 1). Во втором случае множество $$\{ b_i: i>k\}$$ векторов, для которых нам нужно доказать неравенство (20.17), заменилось на собственное его подмножество. Этим заканчивается индуктивный шаг для неравенства (20.17).
Переходим к оценке $$\mu _{kj }$$ (если $$k \neq n+1$$ ). Снова в теле цикла может выполняться одна из двух серий команд, причем в конце каждой серии значение переменной $$k$$ меняется, либо увеличиваясь, либо уменьшаясь на 1. Значение $$k$$ увеличивается, когда алгоритм идет по второй ветви, т.е. достигается выполнение условия (19.4) для всех $$j < k$$ (отдельно, до цикла достигается это условие для $$j=k-1$$, в цикле - для $$j < k-1$$ ). Эти операции никак не влияют на $$\mu _{ij}$$, если $$i > k$$, в частности, при $$i=k+1$$. На следующем шаге значение $$k$$ увеличивается на 1, и неравенства (20.21) следуют из (20.20), которые выполняются на предыдущем этапе.
Значение $$k$$ уменьшается на 1, если в теле цикла выполняется перестановка векторов, при этом после ее выполнения новые значения коэффициентов $$\mu _{kj}$$ совпадают со старыми значениями (с учетом замены $$k$$ на $$k-1$$ ). Остается только проследить, как изменилось значение коэффициентов $$\mu _{kj }$$, когда до перестановки векторов мы добивались выполнения условия (19.4) для $$\mu _{k\,k-1 }$$. При этом к $$k$$ -ой строке матрицы $$\mu$$ прибавлялась ( $$k-1$$ )-я строка, умноженная на $$r$$, где $$| r| < 2| \mu _{k\,k-1 }|$$. Учитывая, что $$| \mu _{k-1\,j }| < 1/2$$, получаем$$ | \mu _{kj }- r \mu _{k-1\,j }| \leq | \mu_{kj }| + | \mu _{k\,k-1 }| \leq \\ \text{(по индуктивному предположению)} \\ \leq 2^{n-k+1}(nB^{n-1})^{1/2}. $$
Поскольку новое значение $$k$$ на 1 меньше старого, получаем требуемую формулу, доказательство неравенств (20.17)-(20.21) закончено.
Для завершения доказательства предложения 20.4 нам осталось только оценить значения, получающиеся на промежуточных этапах алгоритма. Заметим, что при выполнении алгоритма A35 значения коэффициентов $$\mu$$ не более, чем удваиваются. Поскольку в одном теле основного цикла алгоритм A35 выполняется не более, чем $$k-1$$ раз, то
$$| \mu _{ij }| \leq 2^{n-1}(nB^{n-1})^{1/2}\text{ для } j < k-1,$$откуда, воспользовавшись формулами (19.1), ортогональностью векторов $$b_i^*$$, неравенствами $$| b_i^*| < B$$ получаем неравенства $$| b_i | ^2 \leq n^2(4B)^n$$ для $$1\leq i\leq n$$. Остается перемножить границы для знаменателей и для абсолютных величин, прологарифмировать и выделить главную часть, чтобы получить оценки, фигурирующие в предложении 20.4.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.