Result in modular arithmetic
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 univariate polynomial has a simple root modulo a prime number p, then this root can be lifted to a unique root modulo any higher power of p. More generally, if a polynomial factors modulo p into two coprime polynomials, this factorization can be lifted to a factorization modulo any higher power of p (the case of roots corresponds to the case of degree 1 for one of the factors).
By passing to the "limit" (in fact this is an inverse limit) when the power of p tends to infinity, it follows that a root or a factorization modulo p can be lifted to a root or a factorization over the p-adic integers.
These results have been widely generalized, under the same name, to the case of polynomials over an arbitrary commutative ring, where p is replaced by an ideal, and "coprime polynomials" means "polynomials that generate an ideal containing 1".
Hensel's lemma is fundamental in p-adic analysis, a branch of analytic number theory.
The proof of Hensel's lemma is constructive, and leads to an efficient algorithm for Hensel lifting, which is fundamental for factoring polynomials, and gives the most efficient known algorithm for exact linear algebra over the rational numbers.
Modular reduction and lifting
Hensel's original lemma concerns the relation between polynomial factorization over the integers and over the integers modulo a prime number p and its powers. It can be straightforwardly extended to the case where the integers are replaced by any commutative ring, and p is replaced by any maximal ideal (indeed, the maximal ideals of
have the form
where p is a prime number).
Making this precise requires a generalization of the usual modular arithmetic, and so it is useful to define accurately the terminology that is commonly used in this context.
Let R be a commutative ring, and I an ideal of R. Reduction modulo I refers to the replacement of every element of R by its image under the canonical map
For example, if
is a polynomial with coefficients in R, its reduction modulo I, denoted
is the polynomial in
obtained by replacing the coefficients of f by their image in
Two polynomials f and g in
are congruent modulo I, denoted
if they have the same coefficients modulo I, that is if
If
a factorization of h modulo I consists in two (or more) polynomials f, g in
such that ![{\textstyle h\equiv fg{\pmod {I}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
The lifting process is the inverse of reduction. That is, given objects depending on elements of
the lifting process replaces these elements by elements of
(or of
for some k > 1) that maps to them in a way that keeps the properties of the objects.
For example, given a polynomial
and a factorization modulo I expressed as
lifting this factorization modulo
consists of finding polynomials
such that
and
Hensel's lemma asserts that such a lifting is always possible under mild conditions; see next section.
Statement
Originally, Hensel's lemma was stated (and proved) for lifting a factorization modulo a prime number p of a polynomial over the integers to a factorization modulo any power of p and to a factorization over the p-adic integers. This can be generalized easily, with the same proof to the case where the integers are replaced by any commutative ring, the prime number is replaced by a maximal ideal, and the p-adic integers are replaced by the completion with respect to the maximal ideal. It is this generalization, which is also widely used, that is presented here.
Let
be a maximal ideal of a commutative ring R, and
![{\displaystyle h=\alpha _{0}X^{n}+\cdots +\alpha _{n-1}X+\alpha _{n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
be a polynomial in
with a leading coefficient
not in ![{\displaystyle {\mathfrak {m}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Since
is a maximal ideal, the quotient ring
is a field, and
is a principal ideal domain, and, in particular, a unique factorization domain, which means that every nonzero polynomial in
can be factorized in a unique way as the product of a nonzero element of
and irreducible polynomials that are monic (that is, their leading coefficients are 1).
Hensel's lemma asserts that every factorization of h modulo
into coprime polynomials can be lifted in a unique way into a factorization modulo
for every k.
More precisely, with the above hypotheses, if
where f and g are monic and coprime modulo
then, for every positive integer k there are monic polynomials
and
such that
![{\displaystyle {\begin{aligned}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{aligned}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
and
and
are unique (with these properties) modulo ![{\displaystyle {\mathfrak {m}}^{k}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Lifting simple roots
An important special case is when
In this case the coprimality hypothesis means that r is a simple root of
This gives the following special case of Hensel's lemma, which is often called also Hensel's lemma.
With above hypotheses and notations, if r is a simple root of
then r can be lifted in a unique way to a simple root of
for every positive integer n. Explicitly, for every positive integer n, there is a unique
such that
and
is a simple root of ![{\displaystyle h{\bmod {\mathfrak {m}}}^{n}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Lifting to adic completion
The fact that one can lift to
for every positive integer n suggests to "pass to the limit" when n tends to the infinity. This was one of the main motivations for introducing p-adic integers.
Given a maximal ideal
of a commutative ring R, the powers of
form a basis of open neighborhoods for a topology on R, which is called the
-adic topology. The completion of this topology can be identified with the completion of the local ring
and with the inverse limit
This completion is a complete local ring, generally denoted
When R is the ring of the integers, and
where p is a prime number, this completion is the ring of p-adic integers ![{\displaystyle \mathbb {Z} _{p}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
The definition of the completion as an inverse limit, and the above statement of Hensel's lemma imply that every factorization into pairwise coprime polynomials modulo
of a polynomial
can be uniquely lifted to a factorization of the image of h in
Similarly, every simple root of h modulo
can be lifted to a simple root of the image of h in ![{\displaystyle {\widehat {R}}_{\mathfrak {m}}[X].}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Proof
Hensel's lemma is generally proved incrementally by lifting a factorization over
to either a factorization over
(Linear lifting), or a factorization over
(Quadratic lifting).
The main ingredient of the proof is that coprime polynomials over a field satisfy Bézout's identity. That is, if f and g are coprime univariate polynomials over a field (here
), there are polynomials a and b such that
and
![{\displaystyle af+bg=1.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Bézout's identity allows defining coprime polynomials and proving Hensel's lemma, even if the ideal
is not maximal. Therefore, in the following proofs, one starts from a commutative ring R, an ideal I, a polynomial
that has a leading coefficient that is invertible modulo I (that is its image in
is a unit in
), and factorization of h modulo I or modulo a power of I, such that the factors satisfy a Bézout's identity modulo I. In these proofs,
means ![{\displaystyle A-B\in IR[X].}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Linear lifting
Let I be an ideal of a commutative ring R, and
be a univariate polynomial with coefficients in R that has a leading coefficient
that is invertible modulo I (that is, the image of
in
is a unit in
).
Suppose that for some positive integer k there is a factorization
![{\displaystyle h\equiv \alpha fg{\pmod {I^{k}}},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
such that f and g are monic polynomials that are coprime modulo I, in the sense that there exist
such that
Then, there are polynomials
such that
and
![{\displaystyle h\equiv \alpha (f+\delta _{f})(g+\delta _{g}){\pmod {I^{k+1}}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Under these conditions,
and
are unique modulo ![{\displaystyle I^{k+1}R[X].}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Moreover,
and
satisfy the same Bézout's identity as f and g, that is,
This follows immediately from the preceding assertions, but is needed to apply iteratively the result with increasing values of k.
The proof that follows is written for computing
and
by using only polynomials with coefficients in
or
When
and
this allows manipulating only integers modulo p.
Proof: By hypothesis,
is invertible modulo I. This means that there exists
and
such that
Let
of degree less than
such that
![{\displaystyle \delta _{h}\equiv h-\alpha fg{\pmod {I^{k+1}}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
(One may choose
but other choices may lead to simpler computations. For example, if
and
it is possible and better to choose
where the coefficients of
are integers in the interval
)
As g is monic, the Euclidean division of
by g is defined, and provides q and c such that
and
Moreover, both q and c are in
Similarly, let
with
and
One has
Indeed, one has
![{\displaystyle fc+gd=af\delta _{h}+bg\delta _{h}-fg(q+q')\equiv \delta _{h}-fg(q+q'){\pmod {I^{k+1}}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
As
is monic, the degree modulo
of
can be less than
only if ![{\displaystyle q+q'\in I^{k+1}R[X].}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Thus, considering congruences modulo
one has
![{\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}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
So, the existence assertion is verified with
![{\displaystyle \delta _{f}=\beta d,\qquad \delta _{g}=\beta c.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Uniqueness
Let R, I, h and
as a in the preceding section. Let
![{\displaystyle h\equiv \alpha fg{\pmod {I}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
be a factorization into coprime polynomials (in the above sense), such
The application of linear lifting for
shows the existence of
and
such that
and
![{\displaystyle h\equiv \alpha (f+\delta _{f})(g+\delta _{g}){\pmod {I^{n}}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
The polynomials
and
are uniquely defined modulo
This means that, if another pair
satisfies the same conditions, then one has
![{\displaystyle \delta '_{f}\equiv \delta _{f}{\pmod {I^{n}}}\qquad {\text{and}}\qquad \delta '_{g}\equiv \delta _{g}{\pmod {I^{n}}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Proof: Since a congruence modulo
implies the same concruence modulo
one can proceed by induction and suppose that the uniqueness has been proved for n − 1, the case n = 0 being trivial. That is, one can suppose that
![{\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].}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
By hypothesis, has
![{\displaystyle h\equiv \alpha (f+\delta _{f})(g+\delta _{g})\equiv \alpha (f+\delta '_{f})(g+\delta '_{g}){\pmod {I^{n}}},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
and thus
![{\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}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
By induction hypothesis, the second term of the latter sum belongs to
and the same is thus true for the first term. As
is invertible modulo I, there exist
and
such that
Thus
![{\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}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
using the induction hypothesis again.
The coprimality modulo I implies the existence of
such that
Using the induction hypothesis once more, one gets
![{\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}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Thus one has a polynomial of degree less than
that is congruent modulo
to the product of the monic polynomial g and another polynomial w. This is possible only if
and implies
Similarly,
is also in
and this proves the uniqueness.
Quadratic lifting
Linear lifting allows lifting a factorization modulo
to a factorization modulo
Quadratic lifting allows lifting directly to a factorization modulo
at the cost of lifting also the Bézout's identity and of computing modulo
instead of modulo I (if one uses the above description of linear lifting).
For lifting up to modulo
for large N one can use either method. If, say,
a factorization modulo
requires N − 1 steps of linear lifting or only k − 1 steps of quadratic lifting. However, in the latter case the size of the coefficients that have to be manipulated increase during the computation. This implies that the best lifting method depends on the context (value of N, nature of R, multiplication algorithm that is used, hardware specificities, etc.).[citation needed]
Quadratic lifting is based on the following property.
Suppose that for some positive integer k there is a factorization
![{\displaystyle h\equiv \alpha fg{\pmod {I^{k}}},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
such that f and g are monic polynomials that are coprime modulo I, in the sense that there exist
such that
Then, there are polynomials
such that
and
![{\displaystyle h\equiv \alpha (f+\delta _{f})(g+\delta _{g}){\pmod {I^{2k}}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Moreover,
and
satisfy a Bézout's identity of the form
![{\displaystyle (a+\delta _{a})(f+\delta _{f})+(b+\delta _{b})(g+\delta _{g})\equiv 1{\pmod {I^{2k}}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
(This is required for allowing iterations of quadratic lifting.)
Proof: The first assertion is exactly that of linear lifting applied with k = 1 to the ideal
instead of ![{\displaystyle I.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Let
One has
![{\displaystyle a(f+\delta _{f})+b(g+\delta _{g})=1+\Delta ,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
where
![{\displaystyle \Delta =\alpha +a\delta _{f}+b\delta _{g}\in I^{k}R[X].}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Setting
and
one gets
![{\displaystyle (a+\delta _{a})(f+\delta _{f})+(b+\delta _{b})(g+\delta _{g})=1-\Delta ^{2}\in I^{2k}R[X],}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
which proves the second assertion.
Explicit example
Let ![{\displaystyle f(X)=X^{6}-2\in \mathbb {Q} [X].}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Modulo 2, Hensel's lemma cannot be applied since the reduction of
modulo 2 is simply[1]pg 15-16
![{\displaystyle {\bar {f}}(X)=X^{6}-{\overline {2}}=X^{6}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
with 6 factors
not being relatively prime to each other. By Eisenstein's criterion, however, one can conclude that the polynomial
is irreducible in ![{\displaystyle \mathbb {Q} _{2}[X].}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Over
, on the other hand, one has
![{\displaystyle {\bar {f}}(X)=X^{6}-{\overline {2}}=X^{6}-{\overline {16}}=(X^{3}-{\overline {4}})\;(X^{3}+{\overline {4}})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
where
is the square root of 2 in
. As 4 is not a cube in
these two factors are irreducible over
. Hence the complete factorization of
in
and
is
![{\displaystyle f(X)=X^{6}-2=(X^{3}-\alpha )\;(X^{3}+\alpha ),}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
where
is a square root of 2 in
that can be obtained by lifting the above factorization.
Finally, in
the polynomial splits into
![{\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}})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
with all factors relatively prime to each other, so that in
and
there are 6 factors
with the (non-rational) 727-adic integers
![{\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.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Using derivatives for lifting roots
Let
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
![{\displaystyle f(r)\equiv 0{\bmod {p}}^{k}\quad {\text{and}}\quad f'(r)\not \equiv 0{\bmod {p}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
then, for every
there exists an integer s such that
![{\displaystyle f(s)\equiv 0{\bmod {p}}^{k+m}\quad {\text{and}}\quad r\equiv s{\bmod {p}}^{k}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Furthermore, this s is unique modulo pk+m, and can be computed explicitly as the integer such that
![{\displaystyle s=r-f(r)\cdot a,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
where
is an integer satisfying
![{\displaystyle a\equiv [f'(r)]^{-1}{\bmod {p}}^{m}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Note that
so that the condition
is met. As an aside, if
, then 0, 1, or several s may exist (see Hensel Lifting below).
Derivation
We use the Taylor expansion of f around r to write:
![{\displaystyle f(s)=\sum _{n=0}^{N}c_{n}(s-r)^{n},\qquad c_{n}=f^{(n)}(r)/n!.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
From
we see that s − r = tpk for some integer t. Let
![{\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}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
For
we have:
![{\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}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
The assumption that
is not divisible by p ensures that
has an inverse mod
which is necessarily unique. Hence a solution for t exists uniquely modulo
and s exists uniquely modulo ![{\displaystyle p^{k+m}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Observations
Criterion for irreducible polynomials
Using the above hypotheses, if we consider an irreducible polynomial
![{\displaystyle f(x)=a_{0}+a_{1}x+\cdots +a_{n}x^{n}\in K[X]}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
such that
, then
![{\displaystyle |f|=\max\{|a_{0}|,|a_{n}|\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
In particular, for
, we find in ![{\displaystyle \mathbb {Q} _{2}[X]}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\begin{aligned}|f(X)|&=\max\{|a_{0}|,\ldots ,|a_{n}|\}\\&=\max\{0,1,0\}=1\end{aligned}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
but
, hence the polynomial cannot be irreducible. Whereas in
we have both values agreeing, meaning the polynomial could be irreducible. In order to determine irreducibility, the Newton polygon must be employed.[2]: 144
Frobenius
Note that given an
the Frobenius endomorphism
gives a nonzero polynomial
that has zero derivative
![{\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}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
hence the pth roots of
do not exist in
. For
, this implies that
cannot contain the root of unity
.
Roots of unity
Although the pth roots of unity are not contained in
, there are solutions of
. Note that
![{\displaystyle {\begin{aligned}{\frac {d}{dx}}(x^{p}-x)&=px^{p-1}-1\\&\equiv -1{\bmod {p}}\end{aligned}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
is never zero, so if there exists a solution, it necessarily lifts to
. Because the Frobenius gives
all of the non-zero elements
are solutions. In fact, these are the only roots of unity contained in
.[3]
Hensel lifting
Using the lemma, one can "lift" a root r of the polynomial f modulo pk to a new root s modulo pk+1 such that r ≡ s mod pk (by taking m = 1; taking larger m follows by induction). In fact, a root modulo pk+1 is also a root modulo pk, so the roots modulo pk+1 are precisely the liftings of roots modulo pk. The new root s is congruent to r modulo p, so the new root also satisfies
So the lifting can be repeated, and starting from a solution rk of
we can derive a sequence of solutions rk+1, rk+2, ... of the same congruence for successively higher powers of p, provided that
for the initial root rk. This also shows that f has the same number of roots mod pk as mod pk+1, mod pk+2, or any other higher power of p, provided that the roots of f mod pk are all simple.
What happens to this process if r is not a simple root mod p? Suppose that
![{\displaystyle f(r)\equiv 0{\bmod {p}}^{k}\quad {\text{and}}\quad f'(r)\equiv 0{\bmod {p}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Then
implies
That is,
for all integers t. Therefore, we have two cases:
- If
then there is no lifting of r to a root of f(x) modulo pk+1. - If
then every lifting of r to modulus pk+1 is a root of f(x) modulo pk+1.
Example. To see both cases we examine two different polynomials with p = 2:
and r = 1. Then
and
We have
which means that no lifting of 1 to modulus 4 is a root of f(x) modulo 4.
and r = 1. Then
and
However, since
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 2k.
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 rk (roots mod pk) to rk+1 (roots mod pk+1) can be expressed in a much more intuitive way. Instead of choosing t to be an(y) integer which solves the congruence
![{\displaystyle tf'(r_{k})\equiv -(f(r_{k})/p^{k}){\bmod {p}}^{m},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
let t be the rational number (the pk here is not really a denominator since f(rk) is divisible by pk):
![{\displaystyle -(f(r_{k})/p^{k})/f'(r_{k}).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Then set
![{\displaystyle r_{k+1}=r_{k}+tp^{k}=r_{k}-{\frac {f(r_{k})}{f'(r_{k})}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
This fraction may not be an integer, but it is a p-adic integer, and the sequence of numbers rk converges in the p-adic integers to a root of f(x) = 0. Moreover, the displayed recursive formula for the (new) number rk+1 in terms of rk 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
We just need to make sure the number
is not exactly 0. This more general version is as follows: if there is an integer a which satisfies:
![{\displaystyle |f(a)|_{p}<|f'(a)|_{p}^{2},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
then there is a unique p-adic integer b such f(b) = 0 and
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
needs additional work.
The statement of Hensel's lemma given above (taking
) is a special case of this more general version, since the conditions that f(a) ≡ 0 mod p and
say that
and ![{\displaystyle |f'(a)|_{p}=1.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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
Indeed, let
If r is a square root of a modulo p then:
![{\displaystyle f(r)=r^{2}-a\equiv 0{\bmod {p}}\quad {\text{and}}\quad f'(r)=2r\not \equiv 0{\bmod {p}},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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 r1 = r we can recursively construct a sequence of integers
such that:
![{\displaystyle r_{k+1}\equiv r_{k}{\bmod {p}}^{k},\quad r_{k}^{2}\equiv a{\bmod {p}}^{k}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
This sequence converges to some p-adic integer b which satisfies b2 = a. In fact, b is the unique square root of a in
congruent to r1 modulo p. Conversely, if a is a perfect square in
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
) in the 7-adic integers. Modulo 7 one solution is 3 (we could also take 4), so we set
. Hensel's lemma then allows us to find
as follows:
![{\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}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Based on which the expression
![{\displaystyle tf'(r_{1})\equiv -(f(r_{1})/p^{k}){\bmod {p}},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
turns into:
![{\displaystyle t\cdot 6\equiv -1{\bmod {7}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
which implies
Now:
![{\displaystyle r_{2}=r_{1}+tp^{1}=3+1\cdot 7=10=13_{7}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
And sure enough,
(If we had used the Newton method recursion directly in the 7-adics, then
and
)
We can continue and find
. 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
which has initial 7-adic expansion
![{\displaystyle 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 .}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
If we started with the initial choice
then Hensel's lemma would produce a square root of 2 in
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
and
Then
and
so
![{\displaystyle |f(a)|_{2}<|f'(a)|_{2}^{2},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
which implies there is a unique 2-adic integer b satisfying
![{\displaystyle b^{2}=17\quad {\text{and}}\quad |b-a|_{2}<|f'(a)|_{2}={\frac {1}{2}},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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
from modulus 2k to 2k+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 x2 − 17 mod 2k, 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 + 23 and 25 = 1 + 23 + 24.
- 7 = 1 + 2 + 22 and 23 = 1 + 2 + 22 + 24.
The 2-adic square roots of 17 have expansions
![{\displaystyle 1+2^{3}+2^{5}+2^{6}+2^{7}+2^{9}+2^{10}+\cdots }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle 1+2+2^{2}+2^{4}+2^{8}+2^{11}+\cdots }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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
Let
and take initial approximation a = 1. The basic Hensel's lemma cannot be used to find roots of f(x) since
for every r. To apply the general version of Hensel's lemma we want
which means
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 p2 is a p-th power in
(This is false for p = 2.)
Generalizations
Suppose A is a commutative ring, complete with respect to an ideal
and let
a ∈ A is called an "approximate root" of f, if
![{\displaystyle f(a)\equiv 0{\bmod {f}}'(a)^{2}{\mathfrak {m}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
If f has an approximate root then it has an exact root b ∈ A "close to" a; that is,
![{\displaystyle f(b)=0\quad {\text{and}}\quad b\equiv a{\bmod {\mathfrak {m}}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Furthermore, if
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
Let
be a system of n polynomials in n variables over A. View
as a mapping from An to itself, and let
denote its Jacobian matrix. Suppose a = (a1, ..., an) ∈ An is an approximate solution to f = 0 in the sense that
![{\displaystyle f_{i}(\mathbf {a} )\equiv 0{\bmod {(}}\det J_{\mathbf {f} }(a))^{2}{\mathfrak {m}},\qquad 1\leqslant i\leqslant n.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Then there is some b = (b1, ..., bn) ∈ An satisfying f(b) = 0, i.e.,
![{\displaystyle f_{i}(\mathbf {b} )=0,\qquad 1\leqslant i\leqslant n.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Furthermore this solution is "close" to a in the sense that
![{\displaystyle b_{i}\equiv a_{i}{\bmod {\det }}J_{\mathbf {f} }(a){\mathfrak {m}},\qquad 1\leqslant i\leqslant n.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
As a special case, if
for all i and
is a unit in A then there is a solution to f(b) = 0 with
for all i.
When n = 1, a = a is an element of A and
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 Ah containing A such that Ah is Henselian with respect to mAh. This Ah is called the Henselization of A. If A is noetherian, Ah will also be noetherian, and Ah is manifestly algebraic as it is constructed as a limit of étale neighbourhoods. This means that Ah is usually much smaller than the completion  while still retaining the Henselian property and remaining in the same category[clarification needed].
See also
References
- ^ Gras, Georges (2003). Class field theory : from theory to practice. Berlin. ISBN 978-3-662-11323-3. OCLC 883382066.
{{cite book}}
: CS1 maint: location missing publisher (link) - ^ Neukirch, Jürgen (1999). Algebraic Number Theory. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 978-3-662-03983-0. OCLC 851391469.
- ^ Conrad, Keith. "Hensel's Lemma" (PDF). p. 4.
- 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