Hensel's lemma
Encyclopedia
In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, Hensel's lemma, also known as Hensel's lifting lemma, named after Kurt Hensel
Kurt Hensel
Kurt Wilhelm Sebastian Hensel was a German mathematician born in Königsberg, Prussia.He was the son of the landowner and entrepreneur Sebastian Hensel, brother of the philosopher Paul Hensel, grandson of the composer Fanny Mendelssohn and the painter Wilhelm Hensel, and a descendant of the...

, is a result in modular arithmetic
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....

, stating that if a polynomial equation has a simple root modulo a prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

 , then this root corresponds to a unique root of the same equation modulo any higher power of , which can be found by iteratively "lifting" the solution modulo successive powers of . More generally it is used as a generic name for analogues for complete
Completion (ring theory)
In abstract algebra, a completion is any of several related functors on rings and modules that result in complete topological rings and modules. Completion is similar to localization, and together they are among the most basic tools in analysing commutative rings. Complete commutative rings have...

 commutative ring
Commutative ring
In ring theory, a branch of abstract algebra, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra....

s (including p-adic fields in particular) of the Newton method for solving equations. Since p-adic analysis
P-adic analysis
In mathematics, p-adic analysis is a branch of number theory that deals with the mathematical analysis of functions of p-adic numbers....

 is in some ways simpler than real analysis
Real analysis
Real analysis, is a branch of mathematical analysis dealing with the set of real numbers and functions of a real variable. In particular, it deals with the analytic properties of real functions and sequences, including convergence and limits of sequences of real numbers, the calculus of the real...

, there are relatively neat criteria guaranteeing a root of a polynomial.

Statement

Let be a polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...

 with integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

 (or p-adic integer) coefficients, and let k,m be positive integers such that m ≤ k. If r is an integer such that
and

then there exists an integer s such that
and .

Furthermore, this s is unique modulo pk+m, and can be computed explicitly as
where

In this formula for t, the division by pk denotes ordinary integer division (where the remainder will be 0), while negation, multiplication, and multiplicative inversion are performed in .

As an aside, if , then 0, 1, or several s may exist (see Hensel Lifting
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 , then this root corresponds to a unique root of the same equation modulo any higher power...

 below).

Derivation

The lemma derives from considering the Taylor expansion of f around r. From , we see that s has to be of the form s = r + tpk for some integer t. Expanding gives


Reducing both sides modulo pk+m, we see that for to hold, we need


where the O(p2k) terms vanish because k+m ≤ 2k. Then we note that for some integer z since r is a root of f mod pk, so,
which is to say

Then substituting back f(r)/pk for z and solving for t in gives the explicit formula for t mentioned above. 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 .

Hensel Lifting

Using the lemma, one can "lift" a root r of the polynomial f mod pk to a new root s mod pk+1 (by taking m=1; taking larger m also works). The new root s is congruent to r mod 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 for the initial root rk.

What happens to this process if r is not a simple root mod p? If we have a root mod pk at which the derivative mod p is 0, then there is not a unique lifting of a root mod pk to a root mod pk+1: either there is no lifting to a root mod pk+1 or there are multiple choices:
if and then .


That is, for all integers t.
Therefore if then there is no lifting of r to a root of f(x) mod pk+1, while if then every lifting of r to modulus pk+1 is a root of f(x) mod pk+1.

To see the difficulty that can arise in a concrete example, take p = 2, f(x) = x2 + 1, and r = 1. Then f(1) ≡ 0 mod 2 and f'(1) ≡ 0 mod 2. We have f(1) = 2 ≠ 0 mod 4 and no lifting of 1 to modulus 4 is a root of f(x) mod 4.
On the other hand, if we take f(x) = x2 - 17 and then 1 is a root of f(x) mod 2 and for every positive integer k there is more than one lifting of 1 mod 2 to a root of f(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
, let t be the rational number (the pk here is not really a denominator since f(rk) is divisible by pk). Then set
.


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
Newton's method
In numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley'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) ≡ 0 mod 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)|p2, 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 ) is a special case of this more general version, since the conditions that f(a) ≡ 0 mod p and f'(a) ≠ 0 mod p say that |f(a)|p < 1 and |f'(a)|p = 1.

Examples

Suppose that p is an odd prime number and a is a quadratic residue modulo p that is nonzero mod p. Then Hensel's lemma implies that a has a square root in the ring of p-adic integers Zp. Indeed, let f(x)=x2-a. Its derivative is 2x, so if r is a square root of a mod p we have
and ,


where the second condition depends on p not being 2. The basic version of Hensel's lemma tells us that starting from r1= r we can recursively construct a sequence of integers { rk } such that


This sequence converges to some p-adic integer b and b2=a. In fact, b is the unique square root of a in Zp congruent to r1 modulo p. Conversely, if a is a perfect square in Zp 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:
that is,

And sure enough, . (If we had used the Newton method recursion directly in the 7-adics, then r2 = r1 - f(r1)/f'(r1) = 3 - 7/6 = 11/6, and 11/6 ≡ 10 mod 72.)

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 Z7 which has initial 7-adic expansion


If we started with the initial choice then Hensel's lemma would produce a square root of 2 in Z7 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) = x2 - 17 and a = 1. Then f(a) = -16 and f'(a) = 2, so |f(a)|2 < |f′(a)|22, which implies there is a unique 2-adic integer b satisfying b2 = 17 and |b- a|2 < |f'(a)|2 = 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 roots of x2 - 17 from one modulus 2k to the next 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
1 + 23 + 25 + 26 + 27 + 29 + 210 + ..., 1 + 2 + 22 + 24 + 28 + 211...


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 Z3. Let f(x) = x3 - c and take initial approximation a = 1. The basic Hensel's lemma can't be used to find roots of f(x) since f'(r) ≡ 0 mod 3 for every r. To apply the general version of Hensel's lemma we want |f(1)|3 < |f'(1)|32, which means c ≡ 1 mod 27. 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 which is 1 mod p2 is a p-th power in Zp.
(This is false when p is 2.)

Generalizations

Suppose A is a commutative ring
Commutative ring
In ring theory, a branch of abstract algebra, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra....

, complete with respect to an ideal
Ideal (ring theory)
In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring. The ideal concept allows the generalization in an appropriate way of some important properties of integers like "even number" or "multiple of 3"....

 , and let be a polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...

 with coefficients in A. Then if a ∈ A is an "approximate root" of f in the sense that it satisfies


then there is an exact root b ∈ A of f "close to" a; that is,


and


Further, if f ′(a) is not a zero-divisor then b is unique.

As a special case, if and f ′(a) is a unit in A then there is a unique solution to f(b) = 0 in A such that
This result can be generalized to several variables as follows:

Theorem: Let A be a commutative ring that is complete with respect to an ideal m ⊂ A and
fi(x) ∈ A[x1, …, xn] for i = 1,...,n be a system of n polynomials in n variables over A. Let f = (f1,...,fn), viewed as a mapping from An to An, and let Jf(x) be the Jacobian matrix of f. Suppose some a = (a1, …, an) ∈ An is an approximate solution to f = 0 in the sense that
fi(a) ≡ 0 mod (det Jf(a))2m


for 1 ≤ i ≤ n. Then there is some b = (b1, …, bn) in An satisfying f(b) = 0, i.e.,
fi(b) = 0 for all i,


and furthermore this solution is "close" to a in the sense that
bi ≡ ai mod Jf(a)m


for 1 ≤ i ≤ n.

As a special case, if fi(a) ≡ 0 mod m for all i and det Jf(a) is a unit in A then there is a solution to f(b) = 0 with bi ≡ ai mod m for all i.

When n = 1, a = a is an element of A and Jf(a) = Jf(a) is 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
Goro Azumaya
was a Japanese mathematician who introduced the notion of Azumaya algebra in 1951. His advisor was Shokichi Iyanaga. At the time of his death he was an emeritus professor at Indiana University.-External links:...

 in 1950 defined a commutative local ring
Local ring
In abstract algebra, more particularly in ring theory, local rings are certain rings that are comparatively simple, and serve to describe what is called "local behaviour", in the sense of functions defined on varieties or manifolds, or of algebraic number fields examined at a particular place, or...

 satisfying the Henselian property for the maximal ideal m to be a Henselian ring
Henselian ring
In mathematics, a Henselian ring is a local ring in which Hensel's lemma holds. They were defined by , who named them after Kurt Hensel.Some standard references for Hensel rings are , , and .-Definitions:...

.

Masayoshi Nagata
Masayoshi Nagata
Masayoshi Nagata was a Japanese mathematician, known for his work in the field of commutative algebra....

 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
Noetherian ring
In mathematics, more specifically in the area of modern algebra known as ring theory, a Noetherian ring, named after Emmy Noether, is a ring in which every non-empty set of ideals has a maximal element...

, Ah will also be noetherian, and Ah is manifestly algebraic as it is constructed as a limit of étale neighbourhood
Étale topology
In algebraic geometry, the étale topology is a Grothendieck topology on the category of schemes which has properties similar to the Euclidean topology, but unlike the Euclidean topology, it is also defined in positive characteristic...

s. This means that Ah is usually much smaller than the completion  while still retaining the Henselian property and remaining in the same category
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...

.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK