Maple calculations

From Polymath1Wiki
Jump to: navigation, search

The computations below were done in Maple 12. The parameters a, b, c, etc. are initially the Behrend sphere densities (e.g. a is the proportion of points with no 2s that lie in the set), but when one converts from the X's to the Y's, they are the Behrend sphere counts (i.e. a is now the number of points with no 2s that lie in the set).

with(Optimization);
A3 := 8*a + 12*b + 6*c + d;
A4 := 16*a+32*b+24*c+8*d+e;
A5 := 32*a+80*b+80*c+40*d+10*e+f;
A6 := 64*a+192*b+240*c+160*d+60*e+12*f+g;
A7 := 128*a+448*b+672*c+560*d+280*e+84*f+14*g+h;
X1 := {2*a+b <= 2, b <= 1};
X2 := {4*a+2*b+c <= 4, 2*a+c <= 2, 2*b+c <= 2, c <= 1};
X3 := {op(X2), op(subs([a=b,b=c,c=d],X2)), 2*a+d <= 2};

These are the inequalities inherited from xy1, xy2, xxx cubes (averaged over symmetries)

Y3 := subs([a=a/8,b=b/12,c=c/6,d=d],X3);
LPSolve(a+b+c+d,Y3,assume=nonnegint,depthlimit=100,maximize);
[16, [a = 4, b = 6, c = 6, d = 0]]

This gives a proof of [math]c'_3 \leq 16[/math].

X3 := {op(X3), 8*a+6*b+6*c+2*d<=11, 4*a+4*b+3*c+d<=6, 7*a+3*b+3*c+d <= 7, 4*a+6*c+2*d<=7, 5*a+3*c+d<=5};

This comes from the linear inequalities obeyed by the 3D extremals.

X4 := {op(X3), op(subs([a=b,b=c,c=d,d=e],X3)), op(subs([b=c,c=e],X2))};

The op(subs([b=c,c=e],X2) term here reflects the presence of diagonal 2D cubes such as xxyy in 4D with two appearances of each wildcard.

X4 := {op(X4),4*a+2*b+3*c+2*d+e <= 6, 8*a+2*b+3*c+2*d+e <= 8};

These come from the xxyz slices, see Peake.986 or Peake.993

Y4 := subs([a=a/16,b=b/32,c=c/24,d=d/8],X4);
Y4 := {a*3 + b*12 + c*12 + d*23 + e*72 <= 480, a*1 + b*4 + c*4 + d*4 + e*35 <= 160, a*1 + b*4 + c*4 + d*1 + e*41 <= 160, a*0 + b*0 + c*1 + d*0 + e*12 <= 24, a*3 + b*12 + c*19 + d*36 + e*117 <= 648, a*0 + b*0 + c*2 + d*3 + e*12 <= 48, a*3 + b*12 + c*17 + d*33 + e*102 <= 600, a*0 + b*3 + c*2 + d*5 + e*12 <= 96, a*12 + b*57 + c*48 + d*95 + e*288 <= 2064, a*4 + b*19 + c*16 + d*19 + e*134 <= 688, a*4 + b*19 + c*16 + d*4 + e*164 <= 688, a*0 + b*3 + c*4 + d*9 + e*24 <= 144, a*0 + b*3 + c*2 + d*3 + e*18 <= 96, a*0 + b*3 + c*2 + d*0 + e*24 <= 96, a*3 + b*4 + c*4 + d*7 + e*24 <= 168, a*1 + b*1 + c*1 + d*1 + e*8 <= 43, a*2 + b*2 + c*2 + d*3 + e*13 <= 86, a*3 + b*2 + c*4 + d*6 + e*27 <= 138, a*6 + b*2 + c*9 + d*12 + e*60 <= 270, a*6 + b*6 + c*7 + d*12 + e*42 <= 282, a*20 + b*14 + c*15 + d*18 + e*106 <= 650, a*9 + b*6 + c*8 + d*12 + e*51 <= 318, a*27 + b*18 + c*20 + d*24 + e*141 <= 858, a*34 + b*16 + c*19 + d*15 + e*110 <= 832, a*7 + b*2 + c*4 + d*4 + e*20 <= 154, a*6 + b*0 + c*4 + d*3 + e*15 <= 120, a*18 + b*6 + c*11 + d*12 + e*60 <= 426, a*18 + b*6 + c*10 + d*9 + e*57 <= 402, a*11 + b*4 + c*6 + d*5 + e*35 <= 248, a*9 + b*3 + c*5 + d*3 + e*30 <= 201, a*3 + b*0 + c*2 + d*0 + e*12 <= 60, a*16 + b*6 + c*9 + d*8 + e*54 <= 370, a*0 + b*0 + c*0 + d*0 + e*1 <= 1, a*0 + b*0 + c*0 + d*1 + e*4 <= 8, a*0 + b*1 + c*1 + d*3 + e*8 <= 44, a*1 + b*2 + c*1 + d*3 + e*16 <= 72, a*3 + b*8 + c*5 + d*15 + e*40 <= 280, a*1 + b*2 + c*1 + d*9 + e*26 <= 106, a*7 + b*14 + c*7 + d*29 + e*80 <= 504, a*0 + b*2 + c*1 + d*2 + e*16 <= 64, a*0 + b*1 + c*0 + d*0 + e*16 <= 32, a*0 + b*1 + c*0 + d*6 + e*16 <= 56, a*0 + b*7 + c*0 + d*18 + e*40 <= 224, a*0 + b*5 + c*3 + d*9 + e*20 <= 160, a*10 + b*15 + c*14 + d*25 + e*84 <= 602, a*1 + b*1 + c*1 + d*3 + e*9 <= 50, a*9 + b*6 + c*8 + d*18 + e*57 <= 342, a*9 + b*6 + c*7 + d*18 + e*57 <= 330, a*1 + b*0 + c*1 + d*3 + e*13 <= 42, a*9 + b*3 + c*10 + d*18 + e*69 <= 342, a*5 + b*2 + c*3 + d*10 + e*37 <= 162, a*3 + b*1 + c*2 + d*6 + e*23 <= 98, a*2 + b*2 + c*1 + d*3 + e*19 <= 80, a*3 + b*3 + c*2 + d*6 + e*18 <= 120, a*2 + b*2 + c*1 + d*9 + e*27 <= 112, a*14 + b*14 + c*7 + d*31 + e*93 <= 560, a*6 + b*9 + c*7 + d*15 + e*42 <= 336, a*1 + b*1 + c*1 + d*2 + e*6 <= 44, a*2 + b*2 + c*1 + d*2 + e*22 <= 80, a*6 + b*6 + c*5 + d*6 + e*42 <= 240, a*30 + b*21 + c*19 + d*27 + e*138 <= 912, a*3 + b*2 + c*2 + d*4 + e*13 <= 94, a*15 + b*10 + c*8 + d*19 + e*62 <= 440, a*6 + b*4 + c*3 + d*7 + e*29 <= 176, a*21 + b*14 + c*12 + d*25 + e*82 <= 616, a*81 + b*54 + c*49 + d*72 + e*357 <= 2376, a*18 + b*12 + c*9 + d*16 + e*102 <= 528, a*3 + b*3 + c*1 + d*15 + e*44 <= 174, a*6 + b*6 + c*1 + d*36 + e*107 <= 384, a*21 + b*21 + c*7 + d*51 + e*146 <= 840, a*1 + b*1 + c*0 + d*6 + e*19 <= 64, a*1 + b*1 + c*0 + d*3 + e*10 <= 43, a*42 + b*42 + c*7 + d*108 + e*317 <= 1680, a*7 + b*7 + c*1 + d*18 + e*54 <= 280, a*2 + b*1 + c*1 + d*1 + e*6 <= 48, a*9 + b*3 + c*4 + d*9 + e*24 <= 198, a*2 + b*1 + c*1 + d*3 + e*9 <= 56, a*3 + b*2 + c*1 + d*9 + e*27 <= 118, a*30 + b*12 + c*11 + d*39 + e*117 <= 720, a*15 + b*6 + c*5 + d*21 + e*63 <= 366, a*3 + b*1 + c*1 + d*3 + e*8 <= 62, a*6 + b*5 + c*1 + d*30 + e*90 <= 328, a*6 + b*2 + c*1 + d*12 + e*36 <= 160, a*9 + b*3 + c*2 + d*15 + e*45 <= 222, a*12 + b*3 + c*2 + d*18 + e*51 <= 264, a*3 + b*1 + c*1 + d*2 + e*5 <= 56, a*4 + b*1 + c*2 + d*2 + e*9 <= 80, a*2 + b*0 + c*1 + d*1 + e*3 <= 34, a*16 + b*3 + c*6 + d*8 + e*21 <= 272, a*12 + b*6 + c*5 + d*15 + e*45 <= 306, a*39 + b*24 + c*17 + d*51 + e*153 <= 1080, a*3 + b*2 + c*1 + d*5 + e*15 <= 90, a*17 + b*12 + c*6 + d*28 + e*84 <= 520, a*15 + b*9 + c*7 + d*18 + e*57 <= 408, a*9 + b*4 + c*3 + d*9 + e*23 <= 200, a*33 + b*24 + c*11 + d*57 + e*169 <= 1032, a*21 + b*14 + c*7 + d*33 + e*97 <= 616, a*19 + b*6 + c*10 + d*9 + e*55 <= 408, a*15 + b*5 + c*8 + d*5 + e*47 <= 328, a*8 + b*2 + c*4 + d*3 + e*21 <= 160, a*4 + b*1 + c*2 + d*1 + e*11 <= 80, a*6 + b*5 + c*1 + d*14 + e*42 <= 216, a*66 + b*63 + c*11 + d*162 + e*478 <= 2544, a*8 + b*3 + c*4 + d*4 + e*24 <= 176, a*7 + b*3 + c*3 + d*4 + e*19 <= 152, a*6 + b*2 + c*3 + d*3 + e*17 <= 128, a*48 + b*18 + c*17 + d*24 + e*132 <= 960, a*8 + b*3 + c*3 + d*4 + e*20 <= 160, a*6 + b*2 + c*2 + d*3 + e*13 <= 112, a*9 + b*3 + c*2 + d*12 + e*36 <= 201, a*6 + b*2 + c*1 + d*8 + e*24 <= 132, a*12 + b*3 + c*2 + d*12 + e*33 <= 222, a*6 + b*2 + c*1 + d*6 + e*16 <= 118, a*18 + b*7 + c*3 + d*18 + e*46 <= 368, a*5 + b*2 + c*1 + d*5 + e*13 <= 104, a*3 + b*1 + c*1 + d*1 + e*7 <= 56, a*33 + b*12 + c*11 + d*15 + e*93 <= 648, a*6 + b*3 + c*2 + d*3 + e*30 <= 144, a*21 + b*3 + c*2 + d*18 + e*51 <= 336, a*1 + b*0 + c*0 + d*1 + e*4 <= 16, a*14 + b*3 + c*3 + d*9 + e*24 <= 226, a*56 + b*11 + c*12 + d*36 + e*97 <= 896, a*46 + b*9 + c*6 + d*36 + e*99 <= 746, a*56 + b*9 + c*6 + d*46 + e*129 <= 896, a*9 + b*0 + c*4 + d*4 + e*12 <= 144, a*18 + b*3 + c*6 + d*8 + e*21 <= 288, a*4 + b*1 + c*1 + d*2 + e*5 <= 64, a*1 + b*0 + c*0 + d*0 + e*8 <= 16, a*24 + b*5 + c*5 + d*15 + e*42 <= 384, a*16 + b*3 + c*2 + d*12 + e*35 <= 256, a*9 + b*0 + c*4 + d*0 + e*24 <= 144, a*12 + b*2 + c*4 + d*3 + e*21 <= 192, a*8 + b*2 + c*2 + d*3 + e*13 <= 128, a*21 + b*4 + c*2 + d*16 + e*48 <= 336, a*84 + b*16 + c*9 + d*64 + e*186 <= 1344, a*6 + b*1 + c*2 + d*1 + e*11 <= 96, a*4 + b*1 + c*1 + d*1 + e*7 <= 64, a*48 + b*12 + c*11 + d*15 + e*93 <= 768, a*26 + b*6 + c*3 + d*18 + e*48 <= 418, a*28 + b*7 + c*3 + d*18 + e*46 <= 448, a*28 + b*6 + c*3 + d*20 + e*56 <= 448, a*8 + b*2 + c*1 + d*5 + e*13 <= 128, a*8 + b*2 + c*1 + d*2 + e*22 <= 128, a*12 + b*3 + c*2 + d*3 + e*30 <= 192, a*4 + b*1 + c*0 + d*0 + e*16 <= 64};

These are the inequalities from the 4D brute force search

LPSolve(a+b+c+d+e,Y4,assume=nonnegint,depthlimit=100,maximize);
[43, [a = 5, b = 20, c = 18, d = 0, e = 0]]

Gives the correct answer, as it should

LPSolve(a+b+c+d+e,{op(Y4),e=1},assume=nonnegint,depthlimit=100,maximize);
[36, [a = 5, b = 15, c = 12, d = 3, e = 1]]

Again correct

LPSolve(c,{op(Y4),a+b+c+d+e=43},assume=nonnegint,depthlimit=100);
[18, [a = 5, b = 20, c = 18, d = 0, e = 0]]

This shows that 43-point sets have c at least 18.

LPSolve(c,{op(Y4),a+b+c+d+e>=42},assume=nonnegint,depthlimit=100);
[12, [a = 6, b = 24, c = 12, d = 0, e = 0]]

This shows that 42+ point sets have c at least 12

LPSolve(d,{op(Y4),a+b+c+d+e >= 41},assume=nonnegint,depthlimit=100,maximize);
[3, [a = 6, b = 15, c = 17, d = 3, e = 0]]

This shows that 41+ point Moser sets have d at most 3.

LPSolve(d,{op(Y4),a+b+c+d+e >= 40},assume=nonnegint,depthlimit=100,maximize);
[4, [a = 6, b = 15, c = 15, d = 4, e = 0]]

This shows that 40+ point Moser sets have d at most 4.

X4 := subs([a=16*a,b=32*b,c=24*c,d=8*d],Y4);

convert back to densities rather than counts

X5 := {op(X4), op(subs([a=b,b=c,c=d,d=e,e=f],X4)), 2*a+f <= 2};

xyzw1, xyzw2, and xxxx cube inequalities

X5 := {op(X5), 4*a+b+2*c+2*d+e+f <= 11/2, 2*e+f <= 2, 4*a+4*c+2*d+e+f <= 6, 4*a+2*b+2*c+2*d+e+f <= 6, 7*a+b+2*c+2*d+e+f <= 7, 4*a+2*e+f <= 4, 8*a+4*c+2*d+e+f <= 8, 8*a+2*b+2*c+2*d+e+f <= 8, 4*a+2*b+2*d+2*e+f <= 6, 8*a+2*b+2*d+2*e+f <= 8};

These inequalities come from xxyyz cubes, see Peake.989

X5 := {op(X5),8*a+4*b+2*c+2*d+4*e+2*f <=11,4*a+2*b+1*c+2*d+2*e+1*f <= 6,0*a+0*b+2*c+0*d+0*e+1*f <= 2,4*a+4*b+1*c+0*d+2*e+1*f <= 6,7*a+2*b+1*c+1*d+2*e+1*f <= 7,8*a+2*b+1*c+2*d+2*e+1*f <= 8,4*a+0*b+2*c+0*d+0*e+1*f <= 4,4*a+0*b+2*c+2*d+2*e+1*f <= 6,8*a+0*b+2*c+2*d+2*e+1*f <= 8,8*a+4*b+1*c+0*d+2*e+1*f <= 8};

These inequalities come from xxxyz cubes, see Peake.991

Y5 := subs([a=a/32,b=b/80,c=c/80,d=d/40,e=e/10],X5);
LPSolve(a+b+c+d+e+f,Y5,assume=nonnegint,depthlimit=100,maximize);
[125, [a = 8, b = 39, c = 78, d = 0, e = 0, f = 0]]

Off by one! The truth is [math]c'_5=124[/math].

LPSolve(a+b+c+d+e+f,{op(Y5),f=1},assume=nonnegint,depthlimit=100,maximize);
[110, [a = 14, b = 35, c = 40, d = 20, e = 0, f = 1]]

This, together with the bound [math]c'_5=124[/math], implies that [math]a+b+c+d+e+f+14f \leq 124[/math].

Y5 := {op(Y5), a+b+c+d+e+f+14*f <= 124};
LPSolve(a+b+c+d+e+f,{op(Y5),e>=1},assume=nonnegint,depthlimit=100,maximize);
[123, [a = 8, b = 40, c = 72, d = 2, e = 1, f = 0]]

This gives an alternate proof of e=0 for 125-point Moser sets

X5 := subs([a=a*32,b=b*80,c=c*80,d=d*40,e=e*10],Y5);
X6 := {op(X5), op(subs([a=b,b=c,c=d,d=e,e=f,f=g],X5)), op(subs([b=d,c=g],X2)), op(subs([b=c,c=e,d=g],X3))};

xyzwu1, xyzwu2, xxxyyy, xxyyzz cube inequalities

X6 := {op(X6),8*a+4*b+2*c+2*e+4*f+2*g <= 11,0*a+0*b+2*c+0*e+0*f+1*g <= 2,4*a+2*b+1*c+2*e+2*f+1*g <= 6,7*a+2*b+1*c+1*e+2*f+1*g <= 7,4*a+0*b+2*c+0*e+0*f+1*g <= 4,4*a+0*b+2*c+2*e+2*f+1*g <= 6,8*a+0*b+2*c+2*e+2*f+1*g <= 8,8*a+2*b+1*c+2*e+2*f+1*g <= 8,4*a+4*b+1*c+0*e+2*f+1*g <= 6,8*a+4*b+1*c+0*e+2*f+1*g <= 8};

These come from xxxxyz cubes, see Peake.991

X6 := {op(X6),4*a+2*b+0*c+3*d+1*e+1*f+1*g <= 6,4*a+0*b+2*c+3*d+1*e+1*f+1*g <= 6,8*a+2*b+0*c+3*d+1*e+1*f+1*g <= 8,8*a+0*b+2*c+3*d+1*e+1*f+1*g <= 8,0*a+4*b+0*c+0*d+2*e+0*f+1*g <= 4,0*a+0*b+4*c+0*d+0*e+2*f+1*g <= 4,8*a+4*b+0*c+0*d+2*e+0*f+1*g <= 8,8*a+0*b+4*c+0*d+0*e+2*f+1*g <= 8};

These come from xxxyyz cubes, see Peake.991, Peake.993

Y6 := subs([a=a/64,b=b/192,c=c/240,d=d/160,e=e/60,f=f/12],X6);
LPSolve(a+b+c+d+e+f+g,Y6,assume=nonnegint,depthlimit=500,maximize);
[356, [a = 24, b = 72, c = 180, d = 80, e = 0, f = 0, g = 0]]
LPSolve(a+b+c+d+e+f+g,{op(Y6),g=1},assume=nonnegint,depthlimit=100,maximize);
[337, [a = 26, b = 89, c = 120, d = 80, e = 20, f = 1, g = 1]]

This, together with the bound [math]c'_6=353[/math], implies that [math]a+b+c+d+e+f+g+16g \leq 353[/math]. Also shows that g=0 for 338+ point solutions.

LPSolve(a+b+c+d+e+f+g,{op(Y6),f>=1},assume=nonnegint,depthlimit=500,maximize);
[353, [a = 24, b = 77, c = 179, d = 72, e = 0, f = 1, g = 0]]

This shows that f=0 for 354+ point solutions.

LPSolve(e,{op(Y6),a+b+c+d+e+f+g>=354},assume=nonnegint,depthlimit=500,maximize);
[5, [a = 23, b = 76, c = 170, d = 80, e = 5, f = 0, g = 0]]

This shows that there are at most 5 "e" points for 354+ point solutions.

LPSolve(e,{op(Y6),a+b+c+d+e+f+g>=355},assume=nonnegint,depthlimit=500,maximize);
[2, [a = 24, b = 73, c = 178, d = 78, e = 2, f = 0, g = 0]]

Only 2 "e" points allowed for 355+ point solutions.

LPSolve(e,{op(Y6),a+b+c+d+e+f+g>=356},assume=nonnegint,depthlimit=500,maximize);
[0, [a = 24, b = 72, c = 180, d = 80, e = 0, f = 0, g = 0]]

No "e" points for 356-point solutions.

LPSolve(a,{op(Y6),a+b+c+d+e+f+g>=356},assume=nonnegint,depthlimit=500,maximize);
[24, [a = 24, b = 72, c = 180, d = 80, e = 0, f = 0, g = 0]]
LPSolve(b,{op(Y6),a+b+c+d+e+f+g>=356},assume=nonnegint,depthlimit=500,maximize);
[72, [a = 24, b = 72, c = 180, d = 80, e = 0, f = 0, g = 0]]
LPSolve(c,{op(Y6),a+b+c+d+e+f+g>=356},assume=nonnegint,depthlimit=500);
[180, [a = 24, b = 72, c = 180, d = 80, e = 0, f = 0, g = 0]]
LPSolve(d,{op(Y6),a+b+c+d+e+f+g>=356},assume=nonnegint,depthlimit=500);
[80, [a = 24, b = 72, c = 180, d = 80, e = 0, f = 0, g = 0]]

This shows that the only 356-point statistic is (24,72,180,80,0,0,0).

X6 := {op(X6), A6+16*g <= 353};
X7 := {op(X6), op(subs([a=b,b=c,c=d,d=e,e=f,f=g,g=h],X6)), 2*a+h <= 2};

xyzwuv1, xyzwuv2, xxxxxxx inequalities

Y7 := subs([a=a/128,b=b/448,c=c/672,d=d/560,e=e/280,f=f/84,g=g/14],X7);
LPSolve(a+b+c+d+e+f+g+h,Y7,assume=nonnegint,depthlimit=500,maximize);
[1041, [a = 46, b = 168, c = 336, d = 417, e = 72, f = 0, g = 2, h = 0]]
LPSolve(a+b+c+d+e+f+g+h,{op(Y7),h=1},assume=nonnegint,depthlimit=100,maximize);
[1007, [a = 55, b = 179, c = 336, d = 280, e = 139, f = 14, g = 3, h = 1]]