Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I understand Hensel's Lemma and how you lift a root $f(b_{j}) \equiv 0 \pmod{p^\alpha}$ to one $f(b_{j+1}) \equiv 0 \pmod{p^{\alpha+1}}$, as long as $f'(b_{j}) \not\equiv 0 \pmod{p}$.

The equation is actually quite simple: $b_{j+1} \equiv b_{j} - f(b)*(f'(a)^{-1}) \pmod{p^{\alpha+1}}$.

My question is what happens when $f'(b) \equiv 0 \pmod{p}$.

The best I can find is that there are multiple solutions, but nothing I can find says how to find them. Is there a nice equation for $b_{j+1}$ (or the multiple values it can take on) given $b_{j}$.

share|improve this question
1  
I don't have my number theory books with me right now and I don't recall the discussion about this, but I remember that there are only two cases : either all integers lying above $b_j$ are roots, or either none of them are. There is no possibility that only 2 or 3 or ... out of $p$ are, it's all or nothing. If no one has answered this before I come home I'll quote one of my references down here with an answer. –  Patrick Da Silva Dec 12 '11 at 5:17
4  
Here is a more general form of Hensel's lemma: if $|f(a_0)|_p < |f'(a_0)|_p^2$ then there is a unique $p$-adic integer $a$ such that $f(a) = 0$ and $|a - a_0|_p < |f'(a_0)|_p$. This is more important than trying to find a multi-valued formula for all solutions of $f(x) \equiv 0 \bmod p^n$. –  KCd Dec 12 '11 at 6:26
    
Niven/Zuckerman/Montgomery should have this information, IIRC. –  Greg Martin Dec 12 '11 at 7:42
    
@Dylon Moreland: The WP link you posted actually starts editing the section in question. If many people click on it, somebody might actually destroy the article section accidentally! –  Marc van Leeuwen Dec 12 '11 at 12:48
    
@Marc Woops! Here's the correct link. –  Dylan Moreland Dec 12 '11 at 19:20
add comment

1 Answer

I see nobody has answered this yet. As Greg Martin points out, Niven/Zuckerman/Montgomery have some material on this (Section 2.6 in the Fifth Edition): Hensel's Lemma for the case $f'(r)\not\equiv 0\pmod{p}$; a slightly more general version that says that if $f'(r)\equiv 0\pmod{p}$ but you can lift the solution to a "high enough" power of $p$, then you can keep lifting it (uniquely); and a discussion of what happens in the other cases.

Hensel's Lemma. Suppose that $f(x)$ is a polynomial with integer coefficients. If $f(a)\equiv 0\pmod{p^j}$ and $f'(a)\not\equiv 0\pmod{p}$, then there is a unique $t$ (modulo $p$) such that $f(a+tp^i)\equiv 0\pmod{p^{j+1}}$.

The formula, as noted, is $$a_{j+1} = a_j - f(a_j)\overline{f'(a)},$$ where $\overline{f'(a)}$ denotes the modular inverse of $f'(a)$ modulo $p$. This is really the modular version of Newton's Method; you can view $a_1,a_2,a_3,\ldots$ as a sequence of approximations (in the $p$-adic norm), and the sequence $(a_1,a_2,a_3,\ldots)$ yields a $p$-adic solution to $f(x)= 0 $.

What happens if $f'(a)\equiv 0 \pmod{p}$?

Edited. Consider the Taylor expansion of $f(x)$ at $a$: $$f(a+h) = f(a) + f'(a)h + \frac{1}{2}f''(a)h^2 + \cdots + \frac{1}{n!}f^{(n)}(a)h^n,$$ where $n$ is the degree of $f$. Note that a term $c_kx^k$ in $f(x)$ will result in $$\frac{k(k-1)(k-2)\cdots(k-j+1)}{j!}c_kx^{k-j} = \binom{k}{j}c_kx^{k-j}$$ in $\frac{1}{j!}f^{(k)}(x)$; this has integer coefficients, so each of the coefficients $\frac{1}{j!}f^{(j)}(a)$ is an integer if $f(x)$ has integer coefficients and $a$ is an integer.

Now assume that $f(a)\equiv 0 \pmod{p^j}$ and $f'(a)\equiv 0 \pmod{p}$; then $f(a+tp^j)\equiv f(a)\pmod{p^{j+1}}$ for all integers $t$, since we have: $$f(a+tp^j) = f(a) + tp^jf'(a) + \frac{t^2p^{2j}f''(a)}{2} + \cdots + \frac{t^np^{nj}f^{(n)}(a)}{n!},$$ and $\frac{f^{(k)}(a)}{k!}$ is an integer. So if $f(a)\equiv 0\pmod{p^{j+1}}$, then $f(a+tp^j)\equiv 0\pmod{p^{j+1}}$ for all $t$. That is: if the solution lifts, then the single root modulo $p^j$ lifts to $p$ roots modulo $p^{j+1}$. If $f(a)\not\equiv 0\pmod{p^{j+1}}$, then none of the integers that lie above $a$ modulo $p^{j+1}$ can be roots, and there are no roots lying above $a$.

So either you can lift to all residue classes modulo $p^{j+1}$ that are above $a$, or to none.

If the power of $p$ that divides $f(a)$ is sufficiently high compared to the power of $p$ that divides $f'(a)$, then you can still rescue "lifting":

Generalized Hensel's Lemma. Let $f(x)$ be a polynomial with integral coefficients. Suppose that $f(a)\equiv 0 \pmod{p^j}$, $p^{\tau}||f'(a)$, and that $j\geq 2\tau+1$. If $b\equiv a \pmod{p^{j-\tau}}$, then $f(b)\equiv f(a)\pmod{p^j}$ and $p^{\tau}||f'(b)$. Moreover, there is a unique $t$ (modulo $p$) such that $f(a+tp^{j-\tau})\equiv 0 \pmod{p^{j+1}}$.

Above, $p^{\tau}||f'(a)$ means that $p^{\tau}|f'(a)$, but $p^{\tau+1}$ does not divide $f'(a)$. If $\tau=0$, then we get Hensel's Lemma.

Proof. If $f(a)\equiv 0\pmod{p^j}$, then plugging in $b=a+tp^{j-\tau}$ into the Taylor expansion and considering the equation modulo $p^{2j-2\tau}$, we have $$f(b) = f(a+tp^{j-\tau}) \equiv f(a) + tp^{j-\tau}f'(a)\pmod{p^{2j-2\tau}},$$ and $p^{j+1}$ divides the modulus (since $j-2\tau\geq 1$). So $$f(a+tp^{j-\tau}) \equiv f(a) + tp^{j-\tau}f'(a)\pmod{p^{j+1}}.$$ Both $f(a)$ and $p^{j-\tau}f'(a)$ are divisible by $p^j$ (since $f'(a)$ is divisible by $p^{\tau}$), so $f(b)\equiv f(a)\equiv 0\pmod{p^j}$. If we divide by $p^j$, we have $$\frac{f(b)}{p^j} = \frac{f(a+tp^{j-\tau})}{p^j} \equiv \frac{f(a)}{p^j} + \left(\frac{f'(a)}{p^{\tau}}\right) t\pmod{p}.$$ The coefficient of $t$ is not divisible by $p$ (since $p^{\tau+1}$ does not divide $f'(a)$), so there is a unique value of $t$ modulo $p$ for which the right hand side is $0$ modulo $p$. This gives the final clause of the theorem. Finally, since $f'(x)$ is a polynomial with integer coefficients, $$f'(a+tp^{j-\tau}) \equiv f'(a)\pmod{p^{j-\tau}}$$ for all $a$; and $j-\tau\geq \tau+1$, so the congruence also holds modulo $p^{\tau+1}$. Since $p^{\tau}$ divides $f'(a)$ but $p^{\tau+1}$ does not, then $p^{\tau}$ divides $f'(a+tp^{j-\tau})$ but $p^{\tau+1}$ does not. $\Box$

So once you get past a certain point, you can continue lifting as with Hensel's Lemma.

Niven/Zuckerman/Montgomery then show this at work with $x^2+x+223\equiv 0\pmod{3^j}$.

Modulo $3$,t he only solution is $x=1$. $f'(1)=3\equiv 0\pmod{3}$, and $f(1)\equiv 0\pmod{9}$, so each of the three congruence classes lying above $1$, namely $1$, $4$, and $7$, are roots modulo $9$. Since $f(1)\not\equiv 0\pmod{27}$, then $1$ does not lift to solutions modulo $3^3$. Same thing with $f(7)$. On the other hand, $f(4)\equiv 0 \pmod{27}$, so we get three roots modulo $27$, namely $4$, $13$, and $22$. Each of these is still $0$ modulo $81$, so each of these lifts to three solutions modulo $81$. That is, we have nine solutions modulo $81$, namely $4$, $31$, and $58$ (lying over $4$); $13$, $40$, and $67$ (lying over $13$); and $22$, $49$, and $76$ (lying over $22$).

Since $f(4)\equiv 0 \pmod{3^5}$ and $3^2||f'(4)$, we get nine solutions of the form $4 + 27t$ modulo $243$; but there is exactly one value of $t$, $t=2$, for which $4+27t$ is a root modulo $3^6$. So we get nine solutions modulo $3^6$, which are of the form $(4+27(2)) + 81t = 58+81t$.

Similarly, $f(22)\equiv 0\pmod{3^5}$, $3^2||f'(22)$, and so there are nine solutions of the form $22+27t$ modulo $3^5$; there is precisely one value of $t$, namely $t=0$, for which $22+27t$ is a solution modulo $3^6$, which gives nine solutions modulo $3^6$ lying above $22$, the ones of the form $22+81t$.

Finally, $f'(13)\equiv 0 \pmod{27}$, so $f(13+27t)\equiv f(13)\pmod{3^6}$, but $3^4||f(13)$, so none of the integers $13+27t$ modulo $81$ lift to solutions modulo $243$.

After this point, we can apply the generalized Hensel's Lemma: for each $j\geq 5$, there are precisely 18 solutions modulo $3^j$, of which 12 do not lift to $3^{j+1}$ and each of the remaining six lifts to three solutions each.


In summary: if $f(a)\equiv 0 \pmod{p}$, and $f'(a)\equiv 0\pmod{p}$, to determine if $a$ can be lifted to solutions modulo arbitrarily large powers of $p$, determine if you can reach the point where the Generalized Hensel's Lemma applies, i.e., when $j\geq 2\tau+1$. It can be shown that the inequality holds whenever $j$ is larger than the highest power of $p$ that divides the discriminant of $f$.

share|improve this answer
    
Arturo: the use of the full Taylor's expansion in the first part of your answer is not a good idea because, at the level the answer is written, it is not clear if the individual terms in that expansion each make sense modulo $p^{j+1}$ since there could be some high $p$-powers in the factorial denominators. –  KCd Dec 14 '11 at 7:39
    
@Kcd: Good point; thanks for bringing it up. Let me think about it a bit and see how to fix the presentation. –  Arturo Magidin Dec 14 '11 at 17:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.