О распознаваемых свойствах ассоциативных алгебр

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

Первая попытка построения стандартных базисов сделана в работах ([22], 1926; [24], 1927). Стандартный базис впервые определен в идеалах свободных коммутативных алгебр К[х, Х2, ¦ ¦., хп] и рассмотрен алгоритм «критических пар» Бухбергером в ([16], 1965; [17], 1970).

А.И. Ширшов предложил конструкцию стандартных базисов в свободных алгебрах Ли С (х, Х2, ¦ • -, хп) и доказал лемму о композиции (см. [12], 1962). В ассоциативном случае исходной является работа JI.A. Бокутя (см. [1]). Бергман доказал «Diamond» лемму (аналог леммы о композиции в лиевском случае), чем распространил понятие базиса Гребнера на свободные ассоциативные алгебры JC (x, Х2, ¦. -, хп) (см. [14], 1978). Систематическое изложение фактов, связанных со стандартными базисами сделано В. Н. Латышевым в работе ([4], 1988) и В. А. Уфнаровским в обзоре ([11], 1990). Е. С. Голод в ([21], 1988) сформулировал понятие стандартного базиса для фильтрованной алгебры с одномерными фильтрующими подпространствами и предложил «Diamond» лемму в гомологической форме. A.A. Михалев в ([25], 1992; [26], 1996) определил стандартный базис и доказал лемму о композиции для супералгебр Ли, р-супералгебр Ли и цветных супералгебр Ли.

В теории уравнений с частными производными возникли инво-лютивные методы (см. [32], 1978), благодаря которым появилась принципиально новая схема построения базисов Гребнера в коммутативной алгебре, разработанная А. Ю. Жарковым и Ю.А. Блин-ковым (см. [36], 1993). Дальнейшее развитие эти идеи получили в ([20], 1996). Такие стандартные базисы в настоящей работе названы Р-стандартными базисами (см. Гл. З, § 3.1).

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

Стандартный базис в подалгебрах первоначально определен в свободных коммутативных алгебрах JI. Роббиано, М. Свидлером, а также Д. Капуром, К. Мадленером в работах ([33], 1988; [23], 1989) и назван SAG ВI-базисом (Subalgebra Analogue to Grobner bases for ideals). H.K. Иыуду в ([3], 1999) определила это понятие в подалгебрах свободных ассоциативных алгебр.

В.Н. Латышев в ([27]- [28]- [29]- [30]) предложил обобщенную версию стандартных базисов, которая содержит в себе все вышеупомянутые. Она позволяет строить стандартный базис в подполигонах линейных полигонов, в частности, в идеалах строго-градуированных алгебр и алгебр со строгой фильтрацией.

Алгоритмические вопросы в различных классах алгебр исследовались А. И. Ширшовым, В. Н. Латышевым, В. А. Уфнаровским, У. У. Умирбаевым, Т. Гатевой-Ивановой, В. В. Борисенко, А .Я. Беловым, Н. К. Иыуду, Д. И. Пионтковским (см. [2], [3], [7], [9] - [13], [18], [19]).

Ряд распознаваемых свойств ассоциативных стандартно конечно-определенных (с.к.о.) алгебр указан В. Н. Латышевым и Т. Гатевой-Ивановой (см. [18], 1987; [19], 1988). В монографии ([13], 1995) А .Я. Беловым, В. В. Борисенко, В. Н. Латышевым рассмотрено распознавание некоторых свойств автоматных алгебр, в том числе распознаваемость делителей нуля и нильпотентных элементов. В ([2], 1995) доказана распознаваемость свойства элемента быть односторонним делителем нуля в классе алгебр с односторонней 1-переработкой. Алгоритмическая распознаваемость одностронних делителей нуля в классе алгебр с односторонней Д-переработкой, где Я — натуральное число, доказана Д. И. Пионтковским (см. [7]).

В ([3], 1999) положительно решена проблема вхождения в подалгебру свободной ассоциативной алгебры К (х 1,^2,., жп), порожденную конечным числом однородных элементов, с использованием техники 5 /-базисов. В ([9], 1992) У .У. Умирбаевым показано, что для подалгебр в свободной ассоциативной алгебре конечного ранга проблема вхождения и проблема распознавания свободной порожденности заданным конечным множеством элементов алгоритмически неразрешимы. В настоящей работе рассматривается проблема свободной порожденности в частных случаях, причем с использованием техники БЛОШ-базисов (см. Гл. 1, § 1.1). В случае, когда подалгебра в свободной ассоциативной алгебре конечного ранга порождается конечным числом мономов, данная проблема алгоритмически разрешима (см. [8], Глава 4, § 4.1, с. 59−64).

В ([10], 1978) В. А. Уфнаровским показано, что рост ассоциативной с.к.о. алгебры либо полиномиальный, либо экспоненциальный. Алгоритм распознавания конкретного типа роста такой алгебры указан в ([19], 1988). Изменение типа роста при переходе от алгебры Ли к ее универсальной обертывающей алгебре изучалось В. М. Петроградским в ([5], 1993; [31], 1996). Мы, пользуясь результатами работ [15], [31], [35], путем несложных рассуждений получаем положительное решение вопроса об алгоритмической распознаваемости конкретного типа роста с.к.о. алгебры Ли (см. Гл. 2, § 2.4).

Также в настоящей работе изучается распознавание некоторых свойств фактор-алгебр строго-градуированных алгебр (см. Гл. 2,.

§§ 2.2, 2.3), левых делителей нуля в диксоновых справа алгебрах со строгой фильтрацией по модулю конечнопорожденного правого идеала (см. Гл. 2, § 2.1), рассматривается построение Р-стандартных базисов полиномиальных идеалов (см. Гл. З, § 3.1), а также исследуется распознавание свойств подалгебр мономиальных алгебр (см. Гл. 1, §§ 1.1, 1.2).

Основные результаты диссертации: указаны алгоритмы распознавания свойств конечномерности, алгебраичности, нильи нильпотентности фактор-алгебр строго-градуированных алгебр специального видапоказана распознаваемость левых делителей нуля в диксоновых справа алгебрах со строгой фильтрацией специального вида по модулю конечнопорожденного правого идеалапоказана распознаваемость левых делителей нуля в универсальных обертывающих алгебрах конечномерных алгебр Ли по модулю конечнопорожденного правого идеалапоказано равенство ниль-радикала и радикала Джекобсона для строго-градуированных алгебр специального видауказан алгоритм распознавания конкретного типа роста с.к.о. алгебры Липолучен критерий того, является ли предъявленная конечная система полиномов Р-стандартным базисом порожденного ею идеала в алгебре полиномовуказан алгоритм определения по заданному конечному множеству порождающих полиномиального идеала того, что его Р-стандартный базис бесконеченприведен алгоритм построения Р-стандартного базиса полиномиального идеала исходя из конечного множества его порождающих в случае, когда Р-стандартный базис конечендля подалгебр, заданных конечным SAGBI-базисом в конечно-определенной мономиальной алгебре положительно решен вопрос о распознавании свободной порожденности заданными элементами и указан алгоритм распознавания конечномерности этой подалгебры;

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

Пусть К, — поле нулевой характеристикиX — {a?i,. ., хп} - произвольный алфавит- [X] - свободная коммутативная полугруппа, порожденная множеством XК[Х] - полугрупповая алгебра полугруппы [X] над полем /С, являющаяся алгеброй (коммутативных) полиномов, или свободной коммутативной алгеброй над полем /С- (X) — свободная полугруппа, порожденная множеством X- 1С{Х) -полугрупповая алгебра полугруппы (X) над полем /С, являющаяся алгеброй некоммутативных полиномов, или свободной ассоциативной алгеброй ранга п над полем К. Символом С{Х) будем обозначать свободную алгебру Ли, которую можно отождествить с множеством лиевых элементов в свободной ассоциативной алгебре.

К{Х).

Элементы полугруппы [X] ((X)) называются коммутативными (некоммутативными) мономами, а элементы КХ] (К,(Х)) — коммутативными (некоммутативными) полиномами.

Полный порядок х <. < хп, заданный на алфавите X, продолжается до полной упорядоченности полугруппы [X] ((X)), если из двух мономов разной длины старшим считать более длинный, а мономы одинаковой длины сравнивать лексикографически (степенно-лексикографическая упорядоченность). Такая упорядоченность на мономах удовлетворяет условию обрыва убывающих цепей, или d.c.c. (descending chain condition).

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

Определение 1 (см. 29]). Пусть i) V — линейное пространство над полем ТСii) Е = {ea | a Е Л} - выделенный базис пространства V, где Л — упорядоченная полугруппа, в которой полная упорядоченность удовлетворяет d.c.c., базисные элементы сравниваются в соответствии со своими индексами, т. е. еа > ер су > /3- iii) Е — множество линейных операторов на V, содержащее тождественное отображение, таким образом, всякий элемент a Е Е индуцирует линейное отображение a: V —>¦ Viv) некоторые произведения aea, a Е Е, ea Е Е (включая произведения ееa = е (у) объявлены существенными.

Тогда линейное пространство V называется линейным полигоном над свободным моноидом ио = (Е). порожденным операторами из Е.

Если ф = а. ат Е сг{ Е Е, х Е V, то обозначим.

Фх {¦ ¦ .{(7тх).. .).

Определение 2 (см. 29]). Произведение а^х, а^ Е Е, ж Е V называется существенным, если существенным является произведение а3х. Символом х обозначается базисный вектор (старший член) в представлении х? V в виде линейной комбинации элементов из Е.

Определение 3 (см. 29]). Произведение фх, ф = о. от Е и, сгг Е Е. 'X Е V, называется существенным, если каждый множитель стг действует существенным образом.

Определение 4 (см. 29]). Линейное подпространство II С V называется линейным подполигоном, если оно является инвариантным относительно операторов из Е.

Определение 5 (см. 29]). Будем говорить, что множество элементов (7 = {дг} С и порождает II, если II совпадает с линейным пространством Брап^д^ф Е ил д, Е С}. Если все произведения фд1 существенные, тогда С называется существенным множеством порождающих.

Определение 6 (см. 29]). Множество б = С ?7 называется стандартным базисом II, если для всякого элемента х Е II существует существенное произведение фд{, ф Е ш, Е О, такое, что х = фд{.

Определение 7 (см. 29]). Пусть II С V — линейный подполигон и = {д-} С II — его множество порождающих. Равенство х = (0.1) г х Е и, ЛгЕ К, ф{ Е ^ Е называется представлением х Е и, если все произведения «</>,-.д, — являются существенными. Старший базисный вектор и) среди всех /фigi называют параметром представления. Если х = и), то представление (0.1) элемента х называют Н-представлением.

Символом °х обозначают элемент, полученный из х Е V делением на его старший коэффициент (коэффициент при старшем члене).

Определеннее (см. [29]). Пусть существенные произведения и Ф'29], Ф '02 Е со, giJgj Е С, таковы, что гу = фгд^ — ф^д^ Е Е. Тогда 5 =° {фхд-,) —0 {фс1Я]) называется з-элементом с исходным параметром П).

Определение 9 (см. 29]). Для любого существенного произведения фд{, ф Е ш, дг Е С, еа = фд{ определяется редукция Гф^: V V, как линейный оператор на V, который еа сопоставляет элемент Гфл (еа) = еа —0 (фд{), а базисные элементы, отличные от еа, оставляет на месте.

Пусть 71(3 ~ множество всех редукций, содержащее тождественное отображение. Тогда — линейная схема симплифика-ции и верна.

Теорема 1 (см. 29]). Пусть II С V ~ линейный подполигон и С = {дг} Сисущественные порождающие II. Тогда следующие условия эквивалентны:

I) С — стандартный базис;

II) всякий элемент из II редуцируется к нулю;

III) всякий элемент из II обладает Н-представлениемiv) всякий s-элемент имеет представление с параметром, меньшим исходного параметраv) (V, <, 7Zc) — линейная схема симплификации с канонизацией.

Перейдем к подробному изложению работы.

Диссертация состоит из введения, 3 глав, 7 параграфов, приложения и списка литературы.

1. Бокуть Л. А. Вложения в простые ассоциативные алгебры)/ Алгебра и логика — 1976 — 15, N 2-е. 117−142.

2. Иыуду Н. К. Алгоритмическая разрешимость проблемы распознавания делителей нуля в одном классе алгебр// Фунд. и прикл. мат.- 1995. 1Д 2.-е. 541−544.

3. Иыуду Н. К. Стандартный базис и проблема вхождения в подалгебры свободной ассоциативной алгебры/ / Межд. алг. сем., поев. 70-летию каф. высш. алг. Москва, февр. 1999.: Тез. докл. -Москва, 1999.-е. 29−31.

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

5. Петроградский В. М. О некоторых типах промежуточного роста алгебр Ли// Успехи мат. наук.- 1993.5.-е. 181−182.

6. Пионтковский Д. И. Базисы Гребнера и когерентность мо-номиалъной ассоциативной алгебры// Фунд. и прикл. мат.-1996, — 2.-е. 501−509.

7. Пионтковский Д. И. Некоммутативные базисы Гребнера, когерентность ассоциативных алгебр и делимость в полугруппах/ / в печати.

8. Саломаа А. Жемчужины теории формальных языков.—М.:Мир, 1986. 159с.

9. Умирбаев У. У. О проблеме вхождения для свободных ассоциативных алгебр) I 11 Межресп. конф. по мат. логике, Казань, 6−8 окт., 1992: Тез. сообщ. Казань, 1992. — с. 145.

10. Уфнаровский В. А. О росте алгебр)/ Вестн. МГУ.Сер. мат., мех, — 1978.-N 4.-е. 59−65.

11. Уфнаровский В. А. Комбинаторные и ассимптотические методы в алгебре// Итоги науки и техн., Сер. совр. пробл. мат.-1990, — 57.-е. 1−177.

12. Ширшов А. И. Некоторые алгоритмические проблемы для алгебр Ли// Сиб. мат. ж, — 1962. 3, N 2.-е. 292−296.

13. Belov A. J., Borisenko V. V., Latyshev V. N. Monomial algebras// Contemp. math, and its appl., Plenum, New-York.- 1995. 26p.

14. Bergman G. The diamond lemma for ring theory// Adv. math.-1978. 29, N 2.-p.178−218.

15. Bokut L. A. Lie algebra and its universal enveloping algebra have the same Lyndon-Shirshov basis// Intern. J. Algebra and Computation, to appear.

16. Buchberger B. An algorithm for finding a basis for the residue class ring of a zero-dimentional polynomial ideal: Ph. D. thesis.- 1965.-Univ. of Innsbruck, Math. Inst.

17. Buchberger B. An algorithmical criterion for the solvability of algebraic systems of equationsf / Aequationes Math.- 1970. 4, N 3.-p. 374−383.

18. Gateva-Ivanova T. Algorithmic determination of the Jacobson radical of monomial algebras/ Preprint.- 1987, Sofia.

19. Gateva-Ivanova T., Latyshev V. N. On the recognizable properties of as so siative algebras/ / Special vol. of J. S. C.: On comp, aspects comm. algebras. London: Acad. Press.- 1988.-p. 237−254.

20. Gerdt V. P., Blinkov Y. A. Involutive bases of polynomial ideals./ Preprint-Nr./ 1996, NaturwissenshaftlichTheoretisches Zentrum, Univ. of Leipzig.

21. Golod E. S. Standard bases and homology// Lect. notes of math.— 1988. 1352,-p. 88−95.

22. Hermann G. Die frage der end lichen vielen schritte in der theorie der polynomideale// Math. Ann.- 1926. 95 -p. 736−788.

23. Kapur D., Madiener K. A completion procedure for computing a canonical basis for a K-subalgebra.// Computers and Mathematics, Cambridge, MA.- 1989, Springer, New-York, Berlin.-p. 1−11.

24. Macaulay F. S. Some properties of enumeration in the theory of modular systems// Proc. Lond. Math. Soc.- 1927. 26.-p. 531−555.

25. Mikhalev A. A. The composition lemma for color Lie superalgebras and for Lie p-superalgebras// Contemprorary Math.- 1992. 131.

26. Mikhalev A. A. Shirshov composition techniques in Lie superal-gebras (Noncommutative Grobner bases)// J. of Math, sciences.-1996, — 80, N 5.-p.2153−2160.

27. Latyshev V. N. Canonisation and standard bases of filtered structures Transactions of the second intern. TaiwanMoscow algebra work-shop.- 1997, Berlin, New-York.

28. Latyshev V. N. General version of standard bases of linear structures/ / Algebra. Proc. of the intern.alg.conf. on the occasion of 90th birthday of A. G. Kurosh, Moscow, May 25−30, 1998. 2000, Berlin.

29. Latyshev V. N. An improved version of standard bases// to appear.

30. Latyshev V. N. An improved version of standard bases// Proc. of the 12th intern, conf. FPSAC'00, Moscow, June 26−30, 2000.

31. Petrogradsky V. M. Intermediate growth in Lie algebras and their enveloping algebras// J. Algebra.- 1996. 179.-p. 459−482.

32. Pommaret J. F. Systems of partial differential equations and Lie pseudogroups.- New-York: Gordon and Breach.- 1978.

33. Robbiano L., Sweedler M. Subalgebra bases// Comm. algebra. Proc. of the work-shop held at the Federal Univ. of Bahia, Salvador, 1988. Lect. notes Math.- 1990, — 1430-p. 61−87.

34. Sardinas A., Patterson G. A nesserary and sufficient condition for the unique decomposition of coded messages. IRE Intern, conv. record.- 1958. 8. p. 104−108.

35. Smith M. К. Universal enveloping algebras with subexponential but not polynomially bounded growth// Proc. Amer. Math. Soc 1976.-60.-p. 22−24.

36. Zharkov A. Y., Blinkov Y. A Involutive approach to solving systems of algebraic equations// Proc. of «SC'93», intern. IMACS symposium on symbolic computations.-LIFL: Lille.- 1993.-p. 11−16.

37. Аппанова JI. Ю. Об алгоритмической распознаваемости свойств строго-градуированных алгебр и алгебр со строгой фильтрацией /Деп. в ВИНИТИ. N 930-В 00. — 2000.

38. Appanova L. U. The growth type of the Lie s.f.p.-algebra is recognizable// Suppl. abstracts of the 12th intern, conf. FPSAC'00, Moscow, June 2000. Moscow. — 2000. — p. 3−4.

39. Аппанова JI. Ю. P-стандартный базис полиномиальных идеалов/ / в сб. Ученые записки УлГУ. Фунд. проблемы математики и механики. / Под ред. проф. А. С. Андреева. Выпуск 1(8). — Ульяновск. УлГУ. — 2000 — с. 21−30.

40. Аппанова JI. Ю. О распознаваемых свойствах подалгебр моно-миалъных алгебр, заданных конечным S AG ВI-базисом/ Деп. в ВИНИТИ. N 2413-В 00. — 2000.

41. Аппанова Л. Ю. Проблемы коммутативности // Труды молодых ученых Ульяновского государственного университета: Сборник докладов и тезисов докладов студентов и аспирантов на VI ежегодной научно-практической конференции. Ульяновск. УлГУ. — 1997. — с. 3−4.