Лемма Гензеля

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

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

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

Лемма Гензеля является основополагающей в p -адическом анализе , разделе аналитической теории чисел .

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

Первоначальная лемма Гензеля касается связи между полиномиальной факторизацией над целыми числами и над целыми числами по модулю простого числа p и его степеней. Она может быть напрямую расширена на случай, когда целые числа заменяются любым коммутативным кольцом , а p заменяется любым максимальным идеалом (действительно, максимальные идеалы имеют вид , где p — простое число).${\displaystyle \mathbb {Z} }$${\displaystyle p\mathbb {Z},}$

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

Пусть R — коммутативное кольцо, а I — идеал кольца R. Редукция по модулю I относится к замене каждого элемента кольца R его образом при каноническом отображении Например, если — многочлен с коэффициентами в R , то его редукция по модулю I , обозначаемая — многочлен в , полученный заменой коэффициентов f их образом в Два многочлена f и g в сравнимы по модулю I , обозначаемая , если они имеют одинаковые коэффициенты по модулю I , то есть если Если факторизация h по модулю I состоит из двух (или более) многочленов f, g в таких, что${\displaystyle R\to R/I.}$${\displaystyle f\in R[X]}$${\displaystyle f{\bmod {I}},}$${\displaystyle (R/I)[X]=R[X]/IR[X]}$${\displaystyle Р/И.}$${\displaystyle R[X]}$ ${\textstyle f\equiv g{\pmod {I}}}$${\displaystyle fg\in IR[X].}$${\displaystyle h\in R[X],}$${\displaystyle R[X]}$${\textstyle h\equiv fg{\pmod {I}}.}$

Процесс подъема является обратным процессу редукции. То есть данные объекты , зависящие от элементов процесса подъема, заменяют эти элементы элементами (или для некоторого k > 1 ), которые отображаются на них таким образом, что сохраняют свойства объектов. ${\displaystyle Р/И,}$${\displaystyle R}$${\displaystyle R/I^{k}}$

Например, если задан полином и факторизация по модулю I, выраженная как поднятие, эта факторизация по модулю состоит в нахождении полиномов таких, что и лемма Гензеля утверждает, что такое поднятие всегда возможно при мягких условиях; см. следующий раздел.${\displaystyle h\in R[X]}$${\textstyle h\equiv fg{\pmod {I}},}$${\displaystyle I^{k}}$${\displaystyle f',g'\in R[X]}$${\textstyle f'\equiv f{\pmod {I}},}$ ${\textstyle g'\equiv g{\pmod {I}},}$${\textstyle h\equiv f'g'{\pmod {I^{k}}}.}$

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

Пусть — максимальный идеал коммутативного кольца R , и ${\displaystyle {\mathfrak {m}}}$

${\displaystyle h=\альфа _{0}X^{n}+\cdots +\альфа _{n-1}X+\альфа _{n}}$

быть многочленом в со старшим коэффициентом не в${\displaystyle R[X]}$ ${\displaystyle \альфа _{0}}$${\displaystyle {\mathfrak {m}}.}$

Так как — максимальный идеал, фактор-кольцо является полем , а — областью главных идеалов и, в частности, областью уникальной факторизации , что означает, что каждый ненулевой многочлен из может быть разложен единственным образом как произведение ненулевого элемента из и неприводимых многочленов , которые являются моническими (то есть их старшие коэффициенты равны 1).${\displaystyle {\mathfrak {m}}}$ ${\displaystyle R/{\mathfrak {m}}}$${\displaystyle (R/{\mathfrak {м}})[X]}$${\displaystyle (R/{\mathfrak {м}})[X]}$${\displaystyle (R/{\mathfrak {m}})}$

Лемма Гензеля утверждает, что каждое разложение h по модулю на взаимно простые многочлены может быть единственным образом поднято до разложения по модулю для каждого k .${\displaystyle {\mathfrak {m}}}$${\displaystyle {\mathfrak {m}}^{k}}$

Точнее, с учетом вышеизложенных гипотез, если f и g являются моническими и взаимно простыми по модулю , то для каждого положительного целого числа k существуют монические многочлены и такие, что${\textstyle h\equiv \alpha _{0}fg{\pmod {\mathfrak {m}}},}$${\displaystyle {\mathfrak {m}},}$${\displaystyle f_{k}}$${\displaystyle g_{k}}$

${\displaystyle {\begin{align}h&\equiv \alpha _{0}f_{k}g_{k}{\pmod {{\mathfrak {m}}^{k}}},\\f_{k}&\equiv f{\pmod {\mathfrak {m}}},\\g_{k}&\equiv g{\pmod {\mathfrak {m}}},\end{align}}}$

и и являются уникальными (с этими свойствами) по модулю${\displaystyle f_{k}}$${\displaystyle g_{k}}$${\displaystyle {\mathfrak {m}}^{k}.}$

Важным частным случаем является случай, когда В этом случае гипотеза взаимной простоты означает, что r является простым корнем Это дает следующий частный случай леммы Гензеля, который часто также называют леммой Гензеля.${\displaystyle f=Xr.}$${\displaystyle h{\bmod {\mathfrak {m}}}.}$

С указанными выше гипотезами и обозначениями, если r является простым корнем, то r может быть поднято единственным способом до простого корня для каждого положительного целого числа n . Явно, для каждого положительного целого числа n существует единственное такое, что и является простым корнем${\displaystyle h{\bmod {\mathfrak {m}}},}$${\displaystyle h{\bmod {{\mathfrak {m}}^{n}}}}$${\displaystyle r_{n}\in R/{\mathfrak {m}}^{n}}$${\textstyle r_{n}\equiv r{\pmod {\mathfrak {m}}}}$${\displaystyle r_{n}}$${\displaystyle h{\bmod {\mathfrak {m}}}^{n}.}$

Тот факт, что можно поднять до для любого положительного целого числа n, предполагает «перейти к пределу», когда n стремится к бесконечности. Это было одним из главных мотивов для введения p -адических целых чисел . ${\displaystyle R/{\mathfrak {m}}^{n}}$

Если задан максимальный идеал коммутативного кольца R , то степени образуют базис открытых окрестностей для топологии на R , которая называется -адической топологией . Завершение этой топологии можно отождествить с завершением локального кольца и с обратным пределом Это завершение является полным локальным кольцом , обычно обозначаемым Когда R - кольцо целых чисел, а p - простое число, это завершение является кольцом p -адических целых чисел${\displaystyle {\mathfrak {m}}}$${\displaystyle {\mathfrak {m}}}$${\displaystyle {\mathfrak {m}}}$ ${\displaystyle R_{\mathfrak {m}},}$ ${\displaystyle \lim _{\leftarrow }R/{\mathfrak {m}}^{n}.}$${\displaystyle {\widehat {R}}_{\mathfrak {m}}.}$${\displaystyle {\mathfrak {m}}=p\mathbb {Z} ,}$${\displaystyle \mathbb {Z} _{p}.}$

Определение пополнения как обратного предела и приведенное выше утверждение леммы Гензеля подразумевают, что каждое разложение на попарно взаимно простые многочлены по модулю многочлена может быть единственным образом поднято до разложения образа h в Аналогично, каждый простой корень h по модулю может быть поднят до простого корня образа h в${\displaystyle {\mathfrak {m}}}$${\displaystyle h\in R[X]}$${\displaystyle {\widehat {R}}_{\mathfrak {m}}[X].}$${\displaystyle {\mathfrak {m}}}$${\displaystyle {\widehat {R}}_{\mathfrak {m}}[X].}$

Лемма Гензеля обычно доказывается пошагово, поднимая факторизацию до факторизации (линейное поднятие) или факторизации (квадратичное поднятие).${\displaystyle R/{\mathfrak {m}}^{n}}$${\displaystyle R/{\mathfrak {m}}^{n+1}}$${\displaystyle R/{\mathfrak {m}}^{2n}}$

Основным ингредиентом доказательства является то, что взаимно простые многочлены над полем удовлетворяют тождеству Безу . То есть, если f и g являются взаимно простыми одномерными многочленами над полем (здесь ), существуют многочлены a и b такие, что и${\displaystyle R/{\mathfrak {m}}}$${\displaystyle \deg a<\deg g,}$ ${\displaystyle \deg b<\deg f,}$

${\displaystyle af+bg=1.}$

Тождество Безу позволяет определять взаимно простые многочлены и доказывать лемму Гензеля, даже если идеал не является максимальным. Поэтому в следующих доказательствах мы начинаем с коммутативного кольца R , идеала I , многочлена , имеющего старший коэффициент, обратимого по модулю I (то есть его образ в является единицей в ), и факторизации h по модулю I или по модулю степени I , такой, что множители удовлетворяют тождеству Безу по модулю I . В этих доказательствах означает${\displaystyle {\mathfrak {m}}}$ ${\displaystyle h\in R[X]}$${\displaystyle R/I}$${\displaystyle R/I}$${\textstyle A\equiv B{\pmod {I}}}$${\displaystyle A-B\in IR[X].}$

Пусть I — идеал коммутативного кольца R , а — одномерный многочлен с коэффициентами в R , имеющий старший коэффициент , обратим по модулю I (то есть образ в является единицей в ). ${\displaystyle h\in R[X]}$ ${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle R/I}$${\displaystyle R/I}$

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

${\displaystyle h\equiv \alpha fg{\pmod {I^{k}}},}$

такие, что f и g являются моническими многочленами , которые взаимно просты по модулю I , в том смысле, что существуют такие, что Тогда существуют многочлены, такие, что и${\displaystyle a,b\in R[X],}$${\textstyle af+bg\equiv 1{\pmod {I}}.}$${\displaystyle \delta _{f},\delta _{g}\in I^{k}R[X],}$${\displaystyle \deg \delta _{f}<\deg f,}$ ${\displaystyle \deg \delta _{g}<\deg g,}$

${\displaystyle h\equiv \alpha (f+\delta _{f})(g+\delta _{g}){\pmod {I^{k+1}}}.}$

При этих условиях и являются уникальными по модулю${\displaystyle \delta _{f}}$${\displaystyle \delta _{g}}$${\displaystyle I^{k+1}R[X].}$

Более того, и удовлетворяют тому же тождеству Безу, что и f и g , то есть Это немедленно следует из предыдущих утверждений, но необходимо для итеративного применения результата с возрастающими значениями k .${\displaystyle f+\delta _{f}}$${\displaystyle g+\delta _{g}}$$${\displaystyle a(f+\delta _{f})+b(g+\delta _{g})\equiv 1{\pmod {I}}.}$$

Приведенное ниже доказательство написано для вычисления и с использованием только полиномов с коэффициентами в или , когда и это позволяет манипулировать только целыми числами по модулю p .${\displaystyle \delta _{f}}$${\displaystyle \delta _{g}}$${\displaystyle R/I}$${\displaystyle I^{k}/I^{k+1}.}$${\displaystyle R=\mathbb {Z} }$${\displaystyle I=p\mathbb {Z} ,}$

Доказательство: По условию, обратимо по модулю I. Это означает, что существует и такое, что${\displaystyle \alpha }$${\displaystyle \beta \in R}$${\displaystyle \gamma \in IR[X]}$${\displaystyle \alpha \beta =1-\gamma .}$

Пусть степени меньше такой, что${\displaystyle \delta _{h}\in I^{k}R[X],}$${\displaystyle \deg h,}$

${\displaystyle \delta _{h}\equiv h-\alpha fg{\pmod {I^{k+1}}}.}$

(Можно выбрать , но другие варианты могут привести к более простым вычислениям. Например, если и , то можно и лучше выбрать , где коэффициенты являются целыми числами в интервале )${\displaystyle \delta _{h}=h-\alpha fg,}$${\displaystyle R=\mathbb {Z} }$${\displaystyle I=p\mathbb {Z} ,}$${\displaystyle \delta _{h}=p^{k}\delta '_{h}}$${\displaystyle \delta '_{h}}$${\displaystyle [0,p-1].}$

Так как g является моническим, евклидово деление на g определено и дает q и c такие, что и Более того, и q и c находятся в Аналогично, пусть с и${\displaystyle a\delta _{h}}$${\displaystyle a\delta _{h}=qg+c,}$${\displaystyle \deg c<\deg g.}$${\displaystyle I^{k}R[X].}$${\displaystyle b\delta _{h}=q'f+d,}$${\displaystyle \deg d<\deg f,}$${\displaystyle q',d\in I^{k}R[X].}$

Действительно , у одного есть${\displaystyle q+q'\in I^{k+1}R[X].}$

${\displaystyle fc+gd=af\delta _{h}+bg\delta _{h}-fg(q+q')\equiv \delta _{h}-fg(q+q'){\pmod {I^{k+1}}}.}$

Как и в случае моника, степень по модулю может быть меньше только в том случае, если${\displaystyle fg}$${\displaystyle I^{k+1}}$${\displaystyle fg(q+q')}$${\displaystyle \deg fg}$${\displaystyle q+q'\in I^{k+1}R[X].}$

Таким образом, рассматривая сравнения по модулю, имеем${\displaystyle I^{k+1},}$

${\displaystyle {\begin{aligned}\alpha (f+\beta d)&(g+\beta c)-h\\&\equiv \alpha fg-h+\alpha \beta (f(a\delta _{h}-qg)+g(b\delta _{h}-q'f))\\&\equiv \delta _{h}(-1+\alpha \beta (af+bg))-\alpha \beta fg(q+q')\\&\equiv 0{\pmod {I^{k+1}}}.\end{aligned}}}$

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

${\displaystyle \delta _{f}=\beta d,\qquad \delta _{g}=\beta c.}$

Пусть R , I , h и как в предыдущем разделе. Пусть ${\displaystyle \alpha }$

${\displaystyle h\equiv \alpha fg{\pmod {I}}}$

быть разложением на взаимно простые многочлены (в указанном выше смысле), такие Применение линейного подъема для показывает существование и таких, что и${\displaystyle \deg f_{0}+\deg g_{0}=\deg h.}$${\displaystyle k=1,2,\ldots ,n-1\ldots ,}$${\displaystyle \delta _{f}}$${\displaystyle \delta _{g}}$${\displaystyle \deg \delta _{f}<\deg f,}$ ${\displaystyle \deg \delta _{g}<\deg g,}$

${\displaystyle h\equiv \alpha (f+\delta _{f})(g+\delta _{g}){\pmod {I^{n}}}.}$

Многочлены и однозначно определены по модулю Это означает, что если другая пара удовлетворяет тем же условиям, то имеем${\displaystyle \delta _{f}}$${\displaystyle \delta _{g}}$${\displaystyle I^{n}.}$${\displaystyle (\delta '_{f},\delta '_{g})}$

${\displaystyle \delta '_{f}\equiv \delta _{f}{\pmod {I^{n}}}\qquad {\text{and}}\qquad \delta '_{g}\equiv \delta _{g}{\pmod {I^{n}}}.}$

Доказательство : Поскольку конгруэнтность по модулю влечет ту же конгруэнтность по модулю, можно продолжить по индукции и предположить, что единственность доказана для n − 1 , случай n = 0 тривиален. То есть можно предположить, что${\displaystyle I^{n}}$${\displaystyle I^{n-1},}$

${\displaystyle \delta _{f}-\delta '_{f}\in I^{n-1}R[X]\qquad {\text{and}}\qquad \delta _{g}-\delta '_{g}\in I^{n-1}R[X].}$

По гипотезе, имеет

${\displaystyle h\equiv \alpha (f+\delta _{f})(g+\delta _{g})\equiv \alpha (f+\delta '_{f})(g+\delta '_{g}){\pmod {I^{n}}},}$

и таким образом

${\displaystyle {\begin{aligned}\alpha (f+\delta _{f})(g+\delta _{g})&-\alpha (f+\delta '_{f})(g+\delta '_{g})\\&=\alpha (f(\delta _{g}-\delta '_{g})+g(\delta _{f}-\delta '_{f}))+\alpha (\delta _{f}(\delta _{g}-\delta '_{g})-\delta _{g}(\delta _{f}-\delta '_{f}))\in I^{n}R[X].\end{aligned}}}$

По предположению индукции, второй член последней суммы принадлежит и то же самое, таким образом, верно для первого члена. Поскольку обратим по модулю I , существуют и такие, что Таким образом${\displaystyle I^{n},}$${\displaystyle \alpha }$${\displaystyle \beta \in R}$${\displaystyle \gamma \in I}$${\displaystyle \alpha \beta =1+\gamma .}$

${\displaystyle {\begin{aligned}f(\delta _{g}-\delta '_{g})&+g(\delta _{f}-\delta '_{f})\\&=\alpha \beta (f(\delta _{g}-\delta '_{g})+g(\delta _{f}-\delta '_{f}))-\gamma (f(\delta _{g}-\delta '_{g})+g(\delta _{f}-\delta '_{f}))\in I^{n}R[X],\end{aligned}}}$

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

Взаимная простота по модулю I подразумевает существование такого, что Используя гипотезу индукции еще раз, получаем${\displaystyle a,b\in R[X]}$${\textstyle 1\equiv af+bg{\pmod {I}}.}$

${\displaystyle {\begin{aligned}\delta _{g}-\delta '_{g}&\equiv (af+bg)(\delta _{g}-\delta '_{g})\\&\equiv g(b(\delta _{g}-\delta '_{g})-a(\delta _{f}-\delta '_{f})){\pmod {I^{n}}}.\end{aligned}}}$

Таким образом, имеется многочлен степени меньше, чем , сравнимый по модулю с произведением монического многочлена g и другого многочлена w . Это возможно только тогда, когда и подразумевает Аналогично, также находится в , и это доказывает единственность.${\displaystyle \deg g}$${\displaystyle I^{n}}$${\displaystyle w\in I^{n}R[X],}$${\displaystyle \delta _{g}-\delta '_{g}\in I^{n}R[X].}$${\displaystyle \delta _{f}-\delta '_{f}}$${\displaystyle I^{n}R[X],}$

Линейный подъем позволяет поднять факторизацию по модулю до факторизации по модулю. Квадратический подъем позволяет подняться непосредственно до факторизации по модулю за счет подъема также тождества Безу и вычисления модуля вместо модуля I (если использовать приведенное выше описание линейного подъема). ${\displaystyle I^{n}}$${\displaystyle I^{n+1}.}$${\displaystyle I^{2n},}$${\displaystyle I^{n}}$

Для подъема по модулю для больших N можно использовать любой метод. Если, скажем, факторизация по модулю требует N − 1 шагов линейного подъема или только k − 1 шагов квадратичного подъема. Однако в последнем случае размер коэффициентов, которые должны быть обработаны, увеличивается в ходе вычислений. Это означает, что наилучший метод подъема зависит от контекста (значение N , природа R , используемый алгоритм умножения, особенности оборудования и т. д.). ^{[ необходима цитата ]}${\displaystyle I^{N}}$${\displaystyle N=2^{k},}$${\displaystyle I^{N}}$

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

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

${\displaystyle h\equiv \alpha fg{\pmod {I^{k}}},}$

такие, что f и g являются моническими многочленами , которые взаимно просты по модулю I , в том смысле, что существуют такие, что Тогда существуют многочлены, такие, что и${\displaystyle a,b\in R[X],}$${\textstyle af+bg\equiv 1{\pmod {I^{k}}}.}$${\displaystyle \delta _{f},\delta _{g}\in I^{k}R[X],}$${\displaystyle \deg \delta _{f}<\deg f,}$ ${\displaystyle \deg \delta _{g}<\deg g,}$

${\displaystyle h\equiv \alpha (f+\delta _{f})(g+\delta _{g}){\pmod {I^{2k}}}.}$

Более того, и удовлетворяют тождеству Безу вида ${\displaystyle f+\delta _{f}}$${\displaystyle g+\delta _{g}}$

${\displaystyle (a+\delta _{a})(f+\delta _{f})+(b+\delta _{b})(g+\delta _{g})\equiv 1{\pmod {I^{2k}}}.}$

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

Доказательство : Первое утверждение — это в точности утверждение линейного подъема, примененного при k = 1 к идеалу вместо${\displaystyle I^{k}}$${\displaystyle I.}$

Пусть один имеет${\displaystyle \alpha =af+bg-1\in I^{k}R[X].}$

${\displaystyle a(f+\delta _{f})+b(g+\delta _{g})=1+\Delta ,}$

где

${\displaystyle \Delta =\alpha +a\delta _{f}+b\delta _{g}\in I^{k}R[X].}$

Устанавливаем и получаем${\displaystyle \delta _{a}=-a\Delta }$${\displaystyle \delta _{b}=-b\Delta ,}$

${\displaystyle (a+\delta _{a})(f+\delta _{f})+(b+\delta _{b})(g+\delta _{g})=1-\Delta ^{2}\in I^{2k}R[X],}$

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

Позволять${\displaystyle f(X)=X^{6}-2\in \mathbb {Q} [X].}$

По модулю 2 лемма Гензеля не может быть применена, поскольку сокращение по модулю 2 просто ^{[1] стр. 15-16}${\displaystyle f(X)}$

${\displaystyle {\bar {f}}(X)=X^{6}-{\overline {2}}=X^{6}}$

с 6 факторами, не являющимися взаимно простыми друг с другом. По критерию Эйзенштейна , однако, можно заключить, что многочлен неприводим в Over , с другой стороны, можно иметь${\displaystyle X}$${\displaystyle f(X)}$${\displaystyle \mathbb {Q} _{2}[X].}$
${\displaystyle k=\mathbb {F} _{7}}$

${\displaystyle {\bar {f}}(X)=X^{6}-{\overline {2}}=X^{6}-{\overline {16}}=(X^{3}-{\overline {4}})\;(X^{3}+{\overline {4}})}$

где — квадратный корень из 2 в . Так как 4 не является кубом в эти два множителя неприводимы над . Следовательно, полная факторизация в и равна${\displaystyle 4}$${\displaystyle \mathbb {F} _{7}}$${\displaystyle \mathbb {F} _{7},}$${\displaystyle \mathbb {F} _{7}}$${\displaystyle X^{6}-2}$${\displaystyle \mathbb {Z} _{7}[X]}$${\displaystyle \mathbb {Q} _{7}[X]}$

${\displaystyle f(X)=X^{6}-2=(X^{3}-\alpha )\;(X^{3}+\alpha ),}$

где — квадратный корень из 2 в , который можно получить, подняв факторизацию выше. Наконец, в многочлене распадается на${\displaystyle \alpha =\ldots 450\,454_{7}}$${\displaystyle \mathbb {Z} _{7}}$
${\displaystyle \mathbb {F} _{727}[X]}$

${\displaystyle {\bar {f}}(X)=X^{6}-{\overline {2}}=(X-{\overline {3}})\;(X-{\overline {116}})\;(X-{\overline {119}})\;(X-{\overline {608}})\;(X-{\overline {611}})\;(X-{\overline {724}})}$

со всеми множителями, взаимно простыми друг с другом, так что в и имеется 6 множителей с (нерациональными) 727-адическими целыми числами${\displaystyle \mathbb {Z} _{727}[X]}$${\displaystyle \mathbb {Q} _{727}[X]}$${\displaystyle X-\beta }$

${\displaystyle \beta =\left\{{\begin{array}{rrr}3\;+&\!\!\!545\cdot 727\;+&\!\!\!537\cdot 727^{2}\,+&\!\!\!161\cdot 727^{3}+\ldots \\116\;+&\!\!\!48\cdot 727\;+&\!\!\!130\cdot 727^{2}\,+&\!\!\!498\cdot 727^{3}+\ldots \\119\;+&\!\!\!593\cdot 727\;+&\!\!\!667\cdot 727^{2}\,+&\!\!\!659\cdot 727^{3}+\ldots \\608\;+&\!\!\!133\cdot 727\;+&\!\!\!59\cdot 727^{2}\,+&\!\!\!67\cdot 727^{3}+\ldots \\611\;+&\!\!\!678\cdot 727\;+&\!\!\!596\cdot 727^{2}\,+&\!\!\!228\cdot 727^{3}+\ldots \\724\;+&\!\!\!181\cdot 727\;+&\!\!\!189\cdot 727^{2}\,+&\!\!\!565\cdot 727^{3}+\ldots \end{array}}\right.}$

Пусть будет многочленом с целыми (или p -адическими целыми) коэффициентами, и пусть m , k будут положительными целыми числами, такими что m ≤ k . Если r — целое число, такое что${\displaystyle f(x)}$

${\displaystyle f(r)\equiv 0{\bmod {p}}^{k}\quad {\text{and}}\quad f'(r)\not \equiv 0{\bmod {p}}}$

тогда для каждого существует целое число s такое, что${\displaystyle m>0}$

${\displaystyle f(s)\equiv 0{\bmod {p}}^{k+m}\quad {\text{and}}\quad r\equiv s{\bmod {p}}^{k}.}$

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

${\displaystyle s=r-f(r)\cdot a,}$

где целое число, удовлетворяющее${\displaystyle a}$

${\displaystyle a\equiv [f'(r)]^{-1}{\bmod {p}}^{m}.}$

Обратите внимание, что так что условие выполняется. Кстати, если , то может существовать 0, 1 или несколько s (см. Hensel Lifting ниже).${\displaystyle f(r)\equiv 0{\bmod {p}}^{k}}$${\displaystyle s\equiv r{\bmod {p}}^{k}}$${\displaystyle f'(r)\equiv 0{\bmod {p}}}$

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

${\displaystyle f(s)=\sum _{n=0}^{N}c_{n}(s-r)^{n},\qquad c_{n}=f^{(n)}(r)/n!.}$

Из мы видим, что s − r = tp ^k для некоторого целого числа t . Пусть${\displaystyle r\equiv s{\bmod {p}}^{k},}$

${\displaystyle {\begin{aligned}f(s)&=\sum _{n=0}^{N}c_{n}\left(tp^{k}\right)^{n}\\&=f(r)+tp^{k}f'(r)+\sum _{n=2}^{N}c_{n}t^{n}p^{kn}\\&=f(r)+tp^{k}f'(r)+p^{2k}t^{2}g(t)&&g(t)\in \mathbb {Z} [t]\\&=zp^{k}+tp^{k}f'(r)+p^{2k}t^{2}g(t)&&f(r)\equiv 0{\bmod {p}}^{k}\\&=(z+tf'(r))p^{k}+p^{2k}t^{2}g(t)\end{aligned}}}$

Ибо у нас есть:${\displaystyle m\leqslant k,}$

${\displaystyle {\begin{aligned}f(s)\equiv 0{\bmod {p}}^{k+m}&\Longleftrightarrow (z+tf'(r))p^{k}\equiv 0{\bmod {p}}^{k+m}\\&\Longleftrightarrow z+tf'(r)\equiv 0{\bmod {p}}^{m}\\&\Longleftrightarrow tf'(r)\equiv -z{\bmod {p}}^{m}\\&\Longleftrightarrow t\equiv -z[f'(r)]^{-1}{\bmod {p}}^{m}&&p\nmid f'(r)\end{aligned}}}$

Предположение, что не делится на p, гарантирует, что имеет обратный mod , который обязательно уникален. Следовательно, решение для t существует уникально по модулю , а s существует уникально по модулю${\displaystyle f'(r)}$${\displaystyle f'(r)}$${\displaystyle p^{m}}$${\displaystyle p^{m},}$${\displaystyle p^{k+m}.}$

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

${\displaystyle f(x)=a_{0}+a_{1}x+\cdots +a_{n}x^{n}\in K[X]}$

такой что , то${\displaystyle a_{0},a_{n}\neq 0}$

${\displaystyle |f|=\max\{|a_{0}|,|a_{n}|\}}$

В частности, для мы находим в${\displaystyle f(X)=X^{6}+10X-1}$${\displaystyle \mathbb {Q} _{2}[X]}$

${\displaystyle {\begin{aligned}|f(X)|&=\max\{|a_{0}|,\ldots ,|a_{n}|\}\\&=\max\{0,1,0\}=1\end{aligned}}}$

но , следовательно, многочлен не может быть неприводимым. Тогда как в мы имеем оба значения, согласующиеся, что означает, что многочлен может быть неприводимым. Чтобы определить неприводимость, необходимо использовать многоугольник Ньютона. ^{[2] : 144}${\displaystyle \max\{|a_{0}|,|a_{n}|\}=0}$${\displaystyle \mathbb {Q} _{7}[X]}$

Обратите внимание, что при заданном эндоморфизме Фробениуса получается ненулевой многочлен , имеющий нулевую производную.${\displaystyle a\in \mathbb {F} _{p}}$ ${\displaystyle y\mapsto y^{p}}$${\displaystyle x^{p}-a}$

${\displaystyle {\begin{aligned}{\frac {d}{dx}}(x^{p}-a)&=p\cdot x^{p-1}\\&\equiv 0\cdot x^{p-1}{\bmod {p}}\\&\equiv 0{\bmod {p}}\end{aligned}}}$

следовательно, корни степени p из не существуют в . Ибо это означает, что не может содержать корень из единицы .${\displaystyle a}$${\displaystyle \mathbb {Z} _{p}}$${\displaystyle a=1}$${\displaystyle \mathbb {Z} _{p}}$ ${\displaystyle \mu _{p}}$

Хотя корни p -й степени из единицы не содержатся в , существуют решения . Обратите внимание, что${\displaystyle \mathbb {F} _{p}}$${\displaystyle x^{p}-x=x(x^{p-1}-1)}$

${\displaystyle {\begin{aligned}{\frac {d}{dx}}(x^{p}-x)&=px^{p-1}-1\\&\equiv -1{\bmod {p}}\end{aligned}}}$

никогда не равен нулю, поэтому если существует решение, оно обязательно поднимается до . Поскольку Фробениус дает все ненулевые элементы , являются решениями. Фактически, это единственные корни единицы, содержащиеся в . ^[3]${\displaystyle \mathbb {Z} _{p}}$${\displaystyle a^{p}=a,}$${\displaystyle \mathbb {F} _{p}^{\times }}$${\displaystyle \mathbb {Q} _{p}}$

Используя лемму, можно «поднять» корень r многочлена f по модулю p ^k до нового корня s по модулю p ^{k +1,} такого что r ≡ s mod p ^k (взяв m = 1 ; взятие большего m следует по индукции). Фактически, корень по модулю p ^{k +1} также является корнем по модулю p ^k , поэтому корни по модулю p ^{k +1} являются в точности поднятиями корней по модулю p ^k . Новый корень s сравним с r по модулю p , поэтому новый корень также удовлетворяет условию Таким образом, поднятие можно повторить, и, начиная с решения r _k , мы можем вывести последовательность решений r _{k +1} , r _{k +2} , ... той же самой сравнимости для последовательно более высоких степеней p , при условии, что для начального корня r _k . Это также показывает, что f имеет то же количество корней mod p ^{k ,} что и mod p ^{k +1} , mod p ^{k +2} или любая другая более высокая степень p , при условии, что корни f mod p ^k все простые.${\displaystyle f'(s)\equiv f'(r)\not \equiv 0{\bmod {p}}.}$${\displaystyle f(x)\equiv 0{\bmod {p}}^{k}}$${\displaystyle f'(r_{k})\not \equiv 0{\bmod {p}}}$

Что происходит с этим процессом, если r не является простым корнем mod p ? Предположим, что

${\displaystyle f(r)\equiv 0{\bmod {p}}^{k}\quad {\text{and}}\quad f'(r)\equiv 0{\bmod {p}}.}$

Тогда подразумевает То есть для всех целых чисел t . Поэтому у нас есть два случая:${\displaystyle s\equiv r{\bmod {p}}^{k}}$${\displaystyle f(s)\equiv f(r){\bmod {p}}^{k+1}.}$${\displaystyle f(r+tp^{k})\equiv f(r){\bmod {p}}^{k+1}}$

• Если тогда не существует подъема r до корня f ( x ) по модулю p ^{k +1} .${\displaystyle f(r)\not \equiv 0{\bmod {p}}^{k+1}}$
• Если тогда каждое поднятие r до модуля p ^{k +1} является корнем f ( x ) по модулю p ^{k +1} .${\displaystyle f(r)\equiv 0{\bmod {p}}^{k+1}}$

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

${\displaystyle f(x)=x^{2}+1}$и r = 1. Тогда и имеем что означает, что никакое поднятие 1 до модуля 4 не является корнем f ( x ) по модулю 4.${\displaystyle f(1)\equiv 0{\bmod {2}}}$${\displaystyle f'(1)\equiv 0{\bmod {2}}.}$${\displaystyle f(1)\not \equiv 0{\bmod {4}}}$

${\displaystyle g(x)=x^{2}-17}$и r = 1. Тогда и Однако, поскольку мы можем поднять наше решение до модуля 4 и оба подъема (т. е. 1, 3) являются решениями. Производная по-прежнему равна 0 по модулю 2, поэтому априори мы не знаем, можем ли мы поднять их до модуля 8, но на самом деле мы можем, так как g (1) равно 0 mod 8, а g (3) равно 0 mod 8, что дает решения при 1, 3, 5 и 7 mod 8. Поскольку из них только g (1) и g (7) равны 0 mod 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 mod 2 до корня g ( x ) mod 2 ^k .${\displaystyle g(1)\equiv 0{\bmod {2}}}$${\displaystyle g'(1)\equiv 0{\bmod {2}}.}$${\displaystyle g(1)\equiv 0{\bmod {4}},}$

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

${\displaystyle tf'(r_{k})\equiv -(f(r_{k})/p^{k}){\bmod {p}}^{m},}$

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

${\displaystyle -(f(r_{k})/p^{k})/f'(r_{k}).}$

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

${\displaystyle r_{k+1}=r_{k}+tp^{k}=r_{k}-{\frac {f(r_{k})}{f'(r_{k})}}.}$

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

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

${\displaystyle |f(a)|_{p}<|f'(a)|_{p}^{2},}$

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

Утверждение леммы Гензеля, приведенное выше (принимая ), является частным случаем этой более общей версии, поскольку условия, что f ( a ) ≡ 0 mod p и говорят, что и${\displaystyle m=1}$${\displaystyle f'(a)\not \equiv 0{\bmod {p}}}$${\displaystyle |f(a)|_{p}<1}$${\displaystyle |f'(a)|_{p}=1.}$

Предположим, что p — нечетное простое число, а a — ненулевой квадратичный вычет по модулю p . Тогда из леммы Гензеля следует, что a имеет квадратный корень в кольце p -адических целых чисел Действительно, пусть Если r — квадратный корень из a по модулю p, то:${\displaystyle \mathbb {Z} _{p}.}$${\displaystyle f(x)=x^{2}-a.}$

${\displaystyle f(r)=r^{2}-a\equiv 0{\bmod {p}}\quad {\text{and}}\quad f'(r)=2r\not \equiv 0{\bmod {p}},}$

где второе условие зависит от того, что p нечетно. Базовая версия леммы Гензеля говорит нам, что начиная с r ₁ = r мы можем рекурсивно построить последовательность целых чисел, такую ​​что:${\displaystyle \{r_{k}\}}$

${\displaystyle r_{k+1}\equiv r_{k}{\bmod {p}}^{k},\quad r_{k}^{2}\equiv a{\bmod {p}}^{k}.}$

Эта последовательность сходится к некоторому p -адическому целому числу b , которое удовлетворяет условию b ² = a . Фактически, b является единственным квадратным корнем a, сравнимым с r ₁ по модулю p . Наоборот, если a является полным квадратом в и не делится на p , то это ненулевой квадратичный вычет mod p . Обратите внимание, что квадратичный закон взаимности позволяет легко проверить, является ли a ненулевым квадратичным вычетом mod p , таким образом, мы получаем практический способ определить, какие p -адические числа (для нечетного p ) имеют p -адический квадратный корень, и его можно расширить для покрытия случая p = 2, используя более общую версию леммы Гензеля (пример с 2-адическими квадратными корнями из 17 приведен ниже).${\displaystyle \mathbb {Z} _{p}}$${\displaystyle \mathbb {Z} _{p}}$

Чтобы сделать вышеизложенное обсуждение более явным, давайте найдем "квадратный корень из 2" (решение для ) в 7-адических целых числах. По модулю 7 одно решение равно 3 (мы могли бы также взять 4), поэтому мы устанавливаем . Тогда лемма Гензеля позволяет нам найти следующим образом:${\displaystyle x^{2}-2=0}$${\displaystyle r_{1}=3}$${\displaystyle r_{2}}$

${\displaystyle {\begin{aligned}f(r_{1})&=3^{2}-2=7\\f(r_{1})/p^{1}&=7/7=1\\f'(r_{1})&=2r_{1}=6\end{aligned}}}$

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

${\displaystyle tf'(r_{1})\equiv -(f(r_{1})/p^{k}){\bmod {p}},}$

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

${\displaystyle t\cdot 6\equiv -1{\bmod {7}}}$

что подразумевает сейчас:${\displaystyle t=1.}$

${\displaystyle r_{2}=r_{1}+tp^{1}=3+1\cdot 7=10=13_{7}.}$

И конечно же, (если бы мы использовали рекурсию метода Ньютона непосредственно в 7-адических уравнениях, то и )${\displaystyle 10^{2}\equiv 2{\bmod {7}}^{2}.}$${\displaystyle r_{2}=r_{1}-f(r_{1})/f'(r_{1})=3-7/6=11/6,}$${\displaystyle 11/6\equiv 10{\bmod {7}}^{2}.}$