Existence of Solutions to Systems of Polynomial Inequalities

Existence of Solutions to Systems of Polynomial Inequalities

I was wondering whether there is a general method to deciding if a system of polynomial inequalities has a solution. If there was such an algorithm this could be used to solve questions such as the sphere packing question. (The kissing number). Simply find all the inequalities for each sphere and determine if a solution can be found. To skip to the end it turns out that all systems of polynomial inequalities can be put in the following form:

{A_nmx_nx_m+B_nx_n+C ≥ 0}

or using the notation X={x1,x2,x3,...,1}

{Q_nmX_nX_m ≥ 0}

Thus all conditions are built up from matrices, A, vectors B and constants C. We must deal with all the special cases where various components are zero. For the sphere packing problem we can set all the {B=0} which makes it much simpler.

Simplest Case
The simplest case is a single linear equation
Ax+B ≥ 0
This has no solution when A=0 & B<0

Starting in One Dimension
The next simplest case is two linear inequalities:

Ax+B ≥ 0

Cx+D ≥ 0

This can be solved if one of the these conditions is met:
1) AC>0  
2) AC<0  &  A(AD-BC)≥0

Or, to put it another way, there is NO solution if  AC<0 and A(AD-BC)<0  )

(Or:  B₁(c₁B₂-B₁c₂)< 0  & B₁B₂< 0 )

Next add a third linear inequality

Ex+F ≥ 0

There exists a solution if
1) AC>0  and AE>0
2) ....

Quadratic
(1) Ax²+Bx+C ≥ 0

has  a solution if

A>0 or C>0 or det(Q)=B²-4AC>0

  [Q²]-[Q]² > 0
(1) Ax²+C ≥ 0
has no solution if:

C < 0 & A <= 0

Two Quadratics
This is important to get right as we can replace the coefficients with functions of y to build up more equations!
(1) Ax²+Bx+C ≥ 0    XQX >0.... X=(x,1)     [Q²]-[Q]² > 0
(2) Dx²+Ex+F ≥ 0     XRX>0                [R²]-[R]² > 0

has NO solution if....????? (Boundary when they share a common root... the resultant... not enough)
??? (AE-BD)(BF-CE) - (AF-CD)² < 0 ??
Let [M]=Tr(M)

They share a common root when:

([Q]²-[Q²])([R]²-[R²]) - ([Q][R]- [QR])²  = 0

When B=E=0
(1) Ax²+C ≥ 0

(2) Dx²+F ≥ 0

has no solution if: A<0 & C>0 & D>0 & F<0 &  (DC-AF)>0 or vice versa

For multi-variable this becomes???? (just guessing)

(B^T₂.A₁-B^T₁.A₂)(B₁.C₂-B₂C₁) - det(A₁.C₂-A₂C₁)²  <  0

it could also be just as well...(dividing by A₁.A₂)

(B^T₂.A*₂-B^T₁.A*₁)(B₁.C₂-B₂C₁) - (A₁.C₂-A₂C₁)(A*2.C₂-A*1C₁)   <  0

B2=A2=0

Two variables gives:

(A(Ey+H)-(By+G)D)((By+G)(Fy²+Ky+L)-(Cy²+Iy+J)(Ey+H)) - (A(Fy²+Ky+L)-(Cy²+Iy+J)D)² 

a quartic.

Two dimensions
The simplest case is two lines:

Ax+By+C ≥ 0

Dx+Ey+F ≥ 0

There are 2 cases. If they are not parallel there will be a solution otherwise... There is NO solution if
1) AE-BD = 0
2) AD<0
3)


With three lines

Ax+By+C ≥ 0

Dx+Ey+F ≥ 0
Gx+Hy+I ≥ 0

We have the first example where each pair of equations may have a solution (unless they are parallel) but the three together may not have a solution. Need the determinant of the matrix ((A,B,C),(D,E,F),..


Two planes

Ax+By+Cz+D ≥ 0

Ex+Fy+Gz+H ≥ 0

General Linear Case
B_ix+C_i ≥ 0

Quadratic
The simplest is just a single quadratic

(1) Ax²+Bxy+Cy²+Dx+Ey+F ≥ 0
or equivalently
(1) x^TAx+Bx+c ≥ 0
or
(1) X^TQX ≥ 0

When does this have a solution? When it does not represent a 2 dimension curve.
??? 4c - B^TA^-1B < 0 & det(A) > 0  & A₁₁ < 0 (should be invariant under rotations of (x, y) )
This can be written: Ax²+x(By+D)+(Cy²+Ey+F) ≥ 0
Then (from before) it has solutions when:

(3) (By+D)²-4A(Cy²+Ey+F) > 0 or A > 0

and

(4) A!=0 or B!=0 or D!=0 or (Cy²+Ey+F)>0

which is up to TWO simultaneous polynomials in y. (Or we can assume A!=0)

(3) can be written as:
-y²(B²-4AC)-y(2BD-4AE)-(D²-4AF) >0
which has solutions when:

(BD-2AE)²-(B²-4AC)(D²-4AF) > 0 or (B²-4AC) < 0

and

(B²-4AC)!=0 or (BD-2AE)!=0 or (D²-4AF)>0

Solution

(If A₁₁!=0 and A₂₂!=0 and A₃₃!=0)

A₁₁<=0 & A₂₂<=0 & A₃₃<=0 & det(A)(-1)^3>=0  & det(Q)=(4c.det(A)  - B^TA^*B) >= 0

or  A₁₁>0

or  A₂₂>0

or  A₃₃>0

det(A)>0 means the shape has a maximum (at least in 2D) which is given by the longer expression.

6.det(Q)= [Q³]-3[Q][Q²]+2[Q³] > 0

Conic Sections
We want a general method to see if two conic sections:

Ax²+Bxy+Cy²+Dx+Ey+F ≥ 0  or X^TQX ≥ 0

Gx²+Hxy+Iy²+Jx+Ky+L ≥ 0  or X^TRX ≥ 0

have any intersections without having to find those intersections. This case is more interesting because one can easily imagine many 2D closed shapes overlapping. Firstly it has no solutions if either of the equations has no solutions (obviously). If the conic sections intersect there is a solution. If they don't intersect one could still lie "inside" the other depending on our definition of "inside".

For example consider the following:

A²-x²-y² ≥ 0

B²-(x-C)²-(y-D)² ≥ 0

When does this have a solution? This is obviously the equation of two circles and has a solution when the two circles overlap. i.e. when:

(A+B)²-C^2-D² ≥ 0

or to write it in terms of a=A^{2 ,} b=A²

(a+b-C^2-D²)²- 4ab  > 0 & a > 0 & b > 0

Therefor it looks like an algorithm is possible. It would be interesting to find this algorithm an apply it to the sphere packing problem.

Note: The resultant for these two quadratic polynomials would be at least a quartic in y.

Line and Conic section
A slightly simpler problem is to determine if any of a conic section is above or below a given line:

Ax²+Bxy+Cy²+Dx+Ey+F ≥ 0

Gx+Hy+F ≥ 0

General 2D case

A_nmxⁿy^m ≥ 0

B_nmxⁿy^m ≥ 0

All the details are contained in the matrices A and B.

General Problem
The general problem is to decide if given a set of polynomials

P_n(x₁,x₂,x₃,...) > 0

whether there exists a region which satisfies all the conditions.

Perhaps this is implemented in Mathematica's Reduce command? I don't think so as the reduce produces non-polynomial answers.



Algorithm
The algorithm is to try and remove the dependence on the x's. For example in the first case:

(1) Ax+B≥0

(2) Cx+D≥0

Multiply (1) by C but note that the inequality depends on the sign of C

(1) (ACx+BC>0 & C>0) || (ACx+BC<0 & C<0)

(2) (ACx+AD>0 & A>0) || (ACx+AD<0 & A<0)

Subtracting inequalities: A>0 & B<0 => A-B>0

(1) (BC-AD>0 & C>0 & A<0) || (BC-AD)<0 & C<0 & A>0

But there is another solution with (A>0 & C>0) || (A<0 & C<0) how do we get this?



Sphere Packing

The sphere packing equations can be given in one of two forms.
Firstly that the distance of the sphere to the centre is exactly 1 can be given by two inequalities:
x²+y²-1 ≥ 0

1- x²-y² ≥ 0

Secondly that the distance between each sphere is at least 1

1 - (x-X)²-(y-Y)²  ≥ 0

Or the second approach is that the angle between each sphere is greater than π/3. But this uses polynomials up to quartics. For sphere packing the equations are of the form:

A_nmx_nx_m+B_nx_n+C ≥ 0

So an existence theorem for these types of equations could solve the sphere packing problem. Although this would take a lot of equations. For example to prove that in 5 dimensions, 40 spheres are needed would require 850 equations. But if solved by computer that should be very quick.

What are the conditions on A, B and C such that there is a solution?

Symmetries:
Should be invariant under rotations and scales of x. So should be made up of B^TA^-1B, det(A)?, c, 
and translations:

(1) (x^T+d)A(x+d)+B(x+d)+c ≥ 0
(x^T)A(x)+(B+dA+Ad)x+c+Bd ≥ 0
B --> B+2Ad
c --> c+Bd

B^TA^-1B - 4c  --> (B+2dA)A^-1(B+2Ad)-4(c+Bd) --> B^TA^-1B - 4c  + 2(d^TAd)
(B1-B2)^T(B1-B2)
Tr[A1/A2]?

Simplifications??
Let x₀=1 then it is just A^nmx_nx_m ≥ 0


For circles -1xx-1yy+0xy

c - x² - y² + ax+by > 0     with 4c=(4r²-a²-b²)
C - x² - y²+Ax+By > 0  with 4C=(4R²-A²-B²)


condition is distance (a-A)²+(b-B)² < 4(r+R)²

((a-A)²+(b-B)² - 4r²- 4R² )²  - 64r²R² < 0

So we have a quartic condition in the coefficients:

((a-A)²+(b-B)² - 4c-a²-b²- 4C-A²-B² )²  - 4(4c+a²+b²)(4C+A²+B²) < 0


((a-A)²+(b-B)² - 4.C1-|b1|²- 4C2-|B2|² )²  - 4(4.C1 +|B1|²)(4.C2+|B2|²) < 0

???(B2.A2^-1-B1.A1^-1).(B1 C2-B2 C1) - Tr[(C2 A2^-1-C1.A1^-1)(A1 C2 -A2C1.)] ?

???     C2 A2^-1A1 C2 - 2C1.C2

or:
Let A* = det(A)A^-1

J1 = 4.C1 - B1A1^-1B1   or  J1* = 4.det(A1)C1 - B1 A1* B1
J2 = 4.C2 - B2A2^-1B2
J3 = (B1-B2)^T(B1-B2)??

(J3 - J1 - J2)²  - 4(J1)(J2)  <  0  => (J1²+J2²+J3²-2J1.J3-2.J3.J2-2.J1.J2)<0

J1.J2 = 16C1.C2 + C1 (B1A1B1)+C2(B2A2B2) + (B1A..)(B2A..)

Three Circles
With 3 circles with centers X1,X2 X3 and radii r1,r2,r3 the condition that there is a common overlap is:
C(X1,r2), C(X2,r2),C(X3,r3)



General Problem
Need only solve the general problem in 1 variable but for any degree. This can be used to eliminate one variable and so forth.
{A_nxⁿ ≥ 0} and {A_nxⁿ  <0} 


For equalities this is the resultant. Need to find similar thing but for inequalities.