Newton's method in Q_p, square roots, and building solutions digit by digit
In real analysis, Newton's method refines an approximate root of a polynomial by iterating x → x − f(x)/f'(x). Each step roughly doubles the number of correct decimal digits. Hensel's Lemma is the p-adic analog: if you can find an approximate root modulo p -- that is, some x0 with f(x0) ≡ 0 (mod p) -- and the derivative f'(x0) is non-zero mod p, then you can uniquely "lift" this root one p-adic digit at a time to obtain a true root in the p-adic integers Zp.
This is a remarkable bridge between modular arithmetic and p-adic analysis. A simple computation mod p -- checking whether an equation has a solution and whether the derivative is non-zero -- determines whether a full p-adic solution exists. Each lifting step adds one more digit of precision, building the infinite p-adic expansion of the root.
The condition f'(x0) ≢ 0 (mod p) is essential: it guarantees that at each level, exactly one of the p possible new digits works. When the derivative vanishes mod p (the "singular" case), the lemma does not directly apply, and the situation becomes more subtle -- there may be zero, one, or multiple lifts.
Choose a polynomial and a prime, then watch Newton's method in the p-adic world. Starting from a root mod p, the lifting formula xn+1 = xn − f(xn)/f'(xn) extends the root to higher and higher precision, one digit at a time.
Pick a polynomial and a prime. If a root exists mod p with non-zero derivative, Hensel's Lemma lifts it uniquely to higher p-adic precision, one digit at a time -- just like Newton's method.
2 roots found mod 7: x ≡ 3, 4 (mod 7)
Lifting tree -- each level adds one 7-adic digit (shown left-to-right, most significant first):
Hensel's lifting formula: xn+1 = xn - f(xn) / f'(xn) mod pn+1. This is exactly Newton's method, but convergence in the p-adic metric is guaranteed when f'(x0) ≢ 0 (mod p).
Key insight: Unlike real Newton's method, which only converges under certain conditions, Hensel lifting always works when the initial derivative condition is met. Each step produces exactly one more correct p-adic digit -- the convergence is linear and guaranteed, not approximate.
A fundamental application of Hensel's Lemma: determining which numbers have square roots in which p-adic fields. The answer comes down to quadratic residues -- if a is a square mod p, then Hensel lifts it to a full square root in Zp.
Which primes p allow √a to exist in Qp? If a is a quadratic residue mod p (and p is odd), Hensel's Lemma guarantees √a exists in Zp. Click a green cell to see the square root digits via Hensel lifting.
| a \ p | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 |
|---|---|---|---|---|---|---|---|---|---|
| 2 | |||||||||
| 3 | |||||||||
| 5 | |||||||||
| 6 | |||||||||
| 7 |
Connection to Hensel: For odd primes p, if a is a quadratic residue mod p, then f(x) = x² - a has a root x0 mod p with f'(x0) = 2x0 ≢ 0 (mod p). Hensel's Lemma then lifts this root to a unique square root in Zp. For p = 2, the derivative 2x is always ≡ 0, so we need a stronger condition: a ≡ 1 (mod 8).
Key insight: The real numbers have a simple rule: positive numbers have square roots, negative numbers do not. Each Qp has its own rule based on quadratic residues mod p. The number 2, for instance, has a square root in Q7 (since 3² ≡ 2 mod 7) but not in Q5 (since no square equals 2 mod 5). Different primes "see" different equations as solvable.
Visualize the digit-by-digit construction as a tree. At each level, we try all p possible digits and see which ones extend the solution to one higher power of p. Hensel's Lemma guarantees exactly one digit works per branch.
Solve x² ≡ a (mod pn) one digit at a time. At each level, try all possible new digits d = 0, ..., p-1. Only one digit per branch survives -- the hallmark of Hensel's Lemma.
Roots mod 7: x ≡ 3, 4 (mod 7). These are the starting points for Hensel lifting.
Solution tree -- amber nodes survive, gray nodes are pruned:
Surviving solutions (p-adic digits, least significant first):
Key pattern: At each level, we try 7 possible digits (0 through 6), but exactly one works for each branch. This is the uniqueness guarantee of Hensel's Lemma: when f'(x0) ≢ 0 (mod p), there is a unique lift. The two initial roots mod p give two distinct p-adic square roots, mirroring how √a and -√a are two real square roots.
Key insight: The tree makes visible why Hensel lifting produces a unique solution: at every level, p − 1 of the p candidate digits are pruned, leaving exactly one surviving child per branch. The two initial roots mod p (the two square roots) each grow into their own infinite p-adic expansion -- these are the p-adic analogs of +√a and −√a.