ПРОГРАММИРОВАНИЕ, 2013, No 2, с. 11-14
КОМПЬЮТЕРНАЯ АЛГЕБРА
У л :
О РАЦИОНАЛЬНЫХ РЕШЕНИЯХ ЛИНЕЙНЫХ УРАВНЕНИЙ С ЧАСТНЫМИ ПРОИЗВОДНЫМИ ИЛИ РАЗНОСТЯМИ *
© 2013 г. C.B. Парамонов
Факультет вычислительной математики и кибернетики МГУ им. М.В. Ломоносова 119991 ГСП-1, Ленинские горы, МГУ, д. 1, стр. 52 E-mail: s. v.paramonov@yandex. ru Поступила в редакцию 02.07.2012
Доказывается алгоритмическая неразрешимость задачи распознавания существования решений в виде рациональных функций для имеющих полиномиальные коэффициенты линейных однородных уравнений с частными производными или разностями.
1. ВВЕДЕНИЕ
Будем рассматривать линейные однородные уравнения с частными производными, имеющие вид
£ аДх)^у(х) = 0 (1)
«es
где
• х = (х1,..., хт) — вектор независимых переменных,
• в = (в1,..., вт) — мультипоказатель,
• у(х) = у(х1,..., хт) — неизвестная функция от т переменных,
• £ — конечное подмножество множества ,
• а3(х) — полиномы над некоторым фиксированным полем характеристики 0,
• О8 = О^1 ... От, при этом = дХ: — частная производная по хг.
По аналогии будем рассматривать линейные однородные уравнения с частными разностями, имеющие вид
^ as(x)Asy(x) = 0, ses
(2)
As = A11... Amm,
ность по x,:
при этом A, — частная раз-
Агу(х) = у(х1, . . . ,хг + 1, . . . , хт) - у(х 1, . . . ,хт).
В [6], [7] начато изучение алгоритмических аспектов поиска универсального знаменателя рациональных решений уравнения (2). В то же время в [4] доказана алгоритмическая неразрешимость задачи распознавания существования ненулевых полиномиальных решений уравнений (1) и (2). В настоящей статье доказывается алгоритмическая неразрешимость задачи распознавания существования ненулевых рациональных (т.е. имеющих вид отношений двух полиномов) решений уравнений (1) и (2). При этом неразрешимость доказывается уже для уравнений вида
J2a.sôsy(x) = 0,
(3)
ses
где as G Z и
S, =
x,D-, в дифференциальном случае, x,A,, в разностном случае.
*Частичная поддержка РФФИ, грант 13-01-00182-а.
(4)
Как известно, существуют алгоритмы поиска всех рациональных решений линейных дифференциальных и разностных уравнений с полиномиальными коэффициентами в случае одной пе-т=1
Эти алгоритмы доступны в системе компьютер-
12
ПАРАМОНОВ
ной алгебры Maple ([10]). Доказанная в настоящей статье теорема говорит о том, что нет смысла рассчитывать на появление в системах компьютерной алгебры таких алгоритмов для произвольных m > 1.
2. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ
Для целого неотрицательного b возрастающая степень ub определяется как u(u+1)... (u+b—1). Полагая n = (ni,..., nm) e Zm и
X
X i
• Xm
нетрудно заметить, что
ÔiXn = п^п,
= nixn,
,
в разностном случае.
выводится следствие о невозможности алгоритма, отвечающего на вопрос о существовании решений в неотрицательных целых числах. Если в дифференциальном случае записывать полиномы по степеням xn, а в разностном — по степеням xn, то, как показано в [4], каждый одночлен полиномиального решения уравнения (3) также является решением этого
уравнения. Но равенство ^ as£sx^n = 0 имеет
ses
место, если и только если ^ asns = 0. Из
ses
упомянутого следствия теоремы ДМПР вытекает неразрешимость вопроса о существовании полиномиальных решений.
Понятие возрастающей степени может быть обобщено на произвольные целые показатели
(И):
Далее будем использовать обозначение
X
(n) =
X
X
,
,
n G Zmo- Справедливо равенство
5iX(n) = niX(n).
(5)
FI Л.
F I X1, . . . , M , . . . , M
V OXl dXm
y(Xl, . . . ,Xm) = 1,
u
'u(u + 1)... (u + b - 1), 1,
_1_
(u-1)(«-2)...(u-|b|) ,
если b > 0, если b = 0, (6) если b < 0.
Дифференциальный вариант оператора 5 используется в [5] для доказательства следующего факта: не существует алгоритма, который для дифференциального уравнения вида
Где р — полином, определяет наличие у этого уавнения решений в виде формальных степенных рядов.
В [5], [9] для доказательства алгоритмической неразрешимости проблем, связанных с дифференциальными уравнениями, используется теорема Девиса-Матиясевича-Патнема-Робинсон (следуя [8], используем далее аббревиатуру ДМПР как название этой теоремы) о том, что невозможен алгоритм, который бы для произвольного полинома Р(ж1, Х2,..., хт) с целыми коэффициентами отвечал на вопрос, имеет ли уравнение Р(ж1, х2,..., хт) = 0 решение в целых числах (см. [2]). Из теоремы ДМПР легко
Мы будем использовать обозначение в случае произвольных показателей n G Zm. Равенство (5) сохраняет силу.
Ниже доказывается, что уравнение (3) обладает ненулевым рациональным решением тогда и только тогда, когда это уравнение обладает мо-номиальным решением, т.е. решением вида x^. Из соотношений (5) на основе этого выводится, что является решением уравнения (3) тогда и только тогда, когда выполняется равенство asns = 0
ses
теорему ДМПР.
3. НЕРАЗРЕШИМОСТЬ ЗАДАЧИ РАСПОЗНАВАНИЯ СУЩЕСТВОВАНИЯ РАЦИОНАЛЬНЫХ РЕШЕНИЙ
Введем обозначение
o(Xn) = Xs
s^n, sezm
n G Zm,
где в — п означает, что в лексикографически меньше п; предполагается, что коэффициенты е3 являются постоянными и что сумма в правой части конечна.
n
n
X
X
X
1
О РАЦИОНАЛЬНЫХ РЕШЕНИЯХ ЛИНЕЙНЫХ УРАВНЕНИЙ
13
Лемма 1. Если v, ^ е Z^O, 1 < i < m, то xv + o(xv) (vi - №)xv+ o(xv+^)
A,:
x^ + o(x^)
x2^ + o(x2^)
(7)
Доказательство. Пусть р(х) = х^ + о(х^) — числитель, д(х) = х^ + о(х^) — знаменатель, е = (0,0,..., 0,1,0,..., 0). Рассмотрим раздель-
г— 1 т—г
но два случая.
Дифференциальный случай:
п рж) = Рг(х)д(х) - р(х)д?(х) _ хгОг / \ — хг
q(x)
ViX
v—e+jU _
= X
q2 (x)
e+v + o(xv—e+^)
(x^ + o(x^))2
_ (Vi - №)xv+ o(xv+^)
= x2^ + o(x2^) ' Разностный случай:
p(x) p(x + e)q(x) — p(x)q(x + e)
xi^i T Г — xi
q(x)
q(x + e)q(x)
Разложим p(x) и q(x) в сумму одночленов по возрастающим степеням
P(x) = S
sev
a«x ,
q(x) — ^ btx4, tew
Лемма 2. Если в, V, ^ е Zmo, то
г, х^ + о(х^) (V - ^х^ + о(х^) ^-7-Т = -^-7---, (8)
х^ + о(х^) + )
где = (251+52- 1)^.
Доказательство. Равенство (8) эквивалентно равенству
Aifc Aifc-1 ' ' ' Ai1
p(x) q(x)
П К — fe)xv+(2fc —1^ + o(xV+(2k —
j=1
'
x2k ^ + o(x2k
Будем доказывать (9) индукцией по k. Случай k — 1 рассмотрен в лемме 1. Далее достаточно доказать
AAA ^М =
°ifc+1 Aik '''Ai1 q(x) =
Wk — ^ )xv+(2fc+1—+ o(xv+(2fc+1— = j=1_
= x2fc+V + o(x2fc+V) ,
предполагая, что выполнено (9). Для этого воспользуемся равенством (7):
где — конечные подмножества множества
Zm0. Имеем
xj (p(x + e)q(x) — p(x)q(x + e)) =
( _ xs+e x_^ ,_^ _ x_^ xt+e \
as — 126i xt — 12 asxS 12 6t —
s£V j teW s£V i£W j J
= ^ ^ as6t(x^xF — xV^) = sev tew
^ y^ asbt((x + Si + 1) —
sev tew — (x + ti + 1))xV =
^ y^ as6t(sj — tj)xsxt = sev tew
= (Vj — + o(xv+^)'
Таким образом,
p(x) (vi — ^ )xv+^ + o(xv+^)
Aik+i Aik ''' Aii^j) = ПК — ^jj) x
(x
q(x)
r,fc
j=i
xAi
v+(2k-1)M + o(xv+(2k-1}M)
jfc+i
x2fcM + o(x2k I
+ (2fc+1-1)M + o(xv+(2fc+1-1)M)
x2fc+v + o(x2fc+1M)
fc+1
Пк— ^jj)
j=1 k+1
П (Vjj — Mjj )xv+(2fc+1-1}^ + o(xv+(2fc+1-1}^) j=1
x2k+1M + 0(x2fc+1M)
□
xi Д i
Лемма 3. Если рациональная функция х11
является решением уравнения (3), то также является его решением.
Доказательство. Воспользуемся (8) и перепишем (3) в виде
q(x)
x2^ + o(x2^)
□
ses
(v — ^)sxv+rs + o(xv+rs)
1 xM+rs + o(x^+rs)
0'
(10)
x
14
ПАРАМОНОВ
Приведем все слагаемые (10) к общему знаменателю, пусть этот знаменатель будет u(x) = x^+r + o(x^+r). Тогда получим равенство
Е as((v - ^)sxv+r + o(xv+r))
ses_= o,
x^+r + o(x^+r ) из которого получаем
J2as(v - ^)s = 0.
ses
Из последнего равенства следует, что X(v-^) является решением исходного уравнения. □
Теорема 1. Не существует алгоритма, определяющего, имеет ли данное линейное уравнение с частными производным,и или разностями и полиномиальными коэффициентами ненулевое рациональное решение.
Доказательство. Если f (x) = а^м+ф-м) являет~ ся решением уравнения вида (3), то
b = Xv + o(xv ) af (X) = X^ + o(x^)
также является его решением, и по лемме 3 существование решения в виде рациональной функции уравнения равносильно существованию его решения в виде x(v-^). Из соотношений (5) следует, что x(n) является решением уравнения (3) тогда и только тогда, когда выполняется равен-asns = 0
ses
лучаем, что не существует алгоритма, определяющего, имеет ли данное линейное уравнение с частными производными или разностями и полиномиальными коэффициентами ненулевые ра-
□
Не следует упускать из виду, что известные доказательства теоремы ДА И IP предполагают выполненным неравенство m ^ 9 (см., например, [8]), и вопрос о существовании алгоритмов для 2 ^ m ^ 8 остается открытым.
Автор выражает благодарность своему науч-
ному руководителю С.А. Абрамову за постановку задачи, внимание к работе и помощь в написании статьи.
СПИСОК ЛИТЕРАТУРЫ
1. Абрамов С.А. Элементы компьютерной алгебры линейных обыкновенных дифференциальных, разностных и q-разностных операторов. М: МЦ-НМО, 2012.
2. Матиясевич Ю.В. Десятая проблема Гильберта. М: Наука, физматлит, 1993.
3. Abramov S., Petkovsek М. On the Structure of Multivariate Hypergeometric Terms // Advances in Applied Mathematics. 2002. V. 29. P. 386-411.
4. Abramov S., Petkovsek M. On polynomial solutions of linear partial differential and (q-)difference equations // Computer Algebra in Scientific Computing, 14th International Workshop, CASC 2012, Maribor, Slovenia, September 2012, Proceedings, LNCS 7442, 2012. P. 1-11.
5. Denef J., Lipshitz L. Power series solutions of algebraic differential equations // Math. Ann., 267, 1984. P. 213-238.
6. Kauers M., Schneider C. Partial denominator bounds for partial linear difference equations // Proceedings ISSAC'2010, 2010. P. 211-218.
7. Kauers M., Schneider C. A refined denominator bounding algorithm for multivariate linear difference equations // Proceedings ISSAC'2011, 2011. P. 201-208.
8. Pheidas Т., Zahidi K. Undecidability of existential theories of rings and fields: a survey // Hilbert's tenth problem: relations with arithmetic and algebraic geometry, Contemp. Math. 270, 2000. P. 49-105.
9. Sadovnikov A. Undecidable problems about polynomials: Around Hilbert's 10t
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.