Алгоритмические проблемы в кольцах положительной характеристики

• Автор: Чиликов, Алексей Анатольевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Москва
• Количество страниц: 89 с.

Содержание
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 Построение автоматов над полем Т■>
4.3 Построение автоматов над полем Ез
4.4 Алгоритмы построения автоматов для производных функций

1 Введение
В конце прошлого столетия Д. Гильберт поставил следующий вопрос: Существует ли универсальный метод, позволяющий найти хотя бы одно решение системы алгебраических уравнений в целых числах или установить, что их нет (десятая проблема Гильберта)?
На современном языке это означает следующее: Существует ли алгоритм, реализуемый на абстрактной вычислительной машине (па,прим,ер, машине Тьюринга), позволяющий для каждой системы алгебраических уравнений в целых числах найти ее решение (хотя бы одно) или установить, что таких решений не существует?
На вход этому алгоритму подается система, заданная, к примеру, своими коэффициентами. Результатом работы алгоритма должен быть ответ — решение системы, если оно существует, или сообщение об их отсутствии.
Иными словами: Верно ли, что проблема отыскания решений таких систем алгоритмически разрешима?
Наряду с алгебраическими уравнениями, более общие — экспоненциально-диофантовы уравнения в целых числах (ЭДУ), также часто возникают в ряде алгоритмических задач, например, связанных с изучением нормальных базисов алгебр и проблем изоморфизма. Под экспоненциально-диофантовыми уравнениями подразумеваются уравнения вида
Рц(п,..., • • • а^Ьір = 0 (1)

ГДЄ П, . . . , Щ Є N — НеИЗВеСТНЫе, Рі] — полиномы от них с коэффициентами в некотором кольце 7£, Оу*, 6^ элементы того же кольца %. Например, вопрос об устройстве нормаль-

ных базисов в алгебрах, а также проблемы изоморфизма связаны с изучением решений систем экспоненциально-диофан-товых уравнений.
Д. Робинсон установила, что общая проблема о существовании решений у системы таких уравнений алгоритмически неразрешима. Более точно, ей было показано, что проекция множества решений системы ЭДУ может быть произвольным рекурсивно перечислимым множеством.
Это означает следующее: Для любого рекурсивно перечислимого множества М С ^ найдется такая система ЭДУ с параметрами щ,..., п* от неизвестных га^+і,..., щ, что множество значений наборов параметров, при которых эта система имеет решение, есть в точности М.
Позднее Ю. В. Матиясевич ([3]) распространил этот результат на случай чисто диофантовых уравнений
Р(щ,...,п() = 0 (2)
Тем самым он установил алгоритмическую неразрешимость проблемы существования решений у чисто диофантовых уравнений, и таким образом, получил отрицательное решение десятой проблемы Гильберта.
Однако оказывается, что в случае, когда основания экспонент коэффициенты Ьу* и коэффициенты полиномов Ру лежат в поле положительной характеристики (и даже в матричном кольце над таким полем), проблема нахождения множества решений системы ЭДУ является алгоритмически разрешимой.
Алгоритмические проблемы, относящиеся к системам экс-поненциально-диофантовых уравнений, возникают в различных ситуациях (см. обзор [7]). Очень часто исследование алгоритмических вопросов, относящихся к алгебраическим систе-

5) =^4). По теореме о примитивном элементе (см. [2]) любое конечное сепарабельное алгебраическое расширение представимо в виде где £ — корень некоторого сепарабельного
га—1 .
над Т многочлена гп — £ дг1. Рассмотрим матрицу В:
(0 0 ■ ■ 0 /о
1 о ■ ■ 0 /і
• о г-Н ■ 0 h
о 0 ■ ■ 1 In-1 )
Она рациональная стандартного вида, и Т[В] изоморфно •F[£j. Значит, каждое уравнение из 4) является уравнением из 5).
Теперь докажем эквивалентность 5) и 6).
5) => 6). Рассмотрим ЭДУ над И[В'.
±Qi(B')[P;uKB') = о

Пусть / — произвольный .многочлен с коэффициентами из 7с. Матрица В' представляется в виде В' = дВ, д Є И, где В -рациональная матрица стандартного вида. Поэтому f(B') — f(gB) Є Т[В, а следовательно И[В'] С УВ]. Таким образом наше уравнение является ЭДУ над Т{В.
6) =$■ 5) Рассмотрим ЭДУ над J-[B\
±Qi(B)[W](B) = О