How to compute 2-adic square roots?

Solution 1:

One way to apply Hensel cleanly is to use it to find not $\sqrt{17}$ but $(1+\sqrt{17}\,)/2$, whose minimal polynomial is $X^2-X-4$. If you want to use Newton-Raphson instead of Hensel, that too works more cleanly on $X^2-X-4$.

Solution 2:

Because the derivative of $x^2-17$, i.e. $2x$ is $0 \bmod{2}$ Hensel's Lemma doesn't work very cleanly. In this situation when going from $p$ to $p^2$ either there is no lift, or every lift will work$\bmod p^2$. Let's look at what happens here -

$x^2\equiv 17 \bmod 2 \text{ has the solution }x\equiv 1 \bmod 2$

$(2y+1)^2 \equiv 17 \bmod 4 \text { is always true, telling us } x\equiv 1,3 \bmod 4 \text{ both work}$

When we lift to$\bmod 8$ we find $1$ and $5$ (lifts of $1 \bmod 4\,$) both work$\bmod 8$ as well as $3$ and $7$ (the lifts of $3 \bmod 4$). Note that we seem to have 4 solutions! Let's look at$\bmod 16$ and beyond. $$ \begin{array}\\ 1,5\pmod 8 & 1^2 \equiv (1+16) \equiv 17 \pmod{16} & 5^2\equiv 9 \not \equiv 17 \pmod{16} \\ 3,7\pmod{ 8} & 3^2 \equiv 9 \not\equiv 17 \pmod{16} & 7^2\equiv 49 \equiv 17 \pmod{16} \\ \end{array} $$ So of our 4 solutions only $1$ and $7\bmod 8$ will lift to$\bmod 16$. We lift those and try$\bmod 32$. $$ \begin{array}\\ 1,9\pmod{16} & 1^2 \not\equiv 17 \pmod{32} & 9^2\equiv 81 \equiv 17 \pmod{32} \\ 7,15\pmod{16} & 7^2 \equiv 49 \equiv 17 \pmod{32} & 15^2\equiv 225 \not\equiv 17 \pmod{32} \\ \end{array} $$ So of our 4 solutions only $9$ and $7\bmod 16$ will lift to$\bmod 32$. We lift those and try$\bmod 64$. \begin{array}\\ 9,25\pmod{32} & 9^2 \equiv 81 \equiv 17 \pmod{64} & 25^2\equiv 625 \not\equiv 17 \pmod{64} \\ 7,23\pmod{32} & 7^2 \equiv 49 \not\equiv 17 \pmod{64} & 23^2\equiv 529 \equiv 17 \pmod{64}\end{array}

Fairly tedious stuff for humans, but nothing a computer algebra system won't whip out in no time. We have found 2 roots, $1 + 2^3 + O(2^5)$ and $1 + 2+ 2^2 + 2^4 + O(2^5)$.

When Doing the calculations by hand it would probably make more sense to find only one root and multiply by $-1=\frac{1}{1-2}=1+2+2^2+...$ for the other root.

Solution 3:

The binomial formula $(1+x)^\frac 12 = 1 + \frac12 x - \frac 18 x^2 + \ldots$ converges if $x \equiv 0 \pmod 8$, which gives you a way to find square roots for any $y \equiv 1 \pmod 8$.

In fact, the squares in the $2$-adics are the direct product of $\langle 4 \rangle$ with $(1+8\Bbb Z_2)$.

Here you can apply this directly to $17$, and it will converge even faster since it's $1 \pmod {16}$

Another thing this tells you is that a square root of $1+x$ is close to $1+\frac x2$, so you can recursively compute it by saying $\sqrt{1+8x} = (1+4x)\sqrt{(1+8x)/(1+4x)^2} = (1+4x)\sqrt{1-16(x/(1+4x))^2)}$. This gives you an infinite product whose terms are closer and closer to $1$. The number of correct digits doubles on each iteration

Solution 4:

Let me add to the other answers with a more concrete iteration. With precision I mean the number of bits used per $2$-adic integer.

Hensel lifting resembles Newton iteration. The usual Newton-Raphson scheme for the reciprocal squareroot also works for $p$-adic squares, provided you begin with a close-enough initial guess, which here means that the initial unit digit must be correct. Multiplying $a$ with its reciprocal squareroot $1/\sqrt{a}$ gives you the ordinary squareroot $\sqrt{a}$.

Newton-Raphson computation of $x = \frac{1}{\sqrt{a}}$ finds a zero of $f(x)=\frac{1}{a x^2}-1$ using the iteration $$x_{n+1} = x_n\,(3 - a x_n^2)/2,$$ provided that $a\equiv1\pmod{8}$ and $x_0$ is odd. The next bit (weight $2$) of $x_0$ is preserved by the iteration; think of it as deciding on the sign of the squareroot to return. So basically you begin with two correct bits. From there on, each step first doubles the number of correct bits, then loses one bit due to the division by $2$.

A note on the division by $2$. No problem: Division by $2$ is defined in $\mathbb{Q}_2$, and it yields a $2$-adic integer if the dividend is an even $2$-adic integer. This is the case here, as $a$ and all the $x_n$ are odd. So just shift down 1 bit.

However, when working with fixed finite precision, this means that something needs to get shifted into the highest bit. The correct value would depend on $a$'s next higher bit which you do not know, but either choice works in the sense that squaring with the same precision yields the same result. This is why there are four possible solutions with finite precision. If you consider that highest bit an inaccuracy and remove it from the result, there are only two possible solutions, depending on your choice of $x_0\equiv\pm1\pmod{4}$.

Solution 5:

What seems like another way to approach this (but is not -- see below) is to use the $p$-adic exp and log functions. For an element $y = 1+8x$ (with $x\in \Bbb{Z}_2$), by the usual arguments everything makes sense and converges and $$\alpha := \exp\left(\frac{1}{2}\log(y)\right)$$ is a square root of $y$. (It is the one that is $\equiv 1$ mod $4$. Its negative is the other one.)

Concretely, for $y=17$ we have $8x=16 =2^4$, and working out just the first few terms gives

$$\begin{array} \displaystyle\frac{1}{2} \log(17) &=& 2^3-2^6+\frac{1}{3}2^{11}-2^{13} + \dots\\ \exp(\frac{1}{2}\log(17))&=&1\\ &&+\:(2^3-2^6+\frac{1}{3}2^{11}-2^{13} +\dots) \\ &&+ \frac{1}{2}(2^6-2\cdot 2^9 +2^{12}+\dots )\\ &&+\frac{1}{6}(2^9 +\dots)\\ &&+\frac{1}{24}(2^{12} +\dots)\\ &&+\dots\\ &=& 1+2^3+2^5-2^6+\frac{1}{3}2^8-\frac{1}{3}2^{10} \dots \end{array}$$ which is $$\dots 011011101001$$ and that matches the value in ccorn's comment to his answer. And of course, this method works better the closer $y$ is to $1$ ($\Leftrightarrow$ the closer $x$ is to $0$) in $\Bbb{Z}_2$.

In general, one could concretely work out

$$\exp\left(\frac{1}{2}\log(1+8x)\right) = 1 +4x -8x^2 +\dots$$

as a series in $x$ which converges $2$-adically for $|x|_2\le 1$. However, now one sees that what we get here is actually the binomial formula in mercio's answer in disguise.