27. Приложимы идеи упр. 4.3.1-40, но в более простой форме, потому что полиномиальная арифметика не оперирует переносами; деление справа налево использует 4.7-(3). Другой путь заключается в том, чтобы при больших значениях п делить преобразования Фурье коэффициентов с "обратным" использованием упр. 4.6.4-57.

РАЗДЕЛ 4.6.2

1. Для любого выбора к < п различных корней существует р""* нормированных полиномов, имеющих как минимум по одному из этих корней. Поэтому согласно принципу включения и исключения (см. раздел 1.3.3) количество полиномов без линейных множителей составляет Ylk<n (ь)р"~*(~1)*- Частичные суммы этого ряда попеременно больше или меньше его суммы. Требуемые границы можно получить, положив п = 2 и п = 3. При п > р вероятность наличия хотя бы одного линейного множителя составляет 1 - (1 - l/pY- Среднее количество линейных множителей в р раз превышает среднее количество случаев, когда величина х делит полином и(х), так что оно составляет

l+p-l+...+pl-n = Z (l p-n).

[Аналогично находим, что вероятность существования неприводимого множителя степени 2 равна I2fc<n/2 вероятность лежит между - jp" и

I - \р~ при п > 2 и стремится к 1 - е~(1 + jp") + 0{jp~) при п оо. Среднее количество таких множителей равно - .]

Примечание. Пусть и(х) - фиксированный полином с целыми коэффициентами. Петер Вайнбергер (Peter Weinberger) обнаружил, что если и{х) неприводим над кольцом целых чисел, то среднее количество линейных множителей и{х) по модулю р стремится к 1 при р - оо, потому что группа Галуа и{х) транзитивна и среднее количество единичных циклов в случайно выбранном элементе любой группы транзитивных перестановок равно 1. Следовательно, среднее количество линейных множителей и{х) по модулю р равно количеству неприводимых множителей и{х) над кольцом целых чисел при р оо. [См. примечания в ответе к упр. 37, а также Ргос. Symp. Риге Math. 24 (Amer. Math. Soc, 1972), 321-332.]

2. (a) Известно, что u(x) может быть представлен как произведение неприводимых полиномов и что старшие коэффициенты этих полиномов должны быть обратимыми элементами, поскольку они делят старший коэффициент полинома и{х). Поэтому можно считать, что и{х) имеет представление в виде произведения нормированных неприводимых полиномов piixy . ..prixY", где pi{x), ... ,pr{x) различны. Это представление единственно с точностью до порядка множителей, так что условия, налагаемые на и{х), v(x) и w{x), удовлетворяются тогда и только тогда, когда

г;(х) =pi(x)L>/=J ...р„(х)/ ш(х) =pi(x) """ .. р. (х)

mod 2

(b) Производящая функция для количества нормированных полиномов степени п представляет собой 1 + рг + рг + = 1/(1 - рг). Производящая функция для количества полиномов степени п, имеющих вид v{x), где г;(х) - нормированный полином, представляет собой 1 -I- рг + рг + = 1/(1 - рг). Если обозначить производящую функцию для количества нормированных свободных от квадратов полиномов степени п через д{г), то согласно п. (а) этого упражнения 1/(1 -рг) = д{г)/{1 -рг). Следовательно, д(г) = (1 - рг)/(1 - рг) = 1 -I- рг 4- (р - р)г + (р - р)г + Таким образом,

ответ-р" - р"" для п > 2. [Любопытно, что это доказывает, что и{х) ± и{х) с вероятностью 1 - 1/р; это та же вероятность, что и вероятность того, что и{х) ± v{x) в случае независимости и{х) и г;(х) согласно упр. 4.6.1-5.]

Примечание. Аналогично доказывается, что каждый полином и(х) может быть единственным образом представлен в виде г;(х)и;(х), где г;(х) не делится на г-ю степень

никакого неприводимого полинома; количество таких нормированных полиномов v{x) составляет р" - р"~+ при п>г.

3. Пусть и{х) = ui(x)... Ur{x). Имеется не более одного такого полинома v{x) согласно доказательству теоремы 4.3.2С. Существует по меньшей мере один такой полином, если для каждого j можно решить систему с u;j(x) = 1 и u;j;(x) = О при А; ф j. Решением последней является i;i(x) Flitj Uk{x), где гл(х) и V2{x) удовлетворяют соотношению

"Л)и.кф]к{х) + V2{x)uj{x) = 1, deg(i;i) < deg(uj)

согласно расширению алгоритма Евклида (упр. 4.6.1-3).

Над кольцом целых чисел нельзя сделать г;(х) = 1 (по модулю х) и t;(x) = О (по модулю X - 2) при deg(i;) < 2.

4. Исходя из единственности разложения, имеем (1 - рг)" = Пп>1(1 -•?")-""; после взятия логарифмов это соотношение может быть переписано как

1п(1/(1 - рг)) = E.,j>i a-PVJ = Е,>1 Gr,{z)lj.

Из утверждения указания следует ответ Gp{z) = Em>i/("*)"*~- Р")), из которого получаем апр = Erf\n("/)P/"- Таким образом, Ишр-»» а„р/р" = 1/п. Для доказательства утверждения, приведенного в указании, заметим, что

Еп,>1 P{n)9{z-)n-*j- = Е,п>1 9{Пт- Enw Мп) = 9{z). [Числа а„р были впервые найдены Гауссом; см. Werke 2, 219-222.]

5. Пусть апрг - количество нормированных полиномов степени п по модулю р, имеющих в точности г неприводимых множителей. Тогда Qp(z,w) = En г>о"р""- - exp(Efc>i Gp(z)w/k) = ехр(Е„>1 Omu, ln(l/(l - рг""*)); см. формулу 1.2.9~-(38). Имеем

Е„>о -прг" = dGpiz/p, w)/dw „=i = (Е,>1 Gpiz/p)) Gpiz/p, 1)

= (Еп>1 Нт -p-"2"))v(n)/n)/(l - z),

следовательно, Апр = Я„ -Ь 1/2р + 0{р~) для я > 2. Среднее значение 2 равно

[г"] gp{z/p, 2) = п + 1 + (п - 1)/р + 0(пр-2).

(Дисперсия, однако, есть величина порядка п; положите lu = 4.)

6. Согласно теореме Ферма х-в является множителем х*"-х (по модулюр) для О < в < р. Значит, х*" - X кратно 1ст(х - О, х - 1,..., х - (р - 1)) = х£. [Примечание. Следовательно, числа Стирлинга [] кратны р за исключением случаев, когда А; = 1 или А; = р. Формула 1.2.6-(45) показывает, что то же утверждение справедливо и для чисел Стирлинга {} второго рода.]

7. Множители в правой части взаимно просты, и каждый из них является делителем и(х), так что их произведение делит и(х). С другой стороны, и(х) делит

v{x)-v(x) = Uo<s<p{)-)> так что и(х) делит правую часть согласно упр. 4.5.2-2.

8. Вектор (18) является единственным, А;-я компонента которого не равна нулю.

9. Например, начав сх*-1иг/*-1. Затем следует сто раз установить R[x] <- у, X 2х mod 101, у 51г/ mod 101.

10. Матрица Q - I, приведенная ниже, имеет ядро, порожденное двумя векторами г; = (1,0,0,0,0,0,0,0), v = (0,1,1,0,0,1,1,1). Разложение представляет собой

(xV хЧ X + 1)(хЧ X + 1).

/О о о 4 О 2 О 1 2 2 О О

\3 О

р=5 ООО О О 4 3

ON о

4 1 2 2

11. После удаления тривиального множителя х приведенная выше матрица Q - I имеет ядро, порожденное (1,0,0,0,0,0,0) и (0,3,1,4,1, 2,1). Полное разложение полинома таково:

х(х + Зх + 4)(х* + гх" + хЧ 4x4 X + 3).

12. Если р = 2, (х + l)"* = х"* + 1. Если р = 8А; + 1, Q - I представляет собой нулевую матрицу, а значит, существует четыре множителя. Для других значений р имеем:

р = 8А; + 3 р = 8А; + 5 р = 8А; + 7

/О О О 0\ /О О О 0\ /О О О 0\

0 -1 0 1 0 -2 0 0 0 -1 0 -1

0--=0 0 -2 0 0 0 0 0 0 0 -2 0

\0 1 О -1/ \0 О О -2/ \0 -1 О -l/

Здесь Q - I имеет ранг 2, поэтому есть 4 - 2 = 2 множителя. [Однако легко доказать, что х + 1 неприводим над кольцом целых чисел, поскольку у него нет линейных множителей и коэффициент при х в любом множителе степени 2 согласно упр. 20 должен быть не больше 2 по абсолютному значению (см. также упр. 32, поскольку х + 1 = *8(x)). Г. П. Ф. Свиннертон-Дайер (Н. Р. F. Swinnerton-Dyer) показал, что для всех А; > 2 полиномы степени 2*, неприводимые над кольцом целых чисел, полностью разлагаются на линейные и квадратичные множители по модулю любого простого числа. Для степени 8 в качестве примера он привел полином х* - 1бх® + 88х + 192х + 144, имеющий корни ±\/2 ± \/3 ± t [см. Math. Сотр.24 (1970), 733-734]. Согласно теореме Фробениуса (Frobenius) из упр. 37 любой неприводимый полином степени п, в группе Галуа которого не содержится п-циклов, будет иметь множители по модулю почти всех простых чисел.]

13. Случай, когда р = 8Jfc + 1: (х + (1 + ч/)/ч/2)(х + (1-ч/)/ч/2)(х - (1 + ч/)/ч/2)х (х - (1-\/)/\/2). Случай, когда р = 8Jfc + 3: (х + \/х - \){х -\fx - 1). Случай, когда р = 8А; + 5: (х + у/Ц.){х - v/). Случай, когда р = 8А; + 7: (х + \/2х + 1) х (х - \/2х + 1). Разложение для р = 8А; + 7 также справедливо над полем действительных чисел.

14. Алгоритм N может быть адаптирован для поиска коэффициентов w. Пусть А - матрица размера (r+l) х п, в k-Hi строке которой содержатся коэффициенты г;(х)* mod u(x) для О < А; < г. Будем применять метод алгоритма N до тех пор, пока не будет найдена

первая зависимость на шаге N3; затем алгоритм завершается с w{x) = зд + гххН-----\-VkX,

где Vj определены в (18). В этот момент 2 < А; < г; заранее знать г не нужно, поскольку можно проверять зависимость после создания каждой строки А.

15. Можно считать, что и О и что р нечетно. Из метода Берлекампа, примененного к полиному х - и, следует, что квадратный корень существует тогда и только тогда.