Лежит ли многочлен в идеале

[GYNJ]

Рассмотрим идеал $I=(1+x+x^2; 1+y+y^2)\subset \mathbb{Z}[x,y]$ и многочлен $f(x,y)=(1+x+...+x^5)(1+y+...+y^5)$, хочу понять лежит ли он в этом идеале(ах да, пусть порядок такой: $y \prec x$.

В данном случае данный базис идеала является базисом Гребнера, т.е можно спокойно делить $f$ на порождающие многочлены.
Есть такой алгоритм: берем старший член многочлена $f: x^5y^5=in(f)$, если он делится на $in(1+x+x^2)=x^2$ или $ in(1+y+y^2)=y^2$ тогда пусть $Q=in(f)/in(1+x+x^2)$ далее составляется многочлен $f_{1}=f-Q*in(1+x+x^2)$. Если он равен нулю то многочлен из условия лежит в идеале, иначе рассматриваем старшие члены уже его вместе с базисными и если он делится то делим, если нет, то $f$ не лежит.
Уже видно что будет больше одной итерации и считать очень уже много, есть ли способ выяснять подобные вещи проще(в плане вычислений)?

[vpb]

GYNJ в сообщении #1502233 писал(а):

есть ли способ выяснять подобные вещи проще(в плане вычислений)?

В общем случае это сложный вопрос, вряд ли можно проще. А в данном ответ усматривается тривиально и без Грёбнера. (Как -- сами подумайте !. Вопрос для первого курса, от силы. А то и школьника. )

[nnosipov]

vpb в сообщении #1502242 писал(а):

Вопрос для первого курса, от силы. А то и школьника.

Согласен. Даже и считать-то практически нечего.

[GYNJ]

Ну да $1+x+...+x^5=(1+x+x^2)(1+x^3)$ - глупый пример выбрал, но если, допустим, взять $f(x,y)=(1+...+x^5)(1+...+y^5)-x^3y^4-x^2y^2$- тут уже менее очевидно(но я знаю, что он точно не лежит) вот как с ним быть, использовать описанный мною алгоритм лишь?

[nnosipov]

GYNJ в сообщении #1502269 писал(а):

использовать описанный мною алгоритм лишь?

Если пример не слишком искусственный, то да, чудес не бывает.

GYNJ в сообщении #1502269 писал(а):

взять $f(x,y)=(1+...+x^5)(1+...+y^5)-x^3y^4-x^2y^2$- тут уже менее очевидно(но я знаю, что он точно не лежит)

Да, точно не лежит, это можно проверить с помощью пакета Groebner в Maple.

[GYNJ]

Да, я видел что есть в Maple и во многих других системах компьютерной алгебры, но мне хотелось бы узнать именно о возможности проверять это "руками"
(Мне не важные самые общие случаи, достаточно даже идеалов из $\mathbb{Z}[x,y]$ с 2-4 порождающими)

[nnosipov]

GYNJ в сообщении #1502303 писал(а):

проверять это "руками"

С двумя переменными это еще может быть реально (если степени не зашкаливают), но с тремя уже довольно муторно. В книжке Аржанцева "Базисы Гребнера и системы алгебраических уравнений" есть примеры подобных упражнений, можно поэкспериментировать.

Как я понимаю, цель подобных примеров --- помочь разобраться с соответствующим алгоритмом. Их нужно решать именно "вручную", поэтому предлагать слишком громоздкие задания смысла нет.

[GYNJ]

nnosipov в сообщении #1502312 писал(а):

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

Нет, просто есть задача в которой базисы Гребнера и все вышенаписанное вытекает естественным образом, и мне нет смысла рассматривать что-то больше, чем $\mathbb{Z}[x,y]$.

А вышеописанный алгоритм "вхождения" многочлена в идеал я как раз в Аржанцеве и смотрел, еще читал в книге Д. Айзенбада, но там есть в принципе тот же алгоритм. Я полагаю что можно упростить вычисления, если перейти к минимальному базису Гребнера, но в случае двух пораждающих...

[Xaositect]

А в вашей задаче, как в примере, идеал порожден унарными многочленами (каждый зависит от одной переменной)?

[GYNJ]

Xaositect в сообщении #1502324 писал(а):

А в вашей задаче, как в примере, идеал порожден унарными многочленами (каждый зависит от одной переменной)?

Ну да, причем их НОД=1 т.е не зацеплены и это лучший "вид" идеала

[Xaositect]

GYNJ в сообщении #1502342 писал(а):

Ну да, причем их НОД=1 т.е не зацеплены и это лучший "вид" идеала

Тогда все проще, можно просто делить с остатком сначала на один многочлен, а потом на второй.

[GYNJ]

Xaositect в сообщении #1502355 писал(а):

Тогда все проще, можно просто делить с остатком сначала на один многочлен, а потом на второй.

Т.е так можно всегда делать после приведения к базису Гребнера, если окажется, что пораждающие многочлены от одной переменной, т.е допустим для идеала, например $I=(x^3+xy, y^2+y)$ подобное уже не прокатит?

Если я правильно понял вас, то объясните почему это верно?

[vpb]

Вообще говоря, когда речь о двух многочленах из ${\mathbb Z}[x]$, непонятно, что такое разделить один на другой с остатком. Ведь ${\mathbb Z}[x]$ не евклидово кольцо. Например, как разделить с остатком $2x^2$ на $4x+1$? Впрочем, при некотором желании можно делению с остатком в ${\mathbb Z}[x]$ придать смысл. Но тогда всё равно вот это утверждение

Xaositect в сообщении #1502355 писал(а):

Тогда все проще, можно просто делить с остатком сначала на один многочлен, а потом на второй.

не очевидно, как мне видится.

Есть еще такой аспект. Допустим, есть многочлены $f_1,\dots, f_m\in{\mathbb Z}[x]$, и еще один $f$. Как выяснить, лежит ли $f$ в идеале $ (f_1,\ldots,f_m)$? Теоретически можно, построить Грёбнера и т.д., но там будут коэффициенты у промежуточных результатов расти стремительно. Тем не менее, как я понимаю, есть полиномиальный (по времени и памяти) алгоритм (полиномиальный в смысле, что требуемые время и память ограничены полиномом от суммарного числа цифр во всех коэффициентах всех данных). А от двух переменных если смотреть, ${\mathbb Z}[x,y]$, там вообще глухо (я когда-то думал, чуть голову не сломал).

[GYNJ]

Спасибо. В общем, стало ясно что никаких быстрых способов нету, буду как советовали на Maple считать