Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
Мц ^n + fe """ ~ CIqSл
~ $п+к \ п +к-1 Ь ' ' * ^ О, ^ * * ¦ * >
и вспомним, что S (mt (х)) и S (tn2 (х)) являются векторными
пространствами над полем F§1 замкнутыми относительно операции сдвига
входящих в них последовательностей (см. теорему 8.56), то мы убедимся,
что последовательность м0) ult ... лежит как и 5 (тг (х)), так и в S (тt
(ос)), По теореме 8.54 она является нулевой последовательностью. Отсюда
следует, *что пц (х) делит т (х) и пц (х) делит т (х), а значит, и тг (х)
т2 (х) делит т (х). Таким образом, т (х) - тг (х) тг (х). ?
Если минимальные многочлены mi (х), .... mh (х) последовательностей сг1(
о^ соответственно не являются попарно взаимно простыми, то для
определения минимального многочлена суммарной последовательности о - од +
... -f oh необходимо учитывать свойства исходных последовательностей од,
,ah. Наиболее удобен подход, основанный и а использовании производящих
функций. Предположим, что Gt (х) ? Тя Их]], i - 1, h, - производящие
функции последовательностей од, Тогда для производящей функция G (х)
суммарной последовательности о справедливо равенство G (х) - Gi (х) -Е
... -Е Gh{x). По теореме 8.40 каждая производящая функция Gt (х) может
быть представлена в виде дроби, знаменатель которой является многочленом,
возвратным к многочлену гщ (х). Сложим зти дроби, приведя их
предварительно к общему знаменателю, а затем, используя вторую часть
теоремы 8.40 и метод доказательства теоремы
8.42, найдем минимальный многочлен последовательности а. Применяя
указанный подход, можно также получить другое доказательство теоремы
8.57.
8.58. Пример. Пусть од - последовательность над полем являющаяся
импульсной функцией и принадлежащая множеству $ (х4 д- xz Е х -Е 1), а
а.2 - последовательность над jpa, являющаяся импульсной функцией и
принадлежащая 5 (х5 -Е х4 + 1). *°гда по следствию 8.52 соответствующие
минимальные много-члены равны
т\ (х) - х4 Е х3 "Е х + 1 - (х2 + х -Е 1) (х Е I)2 ? !Р" fx],
Щ (х) хь -Е х4 Е 1 - (х2 + х 4- !) (х3 -Е х -Е I) Е F* 1x1.
536
Гл. 8. Линейные рекуррентные последовательности
По теореме 8.40 производящая функция G (л;) суммарной довательности о яв
a, ф- равняется
поел
ж3
{** + *+!) (.? + 1)*
(х* + х + 1) (л*3 р х2 р !)
•.4i
(jfS + x* 4- |)U ь 1)
В силу второй части теоремы 8.40 возвратный к знаменателю мц гочлен /0
(у) = (.г1 -f л: 4* 1) (у + I)2, является характеристик екпм многочленом
для а. Из (8.18) следует, что соответствуюЩ многочлен hQ (у) задается
формулой (у) - -х4, (1/у)3 - -4* Так как /" (х) и /ц, (у) взаимно просты,
то, используя метод до! зательства теоремы 8.42, можно получить
минимальный мн член т (х) последовательности а:
т (у) - (х3 f- х 4- 1) (у 4- 1)'2.
.•Ч='
¦¦в
.U-
•jj
г
В?
%
< и
Заметим, что т (у) является собственным делителем наибольш! общего
кратного многочленов ту (у) и т2 (у), которое равня
(у2 -г х ~Ь 1) (х г I)2 (у3 4- х I I).
Из информации о минимальных многочленах, которую теорема 8.57, можно
непосредственно получить полезный рез тат о минимальном периоде суммарной
последовательности,
8.59. Теорема. Пусть каждая из последовательностей I
= 1.hy является однородной линейной рекуррентной
довательностью над полем с минимальным периодом /у и нимальным
многочленом mt (у) ? fq [х\. Если многоч т1 (х), ..., mh (у) попарно
взаимно просты, то минимальный риод суммарной последовательности о - о1 f
.,, -f oh равняв,
НОК (ту, гл).
Доказательство. Рассмотрим случай h - 2, так как общ случай легко
получить по индукции. Тогда если г -- минимальн период последовательности
о - -г ог3. то по теоремам 8.-и 8.57 г -- ord (mi (у) т2 (у)). Применяя
теорему 3.9, пол уча что г является наименьшим общим кратным ord (mv (у))
ord (m2 (у)), т. е. чисел rj и у,
8.60. Пример. Рассмотрим последовательности оу и о2 примера 8.58.
Минимальные периоды последовательн ot и равняются соответственно - Ord
(тл (у)) 6 и г2 - ord (m2 (у)) = 21. Минимальный период
последовательное^, о = Oj +¦ равняется г = ord (т (у)) = 14. При
вычислена порядков многочленов мы, разумеется, должны воспользоваться
теоремой 3.9. Таким образом, периоды последовательностей п лученыбез
вычисления их членов. В нашем случае можно, конечно! проверить полученные
результаты с помощью непосредственно
ж
' ¦•.•л
§ 5. Семейства линейных последовательностей
537
вычисления периода. Для этого вычислим члены соответствующих
последовательностей:
а,: oao.ujaoai.i.iaoai.uaoau, г, - 6
(Т2: 0,0,0,0,! J,!,!,! А! Д1 ,0,0, i, i ,0,0,0,1 ДО, ... r2 = 21
Jpp аа: ОДО/ГДОЛЛЛ^ЬОЛЛДОДОЛДОЛЛЛ, ... г = 14
Заметим, что г является собственным делителем НОК (гь г2).
8.61. Теорема. Пусть о*, / = !, 2, ..., h, периодические
последовательности над полем ЦД а п - минимальные, периоды этих
последовательностей. Если числа щ, rh попарно взаимно просты, то
минимальный период суммарной последовательности
Oi ! ... f % равен произведению г\ ... гн-
Доказательство. Как и раньше, ограничимся рассмотрением случая h - 2.
