Вычислительные алгоритмы в геометрии чисел

Напомним, что, а = [Ь о- ?1,^2, •] (1) есть формальная запись канонического разложения вещественного числа, а в непрерывную дробь 1 а = ¿-о Н-1.

1 +.

2+ 1 с целым ¿-о = [а] (целая часть а) и натуральными? i, ?2, • • •, U, • • • (неполные частные). Оборвав непрерывную дробь (1) наг—ом шаге, получим подходящую дробь с взаимно простыми целым Р и натуральным Q{. Удобно положить Р- = 1 и Q-i = 0.

Обозначим через ||cu|| расстояние от числа, а до ближайшего целого:

Ы| = minа — п = minila:}, 1 — {а}), пеz 1 1 4 L J/ где {а} — дробная часть числа а. Имеем 0 ^ ||a|| ^ ½. Для подходящих дробей Pi/Qi хорошо известна оценка которую можно представить в виде.

ФМИ < 1.

3).

Вален [28] усилил ее, доказав неравенство.

4).

В обоих случаях константы 1 и ½ нельзя заменить меньшими. Последнее неравенство обычно называют теоремой Валена для подходящих дробей.

Определение 1. Дробь р/д (р € Ъ, д € М) назовем наилучшим приближением числа а, если.

Классическая теорема Лагранжа (см. [17]) утверждает, что последовательность подходящих дробей Д/ф* (г ^ 0 при {а} ^ ½ и г ^ 1 при {а} > ½) состоит из всех наилучших приближений числа а.

В конце XIX века, независимо друг от друга, Г. Ф. Вороной [12] и Г. Мин-ковский [27] положили это наблюдение в основу концепции локальных минимумов решеток с целью обобщения классического алгоритма непрерывных дробей на многомерный случай.

Определение 2. Пусть {7^,., 7^} ~~ 5 линейно независимых точек вещественного евклидова пространства рассматриваемые как столбцы невырожденной матрицы (7 = (7^. 7^) = {1^) с? К.

Множество всех точек ад\ = ад-р и если щ\ < \щ'\ для всех натуральных с{ < д.

Г = Г (£) = {7 = (71, • • •, 7-) = ^17(1) + • • ¦ + I шь ., т, € г}.

•, т3 назовем полной s-мерной решеткой в Rs (для краткости, в дальнейшем слово «полная» будем опускать) с базисом (7^,., 7^).

В случае если все числа 7^ являются целыми, то решетка называется целочисленной.

Положительную величину D — D (Г) = |det (C?)| назовем определителем решетки Г.

Равенство T (G) = Г (G') имеет место (см. [18]) тогда и только тогда, когда G' = G-S для некоторой унимодулярной матрицы S (целочисленной с det (S) — ±1).

Обозначим через ?(RS) множество всех решеток в Ks, а через ?*(RS) его подмножество, состоящее из всех решеток «общего положения», у которых для любого ненулевого узла 7 = (71,., 7S) все координаты 7i отличны от нуля. Другими словами, на координатных гиперплоскостях нет ненулевых узлов Г.

Назовем две матрицы G и G' эквивалентными, если одна получается из другой путем композиции некоторых преобразований вида:

1) изменение знака у столбца или строки;

2) перестановка двух столбцов или строк.

Определение 3. Ненулевой узел 7 = (71,., 7S) назовем локальным минимумом решетки Г, если не существует ненулевого узла rj = (771,., rjs) из Г, для которого.

Ы ^ li для всех г = 1,., 5, и при этом хотя бы одно из этих s неравенств строгое.

Замечание 1. Узлы 7 и —7 только одновременно могут являться локальными минимумами решетки.

Замечание 2. Для любого ненулевого узла г] решетки Г найдется локальный минимум 7, для которого ^ |туг| для всех г = 1,., в.

Замечание 3. Любой локальный минимуму 6 Г примитивен в том смысле, что вектор’у/д не есть узел решетки Г для любого натурального q>l.

Эти свойства непосредственно следуют из определения локального минимума. Из теоремы Минковского о выпуклом теле (см. [18]) следует.

Замечание 4. Для любого локального минимума ¦у = (71,., 75) решетки Г выполняется неравенство.

Ъ.Ъ<�П (Т). (5).

Составим из всех локальных минимумов решетки Г множество Ш?(Г). В двумерном случае рассмотрим решетку.

Га = {7 = (ат! — га2, ТП) = тп^а, 1) + т2(-1,0) | т, т2 € Z} с Р (Га) = 1. Из уже упоминавшейся теоремы Лагранжа о наилучших приближениях следует, что для 0 < а < ½ множество локальных минимумов.

ЯЯ (Га) = {±-{аЯг — Рг, Яг) г = о, 1,2,.}.

Таким образом, в рассматриваемом случае локальные минимумы взаимно однозначно соответствуют подходящим дробям разложения, а в непрерывную дробь и неравенство (5) можно рассматривать как обобщение упомянутого ранее неравенства.

Э"Н < 1- (з).

Определение 4. Назовем матрицу О = (7^. 7^) и определяемый ею базис (7^,., 7^) минимальными, если не существует ненулевого узла Г] из Г, для которого.

Ы<�тах{|711)|>.,|7<(0|} (* = !,.,*).

Понятно, что для решеток «общего положения» Г 6 каждый узел минимального базиса для Г является локальным минимумом решетки. Из определения непосредственно следует.

Замечание 5. Эквивалентные матрицы (и соответствующие им базисы) минимальны только одновременно.

В двумерном случае Г. Ф. Вороной [12] доказал, что невырожденная матрица С, определяющая решетку Г = Г (С?) «общего положения» из £*(К2), минимальна тогда и только тогда, когда она эквивалентна некоторой матрице М вида м = (Х1.

У2) с 0 ^ у ^ х, 0 ^ Х2 ^ У2• Так как ёе^С) ^ 0, то всегда х > 0 и у2 > 0. В связи с этим введем следующие.

Определение 5. Матрицы вида (без требования принадлежности определяемых ими решеток множеству £*(К2)) с 0 ^ у ^ х, 0 ^ Х2 ^ У2, Х1У2 у^ 0, назовем матрицами Вороного. зисом Вороного, если соответствующая ему матрица эквивалентна матрице Вороного.

Построим отображение Ф2, сопоставляющее каждой матрице Вороного вектор в К2 по правилу.

Определение 6. Базис (7^, 7^) двумерной решетки Г назовем багде Б = ХУ2 + Х2У1 — определитель М. Назовем его образ У (Е2) двумерной областью Валена.

По причине однородности достаточно найти образ матриц Вороного с х = у2 = 1- То есть, образ квадрата [О, I]2 при отображении.

Я2,У1) -> (~~—, т-^-) •.

1 + х2У1 1 ~Ь Х2У).

Якобиан этого отображения равен.

— <0, (1 + У1Х2У.

Легко проверить, что образ границы [0,1]2 совпадает с границей области.

ИЪ = {{х, у) еШ2 | 0 х + у ^ 1}.

Из простейших геометрических соображений отсюда следует, что У (М2) = У2. Таким образом, мы вычислили двумерную область Валена, совпадающую с И^.

Из вышесказанного следует, что для любого базиса Вороного (7^, 7^) решетки Г выполняется неулучшаемое неравенство.

ЧЧ + Ы^'К^г), (6) которое уточняет оценку п{ Ы’Чг1'!. |712)722)| } < (7) непосредственно вытекающую из результатов работы Вороного [12]. По аналогии со своим частным случаем для подходящих дробей (см. оценку (4)), последнее неравенство называют теоремой Валена для двумерных решеток.

Вернемся теперь к решеткеГа (0 < а < ½). Хорошо известно (см. [17]), что с точностью до знака первой строки л г / ч I ~ Ъ 1 ~.

М{(а) = (.

Qi ^?+1 матрица Вороного. Поэтому, в соответствии с (6), выполняется неравенство ЯшМ<+1 II ^ D (гa) = 1, уточняющее упомянутую выше классическую теорему Валена о том, что тт{д*||а<2*||, ЗшМшН } < ^ (4).

Это наблюдение, впервые отмеченное в [2], служит мотивировкой введенного нами понятия «область Валена» для двумерных решеток. В первой главе мы распространяем этот результат на трехмерный случай: мы вычисляем явный вид трехмерных областей Валена первого и второго типов. Обозначим через 03 С Мв единичный ¿—мерный куб: дз = {(хь., Ое1Г| Кг^}.

Для приближенного вычисления кратных интегралов функций на кубе Я3 используются квадратурные формулы /(*<*>)-Я"(Л (8) в. к=1 где N — натуральное число. Точки. в которых вычисляются значения подынтегральной функции, называются узлами, их совокупность — сеткой, а величина Длг (/) — погрешностью квадратурной формулы.

Пусть а,., а3 — целые числа, для которых НОД (аь ., а3, Щ = 1. В конце 60-х годов двадцатого века Н. М. Коробов [19] (см. также [20] и [21]) предложил использовать параллелепипедальные сетки для подынтегральных функций, непрерывных в единичном 5-мерном кубе и имеющих период 1 по каждой из переменных х,., х3.

Пусть функция f (x) разлагается в ряд Фурье.

2ni (V'X) (9) vi,., vs=-oo с коэффициентами с (у) = J f (x) e~27Ti^x) dx.

Gs.

Введем обозначения щ = max{l, v||| = v •. -vs.

Будем говорить, что функция f (x) принадлежит классу Е£, если для ее коэффициентов Фурье выполняется оценка ф,)| * IMP где, а > 1 — действительное число. В работе [21] показано, что если функция f (x) G Eg, то ее ряд Фурье (9) сходится абсолютно.

Для погрешности квадратурной формулы (8) на классе Е£ справедлива оценка.

ЫЛ" с (Ю).

Na-v.

Суммирование здесь ведется по всем ненулевым целочисленным решениям v — (vi,., vs) сравнения aV +. + asvs = О (mod А7″). (11).

Задача состоит в том чтобы найти вектор, а = (ai,., as), минимизирующий сумму в правой части оценки (10) для |Длг (/)|. Наибольшие слагаемые в этой сумме соответствуют решениям v сравнения (11) с наименьшими значениями |||и|||. Так возникает идея о нахождении вектора а, который делает величину д (а) =.

Ш1П vezn{o} а-ь=0 (тос! ЛГ).

III У.

III.

12) как можно больше. Соответствующие значения., а3 называются оптимальными коэффициентами.

Параметр д, определяемый равенством (12), был предложен Н.С. Ба-хваловым в работе [3] (мы будем называть его параметром Бахвалова) и характеризует равномерную распределенность узлов параллелепипедаль-ной сетки.

Первостепенное значение приобретает задача построения эффективных алгоритмов для вычисления параметра д и нахождения оптимальных коэффициентов а,., а3 в том смысле, что величина д не меньше заданной границы.

Назовем ненулевое целочисленное решение у =., у3) сравнения локально минимальным, если не существует другого ненулевого решения у' = (у[,., у'3), такого что у[ ^ |г/г| для всех г = 1,., б и при этом хотя бы одно из этих б неравенств строгое. Заметим, что при определении параметра Бахвалова д (а) можно учитывать только локально минимальдение, сделанное В. А. Быковским (см. работы [5] и [6]), позволяет свести задачу вычисления параметра Бахвалова к задаче нахождения множества всех локально минимальных решений сравнения (11).

Все целочисленные решения сравнения (11) составляют целочисленную решетку в определителя ДО. Локально минимальные решения соответаУ +. + а3у3 = 0 (тос! ДО) п) ные решения, количество которых не превосходит 0(к^ 1 ДО). Это наблюствуют локальными минимумами решетки. В связи с этим мы можем рассматривать несколько более общую задачу — о вычислении множества локальных минимумов решетки.

Во второй главе настоящей работы мы разрабатываем алгоритм вычисления множества локальных минимумов целочисленных решеток, основываясь на предложенной в работе В. А. Быковского [7] теоретической схеме. Мы рассматриваем основные составляющие части — алгоритм нахождения ЬЪЬ-приведенного базиса решетки и алгоритм Ртске-Ро]^ для вычисления кратчайшего вектора решетки.

В третьей главе мы рассматриваем применение алгоритма вычисления локальных минимумов к построению эффективного алгоритма нахождения параметра Бахвалова и оптимальных коэффициентов. Для оптимизации вычислений мы вводим понятие эллиптических минимумов решетки и предлагаем алгоритм для их вычисления. Этот алгоритм позволяет находить параметр Бахвалова приближенно и значительно сократить время вычисления оптимальных коэффициентов. В конце главы мы приводим результаты вычислений оптимальных коэффициентов для размерностей 5 = 2,3.

1. Авдеева М. О. Аналог теоремы Валена для совместных приближений пары чисел / М. О. Авдеева, В. А. Быковский // Математический сборник. — 2003. — Т. 194, № 7. — С. 4−14.

2. Авдеева М. О. Уточнение теоремы Валена для базисов Минковского трехмерных решеток / М. О. Авдеева, В. А. Быковский // Математические заметки. 2006. — Т. 79, № 2. — С. 163−168.

3. Бахвалов Н. С. О приближенном вычислении кратных интегралов / Н. С. Бахвалов // Вестн. Моск. ун-та. Сер. Матем., мех., астрон., физ., хим. 1959. — т. — С. 3−18.

4. Быковский В. А. Теорема Валена для двумерных подходящих дробей / В. А. Быковский // Математические заметки. — 1999. — Т. 66, № 1. — С. 30−37.

5. Быковский В. А. О погрешности теоретико-числовых квадратурных формул / В. А. Быковский // Чебышевский сборник. — 2002. — Т. 3. — Вып. 2(4). — Тула: Изд-во Тул. гос. пед. ун-та им. Л. Н. Толстого, 2002. С. 27−33.

6. Быковский В. А. О погрешности теоретико-числовых квадратурных формул / В. А. Быковский // Доклады РАН. 2003. — Т. 389, № 2. — С. 154−155.

7. Быковский В. А. Алгоритм вычисления локальных минимумов решеток / В. А. Быковский // Доклады РАН. 2004. — Т. 399, № 5. — С. 587−589.

8. Быковский В. А. Алгоритм вычисления локальных минимумов целочисленных решеток и его приложения / В. А. Быковский, C.B. Гассан // Вестник Тихоокеанского государственного университета. — 2011. — № 1(20). С. 39−48.

9. Быковский В. А. О параметре оптимальности параллелепипедаль-ных сеток Коробова для кубатурных формул / В. А. Быковский, C.B. Гассан // Журнал вычислительной математики и математической физики. 2011. — Т. 51. — № 8. — С. 1363−1369.

10. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии / О. Н. Василенко. М.: МЦНМО, 2003. — 328 с.

11. Вороной Г. Ф. Собрание сочинений / Г. Ф. Вороной. — Т.1. — Киев: 1952.

12. Гассан C.B. Область Валена для трехмерных матриц Минковского второго типа / C.B. Гассан // Препринт № 06 / Хабаровское отделение института прикладной математики ДВО РАН. — Владивосток: Даль-наука, 2004. 13 с.

13. Гассан C.B. Структура областей Валена для трехмерных решеток / C.B. Гассан // Чебышевский сборник. — 2005. — Т. 6. — Вып. 3(15). — Тула: Изд-во Тул. гос. пед. ун-та им. JI.H. Толстого, 2005. — С. 51−84.

14. Касселс Дж.В.С.

Введение

в теорию диофантовых приближений / Дж.В. С. Касселс. М.: ИЛ., 1961. — 213 с.

15. Касселс Дж.В.С.

Введение

в геометрию чисел / Дж.В. С. Касселс. М.: Мир, 1965. — 421 с.

16. Коробов Н. М. Приближенное вычисление кратных интегралов с помощью методов теории чисел / Н. М. Коробов // Доклады Академии наук СССР. 1957. — Т. 115, № 6. — С. 1062−1065.

17. Коробов H.M. О приближенном вычислении кратных интегралов / Н. М. Коробов // Доклады Академии наук СССР. — 1959. — Т. 124, т. С. 1207−1210.

18. Коробов Н. М. Теоретико-числовые методы в приближённом анализе / Н. М. Коробов. М.: МЦНМО, 2004. — 288 с.

19. Рышков С. С. К теории приведения положительных квадратичных форм по Эрмиту-Минковскому / С. С. Рышков // Исследования по теории чисел. 2, Зап. научн. сем. ЛОМИ. — Л.: Наука, 1973. — Т. 33. С. 37−64.

20. Cohen H. A Course in Computational Algebraic Number Theory / H. Cohen // Graduate Texts in Math. — Vol. 138. — Springer-Verlag, Berlin Heidelberg, 1993. (Algorithm 1.3.14.).

21. Fincke U. Improved methods for calculating vectors of short length in a lattice, including a complexity analysis / U. Fincke, M. Pohst // Math. Сотр. Vol. 44. — 1985. — P. 463−471.

22. Lenstra A.K. Factoring Polynomials with rational coefficients / A.K. Lenstra, H.W. Lenstra, L. Lovasz // Math. Ann. Vol. 261. — 1982. P. 515−534.

23. Minkowski H. Generalization de la theorie des fraction continues / H. Minkowski // Ann. Sci. Ecole Norm. Sup. 1896. — Vol. 13, № 2. P. 41−60.

24. Vahlen K.Th. Uber Naherungswerte und Kettenbruche / K.Th. Vahlen // J. fur Math. Vol. 115. — 1895. — P. 221−233.

25. Vallee B. Une approche geometrique des algorithmes de reduction en petite dimension, Thesis / B. ValleeUniv. of Caen. — 1986.

26. NTL: A Library for doing Number Theory. URL: http://www.shoup.net/ntl/.

27. The GNU Multiple Precision Arithmetic Library. URL: http://gmplib.org/.

28. The Message Passing Interface (MPI) standard. URL: http://www.mcs.anl.gov/research/projects/mpi/.