Содержание
1 Введение 3
2 Экспоненциальные диофантовы уравнения 14
2.1 Постановка задачи......................... 14
2.2 Уравнения над кольцом многочленов ............. 19
2.2.1 Прополки и их свойства.............. 21
2.2.2 Специальные операторы уравнения ... 23
2.2.3 Типы и их продолжения................... 26
2.3 Уравнения над кольцом матриц ................... 31
2.3.1 Лемма о сведении ....................... 31
2.3.2 Лемма о сопряжении...................... 38
2.3.3 Прополки и специальные операторы ... 41
2.3.4 Типы и их продолжения............... 44
3 Ряды Тейлора алгебраических функций 49
3.1 Постановка задачи............................. 49
3.2 Поле вычетов.............................. 50
3.3 Чисто трансцендентные расширения поля вычетов 58
3.4 Алгебраические расширения................. 65
4 Алгоритмы и примеры построения автоматов 73
4.1 Пример применения общего алгоритма......... 73
4.2 Построение автоматов над полем Гг......... 75
4.3 Построение автоматов над полем Гз......... 80
4.4 Алгоритмы построения автоматов для производных функций................................. 82
1 Введение
В конце прошлого столетия Д. Гильберт поставил следующий вопрос: Существует ли универсальный метод, позволяющий найти хотя бы одно решение системы алгебраических уравнений в целых числах или установить, что их нет (десятая проблема Гяльберта)?
На современном языке это означает следующее: Существует ли алгоритм, реализуемый на абстрактной вычислительной машине (например, машине. Тьюринга), позволяющий для каждой системы алгебраических уравнений в целых числах найти ее решение (хотя бы одно) или уетшю-вить, что таких решений не существует?
На вход этому алгоритму подается система, заданная, к примеру, своими коэффициентами. Результатом работы алгоритма должен быть ответ — решение системы, если оно существует. или сообщение об их отсутствии.
Иными словами: Верно ли, что проблема отыскания решений таких систем алгоритмически разрешима?
Наряду с алгебраическими уравнениями, более общие экспоненциа.гьно-диофантовы уравнения в целых числах (ЭДУ), также часто возникают в ряде алгоритмических задач, например, связанных с изучением нормальных базисов алгебр и проблем изоморфизма. Подэкспоненциально-диофантовыми уравнениями подразумеваются уравнения вида
£ РііІЩ, • - • і = 0 (1)
»=1
где Є N — неизвестные, Ру полиномы от них с
коэффициентами в некотором кольце Я, о^*, 6,-д- — элементы того же кольца 71. Например, вопрос об устройстве нормаль-
з
ных базисов в алгебрах, а также проблемы изоморфизма связаны с изучением решений систем экспоненциально-диофан-товых уравнений.
Д. Робинсон установила, что общая проблема о существовании решений у системы таких уравнений алгоритмически неразрешима. Более точно, ей было показано, что проекция множества решений системы ЭДУ может быть произвольным рекурсивно перечислимым множеством.
Это означает следующее: Для любого рекурсивно перечислимого множества М С М* найдется такая система ЭДУ с параметрами щ,.... п* от неизвестных п*+ь • • •, п*, что множество значений наборов параметров, при которых эта система имеет решение, есть в точности М.
Позднее К). В. Матиясевмч (|3|) распространил этот результат на случай чисто диофантовых уравнений
Р(пь...;п,) = 0 (2)
Тем самым он установил алгоритмическую неразрешимость проблемы существования решений у чисто диофантовых уравнений, и таким образом, получил отрицательное решение десятой проблемы Гильберта.
Однако оказывается, что в случае, когда основания экспонент йщ, коэффициенты и коэффициенты ПОЛИНОМОВ Р{} лежат в поле положительной характеристики (и даже в матричном кольце над таким полем), проблема нахождения множества решений системы ЭДУ является алгоритмически разрешимой.
Алгоритмические проблемы, относящиеся к системам экс-поненциалыю-диофантовых уравнений, возникают в различных ситуациях (см. обзор [7]). Очень часто исследование алгоритмических вопросов, относящихся к алгебраическим систс-
4
мам осуществляется путем их вложения в алгебры, конечномерные над кольцом многочленов (или в алгебру Ли вектоі>-ных полей на многообразиях). Например, свободная группа вкладывается в алгебру матриц второго порядка. И алгоритмическая неразрешимость ряда проблем доказывается путем построения подставлений и сведения к общей проблеме нахождения решений системы диофантовых, либо экспоненциально диофантовых уравнений. В этой связи следует упомянуть работы М. Самира ((5), |6|), О. Харлампович (|в|) и ряда других авторов {(17], [23], |24]).
Одним из примеров такого рода является проблема изоморфизма представимых алгебр (т.е. подалгебр алгебры матриц над кольцом многочленов). В частности, из алгоритмической неразрешимости проблемы существования решений у системы ЭДУ следует алгоритмическая неразрешимость проблемы изо морфизма двух подалгебр алгебры матриц над кольцом многочленов над полем. Такого рода проблемы исследовались в литературе (см. [22], [23], (24]).
Еще одним из побудительных мотивов для исследования таких уравнений послужило изучение нормальных базисов алгебр ([18], 119]. (20], [21]). Пусть в* — упорядочен-
ный набор образующих алгебры А над полем Т. Порядок -< на образующих индуцирует лексикографический порядок па множестве слов от {а,}. Нормальным базисом М алгебры А называется ее базис как векторного пространства над Я, состоящий из нсуменыиасмых (т.е. не представимых в виде линейной комбинации меньших слов) элементами. Если А является Я/-алгеброй (в частности, если А представима матрицами над Р), го. в силу теоремы Ширшова о высоте ([9], |1и|), существует такое Н. = Ііі(А) и конечный набор ..., элементов А.
5
что М состоит из элементов вида
где £ < Л. В связи с этим встает вопрос об устройстве множества векторов степеней (А'1,..., к(), в частности, в представимом случае. Если алгебра А представима и мономиальна (т.е. определяющие соотношения имеют ВИД Щ = 0. где II) — мономы), то вопрос о нормальном базисе допускает, в некотором смысле, полный ответ. Имеет место ([11|) следующая
Теорема (критерий представимости мономиальной алгебры). Мономиальная алгебра А яв.гяется представимой тогда и только тогда, когда А имеет ограниченную высоту над некоторым конечным множеством слов VI,...,V*, множество определяющих соотношений разбивается на конечное число серий в*1 • • • Ь(* = 0, где
Е а#, ьИЗг-■<& = »
1
и каждой еерии отвечает своя система ЭДУ.
Из этой теоремы, в частности, следует существование пред-ставимых аэнебр с трансцендентным рядом Гильберта, а также алгоритмическая неразрешимость проблемы изоморфизма двух подалгебр алгебры матриц над кольцом многочленов над полем.
Алгоритмическая неразрешимость проблем, относящихся к свойствам алгебр Хопфа также доказывается путем сведения их к системам экспоненциально-диофантовых уравнений (см.
117])-
Тсм не менее, в случае характеристики р > 0 ситуация иная. Хотя диофанговы щюблемы здесь возникают чаще, они.
6
- Київ+380960830922