Лемма Гензеля: поднятие корня от mod p к p-адическим целым

Лемма Гензеля - это рабочий мост между арифметикой по модулю простого $p$ и арифметикой p-адических целых $\mathbb{Z}_p$. Если у многочлена $f(x) \in \mathbb{Z}[x]$ нашёлся «гладкий» корень по модулю $p$ - то есть $f(a_0) \equiv 0 \pmod p$ и производная $f'(a_0) \not\equiv 0 \pmod p$, - то этот корень однозначно поднимается до настоящего корня $\alpha \in \mathbb{Z}_p$. Доказательство - двадцать строк, инструмент - p-адическая версия метода Ньютона. Курт Гензель сформулировал лемму около 1900 года как часть программы переноса аналитических методов в теорию чисел; сегодня она лежит в основе локально-глобальных принципов, счёта точек на схемах и постановки задач арифметической геометрии.

Постановка

Зафиксируем простое число $p$ и многочлен с целыми коэффициентами

$$f(x) = c_n x^n + c_{n-1} x^{n-1} + \dots + c_1 x + c_0, \qquad c_i \in \mathbb{Z}.$$

Будем называть редукцией $f$ многочлен $\bar f \in \mathbb{F}_p[x]$, полученный взятием всех коэффициентов по модулю $p$. Корни $\bar f$ ищутся перебором среди $\{0, 1, \dots, p-1\}$ - это конечная задача.

Вопрос: можно ли по корню $\bar a_0$ многочлена $\bar f$ восстановить корень самого $f$ в более тонкой структуре - в $\mathbb{Z}_p$, кольце p-адических целых? Ответ: при условии гладкости - да, причём единственным образом.

Лемма Гензеля (классическая формулировка). Пусть $f \in \mathbb{Z}_p[x]$ и существует $a_0 \in \mathbb{Z}_p$ такое, что

$$f(a_0) \equiv 0 \pmod p, \qquad f'(a_0) \not\equiv 0 \pmod p.$$

Тогда существует единственный $\alpha \in \mathbb{Z}_p$ такой, что $f(\alpha) = 0$ и $\alpha \equiv a_0 \pmod p$.

Два условия читаются так: $a_0$ - корень редукции $\bar f$ в $\mathbb{F}_p$ (существование начального приближения) и эта редукция в точке простая, не кратная (гладкость в точке). Гладкость и обеспечивает единственное поднятие.

Хочешь увидеть, как поднимается конкретный корень - выбери многочлен, простое $p$ и получи p-адические шаги Ньютона до точности $p^4$ с проверкой условий леммы.

Итерация p-адического Ньютона

Конструкция корня $\alpha$ повторяет обычный метод Ньютона:

$$a_{n+1} = a_n - \frac{f(a_n)}{f'(a_n)}.$$

Только всё происходит в $\mathbb{Z}_p$, и сходимость измеряется не евклидовой, а p-адической нормой. Напомню: $|x|_p = p^{-v_p(x)}$, где $v_p(x)$ - степень $p$ в каноническом разложении $x$; чем больше $p$ делит $x$, тем меньше его p-адическая «длина».

Стартуем с $a_0$ - нашего начального корня по модулю $p$. На каждом шаге деление $f(a_n)/f'(a_n)$ корректно в $\mathbb{Z}_p$, потому что $f'(a_n) \not\equiv 0 \pmod p$ - значит, $f'(a_n)$ обратим в $\mathbb{Z}_p$ (единицы $\mathbb{Z}_p$ - это в точности элементы, не делящиеся на $p$). Условие невырожденности сохраняется по индукции, так как $a_{n+1} \equiv a_n \pmod{p^{n+1}}$.

Ключевая оценка - квадратичная сходимость: если $f(a_n) \equiv 0 \pmod{p^{2^n}}$, то $f(a_{n+1}) \equiv 0 \pmod{p^{2^{n+1}}}$. Доказательство - разложение Тейлора:

$$f(a_{n+1}) = f(a_n) + f'(a_n)(a_{n+1} - a_n) + \tfrac{1}{2} f''(a_n)(a_{n+1} - a_n)^2 + \dots$$

Первые два слагаемых сокращаются по построению $a_{n+1}$, остаётся остаток порядка $|a_{n+1} - a_n|_p^2 = |f(a_n)/f'(a_n)|_p^2 = |f(a_n)|_p^2$. То есть p-адическая «погрешность» квадратично уменьшается на каждом шаге.

Последовательность $\{a_n\}$ фундаментальна в $\mathbb{Z}_p$ (метрика полна), значит сходится к $\alpha \in \mathbb{Z}_p$ со свойством $f(\alpha) = 0$ и $\alpha \equiv a_0 \pmod p$.

Пример: $\sqrt{2} \in \mathbb{Z}_7$

Решим уравнение $x^2 \equiv 2 \pmod 7$ и поднимем его до корня в $\mathbb{Z}_7$.

Шаг 0. Перебираем $a \in \{0, 1, \dots, 6\}$: $3^2 = 9 \equiv 2 \pmod 7$ - корень. Берём $a_0 = 3$. Производная $f'(x) = 2x$, $f'(3) = 6 \not\equiv 0 \pmod 7$ - гладкость есть. Лемма Гензеля применима.

Шаг 1. $f(a_0) = 9 - 2 = 7$. Делим в $\mathbb{Z}_7$: $f(a_0)/f'(a_0) = 7/6$. Нужно найти обратный к $6$ по модулю $7^2 = 49$: $6 \cdot 41 = 246 = 5 \cdot 49 + 1$, значит $6^{-1} \equiv 41 \pmod{49}$. Тогда

$$a_1 = 3 - 7 \cdot 41 \pmod{49} = 3 - 287 \pmod{49} = 3 - 287 + 6 \cdot 49 = 3 - 287 + 294 = 10.$$

Проверка: $a_1^2 = 100 = 2 \cdot 49 + 2$, значит $a_1^2 \equiv 2 \pmod{49}$. Идём дальше.

Шаг 2. $f(a_1) = 100 - 2 = 98 = 2 \cdot 49$. $f'(a_1) = 20$. Обратный к $20$ по модулю $7^4 = 2401$ можно посчитать расширенным алгоритмом Евклида, но проще остаться в нужной точности: $a_2 = a_1 - 98/20 \pmod{7^4}$. По индукции $a_2^2 \equiv 2 \pmod{7^4}$.

Численно $a_2 = 108$ и $108^2 = 11664 = 4 \cdot 2401 + 2060$, на самом деле тут проще задать $a_2 \equiv a_1 \pmod{49}$ и подобрать $a_2 = 10 + 49 k$ так, чтобы $a_2^2 \equiv 2 \pmod{343}$. Получится $k = 2$, $a_2 = 108$. Дальше - $a_3 = 108 + 343 \cdot k'$, и так далее.

В записи p-адического разложения $\alpha = 3 + 1 \cdot 7 + 2 \cdot 7^2 + \dots$ - это и есть «$\sqrt{2}$» в $\mathbb{Z}_7$, второй корень - $-\alpha$. В вещественных $\sqrt{2}$ иррационально, в $\mathbb{Z}_7$ - вполне себе p-адическое целое. Разные нормы - разные геометрии.

Когда лемма Гензеля не работает

Все три обязательные клетки:

• $f(a_0) \not\equiv 0 \pmod p$ - нет начального корня. Например, $x^2 \equiv 2 \pmod 5$: квадраты в $\mathbb{F}_5$ - $\{0, 1, 4\}$, двойки нет. $\sqrt{2}$ в $\mathbb{Z}_5$ не существует.
• $f'(a_0) \equiv 0 \pmod p$ - корень кратный, нет гладкости. Классический случай: $x^2 \equiv 0 \pmod 2$ с $a_0 = 0$. Здесь $f(0) = 0$, $f'(0) = 0$ - лемма в классической форме молчит. Корни $x^2 = 0$ в $\mathbb{Z}_2$ всё равно есть (само $x = 0$), но единственность поднятия рушится.
• $f \notin \mathbb{Z}_p[x]$ - лемма требует p-адически целых коэффициентов. На дробях из $\mathbb{Q}_p \setminus \mathbb{Z}_p$ нужна аккуратная переформулировка.

Есть усиленная (общая) форма Гензеля: если $|f(a_0)|_p < |f'(a_0)|_p^2$, корень поднимается без условия $f'(a_0) \not\equiv 0 \pmod p$. Условие читается как «$f$ в точке $a_0$ значительно меньше, чем квадрат производной» - этого хватает для квадратичной сходимости Ньютона. На практике общая форма - основной рабочий инструмент в арифметической геометрии: классическая версия слишком жёсткая в характеристике 2.

Геометрический смысл

Уравнение $f(x) = 0$ задаёт нульмерную схему $X = \mathrm{Spec}\, \mathbb{Z}[x]/(f)$. Простое $p$ даёт редукцию $\bar X = X \otimes \mathbb{F}_p$, а лемма Гензеля говорит, что гладкие точки $\bar X(\mathbb{F}_p)$ единственным образом поднимаются до точек $X(\mathbb{Z}_p)$.

В этой постановке лемма обобщается на произвольные гладкие схемы конечного типа над $\mathbb{Z}_p$ (или, шире, над любым полным локальным кольцом): множества $X(\mathbb{Z}_p)$ и $X(\mathbb{F}_p)$ совпадают как множества гладких точек. Поэтому для гладких многообразий счёт $\mathbb{F}_p$-точек эквивалентен счёту $\mathbb{Z}_p$-точек - без леммы Гензеля этот переход был бы нетривиален.

Применения

• Поиск корней многочленов в $\mathbb{Q}_p$. Стандартный алгоритм: ищем корни по модулю $p$ перебором, проверяем гладкость, поднимаем Ньютоном до нужной точности. Скорость - логарифмическая по требуемой точности.
• Локально-глобальные принципы. Принцип Хассе-Минковского для квадратичных форм решает задачи в $\mathbb{Q}$ через одновременную разрешимость в каждом $\mathbb{Q}_p$ и в $\mathbb{R}$ - а внутри каждого $\mathbb{Q}_p$ работает Гензель. Сам переход «от глобального к локальному» формализуется через локализацию кольца по простому идеалу $(p)$.
• Счёт точек схем. $|X(\mathbb{F}_q)|$ для гладких $X$ через дзета-функции и формулу Лефшеца упирается в эквивалентность $X(\mathbb{Z}_p) \to X(\mathbb{F}_p)$ - следствие леммы.
• Криптография. Алгоритм Зассенхауса факторизации многочленов в $\mathbb{Z}[x]$: факторизуем по модулю $p$ (быстро, конечное поле), поднимаем Гензелем до факторизации по модулю $p^N$, дальше восстанавливаем целые делители.
• Якобиевы матрицы и многомерное обобщение. Многомерная лемма Гензеля: для системы $F: \mathbb{Z}_p^n \to \mathbb{Z}_p^n$ условие $\det J_F(a_0) \not\equiv 0 \pmod p$ заменяет $f'(a_0) \not\equiv 0$, итерация - $a_{n+1} = a_n - J_F(a_n)^{-1} F(a_n)$.

Частые ошибки

• Применяют лемму к $p = 2$ автоматически. В характеристике 2 много корней кратные («дискриминант чётный»), и классическая форма требует усиленной. Простой случай - $x^2 + 1$ при $p = 2$: $f(1) = 2 \equiv 0 \pmod 2$, но $f'(1) = 2 \equiv 0 \pmod 2$ - лемма Гензеля молчит, и корень действительно не поднимается в $\mathbb{Z}_2$.
• Считают, что лемма гарантирует корень в $\mathbb{Q}$ или $\mathbb{Z}$. Нет, только в $\mathbb{Z}_p$. У многочлена $x^2 - 2$ есть корень в $\mathbb{Z}_7$, но не в $\mathbb{Q}$ - это разные кольца с разными нормами.
• Путают условие $f(a_0) \equiv 0 \pmod p$ и $f(a_0) \equiv 0 \pmod{p^2}$. Классике хватает первого, но для быстрой сходимости часто стартуют со «второго приближения». На квадратичную сходимость это не влияет, только сдвигает счётчик шагов.
• Применяют только к одномерным многочленам. Лемма работает для систем - нужно лишь следить за невырожденностью якобиана, а не отдельной производной.

FAQ

Чем лемма Гензеля отличается от обычного метода Ньютона? Сама итерация $a_{n+1} = a_n - f(a_n)/f'(a_n)$ совпадает, разница - в норме. Обычный Ньютон сходится в вещественных по архимедовой норме и требует выпуклости / достаточно близкого старта. P-адический Ньютон сходится по неархимедовой норме автоматически, как только начальное приближение лежит в окрестности гладкого корня по модулю $p$. Сходимость гарантирована теоремой, а не численным экспериментом.

Что такое $\mathbb{Z}_p$ и зачем оно нужно? $\mathbb{Z}_p$ - пополнение целых чисел по p-адической норме. Элементы - формальные ряды $\sum_{i \ge 0} c_i p^i$ с $c_i \in \{0, \dots, p-1\}$. Это кольцо позволяет решать диофантовы задачи «локально в простом $p$» - отдельно от вещественных и других простых, - а потом собирать ответы через локально-глобальные принципы вроде квадратичного закона взаимности.

Существует ли многомерная лемма Гензеля? Да. Формулировка: пусть $F: \mathbb{Z}_p^n \to \mathbb{Z}_p^n$ - система p-адически аналитических функций, $F(a_0) \equiv 0 \pmod p$, якобиан $\det J_F(a_0) \not\equiv 0 \pmod p$. Тогда существует единственный $\alpha \in \mathbb{Z}_p^n$ с $F(\alpha) = 0$ и $\alpha \equiv a_0 \pmod p$. Доказательство - то же самое: p-адический Ньютон на векторах с матричной обратной к якобиану.

Коротко

Лемма Гензеля: если многочлен $f \in \mathbb{Z}_p[x]$ имеет корень $a_0 \pmod p$ и $f'(a_0) \not\equiv 0 \pmod p$, то существует единственный $\alpha \in \mathbb{Z}_p$ с $f(\alpha) = 0$ и $\alpha \equiv a_0 \pmod p$. Алгоритм поднятия - p-адический метод Ньютона $a_{n+1} = a_n - f(a_n)/f'(a_n)$, сходящийся квадратично по p-адической норме. Геометрически: гладкие точки редукции $\bar X(\mathbb{F}_p)$ однозначно поднимаются до $X(\mathbb{Z}_p)$. Применения - от корней многочленов в $\mathbb{Q}_p$ и алгоритма Зассенхауса до счёта точек гладких схем и принципа Хассе-Минковского.