Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The Newton Method over $\mathbb{R}$ has the property that the precision is doubled (under some continuous differentialbe assumption) in each iteration. For the ring $\mathbb{Z}_p$ of $p$-adic integers, we also have the Hensel's lemma, but the precision is increase by 1 in each iteration. The proof about the double precision in the case over $\mathbb{R}$ uses the Taylor expansion and its remainder, see http://www.answers.com/topic/newton-s-method#Analysis .

In a special case that is finding square root, one can use $x_{n+1} := \frac{1}{2} x_n - \frac{3}{2} x_n^3 $ ( by considering $x^{-2}-c^{-1}$ instead of $x^2-c$) and one can show that the precision is doubled in the case over $\mathbb{Z}_p$.

In general, is the precision is doubled in each iteration in the case over $\mathbb{Z}_p$, under some conditions?


Sorry, I just fond that in fact the precision is doubled in $p$-adic case, without further assumption. I mentioned the precision increase by 1, since this is written in "A first course in $p$-adic Analysis" by Alain M. Robert.

alt text

But if one examines the proof ,we have $p(\hat{x}) \equiv 0 \ \mathrm{mod} \ p^{n-2k}$. And if $k = 0$, the precision is doubled.

share|improve this question
If I remembered the reference, I would make this an answer. I think it was in a text by Ostrovsky that I saw a proof of Hensel's Lemma that proceeds from a congruence modulo $I$ to a congruence mod $I^2$. I managed to reconstruct for myself what I thought the proof was, but the method is interesting only theoretically, being no good for explicit computation. Maybe someone better informed in the literature than I am can give the reference. –  Lubin Jan 18 '12 at 21:13
A bit late to add to the above comment, but just what “Hensel’s Lemma” refers to, is in a state of confusion. For me, H’s L relates not at all to finding the root of a polynomial but rather to lifting a characteristic-$p$ factorization back to characteristic zero (or the appropriate generalization in the equal-characteristic case). –  Lubin Oct 30 '12 at 2:51
Hensel's lemma can be proved by Newton's method or by the contraction mapping theorem. See Theorem 4.1 in math.uconn.edu/~kconrad/blurbs/gradnumthy/hensel.pdf with different proofs in Sections 5 and 6. In the first proof, the inductively proved bound $|f(a_n)|_p \leq |f'(a_1)|_p^2t^{2^{n-1}}$ where $t = |f(a)/f'(a)^2|_p$ explains why Newton's method doubles the number of correct digits at each step. See Examples 5.1 and 5.2 for explicit doubling, and in Example 6.1 is a comparison of doubling in Newton's method with linear improvements by the contraction mapping iteration. –  KConrad Mar 12 at 18:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.