Notes on polytope decomposition

The notes here are derived from these notes of Pace Nielsen.

Let [math]\displaystyle{ 1/4 \leq \varepsilon \leq 1/3 }[/math]. The problem here is to optimise the ratio J/I, where

[math]\displaystyle{ J := 3 \int\int_{x+y \leq 1-\varepsilon} (\int_0^{3/2-x-y} F(x,y,z)\ dz)^2\ dx dy }[/math]

[math]\displaystyle{ I := \int\int\int_{x+y+z \leq 3/2} F(x,y,z)^2\ dx dy dz }[/math]

for symmetric F supported on [math]\displaystyle{ R := \{ (x,y,z): x+y+z \leq 3/2 \} }[/math] subject to the vanishing marginal condition

[math]\displaystyle{ \int_0^{3/2-x-y} F(x,y,z)\ dz = 0 }[/math] when [math]\displaystyle{ x+y \geq 1+\varepsilon }[/math].

(Throughout these notes, [math]\displaystyle{ x,y,z }[/math] are understood to be non-negative.

We partition R six identical pieces, one of which is

[math]\displaystyle{ R_{xyz} := \{ (x,y,z) \in R: x+y \leq y+z \leq z+x \}. }[/math]

We then partition [math]\displaystyle{ R_{xyz} }[/math] further into 10 pieces:

Name	Inequalities	[math]\displaystyle{ x,y }[/math] inequalities	[math]\displaystyle{ z }[/math] inequalities
[math]\displaystyle{ R_{xyz} }[/math]	[math]\displaystyle{ x,y,z \geq 0; x+y+z \leq 3/2; x+y \leq y+z \leq z+x }[/math]	[math]\displaystyle{ x \geq y \geq 0; 2x+y \leq 3/2 }[/math]	[math]\displaystyle{ x \leq z \leq 3/2-x-y }[/math]
[math]\displaystyle{ A_{xyz} }[/math]	[math]\displaystyle{ z+x \leq 1-\varepsilon }[/math]	[math]\displaystyle{ 2x \leq 1-\varepsilon }[/math]	[math]\displaystyle{ z \leq 1-\varepsilon-x }[/math]
[math]\displaystyle{ B_{xyz} }[/math]	[math]\displaystyle{ y+z \leq 1-\varepsilon \leq z+x \leq 1+\varepsilon }[/math]	[math]\displaystyle{ 2x \leq 1+\varepsilon; x+y \leq 1-\varepsilon; y \leq 1/2+\varepsilon }[/math]	[math]\displaystyle{ 1-\varepsilon-x \leq z \leq \min(1+\varepsilon-x, 1-\varepsilon-y) }[/math]
[math]\displaystyle{ C_{xyz} }[/math]	[math]\displaystyle{ x+y \leq 1-\varepsilon \leq y+z; z+x \leq 1+\varepsilon }[/math]	[math]\displaystyle{ x+y \leq 1-\varepsilon; x \leq 1/2+\varepsilon }[/math]	[math]\displaystyle{ 1-\varepsilon-y \leq z \leq \min(1+\varepsilon-x }[/math]
[math]\displaystyle{ D_{xyz} }[/math]	[math]\displaystyle{ 1-\varepsilon \leq x+y; z+x \leq 1+\varepsilon }[/math]	[math]\displaystyle{ x+y \geq 1-\varepsilon; 2x \leq 1+\varepsilon }[/math]	[math]\displaystyle{ z \leq 1+\varepsilon-x }[/math]
[math]\displaystyle{ E_{xyz} }[/math]	[math]\displaystyle{ y+z \leq 1-\varepsilon; 1+\varepsilon \leq z+x }[/math]	[math]\displaystyle{ x+y \leq 1-\varepsilon; y \leq 1/2-\varepsilon }[/math]	[math]\displaystyle{ 1+\varepsilon-x \leq z \leq 1-\varepsilon-y }[/math]
[math]\displaystyle{ S_{xyz} }[/math]	[math]\displaystyle{ x+y \leq 1-\varepsilon \leq y+z \leq 1+\varepsilon \leq z+x }[/math] [math]\displaystyle{ z \leq 1/2+\varepsilon }[/math]	[math]\displaystyle{ x+y \leq 1-\varepsilon; x \geq 1/2; y \geq 1/2-2\varepsilon }[/math]	[math]\displaystyle{ \max(1-\varepsilon-y,1+\varepsilon-x) \leq z \leq \min(1/2+\varepsilon,1+\varepsilon-y) }[/math]
[math]\displaystyle{ T_{xyz} }[/math]	[math]\displaystyle{ x+y \leq 1-\varepsilon \leq y+z \leq 1+\varepsilon \leq z+x }[/math] [math]\displaystyle{ z \geq 1/2+\varepsilon; x \geq 1/2-\varepsilon }[/math]	[math]\displaystyle{ x+y \leq 1-\varepsilon; x \geq 1/2-\varepsilon }[/math]	[math]\displaystyle{ \max(1-\varepsilon-y,1+\varepsilon-x,1/2-\varepsilon) \leq z \leq 1+\varepsilon-y }[/math]
[math]\displaystyle{ U_{xyz} }[/math]	[math]\displaystyle{ x+y \leq 1-\varepsilon \leq y+z \leq 1+\varepsilon \leq z+x }[/math] [math]\displaystyle{ x \leq 1/2-\varepsilon }[/math]	[math]\displaystyle{ x \leq 1/2-\varepsilon }[/math]	[math]\displaystyle{ \max(1-\varepsilon-y,1+\varepsilon-x) \leq z \leq 1+\varepsilon-y }[/math]
[math]\displaystyle{ G_{xyz} }[/math]	[math]\displaystyle{ x+y \leq 1-\varepsilon; 1+\varepsilon \leq y+z }[/math]	[math]\displaystyle{ x+y \leq 1-\varepsilon; x \leq 1/2-\varepsilon }[/math]	[math]\displaystyle{ 1+\varepsilon-y \leq z }[/math]
[math]\displaystyle{ H_{xyz} }[/math]	[math]\displaystyle{ 1-\varepsilon \leq x+y; y+z \leq 1+\varepsilon \leq z+x }[/math]	[math]\displaystyle{ x+y \geq 1-\varepsilon }[/math]	[math]\displaystyle{ 1+\varepsilon-x \leq z \leq 1+\varepsilon-y }[/math]

Code

eps:=1/4;

FA := 1 - (1291*x)/1000 + (104*x^2)/125 - (659*y)/500 + (111*x*y)/125 + (1099*y^2)/1000 - (1257*z)/1000 + (637*x*z)/1000 + (56*y*z)/125 + (839*z^2)/1000;
FB:= 57/100 - (303*x)/500 + (117*x^2)/250 - (136*y)/125 + (227*x*y)/500 + (133*y^2)/125 - (303*z)/1000 - (9*x*z)/125 + (57*y*z)/250 + (37*z^2)/250;
FC:= 17/50 - (657*x)/1000 + (227*x^2)/500 - (13*y)/20 + (581*x*y)/1000 + (21*y^2)/40 - (9*z)/1000 + (3*x*z)/1000 + (3*y*z)/200 + z^2/250;
FD:= 0;
FE:= 4711/16000 - (199*x)/2000 - (29*x^2)/1000 - (2101*y)/2000 + (413*x*y)/1500 + (33*y^2)/25 - (19*z)/125 - (13*x*z)/1000 + (31*y*z)/125 + (7*z^2)/600;
FS:= 2409/16000 - (9*x)/80 - (61*x^2)/1000 - (493*y)/1000 + (401*x*y)/1500 + (73*y^2)/125 - (73*z)/500 + (59*x*z)/1000 - (9*y*z)/250 + (79*z^2)/1000;
FT:= -(471/8000) + (367*x)/4000 - (7*x^2)/200 - (1133*y)/2000 + (9*x*y)/25 + (129*y^2)/200 + (373*z)/1000 - (103*x*z)/400 - (3*y*z)/200 - (89*z^2)/400;
FU:= -(2548925261/40960000) + (378889*x)/500 - (1486281*x^2)/500 + (2109761*x^3)/500 - (1806913*x^4)/1000 - (823*y)/1000 + (1028*x*y)/125 - (1276175057*x^2*y)/20800000 + (5231*x^3*y)/40 - (604*y^2)/125 + (465755881*x*y^2)/10400000 - (33092919*x^2*y^2)/400000 + (1941*y^3)/500 - (21127*x*y^3)/1000 + (28*y^4)/125 + (705*z)/8 - (196213*x*z)/200 + (130643581043*x^2*z)/41600000 - (1270877*x^3*z)/500 + (51*y^2*z)/16000 - (91952143*z^2)/3328000 + (619313327*x*z^2)/2080000 - (18524*x^2*z^2)/25 + (3*y^2*z^2)/5000 - (2561*z^3)/1000 + (4869*x*z^3)/500 - (9*z^4)/200;
FG:= -(2695785741/10240000) + (2173499391*x)/1280000 - (12242903151*x^2)/2560000 + (52219413*x^3)/10000 - (1806913*x^4)/1000 + (96070478631*y)/83200000 + (1007933539*x*y)/20800000 + (179877147*x^2*y)/2600000 - (36827397*x^3*y)/25000 - (669613358991*y^2)/166400000 - (1310180447*x*y^2)/2600000 + (10110876*x^2*y^2)/3125 + (19620542273*y^3)/3900000 - (17662711*x*y^3)/12500 - (1806913*y^4)/1000 + (104838525951*z)/166400000 - (126851653541*x*z)/41600000 + (15524384001*x^2*z)/2600000 - (20898059*x^3*z)/6250 - (1531159429*y*z)/640000 + (14385788557*y^2*z)/2600000 - (20898059*y^3*z)/6250 - (91851736253*z^2)/166400000 + (4642413047*x*z^2)/2600000 - (738812349*x^2*z^2)/400000 + (2655529*y*z^2)/1625 - (756836049*y^2*z^2)/400000 + (1081347403*z^3)/5200000 - (33823447*x*z^3)/100000 - (36827397*y*z^3)/100000 - (2238403*z^4)/80000;
FH:= -(37/250) + (71*x)/500 - (109*x^2)/1000 + (6*z)/125 - (3*x*z)/1000 - (9*z^2)/250;

Axyz:=Heaviside((1-eps)-(z+x));
Dxyz:=Heaviside(1+eps-(z+x))*Heaviside((x+y)-(1-eps));
ABCDxyz:=Heaviside(1+eps-(z+x));
ABExyz:=Heaviside((1-eps)-(y+z));
Exyz:=Heaviside((z+x)-(1+eps))*Heaviside((1-eps)-(y+z));
BExyz := ABExyz - Axyz;
Bxyz:=ABExyz-Axyz-Exyz;
Gxyz:=Heaviside(y+z-(1+eps));
DHxyz:=Heaviside(x+y-(1-eps));
CFxyz:=Heaviside((y+z)-(1-eps))-DHxyz-Gxyz;
Hxyz:=DHxyz-Dxyz;
Fxyz:=CFxyz-Cxyz;

IA := int(int(int(FA*FA*Axyz,z=x..(3/2-y-x)),x=y..(3/2-y)/2),y=0..1/2);
IB := int(int(int(FB*FB*BExyz,z=x..(3/2-y-x)),x=y..(3/2-y)/2),y=0..1/2) - int(int(int(FB*FB,y=0..1-eps-z),x=1+eps-z..z),z=1/2+eps/2..1-eps);
IC := int(int(int(FC*FC*ABCDxyz,z=x..(3/2-y-x)),x=y..(3/2-y)/2),y=0..1/2) - int(int(int(FC*FC*Axyz,z=x..(3/2-y-x)),x=y..(3/2-y)/2),y=0..1/2) - int(int(int(FC*FC*BExyz,z=x..(3/2-y- x)),x=y..(3/2-y)/2),y=0..1/2) - int(int(int(FC*FC*Dxyz,z=x..(3/2-y-x)),x=y..(3/2-y)/2),y=0..1/2) + int(int(int(FC*FC,y=0..1-eps-z),x=1+eps-z..z),z=1/2+eps/2..1-eps);
ID := int(int(int(FD*FD*Dxyz,z=x..(3/2-y-x)),x=y..(3/2-y)/2),y=0..1/2);
IE := int(int(int(FE*FE,y=0..1-eps-z),x=1+eps-z..z),z=1/2+eps/2..1-eps);
IS := int(int(int(FS*FS,x=1+eps-z..(1-eps-y)),z=y+2*eps..1/2+eps),y=1/2-3*eps/2..1/2-eps)+int(int(int(FS*FS,x=1+eps-z..(1-eps-y)),z=1-eps-y..1/2+eps),y=0..1/2-3*eps/2);
IT := int(int(int(FT*FT,y=0..3/2-x-z),x=1/2-eps..3/2-z),z=1/2+2*eps..1+eps)+int(int(int(FT*FT,y=0..3/2-x-z),x=1+eps-z..3/2-z),z=1/2+eps..1/2+2*eps);
IU := int(int(int(FU*FU,z=1+eps-x..1+eps-y),y=0..x),x=0..1/2-eps);
IG := int(int(int(FG*FG*Gxyz,z=x..(3/2-y-x)),x=y..(3/2-y)/2),y=0..1/2);
IH := int(int(int(FH*FH*Hxyz,z=x..(3/2-y-x)),x=y..(3/2-y)/2),y=0..1/2);

Isum := 6*(IA+IB+IC+ID+IE+IS+IT+IU+IG+IH);
#                                  0.03057904694 

FAxyz := FA;
FAyzx := subs( {x=y,y=z,z=x}, FA );
FAzyx := subs( {x=z,z=x}, FA );
FBxyz := FB;
FByzx := subs( {x=y,y=z,z=x}, FB );
FBzyx := subs( {x=z,z=x}, FB );
FCxyz := FC;
FCyzx := subs( {x=y,y=z,z=x}, FC );
FCzyx := subs( {x=z,z=x}, FC );
FExyz := FE;
FEyzx := subs( {x=y,y=z,z=x}, FE );
FEzyx := subs( {x=z,z=x}, FE );
FSxyz := FS;
FSyzx := subs( {x=y,y=z,z=x}, FS );
FSzyx := subs( {x=z,z=x}, FS );
FTxyz := FT;
FTyzx := subs( {x=y,y=z,z=x}, FT );
FTzyx := subs( {x=z,z=x}, FT );
FUxyz := FU;
FUyzx := subs( {x=y,y=z,z=x}, FU );
FUzyx := subs( {x=z,z=x}, FU );
FGxyz := FG;
FGyzx := subs( {x=y,y=z,z=x}, FG );
FGzyx := subs( {x=z,z=x}, FG );
FHxyz := FH;
FHyzx := subs( {x=y,y=z,z=x}, FH );
FHzyx := subs( {x=z,z=x}, FH ); 

J1func := int(FAyzx, z=0..y) + int(FAzyx, z=y..x) + int(FAxyz, z=x..1-eps-x) + int(FBxyz, z=1-eps-x..1-eps-y) + int(FCxyz, z=1-eps-y..1+eps-x) + int(FUxyz, z=1+eps-x..1+eps-y) + int(FGxyz, z=1+eps-y..3/2-x-y);
J1 := int(int(J1func*J1func, y=0..x), x=0..1/2-eps);

J2func := int(FAyzx, z=0..y) + int(FAzyx, z=y..x) + int(FAxyz, z=x..1-eps-x) + int(FBxyz, z=1-eps-x..1-eps-y) + int(FCxyz, z=1-eps-y..3/2-x-y);
J2 := int(int(J2func*J2func, y=1/2-eps..x),x=1/2-eps..1/2-eps/2);

J3func := int(FAyzx, z=0..y) + int(FAzyx, z=y..x) + int(FAxyz, z=x..1-eps-x) + int(FBxyz, z=1-eps-x..1-eps-y) + int(FCxyz, z=1-eps-y..1+eps-x) + int(FTxyz, z=1+eps-x..3/2-x-y);
J3 := int(int(J3func*J3func, y=0..1/2-eps),x=1/2-eps..1/2-eps/2);

J4func := int(FAyzx, z=0..y) + int(FAzyx, z=y..1-eps-x) + int(FBzyx, z=1-eps-x..x) + int(FBxyz, z=x..1-eps-y) + int(FCxyz, z=1-eps-y..3/2-x-y);
J4 := int(int(J4func*J4func, y=1/2-eps..1-eps-x), x=1/2-eps/2..1/2);

J5func := int(FAyzx, z=0..y) + int(FAzyx, z=y..1-eps-x) + int(FBzyx, z=1-eps-x..x) + int(FBxyz, z=x..1-eps-y) + int(FCxyz, z=1-eps-y..1+eps-x) + int(FTxyz, z=1+eps-x..3/2-x-y);
J5 := int(int(J5func*J5func,y=0..1/2-eps),x=1/2-eps/2..1/2);

J6func := int(FAyzx, z=0..y) + int(FAzyx, z=y..1-eps-x) + int(FBzyx, z=1-eps-x..x) + int(FBxyz, z=x..1-eps-y) + int(FCxyz, z=1-eps-y..1+eps-x) + int(FSxyz, z=1+eps-x..1/2+eps) + int(FTxyz, z=1/2+eps..3/2-x-y);
J6 := int(int(J6func*J6func,y=x-2*eps..1-eps-x),x=2*eps..1/2+eps/2) + int(int(J6func*J6func,y=0..1-eps-x),x=1/2..2*eps);

J7func := int(FAyzx, z=0..y) + int(FAzyx, z=y..1-eps-x) + int(FBzyx, z=1-eps-x..x) + int(FBxyz, z=x..1+eps-x) + int(FExyz, z=1+eps-x..1-eps-y) + int(FSxyz, z=1-eps-y..1/2+eps) + int(FTxyz, z=1/2+eps..3/2-x-y);
J7 := int(int(J7func*J7func,y=0..x-2*eps),x=2*eps..1/2+eps/2);

J8func := int(FAyzx, z=0..y) + int(FAzyx, z=y..1-eps-x) + int(FBzyx, z=1-eps-x..1+eps-x) + int(FEzyx, z=1+eps-x..x) + int(FExyz, z=x..1-eps-y) + int(FSxyz, z=1-eps-y..1/2+eps) + int(FTxyz, z=1/2+eps..3/2-x-y);
J8 := int(int(J8func*J8func,y=0..1-eps-x),x=1/2+eps/2..1-eps);

Jsum := 6*(J1+J2+J3+J4+J5+J6+J7+J8);
#                                  0.06116827145

# these quantities all need to be zero 

M1 := simplify(int(FGyzx, z=0..3/2-x-y));
M2 := simplify(int(FGyzx, z=0..y) + int(FGzyx, z=y..3/2-x-y));
M3 := simplify(int(FUyzx, z=0..1+eps-x) + int(FGyzx, z=1+eps-x..y) + int(FGzyx, z=y..3/2-x-y));
M4 := simplify(int(FUyzx, z=0..1+eps-x) + int(FGyzx, z=1+eps-x..3/2-x-y));
M5 := simplify(int(FTyzx, z=0..3/2-x-y));
# M6 := simplify(int(FSyzx, z=0..1-eps-y) + int(FHyzx, z=1-eps-y..3/2-x-y));
M7 := simplify(int(FEyzx, z=0..1-eps-x) + int(FSyzx, z=1-eps-x..1-eps-y) + int(FHyzx, z=1-eps-y..3/2-x-y));
# M8 := simplify(int(FHyzx, z=0..3/2-x-y));

# if this quantity is positive, we win
evalf( Jsum - 2*Isum );

For a simpler solution, use

FA:= -66+96 * x-147 * x^2+125 * x^3+128 * y-122 * x * y+104 * x^2 * y-275 * y^2+394 * y^3+99 * z-58 * x * z+63 * x^2 * z-98 * y * z+51 * x * y * z+41 * y^2 * z-112 * z^2+24 * x * z^2+72 * y * z^2+50 * z^3;
FB:= -41+52 * x-73 * x^2+25 * x^3+108 * y-66 * x * y+71 * x^2 * y-294 * y^2+56 * x * y^2+363 * y^3+33 * z+15 * x * z+22 * x^2 * z-40 * y * z-42 * x * y * z+75 * y^2 * z-36 * z^2-24 * x * z^2+26 * y * z^2+20 * z^3;
FC:= -22+45 * x-35 * x^2+63 * y-99 * x * y+82 * x^2 * y-140 * y^2+54 * x * y^2+179 * y^3;
FD := 0;
FE:= -12+8 * x+32 * y;
FG:= 5274-19833 * x+18570 * x^2-5128 * x^3-18024 * y+44696 * x * y-20664 * x^2 * y+16158 * y^2-19056 * x * y^2-4592 * y^3-10704 * z+26860 * x * z-12588 * x^2 * z+24448 * y * z-30352 * x * y * z-10980 * y^2 * z+7240 * z^2-9092 * x * z^2-8288 * y * z^2-1632 * z^3;
FH:= 8 * z;
FS:= -6+8 * x+16 * y;
FT := 18-30 * x+12 * x^2+42 * y-20 * x * y-66 * y^2-45 * z+34 * x * z+22 * z^2;
FU := 94-1823 * x+5760 * x^2-5128 * x^3+54 * y-168 * x^2 * y+105 * y^2+1422 * x * z-2340 * x^2 * z-192 * y^2 * z-128 * z^2-268 * x * z^2+64 * z^3;