Hensel's Lemma

Hensel's Lemma (as discussed in $\S 2.6$ of NZM), can be formulated as follows: Let $f(x)$ be a polynomial with integral coefficients, let $p$ be a prime, and suppose that $f(a) \equiv 0 \left(\bmod p^{j}\right)$ for some $j \geq 1$ .

Case 1. $f^{\prime}(a) \not \equiv 0(\bmod p)$ . (The "regular" case.) There is a unique $c(\bmod p)$ such that $f\left(a+c p^{j}\right) \equiv 0\left(\bmod p^{j+1}\right)$ . This $c$ is the root of the linear congruence

$f^{\prime}(a) c \equiv-f(a) / p^{j} (\bmod p)$

Case 2. $f^{\prime}(a) \equiv 0(\bmod p)$ . (The "singular" case.) If $f(a) \equiv 0\left(\bmod p^{j+1}\right)$ then $f\left(a+c p^{j}\right) \equiv 0 \left(\bmod p^{j+1}\right)$ for all $c (\bmod p)$ . If $f(a) \not \equiv 0\left(\bmod p^{j+1}\right)$ then $f\left(a+c p^{j}\right) \not \equiv$ $0\left(\bmod p^{j+1}\right)$ for all $c(\bmod p)$ .

Problem 1

Let $f(x)=x^{2}+1$ . Note that $f(9) \equiv 0(\bmod 41)$ , and that $f^{\prime}(9)=18 \not \equiv 0$ $(\bmod 41)$ . Since $f(9) / 41=2$ , it follows that to lift this root we must take $c$ so that $18 c \equiv -2 (\bmod 41)$ . Use LinCon to determine this $c$ , and thus find a root of $f(x) \equiv 0\left(\bmod 41^{2}\right)$ . Confirm your work by applying PolySolv to $f(x)$ , first with $m=41$ , and then with $m=41^{2}=1681$ .

Problem 2

Let $f(x)=x^{3}+x+1$ , as in Problem 2 of Laboratory 5. From Theorem A. 5 on p . 488 of NZM we know that all roots of $f(x)(\bmod p)$ are non-singular, unless $p$ divides the discriminant of $f$ , denoted $D(f)$ . In the present case, $D(f)=-31$ (verify this with PolynomialDiscriminant). Apply PolySolv to $f(x)$ , and take $m=31$ . Note the two roots. Now apply PolySolv to $f^{\prime}(x)=3 x^{2}+1$ . Thus discover that one of the roots of $f(\bmod 31)$ is singular, and that the other one is regular. From Case 2 of Hensel's Lemma we know that the singular root either lifts to 31 roots $\left(\bmod 31^{2}\right)$ , or else does not lift. Apply PolySolv to $f(x)$ with $m=31^{2}=961$ , to determine which.

Problem 3

The mundane chore of applying LinCon to lift roots to higher powers of $p$ is automated by the program Hensel. Use Hensel for $f(x)=x^{2}+1$ and $p=5$ . View the solutions $\left(\bmod 5^{j}\right)$ that lie above the root $x \equiv 2(\bmod 5)$ . Then view the other solution $(\bmod 5)$ , and those that lie above it. Note that in both cases, the sequence $c_i$ of coefficients seems to exhibit no simple pattern.

Problem 4

The polynomial $f(x)=x^{2}+1$ , when considered $(\bmod 2)$ , has a singular root $x \equiv 1$ $(\bmod 2)$ . Does this lift to a solution $(\bmod 4)$ ? By invoking the program Hensel, one may see that the answer is "No". Now apply Hensel to $g(x)=x^{2}+3$ . Note that $f(x)$ and $g(x)$ are the same $(\bmod 2)$ , but different $(\bmod 4)$ . The the solution $x \equiv 1(\bmod 2)$ can be lifted to $x \equiv 1(\bmod 4)$ . You can view its companion $x \equiv 3(\bmod 4)$ . Note that the two roots $1,3(\bmod$ $4)$ both lie above the single root $1(\bmod 2)$ . You may use the combobox to switch between the two roots $(\bmod 4)$ , but in both cases neither of these roots lift to give a root $(\bmod 8)$ . Finally, take $h(x)=x^{2}+7$ . Note that $g(x)$ and $h(x)$ are the same $(\bmod 4)$ , but different $(\bmod 8)$ . Apply Hensel to $h(x)$ , and note that the root $1(\bmod 4)$ lifts to two roots, $1,5(\bmod 8)$ . Also, note that the root $3(\bmod 4)$ lifts to two roots, $3,7(\bmod 8)$ . Use the combobox to explore the tree of solutions $\left(\bmod 2^{j}\right)$ , and sketch it through $\left(\bmod 2^{7}\right)$ , say. Note that two long strands are forming. How far must these strands be extended before one can be sure that they continue indefinitely? (Hint: Apply Theorem 2.24 of NZM. Theorem A. 5 on p. 488 is also relevant.)

Problem 5

Use Hensel to explore the tree of solutions of $x^{2}+x+223\left(\bmod 3^{j}\right)$ , through $j=7$ . Sketch your findings. Thus verify and extend Table 1 on p. 90 of NZM.

Problem 6

Apply Hensel to $f(x)=5 x+3$ . Note that the sequence of $c_i$ seems to be periodic. For each prime $p<20$ , note the apparent period. We know that the base 10 expansion of a real number $x$ is periodic if and only if $x$ is rational, and that the least period of the base 10 expansion of $a / q$ is the order of $10(\bmod q)$ , provided that $\gcd(10 a, q)=1$ . (This is Problem 30 at the end of $\S 2.8$ of NZM.) Is there an analogue at work here? Explore.

Problem 7

Apply Hensel to $f(x)=x^{4}-10 x^{3}+35 x^{2}-50 x+24\left(\bmod 3^{j}\right)$ , and report your findings.

Problem 8

Apply Hensel to $f(x)=x^{5}-15 x^{4}+85 x^{3}-225 x^{2}+274 x-120\left(\bmod 3^{j}\right)$ , and report your findings.

Problem 9

Use Hensel to study $f(x)=x^{k}-1 \left(\bmod p^{j}\right)$ for various combinations of $k$ and $p$ . For what combinations do you encounter singular roots? (Note: The number of roots (mod $p$ ) is $\gcd(k,p-1)$ , according to Theorem 2.37 of NZM.)