4D Moser brute force search: Difference between revisions
No edit summary |
No edit summary |
||
| Line 5: | Line 5: | ||
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. | 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 | 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). | With these reductions, the number of pairs to check drops to 62 billion (or more precisely, 62009590818). | ||
Revision as of 14:29, 11 June 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).
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 "c" point, such as 2211. Then A must omit either 2111 or 2311; without loss of generality we may assume that it omits 2111; similarly we may assume it omits 1211. Then we can add 1111, 1311, 3111 to A, a contradiction. Thus we may assume that A contains no "c" points. But then we can add 1131, 1311, 3111 to A, contradiction.
