How to compute 2-adic square roots?

Question

I know that, for a $2$-adic unit to be a perfect square, it must be of the form $\cdots001.$, for example the number $17$ ($10001.$) is a $2$-adic square. How would I go about finding the $2$ adic expansion of its square roots? There ought to be two, either of which is $-1$ times the other, but I don't know how to find either one.

I've tried setting up long multiplication and guessing digits that work, but there seem to be too many degrees of freedom. Any insights are appreciated.

Answer 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$.

Answer 2

Use Hensel's Lemma.

Hensel's Lemma does not just prove that $p$-adic solutions exist, it's also an algorithm that takes a solution modulo $p^k$ and refines it to a solution modulo a higher power of $p$.

Answer 3

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.

Answer 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}$.

Answer 5

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