Hensel's lemma is a result that stipulates conditions for roots of polynomials modulo powers of primes to be "lifted" to roots modulo higher powers. The lifting method outlined in the proof is reminiscent of Newton's method for solving equations.
The lemma is useful for finding and classifying solutions of polynomial equations modulo powers of primes with a minimum of computational difficulty.
Find all the solutions to mod .
Rather than searching mod , it is easier to build up the solution modulo smaller powers of . First, the square roots of mod are . Now try to find a solution mod
so mod ; so mod . Similarly, starting with yields , so mod .
The key was that when we expanded the square, some of the terms vanished mod in this case , so the resulting equation was linear in .
Next, try to lift these two solutions to solutions mod . Start with
which gives mod , so . Similarly, lifting yields mod , so . So there are two solutions, mod .
The process is straightforward, but it leads to several questions.
Are lifts always guaranteed to exist?
How many lifts can there be?
How many steps are required? The modulus stepped from to to
Does this work for any polynomial equation?
The answers to these questions are contained in the statement of Hensel's lemma.
Let be a polynomial with integer coefficients. Let be a positive integer, and an integer such that mod . Suppose is a positive integer. Then if mod , there is an integer such that mod and mod . So is a "lifting" of to a root mod . Moreover, is unique mod .
The restriction that is not particularly important in practice since the lemma can be applied recursively, to lift a solution to solutions modulo higher and higher powers of . That is, given as in the lemma, with the assumptions in the lemma, there is a unique solution to mod such that mod , for any .
Let and . Note that mod and mod . Then Hensel's lemma implies that there is a unique lift mod such that mod . The proof supplies a formula for computing , but for now we can find by inspection.
The process can be repeated: has a unique lift to a root mod , which turns out to be . The conditions of Hensel's lemma apply indefinitely, so there are unique lifts to a root mod for all .
We can write the solution mod as a series . In the right context, this can be viewed as a kind of power series.
Let and . Then is the unique root of mod , but in fact there are no roots of mod . The conditions of Hensel's lemma are not satisfied because mod .
Note that if and , the root lifts to three different roots mod .
In general, if mod , the lifting behavior of roots congruent to is somewhat unpredictable. Sometimes there are no lifts and sometimes there are multiple lifts.
Let . How many roots does have mod
Both and are roots mod . Since mod , Hensel's lemma immediately implies a unique lift of this root modulo any higher power of .
On the other hand, mod . The next section will discuss what can be done in this situation in general, but for this particular polynomial it is enough to note that and are both mod , so there is no root mod that lifts mod , hence no such roots modulo any higher power.
So the answer is that there is exactly one root mod .
Here is a problem where Hensel's lemma rules out all but a few possibilities, which should be checked in detail:
The polynomial has a Taylor series expansion
Note that this is in fact a finite sum since is a polynomial, so there are no questions of convergence to worry about. Also note that is actually an integer for all use the power rule and the fact that the binomial coefficient is always an integer
Since , all the terms but the first two vanish mod , so
Setting , we can solve for
which gives rise to a unique solution mod . Note that the numerator of this expression is an integer because is divisible by , and the quotient makes sense because has a multiplicative inverse mod ; this is where the assumptions about are being used.
There are stronger versions of Hensel's lemma that can be applied to cases when mod . Here is a more general statement:
Let be a polynomial with integer coefficients. Let be a positive integer, and an integer such that mod , mod . Suppose is a positive integer. Then if mod but mod , then the following holds:
For every positive integer , there is a unique integer such that mod and mod . Also, mod .
Note that may not be congruent to mod ; that is, the original may not lift to a root modulo higher powers. But the theorem says that some congruent to mod will be liftable to a root modulo higher powers.
Let and . Then we can take and . Since as desired, the stronger form of Hensel's lemma applies. Even though mod , there is no lift of to a root mod . But there is a lift of to a root mod and so on. Similarly, note that is a root mod but there is no lift of to a root mod ; but there is a lift of 41...
So the lifting process is more complicated and often requires some "backtracking" in practice when .
Note that the formula for the lift of simplifies to
which is exactly the formula employed in Newton's method for approximating real roots of polynomials. This is not a coincidence!
(The following paragraph can safely be skipped by anyone but the very curious.)
There is a set of -adic integers that is a sort of limit (an "inverse limit") of the sets . Elements of the set can be written as power series of the form where an appropriate topology is put on the set so that is "small" and higher powers of are "smaller" (in the same way that the powers of in typical power series are small). In this context, the process of Hensel lifting is in fact just Newton's method: solutions mod for higher powers of are better and better approximations to a -adic solution.