\begin{document}
\documentclass[11pt]{article}

\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage{complexity}
\usepackage{graphicx}

\usepackage{palatino} %what a beautiful font!

\newcommand{\handout}[5]{
\noindent
\begin{center}
\framebox[\textwidth]{
\vbox{
\hbox to \textwidth { {\bf #2}\hfill {\bf Computational Number Theory }
}
\vspace{4mm}
\hbox to \textwidth { {\Large \hfill #5  \hfill} }
\vspace{2mm}
\hbox to \textwidth { {\em #3 \hfill #4} }
}
}
\end{center}
\vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{Instructor: #3}{Scribe:
#4}{Lecture #1}}

\newtheorem{theorem}{Theorem}
\newtheorem{theorem*}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[]{Fact}
\newtheorem{subclaim}[theorem]{Subclaim}

% my custom commands
\newcommand{\inparen}[1]{\left(#1\right)}             %\inparen{x+y}  is (x+y)
\newcommand{\inbrace}[1]{\left\{#1\right\}}           %\inbrace{x+y}  is {x+y}
\newcommand{\insquar}[1]{\left[#1\right]}             %\insquar{x+y}  is [x+y]
\newcommand{\inangle}[1]{\left\langle#1\right\rangle} %\inangle{A}    is <A>
\newcommand{\abs}[1]{\left|#1\right|}                 %\abs{x}        is |x|
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}        %\norm{x}       is ||x||
\newcommand{\union}{\cup}
\newcommand{\Union}{\bigcup}
\newcommand{\intersection}{\cap}
\newcommand{\Intersection}{\bigcap}
\newcommand{\super}[2]{#1^{\inparen{#2}}}             %\super{G}{i-1} is G^{(i-1)}
\newcommand{\setdef}[2]{\inbrace{{#1}\ : \ {#2}}}
\newcommand{\inv}[1]{#1^{-1}}
\newcommand{\inrpdt}[2]{\left\langle{#1},{#2}\right\rangle}%\inrpdt{x}{y} is <x,y>.
\newcommand{\pderiv}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\iso}{\cong}
\newcommand{\bea}[1]{\begin{eqnarray*} #1 \end{eqnarray*}}
\newcommand{\legendre}[2]{\inparen{\frac{#1}{#2}}}

% Commands specific to this file
% TODO: Find the right way to typeset group index
\DeclareMathOperator{\Sym}{Sym}
\newcommand{\gpidx}[2]{\insquar{#1 : #2}}             %\gpidx{H}{K}   is [H : K]
\newcommand{\gpigs}[2]{\gpidx{\super{G}{#1}}{\super{G}{#2}}} %Group index of g super ...
\newcommand{\llhd}{\!\!\lhd\!\!\lhd}
\newcommand{\roundoff}[1]{\left\lfloor #1 \right\rceil}

% \newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\renewcommand{\R}{\mathbb{R}}
\renewcommand{\C}{\mathbb{C}}

%for algorithms
\renewcommand{\algorithmicrequire}{\textbf{Input:}}

% Problems we look at
\newcommand{\GIso}{\lang{Graph\text{-}Iso}} %Without \text, ugly minus instead of hyphen.
\newcommand{\GAut}{\lang{Graph\text{-}Aut}}
\newcommand{\SStab}{\lang{Set\text{-}Stab}}

%for Quantum computing
\newcommand{\q}[1]{\left|#1\right\rangle}

\lecture{26 : Hensel Lifting }{CS681}{Piyush P Kurur}{Ramprasad Saptharishi}

We first saw two algorithms to factor univariate polynomials over
finite fields. We shall now get into bivariate factoring over finite
fields. Before that, we need to look at a very important and powerful
tool called Hensel Lifting.

\section{Hensel Lifting}

The intuition behind Hensel Lifting is the following - you have a
function for which you need to find some root. Suppose you have an $x$
very close to a root $x_0$ in the sense that there is a small
error. The question is how can you use $x$ and the polynomial to get a
closer approximation?

Recall the Newton Rhapson Method you might have done in calculus to
find roots of certain polynomials. Let us say $f$ is the polynomial
and $x_0$ is our first approximation of a root. We would like to get a
better approximation. For this, we just set $x_1 = x_0 + \varepsilon.$
And by the Taylor Series,
\begin{eqnarray*}
f(x_1) = f(x_0 + \varepsilon) & = & f(x_0) + \varepsilon f'(x_0)
+ \varepsilon^2\frac{f''(x)}{2!} + \cdots\\
& = & f(x_0) + \varepsilon f'(x_0) + O(\varepsilon^2)
\end{eqnarray*}
Ignoring the quadratic error terms, we want a better
approximation. Thus, in a sense, we would want $f(x_1)$ to be very
close to $0.$ To find the right $\varepsilon$ that would to the trick,
we just set $f(x_1) = 0$ and solve for $\varepsilon.$ With just some
term shuffling, we get
$$\epsilon = -\frac{f(x_0)}{f'(x_0)} \implies x_1 = x_0 -\frac{f(x_0)}{f'(x_0)}$$

But one crucial property we need here is that $f'(x_0)$ is not zero
for otherwise division doesn't make sense. In the same spirit, we
shall look at version $1$ of the Hensel Lifting.

\subsection{Hensel Lifting: Version $1$}

\begin{theorem}
Let $p$ be a prime and $c$ and positive integer, and let $f$ any
polynomial. Suppose we have a solution $x$ that satisfies
$$f(x) = 0\bmod{p^c}\qquad,\qquad f'(x)\neq 0\bmod{p}$$
then we can lift'' $x$ to a better solution $x^\star$ that satisfies
$$f(x^\star) = 0\bmod{p^{2c}}\qquad,\qquad x^\star = x\bmod{p^c}$$
\end{theorem}

It is of course clear that if $f(x^\star) = 0\bmod{p^{2c}}$ then
$f(x^\star) = 0\bmod{p^c}$ but the converse needn't be
true. Therefore, $x^\star$ is a more accurate root of $f.$ The proof
of this is entirely like the proof of the Newton Rhapson Method.

\begin{proof}
Set $x^\star = x + hp^c.$ We need to find out what $h$ is. Just as in
newton rhapson,
\begin{eqnarray*}
f(x^\star) = f(x+hp^c) & = & f(h) + hp^cf'(x) + (hp^c)^2\frac{f''(x)}{2!}
+ \cdots\\
& = & f(h) + hp^cf'(x) + O((hp^c)^2)\\
& = & f(h) + hp^cf'(x)\bmod{p^{2c}}
\end{eqnarray*}
Since we want $f(x^\star) = 0\bmod{p^{2c}}$, we just set the LHS as
zero and we get
$$h = \frac{f(x)}{p^cf'(x)}$$
Note that $f(x) = 0\bmod{p^c}$ and therefore it makes sense to divide
$f(x)$ by $p^c.$ Thus our $x^\star = x + hp^c$ where $h$ is defined as
above and by definition $x^\star = x\bmod{p^c}.$
\end{proof}

Another point to note here is that since $x^\star = x\bmod{p^c}$,
$f(x^\star)\neq 0\bmod{p}$ as well. Therefore, we could lift even
further. And since the accurace doubles each time, starting with $f(x) = 0\bmod{p}$, $i$ lifts will take us to an $x^\star$ such that
$f(x^\star) = 0\bmod{p^{2^i}}.$

Hensel Lifting allows us to get very good approximations to roots of
polynomials. The more general version of Hensel Lifting plays a very
central role in Bivariate Polynomial Factoring.

\subsection{Hensel Lifting: Version $2$}

In the first version of the Hensel Lifting, we wanted to find a root
of $f.$ Finding an $\alpha$ such that $f(\alpha) = 0\bmod{p}$ is as good as
saying that we find a factorization $f(x) = (x - \alpha)g(x) \bmod{p}.$ And also, the additional constraint that
$f'(\alpha) \neq 0\bmod{p}$ is just saying that $\alpha$ is not a
repeated root of $f$ or in other words $(x-\alpha)$ does not divide
$g.$ With this in mind, we can give the more general version of the
Hensel Lifting.

\begin{theorem}
Let $R$ be a UFD and $\mathfrak{a}$ any ideal of $R.$ Suppose we have
a factorization $f = gh\bmod{\mathfrak{a}}$ with the additional
property that there exists $s,t\in R$ such that $sg + th = 1\bmod{\mathfrak{a}}.$ Then, we can lift this factorization to
construct $g^\star, h^\star, s^\star, t^\star$ such that
\begin{eqnarray*}
g^\star & = & g\bmod{\mathfrak{a}}\\
h^\star & = & h\bmod{\mathfrak{a}}\\
f & = &g^\star h^\star \bmod{\mathfrak{a}^2}\\
s^\star g^\star + t^\star h^\star & = &1\bmod{\mathfrak{a}^2}
\end{eqnarray*}
Further, for any other $g',h'$ that satisfy the above four properties,
there exists a $u\in \mathfrak{a}$ such that
\begin{eqnarray*}
g' & = & g^\star(1+u)\bmod{\mathfrak{a}^2}\\
h' & = & h^\star(1-u)\bmod{\mathfrak{a}^2}
\end{eqnarray*}
Therefore, the lifted factorization in some sense is unique.
\end{theorem}
\begin{proof}(sketch)
Set $g^\star = g + te$ and $h^\star = h + se.$ Now solve for $e$ and
that should do it. Finding $s^\star,t^\star$ is also similar. (painful!)
\end{proof}

Here is a more natural way is to look at this. What we want is a solution to
the curve $XY = f$ where $f$ is the function we want to factorize. Let
us call $F(X,Y) = f - XY.$ We have $X,Y$ as solutions such that
$F(X,Y) = f - XY = e.$ Now
\begin{eqnarray*}
F(X+\Delta X, Y + \Delta Y) & = & f - (X+\Delta X)(Y+\Delta Y)\\
& = & f - XY - (X\Delta Y + Y\Delta X) + O(\Delta^2)\\
& = & F(X,Y) - (X\Delta Y + Y\Delta X)\\
& = & e - (X\Delta Y + Y\Delta X)
\end{eqnarray*}
Further, we also know that $sX + tY = 1$ and therefore, if we just set
$\Delta X = se$ and $\Delta Y = te$, we have
$$F(X+\Delta X,Y+\Delta Y) = e - e(sX + tY) = 0 \bmod{\Delta^2}$$

One should also be able to look at the lifts of $s$ and $t$ as
solving appropriate equations. In the next class, we shall look at
this technique put to use in Bivariate Factorization.
\end{document}