Лемма Гензеля - Hensel's lemma

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

Переходя к "пределу" (на самом деле это обратный предел ), когда степень p стремится к бесконечности, следует, что корень или факторизация по модулю p могут быть подняты до корня или факторизации по p -адическим целым числам .

Эти результаты были широко обобщены под тем же названием на случай многочленов над произвольным коммутативным кольцом , где p заменяется идеалом , а «взаимно простые многочлены» означают «многочлены, порождающие идеал, содержащий 1 ».

Лемма Гензеля является фундаментальной в p -адическом анализе , одном из разделов аналитической теории чисел .

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

Модульные редукторы и подъемники

Оригинал леммы Гензеля касается соотношения между полиномиальной факторизации над целыми числами и над целыми числами по модулю на простое число р и его полномочия. Его можно прямо распространить на случай, когда целые числа заменяются любым коммутативным кольцом , а p заменяется любым максимальным идеалом (действительно, максимальные идеалы имеют вид, где p - простое число).

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

Пусть R коммутативное кольцо, и я идеал в R . Приведение по модулю I относится к замене каждого элемента R его образом при каноническом отображении. Например, если является многочленом с коэффициентами из R , его редукция по модулю I , обозначается как многочлен от, полученный заменой коэффициентов f на их изображение в двух многочленов F и г в являются сравнимыми по модулю Я , обозначается , если они имеют одинаковые коэффициенты по модулю I , то есть , если Если факторизация ч по модулю я состоит из двух (или более) многочленов F, G в таким образом, что

Процесс подъема - это процесс, обратный редукции. То есть данные объекты, зависящие от элементов процесса подъема, заменяют эти элементы элементами (или для некоторого k > 1 ), которые отображаются на них таким образом, чтобы сохранить свойства объектов.

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

Заявление

Первоначально лемма Гензеля была сформулирована (и доказана) для поднятия факторизации по модулю простого числа p полинома по целым числам до факторизации по модулю любой степени p и факторизации по p -адическим целым числам . Это можно легко обобщить с тем же доказательством на случай, когда целые числа заменяются любым коммутативным кольцом , простое число заменяется максимальным идеалом , а целые p -адические числа заменяются пополнением по максимальному идеалу . Именно это обобщение, которое также широко используется, представлено здесь.

Пусть - максимальный идеал коммутативного кольца R и

быть полиномом в с ведущим коэффициентом не в

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

Лемма Гензеля утверждает, что любую факторизацию h по модулю на взаимно простые многочлены можно единственным способом поднять в факторизацию по модулю для каждого k .

Точнее, с приведенными выше гипотезами, если где f и g являются моническими и взаимно простыми по модулю, то для каждого натурального числа k существуют монические многочлены и такие, что

и и являются уникальными (с этими свойствами) по модулю

Подъем простых корней

Важный частный случай, когда в этом случае взаимной простоты гипотеза означает , что г является простым корнем из Это дает следующий частный случай леммы Гензеля, который часто называют также леммы Гензеля.

С приведенными выше гипотезами и обозначениями, если r является простым корнем, то r может быть поднят уникальным способом до простого корня для любого положительного целого числа n . Ясно, что для каждого положительного целого числа n существует такое уникальное , что и является простым корнем из

Подъем до адического завершения

Тот факт, что можно поднять до для любого положительного целого числа n, предполагает «перейти к пределу», когда n стремится к бесконечности. Это было одной из основных причин введения p -адических целых чисел .

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

Из определения пополнения как обратного предела и приведенного выше утверждения леммы Гензеля следует, что любую факторизацию на попарно взаимно простые многочлены по модулю многочлена можно однозначно поднять до факторизации образа h в. Аналогично, любой простой корень h по модулю можно поднять до простого корня образа h в

Доказательство

Лемма Гензеля обычно доказывается поэтапно, поднимая факторизацию до факторизации ( линейный подъем ) или факторизации ( квадратичный подъем ).

Основной компонент доказательства состоит в том, что взаимно простые многочлены над полем удовлетворяют тождеству Безу . То есть, если f и g - взаимно простые многомерные многочлены над полем (здесь ), существуют многочлены a и b такие, что и

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

Линейный подъем

Пусть я быть идеальным из коммутативного кольца R , и быть одномерным полиномом с коэффициентами в R , который имеет старший коэффициент , который обратим по модулю Я (то есть, изображение , в это единица , в ).

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

такие, что f и g - унитарные многочлены , взаимно простые по модулю I , в том смысле, что существуют такие, что Тогда существуют многочлены такие, что и

В этих условиях и уникальны по модулю

Более того, и удовлетворяют тому же тождеству Безу, что и f и g , т. Е.

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

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

Доказательство: По условию, обратим по модулю I . Это означает, что существует и такое, что

Пусть степени меньше такой, что

(Можно выбрать, но другие варианты могут привести к более простым вычислениям. Например, если и возможно, и лучше выбрать, где коэффициенты являются целыми числами в интервале )

Как г является унитарным, то евклидово деление из по г определена, и обеспечивает д и с таким образом, что и того, и д и с в Аналогично, пусть с и

У одного действительно есть

Как это унитарное, степень по модулю из может быть меньше , только если

Таким образом, с учетом сравнений по модулю единица

Итак, утверждение существования проверяется с помощью

Уникальность

Пусть R , I , h и as a в предыдущем разделе. Позволять

- факторизация в взаимно простые многочлены (в указанном выше смысле), например, применение линейного подъема для показывает существование и таких, что и

Многочлены и определяются однозначно по модулю. Это означает, что если другая пара удовлетворяет тем же условиям, то одна из них имеет

Доказательство : поскольку сравнение по модулю влечет такое же совпадение по модулю один, можно действовать по индукции и предположить, что единственность доказана для n - 1 , причем случай n = 0 тривиален. То есть можно предположить, что

По предположению имеет

и поэтому

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

снова используя гипотезу индукции.

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

Таким образом, у одного есть полином меньшей степени, чем эта, сравнимый по модулю с произведением монического полинома g и другого полинома w . Это возможно только в том случае, если и подразумевает Аналогично, также находится в и это доказывает уникальность.

Квадратичный лифтинг

Линейный подъем позволяет поднять факторизацию по модулю до факторизации по модулю.Квадратичный подъем позволяет поднять непосредственно до факторизации по модулю за счет подъема также тождества Безу и вычисления по модулю вместо модуля I (если использовать приведенное выше описание линейного подъема).

Для подъема по модулю для больших N можно использовать любой метод. Если, скажем, факторизация по модулю требует N - 1 шага линейного подъема или только k - 1 шага квадратичного подъема. Однако в последнем случае размер коэффициентов, которыми нужно управлять, увеличивается во время вычисления. Это означает, что лучший метод подъема зависит от контекста (значение N , характер R , используемый алгоритм умножения, особенности оборудования и т. Д.).

Квадратичный подъем основан на следующем свойстве.

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

такие, что f и g - унитарные многочлены , взаимно простые по модулю I , в том смысле, что существуют такие, что Тогда существуют многочлены такие, что и

Кроме того, и удовлетворяют тождеству Безу вида

(Это необходимо для разрешения итераций квадратичного подъема.)

Доказательство : Первое утверждение точно , что линейный подъем применяется при к = 1 к идеалу , а не я .

Пусть у кого-то есть

куда

Настройка и один получает

что доказывает второе утверждение.

Явный пример

Позволять

По модулю 2 лемма Гензеля неприменима, поскольку редукция по модулю 2 просто pg 15-16

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

где - квадратный корень из 2 дюймов . Поскольку 4 не является кубом, эти два фактора неприводимы . Следовательно, полная факторизация in и есть

где - квадратный корень из 2, который можно получить, подняв вышеупомянутую факторизацию. Наконец, в многочлене распадается на

со всеми множителями, взаимно простыми друг с другом, так что в и есть 6 множителей с (нерациональными) 727-адическими целыми числами

Использование производных для подъема корней

Пусть будет многочлен с целыми (или p -адическими целыми) коэффициентами, и пусть m , k - положительные целые числа такие, что mk . Если r - такое целое число, что

тогда для каждого существует такое целое число s , что

Кроме того, это s уникально по модулю p k + m и может быть вычислено явно как целое число, такое что

где - целое число, удовлетворяющее

Обратите внимание на то, чтобы условие было выполнено. Кроме того, если , то может существовать 0, 1 или несколько s (см. Hensel Lifting ниже).

Вывод

Мы используем разложение Тейлора f вокруг r, чтобы написать:

Отсюда видно, что s - r = tp k для некоторого целого t . Позволять

Ибо у нас есть:

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

Наблюдения

Критерий неприводимых многочленов

Используя приведенные выше предположения, если мы рассмотрим неприводимый многочлен

так что тогда

В частности, при находим в

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

Фробениус

Обратите внимание , что дано эндоморфизм Фробениуса дает многочлен , который всегда имеет нулевую производную

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

Корни единства

Хотя корни -й степени единства не содержатся в , есть решения . Примечание

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

Хензель лифтинг

Используя лемму, можно "поднять" корень r многочлена f по модулю p k до нового корня s по модулю p k +1 , так что rs mod p k (взяв m = 1; взяв большее m, следует по индукции ). Фактически, корень по модулю p k +1 также является корнем по модулю p k , поэтому корни по модулю p k +1 - это в точности поднятие корней по модулю p k . Новый корень с конгруэнтен г по модулю р , так что новый корень также удовлетворяет Таким образом, подъем можно повторить, и исходя из решения г к о мы можем получить последовательность решений г K + 1 , г K + 2 ,. .. того же сравнения для последовательно возрастающих степеней p , при условии, что начальный корень r k . Это также показывает, что f имеет то же количество корней mod p k, что и mod p k +1 , mod p k +2 или любую другую более высокую степень p , при условии, что все корни f mod p k простые.

Что произойдет с этим процессом, если r не является простым корневым модулем p ? Предполагать

Тогда следует То есть для всех целых t . Таким образом, у нас есть два случая:

  • Если тогда нет подъема r до корня f ( x ) по модулю p k +1 .
  • Если тогда любое поднятие r до модуля p k +1 является корнем f ( x ) по модулю p k +1 .

Пример. Чтобы увидеть оба случая, рассмотрим два разных многочлена с p = 2:

и r = 1. Тогда и Мы имеем, что означает, что никакое поднятие 1 до модуля 4 не является корнем f ( x ) по модулю 4.

и r = 1. Тогда и Однако, поскольку мы можем поднять наше решение до модуля 4, и оба подъема (т.е. 1, 3) являются решениями. Производная по-прежнему равна 0 по модулю 2, поэтому априори мы не знаем, можем ли мы поднять их до модуля 8, но на самом деле можем, поскольку g (1) равно 0 по модулю 8, а g (3) равно 0 по модулю 8, давая решения в 1, 3, 5 и 7 по модулю 8. Поскольку из них только g (1) и g (7) равны 0 по модулю 16, мы можем поднять только 1 и 7 до модуля 16, давая 1, 7, 9 и 15 mod 16. Из них только 7 и 9 дают g ( x ) = 0 mod 32, поэтому их можно поднять, давая 7, 9, 23 и 25 mod 32. Оказывается, что для любого целого числа k ≥ 3 существует четыре подъема 1 по модулю 2 до корня из g ( x ) по модулю 2 k .

Лемма Гензеля для p -адических чисел

В p -адических числах, где мы можем понимать рациональные числа по модулю степеней p, пока знаменатель не кратен p , рекурсия от r k (корни по модулю p k ) к r k +1 (корни по модулю p k +1 ) можно выразить гораздо более интуитивно. Вместо того, чтобы выбирать t как (y) целое число, которое решает сравнение

пусть t будет рациональным числом ( p k здесь на самом деле не знаменатель, поскольку f ( r k ) делится на p k ):

Затем установите

Эта дробь может не быть целым числом, но это p -адическое целое число, и последовательность чисел r k сходится в p -адических целых числах к корню из f ( x ) = 0. Более того, отображаемая рекурсивная формула для (новое) число r k +1 в терминах r k - это в точности метод Ньютона для нахождения корней уравнений в действительных числах.

Работая непосредственно в p- адике и используя p -адическое абсолютное значение , мы получаем версию леммы Гензеля, которая может быть применена, даже если мы начнем с решения f ( a ) ≡ 0 mod p , так что нам просто нужно убедитесь, что число не равно 0. Эта более общая версия выглядит следующим образом: если существует целое число a, которое удовлетворяет:

тогда существует единственное p -адическое целое число b такое, что f ( b ) = 0 и построение b сводится к тому, чтобы показать, что рекурсия из метода Ньютона с начальным значением a сходится в p -адике, и мы позволяем b быть пределом. Уникальность b как корня, подходящего к условию, требует дополнительной работы.

Приведенная выше формулировка леммы Гензеля (взяв ) является частным случаем этой более общей версии, поскольку условия f ( a ) ≡ 0 mod p и говорят, что и

Примеры

Предположим, что p - нечетное простое число, а a - ненулевой квадратичный вычет по модулю p . Тогда лемма Гензеля следует , что имеет квадратный корень в кольце р -адических чисел Действительно, пусть Если г является квадратным корнем с по модулю р , то:

где второе условие зависит от того, что p нечетное. Базовая версия леммы Гензеля говорит нам, что, начиная с r 1 = r, мы можем рекурсивно построить последовательность целых чисел, такую ​​что:

Эта последовательность сходится к некоторому p -адическому целому числу b, для которого b 2 = a . В самом деле, б является единственным корень квадратный из в конгруэнтны г 1 по модулю р . Наоборот, если a - полный квадрат в и не делится на p, то это ненулевой квадратичный вычет по модулю p . Обратите внимание, что квадратичный закон взаимности позволяет легко проверить, является ли a ненулевым квадратичным вычетом по модулю p , таким образом, мы получаем практический способ определить, какие p -адические числа (при нечетном p ) имеют p -адический квадратный корень, и он может распространяется на случай p = 2 с помощью более общей версии леммы Гензеля (ниже приводится пример с 2-адическими квадратными корнями из 17).

Чтобы сделать обсуждение выше более явным, давайте найдем «квадратный корень из 2» (решение ) в 7-адических целых числах. По модулю 7 одно решение равно 3 (мы также можем взять 4), поэтому мы устанавливаем . Лемма Гензеля позволяет нам найти следующее:

На основании чего выражение

превращается в:

что подразумевает сейчас:

И, конечно же, (если бы мы использовали рекурсию метода Ньютона непосредственно в 7-адиках, то и )

Можем продолжить и найти . Каждый раз, когда мы выполняем вычисление (то есть для каждого последующего значения k ), добавляется еще одна цифра с основанием 7 для следующей более высокой степени 7. В 7-адических целых числах эта последовательность сходится, и предел представляет собой квадрат корень из 2, в котором есть начальное 7-адическое разложение

Если бы мы начали с первоначального выбора, то лемма Гензеля произвела бы квадратный корень из 2, в котором конгруэнтно 4 (mod 7) вместо 3 (mod 7), и фактически этот второй квадратный корень будет отрицательным из первого квадратного корня. (что согласуется с 4 = −3 mod 7).

В качестве примера, когда исходная версия леммы Гензеля не верна, но более общая, пусть и Then и так

что означает , существует единственное 2-адическое число Ь , удовлетворяющий

т.е. b ≡ 1 mod 4. В 2-адических целых числах есть два квадратных корня из 17, различающиеся знаком, и хотя они конгруэнтны по модулю 2, они не конгруэнтны по модулю 4. Это согласуется с общей версией формулы Хензеля. Лемма дает нам только уникальный 2-адический квадратный корень из 17, который конгруэнтен 1 по модулю 4, а не по модулю 2. Если бы мы начали с начального приближенного корня a = 3, то мы могли бы снова применить более общую лемму Гензеля, чтобы найти уникальный 2-адический квадратный корень из 17, который сравним с 3 по модулю 4. Это другой 2-адический квадратный корень из 17.

С точки зрения подъема корней с модуля 2 k до 2 k +1 , подъемы, начиная с корня 1 по модулю 2, выглядят следующим образом:

1 мод 2 -> 1, 3 мод 4
1 мод 4 -> 1, 5 мод 8 и 3 мод 4 ---> 3, 7 мод 8
1 mod 8 -> 1, 9 mod 16 и 7 mod 8 ---> 7, 15 mod 16, в то время как 3 mod 8 и 5 mod 8 не поднимаются до корней mod 16
9 mod 16 -> 9, 25 mod 32 и 7 mod 16 -> 7, 23 mod 16, в то время как 1 mod 16 и 15 mod 16 не поднимают до корней mod 32.

Для каждого k не менее 3 существует четыре корня из x 2 - 17 mod 2 k , но если мы посмотрим на их 2-адические разложения, то увидим, что попарно они сходятся только к двум 2-адическим пределам. Например, четыре корня по модулю 32 разбиваются на две пары корней, каждая из которых выглядит одинаково по модулю 16:

9 = 1 + 2 3 и 25 = 1 + 2 3 + 2 4 .
7 = 1 + 2 + 2 2 и 23 = 1 + 2 + 2 2 + 2 4 .

2-адические квадратные корни из 17 имеют разложения

Другой пример, в котором мы можем использовать более общую версию леммы Гензеля, но не базовую, - это доказательство того, что любое целое 3-адическое число c ≡ 1 mod 9 является кубом в Let и принимает начальное приближение a = 1. Основная лемма Гензеля не может использоваться для поиска корней f ( x ), поскольку для каждого r . Чтобы применить общую версию леммы Гензеля, мы хотим, что означает То есть, если c ≡ 1 mod 27, то общая лемма Гензеля говорит нам, что f ( x ) имеет 3-адический корень, поэтому c является 3-адическим кубом. Однако мы хотели получить этот результат при более слабом условии, что c ≡ 1 mod 9. Если c ≡ 1 mod 9, то c ≡ 1, 10 или 19 mod 27. Мы можем применить общую лемму Гензеля три раза в зависимости от значения of c mod 27: если c ≡ 1 mod 27, тогда используйте a = 1, если c ≡ 10 mod 27, тогда используйте a = 4 (поскольку 4 является корнем f ( x ) mod 27), и если c ≡ 19 mod 27 тогда используйте a = 7. (Неверно, что каждый c ≡ 1 mod 3 является 3-адическим кубом, например, 4 не является 3-адическим кубом, так как это не куб по модулю 9.)

Аналогичным образом, после некоторой предварительной работы, лемма Гензеля может быть использована, чтобы показать, что для любого нечетного простого числа p любое p -адическое целое число c, сравнимое с 1 по модулю p 2, является p -й степенью в (Это неверно для p = 2.)

Обобщения

Предположим, что A - коммутативное кольцо , полное относительно идеала, и пусть aA называется «приближенным корнем» f , если

Если f имеет приближенный корень, то он имеет точный корень bA, «близкий к» a ; то есть,

Кроме того, если не является делителем нуля, то b единственно.

Этот результат можно обобщить на несколько переменных следующим образом:

Теорема. Пусть коммутативное кольцо , которое является полным относительно идеала Пусть бы систему п многочленов от п переменных над А . Просмотр как отображение А н к себе, и пусть обозначим его матрицу Якоби . Предположим, что a = ( a 1 , ..., a n ) ∈ A n является приближенным решением f = 0 в том смысле, что
Тогда существует некоторый b = ( b 1 , ..., b n ) ∈ A n такой, что f ( b ) = 0 , т. Е.
Кроме того, это решение «близко» к a в том смысле, что

В частном случае, если для всех i и является единицей в A, то существует решение f ( b ) = 0 с для всех i .

Когда n = 1, a = a является элементом A и гипотезы этой многомерной леммы Гензеля сводятся к тем, которые были сформулированы в лемме Гензеля об одной переменной.

Связанные понятия

Полнота кольца не является необходимым условием для того, чтобы кольцо обладало гензелевым свойством: Горо Адзумая в 1950 году определил коммутативное локальное кольцо, удовлетворяющее гензелевскому свойству для максимального идеала m, чтобы быть гензелевым кольцом .

Масаёши Нагата доказал в 1950-х годах, что для любого коммутативного локального кольца A с максимальным идеалом m всегда существует наименьшее кольцо A h, содержащее A такое, что A h является гензелевым относительно m A h . Это ч называется гензелизацией из A . Если является нетеровой , ч будет также нетеровой и ч явно алгебраическая как она строится как предел этальных окрестностей . Это означает, что A h обычно намного меньше завершения Â при сохранении гензелевского свойства и в той же категории .

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

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