ПРОГРАММИРОВАНИЕ, 2010, No 2, с. 31-35
КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 512.628.2
ВЕРХНЯЯ ГРАНИЦА МИНИМИЗИРУЮЩИХ КОЭФФИЦИЕНТОВ РАЗМЕРНОСТНОГО МНОГОЧЛЕНА КОЛЧИНА*
© 2010 г. М. В. Кондратьева МГУ им. М.В. Ломоносова, механико-математический факультет 119992 Москва, Воробьевы Горы E-mail: kondratieva@sumail.ru Поступила в редакцию 30.08.2009 г.
В статье доказана верхняя оценка минимизирующих коэффициентов размерностного многочлена Колчина подмножества Е С М™, зависящая от максимального порядка входящих в Е элементов. Минимизирующие коэффициенты всегда положительны, а некоторые из них являются инвариантными и играют важную роль в дифференциальной алгебре. В качестве приложения полученного результата мы доказываем оценку для типовой дифференциальной размерности систем дифференциальных уравнений в частных производных, если ограничены порядки и степени исходных уравнений.
1. ВВЕДЕНИЕ
Одним из основных объектов изучения в дифференциальной алгебре является дифференциальный размерностный многочлен, введенный Э. Колчиным [1]. Это аналог размерности в алгебраической геометрии, и оценка коэффициентов размерностного многочлена относится к классическим нерешенным проблемам дифференциальной алгебры. Если известно характеристическое множество простого дифференциального идеала в кольце дифференциальных многочленов, проблема нахождения размерност-ного многочлена является несложной комбинаторной задачей, для решения которой найден ряд алгоритмов (см., например, [2]).
2. ПРЕДВАРИТЕЛЬНЫЕ ФАКТЫ
Обозначим через Ъ множество целых чисел, через N0 — неотрицательные целые числа. Пусть
т
е = (гх,..., гт) £ М^", тогда число гк будем на-
к=0
зывать порядком элемента е и обозначать через огё е. Обозначим также через ^ П ^ количество сочетаний из п элементов по к. Отметим, что любой целозначный (т.е. принимающий в целых точках целые значения) полином ь(в) мо-
8 + г \
жет быть записан в виде v(s) =
d
Е'
где а £ Ъ. Будем называть числа (аа,..., а0) стандартными коэффициентами многочлена у(з).
Определение 1 (см. [2], определение 2.4.9 или [3]). Пусть и = и(Ь) является целозначным многочленом степени ! от переменной Ь. Назовем последовательностью минимизирующих коэффициентов многочлена и вектор Ь(и) = = (Ьа,..., Ьо) € Ъа+1, определяемый индуктивно по ! следующим образом. Если ! = 0 (т.е. и является константой), то положим Ь(и) = = (и). Пусть !> 0 и (аа,...,а0) - стандартные коэффициенты многочлена и, т.е. и(Ь) =
Й Ь + г \
. Обозначим через у(Ь) = и(Ь+
= Е a
i=0
* Работа выполнена при частичной поддержке гранта РФФИ, проект 08-01-90103-Мола.
, ч t + 1 + d + ad t + d + 1 \ Т
+ad) " d + 1 + d + 1 . Так
как deg v < d, можно вычислить последовательность минимизирующих коэффициентов b(v) = = (bk, • • • ,b0)(0 < k < d) многочлена v(t). Теперь положим Ь(ш) = (ad, 0, • • • ,0,bk, • • • ,b0) £ Zd+1.
Отметим такой факт (см. [3] и [2], утверждение 2.4.10): все минимизирующие коэффициенты дифференциального размерностного многочлена неотрицательны. Верно и обратное: если последовательность минимизирующих коэффициентов некоторого целозначного полинома состоит из неотрицательных чисел, то он является размерностным полиномом некоторого дифференциального расширения.
Теперь дадим определение размерностного многочлена Колчина подмножества E С N™. Определим частичный порядок на N™ следующим образом: отношение («!,•••, im) < (j1, • • • , jm) равносильно ik < jk для всех k = 1, •••, m. Рассмотрим функцию ше(s), принимающую в точке s значение Card VE(s), где VE(s) - множество точек x £ Nm таких, что ord x < s и для каждого e £ E не выполняется условие e < x. Тогда (см, например, [1], стр. 115, или [2], теорема 5.4.1)) функция ше(s) для всех достаточно больших s является целозначным многочленом. Будем называть ее размерностным многочленом Колчина множества E и обозначать через ше(s).
3. ОСНОВНЫЕ РЕЗУЛЬТАТЫ
Некоторые из гипотез дифференциальной алгебры, высказанные одним из ее основателей Э. Колчиным, касаются оценок сверху коэффициентов размерностного многочлена минимальной простой компоненты системы дифференциальных уравнений, если наложены ограничения на порядки входящих в систему уравнений (см., например, [1]). Поставим такую задачу. Пусть известен максимальный порядок входящих в характеристическое множество минимальной простой компоненты уравнений, каким образом можно оценить коэффициенты дифференциального размерностного многочлена? Ответ на этот вопрос дает изложенная ниже теорема.
Введем еще некоторые обозначения. Обозначим через C(k,n) множество всех сочетаний из n элементов по k. Пусть E = {e1, • • •, en} С NJJ1, ei = (e1, • • , em) и пусть а £ C(k,n), а именно а = {ii, ••^ik} C{1,_,n}.
Обозначим через 1.с.ш(ег1,..., егк) (или просто через 1.с.ш.(ест)) вектор (к\,..., кт), имеющий координаты к^ = шах^а е\. Определим множество Т = Т(Е) как множество векторов, равных 1.с.ш(ег1,. ..,егк) для некоторого подмножества а = {г1,..., } С {1,..., п}. Пусть т - некоторый вектор из множества Т(Е). Определим число ¡т как сумму
n
¡лт = ¡лт (E) = J2
Е
k=0 аеС(k,n):l.c.m.(ea)=т
( —1)k (1)
Для всех остальных векторов т £ Мт \ Т(Е) положим ¡т = 0.
Один из комбинаторных методов для вычисления размерностного многочлена Колчина ше(в) заключается в нахождении чисел ¡¡т (см., например, [2], формула 2.3.1):
шЕ(s) = Е vTI
т ет V
s + m — ord т
m
(2)
где ¡т - целые числа, определяемые по формуле (1).
Для доказательства основного результата статьи нам понадобится следующая техническая
Лемма 1. Пусть Е С т £ Т(Е). Тогда ¡т(Е)| < 2т-1.
Доказательство. По лемме 2.3.5 и формуле (2.3.2) (см. [2]) ¡лт(Е) = ^(1;...;1)(Я), где Н - некоторая п х т матрица, элементы которой — 0 или 1. Индукцией по т докажем, что ¡(1;...д)(Н)\ <
< 2т-1. Для т = 1 Н - это число, равное либо 0, либо 1, и поэтому \л(1)(Н)\ < 1. Пусть т > 1, и верно предположение индукции. По лемме 2.3.9 [2] ¡(1,...,1)(Н) < \Л(1,...,1)(Н 1)\ + \Л(1,...,1)(Н2)\, где Н 1,Н2 - некоторые матрицы, состоящие из 0 и 1 и Н1, Н2 С мт-1. Поэтому ¡(1;...Д)(Н)\ < ^ 2т-2 + 2т-2 = 2т-1. ' ' □
Теорема 1. Пусть Е С огё ег < Н для всех ег £ Е, (Ьт, ...,Ь0) - минимизирующие коэффициенты многочлена Колчина ше(в). Тогда Ьт = ат < 1, Ьт-1 = йт-1 < Н и для
всех к > 2 выполняется неравенство Ьт-к <
к_2
< 222 Н(т+2)2к_2, где Н = 2(Н + 1). Доказательство. Если Е = 0, то ше (в) =
( в + т\ , ли п
= I т I, и поэтому Ьт = ат = 1, Ьг = 0 для
всех г = 0, ...,т — 1, и в этом случае утверждение справедливо. Пусть теперь Е = 0, Е =
ВЕРХНЯЯ ГРАНИЦА МИНИМИЗИРУЮЩИХ КОЭФФИЦИЕНТОВ
33
= (eij. Тогда bm = am = 0, и по определению 1 и следствию 2.2.20(3) (см. [2])
m
bm-1 = am-1 = ^ птт eij, откуда следует оцен-
+
+
s + m — 1 - bm-1
m — 1 I
s + m — 1 — bm-1 — bm-2 m-1
s + 2 — bm-1 — ••• — b2 \ 2
s + 2 — bm-1 — • •• — b1
+ ••• +
+ bo^
тет \ к
o
s + i — ( E bm+j) j=i-k
k k
i=2
\
/
-1
s + i — ( J2 bm+j)
j=i-k-1 i
/ J
+ bm k •
Подставив в последнюю формулу 8 = —1, получим рекуррентную формулу для вычисления минимизирующих коэффициентов:
bm-k — 'У ] Цт
т ет
k-1 —k1
i=2
(
к — 1 — ord т к
-1
i — 1 — YL bm+j
j=i-k
i
\
+
(
+
i=2
-1
i — 1 — ( Е bm+j j=i-k-1
1<i<ra j=1
ка bm-1 < h. По определению минимизирующих коэффициентов запишем:
) f s + ^ ( s + m — ^-Л +
mm
\
/
El к — 1 — ord т ,
^ , I +
тет
к
/
+
i=3
-1
i 2 ^ ] bm+j
j=i-k-1 i
-1
1 — Е bm+j
j=1-k 2
\
+
/
/
С другой стороны, мы имеем формулу (2). Заметим, что Card Т < (h + 1)m, так как Т - это множество таких элементов т Е Nm, что т = = Lc-m(ei!¡•••,eir), } Е C(т,п),е^ Е E.
По лемме 1 \цт\ < 2m.
По формуле (2.1.10) (см. [2]), применяя оператор А/(s) = / (s) — / (s — 1) m — к раз (2 < к < m), получим:
АГк(s) = £ J s + к — ord Л
Сначала докажем утверждение для к = = 2,3, затем будем действовать индукцией по к. Будет использовано очевидное неравенство
г — Е Ьз > ^
< (£ ь3 )г.
з
Имеем по полученной рекуррентной формуле: Ьт-2 < (Ь+1)т2тЬ2 + Ь2 < 2Ьт+2; Ьт-3 < Ьт+3 + +Ь3 + (Ь + 2Ьт+2)2 < 11Ь2(т+2) < 222 Ь2(т+2).
Пусть теперь к > 3. Имеем по предположению индукции и рекуррентной формуле: Ьт—к—1 <
к к—г
< Нт+к+1 + Нк+1 + ¿(Ь + ^ 22^ Ь(т+2)2')г.
i=2
j=o
ki
Обозначим через 8г = (Ь + ^ 222 Ь(т+2^23 )г,
з=о
М = 222 Ь(т+2)2 1. Сначала мы хотим показать, что для всех г = 2,...,к выполняется
si < M/2i.
(3)
В самом деле, 2isi < 2^(к — i + 2)22 х
xh(m+2)2k-^i ^ 2i(k — i + 2)i2i22"-ihi(m+2)2k-i ^
^ 2i(k-i+2+22k-i)h(m+2)2k-1. Здесь мы пользуемся неравенством
i < 2
i1
i e N
(4)
Теперь мы видим, что для доказательства неравенства (3) достаточно показать, что г(к — г+
сл2к_г\ г\2^_1 -п-
+2 + 22 ) < 22 . Для случая к = г это очевидно: 4к < 2к+1 < 22 (здесь используется тот факт, что х < 2х-2 для х > 4, а ведь у нас к + 1 > 4). Пусть теперь г < к. По формуле (4) имеем: к — г + 2 < 2к—г+1 < 22к_г, поэтому г(к—г+2+2?к_) < г21+2'_' < 2г+2"_ < 22'_1+2'_'.
k
k
Пусть г — 1 < к — г, тогда 2г-1 + 2к-г < 2к-г+1 <
< 2к-1 (так как г ^ 2). Пусть, напротив, к — г ^
< г — 1, тогда 2г-1 + 2к-г < 2г < 2к-1. Мы видим, что в обоих случаях 22 +2 < 22 , что и требовалось для доказательства (3).
Итак, мы получили неравенство вг < М/2г.
Теперь оценка для коэффициента Ьт-к-1 выгля-
к
дит так: Ьт-к-1 < Нт+к+1 + Нк+1 + ^ вг <
г=2
< Нт+к+1 + Нк+1 + М(1/2 + 1/4 + ... 1/2к) <
< Нт+к+1 + Нк+1 + М(1 — 1/2к). Одним словом, для доказательства искомой оценки Ьт-к-1 <
< М нам достаточно получить такое неравенство: Нт+к+1 + Нк+1 < М/2к. И это действительно так: 2к (Нт+к+1 + Нк+1) < 2к+1Нт+к+1 <
< 22к Нт+2к < 222к—1 Нт2к—1+2к = М (используем неравенство (4)). □
4. ОЦЕНКА ТИПОВОЙ ДИФФЕРЕНЦИАЛЬНОЙ РАЗМЕРНОСТИ
Чтобы применить найденную выше оценку в дифференциальной алгебре, нужно найти связь между порядками дифференциальных уравнений, входящих в заданную систему, и порядками уравнений, входящих в характеристическое множество минимальной простой компоненты. Для нахождения характеристического множества существуют алгоритмы (различные варианты алгоритма Розенфельда-Гребнера), однако в общем случае (без каких-либо дополнительных
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.