Hacker News new | ask | show | jobs
by abdullahkhalids 1151 days ago
Can the method of Grobner bases also be used to solve systems of polynomial inequalities?
3 comments

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).