> ^ From:

< ^ Subject:

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

> < [top]