AOP_Tom2 (1021737), страница 213
Текст из файла (страница 213)
и ел(х) = и[(х) иьы(х)и+э(х)...+2и,(х)исы(х)и~э(х)...+Зи;(х)и~ь1(х)и +е(х)...+ . Имеем 1(х) 3. ю1(х), поскольку непрнводимый множитель и;(х) делит все, кроме з-го, члены ю1(х) и является взаимно простым по отношению к этому члену. Ясно и то, что и,(х) 3 емм(х). [Хотя в упр.
2, (Ь) доказывается, что большинство полиномов свободно от квадратов, на практике часто встречаются полиномы "с квадратами", следовательно, этот метод становится весьма важным. Предложения по его усовершенствованию приводятся в Рап! 8. %апй апб Вэггу М. Тгайег, НСОМР 8 (1979), 300-305. Разложение по модулю р, свободное от квадратов, рассматривается также н ВасЬ апб 8ЬаП(Ь А(догййш1с 74шлбег ТЬеогу 1 (М1Т Ргещ, 1996), ответ к упр. 7.27.] 35. Имеем ш,(х) = 8сд(иэ(х),ег(х)) 8сй(и,+,(х),е,(х)), где и„(х) = и,(х)изч1(х)... и ь;(х) = ег(х)е1~ь1(х) .. [Юнь отмечает, что время работы свободного от квадратов разложения по метолу упр.
34 не более чем в два раза превышает время вычисления боб(и(х), и'(х)). Кроме того, если дан произвольный метод свободного от квадратов разложения, метод из этого упражнения приводит к процедуре поиска наибольшего общего делителя. (В случае, когда и(х) и а(х) свободны от квадратов, их наибольший общий делитель просто равен юз(х), где ю(х) = и(х)а(х) = ин(х)юз(х); все полиномы из(х), а!(х), и'(х) и а'(х) свободны от квадратов.) Следовательно, задача преобразования примитивного полинома степени н в его свобсщнае от квадратов представление с точки зрения вычислений эквивалентна задаче поиска наибольшего общего делителя двух полиномов степени п в смысле всимптатическога времени работы для наихудшего случая.] 36.
Пусть П~(х) — значение, вычисленное для "и!(х)" по процедуре из упр. 34. Если йеб(П1)+2йеб((7з)+ = йеб(и), то из(х) = Уу(х) для всех !. Однако вобщем случаеу нас будет е < р и !7~(х) = Пь>а изтрь(х) для 1 < у < р. Для дальнейшего разделения этих множителей можно вычислить !(х)/(Уз(х)Пз(х) ...Ср,(х)Р ~) = П >риз(х)Р07Р! = х(хР) После рекурсивного поиска свободного от квадратов представления х(х) = (е~(х), ез(х),...) получим хь(х) = Па«, и~трь(х), так что можно вычислить отдельные и,(х) по формуле бей(Пу(х),еь(х)) = и +рь(х) длЯ 1 < У < Р. Полинам ирь(х) останетса, в то вРема как другие множители хь (х) будут удалены.
Примечание. Эта процедура очень проста, но реализующая ее программа длинна. Если необходима короткая, а не предельно эффективная программа для полного разложения полиномов по модулю р, то, вероятно, проще будет модифицировать программу разложения с различнымм степенями так, чтобы она давала бсй(хр — х, и(х)) несколько раз для одного и того же значения й до тех пор, пока наибольший общий делитель не станет равным 1. В этом случае нет необходимости начинать с вычисления бей(и(х),и'(х)) и удаления кратных множителей, как было предложено в тексте раздела, поскольку полинам хр" — х свободем от квадратов. 37. Точное значение вероятности составляет П >,(аур/р!)"г/И~!, где Иэ †количест й„ равных ~.
Поскольку согласно упр. 4 а„/р' щ 1//Ь получим формулу из упр 1 З.3 †. Примечания. Из этого упражнения следует, что если зафиксировать простоечисла р и случайным образом выбрать полинам и(х), то возникнет определенная вероятность его разложения укаэанным путем по модулю р. Более сложная задача состоит в определении вероятности при фиксированном полиноме и(х) и "случайном'* простом числе р, которое приводит к одному и тому же асимптотическому результату для почти всех и(х). Г.
Фробениус (С. РгоЬеп!иэ) доказал в 1880 году (хотя результат не был опубликован до 1896 гада), что целый полинам и(х) разбивается па модулю р на множители степени йы..., й„при случайным образом выбранном большом простом р с вероятностью, равной числу перестановок в группе Галуа С из полиномов и(х), которые имеют длины циклов [йы..., й,), деленной на общее количество перестановок в С. [Если и(х) имеет рациональные коэффициенты и различные корни бы..., б„мад полем комплексных чисел, его группа Галуа представляет собой едимственную группу С перестановок, такую, что патнмом П 0 „! а(е+ бр!1!у1 +.
+ бр1„!у„) = П(х,ум...,ув) имеет рациональные коэффициенты и непривадим нвд полем рациональных чисел; см. С. ГгоЪеп!ав, 5!гхпляэЬег!сИге Кал!8!. ргеий. Ауай. ЧТнк (Вег!!и, 1896), 689-703. Линейное отображение х ьэ хр традиционно называется автоморфизмом Фробениуса, как в его знаменитой статье.] Кроме того„Б. Л.
вандер Варден (В. 1,, тапйег%аегйеп) доказал в 1934 году, чта почти все палиномы степени и имеют множество всех и! перестановок в качестве их группы Галуа (МасИ. Алла!ел 109 (1934), 13 — 16]. Поэтому почти все фиксированные неприводимые полиномы и(х) будут множителями, как можно ожидать, по отношению к случайному выбору большого простого числа р.
(См. также работу Ь!. СЬеЪосагеч, МагИ. Аапа!еп 96 (1926), в которой представлена обобщение теоремы Фробениуса для сопряженных классов групп Галуа.] 38. Из условий вытекает, что, когда [з[ = 1, мы имеем либо [и -гз" + . + ио[ < [и»-г[-1 < [з»+и гз" '[, либо [и„зз" з+ +ив[ < и г — 1 < [з" +и -гз" г[. Поэтому согласно теореме Роше [з. Еса!е Ро!угесйв!Оое 21, 37 (1858), 1 — 34[ и(з) имеет минимум п — 1 или п-2 корня внутри окружности [з[ = 1. Если и(з) приводим, он может быть записан как в(з) вг(з), где в и ю — нормированные целые полиномы.
Произведения корней в и корней гв представляют собой ненулевые целые числа, так что каждый множитель имеет корень с абсолютной величиной > 1. Следовательно, единственная возможность заключается в том, что в и ю оба имеют в точности цо одному такому корню и что и» г = О. Эти корни должны быть действительны, поскольку корнями являются комплексно-сопряженные числа. Значит, и(з) имеет действительный корень зо с [зо[ > 1. Но этого не может быть, так как, если г = 1/зо, имеем 0 = [1+и„гг + +иог" [ > 1+и гг — [и з[г — -[ив[" > 1. [О.
Реггоп, Сге!!е 132 (1907), 288-307; обобщения даны в А. Вгаиег, Агпег. Х Ыазб. 70 (1948), 423-432, 73 (1951), 717-720.) 39. Сначала докажем утверждение из указания. Пусть полинам и(х) = а(х — а г )... (х — а ) имеет целые коэффициенты. Результант полинома и(х) с полнномом у — з(х) представляет собой детерминант, так что он является полиномом Ш(у) = а 'зи!(у — з(аг))... (у — з(а )) с целыми козффициеитами (см. упр. 4.6 1-12). Если и(х) делит в(з(х)), то в(!(аг)) = О.
Следовательно, гг(у) имеет общий множитель с в(у). Так что, если в иеприводим, мы имеем йеб(и) = беб(гг) > беб(в). Для данного неприводимого полинама и(х), для которого требуется короткое доказательство неприводимости, можно предположить его нормированность согласно упр. 18, а также считать, что беб(и) > 3. Идея заключается в том, чтобы показать существование полинома з(х), такого, что полипом в(у) = гг(у) является неприводимым па критерию из упр. 38. Тогда все множители и(х) делят полипом в(!(х)), и зто доказывает, что и(х) неприводим. Доказательства будет "укорочено", если коэффициенты з(х) достаточно малы.
Можно показать, что полипом в(у) = (у — 8г)... (у — В,) удовлетворяет критерию упр. 38, если и > 3 и !уг ...В„ф 0 и есди выполняется следующее "условие малости": [/)г[ < 1/(4п), за исключением случаев, когда ! = и или 8г = /)„и [5)бг[ < 1/(4гг). Вычисления производятся непосредственно, с учетом того факта, что [во[ + . + [в»[ < ( + [В [) . ( + [3.[).
Пусть аг, ..., о, — действительные числа, а а„+г, ..., а,ч, — комплексные, где и = г + 2з и а,+,+! — — а,чг для 1 < ! < з. Рассмотрим линейные выражения Вг (ао,, а„г), определенные как Я(Я," ' а,а') для 1 < у < г+ з и В(2," ' а,а,') для г+ з < ! < и. Если 0 < а, < Ь и В = [шаху,г 2'," г [а,[г~[, имеем [3г(аг,...,а„г)[ < ЬВ. Таким образом, если выбрать Ь > (16пВ)" ', должны существовать различные векторы (ао,...,а -г) и (о~о,...,а'„г), такие, что [8пЯу(ао,...,а г)[ = [8пЯг(а~о,...,а'„г)! для 1 < у < п, поскольку имеется Ь" векторов, но не более (16пЬВ)" ' < Ь" возможных (и — 1)-элементных наборов значений.
Пусть !(х) = (ав — ао) + + (а„г — а'„,)х" ' и зг = !(аг). Тогда »условие малости" удовлетворено. Кроме тога, !уг Ф 0; в противном случае з(х) должно делить и(х). [з. А!8опсблгз 2 (1981), 385 — 39Ц 40. В данном множителе-кандидате в(х) = хз + аз гх~ ' + + ао заменим каждый а! рациональной дробью (по модулю р') с числителем и знаменателем < В. Затем выполним умножение иа наименьший общий знаменатель и посмотрим, осуществляет ли полученный полинам деление и(х) над кольцом целых чисел. Если нет, то не существует множителя и(х) с коэффициентами, ограниченными В, которые сравнимы по модулю р' с кратным в(х).
41. дэвид Бойд (Пав!4 Воуб) заметил, что 4хз+4хз+х" +4хг+4 = (2х +4х +Ьхг+4х+2) х (2х — 4хз + 5хг — 4х + 2), и нашел пример более высокой степени для доказательства того, что с > 2, если оно существует. РАЗДЕЛ 4.6.3 1. х'", где т = 20э "1 — наивысшая степень 2, меньшая или равная и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
