Tim Boykett asked:
>
> I have been digging around the code for roots of unity in the
> rings Z_n, and have found a technique called the "Newton/Hensel
> method of lifting". Does anyone have a reference that might explain
> the algorithm, proof of its validity, etc.
See the following Math Reviews for entry points into the literature.
There is also a nice treatment in Zippel's text "Effective Polynomial
Computation", Kluwer, 1993.
-Bill Dubuque
------------------------------------------------------------------------------ 85j:12012 12J20 65P05 von zur Gathen, Joachim (3-TRNT-C) Hensel and Newton methods in valuation rings. (English) Math. Comp. 42 (1984), no. 166, 637--661. ------------------------------------------------------------------------------ Hensel's lemma is a fundamental tool in the study of algebraic equations over $p$-adic fields. In the folklore of number theory it has been known for a long time that Hensel's and Newton's method are formally the same (this remark appears in printed form in an article by D. J. Lewis published in a book edited by W. J. LeVeque [Studies in number theory, 25--75, see p. 29, Prentice-Hall, Englewood Cliffs, N.J., 1969; MR 39 #2699]).
A generalized version of Hensel's lemma in suitable valuation rings is
contained in N. Bourbaki's book [Elements of mathematics, 23, Commutative
algebra (French), see Chapter III, Section 4, Theorem 1 and Theorem 2,
Hermann, Paris, 1958; MR 20 #4576].
This paper also deals with the study of Hensel's method in valuation rings and
shows that Newton's method is a special case of Hensel's. The presentation
emphasizes the algorithmic point of view and is very detailed and clear. The
linear and quadratic cases of Hensel's lemma are both given. Newton's method
is applied to systems of nonlinear partial differential equations. Then the
author presents an algorithm for the computation of a shortest nonzero vector
in a non-Archimedean valuation module. These results are applied in the last
section, which contains an algorithm for factoring polynomials over a ring
with valuations.
Reviewed by Maurice Mignotte
------------------------------------------------------------------------------
87a:12014 12J10 13A18
Ribenboim, Paulo (3-QEN)
Equivalent forms of Hensel's lemma. (English)
Exposition. Math. 3 (1985), no. 1, 3--24.
------------------------------------------------------------------------------
>From the introduction: "The celebrated Hensel's lemma, which is the
cornerstone of the theory of $p$-adic numbers, has been the object of
extensive studies. However, our aim in this paper is not to describe the
development of ideas and applications centered around Hensel's lemma, but
rather to examine closely the various formulations found in the literature. We
place ourselves in the framework of the theory of valued fields and show that
Hensel's lemma is logically equivalent to many propositions concerning the
number of extensions of the valuation to algebraic extensions, or the lifting
of polynomials from the residue field, or the determination of zeroes of a
polynomial by a method which dates back to Newton, or even to a geometric
formulation concerning the mutual distance between the zeroes of
polynomials. These facts are of a `folkloric' nature, yet no complete proof of
their equivalence has appeared in any one paper.
"This article is written at the level of research students."
Reviewed by Antonio Jose Engler
------------------------------------------------------------------------------ 90f:68096 68Q40 13A18 13J10 Miola, A. (I-ROME-I); Mora, T. (I-GENO) Constructive lifting in graded structures: a unified view of Buchberger and Hensel methods. (English) Computational aspects of commutative algebra. J. Symbolic Comput. 6 (1988), no. 2-3, 305--322. ------------------------------------------------------------------------------ A graded structure is a filtered commutative ring $A$ which is filtered by a totally ordered group and has a graded associated ring and a ring completion. The authors define a process for solving, in the ring completion, a polynomial multivariate equation over $A$ by successive approximations. They discuss under which conditions this process converges.
The main interest of this theory is that Hensel lifting, Buchberger's
algorithm for Grobner basis computations in polynomial rings and Hironaka's
division process by a standard basis in rings of formal power series are
instances of the above process. For example, Hensel lifting is an
approximative resolution of $yz-a=0$, which needs some conditions on $a$ and
on the initial values of $y$ and $z$ to be convergent.
{For the entire collection see MR 89j:68004}.
Reviewed by Daniel Lazard