Результирующий

Математическая концепция в теории полиномов

В математике результант двух многочленов — это полиномиальное выражение их коэффициентов, которое равно нулю тогда и только тогда, когда многочлены имеют общий корень (возможно , в расширении поля ), или, что эквивалентно, общий множитель (над их полем коэффициентов). В некоторых старых текстах результант также называется элиминантом . [ ^1]

Результант широко используется в теории чисел , либо напрямую, либо через дискриминант , который по сути является результантом многочлена и его производной . Результант двух многочленов с рациональными или полиномиальными коэффициентами может быть эффективно вычислен на компьютере. Это базовый инструмент компьютерной алгебры и встроенная функция большинства систем компьютерной алгебры . Он используется, среди прочего, для цилиндрического алгебраического разложения , интегрирования рациональных функций и рисования кривых , определяемых двумерным полиномиальным уравнением .

Результант n однородных полиномов от n переменных (также называемый многомерным результантом или результантом Маколея для отличия от обычного результанта) является обобщением обычного результанта , введенным Маколеем . ^[2] Он является, вместе с базисами Грёбнера , одним из основных инструментов теории исключения .

Обозначение

Результат двух одномерных полиномов A и B обычно обозначается или ${\displaystyle \operatorname {res} (A,B)}$ ${\displaystyle \operatorname {Res} (A,B).}$

Во многих приложениях результирующего многочлены зависят от нескольких неопределенных и могут рассматриваться как одномерные многочлены в одном из своих неопределенных, с многочленами в других неопределенных как коэффициенты. В этом случае неопределенность, выбранная для определения и вычисления результирующего, указывается как нижний индекс: или ${\displaystyle \operatorname {res} _{x}(A,B)}$ ${\displaystyle \operatorname {Res} _{x}(A,B).}$

Степени полиномов используются в определении результирующего. Однако полином степени d также может рассматриваться как полином более высокой степени, где старшие коэффициенты равны нулю. Если для результирующего используется такая более высокая степень, она обычно указывается как нижний или верхний индекс, например или ${\displaystyle \operatorname {res} _{d,e}(A,B)}$ ${\displaystyle \operatorname {res} _{x}^{d,e}(A,B).}$

Определение

Результант двух одномерных многочленов над полем или над коммутативным кольцом обычно определяется как определитель их матрицы Сильвестра . Точнее, пусть и будут ненулевыми многочленами степеней d и e соответственно. Обозначим через векторное пространство (или свободный модуль , если коэффициенты принадлежат коммутативному кольцу) размерности i, элементами которого являются многочлены степени строго меньшей i . Отображение такое, что является линейным отображением между двумя пространствами той же размерности. По базису степеней x (перечисленных в порядке убывания) это отображение представляется квадратной матрицей размерности d + e , которая называется матрицей Сильвестра A и B (для многих авторов и в статье Матрица Сильвестра матрица Сильвестра определяется как транспонированная эта матрица; это соглашение здесь не используется, так как оно нарушает обычное соглашение о записи матрицы линейного отображения). $${\displaystyle A=a_{0}x^{d}+a_{1}x^{d-1}+\cdots +a_{d}}$$ $${\displaystyle B=b_{0}x^{e}+b_{1}x^{e-1}+\cdots +b_{e}}$$ ${\displaystyle {\mathcal {P}}_{i}}$ $${\displaystyle \varphi :{\mathcal {P}}_{e}\times {\mathcal {P}}_{d}\rightarrow {\mathcal {P}}_{d+e}}$$ $${\displaystyle \varphi (P,Q)=AP+BQ}$$

Результат A и B , таким образом, является определителем , который имеет e столбцов a _i и d столбцов b _j (тот факт, что первый столбец a и первый столбец b имеют одинаковую длину, то есть d = e , здесь используется только для упрощения отображения определителя). Например, взяв d = 3 и e = 2, мы получаем $${\displaystyle {\begin{vmatrix}a_{0}&0&\cdots &0&b_{0}&0&\cdots &0\\a_{1}&a_{0}&\cdots &0&b_{1}&b_{0}&\cdots &0\\a_{2}&a_{1}&\ddots &0&b_{2}&b_{1}&\ddots &0\\\vdots &\vdots &\ddots &a_{0}&\vdots &\vdots &\ddots &b_{0}\\a_{d}&a_{d-1}&\cdots &\vdots &b_{e}&b_{e-1}&\cdots &\vdots \\0&a_{d}&\ddots &\vdots &0&b_{e}&\ddots &\vdots \\\vdots &\vdots &\ddots &a_{d-1}&\vdots &\vdots &\ddots &b_{e-1}\\0&0&\cdots &a_{d}&0&0&\cdots &b_{e}\end{vmatrix}},}$$ $${\displaystyle {\begin{vmatrix}a_{0}&0&b_{0}&0&0\\a_{1}&a_{0}&b_{1}&b_{0}&0\\a_{2}&a_{1}&b_{2}&b_{1}&b_{0}\\a_{3}&a_{2}&0&b_{2}&b_{1}\\0&a_{3}&0&0&b_{2}\end{vmatrix}}.}$$

Если коэффициенты полиномов принадлежат целочисленной области , то где и являются соответственно корнями, подсчитанными с их кратностями, A и B в любом алгебраически замкнутом поле, содержащем целочисленную область. Это является прямым следствием характеризующих свойств результанта, которые появляются ниже. В общем случае целочисленных коэффициентов алгебраически замкнутое поле обычно выбирается как поле комплексных чисел . $${\displaystyle \operatorname {res} (A,B)=a_{0}^{e}b_{0}^{d}\prod _{\begin{array}{c}1\leq i\leq d\\1\leq j\leq e\end{array}}(\lambda _{i}-\mu _{j})=a_{0}^{e}\prod _{i=1}^{d}B(\lambda _{i})=(-1)^{de}b_{0}^{d}\prod _{j=1}^{e}A(\mu _{j}),}$$ ${\displaystyle \lambda _{1},\dots ,\lambda _{d}}$ ${\displaystyle \mu _{1},\dots ,\mu _{e}}$

Характеристики

В этом разделе и его подразделах A и B — два многочлена относительно x соответствующих степеней d и e , а их результирующий обозначается ${\displaystyle \operatorname {res} (A,B).}$

Характеризующие свойства

Следующие свойства справедливы для результанта двух многочленов с коэффициентами в коммутативном кольце R. Если R — поле или, в более общем случае, область целостности , результант — это единственная функция коэффициентов двух многочленов, которая удовлетворяет этим свойствам.

• Если R является подкольцом другого кольца S , то это значит , что A и B имеют одинаковый результант, если рассматривать их как многочлены над R или S. ${\displaystyle \operatorname {res} _{R}(A,B)=\operatorname {res} _{S}(A,B).}$
• Если d = 0 (то есть если — ненулевая константа), то Аналогично, если e = 0 , то ${\displaystyle A=a_{0}}$ ${\displaystyle \operatorname {res} (A,B)=a_{0}^{e}.}$ ${\displaystyle \operatorname {res} (A,B)=b_{0}^{d}.}$
• ${\displaystyle \operatorname {res} (x+a_{1},x+b_{1})=b_{1}-a_{1}}$
• ${\displaystyle \operatorname {res} (B,A)=(-1)^{de}\operatorname {res} (A,B)}$
• ${\displaystyle \operatorname {res} (AB,C)=\operatorname {res} (A,C)\operatorname {res} (B,C)}$

Нули

• Результат двух многочленов с коэффициентами в целочисленной области равен нулю тогда и только тогда, когда они имеют общий делитель положительной степени.
• Результат двух многочленов с коэффициентами в целочисленной области равен нулю тогда и только тогда, когда они имеют общий корень в алгебраически замкнутом поле, содержащем коэффициенты.
• Существует многочлен P степени меньше e и многочлен Q степени меньше d , такие что Это обобщение тождества Безу на многочлены над произвольным коммутативным кольцом. Другими словами, результант двух многочленов принадлежит идеалу, порожденному этими многочленами. ${\displaystyle \operatorname {res} (A,B)=AP+BQ.}$

Инвариантность относительно кольцевых гомоморфизмов

Пусть A и B — два многочлена соответствующих степеней d и e с коэффициентами в коммутативном кольце R и гомоморфизм колец R в другое коммутативное кольцо S. Применение к коэффициентам многочлена продолжается до гомоморфизма колец многочленов , который также обозначается С помощью этих обозначений имеем: ${\displaystyle \varphi \colon R\to S}$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle R[x]\to S[x]}$ ${\displaystyle \varphi .}$

• Если сохраняет степени A и B (то есть если и ), то ${\displaystyle \varphi }$ ${\displaystyle \deg(\varphi (A))=d}$ ${\displaystyle \deg(\varphi (B))=e}$ $${\displaystyle \varphi (\operatorname {res} (A,B))=\operatorname {res} (\varphi (A),\varphi (B)).}$$
• Если и тогда ${\displaystyle \deg(\varphi (A))<d}$ ${\displaystyle \deg(\varphi (B))<e,}$ $${\displaystyle \varphi (\operatorname {res} (A,B))=0.}$$
• Если и и старший коэффициент A равен тогда ${\displaystyle \deg(\varphi (A))=d}$ ${\displaystyle \deg(\varphi (B))=f<e,}$ ${\displaystyle a_{0}}$ $${\displaystyle \varphi (\operatorname {res} (A,B))=\varphi (a_{0})^{e-f}\operatorname {res} (\varphi (A),\varphi (B)).}$$
• Если и и старший коэффициент B равен тогда ${\displaystyle \deg(\varphi (A))=f<d}$ ${\displaystyle \deg(\varphi (B))=e,}$ ${\displaystyle b_{0}}$ $${\displaystyle \varphi (\operatorname {res} (A,B))=(-1)^{e(d-f)}\varphi (b_{0})^{d-f}\operatorname {res} (\varphi (A),\varphi (B)).}$$

Эти свойства легко выводятся из определения результанта как определителя. Они в основном используются в двух ситуациях. Для вычисления результанта многочленов с целыми коэффициентами обычно быстрее вычислить его по модулю нескольких простых чисел и получить желаемый результант с помощью китайской теоремы об остатках . Когда R — кольцо многочленов от других неопределенных, а S — кольцо, полученное путем специализации к числовым значениям некоторых или всех неопределенных R , эти свойства можно переформулировать так, как если бы степени сохранялись при специализации, результант специализации двух многочленов был бы специализацией результанта . Это свойство является фундаментальным, например, для цилиндрического алгебраического разложения .

Инвариантность относительно замены переменной

• ${\displaystyle \operatorname {res} (A(x+a),B(x+a))=\operatorname {res} (A(x),B(x))}$
• ${\displaystyle \operatorname {res} (A(ax),B(ax))=a^{de}\operatorname {res} (A(x),B(x))}$
• Если и являются обратными многочленами A и B соответственно, то ${\displaystyle A_{r}(x)=x^{d}A(1/x)}$ ${\displaystyle B_{r}(x)=x^{e}B(1/x)}$ $${\displaystyle \operatorname {res} (A_{r},B_{r})=(-1)^{de}\operatorname {res} (A,B)}$$

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

Инвариантность относительно изменения полиномов

• Если a и b — ненулевые константы (то есть они не зависят от неопределенности x ), а A и B такие, как указано выше, то $${\displaystyle \operatorname {res} (aA,bB)=a^{e}b^{d}\operatorname {res} (A,B).}$$
• Если A и B такие, как указано выше, а C — другой многочлен, такой что степень A – CB равна δ , то $${\displaystyle \operatorname {res} (B,A-CB)=b_{0}^{\delta -d}\operatorname {res} (B,A).}$$
• В частности, если либо B является моническим , либо deg C < deg A – deg B , то и, если f = deg C > deg A – deg B = d – e , то $${\displaystyle \operatorname {res} (B,A-CB)=\operatorname {res} (B,A),}$$ $${\displaystyle \operatorname {res} (B,A-CB)=b_{0}^{e+f-d}\operatorname {res} (B,A).}$$

Эти свойства подразумевают, что в алгоритме Евклида для многочленов и всех его вариантах ( псевдоостаточные последовательности ) результирующий двух последовательных остатков (или псевдоостатков) отличается от результирующего исходных многочленов на коэффициент, который легко вычисляется. Наоборот, это позволяет вывести результирующий исходных многочленов из значения последнего остатка или псевдоостатка. Это исходная идея алгоритма подрезультат-псевдоостаток-последовательность , который использует приведенные выше формулы для получения подрезультирующих многочленов как псевдоостатков, а результирующий — как последний ненулевой псевдоостаток (при условии, что результирующий не равен нулю). Этот алгоритм работает для многочленов над целыми числами или, в более общем смысле, над целочисленной областью, без какого-либо деления, кроме точных делений (то есть без использования дробей). Он включает в себя арифметические операции, в то время как вычисление определителя матрицы Сильвестра с помощью стандартных алгоритмов требует арифметических операций. ${\displaystyle O(de)}$ ${\displaystyle O((d+e)^{3})}$

Общие свойства

В этом разделе мы рассмотрим два многочлена и , чьи коэффициенты d + e + 2 являются различными неизвестными . Пусть будет кольцом многочленов над целыми числами, определяемыми этими неизвестными. Результант часто называют общим результантом для степеней d и e . Он обладает следующими свойствами. $${\displaystyle A=a_{0}x^{d}+a_{1}x^{d-1}+\cdots +a_{d}}$$ $${\displaystyle B=b_{0}x^{e}+b_{1}x^{e-1}+\cdots +b_{e}}$$ $${\displaystyle R=\mathbb {Z} [a_{0},\ldots ,a_{d},b_{0},\ldots ,b_{e}]}$$ ${\displaystyle \operatorname {res} (A,B)}$

• ${\displaystyle \operatorname {res} (A,B)}$является абсолютно неприводимым многочленом.
• Если — идеал , порожденный A и B , то — главный идеал , порожденный . ${\displaystyle I}$ ${\displaystyle R[x]}$ ${\displaystyle I\cap R}$ ${\displaystyle \operatorname {res} (A,B)}$

Однородность

Общий результирующий для степеней d и e однороден в различных отношениях . Точнее:

• Он однороден степени e по ${\displaystyle a_{0},\ldots ,a_{d}.}$
• Он однороден степени d по ${\displaystyle b_{0},\ldots ,b_{e}.}$
• Он однороден степени d + e по всем переменным и ${\displaystyle a_{i}}$ ${\displaystyle b_{j}.}$
• Если и задан вес i (то есть вес каждого коэффициента равен его степени как элементарного симметрического многочлена ), то он квазиоднороден с общим весом de . ${\displaystyle a_{i}}$ ${\displaystyle b_{i}}$
• Если P и Q — однородные многомерные полиномы соответствующих степеней d и e , то их результирующая в степенях d и e относительно некоторой неопределенности x , обозначенная в § Обозначения, является однородной степени de относительно остальных неопределенностей. ${\displaystyle \operatorname {res} _{x}^{d,e}(P,Q)}$

Устранение собственности

Пусть — идеал, порожденный двумя многочленами A и B в кольце многочленов , где само является кольцом многочленов над полем. Если хотя бы один из A и B является моническим по x , то: ${\displaystyle I=\langle A,B\rangle }$ ${\displaystyle R[x],}$ ${\displaystyle R=k[y_{1},\ldots ,y_{n}]}$

• ${\displaystyle \operatorname {res} _{x}(A,B)\in I\cap R}$
• Идеалы и определяют одно и то же алгебраическое множество . То есть, кортеж из n элементов алгебраически замкнутого поля является общим нулем элементов тогда и только тогда, когда он является нулем ${\displaystyle I\cap R}$ ${\displaystyle R\operatorname {res} _{x}(A,B)}$ ${\displaystyle I\cap R}$ ${\displaystyle \operatorname {res} _{x}(A,B).}$
• Идеал имеет тот же радикал , что и главный идеал. То есть, каждый элемент имеет мощность, кратную ${\displaystyle I\cap R}$ ${\displaystyle R\operatorname {res} _{x}(A,B).}$ ${\displaystyle I\cap R}$ ${\displaystyle \operatorname {res} _{x}(A,B).}$
• Все неприводимые множители делят каждый элемент ${\displaystyle \operatorname {res} _{x}(A,B)}$ ${\displaystyle I\cap R.}$

Первое утверждение является основным свойством результанта. Остальные утверждения являются непосредственными следствиями второго, что можно доказать следующим образом.

Так как хотя бы один из A и B является моническим, кортеж является нулем тогда и только тогда, когда существует такое, что является общим нулем A и B. Такой общий нуль также является нулем всех элементов. Наоборот, если является общим нулем элементов , то является нулем результирующего, и существует такое, что является общим нулем A и B. Таким образом , и имеют точно такие же нули. ${\displaystyle (\beta _{1},\ldots ,\beta _{n})}$ ${\displaystyle \operatorname {res} _{x}(A,B)}$ ${\displaystyle \alpha }$ ${\displaystyle (\beta _{1},\ldots ,\beta _{n},\alpha )}$ ${\displaystyle I\cap R.}$ ${\displaystyle (\beta _{1},\ldots ,\beta _{n})}$ ${\displaystyle I\cap R,}$ ${\displaystyle \alpha }$ ${\displaystyle (\beta _{1},\ldots ,\beta _{n},\alpha )}$ ${\displaystyle I\cap R}$ ${\displaystyle R\operatorname {res} _{x}(A,B)}$

Вычисление

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

Так как результирующий является определителем матрицы Сильвестра (и матрицы Безу ), его можно вычислить, используя любой алгоритм для вычисления определителей. Для этого требуются арифметические операции. Поскольку известны алгоритмы с лучшей сложностью (см. ниже), этот метод на практике не используется. ${\displaystyle O(n^{3})}$

Из § Инвариантность относительно изменения полиномов следует, что вычисление результанта тесно связано с алгоритмом Евклида для полиномов . Это показывает, что вычисление результанта двух полиномов степеней d и e может быть выполнено в арифметических операциях в поле коэффициентов. ${\displaystyle O(de)}$

Однако, когда коэффициенты являются целыми числами, рациональными числами или многочленами, эти арифметические операции подразумевают ряд вычислений НОД коэффициентов того же порядка и делают алгоритм неэффективным. Последовательности псевдоостатков подрезультата были введены для решения этой проблемы и избегания любых дробей и любых вычислений НОД коэффициентов. Более эффективный алгоритм получается с использованием хорошего поведения результанта при кольцевом гомоморфизме коэффициентов: чтобы вычислить результант двух многочленов с целыми коэффициентами, вычисляют их результанты по модулю достаточного количества простых чисел , а затем восстанавливают результат с помощью китайской теоремы об остатках .

Использование быстрого умножения целых чисел и многочленов позволяет использовать алгоритмы для нахождения результирующих чисел и наибольших общих делителей, имеющие лучшую временную сложность , которая имеет порядок сложности умножения, умноженной на логарифм размера входных данных ( где s — верхняя граница количества цифр входных многочленов). ${\displaystyle \log(s(d+e)),}$

Применение к полиномиальным системам

Результанты были введены для решения систем полиномиальных уравнений и являются старейшим доказательством того, что существуют алгоритмы для решения таких систем. Они в первую очередь предназначены для систем двух уравнений с двумя неизвестными, но также позволяют решать общие системы.

Случай двух уравнений с двумя неизвестными

Рассмотрим систему двух полиномиальных уравнений , где P и Q — полиномы соответствующих полных степеней d и e . Тогда — полином от x , который в общем случае имеет степень de (по свойствам § Однородность). Значение x является корнем R тогда и только тогда, когда либо существует в алгебраически замкнутом поле, содержащем коэффициенты, такое, что , или и (в этом случае говорят, что P и Q имеют общий корень на бесконечности для ). $${\displaystyle {\begin{aligned}P(x,y)&=0\\Q(x,y)&=0,\end{aligned}}}$$ ${\displaystyle R=\operatorname {res} _{y}^{d,e}(P,Q)}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle P(\alpha ,\beta )=Q(\alpha ,\beta )=0}$ ${\displaystyle \deg(P(\alpha ,y))<d}$ ${\displaystyle \deg(Q(\alpha ,y))<e}$ ${\displaystyle x=\alpha }$

Таким образом, решения системы получаются путем вычисления корней R , и для каждого корня вычисляя общий(ие) корень(и) и ${\displaystyle \alpha ,}$ ${\displaystyle P(\alpha ,y),}$ ${\displaystyle Q(\alpha ,y),}$ ${\displaystyle \operatorname {res} _{x}(P,Q).}$

Теорема Безу вытекает из значения , произведения степеней P и Q . Фактически, после линейной замены переменных можно предположить, что для каждого корня x результанта существует ровно одно значение y такое, что ( x , y ) является общим нулем P и Q . Это показывает, что число общих нулей не больше степени результанта, то есть не больше произведения степеней P и Q . С некоторыми техническими подробностями это доказательство можно расширить, чтобы показать, что, учитывая кратности и нули на бесконечности, число нулей в точности равно произведению степеней. ${\displaystyle \deg \left(\operatorname {res} _{y}(P,Q)\right)\leq de}$

Общий случай

На первый взгляд кажется, что результанты можно применить к общей системе полиномиальных уравнений , вычислив результанты каждой пары относительно для исключения одного неизвестного и повторяя процесс до получения одномерных полиномов. К сожалению, это приводит к появлению множества ложных решений, которые трудно удалить. $${\displaystyle {\begin{aligned}P_{1}(x_{1},\ldots ,x_{n})&=0\\&\;\;\vdots \\P_{k}(x_{1},\ldots ,x_{n})&=0\end{aligned}}}$$ ${\displaystyle (P_{i},P_{j})}$ ${\displaystyle x_{n}}$

Метод, введенный в конце 19 века, работает следующим образом: ввести k − 1 новых неизвестных и вычислить Это многочлен в , коэффициенты которого являются многочленами в , которые обладают свойством, что является общим нулем этих многочленных коэффициентов, тогда и только тогда, когда одномерные многочлены имеют общий нуль, возможно, на бесконечности . Этот процесс может быть повторен до нахождения одномерных многочленов. ${\displaystyle U_{2},\ldots ,U_{k}}$ $${\displaystyle \operatorname {res} _{x_{n}}(P_{1},U_{2}P_{2}+\cdots +U_{k}P_{k}).}$$ ${\displaystyle U_{2},\ldots ,U_{k}}$ ${\displaystyle x_{1},\ldots ,x_{n-1},}$ ${\displaystyle \alpha _{1},\ldots ,\alpha _{n-1}}$ ${\displaystyle P_{i}(\alpha _{1},\ldots ,\alpha _{n-1},x_{n})}$

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

Этот алгоритм очень сложен и имеет огромную временную сложность . Поэтому его интерес в основном исторический.

Другие приложения

Теория чисел

Дискриминант многочлена, который является фундаментальным инструментом в теории чисел , равен , где — старший коэффициент многочлена , а его степень. ${\displaystyle a_{0}^{-1}(-1)^{n(n-1)/2}\operatorname {res} _{x}(f(x),f'(x))}$ ${\displaystyle a_{0}}$ ${\displaystyle f(x)}$ ${\displaystyle n}$

Если и — алгебраические числа, такие, что , то — корень результирующего числа и — корень числа , где — степень числа . В сочетании с тем фактом, что — корень числа , это показывает, что множество алгебраических чисел является полем . ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle P(\alpha )=Q(\beta )=0}$ ${\displaystyle \gamma =\alpha +\beta }$ ${\displaystyle \operatorname {res} _{x}(P(x),Q(z-x)),}$ ${\displaystyle \tau =\alpha \beta }$ ${\displaystyle \operatorname {res} _{x}(P(x),x^{n}Q(z/x))}$ ${\displaystyle n}$ ${\displaystyle Q(y)}$ ${\displaystyle 1/\beta }$ ${\displaystyle y^{n}Q(1/y)=0}$

Пусть будет алгебраическим расширением поля, порожденным элементом, имеющим в качестве минимального многочлена . Каждый элемент из может быть записан как , где является многочленом. Тогда является корнем и этот результирующий является степенью минимального многочлена из ${\displaystyle K(\alpha )}$ ${\displaystyle \alpha ,}$ ${\displaystyle P(x)}$ ${\displaystyle \beta \in K(\alpha )}$ ${\displaystyle \beta =Q(\alpha ),}$ ${\displaystyle Q}$ ${\displaystyle \beta }$ ${\displaystyle \operatorname {res} _{x}(P(x),z-Q(x)),}$ ${\displaystyle \beta .}$

Алгебраическая геометрия

Если заданы две плоские алгебраические кривые, заданные как нули многочленов P ( x , y ) и Q ( x , y ) , то результирующий результат позволяет вычислить их пересечение. Точнее, корни являются x -координатами точек пересечения и общих вертикальных асимптот, а корни являются y -координатами точек пересечения и общих горизонтальных асимптот. ${\displaystyle \operatorname {res} _{y}(P,Q)}$ ${\displaystyle \operatorname {res} _{x}(P,Q)}$

Рациональная плоская кривая может быть определена параметрическим уравнением , где P , Q и R — полиномы. Неявное уравнение кривой задается как Степень этой кривой — это наивысшая степень P , Q и R , которая равна общей степени результирующего. $${\displaystyle x={\frac {P(t)}{R(t)}},\qquad y={\frac {Q(t)}{R(t)}},}$$ $${\displaystyle \operatorname {res} _{t}(xR-P,yR-Q).}$$

Символическая интеграция

В символьном интегрировании для вычисления первообразной рациональной дроби используется разложение дроби на части для разложения интеграла на «рациональную часть», которая является суммой рациональных дробей, чьи антипримитивы являются рациональными дробями, и «логарифмическую часть», которая является суммой рациональных дробей вида, где Q — бесквадратный многочлен , а P — многочлен меньшей степени, чем Q. Первообразная такой функции обязательно включает логарифмы и, как правило, алгебраические числа (корни Q ). Фактически, первообразная — это то, где сумма пробегает все комплексные корни Q. $${\displaystyle {\frac {P(x)}{Q(x)}},}$$ $${\displaystyle \int {\frac {P(x)}{Q(x)}}dx=\sum _{Q(\alpha )=0}{\frac {P(\alpha )}{Q'(\alpha )}}\log(x-\alpha ),}$$

Число алгебраических чисел, входящих в это выражение, обычно равно степени Q , но часто случается, что можно вычислить выражение с меньшим числом алгебраических чисел. Метод Лазарда – Риобу – Трегера создает выражение, в котором число алгебраических чисел минимально, без каких-либо вычислений с алгебраическими числами.

Пусть будет квадратно-свободной факторизацией результирующего, который появляется справа. Трэгер доказал, что первообразная — это где внутренние суммы пробегают корни (если сумма равна нулю, как пустая сумма ), и — многочлен степени i от x . Вклад Лазара-Риобу — это доказательство того, что — подрезультат степени i и Таким образом, он получается бесплатно, если результирующий вычисляется с помощью последовательности псевдоостатка подрезультата . $${\displaystyle S_{1}(r)S_{2}(r)^{2}\cdots S_{k}(r)^{k}=\operatorname {res} _{r}(rQ'(x)-P(x),Q(x))}$$ $${\displaystyle \int {\frac {P(x)}{Q(x)}}dx=\sum _{i=1}^{k}\sum _{S_{i}(\alpha )=0}\alpha \log(T_{i}(\alpha ,x)),}$$ ${\displaystyle S_{i}}$ ${\displaystyle S_{i}=1}$ ${\displaystyle T_{i}(r,x)}$ ${\displaystyle T_{i}(r,x)}$ ${\displaystyle rQ'(x)-P(x)}$ ${\displaystyle Q(x).}$

Компьютерная алгебра

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

Однородный результирующий

Результант также определяется для двух однородных многочленов от двух неизвестных. Для двух однородных многочленов P ( x , y ) и Q ( x , y ) соответствующих общих степеней p и q их однородный результант является определителем матрицы над мономиальным базисом линейного отображения , где A пробегает двумерные однородные многочлены степени q − 1 , а B пробегает однородные многочлены степени p − 1 . Другими словами, однородный результант P и Q является результантом P ( x , 1) и Q ( x , 1), когда они рассматриваются как многочлены степени p и q (их степень по x может быть ниже их общей степени): (Заглавные буквы «Res» используются здесь для различения двух результантов, хотя стандартного правила для заглавных букв сокращения не существует). $${\displaystyle (A,B)\mapsto AP+BQ,}$$ $${\displaystyle \operatorname {Res} (P(x,y),Q(x,y))=\operatorname {res} _{p,q}(P(x,1),Q(x,1)).}$$

Однородный результант имеет по существу те же свойства, что и обычный результант, с двумя существенными отличиями: вместо корней полинома рассматриваются нули в проективной прямой , а степень полинома может не меняться при гомоморфизме колец . То есть:

• Результирующий результат двух однородных многочленов над областью целостности равен нулю тогда и только тогда, когда они имеют ненулевой общий ноль над алгебраически замкнутым полем, содержащим коэффициенты.
• Если P и Q — два двумерных однородных многочлена с коэффициентами в коммутативном кольце R и кольцевой гомоморфизм кольца R в другое коммутативное кольцо S , то, распространяясь на многочлены над R , имеем ${\displaystyle \varphi \colon R\to S}$ ${\displaystyle \varphi }$ $${\displaystyle \operatorname {Res} (\varphi (P),\varphi (Q))=\varphi (\operatorname {Res} (P,Q)).}$$
• Свойство однородного результанта быть равным нулю инвариантно относительно любой проективной замены переменных.

Любое свойство обычного результирующего может быть аналогичным образом распространено на однородный результирующий, и результирующее свойство будет либо очень похожим, либо более простым, чем соответствующее свойство обычного результирующего.

результирующая Маколея

Результант Маколея , названный в честь Фрэнсиса Сауэрби Маколея , также называемый многомерным результантом или многополиномиальным результантом , ^[3] является обобщением однородного результанта на n однородных многочленов от n неизвестных . Результант Маколея является многочленом от коэффициентов этих n однородных многочленов, который равен нулю тогда и только тогда, когда многочлены имеют общее ненулевое решение в алгебраически замкнутом поле, содержащем коэффициенты, или, что эквивалентно, если n гиперповерхностей, определяемых многочленами, имеют общий ноль в n –1- мерном проективном пространстве. Многомерный результант является, вместе с базисами Грёбнера , одним из основных инструментов эффективной теории исключения (теории исключения на компьютерах).

Подобно однородному результанту, Macaulay's может быть определен с помощью детерминантов и, таким образом, хорошо ведет себя при кольцевых гомоморфизмах . Однако его нельзя определить одним детерминантом. Из этого следует, что проще сначала определить его на общих многочленах .

Результант однородных многочленов общего вида

Однородный многочлен степени d от n переменных может иметь до коэффициентов; он называется общим , если эти коэффициенты являются различными неизвестными. $${\displaystyle {\binom {n+d-1}{n-1}}={\frac {(n+d-1)!}{(n-1)!\,d!}}}$$

Пусть будут n общих однородных многочленов от n неопределенных, соответствующих степеней Вместе они содержат неопределенные коэффициенты. Пусть C будет кольцом многочленов над целыми числами, от всех этих неопределенных коэффициентов. Многочлены принадлежат, таким образом, и их результирующий (еще не определенный) принадлежит C . ${\displaystyle P_{1},\ldots ,P_{n}}$ ${\displaystyle d_{1},\dots ,d_{n}.}$ $${\displaystyle \sum _{i=1}^{n}{\binom {n+d_{i}-1}{n-1}}}$$ ${\displaystyle P_{1},\ldots ,P_{n}}$ ${\displaystyle C[x_{1},\ldots ,x_{n}],}$

Степень Маколея — это целое число , которое является фундаментальным в теории Маколея. Для определения результирующего рассматривается матрица Маколея , которая является матрицей над мономиальным базисом C -линейного отображения , в котором каждый пробегает однородные многочлены степени , а область значений — это C -модуль однородных многочленов степени D. ${\displaystyle D=d_{1}+\cdots +d_{n}-n+1,}$ $${\displaystyle (Q_{1},\ldots ,Q_{n})\mapsto Q_{1}P_{1}+\cdots +Q_{n}P_{n},}$$ ${\displaystyle Q_{i}}$ ${\displaystyle D-d_{i},}$

Если n = 2 , матрица Маколея является матрицей Сильвестра и является квадратной матрицей , но это уже не так для n > 2. Таким образом, вместо рассмотрения определителя, рассматриваются все максимальные миноры , то есть определители квадратных подматриц, которые имеют столько же строк, сколько и матрица Маколея. Маколеем было доказано, что C -идеал, порожденный этими главными минорами, является главным идеалом , который порожден наибольшим общим делителем этих миноров. Поскольку мы работаем с многочленами с целыми коэффициентами, этот наибольший общий делитель определяется с точностью до знака. Общий результант Маколея является наибольшим общим делителем, который становится равным 1 , когда для каждого i ноль подставляется вместо всех коэффициентов, за исключением коэффициента, вместо которого подставляется единица. ${\displaystyle P_{i},}$ ${\displaystyle x_{i}^{d_{i}},}$

Свойства общего результата Маколея

• Общий результат Маколея представляет собой неприводимый многочлен .
• Он однороден по степени коэффициентов , где — граница Безу . ${\displaystyle B/d_{i}}$ ${\displaystyle P_{i},}$ ${\displaystyle B=d_{1}\cdots d_{n}}$
• Произведение с результирующим каждого одночлена степени D в принадлежит идеалу, порожденному ${\displaystyle x_{1},\dots ,x_{n}}$ ${\displaystyle C[x_{1},\dots ,x_{n}]}$ ${\displaystyle P_{1},\dots ,P_{n}.}$

Результант многочленов над полем

С этого момента мы считаем, что однородные многочлены степеней имеют свои коэффициенты в поле k , то есть они принадлежат Их результант определяется как элемент k, полученный заменой в общем результанте неопределенных коэффициентов фактическими коэффициентами ${\displaystyle P_{1},\ldots ,P_{n}}$ ${\displaystyle d_{1},\ldots ,d_{n}}$ ${\displaystyle k[x_{1},\dots ,x_{n}].}$ ${\displaystyle P_{i}.}$

Основное свойство результанта состоит в том, что он равен нулю тогда и только тогда, когда имеет ненулевой общий ноль в алгебраически замкнутом расширении k . ${\displaystyle P_{1},\ldots ,P_{n}}$

Часть этой теоремы «только если» следует из последнего свойства предыдущего абзаца и является эффективной версией Projective Nullstellensatz : если результат не равен нулю, то где — степень Маколея, а — максимальный однородный идеал. Это подразумевает, что не имеют других общих нулей, кроме единственного общего нуля (0, ..., 0) , $${\displaystyle \langle x_{1},\ldots ,x_{n}\rangle ^{D}\subseteq \langle P_{1},\ldots ,P_{n}\rangle ,}$$ ${\displaystyle D=d_{1}+\cdots +d_{n}-n+1}$ ${\displaystyle \langle x_{1},\ldots ,x_{n}\rangle }$ ${\displaystyle P_{1},\ldots ,P_{n}}$ ${\displaystyle x_{1},\ldots ,x_{n}.}$

Вычислимость

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

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

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

В случае входных полиномов с коэффициентами в поле точное значение результирующего значения редко важно, имеет значение только его равенство (или не равенство) нулю. Поскольку результирующий результат равен нулю тогда и только тогда, когда ранг матрицы Маколея меньше числа ее строк, это равенство нулю можно проверить, применив исключение Гаусса к матрице Маколея. Это обеспечивает вычислительную сложность , где d — максимальная степень входных полиномов. ${\displaystyle d^{O(n)},}$

Другой случай, когда вычисление результанта может предоставить полезную информацию, — это когда коэффициенты входных полиномов являются полиномами от небольшого числа неизвестных, часто называемых параметрами. В этом случае результант, если он не равен нулю, определяет гиперповерхность в пространстве параметров. Точка принадлежит этой гиперповерхности, если и только если существуют значения , которые вместе с координатами точки являются нулем входных полиномов. Другими словами, результант является результатом « исключения » из входных полиномов. ${\displaystyle x_{1},\ldots ,x_{n}}$ ${\displaystyle x_{1},\ldots ,x_{n}}$

У-результирующий

Результант Маколея обеспечивает метод, названный Маколеем « U -результант», для решения систем полиномиальных уравнений .

Для заданных n − 1 однородных многочленов степеней от n неизвестных над полем k их U -результант является результантом n многочленов , где — общая линейная форма , коэффициенты которой являются новыми неизвестными. Обозначение или для этих общих коэффициентов является традиционным и является источником термина U -результант. ${\displaystyle P_{1},\ldots ,P_{n-1},}$ ${\displaystyle d_{1},\ldots ,d_{n-1},}$ ${\displaystyle x_{1},\ldots ,x_{n},}$ ${\displaystyle P_{1},\ldots ,P_{n-1},P_{n},}$ $${\displaystyle P_{n}=u_{1}x_{1}+\cdots +u_{n}x_{n}}$$ ${\displaystyle u_{1},\ldots ,u_{n}.}$ ${\displaystyle u_{i}}$ ${\displaystyle U_{i}}$

U -результант является однородным многочленом от Он равен нулю тогда и только тогда, когда общие нули образуют проективное алгебраическое множество положительной размерности (то есть над алгебраически замкнутым расширением k имеется бесконечно много проективных нулей ). Если U -результант не равен нулю, его степень является границей Безу . U -результант факторизуется над алгебраически замкнутым расширением k в произведение линейных форм. Если — такой линейный множитель, то — однородные координаты общего нуля Более того, каждый общий нуль может быть получен из одного из этих линейных множителей, а кратность как множителя равна кратности пересечения в этом нуле. Другими словами, U -результант обеспечивает полностью явную версию теоремы Безу . ${\displaystyle k[u_{1},\ldots ,u_{n}].}$ ${\displaystyle P_{1},\ldots ,P_{n-1}}$ ${\displaystyle d_{1}\cdots d_{n-1}.}$ ${\displaystyle \alpha _{1}u_{1}+\ldots +\alpha _{n}u_{n}}$ ${\displaystyle \alpha _{1},\ldots ,\alpha _{n}}$ ${\displaystyle P_{1},\ldots ,P_{n-1}.}$ ${\displaystyle P_{i}}$

Расширение на большее количество полиномов и вычислений

U -результант , как определено Маколеем, требует, чтобы число однородных полиномов в системе уравнений было , где — число неопределенных. В 1981 году Дэниел Лазар расширил это понятие до случая, когда число полиномов может отличаться от , и результирующее вычисление может быть выполнено с помощью специализированной процедуры исключения Гаусса, за которой следует символическое вычисление детерминанта . ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle n-1}$

Пусть будут однородными многочленами в степеней над полем k . Без потери общности можно предположить, что Задавая для i > k границу Маколея ${\displaystyle P_{1},\ldots ,P_{k}}$ ${\displaystyle x_{1},\ldots ,x_{n},}$ ${\displaystyle d_{1},\ldots ,d_{k},}$ ${\displaystyle d_{1}\geq d_{2}\geq \cdots \geq d_{k}.}$ ${\displaystyle d_{i}=1}$ ${\displaystyle D=d_{1}+\cdots +d_{n}-n+1.}$

Пусть будут новыми неизвестными и определим В этом случае матрица Маколея определяется как матрица над базисом одночленов в линейного отображения , где для каждого i пробегает линейное пространство, состоящее из нуля и однородных многочленов степени . ${\displaystyle u_{1},\ldots ,u_{n}}$ ${\displaystyle P_{k+1}=u_{1}x_{1}+\cdots +u_{n}x_{n}.}$ ${\displaystyle x_{1},\ldots ,x_{n},}$ $${\displaystyle (Q_{1},\ldots ,Q_{k+1})\mapsto P_{1}Q_{1}+\cdots +P_{k+1}Q_{k+1},}$$ ${\displaystyle Q_{i}}$ ${\displaystyle D-d_{i}}$

Сокращая матрицу Маколея с помощью варианта исключения Гаусса , получаем квадратную матрицу линейных форм в Определителем этой матрицы является U -результант. Как и в случае с исходным U -результантом, он равен нулю тогда и только тогда, когда имеет бесконечно много общих проективных нулей (то есть, если проективное алгебраическое множество, определяемое как , имеет бесконечно много точек над алгебраическим замыканием k ). Опять же, как и в случае с исходным U -результантом, когда этот U -результант не равен нулю, он раскладывается на линейные множители над любым алгебраически замкнутым расширением k . Коэффициенты этих линейных множителей являются однородными координатами общих нулей , а кратность общего нуля равна кратности соответствующего линейного множителя. ${\displaystyle u_{1},\ldots ,u_{n}.}$ ${\displaystyle P_{1},\ldots ,P_{k}}$ ${\displaystyle P_{1},\ldots ,P_{k}}$ ${\displaystyle P_{1},\ldots ,P_{k},}$

Число строк матрицы Маколея меньше, чем где e ~ 2,7182 — обычная математическая константа , а d — среднее арифметическое степеней Отсюда следует, что все решения системы полиномиальных уравнений с конечным числом проективных нулей могут быть определены за время Хотя эта граница велика, она близка к оптимальной в следующем смысле: если все входные степени равны, то временная сложность процедуры полиномиальна относительно ожидаемого числа решений ( теорема Безу ). Это вычисление может быть практически жизнеспособным, когда n , k и d невелики. ${\displaystyle (ed)^{n},}$ ${\displaystyle P_{i}.}$ ${\displaystyle d^{O(n)}.}$

Смотрите также

• Теория исключения
• Подрезультат
• Нелинейная алгебра

Ссылки

1. Салмон, Джордж (1885) [1859], Вводные уроки в современную высшую алгебру (4-е изд.), Дублин, Ходжес, Фиггис и Ко, урок VIII, стр. 66, ISBN 978-0-8284-0150-0
2. Macaulay, FS (1902), «Некоторые формулы исключения», Proc. London Math. Soc. , 35 : 3–27, doi :10.1112/plms/s1-35.1.3
3. Кокс, Дэвид; Литтл, Джон; О'Ши, Донал (2005), Использование алгебраической геометрии , Springer Science+Business Media , ISBN 978-0387207339, Глава 3. Результирующие

• Гельфанд, ИМ; Капранов М.М.; Зелевинский, А. В. (1994), Дискриминанты, результанты и многомерные детерминанты , Бостон: Birkhäuser, ISBN. 978-0-8176-3660-9
• Маколей, Ф. С. (1916), Алгебраическая теория модульных систем, Корнеллская библиотека исторических математических монографий, Cambridge University Press, ISBN 978-1275570412

Внешние ссылки

• Вайсштейн, Эрик В. "Результант". MathWorld .