ПРОГРАММИРОВАНИЕ, 2014, No 2, с. 26 31
КОМПЬЮТЕРНАЯ АЛГЕБРА
ЗАДАЧА ПРОВЕРКИ СУЩЕСТВОВАНИЯ РЕШЕНИЙ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ В ЧАСТНЫХ ПРОИЗВОДНЫХ В ПОЛЯХ ЛОРАНОВЫХ РЯДОВ *
© 2014 г. C.B. Парамонов МГУ им. М.В. Ломоносова, факультет вычислительной математики и кибернетики 119991 Москва, ГСП-1, Ленинские горы, МГУ, д. 1, стр. 52 E-mail: s. v.paramonov@yandex. ru Поступила в редакцию 24.09.2013
Доказывается алгоритмическая неразрешимость задачи проверки существования решений в поле лорановых рядов для линейных дифференциальных уравнений в частных производных с полиномиальными коэффициентами. Дополнительно устанавливается разрешимость задачи проверки существования мономиальных решений с вещественными и комплексными показателями степеней.
1. ВВЕДЕНИЕ
Будем рассматривать линейные однородные уравнения в частных производных, имеющие вид
£ а«(х^«у(х) = 0 (1)
где
• х = (х\,... ,хт) — вектор независимых переменных,
• в = (в1,..., вт) — мультипоказатель,
• у(х) = у(х1,..., хт) — неизвестная функция от т переменных,
• £ — конечное подмножество множества ,
• а«(х) — полиномы над некоторым фиксированным полем К характеристики 0,
• Ds = DS1 ... , при этом Di = дХ — частная производная по Xi.
Далее также будем использовать оператор 5, определяемый следующим образом:
5i = XiDi, 5« = 5«1 ...5«т.
*Частичная поддержка РФФИ, грант 13-01-00182-а.
При m = 1, т.е. в случае одной переменной, уравнение (1) становится обыкновенным дифференциальным уравнением. Для таких уравнений известны и реализованы в системах компьютерной алгебры эффективные алгоритмы поиска всех полиномиальных и рациональных решений (см. [10]), а также решений в виде формальных
m
универсальных алгоритмов нет. Доказательства алгоритмической неразрешимости задач проверки существования решений в виде полиномов (см. [1]) и рациональных функций (см. [16]) опираются на то, что для подмножества уравнений (1) вида
^ asôsy(x)=0, as G Z, (2)
ses
эти задачи эквивалентны задаче проверки существования решений вида xn, где n G Nm или соответственно n G Zn, которая в свою очередь неразрешима, так как эквивалентна алгоритмически неразрешимым (см. [15]) задачам проверки существования решения произвольного ди-офантова уравнения в целых неотрицательных или соответственно целых числах.
В [6, теорема 4.11] показано, что не существует алгоритма проверки существования решений в виде формальных степенных рядов (т.е. решений
в К [[х]]) для неоднородных уравнений в частных производных с полиномиальными коэффициентами и с правой частью, равной 1. Позднее в [1] с применением техники доказательства, близкой к использованной в [6], было установлено, что и для однородных уравнений вида (1) не существует алгоритма проверки существования ненулевых решений в кольце формальных степенных рядов.
В настоящей статье для линейных дифференциальных уравнений в частных производных вида (1) рассматривается задача проверки существования решений в некотором поле лорановых рядов. Известны разные подходы к тому, что считать формальным лорановым рядом нескольких переменных с коэффициентами в поле К. Во введении, содержащемся в статье [3], можно найти обзор публикаций по этой теме.
В разделе 2 мы обобщаем два используемых в компьютерной алгебре подхода к определению этого понятия. Основываясь на этом обобщении, в разделе 3 доказывается алгоритмическая неразрешимость задачи проверки существования решений в поле формальных лорановых рядов нескольких переменных. В разделе 4 аналогичная задача рассматривается для рядов с дробными показателями и также доказывается ее алгоритмическая неразрешимость (в предположении неразрешимости задачи проверки существования решения произвольного диофанто-ва уравнения в рациональных числах, что в данный момент остается гипотезой). В [4] продемонстрировано, что в некоторых случаях можно проверять существование и находить решения в виде рядов с дробными показателями даже для нелинейных уравнений, при этом авторы отмечают, что полной гарантии успеха нет; из доказанного нами следует, что этот метод не может быть доведен до уровня алгоритма, даже если ограничиться линейными уравнениями вида (2). В разделе 5 показывается алгоритмическая неразрешимость аналогичных задач распознавания существования решений в виде сходящихся рядов.
Дополнительно в разделе 6 для уравнений вида (1) устанавливается разрешимость задачи проверки существования мономиальных решений с вещественными и комплексными показателями степеней.
2. ЛОРАНОВЫ РЯДЫ
В случае единственной переменной х понятия кольца формальных степенных рядов К [[х]] и поля формальных лорановых рядов К ((х)) с коК
К((х))
К[[х]]
каждый ненулевой элемент / £ К ((х)) имеет обратный /-1 £ К((х)) и частное двух рядов так-
К((х))
В случае нескольких переменных существуют различные подходы к тому, что считать формальным лорановым рядом — они упоминаются, например, в [3]. Далее мы рассмотрим два таких подхода.
Первый подход (классический) — рассмотрение поля отношений К((х)) кольца формальных степенных рядов К [[х]]. Для этого устанавливается порядок переменных. Если выбран порядок х^, х^2,...,х^т, где г1,г2,..., ¿т — некоторая перестановка индексов 1, 2, ...,т, то поле лорановых рядов вводится итеративно как К((х^))((х,2))... ((х,т)). Заметим, что, например, (х1 + х2)-1 при т = 2 представляется по-разному в зависимости от того, выбран ли поря-
х1, х2 х2, х1
ем ^ (—1)гх-г+1х2, то втором — ^ (—1)гх-г+1х1.
г=0 г=0
Эти представления различаются: первое из них содержит слагаемые с любыми отрицательными
х1
ких слагаемых нет. Однако вводимые таким образом поля изоморфны полю, соответствующему порядку х1, х2,..., хт, и тем самым изоморфны друг другу.
Второй подход, используемый в ряде работ в последние годы, основывается на понятии конуса, в пространстве Мт (см. [4], [3]). К опус С С Мт — это такое множество, что для любых и £ Си с ^ 0 выполнявтся си £ С. Конус С называется конечно порожденным, если существуют такие £ Мт, что
С = |С1^1 + С2^2 +-----+ Спу,п | С1, С2, . . . ,Сп £ М^о}.
Набор ^1, ^2,..., Уп является порождающим,
С
ет целочисленное порождающее множество 21,22,...,2п £ Zm, то этот конус называется
рациональным. Конус О является строго выпуклым, если для любого и € О \ {0} верно, что —и € О. Далее под словом "конус" будет подразумеваться конечно порожденный, рациональный, строго выпуклый конус.
Если О С Кт — некоторый конус, х = (х1,х2,..., хт), то по определению
Кс[[х]] = { £ а„хга | ап € К}.
пес с(1т
Тотальное (т.е. определенное для всех пар элементов) отношение порядка : на множестве Ът называется аддитивным,, если для любых 1,3, к € 2т верно, что
г : 3 ^ г + к : 3 + к.
О
ным отношением порядка если для любого и € О П Zm верно, что 0 : и.
Пусть : — некоторое аддитивное отношение порядка, Т — множество всех конусов, совместимых с -<. Полагая
К^[[х]] = У Кс [[х]]
сет
К^((х)) = У х7К^[[х]]
Обобщая эти два подхода, можно назвать полем формальных лорановых рядов переменных х1,х2,..., хт над пол ем К любое такое поле Л,
К [И] С Л С К [[х, х-1]], (3)
здесь
получаем соответственно кольцо К^ [[х]] и поле К^((х)), связанные с отношением При этом К^((х)) всегда является полем отношений для кольца К^[[х]] (см. [3]). Для т = 1 кольцо обыкновенных степенных рядов К [[х]] и поле лорановых рядов К ((х)) являются частным случаем введенных кольца и поля: если в качестве : использовать стандартное от ношение < (а в одномерном варианте существуют только два аддитивных отношения: стандартное и обратное ему), то единственным совместимым с ним конусом будет луч [0, (всего возможных конусов в данном случае также два: (—те, 0] и [0, +те)).
Второй из описанных подходов к определению поля лорановых рядов многих переменных более гибок, чем первый: при т > 1 существует бесконечное число возможностей для выбора отношения порядка : при втором подходе и лишь т! возможностей выбора порядка переменных при первом. Неизвестно, изоморфно ли каждое из полей К^((х)) полю К ((х)).
• К[[х?]] = К[[х?1 ,...,хтг]], где йг = ±1 г =
1,2,...,т,
• К[[х, х-1]] = К[[х1, ...,хт,х-1, ...,хт1 ]] — кольцо всех формальных сумм ^ апхп.
пеът
Это кольцо содержит делители нуля (даже в
случае одной переменной: (х — 1) ^ хп = 0)
пе1
и не является полем.
Очевидно, что поле Л = К((хг1 ))((хг2))... ((хгт)) удовлетворяет условию (3) при любой перестановке ¿1, г2,..., гт индекс ов 1, 2,... ,т. Докажем, что этим свойством обладают и рассматриваемые поля К^((х)).
Предложение 1. Для любого аддитивного тотального отношения порядка, : на, Zm поле Л = К^ ((х)) при некоторых йг = ±1, г = 1, 2,... ,т, удовлетворяет условию (3).
Доказательство. Сначала покажем, что найдутся такие йг = ±1 г = 1,2,... ,т, что
К[[х?1 ,...,хт]] С К^[[хЬ...,хт]]. Пусть ег = (0, 0,..., 0,1, 0,..., 0) и
г-1
йг =
1, если 0 : ег, —1, если ег : 0,
г = 1, 2,... ,т. Так как отнош ение : аддитивно,
ег : 0 ег — ег : 0 — ег
йг = —1 0 : —ег
Таким образом, если 0 : йгег, при г = 1,2,..., т, то 0 : п1 й1е1 + ■ ■ ■ + птйтет для любого ненулеого п € 2то- Следовательно, конус О = {С1й1е1 + С2й2е2 + ■ ■ ■ + Стйтет | с1, С2,..., сп € Д^о} совместим с А так как
К [[х?1,.. Кс [[х1,
хт ]] = Кс [[х1,...,хт]],
, хт]] С К^[[хЬ... , хт]],
то К [[ж?1 , ...,жт ]] С К^[[жь... ,жт]]- Из доказанного и включения К^[[ж1,..., жт]] С К^ ((ж1,..., жт)) следует, что для любого отношения найдутся такие й = ±1 г = 1,2,..., ш,
К [[ж!1 ,...,жт ]] с К^((жь...,жт)).
Очевидно, что любое поле К^((х)) принадлежит К [[х, х-1]]. □
В следующем разделе мы рассматриваем вопросы существования решений в полях лорано-вых рядов для уравнений вида (1). Если существует поле Л, удовлетворяющее условию (3), и в этом поле существует решение заданного уравнения такого вида, то будем говорить, что уравнение имеет лораново решение.
3. АЛГОРИТМИЧЕСКАЯ НЕРАЗРЕШИМОСТЬ ЗАДАЧИ ПРОВЕРКИ СУЩЕСТВОВАНИЯ ЛОРАНОВЫХ РЕШЕНИЙ
Л
условию (3). Тогда алгоритмически неразрешима задача проверки существования решений в Л
(п) Пусть М — фиксированное непустое множество полей, удовлетворяющих условию (3). Тогда алгоритмически неразрешима
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.