Hensel's Lemma

note

This is Lab 10 from Clint by Hugh Montgomery, edited by Elad Zelingher. All rights reserved to Hugh Montgomery.

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