Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
то через Т (b) обозначим множество таких элементов у ? Е, что Тг?/Г|( (f
(у)) = ft.
6.58. Лемма. Пусть заданы многочлен f ? FgUl положительной степени,
причем НОД (deg (f), q) 1, расширение Е =
- Fga поля где s ;> 3, и элемент b ? Fg. Пусть М - такое натуральное
число, кратное q, что 0 < М deg (/) < f где k = |_s/2J. Тогда
существует такой ненулевой многочлен h ? fq [х], что каждый элемент у ? Т
(Ь) является корнем кратности не менее М этого многочлена, и при этом
deg (/г) < Мд*~1 + qs deg (/).
Доказательство. Положим g = f?k + н + ... + К"*1* m - deg (/), и пусть т0
- меньшее из чисел т и q. Будем искать многочлен h в виде
h (х) =2 & etj (х) g (х)' х>"\ (6.33)
*=0 /=0
где и ~ M!q н eti - многочлены над Fg, которые требуется определить,
причем deg (eu) < m0?s~"2. Поскольку
s
g(x) = f (*"*) + f (x*k+l) +...+! мы можем написать, что h (х) = v (х,
х<*4), где
о (х, й = Ё 23 М (f (у) + / (у9) I • * • + f у!<!*~к-
(-о /-О
Ввиду того что s С 2k 1, получаем, что М
так что можно применить следствие 6.50 для всех п, 0 <; п <; М -
- 1. Тогда
?l") (h (х)) - ? 23 ei}n (х) g (xY х"\ 0 < n < M - 1,
?=0 /-0
гдеei/n M = EW (eu (*))• Если V € T (ft), TO ft =. Tr?/F< (/ (v)) =
= G (7) 4- g (7), где G - f + ft + ... + /" . Учитывая также,
что y?s = у, получим
(?<"> (ft)) (v) = 2 2 "цп (У) (Ь - С (у))1' у' = (7),
j-0 /=0
384
Гл. 6. Уравнения над конечными полями
ш
где
q- 1 и
гп w = s s еип w ф
i=0 /=0
G(x)Y х*> О
tt -С
jW - 1.
• # :<У.йй?
>уу>.
Для того чтобы гарантировать, что каждый элемент у ? Т ( является корнем
многочлена h кратности не менее М, достаточй в силу леммы 6.51, чтобы
были нулевыми все многочлены r^jf О < п < М - 1. Поскольку и - M(q <
qk~x, то
"2 4~ m (q - 1) 9й'-1
deg (rn) < т0ф
.S-2
ч- m (q - 1) 1
и, еслн я ^ 1, то cleg (rn) < mQqs~~2
г Я
и <>-,
к-t
МцЯ
S-2
/Ж/
&
¦;;-м < ЯЙ
m
сш
: .:т
щ
к
- 1. Таким образш|
если через S обозначить суммарное число коэффициентов всяёШ многочленов
гп, 0 п < М
S < М (m0qs~2 -г
1, то mqk) -< /Ит0^~2
.<*&Л
Я
S-1
(6.
Суммарное же число А возможных коэффициентов всех мжш*х!
членов etj, 0< /* <; q A - q(u |- 1 )rn0q
- 1, о </
.'VI mQq
и, удовлетворяет неравенств
fS--2
/Яй?/
44m0?s"2 -|- qs~l. (6,
' i ".?
fi
tv*
IfV
I
Ws
AS'
Ж
Условие, что все многочлены гп равны 0, приводит к системе из однородных
линейных уравнений от А неизвестных коэффицией тов многочленов ец.
Учитывая (6.34) и (6.35), получаем неравенство S < А, означающее, что
существует нетривиальное решение этой системы; это решение определяет
многочлены etj, не ВСС!| равные нулю. if
Определив таким образом многочлены efj, мы определим много-m член h по
формуле (6.33). Тогда, беря и Mlq и пц < пг, пслу-уз чим, что
' > л .
cleg (h) < mQqs~2 m (q - 1) qs~l | uqs < Mqs~l 4- mqs.
I. 9A
. i ' k ¦41
^ \i-A
Ш
w
'Jh
Остается лишь проверить, что h Ф 0. Это вытекает из того, что ненулевые
слагаемые
<I"W - e,j(x)g(xy xi^
многочлена h имеют различные степени. Действительно,
deg {(tv) = deg (eti) + imq$~] + jq\ так что для dtj Ф 0
• qs~' (im + jq) < deg (du) < qs~l A
Ш
qs~~) ({m jq}}
поскольку deg (еи) < m0qs~~2 •< qs~l. Поэтому для того, доказать, что
степени ненулевых многочленов dtJ достаточно показать, что если (i, /) Ф
{i\ jf), где 0 ^ i, I
0 < /, f < м, то im + iq Ф i'm + АЯ- Допустим, ч
m
а
I
§ 4. Метод Степанова-Шмидта
385
/га + jq - i'm + /'<?. Тогда im = i'm (mod <7), и так как по
предположению НОД (га, q) = 1, то i = i' (mod q)t откуда следует, что ( -
i* и / = /', а это невозможно. ?
На основе леммы 6.58 мы можем теперь найти предварительную оценку числа N
(b) - \ Т (Ь) |, т. е. числа элементов у ? ?, удовлетворяющих условию
Тг^?^ (f (у)) = Ь. Позднее этот результат будет улучшен (см. теорему
6.61). Но и той оценки, которую мы сейчас получим, будет вполне
достаточно для доказательства нашего второго главного результата,
приводимого ниже в теореме 6.60,
6.59. Теорема. Пусть f ? [лг] - многочлен степени п ^ 1, причем НОД (n,
q) = 1. Тогда для любого конечного расширения Е = поля р^ число N (Ь)
элементов у ? ?, для которых Тг?/т? (/(?)) - удовлетворяет неравенству
| Л/ (6) - gs~l | < 2л2<7(*/2)+4 для любых b ? р^. (6.36)
Доказательство. Если q* < n2q*, то тривиальная оценка 0 < N (Ь) qs
показывает, что неравенство (6.36) выполняется. Таким образом, можно
считать, что qs^n2q4. Если k = {s/2}, как в лемме 6.58 (где [tj -
наибольшее целое, не превосходящее
/), то
так что число
м=L4- ^ J я
является положительным кратным числа q. Ясно, что Мп <' q5~k~\, так что
все условия леммы 6.58 выполнены. Для многочлена к Ф 0, построенного в
этой лемме, по теореме 1.66 выполняется неравенство N (b) М < deg (/г), и
оценка степени deg (/г), указанная в лемме 6.58, дает
N (Ь) < q<-' + .
Так как
то
N (b) < qs~l -f 2n2qk+l для всех Ь ? р9.
Поэтому
N (b) - qs- 2 N (с) > Я5 ~~ (Я - 0 qs~] - 2 (q - 1) я2 qk+x >
С?ГЯ
еФЬ
> qs~~v - 2n2qk+2t 25 Зак. 222
386
Гл. 6. Уравнения над конечными полями
