можно записать просто и(х) = YjUjx. Обратите внимание на обозначение х-*; также обозначаем j! = ji!... jt! и Sj = ji +----\-jt.

a) Докажите тождество

j,k J p,q>0 •>r,s>0

= i! [p--s = i]apd. [q--r = i]6qCr.

i>0 p,»>0 q,r>0

b) Полином u(x) = XjUjx называется однородным полиномом степени n, если каждый член имеет общую степень п. Таким образом, Sj = тг при щ ф 0. Рассмотрим взвешенную сумму коэффициентов В{и) = 5ZjJl*jl- Используя п. (а), покажите, что В{и) > B{v)B{w), если и(х) = i;(x)u;(x) однороден.

c) Норма Бомбьери [и] полинома и(х) определяется как у/В{и)/п\, если и - однородный полином степени тг. Она определена также для неоднородных полиномов посредством добавления новой переменной xt+i и умножения каждого члена на степень xt+i, такую, что и становится однородным без увеличения его максимальной степени. Например, пусть и(х) = + X - 2; соответствующий однородный полином - + ху - 2у и [и]2 = (3!0!4--l!2!l2--0!3!22)/3! = 16 + 1+4. Если u(x, у, 2) = Зху - 2 аналогично получаем [и] = (1! 3! О! О! 3+0! О! 2! 2! 1)/4! = f+ g. Что говорит п. (Ь) о связи между [и], [г;] и [w] при и(х) = v{x)w{x)?

d) Докажите, что если и{х) - приводимый полином степени тг от одной переменной, то он имеет множитель, коэффициенты которого не превышают n\*[uY/{n/4y. по абсолютному значению. Чему равно соответствующее значение для однородных полиномов от t переменных?

e) Вычислите [и] явно и асимптотически при и{х) = {х - 1)".

f) Докажите, что [u][v] > [uv].

g) Покажите, что 2~М(и) < [и] < 2"Л/(и), если и{х)-полином степени тг и М{и) - величина, определенная в упр. 20. (Вследствие этого грань в п. (d) примерно равна квадратному корню грани, полученной в упр. 20.)

► 22. [М24] {Лемма Хенселя.) Пусть и{х), Ve{x), We{x), а{х), b{x) представляют собой полиномы с целыми коэффициентами, удовлетворяющими соотношениям

и{х) = Ve{x)we{x) modp, a{x)ve{x) +b{x)we{x) = 1 modp,

где p - простое число, e > 1, Ve{x) - нормированный полином, deg(a) < deg(u;e), deg(6) < deg(t;e) и deg(u) = deg{ve) + deg{we). Покажите, как вычислить полиномы Ve+i{x) = Ve{x) и We+i{x) = We{x) (по модулю jj), удовлетворяющие тем же условиям с е, увеличенным на 1. Кроме того, докажите, что Ve+i{x) и We+i{x) единственны по модулю р"*".

Используйте свой метод для р = 2 для доказательства того, что (22) неприводим над кольцом целых чисел, начиная с его разложения по модулю 2, найденного в упр. 10. (Заметьте, что расширенный алгоритм Евклида из упр. 4.6.1-3 даст процесс, начинающийся с е = 1.)

23. [НМ23] Пусть и{х) является полиномом с целыми коэффициентами, свободным от квадратов. Докажите, что имеется только конечное число простых чисел р, таких, что этот полином и{х) не является свободным от квадратов по модулю р.

24. [М20] В тексте раздела говорится о разложении над кольцом целых чисел, а не над полем рациональных чисел. Объясните, как найти полное разложение полинома с рациональными коэффициентами над полем рациональных чисел.

25. [М.85] Каково полное разложение полинома над полем рациональных чисел?

26. [20] Пусть dl, ..., dr - степени неприводимых множителей полинома и{х} по модулю р с правильной кратностью, так что di + + dr = п = deg(u). Объясните, как найти множество {deg(w) и{х) = v{x)w(x) modp для некоторых v{x),w{x)}, выполнив 0{г) операций над битовой строкой длины п.

27. [НМЗО] Докажите, что случайный примитивный полином над кольцом целых чисел в некотором определенном смысле "почти всегда" неприводим.

28. [М25] Процедура разложения с различными степенями "удачна" если существует не более одного неприводимого полинома каждой степени d. Тогда gd{x) никогда не должно разбиваться на множители. Чему равна вероятность такой удачной ситуагщи при разложении случайного полинома степени п по модулю р для фиксированного п при р -> оо?

29. [Л/.8.8] Пусть д{х) - произведение двух или более различных неприводимых полиномов степени d по модулю нечетного простого числа р. Докажите, что

gcd{g(x), <(ж)Ср-1)/2 - 1)

будет собственным множителем д{х) с вероятностью > 1/2 - 1/{2р) для любого фиксированного д{х), когда t(x) выбрано случайным образом из р"* полиномов степени < 2d по модулю р.

30. [Л/.85] Докажите, что если q{x) является неприводимым полиномом степени d по модулю р и если t{x) является произвольным полиномом, то значение

{t{x) + t{xY + t{xy + + ЦхУ) modq{x)

представляет собой целое число (т. е. полином степени < 0). Используйте этот факт, чтобы создать рандомизированный алгоритм для разложения gd{x) в виде произведения неприводимых полиномов степени -d аналогично (21) для случая, когда р = 2.

31. [НМЗО] Пусть р - нечетное простое число и пусть d > 1. Покажите, что существует число п(р, d), обладающее следующими двумя свойствами, (i) Для всех целых t в точности п(р, d) неприводимых полиномов q{x) степени d по модулю р удовлетворяют соотношению (ж + t)P->/modq{x) = 1. (ii) Для всех целых чисел О < < *2 < Р в точности п(р, d) неприводимых полиномов q{x) степени d по модулю р удовлетворяют соотношению (x + ii)(p-i)/2modg(x) = {x + t2Yp-)modq{x).

► 32. [МЗО] (Циклотомические полиномы.) Пусть Ф„(ж) = П1<*:<п к±п( ~ t*): где ш = g2jri/n Торда корни Фп(ж) - это п-е комплексные корни единицы, не являющиеся тп-ми корнями при т < п.

a) Докажите, что Фп(ж) - полином с целыми коэффициентами и что

- 1 = 11Щх); Ых) = п( - l)""-

d\n d\n

(.См. упр. 4.5.2-10(b) и 4.5.3-28(с).)

b) Докажите, что полином Фп(ж) неприводим над кольцом целых чисел. Следовательно, предыдущая формула является полным разложением ж" - 1 над кольцом целых чисел. [Указание. Если f{x) является неприводимым множителем Фп(ж) над кольцом целых чисел и если С - комплексное число, для которого f{Q = О, докажите, что /(С) = О для всех простых чисел р, не делящих п. Вам может помочь тот факт, что ж" - 1 свободен от квадратов по модулю р для всех таких простых чисел.]

c) Обсудите вычисление Фп(ж) и протабулируйте значения этой функции для п < 15.

33. [М18] Истинно ли следующее утверждение: если и{х) / О и полное разложение и{х) по модулюр представляет собойр1(ж)*.. .рг(ж), то u{x}/gcd{u{x),u(х)) = pi{x).. .рг(х)? ► 34. [М25] (Разложение, свободное от квадратов.) Ясно, что любой примитивный полином из области единственного разложения может быть выражен в виде

и(х) = Щ(х)и2(х)из(х)...,

где полиномы щ(х) свободны от квадратов и взаимно просты. Такое представление, в котором Uj(x) является произведением всех неприводимых полиномов, делящих и(х) ровно j раз, единственно с точностью до обратимого множителя; это полезный способ представления полиномов, участвующих в умножении, делении и поиске наибольшего общего делителя.

Пусть GCD(u(x),v(x)) представляет собой процедуру, которая вычисляет три значения:

GCD(u(x),v(x)) = (d(x),u(x)/d(x),v(x)/d(x)), где d(x) = gcd(u(x),v(x)).

Метод, описанный в тексте раздела, следующем за формулой (25), всегда заканчивается проверочным делением u(x)/d(x) и v(x)/d(x), которое позволяет убедиться, что не было использовано "неудачное" простое число, так что значения u(x)/d(x) и v(x)/d(x) представляют собой побочные продукты вычисления наибольшего общего делителя, т. е. можно вычислить GCD(u(x),v(x)) с помощью указанного метода так же быстро, как и gcd(u(x), t;(x)).

Придумайте процедуру для получения свободного от квадратов представления (ui(x),U2(x),...) данного примитивного полинома и(х) над кольцом целых чисел. Ваш алгоритм должен выполнять в точности е вычислений GCD, где е - наибольший индекс, для которого Ue(x) Ф 1. К тому же каждое вычисление GCD должно удовлетворять условиям (27), чтобы можно было использовать построение Хенселя.

35. [М22] (Д. Ю. Е. Юнь (D. Y. У. Yun).) Разработайте алгоритм, вычисляющий свободное от квадратов представление (wi(x),W2(x),...) полинома u)(x) = gcd(u(x), w(x)) над кольцом целых чисел по свободным от квадратов представлениям (ui(x),U2(x),...) и (i;i(x),i;2(x),...) полиномов и(х) и v(x).

36. [MS7] Расширьте процедуру упр. 34 так, чтобы получалось свободное от квадратов представление (ui(x), U2(x),...) полинома и(х) с арифметикой коэффициентов, выполняемой по модулю р.

37. [НМ24] (Джордж Э. Коллинз (George Е. Collins).) Пусть di, ..., dr - положительные целые числа, сумма которых равна п, и пусть р - простое число. Чему равна вероятность того, что неприводимые множители случайного полинома степени п с целыми коэффициентами имеют при полном разложении по модулю р степени d\, ..., dr? Покажите, что асимптотически данная вероятность аналогична вероятности того, что случайная перестановка п элементов имеет циклы длины di, ..., dr.

38. [НМ27] (Критерий Перрона.) Пусть и(х) = ж" -Ь u„-ix"~ + •• + uo-полином с целыми коэффициентами, такой, что зд О, и либо u„ i > 1 + и„ 2 + ••-!- ио, либо (un-i = О и Un 2 > 1 -Ь ип-з -Ь • • • -Ь ио). Покажите, что полином и(х) неприводим над кольцом целых чисел. [Указание. Докажите, что почти все корни и меньше 1 по абсолютному значению.]

39. [HM4S] (Дэвид Д. Кантор (David G. Cantor).) Покажите, что если полином и(х) неприводим над кольцом целых чисел, то он имеет "укороченное" доказательство неприводимости в том смысле, что количество битов в доказательстве - это по крайней мере полином от deg(u) и длин коэффициентов. (Здесь требуется граница длины доказательства, как в упр. 4.5.4-17, а не граница времени, необходимого для поиска такого доказательства.) Указание. Если v(x) неприводим и t является любым полиномом над кольцом целых чисел.