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 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, 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 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.