\documentclass[fullpage]{article}
\newtheorem{define}{Definition}
%\usepackage{amsmath}
\usepackage{amsfonts}
%\usepackage{amssymb}
\input{preamble.tex}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\emod}[1]{\, (\bmod\ #1)}
\begin{document}
\lecture{10}{March 12, 2012}{Madhu Sudan}{Rachel Lin}
Today, we will continue our approach to factoring bivariate
polynomials. We will first focus on the tool of Hensel's Lifting; and then
describe how we perform the factoring.
\section{Hensel's Lifting}
Suppose $f(x,y)=g(x)h(x)\pmod{y}$. We wanted a factorization for higher
powers of $y$: $f(x,y)=\tilde{g}(x,y)\tilde{h}(x,y)\pmod{y^{2k}}$. Hensel's
Lifting says we can obtain this if $g$ and $h$ are ``relatively prime,'' and
that the $\tilde{g}$ and $\tilde{h}$ we obtain are essentially unique. Formally:
\begin{lemma}[Hensel's Lifting] \label{lem:hensel}
If $R$ is a ring, $I\subseteq R$ is an ideal,
and there exist $f,g,h,a,b$ in $R$ such that
\begin{itemize}
\item[(H1) ]$f=gh\pmod{I}$
\item[(H2) ]$ag+bh=1\pmod{I}$.
\end{itemize}
Then, for every positive interger $s$ that is a power of 2, there exist
$\tilde{g},\tilde{h}$ and $\tilde{a},\tilde{b}$ in $R$, such that
\begin{itemize}
\item[(C1) ]$f=\tilde{g}\tilde{h}\pmod{I^{s}}$
\item[(C2) ]$\tilde{g}\tilde{a}+\tilde{b}\tilde{h}=1\pmod{I^{s}}$
\item[(C3) ]$g=\tilde{g}\pmod{I}$ and $h=\tilde{h}\pmod{I}$
\end{itemize}
Furthermore, the solution satisfying the above three conditions is ``unique''
in the following sense:
\begin{description}
\item[Uniqueness:] We say that an ideal $J$ is {\em special} if for
all all interger $k$, and $a, b$ such that $ab \in J^k$, there
is an integer $l$ such that $a \in J^l$ and $b \in J^{k-l}$.
Assume that $I$ is special. Then, for every two solutions $g_1, h_1$ and $g_2,
h_2$ satisfying contidions C1 to C3, there exists $u \in I^t$,
such that:
\[g_2 = g_1(1+u) \pmod{I^{s}}, \qquad h_2 = h_1(1-u)\pmod{I^{s}}\]
\end{description}
\end{lemma}
As we will see later, towards factoring a bivariate polynomial $f \in
\mathbb{F}_q[x, y]$, we will apply the Hensel's lifting to $R =
F_q[x,y]$, $I = (y)$ and a factorization of $f$ mod $I$. When $I = (y)$,
$f \pmod{y}$ is simply a univariate polynomial on $x$ over
$\mathbb{F}_q$, which we know how to factor from previous
lectures. Next we proceed to prove Lemma~\ref{lem:hensel}.
\begin{proof}
We prove this lemma by induction.
\paragraph{Base Case $s = 2$:} We first show that there exists
$\tilde g, \tilde h$ and $\tilde a, \tilde b$ satisfying C1
to C3, and then establish the uniqueness of the solution. By
condition H1 and H2, we have
\[f = g h + q, \mbox{ for some } q \in I\]
\[ag + bh = 1 + r \mbox{ for some } r \in I\]
Write $\tilde{g} = g+g_1$, $\tilde{h} = h +h_1$, for some $g_1, h_1
\in I$ to be set. Then
\[\tilde{g} \tilde{h} = g h + g_1 h
+ h_1 g + h_1 g_1\] Since $h_1 g_1 \in I^2$, in order to satisfy
condition C1, we want $g_1 h + h_1 g + h_1 = q \pmod{I^2}$. To
satisfy this, set $g_1 = b q$, $h_1 = a q$, and get that $g_1 h + h_1
g = q (b h + a g) = q(1 + r)$, which equals to $q$ modulo $I^2$ as
required. By construction $\tilde g = g \pmod I$ and $\tilde h = h
\pmod I$, satisfying condition C3. To show that $\tilde g$ and
$\tilde h$ are also relatively prime, observe that $a \tilde{g} + b
\tilde{h} = a g + b h + r' = 1 + r + r'$, for some $r'\in I$. Let
$r'' = r + r' \in I$. Now we
can take $\tilde{a} = a (1 - r'')$ and $\tilde{b} = b (1 - r'')$, and get
that: \[\tilde{a} \tilde{g} + \tilde{b} \tilde{h} = (1-r'') (a
\tilde{g} + b \tilde{h}) = (1 - r'') (1 + r'') = 1 - r''^2 = 1 \mbox{
}(\mathrm{mod}\mbox{ } \mbox{ } I^2)\]
Now it remains to show that $\tilde g, \tilde h$ is the unique
solution satisfying C1 to C3. That is, if $g^*, h^*$ is a different
solution satisfying C1 to C3, then there is $u \in I$ such that $g^*
= \tilde g (1+u)$ and $h^* = \tilde h (1-u)$.
By contidion C3, we have $g^* = \tilde{g} + g_2$ and $h^* = \tilde{h}
+ h_2$ for some $g_2, h_2 \in I$ (because, modulo $I$, we know that
$g^* = g = \tilde{g}$ and $h^* = h = \tilde{h}$). Therefore, we have:
\[g^* h^* = \tilde{g} \tilde{h} + g_2 \tilde{h} + h_2 \tilde{g} + g_2
h_2\]
By condition C1, we know that $g^* h^* = f = \tilde{g}
\tilde{h}\pmod {I^2}$. Thus, the above equation modulo $I^2$ gives,
\[g_2 \tilde{h} + h_2 \tilde{g} = 0 \pmod {I^2}\]
By condition C2, we have $\tilde a \tilde g + \tilde b \tilde h = 1
\pmod {I^2}$. Therefore,
\begin{eqnarray*}
& & \tilde b (g_2 \tilde{h} + h_2 \tilde{g}) = 0 \pmod {I^2} \\
& & g_2 \tilde b\tilde{h} + \tilde b h_2 \tilde{g} = 0 \pmod {I^2}
\\
& &g_2 ( 1- \tilde{a} \tilde g) + \tilde b h_2 \tilde{g} = 0 \pmod
{I^2} \\
& &g_2 = (\tilde{a}g_2 - \tilde b h_2) \tilde{g} \pmod {I^2}
\end{eqnarray*}
Let $u = \tilde{a}g_2 - \tilde b h_2$. Since $g_2$ and $h_2$ are all
elements in $I$, so is $u$. Furthermore we have $g^* = \tilde g + g_2
= \tilde g(1+u)$. Similarly, by symmetry, we obtain that
\[h_2 = (\tilde b h_2 - \tilde{a}g_2 ) \tilde{h} \pmod {I^2} \]
Therefore, $h^* = \tilde h (1-u)$. This concludes the proof for the
base case.
\paragraph{Induction Step:}
Assume that for the case of $s =
t$, there exist $g_0, h_0 \in R[x]$ and $a_0, b_0 \in I^t$
satisfying conditions C1 to C3, and the solution to the three
conditions is ``unique''. We show that for the case of $s = 2t$, we can construct $g_1,
h_1 \in R[x]$ and $a_1, b_1 \in I^{2t}$ satisfying conditions C1 to
C3, and the solution is also unique.
The existence of $g_1, h_1, a_1, b_1$ satisfying conditions C1 to C3
follows exactly the same proof as in the base case. Therefore, we
focus on the proof of uniqueness. Let $g_1, h_2$ be a different
solution from $g_1, h_1$. Then both $g_1 \pmod {I^t}$, $h_1 \pmod
{I^t}$ and $g_2 \pmod {I^t}$, $h_2 \pmod {I^t}$ are solutions
satisfying C1 to C3 for the case of $s = t$. Then by the induction
hypothesis, we have that there is a $u_0 \in I^{t/2}$ such that,
\[(g_2 \pmod {I^t}) = (g_1 \pmod {I^t}) (1+u_0) \pmod {I^t} \]
\[(h_2 \pmod {I^t}) = (h_1 \pmod {I^t}) (1-u_0) \pmod {I^t} \]
This implies that
\[g_2 = g_1 (1+u_0) \pmod {I^t} \]
\[h_2 = h_1 (1-u_0) \pmod {I^t} \]
Notice that this is differerent
from the condition in the base case where any two solutions must
equal modulo $I$. Nevertheless, following the same argument, we can
derive that there is an element $u \in I^t$ such that,
\[g_2 = g_1 (1+u_0)(1+u) \pmod {I^{2t}} \]
\[h_2 = h_1 (1-u_0)(1-u) \pmod {I^{2t}} \]
Below we show that $u_0$ is in fact an element in $I^t$, then
\[g_2 = g_1 (1+u_0+u + u_0u) = g_1 (1+u_0+u) \pmod {I^{2t}} \]
\[h_2 = h_1 (1-u_0-u + u_0u) = h_1 (1-u_0-u) \pmod {I^{2t}} \] Thus
$g_2 = g_1(1+ u') $ and $h_2 = h_1(1- u') $ for $u' = u_0 + u \in
I^t$ as desired.
To show that $u_0 \in I^t$, consider:
\begin{eqnarray*}
& g_2h_2= g_1h_1 (1-u_0^2) (1-u^2) \pmod {I^{2t}} & \\
& g_2h_2= g_1h_1 (1-u_0^2) \pmod {I^{2t}} & [\mbox{as } u \in I^t]
\end{eqnarray*}
Since $g_1$ and $h_1$ are not elements in $I$, for the last euqation
to hold, it must be the case that $u_0 \in I^t$. Therefore, we
conclude the lemma.
\end{proof}
\section{Outline of Factoring, revisited}
We now give a more complete outline for factoring bivariate polynomials.
Given a monic $f(x,y)\in\mathbb{F}_q[x,y]$, with total degree
$d$, the factoring algorithm $SPLIT$ proceeds as follows:
\begin{enumerate}
\item If $g =\gcd(f, \frac{\partial f}{\partial x}) \ne 1$, then output
$(g, f/g)$ and stop. Otherwise, continue the following steps.
\item Find $y_0\in \mathbb{F}$ such that $f(x,y_0)$ has no repeated
factors. This can be done by computing
$\mathrm{Res}\left(f,\frac{\partial f}{\partial x}\right)$, and
pluging in $y_0 = 1, 2, \ldots$ until we find one that makes the
resultant non-zero.
We claim that this will terminiate in at most $d^2$ iterations, as
$\mathrm{Res}\left(f,\frac{\partial f}{\partial x}\right)$ is a
polynomial in $y$ with degree at most $d^2$. Futhermore, the first
step ensures that $f$ does not have repeated roots; therefore,
$\mathrm{Res}\left(f,\frac{\partial f}{\partial x}\right)$ is not a
zero polynomial. Hence it has at most $d^2$ roots.
\item Put $f_{y_0}(x)=f(x,y) \pmod {(y-y_0)} = f(x, y_0)$ and factor it. This can be done by using
the factoring algorithm for univariate polynomial over
$\mathbb{F}$. Let $g$ be an irreducable factor of $f_{y_0}(x)$, and
$h$ such that $f = gh \pmod {(y-y_0)}$.
% Some factor should be linear; if not,
% we extend $K$. We know that every field can be extended until the polynomial
% splits completely, but we only need a low degree extension with one linear
% factor, say $p(x)=(x-\alpha)h(x)$. We assume $(x-\alpha)$ and $h(x)$ are
% relatively prime.
\item Now we apply Hensel's Lifting to obtain $f= g_1
h_1 \pmod{(y-y_0)^t}$ for a $t \approx d^2$
\item Next, from $ g_1$ we ask if we can find a nontrivial factor
$\tilde g$ of $f$. This is done through the ``Jump'' step, which
tries to find polynomials $\tilde g$ and $\tilde h$ such that
$\tilde g = g_1 \tilde h \pmod{(y-y_0)^t} $, and $\tilde g$ has small
degrees in $y$ (smaller than $d$) and minimal degree in
$x$.
\item Finally, return $\tilde g$ and $f/\tilde g$.
\end{enumerate}
\end{document}