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 (the case of roots corresponds to the case of degree for one of the factors).
By passing to the "limit" (in fact this is an inverse 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 (indeed, the maximal ideals of have the form where 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 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 (or more) 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 (or of for some ) 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 (and proved) 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 (that is, their leading coefficients are 1).
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 (with these properties) 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 called also Hensel's lemma.