Периодичность ЛРП. Длина периода ЛРП.

Максимальные ЛРП.

Определение 1. Последовательность d = {d _x } Î s называется периодической, если существует такое неотрицательное число k, и такое натуральное числоt, что для всех x Î N ₀, x ³ k выполняется равенство d _{x + t} = d _x.

Наименьшие натуральные числа k и t, удовлетворяющие условиям определения 1 называются соответственно, периодом и длиной предпериода последовательности d.

Периодическую последовательность можно изобразить графически следующим образом:

 

Условие периодичности последовательности эквивалентно условию

T^{k + t}·d = T^k ·d, T^{k + t}·d - T^k ·d = 0,

 

или

l ^k (l ^t -1)·d = 0.                                                    (1)

Обозначим через k (d) и t(d) соответственно длину предпериода и периода последовательности d. 

Теорема 1. Пусть d - периодическая последовательность элементов поля F и k Î N ₀, t Î N.   Тогда условие

для всех x Î N ₀, x ³ k равенство d _{x + t} = d _x                                (2)

равносильно условию

k ³ k (d), t(d)| t.                                                   (3)

Доказательство. Пусть k ₀= k (d), t ₀= t(d).Тогда в силу сказанного выше k ₀Î N ₀, t ₀ Î N, наименьшие натуральные числа, удовлетворяющие условию (1).

Пусть теперь для чисел k Î N ₀, t Î N выполняется условие (2), тогда выполняется и условие (1). НОД многочленов l ^k (l ^t -1)·d, . Применяя теорему о вычислении НОД многочленов методом получим

,

где k ₁ = min(k ₀, k), t ₁ = НОД(t ₀, t). Так как  - линейная комбинация многочленов l ^k (l ^t -1)·d, , то следует, что равенство (1) выполняется для чисел k = k ₁, t = t ₁. Тогда k ₁ ³ t ₀ или t ₁ ³ t ₀. Из этих неравенств следует, что k ₁ = t ₀ и t ₁ = t _0.. Тогда k ³ k ₀, t ₀| t.

Обратно, пусть выполняются условия (3). Тогда

.

Поэтому для чисел k и t выполняется условие (1). Отсюда выполняется условие (2).

Следствие 1. Если d - периодическая последовательность над полем F, то для любого многочлена g (l) Î F [l]   последовательность a = g (l)·d – периодическая над полем F, причем

k (a) £ k (d),t(a)|t(d).                                          (4)

Доказательство. Пусть k ₀= k (d), t ₀= t(d). Тогда

.

Тогда по теореме 1 k (a) £ k ₀,t(a)| t ₀.

Следствие 2. Если a, b - периодические  последовательности над полем F, то последовательность d = a + b периодическая и

k (d) £ max{ k (a), k (b)),t(d)|НОК(t(a),t(b)).                           (5)

При этом:

1) если k (a) ¹ k (b), то

k (d) = max{ k (a), k (b));                                         (6)

2) если (t(a),t(b)) = 1, то

t(d) = НОК(t(a),t(b));                                          (7)

3) если a, b - ЛРП, для которых можно указать взаимно простые характеристические многочлены, то справедливы равенства (6), (7).

Доказательство. Пусть k = max{ k (a), k (b)), t = НОК(t(a),t(b)). Тогда по теореме 1  Следовательно,

k ₀= k (d), t ₀= t(d). Тогда по теореме 11, получаем соотношения (4).

1) Пусть k (a) ¹ k (b), например, k (a) < k (b). Тогда k = k (b). По доказанному выше k (d) £ k. Докажем, что k (d) £ k. Допустим противное, что k (d) < k. Тогда многочлен . Поэтому  и по теореме 1 k (b)£ k – 1. Что невозможно. Следовательно, k (d) = k и формула (5) доказана.

2) Пусть (t(a),t(b)) = 1, и t(d) = t. Далее

.

Так как t |(tl), t |t(a), то по теореме 1 .

Поэтому  и по теореме 1 t (b) | t l. Так как (t (b), l) = 1, то t (b) | t. Аналогично доказывает.

3) Пусть a, b - ЛРП, для которых можно указать взаимно простые характеристические многочлены f (l), g (l). Тогда f (l)·a= 0, g (l)·b= 0 и поэтому        (f (l) g (l))·(a+b) = 0.  Так как

Тогда по теореме 1 k (a) £ k ₀,t(a)| t ₀.

 

 

разложения на неприводимые множители

Теорема 1. Любое решение d = {d _x }Î s (f) линейного рекуррентного уравнения периодично, т.е. существует такое натуральное число t, что для любого x Î N ₀ выполняется равенство d _{x + t} = d _x.

Доказательство. В силу теоремы 2 параграфа 3 достаточно доказать, что существуют такие натуральные числа k и l, что

d _k = d _l, d _{k + 1} = d _{l + 1}, …, d _{k + n - 1} = d _{l + n - 1}.                                 (1)

Так как всего различных наборов вида (b ₁, b ₂,…, b_n)над полем   F_p конечно и равно pⁿ. Поэтому, если k > l и t = k - l наименьшее число со свойством (1), то  t £ pⁿ -1.  

Определение 1. Наименьший натуральный период t решения d линейного рекуррентного уравнения называется примитивным периодом решения d. Обозначаем примитивный период решения d через per d.

Теорема 2. Если F = F_p,   d = {d _x }Î s _F (f), f Î F_p [l], то per d £ pⁿ -1.

Доказательство. Число различных наборов  (d₀, d₁,…, d _{n - 1}) равно pⁿ. Если  (d₀, d₁,…, d _{n - 1}) = (0, 0, …, 0), то d = {0} и per d = 1 £ pⁿ -1.

Если (d₀, d₁,…, d _{n - 1}) ¹ (0, 0,…,0), то для любого x Î N ₀ набор  (d _x, d _{x +1},…,d _{x + n - 1}) ¹ (0, 0, …, 0), а число ненулевых наборов вида (d _x, d _{x +1},…, d _{x + n - 1}) равно pⁿ -1. Поэтому даже, если все они встретятся, то при некотором t имеем (d₀, d₁,…, d _{n - 1}) = (d _t, d _{t +1},…, d _{t + n - 1}). Следовательно,  per d £ pⁿ -1.

 

Аннулирующие многочлены

Определение 1. Многочлен f Î F [l] называется нормированным, если его старший коэффициент равен1.

Определение 2. Многочлен g Î F [l] называется аннулирующим последовательность d, если g (l)·d= 0.

Пусть F = F_p, A _F (d) = A (d) – множество всех многочленов, аннулирующих последовательность d.

Пример 1. Пусть d решение уравнения 

d _{x + n} = a ₁d _{x + n - 1} + a ₂d _{x + n - 2} + …+  a_n d _x                                              (1)

t = per d. Тогда

Таким образом, l^t - 1 – аннулирующий многочлен решения d.

Теорема 1. Характеристический многочлен уравнения (1) аннулирует любое решение d уравнения (1).

Доказательство. Пусть d = {d _x } – любое решение уравнения (1),

f (l) = l ⁿ - a ₁l ^{n- 1} - …+ a_n Î F_p [l]

- характеристический многочлен уравнения (1). Тогда для любого x Î N ₀ имеем

f (l)·d = a = {a _x },

где

a _x = (Tⁿ - a ₁ T ^{n- 1} - …+ a_n)·d _x  = a _x = Tⁿ ·d _x - a ₁ T ^{n- 1}·d _x - …+ a_n d _x =

 = d _{x +n} - a ₁d _{x + n - 1}-…- a_n d _x = 0,

так как d - решение уравнения (1).

Теорема 2. Пусть d Î s – последовательность над полем F_p,

f (l) = l ⁿ - a ₁l ^{n - 1} - …+ a_n Î F_p [l]

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

Доказательство. Если d – решение уравнения (1), то по доказанному в теореме 1 полиномиальный оператор f аннулирует d.

Обратно пусть полиномиальный оператор f аннулирует d, т.е. f ·d = a = 0, т.о.

для любого x Î N ₀ имеем

a _x = (Tⁿ - a ₁ T ^{n- 1} - …+ a_n)·d _x  = a _x = Tⁿ ·d _x - a ₁ T ^{n- 1}·d _x - …+ a_n d _x =

 = d _{x +n} - a ₁d _{x + n - 1}-…- a_n d _x = 0.

Отсюда

d _{x +n}  =   a ₁d _{x + n - 1}+…+ a_n d _x

и d = {d _x } – решение уравнения (1).

Теорема 3. Пусть d Î s (f), F = F_p; g, h Î A _F (d) = A (d); q Î F_p [l]. Тогда:

1) g + h Î A _F (d),

2) g - h Î A _F (d),

3) gq Î A _F (d).

Доказательство. Пусть  g, h Î A _F (d) = A (d); q Î F_p [l]. Тогда g ·d = 0, h ·d = 0. Тогда по теореме 4 параграфа 2 имеем

(g + h)·d = g ·d + h ·d = 0 + 0 = 0;

(g - h)·d = g ·d - h ·d = 0 - 0 = 0;

(gq)·d = q ·(g ·d)= q ·0 = 0.

Отсюда следует утверждение теоремы.

Определение 3. Минимальным многочленом последовательности d Î s (f) называется нормированный многочлен наименьшей степени из A (d).

Примеры. Если d = 0, то m _d(l) = 1.

Если для любого x Î N ₀ имеем d _{x +1} = d _x и d _x ¹ 0, то m _d(l) = l -1.

d ¹ 0 тогда и только тогда, когда deg m _d(l) ³ 1.

Теорема 4 (основное свойство минимального многочлена). Многочлен g Î F_p [l] принадлежит A _F (d) тогда и только тогда, когда g делится на минимальный многочлен m _d(l) решения d.

Доказательство. Необходимость.Пусть g Î A _F (d). Докажем, что m _d(l)| g. Допустим, что это не так. Тогда разделим g  на m _d(l) с остатком

g (l)= m _d(l) q (l) + r (l),

где q (l), r (l)Î F_p [l], и deg r (l) < deg m _d(l). Тогда

r (l)·d = (g (l)- m _d(l) q (l))·d = g (l)·d- m _d(l) q (l)·d = 0 + 0 = 0,

и r (l)Î A _F (d) и deg r (l) ³ deg m _d(l). Получаем противоречие.

Достаточность. Пусть m _d(l)| g. Тогда g (l)= m _d(l) q (l), где q (l)Î F_p [l].Тогда по теореме 4 параграфа 2 имеем

g ·d = (m _d q)·d = q ·(m _d·d) = q ·0 = 0.

Теорема 5. Минимальный многочлен главного решения уравнения (1) есть характеристический многочлен этого уравнения.

Доказательство. Пусть d – главное решение уравнения (1), m _d(l) – минимальный многочлен d, f – характеристический многочлен уравнения (1). Так как f ·d = 0,  то по теореме 4 m _d(l)| f и, следовательно, deg m _d(l) £ deg f. По определению главного решения последовательности d, T ·d,…, T^{n - 1}·d образуют базис пространства решений S (f). Так как для любого i = 1, 2,…, n -1

m _d(l)·(Tⁱ ·d) = Tⁱ ·(m _d(l)·d) = Tⁱ ·0 = 0,

то многочлен m _d(l) аннулирует любой элемент из S (f). Тогда S (f) Í S (m _d). Поэтому число элементов в S (f) не меньше чем в S (m _d):

.

Следовательно, deg f £ deg m _d(l). Отсюда deg m _d(l) = deg f. Так как m _d(l)| f и оба многочлена нормированные, то отсюда следует, что m _d(l) = f.