Hacker News new | past | comments | ask | show | jobs | submit | ransac9000's comments login

This is a good point. I think it's just due to convention --- people tend to put terms involving x only at the front, and in the textbook by Cox et. al. that I referenced they use this convention as well.


If you can't algebraically solve the univariate polynomial, you can still get some solutions to the system as long as you can obtain some solutions to the univariate polynomial numerically.


Author here. Gröbner bases are powerful tools for us to understand polynomials. I started on this article when I encountered them during research, and decided to write down some notes. After a few months, these notes turned into this blog post. It's quite a long read, and let me know if you have any questions.


Looks nice!

A tip for your latex: I would use \langle and \rangle to surround the generators of an ideal, which looks better than using < and >. And I think they are called angle brackets, not square brackets (which would be [,]).


Good catch! I thought I changed all < and > into \langle and \rangle.


A bit after halfway, following: "In this case, .. , and we have", I think you need a "-" sign rather than a "+" in your equation?


Good catch! Thanks for the feedback.


Can the method of Grobner bases also be used to solve systems of polynomial inequalities?


Inequalities can be transformed into equations quite easily, by adding variables:

Consider a strict inequality with real variables x_i:

    f(x_1,...,x_n) > 0
By adding the variable y we obtain an equivalent equation:

    f(x_1,...,x_n) = y^-2
This is correct because y^-2 is always strictly positive.

If f is a polynomial, the above can be written as a polynomial equation like so:

    f(x_1,...,x_n) * y^2 = 1
To transform a non-strict inequality into an equation, on the other hand, the procedure is the same, just use 2 instead of -2 as the exponent. That is, this inequality:

    f(x_1,...,x_n) ≥ 0
... is equivalent to this equation:

    f(x_1,...,x_n) = y^2


Trouble starts when your field doesn't always have a solution for f(x_1,...,x_n) = y^2, like rational numbers (but I'm sure you can find more examples). But maybe that can be mitigated as well?


I'm not an expert in this area, but, precisely for the reason you mention, I'd expect it's easier to solve a polynomial inequality over ℚ by solving it over ℝ and intersecting down to ℚ, rather than by working directly over ℚ.


As long as you don’t bump into Gal(ℝ/ℚ) somewhere along the way.


It seems that you can reformulate inequalities into equalities and solve the system: https://arxiv.org/pdf/1603.01183.pdf


For systems of polynomial inequalities, the appropriate tool is Cylindrical Algebraic Decomposition (this tool generalizes to systems of exponential inequalities as well).


thanks for writing this. I have read about 1/3 to 1/2 so far and it is very nicely written and easy to follow.


No problem, and thank you for the kind words!


nicely done


thanks!


Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: