5
$\begingroup$

$\newcommand\Q{\mathbb Q} \newcommand\Z{\mathbb Z}$I am a bit confused on the square root of 2-adics. I am pretty sure I am mixing some steps in an algorithm. To be precise, I am trying to solve an exercise in Koblitz' book p-adic numbers, p-adic analysis and zeta functions (this is not a homework, I just want to do it). In exercise of I.7 the reader is asked to solve the square root of -7 in $\Q_2$ up to 5-digits and the hint is to use a generalization of Hensel's Lemma:

Let $f(x)$ be a polynomial with coefficients in $\Z_p$. If $a_0$ in $\Z_p$ satisfies

  • $f(a_0) = 0 \bmod p^{2m+1}$
  • $f'(a_0) = 0 \bmod p^m$
  • $f'(a_0) \ne 0 \bmod p^{m+1}$

then there is a unique $a\in\Z_p$ such that $f(a) = 0$ and $a=a_0 \bmod p^{m+1}$

Obviously the procedure to solve comes from an algorithm to be seen in the proof of this generalized Hensel's lemma. For my particular problem $f(x)=x^2+7$ and $p=2$, I choose $a_0$ either $1$ or $0$ (so in fact an integer) and then I iterate to get, for a chosen $b_1 =1$ or $b_1=0$, $a_1 = a_0 + b_1 p^{m+1}$ for which $f(a_1)=0 \bmod p^{2m+2}$ and so on i.e. I need to get $b_i$ which gives $a_i$ such that $f(a_i) = 0 \bmod p^{2m+1+i}$.

I might be missing something, but for me the answer for square root of -7 would be of the form $a_0 + b_12+ b_22^2 + \dots $ But I have a problem getting the correct answer. So one of the square root (using Pari to check) is $(a_0,b_1,b_2,\dots)=(1,1,0,1,0,\dots)$.

Is there a cleaner way to think of this algorithm. I get easily confused and make mistakes with the iteration steps.

Maybe I have mixed something in the procedure. Could someone explain to me why for $a_0=1$, we get $(1,1,0,1,0,\dots)$?

From this I feel that manually taking roots and even doing simple arithmetic is not practical in the p-adics.

EDIT: The algorithm I have in mind is actually also written here in this online calculator: http://www.numbertheory.org/php/2adic.html

I still fail to get the correct $b_4$ using the algorithm. However, the online calculator gives me the correct $b_4$. If I follow the procedure, my $b_4$ is $(a_3^2+7)/64 \bmod 2 = 7\bmod 2$ so it is $1$, while the correct answer is $0$.

$\endgroup$
7
  • $\begingroup$ Compare e.g. sharding4's answer to math.stackexchange.com/q/2298779/96384, for the analogous question with 17 insetad of $-7$. $\endgroup$ May 29, 2021 at 14:36
  • $\begingroup$ In your approach, I suggest you start with $m=0$, and then I think you should not name the $b_i$ you find there with the same name as the ones in the expansion in the final answer. They are just intermediate calculations. I.e use what you call $b_i$ first to get $a_i$, and then in the end you can write $a_i = a_0+ c_1 2+ c_2 2^2 + ...$. (I think the $b_i$ are not the same as the $c_i$.) $\endgroup$ May 29, 2021 at 14:41
  • $\begingroup$ why are they different. If I have $a_1=a_0+b_12$ then isn't $a_2 = a_1+b_22^2 = a_0+c_12+b_22^2$ and so on? $\endgroup$
    – quantum
    May 30, 2021 at 5:49
  • $\begingroup$ @Torsten: I am actually a little worried of sharding4's answer in the aforementioned post. It requires me to keep the possible solution for every $p^k$ roots and get rid as I proceed to higher $k$ for which the solutions do not continue (which is at worst case exponential in space and time). I feel one already knows which ones to keep by this version of Hensel's Lemma (I mean there is only 2 possibilities for the root). Anyway, I couldn't determine the fifth digit after I continued to the 6th and 7thu using sharding4's method. $\endgroup$
    – quantum
    May 30, 2021 at 5:57
  • $\begingroup$ Maybe I misunderstood your notation. But don't you get $a_0=1, a_1=3, a_2=3, a_3=11$? Then is not $(a_3^2+7)/64 =2$? $\endgroup$ May 30, 2021 at 16:00

3 Answers 3

1
$\begingroup$

OK I was finally able to get the correct answer. The site http://www.numbertheory.org/php/2adic.html provides a code for 2-adic square roots and I just looked at it and figured out my embarassing mistake.

I will write the steps. We want to get $(11010\dots)_2$ in 2-adics. We have $f(x) = x^2+7$ , $m=1$ and most importantly that $a_0=3$ (not $1$). This will give me one (unique) solution and if we start with $a_0=1$ we get the negative of that solution. We want $a_0=3$ because, we (or I) want to obtain $(11\dots)_2$ so it must start with $a_0=3$ rather than $a_0=1$ because in the other case we would obtain $(10\dots)_2$. So what I am trying to say is: my idea was correct but I started with the wrong $a_0$.

We can use Hensel's lemma because $f'(a_0)=6$ and $2\mid\mid 6$.

To get the digit after $(11)_2$ we use this algorithm: For the i-th step we want to choose $b_i$ such that $a_i = a_{i-1}+b_i2^{m+i}$ satisfies $f(a_i)=0 \bmod 2^{2m+i+1}$.

  • For $i=0$ (no steps here), $a_0=3$ , and $f(a_0)=3^2+7=16$

  • For $i=1$ (the third digit) we want to choose $b_1$ such that $a_1 = 3 + b_12^{1+1}$ satisfies $$f(a_1) = 0 \bmod 2^{2+1+1}$$ So $b_1=0$ and $a_0=a_1=3$.

  • For $i=2$ (the fourth digit) we want to choose $b_2$ such that $a_2 = 3 + b_22^{1+2}$ satisfies $$f(a_2) = 0 \bmod 2^{2+2+1}$$ So $b_2=1$ and $a_2 = 3+8=11$ with $f(a_2)=128$

  • For $i=3$ (the fifth digit) we want to choose $b_3$ such that $a_3=11 + b_32^4$ satisfies $$f(a_3) = 0 \bmod 2^6$$ So $b_3=0$ and so I got the correct five digits $11010$.

It is much easier to program this than to iterate by hand, because it is so easy to make this stupid mistake I made (at some point I was confused modulo what powers of $2$ I should check the $a_i$ and the $f(a_i)$). Also, I do not need to "cache" the roots modulo $2^k$ after $a_0=3$ or $a_0=1$.

$\endgroup$
2
  • $\begingroup$ Ok, but see there my confusion: $2$-adically, $3=1+1*2$ which I would have interpreted as $a_0=1, b_1=1$ whereas you interpret it as $a_0=3, b_1=0$. That's where I would have called one of the b's (yours or mine) c's instead. $\endgroup$ May 30, 2021 at 16:23
  • $\begingroup$ you are correct that it is confusing. I also made an error in the original post. The $b_1$ had to be multiplied with $2^{m+1}$ (in our case $m=1$). So the finaly $p$-adic number is $a_0+b_12^{m+1}+b_22^{m+2}+\dots$. So you are absolutely correct about the coefficients of the power of $2$s. $\endgroup$
    – quantum
    May 31, 2021 at 5:01
0
$\begingroup$

Since $11^2\equiv-7\bmod2^6$, why not render $...01011_2$ and call it a day?

$\endgroup$
0
$\begingroup$

Might be nice to know that we can do it a bit easier if we use series,

$$\sqrt{-7} = (1-8)^{1/2} = \sum_{n\ge 0} \binom{1/2}{n} (-8)^n$$

Remember $\binom{a}{b}=\frac{1}{b!}\prod_{i=0}^{b-1}(a-i)$, we want up to 5 digits, so we can chop it off at just 3 terms,

$$1+\frac{1}{2} (-8)+\frac{-1}{4*2!} (-8)^2 = 1+2^2+2^4 = 10101_2$$

Might be fair to call this our principal root, and since we're in a field we of course have two solutions to $x^2+7=0$ and the negative is simply to complement the digits and add 1, to get $01011_2$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .