Hensel lifting

If we have some polynomial $f$ and $x$ such that

$f(x_0) = 0 \; mod \; p$

and $f'(x_0) \neq 0 \; mod \; p$, we can find $x_1$ such that

$f(x_1) = 0 \; mod \; p^2$

We use the Newton’s method (opens new window), which relies on the Taylor series:

$f(x_0 + k p) = f(x_0) + k p f'(x_0) + (k p)^2 \frac{f''(x_0)}{2} + ...$

Now, using $k p$ as a small value might seem strange, right? Well, we are using p-adic numbers here. A great resource on p-adic numbers is p-adic numbers and Diophantine equations (opens new window) by Yuri Bilu. The p-adic numbers are an extension of the rational numbers, distinct from the real numbers. The distinction arises from how we measure the distance between the numbers.

To understand how the distance between $x$ and $y$ is defined, let’s first see how the length of $x$ is determined. The length of $x$ is $p^{-k}$, where $k$ is the highest power of $p$ such that $p^k | x$.

The distance between $x$ and $y$ is defined as the length of $x-y$.

We write a p-adic number as a series. For example, let’s say

$x = a_0 + a_1 p + a_2 p^2 + ...$

If $a_0 = 0$ and $a_1 \neq 0$, we have $|x| = p^{-1}$.

If $a_0 = 0, a_1 = 0$, and $a_2 \neq 0$, then $|x| = p^{-2}$.

So, using $k p$ and $(k p)^2$ in the Taylor series actually makes sense. The beauty of p-adic numbers is that we still have the analysis and topology tools at our disposal. While the metric is different, we can still utilize derivatives and the Taylor series, for instance.

Back to our original problem—let’s find $x_1$ such that $f(x_1) = 0 \; mod \; p^2$.

We can see:

$f(x_0 + k p) = f(x_0) + k p f'(x_0) \; mod \; p^2$

We set $k$:

$k = - \frac{f(x_0)}{p f'(x_0)}$

Now we have $f(x_0 + k p) = 0 \; mod \; p^2$.