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

1 Введение

2 Экспоненциальные диофантовы уравнения

2.1 Постановка задачи.

2.2 Уравнения над кольцом многочленов

2.2.1 Прополки и их свойства.

2.2.2 Специальные операторы уравнения

2.2.3 Типы и их продолжения.

2.3 Уравнения над кольцом матриц

2.3.1 Лемма о сведении

2.3.2 Лемма о сопряжении.

2.3.3 Прополки и специальные операторы

2.3.4 Типы и их продолжения.

3 Ряды Тейлора алгебраических функций

3.1 Постановка задачи.•.:.

3.2 Поле вычетов.

3.3 Чисто трансцендентные расширения поля вычетов

3.4 Алгебраические расширения

4 Алгоритмы и примеры построения автоматов

4.1 Пример применения общего алгоритма

4.2 Построение автоматов над полем F2.

4.3 Построение автоматов над полем F3.

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

В конце прошлого столетия Д. Гильберт поставил следующий вопрос: Существует ли универсальный метод, позволяющий найти хотя бы одно решение системы алгебраических уравнений в целых числах или установить, что их нет (десятая проблема Гильберта)?

На современном языке это означает следующее: Существует ли алгоритм, реализуемый на абстрактной вычислительной машине (например, машине Тьюринга), позволяющий для каждой системы алгебраических уравнений в целых числах найти ее решение (хотя бы одно) или установить, что таких решений не существует?

На вход этому алгоритму подается система, заданная, к примеру, своими коэффициентами. Результатом работы алгоритма должен быть ответ — решение системы, если оно существует, или сообщение об их отсутствии.

Иными словами: Верно ли, что проблема отыскания решений таких систем алгоритмически разрешима?

Наряду с алгебраическими уравнениями, более общие — экспоненциально-диофантовы уравнения в целых числах (ЭДУ), также часто возникают в ряде алгоритмических задач, например, связанных с изучением нормальных базисов алгебр и проблем изоморфизма. Под экспоненциально-диофантовыми уравнениями подразумеваются уравнения вида s

Е Pij(n>h ■ • • > n^bijoaifrbiji ■ ■ ■ aYjtkjt = 0 (1) г=1 где щ,. ,nt € N — неизвестные, Рц — полиномы от них с коэффициентами в некотором кольце 7Z, сщк.Ь^и — элементы того же кольца 71. Например, вопрос об устройстве нормаль3 ных базисов в алгебрах, а также проблемы изоморфизма связаны с изучением решений систем экспоненциально-диофан-товых уравнений.

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

Это означает следующее: Для любого рекурсивно перечислимого множества М С Nfc найдется такая система ЭДУ с параметрами щ,., щ от неизвестных щ+ь ■ • • > nt-, что множество значений наборов параметров, при которых эта система имеет решение, есть в точности М.

Позднее Ю. В. Матиясевич ([3]) распространил этот результат на случай чисто диофантовых уравнений

Р(пи.,щ) = 0 (2)

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

Однако оказывается, что в случае, когда основания экспонент ciijk, коэффициенты bijk и коэффициенты полиномов Pij лежат в поле положительной характеристики (и даже в матричном кольце над таким полем), проблема нахождения множества решений системы ЭДУ является алгоритмически разрешимой.

Алгоритмические проблемы, относящиеся к системам экс-поненциально-диофантовых уравнений, возникают в различных ситуациях (см. обзор [7]). Очень часто исследование алгоритмических вопросов, относящихся к алгебраическим систе4 мам осуществляется путем их вложения в алгебры, конечномерные над кольцом многочленов (или в алгебру Ли векторных полей на многообразиях). Например, свободная группа вкладывается в алгебру матриц второго порядка. И алгоритмическая неразрешимость ряда проблем доказывается путем построения представлений и сведения к общей проблеме нахождения решений системы диофантовых, либо экспоненциально диофантовых уравнений. В этой связи следует упомянуть работы М. Сапира ([5], [6]), О. Харлампович ([8]) и ряда других авторов ([17], [23], [24]).

Одним из примеров такого рода является проблема изоморфизма представимых алгебр (т.е. подалгебр алгебры матриц над кольцом многочленов). В частности, из алгоритмической неразрешимости проблемы существования решений у системы ЭДУ следует алгоритмическая неразрешимость проблемы изоморфизма двух подалгебр алгебры матриц над кольцом многочленов над полем. Такого рода проблемы исследовались в литературе (см. [22], [23], [24]).

Еще одним из побудительных мотивов для исследования таких уравнений послужило изучение нормальных базисов алгебр ([18], [19], [20], [21]). Пусть аг . -< at — упорядоченный набор образующих алгебры А над полем Т. Порядок -< на образующих индуцирует лексикографический порядок на множестве слов от {аг}. Нормальным базисом М алгебры А называется ее базис как векторного пространства над Т, состоящий из неуменьшаемых (т.е. не представимых в виде линейной комбинации меньших слов) элементами. Если А является Р/-алгеброй (в частности, если А представима матрицами над Т\ то, в силу теоремы Ширшова о высоте ([9], [10]), существует такое h = ht(А) и конечный набор v\,., vs элементов А, 5 что М состоит из элементов вида к\ kf V- ■ ■ • Vuii uit где t < h. В связи с этим встает вопрос об устройстве множества векторов степеней (ki,., kt), в частности, в представи-мом случае. Если алгебра А представима и мономиальна (т.е. определяющие соотношения имеют вид Uj = 0, где Uj — мономы), то вопрос о нормальном базисе допускает, в некотором смысле, полный ответ. Имеет место ([11]) следующая

Теорема (критерий представимости мономиальной алгебры). Мономиалъная алгебра А является представимой тогда и только тогда, когда А имеет ограниченную высоту над некоторым конечным множеством слов v\,. :Vt, мно-otcecmeo определяющих соотношений разбивается на конечное число серий v\l • • ■ v^ — 0; где

2Pij{k\, ■. ■, kt)ciji ■ ■ ■ с^ = О i и каждой серии отвечает своя система ЭДУ.

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

Алгоритмическая неразрешимость проблем, относящихся к свойствам алгебр Хопфа также доказывается путем сведения их к системам экспоненциально-диофантовых уравнений (см.

117])

Тем не менее, в случае характеристики р > 0 ситуация иная. Хотя диофантовы проблемы здесь возникают чаще, они, 6 тем не менее, проще решаются. Множество решений ЭДУ допускает эффективное описание в терминах р-ичного разложения неизвестных ni,., nt. Поскольку значения многочленов Ру(щ,., щ) периодичны с периодом р по всем щ, ситуация сводится к исследованию уравнений вида сТ---спг = О 1=1

Каждое решение уравнения (системы уравнений) представляет собой вектор (ni,., nt). Каждой его компоненте щ сопоставим ее р-ичную запись к О щ = щ . щ

Тогда каждому решению отвечает последовательность кортежей цифр

Будем интерпретировать эти кортежи как буквы. В этом случае их последовательности есть слова над алфавитом из кортежей. Т.е. каждому решению соответствует слово. Множество всех слов, отвечающих решениям ЭДУ, образует язык над конечным алфавитом. А. Я. Беловым был поставлен вопрос об устройстве данного языка.

Имеет место следующий результат

Теорема 1. Множество слов, отвечающих решениям системы ЭДУ над матрично представимым кольцом положительной характеристики, является регулярным языком. Существует эффективный алгоритм построения конечного автомата, задающего этот язык.

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

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

Регулярные языки, в свою очередь, являются объектом, хорошо изученным в теории формальных языков. Теорема Клини утверждает, что любой такой язык может быть задан при помощи конечного автомата (доказательство этого утверждения, как и многие другие факты из теории формальных языков, можно найти в [4]).

Иными словами, существует ориентированный граф, стрелки которого помечены буквами, символизирующими кортежи цифр (всего букв рг). Одна из вершин объявлена начальной, а некоторые другие — финальными. При этом существует взаимно-однозначное соответствие между решениями нашей системы и словами, которые могут быть прочитаны, идя по стрелкам данного графа из начальной вершины в финальную. При этом пути могут иметь любую длину, и каждая из вершин (в том числе начальная и финальные) могут быть пройдены любое число раз. Такой граф как раз и называется конечным автоматом.

Имеется эффективный алгоритм построения такого графа. Этот алгоритм и будет описан ниже.

Возможность эффективного построения конечного автомата, распознающего решения системы, влечет алгоритмическую разрешимость задачи о существовании решений. В самом деле, 8 имея автомат, можно легко установить, существуют ли пути, ведущие из начальной вершины в финальную (хотя бы полным перебором). Если такие пути существуют — система имеет решение, и его легко построить. Если же таких путей нет — то нет и решений.

В частности, хотя проблема изоморфизма двух подалгебр алгебры матриц над кольцом многочленов над полем алгоритмически неразрешима, тем не менее, есть надежда на отыскание алгоритма, решающего эту задачу в случае любой положительной характеристики основного поля. В случае мономи-альных алгебр существование такого алгоритма сразу следует из Теоремы 1 и критерия представимости мономиальной алгебры. Появилась надежда на положительное решение и некоторых других алгоритмических задач.

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

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

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

Пусть Р{х — экспоненциально-диофантов полином. Тогда 9 есть ряд Тейлора рациональной функции. Экспоненциально-диофантово уравнение

Р(хи .,хк)= О эквивалентно обращению в 0 соответствующего коэффициента ряда Тейлора. Теорема 1 очевидным образом влечет алгоритмическую разрешимость вопроса о существовании нулей среди коэффициентов ряда Тейлора соответствующей функции.

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

В общем случае встает вопрос об отыскании коэффициентов ряда Тейлора, а точнее, о построении автомата, вычисляющего соответствующий коэффициент по его порядковому номеру. Более слабая постановка вопроса такова — построить автомат, решающий уравнение xv = w (3) где х — степенной ряд, v = (Vi,., vn) — мультииндекс, коэффициент ряда при ^ • • • , ш — произвольный элемент базового поля. Ясно, что эти вопросы эквивалентны в случае, когда базовое поле конечно.

В случае конечного поля исчерпывающий ответ дает следующий ([15]) результат, принадлежащий G. Christol, Т. Катае, М. Mendes-France, G. Rauzy.

Теорема. Ряд Е а рХ является рядом Тейлора алгебраической функции тогда и только тогда, когда существует конечный р-автомат, порождающий последовательность коэффициентов av.

10

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

Отметим, что если ряд T,clvxU представляет рациональную функцию, то последовательность коэффициентов периодична по каждой координате и в этом случае теорема тривиализует-ся.

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

Теорема. Ряд £ CLVX ЯвЛЯбТПСЯ рядом Тейлора алгебраической функции тогда и только тогда, когда существует е, такое что при всех j = (ji,--.,Jn) с условием ji < ре найдутся е' < е и j' = ., j'n) с условием j\ < ре' , для которых apeu+j = ape'l/+j,

Его доказательство можно найти в [15] и [16]. Хороший обзор результатов, относящихся к рядам Тейлора алгебраических функций приведен также в статьях [12], [13], [14].

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

Автором была установлена

Теорема 2. Пусть Т — поле положительной характеристики р, Е avxv — ряд Тейлора алгебраической функции над Т. Тогда множество значений v, для которых аи = А; где А — произвольный элемент поля J-, разрешимо и распозна

11 ется конечным р-автоматом. Такой автомат может быть эффективно построен по уравнению, задающему функцию, и значению А.

Эта теорема является обобщением, с одной стороны, упомянутой выше теоремы G. Christol, Т. Kamae, М. Mendes-France, G. Rauzy для бесконечного основного поля, а с другой стороны — Теоремы 1.

Следствие. Задача о существовании заданного значения среди коэфициентов ряда Тейлора алгебраической функции алгоритмически разрешима в случае, если базовое поле имеет положительную характеристику.

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

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

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

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

12 жительной характеристики.

Наконец, в третьей части рассмотрены практические алгоритмы и примеры построения конечных автоматов, представляющих ряды Тейлора.

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

Также автор выражает глубокую благодарность доктору физико-математических наук, профессору Георгию Борисовичу Шабату, кандидату физико-математических наук, доценту Николаю Германовичу Мощевитину, доктору физико-математических наук, профессору Виктору Николаевичу Латышеву, доктору физико-математических наук, профессору Александру Александровичу Нечаеву, кандидату физико-математических наук Михаилу Николаевичу Вялому, кандидату физико-математических наук Сергею Павловичу Тарасову за ценные замечания и внимание к работе.

13

1. Коблиц Н. р-адические числа, р-адический анализ и дзета-функции. Москва,"Мир", 1982.

2. Ленг С. Алгебра. Москва,"Мир", 1968.

3. Матиясевич Ю. В. Десятая проблема Гильберта. Москва, "Наука", 1993.

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

5. Сапир М. В. Проблемы бернсайдовского типа и конечная базируемость в многообразиях полугрупп. Изв. АН СССР. Сер. мат., 1987, Vol51, №2, р319-340. (РЖМат, 1987, 7А143)

6. Сапир М. В. Минимальное многообразие ассоциативных алгебр с неразрешимой проблемой равенства. Мат. сб., 1989, Voll80, №12, р1691-1708. (РЖМат, 1990, 4А212)

7. Уфнаровский В. А. Комбинаторные и асимптотические методы в алгебре. Итоги науки и техн. Сер. Соврем, пробл. мат. Фундам. направления. — М.: ВИНИТИ, 1990, Vol57, р5-177. (РЖМат, 1990, 7А338)

8. Харлампович О. Г. Проблема равенства для разрешимых алгебр Ли и групп. Мат. сб., 1989, Voll80, №8, рЮЗЗ-1066. (РЖМат, 1990, 2А191)

9. Ширшов А. И. О некоторых неассоциативных нилькольцах и алгебраических алгебрах. Мат. сб., 1957, Vol41, №3, р381—394. (РЖМат, 1958, 164)86

10. Ширшов А. И. О кольцах с тождественными соотношениями. Мат. сб., 1957, Vol43, №2, р277-283. (РЖМат, 1958, 7544)

11. Christol G., Kamae Т., Mendes-Franee M. and Rauzy G. Suites algebriques, automates et substitutions. , Bull. Soc. Math. France 108, p401-419, 1980

12. Denef J. and Lipshitz L. Algebraic power series and diagonals. J. Number Theory 26, p46-67, 1987

13. Anick D. Non-commutative graded algebras and their Hilbert series. J. Algebra, 1982, Vol78, №1, pl20-140. (РЖМат, 1983, 3A354)

14. Le Chenadec P. Canonical forms in finetely presented algebras. Research Notes in Theoretical Computer Science, Pitman, 1986,87

15. Mora F. Greoebner bases for non-commutative polinomial rings. Proc. AAEECC3, L.N. Сотр. Sci, 1986, Vol229, p353-362.

16. Bergman G. Centralizers in free associative algebras. Trans. Amer. Math. Soc., 1969, Voll37, p327-344. (РЖМат, 1970, 2A242)

17. Anick D. The smallest singularity of a Hilbert series. Math, scand., 1982, Vol51, p35-44.

18. Cohn P. Free rings and their relations. — London-New York: Acad. Press, 1971, p346. (РЖМат, 1972, 11A105K). (Пер. на рус. яз.: Кон П. Свободные кольца и их связи. — М.: Мир, 1975. 422 с. (РЖМат, 1976, 5А259К))

19. Shirayanagi К. Decision of Algebra Isomorphisms Using Grobner Bases. In book: Computational algebraic geometry (F. Eyssette and A. Galligo eds.). Progr. in Math. Birkhauser, 1993. 109, p253-265.