ПРОГРАММИРОВАНИЕ, 2015, No 2, с. 18-25
КОМПЬЮТЕРНАЯ АЛГЕБРА
У V 004.421.6+512.628.2
АЛГОРИТМ ПРОВЕРКИ ТРИВИАЛЬНОСТИ "СМЕШАННЫХ" ИДЕАЛОВ В КОЛЬЦЕ ДИФФЕРЕНЦИАЛЬНЫХ
МНОГОЧЛЕНОВ
© 2015 г. А.И. Зобнин, М.А. Лимонов
Московский государственный университет им. М.В. Ломоносова 119991 Москва, ГСП-1, Ленинские горы, д. 1 E-mail: Alexey.Zobnin@gmail.com, matemaks@yandex.ru Поступила в редакцию 15.09.2014
В статье предлагается алгоритм проверки тривиальности идеала [f] + (h1,..., ht) в обыкновенном кольце дифференциальных многочленов при некотором дополнительном условии на многочлен f. Эта задача тесно связана, с одной стороны, с задачей Колчина об экспонентах дифференциальных идеалов, а с другой — с вопросами конечности дифференциальных стандартных базисов.
1. ВВЕДЕНИЕ
В одной из своих ранних работ [1] Эллис Кол-чин изучал возможные значения экспонент дифференциальных идеалов особого вида. Экспо-нентой идеала I называется минимальное натуральное число ш, такое, что у/1 С I (если такого числа не существует, то экспонента считается равной бесконечности). Колчин рассматривал идеалы, порождённые дифференциальным многочленом первого порядка. В его работе было разобрано несколько достаточно общих случаев (но не все), и в этих случаях было установлено, что экспонента может равняться 1, 2 или те. В частности им рассматривались дифференциальные многочлены, не имеющие сингулярных корней, то есть такие, что
[f,Sf ] = (1), (1)
где Sf — сепаранта f (частная производная многочлена f по старшей переменной). Колчин установил, что если, вдобавок, многочлен f удовлетворяет условию
[Д ] + (Sf) = (1), (2)
то экспонента идеала [Д] равна 1, то есть, идеал [д является радикальным (этот результат справедлив для многочленов Д любого порядка). В то же время случай
[f,Sf ] = (1), [f] + (Sf ) = (1) (3)
Колчин оставил неразобранным. Он даже не предложил никакого практического способа проверки того, выполняется ли условие (2) при
предположении (1).
С другой стороны, в 2007 году Дмитрий Трушин, изучая так называемый идеал сепарант, доказал [2], что при предположении (1) условие (2) равносильно наличию в идеале квазилинейного многочлена (т. е. дифференциального многочлена, разрешённого относительно старшей производной). В свою очередь, это равносильно существованию у идеала [f] конечного дифференциального стандартного базиса (аналога базиса Грёбнера) при порядках, близких в некотором
смысле к лексикографическому [3].
Как мы видим, в этих задачах возникает одно
f
ложение (1) можно проверить алгоритмически с помощью алгоритма Розенфельда-Грёбнера [4, 5], то готового алгоритма для проверки тривиальности "смешанной" суммы дифференциального и недифференциального идеалов, т. е. проверки условия (2), не было известно. Более того, высказывались мнения1, что такая задача алгоритмически неразрешима.
1 Частная беседа одного из авторов с участниками конференции Grobner Bases in Symbolic Analysis, Линц, Австрия, 2006.
В данной работе мы предъявим алгоритм, проверяющий условие (2) (а на самом деле, решающий более общую задачу): при более слабом предположении
' дуо '...' дуг _
= (1),
(4)
где I — порядок дифференциального многочлена /, проверить, верно ли равенство
[/] + (Н1'...'Ы) = (1)'
(5)
где Н\'...' Н — произвольные заданные многочлены. Идеалы вида [/] + (Н1'...' Нг) мы будем называть «смешанными»: вообще говоря, они не являются дифференциальными. Мы надеемся, что предложенный алгоритм поможет в исследовании так называемой проблемы Ритта [5, 6], которая до сих пор является открытой.
Статья организована следующим образом. В главе 2 мы приводим необходимые определения из дифференциальной алгебры. В главе 3 строится разложение производной дифференциального многочлена по старшим переменным с помощью так называемых обобщенных сепарант. В их терминах в главе 4 формулируется алгоритм, решающий поставленную задачу. В главе 5 приводится несколько примеров, иллюстрирующих работу алгоритма.
2. ОПРЕДЕЛЕНИЯ И ОБОЗНАЧЕНИЯ
Мы будем работать над полем констант Т нулевой характеристики.
Кольцо К называется алгеброй Ритта, если оно является алгеброй над 0>.
Отображение 5 : К ^ К называется дифференцированием, если для любых элементов а и Ь кольца К выполнены следующие свойства:
1. 5(а + Ь) = 5(а) + 5(Ь) — линейность;
2. 5(аЬ) = а5(Ь) + Ь5(а) — правило Лейбница.
Кольцо К называется обыкновенным дифференциальным кольцом, если на нем задано одно дифференцирование.
Пусть Т — обыкновенное дифференциальное поле. Кольцом, дифференциальных ммогочленов от одной неизвестной над Т называется кольцо многочленов от счетного числа переменных
Т[уо'...' уП'...] (обозначается Т{у}) с дифференцированием 5, таким, что 5(уг) = уг+1 и 5, ограниченное на Т, совпадает с дифференцированием поля Т. Дифференцирование 5, заданное таким способом, однозначно продолжается на Т{у} по линейности и правилу Лейбница.
В дальнейшем для удобства мы будем обозначать п-ю производную многочлена / как 5п/.
п
Пусть М = Л угде аг ^ 0, причем ап > 0.
г=0
Тогда п называется порядком монома М (обозначение: огё М = п). Соответственно, порядком многочлена называется максимальный порядок мономов, его составляющих.
Будем говорить, что переменная у г старше переменной у^ (обозначение: уг >- у^), если г > у.
Дифференциальным идеалом, дифференциального кольца К называется идеал I, такой, что 5(1) с I.
Будем обозначать через (Е) и [Е] соответственно алгебраический и дифференциальный идеалы, порождённые элементами из Е.
Для элемента / кольца Т{у} определим сепаранту Sf как частную производную по старшей переменной. Для элементов поля Т полагаем ее нулем.
Многочлен называется квазилинейным,, если его сепаранта — ненулевой элемент поля Т.
3. ОБОБЩЕННЫЕ СЕПАРАНТЫ
п
значения порядка дифференцирования и I для порядка многочлена.
Известно, что производные дифференциального многочлена "линейны" по своей старшей переменной. Более того, коэффициент перед этой переменной для любого порядка дифференцирования один и тот же — это сепаранта:
5п/ = Sf уг+п + Я и
(6)
где огё Qf,n < I+п. Мы обобщим это наблюдение на переменные, «предшествующие» старшей.
Лемма 1. Пусть моном М записан в виде М = Уп ... Утл ■ Тогда
5пМ = ^
П!
а
ПУг
81! ...ва!1 1
0, г=1
81+...+^ =п
Доказательство. Следует непосредственно из правила Лейбница. □
Лемма 2. Пусть Д — дифференциальный многочлен. Тогда для любого в € N
д§Д = § (Д ^ + и
дуз \дуз) дуэ-1,
где ду- — обычная частная производная.
Доказательство. Пусть I = огё Д. Воспользуем-" I дт
ся формулой §Д = ^ дут:Уг+1) которая следует
i=0
из правила Лейбница. Имеем döf \i=o
d Е шVi+1
dys
dys
+E
i=o
i gäL
i=o
dys
dyi+i df dys dyi
Во второй сумме только слагаемое
Ш dys— = ays-l не Равно 0' т- е-
döf dys
E
i=o
i д-L-
E ^ yi+i +
i=o
dyi
df
dys
df dys-i
yi+i +
= ö
df dys-i
df dys
+
df dys-i'
Лемма 3. Пусть Д — дифференциальный многочлен. Тогда для, любых п, в € N верно
dönf dys
n /
ЕСП öi(
df
i=o
dyi+s-n
Воспользуемся линейностью дифференцирования и леммой 2 в каждом слагаемом в последней сумме:
gi( döf \ = ¿Л df + / df
\dyi+s-k) \dyi+s-k-i \dyi+s-k
= öi
df
dyi+s-k-
0 + Ö (dyi+s-^j '
Следовательно,
dök+if _ dys
kk у dö^—^i— + у aöi+i df
^ k dy(i+s-k)-i ^ k
i=o k
i=o k+i
dyi+s-k
Л -P k+i о j>
Edöi+ Eak-iöi df
i=0 dy(i+s-k)-i ti k+i
k dyi+s-k—i
E^i xi ck+iö
df
□
= Jдyi+s-(k+1) .
□
Рассмотрим дифференциальный многочлен д порядка I и произвольное целое число к ^ 0. Представим многочлен в виде д = до+Ад,к у к, где
до не зависит от у к, а многоч лен Ад,к у к получает-д
ук
за скобки.
Лемма 4. Пусть Д — дифференциальный многочлен и огё Д = I. Тогда для любых кипе условием п € N 0 ^ к € Ъ, п > 2к верно следующее равенство:
Доказательство. Докажем это утверждение индукцией по п. База (и = 1) верна по лемме 2. Предположим, что для и = k утверждение вер-
и=
ßfik+lf Qxkg
k + 1. Пусть öf = g. Тогдa dy f = -¡y1- Применим предположение индукции к многочлену ökg. Имеем
dök+if _ dys
v" Ci dgg ^ v" ai döf = ¿0 Ckö l sy+7k) = ¿0 Ckö l dy+Tk
A
&n f ,n+i—k
= V ck-i+j ök-i+U
n
j=0
dy3
Здесь мы по умолчанию понимаем С^к = 0 для к
Доказательство. Заметим, что в силу линейности дифференцирования мы можем считать Д мономом. Пусть deg Д = д и Д' представляется в виде
f = П ym = П уп ,
i=0
i=i
где г г ^ г,- при г ^ 3. Тогда применив лемму 1 к 5п/, получим
5п / = Е
п!
П Уп
в1!... ва!
1 а г=1
«1+...+^=п
+«4
дуп+г-к
дуп+г-к = Л ¿п-,п+г-к.
Е °п 5г
Л6г д/
f,n+г-k к
г=0
дуг+г-к п
Есп 5г
д/
Е сп-г+^'5к
,=г-к
-г+, / дУ,
Есп-г+^' 5к ,=о
дуг+г-к
-г+, /
дУз
(по лемме 4). Коэффициенты Sf,n,k будем называть обобщёнными сепара,нт,ам,и многочлена /. В частности, при к = 0 обобщённая сепаранта совпадает с обычной: Sf.no = Sf = — . Заметим, что при указанных предположениях огё Sfín,k ^ к + I.
Так как п > 2к, то в каждом мономе вида Па=1 перемениая уп+г-к встречается лишь
один раз. Действительно, пусть уп+в4 = Уп+г-к и Утз = Уп+г-к■ Но тогда
гг + вг + г, + в, = 2(п + I — к).
Следовательно,
а
2(п + I — к) ^ 2га + Е ва = 21 + п.
г=1
Значит, п ^ 2к, что противоречит выбору п > 2к. Мы получили, что многочлен 5п/ линеен по всем переменным уп+г-к'п > 2к. Пусть 5п/ = /0 + Л$п-,п+г-кУп+г-к- Тогда, в силу линейности 5п/ по Уп+г-к,
д5п/ д(/о + Л¿пАп+г-кУп+г-к) _
Предложение 1. При п > 2р
5п/ = Sf,n,о Уг+п + Sf,n,l Уг+п-1 + ... + +Sf,n,p уг+п-р + Tf,n,p'
где огё Т-,п,р <1 + п — р.
(Г)
С другой стороны, по лемме 3
д ¿п — п ' ( д — \
75-— = У" С 5г [ 75—-— . Заметим, что так
ОУп + Ь-к п п \ дУ4+1-к ) '
г=о
как огё / = I, то для всех г > к выполнено дУр—— = 0. Отсюда следует, что
ду4+1 — к
Последнее равенство верно, так как если I > к, то из 0 ^ 3 <1 — к =^ сП-1+:' = 0 а если I < к,
то к — I < з < 0=^ — = 0 □
/
огё / = I, п Е N 0 ^ к Е Ъ и п > 2к. Введём более удобное обозначение
,п,к := Л¿п-,г+п-к = Е Сп г+У 5к г+Ч
Доказательство. Докажем утверждение индукцией по р. База выполнена: при р = 0 утверждение превращается в формулу (6). Предположим, р
докажем его для р +1, где 2(р +1) < п. За
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.