Лемма Гаусса (полиномы)

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

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

Следствием , является то , леммы Гаусса, иногда также называемой леммой Гаусса что примитивный многочлен неприводим по целым числам тогда и только тогда, когда он неприводим по рациональным числам . В более общем смысле, примитивный полином имеет одинаковую полную факторизацию как по целым, так и по рациональным числам. В случае коэффициентов в уникальной области факторизации $R$ «рациональные числа» должны быть заменены « полем дробей R $»$ . Это означает, что если $R$ является либо полем , либо кольцом целых чисел, либо уникальной областью факторизации, то каждое кольцо многочленов (от одного или нескольких неопределённых) над $R$ является уникальной областью факторизации. Другим следствием является то, что факторизация и вычисление наибольшего общего делителя многочленов с целыми числами или рациональными коэффициентами могут быть сведены к аналогичным вычислениям с целыми числами и примитивными многочленами. Это систематически используется (явно или неявно) во всех реализованных алгоритмах (см. «Наибольший общий делитель полинома» и «Факторизация многочленов»). ).

Лемма Гаусса и все ее следствия, не предполагающие существования полной факторизации, остаются верными для любой области НОД ( области целостности , в которой существуют наибольшие общие делители). В частности, кольцо многочленов над областью НОД также является областью НОД. Если назвать примитивным многочлен, коэффициенты которого порождают единичный идеал , лемма Гаусса верна над каждым коммутативным кольцом . ^{[ 2 ]} необходимо соблюдать некоторую осторожность Однако при использовании этого определения примитива , поскольку в уникальной области факторизации, которая не является областью главного идеала , существуют полиномы, которые являются примитивными в указанном выше смысле и не примитивными в этом новом смысле.

Лемма о целых числах

Если $F(X)=a_{0}+a_{1}X+\dots +a_{n}X^{n}$ является многочленом с целыми коэффициентами, то $F$ называется примитивным, если наибольший общий делитель всех коэффициентов $a_{0},a_{1},\dots ,a_{n}$ равен 1; другими словами, ни одно простое число не делит все коэффициенты.

Лемма Гаусса (примитивность) — Если P ( X ) и Q ( X ) являются примитивными полиномами над целыми числами, их произведение P ( X ) Q ( X ) также является примитивным.

Доказательство: Очевидно, что произведение f ( x ) g ( x ) двух примитивных многочленов имеет целые коэффициенты. Следовательно, если оно не является примитивным, должно существовать простое число p , которое является общим делителем всех его коэффициентов. Но p не может делить все коэффициенты ни f ( x ), ни g ( x ) (иначе они не были бы примитивными). Пусть а _р х ^р будет первым членом f ( x ), не делящимся на p , и пусть b _s x ^с быть первым членом g ( x ), не делящимся на p . Теперь рассмотрим термин x ^{р + с} в произведении, коэффициент которого равен

\cdots +a_{r+2}b_{s-2}+a_{r+1}b_{s-1}+a_{r}b_{s}+a_{r-1}b_{s+1}+a_{r-2}b_{s+2}+\cdots .

Член a _r b _s не делится на p (поскольку p является простым), но все остальные делятся, поэтому вся сумма не может делиться на p . По предположению, все коэффициенты произведения делятся на p , что приводит к противоречию. Следовательно, коэффициенты произведения не могут иметь общего делителя и, следовательно, являются примитивными. $\square$

Лемма Гаусса (несводимость). Непостоянный многочлен в Z [ X ] неприводим в Z [ X ] тогда и только тогда, когда он одновременно неприводим в Q [ X ] и примитивен в Z [ X ].

Ниже приводится доказательство для более общего случая. Обратите внимание, что неприводимый элемент Z Z (простое число) по-прежнему остается неприводимым, если рассматривать его как постоянный многочлен от [ X ] ; это объясняет необходимость использования слова «непостоянное» в заявлении.

Заявления для уникальных областей факторизации

Лемма Гаусса в более общем смысле справедлива для произвольных уникальных областей факторизации . Там содержимое $c (P)$ полинома $P$ можно определить как наибольший общий делитель коэффициентов $P$ (как и в НОД, содержимое на самом деле представляет собой набор ассоциированных элементов ). Полином $P$ с коэффициентами в UFD $R$ тогда называется примитивным , если единственные элементы $R$ которые делят все коэффициенты $P$ сразу, являются обратимыми элементами R $,$ ; т. е. НОД коэффициентов равен единице.

Утверждение о примитивности: если $R$ является UFD, то набор примитивных полиномов в $R [X]$ замкнут при умножении. В более общем смысле, содержание продукта $fg$ многочленов является произведением $c(f)c(g)$ их индивидуального содержания.

Утверждение о неприводимости: пусть $R$ — уникальная область факторизации, а $F$ — поле частных . Непостоянный полином $f$ в $R[x]$ является неприводимым в $R[x]$ тогда и только тогда, когда оно одновременно неприводимо в $F[x]$ и примитивен в $R[x]$ .

(Доказательства см. в разделе #Общая версия ниже.)

Позволять $R$ быть уникальной областью факторизации с полем дробей $F$ . Если $f\in F[x]$ является многочленом над $F$ тогда для некоторых $d$ в $R$ , $df$ имеет коэффициенты в $R$ , и так – вынесение НОД $q$ коэффициентов – можем написать $df=qf'$ для некоторого примитивного многочлена $f'\in R[x]$ . Как можно проверить, этот полином $f'$ уникален с точностью до умножения на единицу и называется примитивной частью (или примитивным представителем ) $f$ и обозначается $\operatorname {pp} (f)$ . Процедура совместима с продуктом: $\operatorname {pp} (fg)=\operatorname {pp} (f)\operatorname {pp} (g)$ .

Эту конструкцию можно использовать для отображения оператора:

Кольцо многочленов над УФД является УФД.

Действительно, по индукции достаточно показать $R[x]$ является УФО, когда $R$ это УФО. Позволять $f\in R[x]$ быть ненулевым полиномом. Сейчас, $F[x]$ является уникальной областью факторизации (поскольку это область главных идеалов) и, следовательно, как многочлен от $F[x]$ , $f$ можно факторизовать как:

f=g_{1}g_{2}\dots g_{r}

где $g_{i}$ являются неприводимыми полиномами $F[x]$ . Теперь мы пишем $f=cf'$ для НОД $c$ коэффициентов $f$ (и $f'$ это примитивная часть), а затем:

f=cf'=c\operatorname {pp} (g_{1})\operatorname {pp} (g_{2})\cdots \operatorname {pp} (g_{r}).

Сейчас, $c$ является произведением простых элементов $R$ (с $R$ является UFD) и простым элементом $R$ является основным элементом $R[x]$ , как $R[x]/(p)\cong R/(p)[x]$ является целостной областью. Следовательно, $c$ допускает простую факторизацию (или уникальную факторизацию на неприводимые). Далее обратите внимание, что $f'=\operatorname {pp} (g_{1})\cdots \operatorname {pp} (g_{r})$ представляет собой уникальную факторизацию на неприводимые элементы $R[x]$ , как (1) каждый $\operatorname {pp} (g_{i})$ неприводим по утверждению о неприводимости и (2) он уникален, поскольку факторизация $f'$ также можно рассматривать как факторизацию в $F[x]$ и факторизация там уникальна. С $c$ и $f'$ однозначно определяются $f$ с точностью до единичных элементов, приведенная выше факторизация $f$ представляет собой уникальную факторизацию на неприводимые элементы. $\square$

Условие, что « R — единственная область факторизации», не является лишним, поскольку из него следует, что каждый неприводимый элемент этого кольца также является простым элементом , что, в свою очередь, означает, что каждый ненулевой элемент R имеет не более одной факторизации в произведение. неприводимых элементов и единицы с точностью до порядка и ассоциированного отношения. В кольце, где факторизация не уникальна, скажем, $pa = qb$ с p и q неприводимыми элементами, которые не делят ни один из сомножителей на другой стороне, произведение $(p + qX)(a + qX) = pa + (p + а) qX + q 2 Х 2 знак равно q (б + (п + а) X + qX 2)$ показывает несостоятельность утверждения о примитивности. В качестве конкретного примера можно взять $R = Z [i \sqrt5]$ , $p = 1 + i \sqrt5$ , $a = 1 - i \sqrt5$ , $q = 2$ , $b = 3$ . В этом примере полином $3 + 2 X + 2 X 2$ (полученный путем деления правой части на $q = 2$ ) представляет собой пример несостоятельности утверждения о неприводимости (оно неприводимо над R , но приводимо над своим полем частных $Q [i \sqrt5]$ ). Другой известный пример — полином $X 2 - X - 1$ , корнями которого являются золотое сечение $φ = (1 + \sqrt5)/2$ и сопряженное с ним $(1 - \sqrt5)/2,$ показывающее, что оно приводимо над полем $Q [\sqrt5]$ , хотя и неприводимо. над не-УФД $Z [\sqrt5],$ имеющим $Q [\sqrt5]$ как поле частных. В последнем примере кольцо можно превратить в UFD, взяв его целое замыкание $Z [φ]$ в $Q [\sqrt5]$ (кольцо целых чисел Дирихле), над которым $X 2 - X - 1$ становится приводимым, но в первом примере R уже целозамкнут.

Общая версия

Позволять $R$ быть коммутативным кольцом. Если $f$ является полиномом по $R[x_{1},\dots ,x_{n}]$ , тогда пишем $\operatorname {cont} (f)$ ради идеала $R$ порожденный всеми коэффициентами $f$ ; это называется содержанием $f$ . Обратите внимание, что $\operatorname {cont} (af)=a\operatorname {cont} (f)$ для каждого $a$ в $R$ . Следующее предложение утверждает более существенное свойство.

Предложение ^{[ 3 ]} — Для каждой пары полиномов $f,g$ в $R[x_{1},\dots ,x_{n}]$ ,

\operatorname {cont} (fg)\subset \operatorname {cont} (f)\operatorname {cont} (g)\subset {\sqrt {\operatorname {cont} (fg)}}

где ${\sqrt {\cdot }}$ обозначает радикал идеала . Более того, если $R$ является областью НОД (например, уникальной областью факторизации), тогда

\operatorname {gcd} (\operatorname {cont} (fg))=\operatorname {gcd} (\operatorname {cont} (f))\operatorname {gcd} (\operatorname {cont} (g))

где $\operatorname {gcd} (I)$ обозначает единственный минимальный главный идеал, содержащий конечно порожденный идеал $I$ . ^{[ примечание 3 ]}

Полином $f$ называется примитивным, если $\operatorname {cont} (f)$ идеальная ли единица $(1)$ . ^{[ 4 ]} Когда $R=\mathbb {Z}$ (или, в более общем плане, когда $R$ является областью Безу ), это согласуется с обычным определением примитивного многочлена. (Но если $R$ является всего лишь UFD, это определение несовместимо с определением примитивности в #Statements для уникальных областей факторизации .)

Следствие ^{[ 2 ]} — Два многочлена $f,g$ примитивны тогда и только тогда, когда произведение $fg$ является примитивным.

Доказательство. Это легко сделать, используя тот факт, что ^{[ 5 ]} что ${\sqrt {I}}=(1)$ подразумевает $I=(1).$ $\square$

Следствие ^{[ 6 ]} - Предполагать $R$ — это область НОД (например, уникальная область факторизации) с полем дробей $F$ . Тогда непостоянный полином $f$ в $R[x]$ неприводимо тогда и только тогда, когда оно неприводимо в $F[x]$ и НОД коэффициентов $f$ это 1.

Доказательство: ( $\Rightarrow$ ) Прежде всего заметим, что НОД коэффициентов $f$ равно 1, так как в противном случае мы можем вынести за скобки некоторый элемент $c\in R$ из коэффициентов $f$ писать $f=cf'$ , что противоречит неприводимости $f$ . Далее, предположим $f=gh$ для некоторых непостоянных полиномов $g,h$ в $F[x]$ . Затем для некоторых $d\in R$ , полином $dg$ имеет коэффициенты в $R$ и так, исключив НОД $q$ коэффициентов запишем $dg=qg'$ . Сделайте то же самое для $h$ и мы можем написать $f=cg'h'$ для некоторых $c\in F$ . Теперь позвольте $c=a/b$ для некоторых $a,b\in R$ . Затем $bf=ag'h'$ . Отсюда, используя предложение, получаем:

(b)\supset \operatorname {gcd} (\operatorname {cont} (bf))=(a)

.

То есть, $b$ делит $a$ . Таким образом, $c\in R$ а затем факторизация $f=cg'h'$ представляет собой противоречие с неприводимостью $f$ .

( $\Leftarrow$ ) Если $f$ является неприводимым над $F$ , то либо оно неприводимо над $R$ или он содержит постоянный многочлен в качестве множителя, вторая возможность исключается предположением. $\square$

Доказательство предложения: Очевидно, $\operatorname {cont} (fg)\subset \operatorname {cont} (f)\operatorname {cont} (g)$ . Если ${\mathfrak {p}}$ является простым идеалом, содержащим $\operatorname {cont} (fg)$ , затем $fg\equiv 0$ модуль ${\mathfrak {p}}$ . С $R/{\mathfrak {p}}[x_{1},\dots ,x_{n}]$ является кольцом полиномов над областью целостности и, следовательно, является областью целостности, это означает либо $f\equiv 0$ или $g\equiv 0$ модуль ${\mathfrak {p}}$ . Следовательно, либо $\operatorname {cont} (f)$ или $\operatorname {cont} (g)$ содержится в ${\mathfrak {p}}$ . С ${\sqrt {\operatorname {cont} (fg)}}$ является пересечением всех простых идеалов, содержащих $\operatorname {cont} (fg)$ и выбор ${\mathfrak {p}}$ был произвольным, $\operatorname {cont} (f)\operatorname {cont} (g)\subset {\sqrt {\operatorname {cont} (fg)}}$ .

Теперь мы докажем «более того». Вынеся НОД из коэффициентов, мы можем написать $f=af'$ и $g=bg'$ где НОД коэффициентов $f',g'$ оба равны 1. Очевидно, достаточно доказать утверждение, когда $f,g$ заменяются на $f',g'$ ; таким образом, мы предполагаем НОД коэффициентов $f,g$ оба равны 1. Остальная часть доказательства проста и прозрачна, если $R$ — уникальная область факторизации; таким образом, мы даем доказательство в этом случае здесь (и см. ^{[ примечание 4 ]} для доказательства для случая НОД). Если $\gcd(\operatorname {cont} (fg))=(1)$ , то и доказывать нечего. Итак, предположим иначе; то существует неединичный элемент, делящий коэффициенты $fg$ . Разложив этот элемент на произведение простых элементов, мы можем считать этот элемент простым элементом. $\pi$ . Теперь у нас есть:

(\pi )={\sqrt {(\pi )}}\supset {\sqrt {\operatorname {cont} (fg)}}\supset \operatorname {cont} (f)\operatorname {cont} (g)

.

Таким образом, либо $(\pi )$ содержит $\operatorname {cont} (f)$ или $\operatorname {cont} (g)$ ; противоречащие НОД коэффициентов $f,g$ оба 1. $\square$

Примечание . В области НОД (например, уникальной области факторизации) НОД всех коэффициентов полинома $f$ , уникальный с точностью до единичных элементов, также называется содержимым $f$ .

Приложения

Из леммы Гаусса следует, что для каждой уникальной области факторизации $R$ , кольцо полиномов $R[X_{1},X_{2},...,X_{n}]$ также является уникальным доменом факторизации ( об уникальных доменах факторизации см. #Statements ). Лемму Гаусса можно также использовать для доказательства критерия неприводимости Эйзенштейна . Наконец, его можно использовать, чтобы показать, что круговые многочлены (унитарные единицы с целыми коэффициентами) неприводимы.

Из леммы Гаусса следует следующее утверждение:

Если $f(x)$ представляет собой монический полином от одной переменной с коэффициентами в уникальной области факторизации. $R$ (или, в более общем смысле, домен GCD), затем корень $f$ это в области дробей $F$ из $R$ находится в $R$ . ^{[ примечание 5 ]}

Если $R=\mathbb {Z}$ , тогда говорится, что рациональный корень монического многочлена над целыми числами является целым числом (см. теорему о рациональном корне ). Чтобы увидеть утверждение, позвольте $a/b$ быть корнем $f$ в $F$ и предположим $a,b$ являются относительно простыми . В $F[x]$ мы можем написать $f=(x-a/b)g$ с $cg\in R[x]$ для некоторых $c\in R$ . Затем

cbf=(bx-a)cg

является факторизацией в $R[x]$ . Но $bx-a$ примитивен (в смысле УФД) и, следовательно, $cb$ делит коэффициенты $cg$ по лемме Гаусса, и так

f=(bx-a)h

с $h$ в $R[x]$ . С $f$ моник, это возможно только тогда, когда $b$ является единицей.

Аналогичный аргумент показывает:

Позволять $R$ быть НОД областью с полем дробей $F$ и $f\in R[x]$ . Если $f=gh$ для некоторого полинома $g\in R[x]$ что примитивно в смысле УФО и $h\in F[x]$ , затем $h\in R[x]$ .

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

Примечания

^ Эта теорема по историческим причинам называется леммой .
^ Здесь используется неопределенный артикль, поскольку, когда коэффициенты принадлежат уникальной области факторизации , «наибольший» относится к предварительному порядку делимости, а не к естественному порядку целых чисел, и, как правило, существует несколько наибольших общих делителей.
^ Генератор главного идеала - это НОД некоторых генераторов I (и он существует, потому что $R$ является доменом НОД).
^
Доказательство для случая НОД : Доказательство здесь взято из Минс, Р.; Ричман, Ф.; Рюйтенбург, В. (1988). Курс конструктивной алгебры . Университетxt. Спрингер-Верлаг. ISBN 0-387-96640-4 . Нам понадобится следующая простая лемма о НОД:
- Если $\gcd(a,b)=\gcd(a,c)=1$ , затем $\gcd(a,bc)=1$ .
(Доказательство леммы нетривиально, оно проводится с помощью элементарной алгебры.) Мы рассуждаем индукцией по сумме чисел членов в $f,g$ $е,г$ ; то есть мы предполагаем, что предложение установлено для любой пары многочленов с общим числом членов на один меньше. Позволять $(c)=\gcd(\operatorname {cont} (fg))$ $(c)=\gcd(\operatorname {cont} (fg))$ ; то есть $c$ $с$ - НОД коэффициентов $fg$ $fg$ . Предполагать $(c)\neq (1)$ ${\ displaystyle (c) \ neq (1)}$ ; в противном случае мы закончили. Позволять $f_{0},g_{0}$ $f_{0},g_{0}$ обозначают члены высшей степени $f,g$ $е,г$ с точки зрения лексикографического мономиального порядка . Затем $f_{0}g_{0}$ $f_{0}g_{0}$ именно является ведущим термином $fg$ $fg$ и так $c$ $с$ делит (уникальный) коэффициент $f_{0}g_{0}$ $f_{0}g_{0}$ (поскольку он делит все коэффициенты $fg$ $fg$ ). Теперь, если $c$ $с$ не имеет общего множителя с (единственным) коэффициентом $f_{0}$ $f_{0}$ и не имеет общего делителя с множителем $g_{0}$ $g_{0}$ , тогда по предыдущей лемме $\gcd(c,\operatorname {cont} (f_{0}g_{0}))=(1)$ $\gcd(c,\operatorname {cont} (f_{0}g_{0}))=(1)$ . Но $c$ $с$ делит коэффициент $f_{0}g_{0}$ $f_{0}g_{0}$ ; так это противоречие. Таким образом, либо $c$ $с$ имеет общий множитель с коэффициентом $f_{0}$ $f_{0}$ или делает с этим из $g_{0}$ $g_{0}$ ; скажем, первое. Позволять $(d)=\operatorname {gcd} (c,\operatorname {cont} (f_{0}))$ $(d)=\operatorname {gcd} (c, \operatorname {cont} (f_{0}))$ . С $d$ $d$ делит коэффициенты $fg-f_{0}g=(f-f_{0})g$ $fg-f_{0}g = (ff_{0})g$ , по индуктивному предположению,
$(d)\supset \operatorname {gcd} (\operatorname {cont} ((f-f_{0})g))=\operatorname {gcd} (\operatorname {cont} (f-f_{0}))\operatorname {gcd} (\operatorname {cont} (g))=\operatorname {gcd} (\operatorname {cont} (f-f_{0}))$ .
С $(d)$ ${\ displaystyle (d)}$ содержит $\operatorname {cont} (f_{0})$ $\operatorname {cont} (f_{0})$ , он содержит $\operatorname {cont} (f)$ $\operatorname {продолжение} (е)$ ; то есть $(d)=(1)$ ${\ displaystyle (d) = (1)}$ , противоречие. $\square$ $\square$
^ Другими словами, это говорит о том, что уникальная область факторизации целозамкнута .