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, e.g. [math]\displaystyle{ 124 \leq c'_5 \leq 127 }[/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).

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,19,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]
• (3,16,23,0,0) [22272 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.

n=5

I think that c_5′ must be 128 or less. 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.

In fact, I can now rule out 128-point sets as follows. 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.

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.

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

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.