Difference between revisions of "4D Moser brute force search"

From Polymath Wiki
Jump to: navigation, search
(New page: 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 set...)
 
Line 3: Line 3:
 
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.
 
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, 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 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, 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 397 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]].
 
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 397 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]].
 +
 +
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.

Revision as of 20:31, 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]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, 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 397 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.

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.