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 univariate polynomial has a simple root modulo a prime number, then this root can be lifted to a unique root modulo any higher power of. More generally, if a polynomial factors modulo into two coprime polynomials, this factorization can be lifted to a factorization modulo any higher power of .
By passing to the "limit" when the power of tends to infinity, it follows that a root or a factorization modulo can be lifted to a root or a factorization over the -adic integers.
These results have been widely generalized, under the same name, to the case of polynomials over an arbitrary commutative ring, where is replaced by an ideal, and "coprime polynomials" means "polynomials that generate an ideal containing ".
Hensel's lemma is fundamental in -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 and its powers. It can be straightforwardly extended to the case where the integers are replaced by any commutative ring, and is replaced by any maximal ideal.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 be a commutative ring, and an ideal of. Reduction modulo refers to the replacement of every element of by its image under the canonical map For example, if is a polynomial with coefficients in, its reduction modulo, denoted is the polynomial in obtained by replacing the coefficients of by their image in Two polynomials and in are congruent modulo, denoted if they have the same coefficients modulo, that is if If a factorization of modulo consists in two polynomials in such that
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 that maps to them in a way that keeps the properties of the objects.
For example, given a polynomial and a factorization modulo 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 for lifting a factorization modulo a prime number of a polynomial over the integers to a factorization modulo any power of and to a factorization over the -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 -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, and
be a polynomial in with a leading coefficient not in
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.
Hensel's lemma asserts that every factorization of modulo into coprime polynomials can be lifted in a unique way into a factorization modulo for every.
More precisely, with the above hypotheses, if where and are monic and coprime modulo then, for every positive integer there are monic polynomials and such that
and and are unique modulo
Lifting simple roots
An important special case is when In this case the coprimality hypothesis means that is a simple root of This gives the following special case of Hensel's lemma, which is often also called Hensel's lemma.With above hypotheses and notations, if is a simple root of then can be lifted in a unique way to a simple root of for every positive integer. Explicitly, for every positive integer, there is a unique such that and is a simple root of
Lifting to adic completion
The fact that one can lift to for every positive integer suggests to "pass to the limit" when tends to the infinity. This was one of the main motivations for introducing -adic integers.Given a maximal ideal of a commutative ring, the powers of form a basis of open neighborhoods for a topology on, 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 is the ring of the integers, and where is a prime number, this completion is the ring of -adic integers
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 in Similarly, every simple root of modulo can be lifted to a simple root of the image of in
Proof
Hensel's lemma is generally proved incrementally by lifting a factorization over to either a factorization over , or a factorization over .The main ingredient of the proof is that coprime polynomials over a field satisfy Bézout's identity. That is, if and are coprime univariate polynomials over a field, there are polynomials and such that and
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, an ideal, a polynomial that has a leading coefficient that is invertible modulo , and factorization of modulo or modulo a power of, such that the factors satisfy a Bézout's identity modulo. In these proofs, means
[|Linear lifting]
Let be an ideal of a commutative ring, and be a univariate polynomial with coefficients in that has a leading coefficient that is invertible modulo .Suppose that for some positive integer there is a factorization
such that and are monic polynomials that are coprime modulo, in the sense that there exist such that Then, there are polynomials such that and
Under these conditions, and are unique modulo
Moreover, and satisfy the same Bézout's identity as and, that is, This follows immediately from the preceding assertions, but is needed to apply iteratively the result with increasing values of.
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.
Proof: By hypothesis, is invertible modulo. This means that there exists and such that
Let of degree less than such that
(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 is monic, the Euclidean division of by is defined, and provides and such that and Moreover, both and are in Similarly, let with and
One has Indeed, one has
As is monic, the degree modulo of can be less than only if
Thus, considering congruences modulo one has
So, the existence assertion is verified with
Uniqueness
Let,, and as a in the preceding section. Letbe a factorization into coprime polynomials, such The application of linear lifting for shows the existence of and such that and
The polynomials and are uniquely defined modulo This means that, if another pair satisfies the same conditions, then one has
Proof: Since a congruence modulo implies the same congruence modulo one can proceed by induction and suppose that the uniqueness has been proved for, the case being trivial. That is, one can suppose that
By hypothesis, has
and thus
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, there exist and such that Thus
using the induction hypothesis again.
The coprimality modulo implies the existence of such that Using the induction hypothesis once more, one gets
Thus one has a polynomial of degree less than that is congruent modulo to the product of the monic polynomial and another polynomial. 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 .For lifting up to modulo for large one can use either method. If, say, a factorization modulo requires steps of linear lifting or only 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.
Quadratic lifting is based on the following property.
Suppose that for some positive integer there is a factorization
such that and are monic polynomials that are coprime modulo, in the sense that there exist such that Then, there are polynomials such that and
Moreover, and satisfy a Bézout's identity of the form
Proof: The first assertion is exactly that of linear lifting applied with to the ideal instead of
Let One has
where
Setting and one gets
which proves the second assertion.