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. }[/math]

Beyond this point, we only have some upper and lower bounds, in particular [math]\displaystyle{ 124 \leq c'_5 \leq 125 }[/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. Is it possible to do any better? Note that we have a significantly better bound for [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 4 c'_4 = 124 }[/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).

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

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.

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 only non-trivial sharp linear inequality obeyed by a,b,c is thus

[math]\displaystyle{ 2a+b+2c \leq 8 }[/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).

Question: What are the extremal statistics here? What are all the inequalities obeyed by a,b,c,d?

n=4

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

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

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, one can check by hand that [math]\displaystyle{ 2a + b + 2c \leq 8 }[/math] (treating the c=1 and c=0 cases separately), 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.
• More inequalities needed!

Statistics for these solutions can be found here.

n=5

A lower bound [math]\displaystyle{ c'_5 \geq 124 }[/math] can be established by taking

• all points with two 1s;
• all points with one 1 and an even number of 0s; and
• Four points with no 1s and two or three 0s. Any two of these four points differ in three places, except for one pair of points that differ in one place.

This suggests further solutions for c'_N

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

where A(m,d) is a subset of [0,2]^m 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 size of A(m,d) in general.

• [math]\displaystyle{ |A(m,1)| = 2^m }[/math] because it includes all points in [math]\displaystyle{ [0,2]^m }[/math]
• [math]\displaystyle{ |A(m,2)| = 2^{m-1} }[/math] because it can include all points in [math]\displaystyle{ [0,2]^m }[/math] with an odd number of 0s

Trivially, [math]\displaystyle{ c'_5 \leq 4c'_4 = 129 }[/math].

Proof of [math]\displaystyle{ c'_5 \leq 128 }[/math]: There are only 24 points possible with two 2’s so if there are three in a row the first one must have at least 18 of these points the second cube must also have at least 18 so there must be at least 12 in both final the third must have at least 18 so there must be at least 6 in all three which results in a line. So the maximum value for c_5′ is 128 or less. [math]\displaystyle{ \Box }[/math]

Proof of [math]\displaystyle{ c'_5 \leq 127 }[/math] If one had a 128-point set, then the set must slice as 43+43+42 (or a permutation thereof) in every direction. But all 43-point slices have d=0 and all 42-point slices have d <= 2. Thus, there are at most two points amongst the sixteen points x222y, x22y2, x2y22, xy222 with x,y = 1,3 that lie in the set. Averaging this over all orientations we see that at most one eighth of all points with exactly 3 2s lie in the set. Thus, by the pigeonhole principle and a double counting argument, there exists a middle slice of the set with this property, i.e. a slice with c <= 24/8 = 3, but we know from the 43-point and 42-point distribution data that this is impossible. [math]\displaystyle{ \Box }[/math]

Lemma 1: Any Moser set with at least 42 points in the middle slice [math]\displaystyle{ 2**** }[/math] has at most 124 points.

Proof There are two cases, depending on the "c" value of the middle slice.

Suppose first that c is at least 17; thus there are at least 17 points of the form 222xy, 22xy2, 2xy22, or 2x22y, where the x, y denote 1 or 3. This gives 36 "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 16; 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]

Lemma 2: Any Moser set containing an element with at least four 2s has at most 124 points.

Proof If 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. So we may assume that 22222 is not in the set. Without loss of generality we may now assume that 12222 is in the set.

By the n=4 theory, the 1**** slice now has at most 39 points. In order to make at least 125=39+43+43 points, the 2**** and 3**** slice must now have exactly 43 points. But then the claim follows from Lemma 1.[math]\displaystyle{ \Box }[/math]

Proof of [math]\displaystyle{ c'_5 \leq 126 }[/math]: By Lemma 1, a 127-point Moser set must slice as 43+41+43 in every orientation. From the n=4 theory this means that all the side slices have d=0, which implies that all middle slices have c=0 (since a c-point for a middle slice is necessarily a d-point for two side slices in two other orientations. We already know the middle slice has d=e=0. From the inequality [math]\displaystyle{ 4a+b \leq 64 }[/math] and the trivial inequality [math]\displaystyle{ b \leq 32 }[/math] gives at most 40 points for the middle slice, a contradiction. [math]\displaystyle{ \Box }[/math]

Let (A,B,C,D,E,F) be the number of points in a Moser set in [math]\displaystyle{ [3]^5 }[/math] with no 2s, one 2, etc. up to all five 2s; thus (A,B,C,D,E,F) ranges between (0,0,0,0,0,0) and (32,80,80,40,10,1). Lemma 2 says that a Moser set with more than 124 points must have E=F=1. We also have some other inequalities:

• [math]\displaystyle{ 2B+C \leq 160 }[/math]. 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.
• More inequalities needed!

Lemma 3 A Moser set which contains all 80 points that have exactly two 2s, has at most 124 points.

Proof: By considering lines connecting two points with one 2 to one point with two 2s, we see from the inequality [math]\displaystyle{ 2B+C \leq 160 }[/math] that at most half of the 80 points with one 2 lie in the set. If the set has all the points with exactly two 2s, then there are no points with three or more 2s. It thus suffices to show that there are at most four points with no 2s. In fact two of these have an even number of 1s, and two have an odd number.

Suppose 11111 is one of the points. 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]

Proof of [math]\displaystyle{ c'_5 \leq 125 }[/math]: By Lemma 1, a 126-point Moser set must slice as 43+41+42 or 43+40+43 in every direction. Suppose first that there is a 43+41+42 slice, thus for instance the 2**** slice has 41 points. By the n=4 theory, c(2****) is at least 6. This gives at least six points of the form 222xy, 22xy2, 2xy22, 2x22y, where the x, y denote 1 or 3. This gives 12 "xy" wildcards in all in four coordinate slots; by the pigeonhole principle, one of these slots sees at least 3 of these wildcards. Let's say that it is the second coordinate slot, thus d(*1***)+d(*3***) is at least 3. But the *1*** and *3*** slices have sizes (43, 43), (43, 42), or (42, 43), and thus have a net d of at most 2 by the n=4 theory, a contradiction.

We may thus assume that every way of slicing the 126-point set slices as 43+40+43. Then all side slices have d=0, thus all middle slices have c=0. From the inequalities [math]\displaystyle{ 4a+b \leq 64 }[/math], [math]\displaystyle{ b \leq 32 }[/math] we conclude that all middle slices have statistics (8, 32, 0, 0, 0). In particular, every point with two 2s lies in the set, and the claim now follows from Lemma 3. [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 gives

Lemma 4 Let A be a Moser set in [math]\displaystyle{ [3]^5 }[/math] that does not contain the center point 22222. Then the total score of all the ten side-slices of A is equal to [math]\displaystyle{ 5|A| }[/math]. In particular, there exists a pair of opposite side-slices whose scores add up to at least |A|.

Suppose now we have a 125-point Moser set. By Lemma 2 and Lemma 4 and symmetry, we may assume that the 1**** and 3**** slices have score adding up to 125. By Lemma 1, 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 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 5 If a Moser set has 125 points then the number C of points with

exactly two 2’s is either 78 or 79.

Proof By Lemma 3, C must be less than 80.

If it is 77 or less then the three or more missing points must have 6 or more values equal to 2 divided among 5 coordinates one coordinate must have two such values. Then in that coordinate b must be equal to 30 or less. Now if this center slice is 38 or less then we have 38 + 43 + 43 is less than 125 and we are done. So it must be 39 or more. We have 4a + b is less than or equal to 64 from the section of the wiki on Moser sets devoted to n = 4. so we have a + b is 39 or more and 4a + b is 64 or less we can subtract and get 3a is less than 25 so a is less than 9 but that combined with b is thirty or less gives a total set size of 38 or less which results in a contradiction as noted above.

So the number of points with exactly 2 2’s in a Moser set with n=5 With 125 or more points is greater than 77 and not equal to 80. So it must be 78 or 79. [math]\displaystyle{ \Box }[/math]

Lemma 6 If a Moser set has 124 points or less and its center slice is of side 41

It must have 11 points or less with two twos in its center slice.

Proof Suppose it has 12 or more then all 12 points have values not equal to 2 divided among 4 coordinates there are 24 such values So one coordinate must have six of these values.

Now if four of these are are equal to one or four equal to three we have one side slice equal to 40 (since a 41 point slice can have at most d equal to three) and combined with the fact we have shown the center slice must be 41 or lower and the third slice must be 43 or less we have the total points sum to 124 or less and we are done so they must be divided 3 3 and then each side slice must be 41 or less and that combined with the center slice being 41 or less we 124 points or less and we are done. [math]\displaystyle{ \Box }[/math]

Lemma 7 If the center slice of a Moser set is size 41 or more the set must have

124 or less points.

Proof: Because we have shown c of the center slice must be less than 12 we are left only with case where there are c = 6, note that these points have three 2’s overall in the configuration . We will first show that there must be three or more points with three twos outside the center slice, Now since c = 6 the 6 points have 12 coordinates with value 1 or 3 divided among 4 coordinates one coordinate must have at least three of these coordinates now if we slice at this coordinate we will three coordinates which will not be in the center slice then if there are less than three coordinates with three twos outs we will end up with c for the center slice being less than 6 and hence the center slice will have to have 40 points or less and the three points with two threes that moved outside the center will if they lie in one slice lower its value to 41 hence lower the total value to or less if they are split among two slices those slices will have value 42 or less and combined with 40 or less of the center will give 124 or less.

So we have must 9 points then we must have one cut with side slices in one of the four categories 1, 2, 3, 4 discussed earlier.

This implies d=0 for the side slices of this cut we have all 9 points with three twos in the center slice then we have 18 values not equal to 2 divided among 4 coordinates one must have 5 values we cut along that coordinate and if one of the side slices has 4 or more points then that slice will have 40 or less points and that combined with the 41 points of the center slice and the fact the remaining slice must have 43 or less points gives 124 and we are done. So we must have 3 such points in one outside slice and two in another. That gives at most 41 points in the center slice at most 42 points in one side slice and at most 41 points in the other slice which gives less than 124 points and we are done. [math]\displaystyle{ \Box }[/math]

Lemma 8: If a Moser set contains a point with three twos it has 124

points or less.

Proof We have there is cut which gives one slice with 43 points on each outside slice thus the point with three twos must lie in the center slice of this cut we slice at a value where this point does not equal two then in the new set of slices the center slice must have 40 points or less and the point with three twos must lie on one of the outside slices if it has value 41 the we must have a total of 124 points and we are done if it has value 42 it must have two points with three twos and one coordinate at which these points have values 3 and 1 we slice at this value and get that the center slice must have 40 points or less and since the two side slices have at least one point with three two’s each they must have 42 points or less and the total is 124 or less and we are done. [math]\displaystyle{ \Box }[/math]

Variants

A lower bound for Moser’s cube k=4 (values 0,1,2,3) is: q entries are 1 or 2; or q-1 entries are 1 or 2 and an odd number of entries are 0. This gives a lower bound of

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

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

For k=5 (values 0,1,2,3,4) If A, B, C, D, and E denote the numbers of 0-s, 1-s, 2-s, 3-s, and 4-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.