Введение к работе
Актуальность темы
Данная диссертация относится к компьютерной алгебре, алгебраической теории кодирования и комбинаторике (стандартные базисы над коммутативными цепными кольцами с приложениями в теории полилинейных ре-куррент).
Развитие прикладных аспектов современной алгебры в последние десятилетия связано, в значительной степени, с построением основ теории полилинейных рекуррентных последовательностей и теории линейных кодов над конечными модулями. Возникающие при этом проблемы вычислительного
» характера чаще всего сводятся к необходимости оперирования с полиноми-
альными идеалами над конечными кольцами.
В качестве основных примеров можно указать следующие задачи: вычисление периода (поли-)линейной рекурренты [I]1; построение системы образу-
» ющих и вычисление мощности семейства полилинейных рекуррент с задан-
ным характеристическим идеалом (линейного полициклического кода) J2]2, [З]3, [4]4, [5]5 и описание полилинейных регистров сдвига, генерирующих это семейство [б]6, описание систем образующих и характеристических идеалов суммы и пересечения таких семейств; построение проверочной матрицы линейного циклического кода; решение системы полиномиальных уравнений над кольцом [7]7.
Все эти задачи сводятся к построению "удобных" систем образующих идеалов І в кольце многочленов R[X] = R[x\,..., х к] над конечным кольцом R с единицей, позволяющих достаточно просто проверять принадлежность заданного многочлена идеалу, вычислять мощность факторкольца R[X]/I,
, строить системы образующих суммы и пересечения идеалов, радикала иде-
ала и его примарных компонент.
В случае, когда R — поле эти задачи решаются с помощью теории ба-
1 Кузьмин А. С, Куракин В. Л., Нечаев А. А. Псевдослучайные и полилинейные по
следовательности. Труды по дискретной математике, 1, (1997), с. 139-202.
2 Нечаев А А. Линейные рекуррентные последовательности над коммутативными
кольцами. Дискретная Математика, 3, (4) (1991), с. 105-127.
3 Кузьмин А. С, Нечаев А. А., Марков В. Т. Линейные коды над конечными кольцами
и модулями. Фундаментальная и прикладная математика, 3, (1) (1997), с. 195-254.
4 Нечаев А. А. Линейные коды и полилинейные рекурренты над конечными кольцами
и квазифробениусовыми модулями Доклады академии наук, 36, (4) (1995), с 451-454.
5 Kurakin V L , Kuzmin A. S., Mikhalev А. V., Nechaev A. A. Linear recurring sequences
over rings and modules (Contemporary Mathematics and its Applications, Thematic surveys,
10, Algebra 2. Moscow, 1994.) Journal of Mathematical Sciences, 76 (6) (1995), pp. 2793-2915.
6 Нечаев А. А., Михайлов Д. А. Каноническая система образующих унитарного по
линомиального идеала над коммутативным артиновым цепным кольцом Дискретная
математика, 13, (4) (2001) с. 3 42
7 Нечаев А. А., Михайлов Д. А. Решение системы полиномиальных уравнений над
кольцом Галу а-Эйзенштейна с помощью канонической системы образующих полино
миального идеала Дискретная Магематика, 16, (4) (рОЭДЬ сцilj"uh ~
зисов Гребнера-Ширшова основы которой заложили Б. Бухбергер ([8]8) и А. И. Ширшов ([9]9) (см. также [10]10, [II]11, [12]12, [ІЗ]13 , [14]14 , [15]lS).
В общем случае, для решения этих задач, также естественно использовать технику стандартных базисов полиномиальных идеалов, общая теория которых в настоящее время хорошо развита (см., например, [16]16). Однако, попытки использовать стандартные базисы, которые строятся по известным общим алгоритмам, показали, что эти базисы зачастую малоэффективны. Дальнейшие исследования выявили, что для решения поставленных задач нужно строить базисы идеалов, по специально разработанным алгоритмам, учитывающим специфику кольца коэффициентов R ([2, б, 7]).
В диссертации рассматривается случай, когда R — коммутативное конечно-цепное кольцо (наиболее востребованный с точки зрения практических приложений) Любой алгоритм построения стандартных базисов идеалов кольца R[X] основан на некотором линейном и согласованным с умножением упорядочении мономов гх\г ....х' этого кольца. При этом упомянутые выше общие алгоритмы используют лишь порядки, однозначно определяемые набором показателей ii,...,ik, и не учитывают специфику коэффициента г. Стандартные базисы, которые строятся в данной работе, наоборот, основаны на упорядочениях мономов, которые в первую очередь учитывают эту специфику: место идеала rR в конечной цепи идеалов кольца R.
Идея использования таких порядков для построения стандартных базисов с целью решения названных выше прикладных задач была впервые реализована А. А. Нечаевым в [2] для кольца многочленов от одного переменного, и затем развивалась в [6, 7]
Цель Работы
Целью работы является определение и исследование согласованных с нормированием на кольце коэффициентов стандартных базисов идеалов алгебры
8 Buchberger В , Em Algonthmus zum Auffindender Basiselemente des Restklassenrtnges
nach etnem nulldtmensionalen Polynomideal. Ph.D Thesis, Inst. University of Innsbruck,
Innsbruck, Austria, 1965
9 А. И Ширшов, Некоторые алгоритмические проблемы для алгебр Ли, Сибирский
математический журнал, 3, (1962) с. 292-296.
10 Дэвенчорт Д., Сирэ И., Турнье Э. Компьютерная алгебра. М/ Мир, 1991.
11 Компьютерная алгебра Символьные и алгебраические вычисления Под редакцией
Бухбергера Б , Коллинза Д , Лооса Р., М.: Мир, 1986
" Латышев В. Н. Конструктивная теория колец. Стандартные базисы. М.' Изд-во МГУ, 1988.
13 Михалев А. В., Панкратьев Е. В. Компьютерная алгебра. Вычисления в дифферен
циальной и разностной алгебре. М : Изд-во МГУ, 1989.
14 Eisenbud D Commutative Algebra. With a view toward algebraic geometry. Graduated
texts in Mathematics, 150, Berlin: Springer-Verlag, 1995
15 Kondratieva M V , Levin А. В., Mikhalev A. V. and Pankratiev E V Differential and
Difference Dimension Polynomials. Kluwer Academic Publishers, 1999.
18 W Adams, P Loustaunau, An introduction to Grobner bases, Graduate Studies in Mathematics, v. 3, American Mathematical Society, 1994.
коммутативных полиномов над коммутативным артиновым цепным кольцом, а также применение этих базисов к вычислениям в идеалах и рекур-рентах.
Научная новизна
Основные результаты являются новыми и состоят в следующем:
-
Построена теория стандартного базиса полиномиального идеала, согласованного с нормированием на кольце коэффициентов; предложен алгоритм построения этого стандартного базиса (см. алгоритм 1.4.7) (тем самым получила дальнейшее развитие теория канонических систем образующих А. А. Нечаева).
-
С использованием согласованных стандартных базисов получены новые решения следующих классических задач: характеризация минимальных и редуцированных стандартных базисов (см. теорему 1.5.12), вычисление мощностей факторов кольца полиномов, эффективное построение систем образующих модуля сизигий, идеала элиминации, пересечения и частного идеалов (см. разделы 2.2 и 2.3).
-
Найден алгоритм проверки того, что семейство линейных рекуррент является циклическим (факторкольцо является квазифробениусовым) (см. алгоритм 3.2.6).
-
Найдены новые условия, определяющие, когда данные диаграмма Фер-ре Т и полная система ^"-унитарных полиномов образуют регистр сдвига (см. теорему 3.3.9). Определены и изучены цилиндрические идеалы (см. теорему 3.4.4). На основании этих результатов построена эффективная процедура проверки существования (и нахождения в таком случае) поднятия редуцированного базиса Гребнера унитарного идеала до согласованного стандартного базиса той же мощности (см. предложение 3.4.8).
Основные методы исследования
В работе используются методы и результаты теории модулей, коммутативной алгебры, теории полугрупп, теории рекуррентных последовательностей, техники схем симплификации, компьютерных вычислений.
Практическая и теоретическая ценность
Работа носит как теоретический, так и прикладной характер. Результаты диссертации могут быть использованы в различных задачах теории рекуррентных последовательностей, теории линейных кодов, в задачах компью-
терной алгебры, при создании программных пакетов для вычисления в идеалах и рекуррентах над коммутативными артиновыми цепными кольцами.
Апробация результатов
Основные результаты диссертации докладывались на научно исследовательском семинаре и семинаре "Кольца и модули" кафедры высшей алгебры МГУ; на конференции по математике и безопасности информационных технологий (Москва, Россия, 2003 г.); на девятых математических чтениях МГСУ (Руза, Россия, 2003 г.); на международной алгебраической конференции посвященной 250-летию московского университета (Москва, Россия, 2004 г.). На основе полученных результатов разработан пакет программ "Polynom" для вычислений в алгебре полиномов над коммутативными конечно-цепными кольцами.
Публикации
Основные результаты опубликованы в 3 работах, список которых приведен в конце автореферата.
Структура диссертации
Диссертация состоит из оглавления, введения, трех глав, приложения, списка литературы, предметного указателя, и указателя обозначений. Полный объем диссертации — 139 страниц, библиография включает 32 наименования.
