Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 31
Текст из файла (страница 31)
[ВМ33] Если п(х) = а~х" + - + по является некоторым полиномом нед полем комплексных чисел, обозначим [[и[! = ([о„[з+ + ]во]з) Г . а) Пусть а(х) = (х - п)ю(х) и о(х) = (бх — 1)щ(х), где о — произвольное комплексное число, а а — сопряженное ему. Докажите, что [[и]! = [[о[!. Ь) Пусть и (х — о~)... (х — а„) представляет собой полное разложение и(х) иад полем комплексных чисел. Введем обозначение М(и) = [к„! [[У шак(1, ]аз !).
Докажите, что М(и) < []и[!. с) Покажите., что [и ! < [ьу') М(и) + [2 ~) [и„! для 0 < 1 < и. Й) Объедините эти результаты для докэзательсзва того, что если и(х) = о(х)ю(х) и п(х) = е,х + ° + ое, где и, о, ю имеют целые коэффициенты, то коэффициенты о ограничены следующим образокс [о, ! < [™, ') [[в[]+ [,:,') ! "!. 21. [НМЮЙ] Продолжая упр.
20, выведем полезные границы коэффициентов палииомов ощ многих переменных нвд кольцом целых чисел. Для удобства будем использовать полужирные символы, чтощя обозначить последовательности из $ целых чисел. Таким образом, вместо записи в(х~ " х ) = ~: вд 1*[' " х[' й -"д можно записать просто и(х) = 2 „изх". Обратите внимание на обозначение х1; также обозначаем 3! =/1!...р! и Ез =/1 +. +за а) Докажите тождество 1 р!ц! г! э! — ~> [р —,)=с! — ЦарЬ, ~ [г — з=е — )с]с 4 зь "' 'еч>о ")! лэ>О ж ) Е ~~~ [р+е=Цард, ~ [ц+гж1]Ьчст.
а >о ива р.*>о полинам и(х) = 2 . и!к! называется ооиородимм полнномом степени и, если каждый член имеет общую степень и. Такпм образом, Ез = и при из ЭЬ О, Рассмотрим взвешенную сумму коэффициентов В(и) = 2 3)[из[э. Используя п, (а), покажите, что В(и) > В(и) В(ш), если и(х) = о(х)ш(х) однороден. Норма Бомбьери [и] полинома и(х) определяется как ь/В(и)/и!, если и — однородный полинам степени и. Она определена также для неоднородных полиномов посредством добавления новой переменной хс ы и умножения каждого члена на степень х~ем такую, что и становится однородным без увеличения его максимальной степени.
Например, пусть и(х) = 4х" + х — 2; соответствующий однородный полинам — 4хз + хрз — 2рз и [и]~ = (3!О!4 +1!2!1 +О!3!2 )/3! = 16+1+4. Если и(х р х) = Зхрз — хз, аналогично получаем [и]~ = (1!3!О!О!3 +О!О!2!2! 1з)/4! = 1э+3. Что говорити. (Ь) о связи между [и], [е] н [ш] при и(х) = а(х) ш(х)? Докажите, что если и(х) — приводимый полинам степени и от одной переменной, то он имеет множитель, коэффициенты которого не превышают п!'М[и]'~ /(и/4)! по абсолютному значению.
Чему равна соответствующее значение для однородных полиномов от ! переменных? Вычислите [и] явно и аснмптотически при и(х) = (х~ — 1)". Докажите, что [и][е] > [ио]. Покажите, что 2 "~>М(и) < [и] < 2"~зМ(и), если и(х) — полинам степени и и М(и)— величина„определенная в упр. 20. (Вследствие этого грань в п. (6) примерно равна квадратному корню грани, полученной в упр.
20.) [М24] (Лемма Хеисслл.) Пусть и(х), о,(х), ш,(х), о(х), Ь(х) представляют собой номы с целыми коэффициентами, удовлетворяющими соотношениям с) е) () 6) ° 22. поли и(х) = лс(х)шл(х) шод р . о(х)сл(х) + Ь(х)ше(х) щ 1 шойр где р — простое число, е > 1, е,(х) — нормированный поливом, с(еб(а) < бей(ш,), Йеб(Ь) < бей(гч) и с(еб(и) = дек(щ) + боб(ш,). Покажите, как вычислить полиномы оым(х) щ а.
(х) и все(х) щ шл(х) (по модулю р'), удовлетворяющие тем же условиям с с, увеличенным па 1. Кроме того, докажите, что ил.ль(х) и ш,е1(х) единственны по модулю р'е . Используйте свой метод для р = 2 для доказательства того, чта (22) неприводнм нал кольцом целмх чисел, начиная с его разложения по модулю 2, найденного в упр. 10. (Заметьте, что расширенный алгоритм Евклида из упр. 4.6.1-3 даст процесс, начинающийся с е = 1 ) 23. [НМ28] Пусть и(х) является полнномом с целыыи коэффициентами, свободным от квадратов. Докажите, что имеется только конечное число простых чисел р, таких, что этот полинам и(х) не является свободным от квадратов по модулю р, 24. [М20] В тексте раздела говорится о разложении над кольцом целых чисел, а не над полем рационельнык чисел.
Обьясните, как найти полное разложение полинома с рациональными коэффициентами над полем ращюнальнык чисел. 25. (М25] Каково полное разложение полннома х~+х~+к~+к+2 над полем рациональных чисел? 26. (80] Пусть йп ..., 5„— степени непривадимых множителей полинома и(х) по модулю р с правильной кратностью, так что 51 + . + е(, = и = йеб(и). Объясните, как найти мяожество (Йеб(а) ( и(х) ьз а(х)ю(х) шодр для некоторых а(х),ю(х)), выполнив О(г) операций над битовой строкой длины и. 27. [НМЮО) Докажите, что случайный цримнтивный полинам над кольцом целых чисел в некотором определенном смысле»почти всегда" непривадим. 26, (М25] Процедура разложения с различными степенями "удачна", если существует не более одного неприводимого полинома каждой степени 5. Тогда Оз(х) никогда не до,чжно разбиваться на множители.
Чему равна вероятность такой удачной ситуации при разложении случайнога полинома степени и по модулю р для фиксированного и при р -э оо? 29. (М22] Пусть О(х) — произведение двух илн более различных неприводнмых полиномов степени 5 по модулю нечетного простого числа р. Докажите, что йод(О(х), Г(х)Ф -'>Г' — 1) будет собственным множителем д(х) с вероятностью > 1/2 — 1/(2р") для любого фиксированного О(х), когда 1(х) выбрано случайным образом из рэ» палиногхов степени < 2е1 по модулю р.
30. [МЯ5] Докажите, что если о(х) является неприводнмым полинаыом степени 5 па модулю р н если Г(х) является произвольным полнномом, то значение (1(х)+1(х) +1(х)г'+" +1(х)"-') 00(х) представляет собой целое число (т. е. полинам степени < О). Используйте этот факт„ чтобы создать раидомнзнрованный алгоритм для разложения Оа(х) в виде произведения неприводимых полиномов степени -Н аналогично (21) для случая, когда р = 2. 31. (ИЮО] Пусть р — нечетное простое чисто и пусть Н > 1.
Покажите, что существует число п(р, 5), обладающее следующими двумя свойствами. (1) Для всех целых 1 в точности п(р, и) непривадимых полиномов о(х) степени е( па модулю р удовлетворяют соотношению (х + 1)Ф пгэ шаг(а(х) = 1. (0) для всех целых чисел 0 < 11 < 1э < р в точности п(р, П) неприаодкмых полиномов о(х) степени 5 по модулю р удовлетворяют соотношению (х+И)Ф и?эшобо(х) =(х+гэ)1» -и?эшобй(х).
ь 32. (М50] (1(иилогломичесиие палиномм.) ПУсгь Ф„(х) = П1<ь<»,их»(х ы ') где ы = е П". Тогда корни Ф„(х).--это и-е комплексные корни единицы, не являющиеся т-ми корнями при ш < п. а) Докажите, чта Ф„(х) — полинам с целыми коэффициентами и что » 1 П 1 щ» е1» (См. упр. 4.5.2-10(Ь) и 4.5.3-28(с).) Ь) Докажите, что полинам Ф (х) неприводим нэд кольцом целых чисел. Следовательно, предыду1дая формула является полным разложением х" — 1 над кольцом целых чисел. [Указание. Если г(х) является непрнводимым множителем Ф„(х) нэд кольцом целых чисел и если ( — комплексное число, для которого уЯ = О, докажите, что г(~г) = 0 лля всех простых чисел р, не делящих и.
Вам может помочь тот факт, что х" — 1 свободен ат квадратов па модулю р для всех таких простых чисел.) с) Обсудите вычисление Ф (х) н протабулируйте значения этой функции для и < 15. 33. [м12! истинно ли следующее утверждение: если и(х) эе О и полное разложение и(х) по модулюрпредставляет собой р, (х)"...
р,(х)"", то и(х)/бег((и(х), и (х)) = рз(х)...р,(х)? ь 34. [М25] (Разлохсеиие, свободное ош каш(ратае.) Ясно, что любой примитивный полипом из области единственного разложения может быть выражен в виде и(х) = и1(х)из(х) иэ(х) ..., где полииомы и,(х) свободны от квадратов и взаимно просты. Такое представление, в котором и,(х) является произведением всех неприводнмых поликанов, делящих и(х) ровно у раэ, единственно с точностью до обратимого множителя; это полезный способ представления полнномов, участвующих в умножении, делении и поиске наибольшего общего делителя.
Пусть ССП(и(х), а(х)) представляет собой процедуру, которая вычисляет трн значения: ССП(и(х), о(х)) = (И(х), и(х)/а1(х), и(х)/И(х)), где г((х) = бса(и(х), о(х)). Метод, описанный в тексте раздела, глелуюшем за формулой (25), всегда заканчивается проверочным делением и(х)/5(х) и о(х)/с((х), которое позволяет убедиться, что не было использовано "неудачное' простое число, так что значения и(х)/г((х) и и(х)/4х) представляют собой побочные продукты вычисления нанболыпего общего делителя, т. е. мшкно вычислить ССП(и(х), о(х)) с помощью укаэанного метода так же быстро, как и бса(и(х), а(х)).
Придумайте процедуру для получения свободного от квадратов представления (и,(х),из(х),...) данного примитивного полинома и(х) иад кольцом целых чисел. Ваш алгоритм должен выполнять в точности е вычислений СС11, где е — наибольший индекс, для которого и,(х);е 1. К тому же каждое вычисление ССП должно уловлетворять условиям (27), чтобы можно было использовать построение Хенселя.
35. [М22) (Д. Ю. Е. Юнь (П. 'з'. з". )/ап).) Разработайте алгоритм, вычисляющий свободное от квадратов представление (ю,(х), юз(х),...) полинома ш(х) = бег)(и(х),е(х)) нвд кольцом пелых чисел по свободным ок квадратов представлениям (и1(х),из(х),...) н (о1(х),оз(х),...) полиномов и(х) и и(х). 36, [М27) Расширьте процедуру упр. 34 так, чтобы получалось свободное от квадратов представление (и1(х), из(х),...) полииома и(х) с арифметикой коэффициентов, выполняемой по модулю р. 37.
[НМ24[ (Джордж Э. Коллинз (Сеогбе Е. Со!!!пз).) Пусть Им ..., 5, — положительные целые числа, сумма которых равна н, и пусть р — простое число. Чему равна вероятность того, что иеприводимые множители случайного полинома степени и с целымн коэффициентами имеют при полном разложении по модулю р степени 5м ..., г!? Покажите, что эснмптотнчески данная вероятность аналогична вероятности того, что случайная перестановка гг элементов имеет циклы длины А, ..., 5 . 38. [НМ27) (Критерий Перрона.) Пусть и(х) = х" + и„1х" ' + .
+ ио — полинам с целыми коэффициентами, такой, что ио ф О, и либо [и 1[ ) 1+ [и,-з[+ . + [ио[, либо (и . 1 = О и и„-з > 1+ [и -э[+ . + [ио[), Покажите, что полинам и(х) иеприводим над кольцом целых чисел. [Указание. Докажите, что почти все корим и меньше 1 по абсолютному значению.'; 39. [НМ42) (Дэвид Д. Кантор (ПатЫ 6, Сапсог),) Покажите, что если полинам и(х) неприводим над кольцом целых чисел, то он имеет "укороченное" доказательство неприводимости в том смысле, что количество битов в доказательстве — это по крайней мере полинам от беб(и) и длин коэффициентов.
(Здесь требуется граница длины доказательства, как в упр. 4.5.4-1 7, а не граница времени, необходимого для поиска такого доказательства.) Указание. Если о(х) неприводим и г является любым полнномом над кольцом целых чисел, то все множители е(1(х)) имеют степень > деб(о). Критерий Перрона дает болыпой запас непрнводимых полиномов о(г). ь 40. [МЯ0) (П.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
