\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{27 : Bivariate Factoring }{CS681}{Piyush P Kurur}{Ramprasad Saptharishi} We shall now look at Bivariate Factoring. This is an instance where there are a lot of corner cases that need to be handled but we shall make some preliminary assumptions on the polynomial. We shall soon see how we can ensure those properties as well. \section{Bivariate Factoring} We are given a polynomial $f\in K[X,Y]$ that we would like to factor. Before we go into factorization as such, we first need to figure out how to do the $\gcd$ algorithm over two variables. \subsection{The Euclidian Algorithm for $K[X,Y]$} Lets say we are given two polynomials $f(X,Y)$ and $g(X,Y).$ How do we compute their $\gcd$? Remember that when we had univariate factoring, the euclidian algorithm would divide. But over $K[X,Y]$, how do we do that? Hence, instead of looking at these polynomials over $K[X,Y]$, we look at them as univariate polynomials rational functions over one variables, namely $K(X)[Y].$ Thus coefficients could now be of the form $p(X)/q(X).$ This then give rise to another problem, can the denominator keep getting larger? That is a serious issue since during the process, we could potentially be doubling the degree at each step But clearly, the final answer cannot have a really large $X$-degree; it clearly must be bounded by the $X$ degrees of $f$ and $g.$ So what we do instead is do these computations modulo a number of irreducible polynomials. We just need to make sure that the product of all these irreducible polynomials have degree larger than the $X$ degree of both $f$ and $g.$ \\ This would then let us compute the $\gcd$ of two bivariate polynomials. Now we can think of $f$ as an element in $K[X][Y]$, a polynomial in $Y$ each of whose coefficients are polynomials in $X.$ The first things we do is pull out the gcd of all the coefficients. And we also express $f$ as an element of $K[Y][X]$ and repeat the same thing. Then we shall assume that $f$ is squarefree. This needs justification but we shall do this later. But for the moment let us assume that this can be done and proceed. Now we have $f(X,Y) \in K[X][Y].$ We shall put $Y = 0$ to get a univariate polynomial in $X.$ Since we have already done factoring of univariate polynomials, we shall factorize $f(X,0)$ into coprime factors $f(X,0) = g_0h_0.$ Note that this is just saying $$ f = g_0h_0 \bmod{Y} $$ since $Y=0$ is precisely taking $\bmod{Y}.$ And we further have the property, because the factors are coprime\footnote{we shall get back to this} that $sg_0 + th_0 = 1\bmod{Y}.$ Thus we can Hensel Lift this factorization for $k$ steps to get $$ f = g_kh_k\bmod{Y^{2^k}} $$ We would now argue that after sufficient hensel lifting, we can retrieve a factor of $f.$ \begin{claim} If $f$ was not irreducible, hen there is an irreducible factor of $f$, say $g$ such that $g = g_0l_0\bmod{Y}$ \end{claim} \begin{proof} This is obvious. Suppose $f$ factorizes into irreducible factors as $f_0f_1\cdots f_l.$ Then clearly, $$ f = f_0f_1\cdots f_l \bmod{Y} $$ And therefore $g_0$ must divide one of these factors and whatever factor it may be, set that as $g.$ Therefore, $g = g_0l_0\bmod{Y}$ \end{proof} Now start with $g = g_0l_0\bmod{Y}$ and lift this to $k$ steps. What we know is that $\deg_X(g) < \deg_X(f)$ and $\deg_Y(g)\leq \deg_Y(f).$ What we have is just $f = g_kh_k\bmod{Y^{2^k}}.$ We shall use this to try and get hold of a factor. Suppose we look at the following equation to solve: \begin{eqnarray*} \tilde{g} & = & g_k\tilde{l}\bmod{Y^{2^k}}\\ \deg_X(g) & < & \deg_X(f)\\ \deg_Y(g) & \leq & \deg_Y(f) \end{eqnarray*} Firstly, does this system of equations have a solution? Indeed; we just say that $g = g_0l_0\bmod{Y}$ can be lifted to $k$ steps to give $g = g_kl_k\bmod{Y^{2^k}}$ and clearly $g$ and $l_k$ satisfy the system of equations. Therefore, we are guaranteed that at least one such solution exists if $f$ is not irreducible. Now, how do we compute such a solution? Notice that we already know $g_k$ and once we have $g_k$, if we think of the coefficients of $\tilde{g}$ and $\tilde{l}$ as variables, the above is just a system of linear equations. Thus, one could solve that system using gaussian elimination to get some solution $\tilde{g}.$ It might very well be possible that $\tilde{g} \neq g.$ But from a solution $\tilde{g}$, how do we retrieve a factor? \\ Look at the two equations $f = g_kh_k\bmod{Y^{2^k}}$ and $\tilde{g} = g_k\tilde{l}\bmod{Y^{2^k}}.$ And in essence, both $f$ and $\tilde{g}$ share a common factor modulo $Y^{2^k}.$ Therefore, if one were to consider them as polynomials of $X$ with coefficients coming from $K[Y]$, this means that the $X$-resultant of $f$ and $\tilde{g}$ is zero modulo $Y^{2^k}.$ By the $X$ resultant we mean the resultant, considered as polynomials in $K[Y][X].$ Therefore $$ \text{Res}_X(f,\tilde{g}) = 0\bmod{Y^{2^k}} $$ The resultant would be a polynomial in $Y.$ What is the maximum degree of this polynomial possible? Since we are looking at the determininant, the size of the sylvester matrix is $2m$ where $m$ is the $\deg_X(f).$ And each element of this matrix would be a polynomial in $Y$ of degree at most $n$ where $n = \deg_X(f).$ Therefore, the degree of the resultant polynomial is at most $2mn + 2.$ And if $2^k$ is larger than $2mn+2$, then $$ \text{Res}_X(f,\tilde{g}) = 0\bmod{Y^{2^k}} \implies \text{Res}_X(f,\tilde{g}) = 0 $$ and therefore, $f$ and $\tilde{g}$ must infact share a common factor. Use the euclidian algorithm to extract out this factor. \\ All that is left to do are the corner cases. We shall deal with them in the next class. \end{document}