ность остатков, доказывающая, что полином и{х) взаимно прост с и{х). Считая uo{x) = и{х), ui{x) = и{х) (и следуя Штурму), изменим знак всех остатков. Получим

ciUo{x) = ui{x)qi{x) - diU2{x), C2Uiix) = U2ix)q2ix) - d2U3(x),

(29)

CfcWfc-i(x) = Ukix)qk{x) - dkUk+i{x)

для некоторых положительных констант cj и dj, где deg(ufc+i) = 0. Будем говорить, что отклонение V{u,a) полинома и{х) в а равно количеству изменений знака в последовательности uo{a), ui{a), Uk+i{a), не считая нулей. Например, если последовательность знаков представляет собой О, +, -, -, О, +, +, -, получим V{u,a) = 3. Теорема Штурма утверждает, что количество корней и{х) в интервале а < X <Ь равно V{u, а) - V{u, b). Доказательство этого факта на удивление коротко (см. упр. 22).

Хотя алгоритмы С и Е интересны, история на них не заканчивается. Важные альтернативные пути вычисления gcd полиномов над целыми числами будут рассмотрены в конце раздела 4.6.2. Имеется также общий алгоритм для вычисления детерминанта, о котором можно сказать, что он включает в себя алгоритм С в качестве частного случая [см. Е. Н. Bareiss, Math. Сотр. 22 (1968), 565-578].

В четвертом издании этой книги я намерен переделать материал настояще-JL го раздела, уделив достойное внимание как исследованиям детерминантов в 19 веке, так и работе W. НаЫсЫ, Comm. Math. Helvetici 21 (1948), 99-116. Превосходное обсуждение последней дано в работе R. Loos in Computing, Supplement 4 (1982), 115-137. К этим же методам относится и интересный метод вычисления детерминантов, который выведен Ч. Л. Доджсоном (С. L. Dodgson) (известным также под именем Льюис Кэррол (Lewis Carroll)) из теоремы Якоби. Обзор ранней истории исследований тождественности детерминантов подматриц можно найти в работе D. Е. Knuth, Electronic J. Combinatorics 3,2 (1996), статья R5, §3.

УПРАЖНЕНИЯ

1. [10] Вычислите псевдочастное q(x) и псевдоостаток г(х), т. е. полиномы, удовлетворяющие (8), для и(х) = х + х-х* + 2х-\-Зх -х-\-2и v(x) = 2ж-Ь2ж-ж-ЬЗ над целыми числами.

2. [15] Чему равен наибольший общий делитель полинома Зх+х+4х*+4х-\-Зх+4х+2 и "обратного" ему полинома 2х-\-4х-\-Зх*-\-4х-\-4х-\-х+3 по модулю 7? (В данном случае под "обратным" подразумевается полином с обращенным порядком коэффициентов. - Прим. перев.)

► 3. [М25] Покажите, что алгоритм Евклида для полиномов над полем S может быть расширен для поиска полиномов U(x) и V(x) над S, таких, что

и(х) V(x) -Ь и(х) v(x) = gcd(u(x), v(x))

(см. алгоритм 4.5.2Х). Чему равны степени полиномов U(x) и V(x), вычисленных при помощи такого расширенного алгоритма? Докажите, что если S - поле рациональных чисел и если и(х) = ж" - 1 и г) (ж) = ж" - 1, то расширенный алгоритм дает полиномы U(x)

и V{x), имеющие целые коэффициенты. Найдите U{x) и V(x) для и{х) = х - 1 и v{x) = х-1.

► 4. [МЗО] Пусть р - простое число, и предположим, что алгоритм Евклида, примененный к полиномам и{х) и v{x) по модулю р, приводит к последовательности полиномов, имеющих степени соответственно т, п, щ, ..., nt, -оо, где тп = deg(u), п - deg(t)) и П( > 0. Положим, что m > п. Если и(ж) и г)(а;) являются нормированными полиномами, независимо и равномерно распределенными среди всех р"+" пар нормированных полиномов степеней соответственно ш и п, то чему равны средние значения трех величин t, tii + + nt и

(п - m) ni -I-----h (nt-1 - П()П(, выраженные как функции от m, п и р? (Эти три величины

являются основными факторами, влияющими на время работы алгоритма Евклида с полиномами по модулю р, если считать, что деление выполняется при помощи алгоритма D.) [Указание. Покажите, что и{х) mod v{x) равномерно распределен и независим от v{x).]

5. [М22] Чему равна вероятность того, что и{х) и v{x) взаимно просты по модулю р, если и{х) и v{x) - независимые равномерно распределенные нормированные полиномы степени п?

6. [М23] Мы видели, что алгоритм Евклида 4.5.2А для целых может быть преобразован в алгоритм для поиска наибольшего общего делителя полиномов. Можно ли аналогичным путем преобразовать бинарный алгоритм поиска gcd 4.5.2В в алгоритм, работающий с полиномами?

7. [МЮ] Чему равны обратимые элементы в области всех полиномов над областью единственного разложения S?

► 8. [М22] Покажите, что, если полином с целыми коэффициентами неприводим над областью целых чисел, он неприводим и при рассмотрении его над полем рациональных чисел.

9. [М25] Пусть и{х) и v{x) - примитивные полиномы над областью единственного разложения S. Докажите, что и{х) и v{x) взаимно просты тогда и только тогда, когда полиномы U{x) и V{x) над S таковы, что u{x)V{x) + U{x)v{x) - полином нулевой степени. [Указание. Расширьте алгоритм Е так, как алгоритм 4.5.2А был расширен в упр. 3.]

10. [М28] Докажите, что полиномы над областью единственного разложения образуют область единственного разложения. [Указание. Используйте результат упр. 9 для того, чтобы показать, что имеется не более одного возможного разложения.]

11. [М22] Какие строки появились бы в табл. 1, если бы последовательность степеней была 9, 6, 5, 2, -00, а не 8, 6, 4, 2, 1, О?

► 12. [М24] Пусть ui{x), U2{x), из{х), ... - последовательность полиномов, полученная во время работы алгоритма С. Матрица Сильвестра представляет собой квадратную матрицу, построенную из строк с Anj-i по Ао и с Вщ-! по Во (в обозначениях, аналогичных обозначениям для табл. 1). Покажите, что если ui{x) и U2{x) имеют общий множитель положительной степени, то детерминант матрицы Сильвестра равен нулю, и обратно: покажите, что если для некоторого к deg(ufc) = О, то детерминант матрицы Сильвестра ненулевой (покажите это, выведя формулу для его абсолютного значения через £{uj) и deg{uj), l<j<k).

13. [М22] Покажите, что при Si = S2 = = Sk-i = 1 старший коэффициент i примитивной части gcd{u{x),v{x)) входит в показанную в (28) последовательность полиномов, которая получается с помощью алгоритма С. Каково поведение для общего случая 6j?

14. [М29] Пусть г{х) - псевдоостаток от псевдоделения и{х) на v{x). Покажите, что если deg(u) > deg(t)) -Ь 2 и deg(t)) > deg(r) + 2, то г(х) кратен £{v).

15. [М26] Докажите неравенство Адамара (25). [Указание. Рассмотрите матрицу АА.]

► 16. [М22] Пусть f{xi,... ,Хп) - полином от многих переменных, не равный тождественно нулю, и пусть r(Si,..., Sn) - множество корней (xi,..., ж„) уравнения f{xi,..., ж„) = О, таких, что XI е Si, ..., х„ е S„. Если степень / не превышает dj < \Sj \ для переменной Xj, докажите, что

r(Si,...,S„) < Si...S„-(Si-di)...(S„-d„).

Следовательно, вероятность нахождения корня случайным образом,

ir(Si,...,S„)i/Si...S„,

приближается к нулю при увеличении множеств Sj. [Это неравенство имеет множество приложений при разработке алгоритмов рандомизации, так как предоставляет хороший способ проверки, является ли сложная сумма произведений сумм равной нулю без раскрытия всех сомножителей.]

17. [М32] (Алгоритм П. М. Кона (Р. М. Cohn) деления строковых полиномов.) Пусть А является алфавитом, т. е. множеством символов. Строка а над алфавитом А представляет собой последовательность из п > О символов а = ai...a„, где каждое aj € А. Длина а, записываемая как а, равна количеству символов п. Строковым полиномом над алфавитом А является конечная сумма U = г к Ок, где каждое г к является ненулевым рациональным числом, а каждое ак -строкой над алфавитом А; мы полагаем, что Oj ф ак при j ф к. Степень U, deg(U), определяется как -оо, если U - О (т. е. если сумма пуста); в противном случае deg(u) = тахо:к. Сумма и произведение строковых полиномов определяются очевидным образом. Так, С,. rjaj)(Y SkPk) = Ej.fc rjSkQj/3k, где произведение Двух строк получается щ-тем их простого соединения; после этого они становятся членами суммы. Например, если А = {а, Ь}, U = аЬ + Ьа - 2а - 2Ь и V = а + b - I, то deg(U) = 2, deg(V) = 1,V =аа + аЬ + Ьа + ЬЬ-2а-2Ь + 1иУ-и = аа + ЬЬ+1. Ясно, 4Todeg(t/V) = deg(C/)-bdeg(V) и deg(U+V) < max(deg(t/), deg(V)) с равенством в последней формуле при deg(U) ф deg(V). (Строковые полиномы могут рассматриваться как обычные полиномы от многих переменных над полем рациональных чисел, но переменные не коммутативны относительно умножения. На математическом языке множество строковых полиномов с определенными здесь операциями представляет собой "свободную ассоциативную алгебру", порожденную А над полем рациональных чисел.)

a) Пусть Ql, Q2, и и V-такие строковые полиномы с deg(U) > deg(V), что deg(QiU - Q2V) < deg(QiU). Разработайте алгоритм поиска строкового полинома Q, такого, что deg(U - QV) < deg(U). (Следовательно, если даны U и V, такие, что QiU = Q2V + R и deg(R) < deg(QiU) для некоторых Qi и Q2, то существует решение для этих условий при Ql =1.)

b) Даны строковые полиномы U hV с deg(V) > deg(QiL -Q2V) для некоторых Qi и Q2. Покажите, что результат п. (а) может быть улучшен для поиска частного Q, такого, что и = QV + R, deg(R) < deg(V). (Это аналог (1) для строковых полиномов; в п. (а) показано, что можно достичь deg(iZ) < deg(U) при более слабой гипотезе.)

c) Однородный полином-это полином, все члены которого имеют одну и ту же степень (длину). Пусть Ui, U2, Vl, V2 являются однородными строковыми полиномами с UiVi = U2V2 и deg(Vi) > deg(V2). Покажите, что существует однородный строковый полином и, такой, что U2 = UiU и Vi = UV2.

d) Даны однородные строковые полиномы U и V с UV = VU. Докажите, что имеется однородный строковый полином W, такой, что U = rW", V = sW" для некоторых целых т, п и рациональных чисел г, s. Разработайте алгоритм для вычисления И, имеющего наибольшую возможную степень. (Этот алгоритм интересен, например, когда и = а и V = /3 - строки, удовлетворяющие соотношению а/З = /За; тогда W - просто некоторая строка 7. Когда U = х" и V = ж", решение с наибольшей степенью