Is there a “symmetric” way to use the Euclidean algorthm on $R[x,y]$ for a domain $R$?
up vote
1
down vote
favorite
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.
abstract-algebra polynomials euclidean-algorithm euclidean-domain
asked Nov 21 at 17:40
mweiss
17.5k23270
add a comment |
up vote
1
down vote
favorite
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.
abstract-algebra polynomials euclidean-algorithm euclidean-domain
asked Nov 21 at 17:40
mweiss
17.5k23270
2
Have you ever heard of Gröbner bases? It seems like being "even-handed" is just something about your choice of monomial ordering.
– rschwieb
Nov 21 at 17:49
@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.
– mweiss
Nov 21 at 18:21
good luck: I think it is what you want
– rschwieb
Nov 21 at 18:59
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.
– mweiss
Nov 21 at 19:04
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.
– Bill Dubuque
Nov 22 at 19:34
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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.
abstract-algebra polynomials euclidean-algorithm euclidean-domain
asked Nov 21 at 17:40
mweiss
17.5k23270
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.
abstract-algebra polynomials euclidean-algorithm euclidean-domain
abstract-algebra polynomials euclidean-algorithm euclidean-domain
asked Nov 21 at 17:40
mweiss
17.5k23270
asked Nov 21 at 17:40
mweiss
17.5k23270
asked Nov 21 at 17:40
mweiss
17.5k23270
asked Nov 21 at 17:40
mweiss
17.5k23270
asked Nov 21 at 17:40
mweiss
17.5k23270
17.5k23270
2
Have you ever heard of Gröbner bases? It seems like being "even-handed" is just something about your choice of monomial ordering.
– rschwieb
Nov 21 at 17:49
@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.
– mweiss
Nov 21 at 18:21
good luck: I think it is what you want
– rschwieb
Nov 21 at 18:59
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.
– mweiss
Nov 21 at 19:04
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.
– Bill Dubuque
Nov 22 at 19:34
add a comment |
2
Have you ever heard of Gröbner bases? It seems like being "even-handed" is just something about your choice of monomial ordering.
– rschwieb
Nov 21 at 17:49
@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.
– mweiss
Nov 21 at 18:21
good luck: I think it is what you want
– rschwieb
Nov 21 at 18:59
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.
– mweiss
Nov 21 at 19:04
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.
– Bill Dubuque
Nov 22 at 19:34
2
2
Have you ever heard of Gröbner bases? It seems like being "even-handed" is just something about your choice of monomial ordering.
– rschwieb
Nov 21 at 17:49
Have you ever heard of Gröbner bases? It seems like being "even-handed" is just something about your choice of monomial ordering.
– rschwieb
Nov 21 at 17:49
@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.
– mweiss
Nov 21 at 18:21
@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.
– mweiss
Nov 21 at 18:21
good luck: I think it is what you want
– rschwieb
Nov 21 at 18:59
good luck: I think it is what you want
– rschwieb
Nov 21 at 18:59
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.
– mweiss
Nov 21 at 19:04
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.
– mweiss
Nov 21 at 19:04
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.
– Bill Dubuque
Nov 22 at 19:34
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.
– Bill Dubuque
Nov 22 at 19:34
add a comment |
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3008081%2fis-there-a-symmetric-way-to-use-the-euclidean-algorthm-on-rx-y-for-a-domai%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3008081%2fis-there-a-symmetric-way-to-use-the-euclidean-algorthm-on-rx-y-for-a-domai%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
Have you ever heard of Gröbner bases? It seems like being "even-handed" is just something about your choice of monomial ordering.
– rschwieb
Nov 21 at 17:49
@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.
– mweiss
Nov 21 at 18:21
good luck: I think it is what you want
– rschwieb
Nov 21 at 18:59
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.
– mweiss
Nov 21 at 19:04
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.
– Bill Dubuque
Nov 22 at 19:34