Moser's cube problem

Define a Moser set to be a subset of [math]\displaystyle{ [3]^n }[/math] which does not contain any geometric line, and let [math]\displaystyle{ c'_n }[/math] denote the size of the largest Moser set in [math]\displaystyle{ [3]^n }[/math]. The first few values are (see OEIS A003142):

[math]\displaystyle{ c'_0 = 1; c'_1 = 2; c'_2 = 6; c'_3 = 16; c'_4 = 43; c'_5 = 124. }[/math]

Beyond this point, we only have some upper and lower bounds, in particular [math]\displaystyle{ 353 \leq c'_6 \leq 355 }[/math]; see this spreadsheet for the latest bounds.

The best known asymptotic lower bound for [math]\displaystyle{ c'_n }[/math] is

[math]\displaystyle{ c'_n \gg 3^n/\sqrt{n} }[/math],

formed by fixing the number of 2s to a single value near n/3. Compare this to the DHJ(2) or Sperner limit of [math]\displaystyle{ 2^n/\sqrt{n} }[/math]. Is it possible to do any better? Note that we have a significantly better bound for the DHJ(3) [math]\displaystyle{ c_n }[/math]:

[math]\displaystyle{ c_n \geq 3^{n-O(\sqrt{\log n})} }[/math].

A more precise lower bound is

[math]\displaystyle{ c'_n \geq \binom{n+1}{q} 2^{n-q} }[/math]

where q is the nearest integer to [math]\displaystyle{ n/3 }[/math], formed by taking all strings with q 2s, together with all strings with q-1 2s and an odd number of 1s. This for instance gives the lower bound [math]\displaystyle{ c'_5 \geq 120 }[/math], which compares with the upper bound [math]\displaystyle{ c'_5 \leq 3 c'_4 = 129 }[/math].

Using DHJ(3), we have the upper bound

[math]\displaystyle{ c'_n = o(3^n) }[/math],

but no effective decay rate is known. It would be good to have a combinatorial proof of this fact (which is weaker than DHJ(3), but implies Roth's theorem).

Notation

Given a Moser set A in [math]\displaystyle{ [3]^n }[/math], we let a be the number of points in A with no 2s, b be the number of points in A with one 2, c the number of points with two 2s, etc. We call (a,b,c,...) the statistics of A. Given a slice S of [math]\displaystyle{ [3]^n }[/math], we let a(S), b(S), etc. denote the statistics of that slice (dropping the fixed coordinates). Thus for instance if A = {11, 12, 22, 32}, then (a,b,c) = (1,2,1), and (a(1*),b(1*)) = (1,1).

We call a statistic (a,b,c,...) attainable if it is attained by a Moser set. We say that an attainable statistic is Pareto-optimal if it cannot be pointwise dominated by any other attainable statistic (a',b',c',...) (thus [math]\displaystyle{ a' \geq a }[/math], [math]\displaystyle{ b' \geq b }[/math], etc.) We say that it is extremal if it is not a convex combination of any other attainable statistic (this is a stronger property than Pareto-optimal). For the purposes of maximising linear scores of attainable statistics, it suffices to check extremal statistics.

We let [math]\displaystyle{ (\alpha_0,\alpha_1,\ldots) }[/math] be the normalized version of [math]\displaystyle{ (a,b,\ldots) }[/math], in which one divides the number of points of a certain type in the set by the total number of points in the set. Thus for instance [math]\displaystyle{ \alpha_0 = a/2^n, \alpha_1 = b/(n 2^{n-1}), \alpha_3 = c/(\binom{n}{2} 2^{n-2}) }[/math], etc., and the [math]\displaystyle{ \alpha_i }[/math] range between 0 and 1. Averaging arguments show that any linear inequality obeyed by the [math]\displaystyle{ \alpha_i }[/math] at one dimension is automatically inherited by higher dimensions, as are shifted versions of this inequality (in which [math]\displaystyle{ \alpha_i }[/math] is replaced by [math]\displaystyle{ \alpha_{i+1} }[/math].

The idea in 'c-statistics' is to identify 1s and 3s but leave the 2s intact. Let’s use x to denote letters that are either 1 or 3, then the 81 points in [math]\displaystyle{ [3]^4 }[/math] get split up into 16 groups: 2222 (1 point), 222x, 22×2, 2×22, x222 (two points each), 22xx, 2×2x, x22x, 2xx2, x2×2, xx22 (four points each), 2xxx, x2xx, xx2x, xxx2 (eight points each), xxxx (sixteen points). Let c(w) denote the number of points inside a group w, e.g. c(xx22) is the number of points of the form xx22 inside the set, and is thus an integer from 0 to 4.

n=0

We trivially have [math]\displaystyle{ c'_0=1. }[/math]

n=1

We trivially have [math]\displaystyle{ c'_1=2. }[/math] The Pareto-optimal values of the statistics (a,b) are (1,1) and (2,0); these are also the extremals. We thus have the inequality [math]\displaystyle{ a+b \leq 2 }[/math], or in normalized notation

[math]\displaystyle{ 2\alpha_0 + \alpha_1 \leq 2 }[/math].

n=2

We have [math]\displaystyle{ c'_2 = 6 }[/math]; the upper bound follows since [math]\displaystyle{ c'_2 \leq 3 c'_1 }[/math], and the lower bound follows by deleting one of the two diagonals from [math]\displaystyle{ [3]^2 }[/math] (these are the only extremisers).

The extremiser has statistics (a,b,c) = (2,4,0), which are of course Pareto-optimal. If c=1 then we must have a, b at most 2 (look at the lines through 22). This is attainable (e.g. {11, 12, 22, 23, 31}, and so (2,2,1) is another Pareto-optimal statistic. If a=4, then b and c must be 0, so we get another Pareto-optimal statistic (4,0,0) (attainable by {11, 13, 31, 33} of course). If a=3, then c=0 and b is at most 2, giving another Pareto-optimal statistic (3,2,0); but this is a convex combination of (4,0,0) and (2,4,0) and is thus not extremal. Thus the complete set of extremal statistics are

(4,0,0), (2,4,0), (2,2,1).

The sharp linear inequalities obeyed by a,b,c (other than the trivial ones [math]\displaystyle{ a,b,c \geq 0 }[/math]) are then

• [math]\displaystyle{ 2a+b+2c \leq 8 }[/math]
• [math]\displaystyle{ b+2c \leq 4 }[/math]
• [math]\displaystyle{ a+2c \leq 4 }[/math]
• [math]\displaystyle{ c \leq 1 }[/math].

In normalized notation, we have

• [math]\displaystyle{ 4\alpha_0 + 2\alpha_1 + \alpha_2 \leq 4 }[/math]
• [math]\displaystyle{ 2\alpha_1 + \alpha_2 \leq 2 }[/math]
• [math]\displaystyle{ 2\alpha_0 + \alpha_2 \leq 2 }[/math]
• [math]\displaystyle{ \alpha_2 \leq 1 }[/math].

The Pareto optimizers for c-statistics are (c(22),c(2x),c(x2),c(xx)) = (1112),(0222),(0004), which are covered by these linear inequalities:

• [math]\displaystyle{ c(22)+c(2x)+c(xx) \le 4 }[/math],
• [math]\displaystyle{ c(22)+c(x2)+c(xx) \le 4 }[/math].

n=3

We have [math]\displaystyle{ c'_3 = 16 }[/math]. The lower bound can be seen for instance by taking all the strings with one 2, and half the strings with no 2 (e.g. the strings with an odd number of 1s). The upper bound can be deduced from the corresponding upper and lower bounds for [math]\displaystyle{ c_3 = 18 }[/math]; the 17-point and 18-point line-free sets each contain a geometric line.

If a Moser set in [math]\displaystyle{ [3]^3 }[/math] contains 222, then it can have at most 14 points, since the remaining 26 points in the cube split into 13 antipodal pairs, and at most one of each pair can lie in the set. By exhausting over the [math]\displaystyle{ 2^{13} = 8192 }[/math] possibilities, it can be shown that it is impossible for a 14-point set to exist; any Moser set containing 222 must in fact omit at least one antipodal pair completely and thus have only 13 points. (A human proof of this fact can be found here.)

The Pareto-optimal statistics are

(3,6,3,1),(4,4,3,1),(4,6,2,1),(2,6,6,0),(3,6,5,0),(4,4,5,0),(3,7,4,0),(4,6,4,0), (3,9,3,0),(4,7,3,0),(5,4,3,0),(4,9,2,0),(5,6,2,0),(6,3,2,0),(3,10,1,0),(5,7,1,0), (6,4,1,0),(4,12,0,0),(5,9,0,0),(6,6,0,0),(7,3,0,0),(8,0,0,0).

These were found from a search of the [math]\displaystyle{ 2^{27} }[/math] subsets of the cube. A spreadsheet containing these statistics can be found here. Here are more 3D Moser statistics. A lookup table for 3D Moser sets was constructed.

The extremal statistics are

(3,6,3,1),(4,4,3,1),(4,6,2,1),(2,6,6,0),(4,4,5,0),(4,6,4,0),(4,12,0,0),(8,0,0,0)

The sharp linear bounds are :

• [math]\displaystyle{ 2a+b+2c+4d \leq 22 }[/math]
• [math]\displaystyle{ 3a+2b+3c+6d \leq 36 }[/math]
• [math]\displaystyle{ 7a+2b+4c+8d \leq 56 }[/math]
• [math]\displaystyle{ 6a+2b+3c+6d \leq 48 }[/math]
• [math]\displaystyle{ b+c+3d \leq 12 }[/math]
• [math]\displaystyle{ a+2c+4d \leq 14 }[/math]
• [math]\displaystyle{ 5a+4c+8d \leq 40 }[/math]
• [math]\displaystyle{ a+4d \leq 8 }[/math]
• [math]\displaystyle{ b+6d \leq 12 }[/math]
• [math]\displaystyle{ c+3d \leq 6 }[/math]
• [math]\displaystyle{ d \leq 1 }[/math]

In normalized notation,

• [math]\displaystyle{ 8\alpha_0+ 6\alpha_1 + 6\alpha_2 + 2\alpha_3 \leq 11 }[/math]
• [math]\displaystyle{ 4\alpha_0+4\alpha_1+3\alpha_2+\alpha_3 \leq 6 }[/math]
• [math]\displaystyle{ 7\alpha_0+3\alpha_1+3\alpha_2+\alpha_3 \leq 7 }[/math]
• [math]\displaystyle{ 8\alpha_0+4\alpha_1+3\alpha_2+\alpha_3 \leq 8 }[/math]
• [math]\displaystyle{ 4\alpha_1+2\alpha_2+\alpha_3 \leq 4 }[/math]
• [math]\displaystyle{ 4\alpha_0+6\alpha_2+2\alpha_3 \leq 7 }[/math]
• [math]\displaystyle{ 5\alpha_0+3\alpha_2+\alpha_3 \leq 5 }[/math]
• [math]\displaystyle{ 2\alpha_0+\alpha_3 \leq 2 }[/math]
• [math]\displaystyle{ 2\alpha_1+\alpha_3 \leq 2 }[/math]
• [math]\displaystyle{ 2\alpha_2+\alpha_3 \leq 2 }[/math]
• [math]\displaystyle{ \alpha_3 \leq 1 }[/math]

The c-statistics can also be found from an exhaustive search of Moser sets. The resulting Pareto sets and linear inequalities can be found on Sheet 8 of this spreadsheet

The following are Pareto optimal (3,6,3,1),(4,4,3,1),(4,6,2,1),(2,6,6,0),(3,6,5,0),(4,4,5,0),(3,7,4,0),(4,6,4,0), (3,9,3,0),(4,7,3,0),(5,4,3,0),(4,9,2,0),(5,6,2,0),(6,3,2,0),(3,10,1,0),(5,7,1,0), (6,4,1,0),(4,12,0,0),(5,9,0,0),(6,6,0,0),(7,3,0,0),(8,0,0,0). Here is a human proof of the 3D Pareto-optimal Moser statistics.

n=4

A computer search has obtained all extremisers to [math]\displaystyle{ c'_4=43 }[/math]. The 42-point solutions can be found here.

Proof that [math]\displaystyle{ c'_4 \leq 43 }[/math]: When e=1 (i.e. the 4D set contains 2222) then we have at most 41 points (in fact at most 39) by counting antipodal points, so assume e=0.

Define the score of a 3D slice to be a/4+b/3+c/2+d. Observe from double counting that the size of a 4D set is the sum of the scores of its eight side slices.

But by looking at the extremals we see that the largest score is 44/8, attained at only one point, namely when (a,b,c,d) = (2,6,6,0). So the only way one can have a 44-point set is if all side slices are (2,6,6,0), or equivalently if the whole set has statistics (a,b,c,d,e) = (4,16,24,0,0). But then we have all the points with two 2s, which means that the four "a" points cannot be separated by Hamming distance 2. We conclude that we must have an antipodal pair among the "a" points with an odd number of 1s, and an antipodal pair among the "a" points with an even number of 1s. By the symmetries of the cube, we may take the a-set to then be 1111, 3333, 1113, 3331. But then the "b" set must exclude both 1112 and 3332, and so can have at most three points in the eight-point set xyz2 (with x,y,z=1,3) rather than four (to get four points one must alternate in a checkerboard pattern). Adding this to the at most four points of the form xy2z, x2yz, 2xyz we see that b is at most 15, a contradiction. [math]\displaystyle{ \Box }[/math]

Given a subset of [math]\displaystyle{ [3]^4 }[/math], let a be the number of points with no 2s, b be the number of points with 1 2, and so forth. The quintuple (a,b,c,d,e) thus lies between (0,0,0,0,0) and (16,32,24,8,1).

The 43-point solutions have distributions (a,b,c,d,e) as follows:

• (5,20,18,0,0) [16 solutions]
• (4,16,23,0,0) [768 solutions]
• (3,16,24,0,0) [512 solutions]
• (4,15,24,0,0) [256 solutions]

The 42-point solutions are distributed as follows:

• (6,24,12,0,0) [8 solutions]
• (5,20,17,0,0) [576 solutions]
• (5,19,18,0,0) [384 solutions]
• (6,16,18,2,0) [192 solutions]
• (4,20,18,0,0) [272 solutions]
• (5,17,20,0,0) [192 solutions]
• (5,16,21,0,0) [3584 solutions]
• (4,17,21,0,0) [768 solutions]
• (4,16,22,0,0) [26880 solutions]
• (5,15,22,0,0) [1536 solutions]
• (4,15,23,0,0) [22272 solutions]
• (3,16,23,0,0) [15744 solutions]
• (4,14,24,0,0) [4224 solutions]
• (3,15,24,0,0) [8704 solutions]
• (2,16,24,0,0) [896 solutions]

Note how c is usually quite large, and d quite low.

One of the (6,24,12,0,0) solutions is [math]\displaystyle{ \Gamma_{220}+\Gamma_{202}+\Gamma_{022}+\Gamma_{112}+\Gamma_{211} }[/math] (i.e. the set of points containing exactly two 1s, and/or exactly two 3s). The other seven are reflections of this set.

There are 2,765,200 41-point solutions, listed here. The statistics for such points can be found here. Noteworthy features of the statistics:

• d is at most 3 (and, except for 256 exceptional solutions of the shape (5,15,18,3,0), have d at most 2; here are the d=2 solutions and d=1 solutions)
• c is at least 6 (and, except for 16 exceptional solutions of the shape (7,28,6,0,0), have c at least 11).

Statistics for the 41-point, 42-point, and 43-point solutions can be found here. Here is the full list of Pareto-optimals.

If a Moser set in [math]\displaystyle{ [3]^4 }[/math] contains 2222, then by the n=3 theory, any middle slice (i.e. 2***, *2**, **2*, or ***2) is missing at least one antipodal pair. But each antipodal pair belongs to at most three middle slices, thus two of the 40 antipodal pairs must be completely missing. As a consequence, any Moser set containing 2222 can have at most 39 points. (A more refined analysis can be found at found here.)

We have the following inequalities connecting a,b,c,d,e:

• [math]\displaystyle{ 4a+b \leq 64 }[/math]: There are 32 lines connecting two "a" points with a "b" point; each "a" point belongs to four of these lines, and each "b" point belongs to one. But each such line can have at most two points in the set, and the claim follows.
• This can be refined to [math]\displaystyle{ 4a+b+\frac{2}{3} c \leq 64 }[/math]: There are 24 planes connecting four "a" points, four "b" points, and one "c" point; each "a" point belongs to six of these, each "b" point belongs to three, and each "c" point belongs to one. For each of these planes, we have [math]\displaystyle{ 2a + b + 2c \leq 8 }[/math] from the n=2 theory, and the claim follows.
• [math]\displaystyle{ 6a+2c \leq 96 }[/math]: There are 96 lines connecting two "a" points with a "c" point; each "a" point belongs to six of these lines, and each "c" point belongs to two. But each such line can have at most two points in the set, and the claim follows.
• [math]\displaystyle{ 3b+2c \leq 96 }[/math]: There are 48 lines connecting two "b" points to a "c" point; each "b" point belongs to three of these points, and each "c" point belongs to two. But each such line can have at most two points in the set, and the claim follows.

The inequalities for n=3 imply inequalities for n=4. Indeed, there are eight side slices of [math]\displaystyle{ [3]^4 }[/math]; each "a" point belongs to four of these, each "b" point belongs to three, each "c" point belongs to two, and each "d" point belongs to one. Thus, any inequality of the form

[math]\displaystyle{ \alpha a + \beta b + \gamma c + \delta d \leq M }[/math]

in three dimensions implies the inequality

[math]\displaystyle{ 4 \alpha a + 3 \beta b + 2 \gamma c + \delta d \leq 8M }[/math]

in four dimensions. Thus we have

• [math]\displaystyle{ 8a+3b+4c+4d \leq 176 }[/math]
• [math]\displaystyle{ 2a+b+c+d \leq 48 }[/math]
• [math]\displaystyle{ 14a+3b+4c+4d \leq 244 }[/math]
• [math]\displaystyle{ 4a+b+c+d \leq 64 }[/math]
• [math]\displaystyle{ 3b+2c+3d \leq 96 }[/math]
• [math]\displaystyle{ a+c+d \leq 28 }[/math]
• [math]\displaystyle{ 5a+2c+2d \leq 80 }[/math]
• [math]\displaystyle{ a+d \leq 16 }[/math]
• [math]\displaystyle{ b+2d \leq 32 }[/math]
• [math]\displaystyle{ 2c+3d \leq 48 }[/math]

Cubes also sit diagonally in the 4-dimensional cube. They may have coordinates xxyz, where xx runs over (11,22,33) or (13,22,31), while y and z run over (1,2,3). These cubes have a different distribution of 2s than the ordinary slices: (a,b,c,d,e) = (8,8,6,4,1) instead of (8,12,6,1,0) for the side slices and (0,8,12,6,1) for the middle slices. So a different set of inequalities arise. Apply the same procedure as described above for n=3: (Run through the [math]\displaystyle{ 2^{27} }[/math] subsets of the cube; identify those without combinatorial lines; calculate their statistics in the new xxyz arrangement; retain the Pareto-optimal statistics; retain the extremal statistics; find what inequalities they satisfy.) The inequalities that arise are

• [math]\displaystyle{ 2a+b+2c+2d+4e \le 24 }[/math] and
• [math]\displaystyle{ 4a+b+2c+2d+4e \le 32 }[/math]

within the 3D cube, which when averaged becomes

• [math]\displaystyle{ 4a+b+2c+4d+16e \le 96 }[/math] and
• [math]\displaystyle{ 8a+b+2c+4d+16e \le 128 }[/math]

for the 4D cube. A spreadsheet containing these statistics can be found here on sheet 2. Other sheets of this spreadsheet contain results for a 3D cube sitting diagonally in a 5D, 6D or 7D cube. Notice the similarity of the equations that arise for the xxxyz, xxyyz and xxxxyz diagonals. Also notice the (a,b,c,...) statistics for the xxxxyyz diagonals have the same Pareto sets and linear inequalities as the cube's c-statistics.

The c-statistics for the 3D cube are bounded by a set of 20 inequalities. By considering the fourteen ways a 3D cube sits in the 4D cube, the result is a set of 239 inequalities for the 4D cube's c-statistics. However, all 239 inequalities are satisfied by a 44-point solution given by c(xxxx) = c(2xxx) = c(22xx) = 4, and permutations.

If a Moser set for n=4 has 4 or more points with three 2’s it has less than 41 points.

See 4D Moser sets with d at least 4 have at most 40 points.

If a Moser set for n=4 has 1 or more points with three 2’s it has less than 43 points.

See 4D Moser sets with d at least 2 have at most 42 points.

If a Moser set for n=4 has 3 or more points with three 2’s it has less than 42 points.

See 4D Moser sets with d at least 3 has at most 41 points.

Brute-force calculations for [math]\displaystyle{ [3]{}^4 }[/math]

An attempt was made to find extremal statistics for the four-dimensional case by brute force. Since a simple routine would check 2^81 possibilities, which is infeasible, shortcuts would be needed.

The outline of a suggested routine is as follows: There are just over 3.8 million line-free subsets of [3]^3. Since the cube has 3!2^3 = 48 symmetries, they fall into 83158 equivalence classes. To consider all possibilities, it is enough to do the following:

• Let the 1*** slice be a representative from one of the 83158 classes.
• Let the 3*** slice be one of the 3.8 million subsets.
• Identify which points in 2*** would not complete a vertical or sloping line from the 1*** slice to the 3*** slice.
• Go to a lookup table, and find the Pareto-optimal statistics of all line-free subsets of 2*** with the restriction from the previous step. This lookup table would need 2^27 rows, or 2^27/48 if one made use of the cube's symmetries.
• Deduce a set of possible statistics for the combined **** cube. Update the list of [3]^4 Pareto statistics
• Loop through the 83158 1*** slices and 3.8 million 3*** slices.

A large part of this calculation is to build the lookup table. Here is a Matlab script to carry it out.

Here is a slightly different implementation of the 4D Moser brute force search. It obtained this list of Pareto-optimals and this list of extremals.

Proof that [math]\displaystyle{ c'_5 }[/math] = 124

Let (A,B,C,D,E,F) be the statistics of a five-dimensional Moser set, thus (A,B,C,D,E,F) varies between (0,0,0,0,0,0) and (32,80,80,40,10,1).

There are several Moser sets with the statistics (4,40,80,0,0,0), which thus have 124 points. Indeed, one can take

• all points with two 2s;
• all points with one 2 and an even number of 1s; and
• 11111, 11333, 33311, 33331. Any two of these four points differ in three places, except for one pair of points that differ in one place.

For the rest of this section, we assume that the Moser set [math]\displaystyle{ {\mathcal A} }[/math] is a 125-point Moser set. We will prove that [math]\displaystyle{ {\mathcal A} }[/math] cannot exist.

Lemma 1: F=0.

Proof If F is non-zero, then the Moser set contains 22222, then each of the 121 antipodal pairs can have at most one point in the set, leading to only 122 points. [math]\displaystyle{ \Box }[/math]

Lemma 2: Every middle slice of [math]\displaystyle{ {\mathcal A} }[/math] has at most 41 points.

Proof Without loss of generality we may consider the 2**** slice. There are two cases, depending on the value of c(2****).

Suppose first that c is at least 17; thus there are at least 17 points of the form 222xy, 22x2y, 22xy2, 2x2y2, 2xy22, or 2x22y, where the x, y denote 1 or 3. This gives 34 "xy" wildcards in all in four coordinate slots; by the pigeonhole principle one of the slots sees at least 9 of the wildcards. By symmetry, we may assume that the second coordinate slot sees at least 9 of these wildcards, thus there are at least 9 points of the form 2x22y, 2x2y2, 2xy22. The x=1, x=3 cases can absorb at most six of these, thus each of these cases must absorb at least three points, with at least one absorbing at least five. Let's say that it's the x=3 case that absorbs 5; thus [math]\displaystyle{ d(*1***) \geq 3 }[/math] and [math]\displaystyle{ d(*3***) \geq 5 }[/math]. From the n=4 theory this means that the *1*** slice has at most 41 points, and the *3*** slice has at most 40. Meanwhile, the middle slice has at most 43, leading to 41+41+42=124 points in all.

Now suppose c is less than 17; then by the n=4 theory the middle slice is one of the eight (6,24,12,0,0) sets. Without loss of generality we may take it to be [math]\displaystyle{ \Gamma_{220}+\Gamma_{202}+\Gamma_{022}+\Gamma_{112}+\Gamma_{211} }[/math]; in particular, the middle slice contains the points 21122 21212 21221 23322 23232 23223. In particular, the *1*** and *3*** slices have a "d" value of at least three, and so have at most 41 points. If the *2*** slice has at most 42 points, then we are at 41+42+41=124 points as needed, but if we have 43 or more, then we are back in the first case (as [math]\displaystyle{ c(*2***) \geq 17 }[/math]) after permuting the indices. [math]\displaystyle{ \Box }[/math]

Since 125=41+41+43, we thus have

Corollary 1: Every side slice of [math]\displaystyle{ {\mathcal A} }[/math] has at least 41 points. If one side slice does have 41 points, then the other has 43.

Combining this with the n=4 statistics, we conclude

Corollary 2: Every side slice of [math]\displaystyle{ {\mathcal A} }[/math] has e=0, and [math]\displaystyle{ d \leq 3 }[/math]. Given two opposite side slices, e.g. 1**** and 3****, we have [math]\displaystyle{ d(1****)+d(3****) \leq 4 }[/math].

Corollary 3: E=0.

Corollary 4: Any middle slice has a "c" value of at most 8.

Proof Let's work with the 2**** slice. By Corollary 2, there are at most four contributions to c(2****) of the form 21*** or 23***, and similarly for the other three positions. Double counting then gives the claim. [math]\displaystyle{ \Box }[/math]

Lemma 3: [math]\displaystyle{ 2B+C \leq 160 }[/math].

Proof: There are 160 lines connecting one "C" point to two "B" points (e.g. 11112, 11122, 11132); each "C" point lies in two of these, and each "B" point lies on four. A Moser set can have at most two points out of each of these lines. Double counting then gives the claim. [math]\displaystyle{ \Box }[/math]

Lemma 4 Given m A-points with [math]\displaystyle{ m \geq 5 }[/math], there exists at least m-4 pairs (a,b) of such A-points with Hamming distance exactly two (i.e. b differs from a in exactly two places).

Proof It suffices to check this for m=5, since the case of larger m then follows by locating a pair, removing a point that contributes to that pair, and using the induction hypothesis. Given 5 A-points, we may assume by the pigeonhole principle and symmetry that at least three of them have an odd number of 1s. Suppose 11111 is one of the points, and that no pair has Hamming distance 2. All points with two 3s are excluded, so the only points allowed with an odd number of 1s are those with four 3s. But all those points differ from each other in two positions, so at most one of them is allowed. [math]\displaystyle{ \Box }[/math]

Corollary 5 [math]\displaystyle{ C \leq 79 }[/math].

Proof: Suppose for contradiction that C=80, then D=0 and [math]\displaystyle{ B \leq 40 }[/math]. From Lemma 4 we also see that A cannot be 5 or more, leading to the contradiction. [math]\displaystyle{ \Box }[/math]

Define the score of a Moser set in [math]\displaystyle{ [3]^4 }[/math] to be the quantity [math]\displaystyle{ a + 5b/4 + 5c/3 + 5d/2 + 5e }[/math]. Double-counting (and Lemma 2) gives

Lemma 5 The total score of all the ten side-slices of [math]\displaystyle{ {\mathcal A} }[/math] is equal to [math]\displaystyle{ 5|{\mathcal A}| = 5 \times 125 }[/math]. In particular, there exists a pair of opposite side-slices whose scores add up to at least 125.

By Lemma 5 and symmetry, we may assume that the 1**** and 3**** slices have score adding up to at least 125. By Lemma 2, the 2**** slice has at most 41 points, which imply that the 1**** and 3**** have 41, 42, or 43 points. From the n=4 statistics we know that all 41-point, 42-point, 43-point slices have score less than 62, with the following exceptions:

1. (2,16,24,0,0) [42 points, score: 62]
2. (4,16,23,0,0) [43 points, score: 62 1/3]
3. (4,15,24,0,0) [43 points, score: 62 3/4]
4. (3,16,24,0,0) [43 points, score: 63]

Thus the 1**** and 3**** slices must come from the above list. Furthermore, if one of the slices is of type 1, then the other must be of type 4, and if one slice is of type 2, then the other must be of type 3 or 4.

Lemma 6 There exists one cut in which the side slices have total score strictly greater than 125 (i.e. they thus involve only Type 2, Type 3, and Type 4 slices, with at least one side slice not equal to Type 2, and the cut here is of the form 43+39+43).

Proof If not, then all cuts have side slices exactly equal to 125, which by the above table implies that one is Type 1 and one is Type 4, in particular all side slices have c=24. But this forces C=80, contradicting Corollary 5. [math]\displaystyle{ \Box }[/math]

Adding up the corners we conclude

Corollary 6 [math]\displaystyle{ 6 \leq A \leq 8 }[/math].

Lemma 7 [math]\displaystyle{ D=0 }[/math].

Proof Firstly, from Lemma 6 we have a cut in which the two side slices are omitting at most one C-point between them (and have no D-point), which forces the middle slice to have at most one D-point; thus D is at most 1.

Now suppose instead that D=1 (e.g. if 11222 was in the set); then there would be two choices of coordinates in which one of the side slices would have d=1 (e.g. 1**** and *1****). But the n=4 statistics show that such slices have a score of at most 59 7/12, so that the total score from those two coordinates is at most 63 + 59 7/12 = 122 7/12. On the other hand, the other three slices have a net score of at most 63+63 = 126. This averages out to at most 124.633... < 125, a contradiction. [math]\displaystyle{ \Box }[/math]

Corollary 7 Every middle slice has at most 40 points.

Proof From Lemma 7 we see that the middle slice must have c=0, but from the n=4 statistics this is not possible for any slice of size 41 or higher (alternatively, one can use the inequalities [math]\displaystyle{ 4a+b \leq 64 }[/math] and [math]\displaystyle{ b \leq 32 }[/math]). [math]\displaystyle{ \Box }[/math]

Each middle slice now has 39 or 40 points, with c=d=e=0, and so from the inequalities [math]\displaystyle{ 4a+b \leq 64 }[/math], [math]\displaystyle{ b \leq 32 }[/math] must have statistics (8,32,0,0,0),(7,32,0,0,0), or (8,31,0,0,0). In particular the "a" index of the middle slices is at most 8. Summing over all middle slices we conclude

Lemma 9 B is at most 40.

Lemma 10 C is equal to 78 or 79.

Proof By Corollary 5, it suffices to show that [math]\displaystyle{ C \geq 78 }[/math].

As 125=43+39+43, we see that every center slice must have at least 39 points. By Lemma 2 and Lemma 7 the center slice has c=d=e=0, thus the center slice has a+b >= 39. On the other hand, from the n=4 theory we have 4a+b <= 64, which forces b >= 31.

By double counting, we see that 2C is equal to the sum of the b's of all the five center slices. Thus C >= 5*31/2 = 77.5 and the claim follows. [math]\displaystyle{ \Box }[/math]

From Lemmas 9 and 10 we see that [math]\displaystyle{ B+C \leq 119 }[/math], and thus [math]\displaystyle{ A \geq 6 }[/math]. Also, if [math]\displaystyle{ A \geq 7 }[/math], then by Lemma 4 we have at least three pairs of A points with Hamming distance 2. At most two of these pairs eliminate the same C point, so we would have C=78 in that case.

Putting all the above facts together, we see that (A,B,C,D,E,F) must be one of the following triples:

• (6,40,79,0,0,0)
• (7,40,78,0,0,0)
• (8,39,78,0,0,0)

All three cases can be eliminated, giving [math]\displaystyle{ c'_5=124 }[/math].

Elimination of (6,40,79,0,0,0)

Look at the 6 A points. From Lemma 4 we have at least two pairs (a,b), (c,d) of A-points that have Hamming separation 2.

Now look at the midpoints of these two pairs; these midpoints are C-points cannot lie in the set. But we have exactly one C-point missing from the set, thus the midpoints must be the same. By symmetry, we may thus assume that the two pairs are (11111,11133) and (11113,11131). Thus 11111,11133, 11113, 11131 are in the set, and so every C-point other than 11122 is in the set. On the other hand, the B-points 11121, 11123, 11112, 11132 lie outside the set.

At most one of 11312, 11332 lie in the set (since 11322 lies in the set). Suppose that 11312 lies outside the set, then we have a pair (xy1z2, xy3z2) with x,y,z = 1,3 that is totally omitted from the set, namely (11112,11312). On the other hand, every other pair of this form can have at most one point in the set, thus there are at most seven points in the set of the form (xyzw2) with x,y,z,w = 1,3. Similarly there are at most 8 points of the form xyz2w, or of xy2zw, x2yzw, 2xyzw, leading to at most 39 B-points in all, contradiction.

Elimination of (7,40,78,0,0,0)

By Lemma 4, we have at least three pairs of A-points of distance two apart that lie in the set. The midpoints of these pairs are C-points that do not lie in the set; but there are only two such C-points, thus two pairs must have the same midpoint, so we may assume as before that 111xy lies in the set for x,y=1,3, which implies that 1112* and 111*2 lie outside the set.

Now consider the 160 lines between 2 B points and one C point (cf. Lemma 3). The sum of all the points in each such line (counting multiplicity) is 4B+2C = 316. On the other hand, every one of the 160 lines can have at most two points, and two of these lines (namely 1112*, 111*2) have no points. Thus all the other lines must have exactly two points.

We know that the C-point 11122 is missing from the set; there is one other missing C-point. Since 1112x, 111x2 lie outside the set, we conclude from the previous paragraph that 1132x, 113x2 and 1312x, 131x2 lie in the set. Taking midpoints we conclude that 11322 and 13122 lie outside the set. But this is now three C-points missing (together with 11122), a contradiction.

Elimination of (8,39,78,0,0,0)

By Lemma 4 we have at least four pairs of A-points of distance two apart that lie in the set. The midpoints of these pairs are C-points that do not lie in the set; but there are only two such C-points, thus two pairs (a,b), (c,d) must have the same midpoint p, and the other two pairs (a',b'), (c',d') must also have the same midpoint p'. (Note that every C-point is the midpoint of at most two such pairs.)

Now consider the 160 lines between 2 B points and one C point (cf. Lemma 3). The sum of all the points in each such line (counting multiplicity) is 4B+2C = 312. Every one of the 160 lines can have at most two points, and four of these (those in the plane of (a,b,c,d) or of (a',b',c',d') have no points. Thus all other lines must have exactly two points.

Without loss of generality we have (a,b)=(11111,11133), (c,d) = (11113,11131), thus p = 11122. By permuting the first three indices, we may assume that p' is not of the form x2y2z, x2yz2, xy22z, xy2z2. Then 1112x lies outside the set and 1122x lies in the set, so by the above paragraph 1132x lies in the set; similarly for 113x2, 1312x, 131x2. This implies that 13122, 11322 lie outside the set, but this (together with 11122) shows that at least three C-points are missing, a contradiction.

n=6

We have [math]\displaystyle{ c'_6 \geq 353 }[/math]. This can be seen for instance by taking the union of the Gamma-cells (6,0,0),(5,0,1),(3,3,0), (3,2,1),(3,1,2),(2,2,2),(1,3,2),(0,3,3),(2,0,4),(0,2,4),(0,1,5).

Lemma 8 A 6D Moser set with g=1 has at most 351 points.

Proof Define the 22**** score of a 4D set to be 15 a + 5 b + 5 c/2 + 3d/2 + e. Observe that the cardinality of a 6D set is the average of its 30 22**** scores of its 22****-type slices, plus a+b.

If g=1, then a <= 32 and b <= 96 and so a+b <= 128. Meanwhile, the largest 22**** score for a set with e=1 is 223.5, by the the Pareto optimal list. The claim follows. (Actually, the Maple calculations give the better upper bound of 337.)

Lemma 9 A 6D Moser set with f>0 has at most 353 points.

Proof Currently only via Maple calculations.

Define the 11**** score of a 4D Moser set to be 4a+6b+10c+20d+60e. The cardinality of a 6D set with f=g=0 is the average of its 60 scores. From the Pareto optimal list, the largest scores are

• 356 - attained by (6,12,18,4,0)
• 352 - attained by (5,12,18,4,0), (5,12,12,4,1), (6,8,12,8,0)
• 350 - attained by (6,11,18,4,0), (5,15,12,3,1), (6,11,12,7,0), (5,15,18,3,0)
• 348 - attained by (6,14,12,6,0), (3,16,24,0,0), (4,12,18,4,0), (4,12,12,4,1), (5, 8, 12, 8, 0)
• all other statistics are at most 346.

This establishes [math]\displaystyle{ c'_6 \leq 356 }[/math].

With a bit more effort I can get c'_6 \leq 355. Consider the 112*** slices (and symmetries thereof). Double counting shows that these slices must have statistics (3,9,3,0) on the average. But all 3D slices must obey the inequalities b+c+3d \leq 12 and 3a+2b+3c+6d \leq 36 (see https://spreadsheets.google.com/ccc?key=p5T0SktZY9DuKZ2DyzO9EOg&hl=en ), and so all 112*** slices must obey these inequalities with equality; also, d must be zero. We conclude that the 112*** slices have statistics (3,9,3,0), (2,6,6,0), or (4,12,0,0). The latter two possibilities are inconsistent with the 11**** slices having statistics (6,12,18,4,0) (since all but at most two of the “d” points in the 11**** slice lie in 112***). So all 112*** slices have statistics (3,9,3,0). Since 11**** has statistics (6,12,18,4,0), this implies that exactly one of 111222 and 113222 lie in the set. More generally, we see that given any two adjacent “d” points in [3]^6, exactly one of them lies in the set; thus the d points of the form ***222 consist either of those strings with an even number of 1s, or those with an odd number of 1s.

Let’s say it’s the former, thus the set contains 111222, 133222, and permutations of the first three coordinates, but omits 113222, 333222 and permutations of the first three coordinates. Meanwhile, we see that the (24,72,180,80,0,0,0) set saturates the inequality 4c+3d \leq 960, which is only possible if every line connecting two “c” points to a “d” point meets exactly two elements in the set. Since the “d” points 113222, 333222 are omitted, we conclude that the “c” points 113122, 113322, 333122, 333322 must lie in the set, and similarly for permutations of the first three and last three coordinates. But this gives at least 15 of the 16 "c" points ending in 22; by symmetry this leads to 225 c-points in all, which is far too many.

The (6,12,18,4,0) sets have been completely classified. The basic example is the set consisting of 1111, 1113, 3333, 1332, 1322, 1222, 3322 and permutations (i.e. (4,0,0), (3,0,1), (0,0,4), (1,1,2), (1,2,1), (1,3,0), (0,2,2) in Gamma-notation). This set has d-points 1222, 2122, 2212, 2221. More generally, given any [math]\displaystyle{ x,y,z,w \in \{1,3\} }[/math], there is a unique (6,12,18,4,0) set with d-points x222, 2y22, 22z2, 222w, and these are the only 16 possibilities.

Connection with Fujimura's Problem

Recall the Gamma cells, where [math]\displaystyle{ \Gamma_{a,b,c} }[/math] is the set of points whose coordinates include a 1s, b 2s and c 3s. When the Moser problem is specialised to unions of cells, it becomes a Fujimura-type problem but in which one has to forbid isosceles triangles [math]\displaystyle{ (a+r,b,c+s), (a,b+r+s,c), (a+s,b,c+r) }[/math] rather than equilateral triangles, and each point [math]\displaystyle{ (a,b,c) }[/math] is weighted by the cell cardinality [math]\displaystyle{ \frac{(a+b+c)!}{a!b!c!} }[/math]. (In particular, one has to exclude vertical line segments [math]\displaystyle{ (a+r,b,c+r),(a,b+2r,c) }[/math], thus each value of [math]\displaystyle{ c-a }[/math] can have at most one cell.

An integer program was run to find solutions of the Moser problem which were sets of Gamma cells. The resulting lower bounds it found, for various dimensions n, are 2, 6, 16, 43, 122, 353, 1017, 2902, 8622, 24786, 71766, 212423, 614875.

General n

General solution for [math]\displaystyle{ c'_N }[/math]. For any q, the union of the following sets is a Moser set. The size of this Moser set is maximized when q is near N/3, in which case it is [math]\displaystyle{ O(3^n/\sqrt{n}) }[/math]. Most of the points are in the layers with q 2s and q-1 2s.

• q 2s, all points from A(N-q,1)
• q-1 2s, points from A(N-q+1,2)
• q-2 2s, points from A(N-q+2,3)
• etc.

where A(m,d) is a subset of [math]\displaystyle{ [1,3]^m }[/math] for which any two points differ from each other in at least d places.

Mathworld’s entry on error-correcting codes suggests it might be NP-complete to find the maximum size of A(m,d) in general. However, the size of A(m,d) can be bounded by sphere-packing arguments. For example, points in A(m,3) are surrounded by non-intersecting spheres of Hamming radius 1, and points in A(m,5) are surrounded by non-intersecting spheres of Hamming radius 2.

• [math]\displaystyle{ |A(m,1)| = 2^m }[/math] because it includes all points in [math]\displaystyle{ [1,3]^m }[/math]
• [math]\displaystyle{ |A(m,2)| = 2^{m-1} }[/math] because it can include all points in [math]\displaystyle{ [1,3]^m }[/math] with an odd number of ones.
• [math]\displaystyle{ |A(m,3)| \le 2^m/(m+1) }[/math] because the size of a Hamming sphere is m+1.

The integer programming routine from Maple 12 was used to obtain upper bounds for [math]\displaystyle{ c'_6 }[/math] and [math]\displaystyle{ c'_7 }[/math]. A large number of linear inequalities, such as those described above in sections (n=3) and (n=4), were combined. The details are in Maple calculations. The results were that [math]\displaystyle{ c'_6 \le 356 }[/math] and [math]\displaystyle{ c'_7 \le 1041 }[/math].

A genetic algorithm has provided the following examples:

• [math]\displaystyle{ c'_6 \geq 353 }[/math] (26 examples; here is one)
• [math]\displaystyle{ c'_7 \geq 988 }[/math] Here is the example

The first of these 353-point genetic results turned out to be built entirely from Gamma sets (Recall Gamma(a,b,c) is those points with a 1s, b 2s and c 3s.) The Gamma sets were (6,0,0),(5,0,1),(3,3,0), (3,2,1),(3,1,2),(2,2,2),(1,3,2),(0,3,3),(2,0,4),(0,2,4),(0,1,5). This led to a search for solutions built from complete Gamma sets.

This Moser problem, when specialised to unions of Gamma cells, becomes a Fujimura-type problem but in which one has to forbid isosceles triangles (a+r,b,c+s),(a,b+r+s,c),(a+s,b,c+r) rather than equilateral triangles (a+r,b,c),(a,b+r,c),(a,b,c+r), and each point (a,b,c) is weighted by the cell cardinality [math]\displaystyle{ \frac{N!}{a!b!c!} }[/math]. (In particular, one has to exclude vertical line segments (a+r,b,c+r),(a,b+2r,c),(a+r,b,c+r), thus each value of c-a can have at most one cell.) Results are given at this address, and show that [math]\displaystyle{ c'_7\geq 1017, c'_8 \geq 2902 }[/math] and so on.

For general N, the following collection of Gamma sets [math]\displaystyle{ \Gamma_{a,b,c} }[/math] is roughly one third better than the A sets described above when n is large:

• [math]\displaystyle{ \Gamma(a,q,N-a-q) }[/math] when [math]\displaystyle{ a\ne 2 (mod 3) }[/math]
• [math]\displaystyle{ \Gamma(a,q-1,N+1-a-q) }[/math] when [math]\displaystyle{ a\ne 1 (mod 3) }[/math]
• [math]\displaystyle{ \Gamma(a,q-2,N+2-a-q) }[/math] when [math]\displaystyle{ a = 0 (mod 3) }[/math]
• [math]\displaystyle{ \Gamma(a,q-3,N+3-a-q) }[/math] when [math]\displaystyle{ a = 2 (mod 3) }[/math]

Extra points may be found in the following way: Suppose one has an unused cell (a+r,b,c+r) which forms a degenerate isosceles triangle with another cell (a,b+2r,c) that is being fully used, but is otherwise not forming any triangles with existing cells. Then there is a little bit of room to add a few more points: namely, one can add any subset of to the set without creating lines as long as no two points in that subset are a Hamming distance of exactly 2r apart. For instance one can certainly add a single point to the Gamma example without difficulty.

For N=5, one can start with the 122-point solution (0 0 5), (1 1 3), (0 2 3 ), (1 2 2 ), (2 1 2 ), (2 2 1 ),(3 2 0 ), (3 1 1), (5 0 0 ). Add a single point from each of (1,0,4) and (4,0,1), to give a maximal 124-point solution.

For N=10, twelve points from Gamma(5,0,5) can be added to the 24786-point solution, to give a 24798-point solution. No two of these twelve points are Hamming distance 4 from each other, so no triangles are made with Gamma(3,4,3) which is part of the 24786-point solution.

Larger sides (k>3)

The following set gives a lower bound for Moser’s cube [math]\displaystyle{ [4]^n }[/math] (values 1,2,3,4): Pick all points where q entries are 2 or 3; and also pick those where q-1 entries are 2 or 3 and an odd number of entries are 1. This is maximized when q is near n/2, giving a lower bound of

[math]\displaystyle{ \binom{n}{n/2} 2^n + \binom{n}{n/2-1} 2^{n-1} }[/math]

The following set improves this bound to [math]\displaystyle{ (2+o(1))\binom{n}{n/2} 2^n }[/math]. It includes four half-layers.

Pick all points with a 1s, b 2s, c 3s, d 4s, for which

• a+d = q or q-1, a and b have same parity
• a+d = q-2 or q-3, a and b have opposite parity

which is comparable to [math]\displaystyle{ 4^n/\sqrt{n} }[/math] by Stirling's formula.

For k=5 (values 1,2,3,4,5) If A, B, C, D, and E denote the numbers of 1-s, 2-s, 3-s, 4-s and 5-s then the first three points of a geometric line form a 3-term arithmetic progression in A+E+2(B+D)+3C. So, for k=5 we have a similar lower bound for the Moser’s problem as for DHJ k=3, i.e. [math]\displaystyle{ 5^{n - O(\sqrt{\log n})} }[/math].

The k=6 version of Moser implies DHJ(3). Indeed, any k=3 combinatorial line-free set can be "doubled up" into a k=6 geometric line-free set of the same density by pulling back the set from the map [math]\displaystyle{ \phi: [6]^n \to [3]^n }[/math] that maps 1, 2, 3, 4, 5, 6 to 1, 2, 3, 3, 2, 1 respectively; note that this map sends k=6 geometric lines to k=3 combinatorial lines.