Let $R$ be any integral domain, and $R[x,y]$ the ring of polynomials over $F$ in two variables. If we regard $R[x,y]$ as $\left(R[x]\right)[y]$, i.e. as polynomials in $y$ whose coefficients come from $R[x]$, then given any two polynomials $p(x,y), d(x,y)$, as long as $d$ is monic we can use the Euclidean algorithm to find $q_1(x,y)$ and $r_1(x,y)$ so that $$p(x,y) = d(x,y)q_1(x,y)+r_1(x,y)$$ with $\textrm{ydeg } r_1 < \textrm{ydeg } d$ (where here, $\textrm{ydeg }$ denotes the degree in $y$, e.g. $x^2y^3$ has $\textrm{ydeg } =3$. Likewise if we regard $R[x,y]$ as $\left(R[y]\right)[x]$, i.e. as polynomials in $x$ with coefficients in $R[y]$, then given the same two polynomials $p(x,y), d(x,y)$ we can use the Euclidean algorithm to find $q_2(x,y)$ and $r_2(x,y)$ such that $$p(x,y) = d(x,y)q_2(x,y)+r_2(x,y)$$ with $\textrm{xdeg } r_1 < \textrm{xdeg } d$.

This shows that the Euclidean algorithm can be used on $R[x,y]$ in two distinct ways. In general the two quotients $q_1, q_2$ and remainders $r_1, r_2$ are different depending on which of those two paths we choose. Essentially when we choose to measure the degree of a polynomial by focusing on one variable or the other, we "break" the symmetry between $x$ and $y$.

Is there a way to define a Euclidean degree function and implement the Euclidean algorithm on $F[x,y]$ that is "even-handed", in the sense that it deals with both variables in the same way? The obvious thing to try is to use the total degree, but that doesn't work: with $p(x,y) = x^2y$ and $d(x,y) = xy^2$ there is clearly no $q(x,y), r(x,y)$ such that $x^2y = xy^2q(x,y) + r(x,y)$ and for which $r$ has total degree $< 3$.

My instinct is that it can't be done, but I am wondering if there is a simple way to prove it.

I guess a sub-question here is: Is there a name for a ring (like $R[x]$ and $R[x,y]$ for $R$ a domain) in which you can always divide a given polynomial by an arbitrary monic divisor, but not necessarily by any divisor? It's not quite as strong as being a Euclidean domain, but it's precisely the situation I'm thinking about.

  • 2
    $\begingroup$ Have you ever heard of Gröbner bases? It seems like being "even-handed" is just something about your choice of monomial ordering. $\endgroup$ – rschwieb Nov 21 '18 at 17:49
  • $\begingroup$ @rschweib I have heard of them but don't really know much. I just took a look at the Wikipedia page and it seems that Grobner bases are in a sense of "generalizing" the Euclidean division algorithm, but I can't quite tell if (once one chooses a monomial ordering) there is still an algorithmic way to produce a quotient and remainder. I'll read up on it and see what I can figure it out. $\endgroup$ – mweiss Nov 21 '18 at 18:21
  • $\begingroup$ good luck: I think it is what you want $\endgroup$ – rschwieb Nov 21 '18 at 18:59
  • $\begingroup$ Okay, I see now how division with a monomial ordering works. The thing is, in order to choose a monomial ordering you kind of have to prioritize either $x$ or $y$ -- for example if you use a lexicographic order than the fact that $x$ comes before $y$ determines everything else. So the symmetry is still broken, in that sense. $\endgroup$ – mweiss Nov 21 '18 at 19:04
  • $\begingroup$ You should definitely first read the literature on ideal standard basis agorithms and monomial orderings. These can be viewed as (multivariate) generalizations of the Euclidean algorithm and (nonlinear) generalization of Gaussian elimination. $\endgroup$ – Bill Dubuque Nov 22 '18 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.