Solving $p$-adic polynomial equations using Jarratt’s Method

Solving polynomial equations is one of the oldest problems in mathematics which dates back to the Babylonians. There are several analytic, algebraic and geometric approaches for finding roots of polynomials. In this paper we discuss an iterative method to approximate solutions of polynomial equations of the form $f(x)=0$ in the $p$-adic numbers, where $f\in\mathbb{Z}_{p}[x]$.

Well-known numerical methods to approximate roots of functions on the real numbers are Newton’s Method, Olver’s Method [8], Halley’s method [3] and others. In this paper, we look at a method developed by P. Jarratt in 1966 [5]. This method has a higher order of convergence than all of the afore-mentioned methods. We set up a $p$-adic analogue of Jarratt’s method. Analogues of Olver’s and Halley’s method in the $p$-adic setting have previously been established by J.F.T. Rabago [9]. Apart from improving the order of convergence, we also weaken the initial conditions in Rabago’s work. Below is a definition of the term “order of convergence” for general Banach spaces, including the complete valued fields $\mathbb{R}$ and $\mathbb{Q}_{p}$.

Before turning to Jarret’s method, let us briefly review Newton’s and Olver’s methods in the context of $p$-adic numbers. Suppose $p$ is a prime and let $f(x)\in\mathbb{Z}_{p}[x]$ be a polynomial. Throughout the sequel, we assume the leading coefficient of $f$ to be a unit in $\mathbb{Z}_{p}$. Then all solutions of $f$ in $\mathbb{Q}_{p}$ lie in $\mathbb{Z}_{p}$. Assume that $x_{1}\in\mathbb{Z}_{p}$ such that $f(x_{1})\equiv 0\bmod{p}$ but $f^{\prime}(x_{1})\not\equiv 0\bmod{p}$. Newton’s method uses the iteration

which yields a sequence in $\mathbb{Z}_{p}$ which converges to a simple root of $f$ in $\mathbb{Z}_{p}$. In the case when $f\in\mathbb{Z}[x]$, this provides a convenient proof of Hensel’s lemma which, for all $m\in\mathbb{N}$, asserts that a solution $x_{1}\in\mathbb{Z}$ of the congruence $f(x_{1})\equiv 0\bmod{p}$ satisfying $f^{\prime}(x_{1})\not\equiv 0\bmod{p}$ can be uniquely lifted to a root $x$ of the congruence $f(x)\equiv 0\bmod{p^{m}}$. In fact, one may replace the condition $f^{\prime}(x_{1})\not\equiv 0\bmod{p}$ by the weaker condition

which leads to a generalized version of Hensel’s lemma (see [6]). The order of convergence of Newton’s method is 2.

Olver’s method, an iteration with higher order of convergence, was carried over to $p$-adic numbers by J.F.T. Rabago in 2016 [9]. He proved that if $f(x)\in\mathbb{Z}_{p}[x]$ and if $x_{1}\in\mathbb{Z}$ satisfies $f(x_{1})\equiv 0\bmod{p}$ and $f^{\prime}(x_{1})\not\equiv 0\bmod{p}$, then the sequence $(x_{n})$ defined iteratively as

converges to a simple root of $f$ in $\mathbb{Z}_{p}$. The order of convergence of this method is 3 for $p\geq 3$ and 4 for $p=2$.

Our goal is to implement a $p$-adic analogue of a simplified version of Jarratt’s method which has order of convergence 4. We will also weaken the initial condition $f^{\prime}(x_{1})\not\equiv 0\bmod{p}$, replacing it by the condition (1.2) above. This allows us to begin with an $x_{1}$ which possibly is a multiple root of the congruence $f(x)\equiv 0\bmod{p}$. At the end of this article we will briefly discuss Thurston’s method which is useful when the initial condition (1.2) is not satisfied. In a nutshell, Thurston’s method either tells us after finitely many steps that a Hensel lifting of a given root $x_{1}$ of the congruence $f(x)\equiv 0\bmod{p}$ to a solution of $f(x)=0$ in $\mathbb{Z}_{p}$ does not exist, or it produces a new polynomial $F$ in place of $f$ which meets the above-mentioned initial conditions. In this case we can perform Jarratt’s method for $F$, which in turn gives us an approximation to a root of $f$ in $\mathbb{Z}_{p}$.

Jarratt’s original method is an iterative numerical method for solving equations $f(x)=0$, where $f$ is a real-valued function defined on intervals in $\mathbb{R}$. The iteration is defined as

Precise initial conditions on $x_{1}$ for a generalized version of this method on Banach spaces were worked out in [1]. The order of convergence of this method is 4, as established in [5].

Instead of using the original method, we here use a simplified version. The idea is as follows. Using a Taylor approximation (if existent), we find

Plugging the right-hand side above into (2.1) and neglecting the error, we arrive at the simpler iteration

We will refer to this iteration as Simplified Jarratt Method (SJM) in the rest of this article. Below we will prove that SJM has order of convergence 4 over the real numbers. If $p>3$, this result carries over to $\mathbb{Q}_{p}$, as we will see later.

Now we apply SJM to polynomials in $\mathbb{Z}_{p}[x]$ subject to certain initial conditions which we work out in detail. We shall prove the following theorem, which is our main result.

As noted in the introduction, in [9], a $p$-adic analogue of Olver’s method was worked out. This method converges with order 3 and was formulated in [9] under the stronger initial condition that $|f(x_{1})|_{p}<1$ and $|f^{\prime}(x_{1})|_{p}=1$, which means that $x_{1}$ is a simple root of the congruence $f(x)\equiv 0\bmod{p}$. In contrast, our condition (3.1) allows us to take $x_{1}$ as a multiple root of the said congruence. We point out that (3.1) matches the condition in the following theorem which is a version of the Generalized Hensel Lemma (see [6]).

This shows that a root $a$ of the congruence $f(x)\equiv 0\bmod{p}$ can be lifted uniquely to a simple root $\gamma$ of $f$ in $\mathbb{Z}_{p}$, provided that $|f(a)|_{p}<|f^{\prime}(a)|_{p}^{2}$. Hence, if $x_{1}=a$ satisfies this condition, then the SJM iteration gives a sequence which converges to precisely this unique lifting $\gamma$ of $a$.

Theorem 3.2 can be proved using Newton’s method (see [2]). In our proof of Theorem 3.1, we replace Newton’s method by SJM.

For the proof of Theorem 3.1, we will use the lemma below.

Now we turn to the

Proof of Theorem 3.1. We set

and recall our assumption $|t|_{p}<1$. We shall proceed similarly as in the proof of the Generalized Hensel Lemma in [2] and aim to show the following statements by induction over $n$:

1. (1)

   $\left\lvert x_{n}\right\rvert_{p}\leq 1$,

2. (2)

   $\left\lvert f^{\prime}(x_{n})\right\rvert_{p}=\left\lvert f^{\prime}(x_{1})\right\rvert_{p}$,

3. (3)

   $\left\lvert f(x_{n})\right\rvert_{p}\leq\left\lvert f^{\prime}(x_{1})\right\rvert_{p}^{2}t^{4^{n-1}}$.

For $n=1$, these conditions are clearly true. So let us assume the conditions to be true for $n$. Now for $n+1$, we have

where $y_{n}:=x_{n+1}-x_{n}$. From Lemma 4.1 we know that

where we use statement (3) together with our assumption $t<1$ above. Further, using (2), we deduce that $\left\lvert y_{n}\right\rvert_{p}\leq\left\lvert{f(x_{n})}/{f^{\prime}(x_{1})}\right\rvert_{p}$, and from (3), we then get

Finally, from (1), we know that $\left\lvert x_{n}\right\rvert_{p}\leq 1$ and hence we have $\left\lvert x_{n+1}\right\rvert_{p}\leq 1$ by appealing to (5.1). Thus, we have established (1) for $n+1$ in place of $n$. To prove (2) for $n+1$, we use the fact that if $F\in\mathbb{Z}_{p}[x]$, then

for some polynomial $G\in\mathbb{Z}_{p}[x,y]$ and hence

for any $x,y\in\mathbb{Z}_{p}$. Applying this to $F=f^{\prime}$, we have

where we use (5.2) and (3). Now if $\left\lvert f^{\prime}(x_{n+1})\right\rvert_{p}\not=\left\lvert f^{\prime}(x_{n})\right\rvert_{p}$, then we have

Hence we arrive at a contradiction. So $\left\lvert f^{\prime}(x_{n+1})\right\rvert_{p}=\left\lvert f^{\prime}(x_{n})\right\rvert_{p}=\left\lvert f^{\prime}(x_{1})\right\rvert_{p}$.

To prove (3) for $n+1$, we use Taylor’s formula and recall that $p>3$, obtaining

for some $z\in\mathbb{Z}_{p}$.

where

and

with $a:=f(x_{n})$, $b:=f^{\prime}(x_{n})$, $c:=f^{\prime\prime}(x_{n})$, $d:=f^{\prime\prime\prime}(x_{n})$. The above expressions may be calculated conveniently using a suitable computer algebra system.

We note that $|b|_{p}=|f(x_{1})|_{p}$ by (2) and $|a|_{p}<|b|_{p}^{2}$ by (2) and (3). It follows that $|A_{n}|_{p}\leq|b|_{p}^{6}$ and $|B_{n}|_{p}=|b|_{p}^{9}$, and hence

where for the second inequality above, we use (5.2) again, and for the last inequality, we use (2) and (3). Hence we are done with the induction.

Using (5.3) and $t<1$, it is clear that $(x_{n})$ is a Cauchy sequence in $\mathbb{Z}_{p}$ and hence converges to some $p$-adic integer $\gamma$. Further, from (2) and (3), we get $|f^{\prime}(\gamma)|_{p}=|f^{\prime}(x_{1})|_{p}>0$ and $f(\gamma)=0$. Finally, using arguments parallel to those in the proof of (2.9), we see that

where $e_{n}:=x_{n}-\gamma$ and $\rho$ as defined in (2.10). Thus we get

and hence, $(x_{n})$ converges with order 4. ∎

Two questions remain to be answered.

(A) Can every zero in $\mathbb{Z}_{p}$ of $f$ be approximated using SJM, provided we choose $x_{1}$ suitably?

(B) What happens if the initial condition (3.1) on $x_{1}$ in Theorem 3.1 is not satisfied? Is there a method which produces a suitable $x_{1}$ satisfying this condition?

Regarding question (A), we note that SJM only approximates simple roots of $f$. If $\gamma$ is a simple root, then clearly there is $x_{1}$ satisfying the initial condition in Theorem 3.1, giving rise to a sequence $(x_{n})$ converging to $\gamma$: In particular, we may just take $x_{1}:=\gamma$. If $f$ has multiple roots, then it is easy to produce a polynomial $\tilde{f}$ whose roots are all simple and coincide with the roots of $f$: Take $\tilde{f}=f/\mbox{gcd}(f,f^{\prime})$, where $\mbox{gcd}(f,f^{\prime})$ is a greatest common divisor (unique up to multiplication by a unit in $\mathbb{Z}_{p}$) of $f$ and $f^{\prime}$ in $\mathbb{Z}_{p}[x]$. Such a greatest common divisor can be conveniently calculated using the Euclidean algorithm in $\mathbb{Q}_{p}[x]$.

To address question (B), we may employ Thurston’s method. Here we only describe briefly how this method works. For the details, we refer the interested reader to [13]. Let

be a root of $f$ in $\mathbb{Z}_{p}$. In particular, $f(a_{0})\equiv 0\bmod{p}$. Let

Now Thurston’s method produces a chain of polynomials $F_{0},F_{1},F_{2},F_{3},...$, starting from $F_{0}=f$, where $F_{i}$ satisfies the equation $F_{i}(\gamma_{i})=0$. In particular, $F_{i}(a_{i})\equiv 0\bmod{p}$. Hence, we may proceed as follows to solve $f(x)=0$ in $\mathbb{Z}_{p}$: First, we find $a_{0}$ such that $F_{0}(a_{0})=f(a_{0})\equiv 0\bmod{p}$. Then we produce $F_{1}$ and find $a_{1}$ such that $F_{1}(a_{1})\equiv 0\bmod{p}$, if existent. This $a_{1}$ may not be unique. Then we produce $F_{2}$ and find (a not necessarily unique) $a_{2}$ such that $F_{2}(a_{2})\equiv 0\bmod{p}$, if existent. We continue this process. If we can continue this process ad infinitum, this gives rise to a sequence $(a_{0}+a_{1}p+\cdots+a_{n}p^{n})$ which converges to a root $\gamma$ in $\mathbb{Z}_{p}$. Generally, this sequence converges only with order 1, though.

Thurston proved that if $f$ has only simple roots in $\mathbb{Z}_{p}$, then for every $a_{0}$ satisfying $f(a_{0})\equiv 0\bmod{p}$, the above process either stops at some point in which case $a_{0}$ cannot be lifted to a root $\gamma$ of $f$ in $\mathbb{Z}_{p}$, or, after finitely many steps, we get an index $n$ for which there exists $a_{n}$ with $F_{n}(a_{n})\equiv 0\bmod{p}$ and $F_{n}^{\prime}(a_{n})\not\equiv 0\bmod{p}$. In this case, we are in the situation of Hensel’s Lemma, and $a_{n}$ therefore lifts uniquely to a root $\gamma_{n}$ of $F_{n}$. To apply SJM, we only need the weaker condition $|F_{n}(a_{n})|_{p}<|F_{n}^{\prime}(a_{n})|_{p}^{2}$ from the Generalized Hensel Lemma. Therefore, if $f$ has only simple roots in $\mathbb{Z}_{p}$, then we can get all roots of $f$ in $\mathbb{Z}_{p}$ as follows: We apply Thurston’s method initially, starting with an $a_{0}$ satisfying $f(a_{0})\equiv 0\bmod{p}$ and, as soon as we reach the said index $n$, apply the faster SJM with $x_{1}=a_{n}$ and $F_{n}$ in place of $f$. This gives rise to a sequence $(x_{n})$ which converges to a root $\gamma_{n}\in\mathbb{Z}_{p}$ of $F_{n}$. From this, we retrieve a root

of $f(x)$.

One last brief remark on practical applications of SJM. This method produces a sequence whose elements lie in $\mathbb{Z}_{p}$. For practical applications, however, only sequences in $\mathbb{Z}$ are useful since we cannot encode an infinite $p$-adic representation using a computer. Therefore, to implement SJM in practice, one needs to cut off the $p$-adic representation of $x_{n}$ at an appropriate point, getting an integer $x_{n}^{\prime}$. Then one calculates $x_{n+1}$ (and hence $x_{n+1}^{\prime}$) using $x_{n}^{\prime}$ in place of $x_{n}$. This will give a sequence $(x_{n}^{\prime})$ of integers converging to our root $\gamma\in\mathbb{Z}_{p}$ of $f$.