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

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

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

Введение.

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].

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

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

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).

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

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

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

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

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

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

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

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

Пусть 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 = о

II) т нормален относительно схемы симплификации ©х\{т}-Доказана следующая теорема

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

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

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

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

Пусть даны два множества переменных 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).

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

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

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.