Sphere Packing

  Sphere Packing  

The sphere packing problem or kissing number problem can be stated as a set of quadratic inequalities:

{A_i^nmx_nx_m + C_i ≥ 0}

Can we find a general algorithm to solve these equations? (Don't see why not!) (Actually need for pair of equations in N variables.)

One Equation - One variable ✓
(1) Ax²+C ≥ 0
has no solution if:

C < 0 & A <= 0

Two Equation - One variable ✓

(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 

N Equations - One variable (SOLVED!) ✓

(1) Ax²+C ≥ 0

(2) Dx²+F ≥ 0
(3) Gx²+I ≥ 0

has NO solution if (and only if) one pair does not have a solution or any single equation has no solution. (If all pairs have solution then all MUST have a solution). <-- This only works in one variable! 

One Equation - M variables ✓
(1) x^TAx+c ≥ 0
Solution if:

A₁₁<=0 & A₂₂<=0 & det(A)(-1)^M>=0  & c >= 0

or  A₁₁>0

or  A₂₂>0
or C>0

Two Equations - Two variables  (✓)
(1) x^TAx+c ≥ 0  
(2) x^TDx+f ≥ 0
Solution if:
One condition is (from the resultant):

det(cD-fA) ≥ 0  

Two Equations - Three variables (✓?)
(1) x^TAx+c ≥ 0  
(2) x^TDx+f ≥ 0

  det(cD-fA) > 0 

Two Equations - M variables (✓?)
(1) x^TAx+c ≥ 0
(2) x^TDx+f ≥ 0
Condition for overlapping  det(cD-fA) > 0 
Second equation one inside the other? Use area:
 det(D/f) - det(A/c) > 0 

-----------------------

Three Equations - 2 variables
(1) x^TAx+c ≥ 0  . ....  x^TA'x+1 ≥ 0  ,  A'=A/c
(2) x^TDx+f ≥ 0
(3) x^TGx+i ≥ 0
???(εADG)+...????...

c⁴((εε(DG))(εε(DG))-(εεDD)(εεGG))² + ...
+c²f²(...εε(DG)εε(DA)εε(AG)εε(GG)??...))))
+f⁴((εε(AG))(εε(AG))-(εεAA)(εεGG))² 
+i⁴((εε(AD))(εε(AD))-(εεAA)(εεDD))² > 0

(εεDG) =  (det(D+G)-det(D)-det(G))/2

(εε(DG))(εε(DG))-(εεDD)(εεGG) = (2D+2G-V)(2D+2G-V)-4DG
= (det(D) + det(G) - det(D+G))^2 -4det(D)det(G)
= ((det(D)-det(G))² - 2(det(D)+det(G))det(D+G) + det(D+G)²)² + O(A)
... + det(D+A+G)²??? + ...

1 equation: det(A)    power = 2
2 equations: det(D/f-A/c)    power = 4  and det(D/f) - det(A/c) 
3 equations: ((det(D)-det(G))² - 2(det(D)+det(G))det(D+G) + det(D+G)²)² + O(A)  power = 12
4 equations:  ????
N equations: (only solved for single variable case!).
N equations: V. complicated!!! Three Equations - Three Variables
1) [A]
2) [D-A]
3) (([D]-[G])² - 2([D]+[G])[D-G] + [D-G])² +....O(A)
not unfortunately:?[D+A+G][D+A-G][D-A+G][D+A-G] (area of triangle)
R = matrix (0,[D-G],[D-A]),([D-G],0,[G-A]),(...)

Warning: 
y-(x-3)(x+4)=0  
y-(x+2)(x-3)=0
y-(x+2)(x+4)=0
Resultant is 0 but has no triple root! using eliminate(..,[x,y]) in maxima.

NOTES
-x^2-y^2+xy+5>0,  det(A)=3/4, c=5
-x^2-y^2-xy+5>0,  det(D)=5/4, f=5
x^2+y^2-6>0,       det(G) =1,  i=-6
Each pair has a solution but the triple does NOT have a solution.

N Equations - Two variables
(1) x^TAx+c ≥ 0
(2) x^TDx+f ≥ 0
(3)....
???


N Equation - M variables
(1) x^TAx+c ≥ 0  
(2) x^TDx+f ≥ 0 
(3) x^TGx+i ≥ 0 
Solution iff:
????
det f(A,D,G,...c,f,i...)>0

To Prove Circles Kissing Number =6
(1a) x1^2+y1^2 -1 ≥ 0
(1b) -x1^2+-y1^2 +1 ≥ 0
(1.2) x1^2+x2^2-2x1.x2+y1^2+y2^2-2y1.y2 - 1 ≥ 0

12x12 matrices
A1a = (100000000000,010000000000,0000....) c=-1
A1b = (-100000000000,0-10000000000,0000....) c=1
A1.2 = (1-100000000000,-110000000000000,000....) c=-1

Roughly 13,000 numbers altogether! (Use sparse arrays)

Converting to a single equation.

We have:

Xn.Xn - 1 = 0

(Xn-Xm)²-1 = Snm²

So this can be converted into a quartic in N(N-1)/2+DN  variables:

(Xn.Xn-1)² + (|Xn-Xm|²-1-(Snm)²)² = 0

For the case of N=5, 1025 variables. A general quartic in 1025 variables has A with 46,261,908,225 components. So the general formula is very long... unless expressed in a tensor notation then we can use tensor simplifications.

X= {1,Xn,Snm}

A=

{An|m,   Bnn'|m}

{Bn|mm',Cnn'|mm'}