Определяющие свойства периодов последовательностей

Последовательность X— периодическая, если x_i = x_i+t при всех г > р, где те N, р е N₀. Если р — наименьшее число, при котором х, — = х, —_+т при всех i > р, то говорят, что в Xимеются совпадения на расстоянии т начиная с номера р. Наименьшее т, при котором в Xесть совпадения на расстоянии т, называют длиной периода последовательности Х_>, обозначается t (X^). Длиной предпериода последовательности X(обозначается v (X_>)), называется наименьшее v такое, что в Xимеются совпадения на расстоянии t (X^) начиная с номера V.

Обозначим: t (X_>) = t, v (X_^) = v. Предпериодом последовательности X называется при v > 0 ее [0, v — 1]-отрезок, и периодом при v > 0 — ее [v + i, v + i +1 — 1]-отрезок, i > 0.

Если v = 0, т. е. x_l — x_i+t для всех натуральных то последовательность X называется чисто периодической с длиной периода t. Периодом чисто периодической последовательности Х_> является ее [i, i + t- 1]-отрезок, i > 0.

Утверждение 8.1.

• а) если в Xесть совпадения на расстоянии т, то t делит т;
• б) если последовательность У_> = /"(Х_>) = {/(х,-)}, где X= {х,-} — периодическая последовательность и /: X —> К, то У^ — также периодическая, при этом у (У_>) < v и Ь (УД) делит t. В частности, если / — биекция, то у (У_>) = v и ?(У_>) = t.

А а) по определению длины периода t < т. Если t = т, то по определению длины предпериода v = р, т. е. утверждение а) верно.

Если t не делит т, разделим т на t с остатком: т = tk + г, где 0 < г < t, тогда при любом i > max{v, р} верна цепь равенств: x_i+r = x_i+r+tk = x_i+T = х, что при г < t противоречит определению длины периода. Значит, г = 0 и t т;

б) если Xj = x_i+t, то /(х,) = f (x_i+t), где i > v. Значит, в У_> имеются совпадения на расстоянии t, начиная с номера р < V, так как нельзя исключить, что /(х_г) = f (x_i+t) для некоторых i) < v и по утверждению 8.1а t (Y_>) делит t.

Если /— биекция, то х_г— = Xj /(х_;) = /(х_у) при г, у > 0. Поэтому в Х^ и У_, члены с номерами г, j вместе либо совпадают, либо не совпадают. Тогда v (y_J = v (XJ и i (y_J = *<*_*).?

Теорема 8.1. Для последовательностей X= {х,*} и У_> = {г/,} над конечной аддитивной группой X, где у_г = х₀ + … + x_z, i = 0, 1, верно:

• а) если Х^ — периодическая с длиной предпериода v > 0 и с длиной периода t, то У. — периодическая с длиной предпериода v — 1 и с длиной периода х, где х I dt и d есть порядок элемента y_v+t — y_v группы X;
• б) если X— чисто периодическая с длиной периода t, то У_> — чисто периодическая с длиной периода х, где xdt и d есть порядок элемента y_t__{ группы X; при этом y:_dt = 0,j = 1, 2,…

^ а) Из соотношения между членами последовательностей Х_> и У^ имеем при i > 0.

В силу периодичности последовательности Xэлемент х_м + x_i+2 + —+x_i+t группы X одинаков при всех i > v и совпадает с y_VJrt — y_v. Тогда y_i+dt = у_; + + d (y_v+t — y_v) = у_{ при всех i > v — 1. Значит, в УД есть совпадения на расстоянии dt, начиная с номера, не большего v — 1. Отсюда последовательность периодическая, и по утверждению 8.1а < v и t (Y_>) делит dt.

Если V (УД < V — 1, ТО y_v-2+dt = #v-2> ^Т0ГД^а *_v-l + *v + - + *_v-2+A = °* ОТСЮДЭ (Х-1 — x_v__1+A) + d (y_v__l+t — y_v_) = 0. Поскольку — У у- i) = ^0/_v+f" У у) = 0,.

то jy. j =x_v_₁₊^, что противоречит условию о длине нреднериода последовательности Х_>. Тогда у (У_Д = v — 1;

б) При v = 0 порядок d элемента y_t__x совпадает с порядками элементов х_{ + х_м + … + x_i+t__v i = 0, 1,… Поэтому y_i+dt = y_i при i > 0, значит, в УД есть совпадения на расстоянии dt, начиная с номера 0. Отсюда Y_^ — чисто периодическая последовательность, т делит dt и при любом j> 1 y^_dt = jd (x₀ + … + + х,-,) =jdy_t_ = 0. ?

Отметим свойства сопряжения последовательностей.

Теорема 8.2.

• а) последовательность Х_> над X = Х_х х … х Х" периодическая Х[^ периодическая, j = 1, …, п, где у (ХД = max{v (XiP), …, v (X^)}, t (X__>) = = HOK (?(X^), t (^ⁿ⁾));
• б) если последовательности и отличаются лишь сдвигом нау-1 знак, т. е. если x_itj = х_м ,_i, i > 1, у = 2, …, п, то ?(ХД = ?(Х1Р) = … = t{X^),

v (*_>) = v (X).'.

^ а) Пусть у (ЛД) = v, ?(АД) = t, v (X^) = v_; и t (X^) = tj, j = 1,…, п. Тогда в АД имеются совпадения на расстоянии НОКД,…, t_n) начиная с номера v, где v < max{v₁, v_w}.

Если t < HOK (?j, t_n), то среди чисел Д …, t_n найдется такое, кото рое не делит t. Пусть, например, t_{ не делит t, тогда в XД* нет совпадений на расстоянии t, иначе получим противоречие с утверждением 8.1а. Значит, и в Xне имеется совпадений на расстоянии t, что невозможно, так как по определению ?(АД) = t. Следовательно, t = НОК (Д…, t_n).

Если v < р, где р = max{v_t,…, v"}, то среди чисел v_t,…, v" найдется такое, которое равно р и больше V. Пусть, например, р = v_{ > v. Тогда х _+i = x _+i+t при i > 0, следовательно, верны равенства и для первых компонент этих наборов: x"_+it ^ = x"_{+i+tt v} i > 0. Отсюда v_{ < р, т. е. имеем противоречие. Значит, v = р;

б) Для последовательности У_> над У обозначим через УДи] последовательность всех ее гг-грамм, п > 0. Если х₂— j = * - 1 , j = 2, …, n, то последовательности X _> и X^ отличаются сдвигом на один знак. Тогда и х⁽4>п] отличаются сдвигом на j — 1 знаков, j = 2, …, п. Заметим, что ?(У_Д = ?(У_>[я]) и у (УД = у (УД[и]) при п > 0 для любой последовательности УД. ?

Следствие. Если последовательность над X = Х_х х … х Х" периодическая и t (X_>) =р^т, где р — простое, те N, то t (X^) = p^mj, j = 1, г?, где 0 < и maximj,…, m,} = m. t>