In
mathematics, Hensel's lemma, also known as Hensel's lifting lemma, named after
Kurt Hensel
Kurt Wilhelm Sebastian Hensel (29 December 1861 – 1 June 1941) was a German mathematician born in Königsberg.
Life and career
Hensel was born in Königsberg, East Prussia (today Kaliningrad, Russia), the son of Julia (née von Adelson) and lan ...
, is a result in
modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his bo ...
, stating that if a
univariate polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An examp ...
has a
simple root
Simple or SIMPLE may refer to:
*Simplicity, the state or quality of being simple
Arts and entertainment
* ''Simple'' (album), by Andy Yorke, 2008, and its title track
* "Simple" (Florida Georgia Line song), 2018
* "Simple", a song by Johnn ...
modulo a
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
, 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
In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common ...
, 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
In mathematics, the inverse limit (also called the projective limit) is a construction that allows one to "glue together" several related objects, the precise gluing process being specified by morphisms between the objects. Thus, inverse limits c ...
) 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
In mathematics, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring properties that are not ...
, 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
In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Peter Gustav Lejeune Dirichlet's 1837 introduction of Diri ...
.
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
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices ...
over the
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ratio ...
s.
Modular reduction and lifting
Hensel's original lemma concerns the relation between
polynomial factorization
In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same dom ...
over the integers and over the integers
modulo a
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
and its powers. It can be straightforwardly extended to the case where the integers are replaced by any
commutative ring
In mathematics, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring properties that are not ...
, and is replaced by any
maximal ideal
In mathematics, more specifically in ring theory, a maximal ideal is an ideal that is maximal (with respect to set inclusion) amongst all ''proper'' ideals. In other words, ''I'' is a maximal ideal of a ring ''R'' if there are no other ideals con ...
(indeed, the maximal ideals of
have the form
where is a prime number).
Making this precise requires a generalization of the usual
modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his bo ...
, 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
In mathematics, a canonical map, also called a natural map, is a map or morphism between objects that arises naturally from the definition or the construction of the objects. Often, it is a map which preserves the widest amount of structure. A c ...
For example, if