AOP_Tom2 (1021737), страница 209
Текст из файла (страница 209)
(На самом деле в этом частном случае НОПД будет являться любая матрица с детерминантам х1.) 20. Рассмотрите построение из упр. 4.6.2-22, но такое, что р™ заменено малым числом е. 21. Для получения верхней грани положим, что алгоритм К используется только при т — и < 1 и коэффициенты огршгичены согласна (26) с т = и. [Указанная формула дает практическое время вычисления, а не только верхнюю грань.
Более подробную информацию можно найти в работе О. Е. Со!!!пе, Рюс. 1968 Яапгшег 1пзк оп ЯушЬобс Ма!Леша!!са! Согпрпзасюп, ебйеб Ьу КоЬегс О. ТоЬеу (1ВМ Еебгга! Яузсеше Сепсег, Липе, 1969), 195-231.] 22. Последовательность знаков не может содержать два идущих подряд нуля, поскольку иью(х) — ненулевая константа в (29). Кроме того, в качестве падпоследавательности не может встретиться»+, О, +" или "—, О, — ". Формула 1'(и, а) — К(и,Ь), очевидно, верна при 6 = о, так чта ге необходима проверить только при увеличивающемся Ь. Полиномы и,(х) имеют конечное количество корней, и Г(и, Ь) изменяется талька тогда, когда 6 встречается илн проходит через такие корни. Пусть х — корень некоторого (возмажно, нескольких) и .
Когла 6 увеличивается от х — е до х, знаковая последовательность около у переходит ат "+, х, -" к »+, О, -" или ат "-, х, +" к '-, О, +" при у > 0; при з = 0 — от »+, -" к »О, -" или ат " †, +» к »О, +"(поскальку и'(х) †производн, и (х) отрицательна при уменьшении и(х)). Таким образом, изменение 1» составляет -б,а. При возрастании 6 от х до х + «подобное рассмотрение показывает,чта Г остается неизменным. (Л. Э. Хайндел (Е. Е Не!пйе!) в работе бАСМ 18 (1971), 533 — 548, применил эти идеи для построения алгоритма обособленна действительных нулей данного полинама и(х) за время, растущее как полинам от йе8(и) и 1об)т, где все коэффициенты иу — целые числа (и, ( < Уд, а все операции абсолютно точны.) 23. Если и имеет п — 1 действительный корень между и действительными корнями и, то, рассмотрев изменения знаков, получим, что и(х) шой и(х) имеет и — 2 действительных корня, лежащих между и — 1 корнем а.
б««б««(«-з««) б«(«-6«),,.(«-«у «) 24. Сначала покажите, что Ьу = д,' 'д,', ' ' ... д« '" ' ', а затем — что показатель степени дз в левой части (18) имеет вид б«+ б«х, где х = б«+ +б««+ 1 — б«(бз+ +᫠— «+ 1) — б«(1 — б«)(б«+ +бу-) +1) — "— ᫠— ((1 — б«)...(1 — б«-«)(1). Однако х = 1, поскольку он не зависит от б, м и можно принять, что б, ) = О, и т. д. Подобное доказательство работает и для дз, дм, а упрощение — лля (23). 25. Каждый коэффициент и«(х) может быть выражен как детерминант, в котором один столбец содержит только б(и), б(в) и нули, Чтобы использовать этот факт, модифицируем алгоритм С следующим образом.
На шаге С1 установим д ( — йсй(б(и),б(о)) и Ь +- О. На шаге СЗ, если Ь = О, установим и(х) (- и(х), и(х) (- г(х)/д, Ь +- б(и)~/д, д (- б(и) и вернемся к шагу С2. В противном случае будем работать по немодифицированному алгоритму. Эффект этой новой инициализации заключается в простой замене и«(х) на иу(х)/8сй(б(и),б(и)) для всех,у' > 3. Таким образом, в (28) /~д ' становится сю 28. Фактически верно даже большее.
Обратите внимание, что алгоритм из упр. 3 вычисляет хр»(х) н ~д„(х) для и > — 1. Пусть е» = йей(д„) и й„= йеб(р и — д„и). В упр. 3 мы видели, что с! -«+ е» = йей(и) для п > О. Докажем, что условия йе8(д) < е„ н йей(ри — ди) < й «влекут за собой р(х) = с(х)р»-г(х) и д(х) = с(х)д ((х). По данным р и д можно найти с(х) и й(х), такие, что р(х) = с(х)р» «(х) + й(х)р„(х) и д(х) с(х)д ((х) + й(х)д (х), поскольку р -г(х)д (х) — р (х)д ((х) = Ь1. Следовательно, ри — ди = с(р„«и — д» «и)+й(р и-д и). Если й(х) ~ О, мы должны иметь йеб(с) +е„ йеб(й) + е„, так как йе8(д) < йе8(д ). Отсюда следует, что йей(с) + й„«> йеб(й) .(.
й„, поскольку это, несомненно, верно, если й = — оа. В противном случае й„«+ е„ й„+е»ш > й„+е ы Таким образом, йеб(ри — да) = йе8(с)+й„ь Но мы предположили, что йеб(ри — да) < й, « = й» «+ е» вЂ” е„ц так что йеб(с) < е„— е„-( и йе8(й) < О, что приводит к противоречию. [Этот результат, по сути, получен в работе Н Кгапес(«ег, Маласзбег)сбсе Кбшд!. ргенд.
АЬай. ИЪэ. (Вег!(и, 1881), 535 — 600. Отсюда вытекает следующая теорема. "Пусть и(х) и в(х) — взаимно простые полиномы над полем и пусть й < йеб(а) < йеб(и). Если д(х) является палинамом наименьшей степени, таким, что существуют полинамы р(х) и г(г), такие, что р(х)и(х) — д(х)и(х) = г(х) н й»8(г) = й, то р(х)/д(г) = р„(х)/д„(х) для некаторога и". Для й -« > й > й»-« существует решение д(х), такое, что йеб(д) = е„, + й — й„«< е . Итак, все решения столь низкой степени имеют указанное свойство.) 27. Приложимы идеи упр. 4.3.1-40, но в более простой форме, потому что полиномиальная арифметика не оперирует переносами; деление справа налево использует 4.7 — (3).
Другой путь заключается в том, чтобы при больших значениях и делить преобразования Фурье коэффициентов с "обратным" использованием упр. 4.б,4 — 57. РАЗДЕЛ 4.6.2 1. Для любого выбора А < и различных корней существует р" л нормированных полиномов, имеющих как минимум по одному из этих корней. Поэтому согласна принципу включения и исключения (см. раздел 1 3,3) количества полиномов без линейных множителей составляет 2' ,<„(г)р" «( — 1)".
Частичные суммы этого ряда попеременно больше или меньше его суммы. Требуемые границы можно получить, положив и = 2 и и = 3. При и > р вероятность наличия хотя бы одного линейного л«нажителя составляет 1 — (1 — 1/р)". Среднее количества линейных множителей в р раз превьпвает среднее количество случаев, когда величина х делит полинам и(х), так что апа составляет 1+р '+" +р'-" =-,-~,.(1 — р-"). (Аналогично находим, что вероятность существования непрнводимога множителя степени 2 Равна 2 л<„«л ("~" л'««~)(-1) "Р ™. Эта веРоЯтность лежит мев«ДУ э — -'Р ' и -' — -'р ' при п > 2 н стремится к 1 — е сщ(1+ -'р ') + 0(р э) прн и -+ аа.
Среднее количество таких множителей равно -' — 1р л Примечание. Пусть и(х) — фиксировшлный полинам с целыми коэффициентами. Петер Вайнбергер (Ре«ег ЪЧеспЬегйег) обнаружил, чта если и(х) непривадим над кольцом целых чисел, то среднее количество линейных множителей и(х) по модулю р стремится к 1 при р -л аа, потому что группа Галуа и(х) транзитивна и среднее количества единичных циклов в случайно выбранном элементе любой группы транзитивных перестановок равно 1.
Следовательно, среднее количество линейных множителей и(х) по модулю р равно количеству непрнводимых множителей и(х) нэд кольцом целых чисел прн р -л са. [См. примечания в ответе к упр, 37, а также Ргос. Яушр. Риге Мас)л. 24 (Ащег. Мас1«. Яасч 1972), 321-332.] 2. (а) Известно, что и(х) может быть представлен как произведение неприводимых полиномов н что старшие коэффициенты этих полиномов должны быть обратимыми элементами, поскольку они делят старший коэффициент полинома и(х). Поэтому можно считать, что и(х) имеет представление в виде произведения нормированных неприводимых пояиномов р«(х)" ...р,(х)", где р«(х),..., р,(х) различны.
Это представление единственно с точностью до порядка множителей, так что условия, налагаемые на и(х), е(х) и и«(х), удовлетворяются тогда и талька тогда, когда (Ь) Производящая функция для количества нормированных палиномов степени и представляет собой 1 4- рэ + рлээ 4- ° = 1/(1 — рэ).
Производящая функция для количества полиномов степени и, имеющих вид а(х), где а(х) — нормированный полинам, представляет собой 1 + рхэ + рлэ«+ ж 1/(1 — рэ ). Если обозначить производящую функцию для количества нормированных свободных от квадратов полинамов степени и через д(э), то согласно п. (а) этого упражнения 1/(1 — рэ) = д(э)/(1- рэл). Следовательно, д(х) = (1 — рэл)/(1 — рэ) = 1 + рэ + (рл — р)хэ + (рэ — рл)эз + . Таким образом, ответ — р" — р" для и > 2. (Любопытно, что эта доказывает, чта и(х) 1 и'(х) с вероятностью 1 — 1/р; эта та же вероятностлч что и вероятность тога, что и(х) С а(х) в случае независимости и(х) и а(х) согласно упр.
4.б.1 — 5.) Примечание. Аналогично доказывается, чта каждый полинам и(х) может быть единственным образом представлен в виде а(х) и(х)", где а(х) не делится на г-ю степень никакого неприводимого полинома; количество таких нормированных полиномов е(х) составляет р" — р" 'е' при и > г.
3. Пусть и(х) = п~(х) ., и,(г) Имеется не более одного такого полинома о(х) согласно доказательству теоремы 4.3.2С. Существует по меньшей мере адик такой лелином, если для каждого / можно решить систему с ш,(х) = 1 и шь(х) = 0 при к р /. Решением последней является о~(х) [)[„Х иь(х), где о~(х) и о«(х) удовлетворяют соотношению о~(х) Д„„1 и»(х) + о»(х)и;(х) = 1, Йеб(о~) < беб(и,) согласно расширению алгоритма Евклида (упр. 4.6.1-3). Над кольцом целых чисел нельзя сделать о(х) га 1 (по модулю х) и о(х) щ 0 (по модулю х — 2) при деб(о) < 2. 4. Исходя из единственности разложения, имеем (1 — р») ' = [(„>,(1 — »") "е; после взятия логарифмов зто соотношение может быть переписано как 1в(1/(1 — р»)) = 2 ь .>, окз««// = 2 .> Ср(«1)//.
Из утверждения указания следует ответ Ср(«) = Я >, р(п»)гн 1п(1/(1 — р«~)), из котоРого полУчаем а» = т ьд(п/о)Р~/и, Таким обРазом, 1пп„а„»/Р" = 1/и. Для доказательства утверждения, приведенного в указании, заметим, что ~„ 1> р(п)д(«"')и '/ ' = ~ >, д(» )гп ' ~„'„1 р(п) = д(»). [Числа аьр были впервые найдены Гауссом; см. Иге»)ге 2, 219-222.] 5. Пусть а„,— количество нормированнык полиномов степени и по модулю р, имеющих в точности г непРиводнмык множителей. Тогда й»(«,ю) = 2 „„>ее„ж»"ю' екр(2 >, С„(«~) щ"/й) = ехр(2 >, а 1п(1/(1 — р«)); см, формулу 1.2.9 — (38). Имеем 2 „>о А„»" = ой»(«/р, щ)/ош[ =~ = (2 „>, Сг(« /р )) Я„(»/р,1) (2 )п(1/(1 р1-ь»ь))р(п)/и)/(1 «) следовательно, А р — — Н„+ 1/2р -ь О(р») для и > 2. Среднее значение 2' равно [»"]Я (г/р, 2) = и+ 1+ (и — 1)/р+ 0(пр»).
(Дисперсия, однако, есть величина порядка и»: положите ю = 4.) 6. Согласно теореме Ферма х — » является множителем х» — х (по модулю р) для 0 < в < р, Значит, х" — х кратно 1сщ(х — О, х — 1... х — (р — 1)) = хд. [Примечание. Следовательно, числа Стирлинга [Д кратны р эа исключением случаев, когда й = 1 или /г = р. Формула 1.2.б-(45) показывает, что то же утверждение справедливо и для чисел Стирлинга (),) второго рода.) 7. Множители в правой части взаимно просты, и каждый из них является делителем и(х), так что ик произведение делит и(х).
С другой стороны, и(х) делит так что и(х) делит правую часть согласно упр, 4.5,2-2. 8. Вектор (18) является единственным, 1с-я компонента которого не равна нулю. 9. Например, начав с х +- 1 и д » — 1. Затем следует сто раз установить Н[х[ ь- д, х +-2х шоб 101, д ь- 519 щоб 101. 10. Матрица 4) — 7, приведенная ниже, имеет ядро, порожденное двумя векторами ер~ = (1, 0,0,0,0,0,0, 0), о~О = (О, 1,1,0,0, 1, 1,1). Разложение представляет собой (х'+ х'+ х'+ я+1)(х'+ я+1). р=2 0 0 0 О 0 0 0 1 1 О О 0 О О 1 0 1 О О 0 0 1 0 0 1 О 0 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 р=5 0 О 0 0 0 0 0 0 1 О 2 0 4 3 4 4 4 4 2 1 2 3 4 3 2 4 0 1 3 2 2 1 4 2 1 0 О О О 0 0 1 0 1 0 0 О 0 1 0 1 О О 0 4 0 2 0 1 2 2 0 0 3 0 11.
После удаления тривикчьиого множителя х приведенная выше матрица Я вЂ” 7 имеет ядро, порожденное (1,0,0,0,0,0, 0) и (0,3, 1,4,1, 2,1). Полное разложение полинома таково: х(х + Эх+ 4)(хе+ 2х +х +4х +х+ 3). 12. Если р = 2, (х+ 1) = х + 1. Если р = 85+ 1, Я вЂ” 1 представляет собой нулевую матрицу, а значит, существует четыре множителя. Для других значений р имеем: р=81+3 р = 85+5 р=8к+7 Π— 2 0 0 0 -1 0 -1 14.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
