How to compute 2-adic square roots?

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.

• Wow. I’m an old hand at this racket, and what you tried I’ve always recommended, as one possible strategy, for finding square roots. But I never realized, till your question, that it just doesn’t work when $p=2$. For other primes, it’s not a matter of guessing, but taking an unknown digit $a$ and getting a congruence $2a\equiv b\pmod p$, where $b$ comes from observation of the results so far. But you can’t divide by $2$ when you’re doing congruences modulo $2$. Bummer. – Lubin May 29 '17 at 22:15
• Sorry I need to get my hands on "J.P. Serre, A Course in Arithmetic, Graduate Texts in Mathematics 7, Springer-Verlag (1973)" – Adam Jun 25 '18 at 19:24

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

• I got this to work very cleanly, thank you! Hensel certainly converges more slowly than other methods, but it's the one I've made the most sense of so far. – G Tony Jacobs May 30 '17 at 13:11
• Actually, it converges more quickly than Taylor, and appears to be the most practical for getting quick results with the technology I'm using. Thanks very much! – G Tony Jacobs May 30 '17 at 14:16

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.

• Very nice! First time I seem to learn about the term "lifting"... – Gottfried Helms May 28 '17 at 6:13
• So, if I understand correctly, we're basically lifting manually, without a formula telling us which lift will work in each case? – G Tony Jacobs May 30 '17 at 13:24
• Yes. The trouble is that both lifts will work$\bmod 2^k$ but only 1 of the two will work when lifted $\bmod 2^{k+1}$ – sharding4 May 30 '17 at 13:32
• I think I see. In the last step, for example, $9$ lifts from $\mod 32$ to $\mod 64$, but $25$ does not. That means that both $9$ and $32+9=41$ will work $\mod 64$, but only one of those two will lift to $\mod 128$, right? – G Tony Jacobs May 30 '17 at 13:48
• Yes that's correct. Although you can find a square root using Hensel's lemma in this case, it seems clear that one of the other methods or using the very nice observation ($(1+\sqrt(17)/2$) of Lubin with Hensel's lemma would be the way to go. – sharding4 May 30 '17 at 13:55

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

• For that infinite product process, would the next step be to pull a factor of $(1-8(x/(1+4x))^2)$ out of the radical, leaving its square in the denominator inside, and then again rewriting what's under the radical as $1$ plus or minus some expression? – G Tony Jacobs May 30 '17 at 13:22
• Also, I think your degree 2 term in that power series expansion is incorrect. Did you forget to divide by $2!$? – G Tony Jacobs May 30 '17 at 13:30
• um yes, thanks for noticing. And yes to the first comment too. – mercio May 30 '17 at 13:31
• Thank you; this is very helpful. The Taylor series method seems a bit easier to apply than the infinite product method, at least when I'm doing computations by hand, or with a spreadsheet. – G Tony Jacobs May 30 '17 at 13:44
• yeah there is no pesky division that make everything complicated. If the cost of division is significantly larger than multiplication, you can delay it until the very end so you do only one division, and then I think the recursive formula is more efficient. Also we are dividing and multiplying by things that are closer and closer to $1$, so they should be faster and faster to perform as you do more steps. – mercio May 30 '17 at 14:01

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

• Right you are. There will always be rounding errors when N-R tells you to divide by something in the maximal ideal of your $p$-adic ring. In this case, you’ll get an answer whose square is correct to $n$ two-adic digits, but the answer itself will be guaranteed to be accurate only to $n-1$ two-adic digits. – Lubin May 29 '17 at 22:21
• This method seems to converge the fastest by far, but I need to study Newton-Raphson to really understand what's going on. – G Tony Jacobs May 30 '17 at 13:26
• Actually, this converges very quickly, via very large integers. After just a couple of steps, the numbers involved are too big for me to work with! – G Tony Jacobs May 30 '17 at 14:37
• @GTonyJacobs: Reduce $x_{n+1}$ modulo $2^k$ for some $k$ of your choosing, e.g. $k=32$. That's what I called the ($p$-adic) precision. You do not need to keep higher bits of the $x_n$ than you want. – ccorn May 30 '17 at 19:01
• E.g. with 32 bits of precision, the reciprocal-squareroot iteration goes like this: 00000000000000000000000000000001 11111111111111111111111111111001 00000000000000000000101101011001 01111011100011000001000101011001 10101000101100100001000101011001 and multiplying that last one with $17\pmod{2^{32}}$ gives the squareroot 00110011110100110010011011101001. – ccorn May 30 '17 at 20:04

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.

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

• This makes sense, except for one thing. I find that $x^2-17$ has four solutions, modulo $8$, namely all of the units. That's great, but when I want to lift those solutions, to use Hensel, I need a multiplicative inverse $\pmod{2}$ of $f'(x)$, where $x$ is the solution I'm trying to lift. However, $f'(x)=2x$, which is $0\pmod{2}$. So, I'm stuck. – G Tony Jacobs May 27 '17 at 13:46
• Try $x=1+8y$, then $17=1+16y+64y^2$, so $1=y+4y^2$. This means $y\equiv 1\pmod 4$. So $x\equiv1\pmod 8$ lifts to $x\equiv9\pmod{32}$ etc. – Lord Shark the Unknown May 27 '17 at 13:53
• A $2$-adic square root is very messy. The Wikipedia entry for Hensel's lemma discusses this root but probably provides more heat than light. There are 2 distinct square roots, but you end up getting 4 solutions $\mod 2^k$ which converge $2$-adically to the 2 roots. – sharding4 May 27 '17 at 13:57
• There is a version of Hensel's lemma that applies when $f'$ of the root vanishes modulo $p$. It can be found, for example, in Niven/Zuckerman/Montgomery's book. Indeed, it's a way of systematizing the computation done in sharding4's answer. – Greg Martin May 28 '17 at 2:53