AOP_Tom2 (1021737), страница 211
Текст из файла (страница 211)
Инвариантные соотноп<ения М(и) = сМ(с)<<э и Ц»Ц = 1 гарантируют, что М(и) < с на кая<дом шаге итерации. Заметьте, что, когда с(х) = ое(х ) + хо< (х ), мы имеем 0(х) = оо(х) — хо< (х) . Можно показать, что если каждое ]а, ] < р или > 1/р, то М(и) = ЦиЦ(1 + О(р)); следовательно, с после 1 шагов будет равно М(и)(1+0(рг )). Например, если и(х) представляет собой полинам нз (22), последовательные значения с для с = О, 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-564] доказывает, что М(и) является геометрическим средним [и(х)[ в единичном круге, а именно— ехр( — '1 !и[/(ем)[з10). В упр. 21, (а) будет аналогично показано, что [[и[[ является средним квадратичным [и(х)[ в единичном круге. Неравенства М(и) < []и[[., восходящее к Э. Ландау (Е. Ьапс!аи) [Вирй Вос. МасЬ. с!е Ггапсе ЗЗ (1905), 251 — 261], может поэтому трактоваться как соотношение между средними значениями. Число М(и) часто называется мерой Махлеро полинома, потому что Курт Махлер (Китс МаЫег) использовал его в МаСЬегааййа 7 (1960), 98-100. Дженсен также доказал, что — ' / е' з !и]/(е ~)]с(6 = — 2 т", и /[2тзпах([аз[,1)гм) пРи т > О. 21.
(а) Коэффициент при арбчсгзс, равен нулю с обеих сторон, кроме случая р ~-в = с!+ г. Когда это условие выполняется, коэффициент справа равен (р т в)!; слева он составляет (. ) ( .) ц! г! = ( ) и!г! = (с!+ г)!. 1 [В. Веаизащу апг! 1. Пббос, Тгапз. Ашег. МаСЬ. Вос. 845 (1995), 2601 — 2619; В. ЕейЬегбег, АММ 101 (1994),. 894.896.] (Ь) Пусть ар — — ар, Ьч = юч, с„= О„б(, = ю,. Тогда правая сторона (а) равна В(и), а левая сторона представляет собой сумму неотрицательных членов для каждого 3 и 1с. Если рассмотреть только члены, где ЕЗ является степенью а, члены ар/(р — !)! исчезнут, за исключением р = ЗЬ Эти члены сводятся к —,]азюь3)й![ = В(а)В(ю).
1 .,г зэк [В. Веаихапзу, Е. ВошЬ!еп', Р. Епба, апс! Н. Мопзбопзегу, Х !з!ипзЬег ТЬеогу Зб (1990), 219-245.] (с) Добавление новой переменной при необходимости достичь однородности не меняет соотношения и = аю. Таким образом, если о н ю имеют общие степени т и и соответственно, получаем (т -!- и)! [и] > т! [а] и! [ ]; другими словами, [а][ю] < (юг") Ы [и]. Существует один изящный способ рассмотрения нормы Бомбьери, заключающийся в том, чтобы представить, чта переменные некоммутативны. Например, вместо Зхуз — згюг можно записать -хууу+-ухуу+-ууху+-ууух — -ззюю — -зюзю — -зююх--юззю — -юхюх— з з з з 1, з ! 1 4 4 4 4 б б б б б -'ююзх.
Тогда норма Бомбьери будет представлять собой норму [[ [[ новых коэффициентов. Другой интересной формулой для однородного паливома и степени и является г г „г „г [и]г — / / е *~ ' *~ зз ' ' зз [и(х.! зу)[гзсгзйу (с1) случай с одной переменной соответствует с = 2. предположим, что и = ою, где ив однородный полинам степени т от С переменных. Тогда [аь[г!с!/гп! < [о] для всех й и Ы > (пз/С)!', поскольку!об Г(х) выпукла при х > О; поэтому [оь)г < пз! [а]~/(т/11!'.
Можно положить, что т! [а]~/(гп/!)1~ < т! [ю]~/(тп/С))~, где т = и — т — степенью. Тогда ! [ ]г/ )р < )згг ~)згг [,][ ]/( / )(Ыг( / ))ззг < !Ыг [ ]/( / !з (Лучшая грань получится, если максимизировать предпоследнее выражение по всем степеням тн для каждого неисключенного множителя.) Величина и!стс/(и/21)!ссг равна с (21)ттс и 1гс Игэ(1+0(„-')), где с = 2ттгк Сг' с1тг1стс (ш1.004 прис= 2). Заметьте, что существование неприевдимого множителя с такими малыми коэффициентами здесь не доказывалось; может потребоваться дальнейшее разложение (см. упр. 41). (е) [и]г = 2 „(,")г/(г"] = 2 (г)(г" г")/(г„") = 4"/('„"] = с/Япп+ 0(п 'т').
Если в(х) = (х — 1)" и ис(х) = (х+ 1)", имеем [в] = [ю] = 2"; следовательно, неравенство (с) становится в этом случае равенством. (1) Пусть и и в — однородные полиномы степени тп и и. Тогда г ~ (с т1(иссс -1() ~ /~~- (иг(г (вь-с( ] /~- (1](ь"-г)'] [ ]г[ ]г согласно неравенству Коши. (В. Веаигашу, Х ЯуспЬо/сс Сошр. 13 (1992), 463-412, Ргоровйюп 5.] (6) В соответствии г упр.
20 ( " ) 'М(и) < ( "г ) '((и((г = („„"г,) ' 2 . (из(г < [и] = Ес (т) '(из( < ~, (")М(и) = 2" М(и) . Первое неравенство следует также из и. (Е); если и(х) = и„П" (х-аг), имеем [и] < (и„(г П" [х — а ]г = (и„(г П" (1+(а (г) < (ив( Цг" с(2шах(1,(ст,() ) = 2" М(и)г. 22. Рассмотрим более общую ситуацию. Предположим, что и(х) = в(х)ю(х) шобд, а(х) в(х) + Ь(х)св(х) = 1 шод р, и сс(в) — ш 1 шос1 т, с1еб(а) < с1еб(ю), с1еб(Ь) < с1еб(в), с1еб(и) = с1еб(в) + Йеб(ю), где г = бсс1(р,д) и р,д не обязательно должны быть простыми числами. Построим полиномы (т(х) = в(х) и И'(х) щ ю(х) шос1 д такие, что и(х) ш И(х) И'(х) шос1 дт, 8(Ъ') = 6(в), бей(Ъ') = с1еб(сс), с1ей(Ит) = с1еб(ю).
Кроме того, если т — простое число, результат по модулю дт окажется единственным. В задаче спрашивается, как найти 6(х) и ю(х), такие, что тт(х) = в(х) +д6(х), И (х) = ю(х) + дю(х), с1еб(6) < с1еб(в), с1еб(ю) < с1еб(ю); другое условие, (в(х) Ч- д6(х))(ю(х) + дсв(х)) = и(х) шас1 дт, эквивалентно ю(х)в(х) + 6(х)ю(х) ш /(х) шос1 т, где /(х) удовлетворяет соотношению и(х) с— в в(х)ю(х) + д/(х) шос1 дт Для всех 1(х) имеем (а(г )/(х) + С(х) ю(х))в(х) С- (Ь(х)/(х) — 1(х)в(х))ю(х) ы /(х) шос1 т, Поскольку для 4(в) существует обратный элемент по модулю г, можно с помощью алгоритма 4.6.1В найти частное С(х), такое, что с1еб(Ь/ — Фв) < с1еб(в); для этого С(х), с1еб(а/+ ею) < с1еб(ю), поскольку имеем с1еб(/) < с1еб(и) = с)еб(в) + стеб(ю). Таким образом, искомое решение — 6(х) = Ь(х)/(х) — 1(х)в(х) = Ь(х)У(х) 'пой в(х) ю(х) = а(х)/(х) + 1(х)ю(х).
Если (в(х), ю(х)) представляет собой другое решение, имеем (ю(х) — ю(х))в(х) = (6(х) — 6(х))ю(х) шос1 т. Следовательно, если г — простое число, в(х) должно делить б(х) — 6(х), но бей(в — 6) < с1ей(в), так что в(х) = 6(х) и ю(х) = ю(х). Если р делит д, так что т = р, выбор И(х) и И'(х) удовлетворяет также соотношению а(х) Ст(х) + Ь(х)И'(х) = 1 (по модулю р), что и требуется по лемме Хенселя. Для р = 2 процесс разложения протекает следующим образом (далее записываются только коэффициенты с надчеркиванием для обозначения отрицательных цифр). В упр.
10 утверждается, что вт(х) = (111), юс(х) = (1! 10011) в однобнтовой комплементарной к 2 записи. Расширенный алгоритм Евклида приводит к а(х) = (100001),Ь(х) = (10). Мтсожитссссь в(х) = хг + стх+ се должен иметь (сс( < [1+ с/0133] = 11, !се( < 10 согласно упр. 20. Три применения леммы Хенселя дают вс(х) = (1 3 1), юс(х) = (1 3 5 44 3 5). Таким образом, сс ш 3 и се ш -1 шос116; единственный возможный квадратичный множитель и(х) — хе+ Зх — 1. Деление ошибочно, поэтому и(х) — неприводимый полинам. (Поскольку "неприводизюсть" этого "ненаглядного" полинома доказана четырьмя различными методами, вряд ли кто-то сможет найти хоть один его множитель...
) Ганс Зассенхауз (Нане 2везепЬапе) обнаружил, что зачастую можно ускорить вычисления, увеличив Р так же, как и 9: если в приведенных выше обозначениях г = Р, можно найти А(х), В(х), такие, что А(х)И(х) + В(х)И'(х) гй 1шос1рз, а именно— взяв А(х) = а(х) + ра(х), В(х) = И(х) + РИ(х), где а(х)Ъ'(х) + Ь(х)Ис(х) ш д(х) спос1Р, а(х)И(х) + И(х)И'(х) ш 1 — Рд(х)псос1рз.
Также можно найти С с 4(И)С сй 1гпос1рз. Так можно свести разложение, свободное от квадратов, и(х) = в(х)ш(х) шос1Р, к их единственным расширениям по модулю Р, Р, Р, Р и т. д. Однако такая "ускоренная' з с в се процедура на практике достигает точки замедления, как только мы достигаем двойной точности, поскольку время для умножении чисел с многократной точностью в реальном диапазоне значений перевешивает преимущества от возведения модулей в квадрат. С вычислительной точки зрения представляется, что лучше работать с последовательными моДУлнмн Р' Р Р Р Р с Р Р +, Р, ..., где Š— наименьшае степень 2 с Рх, ббльшим однократной точности, и е — наибольшим целым числом, таким, что р' имеет однократную точность, "Лемма Хенселя" на самом деле была открыта К.
Ф. Гауссом (С. Е. Саная) около 1799 года, в черновике неоконченной книги Апл)уюе Незсс)оогшп, 1373-374. Гаусс внес большую часть материала нз этой рукописи в свою В1здше1гсопее АгйИшейсш (1801), но его идеи о разложении полиномов были опубликованы лишь после его смерти [см.
Исегйе 2 (Соссшйеп, 1876), 238]. Имя Хенселя оказалось связанным с методом, потому что он стал основой теории Р-ичных чисел (см. упр. 4.1-31). Лемма может быть обобщена несколькими способами. Во-первых, если имеется большее количество множителей, например и(х) = вс(х)вз(х)вз(х) шойр, можно найти ас(х), аз(х), аз(х), такие, что ас(х)вз(х)вз(х) + аз(г)вс(х)вз(х) + аз(х)вс(х)вз(х) ш 1 шос1Р и с1ей(а,) ( с1е8(в;). (По существу, 1/к(х) расширяется в отдельных частях до 2 а,(х)/вс(х).) Точный аналог построения теперь позволяет провести разложение, не изменяя старшие коэффициенты сс и вз; мы получаем бс(х) = ас(х)/(х) шос1 ос(х), дз(х) = аз(х)/(х) шос) вз(х) и т. д. Другое важное обобщение состоит в различных одновременных модулях соответствующего вида р', (хз — аз) "з,......, (хс — ас)сч при выполнении поиска наибольших общих делителей и разложении полнномов от нескольких переменных.
(См. О. у. 'зс. "з'пп, РЬ. Р. ТЬезш (М. 1. Т., 1974).( 23. Дискриминант рр(п(х)) представляет собой ненулевое целое чишю (см. упр. 4.6.1-12), н кратные множители по модулю р существуют тогда и только тогда, когда р делит этот днскриминант. (Разложение (22) по модулю 3 равно (х + 1)(х' — х — 1)'(хе + хз — х + 1); квадратные множители для этого полинома имеются талька для р = 3, 23, 233 н 121702457. Нетрудно доказать, что наименьшее простое число, не являющееся "неудачным", не превышает 0(п!обсссп), если и = бей(и), а ссс является гранью по абсолютной величине коэффициентов и(х).( 24.
Умссожьте нормированный полинам с рациональными коэффициентами на подходящее ненулевое целое число для получения примитивного полинома над кольцом целых чисел. Разложите полинам нэд кольцом целых чисел, а затеи конвертируйте множители в нормированные полиномы (таким образом, не будет потеряно ни одно разложение; см. упр. 4.6.1-8). 26. Рассмотрение постоянного члена показывает, что у полинома нет множителей степени 1, так что если полинам приводим, то он должен иметь один множитель степени 2 и один — степени 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
