19.2. ВВЕДЕНИЕ В ТЕОРИЮ ИНВАРИАНТОВ

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

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

(ибо - однородный многочлен степени Так как веса всех кодовых слов делятся на 4, то содержит только степени Следовательно,

где Задача, которую мы хотим решить, заключается в отыскании всех многочленов удовлетворяющих уравнениям (19.7) и (19.8).

Инварианты. Уравнение (19.7) говорит о том, что многочлен не изменяется, или инвариантен, при следующем линейном преобразовании:

или в матричных обозначениях:

Аналогично уравнение (19.8) говорит о том, что инвариантен также относительно преобразования

или

Конечно, как следствие многочлен должен быть инвариантным относительно любой комбинации этих преобразований. Нетрудно показать (как мы увидим в § 19.3), что матрицы

при умножении друг на друга всеми возможными способами порождают группу состоящую из 192 матриц.

Поэтому наша задача звучит теперь так: найти все многочлены которые инвариантны относительно преобразований, задаваемых всеми 192 матрицами группы

Сколько существует инвариантов? Первое, что мы хотим выяснить — это сколько существует инвариантов. Этот вопрос поставлен не совсем строго, так как, конечно, если инварианты, то инвариантами являются и любое их скалярное кратное и также сумма разность и произведение Кроме того, нам достаточно изучить только однородные инварианты (у которых все одночлены имеют одинаковую степень).

Поэтому правильно так поставить вопрос: сколько существует линейно независимых, однородных инвариантов заданной степени Обозначим это число через

Чтобы было удобнее оперировать с числами представим их в виде степенного ряда или производящей функции

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

Сейчас мы приведем замечательную теорему Молина, опубликованную в 1897 г. ([971], Бурбаки [190, с. 138], Бернсайд [211, с. 301], Миллер и др. [955, с. 259]).

Теорема 2. Для любой конечной группы комплексных -матриц определяется выражением

где число матриц в группе обозначает определитель и I — единичная матрица. Другими словами, функция равна усредненному по всем матрицам А из группы многочлену, обратному

Назовем рядом Молина группы Доказательство этой теоремы приводится в § 19.3.

Для нашей группы состоящей из матриц, соответствующих преобразованиям получаем, что

Можно сократить выкладки, но вполне допустимо иметь дело непосредственно со всеми 192 членами этого ряда (многие из них совпадают) и складывать их. Результат удивителен: окончательное выражение имеет вид

Интерпретация Очень простой вид выражения (19.11) позволяет нам высказать некоторые предположения. Разлагая по степеням X, мы имеем:

Одно следствие мы можем вывести сразу: равно нулю, если не кратно , т. е. степень однородного инварианта должна быть кратна . (Это уже доказывает тот факт, что длина четного самодуального кода делится на .) Но мы можем сказать больше. Правую часть выражения (19.12) мы могли бы найти точно, если бы мы имели два «базисных» инварианта степени 8 и 24 таких, что все инварианты получались бы из них сложением и умножением.

Эти два инварианта, степени степени 24, породили бы следующие инварианты:

При условии, что все произведения линейно независимы, что эквивалентно алгебраической независимости числа а в формуле (19.13) точно равны коэффициентам ряда

что согласуется с (19.11). Поэтому если мы можем найти два алгебраически независимых инварианта степеней 8 и 24, то мы решим нашу задачу. Ответ будет таков: любой инвариант этой группы является многочленом от Далее весовые функции кодов Хэмминга и Голея имеют степени 8 и 24 и инвариантны относительно этой группы. Поэтому мы можем выбрать (Нетрудно проверить, что они алгебраически независимы.) На самом деле, удобнее работать с инвариантом

чем с самим инвариантом Таким образом, мы доказали следующую теорему, открытую Глисоном в 1970 г.

Теорема За. Любой инвариант группы является многочленом от (выражение и (выражение (19.15)).

Это дает нам решение также и нашей первоначальной задачи.

Теорема Любой многочлен, удовлетворяющий уравнениям (19.7) и (19.8), является многочленом от и

И, наконец, мы охарактеризовали весовую функцию четного самодуального кода.

Теорема 3с. (Глисон [486].) Весовая функция любого четного самодуального кода является многочленом от

Другие доказательства этой теоремы даны Берлекэмпом и др. [129], Бруе и Энгехардом [201] и Фейтом [424] (см. также Ассмус и Мэттсон [47]). Но приведенное здесь доказательство

представляется наиболее содержательным и наиболее легким для понимания и обобщения.

Заметим, что показатели 8 и 24 в знаменателе выражения (19.11) помогли нам угадать степени базисных инвариантов.

Такая ситуация типична, что побуждает использовать этот метод. Начинаем с группы матриц вычисляем сложную с виду сумму, представленную в выражении (19.9), и упрощаем результат. Все сложности чудесным образом пропадают, оставляя окончательное выражение, похожее на формулу (19.11) (хотя не всегда столь простое — точный вид окончательного выражения приводится в § 19.3). Это выражение подсказывает нам, как найти степени базисных инвариантов.

Упражнение. (3). (Глисон [486; 129, 883].) Используя описанный выше метод, показать, что весовая функция любого двоичного самодуального кода представляет собой многочлен от и

[Указание. Согласно упражнению (38) гл. 1 веса всех кодовых слов должны делиться на 2. Группа, порожденная преобразованием и преобразованием, задаваемым матрицей

имеет порядок 16 и ряд Молина ]

Нахождение базисных инвариантов. В общем случае нахождение базисных инвариантов является более простой задачей, чем нахождение функции При этом можно либо использовать весовые функции кодов, обладающих подходящими свойствами, как в описанном выше примере, либо находить базисные инварианты усреднением, используя следующий простой результат (доказанный в § 19.3).

Теорема 4. Если произвольный многочлен от переменных и 9 — конечная группа -матриц, то многочлен

является инвариантом, где обозначает многочлен, полученный применением преобразования А к переменным многочлена

Конечно, может равняться нулю. Ниже будет приведен пример использования этой теоремы.

Применение теоремы 3. Чтобы показать силу теоремы Зс, воспользуемся ею для нахождения весовой функции -кода Согласно теоремам 7, 8, 25 гл. 16 это четный самодуальный код с минимальным расстоянием 12. Следовательно, весовая

функция этого кода, представляющая собой однородный многочлен степени 48, имеет вид:

Коэффициенты при равны нулю. Здесь неизвестное нам число кодовых векторов веса 12. Замечательно, что раз мы знаем выражение (19.17), то весовая функция кода полностью определяется теоремой ибо теорема утверждает, что должен быть многочленом от . А так как однородный многочлен степени однородный многочлен степени однородный многочлен степени 24, то этот многочлен должен быть линейной комбинацией многочленов

Таким образом, теорема утверждает, что

для некоторых действительных чисел Раскрывая выражение (19.18), имеем

и, приравнивая коэффициенты в выражениях (19.17) и (19.19), получаем, что

Следовательно, определяется единственным образом. Подставляя значения в выражение (19.18), находим, что

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

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

Очень простой пример. Согласно теореме 13 гл. 5 весовая функция самодуального кода над GF(q) удовлетворяет уравнению

Задача: найти все многочлены, удовлетворяющие уравнению (19.21).

Для решения этой задачи поступаем, как и прежде. Уравнение (19.21) утверждает, что многочлен должен быть инвариантным относительно преобразования

где

Далее и поэтому должен быть инвариантным относительно группы , состоящей из двух матриц 1 и А.

Чтобы узнать, сколько инвариантов существует, вычислим ряд Молина воспользовавшись выражением (19.9). Находим, что

что даже проще, чем формула (19.11). Формула (19.23) говорит о том, что могут существовать два базисных инварианта степеней 1 и 2 (показатели степеней знаменателя). Если мы сможем найти алгебраически независимые инварианты степеней 1 и 2, скажем, то из выражения (19.23) получим, что любой инвариант группы является многочленом от

На этот раз для нахождения базисных инвариантов мы воспользуемся методом усреднения. Усредним многочлен по группе, т. е. применим теорему 4 к многочлену Матрица 1 оставляет х, конечно, без изменения, а матрица А преобразует Следовательно, среднее

является инвариантом. Конечно, при умножении на любое число снова получается инвариант, и поэтому мы можем разделить на число ( и выбрать

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

Чтобы упростить это выражение, вычтем из него многочлен (который, конечно, также является инвариантом) и разделим на соответствующую константу. Полученный таким образом многочлен и представляет собой желаемый базисный инвариант степени 2.

Наконец, надо показать, что алгебраически независимы: для этого надо показать, что ни одна из сумм вида

не равна тождественно нулю (где комплексные числа, не равные одновременно нулю) при разложении по степеням Это можно увидеть, рассматривая старшие члены. (Старшим членом многочлена является член, который выписывается первым при использовании естественного упорядочения, иллюстрируемого выражениями (19.15), (19.20), (19.24).) Таким образом, старшим членом является х, старшим членом является а старшим членом является Так как различные слагаемые в сумме (19.25) имеют различные старшие члены, то эта сумма может равняться нулю, только если все коэффициенты справны нулю. Следовательно, алгебраически независимы.

Итак, мы доказали следующую теорему.

Теорема 5. Любой инвариант группы или, что эквивалентно, любой многочлен, удовлетворяющий уравнению (19.21), или, что эквивалентно, весовая функция любого самодуального кода над GF(q) представляет собой многочлен от

В этом месте читатель должен воскликнуть: «Стоп!» и указать, что самодуальный код всегда имеет четную длину и поэтому каждый член в весовой функции должен иметь четную степень. Но в теореме имеет степень 1.

Таким образом, мы использовали не все, что мы знаем о коде. Весовая функция должна также быть инвариантна относительно преобразования:

где

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

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

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

Теорема 6. Весовая функция любого самодуального кода над GF(q) является многочленом от

Общий план решения. Как показали рассмотренные нами примеры, решение поставленной задачи с помощью теории инвариантов распадается на два этапа.

Этап I. Превращение условий задачи (т. е. свойств кода) в алгебраические ограничения на многочлены (т. е. на весовые функции)

Этап II. Использование теории инвариантов для нахождения всех возможных многочленов, удовлетворяющих этим ограничениям.