Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 103
Текст из файла (страница 103)
0(рз')), Например, если и(х) представляет собой полипом из (22), последовательные значении с для 1 = О, 1, 2, ... оказываютсв равными 10.63, 12.42, 6.85, 6.64, 6.65, 6.6228, 6.62246, 6.62246, ..., В этом примере р ж .90982. Заметьте, что сходимость не монотонна. В конечном итоге в(х) сходится к одночлену х"', где пт — количество корней с [ау[ < 1, в предположении, что [пб[ ф 1 для всех /; в общем, если имеется Л корней с [а [ = 1, коэффициенты при х и х + не достигнут нуля, в то время как это произойдет с коэффициентами прн высших и низших степенях х.
Известная формула Дженсена [Асса МаГЛ. 22 (1899), 359-364) доказывает, что М(и) является геометрическим средним [и(х)[ в единичном круге, а именно— ехР( — ' )е 1п[/(ет ) [ 4В). В упр. 21, (а) будет аналогично показано, что ЦиЦ являетстт средним квадратичным [и(х)[ в единичном круге. Неравенство М(и) < ЦиЦ, жтсходящее к Э. Ландау (Е. Ьалс1ап) [ВиЛЛ Яос. МаГЛ.
т(е 1тгавсе 33 (1905), 2о1-261), может поэтому трактоваться как соотношение между средними значениями. Число М(и) часто называется мерой Махлера полннома, потому что Курт Махлер (Кшс МаЫет) использовал его в МасЛешас/Ла 7 (1960), 98-100. Дженсен также доказал, что — ' /~ е' е)п[/(етт)[тИ= — ~„". та; /(2атщах([ау[,1)т ) пРи та > О. 21. (а) Коэффициент при авбчс т(т равен нулю с обеих сторон, кроме случая р+в = 0+ г. Когда это условие выполняется, коэффициент справа равен (р + в)1; слева он составляет (, ) ( .) т1! г'. = ( ) с1! г! ж (т1+ г)! . [В, Веапзашу апб 3. 1148ог, Тпшэ, Ашег. МагЛ.
Яос. 346 (1995), 2607-2619; П. Хе11Ьегбег, АММ 101 (1994), 894-896.] (Ь) Пусть ар — — сю Ь = тгч, с = 9, т(, = От,. Тогда правая сторона (а) равна В(и), а левая сторона представляет собой сумму неотрицательных членов для каждого Ц и 1с. Если рассмотреть только члены, где ЕЦ является степенью о, члены ор/(р — ))! исчезнут, за исключением р = 1. Эти члены свсщятся к —,]е1тгь)1!Ы[ = В(о)В(ти). „„1!Ы [В. Веапхашу, Е. ВотМеп', Р. Епбо, апб Н. Моптбошегу, Х !т!пшбег ТЛеогу 36 (1990), 219-245.) (с) Добавление новой переменной при необходимости достичь однородности не меняет соотношения и ы сит.
Таким образом, если о и ит имеют общие степени гл и а соответственно, получаем (от+ а)! [и]т > тп! [г]~ а! [та]~; другими словами, [о][ит] < (~+") ~~~[и!. Существует адин изящный способ рассмотрения нормы Бомбьери, заключающийся в точ, чтобы представить, что переменные некоммутатнвпы. Например, вместо Зхрэ — хтид мОжнО заштсать ЗхРРР+Зухуу+ЗРРхР+4999х — еххтгю — бхюхы — бхыых — еитххы-бюхых т т 1еититхх. Тогда норма Бомбьери будет представлять собой норму Ц Ц новых коэффициентов. Другой интересной формулой для однородного полинома и степени а является [и) = — / / е *т "' *' "' ' "' [и(к+ту)[ тйст(у.
(т1) Случай с одной переменной соответствует 1 = 2. Предположим, что и = ию, где ив однородный патином степени тл от 1 переменных. Тогда [сь[~ Ы/та! < [в)т для всех 1с и Ы > (тл/Г)!т, поскольку 1об Г(х) выпукла при х > 0; поэтому [от,[т < та! [г]т/(ат/Ф)!т. Можно положить, что тл! [о]~/(та/1)!' < ш'! [ю]~/(тл'/1) !', где та = и — та — степень ит.
Тогда [сь[ < та! [е] /(пт/1)! < ш! та! 1 [о][ы]/(пт/1)!м (та/170 < и'. т [и]/(а/21)!т, (Лучшая грань получится, если максимизировать предпоследнее выражение по всем степеням гл для каждого неисключенного множителя.) Величина и!ъ~~/(и/21)Р~ъ равна съ(21)"~'и 1ъ' ъ1~э(1+0(а)), где сь =2ъ~ая <ъ' '>гэРгь ( 1.004 приъ= 2), в Заметьте, что существование непроходимого множителя с такими малыми коэффициентами здесь не доказывалось; может потребоваться дальнейшее разложение (см. упр. 41).
(е) [и[ъ = 2' ,(")ъ/[ъ") = 2 „(ь)(ъ„"~~э)/(ъ„") 4"/[ъ„") = ъ/япп+ 0(п ъг ). если е(х) = (х — 1)" и ъг(х) = (х+ 1)", имеем [е) = [ю[ = 2"; следовательно, неравенство (с) становится в этом случае равенством. (1) Пусть к и э — однородные полиномы степени гп и и. Тогда согласно неравенству Коши, [В. Веапзашу, Х Яуглбобс Сошр. 13 (1992), 465-472, Ргоров! Вов 5,) (5) В соответствии с упр. 20 (ъ„~ъ,) М(и) < [~„7ъ~) '[[н[[' = [1 д~) '2 ъ ["3[ [в) = Еу (ъб) [ву[ < ~"1 [".)М(в) = 2" М(п)ъ, Первое неравенство следует также из п (1)' если п(х) = " П,"= (х -аз), имеем [в[ъ < [на [э [ [,"., [х -аз[ ъ = [ни [ъ д,", (1+ [ну [э) < [в [ъ[[, ,(2 шах(1,[п~[)') = 2"М(в)'.
22, Рассмотрим более обпбю ситуацию. Предположим, что в(х) ш «(х)ш(х)шойе, а(х) е(х). + Ь(х)ш(х) ш 1 пъойр, и с6(г) ш 1 апой г, йеб(а) < йеб(ы), йеб(Ь) < йеб(э), йеб(и) = йеб(э) + йеб(ш)„где г = бей(р,9) и р, е не обязательно должны быть простыми чисвами, Построим полиномы И(х) и э(х) и И'(х) ш ш(х) пъос1 о такие, что и(х) ш И(х) И'(х) шой 4г, г(г) = г(е), йеб(И) = йеб(е), йеб(И') = йеб(ье). Кроме того, если г — простое число, результат по модулю дт окажется единственным.
В задаче спрашивается, как найти 6(х) и й(х), такие, что И(х) = э(х) + 96(х), И~(х) = ш(х) + 9г6(х), йеб(6) < йеб(е), йеб(Ю) < йеб(ьэ); другое условие, ( '(х) +66(х))(ъе(х) +9й(х)) ш в(х) пюй 6г, эквивалентно Ф(х)е(х) + 6(х)ьг(х) ш /(х) шой г, где /(х) удовлетворяет ссютношению и(х) ш э(х)ш(х) +6/(х) шойдг. Дчя всех 1(х) имеем (а(х)/(х)+1(х)ш(х))и(х)+ (Ь(х)У(х) — 1(х)и(х))ш(х) ш /(х) той г.
Поскольку для 6(е) существует обратный элемент по модулю г, можно с помощью алгоритма 4.0.1Р найти частное 1(х), такое, что йеб(Ь/ — ьв) < йеб(е); для этого 1(х), йеб(а/+ Фш) < йеб(ье), поскольку имеем йеб(/) < йеб(к) = йеб(е) + йеб(ье).
Таким образом, искомое решение — 6(х) = Ь(х)/(х) — Ф(х)г(х) = Ь(х)/(х) пъойэ(х), ъэ(х) = а(х)/(х) + Ф(х) ъе(х). Если (5(х), ъй(х)) представляет собой другое решение, имеем (ъ6(х) — й(х))е(х) ш (д(х) — о(х))ш(х) ъпойг. Следовательно, если г — простое число, и(х) должно делить э(х) -6(х),но йеб(5- 6) < йеб(э), так что 6(х) = 6(х) н в(х) = в(х). Если р делит 9, так что г = р, выбор И(х) и Иг(х) удовлетворяет также соотношению а(х) И(х) + Ь(х) Иг(х) ш 1 (по модулю р), что и требуется по лемме Хенселя. Для р = 2 процесс разложения протекает следующим образом (далее записываются только коэффициенты с надчеркиванием для обозначения отрицательных цифр).
В упр. 10 утверждается, что еъ(х) = (111), ъиъ(х) ы (1110011) в однобнтовой комнлементарноя к 2 записи. Расширенный алгоритм Евклида приводит к а(х) = (100001),Ь(х) = (10). Множитель е(х) = х + с~х+ се должен иметь [съ[ < [1+ ъ/1ГЗ[ = 11, [се[ < 10 согласно упр. 20. Три применения леммы Хенселя дшот еэ(х) ы (131), ыъ(х) = (1354435). Таким образом, съ и 3 н со ш -1 азой 15; единственныб возможный квадратичный множитель и(х) — хе+ Зх -1. Деление ошибочно, поэтому к(х) — неприаоднмый полипом.
(Поскольку "неприводимссть" этого "ненаглядного" полинома доказана четырьмя различными мето. дамм, вряд ли кто-то смохсет найти хоть один его множитель... ) Ганс Зассенхауз (Напэ Еаээепйаээ) обнаружил, что зачастую можно ускорить вычисления, увеличив р так же, как н Ьс если э приведенных выше обозначениях г =р, можно найти А(х), В(х), такие, что А(х)Ь'(х) + В(х)И'(х) ез 1шобрэ, а нменно— взяв А(х) = а(х) + ра(х), В(х) = Ь(х) + рЬ(х), где а(х)И(х) + Ь(х)И'(х) ш 9(х) шос(р, а(х)И(х) + Ь(х)И'(х) ш 1 — рд(х)шобрз.
Также можно найти С с Ь(у)С и 1шобрэ, Так можно свести разложение, свободное от квадратов, п(х) ш э(х)в(х)шобр, к их едннственным расширениям по модулю р, р~, рэ, р'э и т. д. Однако такая "ускоренная" процедура на практике достнгает точки замедления, как только мы достигаем двойной точности, поскольку время для умножения чисел с многократной точностью э реальном диапазоне значений перевешивает преимущества от возведения модулей в квадрат.
С вычислительной точки зрения представляется, что лучше работать с последоаательнымн модулами р, р~, р~, рэ, ..., рх, р~+', рхьы, рхьы,, где Š— наименьшая степень 2 с рх, ббльшим однократной точности, н е — наибольшим целым числом, такнм, что р' имеет однократную точность. "Лемма Хенселя" на самом деле была открыта К. Ф. Гауссом (С. Р. Оапээ) около 1799 года, в черновике неоконченной книги Алв1узш Неэн(погши, 3373 — 374, Гаусс внес большую часть материала нз этой рукописи э свою В(эйивй(олеэ Аг!гйшейсш (1801), но его идеи о разложения полнномов были опубликованы лишь после его смерти (см. Игегйе 2 (Сохбшбеп, 1876), 238].
Имя Хенселя оказалось связанным с методом, потому что он стал основой теории р-ичных чисел (см. упр. 4.1-31). Лемма может быть обобщена несколькими способамн. Во-первых, еслн имеется большее количество множителей, капример к(х) ш ш(х)ээ(х)эз(х)шеар, можно найти аэ(х), аэ(х), аз(х), такие, что а~(х)оэ(х)эз(х) + ат(х)эд(х)эз(х) + аз(х)эа(х)эз(х) ш 1 шобр и бей(а;) < беб(ш). (По существу, 1/и(х) расширяется э отдельных частях до ) а,(х)/в;(х),) Точный аналог построения теперь позволяет провести разложение, не изменяя старшие коэффициенты э~ и эз; мы получаем бь(х) = аз(х)у(х) пюс( ээ(х), бз(х) = ат(х)у(х) шоб эх(х) и т.
д. Другое важное обобщенме состоит э разлнчных одновременных модулях соответствующего вида р',(хэ — аэ)"',.....,,(хэ — а,)"' при выполнении поиска наибольших общих делителей и разложении полиномоа от нескольких переменных. ]См. Р. У. У. 'т'пп, РЬ. 11. Тйеэ)в (М. 1. Т., 1974),] 23. Днскрнмннант рр(и(х)) представляет собой ненулевое целое чнсло (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
