Сначала рассмотрим величину g(ui,... Когда N = т, так что сумма (47) берется по всему периоду, g(ui,... ,ut) = 0, кроме случая, когда [щ,..., щ) удовлетворяет уравнению (15). Поэтому разброс ограничен сверху суммой r{ui,... ,щ), взятой по всем ненулевым решениям (15). Теперь рассмотрим, что произойдет с такой же, как (47), суммой, когда меньше т и q{ui,... ,щ) не кратно т. Справедливы равенства

N

Q<n<N

N т

0<n<N 0<к<т 0<j<m

0<fc<m \ 0<n<N

(49) (50)

0<j<ro

Сейчас Ski = (""Sko, поэтому \Ski\ = \Sko\ для всех I, и можно вычислить это общее значение, выполнив экспоненциальное суммирование:

0</<го Q<l<m 0<j<ro

E E

0<t,j<ro 0<«m

0<i<m i<j<m+i 0<l<m

Пусть s - минимальное число среди чисел, для которых о* = 1 (по модулю т), и пусть

s = (а* - 1)с/(а - 1) mod т.

Тогда S - это делитель т (см. лемму 3.2.1.2Р) и Xn+js = а;„ + js (по модулю т). Сумма по I равна нулю, за исключением случая, когда j - г кратно s, поэтому получим, что

\Sko? = rn

0<j<m/s

Справедливо равенство s = qs, где q и т - взаимно простые (см. упр. 3.2.1.2-21), поэтому оказывается, что

если А;-ь 9 О (по модулю m/s), , .

\ m/y/s, если k + q = 0 (по мод}лю m/s).

Используя эти равенства в (49) и вспомнив неравенство (45), можно показать, что

0<t<m

<

0<n<iV

Е-()

(52)

где сумма берется по О < А; < т, таким, что к + q = О {по модулю m/s). Если воспользоваться упр. 25, чтобы оценить оставшуюся сумму, то получится, что

0<n<N

~ тг N

(53)

Те же грани могут быть использованы, чтобы оценить \N~ I3o<n<JVI Для любого q 0 (по модулю т), так как можно заменить т делителем т. В действительности верхняя грань будет даже меньше, когда q имеет общий делитель с т, так как S и m/y/s, вообще говоря, становятся меньше (см. упр. 26).

Мы доказали, что часть g{ui, ...,ut) нашей верхней грани разброса (44) мала, когда Л достаточно большое и когда {ui,... ,ut) не удовлетворяет (15). В упр. 27 доказывается, что часть /{щ,. нашей верхней грани мала, когда сумма берет-

ся по всем не равным нулю векторам {щ,... ,ut), удовлетворяющим (15), и таким, что эти векторы достаточно далеки от (О,... ,0). Объединив результаты, получим следующую теорему Нидеррейтера (Niederreiter).

Теорема N. Пусть (Хп) - линейная конгруэнтная последовательность (Xq, а, с, т) с периодом длиной тп и пусть s - наименьшее положительное число, такое, что а = 1 (по модулю т). Тогда t-мерный разброс относительно первых N значений (Хп), как определено в (42), удовлетворяет равенствам

О (Vslogs2l + о () + 0((logm) w); (54) I?W = 0((logm)*r„ax). (55)

Здесь Гтях - максимальное значение величины r{ui,... ,ut), определенной в (46), которая взята по всем удовлетворяющим уравнению (15) ненулевым целым векторам

{ui,...,Ut).

Доказательство. Первые два члена О в (54) определяются векторами {ui,...,Ut) из (44), не удовлетворяющими (15), так как в упр. 25 доказывается, что f{ui,щ), где сумма берется по всем {ui,... равнаО(((2/7г) Inm)*), и упр. 26 ограничивает каждое g{ui,... ,ut). (Эти члены отсутствуют в (55), поскольку в этом случае g{ui,... ,щ) = 0.) Оставшийся член О в (54) и (55) определяется ненулевым вектором {щ,... ,Ut), который удовлетворяет (15), если использовать грани, полученные в упр. 27. (Внимательно проверяя данное доказательство, каждое О в этой формуле можно заменить функцией от t.)

Равенство (55) относится к критерию серий при размерности t для полного периода, тогда как равенство (54) дает полезную информацию о распределении первых Л сгенерированных значений, когда Л меньше т, если только Л не слишком мало. Заметим, что (54) гарантирует малый разброс только тогда, когда s достаточно большое, иначе будет доминировать член m/\/s. Если т = pl.-.p и gcd(a - 1, т) = р( •..pl, то s равно Pj"- ...р"" по лемме 3.2.1.2Р. Таким образом, наибольшие значения s соответствуют большому потенциалу. В общем

случае m = 2, а = 5 (по модулю 8) и получаем s = \т. Значит, равно 0{у/гп (logmy/N) + 0((logm)Vmax)- Не составляет труда доказать, что

- (56)

(см. упр. 29). Следовательно, равенство (54), в частности, указывает, что разброс в -мерном случае будет мал, если критерий серий пройден и если в некоторой степени больше ут (logm)+i.

В смысле теоремы N это почти так же строго. Из результатов упр. 30 следует, что линейные конгруэнтные последовательности, подобные приведенным в строках 8 и 13 табл. 1, имеют разброс порядка (logm)7m при размерности 2. Разброс в этом случае чрезвычайно мал несмотря на то, что существуют области, имеющие вид параллелограмма площадью » l/y/m, в которых нет точки (f7„,f7„+i). Тот факт, что разброс может столь резко измениться, когда точки вращаются, предупреждает о том, что критерий серий может быть не так точен при определении случайности, как инвариантный относительно вращения спектральный критерий.

G. Историческая справка. В 1959 году, когда верхнюю грань ошибки вычисления i-мерного интеграла определяли методом Монте-Карло, Н. М. Коробов придумал метод оценки множителя линейной конгруэнтной последовательности. Его усложненная формула связана, скорее, со спектральным критерием, так как на нее сильно влияют "малые" решения (15); но это не совсем одно и то же. Критерий Коробова широко обсуждался в литературе и изучался Купером и Нидеррейтером (см. Kuipers and Niederreiter, Uniform Distribution of Sequences (New York: Wiley, 1974), §2.5).

Необычно сформулировали спектральный критерий P. P. Ковэю и P. Д. Мак-Ферсон (R. R. Coveyou and R. D. MacPherson, JACM 14.(1967), 100-119), введя его интересным косвенным путем. Вместо того чтобы работать с решеточной структурой последовательных точек, они рассматривали случайные числа генераторов как источник -мерных "волн". Числа у/х( + xj , такие, что xi + • + a*~xt = О (по модулю т), в их трактовке рассматривались как "частоты" волн или точки "спектра", определенного генератором случайных чисел, с низкочастотными волнами, которые неблагоприятны для случайности. Отсюда название спектральный критерий. Ковэю и Мак-Ферсон ввели аналогичную алгоритму S процедуру для выполнения их критерия, основанную на принципах леммы А. Тем не менее их оригинальная процедура (в которой используются матрицы UU и VV вместо U и V) имела дело с крайне большими числами. Идея работы непосредственно с U и V была независимо предложена Ф. Янссенсом и У. Дитером (см. F. Janssens and и. Dieter, Math. Сотр. 29 (1975), 827-833).

Несколько других авторов указывают, что спектральный критерий можно было бы объяснять в намного более конкретных терминах, и предлагают изучить решетки и решетчатые структуры соответствующих линейных конгруэнтных последовательностей, что сделает фундаментальные ограничения случайности графически наглядными. [См. работы Марсалья, Вуда, Ковэю, Веера, Руфа и Вильямсон, Марсалья и Веера: G. Marsaglia, Proc. Nat. Acad. Sci. 61 (1968), 25-28; W. W. Wood, J. Chem. Phys. 48 (1968), 427; R. R. Coveyou, Studies in Applied Math. 3 (Philadelphia: SIAM, 1969), 70-111; W. A. Beyer, R. B. Roof, and D. Williamson, Math. Сотр. 25 (1971),