ПРОГРАММИРОВАНИЕ, 2009, № 2, с. 53-62
КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 681.3.06
О ДИСТРИБУТИВНЫХ РЕШЕТКАХ ПРАВЫХ ДЕЛИТЕЛЕЙ ЛИНЕЙНЫХ ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ ОПЕРАТОРОВ
© 2009 г. А. В. Пургин
Математический факультет Красноярский государственный педагогический университет 660049 Красноярск, ул. Перенсона, 7 E-mail: pavl972@yandex.ru Поступила в редакцию 01.09.2008 г.
В работе рассмотрены некоторые комбинаторные вопросы теории факторизации линейных обыкновенных дифференциальных операторов и конструктивно доказана теорема о том, что любая конечная дистрибутивная решетка является решеткой правых делителей некоторого даламберова линейного обыкновенного дифференциального оператора с коэффициентами из дифференциального поля С'(х) рациональных функций.
1. ВВЕДЕНИЕ
Алгоритмические вопросы теории линейных обыкновенных дифференциальных уравнений в последнее время получили значительное развитие. Для решения конкретных уравнений часто полезно знать, как устроено множество правых делителей данного линейного обыкновенного дифференциального оператора (ЛОДО). При решении задач, связанных с факторизацией (т. е. с разложением на неприводимые множители) линейных операторов, часто эффективны не только методы анализа, но и комбинаторные методы. Множество работ, например, [1-9], посвящено алгоритмам факторизации линейных дифференциальных операторов. Известно [7], что произвольный линейный обыкновенный дифференциальный оператор разлагается на неприводимые множители с конечным числом параметров. Относительно недавно (1996 г.) был получен алгоритм [7], который перечисляет все возможные факторизации заданного ЛОДО с рациональными коэффициентами. В работе [10] были охарактеризованы в терминах теории решеток ЛОДО, в факторизациях которых отсутствуют параметры, а именно получен следующий результат.
Предложение 1 [10]. Решетка правых делителей ЛОДО Р дистрибутивна тогда и только тогда, когда все факторы оператора Р непара-метризованы.
(Определение дистрибутивной решетки см. ниже.) Но до сих пор общая структура всех фак-торизаций операторов неизвестна.
Основным результатом данной работы является теорема 1, утверждающая, что любая конечная дистрибутивная решетка является решеткой правых делителей некоторого даламберова линейного обыкновенного дифференциального оператора с коэффициентами из дифференциального поля С(х) рациональных функций.
В данной работе для исследования этой структуры используются методы теории частично упорядоченных множеств (ч. у. множеств). Адекватным представлением структуры данных, выдаваемых упомянутым выше алгоритмом нахождения всех факторизаций данного оператора, является решетка - ч. у. множество, в котором для любых двух элементов существует их точная верхняя и точная нижняя грань.
В настоящей работе рассмотрим некоторые комбинаторные (перечислительные) вопро-
сы теории факторизации ЛОДО и конструктивно докажем теорему 1, упомянутую выше.
Символом Р будем обозначать линейный обыкновенный дифференциальный оператор
Р = Вп + /1(х)Вп~1 + ... + /п(ж), В = й/йх,
где /5(ж) принадлежат некоторому дифференциальному полю К. В дальнейшем мы без ограничения общности можем рассматривать только нормализованные операторы (т. е. операторы, у которых старшие коэффициенты равны 1) и их нормализованные делители. Далее оператором будем называть линейный обыкновенный дифференциальный оператор.
Введем отношение частичного порядка на множестве всех правых делителей произвольного ЛОДО Р следующим образом: пусть Р\ и Р2 - некоторые правые делители оператора Р, будем говорить, что Р\ ^ если оператор Р\ является правым делителем оператора Р2. Таким образом заданное частично упорядоченное множество правых делителей произвольного ЛОДО Р является решеткой с операциями взятия точной нижней грани \^{Р1,Р2} = гССО(_Р1, Р2) и точной верхней грани зир{Р1,Р2} = гЬСМ(Р1, Р2), гДе гССО(Р1, Р2) обозначает оператор, являющийся правым наибольшим общим делителем ненулевых операторов Р\ и Р2, а гЬСМ(Р1, Р2) ~~ оператор, являющийся их правым наименьшим общим кратным [9].
Через п будем обозначать га-элементную цепь, т. е. линейно-упорядоченное множество из га элементов.
Через п1 будем обозначать га-элементную антицепь, т. е. ч. у. множество, в котором любые 2 элемента несравнимы.
Определение 1. Длиной конечной цепи будем называть число, на единицу меньшее количества ее элементов.
Теоретико-решеточные операции будем обозначать следующим образом: зир{ж, у} = х У у = = х + у, ш1{ж, у} = х А у = ху. Операцию взятия точной верхней грани множества элементов будем также называть объединением этого множества элементов или их суммой, а операцию взятия точной нижней грани - соответственно пересечением множества элементов, или их произведением. Будем обозначать наибольший эле-
мент решетки Ь символом а наименьший -символом 0/,. Решетку правых делителей оператора Р будем обозначать Ьр.
Определение 2. Решетка Ь называется дистрибутивной, если для любых х,у,г £ Ь выполняется тождество ж (у + г) = ху + хг.
Определение 3. Будем говорить, что элемент х покрывается элементом у (или у покрывает х) и писать х -<; у, если х < у, и для любого г такого, что х ^ г ^ у, либо г = ж, либо г = у. В этом случае элемент х будем называть нижним покрытием элемента у, а элемент у -верхним покрытием элемента х.
Определение 4. Элемент решетки Ь, покрывающий элемент Ор, называется атомом, а элемент, покрываемый элементом 1р, называется коатомом.
Определение 5. Интервалом I = [х,у] называется множество всех таких г £ Ь, что х ^
£ 5$ У-
Определение 6. Прямое произведение Ах В решеток А ж В определяется как декартово произведение множеств-носителей решеток и является решеткой, в которой операции определяются покомпонентно (см., например, [11]).
Решетки и ч. у. множества изображаются в виде диаграмм Хассе, т. е. элементы решетки или ч. у. множества обозначены кружками, и, если х -< у, то элементы ж и у соединены отрезком и элемент ж находится ниже элемента у.
Пусть Р = Р1 о Р2 о ... Рг о Р1+1 о Р1+2 о ... о Р^ некоторая факторизация линейного обыкновенного дифференциального оператора Р на неприводимые множители Р{. Множители мы будем также называть факторами. Далее на протяжении всей работы будем рассматривать только такие факторизации. Для любого I 6 {1,..., к} обозначим символом (Рг) следующий оператор:
(Рг) = Рг О Рг +1 О Рг + 2 О ... О Рк
- именно он и является элементом решетки правых делителей оператора.
(-РгЧ-1) будет некоторым нижним покрытием правого делителя (Д).
Определение 7. Оператор Р называется да-ламберовым, если все его неприводимые множители Р{ являются операторами первого порядка: Рг = В + аг (ж), аг е С(х).
Определение 8 [7]. Будем говорить, что оператор Р (справа) преобразуется в оператор Р\ оператором В и писать Р Р\, если
гОС'В(Р, В) = 1 и К = гЬСМ(Р1 В) = Рг о В = = В\ о Р. В этом случае операторы Р и Р\ будем называть сходными.
Определение 9 [7]. Два (для простоты неразложимых) оператора Р и <3 будем называть перестановочными в произведении Р о если
Род = д1оР1,д1фР,
Отсюда легко видеть, что в этом случае Р сходен с Р\, сходен с ж Р\ Р.
Поясним связь между факторизациями ЛОДО и решетками их правых делителей на следующих простых примерах.
Прямое (декартово) произведение п экземпляров 2-элементной цепи 2 будем обозначать 2п. Из результатов работы [7] следует, что решетка 2п является решеткой правых делителей ЛОДО, когда все факторы перестановочны и несходны.
На следующих рисунках изображены используемые в работе решетки правых делителей ЛОДО второго порядка в виде диаграмм Хассе. На рис. 1 изображена диаграмма Хассе решетки правых делителей даламберова ЛОДО второго порядка Р = Р\ о Р2, когда его факторы Р\ и неперестановочны, а на рис. 2 - когда факторы перестановочны, но несходны, т. е. в фак-торизациях отсутствуют параметры, и поэтому по предложению 1 эта решетка дистрибутивна и является решеткой 22.
Каждому отрезку на диаграмме Хассе, соединяющему элементы (Рг) и (Рг+1), поставим в соответствие фактор Р{. Каждой вершине - соответственно правый делитель (Рг) оператора Р.
Минимальный элемент 1 этих решеток - это фактор нулевого порядка, т. е. константа из дифференциального поля К = С(х).
Определение 10 [12]. Порядковый идеал частично упорядоченного множества М есть такое подмножество I ч. у. множества М, что, если жб/иу^ж, то у £ I.
Определение 11. Под высотой элемента х решетки Ь будем понимать длину максимальной цепи в интервале [0/,, х] и обозначать высоту х через ]г(х). Высотой решетки Ь будем называть высоту элемента 1
Р10Р2 = (Р,) = Р
Рх
^ Р2 = (Р2)
Р2 • 1
Рис. 1. Решетка 3.
Нетрудно показать, что решетка .1{М) порядковых идеалов частично упорядоченного множества М дистрибутивна.
Категорию конечных частично упорядоченных множеств обозначим РОЯ, а категорию конечных дистрибутивных решеток конечной высоты обозначим БЬ.
Предложение 2 [13]. Категории РОБ и БЬ двойственны друг другу посредством контрава-риантного Нот-функтора Нот(*, 2), который ч. у. множеству М ставит в соответствие М* - решетку порядковых идеалов ч. у. множества М, и дистрибутивной решетке Б ставит в соответствие Ь* - частично упорядоченное множество неразложимых в объединение элементов дистрибутивной решетки Б. Более того, если М и Б соответствуют друг другу, то высота Б равна числу элементов М.
Предложение 3 [13]. Пусть Б - дистрибутивная решетка, и Р = Ь* - соответствующее ей ч. у. множество. Тогда Б является булевой решеткой, если и только если Р является антицепью.
Несложные вычисления доказывают следующую лемму. Соответствующая диаграмма Хассе изображена на рис. 2.
Лемма 1. Пусть даны операторы Б\ = В+ +а(ж), Б2 = В + Ь(х), Мг = В + р(х), М2 = = В + д(х) такие, что Б\о Б2 = М\ о М2, М\ ф ф М2 ф Б2. Тогда аир выражаются через
о — д
, д' - У о — д
Предложение 4 (критерий перестановочности) [7]. Два ЛОДО Бх = В + а, Ь2 = В + Ъ с коэффициентами из дифференциального поля
К являются перестановочными в произведении
В'
Ь1 о ¿2) если и только если а = Ь--— — В,, где
В
В - некоторая функция из поля К.
Предложение 5 [7]. Пусть даны два ЛОДО Ь1 =
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.