Hensel's lemma

In mathematics, Hensel's lemma, also known as Hensel's lifting lemma, named after Kurt Hensel, is a result in modular arithmetic, stating that if a polynomial equation has a simple root modulo a prime number p, then this root corresponds to a unique root of the same equation modulo any higher power of p, which can be found by iteratively "lifting" the solution modulo successive powers of p. More generally it is used as a generic name for analogues for complete commutative rings (including p-adic fields in particular) of Newton's method for solving equations. Since p-adic analysis is in some ways simpler than real analysis, there are relatively neat criteria guaranteeing a root of a polynomial.

Statement

Many equivalent statements of Hensel's lemma exist. Arguably the most common statement is the following.

General statement

Assume $K$ is a field complete with respect to a normalised discrete valuation $v$. Suppose, furthermore, that ${\mathcal {O}}_{K}$ is the ring of integers of $K$ (i.e. all elements of $K$ with non-negative valuation), let $\pi \in K$ be such that $v(\pi )=1$ and let $k={\mathcal {O}}_{K}/\pi {\mathcal {O}}_{K}$ denote the residue field. Let $f(X)\in {\mathcal {O}}_{K}[X]$ be a polynomial with coefficients in ${\mathcal {O}}_{K}$. If the reduction ${\overline {f}}(X)\in k[X]$ has a simple root (i.e. there exists $k_{0}\in k$ such that ${\overline {f}}(k_{0})=0$ and ${\overline {f'}}(k_{0})\neq 0$), then there exists a unique $a\in {\mathcal {O}}_{K}$ such that $f(a)=0$ and the reduction ${\overline {a}}=k_{0}$ in $k$.

Alternative statement

Another way of stating this (in less generality) is: let $f(x)$ be a polynomial with integer (or p-adic integer) coefficients, and let m,k be positive integers such that m ≤ k. If r is an integer such that

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

then there exists an integer s such that

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

Furthermore, this s is unique modulo p^k+m, and can be computed explicitly as the integer such that

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

where $a$ is an integer satisfying

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

Note that $f(r)\equiv 0{\bmod {p}}^{k}$ so that the condition $s\equiv r{\bmod {p}}^{k}$ is met. As an aside, if $f'(r)\equiv 0{\bmod {p}}$, then 0, 1, or several s may exist (see Hensel Lifting below).

Derivation

We use the Taylor expansion of f around r to write:

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

From $r\equiv s{\bmod {p}}^{k},$ we see that s − r = tp^k for some integer t. Let

${\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}}$

For $m\leqslant k,$ we have:

${\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}}$

The assumption that $f'(r)$ is not divisible by p ensures that $f'(r)$ has an inverse mod $p^{m}$ which is necessarily unique. Hence a solution for t exists uniquely modulo $p^{m},$ and s exists uniquely modulo $p^{k+m}.$

Simple statement

For $f\in \mathbb {Z} _{p}[x]$, if there is a solution $a_{0}$ of $f(a_{0})\equiv 0{\bmod {p}}$ and $f'(x)\equiv 0{\bmod {p}}$ has no solutions, then there exists a unique lift $\alpha \in \mathbb {Z} _{p}$ such that $f(\alpha )=0$. Note that given a solution $\alpha \in \mathbb {Z} _{p}$ where $f(\alpha )=0$, its projection to $\mathbb {Z} /p$ gives a solution to $f(\alpha )\equiv 0{\bmod {p}}$, so Hensel's lemma gives a way to take solutions ${\bmod {p}}$ and give a solution in $\mathbb {Z} _{p}$.

Observations

Frobenius

Note that given an $a\in \mathbb {F} _{p}$ the Frobenius endomorphism $(-)\mapsto (-)^{p}$ gives a polynomial $x^{p}-a$ which always has zero derivative

${\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}}$

hence the p-th roots of $a$ do not exist in $\mathbb {Z} _{p}$. For $a=1$, this implies $\mathbb {Z} _{p}$ cannot contain the root of unity $\mu _{p}$.

Roots of unity

Although the $p$-th roots of unity are not contained in $\mathbb {F} _{p}$, there are solutions of $x^{p}-x=x(x^{p-1}-1)$. Note

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

is never zero, so if there exists a solution, it necessarily lifts to $\mathbb {Z} _{p}$. Because the Frobenius gives $a^{p}=a$, all of the non-zero elements $\mathbb {F} _{p}^{\times }$ are solutions. In fact, these are the only roots of unity contained in $\mathbb {Q} _{p}$.

Hensel lifting

Using the lemma, one can "lift" a root r of the polynomial f modulo p^k to a new root s modulo p^k+1 such that r ≡ s mod p^k (by taking m=1; taking larger m follows by induction). In fact, a root modulo p^k+1 is also a root modulo p^k, so the roots modulo p^k+1 are precisely the liftings of roots modulo p^k. The new root s is congruent to r modulo p, so the new root also satisfies $f'(s)\equiv f'(r)\not \equiv 0{\bmod {p}}.$ So the lifting can be repeated, and starting from a solution r_k of $f(x)\equiv 0{\bmod {p}}^{k}$ we can derive a sequence of solutions r_k+1, r_k+2, ... of the same congruence for successively higher powers of p, provided $f'(r_{k})\not \equiv 0{\bmod {p}}$ for the initial root r_k. This also shows that f has the same number of roots mod p^k as mod p^k+1, mod p ^k+2, or any other higher power of p, provided the roots of f mod p^k are all simple.

What happens to this process if r is not a simple root mod p? Suppose

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

Then $s\equiv r{\bmod {p}}^{k}$ implies $f(s)\equiv f(r){\bmod {p}}^{k+1}.$ That is, $f(r+tp^{k})\equiv f(r){\bmod {p}}^{k+1}$ for all integers t. Therefore, we have two cases:

• If $f(r)\not \equiv 0{\bmod {p}}^{k+1}$ then there is no lifting of r to a root of f(x) modulo p^k+1.
• If $f(r)\equiv 0{\bmod {p}}^{k+1}$ then every lifting of r to modulus p^k+1 is a root of f(x) modulo p^k+1.

Example. To see both cases we examine two different polynomials with p = 2:

$f(x)=x^{2}+1$ and r = 1. Then $f(1)\equiv 0{\bmod {2}}$ and $f'(1)\equiv 0{\bmod {2}}.$ We have $f(1)\not \equiv 0{\bmod {4}}$ which means that no lifting of 1 to modulus 4 is a root of f(x) modulo 4.

$g(x)=x^{2}-17$ and r = 1. Then $g(1)\equiv 0{\bmod {2}}$ and $g'(1)\equiv 0{\bmod {2}}.$ However, since $g(1)\equiv 0{\bmod {4}},$ we can lift our solution to modulus 4 and both lifts (i.e. 1, 3) are solutions. The derivative is still 0 modulo 2, so a priori we don't know whether we can lift them to modulo 8, but in fact we can, since g(1) is 0 mod 8 and g(3) is 0 mod 8, giving solutions at 1, 3, 5, and 7 mod 8. Since of these only g(1) and g(7) are 0 mod 16 we can lift only 1 and 7 to modulo 16, giving 1, 7, 9, and 15 mod 16. Of these, only 7 and 9 give g(x) = 0 mod 32, so these can be raised giving 7, 9, 23, and 25 mod 32. It turns out that for every integer k ≥ 3, there are four liftings of 1 mod 2 to a root of g(x) mod 2^k.

Hensel's lemma for p-adic numbers

In the p-adic numbers, where we can make sense of rational numbers modulo powers of p as long as the denominator is not a multiple of p, the recursion from r_k (roots mod p^k) to r_k+1 (roots mod p^k+1) can be expressed in a much more intuitive way. Instead of choosing t to be an(y) integer which solves the congruence

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

let t be the rational number (the p^k here is not really a denominator since f(r_k) is divisible by p^k):

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

Then set

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

This fraction may not be an integer, but it is a p-adic integer, and the sequence of numbers r_k converges in the p-adic integers to a root of f(x) = 0. Moreover, the displayed recursive formula for the (new) number r_k+1 in terms of r_k is precisely Newton's method for finding roots to equations in the real numbers.

By working directly in the p-adics and using the p-adic absolute value, there is a version of Hensel's lemma which can be applied even if we start with a solution of f(a) ≡ 0 mod p such that $f'(a)\equiv 0{\bmod {p}}.$ We just need to make sure the number $f'(a)$ is not exactly 0. This more general version is as follows: if there is an integer a which satisfies:

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

then there is a unique p-adic integer b such f(b) = 0 and $|b-a|_{p}<|f'(a)|_{p}.$ The construction of b amounts to showing that the recursion from Newton's method with initial value a converges in the p-adics and we let b be the limit. The uniqueness of b as a root fitting the condition $|b-a|_{p}<|f'(a)|_{p}$ needs additional work.

The statement of Hensel's lemma given above (taking $m=1$) is a special case of this more general version, since the conditions that f(a) ≡ 0 mod p and $f'(a)\not \equiv 0{\bmod {p}}$ say that $|f(a)|_{p}<1$ and $|f'(a)|_{p}=1.$

Examples

Suppose that p is an odd prime and a is a non-zero quadratic residue modulo p. Then Hensel's lemma implies that a has a square root in the ring of p-adic integers $\mathbb {Z} _{p}.$ Indeed, let $f(x)=x^{2}-a.$ If r is a square root of a modulo p then:

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

where the second condition is dependent on the fact that p is odd. The basic version of Hensel's lemma tells us that starting from r₁ = r we can recursively construct a sequence of integers $\{r_{k}\}$ such that:

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

This sequence converges to some p-adic integer b which satisfies b² = a. In fact, b is the unique square root of a in $\mathbb {Z} _{p}$ congruent to r₁ modulo p. Conversely, if a is a perfect square in $\mathbb {Z} _{p}$ and it is not divisible by p then it is a nonzero quadratic residue mod p. Note that the quadratic reciprocity law allows one to easily test whether a is a nonzero quadratic residue mod p, thus we get a practical way to determine which p-adic numbers (for p odd) have a p-adic square root, and it can be extended to cover the case p = 2 using the more general version of Hensel's lemma (an example with 2-adic square roots of 17 is given later).

To make the discussion above more explicit, let us find a "square root of 2" (the solution to $x^{2}-2=0$) in the 7-adic integers. Modulo 7 one solution is 3 (we could also take 4), so we set $r_{1}=3$. Hensel's lemma then allows us to find $r_{2}$ as follows:

${\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}}$

Based on which the expression

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

turns into:

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

which implies $t=1.$ Now:

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

And sure enough, $10^{2}\equiv 2{\bmod {7}}^{2}.$ (If we had used the Newton method recursion directly in the 7-adics, then $r_{2}=r_{1}-f(r_{1})/f'(r_{1})=3-7/6=11/6,$ and $11/6\equiv 10{\bmod {7}}^{2}.$)

We can continue and find $r_{3}=108=3+7+2\cdot 7^{2}=213_{7}$. Each time we carry out the calculation (that is, for each successive value of k), one more base 7 digit is added for the next higher power of 7. In the 7-adic integers this sequence converges, and the limit is a square root of 2 in $\mathbb {Z} _{7}$ which has initial 7-adic expansion

$3+7+2\cdot 7^{2}+6\cdot 7^{3}+7^{4}+2\cdot 7^{5}+7^{6}+2\cdot 7^{7}+4\cdot 7^{8}+\cdots .$

If we started with the initial choice $r_{1}=4$ then Hensel's lemma would produce a square root of 2 in $\mathbb {Z} _{7}$ which is congruent to 4 (mod 7) instead of 3 (mod 7) and in fact this second square root would be the negative of the first square root (which is consistent with 4 = −3 mod 7).

As an example where the original version of Hensel's lemma is not valid but the more general one is, let $f(x)=x^{2}-17$ and $a=1.$ Then $f(a)=-16$ and $f'(a)=2,$ so

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

which implies there is a unique 2-adic integer b satisfying

$b^{2}=17\quad {\text{and}}\quad |b-a|_{2}<|f'(a)|_{2}={\frac {1}{2}},$

i.e., b ≡ 1 mod 4. There are two square roots of 17 in the 2-adic integers, differing by a sign, and although they are congruent mod 2 they are not congruent mod 4. This is consistent with the general version of Hensel's lemma only giving us a unique 2-adic square root of 17 that is congruent to 1 mod 4 rather than mod 2. If we had started with the initial approximate root a = 3 then we could apply the more general Hensel's lemma again to find a unique 2-adic square root of 17 which is congruent to 3 mod 4. This is the other 2-adic square root of 17.

In terms of lifting the roots of $x^{2}-17$ from modulus 2^k to 2^k+1, the lifts starting with the root 1 mod 2 are as follows:

1 mod 2 --> 1, 3 mod 4

1 mod 4 --> 1, 5 mod 8 and 3 mod 4 ---> 3, 7 mod 8

1 mod 8 --> 1, 9 mod 16 and 7 mod 8 ---> 7, 15 mod 16, while 3 mod 8 and 5 mod 8 don't lift to roots mod 16

9 mod 16 --> 9, 25 mod 32 and 7 mod 16 --> 7, 23 mod 16, while 1 mod 16 and 15 mod 16 don't lift to roots mod 32.

For every k at least 3, there are four roots of x² − 17 mod 2^k, but if we look at their 2-adic expansions we can see that in pairs they are converging to just two 2-adic limits. For instance, the four roots mod 32 break up into two pairs of roots which each look the same mod 16:

9 = 1 + 2³ and 25 = 1 + 2³ + 2⁴.

7 = 1 + 2 + 2² and 23 = 1 + 2 + 2² + 2⁴.

The 2-adic square roots of 17 have expansions

$1+2^{3}+2^{5}+2^{6}+2^{7}+2^{9}+2^{10}+\cdots$

$1+2+2^{2}+2^{4}+2^{8}+2^{11}+\cdots$

Another example where we can use the more general version of Hensel's lemma but not the basic version is a proof that any 3-adic integer c ≡ 1 mod 9 is a cube in $\mathbb {Z} _{3}.$ Let $f(x)=x^{3}-c$ and take initial approximation a = 1. The basic Hensel's lemma cannot be used to find roots of f(x) since $f'(r)\equiv 0{\bmod {3}}$ for every r. To apply the general version of Hensel's lemma we want $|f(1)|_{3}<|f'(1)|_{3}^{2},$ which means $c\equiv 1{\bmod {2}}7.$ That is, if c ≡ 1 mod 27 then the general Hensel's lemma tells us f(x) has a 3-adic root, so c is a 3-adic cube. However, we wanted to have this result under the weaker condition that c ≡ 1 mod 9. If c ≡ 1 mod 9 then c ≡ 1, 10, or 19 mod 27. We can apply the general Hensel's lemma three times depending on the value of c mod 27: if c ≡ 1 mod 27 then use a = 1, if c ≡ 10 mod 27 then use a = 4 (since 4 is a root of f(x) mod 27), and if c ≡ 19 mod 27 then use a = 7. (It is not true that every c ≡ 1 mod 3 is a 3-adic cube, e.g., 4 is not a 3-adic cube since it is not a cube mod 9.)

In a similar way, after some preliminary work, Hensel's lemma can be used to show that for any odd prime number p, any p-adic integer c congruent to 1 modulo p² is a p-th power in $\mathbb {Z} _{p}.$ (This is false for p = 2.)

Generalizations

Suppose A is a commutative ring, complete with respect to an ideal ${\mathfrak {m}},$ and let $f(x)\in A[x].$ a ∈ A is called an "approximate root" of f, if

$f(a)\equiv 0{\bmod {f}}'(a)^{2}{\mathfrak {m}}.$

If f has an approximate root then it has an exact root b ∈ A "close to" a; that is,

$f(b)=0\quad {\text{and}}\quad b\equiv a{\bmod {\mathfrak {m}}}.$

Furthermore, if $f'(a)$ is not a zero-divisor then b is unique.

This result can be generalized to several variables as follows:

Theorem. Let A be a commutative ring that is complete with respect to ideal ${\mathfrak {m}}\subset A.$ Let $f_{1},\ldots ,f_{n}\in A[x_{1},\ldots ,x_{n}]$ be a system of n polynomials in n variables over A. View $\mathbf {f} =(f_{1},\ldots ,f_{n}),$ as a mapping from Aⁿ to itself, and let $J_{\mathbf {f} }(\mathbf {x} )$ denote its Jacobian matrix. Suppose a = (a₁, ..., a_n) ∈ Aⁿ is an approximate solution to f = 0 in the sense that

$f_{i}(\mathbf {a} )\equiv 0{\bmod {(}}\det J_{\mathbf {f} }(a))^{2}{\mathfrak {m}},\qquad 1\leqslant i\leqslant n.$

Then there is some b = (b₁, ..., b_n) ∈ Aⁿ satisfying f(b) = 0, i.e.,

$f_{i}(\mathbf {b} )=0,\qquad 1\leqslant i\leqslant n.$

Furthermore this solution is "close" to a in the sense that

$b_{i}\equiv a_{i}{\bmod {\det }}J_{\mathbf {f} }(a){\mathfrak {m}},\qquad 1\leqslant i\leqslant n.$

As a special case, if $f_{i}(\mathbf {a} )\equiv 0{\bmod {\mathfrak {m}}}$ for all i and $\det J_{\mathbf {f} }(\mathbf {a} )$ is a unit in A then there is a solution to f(b) = 0 with $b_{i}\equiv a_{i}{\bmod {\mathfrak {m}}}$ for all i.

When n = 1, a = a is an element of A and $J_{\mathbf {f} }(\mathbf {a} )=J_{f}(a)=f'(a).$ The hypotheses of this multivariable Hensel's lemma reduce to the ones which were stated in the one-variable Hensel's lemma.

Related concepts

Completeness of a ring is not a necessary condition for the ring to have the Henselian property: Goro Azumaya in 1950 defined a commutative local ring satisfying the Henselian property for the maximal ideal m to be a Henselian ring.

Masayoshi Nagata proved in the 1950s that for any commutative local ring A with maximal ideal m there always exists a smallest ring A^h containing A such that A^h is Henselian with respect to mA^h. This A^h is called the Henselization of A. If A is noetherian, A^h will also be noetherian, and A^h is manifestly algebraic as it is constructed as a limit of étale neighbourhoods. This means that A^h is usually much smaller than the completion  while still retaining the Henselian property and remaining in the same category.

See also

• Hasse–Minkowski theorem
• Newton polygon
• Locally compact field
• Lifting-the-exponent lemma

References

• Eisenbud, David (1995), Commutative algebra, Graduate Texts in Mathematics, vol. 150, Berlin, New York: Springer-Verlag, doi:10.1007/978-1-4612-5350-1, ISBN 978-0-387-94269-8, MR 1322960
• Milne, J. G. (1980), Étale cohomology, Princeton University Press, ISBN 978-0-691-08238-7