Mixing
Why doesn't Buchberger's algorithm solve Hilbert's tenth problem?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I've been reading a bit about Buchberger's algorithm and Groebner bases. I'm not really trying to understand the math behind it at this point, just trying to get an idea of how the method could be used to solve systems of polynomial equations. From what I've seen on the Web, it looks to me like the method could be used to find all integer solutions of a system of Diophantine equations. There's clearly something I don't understand, since I know Hilbert's tenth problem is unsolvable.
Here's what I'm thinking. Given a system of polynomials with integer coefficients, the method produces a "triangular" system of polynomials with integer coefficients with the same zero set, and in which each polynomial has one fewer unknown than the preceding one, as in Gaussian elimination.
Say the last polynomial is $p(z) =a_nz^n+a_n-1z^n-1+dots+a_0$ By comparing $|a_nz^n|$ to $sum_k=0^n-1|a_kz^k|$ we can find $N$ such that $p(z)=0implies |z|<N.$ Then we can can systematically test every integer in the range $[-N, N]$ and substitute each $0$ of $p$ into the next equation, arriving at a univariate polynomial, and percolate up until we have found all solutions.
The only way out that I can think of is that the system has a solution but no Groebner basis exists, but nothing I've read so far indicates that this is a possibility. On the other hand, perhaps there's some part of the description of Groebner bases that I have understood. Or, perhaps I'm just being stupid.
Which is it?
diophantine-equations groebner-basis
asked Jul 29 at 23:03
saulspatz
10.3k21323
add a comment |Â
up vote
1
down vote
favorite
I've been reading a bit about Buchberger's algorithm and Groebner bases. I'm not really trying to understand the math behind it at this point, just trying to get an idea of how the method could be used to solve systems of polynomial equations. From what I've seen on the Web, it looks to me like the method could be used to find all integer solutions of a system of Diophantine equations. There's clearly something I don't understand, since I know Hilbert's tenth problem is unsolvable.
Here's what I'm thinking. Given a system of polynomials with integer coefficients, the method produces a "triangular" system of polynomials with integer coefficients with the same zero set, and in which each polynomial has one fewer unknown than the preceding one, as in Gaussian elimination.
Say the last polynomial is $p(z) =a_nz^n+a_n-1z^n-1+dots+a_0$ By comparing $|a_nz^n|$ to $sum_k=0^n-1|a_kz^k|$ we can find $N$ such that $p(z)=0implies |z|<N.$ Then we can can systematically test every integer in the range $[-N, N]$ and substitute each $0$ of $p$ into the next equation, arriving at a univariate polynomial, and percolate up until we have found all solutions.
The only way out that I can think of is that the system has a solution but no Groebner basis exists, but nothing I've read so far indicates that this is a possibility. On the other hand, perhaps there's some part of the description of Groebner bases that I have understood. Or, perhaps I'm just being stupid.
Which is it?
diophantine-equations groebner-basis
asked Jul 29 at 23:03
saulspatz
10.3k21323
4
I don't know much about Buchberger's algorithm but I don't think it actually produces a "triangular" system as you describe. For instance, if you started with just a single polynomial, wouldn't the algorithm do nothing?
– Eric Wofsey
Jul 29 at 23:24
1
@EricWofsey I guess that's the part of the explanation that I didn't understand. I'll have to go over those Web pages again and look for that.
– saulspatz
Jul 30 at 0:21
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I've been reading a bit about Buchberger's algorithm and Groebner bases. I'm not really trying to understand the math behind it at this point, just trying to get an idea of how the method could be used to solve systems of polynomial equations. From what I've seen on the Web, it looks to me like the method could be used to find all integer solutions of a system of Diophantine equations. There's clearly something I don't understand, since I know Hilbert's tenth problem is unsolvable.
Here's what I'm thinking. Given a system of polynomials with integer coefficients, the method produces a "triangular" system of polynomials with integer coefficients with the same zero set, and in which each polynomial has one fewer unknown than the preceding one, as in Gaussian elimination.
Say the last polynomial is $p(z) =a_nz^n+a_n-1z^n-1+dots+a_0$ By comparing $|a_nz^n|$ to $sum_k=0^n-1|a_kz^k|$ we can find $N$ such that $p(z)=0implies |z|<N.$ Then we can can systematically test every integer in the range $[-N, N]$ and substitute each $0$ of $p$ into the next equation, arriving at a univariate polynomial, and percolate up until we have found all solutions.
The only way out that I can think of is that the system has a solution but no Groebner basis exists, but nothing I've read so far indicates that this is a possibility. On the other hand, perhaps there's some part of the description of Groebner bases that I have understood. Or, perhaps I'm just being stupid.
Which is it?
diophantine-equations groebner-basis
asked Jul 29 at 23:03
saulspatz
10.3k21323
I've been reading a bit about Buchberger's algorithm and Groebner bases. I'm not really trying to understand the math behind it at this point, just trying to get an idea of how the method could be used to solve systems of polynomial equations. From what I've seen on the Web, it looks to me like the method could be used to find all integer solutions of a system of Diophantine equations. There's clearly something I don't understand, since I know Hilbert's tenth problem is unsolvable.
Here's what I'm thinking. Given a system of polynomials with integer coefficients, the method produces a "triangular" system of polynomials with integer coefficients with the same zero set, and in which each polynomial has one fewer unknown than the preceding one, as in Gaussian elimination.
Say the last polynomial is $p(z) =a_nz^n+a_n-1z^n-1+dots+a_0$ By comparing $|a_nz^n|$ to $sum_k=0^n-1|a_kz^k|$ we can find $N$ such that $p(z)=0implies |z|<N.$ Then we can can systematically test every integer in the range $[-N, N]$ and substitute each $0$ of $p$ into the next equation, arriving at a univariate polynomial, and percolate up until we have found all solutions.
The only way out that I can think of is that the system has a solution but no Groebner basis exists, but nothing I've read so far indicates that this is a possibility. On the other hand, perhaps there's some part of the description of Groebner bases that I have understood. Or, perhaps I'm just being stupid.
Which is it?
diophantine-equations groebner-basis
asked Jul 29 at 23:03
saulspatz
10.3k21323
asked Jul 29 at 23:03
saulspatz
10.3k21323
asked Jul 29 at 23:03
saulspatz
10.3k21323
asked Jul 29 at 23:03
saulspatz
10.3k21323
10.3k21323
4
I don't know much about Buchberger's algorithm but I don't think it actually produces a "triangular" system as you describe. For instance, if you started with just a single polynomial, wouldn't the algorithm do nothing?
– Eric Wofsey
Jul 29 at 23:24
1
@EricWofsey I guess that's the part of the explanation that I didn't understand. I'll have to go over those Web pages again and look for that.
– saulspatz
Jul 30 at 0:21
add a comment |Â
4
I don't know much about Buchberger's algorithm but I don't think it actually produces a "triangular" system as you describe. For instance, if you started with just a single polynomial, wouldn't the algorithm do nothing?
– Eric Wofsey
Jul 29 at 23:24
1
@EricWofsey I guess that's the part of the explanation that I didn't understand. I'll have to go over those Web pages again and look for that.
– saulspatz
Jul 30 at 0:21
4
4
I don't know much about Buchberger's algorithm but I don't think it actually produces a "triangular" system as you describe. For instance, if you started with just a single polynomial, wouldn't the algorithm do nothing?
– Eric Wofsey
Jul 29 at 23:24
I don't know much about Buchberger's algorithm but I don't think it actually produces a "triangular" system as you describe. For instance, if you started with just a single polynomial, wouldn't the algorithm do nothing?
– Eric Wofsey
Jul 29 at 23:24
1
1
@EricWofsey I guess that's the part of the explanation that I didn't understand. I'll have to go over those Web pages again and look for that.
– saulspatz
Jul 30 at 0:21
@EricWofsey I guess that's the part of the explanation that I didn't understand. I'll have to go over those Web pages again and look for that.
– saulspatz
Jul 30 at 0:21
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
accepted
The impossibility of deciding the solvability of Diophantine equations can be proven by exhibiting a single equation.
The Groebner basis of a principal ideal is any one of its generators.
The analysis you did to decide a polynomial of a single variable, wouldn't apply to one in several variables. For example, $y-x=0$ has arbitrarily large integer solutions.
That makes sense, but why do all those example show triangular systems, then? It that just something that happens sometimes? Also, is it true than that there are systems with solutions that Groebner bases won't help solve? Thanks for your help.
– saulspatz
Jul 30 at 0:29
@saulspatz Gauss elimination is Buchberger's for linear equations. Do you always get triangular systems by doing Gauss? A trapezoid is the most that you can hope for, for linear systems.
– user580373
Jul 30 at 0:31
Okay, I understand. Thanks, again.
– saulspatz
Jul 30 at 0:36
@saulspatz See how confusing something, that although absolutely trivial, and even containing ideas that you are supposed to know, but that is slightly out of your horizon of understanding can be? Take that into account, when you see students asking trivial questions that they don't have any idea of how to even start.
– user580373
Jul 30 at 0:42
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
The impossibility of deciding the solvability of Diophantine equations can be proven by exhibiting a single equation.
The Groebner basis of a principal ideal is any one of its generators.
The analysis you did to decide a polynomial of a single variable, wouldn't apply to one in several variables. For example, $y-x=0$ has arbitrarily large integer solutions.
That makes sense, but why do all those example show triangular systems, then? It that just something that happens sometimes? Also, is it true than that there are systems with solutions that Groebner bases won't help solve? Thanks for your help.
– saulspatz
Jul 30 at 0:29
@saulspatz Gauss elimination is Buchberger's for linear equations. Do you always get triangular systems by doing Gauss? A trapezoid is the most that you can hope for, for linear systems.
– user580373
Jul 30 at 0:31
Okay, I understand. Thanks, again.
– saulspatz
Jul 30 at 0:36
@saulspatz See how confusing something, that although absolutely trivial, and even containing ideas that you are supposed to know, but that is slightly out of your horizon of understanding can be? Take that into account, when you see students asking trivial questions that they don't have any idea of how to even start.
– user580373
Jul 30 at 0:42
add a comment |Â
up vote
3
down vote
accepted
The impossibility of deciding the solvability of Diophantine equations can be proven by exhibiting a single equation.
The Groebner basis of a principal ideal is any one of its generators.
The analysis you did to decide a polynomial of a single variable, wouldn't apply to one in several variables. For example, $y-x=0$ has arbitrarily large integer solutions.
That makes sense, but why do all those example show triangular systems, then? It that just something that happens sometimes? Also, is it true than that there are systems with solutions that Groebner bases won't help solve? Thanks for your help.
– saulspatz
Jul 30 at 0:29
@saulspatz Gauss elimination is Buchberger's for linear equations. Do you always get triangular systems by doing Gauss? A trapezoid is the most that you can hope for, for linear systems.
– user580373
Jul 30 at 0:31
Okay, I understand. Thanks, again.
– saulspatz
Jul 30 at 0:36
@saulspatz See how confusing something, that although absolutely trivial, and even containing ideas that you are supposed to know, but that is slightly out of your horizon of understanding can be? Take that into account, when you see students asking trivial questions that they don't have any idea of how to even start.
– user580373
Jul 30 at 0:42
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
The impossibility of deciding the solvability of Diophantine equations can be proven by exhibiting a single equation.
The Groebner basis of a principal ideal is any one of its generators.
The analysis you did to decide a polynomial of a single variable, wouldn't apply to one in several variables. For example, $y-x=0$ has arbitrarily large integer solutions.
The impossibility of deciding the solvability of Diophantine equations can be proven by exhibiting a single equation.
The Groebner basis of a principal ideal is any one of its generators.
The analysis you did to decide a polynomial of a single variable, wouldn't apply to one in several variables. For example, $y-x=0$ has arbitrarily large integer solutions.
answered Jul 29 at 23:49
user580373
That makes sense, but why do all those example show triangular systems, then? It that just something that happens sometimes? Also, is it true than that there are systems with solutions that Groebner bases won't help solve? Thanks for your help.
– saulspatz
Jul 30 at 0:29
@saulspatz Gauss elimination is Buchberger's for linear equations. Do you always get triangular systems by doing Gauss? A trapezoid is the most that you can hope for, for linear systems.
– user580373
Jul 30 at 0:31
Okay, I understand. Thanks, again.
– saulspatz
Jul 30 at 0:36
@saulspatz See how confusing something, that although absolutely trivial, and even containing ideas that you are supposed to know, but that is slightly out of your horizon of understanding can be? Take that into account, when you see students asking trivial questions that they don't have any idea of how to even start.
– user580373
Jul 30 at 0:42
add a comment |Â
That makes sense, but why do all those example show triangular systems, then? It that just something that happens sometimes? Also, is it true than that there are systems with solutions that Groebner bases won't help solve? Thanks for your help.
– saulspatz
Jul 30 at 0:29
@saulspatz Gauss elimination is Buchberger's for linear equations. Do you always get triangular systems by doing Gauss? A trapezoid is the most that you can hope for, for linear systems.
– user580373
Jul 30 at 0:31
Okay, I understand. Thanks, again.
– saulspatz
Jul 30 at 0:36
@saulspatz See how confusing something, that although absolutely trivial, and even containing ideas that you are supposed to know, but that is slightly out of your horizon of understanding can be? Take that into account, when you see students asking trivial questions that they don't have any idea of how to even start.
– user580373
Jul 30 at 0:42
That makes sense, but why do all those example show triangular systems, then? It that just something that happens sometimes? Also, is it true than that there are systems with solutions that Groebner bases won't help solve? Thanks for your help.
– saulspatz
Jul 30 at 0:29
That makes sense, but why do all those example show triangular systems, then? It that just something that happens sometimes? Also, is it true than that there are systems with solutions that Groebner bases won't help solve? Thanks for your help.
– saulspatz
Jul 30 at 0:29
@saulspatz Gauss elimination is Buchberger's for linear equations. Do you always get triangular systems by doing Gauss? A trapezoid is the most that you can hope for, for linear systems.
– user580373
Jul 30 at 0:31
@saulspatz Gauss elimination is Buchberger's for linear equations. Do you always get triangular systems by doing Gauss? A trapezoid is the most that you can hope for, for linear systems.
– user580373
Jul 30 at 0:31
Okay, I understand. Thanks, again.
– saulspatz
Jul 30 at 0:36
Okay, I understand. Thanks, again.
– saulspatz
Jul 30 at 0:36
@saulspatz See how confusing something, that although absolutely trivial, and even containing ideas that you are supposed to know, but that is slightly out of your horizon of understanding can be? Take that into account, when you see students asking trivial questions that they don't have any idea of how to even start.
– user580373
Jul 30 at 0:42
@saulspatz See how confusing something, that although absolutely trivial, and even containing ideas that you are supposed to know, but that is slightly out of your horizon of understanding can be? Take that into account, when you see students asking trivial questions that they don't have any idea of how to even start.
– user580373
Jul 30 at 0:42
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2866513%2fwhy-doesnt-buchbergers-algorithm-solve-hilberts-tenth-problem%23new-answer', 'question_page');
);
Post as a guest
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
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
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
4
I don't know much about Buchberger's algorithm but I don't think it actually produces a "triangular" system as you describe. For instance, if you started with just a single polynomial, wouldn't the algorithm do nothing?
– Eric Wofsey
Jul 29 at 23:24
1
@EricWofsey I guess that's the part of the explanation that I didn't understand. I'll have to go over those Web pages again and look for that.
– saulspatz
Jul 30 at 0:21