11.3. Общие свойства линеаризированных и аффинных многочленов

В этом разделе мы докажем общие свойства аффинных многочленов. В последующих разделах настоящей главы будут даны приложения этих результатов к некоторым вопросам теории кодирования. Основные идеи всех результатов данного раздела принадлежат Оре [1933, 1934], хотя многие из этих теорем были недавно независимо передоказаны несколькими специалистами по теории кодирования.

11.31. Теорема. Многочлен является линеаризированным тогда и только тогда, когда его корни образуют линейное пространство над и все имеют одну и ту же кратность, равную степени числа

Замечание. Корни многочлена не обязательно лежат в они могут лежать в некотором расширении этого поля.

Доказательство. Необходимость. Пусть линеаризированный многочлен, его корни, а Тогда следовательно, также корень Значит, корни образуют линейное пространство над

Производная многочлена равна Если то не имеет кратных корней. С другой стороны, если но то

является степенью линеаризированного многочлена без кратных корней. В этом случае кратность каждого корня многочлена равна

Заметим, что если то

Достаточность. Пусть корни многочлена образуют линейное пространство над выберем в нем базис Каждый корень многочлена может быть однозначно записан в виде Для некоторого подходящего набора коэффициентов Не ограничивая общности рассуждений, можно считать многочлен нормированным. Тогда

Положим

Докажем теперь индукцией по что линеаризированный многочлен. Это утверждение очевидно для Пусть линеаризированный многочлен. Тогда

и

Так как линеаризированный многочлен, то его скалярное кратное и его степень также линеаризированные многочлены. Разность двух линеаризированных многочленов является линеаризированным многочленом, поэтому линеаризирован. Следовательно, линеаризированный многочлен и потому линеаризирована и его степень

Аналогичный результат для аффинных многочленов содержится в следующей теореме:

11.32. Теорема. Многочлен является аффинным тогда и только тогда, когда его корни образуют аффинное пространство над [т. е. если — его корни, то и также его корень для любых ] и все имеют одну и ту же кратность, равную степени числа

Доказательство. Пусть — аффинный многочлен. Если корни то корень для каждого Следовательно, значит, корень многочлена Это означает, что корни аффинного многочлена образуют аффинное пространство.

Производная аффинного многочлена и равна коэффициенту . Если то все корни различны. Если же то есть степень аффинного многочлена с различными корнями, и, следовательно, каждый корень имеет кратность

С другой стороны, если корни некоторого многочлена образуют аффинное пространство, то разности этих корней образуют линейное пространство. Согласно теореме 11.31, многочлен, корнями которого служат различные элементы этого линейного пространства, есть линеаризированный многочлен Если произвольный корень то или где Следовательно, корни суть корни многочлена , и так как

кратность каждого корня равна то скалярное кратное многочлена аффинный многочлен,

Различные корни произвольного аффинного многочлена образуют аффинное пространство. Пересечение любых двух аффинных пространств снова является аффинным пространством. Так как общие корни любых двух многочленов являются корнями их наибольшего общего делителя, то н. о. д. двух аффинных многочленов с различными корнями является аффинным многочленом с различными корнями. Более того, н. о. д. многочленов равен н. о. д. многочленов возведенному в наименьшую из степеней или Отсюда, в частности, вытекает теорема 11.331.

11.331. Теорема. Н. о. д. двух аффинных многочленов является аффинным многочленом.

Если нуль — корень двух аффинных многочленов, то нуль является также корнем их н. о. д. Поэтому справедливо следующее утверждение.

11.332. Теорема. Н. о. д. двух линеаризированных многочленов является линеаризированным многочленом.

Если два аффинных многочлена и А делит В, то корни многочлена А образуют подмножество множества корней В. Аффинное пространство корней А является, таким образом, аффинным подпространством пространства корней В. Множество всевозможных разностей корней А (т. е. совокупность всех корней линеаризированной части А) есть подмножество множества всевозможных разностей корней В — т. е. совокупности корней линеаризированной части В (см. доказательство теоремы 11.32). Так как кратность любого корня линеаризированной части аффинного многочлена совпадает с кратностью корней исходного аффинного многочлена, то получаем следующий результат.

11.34. Теорема. Если аффинные многочлены и А делит В, то линеаризированная часть А делит линеаризированную часть В. Обратно если линеаризированные многочлены от делит то делит для любого лежащего в поле коэффициентов

Часто необходимо знать, лежат ли в поле все корни заданного аффинного многочлена . Если делит то все корни лежат в но если не делит то часть корней лежит вне Согласно

теореме делит только если делит Если же делит то и делит тогда и только тогда, когда существует такой элемент что Ясно, что для некоторых и существуют такие элементы что Такие и образуют линейное пространство, называемое ранговым пространством линеаризированного многочлена Если и принадлежит ранговому пространству, то и делит и все корни многочлена и лежат в Если же и не принадлежит ранговому пространству, то не существует такого что и все корни многочлена и лежат вне Вопрос о принадлежности элементов из ранговому пространству заданного линеаризированного многочлена полностью решается следующей теоремой.

11.35. Теорема. Пусть произвольный нормированный линеаризированный многочлен над делящий Тогда существует единственный нормированный линеаризированный многочлен делящий и такой, что:

11.353. Корни лежат в тогда и только тогда, когда

11.354. Корни лежат в тогда и только тогда, когда

Многочлены и будем называть дуальными.

11.355. Пример. Пусть над Тогда

и можно проверить, что

Корни уравнения лежат в тогда и только тогда, когда т. е. когда Корни уравнения лежат в тогда и только тогда, когда т. е. когда и

Вообще над линеаризированные многочлены дуальны друг другу.

11.356. Пример. Рассмотрим более сложный случай для поля полагая а корнем многочлена . Пусть

Установив, что все случаи утверждений 11.353 и 11.354 легко получить как следствия этих равенств; например,

Доказательство теоремы 11.35. Пусть базис пространства корней многочлена и пусть базис поля над Положим

Тогда

и

Это доказывает утверждение 11.351. Равенство

задает разложение многочлена на множители вида и, где каждое и является корнем Это доказывает

утверждение 11.353, а также единственность многочлена, дуального к многочлену так как корневое пространство многочлена, дуального многочлену должно быть ранговым пространством

Для доказательства утверждения 11.352 подсчитаем Так как линеаризированный многочлен над то следовательно, Полагая получаем, что . Это равенство должно быть тождеством относительно у и потому что доказывает утверждение 11.352.

Для доказательства утверждения 11.354 выберем базис в корневом пространстве многочлена и базис Остальная часть доказательства является двойственной к доказательству утверждения 11.353.

Если все коэффициенты линеаризированного многочлена лежат в основном поле то на некоторые вопросы о его свойствах можно ответить с помощью рассмотрения ассоциированного с ним многочлена, определяемого следующим образом.

11.36. Определение. Если для всех , то многочлены называются ассоциированными; линеаризированно ассоциированный с стандартно ассоциированный с

Плодотворность этого определения видна из следующей теоремы:

11.37. Теорема. Если линеаризированные многочлены над стандартно ассоциированные с ними многочлены, то делит тогда и только тогда, когда делит Если то где линеаризированно ассоциированный с

Доказательство. Каждое из равенств

и

справедливо тогда и только тогда, когда Для всех к.

11.38. Следствие. Если линеаризированный многочлен над то делит тогда и только тогда, когда

стандартно ассоциированный с ним многочлен делит Если делит то стандартно ассоциированный с L (дуальным к L) многочлен задается равенством

11.381. Пример. В соответствии с разложением можно записать разложение для линеаризированно ассоциированного многочлена Эти разложения дуальны друг другу.

Используя последнее следствие, можно определить число элементов поля обладающих линейно независимыми сопряженными относительно элементами Если то линейно зависимы тогда и только тогда, когда существуют такие элементы не равные одновременно нулю, что Так как и — корень многочленов и то он является также корнем их н. о. д.

Н. о. д. этих двух линеаризированных многочленов также линеаризирован. Таким образом, все сопряженные с и элементы линейно зависимы тогда и только тогда, когда и является корнем некоторого многочлена делящего

Пусть и н. о. д. , так что различные неприводимые делители многочлена Обозначим через степень многочлена

Ясно, что Максимальный собственный делитель многочлена имеет вид Каждый собственный делитель многочлена делит по меньшей мере один из этих максимальных делителей. Каждому максимальному делителю многочлена соответствует максимальный линеаризированный делитель многочлена а именно Элемент имеет линейно независимых

сопряженных тогда и только тогда, когда он не является корнем ни одного из этих многочленов .

Н. о. д. нескольких максимальных делителей многочлена скажем, равен и имеет степень Соответственно н. о. д. многочленов Ни является линеаризированным многочленом степени Если случайным образом выбирается элемент поля то вероятность того, что он есть корень равна вероятность того, что он является корнем равна а вероятность того, что он одновременно является корнем равна Таким образом, вхождение элемента в качестве корня в независимые события. То же самое можно сказать о д. Вероятность того, что случайно выбранный элемент поля не есть корень равна Применяя теорему умножения вероятностей, заключаем, что вероятность того, что случайно выбранный элемент поля не является корнем ни одного из многочленов равна Это дает теорему 11.39.

11.39. Теорема. Число элементов поля обладающих линейно независимыми сопряженными относительно поля равно

где степени различных неприводимых делителей многочлена над

11.391. Пример. Рассмотрим поле Над

где неприводимый многочлен степени произведение двух неприводимых кубических многочленов. Итак, и число элементов поля имеющих 14 линейно независимых сопряженных относительно элементов, равно Эти элементы лежат в классах сопряженных (над GF(2)) элементов. Существует 448 неприводимых двоичных многочленов 14-й степени, корни которых линейно независимы.

Читатели, относящиеся с недоверием к вероятностной аргументации, использованной в предыдущем доказательстве, могут доказать этот же результат с помощью комбинаторных методов. С нашей точки зрения вероятностный подход делает результат более прозрачным.

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