случайности. На самом же деле она не может обеспечить даже маленькую сериальную корреляцию для 1 ООО последовательных элементов последовательности (см. упр. 14).

Во-вторых, (39) и точность приближения обеспечивают относительно малое значение С только при а w /m. Поэтому предлагалось выбирать множитель, равный примерно /rn. На самом деле почти все множители дают значения С, постоянно меньшие, чем 1/л/т, поэтому (39) не является очень хорошей аппроксимацией истинного поведения оценки. Минимизация грубой верхней границы С не минимизирует само значение С.

В-третьих, было замечено, что (39) дает свои самые лучшие оценки, когда

с/т « i ± %/3, (40)

так как эти значения являются корнями уравнения 1 - бж -I- 6х = 0. "При отсутствии любого другого критерия выбора с можно использовать и этот." Последнее утверждение имеет смысл, но оно вводит в лучшем случае в заблуждение, так как эксперимент показал, что значение с оказывает большое влияние на истинное значение сериального коэффициента корреляции, когда а - хороший множитель. Выбор (40) в значительной степени снижает значение С только в случаях, аналогичных примеру 2. И мы обманываем себя, так как плохой множитель продемонстрирует свои недостатки другим путем.

Ясно, что необходима лучшая оценка, чем (39). Такая оценка сейчас доступна благодаря теореме D, в основных чертах доказанной в работе Ульриха Дитера (Ulrich Dieter) [Math. Сотр. 25 (1971), 855-883]. В соответствии с теоремой D а{а,т,с) будет малым, если частичные отношения а/т малы. Кроме того, детальнее анализируя обобщенные суммы Дедекинда, можно получить вполне точные оценки.

Теорема К. При предположениях теоремы D всегда выполняется i<J<t i<i<< i<i<t i,<i<f

j odd j even j odd j even

Доказательство. Обратитесь к работе Д. Э. Кнута (D. Е. Knuth, Acta Arith-metica 33 (1978), 297-325), в которой, кроме всего прочего, показано, что эти границы, по существу, - наилучшие возможные границы, когда частичные отношения большие. I

Пример 4. Оцените сериальную корреляцию для а = 3141592621, m = 2 и нечетного с.

Решение. Частичные отношения а/т равны 10, 1, 14, 1, 7, 1, 1, 1, 3, 3, 3, 5, 2, 1, 8,7, 1, 4, 1, 2, 4, 2. Таким образом, по теореме К

-55 < а{а,т,с) < 67.5

и сериальная корреляция гарантированно будет крайне низкой для всех с.

Заметим, что эта граница значительно лучше, чем можно было получить из (39), так как ошибка в (39) имеет порядок а/т. Наш "случайный" множитель не может быть настолько лучше специально выбранного множителя, чтобы хорошо выглядеть

при использовании (39). На самом деле можно показать, что среднее значение ]Cj=i jj взятое по всем множителям а, относительно простым с т, равно

(lnm)2 +O((logm)(loglogm))

(см. упр. 4.5.3-35). Поэтому вероятность того, что случайный множитель имеет большую сумму uj, скажем, больше (logm)* для некоторого фиксированного б > О, стремится к нулю при т оо. Это доказывает эмпирически очевидный момент, что почти все линейные конгруэнтные последовательности имеют чрезвычайно низкую сериальную корреляцию по целому периоду.

В упражнениях, приведенных ниже, показано, что другие априорные критерии, такие как критерий серий по целому периоду, могут быть выражены и в терминах небольшого обобщения сумм Дедекинда. Из теоремы К следует, что линейная конгруэнтная последовательность будет удовлетворять этим критериям тогда и только тогда, когда определенные дроби (зависящие от а и т, но не от с) имеют малые частичные отношения. В частности, из результатов упр. 19 следует, что проверка по критерию серий для пар удовлетворительна тогда и только тогда, когда а/т имеет небольшие частичные отношения.

В книге Суммы Дедекинда Ганса Радемахера и Эмиля Гросвальда (Hans Ra-demacher and Emil Grosswald, Math. Assoc. of America, Carus Monograph No. 16, 1972) обсуждается история и свойства сумм Дедекинда и их обобщений. Другие теоретические критерии, в том числе критерий серий для больших размерностей, рассматриваются в разделе 3.3.4.

УПРАЖНЕНИЯ (часть 1)

1. [МЮ] Выразите х mod у в терминах "пилообразной" и (5-функций.

2. [М20] Докажите "реплективный закон", равенство (10).

3. [НМ22] Найдите разложение б ряд Фурье (по синусам и косинусам) функции ((ж)).

► 4. [МЮ] Если т = 10°, то какое максимальное значение возможно для d (в обозначениях теоремы Р), если дано, что потенциал генератора равен 10?

б. Получите формулу (17).

6. [М27] Предположим, что hh + кк = 1. а) Покажите без использования леммы В, что

.ih,k,c)=aih,k,0) + 12 j: {[)i))+e{{f))

0<j<c

для всех целых с > 0.

b) Покажите, что (()) + ((х)) " hk ~ ¥{h)""

c) Основываясь на предположениях леммы В, докажите равенство (21).

► 7. [М24] Докажите закон взаимности (19), когда с = О, используя обобщенный закон взаимности из упр. 1.2.4-45.

► 8. [М34] (Л. Карлиц (L. Carlitz).) Пусть

Е ((f))(())

0<j<r

Обобщив метод доказательства, использованный в лемме В, докажите следующее прекрасное тождество Г. Радемахера (Н. Rademacher). Если каждые из чисел р, д, г взаимно просты одно относительно другого, то

р{р, q, г) + p{q, г,р) + р(г,р, 9) = £: + £; + £- -3-

qr rp pq

(Закон взаимности для сумм Дедекинда при с = О является частным случаем при г = 1.)

9. [м40] Существует ли простое доказательство тождества Радемахера (упр. 8) с использованием в частном случае метода доказательства упр. 7?

10. [М20] Покажите, что когда О < h < к, то можно легко выразить (т(к - h, к, с) и CT(h,k, -с) в терминах (7{h,k,c).

11. [Л/50] Формулы, приведенные в разделе, показывают, как оценить ст{Н,к,с), когда h як - взаимно простые числа и с - целое число. В общем случае докажите, что

a) a{dh,dk,dc) = ст{Н,к, с) для целых rf > 0;

b) (t(/i, к, с + в) = (T(h, к, с) + 6{{hc/k)) для целых с, действительных 0<в<1, hlkii hh = 1 (по модулю к).

12. [м24] Покажите, что если h и к - взаимно простые числа и с - целое число, то \cT{h,k,c)\<{k-l){k-2)/k.

13. [М24] Обобщите равенство (26) так, чтобы получить выражение для ст{Н,к,с).

* 14. [М20] Линейный конгруэнтный генератор, для которого т = 2, а = 2* -Ь 1, с = 1, был подвергнут сериальному корреляционному критерию для трех групп по 1 ООО последовательных чисел. В результате этого была получена очень высокая корреляция, лежащая между 0.2 и 0.3 в каждом случае. Чему равна сериальная корреляция данного генератора, взятая по всем 2° числам периода?

15. [М21] Обобщите лемму В так, чтобы ее можно было применять к действительньш числам с, О < с < Л.

16. [М24] Задана таблица Евклида, определенная в (32). Пусть.ро = 1, pi = oi и pj = ajpj-i + pj-2 для 1 < j < <. Покажите, что сложные части сумм в теореме D могут быть переписаны следующим образом, позволяющим выполнять вычисления с нецелыми числами:

[Указание. Докажите тождество l]i<,<r(-l)"V"j"j+i = {-VPT-i/mimr+i для 1 < r<t.]

17. [М22] Напишите алгоритм вычисления a{h, к, с) для целых h, к, с, удовлетворяющих предположениям теоремы D. Он должен использовать только арифметику целых чисел (с неограниченной точностью), и ответ должен быть записан в виде А + В/к, где А и В - целые числа (см. упр. 16.) По возможности используйте только конечное число переменных для временного запоминания вместо того, чтобы вводить такой массив, как ai, 02, ..., at.

► 18. [М23] (У. Дитер (U. Dieter).) Даны положительные целые числа h, к, z. Пусть

sih,k,c,z)=j:({))-

0<j<z

Покажите, что сумма может быть вычислена в приближенной форме в терминах обобщенных сумм Дедекинда и пилообразной функции. [Указание. Когда z < к, величина а/к\ - L(j - z)/k\ равна 1 для О < j < г и равна О для z < j < к, поэтому можно включить данный множитель и выполнить суммирование по О < j < к.]