345-360; G. Marsaglia and W. A. Beyer, Applications of Number Tlieory to Numerical Analysis, edited by S. K. Zaremba (New York: Academic Press, 1972), 249-285, 361-370.] P. Дж. Стоунхам (R. G. Stoneham), используя оценки экспоненциальных сумм, показал, чтор/+еболее элементов последовательности аХо modp имеют асимптотически малый разброс, когда а - примитивный корень по модулю простого числа р [Acta Arithmetica 22 (1973), 371-389]. У Гаральда Нидеррейтера это объяснение растянулось на несколько статей (см. работы Harald Niederreiter, Math. Сотр. 28 (1974), 1117-1132; 30 (1976), 571-597; Advances in Math. 26 (1977), 99-181; Bull. Amer. Math. Soc. 84 (1978), 957-1041. См. также его книгу Н. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods (Philadelphia: SIAM, 1992)).

УПРАЖНЕНИЯ

1. [MIO] Что произойдет со спектральным критерием, если размерность уменьшить до единицы? (Другими словами, что произойдет при t = 1?)

2. [НМ20] Пусть Vi, ..., Vt - линейно независимые векторы в f-мерном пространстве, пусть Lo - решетка из точек, определенных в (10), и пусть Ui, ..., Ut определены в (19). Докажите, что максимальное расстояние между {t - 1)-мерными гиперплоскостями семейства параллельных гиперплоскостей, покрывающих Lo, равно l/mm{f{xi,... jXtY {xi,.., ,xt) ф (О,... ,0)}, где / определено в (17).

3. [м24] Определите из и щ для всех линейных конгруэнтных генераторов с потенциалом 2 и периодом длиной т.

> 4. [М23] Пусть ui 1, «12, «21, И22 - элементы матрицы размера 2x2, состоящей из целых чисел и такой, что иц + aun = «21 + au22 = О (по мод}лю тп) и U11U22 - и21и12 = тп.

a) Докажите, что все целые решения {у\, г/г) уравнения у\ +ау2 s О (по модулю тп) имеют

вид (г/1,2/2) = {XlUll+X2U21,XiUn+X2U22) для цеЛЫХ Xi, Х2.

b) Если вдобавок 2uiiU2i + И12И22 < «11 + «12 < «21 + «22, докажите, что (2/1,2/2) = (uii, U12) минимизирует yi + yl по всем соответствующим ненулевым решениям этого уравнения.

5. [МЗО] Докажите, что двумерный спектральный критерий на шагах S1-S3 алгоритма S выполняется правильно. [Указание. См. упр. 4; доказательство того, что (/г + Kf -Ь (р -rpf > -Ьр, начните с шага S2.]

То, что указанное неравенство, несомненно, впервые выполняется на шаге S2, является неожиданным. Целое числод, минимизирующее {h - qh) + {р- qр), согласно (24) равно q = округление((/1/1 +pp)/{h + Р))- Если {h - qhf -Ь {р - др) < + , получим q фО, q ф -1. Следовательно, {р - qp) > р; отсюда {h - qh) < /1, т. е. \h - qh\ < h либо q равно q или q+1. Получим hu+pv > h{h - qh) + p{p - qp) > -{h +P)- Если + < s, TO на следующей итерации шага S2 будет сохранено предположение указания. Если u + v >s> {u-h) + {v-p), получим 2/i(w-/i)-bp(i)-p) = 2{h{h--u)+p{p-v)) = {и - hf + {v - pf + +p - (u + v) < (и - h) + {v - p) < + p. Следовательно, согласно упр. 4 (u - h) + {v - p) является минимальным. Наконец, если и + , и (и - h) -\- {v - р) будут > S, положим и = h - qh, v = р - qp; тогда согласно упр. 4 2\hu +-pv\ < + р < и + v и + р минимальны.

[Общие правила нахождения кратчайших 2-В-векторов относительно других метрик обсуждают Кэйб и Шнорр в работе Kaib and Sclmorr, J. Algorithms 21 (1996), 565-578.]

6. [МЗО] Пусть ао, ai, ..., at-i - частичные отношения а/т, определенные в разделе 3.3.3, и пусть А - maxo<j<f aj. Докажите, что /х2 > 2тг/{А + I + 1/А).

7. [НМ22] Докажите, что вопросы (а) и (Ь), поставленные после (23), имеют такое же решение для действительных чисел gi, ..., gj i, g+i, ..., qt (см. (24) и (26)).

8. [М18] В строке 10 табл. 1 значение fn очень мало, однако fis совершенно удовлетворительно. Чему равно наибольшее возможное значение цз, когда fi2 = 10~* и m = Ю"?

9. [НМ32] (Ч. Эрмит (С. Hermite), 1846.) Пусть f{xi,...,xt) - положительно определенная квадратичная форма, определенная матрицей U, как в (17), и пусть 9 - минимальное значение / в не равной нулю целой точке. Докажите, что в < ()~idetl/. [Указание. Если W - любая целочисленная матрица с определителем, равным 1, матрица WU определена формой, эквивалентной /. Если же S - любая ортогональная матрица (т. е. earn = S), матрица I/S определена формой, равной /. Покажите, что существует эквивалентная форма д, мршимум которой 9 достигается в (1,0, ...,0). Затем докажите общий результат индукцией по t, записывая g{xi,. ..,xt) = 9{xi + 2X2 + + ptXt) + h{x2, .., Xt), где h - положительно определенная квадратичная форма t - 1 переменной.]

10. [М28] Пусть yi иу2 - взаимно простые числа, такие, что yi + ау2 = О (по модулю тп) ИУ1+У2 < у/4/Зт. Покажите, что существуют целые числа ui и u2, такие, что «1-(-««2 = О (по модулю т), иц/г - u2yi = m, 2 uiyi -(-игуг! < min(ui-(-ui, у?-(-уг) и (ui + «2)(yi + yl) > пг- (Следовательно, согласно упр. 4 = min(ui-(-ui,У1+у)-)

► 11. [НМЗО] (Алан Г. Вотерман (Alan G. Waterman), 1974.) Придумайте эффективную процедуру вычисления множителя а = 1 (по модулю 4), для которой существует относи-тельно простое решение уравнения yi + оуг = О (по модулю т) с у? + yl = у/4/3 т - е, где б > О настолько малб, насколько это возможно при заданном m = 2. (Согласно упр. 10 такой выбор о гарантирует, что > т/(у1 + yl) > у/3/4т, и существует возможность, что U2 будет близко к своему оптимальному значению у/4/3 тп. На практике будем подсчитывать несколько таких множителей для малых е, выбирая затем один из них с наилучшими спектральными значениями 1/2, из, ....)

12. [НМ23] Не прибегая к использованию графических методов, докажите, что любое решение вопроса (Ь), поставленного после (23), должно удовлетворять уравнениям (26).

13. [НМ22] В лемме А используется факт, что U не вырождена, для доказательства того, что положительно определенная квадратичная форма принимает некоторое не равное нулю минимальное значение в точке с целыми не равными нулю координатами. Покажите, что это предположение необходимо, рассмотрев квадратичную форму (19), матрица коэффициентов которой не вырождена и для которой значения /(xi,...,X() расположены произвольно в окрестности нуля (но никогда его не достигают) в не равной нулю точке с целыми координатами (xi,..., Ж().

14. [24] Вручную выполните алгоритм S для тп = 100, а = 41, Г = 3.

► 15. [М20] Пусть и - вектор с целыми координатами, удовлетворяющий (15). Сколько [t - 1)-мерных гиперплоскостей, определенных U, пересекают единичный гиперкуб {(ж1,... ,xt) I О < Xj < 1 для 1 < j < t}? (Это примерно равно числу гиперплоскостей в семействе, которого достаточно, чтобы покрыть Lo)

16. [МЗО] (У. Дитер (U. Dieter).) Покажите, как можно преобразовать алгоритм S, чтобы вычислить минимальное число Nt параллельных гиперплоскостей, пересекающих единичный гиперкуб, как в упр. 15 для всех U, которые удовлетворяют (15). [Указание. Каким приблизительно будет аналог положительно определенной квадратичной формы и леммы А?]

17. [20] Преобразуйте алгоритм S таким образом, чтобы он не только вычислял величины Ut, но и давал на выходе все векторы с целыми координатами (ui,..., u(), удовлетворяющие (15), и такие, что и\-\-----(- и? =ut при 2 <t <Т.

18. [МЗО] В этом упражнении рассмотрен наихудший случай использования алгоритма S.

a) С помощью "комбинаторной матрицы", элементы которой имеют вид у + xSij (см. упр. 1.2.3-39), найдите целочисленные матрицы размера 3 х 3 С/ и V, удовлетворяющие (29) и такие, что преобразование на шаге S5 ничего не дает для любого j, но соответствующие значения Zk в (31) настолько велики, что перебор всех значений невозможен. (Матрица U не обязана удовлетворять (28); нас интересует здесь произвольная положительно определенная квадратичная форма с определителем т.)

b) Хотя преобразование (23) не используется для матриц, построенных в (а), найдите другое преобразование, которое дает значительное сокращение.

► 19. [НМ25] Предположим, что шаг S5 изменен так, что преобразование с q = 1 осуществляется, когда 2Vi - Vj =Vj - Vj. (Таким образом, q = [{Vi - Vj / Vj - Vj) + каково бы ни было i ф j.) Возможно ли, что при этом алгоритм S зациклится?

20. [М23] Обсудите, как применить подходящий спектральный критерий к линейной конгруэнтной последовательности, у которой с = О, Хо - нечетное, тп = 2, о mod 8 = 3 или 5 (см. упр. 3.2.1.2-9.)

21. [М20] (Р. В. Госпер (R. W. Gosper).) Для некоторых задач случайные числа испать-зуются группами по четыре числа, но отбрасывается второе число из каждого множества. Как можно исследовать структуру решетки {~{Х4п,Х4п+2,Х4п+з)}, которую производит линейный конгруэнтный генератор периода m = 2?

22. [М46] Какова наилучшая верхняя грань для рз, если р2 очень близко к своему максимальному значению 4/3 тг? Какова наилучшая верхняя грань р2, если рз очень близко к своему максимальному значению 7г\/2?

23. [М46] Пусть Ui, Vj - векторы, координаты которых являются действительными числами cUi-Vj = Sij для 1 < t, j < t, и такие, что Ui Ut = 1, 2\Ui-Uj\ < 1, 2\Vi-Vj\ < Vj Vj для i Ф j. Насколько большим может быть Vi Vi? (Этот вопрос имеет отношение к граням на шаге S7, если и (23), и преобразование из упр. 18, (Ь) не производят никаких сокращений. Известно, что максимальное значение равно {t + 2)/3. Оно достигается, когда Ui=Ii, Uj = i/i + iv/j, Vi = h-il2 + ---+ It)l\/b, Vj = 2Ij/y/Z для 2 < J < где (/i,..., /() - единичная матрица. Эту схему предложил Б. В. Алексеев.)

► 24. [МЙй] Обобщите спектральный критерий для последовательностей второго порядка вида Хп = {аХп-1 +ЬХп-2) modp, имеющих длину периода р - 1 (см. формулу 3.2.2-(8)). Как следует изменить алгоритм S?

25. [НМ24] Пусть d - делитель т и пусть О < q < d. Докажите, что сумма г(А;), где суммирование производится по всем О < А; < т, таким, что к mod d = q, меньше либо равна {2/d-K) ln(m/d) + 0(1). (Здесь г{к) определено формулой (46) при t = 1.)

26. [М22] Объясните, почему, если использовать метод доказательства (53), можно получить грани, подобные полученным, для

0<п<лг

при о < q < т. Почему доказательство (53) ничего не дает, когда m = 1?

27. [HM3»] (Э. Хлавка (Е. Hlawka) и Г. Нидеррейтер (Н. Niederreiter).) Пусть r(ui,...,m() - функция, определенная в (46). Докажите, что сумма r{ui,... ,Ut), где суммирование производится по всем О < mi, ..., u( < m так, что (mi, ..., u() ф (О,..., 0), и выполняется равенство (15), меньше или равна 2((7г -I- 27rlgm) Гтлх), где Гтлх - максимальный член r(ui,..., U() этой суммы.

► 28. [М28] (Г. Нидеррейтер.) Найдите аналог теоремы N для случая, когда m - простое число, с = О, а - первообразный корень по модулю т, Ао О (по модулю т).