# Automating the solution of pairs of polynomial inequalities as a bound

Let's consider the following pair of quadratic inequalities:

\begin{aligned} x^2+x &\geq a\\ x^2-x &< a\end{aligned}

The solution of the first inequality is

$$\left( x \geq \frac{-1+ \sqrt{1+4a}}{2} \right) \lor \left( x \geq \frac{-1- \sqrt{1+4a}}{2} \right)$$

Now, the first one is always going to be larger than the second one, as $$\sqrt{1+4a}>0$$. So, $$x \geq \frac{-1+ \sqrt{1+4a}}{2}$$ is the "true" lower bound. Therefore, we will consider the solution as:

$$x \geq \frac{-1+ \sqrt{1+4a}}{2}$$ ------> (1)

For the second inequality, the solution is $$x < \frac{1+ \sqrt{1+4a}}{2}$$ or $$x < \frac{1- \sqrt{1+4a}}{2}$$.

Again, since $$\sqrt{1+4a}>0$$, the second solution is always going to be smaller than the first solution. So, $$x < \frac{1- \sqrt{1+4a}}{2}$$ is the "true" upper bound.

However, because $$\frac{1- \sqrt{1+4a}}{2}$$ is negative of the solution of the first inequality from (1), we encounter some issues. For example, if the solution in (1) is negative (<0), then its fine. For example, if, say, (1) evaluates to $$x \geq -5$$, then our solution to the second inequality implies $$x<5$$, which is fine. But, if the solution in (1) is positive (>0), then the pair of solutions taken together doesn't make sense. For example, if (1) evaluates to $$x \geq 5$$, then our solution to the second inequality implies $$x<-5$$, which is nonsensical.

Therefore, we need to reject this solution for the second inequality and accept the other solution as the true solution:

$$x < \frac{1+ \sqrt{1+4a}}{2}$$ ------> (2)

Thus, from (1) and (2), we can say that the solution of these 2 inequalities given as a bound is:

$$x \in [\frac{-1+ \sqrt{1+4a}}{2}, \frac{1+ \sqrt{1+4a}}{2})$$

As demonstrated, the process of rejecting 2 of the possible solutions can be a bit involved. Also, the process can be different for other sets of inequalities, where the same lines of thinking might not disqualify 2 of the candidate solutions.

I want to be able to automate this process for any pair of inequalities. I have written the following code to solve a set of quadratic polynomial inequalities and return the solution as a bounded set:

from sympy import simplify, degree
import math

def extract_terms(LHS, operator, var):
expression = simplify(LHS)
variable  = simplify(var)
poly_degree  = degree(expression, gen=variable)

term_coeffs = []
for x in range(poly_degree,-1,-1):
if x>0:
term = simplify(str(variable)+"**"+str(x))
term_coeffs.append(expression.coeff(term))
expression = simplify(str(expression)+"-"+str(simplify("("+str(term)+")*("+str(expression.coeff(term))+")")))
else:
const_value =  expression
term_coeffs.append(const_value)
return term_coeffs

c, d, e = extract_terms(LHS, operator, var)
try:
s1 = -(d/(2.0*c))+math.sqrt(-(e/c)+(d/(2.0*c))**2)
s2 = -(d/(2.0*c))-math.sqrt(-(e/c)+(d/(2.0*c))**2)
return s1, s2
except:
print('The given inequality does not have a real solution.')
return 0

def give_soln_bounds(LHS_1, operator_1, var, LHS_2, operator_2):
s1a, s2a = solve_quad_inequality(LHS_1, operator_1, var)
print("The candidate solutions for {}{}0 are: {}{}{} or {}{}{}".format(LHS_1, operator_1, var, operator_1, s1a, var, operator_1, s2a))

s1b, s2b = solve_quad_inequality(LHS_2, operator_2, var)
print("The candidate solutions for {}{}0 are: {}{}{} or {}{}{}".format(LHS_2, operator_2, var, operator_2, s1b, var, operator_2, s2b))

a = s1a if s1a>=s2a else s2a
if s1b<s2b:
if s1b>a:
b = s1b
else:
b = s2b
else:
if s2b>a:
b=s2b
else:
b=s1b

print('The bounded solution for the given pair of inequalities is: x ∈ ['+str(a)+', '+str(b)+')')

give_soln_bounds("x**2-5*x+6", ">=", "x", "x**2-5*x+4", "<")


This gives the following output:

The candidate solutions for x**2-5*x+6>=0 are: x>=3.00000000000000 or x>=2.00000000000000
The candidate solutions for x**2-5*x+4<0 are: x<4.00000000000000 or x<1.00000000000000
The bounded solution for the given pair of inequalities is: x ∈ [3.00000000000000, 4.00000000000000)


Another example test:

give_soln_bounds("x**2+x-1", ">=", "x", "x**2-x-1", "<")
>>>
The candidate solutions for x**2+x-1>=0 are: x>=0.618033988749895 or x>=-1.61803398874989
The candidate solutions for x**2-x-1<0 are: x<1.61803398874989 or x<-0.618033988749895
The bounded solution for the given pair of inequalities is: x ∈ [0.618033988749895, 1.61803398874989)


It seems to work fine for the examples I have thrown at it so far, but is there any way to know if its truly correct? Any counterexample would be great too!

Also, it can't handle equations where I give symbolic inputs. For example, $$x^2-x-k<0$$, where the solution is expected in terms of k. Is there any way to do that?

Another issue is, if I want to this for cubic inequalities, I can foresee a problem with comparing all the 9 possibilities arising from the 3 candidate solutions for each inequality. Is there any way to cut down on the number of comparisons to be made to search for the valid solutions?

And finally, if you see any possible improvement in the code (be it style-wise or performance-wise), please do let me know.

The solution for the first inequality is actually $$x \geq \frac{-1+ \sqrt{1+4a}}{2}$$ or $$x \leq \frac{-1- \sqrt{1+4a}}{2}$$ i.e. $$x\in (-\infty, \frac{-1- \sqrt{1+4a}}{2}) \cup (\frac{-1+ \sqrt{1+4a}}{2}, \infty)$$