Hensel Lifting F83168

1. **Problem Statement:** We want to understand why for any polynomial $f(x)$ and prime $p$, every solution to the congruence $$f(x) \equiv 0 \pmod{p}$$ can be lifted to at least one solution modulo higher powers of $p$, i.e., $$f(x) \equiv 0 \pmod{p^k}$$ for any integer $k \geq 2$. 2. **Key Idea: Hensel's Lemma** The main tool to explain this is Hensel's lemma, which states that if $x_0$ is a solution modulo $p$ and the derivative $f'(x_0)$ is not congruent to zero modulo $p$, then there exists a unique solution $x_k$ modulo $p^k$ such that $$x_k \equiv x_0 \pmod{p}$$ and $$f(x_k) \equiv 0 \pmod{p^k}.$$ 3. **Why does this work?** - Suppose $x_0$ satisfies $f(x_0) \equiv 0 \pmod{p}$. - If $f'(x_0) \not\equiv 0 \pmod{p}$, then the solution can be "lifted" uniquely to modulo $p^2$, $p^3$, and so on, by solving a linearized equation at each step. 4. **Intermediate step: Lifting from $p$ to $p^2$** We look for $x_1 = x_0 + tp$ such that $$f(x_1) = f(x_0 + tp) \equiv 0 \pmod{p^2}.$$ Using Taylor expansion modulo $p^2$: $$f(x_0 + tp) \equiv f(x_0) + tp f'(x_0) \pmod{p^2}.$$ Since $f(x_0) \equiv 0 \pmod{p}$, write $f(x_0) = p m$ for some integer $m$. We want $$p m + t p f'(x_0) \equiv 0 \pmod{p^2} \implies m + t f'(x_0) \equiv 0 \pmod{p}.$$ Because $f'(x_0) \not\equiv 0 \pmod{p}$, this linear congruence has a unique solution for $t$ modulo $p$. 5. **If $f'(x_0) \equiv 0 \pmod{p}$** - The lifting may fail or multiple solutions may appear. - The number of solutions modulo $p^k$ can increase compared to modulo $p$. - This happens because the polynomial is "singular" at $x_0$ modulo $p$. 6. **Summary of conditions for number of solutions to increase:** - If $f'(x_0) \equiv 0 \pmod{p}$ for some root $x_0$ modulo $p$, then the number of solutions modulo $p^k$ can be greater than the number modulo $p$. - Otherwise, each root modulo $p$ lifts uniquely to a root modulo $p^k$, so the number of solutions remains the same. 7. **Final conclusion:** - Every solution modulo $p$ can be lifted to at least one solution modulo $p^k$. - The number of solutions increases when the polynomial has roots modulo $p$ where the derivative also vanishes modulo $p$. This explains the behavior of solutions to $f(x) \equiv 0 \pmod{p^k}$ as $k$ increases.