научная статья по теме АЛГОРИТМ ПРОВЕРКИ ТРИВИАЛЬНОСТИ «СМЕШАННЫХ» ИДЕАЛОВ В КОЛЬЦЕ ДИФФЕРЕНЦИАЛЬНЫХ МНОГОЧЛЕНОВ Математика

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

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

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

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