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 (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 scanning code 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. If instead one types

 scan x y count

then this will indicate what percentage of the scan range is covered by x to y.

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.