Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $\mathbb{F}$ be a field and $A(x,y)$ and $B(x,y)$ be polynomials in $\mathbb{F}[x,y]$. We would like to prove that $A(x,y)$ divides $B(x,y)$.

Will the following approach work? We can interpret $A(x,y)$ and $B(x,y)$ as univariate polynomials in $y$ over the field of rational functions in $x$ over $\mathbb{F}$, that is $\mathbb{F}(x)$. We then show that $A(x,y)$ divides $B(x,y)$ as univariate polynomials in $y$ over $\mathbb{F}(x)$ (that is, as polynomials in $\mathbb{F}(x)[y]$), and then use Gauss's lemma to imply that therefore $A(x,y)$ divides $B(x,y)$ as polynomials in $\mathbb{F}[x][y]$.

I noticed this in a paper, and am unable to see how Gauss's lemma trivially establishes this implication (Assume the other step can be done and is irrelevant, namely the univariate divisibility proof. I am only interested in the implication part where it goes from univariate over the rational function field to univariate over $\mathbb{F}[x][y]$ using Gauss lemma). Any clarification would be appreciated.

For instance, suppose $A(x,y)=yx^2$ and $B(x,y)=y^2x$. Then $A$ does divide $B$ as polynomials in $y$ over $\mathbb{F}(x)$, but clearly not as bivariate polynomials in $\mathbb{F}[x,y]$.

  1. Gauss's lemma states that if a univariate polynomial in $\mathbb{D}[x]$ (where $\mathbb{D}$ is a UFD) is reducible as a polynomial in $\mathbb{K}[x]$ (where $\mathbb{K}$ is the field of fractions of $\mathbb{D}$), then it is reducible in in $\mathbb{D}[x]$ itself.
  2. The paper can be looked at here. Check out the first couple of paragraphs in Section 5 "Piecing it together". (The paper as such is an important work in the field of probabilistically checkable proofs in complexity theory, and the constructions use algebraic tools).
share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

Sometimes (I learned this the hard way), you just have to keep reading. In the text, it is stated that one first divides by the $\gcd(A,B)$ to make sure that $A$ and $B$ share no factor. We now want to show that $A$ is constant.

Now what you are saying is correct, of course. If $A$ divides $B$ in $\mathbb F(x)[y]$, then all you get is $A\cdot C=B$ with $C\in\mathbb F(x)[y]$. You can multiply by some $D\in \mathbb F[x]$ of minimal degree to have $\tilde C := CD\in \mathbb F[x,y]$, though. This yields $A\cdot \tilde C=B\cdot D$. Now if $A$ and $B$ share no common factor, this means $A\mid D$. Since we chose $D$ to be of minimal degree, it shares no factor with $\tilde C$, so actually $A=D\in \mathbb F[x]$. However, this did not depend on our choice of $x$ or $y$, so we can just as well prove $A\in\mathbb F[y]$. Hence, $A\in \mathbb F[x]\cap \mathbb F[y]=\mathbb F$, so $A$ is a constant.

Regarding your example: It is important to have the statement not just for one of the variables, but for both. Otherwise, it's false as your example shows.

share|improve this answer
    
Thanks! I got caught up at that point since the paper made it sound like it was an immediate consequence of Gauss Lemma (though I do not see the need for the lemma at all). While your entire answer was helpful, I think the key point is the last line, that we need the univariate divisibility for both variables and not just one. Also, "Now if $A$ and $B$ share no common factor, this means $A\mid D$." Doesn't this itself imply that $A \in \mathbb F[x]$?. Do we really need "Since we chose $D$ to be of minimal degree, it shares no factor with $\tilde C$, so actually $A=D\in \mathbb F[x]$."? –  BharatRam Aug 26 '13 at 12:18
    
You're right about the last part. In a first version of the answer, I had prematurely concluded $A=D$ right away and then noticed that one can only get $A\mid D$. I fixed that instead of realizing that $A\mid D$ is actually enough. –  Jesko Hüttenhain Aug 26 '13 at 12:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.