научная статья по теме О РАЦИОНАЛЬНЫХ РЕШЕНИЯХ ЛИНЕЙНЫХ УРАВНЕНИЙ С ЧАСТНЫМИ ПРОИЗВОДНЫМИ ИЛИ РАЗНОСТЯМИ Математика

Текст научной статьи на тему «О РАЦИОНАЛЬНЫХ РЕШЕНИЯХ ЛИНЕЙНЫХ УРАВНЕНИЙ С ЧАСТНЫМИ ПРОИЗВОДНЫМИ ИЛИ РАЗНОСТЯМИ»

ПРОГРАММИРОВАНИЕ, 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 рублей.

Показать целиком

Пoхожие научные работыпо теме «Математика»