Матричное представление элементов фактора полиномиального кольца по нульмерному идеалу

Автор выражает благодарность В.Е.Воскресенскому за постановку задачи и денные обсуждения, а также С.Ю.Попона за полезные беседы.

Библиографический список

1. В. Е. Kunyvskii, В. Z. Moroz, V. Е. Voskresenskii On integral models of an algebraic torus. // Max - Planck - Institut fur Mathematic. Preprint Series 2001 (12).

2. В. E. Воскресенский, Т. В. Фомина Целые структуры в алгебраических торах. // Изв. РАН: Сер. матем. 1995. Т. 59: 5. С. 3-18.

3. Popov S . Yu ., Voskresenskii V .Е ., Galois lattices and reduction of algebraic tori.//Communications of Algebra, N 9, 2001. P.213-223.

4. С. Ю. Попов Стандартная целая модель алгебраического тора. //Вес.СамГУ.2001,К 4(22),С 20-54.

5.Г. Полна, Г. Cere Задачи и теоремы из анализа.//М.: Наука. 1978. 4.2.

УДК 681.3.06

А.В.МЕСЯНЖИН

Матричное представление элементов фактора полиномиального кольца по нульмерному идеалу 1

Введение

В работах |4, 5| развит общий алгоритмический подход к построению матричных представлений редуцированных по нульмерному идеалу полиномов с последующим применением этих представлений в задаче исследования корней идеала. В алгоритмах используется понятие стандартного базиса Гребнера, восходящее к Вухбергеру |6|. Однако в [1, 2, 10, 11, 12| было показано, что во многих задачах, связанных с полиномиальными идеалами, намного более эффективным является использование базисон Гребнера специального вида, называемых инволютивными. В данной статье показана целесообразность использования в вышеприведенной задаче алгоритмов, основанных на инволютивном делении Жане.

Ниже мы будем использовать следующие обозначения:

К, — К[хх,.. . ,хп] кольцо полиномов над полем К нулевой характеристики;

'Рабата финансировалась за счет гранта РФФИ 00-15-96691

з,3 идеалы в R;

/, д, h, q, г полипомы из R;

F, G, Н конечные подмножества из R;

red(/, G) редукция / по G;

Z>o множество неотрицательных чисел;

М = {ij1 • • • = ха I а = (di,..., (/,„) 6 Z5„} - множество мономов из R;

Т = {аи ! м е М, а € К} - множество термов из R;

и, V, w, я, t мономомы или термы;

U, V, W конечные подмножества из М; deg¡(u) степень переменной Xi в и; deg(u) полная степень монома и; cf(/, и) коэффициент терма и в нолииоме /;

>- допустимое мономиальное упорядочение с порядком переменных

x¡ У ... У хп;

It(/) лидирующий терм относительно упорядочения >-; 1с(/) = cf(/, lt(/)) лидирующий коэффициент /; lm(/) = lt(/)/Ir.(/) лидирующий моном /; и | V означает, что моном и делит моном v; а <С /3, где Q, 0 g Z"0 означает, что х° | х13, где ха, х" £ М; supp(/) = {76 Z"0 I tyх7 6 /} - множество степеней мономов, содержащихся в /.

Матричное представление

Пусть 3 - нульмерный идеал, G - его базис Гребнера. Построим множество [4j:

*У={1}иИ

В случае нульмерности идеала 3 выполняется условие |3):

поэтому W будет конечным множеством. Перепишем (1) в виде:

W = {1} и [ха I

По свойству базисов Гребнера [3] имеем, что если / редуцирован относительно G, то выполняется:

(V9 € G)(i 7 € supp(/)) deg(lm(g)) < 7.

Таким образом / € ¡ с, С £ W}, а это доказывает следую-

щее утверждение:

Теорема 1 IV является базисом фактор-кольца R/3, рассмотренного, как линейное пространство над полем К.

Операция умножения в R/3 определяется по правилу представителей:

(V/, /гея) red(/, G) • red (h, G) = red (/  h,G).

Зафиксируем полином h е R и запишем осуществляющий умножение на h линейный оператор [5]:

: R/3 R/3

red(/,G) i—» red(/>/, С)' y >

Пусть Hh = (hij)1j=l,liij £ К - матрица этого оператора относительно базиса W. Пусть также дан осуществляющий умножение на полином g оператор С* с матрицей Сд — j.

Так как произведение редуцированных полиномов коммутирует

red(g, G)  red(/>, G) = red (д -h,G) = red (h g,G) = red (h., G) • red(g, G),

то по (4) коммутирует и произведение операторов:

Таким образом множество линейных операторов ,д € R/3 (а также множество соответствующих матриц Lg) образует коммутативное кольцо, изоморфное кольцу R/3, и все арифметические операции над редуцированными полиномами можно заменить на аналогичные; действия над матрицами линейных операторов в базисе W, соответствующих данным полиномам.

Для построения же матриц первоначальных полиномов достаточно построить сначала матрицы, соответствующие линейным операторам умножения на простые переменные Xi: í¡Xi. Затем для полинома д = b¡xa —

bixf1!^ •   a:%n,b¡ € К, искомая матрица есть:

*

Теорема 2 (Теорема Стикельбергера)[5] Пусть 3 - нульмерный идеал,

и пусть А - множество его корней. Тогда для любого полинома h £ R все собственные значения линейного оператора ¿¡У' есть h(a), где а £ Л, и кратность собственного значения h(oi) равна кратности ß(at) корня идеала а.

Следствие. Имеют место соотношения для определителя

= П ч<*г(а\

аеЛ

и для следа матрицы линейного оператора

Тгасе(£|/,) = ^ р,(а)к(а).

а£Л

Теорема 3 [5] Пусть 3 - нульмерный идеал. Зафиксируем полином К € И и определим эрмитову квадратичную форму:

Хг^3 : И/Э — К

гес1

и пусть Хс/, матрица этой квадратичной формы. Тогда:

гапк

Эти свойства широко используются в исследовании корней нульмерного идеала |4, 5|, а также для нахождения самих корней.

Построение матриц

Рассмотрим сначала построение базиса фак тор-кольца.

Пример 1 Пусть К = К[х,у,г], и пусть нульмерный идеал 3 порождается множеством полипомов

г3 — хг — 1, ху2 + 2—1, х2у + уг + 1-1

Базис Гребнсра для этого идеала относительно упорядочения (1е.д_геу_1ех с порядком переменных х У у У г:

д0 = х2г — х2 + ху + уг + г2 + х — г — 1, 51 = г3 - хх — 1,

92 = ху2 + г - 1,

93 = х2у + уг + х - 1, дЛ = у2 г + ху - хг + х - у, дъ = хуг2 + хг2 - уг2 - х2 + ху + у2 + уг - 1, дв = х3 + хуг + 2уг2 - у2 + 2хг + уг — г2 + Зх + у — г — 1, р7 = 2/3 + хуг — 2жг2 + уг2 + х2 — 2ху - у2 + хг — уг + г2 - г

Базис фактор-кольца

IV = {хуг, хг2, у г2, х2, ху, у2, хг, уг, г2, х, у, г, 1}

можно построить перебором всех делителей и монома

т — 1сгп{1ш(.д) \ д е С}

с проверкой для них выполнения условия, чти они не делятся ни на какой из старших членов полиномов в С. Но при построении для того же идеала инволютивного базиса Жане [ 1, 10]

90 = хуг2 + хг2 — уг2 — х2 + ху + у2 + уг — 1,

91 = У3 + хуг — 2хг2 + уг2 +х2 — 2 ху — у2 + хг — уг + г2 — г, <?2 = х3 + хуг + 2 уг2 — у2 + 2хг + уг — г2 + Зх + у — 2 — 1,

<7.ч = уг3 - хуг - у, ^ <74 = ж2г — X2 + ху + 2/г + 22 + х — 2 — 1, ] 95 = г3 - Х2 — 1,

96 = ху2 + 2 - 1,

97 = х'2у + уг + х - 1,

<78 - у2 г + ху — хг + х — у,

99 = хг3 - х2 + ху + у г 4- г2 — г — 1

"побочным" продуктом работы агоритма 11ЧУОЫ_1Т1УеВа818 [1, 10] будет бинарное дерево Жане, в листьях которого полиномы из J, а в безлистовых узлах - все мономы из XV, и только они:

В общем случае можно сформулировать утверждение, позволяющее эффективно находить все элементы базиса

Теорема 4 Пусть Ь деление Жане и пусть 3 - базис Жане нульмерного идеала, тогда:

У/ = {« 6 М1 |

где V и/ означает, что моном у является инволютивным делителем монома VI |1, 10].

Доказательство

Так как инволютивный базис является частным случаем базиса Греб-нера, то в случае нульмерности идеала выполняется условие (2). Отсюда но построению ипволютивного базиса (умножение на немульгипликатив-ные переменные с последующей редукцией по мультипликативным) сразу следует, что для любого набора переменных

(Цх{1,..., хи)(Э Я е 1т(9) = . •

и дерево Жане будет "заполненным", то есть из любого нелистового узла существует ветвь по мультипликативной переменной, заканчивающаяся листом. Поэтому для монома ибМ существует лишь две взаимоисключающие альтернативы:

либо (3 ч € У)[1т(д) и], либо (3 ц е ,/)[« 1т(</)],

что при рассмотрении (1) и доказывает утверждение теоремы.

Пример 2 Приведем прим.ер "незаполненного " дерева Жане. Пусть идеал порождается множеством полиномов:

р . Г /о = У3 + хуг + 1, ' \ Л = х2у + хг + 1.

Для его базиса Гребнера

до = ху*г + А2 - х2 + у2 + хг, с . , 91 = х2у + хг + 1, I 32 = У3 + хуг + 1,

9з — х3г2 - хуг2 — х3 + ху2 + х2г — уг.

невыполняется условие (2), то есть идеал не нульмерный, а также выполнено О ф {1}, таким образом существует бесконечное множество корней идеала. Для базиса Жане

до — х3г2 — хуг2 — х3 + ху2 + х2г — у г, <71 = ху3 — хх2 + х — 2, . д2 = х2у + хг + 1, '| Яз = У3 + хуг + 1,

<74 = ху2г + х2гг - х2 + у2 + хг, 95 = хъу + х2г + х.

построено дерево Жане:

Видно, что отсутствуют заканчивающиеся листами ветви из узлов, соответствующих мономам {х*,х2г,хг,хуг,уг,у2г,2} — V и, таким образом, множество мономов, не делящихся на 1т(д), д е С:

{1,х,х2,х3,х3г,ху,ху2,у,у2}и{и € М | (Зи € У)[у \ь и]}

Как уже было сказано выше, для построения матриц, представляющих редуцированные по нульмерному идеалу полиномы, в первую очередь требуется построить матрицы ШХ1,..., ИХг1. Для построения обычно редуцируют по базису Гребнера все мономы х^ги^, С IV, тем самым находя их разложение по IV.

Более эффективным, однако, представляется работа с базисом Жане, и вместо обычной редукции использование инволютивной. Если рассмотреть элементы базиса IV, как нелистовые узлы дерева Жане, то

умножение на мультипликативную переменную есть элементарный переход в следующий по выбранной переменной узел. Если этот узел оказался листовым, то результат - тривиальная редукция хранящегося в листе полинома, то есть:

Если же узел, в который произошел переход, нелистовой, то он и будет результатом:

Таким образом, лишь в случае умножения узла на немультипликативную переменную придется пользоваться инволютивной редукцией, которая, как было показано в [1, 10], работает эффективнее классической редукции [6].

1. Gerdt VP., Blinkov Yu.A. Involutive Bases of Polynomial Ideals // Math. Сотр. Sim. 1998, 45. P.519-542.

2. Gerdt V.P., Blinkov Yu.A. Minimal Involutive Bases, // Math. Сотр. Simul. 1998, 45. P.543-560.

3. Krister Forsman. Elementary Aspects of Constructive Commutative Algebra. // Department of Electrical Engineering Linkoping University, S-581 83 Linkoping Sweden, 1992-09-15.

4. Laureano Gonzales - Vega and Guadalupe Trujillo Dpto. Symbolic Recipes for Polynomial System Solving: Real Solutions. // Matemáticas, Estadística y Computación Universidad de Cantabria, Santander 39071, Spain.

5. Fabrice Rouillier Solving zero-dimensional polynomial systems through the Rational Univariate Representation. // Institut National de Recherche Informatique et en Automatique, Rapport de recherche No 3426 20/05/98, theme 2 - Génie logiciel et calcul symbolique. Projet Polka.

6. Бухбергер Б. Базисы Грцбнера. Алгоритмический метод в теории полиномиальных идеалов // Компьютерная алгебра. Символьные и алгебраические вычисления. М. Мир, 1986. С.331-372.

Itf 4

(Э q G J)[xiWj = lm(ç)] =î- red^ijUiy, J) = —

($ q E J)[x,Wj = lm(<j)] iedi{xiWj, J) = XiWj.

Библиографический список

7. Д.Кокс, Дж.Литтл, Д.О'ши. Идеалы, многообразия и алгоритмы. Введение в вычислительные аспекты алгебраической и коммутативной алгебры: Пер. с англ.-М.: Мир, 2000. 687 е.,ил.

8. Гердт В.П., Блинков Ю.А. Инволютивное деление мономов // Программирование. 1998, 6. С.22-24.

9. Gerdt, V.P. Involutive Division Technique: Some Generalizations and Optimizations 11 Записки научных семинаров СПОМИ (С.Петербург) 1999, 258. С.185-206.

10. Г'ердт В.П., Янович ДА., Блинков Ю.А. Быстрый поиск делителя Жане // Прог раммирование. 2001, 1. С.32-36.

11. Gerdt V.P., Blinkov Yu.A., Yanovich D.A. Construction of Janet Bases

I.Monomial Bases. In: Computer Algebra in Scientific Computing / CASC'01, V.G.Ganzha, E.W.Mayr and E.V.Vorozhtsov (Eds.), Springer-Verlag, Berlin, 2001, pp. 233-248.

12. Gerdt V.P., Blinkov Yu.A., Yanovich D.A. Construction of Janet Bases

II.Polynomial Bases. In: Computer Algebra in Scientific Computing / CASC'01, V.G.Ganzha, E.W.Mayr and E.V.Vorozhtsov (Eds.), Springer-Verlag, Berlin, 2001, pp. 248-264.

УДК 512.3

А.И. БОБЫЛЕВ

Подсчет гауссовых интегралов методом изомстрий

Пусть 0>р — поле р-адических чисел, | • |р норма этого поля, Ор кольцо целых р-адических чисел, С/р — группа р-адических единиц; ёх — аддитивная мера Хаара в (2Р1 подчиненная условию

о,

Хр{х) — аддитивный характер поля <Ц>р; В1(а) и 57(о) — соответственно р-адический круг и р-адическая окружность с центром в точке а € и