(Лучшая грань получится, если максимизировать предпоследнее выражение по всем степеням т для каждого неисключенного множителя.) Величина n\*/{n/2ty! равна Ct(2t)"/n-(=-)/»(l + 0()), где ct = 2V8-(2t-i)/8jt/4 1 р 2).

Заметьте, что существование неприводимого множителя с такими малыми коэффициентами здесь не доказывалось; может потребоваться дальнейшее разложение (см. упр. 41).

(e) [иг = ЕкНти) = = 47а") = v+o{n-). если

t;(x) = (х - 1)" и w{x) = (х -I-1)", имеем [t;] = [w] = 2"; следовательно, неравенство (с) становится в этом случае равенством.

(f) Пусть и и V - однородные полиномы степени шип. Тогда

luv?

-Г ГГ) -кИ) (.-j) Яг гп у

согласно неравенству Коши. [В. Beauzamy, J. Symbolic Сотр. 13 (1992), 465-472, Proposition 5.]

(g) В соответствии с упр. 20 („%j)-M(u) < (j)"!"!! = (t„%j)-Е, [и] = Ej < Ej (")л(") = 2"M(u). Первое неравенство следует также из

п. (f); еслии(х) = и„ UUi-j), имеем [и] < ЫЩА - <J? = + <

Krn;=i(2ma(l, lajl)) = 2"M(u)

22. Рассмотрим более обхцую ситуацию. Предположим, что и{х) = v{x)w{x) modq, a(x)v{x) + b(x)w{x) = 1 modp, и ce{v) ~ 1 modr, deg(a) < deg(u)), deg(6) < deg(i;), deg(u) = deg(i;) --deg(u;), где r = gcd(p, g) и p, g не обязательно должны быть простыми числами. Построим полиномы V(x) = v{x) и W{x) = w{x) modg такие, что u(x) = V(x)W(x) modgr, £{V) = £{v), deg(F) = deg(t;), deg(iy) = deg(u;). Кроме того, если г - простое число, результат по модулю qr окажется единственным.

В задаче спрашивается, как найти С(х) и й)(х), такие, что V{x) = v{x) + qv{x), W{x) = w{x) +qu){x), deg(C) < deg(t;), deg{w) < deg(u;); другое условие,

(t;(x) -I- qv(x)){w{x) + qii){x)) = u(x) mod qr,

эквивалентно iD(x)t;(x) + v{x)w{x) = /(x)modr, где f{x) удовлетворяет соотношению u(x) = i;(x)u;(x) -- qf{x) mod qr. Для всех t(x) имеем

(a(x)/(x) + t{x)w{x))v{x) + (b(x)/(x) - t{x)v{x))w{x) = f{x) modr.

Поскольку для (t;) существует обратный элемент по модулю г, можно с помощью алгоритма 4.6.1D найти частное t(x), такое, что deg(b/ - tv) < deg(t;); для этого t(x), deg(a/ -I- tw) < deg(u)), поскольку имеем deg(/) < deg(u) = deg(t») -I- deg(u;). Таким образом, искомое решение - г;(х) = 6(х)/(х) - t(x)t;(x) = 6(х)/(х) mod г;(х), й)(х) = а(х)/(х)-I-t(x)u;(x). Если {v(x),w{x)) представляет собой другое решение, имеем {w{x) - ui{x))v{x) = (S(x) - C(x))u;(x) modr. Следовательно, если г - простое число, v{x) должно делить 5(х) -С(х), но deg(5-C) < deg(i;), такчто S(x) = С(х) и t5(x) = й)(х).

Если р делит q, так что г - р, выбор V{x) и W{x) удовлетворяет также соотношению a{x)V{x) + b{x)W{x) = 1 (по модулю р), что и требуется по лемме Хенселя.

Для р = 2 процесс разложения протекает следующим образом (далее записываются только коэффициенты с надчеркиванием для обозначения отрицательных цифр). В упр. 10 утверждается, что v\{x) = (111), Wi{x) = (1110011) в однобитовой комплементарной к 2 записи. Расширенный алгоритм Евклида приводит к а(х) = (100001),6(х) = (10). Множитель v{x) - х + Cix -I- Со должен иметь ci < [1 -I- \/113j = 11, со < 10 согласно упр. 20. Три применения леммы Хенселя дают Vi{x) = (13 1), u;4(x) = (1 3 5 443 5). Таким образом, Ci = 3 и Со = -1 mod 16; единственный возможный квадратичный множитель

и{х)-х + Зх -1. Деление ошибочно, поэтому и(х) - неприводимый полином. (Поскольку "неприводимость" этого "ненаглядного" полинома доказана четырьмя различными методами, вряд ли кто-то сможет найти хоть один его множитель... )

Ганс Зассенхауз (Hans Zassenhaus) обнаружил, что зачастую можно ускорить вычисления, увеличив р так же, как и д: если в приведенных выше обозначениях г = р, можно найти А{х), В{х), такие, что А{х)у{х) -I-В(х)И(х) = Imodp, а именно - взяв А{х) = а(х) + ра{х), В{х) = 6(х) -I- р6(х), где a(x)V(x) + 6(х)И(х) = g(x)modp, a(x)F(x) -I- b{x)W{x) = 1 -pg(x)modp2. Также можно найти С с £(V)C = Imodp. Так можно свести разложение, свободное от квадратов, и(х) = v(x)w(x) modp, к их единственным расширениям по модулю р, p, р* р® и т. д. Однако такая "ускоренная" процедура на практике достигает точки замедления, как только мы достигаем двойной точности, поскольку время для умножения чисел с многократной точностью в реальном диапазоне значений перевешивает преимущества от возведения модулей в квадрат. С вычислительной точки зрения представляется, что лучше работать с последовательными модулями р, р2, р"*, р*, ..., р, p"*" р2, р"*", • • , где Е - наименьшая степень 2 с р, ббльшим однократной точности, и е - наибольшим целым числом, таким, что р имеет однократную точность.

"Лемма Хенселя" на самом деле была открыта К. Ф. Гауссом (С. F. Gauss) около 1799 года, в черновике неоконченной книги Analysis Residuorum, §373-374. Гаусс внес большую часть материала из этой рукописи в свою Disquisitiones Arithmeticse (1801), но его идеи о разложении полиномов были опубликованы лишь после его смерти [см. WerJce 2 (Gottingen, 1876), 238]. Имя Хенселя оказалось связанным с методом, потому что он стал основой теории р-ичных чисел (см, упр. 4.1-31). Лемма может быть обобщена несколькими способами. Во-первых, если имеется большее количество множителей, например и(х) = vi{x)v2{x)v3{x) modp, можно найти ai(x), а2(х), аз(х), такие, что ai(x)i;2(x)t;3(x)-I-а2(х)г;1(х)г;з(2;)-)-аз(х)г;1(х)г;2(х) = 1 modp и deg(ai) < deg(i;,), (По существу, 1/и(х) расширяется в отдельных частях до Е•()/«()) Точный аналог построения теперь позволяет провести разложение, не изменяя старшие коэффициенты vi и V2; мы получаем Ci(x) = ai(x)/(x) modi;i(x), С2(х) = а2(х)/(х) modi;2(x) и т. д. Другое важное обобщение состоит в различных одновременных модулях соответствующего вида

р,(х2 - ог)",......,{xt - at)" при выполнении поиска наибольших общих делителей

и разложении полиномов от нескольких переменных. [См. D, Y. У. Yun, Ph. D. Thesis (М. I. Т., 1974).]

23. Дискримингшт pp(u(x)) представляет собой ненулевое целое число (см. упр. 4.6.1-12), и кратные множители по модулю р существуют тогда и только тогда, когда р делит этот дискриминант. [Разложение (22) по модулю 3 равно (х -I- 1){х - х - 1)(х + х - х + 1); квадратные множители для этого полинома имеются только дляр == 3, 23, 233 и 121702457. Нетрудно доказать, что наименьшее простое число, не являющееся "неудачным" не превышает 0{n\ogNn), если п = deg(u), а N является гранью по абсолютной величине коэффициентов и{х).]

24. Умножьте нормированный полином с рациональными коэффициентами на подходящее ненулевое целое число для получения примитивного полинома над кольцом целых чисел. Разложите полином над кольцом целых чисел, а затем конвертируйте множители в нормированные полиномы (таким образом, не будет потеряно ни одно разложение; см. упр. 4.6.1-8).

25. Рассмотрение постоянного члена показывает, что у полинома нет множителей степени 1, так что если полином приводим, то он должен иметь один множитель степени 2 и один - степени 3. Разложение по модулю 2 представляет собой х(х -I- lix -I- х -I-1) и для

нас бесполезно. Разложение по модулю 3 представляет собой (х + 2)(х + 2х + 2), а по модулю 5 - (х + х + 1)(х+4х+2). Таким образом, искомый ответ-(х + х+1)(х-х + 2).

26. Начнем с D (0...01), представляющего множество {0}. Затем для 1 < J < г установим D <- D W {D dj), где V означает побитовое "или" а D d - побитовый сдвиг D влево на d позиций. (В действительности достаточно работать только с битовым вектором размерности ((п + 1)/2], поскольку п - т содержится в множестве тогда и только тогда, когда в нем содержится т.)

27. В упр. 4 утверждается, что случайный полином степени п неприводим по модулю р с весьма малой вероятностью, около 1/п. Но из китайской теоремы об остатках следует, что случайный нормированный полином степени п над кольцом целых чисел будет приводим для каждого из к различных простых чисел с вероятностью около (1 - 1/п)*, которая будет стремиться к нулю при А; -> оо. Следовательно, почти все полиномы над кольцом целых чисел являются неприводимыми для бесконечно большого количества простых чисел и почти все примитивные полиномы над кольцом простых чисел являются неприводимыми полиномами (другое доказательство дано в работе W. S. Brown, АММ 70 (1963), 965-969).

28. См. упр. 4; вероятность составляет [z"]{l+aipz/p){l+a2pz/p)(l+a3pZ/p)..., предельное значение при п -> оо составляет g{z) = {I + z){l + z){l + z)---- Для

1 < n < 10 искомые значения равны , , , , Щ, if, Щ§. [Пусть f(y) = 1п(1 + у)-у = 0{у). Имеем

g(z) = exp(i:„>i zn + E„>i fiVn)) = h{z)/{l - z),

и можно показать, что предельная вероятность равна h{l) = exp(E„>i/(1/п)) = е"* и .56146. В действительности Н. Г. де Брейн (N. G. de Bruijn) установил, что асимптотическая формула имеет следующий вид: limp-юо Опр = е~ +е~/п + 0{п~ log п). [См. D. Н. Lehmer, Acta Arith. 21 (1972), 379-388; D. Н. Greene and D. E. Knuth, Math, for the An&lysis of Algorithms (Boston: Birkhauser, 1981), §4.1.6.] С другой стороны, ответ для 1 < п < 10 при р = 2 имеет меньшие значения: 1, , j, j, jg, j, fj, Щ, Щ, Щ. В работе A. Knopfmacher and R. Warlimont, IVans. Amer. Math. Soc. 347 (1995), 2235-2243, показано, что для фиксированного р вероятность составляет Ср -I- 0(1/п), где Ср = Пт>1 е-"(1 + атр/рП и С2 « .397.]

29. Пусть qi{x) и q2{x) - любые неприводимые делители д{х). По китайской теореме об остатках (упр. 3) выбор случайного полинома t(x) степени < 2d эквивалентен выбору двух случайных полиномов ti(x) и t2(x) степени < d каждый, где ti{x) = t(x) modд;(х). Наибольший общий делитель будет корректным множителем, если ti(x)(p modqi(x) = 1 и t2(x)(p~)/2modqi(x) ф 1 или наоборот, и это условие вьшолняется в точности для 2((р - 1)/2){(р + 1)/2) = (р" - 1)/2 выборов <i(x) и <2(х).

Примечания. Здесь рассматривается только поведение с учетом двух неприводимых множителей, но истинное поведение, вероятно, гораздо лучше. Предположим, что каждый неприводимый множитель qi{x) имеет вероятность деления полинома t(x)(p-i)/2 - 1 для каждого t(x) независимо от поведения других qj{x) и t{x); предположим, что д{х) имеет всего г неприводимых множителей. Тогда, если закодировать каждый qi{x) последовательностью нулей и единиц в соответствии с тем, делит qi{x) или нет t(x)(p - 1 для последовательных проверяемых t, можно получить случайный бинарный луч с г "листьями" (см. раздел 6.3). Цена, связанная с внутренним узлом этого луча, который имеет т листьев в качестве потомков, равна 0(m(logp)), а решением рекуррентного соотношения А„ = (j) -- 2~" Е {Ак является An = 2(2) в соответствии с упр. 5.2.2-36. Следовательно, сумма цен данного случайного луча, представляющая ожидаемое время полного разложения д{х), составляет 0(r(logp)) при этих правдоподобных предположениях. Правдоподобность предположений становится абсолютно справедливой при выборе