Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
В (*) С (*) -j- В (x) D (x).
%
:1 * :•$
Тем самым мы показали, что множество всех формальн степенных рядов над fg
с введенными там операциями сложе и умножения становится коммутативным
кольцом с единиц Это кольцо называется кольцом формальных степенных ря
надполем F9 и обозначается через F* [[*]]¦ Кольцо многочле F?U] является
подкольцом кольца F* [[*]]¦ Более силь утверждение содержится в следующей
теореме.
8.36. Теорема. Кольцо F<? llx]] формальных степенных р над полем fq
является областью целостности, которая содерМ кольцо многочленов F<? [х]
в качестве подкольцо.
Доказательство. Остается проверить, что F9 f[x]j не сод жит делителей
нуля, т. е. что произведение двух элементов коль| F* ГМ1 равняется нулю
тогда и только тогда, когда один
• Щ
&
щ
§ 3. Производящие функции 519
сомножителей равен нулю. Предположим противное, Пусть В (х) С (л-) - 0, и
при этом
СЮ
В (х) - S ЬпХп Ф о, С (X) - СпХП Ф О
П-О п-0
лежат в |[х]]. Пусть k - наименьшее натуральное число, для которого bk Ф
0, а т - наименьшее натуральное число, для которого ст Ф 0. Тогда
коэффициент при хк^т в произведении В (х) С (х) равняется bkcm Ф 0. а это
противоречит тому, что В (х) С (х) 0. ?
Для приложений нам понадобится выяснить, какие из элементов кольца (F^
[[х]] обратимы относительно операции умножения* т, е. для каких элементов
В (х) ? Fg [[x]J найдутся соответствующие элементы С (х) ? Fg [[x]J,
такие, что В (х) С (х) - 1. Обратимые степенные ряды можно легко
охарактеризовать.
8.37, Теорема. Формальный степенной ряд
о(c)
В (х) •= 2 Ьпх" 6 F" [[а:]]
П =0
имеет обратный относительно операции умножения элемент тогда и только
тогда, когда Ф 0.
Доказательство. Если
оо
С(ДГ)= S W1
п - 0
- такой элемент из Fg [[х]|, что В (х) С (х) s? ], то коэффициенты bQt bu
... и с0, о, ... должны удовлетворять следующей бесконечной системе
уравнений:
Ь{?о = 1" b^Ci н- Ьгс0 0,
t ЬlC\ j- Ь%Со - 0,
bffin -j- bxcn_x f ! bnc0 - 0*
Из первого уравнения мы получаем, что обязательно Ф 0.
и этом если это условие удовлетворяется, то однозначно определяется из
первого уравнения. Переходя ко второму уравнению, видим, что теперь можно
однозначно определить с,. В общем все коэффициенты с0, си ... можно
рекурсивно определить из первого уравнения и рекуррентного соотношения
'• rt.
520
Гл. 8, Линейные рекуррентные последовательности
V
•Гг?
•Т
Получившийся формальный степенной ряд С (х) является иым к В fxi
относительно операции умножения формальных пенных рядов.
Таким образом, если для В (х) ? F? [[х]) существует о ратный элемент
относительно операции умножения формальн степенных рядов, то этот элемент
определен однозначно. Обоз чим его через MB (х). Произведение А (х) (1/В
(х)), где А (
€ [[дг]i, будет обычно записываться в виде И (х)/В (х). Так к!
F? If*)] - область целостности, то для указанных выше вы жеинй
справедливы обычные правила оперирования с дробя Элемент, обратный к
элементу В (х) относительно умножен^ или выражение А (х)/В (х) можно
вычислить с помощью ал| ритма, приведенного при доказательстве теоремы
8.37. Д| подобных вычислений применимо также и обычное деление угл
8.38. Пример. Пусть многочлен В (х) - 3 + х + х2 расе гривается как
формальный степенной ряд над полем Р5. По т реме 8.37 В (х) обратим
относительно операции умножения мальных степенных рядов. Вычислим MB (х)
с помощью алгорит делення углом: ¦*
34-х4-х2
14-0- х+0 ¦ ха4-0 ¦ х34-0 ¦ х*4-0 ¦ - дг*,..
-I-2х-2ха
Зх4-Зха4-0 ¦ х3
2-f-x4-4xs-f-2x4+...
-Зх- х
2.
2х34-4х34~0 ¦ х4
2ха-4х:| - 4х4
х4+0х5+0х
fi
Таким образом, мы получили, что
1
Л
* V!
3 -j- х 4" х'
2 4 х j 4х2 4" 2х* j
8,39. Пример. Вычислим А (хУВ fx) ? F2 1[*1L вде
00
.4 (х) - I -• х г х3 •{ х3 4~ ,..
И ! ¦Хп,
п=О
: л.
а В (х) 1 -1- х -г -V3 Используя алгоритм деления углом, оп
ская члены с нулевыми коэффициентами и учитывая то, что поле (р..
выполняется равенство -1 ~ -И. получаем
1 - X { X2 -x34-x44-xfi 4
\^х -X3
14-Х4-Х3
> •
X2
л
X4 7"Х
4-х
ь
14-х2 4-х3 4-*5-f ¦ ¦¦
В
Х^-Х*
+хе
+х"
х74--хЧ-х94~х10
. •/.
* ¦*,.
• V*
(
• и
4s
4
• Л'
§ 3. Производящие функции 521
Таким образом*
1+?+?*.±4± = l+ ^-|-jc" + r7+,.. .
1 -f х + * * 1
Для применения теории формальных степенных рядов рассмотрим теперь
однородную линейную последовательность k-го порядка So, s,, ... над полем
fg, удовлетворяющую линейному рекуррентному соотношению (8.7). Назовем
многочлен
(* (х) = 1 - ah_tx - ak^x2 - * * * - a^xk ? fq {x] (8.14)
возвратным характеристическим многочленом l) этой последовательности.
Характеристический многочлен / (лг) и возвратный характеристический
многочлен /* (х) связаны,между собой соотношением /* (х) =? xkf (1/х).
Можно показать, что для производящих функций справедливо следующее
фундаментальное равенство.
8.40. Теорема. Пусть s,)y ... - однородная линейная рекуррентная
последовательность k-го порядка над полем Fg, удовлетворяющая линейному
рекуррентному соотношению (8.7). Пусть /* (х) б Fg fx] - возвратный
