При и(х) = х" - 1 и v{x) = х" -1 тождество (х" - 1) mod (х" - 1) = х"" 1

показывает, что все полиномы, образующиеся во время вычислений, нормированы и имеют целые коэффициенты. При и(х) = х -1 и v(x) = х-1 имеем V{x) = х+х* + х + х + 1 и U(x) = -(x + x+x+х" +x* + x® + x7f х). (См. также равенство 3.3.3-(29), дающее альтернативную формулу для U{x) и V{x), а также упр. 4.3.2-6, в котором 2 заменено на x.)

4. Поскольку частное q{x) зависит только от v{x) и первых т - п коэффициентов и(х), остаток г(х) = u{x)-q{x)v{x) равномерно распределен и независим от d(x). Следовательно, каждый шаг алгоритма может рассматриваться как независимый от других. Этот алгоритм ведет себя существенно лучше, чем алгоритм Евклида над целыми числами.

Вероятность того, что ni - п - к, равна р"*(1 - 1/р), и t = О с вероятностью р~". Каждый последующий шаг, по существу, ведет себя так же, поэтому любая данная последовательность степеней п, ni, nt, -оо появляется с вероятностью (р - 1)/р". Чтобы найти среднее значение /(щ,..., П(), введем обозначение St для суммы f{ni,... ,щ) по всем последовательностям п > ni > • • • > > О, имеющим данное значение t; тогда среднее значение составляет Е« St{p - lY/p"-

Пусть f{ni,... ,nt) = t; тогда St = (")t, так что среднее равно п(1 - 1/р). Точно так

же при f{ni,.. .,nt) = ni-\-----\-nt получим St = (2)("ri) и среднее значение (2)(1 - 1/р)-

И наконец, для f{ni,. ..,щ) = {п- ni)ni Н-----1- (n«-i - nt)nt

и среднее значение составляет С) - (п + 1)р/{р - 1) + (р/(р - 1))(1 - l/p""*")-

(Вероятность того, что nj+i = nj - 1 для 1 < j < t = п равна (1 - 1/р)", получается, если выбрать St - [t - n]; эта вероятность стремится к 1 при р оо. Как следствие имеем дополнительные основания утверждать, что алгоритм С всегда дает ($2 = 5з = • • • = 1, поскольку любые полиномы, не удовлетворяющие последнему условию, не будут удовлетворять и прежнему условию по модулю р при любом р.)

5. Используя формулы из упр. 4, при fijii,... ,щ) = [nt = 0] найдем, что вероятность равна 1 - 1/р при п > О и 1 при п = 0.

6. Полагая, что постоянные члены и(0) и d(0) ненулевые, представим себе алгоритм деления "справа налево", и(х) = v{x)q{x) + х™~"г(х), где deg(r) < deg(d). Получим алгоритм поиска gcd, аналогичный алгоритму 4.5.2В, который, по сути, представляет собой алгоритм Евклида, приложимый к "обратному" полиному (в смысле упр. 2). Впоследствии ответ обращается и умножается на подходящую степень х.

Существует подобный алгоритм, аналогичный методу из упр. 4.5.2-40. Среднее количество итераций для обоих алгоритмов найдено в работах G. Н. Norton, SICOMP 18 (1989), 608-624; К. Ma and J. von zur Gathen, J. Symbolic Сотр. 9 (1990), 429-455.

7. Обратимым элементам S (в качестве полиномов нулевой степени).

8. Если и(х) = v{x)w{x), где и(х) имеет целые коэффициенты, а v{x) и w{x) - рациональные коэффициенты, существуют ненулевые целые тип, такие, что т v(x) и п w{x) имеют целые коэффициенты. и(х) примитивен, так что (4) означает следующее;

и{х) = рр((пг 1(х))(п w(x))) = ± рр(т • d(x)) рр(п • и;(х)).

9. Алгоритм Е можно расширить следующим образом. Пусть (wi(x),U2(x),из,И4(х)) и (t;i(x), г;2(х), г;з, г;4(х)) представляют собой четверки, удовлетворяющие соотношениям Ui(x)u(x) 4- U2(x)d(x) = U3U4(x) и Di(x)u(x) + D2(x)d(x) = D3i4(x). Расширснный алгоритм начинается с четверок (1, О, cont(u), рр(и(х))) и (0,1, cont(t;), рр(г;(х))) и работает с ними таким образом, чтобы соблюсти указанные выше условия, где U4(x) и г;4(х) проходят по той же последовательности, что и и(х) и v(x) в алгоритме Е. Если aU4(x) = q{x)vi{x)+br{x), то

av3{ui(x),U2ix))-q{x)u3ivi{x),V2{x)) = (ri(x),Г2(х)), гдег1(х)и(х)+Г2(х)г)(х) = Ьизизг{х), так что расширенный алгоритм может сохранить требуемые соотношения. Если и(х) и v{x) взаимно просты, то расширенный алгоритм в конечном счете находит г(х) нулевой степени и мы получаем U(x) = Г2(х), V(x) = ri(x), как и требовалось. (На практике можно разделить ri(x), Г2(а;) и бизз на gcd(cont(ri), соШ(г2)).) Обратно, если такие U{x) и V{x) существуют, то и{х) и v{x) не имеют общих простых делителей, поскольку они примитивны и не имеют общих делителей положительной степени.

10. С помощью последовательного разложения приводимых полиномов на полиномы меньших степеней мы должны получить конечное разложение любого полинома на неприводимые. Разложение содержимого единственно. Чтобы показать, что существует не более одного разложения на примитивные части, необходимо доказать, что если и(х) - неприводимый делитель произведения v{x)w{x), но не произведение обратимого элемента и неприводимого полинома v{x), то и(х) является делителем w{x). Это можно доказать, обратив внимание на то, что и(х) представляет собой делитель v{x)w{x)U{x) = rw{x) - w{x)u{x)V(x) согласно результату упр. 9, где г - ненулевая постоянная.

11. Потребовались бы только строки Ai, Ао, Ва, Вз, В2, Вх, Во, С\, Со, Do- В общем, пусть Uj+2(x) = 0. Тогда строки, необходимые для доказательства, - от v4„2 „ до Ло, от

до Во, от Сп2-", до Со, от Dns-nj до Do и т. д.

12. Если Tik = О, доказательство, приведенное в тексте для (24), показывает, что значение детерминанта составляет ±hk, что равно ±t1~/ Пкч* i.~~K Если полиномы имеют множитель положительной степени, можно искусственно положить, что нулевой полином имеет нулевую степень, и использовать ту же формулу с = 0.

Примечание. Значение детерминанта Сильвестра R{u, v) называется результантом и иу, & величина {-1У--~С{и)~Я{и,и) - дискриминантом и, где и-производная и. Если и(х) имеет разложение вида а(х - Qi)... (х - Qm) и если v{x) = 6(х -i)... ...{х- то результант R{u,v) равен aviai).. .v{a„) = (-l)""6"w(y9i)... u(;9„) = ab"YliLl n7=i(*i ~ Отсюда следует, что полиномы степени тп от у определены

как соответствующие результанты и(у - х), и{у + х), хи(у/х) и и{ух) с v{x), имеющие в качестве соответствующих корней суммы а, + Pj, разности qj - /3j, произведения и частные Qi/Д (при v{0) ф О). Эта идея была использована Р. Г. К. Лоосом (R. G. К. Loos) для создания алгоритмов арифметики алгебраических чисел [Computing-, Supplement 4 (1982), 173-187].

Если каждую строку Ai в матрице Сильвестра заменить строкой на

{boAi+bxAi+i -f-----f-6 ) - {aoBi + aiBi+i +----f-On2-i-i-Bn2-i).

а затем удалить строки с Bn-i по Во и последние П2 столбцов, то получим детерминант размера щ х ni в качестве результанта вместо исходного определителя размера {п\ + П2) х {пх -Ьпг). В некоторых случаях результант может быть эффективно вычислен по значению этого детерминанта [см. САСМ 12 (1969), 23-30, 302-303].

Я. Т. Шварц (J. Т. Schwartz) показал, что можно вычислить результанты и последовательности Штурма для полиномов степени п с помощью всего O(n(log п)) арифметических операций при п -> оо [см. JACM 27 (1980), 701-717].

13. С помощью индукции по j можно показать, что значения {uj+i{x),gj+x,hj) замещены соответственно значениями (£+J w{x)uj{x),( gj, t hj) при j > 2, гдеру = щ -f-n2 -2пу. [Несмотря на этот рост грани (26) остаются справедливыми.]

14. Пусть р - простой элемент из данной области и пусть ],к - максимум, такой, что P*\d„ = (.{v), p\v„-i. Пусть Р = р. Согласно алгоритму R можем записать q{x) =

ао+РаххА-----f-PosX, где s = т-п > 2. Рассмотрим коэффициенты прих""*", х" их"" в

v{x)q{x), а именно - РахЬп+РагЬп-х-----, aoVn + PaxVn-x-i----и oot)n-i -f Poid„ 2 Н----,

каждый из которых кратен . Из первого делаем вывод, что p\ai, из второго - что р"""*-\ао, а из третьего - что Р\оо. Следовательно, Р\г(х). [Если m = п + 1, лучшее, что можно доказать, -это то, что р/ делит г(х). Например, взгляните на и(х) = х +1, v{x) = Ах + 2х + 1, г(х) = 18. С другой стороны, можно воспользоваться аргументом, основанным на детерминантах матриц наподобие (21) и (22) для того, чтобы показать, что

£(r)degCv)-deg(r)-I( всегда кратно £(i,)Cdeg(u)-deg(v))(deg(v)-deg(r)-l)j

15. Пусть Cij = OnOji Н-----1- ainajn. Можно положить, что сц > О при всех i. Если aj ф О

для некоторого i ф j, то можно заменить строку г и столбец i на (cn-tcji, Cin-tcjn), где t = Cij/cjj; эта операция не изменяет значение det С и уменьшает значение верхней грани, которое мы доказываем, поскольку сц заменяется на сц - cj /cjj. Такое замещение можно производить систематично для увеличивающегося i и j < i, пока не будет достигнуто Cij = о для всех i ф j. [Этот алгоритм называется ортогонализацией Грама-Шмидта (см. Crelle 94 (1883), 41-73; Math. Annalen 63 (1907), 442).] Тогда det{A) = det(AA) = сц ... c„„.

16. Полином от одной переменной степени d над любой областью единственного разложения имеет не более d корней (см. упр. 3.2.1.2-16(Ь)); так что если п = 1, то ясно, что r(5i) < dl. При n > 1 имеем /(xi,...,x„) = ро(х2,..., х„)-f xipi(x2,..., х„)-f

----1- xfpdi (x2,..., x„), где Qk ненулевое минимум для одного к. Для данных (х2,..., Хп)

следует, что /(xi,...,x„) равна нулю не более чем при di значениях xi, кроме случая, когда дк{х2,... ,х„) = 0. Следовательно, r(Si,..., Sn)\ < di(S2 - d2)... (S„ - dn) + 5i(52... S„-(52-d2)... (5„-d„)). [R. A. DeMiUo and R. J. Lipton, Inf. Proc. Letters 7 (1978), 193-195.]

Примечание. Указанная верхняя грань - наилучшая из возможных, так как для полинома /(xi,...,x„) = Ilij - Sk \ Sk G. Sj, 1 < к < dj, 1 < j < n} достигается равенство. Однако существует другой подход, при котором верхняя грань может быть значительно улучшена, хотя и в другом смысле. Пусть fi(xi,...,Хп) = f{xi,... ,Хп) и пусть /j + i(xj+i,... ,Хп)-любой ненулевой коэффициент при степени Xj в fjixj,... ,Хп). Тогда можем положить dj равным степени при Xj в fj вместо (зачастую существенно большей) степени Xj в /. Например, можем положить di = 3 и d2 = 1 в полиноме Х?Х2 - 3xf Х2 4- Хг"" -f 5. Это наблюдение гарантирует, что di -f • • -f dn < d, когда каждый член / имеет общую степень < d. Следовательно, вероятность в этих случаях равна

\r{S,...,S)\ ( di\ / d„\ di-f +dn d

\s\ У \s\)--\: \s\)- \s\ -\s\

при равенстве всех множеств Sj. Если она < j и если /(х i,..., Хп) становится равным нулю для 50 случайно выбранных векторов (xi,...,Xn), то /(xi,...,Xn) тождественно равна нулю с вероятностью как минимум 1 - 2"".

Более того, если fj{xj,... ,х„) имеет специальный вид x/j+i(xj+i,... ,х„) с Cj > О, можно получить dj = 1, так как Xj должно быть равно О, когда /j+i(xj+i,... ,Хп) Ф 0. Поэтому разреженные полиномы с только т ненулевыми членами будут иметь dj < 1 для минимум n - lgm значений j.

Применения этого неравенства для вычисления gcd и других операций над разреженными полиномами от многих переменных были введены Р. Циппелем (R. Zippel) (Lecture Notes in Сотр. Sci. 72 (1979), 216-226). Я. Т. Шварц (J. Т. Schwartz) [JACM 27 (1980), 701-717] привел дальнейшие расширения, включая устранение больших чисел с помощью модулярной арифметики: если коэффициенты / целые, если Р является множеством целых чисел > 5 и если /(xi,... ,Хп) < L для каждого Xj 6 Sj, то количество решений /(xi,..., Хп) = О (mod р) для р 6 Р не превышает

5i... \Sn\\P\ - (Si - dl)... {\Sn\- dn){\P\ ~ log, L).