Lifting solutions modulo $2^{10}$ to a solution $2^{19}$

Question

We are given that $55$ is a solution to $x^ 3 − 9 x + 8 \equiv 0 \pmod {2^{10}}$.

Find a solution to $x^ 3 − 9 x + 8 \equiv 0 \pmod {2^{19}}$ that is a lift of $55$.

I was going to try lift the solution to modulo $2^{20}$ using Hensel's Lemma, but I can't use that here because $f'(55) \equiv 0 \pmod 2$, so the method fails. But then if you check $f(55)$ modulo $2^{20}$, you get something that is non-zero. Doesn't this mean there are no solutions except $55$ itself?

Any help would be really appreciated, thanks.

Answer 1

Here is a simple computer search using sage.

sage: R = Zp(2, prec=19)
sage: RX.<X> = PolynomialRing(R)
sage: for s in [0 .. 2^19-1]:
....:     if ( s^3 -9*s + 8 ) % 2^19 == 0:
....:         print "s=%7s s mod 2^10=%4s R(s)=%s" % ( s, s% 2^10, R(s) )
....: 
s=      1 s mod 2^10=   1 R(s)=1 + O(2^19)
s=  85047 s mod 2^10=  55 R(s)=1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + 2^14 + 2^16 + O(2^19)
s= 262145 s mod 2^10=   1 R(s)=1 + 2^18 + O(2^19)
s= 347191 s mod 2^10=  55 R(s)=1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + 2^14 + 2^16 + 2^18 + O(2^19)
s= 439240 s mod 2^10= 968 R(s)=2^3 + 2^6 + 2^7 + 2^8 + 2^9 + 2^12 + 2^13 + 2^15 + 2^17 + 2^18 + O(2^22)

So the lifts are there, and they are two for $55$, this answers the question.

---

Some comments on this maybe.

The given polynomial $f=X^3-9X+8\in\Bbb Z_2[X]$ reduces modulo $2$ to $\bar f = X^3-X=X(X-1)(X+1)=X(X-1)^2\in\Bbb F_2[X]$, it has a double root in $1$, and we want to lift both $0$, and the double root $1$. The derivative $f'=3X^2-9\in \Bbb Z_2[X]$ has then the values $f'(0)=-9=1\ne 0\in \Bbb F_2$, and $f'(1)=3-9=0\in\Bbb F_2$. As seen above, we have a unique lift of $0$ from $\Bbb Z$ modulo $2^1$ to $\Bbb Z$ modulo $2^{19}$.

What about lifting the $1\in \Bbb Z/2$?

First, we have $X^3-9X+8=(X-1)(X^2+X-8)$ over $\Bbb Z$, the $1\in \Bbb Z$ will remain root modulo any power of $2$, so we will look as an intermezzo at the quotient $g=(X^2+X-8)$. Then $g(1)=0$, $g'(1)\ne 0$ modulo $2$, so we expect unique lifts. And here they are:

sage: for N in range(3,20):
....:     R = Zp(2, prec=N)
....:     print "N = %s" % N
....:     for s in [0 .. 2^N-1]:
....:         if (s^2 + s - 8) % 2^N == 0:
....:             print "Solution s = %s = %s" % (s, R(s))
....: 
N = 3
Solution s = 0 = 0
Solution s = 7 = 1 + 2 + 2^2 + O(2^3)
N = 4
Solution s = 7 = 1 + 2 + 2^2 + O(2^4)
Solution s = 8 = 2^3 + O(2^7)
N = 5
Solution s = 8 = 2^3 + O(2^8)
Solution s = 23 = 1 + 2 + 2^2 + 2^4 + O(2^5)
N = 6
Solution s = 8 = 2^3 + O(2^9)
Solution s = 55 = 1 + 2 + 2^2 + 2^4 + 2^5 + O(2^6)
N = 7
Solution s = 55 = 1 + 2 + 2^2 + 2^4 + 2^5 + O(2^7)
Solution s = 72 = 2^3 + 2^6 + O(2^10)
N = 8
Solution s = 55 = 1 + 2 + 2^2 + 2^4 + 2^5 + O(2^8)
Solution s = 200 = 2^3 + 2^6 + 2^7 + O(2^11)
N = 9
Solution s = 55 = 1 + 2 + 2^2 + 2^4 + 2^5 + O(2^9)
Solution s = 456 = 2^3 + 2^6 + 2^7 + 2^8 + O(2^12)
N = 10
Solution s = 55 = 1 + 2 + 2^2 + 2^4 + 2^5 + O(2^10)
Solution s = 968 = 2^3 + 2^6 + 2^7 + 2^8 + 2^9 + O(2^13)
N = 11
Solution s = 968 = 2^3 + 2^6 + 2^7 + 2^8 + 2^9 + O(2^14)
Solution s = 1079 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + O(2^11)
N = 12
Solution s = 968 = 2^3 + 2^6 + 2^7 + 2^8 + 2^9 + O(2^15)
Solution s = 3127 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + O(2^12)
N = 13
Solution s = 3127 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + O(2^13)
Solution s = 5064 = 2^3 + 2^6 + 2^7 + 2^8 + 2^9 + 2^12 + O(2^16)
N = 14
Solution s = 3127 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + O(2^14)
Solution s = 13256 = 2^3 + 2^6 + 2^7 + 2^8 + 2^9 + 2^12 + 2^13 + O(2^17)
N = 15
Solution s = 13256 = 2^3 + 2^6 + 2^7 + 2^8 + 2^9 + 2^12 + 2^13 + O(2^18)
Solution s = 19511 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + 2^14 + O(2^15)
N = 16
Solution s = 19511 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + 2^14 + O(2^16)
Solution s = 46024 = 2^3 + 2^6 + 2^7 + 2^8 + 2^9 + 2^12 + 2^13 + 2^15 + O(2^19)
N = 17
Solution s = 46024 = 2^3 + 2^6 + 2^7 + 2^8 + 2^9 + 2^12 + 2^13 + 2^15 + O(2^20)
Solution s = 85047 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + 2^14 + 2^16 + O(2^17)
N = 18
Solution s = 85047 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + 2^14 + 2^16 + O(2^18)
Solution s = 177096 = 2^3 + 2^6 + 2^7 + 2^8 + 2^9 + 2^12 + 2^13 + 2^15 + 2^17 + O(2^21)
N = 19
Solution s = 85047 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + 2^14 + 2^16 + O(2^19)
Solution s = 439240 = 2^3 + 2^6 + 2^7 + 2^8 + 2^9 + 2^12 + 2^13 + 2^15 + 2^17 + 2^18 + O(2^22)

Sorry for this, i would have hated such an intermezzo some years before.

The lifts of the root $55$ of $g$ start with $1 + 2 + 2^2 + 2^4 + 2^5 + \dots$ .

Now let us look at the lifts of $55$ for $f=X^3-9X+8$. They are:

sage: for N in range(10, 20):
....:     R = Zp(2, prec=N)
....:     print "N = %s" % N
....:     for s in [0 .. 2^N-1]:
....:         if (s-1)*(s^2 + s - 8) % 2^N == 0 and s % 2^10 == 55:
....:             print "Solution s = %s = %s" % (s, R(s))
....: 
N = 10
Solution s = 55 = 1 + 2 + 2^2 + 2^4 + 2^5 + O(2^10)
N = 11
Solution s = 55 = 1 + 2 + 2^2 + 2^4 + 2^5 + O(2^11)
Solution s = 1079 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + O(2^11)
N = 12
Solution s = 1079 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + O(2^12)
Solution s = 3127 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + O(2^12)
N = 13
Solution s = 3127 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + O(2^13)
Solution s = 7223 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + 2^12 + O(2^13)
N = 14
Solution s = 3127 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + O(2^14)
Solution s = 11319 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + 2^13 + O(2^14)
N = 15
Solution s = 3127 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + O(2^15)
Solution s = 19511 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + 2^14 + O(2^15)
N = 16
Solution s = 19511 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + 2^14 + O(2^16)
Solution s = 52279 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + 2^14 + 2^15 + O(2^16)
N = 17
Solution s = 19511 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + 2^14 + O(2^17)
Solution s = 85047 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + 2^14 + 2^16 + O(2^17)
N = 18
Solution s = 85047 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + 2^14 + 2^16 + O(2^18)
Solution s = 216119 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + 2^14 + 2^16 + 2^17 + O(2^18)
N = 19
Solution s = 85047 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + 2^14 + 2^16 + O(2^19)
Solution s = 347191 = 1 + 2 + 2^2 + 2^4 + 2^5 + 2^10 + 2^11 + 2^14 + 2^16 + 2^18 + O(2^19)

Sorry again, it this is annoying, but this experimental issue makes one thing clear:

If $s$ is an odd root modulo $O(2^{N+1})$, then $t:=s+2^N$ is also a root for $f=X^3-9X+8$.

Indeed, working modulo $O(2^{N+1})$, $$ \begin{aligned} f(s)-f(t) &=(s^3-9s+8)-(t^3-9t+8)\\ &=(s^3-t^3)-9(s-t)\\ &=(s-t)(s^2+st+t^2-9)\\ &\in O(2^N)\cdot O(2^1)\ . \end{aligned} $$