Determine if polynomial system has finite number of solutions

In summary, the Wikipedia article on system of polynomial equations states that to determine if a system has an infinite number of solutions, one can compute the Groebner basis of the system and check if there is a leading monomial that is a pure power of each variable. If there is, then the system is zero-dimensional and has a finite number of solutions. If there is no such monomial, then the system is not zero-dimensional and has an infinite number of solutions.
  • #1
aheight
321
109
TL;DR Summary
I don't understand Wikipedia's definition of when a polynomial system has a finite or infinite solution. That is, I don't know what "pure power of a variable in the Grobner basis" means:
Wish to determine when a system of polynomials has an infinite number of solutions, that is, is not zero-dimensional. The Wikipedia article : System of polynomial equations states:

The first thing to do for solving a polynomial system is to decide whether it is inconsistent, zero-dimensional or positive dimensional. This may be done by the computation of a Gröbner basis of the left-hand sides of the equations. The system is inconsistent if this Gröbner basis is reduced to 1. The system is zero-dimensional if, for every variable there is a leading monomial of some element of the Gröbner basis which is a pure power of this variable. For this test, the best monomial order (that is the one which leads generally to the fastest computation) is usually the graded reverse lexicographic one (grevlex).

I interpret the quote to mean the system has an infinite number of solutions if the Grobner basis does not have a leading monomial which is a pure power of the variable.

For example, I have the system:

$$
\begin{aligned}
g(z,w)&=\left(-\frac{976 w^2}{53}+\frac{178 w z}{71}+\frac{27 w}{94}+\frac{323 z^2}{84}+\frac{271 z}{67}+\frac{199}{28}\right) \\
h(z,w)&= \left(\frac{72 w^2}{89}-\frac{502 w z}{97}-\frac{44 w}{57}+\frac{73 z^2}{5}-\frac{369 z}{73}+\frac{483}{95}\right)
\end{aligned}
$$

Which Mathematica's NSolve returns four solutions. And I can compute the Grobner basis with the code below. The Grobner basis is:

$$
\begin{aligned}
&1.15564\times 10^{38} w^4-2.74482\times 10^{37} w^3-8.43405\times 10^{37} w^2+1.37174\times 10^{37} w+1.9389\times 10^{37}\\
&4.72185\times 10^{45} w^3-7.68083\times 10^{45} w^2-1.1989\times 10^{45} w+1.74982\times 10^{45} z+2.44771\times 10^{45}
\end{aligned}
$$

I've not been able to fine a definition of "pure power of a variable of Grobner basis" and was hoping someone could explain this to me. Thanks.

Mathematica:
In[346]:=
g0[{z_, w_}] =
  199/28 + (27 w)/94 - (976 w^2)/53 + (271 z)/67 + (178 w z)/71 + (
   323 z^2)/84;
h0[{z_, w_}] =
  483/95 - (44 w)/57 + (72 w^2)/89 - (369 z)/73 - (502 w z)/97 + (
   73 z^2)/5;
NSolve[{g0[{z, w}] == 0, h0[{z, w}] == 0}, {z, w}]
GroebnerBasis[{g0[{z, w}], h0[{z, w}]}, {z, w}] // N

Out[348]= {{z -> 0.309562 - 0.532126 I,
  w -> 0.688127 - 0.178627 I}, {z -> 0.309562 + 0.532126 I,
  w -> 0.688127 + 0.178627 I}, {z -> 0.0622197 - 0.609678 I,
  w -> -0.56937 + 0.088145 I}, {z -> 0.0622197 + 0.609678 I,
  w -> -0.56937 - 0.088145 I}}

Out[349]= {1.9389*10^37 + 1.37174*10^37 w - 8.43405*10^37 w^2 -
  2.74482*10^37 w^3 + 1.15564*10^38 w^4,
 2.44771*10^45 - 1.1989*10^45 w - 7.68083*10^45 w^2 +
  4.72185*10^45 w^3 + 1.74982*10^45 z}
 
Mathematics news on Phys.org
  • #2
The leading monomials of the two elements are ## 1.15564\times 10^{38} w^4 ## and ## 4.72185\times 10^{45} w^3##. Each of these is a pure power of ## w ## (because they include only ## w ## and not ## v ##) but there is no element for which the leading monomial is a pure power of ## v ##. The system is therefore not zero-dimensional.

I think you're going to need a better source than Wikipedia.
 
  • Like
Likes aheight
  • #3
pbuk said:
The leading monomials of the two elements are 1.15564×1038w4 and 4.72185×1045w3. Each of these is a pure power of w (because they include only w and not v) but there is no element for which the leading monomial is a pure power of v. The system is therefore not zero-dimensional.

Thanks. However after reading a bit on Groebner basis and monomial ordering, perhaps the Wikipedia reference is in regards to lexicographic ordering Monomial ordering which would place a higher priority on z in the Groebner basis:

Lexicographic order
(lex) first compares exponents of x1 in the monomials, and in case of equality compares exponents of x2, and so forth

so that in lexicographic order, the basis would be:

\begin{aligned}

&1.15564\times 10^{38} w^4-2.74482\times 10^{37} w^3-8.43405\times 10^{37} w^2+1.37174\times 10^{37} w+1.9389\times 10^{37}\\

&1.74982\times 10^{45} z+4.72185\times 10^{45} w^3-7.68083\times 10^{45} w^2-1.1989\times 10^{45} w+2.44771\times 10^{45}

\end{aligned}

Not sure though.
 
  • #4
aheight said:
Thanks. However after reading a bit on Groebner basis and monomial ordering,
If you want to understand this stuff you need to do more than 'read a bit', and Wikipedia is not the place to do it. Use one of the references in the Wikipedia article, or better still the MathWorld entry, or search for some course notes like these: http://www.inf.ed.ac.uk/teaching/courses/ca/notes03.pdf.

aheight said:
perhaps the Wikipedia reference is in regards to lexicographic ordering Monomial ordering which would place a higher priority on z in the Groebner basis:
No, the Wikipedia article specifically refers to graded reverse lexicographic ordering (grevlex) in which ## z^1 ## terms do not have precedence over ## w^4 ## terms (that's what graded means here). You will learn about this when you study the subject properly from an authoritative source, it is pointless trying to pick it up by asking random questions on an internet forum.
 
  • #5
aheight said:
Summary:: I don't understand Wikipedia's definition of when a polynomial system has a finite or infinite solution. That is, I don't know what "pure power of a variable in the Grobner basis" means:

Wish to determine when a system of polynomials has an infinite number of solutions, that is, is not zero-dimensional. The Wikipedia article : System of polynomial equations states:
I interpret the quote to mean the system has an infinite number of solutions if the Grobner basis does not have a leading monomial which is a pure power of the variable.

For example, I have the system:

$$
\begin{aligned}
g(z,w)&=\left(-\frac{976 w^2}{53}+\frac{178 w z}{71}+\frac{27 w}{94}+\frac{323 z^2}{84}+\frac{271 z}{67}+\frac{199}{28}\right) \\
h(z,w)&= \left(\frac{72 w^2}{89}-\frac{502 w z}{97}-\frac{44 w}{57}+\frac{73 z^2}{5}-\frac{369 z}{73}+\frac{483}{95}\right)
\end{aligned}
$$

Which Mathematica's NSolve returns four solutions. And I can compute the Grobner basis with the code below. The Grobner basis is:

$$
\begin{aligned}
&1.15564\times 10^{38} w^4-2.74482\times 10^{37} w^3-8.43405\times 10^{37} w^2+1.37174\times 10^{37} w+1.9389\times 10^{37}\\
&4.72185\times 10^{45} w^3-7.68083\times 10^{45} w^2-1.1989\times 10^{45} w+1.74982\times 10^{45} z+2.44771\times 10^{45}
\end{aligned}
$$

I've not been able to fine a definition of "pure power of a variable of Grobner basis" and was hoping someone could explain this to me. Thanks.

Mathematica:
In[346]:=
g0[{z_, w_}] =
  199/28 + (27 w)/94 - (976 w^2)/53 + (271 z)/67 + (178 w z)/71 + (
   323 z^2)/84;
h0[{z_, w_}] =
  483/95 - (44 w)/57 + (72 w^2)/89 - (369 z)/73 - (502 w z)/97 + (
   73 z^2)/5;
NSolve[{g0[{z, w}] == 0, h0[{z, w}] == 0}, {z, w}]
GroebnerBasis[{g0[{z, w}], h0[{z, w}]}, {z, w}] // N

Out[348]= {{z -> 0.309562 - 0.532126 I,
  w -> 0.688127 - 0.178627 I}, {z -> 0.309562 + 0.532126 I,
  w -> 0.688127 + 0.178627 I}, {z -> 0.0622197 - 0.609678 I,
  w -> -0.56937 + 0.088145 I}, {z -> 0.0622197 + 0.609678 I,
  w -> -0.56937 - 0.088145 I}}

Out[349]= {1.9389*10^37 + 1.37174*10^37 w - 8.43405*10^37 w^2 -
  2.74482*10^37 w^3 + 1.15564*10^38 w^4,
2.44771*10^45 - 1.1989*10^45 w - 7.68083*10^45 w^2 +
  4.72185*10^45 w^3 + 1.74982*10^45 z}
Buchberger's algorithm is the solution to the problem. Unfortunately, the English Wikipedia version isn't as good as it should be, so you can either use
https://de.wikipedia.org/wiki/Buchberger-Algorithmus + Google Translate
or search the web for the Buchberger algorithm. The Wikipedia link is similar to your example, see also the discussion in https://www.physicsforums.com/threads/math-challenge-march-2021.1000319/page-2#post-6466108
 
  • Like
Likes aheight
  • #6
fresh_42 said:
Buchberger's algorithm is the solution to the problem. Unfortunately, the English Wikipedia version isn't as good as it should be, so you can either use
https://de.wikipedia.org/wiki/Buchberger-Algorithmus + Google Translate
or search the web for the Buchberger algorithm. The Wikipedia link is similar to your example, see also the discussion in https://www.physicsforums.com/threads/math-challenge-march-2021.1000319/page-2#post-6466108

Thanks for that. It certainly looks like something I can follow. So if I run through the Buchberger iterations with my polynomial system above, would you say I would expect to obtain the same Grobner basis as I obtain with the following Mathematica code:

Mathematica:
polys5={199/28+(27 w)/94-(976 w^2)/53+(271 z)/67+(178 w z)/71+(323 z^2)/84,483/95-(44 w)/57+(72 w^2)/89-(369 z)/73-(502 w z)/97+(73 z^2)/5};
gb2=GroebnerBasis[polys5,{z,w},MonomialOrder->DegreeReverseLexicographic]//N
MonomialList[#,{z,w},DegreeReverseLexicographic]& /@gb2

$$
\begin{align*}
&-2.55909\times 10^{18} w^2+5.31659\times 10^{17} w z+6.73889\times 10^{16} w+7.3855\times 10^{17} z+7.92406\times 10^{17},\\
&-3.12276\times 10^{16} w^2-1.50238\times 10^{14} w+1.89167\times 10^{16} z^2+2.76544\times 10^{15} z+1.65814\times 10^{16},\\
&4.72185\times 10^{45} w^3-7.68083\times 10^{45} w^2-1.1989\times 10^{45} w+1.74982\times 10^{45} z+2.44771\times 10^{45}\\
\end{align*}
$$
which I would suspect the last two representing the reduced form. And note the DegreeReverseLexicographic ordering of the monomials:

$$
\left(
\begin{array}{ccccc}
5.31659\times 10^{17} w z & -2.55909\times 10^{18} w^2 & 7.3855\times 10^{17} z & 6.73889\times 10^{16} w & 7.92406\times 10^{17} \\
1.89167\times 10^{16} z^2 & -3.12276\times 10^{16} w^2 & 2.76544\times 10^{15} z & -1.50238\times 10^{14} w & 1.65814\times 10^{16} \\
4.72185\times 10^{45} w^3 & -7.68083\times 10^{45} w^2 & 1.74982\times 10^{45} z & -1.1989\times 10^{45} w & 2.44771\times 10^{45} \\
\end{array}
\right)
$$
which by inspection, with my limited familiarity of the subject, suggest the ideal is zero-dimensional?
 
  • #7
I expect it, yes, but it may depend on whether you select ##w<z## or ##z<w##. I don't know whether Mathematica goes the full path to a reduced basis. However, it is very likely that they coded Buchberger. Your polynomials are neither many nor complicated, so you can easily work through the algorithm by hand. The math challenge thread contains the algorithm and its explanation in English. If you get the same result, then you can apply the Mathematica code with more confidence next time. Or you crosscheck it with the example given in the other thread.

Edit: I checked the zeros with WolframAlpha. This is no problem with only 2 variables.
 
Last edited:
  • Like
Likes aheight

FAQ: Determine if polynomial system has finite number of solutions

1. How can I determine if a polynomial system has a finite number of solutions?

To determine if a polynomial system has a finite number of solutions, you can use the Fundamental Theorem of Algebra which states that a polynomial of degree n can have at most n distinct complex roots. Therefore, if the polynomial system has a finite number of variables and each variable has a finite degree, then the system will have a finite number of solutions.

2. Can I use the degree of the polynomial to determine if the system has a finite number of solutions?

Yes, the degree of the polynomial can be used to determine if the system has a finite number of solutions. If the degree of the polynomial is finite, then the system will have a finite number of solutions. However, if the degree of the polynomial is infinite, then the system may have an infinite number of solutions.

3. Is there a specific method or algorithm to determine the number of solutions for a polynomial system?

Yes, there are various methods and algorithms that can be used to determine the number of solutions for a polynomial system. Some common methods include substitution, elimination, and graphing. However, the most accurate method is to use the Fundamental Theorem of Algebra as mentioned earlier.

4. Can a polynomial system have both a finite and infinite number of solutions?

No, a polynomial system can only have either a finite or infinite number of solutions. It cannot have both. If the system has a finite number of variables and each variable has a finite degree, then it will have a finite number of solutions. If the system has an infinite number of variables or variables with infinite degrees, then it will have an infinite number of solutions.

5. Are there any special cases where it is difficult to determine the number of solutions for a polynomial system?

Yes, there are some special cases where it can be difficult to determine the number of solutions for a polynomial system. One example is when the system has multiple variables and each variable has a high degree. In these cases, it may require advanced mathematical techniques to accurately determine the number of solutions.

Back
Top