Lookup table

A 113 MB lookup table (12MB when compressed) was created. The purpose of the table is, given a forbidden set [math]\displaystyle{ A \subset [3]^3 }[/math], to compute all the possible statistics (a,b,c,d) of Moser sets that avoid A.

To reduce the size of this table, the following reductions were employed:

• One can assume that the forbidden set A does not contain the centre 222. This is because the only effect of adding in the centre is to send d to zero in the list of statistics. This reduces the number of forbidden sets from 2^27 to 2^26.
• In principle, one can use the 48 symmetries of the cube to reduce 2^26 to 2^26/48 ~ 1,400,000. In practice, we will use 144*2^14 ~ 2,400,000 instead, to facilitate lookup. The way this worked was that I split the forbidden set into a 12-bit string (representing the b's) and a 14-bit string (representing the a's and c's). The b-string was then mapped to the reflection of itself (among all 48 reflections) which had the smallest b-value; of the 4096 b-strings, there are 144 minimal such b-strings. So the total number of forbidden sets is 144 * 2^{14}. The minimal b-strings, in decimal, are

0 1 3 6 7 15 19 20 21 22 23 28 29 31 54 55 56 57 58 59 62 63 96 97 99 101 102 103 111 112 113 115 116 117 118 119 
124 125 127 240 241 243 246 247 255 270 271 284 285 286 287 318 319 324 325 327 332 333 334 335 343 348 349 350 351 
360 361 362 363 364 365 366 367 377 379 380 381 382 383 449 451 454 455 457 459 462 463 468 469 470 471 473 475 476 
477 478 479 497 498 499 502 503 504 505 506 507 510 511 876 877 879 895 911 924 925 927 938 939 942 943 958 959 995 
998 999 1005 1007 1011 1013 1014 1015 1020 1021 1023 1782 1783 1785 1787 1791 2013 2015 2046 2047 4095

• The (1,b,c,d) statistics can be recovered from the (0,b,c,d) statistics, because as long as A does not forbid all the a's, one can always add one a-point "for free" (it cannot create a line). So we can assume a is not 1.
• For each (a,c,d), one only needs to record the largest b which is feasible (a number between 0 and 12, or -1 if no such b exists). From the preceding discussion we can ignore the case a=1. The cases (a,c,d) = (0,0,0) or (8,0,0) are also degenerate and can be deleted. Given the statistics for 3D Moser sets, this leaves 49 choices for (a,c,d), which I ordered as

(2,0,0) (3,0,0) (4,0,0) (5,0,0) (6,0,0) (7,0,0)
(0,1,0) (2,1,0) (3,1,0) (4,1,0) (5,1,0) (6,1,0)
(0,2,0) (2,2,0) (3,2,0) (4,2,0) (5,2,0) (6,2,0)
(0,3,0) (2,3,0) (3,3,0) (4,3,0) (5,3,0) 
(0,4,0) (2,4,0) (3,4,0) (4,4,0) 
(0,5,0) (2,5,0) (3,5,0) (4,5,0) 
(0,6,0) (2,6,0) 
(0,0,1) (2,0,1) (3,0,1) (4,0,1) 
(0,1,1) (2,1,1) (3,1,1) (4,1,1) 
(0,2,1) (2,2,1) (3,2,1) (4,2,1) 
(0,3,1) (2,3,1) (3,3,1) (4,3,1) 

For each forbidden set A, and each such value of a,c,d, I recorded the largest b-value such that (a,b,c,d) is a feasible statistic of a Moser set avoiding A (or -1, if no such b-value exists), for a total size of 144 * 2^{14} * 49 = 110 MB. (Presumably the extra 3MB in my file are for file management purposes.)

The C code to generate table is here. The file took about 80 minutes to generate. What I did was as follows. I brute-force located all 3813884 3D Moser sets, and sorted them into the 499 (a,b,c,d) possible statistics, creating 499 lists. I then threw away the redundant or easy statistics (i.e. (1,b,c,d), (0,1,c,d), (0,0,1,d), (a,0,0,0), (0,b,0,0), (0,0,c,0), (0,0,0,d)), leaving 369 lists, totaling 3151007 sets in all. I sorted these lists by size; most are quite small, for instance 159 of them are under 1000 in length, the longest being (2,5,2,0) which has 108528 elements. To find the statistics for each choice of forbidden set, I then started with the smallest lists first and worked down towards the largest lists, but each time I found a feasible set (a,b,c,d), I then skipped all smaller choices of (a,b,c,d), and conversely when I found that (a,b,c,d) was infeasible I skipped all larger choices of (a,b,c,d). Also, I initially computed the maximal values of a,b,c,d compatible with the forbidden set and excluded any (a,b,c,d) that were not less than or equal to these maximal values.

After creating the above lookup table, I computed for each of the forbidden sets, what exactly the Pareto optimal sets were; it turns out that each forbidden set can have at most 26 Pareto optimal statistics, which I numbered from 1 to 499 (there are 499 possible statistics for 3D Moser sets). I then stored these lists in a [math]\displaystyle{ 144 \times 2^{14} \times 26 }[/math] integer array (119MB, compressible to 9MB). The code for this is here.