4D Moser brute force search

From Polymath Wiki
Revision as of 20:15, 11 June 2009 by Teorth (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, 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 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 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.