Евклидова область

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

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

Итак, если задана область целостности $R$ , часто бывает очень полезно знать, что $R$ имеет евклидову функцию: в частности, это подразумевает, что $R$ является ПИД. Однако, если нет «очевидной» евклидовой функции, то определение того, является ли $R$ ПИД, обычно является гораздо более простой задачей, чем определение того, является ли она евклидовой областью.

Евклидовы домены появляются в следующей цепочке включений классов :

rngs ⊃ кольца ⊃ коммутативные кольца ⊃ области целостности ⊃ целозамкнутые области ⊃ области НОД ⊃ области уникальной факторизации ⊃ области главных идеалов ⊃ евклидовы области ⊃ поля ⊃ алгебраически замкнутые поля

Определение

Пусть $R$ — область целостности. Евклидова функция на $R$ — это функция $f$ из $R \ {0}$ в неотрицательные целые числа, удовлетворяющая следующему фундаментальному свойству деления с остатком:

(EF1) Если $a$ и $b$ принадлежат $R$ и $b$ не равно нулю, то существуют $q$ и $r$ в $R$ такие, что $a = bq + r$ и либо $r = 0$ , либо $f (r) < f (b)$ .

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

В этом контексте $q$ и $r$ называются соответственно частным и остатком от деления (или евклидового деления ) числа $a$ на $b$ . В отличие от случая целых чисел и многочленов , частное, как правило, не определено однозначно, но когда частное выбрано, остаток определен однозначно.

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

(EF2) Для всех ненулевых $a$ и $b$ в $R$ , $f (a) \leq f (ab)$ .

Однако можно показать, что (EF1) достаточно для определения евклидовой области; если целостная область $R$ снабжена функцией $g$ , удовлетворяющей (EF1), то $R$ также может быть снабжена функцией, удовлетворяющей как (EF1), так и (EF2) одновременно. Действительно, для $a$ в $R \ {0}$ можно определить $f (a)$ следующим образом: ^[1]

f(a)=\min _{x\in R\setminus \{0\}}g(xa)

Говоря словами, можно определить $f (a)$ как минимальное значение, достигаемое $g$ на множестве всех ненулевых элементов главного идеала, порожденного $a$ .

Евклидова функция $f$ является мультипликативной , если $f (ab) = f (a) f (b)$ и $f (a)$ никогда не равно нулю. Отсюда следует, что $f (1) = 1$ . В более общем случае, $f (a) = 1$ тогда и только тогда, когда $a$ является единицей .

Примечания к определению

Многие авторы используют другие термины вместо «евклидовой функции», такие как «функция степени», «функция оценки», «калибровочная функция» или «функция нормы». ^[2] Некоторые авторы также требуют, чтобы областью определения евклидовой функции было все кольцо $R$ ; ^[2] однако, это не существенно влияет на определение, поскольку (EF1) не включает значение $f (0)$ . Определение иногда обобщают, позволяя евклидовой функции принимать свои значения в любом хорошо упорядоченном множестве ; это ослабление не влияет на наиболее важные следствия свойства евклидовости.

Свойство (EF1) можно переформулировать следующим образом: для любого главного идеала $I$ кольца $R$ с ненулевым генератором $b$ все ненулевые классы фактор-кольца $R / I$ имеют представителя $r$ с $f (r) < f (b)$ . Поскольку возможные значения $f$ вполне упорядочены, это свойство можно установить, показав, что $f (r) < f (b)$ для любого $r \notin I$ с минимальным значением $f (r)$ в его классе. Обратите внимание, что для евклидовой функции, которая установлена таким образом, не обязательно должен существовать эффективный метод определения $q$ и $r$ в (EF1).

Примеры

Примеры евклидовых доменов включают в себя:

Любое поле. Определим $f (x) = 1$ для всех ненулевых $x$ .
$Z$ $,$ кольцо целых чисел. Определим $f (n) = | n |$ , абсолютное значение n.^[3]
$Z [i]$ , кольцо целых гауссовых чисел . Определим $f (a + bi) = a 2 + b 2$ , норму целого гауссового числа $a + bi$ .
$Z [ω]$ (где $ω$ — примитивный ( недействительный ) кубический корень из единицы ), кольцо целых чисел Эйзенштейна . Определим $f (a + b ω) = a 2 - ab + b 2$ , норму целого числа Эйзенштейна $a + b ω$ .
$K [X]$ , кольцо многочленов над полем $K.$ Для каждого ненулевого многочлена $P$ $определим$ f $(P) как$ степень P .[^4]
$K [[X]]$ , кольцо формальных степенных рядов над полем $K$ . Для каждого ненулевого степенного ряда $P$ определим $f (P)$ как порядок P $,$ то есть степень наименьшей степени $X,$ встречающейся в $P$ . В частности, для двух ненулевых степенных рядов $P$ и $Q$ $f (P$ ) $\leq$ $f$ $($ $Q$ $)$ тогда и только тогда, когда $P$ делит $Q$ .
Любое дискретное кольцо оценки . Определим $f (x)$ как наивысшую степень максимального идеала $M,$ содержащего $x$ . Эквивалентно, пусть $g$ будет генератором $M$ , а $v$ будет единственным целым числом, таким что $g v$ является ассоциированным с $x$ , тогда определим $f (x) = v$ . Предыдущий пример $K [[X]]$ является частным случаем этого.
Область Дедекинда с конечным числом ненулевых простых идеалов $P 1, ..., P n$ . Определим , где $v$ $i$ — дискретное оценивание, соответствующее идеалу $P$ $i$ . ^[5] $f(x)=\sum _{i=1}^{n}v_{i}(x)$

Примеры доменов, которые не являются евклидовыми доменами, включают в себя:

Любая область, которая не является областью главных идеалов , например, кольцо многочленов по крайней мере от двух неизвестных над полем, или кольцо одномерных многочленов с целыми коэффициентами , или числовое кольцо $Z [\sqrt -5]$ .
Кольцо целых чисел Q $(\sqrt -19) ,$ состоящее из чисел $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠а + б √ −19/2⁠$ где $a$ и $b$ — целые числа и оба четные или оба нечетные. Это главная идеальная область, которая не является евклидовой. Это было доказано Теодором Моцкиным и было первым известным случаем.^[6]
Кольцо $A = R [X, Y]/(X 2 + Y 2 + 1)$ также является областью главных идеалов ^[7] , которая не является евклидовой. Чтобы увидеть, что это не евклидова область, достаточно показать, что для любого ненулевого простого числа отображение, индуцированное отображением фактора, не является сюръективным . ^[8] $p\in A$ $A^{\times }\to (A/p)^{\times }$ $A\to A/p$

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

Пусть R — область, а f — евклидова функция на R. Тогда:

R — область главных идеалов (PID). Фактически, если I — ненулевой идеал R , то любой элемент a из I \ {0} с минимальным значением (на этом множестве) f ( a ) является генератором I . ^[9] Как следствие, R также является уникальной областью факторизации и нётеровым кольцом . Что касается общих областей главных идеалов, существование факторизаций (т. е. то, что R является атомной областью ) особенно легко доказать в евклидовых областях: выбрав евклидову функцию f , удовлетворяющую (EF2), x не может иметь никакого разложения на более чем f ( x ) неединичных множителей, поэтому, начиная с x и многократно разлагая приводимые множители, мы обязательно получим факторизацию на неприводимые элементы .
Любой элемент R, в котором f принимает свое глобально минимальное значение, обратим в R. Если выбран f, удовлетворяющий (EF2), то обратное также верно, и f принимает свое минимальное значение точно в обратимых элементах R.
Если евклидово деление алгоритмично, то есть если существует алгоритм вычисления частного и остатка, то расширенный евклидов алгоритм может быть определен точно так же, как в случае целых чисел. ^[10]
Если евклидова область не является полем, то она имеет элемент a со следующим свойством: любой элемент x, не делящийся на a, можно записать как x = ay + u для некоторой единицы u и некоторого элемента y . Это следует из того, что a принимается за неединицу с f ( a ) как можно меньшим. Это странное свойство можно использовать, чтобы показать, что некоторые главные идеальные области не являются евклидовыми областями, поскольку не все PID обладают этим свойством. Например, для d = −19, −43, −67, −163 кольцо целых чисел является PID, который не является евклидовым, но случаи d = −1, −2, −3, −7, −11 являются евклидовыми. ^[11] $\mathbf {Q} ({\sqrt {d}}\,)$

Однако во многих конечных расширениях Q с тривиальной группой классов кольцо целых чисел является евклидовым (не обязательно относительно абсолютного значения нормы поля; см. ниже). Предполагая расширенную гипотезу Римана , если K является конечным расширением Q , а кольцо целых чисел K является PID с бесконечным числом единиц, то кольцо целых чисел является евклидовым. ^{[12] В частности, это}применимо к случаю полностью вещественных квадратичных числовых полей с тривиальной группой классов. Кроме того (и без предположения ERH), если поле K является расширением Галуа поля Q , имеет тривиальную группу классов и единичный ранг строго больше трех, то кольцо целых чисел является евклидовым. ^[13] Непосредственным следствием этого является то, что если числовое поле является полем Галуа над Q , его группа классов тривиальна, а расширение имеет степень больше 8, то кольцо целых чисел обязательно является евклидовым.

Норма-евклидовы поля

Алгебраические числовые поля K поставляются с канонической нормой функции на них: абсолютное значение нормы поля N , которая переводит алгебраический элемент α в произведение всех сопряженных с α . Эта норма отображает кольцо целых чисел числового поля K , скажем, O _K , в неотрицательные рациональные целые числа , поэтому она является кандидатом на то, чтобы быть евклидовой нормой на этом кольце. Если эта норма удовлетворяет аксиомам евклидовой функции, то числовое поле K называется нормо-евклидовым или просто евклидовым . ^[14]^[15] Строго говоря, именно кольцо целых чисел является евклидовым, поскольку поля являются тривиально евклидовыми областями, но терминология стандартна.

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

Те, которые не являются главными и, следовательно, не являются евклидовыми, например, целые числа $\mathbf {Q} ({\sqrt {-5}}\,)$
Те, которые являются главными и неевклидовыми, такие как целые числа $\mathbf {Q} ({\sqrt {-19}}\,)$
Те, которые являются евклидовыми, но не нормированными, например, целые числа ^[16] $\mathbf {Q} ({\sqrt {69}}\,)$
Те, которые являются нормированными по евклидовой норме, такие как гауссовы целые числа (целые числа ) $\mathbf {Q} ({\sqrt {-1}}\,)$

Норма-евклидовы квадратичные поля были полностью классифицированы; они находятся там, где принимает значения $\mathbf {Q} ({\sqrt {d}}\,)$ $d$

−11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73 (последовательность A048981 в OEIS ). ^[17]

Каждое евклидово мнимое квадратичное поле является нормированным евклидовым и является одним из пяти первых полей в предыдущем списке.

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

Оценка (алгебра)

Примечания

↑ Роджерс, Кеннет (1971), «Аксиомы для евклидовых областей», American Mathematical Monthly , 78 (10): 1127–8, doi :10.2307/2316324, JSTOR 2316324, Zbl 0227.13007
^ ab Даммит, Дэвид С.; Фут, Ричард М. (2004). Абстрактная алгебра . Wiley. стр. 270. ISBN 9780471433347.
^ Фрэли и Кац 1967, с. 377, Пример 1
^ Фрэли и Кац 1967, с. 377, Пример 2
↑ Сэмюэль, Пьер (1 октября 1971 г.). «О евклидовых кольцах». Журнал алгебры . 19 (2): 282–301 (стр. 285). doi : 10.1016/0021-8693(71)90110-4 . ISSN 0021-8693.
^ Motzkin, Th (декабрь 1949). «Алгоритм Евклида». Бюллетень Американского математического общества . 55 (12): 1142–1146. ISSN 0002-9904.
^ Пьер, Сэмюэл (1964). Лекции по уникальным факторизационным областям (PDF) . Институт фундаментальных исследований Тата. С. 27–28.
^ «Частное многочленов, PID, но не евклидова область?».
^ Фрели и Кац 1967, с. 377, Теорема 7.4.
^ Фрэли и Кац 1967, с. 380, Теорема 7.7.
^ Моцкин, Теодор (1949), «Алгоритм Евклида», Бюллетень Американского математического общества , 55 (12): 1142–6, doi : 10.1090/S0002-9904-1949-09344-8 , Zbl 0035.30302
^ Вайнбергер, Питер Дж. (1973), «О евклидовых кольцах целых алгебраических чисел», Труды симпозиумов по чистой математике , 24 , AMS: 321–332, doi :10.1090/pspum/024/0337902, ISBN 9780821814246
^ Харпер, Малкольм; Мёрти, М. Рам (2004), «Евклидовы кольца алгебраических целых чисел» (PDF) , Канадский журнал математики , 56 (1): 71–76, CiteSeerX 10.1.1.163.7917 , doi :10.4153/CJM-2004-004-5
^ Рибенбойм, Пауло (1972). Алгебраические числа . Wiley-Interscience. ISBN 978-0-471-71804-8.
^ Харди, GH; Райт, EM; Сильверман, Джозеф; Уайлс, Эндрю (2008). Введение в теорию чисел (6-е изд.). Oxford University Press. ISBN 978-0-19-921986-5.
^ Кларк, Дэвид А. (1994). «Квадратичное поле, которое является евклидовым, но не нормированным». Manuscripta Mathematica . 83 (3–4): 327–330. CiteSeerX 10.1.1.360.6129 . doi :10.1007/BF02567617. Zbl 0817.11047.
^ LeVeque, William J. (2002) [1956]. Темы теории чисел. Том I и II. Довер. С. II:57, 81. ISBN 978-0-486-42539-9. Збл 1009.11001.

Ссылки

Фрели, Джон Б.; Кац, Виктор Дж. (1967). Первый курс абстрактной алгебры (5-е изд.). Аддисон-Уэсли. ISBN 0-201-53467-3.
Сэмюэль, Пьер (1971). "О евклидовых кольцах" (PDF) . Журнал алгебры . 19 (2): 282–301. doi : 10.1016/0021-8693(71)90110-4 . Архивировано из оригинала (PDF) 2021-05-06 . Получено 2021-04-24 .