Также можно показать, что последовательность удовлетворяет критерию сериальной корреляции.

Следствие S. Если [О.. 1)-последовательность {к + 1)-распределена, то коэффициент сериальной корреляции между Un и Un+k стремится к нулю:

(Все суммирования здесь выполняются по О < j < п.) Доказательство. По теореме В значения

hEUjUj+k, Euf, ii:u+k EUj, iEUj+k

стремятся соответственно к пределу , , , , при п -> оо.

Рассмотрим несколько более общие свойства распределений последовательностей. Мы определяли понятие fc-распределения, рассматривая все смежные строки размерности к, например последовательность является 2-распределенной тогда и только тогда, когда точки

([/0,[/l), ([/ьС/2), iU2,U3), ([/3,t/4), ([/4, [/5), ...

равнораспределены в единичном квадрате. Это вполне возможно несмотря на то, что пары точек ([/i, [/2), (UsUi), {Us,), . . могут быть не равнораспределенными. Если в некоторой области не хватает точек (f/2n-i, t2n), их можно компенсировать другими точками: {U2n,U2n+i)- Например, периодическая бинарная последовательность

(Х„) = 0,0,0,1, 0,0,0,1, 1,1,0,1, 1,1,0,1, 0,0,0,1, ... (11)

с периодом длины 16 будет 3-распределенной; однако последовательность четных элементов (Лгп) = О, О, О, О, 1, О, 1, О, ... имеет в три раза больше нулей, чем единиц, тогда как подпоследовательность нечетных элементов {Х2П+1} = О, 1, О, 1, 1, 1, 1, 1, ... имеет в три раза больше единиц, чем нулей.

Предположим, что последовательность ([/„) является оо-распределенной. Пример (11) показывает, что подпоследовательность черед}ющихся членов (f/2n) = fo, U2, U4, Щ, ... не обязана быть оо-распределенной или даже 1-распределенной. Но ([/гп) на самом деле является оо-распределенной и многое еще будет верным.

Определение Е. [О.. 1)-последовательность {Un} называют (т, к)-распределенной, если

Рг(Ы] < U,„n+j <Vl, U2 < Umn+j+l <V2, Uk < Umn+j+k-l < Vk)

- {Vl -Ui)...{Vk - Uk)

для любого выбора действительных чисел Ur, Vr при О < Ur < Vr < 1 для 1 < г < к и для всех целых j при О < j < т.

Поэто.му -распределенная последовательность является частным случаем определения Е при т = 1; случай, когда m = 2, означает, что строки размерности к,

начинающиеся с четного номера, должны иметь такую же плотность, как и строки размерности к, начинающиеся с нечетного номера, и т. д. Следующие свойства определения Е очевидны:

(т, fc)-распределенная последовательность является

(т, к)-распределенной для 1 < к < к; (12)

(т, к)-распределенная последовательность является (d, к)-распределенной для всех делителей d числа т. (13)

(См. упр. 8.) Также можно определить понятие (т, fc)-pacпpeдeлeннocти 6-ичной последовательности, как в определении D, и доказать теорему А, остающуюся верной для (т, fc)-pacпpeдeлeнныx последовательностей.

Следующая теорема, которая во многих отношениях является, скорее, сюрпризом, показывает, что свойства, присущие оо-распределению, действительно очень строгие, более строгие, чем мы представляли себе, когда впервые рассматривали определение этого понятия.

Теорема С. (Иван Нивен (Ivan Niven) и Г. С. Цукерман (Н. S. Zuckerman).) оо-распределенная последовательность является (т, fc)-pacпpeдeлeннoй для всех положительных тик.

Доказательство. Достаточно доказать теорему для Ь-ичной последовательности, используя обобщение только что упомянутой теоремы А. Более того, можно предположить, что т - к, так как (12) и (13) утверждают, что последовательность (т, fc)-pacпpeдeлeнa, если она (тк, mfc)-pacпpeдeлeнa.

Таким образом, докажем, что любая оо-распределенная Ь-ичная последовательность Хо, Xl,... является {т, т)-распределенной для всех положительных целых т. Наше доказательство - это упрощенная версия первоначального доказательства, приведенного в статье Niven and Zuckerman, Paciuc J. Math. 1 (1951), 103-109.

Ключевая используемая идея является важным методом, применяемым во многих ситуациях в математике: "Если и сумма т величин, и сумма их квадратов согласуются с гипотезой, что т величин равны, то гипотеза верна". В строгом виде этот принцип можно сформулировать так.

Лемма Е. Заданы т последовательностей чисел (yjn) = Vjo, Vji, для 1 < i < m. Предположим, что

lim (yin +У2П + --- + Утп) = та,

поо

lim sup (yfn + 2/2П + • + Утп) < та"-

п-оо

Тогда для каждого j существует Ит„ юо yjn и он равен а.

Невероятно простое доказательство этой леммы приведено в упр. 9.

Продолжим доказательство теоремы С. Пусть х = xiX2 Хщ - Ь-ичное число; скажем, что х встречается на позиции р, если Xp-m+iXp-m+2 Хр - х. Пусть Uj(n) - число X, находящихся на позиции р, когда р < п и pmodm = j. Пусть

Vjn = ]{п)/т1 и нужно доказать, что

lim yj„ = . (15)

Во-первых, известно, что

lim (2/on + 2/in + -- + 2/(m-i)n) = 7, (16)

так как последовательность т-распределена. Согласно лемме Е и равенству (16) теорема доказана, если показать, что

limsup(2/2„ + у1п + --- + 2/(m-i)„) < -4;г- (17)

Однако это неравенство не очевидно; необходимо несколько деликатных маневров, прежде чем можно будет его доказать. Пусть q кратно т. Рассмотрим

С(п)= j: (Лп)-Ып-Я)\

0<j<m V /

(18)

0<j<

Это число появлений пар х-в на позициях pi и Р2, для которых п - q<pi<p2<n и р2 - pi кратно т. Рассмотрим сумму

N+g п=1

Каждое появление пары х-в, встречающейся на позициях pi и р2 с pi < Р2 < pi+q, где р2 - pi кратно т и pi < N, учитывается точно pi + q -Р2 раз в общей сумме 5yv (т. е. когда р2 < п <pi+ q), а такие пары, которые появляются на позициях pi и рг с N <pi < р2 < N + q, учитываются точно N + q - Р2 раз.

Пусть dt{n) - число пар ж, встречающихся на позициях pi и р2 с pi-\-t = р2 < п. Приведенный выше анализ показывает, что

{q-mt)dmt{N + q)>SN> {q - mt)d„,t{N). (20)

0<t<g/m 0<t<q/m

Так как начальная последовательность является -распределенной, то

limd™.(Ar) = (21)

для всех t,Q <t < q/m, и, следовательно, из (20) получаем

lim - = V Я(я-т) ,24

0<t<q/m

Из этих равенств после нескольких преобразований получим утверждение теоремы. По определению

Sn=Y1 Е iri) - ijin - q)f - Ып) - iM - 9))),

п=1 0<j<m