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

Горбатов, Евгений Владимирович

Стандартные базисы, согласованные с нормированием, и вычисления в полилинейных рекуррентах тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Горбатов, Евгений Владимирович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2004 ГОД ЗАЩИТЫ

01.01.06 КОД ВАК РФ

Диссертация по математике на тему «Стандартные базисы, согласованные с нормированием, и вычисления в полилинейных рекуррентах»

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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА

Механико-математический факультет

На правах рукописи УДК 512.714+519.725

Горбатов Евгений Владимирович

СТАНДАРТНЫЕ БАЗИСЫ, СОГЛАСОВАННЫЕ С НОРМИРОВАНИЕМ, И ВЫЧИСЛЕНИЯ В ПОЛИЛИНЕЙНЫХ РЕКУРРЕНТАХ

01.01.06 математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2004

Работа выполнена на кафедре высшей алгебры механико-математического факультета Московского государственного университета им. М. В. Ломоносова.

Научные руководители:

доктор физико-математических наук, профессор А. В. Михалев

доктор физико-математических наук, профессор А. А. Нечаев

Официальные оппоненты: доктор физико-математических наук,

доцент И. Б. Кожухов

доктор физико-математических наук, профессор А. С. Кузьмин

Ведущая организация: Математический институт

им. В. А. Стеклова РАН

Защита диссертации состоится к Нар ГО_ 2004 г. в 16 ч. 15 мин.

на заседании диссертационного совета Д.501.001.84 в Московском Государственном Университете им. М. В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан . ¿1 февраля 2004 г.

Ученый секретарь диссертационного совета Д.501.001.84 в МГУ доктор физико-математических наук, профессор

В. Н. Чубариков

W-ч ИМ MÍ/

Общая характеристика работы

Актуальность темы

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

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

В качестве основных примеров можно указать следующие задачи: вычисление периода (поли-)линейной рекурренты [I]1; построение системы образующих и вычисление мощности семейства полилинейных рекуррент с заданным характеристическим идеалом (линейного полициклического кода) |2]2, [З]3, [4]4, [5]5 и описание полилинейных регистров сдвига, генерирующих это семейство [б]6, описание систем образующих и характеристических идеалов суммы и пересечения таких семейств; построение проверочной матрицы линейного циклического кода; решение системы полиномиальных уравнений над кольцом [7]7.

Все эти задачи сводятся к построению "удобных" систем образующих идеалов I в кольце многочленов = Я[х1, ...,£&] над конечным кольцом 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., Mikhaiev А. V., Nechaev A. A. Ltnear 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) (p*V¿fe.cH¡ÍlxftbНАЛЬН~

I БИБЛИОТЕКА АЯI

, ' ¿"reí i

зисов Гребнера-Ширшова основы которой заложили Б. Бухбергер ([8]®) и А. И. Ширшов ([9]9) (см. также [10]10, [И]11, [12]12, [13]13 , [14]14 , [15]»).

В общем случае, для решения этих задач, также естественно использовать технику стандартных базисов полиномиальных идеалов, общая теория которых в настоящее время хорошо развита (см., например, [16]16). Однако, попытки использовать стандартные базисы, которые строятся по известным общим алгоритмам, показали, что эти базисы зачастую малоэффективны. Дальнейшие исследования выявили, что для решения поставленных задач нужно строить базисы идеалов, по специально разработанным алгоритмам, учитывающим специфику кольца коэффициентов R ([2, б, 7]).

В диссертации рассматривается случай, когда R — коммутативное конечно-цепное кольцо (наиболее востребованный с точки зрения практических приложений) Любой алгоритм построения стандартных базисов идеалов кольца ñ[X] основан на некотором линейном и согласованным с умножением упорядочении мономов гх\г этого кольца. При этом упомянутые выше общие алгоритмы используют лишь порядки, однозначно определяемые набором показателей ii,...,ik, и не учитывают специфику коэффициента г. Стандартные базисы, которые строятся в данной работе, наоборот, основаны на упорядочениях мономов, которые в первую очередь учитывают эту специфику: место идеала rR в конечной цепи идеалов кольца R.

Идея использования таких порядков для построения стандартных базисов с целью решения названных выше прикладных задач была впервые реализована А. А. Нечаевым в [2] для кольца многочленов от одного переменного, и затем развивалась в [6, 7]

Цель Работы

Целью работы является определение и исследование согласованных с нормированием на кольце коэффициентов стандартных базисов идеалов алгебры

8 Buchberger В , Em Algorithmus zum Auffindender Bastselemente des Restklassenrmges nach einem nulldimensionalen Polynomideal. Ph.D Thesis, Inst. University of Innsbruck, Innsbruck, Austria, 1965

9 А. И Ширшов, Некоторые алгоритмические проблемы для алгебр Ли, Сибирский математический журнал, 3, (1962) с. 292-296.

10 Дэвенпорт Д., Сирэ И., Турнье Э. Компьютерная алгебра. М/ Мир, 1991.

11 Компьютерная алгебра Символьные и алгебраические вычисления Под редакцией

Бухбергера Б , Коллинза Д , Лооса Р., М.: Мир, 1986

13 Латышев В. Н. Конструктивная теория колец. Стандартные базисы. М.' Изд-во МГУ, 1988.

13 Михалев А. В., Панкратьев Е. В. Компьютерная алгебра. Вычисления в дифференциальной и разностной алгебре. M : Изд-во МГУ, 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.

Ie W Adams, P Loustaunau, An introduction to Gröbner bases, Graduate Studies in Mathematics, v. 3, American Mathematical Society, 1994.

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

Научная новизна

Основные результаты являются новыми и состоят в следующем:

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

2. С использованием согласованных стандартных базисов получены новые решения следующих классических задач: характеризация минимальных и редуцированных стандартных базисов (см. теорему 1.5.12), вычисление мощностей факторов кольца полиномов, эффективное построение систем образующих модуля сизигий, идеала элиминации, пересечения и частного идеалов (см. разделы 2.2 и 2.3).

3. Найден алгоритм проверки того, что семейство линейных рекуррент является циклическим (факторкольцо является квазифробениусовым) (см. алгоритм 3.2.6).

4. Найдены новые условия, определяющие, когда данные диаграмма Фер-ре Т и полная система ^-унитарных полиномов образуют регистр сдвига (см. теорему 3.3.9). Определены и изучены цилиндрические идеалы (см. теорему 3.4.4). На основании этих результатов построена эффективная процедура проверки существования (и нахождения в таком случае) поднятия редуцированного базиса Гребнера унитарного идеала до согласованного стандартного базиса той же мощности (см. предложение 3.4.8).

Основные методы исследования

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

Практическая и теоретическая ценность

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

Апробация результатов

Основные результаты диссертации докладывались на научно исследовательском семинаре и семинаре "Кольца и модули" кафедры высшей алгебры МГУ; на конференции по математике и безопасности информационных технологий (Москва, Россия, 2003 г.); на девятых математических чтениях МГСУ (Руза, Россия, 2003 г.); на международной алгебраической конференции «освященной 250-летию московского университета (Москва, Россия, 2004 г.). На основе полученных результатов разработан пакет программ "Polynom" для вычислений в алгебре полиномов над коммутативными конечно-цепными кольцами.

Публикации

Основные результаты опубликованы в 3 работах, список которых приведен в конце автореферата.

Структура диссертации

Диссертация состоит из оглавления, введения, трех глав, приложения, списка литературы, предметного указателя, и указателя обозначений. Полный объем диссертации — 139 страниц, библиография включает 32 наименования.

Краткое содержание работы

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

Пусть X — {xi,... ,Хк}, к ^ 1 — множество переменных и [X] = [xi,..., Xk] — полугруппа коммутативных мономов над X. Пусть также R — некоторое коммутативное кольцо Полугруппой одночленов называется подполугруппа [R, А"] = { аи | а G R, и € [X] } полугруппы ( , •). Порядок на [Я, X] назовем разделяющим мономы, если для любых а, Ь € R\0 и и, v е [X], и ф v

аи -< bv или bv -< аи.

Если =<: - разделяющий мономы порядок, то во множестве одночленов произвольного полинома F 6 Я[Л"]\0 найдется наибольший относительно одночлен — ведущий член полинома F относительно =<:. Разделяющий мономы порядок ^ назовем мультипликативным если для любых F 6 R[X] и U €

lt^(FiZ) = \t^(F)U.

Доказывается, что если на [Я, X] существует мультипликативный порядок, то идеалы вида Ап(а), а € Я образуют цепь в решетке всех идеалов Я. Обратно, если идеалы этого вида образуют цепь, и для любых а, Ь, с € Я

(Ап(Ь) С Ап(о) & 6с ф 0) => Ап(Ьс) С Ап(ас),

то на [Л, X] существует мультипликативный порядок.

Устанавливается, что если кольцо Я — квазифробениусово (наиболее востребованный для приложений в теории кодирования случай), то на [Я, X] существует мультипликативный порядок в точности если Я — коммутативное артиново цепное кольцо. При этом мультипликативный порядок на [Я, X] может быть задан соотношением

, Ле/ Г Яа С Я6 или аи^Ьь <=4> { (1)

I Яа = ЯЬ и и ^ V

(для некоторого допустимого порядка ^ на полугруппе мономов [X]). Этот порядок согласован с нормой

||г|| = шах{ г € О^п | г € гас1(Я)' }

на Я (здесь п — индекс нильпотентности радикала Джекобсона га<3(Я)), в том смысле, что I/ ^ V => ||{У|| ^ ||У||.

Функция ведущего члена отвечающая этому порядку обозначается Пл. Именно эта функция использовалась в [2, б, 7] при построении канонических систем полиномов.

Определение ([12]) Пусть (М, ^) — непустое, упорядоченное множество с условием минимальности и 5 С Мм. Тройка 6 = (М, , 5) называется схемой симплификации на М если выполнено условие:

Ут е М Уз € Б : в(т) =<: т.

Говорят, что т 6 М — нормальный или редуцированный элемент (относительно 6) если У$ 6 5 : я (т.) — т. Совокупность всех нормальных элементов обозначается Л/е-

Пусть 5 — подполугруппа в полугруппе Мм (с композицией функций в качестве умножения), порожденная 5 и {1м}- Для любого элемента т е М множеством нормальных форм называется

1Чоге(т) = 5(т)

Определение Пусть Я — кольцо, М = Мд — правый модуль и Р(М) — множество всех подмножеств М. Схему симплификации 6 = (Л/, , 5) будем называть консервативной на Мд, если определено отображение ¡5 : Р{М) -У Р(5), 6 : х такое что Ух £ МУз € 5Х:

х — зх € *Я.

Это отображение называется отображением сечения.

Множество С /1 назовем &-стандартным базисом подмодуля А если

Wae А: Norex(а) Э 0.

Для коммутативного артинового цепного кольца R следующим образом строятся две консервативные схемы симплификации 0 и вг на Я[Х]д[х] ■

Построение схемы симплификации <0 = (Я[Х], , S). Зафиксируем некоторый элемент ж 6 rad(Ä) \ [rad(ß)]2. Всякий элемент а € R можно представить в виде а = ao7rlla", где а0 € Д*.

Любой полином F € Я[Х] \ 0 представляется в виде:

F = aoTraoUo + ...+amiTa™um, (2)

где о, g Д*, а, € 0,n- 1, и, - попарно различные мономы из [X] и жа°ио У ... У жатит (в смысле порядка (1)).

Пусть G € ß[X] и G = Ьож vq -(- ... + ЬТж0г vr — представление аналогичное (2), тогда, по определению, F -< G если существует индекс i е 0,min(m,r) такой, что жа°ио = ■■■, жа,-1иг-1 = и

жа'и, -< ж Vi, или если m < г и жа°ио = ж^Уо, ..., жатит — ж0тьт. Иными словами, порядок -< на Я[Х] сводится к лексикографическому сравнению слов получающихся из полиномов выписыванием составляющих их одночленов по убыванию.

Пусть G 6 Я[Х]\0 и и G [X], тогда Lt(uG) = uLt(G) - auv, где а Е R и v 6 [X]. Пусть F £ Я[Х] и с — коэффициент при мономе uv в F, действие 1

редукции га,и на F определяется следующим образом:

Г F если с $ Ra,

rcAF) =

( F — buG если с е Ra и с = Ьа.

В схеме © выбираем S — {го,и | G € R[X]\0, и е [X]}; отображение сечения задается равенством Sx — { г о,и | G € и 6 [X] }.

Построение схемы симплификации = (Я[Х], =<1г , Sr ). Пусть Г — семейство представителей классов вычетов R по ttR = rad(/?). Тогда для любого с е R существует единственный вектор (со, С\,..., cn_i) G Г™, такой что

с = Со + 7ГС1 + . . . + 7ГП_1С„_1. (3)

Порядок =<!г на R[X] из схемы симплификации ®г определяется как и

, исходя из представления полинома F в виде (2), в котором, однако, выбираются аг 6 Г, аг б 0, п — 1 и мономы иг — не обязательно различны.

Пусть G G R[X]\0 такой, что Lt(G) = жаг>, v € [X] и U = ж0и, где и е [X], тогда Lt(UG) = ULt(G) = жа+^иу. Пусть F 6 Я[Х] и с - коэффициент при мономе uv в F, если са+р — элемент из Г стоящий при жа+0 в

разложении (3), то действие редукции г^ у на ? определяется следующим образом:

= Р- Сс+рив.

В схеме бг выбираем 5Г = { и \ в 6 Я[Х]\0, и = тгаи, и 6 [Л"]}; отоб-ражспис сечения задается равенством = = {»•£,(/ |<?6Х, и = каи,иб[Х]}.

Доказывается, что схемы симплификации б и вг эквивалентны, то есть, что для любого идеала из Я{Х] классы 0- и вг-стандартных базисов совпадают. Эти базисы названы стандартными базисами согласованными с нормой или, короче, согласованными стандартными базисами.

Для эффективного построения согласованных стандартных базисов, как и в классическом случае, вводится понятие Б-полинома.

Пусть У.бе ЩХ] и ЩГ) = ажаи, 1Л(С) = Ьп0у, где а,Ь е Я*, а,0 € О, п — 1 и и,у £ [X]. Пусть ш = НОД (и, ь) е [X] и ) = тах{а,/3}. 5-полиномом от Р и С называется полином

7Г Чц]

3{Г'С) = ЩЩР - Щс)с-

Доказана теорема, являющаяся аналогом леммы о композиции из теории базисов Гребнера над полями.

Теорема 1. Пусть х — непустая система полиномов из идеала I кольца тогда следующие утверждения эквивалентны:

(a) X ~ стандартный базис идеала I.

(b) х — ®Г-стандартный базис идеала I.

(c)ЧРе1:ЭОеХ ЩР)-

(й) I = (х) и УСЬС2 е X : N0^(5(0!, в2)) = 0(Э 0).

(е) I — (х) и — схема симплификации с канонизацией, то есть любой полином Р 6 Д[АГ] имеет единственную нормальную форму относительно «г.

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

В условии (е) теоремы 1 схему симплификации ©г нельзя заменить на 0. В этом состоит ключевое различие этих схем симплификации.

Определение Пусть © = (М, ^ , 5) — консервативная схема симплификации на Ма. Систему х С М назовем &-редуцированной если для любого элемента т, € х:

(¡) тп является ©-самонормальным, то есть для любой редукции э 6 5{т} или згп — тп или втп - О

(ii) m нормален относительно схемы симплификации

Доказана следующая теорема

Теорема 2. Пусть I — ненулевой идеал в тогда;

(a) Любой &-редуцированный стандартный базис является минимальным.

(b) Любой 6Г-редуцированный стандартный базис является &-редуциро-ванным.

(c) Идеал I обладает единственным Й5Г -редуцированным стандартным базисом (с точностью до умножения составляющих этот базис полиномов на обратимые элементы из R).

Во второй главе были решены некоторые классические вычислительные задачи в идеалах кольца R[X\.

В предложении 2.1.1 приводится полная система представителей различных классов вычетов в IjJ для любых идеалов I и J из При этом для каждого F 6 7 представитель из класса вычетов F + J может быть найден эффективно по F. Это предложение позволяет определить формулу для мощности I/J (когда она конечна) и обобщить результат из [5], где была вычислена мощность факторкольца R[X]/I.

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

Пусть даны два множества переменных X — (rri, . и Y =

{yi,...,yi} Пусть также дан идеал I < Y] = Ä[a?i,.. ,хк;уи... ,yt] Задача элиминации состоит в нахождении множества образующих идеала Ix = /ПЛ[Х]< Д[Х] исходя из множества образующих идеала I. В пункте 2.3 изложен алгоритм решающий данную задачу. Следует заметить, что этот алгоритм существенно отличается от классического алгоритма элиминации для полей.

Далее изучается связь согласованных стандартных базисов с канонической системой образующих (КСО) из [7]. Доказывается (предложение 2.4.2), что всякая каноническая система образующих является согласованным стандартным базисом.

На основе условия (d) теоремы 1 строится алгоритм вычисляющий согласованный стандартный базис полиномиального идеала по произвольной системе образующих (см. алгоритм 1.4.7). При этом существенным образом используется, развитая в первой главе, техника стандартных базисов (в частности S-полиномы). С использованием этого алгоритма построена эффективная процедура вычисления канонической системы образующих идеала, которой не было предложено в [2,6,7].

Указанные алгоритмы были реализованы программно и вошли в пакет приложений "Polynom".

В начале третьей главы излагаются необходимые, известные из [1], [5], [17]17, определения и результаты теории полилинейных рекуррент.

Пусть В — произвольное кольцо и M в — правый В-модуль. Множество Мдк> всех к-последовательностей д: N* -v Mb над Mb естественным образом наделяется структурой В[Х]-модуля, при этом ^-последовательность fi называется к-линейной рекуррентной последовательностью (k-ЛРП), если ее аннулятор рв[Х\ iß) — I есть правый унитарный идеал (для каждого s £ 1,к существует унитарный полином Fa(x) € В[х] такой, что F„{xs) € I).

Семейство L\f(I) всех fc-ЛРП аннулирующих идеал I есть В[Х}-подмодуль в Mgk>. Хорошо известно, что это — циклический модуль в случая, когда к = 1, В — поле и Mg = Вв- В работе [2], для случая, когда к — 1

I ий- коммутативное артиново цепное кольцо, был дан критерий циклич-

ности семейства Ьц(1) и поставлена задача об обобщении этого критерия на случай многих переменных. Следующая теорема дает решение этой задачи.

^ Теорема 3. Пусть R — коммутативное артиново кольцо, Q r — квазиф-

робениусов модуль и /<Ш[Х] — унитарный идеал. Тогда следующие условия эквивалентны.

(a) Семейство Lq(T) является циклическим 11{Х}-модулем.

(b) Факторкольцо R[X]/I является квазифробениусовым.

(Здесь \fr= {Fe R[X] | 3t 6 N: F* € / } - радикал идеала T.)

t Теорема 3 представляет обобщение критерия П. Лю [18]18, который был

доказан для случая одной переменой (k = 1) и коммутативного артинова цепного кольца R. Данное доказательство значительно короче, так как использует хорошо известные свойства квазифробениусовых колец.

С использованием критерия 3 и методов согласованных стандартных базисов, для коммутативного артинова цепного кольца R построен алгоритм проверки цикличности семейства Lr(I) по произвольной системе образующих идеала I.

Произвольное конечное подмножество / С N' называется диаграммой Ферре если

17 Kurakin V. L., Mikhalev A. V., Nechaev A. A , and Tsypyschev V. N. Linear and polylinear recurring sequences over Abehan groupa and modules. Journal of Mathematical Sciences,, 102, (6) (2000), pp 4598-4626.

18 I.u P Z A criterion for annihilating ideals of linear recurring sequences over Galois rings. AAKCC-417, 11, (2) (2000).

где порядок ^ на М* определяется определяется формулой

Пусть Т — диаграмма Ферре и х ~ система полиномов из =

ñ[a;i,... , ж/t]. Пара (Xj?) называется к-линейным регистром сдвига или Т-линейным регистром сдвига над модулем Mr если и только если, гомоморфизм

(Tf. LM{x) о-(ц) = ц\jr

является изоморфизмом. При этом семейство последовательностей LM(x) называется множеством рекуррент порожденных регистром сдвига (х , Т).

Пусть ls s-я строка единичной матрицы размера к. Внутренностью, внутренней границей, внешней границей диаграммы Ферре Т С. в направлении ls, 8 £ 1, к назовем соответственно множества

Т, = {reT\r + laeT},

= Т\ТВ,

А,Т = двТ+1в,

Объединение AT — U AST называется внешней границей диаграммы

е=1

Ферре Т. Полином Н € В[Х\ называется Т-унитарным если для некоторого re AT

Н — хГ - hix*. (4)

ier

Множество Ф С В[Х] из \АТ\ полиномов называется полной системой Т-унитарных полиномов если для каждого г g AT эта система содержит единственный полином вида (4).

.Т-"-линейный регистр сдвига (х > Т) называется каноническим Т-линейным регистром сдвига если х ~~ полная система ^-унитарных полиномов. В работе [17] доказывается, что множество последовательностей порожденных любым регистром сдвига порождается некоторым каноническим регистром сдвига (возможно над большим кольцом).

В [17] была поставлена задача описания условий на коэффициенты полиномов из Xi ПРИ которых пара (х, Т) есть канонический регистр сдвига. Решение дает следующая теорема.

Теорема 4. Пусть Т — диаграмма Ферре, Ф — полная система Т-унитарных полиномов из В[Х) up — pg(M) — аннулятор модуля М в В. Тогда пара (х, Т) образует Т-линейный регистр сдвига если и только если для любых s,t(rl,k,sjLt выполняются следующие условия:

Для j £ даТ П Tt

Hj+i.+i. = Hfri,xt +

и для j £ даТ П dtT

Hj+l,Xt+ = Hj+ltXs + ^ hj+\i,kH\,+\,.

kedtT нее,?

В общем случае не любая последовательность порожденная регистром сдвига есть к-ЛРП ([17]). Следующая теорема показывает, что последовательность порожденная регистром сдвига над кообразующим Св является fc-ЛРП если кольцо В — нетерово справа.

Теорема 5. Пусть В - нетерово справа кольцо, I — правый идеал в В[Х], Т С Nq — диаграмма Ферре и С в — кообразующий. Тогда если пара (/, Т) является регистром сдвига над Св, то I — унитарный идеал.

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

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

Теорема 6. Для произвольного идеала I <3 Я[Х] следующие условия эквивалентны:

(b) I выделяется прямым слагаемым в R{X]r.

(d) R[X}/I является свободным R-модулем.

(e) жI = /ПтгЯ[Х].

(f) I = 0 или I обладает согласованным стандартным базисом состоящим из не равных 0 по модулю rad(-ft) полиномов.

Следует отметить, чго для унитарного идеала I и канонической системы образующих эквивалентность (d)<t>(f) из теоремы 6 была доказана ранее в [6].

Естественный гомоморфизм v: Я Я = Я/ гас!(Я) стандартным образом продолжается до гомоморфизма колец полиномов Я[Х] —> Я[Х].

Будем говорить, что базис Гребнера iр С Я[Х]\0 поднимается (в H[X]J, если существует стандартный базис х Q Я[Х] такой, что х = и Gi ф G-> для различных G'x, G2 £ X

В [6] была поставлена задача определить всякий ли базис Гребнера поднимается в Я[Х]. В работе получено продвижение в решении этой проблемы,

а именно, доказано, что базис Гребнера х полиномиального идеала над полем вычетов Я поднимается в Я[Х] тогда и только тогда, когда идеал (х) является образом некоторого цилиндрического идеала I < ЩХ].

В [6] доказано, что унитарный идеал I является цилиндрическим если и только если пара (7, Т) образует линейный регистр сдвига, где Т — диаграмма Ферре, такая что

С использованием этого результата, теоремы 4, а также методов решения систем нелинейных алгебраических уравнений над кольцами Галуа из [7], в работе, для случая когда Я — кольцо Галуа, построена эффективная процедура проверки существования (и нахождения в таком случае) поднятия редуцированного базиса Гребнера унитарного идеала до согласованного стандартного базиса той же мощности (см. предложение 3.4.8).

Благодарности

Автор глубоко благодарен своим научным руководителям доктору физико-математических наук, профессору Александру Александровичу Нечаеву и доктору физико-математических наук, профессору Александру Васильевичу Михалеву за постановку задач, детальное обсуждение результатов работы и многочисленные важные замечания.

Работы автора по теме диссертации

1. Горбатов Е. В., Нечаев А. А Критерий цикличности семейства полилинейных рекуррент над С^Р-модулем. Успехи мат наук, 56, (4) (2001), с. 167-168.

В данной статье Горбатову Е. В. принадлежит первоначальное доказательство и основной результат (теорема 2 — критерий цикличности семейства полилинейных рекуррент). Нечаеву А. А. принадлежат постановка задачи (обобщение результатов Р. Ьи на случай полилинейных рекуррент над С^Е-модулем), идея использования леммы Дьёдонне (ссылка на (следствие 13.4-3 из [6/, при доказательстве заглавной теоремы), и некоторые окончательные формулировки.

2. Горбатов Е. В. Стандартный базис полиномиального идеала над коммутативным артиновым цепным кольцом. Дискретная математика, 16, (1) (2004), с 52-78.

3. Горбатов Е. В. Стандартные базисы согласованные с нормированием и вычисления в идеалах и полилинейных рекуррентах. Труды международной алгебраической конференции посвященной 250-летию московского университета, Фундаментальная и прикладная математика, 10, (3) (2004), с. 1С.

Издательство ЦПИ при механико-математическом факультете МГУ им. М.В. Ломоносова. Подписано в печать О/. 05 Формат 60x90 1/16. Усл. печ. л №

Тираж 100 экз. Заказ £

Лицензия на издательскую деятельность ИД В 04059, от 20.02.2001 г.

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета

2134

РНБ Русский фонд

2006-4 3006

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Горбатов, Евгений Владимирович

Введение.

1. Схемы симплификации и стандартные базисы.

1.1 Порядки на полиномах

1.2 Схемы симплификации

1.3 Схемы симплификации на полиномах.

1.4 Стандартные базисы и Б-полиномы

1.5 Минимальные и редуцированные стандартные базисы.

2. Стандартные базисы и вычисления в идеалах.

2.1 Основные свойства стандартных базисов

2.2 Модуль сизигий и вычисления с идеалами.

2.3 Элиминация.

2.4 Каноническая система образующих и согласованные стандартные базисы.

Введение диссертация по математике, на тему "Стандартные базисы, согласованные с нормированием, и вычисления в полилинейных рекуррентах"

В качестве основных примеров можно указать следующие задачи: вычисление периода (поли-)линейной рекурренты [6]; построение системы образующих и вычисление мощности семейства полилинейных рекуррент с заданным характеристическим идеалом (линейного полициклического кода) [7, 10, 13, 26] и описание полилинейных регистров сдвига, генерирующих это семейство [14]; описание систем образующих и характеристических идеалов суммы и пересечения таких семейств; построение проверочной матрицы линейного циклического кода; решение системы полиномиальных уравнений над кольцом [15].

Все эти задачи сводятся к построению "удобных" систем образующих идеалов I в кольце многочленов = Хк] над конечным кольцом

R с единицей, позволяющих достаточно просто проверять принадлежность заданного многочлена идеалу, вычислять мощность факторкольца R[X]/I, строить системы образующих суммы и пересечения идеалов, радикала идеала и его примарных компонент.

В случае, когда R — поле эти задачи решаются с помощью теории базисов Гребнера-Ширшова основы которой заложили Б. Бухбергер ([20]) и А. И. Ширшов ([16]) (см. также [2, 5, 8, 9, 22, 23]).

В общем случае, для решения этих задач, также естественно использовать технику стандартных базисов полиномиальных идеалов, общая теория которых в настоящее время хорошо развита (см., например, [18, 4]). Однако, попытки использовать стандартные базисы, которые строятся по известным общим алгоритмам, показали, что эти базисы зачастую малоэффективны. Дальнейшие исследования выявили, что для решения поставленных задач нужно строить базисы идеалов, по специально разработанным алгоритмам, учитывающим специфику кольца коэффициентов R ([10, 14, 15]).

В диссертации рассматривается случай, когда R — коммутативное конечно-цепное кольцо (наиболее востребованный с точки зрения практических приложений). Любой алгоритм построения стандартных базисов идеалов кольца R[X] основан на некотором линейном и согласованном с умножением упорядочении мономов rx%i.x%£ этого кольца. При этом упомянутые выше общие алгоритмы используют лишь порядки, однозначно определяемые набором показателей ii,i]Cl и не учитывают специфику коэффициента г. Стандартные базисы, которые строятся в данной работе, наоборот, основаны на упорядочениях мономов, которые в первую очередь учитывают эту специфику: место идеала rR в конечной цепи идеалов кольца R.

Идея использования таких порядков для построения стандартных базисов с целью решения названных выше прикладных задач была впервые реализована А. А. Нечаевым в [10] для кольца многочленов от одного переменного, и затем развивалась в [14, 15].

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

Основные результаты являются новыми и состоят в следующем:

4. Найдены новые условия, определяющие, когда данные диаграмма Ферре Т и полная система ^-унитарных полиномов образуют регистр сдвига (см. теорему 3.3.9). Определены и изучены цилиндрические идеалы (см. теорему 3.4.4). На основании этих результатов построена эффективная процедура проверки существования (и нахождения в таком случае) поднятия редуцированного базиса Гребнера унитарного идеала до согласованного стандартного базиса той же мощности (см. предложение 3.4.8).

На основе полученных результатов разработан пакет программ "Polynom" для вычислений в алгебре полиномов над коммутативными конечно-цепными кольцами.

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

Основные результаты диссертации докладывались на научно исследовательском семинаре и семинаре "Кольца и модули" кафедры высшей алгебры МГУ; на конференции по математике и безопасности информационных технологий (Москва, Россия, 2003 г.)([38]); на девятых математических чтениях МГСУ (Руза, Россия, 2003 г.)([36, 37]); на международной алгебраической конференции посвященной 250-летию московского университета (Москва, Россия, 2004 г.)([39, 40]).

Основные результаты опубликованы в 3 работах ([33, 34, 35]).

Краткое содержание работы

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

Пусть X = {а?!,., ж*;}, к ^ 1 — множество переменных и [X] = [жь ., Хк] — полугруппа коммутативных мономов над X. Пусть также Я — некоторое коммутативное кольцо. Полугруппой одночленов называется подполугруппа [Я, X] = {аи | а Е Я, и £ [X] } полугруппы (Я[Х], •). Порядок ^ на [Я, X] назовем разделяющим мономы, если для любых а, Ь £ Л\0 и и, V 6 [Х],и фу аи -< Ьу или Ьь -< аи.

Если — разделяющий мономы порядок, то во множестве одночленов произвольного полинома ^ 6 Д[Х]\0 найдется наибольший относительно =<! одночлен 1Ц — ведущий член полинома Р относительно =4. Разделяющий мономы порядок ^ назовем мультипликативным если для любых Р 6 Я[Х] и и € [Л, X]

Доказывается, что если на [Я, X] существует мультипликативный порядок, то идеалы вида Ап(а), аб й образуют цепь в решетке всех идеалов Я. Обратно, если идеалы этого вида образуют цепь, и для любых а, 6, с £ Я

Ап(6) С Ап(а) & Ьс ф 0) Ап(6с) С Ап(ас), то на [Я, X] существует мультипликативный порядок.

Устанавливается, что если кольцо R — квазифробениусово (наиболее востребованный для приложений в теории кодирования случай), то на [Л, X] существует мультипликативный порядок в точности если R — коммутативное артиново цепное кольцо. При этом мультипликативный порядок на [Я, X] может быть задан соотношением def f Ra С Rb или /Л Л , ч au 4 bv < ^ (0.0.1) Ra = Rb и и 4 v к ' для некоторого допустимого порядка на полугруппе мономов [X]). Этот порядок согласован с нормой г|| = тах{г 6 Щп | г <Е rad(R)* } на R (здесь п — индекс нильпотентности радикала Джекобсона rad (Я)), в том смысле, что U 4V \\U\\ < ||V||.

Функция ведущего члена отвечающая этому порядку обозначается Lt. Именно эта функция использовалась в [10, 14, 15] при построении канонических систем полиномов.

Определение ([8]) Пусть (М, ) — непустое, упорядоченное множество с условием минимальности и 5 С Мм. Тройка & = (М, , S) называется схемой симплификации на М если выполнено условие:

Vm G М Vs € S : s(m) 4 т.

Говорят, что т G М — нормальный или редуцированный элемент (относительно &) если Vs € S : s(m) = т. Совокупность всех нормальных элементов обозначается N&.

Пусть S — подполугруппа в полугруппе Мм (с композицией функций в качестве умножения), порожденная S U {1м}- Для любого элемента тбМ множеством нормальных форм называется

Nore(m) = S(m) П N&.

Определение Пусть R — кольцо, М = Мц — правый модуль и Р(М) — множество всех подмножеств М. Схему симплификации & = (М, , S) будем называть консервативной на Мц, если определено отображение 6 : Р(М) Р(5), S : х Sx, такое что Уж G MVs G 5Х: х — sx Е X-ß.

Это отображение называется отображением сечения.

Множество % С Л назовем &-стандартным базисом подмодуля Л если

Va € А : Nor6x(a) Э 0.

Для коммутативного артинового цепного кольца R следующим образом строятся две консервативные схемы симплификации 65 и 65Г

Построение схемы симплификации 65 = (R[X], , 5). Зафиксируем некоторый элемент -к € rad(-ft) \ [rad(Ä)]2. Всякий элемент а £ R можно представить в виде а = ao7r"a", где ао Е R*. Любой полином F Е R[X] \ 0 представляется в виде:

F = а0тгаои0 + . + aro7ramuw, (0.0.2) где аг- Е -R*, 0!г- Е 0, п — 1, — попарно различные мономы из [X] и 7та°гго >-. >- 7ramitTO (в смысле порядка (0.0.1)).

Пусть G Е и G — bo7T^°vo + . + br7r^rvr — представление аналогичное (0.0.2), тогда, по определению, F -< G если существует индекс i Е 0,min(m,г) такой, что 7га°щ = = tt^vi-i и тга{щ -< irß'Vi, или если т < г и 7га°гго = 7т^°г>о, ., тгатит = тг^тут. Иными словами, порядок -< на Ä[X] сводится к лексикографическому сравнению слов получающихся из полиномов выписыванием составляющих их одночленов по убыванию.

Пусть G € Д[Х]\0 и u G [X], тогда Lt(uG) = uLt(G) = auv, где а 6 Л и v G [X]. Пусть F G R[X] и с — коэффициент при мономе uv в F, действие редукции rc,u на F определяется следующим образом: „ч Г F если с Ф Ra, = 1

К F — buG если с G Ra и с = Ьа.

В схеме © выбираем S = { гq,u | G € Д[Х]\0, и € [X] }; отображение сечения задается равенством Sx = { гс,и | G £ Xi и £ [X] }.

Построение схемы симплификации Фг = (R[X], , SF). Пусть Г — семейство представителей классов вычетов R по ttR = r&d(R). Тогда для любого с £ R существует единственный вектор (со, Ci,., cni) 6 Г", такой что

С = Со + 7ГС1 + . . . + ТГ^Сп-Ь (0.0.3)

Порядок на R[X) из схемы симплификации определяется как и =<; , исходя из представления полинома F в виде (0.0.2), в котором, однако, выбираются щ € Г, аг- £ 0, п — 1 и мономы щ — не обязательно различны.

Пусть G е R[X]\0 такой, что Lt(G) = irav, v G [X] и U = Л, где и G [I], тогда Lt(UG) = ULt(G) = ira+ßuv. Пусть F 6 R[X] и с - коэффициент при мономе uv в F, если ca+ß — элемент из Г стоящий при 7га+/3 в разложении (0.0.3), то действие редукции г^ ц на F определяется следующим образом: rTG,u(F) = F- Ca+ßUG.

В схеме вг выбираем 5Г = {г^ | <3 е Л[Х]\0, и = жаи, и е [X]}; отображение сечения задается равенством = = {4,и с/ = 1гаи, и е [X]}.

Доказывается, что схемы симплификации <3 и 65Г эквивалентны, то есть, что для любого идеала из ЩХ] классы 0- и (5г-стандартных базисов совпадают. Эти базисы названы стандартными базисами согласованными с нормой или, короче, согласованными стандартными базисами.

Для эффективного построения согласованных стандартных базисов, как и в классическом случае, вводится понятие Э-полинома.

Пусть е ЩХ] и и(^) = атгаи, Ы;(<7) = бЛ, где а,Ь в В*, а,/3 е

0,n- 1 и u,v G [X]. Пусть w = НОД (и, v) 6 [X] и 7 = max{a,ß}. S-полиномом от F и G называется полином

7f^W

S{F'G) = ЩТ/~ Щс)°

Доказана теорема, являющаяся аналогом леммы о композиции из теории базисов Гребнера над полями.

Теорема 1. Пусть х ~ непустая система полиномов из идеала I кольца R[X], тогда следующие утверждения эквивалентны: a) х ~ &-стандартный базис идеала I. b) х ~ -стандартный базис идеала I. c)VFeI:3GeX Lt(G)|Lt(F). d) I=(x)n VGi, G2 G x : Nor&X(S(GU G2)) = 0(э 0). e) I = (x) w — схема симплификации с канонизацией, то есть любой полином F £ ЩХ] имеет единственную нормальную форму относительно 0Г.

В условии (е) теоремы 1 схему симплификации 0Г нельзя заменить на 0. В этом состоит ключевое различие этих схем симплификации.

Определение Пусть & = (М, =^,5) — консервативная схема симплификации на Мд. Систему х С М назовем &-редуцированной если для любого элемента т Е х:

I) т является 6-самонормальным, то есть для любой редукции в 6 5{то} или

8771 = т или 5771 = о

Теорема 2. Пусть I — ненулевой идеал в В,[Х], тогда: a) Любой 0 -редуцированный стандартный базис является минимальным. b) Любой 0Г -редуцированный стандартный базис является <3-редуцированным. c) Идеал I обладает единственным <3Т-редуцированным стандартным базисом (с точностью до умножения составляющих этот базис полиномов на обратимые элементы из Я).

Во второй главе были решены некоторые классические вычислительные задачи в идеалах кольца

В предложении 2.1.1 приводится полная система представителей различных классов вычетов в I/«7 для любых идеалов I и 7 из ДрГ]. При этом для каждого ^ £ / представитель из класса вычетов .Р + <7 может быть найден эффективно по Р. Это предложение позволяет определить формулу для мощности 1(3 (когда она конечна) и обобщить результат из [26], где была вычислена мощность факторкольца Н[Х]/1.

Пусть даны два множества переменных X = и У =

Уъ • • •, У/}- Пусть также дан идеал I < И[Х, У] = Щхъ., хк] уъ • • •, уЦ-Задача элиминации состоит в нахождении множества образующих идеала 1Х = I Г) <1 Я[Х] исходя из множества образующих идеала I. В пункте 2.3 изложен алгоритм решающий данную задачу. Следует заметить, что этот алгоритм существенно отличается от классического алгоритма элиминации для полей.

Далее изучается связь согласованных стандартных базисов с канонической системой образующих (КСО) из [15]. Доказывается (предложение 2.4.2), что всякая каноническая система образующих является согласованным стандартным базисом.

На основе условия (с1) теоремы 1 строится алгоритм вычисляющий согласованный стандартный базис полиномиального идеала по произвольной системе образующих (см. алгоритм 1.4.7). При этом существенным образом используется, развитая в первой главе, техника стандартных базисов (в частности Б-полиномы). С использованием этого алгоритма построена эффективная процедура вычисления канонической системы образующих идеала, которой не было предложено в [10, 14, 15].

Указанные алгоритмы были реализованы программно и вошли в пакет приложений " Polynom ".

В начале третьей главы излагаются необходимые, известные из [26, 27, 6], определения и результаты теории полилинейных рекуррент.

Пусть В — произвольное кольцо и Мв — правый .В-модуль. Множество Mßk> всех к-последовательностей ß: N* —> Мв над Мв естественным образом наделяется структурой В[Х]~модуля, при этом /¿-последовательность Ii называется к-линейной рекуррентной последовательностью (k-ЛРП), если ее аннулятор Рв[Х]{ц) = I есть правый унитарный идеал (для каждого s Е 1,к существует унитарный полином Fa(x) G В[х] такой, что Fs(xs) Е I).

Семейство Ьм{1) всех /г-ЛРП аннулирующих идеал I есть В [Х]-подмодуль в Mßk>. Хорошо известно, что это — циклический модуль в случае, когда к = 1, В — поле и Мв — Bß. В работе [10], для случая, когда к = 1 и R — коммутативное артиново цепное кольцо, был дан критерий цикличности семейства Lr(I) и поставлена задача об обобщении этого критерия на случай многих переменных. Следующая теорема дает решение этой задачи.

Теорема 3. Пусть R — коммутативное артиново кольцо, Qr — квазифро-бениусов модуль и I < R[X] — унитарный идеал. Тогда следующие условия эквивалентны. a) Семейство Lq(I) является циклическим К[Х]-модулем. b) Факторкольцо R[X]/I является квазифробениусовым. c) Выполняется соотношение

R[X]/Vl)n = [(/ : Vl)/I\w

Здесь yfl = { F £ R[X] | 3t 6 N: F' 6 I} - радикал идеала I.)

Теорема 3 представляет обобщение критерия П. Лю [28], который был доказан для случая одной переменой (к = 1) и коммутативного артинова цепного кольца Я. Данное доказательство значительно короче, так как использует хорошо известные свойства квазифробениусовых колец.

С использованием критерия 3 и методов согласованных стандартных базисов, для коммутативного артинова цепного кольца В, построен алгоритм проверки цикличности семейства Ьд(1) по произвольной системе образующих идеала /.

Произвольное конечное подмножество Т С Нд называется диаграммой Ферре если

Vг,i € (г € Т, 3 < «) {о € Т), где порядок ^ на определяется определяется формулой $ ^ г 3* £ +

Пусть Т — диаграмма Ферре и х ~~ система полиномов из ЩХ] = В,[хг,.,Хк\. Пара (х, З7) называется к-линейным регистром сдвига или Т-линейным регистром сдвига над модулем Мд если и только если, гомоморфизм

Ьм(х) = Ит является изоморфизмом. При этом семейство последовательностей Ьм(х) называется множеством рекуррент порожденных регистром сдвига (%, Т).

Пусть 1в — 5-я строка единичной матрицы размера к. Внутренностью, внутренней границей, внешней границей диаграммы Ферре Т С в направлении la, s € 1, к назовем соответственно множества

Ts = {г е Т\ г + 1, е Т}, dsT = T\Fa,

AST = d3T +18, к

Объединение AT = U AST называется внешней границей диаграммы

S=1

Ферре Т. Полином Н Е В[Х] называется Т-унитарным если для некоторого г G AT

H = xr (0.0.4)

Множество Ф С В[Х] из \АТ\ полиномов называется полной системой Т-унитарных полиномов если для каждого г 6 AT эта система содержит единственный полином вида (0.0.4).

-линейный регистр сдвига (х 5 Т) называется каноническим Т-линейным регистром сдвига если х ~ полная система ^"-унитарных полиномов. В работе [27] доказывается, что множество последовательностей порожденных любым регистром сдвига порождается некоторым каноническим регистром сдвига (возможно над большим кольцом).

В [27] была поставлена задача описания условий на коэффициенты полиномов из Xi ПРИ которых пара {х-, Т) есть канонический регистр сдвига. Решение дает следующая теорема.

Теорема 4. Пусть Т — диаграмма Ферре, Ф — полная система Т-унитарных полиномов из В[Х] и р = рв(М) — аннулятор модуля М в В. Тогда пара (х> F) образует Т-линейный регистр сдвига если и только если для любых s,t £ l,k, s ф t выполняются следующие условия:

Дляз£д8?П?1

Hj+U+is = Hj+I,xt+ hi+i„bHk+it, k£dt? и для j € dsT П dtF

Hj+i,xt+ h3+i>*Hk+it = Hfritxs+ ^^ hj+it,kHk+ls. kedtT keds T

В общем случае не любая последовательность порожденная регистром сдвига есть fc-ЛРП ([27]). Следующая теорема показывает, что последовательность порожденная регистром сдвига над кообразующим С в является fc-ЛРП если кольцо В — нетерово справа.

Теорема 5. Пусть В — нетерово справа кольцо, I — правый идеал в В[Х], С Nq — диаграмма Ферре и С в — кообразующий. Тогда если пара (I, Т) является регистром сдвига над Св, то I ~ унитарный идеал.

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

Теорема 6. Для произвольного идеала I <3 R[X] следующие условия эквивалентны: b) I выделяется прямым слагаемым в R[X]r. c) I является свободным R-модулем. d) R[X]/I является свободным R-модулем. fej7rJ =/ПтгД[Х]. f) I = 0 или I обладает согласованным стандартным базисом состоящим из не равных 0 по модулю rad(i?) полиномов.

Следует отметить, что для унитарного идеала I и канонической системы образующих эквивалентность (d)^(f) из теоремы 6 была доказана ранее в [14].

Естественный гомоморфизм v: R R = RJ rad(i?) стандартным образом продолжается до гомоморфизма колец полиномов R[X] i?[X].

Будем говорить, что базис Гребнера ф С /2[Х]\0 поднимается (в R[X)), если существует стандартный базис х Q ЩХ] такой, что х = Ф и G\ Ф G2 для различных G\,G2 € Х

В [14] была поставлена задача определить всякий ли базис Гребнера поднимается в В работе получено продвижение в решении этой проблемы, а именно, доказано, что базис Гребнера х полиномиального идеала над полем вычетов R поднимается в ДрГ] тогда и только тогда, когда идеал (х) является образом некоторого цилиндрического идеала I <3

В [14] доказано, что унитарный идеал I является цилиндрическим если и только если пара (I, Т) образует линейный регистр сдвига, где Т — диаграмма Ферре, такая что

X]\LM(J) =

С использованием этого результата, теоремы 4, а также методов решения систем нелинейных алгебраических уравнений над кольцами Галуа из [15], в работе, для случая когда R — кольцо Галуа, построена эффективная процедура проверки существования (и нахождения в таком случае) поднятия редуцированного базиса Гребнера унитарного идеала до согласованного стандартного базиса той же мощности (см. предложение 3.4.8).

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Горбатов, Евгений Владимирович, Москва

1. Атья М., Макдональд И. Введение в коммутативную алгебру. М.: Мир, 1972.

2. Дэвенпорт Д., Сирэ И., Турнье Э. Компьютерная алгебра. М.: Мир, 1991.

3. Каш Ф. Модули и кольца. М.: Мир, 1981.

4. Кокс Д., Литтл Дж., Д. О'Ши Идеалы, многообразия и алгоритмы. М.: Мир, 2000.

5. Компьютерная алгебра. Символьные и алгебраические вычисления. Под редакцией Бухбергера Б., Коллинза Д., Лооса Р., М.: Мир, 1986.

6. Кузьмин А. С., Куракин В. Л., Нечаев А. А. Псевдослучайные и полилинейные последовательности. Труды по дискретной математике, 1, (1997), с. 139-202.

7. Кузьмин А. С., Нечаев А. А., Марков В. Т. Линейные коды над конечными кольцами и модулями. Фундаментальная и прикладная математика, 3, (1) (1997), с. 195-254.

8. Латышев В. Н. Конструктивная теория колец. Стандартные базисы. М.: Изд-во МГУ, 1988.

9. Михалев А. В., Панкратьев Е. В. Компьютерная алгебра. Вычисления в дифференциальной и разностной алгебре. М.: Изд-во МГУ, 1989.

10. Нечаев А. А. Линейные рекуррентные последовательности над коммутативными кольцами. Дискретная Математика, 3, (4) (1991), с. 105-127.

11. Нечаев А. А. Линейные рекуррентные последовательности над квазиф-робениусовыми модулями. Успехи математических наук, 48, (3) (1993), с. 197-198.

12. Нечаев А. А. Конечные квазифробениусовы модули, приложения к кодам и линейным рекуррентам. Фундаментальная и прикладная математика, ЦНИТ МГУ, 1, (1) (1995), с. 229-254.

13. Нечаев А. А. Линейные коды и полилинейные рекурренты над конечными кольцами и квазифробениусовыми модулями. Доклады академии наук, 35, (4) (1995), с. 451-454.

14. Нечаев А. А., Михайлов Д. А. Каноническая система образующих унитарного полиномиального идеала над коммутативным артиновым цепным кольцом. Дискретная математика, 13, (4) (2001) с. 3-42.

15. Нечаев А. А., Михайлов Д. А. Решение системы полиномиальных уравнений над кольцом Галуа- Эйзенштейна с помощью канонической системы образующих полиномиального идеала. Дискретная Математика, 16, (4) (2004), с. 21-51.

16. А. И. Ширшов, Некоторые алгоритмические проблемы для алгебр Ли, Сибирский математический журнал, 3, (1962) с. 292-296.

17. Фейс К. Алгебра: кольца, модули, категории, т. 2., М.: Мир, 1979.

18. Adams W., Loustaunau P. An Introduction to Grobner bases. Graduate Studies in Mathematics, 3, American Mathematical Society, 1994.

19. Apel J. Computational ideal theory in finitely generated extension rings. J. Theoretical Computer Science, 244, (2000), pp. 1-33.

20. Buchberger B., Ein Algorithmus zum Auffindender Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. Ph.D. Thesis, Inst. University of Innsbruck, Innsbruck, Austria, 1965.

21. Byrne E., Fitzpatrick P. Gröbner bases over Galois Rings with an application to decoding alternant codes. J. Symbolic Computation, 31, (2001), pp. 565584.

22. Eisenbud D. Commutative Algebra. With a view toward algebraic geometry. Graduated texts in Mathematics, 150, Berlin: Springer-Verlag, 1995.

23. Kondratieva M. V., Levin A. B., Mikhalev A. V. and Pankratiev E. V. Differential and Difference Dimension Polynomials. Kluwer Academic Publishers, 1999.

24. Kronecker L. Vorlesungen über Zahlentheorie. Bd.l, Leipzig, Teubner, 1901.

25. Krull W. Algebraische Theorie der Ringe II. Math. Annalen, 91, (1923), pp. 1-46.

26. Kurakin V. L., Mikhalev A. V., Nechaev A. A., and Tsypyschev V. N. Linear and polylinear recurring sequences over Abelian groups and modules. Journal of Mathematical Sciences, 102, (6) (2000), pp. 4598-4626.

27. Lu P. Z. A criterion for annihilating ideals of linear recurring sequences over Galois rings. AAECC-417, 11, (2) (2000).

28. Mora T. Seven Variations on Standard Bases. Preprint, Univ. de Genova, Dip. di Mathematica, (45) (1986).

29. Nechaev A. A. Polylinear recurring sequences over modules and quasi-Frobenius modules. Proc. First Int. Tainan-Moscow Algebra Worcshop, 1994, Walter de Gruyter, Berlin-N. Y. (1996), pp. 283-298.

30. Norton G. H., Salagean A. Strong Grôbner bases and cyclic codes over a finite-chain ring. Proceedings of the International Workshop on Coding and Cryptography, Paris, (2001) Jan., pp. 8-12.

31. Robbiano L. On the Theory of Graded Structures. J. Simb. Comp., 2, (1986), pp. 139-170.ПРАКТИЧЕСКАЯ АПРОБАЦИЯ РЕЗУЛЬТАТОВДИССЕРТАЦИИ

32. Горбатов Е. В., Михалев А. В., Нечаев А. А. Стандартный базис полиномиального идеала над коммутативным артиновым цепным кольцом. Труды девятых математических чтений МГСУ, М.: Издательство МГСУ, (2003), с. 90-92.

33. Горбатов Е. В., Михалев А. В., Нечаев А. А. Схемы симплификации на полиномах и стандартные базисы. Труды девятых математических чтений МГСУ, М.: Издательство МГСУ, (2003), с. 93-96.

34. Горбатов Е. В., Михалев А. В., Нечаев А. А. Модульные и кольцевые схемы симплификации. Тезисы докладов международной алгебраической конференции посвященной 250-летию московского университета, МГУ, (2004), с. 38-40.

35. Горбатов Е. В. Стандартный базис полиномиального идеала над коммутативным артиновым цепным кольцом. Дискретная математика, 16, (1) (2004), с. 52-78.