View source for 4D Moser brute force search

The brute force search program requires first building a preliminary lookup table, and then a refined lookup table, to determine the Pareto-optimal statistics for all forbidden Level 2 sets.  Details of the lookup table construction are [[Lookup table|here]].

The basic idea is to run over pairs of Level 1 slices and Level 3 slices, which are 3D Moser sets.  For each such pair, compute the forbidden Level 2 set, then use the lookup table to find the optimal statistics for that pair, add that to a global table of feasible (a,b,c,d,e) statistics for 4D Moser sets, and iterate.  However, the total number of such pairs is <math>3813884 \times 3813884 \sim 1.4 \times 10^{13}</math>, which is computationally infeasible.

However, one can use symmetries to cut this number down. Look at the "a" corners of the Level 1 and Level 3 sets; these are two 8-bit strings (which we call the "a-signatures" of the Level1 and Level3 sets), so there are <math>2^{16}</math> possible choices for these.  Actually we can eliminate those choices for which a=1 and a=2, because if (0,b,c,d,e) is a feasible statistic then (1,b,c,d,e) and (2,b,c,d,e) is feasible also (just pick a "b", "c", "d", or "e" point which is not in the set, and then pick a pair of "a" points with that midpoint).  In fact (3,b,c,d,e) is also feasible, see Lemma below.  

For the remaining configurations, one exploits the symmetry group of <math>[3]^4</math>, which has order <math>4! \times 2^4 = 384</math>.  There are 391 remaining equivalence classes; for each equivalence class, we pick a representative which minimises the number of Level1 x Level3 pairs.  A table of these representatives can be found [[Optimal a-set pairs|here]].  A table of how many Moser sets there are for each a-signature can be found [[3D Moser statistics|here]].

With these reductions, the number of pairs to check drops to 62 billion (or more precisely, 62009590818).

The code to scan the pairs is [[scanning code|here]].  When compiled (say, as scan.exe), the format is

  scan x y

which will scan the signature-pair classes from x to y, where <math>0 \leq x \leq y \leq 390</math>, and output the relevant feasible statistics to stdout and to an output file.  If instead one types

  scan x y count

then this will indicate what percentage of the scan range is covered by x to y.

In the case x=372 and y=390 (which only takes about a minute to run), here is the [[stdout output]] and [[file output]] (for testing purposes).   The full file output can be [http://abel.math.umu.se/~klasm/Data/HJ/PARETO-DATA-NEW.tar.gz found here].


'''Lemma'''  Suppose that (0,b,c,d,e) is a feasible statistic for a 4D Moser set.  Then (3,b,c,d,e) is also feasible.

'''Proof'''  Let A be a 4D Moser set with statistics (0,b,c,d,e).  It suffices to show that we can add three "a" points to A and still have a Moser set, i.e. one can find three "a" points whose three midpoints are omitted by A.  We assume for contradiction that this is not possible.

Suppose first that A contains a "d" point, such as 2221.  Then A must omit either 2211 or 2231; without loss of generality we may assume that it omits 2211. Similarly we may assume it omits 2121 and 1221.  Then we can add 1131, 1311, 3111 to A, a contradiction.  Thus we may assume that A contains no "d" points.  

Now suppose that A omits a "c" point, such as 2211.  Then one can add 3333, 3111, 1311 to A, a contradiction.  Thus we may assume that A contains all "c" points, which in particular implies that A omits the "e" point 2222.

Since A contains all the "c" points, it must omit a "b" point, such as 2111.  But then 3111, 1111, 3333 can be added to the set, a contradiction.

== Pareto Maxima and Extremal Points ==
This routine was run on a Linux cluster, taking around two hours.  The output files were collated, there were 390 Pareto maxima:

     3    16    24     0     0
     4    14    19     2     0
     4    15    24     0     0
     4    16     8     4     1
     4    16    14     4     0
     4    16    23     0     0
     4    17    21     0     0
     4    18    19     0     0
     5    12    12     4     1
     5    12    13     6     0
     5    12    15     5     0
     5    12    19     2     0
     5    13    10     4     1
     5    13    14     5     0
     5    13    21     1     0
     5    15     9     4     1
     5    15    12     3     1
     5    15    13     5     0
     5    15    18     3     0
     5    15    20     1     0
     5    15    22     0     0
     5    16     7     4     1
     5    16    10     3     1
     5    16    11     5     0
     5    16    12     2     1
     5    16    16     3     0
     5    16    19     1     0
     5    16    21     0     0
     5    17    12     4     0
     5    17    14     3     0
     5    17    16     2     0
     5    17    18     1     0
     5    17    20     0     0
     5    18    13     3     0
     5    18    14     2     0
     5    20     8     4     0
     5    20    10     3     0
     5    20    13     2     0
     5    20    14     1     0
     5    20    18     0     0
     5    21    10     2     0
     5    21    15     0     0
     5    22    13     0     0
     6     8    12     8     0
     6    10    11     4     1
     6    11    12     7     0
     6    12    10     7     0
     6    12    13     5     0
     6    12    18     4     0
     6    13    16     4     0
     6    14     9     4     1
     6    14     9     7     0
     6    14    12     6     0
     6    14    16     3     0
     6    14    19     1     0
     6    14    21     0     0
     6    15     7     4     1
     6    15    10     3     1
     6    15    10     6     0
     6    15    11     2     1
     6    15    12     5     0
     6    15    15     4     0
     6    15    20     0     0
     6    16     7     3     1
     6    16     8     6     0
     6    16     9     2     1
     6    16    10     5     0
     6    16    12     1     1
     6    16    13     4     0
     6    16    14     3     0
     6    16    18     2     0
     6    16    19     0     0
     6    17     9     5     0
     6    17    10     4     0
     6    17    13     3     0
     6    17    15     2     0
     6    17    17     1     0
     6    17    18     0     0
     6    18    13     2     0
     6    18    16     1     0
     6    18    17     0     0
     6    19     9     4     0
     6    19    12     3     0
     6    19    15     1     0
     6    20     7     4     0
     6    20     9     3     0
     6    20    12     2     0
     6    20    13     1     0
     6    20    15     0     0
     6    21     8     3     0
     6    21     9     2     0
     6    21    12     1     0
     6    21    14     0     0
     6    22     7     3     0
     6    22     8     2     0
     6    22    10     1     0
     6    23     9     1     0
     6    24     7     2     0
     6    24     8     1     0
     6    24    12     0     0
     6    25     9     0     0
     6    26     7     0     0
     7     8     6     8     0
     7    11     9     4     1
     7    11    12     6     0
     7    12     8     4     1
     7    12     8     6     0
     7    12    12     3     1
     7    12    12     5     0
     7    12    13     4     0
     7    12    15     3     0
     7    12    17     2     0
     7    13     7     4     1
     7    13    10     3     1
     7    13    11     5     0
     7    13    12     2     1
     7    13    12     4     0
     7    13    14     3     0
     7    13    16     2     0
     7    14     6     4     1
     7    14     6     7     0
     7    14     9     5     0
     7    14    10     2     1
     7    14    12     1     1
     7    14    17     1     0
     7    14    19     0     0
     7    15     7     5     0
     7    15     8     3     1
     7    15     9     2     1
     7    15    11     1     1
     7    15    11     4     0
     7    15    13     3     0
     7    15    16     1     0
     7    16     6     3     1
     7    16     6     6     0
     7    16     8     2     1
     7    16    10     1     1
     7    16    10     4     0
     7    16    12     0     1
     7    16    12     3     0
     7    16    15     2     0
     7    16    17     0     0
     7    17     6     5     0
     7    17     7     4     0
     7    17    11     3     0
     7    17    13     2     0
     7    17    14     1     0
     7    17    16     0     0
     7    18    10     3     0
     7    18    13     1     0
     7    18    15     0     0
     7    19     9     3     0
     7    20     6     4     0
     7    20    11     2     0
     7    20    12     1     0
     7    20    14     0     0
     7    21     8     2     0
     7    21    10     1     0
     7    21    12     0     0
     7    22     9     1     0
     7    22    11     0     0
     7    23     6     3     0
     7    23     7     1     0
     7    23    10     0     0
     7    24     6     2     0
     7    24     9     0     0
     7    25     6     1     0
     7    25     8     0     0
     7    26     3     1     0
     7    28     6     0     0
     7    29     3     0     0
     7    30     1     0     0
     8     8     0     8     0
     8     8     9     7     0
     8     8    12     6     0
     8     9     9     4     1
     8     9    10     6     0
     8     9    12     3     1
     8     9    12     5     0
     8     9    13     4     0
     8     9    15     3     0
     8    10     7     4     1
     8    10    10     3     1
     8    10    10     5     0
     8    10    12     2     1
     8    10    12     4     0
     8    10    13     3     0
     8    10    15     2     0
     8    11     6     4     1
     8    11     9     6     0
     8    11    10     2     1
     8    11    11     4     0
     8    12     7     6     0
     8    12     9     3     1
     8    12     9     5     0
     8    12    10     4     0
     8    12    12     1     1
     8    12    14     2     0
     8    12    16     1     0
     8    12    18     0     0
     8    13     7     3     1
     8    13     7     5     0
     8    13     9     2     1
     8    13    12     0     1
     8    13    12     3     0
     8    14     0     7     0
     8    14     6     6     0
     8    14     7     2     1
     8    14     8     1     1
     8    14     9     4     0
     8    14    11     0     1
     8    14    11     3     0
     8    14    13     2     0
     8    14    15     1     0
     8    14    17     0     0
     8    15     6     3     1
     8    15     6     5     0
     8    15     7     1     1
     8    16     0     6     0
     8    16     4     3     1
     8    16     4     5     0
     8    16     6     2     1
     8    16     8     4     0
     8    16     9     0     1
     8    16    10     3     0
     8    16    12     2     0
     8    16    14     1     0
     8    16    16     0     0
     8    17     0     5     0
     8    17     3     4     0
     8    17     8     3     0
     8    17    10     2     0
     8    17    12     1     0
     8    17    14     0     0
     8    18     9     2     0
     8    18    11     1     0
     8    18    12     0     0
     8    19     6     3     0
     8    19     8     2     0
     8    20     0     4     0
     8    20     4     3     0
     8    20     7     2     0
     8    20     9     1     0
     8    20    11     0     0
     8    21     4     2     0
     8    21     7     1     0
     8    22     3     2     0
     8    22     6     1     0
     8    22     9     0     0
     8    23     0     3     0
     8    23     4     1     0
     8    24     0     2     0
     8    24     3     1     0
     8    24     8     0     0
     8    25     1     1     0
     8    25     6     0     0
     8    26     0     1     0
     8    26     4     0     0
     8    28     3     0     0
     8    32     0     0     0
     9     8    10     4     0
     9     9     9     4     0
     9     9    12     3     0
     9    10     8     4     0
     9    10    10     3     0
     9    10    12     2     0
     9    10    13     1     0
     9    10    15     0     0
     9    11    11     2     0
     9    12     7     4     0
     9    12     9     3     0
     9    12    12     1     0
     9    12    14     0     0
     9    13     7     3     0
     9    13    10     2     0
     9    14     9     2     0
     9    14    11     1     0
     9    14    13     0     0
     9    15     6     3     0
     9    16     0     4     0
     9    16     4     3     0
     9    16     8     2     0
     9    16    10     1     0
     9    16    12     0     0
     9    17     3     3     0
     9    17     6     2     0
     9    17     8     1     0
     9    17    10     0     0
     9    18     2     3     0
     9    18     4     2     0
     9    18     7     1     0
     9    18     9     0     0
     9    19     0     3     0
     9    19     3     2     0
     9    19     6     1     0
     9    20     1     2     0
     9    20     5     1     0
     9    20     8     0     0
     9    21     4     1     0
     9    21     6     0     0
     9    22     1     1     0
     9    22     5     0     0
     9    24     4     0     0
     9    25     2     0     0
     9    28     0     0     0
    10     8     6     4     0
    10     8     8     3     0
    10     9     7     3     0
    10     9    10     2     0
    10     9    11     1     0
    10     9    13     0     0
    10    10     5     4     0
    10    10     9     2     0
    10    10    12     0     0
    10    11     6     3     0
    10    12     4     4     0
    10    12     5     3     0
    10    12     7     2     0
    10    12    10     1     0
    10    12    11     0     0
    10    13     6     2     0
    10    13     8     1     0
    10    13    10     0     0
    10    14     3     3     0
    10    14     5     2     0
    10    14     9     0     0
    10    15     2     3     0
    10    15     7     1     0
    10    16     4     2     0
    10    16     6     1     0
    10    16     8     0     0
    10    17     4     1     0
    10    17     6     0     0
    10    18     2     1     0
    10    18     5     0     0
    10    20     4     0     0
    10    21     2     0     0
    10    22     1     0     0
    10    24     0     0     0
    11     4     6     4     0
    11     6     5     4     0
    11     7     6     3     0
    11     8     4     4     0
    11     8     5     3     0
    11     9     6     2     0
    11     9     8     1     0
    11     9    10     0     0
    11    10     3     3     0
    11    10     5     2     0
    11    10     9     0     0
    11    11     2     3     0
    11    11     7     1     0
    11    12     4     2     0
    11    12     6     1     0
    11    12     8     0     0
    11    13     4     1     0
    11    13     6     0     0
    11    14     2     1     0
    11    14     5     0     0
    11    16     4     0     0
    11    17     2     0     0
    11    18     1     0     0
    11    20     0     0     0
    12     4     3     3     0
    12     6     2     3     0
    12     6     5     2     0
    12     6     7     1     0
    12     6     9     0     0
    12     8     4     2     0
    12     8     6     1     0
    12     8     8     0     0
    12     9     4     1     0
    12     9     6     0     0
    12    10     2     1     0
    12    10     5     0     0
    12    12     4     0     0
    12    13     2     0     0
    12    14     1     0     0
    12    16     0     0     0
    13     6     5     0     0
    13     8     4     0     0
    13     9     2     0     0
    13    10     1     0     0
    13    12     0     0     0
    14     4     3     0     0
    14     5     2     0     0
    14     6     1     0     0
    14     8     0     0     0
    15     4     0     0     0
    16     0     0     0     0

Using [http://www.qhull.org/ qhull], 58 extremals were found:

     3     16     24      0      0 
     4     14     19      2      0 
     4     15     24      0      0 
     4     16      8      4      1 
     4     16     14      4      0 
     4     18     19      0      0 
     5     12     12      4      1 
     5     12     19      2      0 
     5     13     21      1      0 
     5     15      9      4      1 
     5     15     12      3      1 
     5     15     18      3      0 
     5     16      7      4      1 
     5     16     10      3      1 
     5     16     12      2      1 
     5     20      8      4      0 
     5     20     18      0      0 
     5     21     10      2      0 
     6      8     12      8      0 
     6     10     11      4      1 
     6     12     18      4      0 
     6     14      9      4      1 
     6     14      9      7      0 
     6     14     12      6      0 
     6     14     21      0      0 
     6     15      7      4      1 
     6     16     18      2      0 
     7     12     12      3      1 
     7     14      6      4      1 
     7     14      6      7      0 
     7     16     12      0      1 
     7     30      1      0      0 
     8      8      0      8      0 
     8      8      9      7      0 
     8      8     12      6      0 
     8      9      9      4      1 
     8      9     12      3      1 
     8      9     15      3      0 
     8     10      7      4      1 
     8     10     12      2      1 
     8     11      6      4      1 
     8     11     10      2      1 
     8     12     12      1      1 
     8     12     18      0      0 
     8     13     12      0      1 
     8     14      0      7      0 
     8     14      6      6      0 
     8     14      8      1      1 
     8     15      6      3      1 
     8     15      7      1      1 
     8     16      4      3      1 
     8     16      6      2      1 
     8     16      9      0      1 
     8     16     16      0      0 
     8     26      0      1      0 
     8     32      0      0      0 
    11      8      4      4      0 
    16      0      0      0      0

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