скалярное произведение X U имеет данное значение q. В нашем случае все гиперплоскости разделяются фиксированными расстояниями и в одной из них содержится (О, О,..., 0). Следовательно, можно так установить значение U, что множество всех целых значений q даст все гиперплоскости в семействе. Тогда расстояние между соседними гиперплоскостями будет равно минимальному расстоянию от (О, О,..., 0) до гиперплоскости с q = 1, & именно:

действительные xi

iVxl + ---+xt xiui + ---+xtut = iy (12)

В соответствии с неравенством Коши (см. упр. 1.2.3-30) имеем

(xiui + • • + xtutf <{xl + ---+xt){ul + --- + ut), (13)

следовательно, минимум в (12) достигается, когда каждое Xj = Ujl{u\ -f- • • -t- м). Это означает, что расстояние между соседними гиперплоскостями равно

1/у/и\ + -.. + и] = 1/длина(г7). (14)

Другими словами, искомая величина vt точно равна длине кратчайшего вектора и, определяющего семейство гиперплоскостей {X-U = q \ целое q}, в которых содержатся все элементы Lo-

Такой вектор U = {ui,... ,щ) должен быть ненулевым и удовлетворять требованию V-U = целое для всех V в Lq. В частности, так как все точки (1,0,...,0), (0,1,..., 0), ..., (О, О,..., 1) принадлежат Lq, все Uj должны быть целыми. Кроме

того, так как Vi принадлежит Lq, получим, что (mi +au2 -\------a~ut) - целые,

т. е.

щ + au2 -t- • • • -t- а*~щ = О (по модулю т). (15)

И наоборот, любой ненулевой целый вектор U = {щ,...,щ), удрвлетворяющий (15), определяет семейство гиперплоскостей с необходимыми свойствами, так как будут покрыты все Lq. Скалярное произведение {y\V\ + ••• + у1\\)-и будет целым для всех целых j/i, ..., yt- Мы доказали, что

min {и\л-----\-и\ I ui+au2-\-----f-a = О (по модулю т)}

(ui,...,u,)/(0„..,O) g

= min ((тх1-ах2-ахз-----ахА+xl+xi-\-----hi?) •

C. Обоснование вычислительных методов. Сведем спектральный критерий к задаче нахождения минимального значения (16). Но как можно найти минимальное значение за разумный отрезок времени? Грубое силовое исследование не входит в наши планы, так как m - очень большое в случаях, представляющих практический интерес.

Будет интересно и, возможно, более полезно разработать вычислительные методы решений даже более общей проблемы: найти минимальное значение величины

f{Xi,...,Xt) = {UuXi +--- + UtlXtf + --- + {uuXi +---+UttXtf (17)

no всем ненулевым целым векторам {xi,... ,Xt) для любой невырожденной матрицы с коэффициентами U = (uij). Выражение (17) назовем положительно определенной квадратичной формой от t переменных. Так как U - невырожденная матрица, (17) не может быть нулем, если не все Xj равны нулю.

Запишем как Ui, ..., Ut все строки U. Тогда (17) можно записать как

/(1 ,...,xt) = {xiUi + ---+ XtUt) • (xiC/i + + xtUt), (18)

квадрат длины вектора л;it/iH-----\-XtUt. Невырожденная матрица U имеет обратную

матрицу, а это означает, что можно найти единственным образом определенные векторы Vi,...,Vt, такие, что

Ui-Vj=6ij, l<i,j<t. (19)

Например, в частном случае (16), возникающем в связи со спектральным критерием, получим

Ui = { m,0,0,...,0), Fi = i(l,a,a2,...,a-i),

U2 = { -a,l,0,...,0), 1/2= (0,1, 0,..., 0),

С/з = ( -a2,0,l,...,0), V3= (0,0, 1,..., 0), (20)

C/t = (-a-i,0,0,...,l), Vt= (0,0, 0,..., 1).

Эти Vj точно равны векторам (8) и (9), которые использовались для определения начальной решетки Lq- Как и подозревает читатель, здесь нет совпадения: действительно, мы начинали с произвольной решетки Lq, определенной любым множеством линейно независимых векторов Vi,... ,Vt. Доводы, используемые нами выше, могут быть обобщены, чтобы показать, что максимальное расстояние мeжд;J гиперплоскостями в покрывающем все точки семействе равно минимуму (17), где коэффициенты Uy- определены в (19) (см. упр. 2).

Первый шаг в минимизации (18) - ее сведение к конечной задаче: необходимо показать, что для нахождения минимума нет нeoбxoимocти в бесконечном множестве векторов {хх,...,Xt). Удобно выразить Хк через векторы Vi,...,Vt, а именно

Хк = {XiUi + --- + XtUt)-Vk, и из неравенства Коши получить неравенство

{{xiUi + + XtUt) П)" < f{xi,.. .,xt){Vk 14). Итак, получена удобная верхняя граница каждой координаты Хк-

Лемма А. Пусть {xi,...,xt) - ненулевой вектор, минимизирующий (18), и пусть (2/1) • ) 2/f) - любой ненулевой целочисленный вектор. Тогда,

xl<f{yu...,yt){Vk-Vk) ддя1<к<г. (21)

В частности, полатя у( = Sij для всех г, получим

4<iUj-Uj){Vk-Vk) ддя\<],к<1. I (22)

Лемма А сводит задачу к нахождению минимума по конечному множеству, но правая часть (21) обычно является слишком большой для того, чтобы можно было перебрать все значения (по крайней мере, нужна еще одна добавочная идея). В таком случае помогает старый афоризм: "Если вы не можете решить задачу в том виде, в каком она сформулирована, упростите ее, чтобы получить

такой же ответ". Например, алгоритм Евклида имеет такой вид, что если наибольший общий делитель чисел на входе неизвестен, придется выбирать его среди меньших чисел, имеющих тот же наибольший общий делитель. (На самом деле в основе открытия всех подобных алгоритмов, возможно, лежит несколько более общий подход: "Если вы не можете непосредственно решить задачу, сведите ее к одной из более простых задач, решив которые, вы сможете справиться с исходной задачей".)

В рассматриваемом здесь случае более простой проблемой является проблема, требующая меньшего количества проверок, потому что правая часть в (22) уменьшилась. Ключевой используемой идеей является возможность заменить одну квадратичную форму другой, которая представляет собой эквивалент для достижения всех практических целей. Пусть j - любой фиксированный индекс, I < j < t, и пусть (qi,... ,qji,qj+i,... ,qt) - любая последовательность t - I целых чисел. Рассмотрим следующее преобразование векторов:

V/ = Vi-qj, xl =x,-qiXj, U! = для г j;

VJ = Vj, xj =xj, Uj = Uj + EijqiUi.

Легко видеть, что новые векторы UI,..., UI определяют квадратичную форму /, для которой f{x[,. ..,х[) - f{xi,х). Кроме того, основное условие ортогональности (19) сохраняется, так как легко проверить, что U- VJ - dij. Когда {xi,...,xt) пробегает множество всех не равных нулю целочисленных векторов, то {х,... ,х[) пробегает это же множество; следовательно, новая форма / имеет тот же минимум, что и /.

Нашей целью является использование преобразования (23) и замена Ui на и[ и Vi на V/ для всех г, чтобы сделать правую часть (22) малой (правая часть (22) будет малой, когда Uj Uj и Т4 • Т4 будут малы). Следовательно, вполне естественно задать два следующих вопроса относительно преобразования (23).

a) Какие значения qi делают V/ • V/ настолько малыми, насколько это возможно?

b) Какие значения qi, qj-i, qj+i, qt делают UyUj настолько малыми, насколько это возможно?

Легче всего ответить на эти вопросы сначала для действительных значений qi. Вопрос (а) совершенно простой, так как

{Vi -qiVj) {Vi -qiVj) = Ц-Ц-2qi Vi Vj +q Vj Vj

= {Vj Vj) {qi - {Vi Vj/Vj .Vj))+Vi-Vi- {Vi Vj)/Vj • Vj и минимум достигается, когда

qi = Vi.Vj/Vj-Vj. (24)

С геометрической точки зрения мы спрашиваем, сколько раз можно вычесть Vj аз Vi, чтобы получить вектор минимальной длины V, и отвечаем: нужно выбрать такое qi, чтобы V/ было перпендикулярно Vj (т. е. сделать так, чтобы выполнялось