ПРОГРАММИРОВАНИЕ, 2010, No 2, с. 7-12
КОМПЬЮТЕРНАЯ АЛГЕБРА -
УДК 004.92+004.94
ОБ ОДНОЙ АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМОЙ ПРОБЛЕМЕ, СВЯЗАННОЙ С РАЗНОСТНЫМИ УРАВНЕНИЯМИ С ПАРАМЕТРАМИ*
© 2010 г. С. А. Абрамов
Вычислительный центр РАН 119991 Москва, ул. Вавилова, 40 E-mail: sergeyabramov@mail.ru Поступила в редакцию 01.06.2009 г.
Рассматриваются линейные разностные уравнения с полиномиальными коэффициентами, зависящими от параметров. Доказывается алгоритмическая неразрешимость проблемы распознавания существования таких значений параметров, при которых уравнение имеет полиномиальное решение, или, в другом варианте, решение в виде рациональной функции (аналогично доказанной ранее Ж.-А. Вейлем неразрешимости для дифференциального случая).
1. ВВЕДЕНИЕ
В настоящее время в компьютерной алгебре и близких ей дисциплинах известно уже довольно большое число алгоритмически неразрешимых проблем. Часть этих проблем относится к обыкновенным дифференциальным уравнениям, преимущественно - к алгебраическим дифференциальным уравнениям, имеющим вид / (х, у', у'',.у(р)) = 0, где / - полином с коэффициентами в поле Q рациональных чисел (см., например, работу [1], которая посвящена вопросам алгоритмической разрешимости и неразрешимости, связанным с такими дифференциальными уравнениями, и содержит, помимо оригинальных результатов, еще и некоторый вводный обзор публикаций по этой теме). Линейные дифференциальные уравнения с полиномиальными коэффициентами являются частным случаем алгебраических дифференциальных уравнений, и многие вопросы для них выглядят проще, чем для алгебраических дифференциальных уравнений общего вида. Тем не менее и в связи с линейными уравнениями имеются проблемы, не допускающие алгоритмического решения. Неопубли-
* Частичная поддержка РФФИ, грант 10-01-00249-а, и ECONET, грант 21315ZF.
кованный результат Ж.-А. Вейля касается линейных дифференциальных уравнений с полиномиальными коэффициентами, зависящими от параметров: показана невозможность алгоритма, позволяющего узнавать, существуют ли для произвольного заданного уравнения числовые значения параметров, при которых это уравнение имеет решение в виде ненулевой рациональной функции. Результат Ж.-А. Вейля достаточно просто переносится на случай полиномиальных решений дифференциальных уравнений обсуждаемого вида. Этим вопросам посвящен раздел 2 статьи.
Раздел 3 содержит основной результат статьи: показывается, что алгоритмическая неразрешимость, аналогичная установленной Ж.-А. Вей-лем, имеет место и для линейных разностных уравнений с полиномиальными коэффициентами, зависящими от параметров. Отметим, что алгоритмы поиска полиномиальных и рациональных решений не содержащих параметры уравнений с полиномиальными коэффициентами хорошо известны в компьютерной алгебре. Наиболее ранние алгоритмы такого рода можно найти в [2] (дифференциальный случай) и [3,4] (разностный случай).
В разделе 4 обсуждается проблема, видимо, пока открытая, касающаяся уравнений с одним параметром.
О результатах этой статьи кратко сообщалось
в [5].
Автор признателен Ж.-А. Вейлю (Лиможский университет) и С.П. Цареву (Сибирский федеральный университет) за интересные и полезные обсуждения вопросов, затрагиваемых в статье.
2. ДИФФЕРЕНЦИАЛЬНОЕ УРАВНЕНИЕ С ПАРАМЕТРАМИ
Иногда приходится сталкиваться с уравнениями (например, дифференциальными), содержащими параметры. Пусть в уравнении Ь(у) = 0 оператор Ь имеет вид
Гр(Х, tl,. ..,
+rp_l(x,tl,...,tm)Dp_1 + ...+
(1)
где Г0,Г1,...,Гр суть полиномы указанных переменных. Здесь х - независимая переменная, - параметры.
Возникает вопрос, можно ли алгоритмически отыскивать такие значения параметров, при которых уравнение Ь(у) = 0 имеет решения того или иного вида, или хотя бы распознавать существование таких значений. Ж.-А. Вейлю принадлежит следующий результат
1
1 Самим Ж.-А. Вейлем этот результат не опубликован. Со ссылкой на Ж.-А. Вейля доказательство приводится в статье Д. Буше [6], где рассматривается ряд частных случаев задачи поиска точных решений уравнений с параметрами.
Пусть Р(^^2,... ^т) - какой-то полином с целыми коэффициентами. Тогда функция
У (х,им,-..,т) = ехР (^2>->М:
х (х - 1)*1 (х - 2)*2 ... (х - шУт
(2)
при некоторых конкретных числовых значениях т1,т2, ...,тт параметров t1,t2,...,tm является рациональной функцией от х, если и только если Р (Т1,Т2, ...,Тт) = 0 и Т1,Т2,...,Тт е При этом функция У при любых значениях параметров удовлетворяет уравнению
У' - уУ = 0,
т.е. уравнению
41 + +
х — 1 х — 2 +Р (tl,t2,...,tm)^ У = 0,
+
х — т
- +
(3)
Теорема 1. Невозможен алгоритм, который бы для произвольного оператора Ь вида (1) с п(х,Ь^2, ...,т е 0>[х,4ь42 ,.. .^т], г = = 0,1,..., р, отвечал на вопрос, существуют ли числовые значения параметров t1,t2,..., т при которых уравнение Ь(у) = 0 имеет решение в виде ненулевой рациональной функции от х.
Доказательство опирается на теорему Ю.В. Матиясевича о том, что невозможен алгоритм, который бы для произвольного полинома Р {Ь1,42,... , tm) с целыми коэффициентами отвечал на вопрос, имеет ли уравнение Р(t1,t2,...,tm) = 0 решение в целых числах ([7, 8]; эта теорема дает решение в отрицательном смысле десятой проблемы Гильберта).
которое можно домножением на (х — 1)(х— —2)... (х — т) превратить в уравнение с полиномиальными коэффициентами. Следовательно, если бы мы обладали алгоритмом А, отвечающим на вопрос о существовании значений параметров, при которых уравнение Ь(у) = 0 с оператором Ь вида (1) имеет решение в виде рациональной функции, то этот алгоритм позволял бы отвечать на вопрос о том, разрешимо ли при данном Р(^^2, . . . ^т) е Z[tl,t2, ...,т уравнение Р^ь^,...,^) = 0 в целых числах. Для получения ответа достаточно было бы построить дифференциальное уравнение (3), представить его как уравнение с полиномиальными коэффициентами, зависящими от параметров ^^2,..., т и к полученному дифференциальному уравнению применить алгоритм А. Это противоречило бы теореме Матиясевича. □ Результат Ж.-А. Вейля достаточно просто переносится на случай полиномиальных решений дифференциальных уравнений обсуждаемого вида: невозможен алгоритм, который для произвольного оператора Ь вида (1) с ri(x,tl,t2,...,tm) е Щx,tl,t2,...,tm], г = 0, 1,...,р, отвечал бы на вопрос, существуют ли числовые значения параметров 41,42,...,4?п, при которых уравнение Ь(у) = 0 имеет ненулевое полиномиальное решение. Утверждение следует из того, что невозможен алгоритм, который для
г
т
произвольного полинома Р(Ь\,Ь2, ■ ■■, ¿т) с целыми коэффициентами отвечал бы на вопрос, имеет ли уравнение Р(¿г,Ь2, ■ ■ ■ ^т) = 0 решение в неотрицательных целых числах (этот факт является следствием теоремы Матиясевича, так как уравнение Р(¿г,Ь2, ■■■, ¿т) = 0 имеет решение в целых числах, если и только если уравнение
Р(пг - Уг,П2 - Уэ^^^ит - Ут) = 0, (4)
где иг,уг,и2,у2, ■■ ■, ит, Ут - неизвестные, имеет решение в неотрицательных целых числах). Мы видим, что функция (2) является полиномом от х при некоторых конкретных числовых значениях тг ,т2,^ ■ ■, тт параметров ¿т, если и только если тх,^^^,^ суть неотрицательные целые и при этом Р(тг,т2, ■ ■ ■ ,тт) = 0. Рассуждая как прежде, получаем, что если бы мы обладали алгоритмом А, отвечающим на вопрос о существовании значений параметров, при которых уравнение Ь(у) = 0 с оператором Ь вида (1) имеет ненулевое полиномиальное решение, то этот алгоритм позволял бы отвечать на вопрос о том, имеет ли уравнение Р(Ь\,Ь2, ■■■, tm) = 0 при данном полиноме Р(¿г, ¿т) с целыми коэффициентами решение в целых неотрицательных числах.
3. РАЗНОСТНОЕ УРАВНЕНИЕ С ПАРАМЕТРАМИ
В связи с уравнениями с параметрами обратимся к разностному случаю. Оператор Ь теперь имеет вид
Тp(x, tг, ■ ■ ■ , ^т )Е р+ +Тр-1(хМ, ■ ■ ■ ,гт)Ер-1 + ■ +То(х,и, ■ ■ ■ , ¿т),
■ +
(5)
где Е - оператор сдвига: Е(Р(х)) = Р(х + 1), и То,Т\, ■ ■ ■ ,Тр суть полиномы указанных переменных, ¿г,Ь2, ■ ■ ■ ,Ьт - параметры.
Условимся называть знаменателем рациональной функции Р(х) € 0(х) полином с(х) €
Ь(х)
€ К[х], 1е(с(х)) = 1, для которого Р(х) =
с(х)
с(х) = 1. Числитель и знаменатель любой рациональной функции определены единственным образом.
Лемма 1. Пусть Ь = хтЕ - (х + тх)(х+ +т2) ■■■ (х + тт), где тг,т2, ■ ■ ■ ,тт - некоторые числа. В этом случае:
(г) если уравнение Ь(у) = 0 имеет решение в виде ненулевой рациональной функции, то тг ,т2,■ ■ ■ ,тт - целые;
(гг) если тг,т2, ■ ■ ■ ,тт - целые, то уравнение Ь(у) = 0 имеет решение в виде рациональной функции
Е(х) = Ег(х)Е2(х) ■ ■ ■ Ет(х),
где
Ег(х) =
х(х + 1) ■■■ (х + тг - 1), 1
(х - 1)(х - 2) ■■■ (х - \тг
тг > 0, тг < 0,
(6)
г = 1,2,■■■,m;
(ггг) если среди целых тг,т2,■■■,тm есть хотя бы одно отрицательное, то знаменатель рациональной функции Е(х) из (гг) делится на х - 1, и, как следствие, Е(х) не является полиномом.
Доказательство. (1), (И) Пусть для некоторого г, 1 < г < т, число тг - целое. Тогда подстановка
у (х) = г(х)Ег(х)
в уравнение Ь(у) = 0, где г(х) - новая неизвестная функция, а рациональная функция Ег (х) определена посредством (6), приводит к новому уравнению, которое после упрощения приобретает вид Ь'(г) = 0, где
„т— 1
Е - (х + 71) ■ ■ ■ (х + т—1)(х + т»+1) ■ ■ ■ (х + тт)
при некотором полиноме Ь(х) € 0[х], взаимно простом с с(х). При этом полином Ь(х) называется числителем Р(х). Знаменателем нулевой рациональной функции будем считать полином
при т > 2. Если т = 1, то Ь' = Е - 1, и уравнение Ь'(г) = 0 имеет решение, тождественно равное единице. В итоге получаем (11).
Если среди исходных чисел тг,т2,■■■,тm имеются нецелые, то после нескольких подстановок указанного вида с целыми тг мы получаем уравнение Ь(и) = 0, где и - новая неизвестная функция,
Ь = х1Е - (х + аг)(х + ■■■ (х + а),
и среди чисел а1,а2,...,аг нет целых. Пусть уравнение Ь(и) = 0 имеет ненулевое полиномиальное решение р(х). Тогда
х1р(х + 1) = (х + И1)(х + и2)... (х + ог)р(х).
Очевидно, что х|р(х). Пусть Н - наибольшее целое такое, что (х + Н)|р(х). Для некоторого полинома д(х) имеем: р(х) = (х + Н)д(х) и
х1 (х + Н + 1)д(х + 1) =
= (х + И1)(х + И2)... (х + и)(х + Н)д(х).
Следов
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.