Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
каждого i = 1,2, h элемент at пробегает корни многочлена ft (дг). Тогда
по теореме 8.55
SF (ft (дс)) = 2 (дс - af), 1 < i < h.
ai
Заметим, что для подпространств Уъ У2, У3 векторного пространства SF
справедлив закон дистрибутивности:
Vi (Уг + Уз) - ViV% + УгК
В самом деле, по закону дистрибутивности для Последователь ностей ух (Г2
+ V9) s У\У% + VjVs' С другой стороны, оче видно, что УуУз с (У2 4- у3),
ViVb ^ У\ (Уг т Уз) и, следовательно, У\У2 + УгУз s Vi (У% ~Т Уз)- На
основании закона дистрибутивности справедливо равенство
sf (h W)SF (fh (дс)) = 2 $р (дс - "i).." SF (дг - aA).
оьА, * *
544
Гл. 8. Линейные рекуррентные последовательности
• |
..V
Нетрудно проверить, что
Sр (X - ^ F ' * * (r)л)*
откуда по теореме 8.55
t.
"• i'e
Sf ifi (л))... 5f (fh (x))
Sp (x CL I ... ctfr)
tel f * * * I
SF(h(x) V ... vfh(x)).
Утверждение теоремы 8.67 следует теперь из леммы 8.68.
Теорема 8,67 показывает, в частности, как находить характер стический
многочлен для произведения однородных линейв рекуррентных
последовательностей в случае, рассматриваем в этой теореме. Другой подход
может основываться на теор 8.21. Для этого достаточно детально разобрать
случай произведе! двух однородных линейных рекуррентных
последовательности Пусть последовательность s0, slt ... лежит в S (/
(х)), а после вательиость tlt ... лежит в S (g (х)). Еслн многочлен /
имеет лишь простые, корни а1ч ак, а многочлен g (х) им лишь простые корнк
..., flm, то по формуле (8.8)
k т
sn " S ь&1, ^=Sc/P/* п ~о, 1,
i=i /=i
где коэффициенты bt и Cj лежат в конечном расширении по fq. Если ¦у1, уг
- различные значения, которые могут пр нимать произведения вида ctjpy, 1
i < k, 1 < / < tn, тр|
k т r
U" = SA -=2 2 = 2 <*.??> я = 0. 1,
{=1 /=1 ( = [
где д?*, ..., - некоторые коэффициенты из конечного рас:
рения поля Fg. Пусть теперь
¦|
%
• <Г<
Ж.
!iS
$
h(x)~f (х) v g(x}^ хг - д^гх
(Г-1
t "
- аО V Fq [xj.
I s
Тогда для n ~ 0, 1,
* * P
получаем
r
U
n-\-r ¦* "Г-i"/l+r-I
= Ц (?,) = o,
M
,=вд
• • j' S!
\*:V . ля
t
,
Г*,
•"d
и, таким образом, многочлен h (x) будет характеристическим мво§ гочленом
последовательности и0, иг, .... являющейся произвел нием
последовательностей s0, sif ... и ^ tx, ... .
8.69. Пример, Рассмотрим последовательность 0, 1, 0, 1 .j иад полем Fa с
минимальным периодом 2 и минимальным много членом (х - I)2, Если мы
умножим эту последовательность саму себя, то получим ту же самую
последовательность. С друга стороны, (х - I)2 v (х - I)2 - х - 1, что не
является характер
У . ".
J Га : '
'Ч--
§ 5. Семейства линейных последовательностей
545
ристическим многочленом последовательности, полученной в результате
перемножения. Таким образом, равенство, доказанное в теореме 8.67, может
не выполняться, если некоторые нз многочленов fi (х) имеют кратные корни.
?
Для операции умножения последовательностей можно получить аналог теоремы
8.61. По понятным причинам мы не будем рассматривать последовательностей,
в которых все члены, кроме конечного числа, равны 0.
8.70. Теорема. Пусть Oi, i = 1, 2, ..., /t, - периодические
последовательности над полем с бесконечным числом ненулевых членов. Пусть
минимальный период последовательности равен r-t, Если числа гх, ..., rh
попарно взаимно просты, то минимальный период произведения о{ ... oh
равняется гх ... г*.
Доказательство. Ограничимся рассмотрением случая h = 2, так как общий
случай легко получается индукцией по h. Как и в доказательстве теоремы
8.61, нетрудно показать, что минимальный период г последовательности
должен иметь вид г -- dYd%, где dx - делитель числа rlf a d% - делитель
числа г2¦ В частности, dxr2 является периодом последовательности Таким
образом, если ах -это последовательность s0, st,..., а сг2 -
последовательность t0, ti, .... то равенство
d^r^n " 5n j_ dxrJ>n-\-dxr% ~ Stttri
выполняется для всех достаточно больших п. Так как существует целое число
b, такое, что tn ф 0 для всех достаточно больших п не b (mod г2), то для
таких п получаем sn±dlr2 = Зафиксируем теперь достаточно большое п. По
китайской теореме об остатках можно выбрать такое целое число т ф п, для
которого т = п (mod и т = b (mod г2). Тогда
Sn ~ 5//j - Sm+rf^^ =- Sn+tfjrat
и, таким образом, dxr2 является периодом последовательности
Следовательно, гх делит dxr2, а в силу того, что гх н г2 взаимно просты,
гг делит dx, откуда следует, что dx = гх. Аналогично доказывается
равенство d2 - r2. ?
Операцию умножения последовательностей можно использо-вать для описания
соотношений между однородными линейными рекуррентными
последовательностями, характеристические многочлены которых являются
степенями друг друга. Рассмотрим слу-Чай линейных характеристических
многочленов.
8.71. Лемма. Если с ? с Ф 0, a k - целое положитель-н°е число, то
546
Гл, 8. Линейные рекуррентные последовательности
*<'
Доказательство. Пусть последовательность s0, sit ... ле; в 5(х - с)} а
последовательность 4" лежит в S ((х - 1)
