Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 118
Текст из файла (страница 118)
Гл. 8. Линейные реиуррснтиые носледонательностн Обозначим через Е* множество последовательностей, получени из Е путем отбрасывания нулевой последовательности. Прово приведенные выше рассуждения для всех о Е Е', приход ' к тому, что конечная сумма векторпгих пространств ~ 5 (т, ( обе' является линейным подпространством пространства Е. С друг' стороны, очевидно, что Е: — ~~ 5 (т, (х)) и, значит, Е 8е' ~ 5 (т, (х)). Применяя теорему 8.55, получаем ос е Е =- Е 5(то(х)) = 5()(х)), осе где )' (х) — наименьшее общее кратное многочленов т„(х), а,,.! пробегает конечное множество Е'.
Из теоремы 8.55 следует, что сумма двух и более однородн линейных рекуррентных последовательностей над полем является однородной линейной рекуррентной последовател' постыл. Характеристический многочлен суммарной последа ' тельности тоже легко получается из этой теоремы.
В важных ча ных случаях минимальный многочлен и минимальный пер ' суммарной последовательности можно непосредственно получ ' из соответствующих характеристик суммируемых послед тельностей. 8.57. Теорема. Пусть оь ~' =-- 1, 2, ..., й,— однородные неиные рекуррентные последоватпельности над полем Гч, а т; (х Е и и [х ( — соответствующие минимальные многочлены. Ер многочлены т, (х), ..., ть (х) попарно взаимно просты, то ми мальный многочлен суммы о, + ... + оь равен произведен " т, (х) ... ть (х).
Доказательство. Для доказательства достаточно рассмотр' случай й — -- 2„так как доказательство в общем случае легко лучить по индукции. Если один нз многочленов т, (х) или т, является постоянным многочленом, равным 1, то результат т виален, Аналогично, если минимальный многочлен т (х) ~ Кч (х(, соответствующий сумме о, -( о,, является постоянн многочленом, равным 1, то результат получается непосредствен Предположим, что все многочлеиы т, (х), ти (х), т (х) являю многочлеиами положительной степени.
Так как в силу теоремы 8., о, (т би а 5 (т, (х)) + 5 (тт (х)) =- 5 (т, (х) ти (х)), то т (х) делит т, (х) т, (х). Пусть о, — последовательность з,, ..., а ои — последовательность йи гт, ..., и пусть т (х) == х' - - а„,х" — ' — — а„. 4 В. Семейства линейных последовательностей Тогда х„„ь + 1„,ь =- ад, (зи,ь, + 1„,ь 1); ° . ° -' ае(хн -';- Гв), а=0, 1, Если мы ~ало~им =' знеь аь-гзн л 1- ° — аезп— ~"ь ' ал-г( .ь-1 Ь + аеГ., и = О, 1, и вспомним, что 5 (т, (х)) и 5 (т, (х)) являются векторными пространствами над полем Ке, замкнутыми относительно операции сдвига входящих в них последовательностей (см.
теорему 8,5б), го мы убедимся, что последовательность и„, и„... лежит как и 5 (т, (х)). так и в 5 (те (х)). По теореме 8.54 она является нулевой последовательностью. Отсюда следует, что т, (х) делит т (х) и т (х) делит т (х), а значит, и т, (х) тв (х) делит т (х). Таким образом, т (х) = т, (х) те (х). и Если минимальные многочлены т, (х), .... ть (х) последовательностей и„..., а„соответственно не являются попарно взаимно простыми, то для определения минимального многочлена суммарной последовательности о = а, + ...
+ оь необходимо учитывать свойства исходных последовательностей а„..., аь. Наиболее удобен подход, основанный на использовании произнодящнх функций. Предположим, что 6; (х) Р Гс 1(х]), 1 — 1, ..., а, — производящие функции последовательностей аь Тогда для производящей функции 6 (х) суммарной последовательности о справедливо равенство 6 (х) = 6, (х) + ... -ь 6ь (х). По теореме 8.40 каждая производящая функция 6, (х) может быть представлена в виде дроби, знаменатель которой является много- членом, возвратным к многочлену т~ (х).
Сложим эти дроби, приведя их предварительно к общему знаменателю. а затем, используя вторую часть теоремы 8.40 и метод доказательства теоремы 8.42, найдем минимальный многочлен последовательности и. Применяя указанный подход, можно также получить другое доказательство теоремы 8.57. 8 58. Пример. Пусть о, — последовательность над полем ",. являющаяся импульсной функцией и принадлежащая множеству (х -- х' + х + 1), а о, — последовательность иад (е, являющаяся импульсной функцией и принадлежащая 5 (х' + х' 4 1).
Т~гда по следствию 8,52 соответствующие минимальные много- члены равны (. „+ 1) (х+ 1)'Е'» 1 1 П (хв + х + 1) Е ~'е (х). бзб Гл 8 .Чннейные рекуррентные последовательности По теореме 8.40 производящая функция б (х) суммарной посл' довательцости а = о, + и, равняется хв х' б(х1 = (хе + х+ 1) (х+ 1)г !хе+ х -1-!) (к'+ хе+!) к" — (х 4 хг,. !) !к + 1)г ' В силу второй части теоремы 8.40 возвратный к знаменателю м ' гочлен )е (х) = (ха + х + 1) (х + 1)-, является характеристи скигг чногочленом для и. Из (8.18) следует, что соответствующ' миогочлен Ье (х) задается формулой йв (х) = — х' (!гх)а .= — — ' Так как г„(х) и й, (х) взаимно просты, то, используя метод до зательства теоремы 8.42, можно получить минимальный мн '. член т (х) последовательности о: т Ге! = (х' '- х .Р 1) (х + 1)'.
Заметим, что т (х) является собственным делителем наиболь общего кратного чногочлеиов т, (х) и т, (х), которое равна (х' -г- х -1- 1) (х г- !)' (х' -- х 1 1), Из информации о минимальных многочленах, которую д' теорема 8.57, можно непосредственно получить полезный реву тат о минимальном периоде суммарной последовательности. 8.59.
Теорема. 77усть каждая из последовательностей о;, Т' = 1, ..., 6, являегпся однородной линейной рекуррентной пвс довательностью над полем гч с минимальным периодом г; и нимальным многочленом т; (х) ~ 'г !х1. Если много т, (х), ..., та (х) попарно взаимно просты, то минимальный риод суммарной последовательности о = о, +,.
+ о„равняв, НОК (г,, ..., гь). Доказательство, Рассмотрим случай й =- 2, так как об случай легко получить по индукции. Тогда если г — мннимальн ' период последовательности а:= о, + ое, то по теоремам 8. и 8.57 г =- огй (т, (х) т, (х)), Применяя теорему 3.9, получас ' что г является наименьшим общим кратным огд (т, (х)) 1 огд (те (х)), т.
е. чисел г, и ге. 8.60. Пример. Рассмотрим последовательности о, и а, примера 8.58. Минимальные периоды последовательн а, и о, равняются соответственно г, =- пгд (т, (х)) = 5 и гв =- огд (т, (х)) = 21. Минимальный период последовательное' а = и, и и, равняется г =- огс1 (пг (х)) = 14. При вычислен порядков многочленов мы, разумеется, должны воспользоватьс теоремой 3.9. Таким образом, периоды последовательностей п лучены без вычисления их членов. В нашем случае можно, конечно' проверить полученные результаты с помощью непосредственно, $ 5.
Семейства линейных последовательностей 537 вычисления периода. Для этого вычислим члены соответствуюшн х последовательностей: и,:0,0,0,1,1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,0,1,1,...г, †. 6 о,:0,0,0,0,1,1,1,1,1,0,1,0,1,0,0,1,1,0,0,0,1,0,0,...г,== 2! ',-о.,: 0,0,0,1,0,0,1,1,1,1,0,1,1,0,0,0,0,1,0,0,1,1,1, , г =- 14 Заметим, что г является собственным делителем НОК (г,, г,). Г1 8.61. Теорема.
Пусть о,, 1 =. 1, 2, ..., й, — периодические последовательности над полем Кч, и г~ — минимальные периоды чтих последовательностей, Если числа г,, ..., гь попарно взаимно просты, гпо минимальный период суммарной последовательности о, '- ... + оь равен произведению г, ... гь. Доказательство.
Как и раньше, ограничимся рассмотрением случая й = 2. Очевидно, что г,г, является периодом суммарной последовательности о ==- и, + и,, Таким образом, минимальный период последовательности о, равный г, должен делить произве- дение г,г,. Следовательно, г можно представить в виде г =- д1дм где д, и д, — положительные делители чисел г, и гв соответ- ственно.
В частности, д,гв является периодом последовательности о. Гели о, обозначает последовательность в„, в,, ..., а о,, - — после- довательность 1о, 1,, ..., то в„гва. + 1„+в... = в -1 1, для всех достаточно больших и. Но 1„ч в,„= 1„для всех достаточно больших и, отсюда получаем, что в„+в...
= в„для всех достаточно больших и. Следовательно, г, делит д,г„а так как г, и г, взаимно просты, то г„делит с1,, и, значит, И, =- г,. Аналогично доказы- вается и равенство дв =- г,. П В случае конечного поля гв можно ввести интересную опера- цию над последовательностями элементов этого поля, называе- мую операцией бинарного дополнения. Так, если о — последо- вательность над полем г „ то ее бинарное дополнение, обозначае- мое через д, получается из о заменой каждого элемента, равного О, ~а 1, а каждого элемента, равного 1, — на О. Бинарное допол- нение можно рассматривать как частный случай операции сло- жения последовательностей, так как последовательность д можно получить, прибавляя к о последовательность 1, 1, 1, ....
Следо- вательно, если и является однородной линейной рекуррентной последовательностью, то и д является однородной линейной ре- «Уррентиой последовательностью. Очевидно, что минимальный период о совпадает с минимальным периодом и. Минимальный многочлен последовательности д легко можно получить из мини- мального многочлена исходной последовательности о, 6 62. Теорема. Пусть о — однородная линейная рекуррентная "оследовательность над полем Г,, а д — ее бинарное дополнение.
838 Гл. 8. Линейные рекуррвнтные последовательности г(редставим минимальный многочлен т (х) Р Кв 1х! последовательности о в виде т (х) --- (х ' 1)"т, (х), где «г ~ О, т, (х) Е ;- ~Г, (х), гп, (1) = — 1. Тогда лгинимальный многочлен т (х) по-. «',гедовательности о задается формулой (х;-1)«п(х), если и =-0; гй(х) = «п,(х), если й =:: 1; т (х), если (г )! .
Доказательс«пво. Пусть г — последовательность над нолем Кв.г зсе члены которой равны 1. Так как д =- о + е, а мипимальн многочлен последовательности г равен х -! 1, случай й = следует из теоремы 8.57. Если (г,'. 1, то из теоремы 8,55 вытекает' гто д = о+ е Е 5 (т (х)). Тогда т (х) делит т (х). Если т ( гвляется постоянным многочленом, равным 1, то о является ну девой последовательностью и о -- г, а следовательно, теорем' в этом случае справедлива.
Предположим теперь, что с(еи (т (х)) ~ О. Из теорем 8.53 и 8.55 следует, что о = о + г Р 5 (т (х) ' (х -1- ! )), и тогда т (х) делит т (х) (х + 1). Отсюда для «г ) получаем, что либо т (х) — --- т (х), либо т (х) = (х + 1)" ' т, (х Если Ь -,- 1, то о --= д + е Е 5 (т (х)), откуда следует, ч «й (х) -- т (х), Если же «г — 1, то пусть о — последовательн :„, з,, ..., а т,(х) =хе+а„гх" — '+ +а„ является многочленом положительной степени (случай многочлен нулевой степени тривиален). Положим ил = зв+ь+ад-гав+я-г+ ' 1 авв Так как т (х) =- (х + 1) т, (х) — характеристический многочл последовательности з„.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
