HenselLift

The $b$-adic root of a polynomial that reduces to seed mod $b$, by Newton's iteration — Hensel's lemma made to run. AdicSqrt is the special case $f = x^2 − a$.

HenselLift(f, seed, b, prec?)needs $f(seed) ≡ 0$ and $f'(seed)$ a unit mod $b$; $f$ in one free variable

AdicSqrt(x, prec?)a square root in $\mathbb{Z}_p$, prime $p$; declines when there is none

Typed signatures

Type	Package	Applies
(any, integer, integer, integer?) -> value	numerals	always

Domain: Numeral systems

Details

• Each Newton step doubles the number of correct digits, so 20 digits take five steps
• The result is capped at prec (default 20): a root found this way is known modulo $b^{prec}$ and nothing more, which is where capped values come from
• A root with $f'(seed) ≡ 0$ is not simple and does not lift this way — $x^3 − x$ from 1 in $\mathbb{Z}_2$ declines
• Composite $b$ works when $f'(seed)$ is coprime to $b$, and that is how the non-rational elements of $\mathbb{Z}_{10}$ appear: $x^2 − x$ from 5 lifts to the idempotent $…890625$
• Square roots: an odd prime needs $x$ to be a quadratic residue mod $p$; $p = 2$ needs $x ≡ 1 \pmod 8$ and starts the iteration one level up, since $f'(a) = 2a$ is not a unit

Examples

Basic #

$\sqrt{2}$ in $\mathbb{Z}_7$, from $3^2 ≡ 2 \pmod 7$

live ↗

In$\mathrm{HenselLift}(x^2-2, 3, 7, 6)$Out$\mathrm{AdicNumeral}(7, 38\,181, 6)$

and squaring it gives 2 back, to the same precision

live ↗

In$\mathrm{AdicSqrt}(\mathrm{AdicNumeral}(7, 2), 6)^2$Out$\mathrm{AdicNumeral}(7, 2, 6)$

Applications #

a 10-adic idempotent: $e^2 = e$, and $e ≠ 0, 1$

live ↗

In$\mathrm{AdicExpansion}(\mathrm{HenselLift}(x^2-x, 5, 10, 8))$Out$\text{…12890625 + O(10\textasciicircum{}8)}$

Possible issues #

3 is not a square mod 7, so it has no 7-adic square root

live ↗

In$\mathrm{AdicSqrt}(\mathrm{AdicNumeral}(7, 3))$Out$\mathrm{AdicSqrt}(\mathrm{AdicNumeral}(7, 3))$

Declines at a non-simple root: $f'(1)=2$ is not a unit mod 2, so Newton's step can't lift

live ↗

In$\mathrm{HenselLift}(x^3-x, 1, 2, 6)$Out$\mathrm{HenselLift}(x^3-x, 1, 2, 6)$

Neat examples #

1 / 2

The two roots of $x^2=x$ lifted in $\mathbf{Z}_{10}$ are orthogonal idempotents: their product is 0

live ↗

In$\mathrm{HenselLift}(x^2-x, 5, 10, 8)\mathrm{HenselLift}(x^2-x, 6, 10, 8)$Out$\mathrm{AdicNumeral}(10, 0, 8)$

About

Examples	7

See also: AdicNumeral, AdicExpansion