4D Moser brute force search: Difference between revisions
→Pareto Maxima and Extremal Points: removed the weaker list of linear inequalities |
No edit summary |
||
| Line 19: | Line 19: | ||
then this will indicate what percentage of the scan range is covered by x to y. | 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). | 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]. | ||
Latest revision as of 21:12, 6 July 2009
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 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]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ [3]^4 }[/math], which has order [math]\displaystyle{ 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 here. A table of how many Moser sets there are for each a-signature can be found 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 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]\displaystyle{ 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 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 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
