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

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

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

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

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

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]

{\ displaystyle 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 $.$ ^[3]
$Z [i]$ — кольцо гауссовских целых чисел . Определим $f (a + bi) = a2 + b2,$ нормугауссовацелого числа $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$ . Определим , где $vi$ $—$ дискретная оценка $,$ соответствующая идеалу $Pi$ . ^[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,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);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 , скажем _OK , в неотрицательные рациональные целые числа , поэтому она является кандидатом на роль евклидовой нормы на этом кольце. Если эта норма удовлетворяет аксиомам евклидовой функции, то числовое поле К называется нормо-евклидовым или просто евклидовым . ^[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 в ОЭИС ) . ^[17]

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

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

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

Примечания

^ Роджерс, Кеннет (1971), «Аксиомы евклидовых областей», American Mathematical Monthly , 78 (10): 1127–8, doi : 10.2307/2316324, JSTOR 2316324, Zbl 0227.13007
^ аб Даммит, Дэвид С.; Фут, Ричард М. (2004). Абстрактная алгебра . Уайли. п. 270. ИСБН 9780471433347.
^ Фрэли и Кац 1967, с. 377, Пример 1
^ Фрэли и Кац 1967, с. 377, Пример 2
^ Самуэль, Пьер (1 октября 1971 г.). «О евклидовых кольцах». Журнал алгебры . 19 (2): 282–301 (с. 285). дои : 10.1016/0021-8693(71)90110-4 . ISSN 0021-8693.
^ Моцкин, Т. (декабрь 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), «О евклидовых кольцах алгебраических целых чисел», Труды симпозиумов по чистой математике , AMS, 24 : 321–332, doi : 10.1090/pspum/024/0337902, ISBN 9780821814246
^ Харпер, Малькольм; Мурти, М. Рам (2004), «Евклидовы кольца целых алгебраических чисел» (PDF) , Canadian Journal of Mathematics , 56 (1): 71–76, CiteSeerX 10.1.1.163.7917 , doi : 10.4153/CJM-2004-004 -5
^ Рибенбойм, Пауло (1972). Алгебраические числа . Уайли-Интерсайенс. ISBN 978-0-471-71804-8.
^ Харди, GH; Райт, Э.М.; Сильверман, Джозеф; Уайлс, Эндрю (2008). Введение в теорию чисел (6-е изд.). Издательство Оксфордского университета. ISBN 978-0-19-921986-5.
^ Кларк, Дэвид А. (1994). «Квадратичное поле, которое является евклидовым, но не нормо-евклидовым». Манускрипта Математика . 83 (3–4): 327–330. CiteSeerX 10.1.1.360.6129 . дои : 10.1007/BF02567617. Збл 0817.11047.
^ Левек, Уильям Дж. (2002) [1956]. Темы теории чисел. Том. Я и II. Дувр. стр. II: 57, 81. ISBN. 978-0-486-42539-9. Збл 1009.11001.