Moser's cube problem: Difference between revisions

From Polymath Wiki
Jump to navigationJump to search
← Older edit
No edit summary
m fix OEIS link
 
(42 intermediate revisions by 4 users not shown)
Line 1: Line 1:
Define a ''Moser set'' to be a subset of <math>[3]^n</math> which does not contain any [[geometric line]], and let <math>c'_n</math> denote the size of the largest Moser set in <math>[3]^n</math>.  The first few values are (see [http://www.research.att.com/~njas/sequences/A003142 OEIS A003142]):
Define a ''Moser set'' to be a subset of <math>[3]^n</math> which does not contain any [[geometric line]], and let <math>c'_n</math> denote the size of the largest Moser set in <math>[3]^n</math>.  The first few values are (see [http://oeis.org/A003142 OEIS A003142]):


: <math>c'_0 = 1; c'_1 = 2; c'_2 = 6; c'_3 = 16; c'_4 = 43; c'_5 = 124.</math>
: <math>c'_0 = 1; c'_1 = 2; c'_2 = 6; c'_3 = 16; c'_4 = 43; c'_5 = 124; c'_6 = 353.</math>


Beyond this point, we only have some upper and lower bounds, in particular <math>353 \leq c'_6 \leq 361</math>; see [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DsU-uZ1tK7VEg this spreadsheet] for the latest bounds.
Beyond this point, we only have some upper and lower bounds; see [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DsU-uZ1tK7VEg this spreadsheet] for the latest bounds.


The best known asymptotic lower bound for <math>c'_n</math> is
The best known asymptotic lower bound for <math>c'_n</math> is
Line 81: Line 81:


These were found from a search of the <math>2^{27}</math> subsets of the cube.
These were found from a search of the <math>2^{27}</math> subsets of the cube.
A spreadsheet containing these statistics can be [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DuKZ2DyzO9EOg&hl=en# found here].
A spreadsheet containing these statistics can be [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DuKZ2DyzO9EOg&hl=en# found here].  Here are more [[3D Moser statistics]].  A [[lookup table]] for 3D Moser sets was constructed.


The extremal statistics are
The extremal statistics are
Line 116: Line 116:
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 [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DuKZ2DyzO9EOg&hl=en# this spreadsheet]
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 [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DuKZ2DyzO9EOg&hl=en# 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).
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]].
 
We first compute the Pareto-minimal counterexamples (i.e. the (a,b,c,d) which are larger than these but end up in the list after removing one from any of a,b,c,d) and eliminate each of them. From the n=2 inequalities (and using the planes xy1, xy2, and xxx, averaged over symmetries) we have a number of linear constraints
 
a/4+c/6 \leq 2; a/4 + d \leq 2; b/6+c/6 \leq 2; b/6+d \leq 2; c/3+d \leq 2; a/2+b/6+c/6 \leq 4; b/3+c/3+d \leq 4
 
which eliminate many of these; these inequalities, by the way, together with the trivial inequality d \leq 1, are given as Y3 in the maple computations on the Wiki.
It seems that the Pareto-minimal counterexamples that are consistent with these inequalities are (4,5,3,1), (3,11,1,0), (4,10,1,0), (5,8,1,0), (6,5,1,0), (5,7,2,0), (6,4,2,0), (4,8,3,0), (5,5,3,0), (6,0,3,0), (3,8,4,0), (4,7,4,0), (5,0,4,0), (3,7,5,0), (4,5,5,0), (3,6,6,0), so one has to eliminate 16 possibilities.
   
The distribution (4,5,3,1) cannot occur. Assume that we have set with these statistics. Note  that no two points with two 2’s can have the same c-statistic. Without loss of generality we can assume that these points in the Moser set are (1,2,2), (2,1,2) and (2,2,1). Next we note that the points (1,1,1) and (1,1,3) cannot be in the set. If (1,1,1) it blocks (3,3,3), (1,3,3) and (3,1,3) and also (3,3,1). This leaves (1,1,3) and one of (1,3,1) and (1,1,3) and prevents four points with four twos being in the set giving a contradiction.
 
If (1,1,3) is in the set it blocks all points with no 2’s whose third coordinate is 1 except (1,1,1). However (1,1,1) is forbidden by the previous paragraph. The only way for there to be 4 points of type a is if all point of type a with a final coordinate equal to 3 are in the set. However this blocks all points of type b whose final coordinate is 3. The points (1,2,2) and (2,2,2) limit the the number of points of type b whose final coordinates are one and two to two each. This prevents 5 such points and we have another contradiction.
Now in order to have 4 points of type a we must have two among (1,1,1),(1,1,3),(1,3,3) and (3,3,3) but by the above we cannot have (1,1,1) or (1,1,3) so we must have (1,3,3) and (3,3,3). Now we must have one of (1,3,1) and (1,1,3) without loss of generality say (1,3,1) this will block all other points of type a except (1,3,3) recalling that (1,1,1) and (3,3,3) cannot be in the set so to have four points of type a we must have (1,3,3).
(1,3,1) and (1,3,3) block (1,3,2). (3,3,1) and (3,3,3) block  (3,3,2). (1,3,3) and (3,3,3) block (2,3,3). (1,3,1) and (3,3,1) block (2,3,1) Furthermore because of the formation of potential lines we can only have one of the following pairs: (1,1,2) and (1,3,2), (1,2,1) and (1,3,2), and (1,2,1) and (1,2,3) because of this and because we need 8 points of type b we must have both (3,2,1) and (3,2,3) to bring the total to 5 but this blocks both (1,2,1) and (1,2,3) and there is no way to get 5 points of type a. So this gives a contradiction and we are done.
 
The distribution (3,11,1,0) cannot occur as every point of type c lies on two lines whose other points are of type b with no points of type be lying on both lines. 11 points of type b implies the removal of one from the complete set of such points. Thus for every point of type c at most one line will be affected and the other will block the point of type c thus making it impossible.
 
The distribution (4,10,1,0) cannot occur because the two missing points of type b must lie on one face, the face that contains the element c, The face opposite it contains all its points of type b. Hence it at most two points of type a which must be on a diagonal. These points combined with the points of type b not on either of the two faces which must all be in the set since the missing points are on the original face block two points on a diagonal in the original face so the remaining possibilities for points on the original face must be on the other diagonal but c will limit the number of these to one. Thus the maximum of points of type a are one on the original face and two on the opposite face which gives a maximum of three but we must have four so this distribution cannot be realized.
 
The distribution (5,8,1,0) cannot be realized. The point of type c must be on a face. That face can contain at most two points of type a and two of type b to avoid lines with the point of type c which is the center point of the face. If the opposite face has all four points of type a then these will block all point of type b in that face the center point of the original face will block two more allowing a maximum of 6 which is less than 8 so the opposite face must have three points and the original face must have two.
 
Then there are only two points of type b on the original face  the opposite face must have three of type a these must block two points of type b so there must be only two points of type b on the opposite face. To get eight points of type b the remaining four points in the center slice between the face and its opposite must have all four of its points of type b. These points are at the corners of the center slice and together with the three points of type a  in the opposite face they block three of the slots for corner points for the original face, Thus the original face can only have one point of type a and together with the three of the opposite face we get a maximum of four points of type a and we are done.
 
The distribution (6,5,1,0) cannot be realized. The point of type c is the center point of a face which must have at most two points of type a so the opposite face must have four points of type a to give six. These four points block all points of type b in the opposite face. The presence of a center point in the original face blocks two points of type b so the original face has at most two points of type b. The remaining slots for points of type b are in the center at the corner positions of the center slice three of the must be filled and with the four points of the opposite slice they block three of the slots for points of type a in the original slice that leaves one open slot allowing a maximum of one point of type a and a total of at most 5 points of type a which is less than 6 so we get a contradiction and we are done.
 
A configuration of type (5,7,2,0) cannot be realized. First we see that two points of type c cannot have the same c-statistic. If they did we could slice the cube so there are two opposite faces with the center point filled. these forces would each have at most two points of type a for a maximum of 4 which is less than 5 which gives a contradiction. So we can assume without loss of generality the points of type c are (1,2,2) and (2,1,2).
 
Slice along the first coordinate then the square with first coordinate with value one has its center point and hence has at most 2 points each of type a and type b.
If the slice with first coordinate 3 has four points of type a then it can have no points of type b and the maximum number of points of type b are four in the square with first coordinate 2 and two in the square with first coordinate 1 for a total of 6 which is less than 7 which gives a contradiction. So the square with first coordinate three must have at most three points of type a, and the square with first coordinate one must have at most two of type a. So the only way 5 such points can be realized is if the the square with first coordinate 1 has two points of type a and the square with first coordinate three has three such points.
 
The three points of type a in the square with first coordinate three block two points of type b so only two points of type b can be in that square. Since the center spot is filled in the square with first coordinate one that square can have at most two points of type b. Thus for there to be 7 points of type b there must be three in the square with first coordinate 2. Because of the presence of the point with coordinates (2,1,2) only one of the points (2,1,3) and (2,1,1) can be in the set which means that both (2,3,3) and (2,3,1) must be in the set. The presence of these points means that only two of the points (1,3,1), (3,3,1), (1,3,3), and (3,3,3) can be in the set. To get five points of type a three of (1,1,1),(1,1,3),(3,1,1) and (3,1,3) must be in the set. But these points can be divided into two pairs (1,1,1) and (3,1,3), and (1,1,3) and (3,1,3) which form lines with (2,1,2) thus there can be at most two of these points and at most 4 points of type a but we need 5 such points so we are done.
 
The configuration of type (6,4,2,0) cannot be realized. Assume we have such a configuration. The two points of type c in the configuration cannot have the same c-statistic. If they did we could slice along a coordinate and get the two side squares to have their center points thus they could each have only two points of type a, limiting the points of type a to 4 which is less than 6 giving a contradiction. Without loss of generality we can assume the two points of type c are (1,2,2) and (2,1,2).
 
Slice on the first coordinate then the square of points with first coordinate equal to one has its center points and so can only have two points of type a. The square with first coordinate three must have all of its points of type a to make six.
The square with  first coordinate three must have no points of type b as its four coordinates of type a blocks them. The square with first coordinate one can have at most two of these points because it has its center point. That means that the square with first coordinate two must have two such points.
 
The square with third coordinate equal to three contains all of its points of type a from above. In particular it contains (3,1,1) and (3,1,3). These together with point (2,1,2) block points (1,1,1) and (1,1,3) int the square with first coordinate equal to one. Since that square contains two points of type a it must contain the remaining two, (1,3,1) and (1,3,3). These two together with (3,3,1) and (3,3,3) block (2,3,1) and (2,3,3) in the square with two as its first coordinate. But the only other possibilities for a point of type b in this square are (2,1,1) and (2,1,3) but (2,1,2) prevents both from being in the set. Thus this square can only have one point of type b, the square with one as its first coordinate has its center point and can only have one and as noted above the square with first coordinate equal to three has no such points. So the maximum number of points of type b in the set is 3 which is less than 4 and we are done.
 
A Moser configuration with n=3 cannot have statistics (4,8,3,0). First we show that no two points of type c can have the same c-statistics. If they do then we can slice on a a coordinate and get the two side slices that both have their center slice then each can only have two points of type b which means to have 8 such points the center slice must have all four of its points of type b and hence can have no points of type c, but since the two side slices only each have one there are less than three points of type c and we are done. Without loss of generality we than can take the three center points to be (1,2,2), (2,1,2) and (2,2,1). We slice along the first coordinate.
 
The square with its first coordinate equal to 3 cannot have four points. If it did it would have no points of type b and the other two slices would have to have all of their points of this type but the square with first coordinate equal to one has its center point equal to one has its center point so it can only have two and we get a contradiction. The square with its first coordinate equal to three cannot have three points if it did it would have at most two points of type b or a line would be formed. The square with its first coordinate equal to one would have at most two. So for there to be 8 such points there must four such points in the square with first coordinate equal to 2 but that would block all points of type c in the square and it has (2,1,2) and (2,2,1) by the above. So the square with its first coordinate equal to three must have at most two points of type a and since the square with first coordinate equal to one can have at most two due to the presence of its center point it must have two and the other side slice must have two.
 
Now the square with its first coordinate equal to three cannot contain the point (3,1,1) because along with the points (2,1,2) and (2,2,1) it would block (1,1,3) and (1,3,1) but this would limit the possible points of type a to those on a diagonal which due to the presence of the center square can only one point which would give a contradiction to the conclusion of the above paragraph. The square with its first coordinate equal to one cannot contain the point (1,1,1) because along with the points (2,1,2) and (2,2,1) it would block (3,1,3) and (3,3,1) this would force the two points of the square with first coordinate equal to three to have its points on the other diagonal but this then it would have to have both points on this diagonal and hence contain the point (3,1,1) which leads to a contradiction as noted previously.
 
The square with first coordinate equal to one must have two points and hence it must have a point on each diagonal as the center point prevents the presence of two. Since (1,1,1)is forbidden by the above it must have (1,3,3). If the square with first coordinate equal to three contained (3,3,3) then with (1,3,3) it would block the point (2,3,3) the points (2,1,2) and (2,2,1) would block an additional point of type b in the center slice and the center slice would have at most two points of type b, due to the presence of its center point the square with first coordinate equal to one would have at most two such points. So to get a total of 8 the square with first coordinate equal to three would have to have all four of its points of type b but together with the point (3,3,3) these would block (3,1,3) and (3,3,1).
Since (3,1,1) is not possible due to the above the square with first coordinate equal to three would have at most one point of type a which contradicts the fact it must have two proved above. So the point (3,3,3) cannot occur in this slice. Since we have already proved it cannot contain (3,1,1) and it must have two points of type a it must contain (3,1,3) and (3,3,1).
 
Now the square with first coordinate equal to one contains (1,1,1) by the above it cannot contain (1,3,3) and since it must have two points of type a it must include one of (1,3,1) or (1,1,3). Since by the above the other side slice must contain both of the points (3,3,1) and (3,1,3) one of the points (2,3,1) or (2,1,3) will be blocked. The points (2,1,2) and (2,2,1) would block an additional point of type b in the center slice and it will have at most two points of type b. The square with first coordinate equal to one will have at most two points of type b. So the square with first coordinate equal to three must contain all of its points of type b for there to be 8 such points. With (2,1,2) and (2,2,1) they would block the points (1,1,2) and (1,2,1). Since the square with first coordinate equal to one must have first coordinate equal to one must have two points of type b it must contain (1,3,2) and (1,2,3) but with (1,3,3) they would block both (1,3,1) and (1,1,3) but the square with first coordinate equal to one must have one of these points as shown previously so are done.
 
 
 
 
 
 
 


== n=4 ==
== n=4 ==
Line 221: Line 165:
* c is at least 6 (and, except for [http://abel.math.umu.se/~klasm/moser-n=3-t=3-41-c=6.gz 16 exceptional solutions] of the shape (7,28,6,0,0), have c at least 11).
* c is at least 6 (and, except for [http://abel.math.umu.se/~klasm/moser-n=3-t=3-41-c=6.gz 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 [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DuqNcxJ171Bbw&hl=en here].
Statistics for the 41-point, 42-point, and 43-point solutions can be found [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DuqNcxJ171Bbw&hl=en here].  [http://spreadsheets.google.com/ccc?key=rwXB_Rn3Q1Zf5yaeMQL-RDw&hl=en Here is the full list of Pareto-optimals].


If a Moser set in <math>[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.
If a Moser set in <math>[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.
Line 260: Line 204:
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.
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. ===
====  If a Moser set for n=4 has 4 or more points with three 2’s it has less than 41 points. ====
 
We first note that, as shown above, if a Moser set includes 2222, it has at most 39 points.  So any Moser set with 41 or more points has no point with four 2's.  So e=0.
 
If a Moser set for n=4 has six or more points with three 2’s it must have less than 41 points. We have 5 points with exactly three 2’s and one coordinate not equal to 2. That gives 5 values not equal to 2 and four coordinates one coordinate must have the coordinate value not equal to 2 from 2 of the five points. One value must be three the other one. We slice at this point and get two cubes with the center point filled which by the n=3 section of the wiki on Moser sets must have 13 points or less. Since there are six or more points with three 2’s the center slice must have the remaining four or more. Now if we have 41 or more points it must have a center slice equal to 15 points or more. However by the Pareto-optimal statistics in the section n=3 of the wiki we see that a cube with c greater than three can have value at most 14. So there at most 13+14+13=40 points and we are done.
 
 
On the 3D section of the Wiki, we have the inequalities
 
:<math>4\alpha_0+4\alpha_1+3\alpha_2+\alpha_3 \leq 6 (1)</math>
 
:<math>7\alpha_0+3\alpha_1+3\alpha_2+\alpha_3 \leq 7 (2)</math>
 
which when averaged on middle slices gives the 4D inequalities
 
:<math>b/8 + c/6 + 3d/8 + e \leq 6 (3) </math>
 
:<math>7b/32 + c/8 + 3d/8 + e \leq 7. (4) </math>
 
Averaging (1) on side slices similarly gives
 
:<math>a/4 + b/8 + c/8 + d/8 \leq 6. (5) </math>
 
Computing 9/4 *(3) + (4) + 4*(5) gives
 
:<math>a+b+c+d+e \leq 89/2 - 23 d / 32 - 9 e / 4</math>
 
and so if a+b+c+d+e &ge; 41 then we must have d &le; 4.
 
'''Lemma 0''' I used maple to find the integer solutions to d=4, a+b+c+d+e &ge; 41 that were consistent with all known inequalities. They are: (6,16,15,4,0,0), (7,16,14,4,0,0), (7,17,13,4,0,0), and (7,18,12,4,0,0) <math>\square</math>
 
'''Lemma 1''' If a Moser set has 4 points with 3 2’s and its size is 41
or more then it must not have two pairs of points, each pair with three twos and
the same c statistic.
 
'''Proof''' Assume the Moser set has two such pairs.  Without loss of generality,
they are 1222,3222, and 2122,2322.
Cut at the first coordinate. Both side slices include their central point, and so must have 13 or fewer points.  So the center slice must have 15 or more points.
 
Recall the two points of the form say 2×22 which are in the center cube. 
We can slice at the second coordinate, and the side squares have the center spot occupied.
Consider the points in the center cube with one coordinate equal
to 2 in the cube (and two coordinates in the 4D configuration).  There must be
at most 8: two each from the side squares since the center
spot is occupied and possibly all 4 from the center square.
 
From the Pareto optimal statistics in section n=3 of this Moser wiki,
and the fact the center cube has 15 points and has c=2,
the statistics of the center slice must be (4,9,2,0).  
But from the above we have at most 8 points
with one coordinate equal to 2, so we are done.
<math>\square</math>
 
'''Lemma 2''' If a Moser set has 4 points with 3 2’s and its size is 41
or more then it must not have any set of two points with three twos with
the same c statistic.
 
'''Proof''' We start by assuming we have such a pair.  By Lemma 1, there is only one such pair.  Suppose they are 1222 and 3222.  Without loss of generality, the other two points with three 2s are 2122 and 2212.
 
Slice on the first coordinate.  We get two slide slices with 13 or less points, so the center slice must have 15 points or more.  It cannot have sixteen points as it has at least one point with three twos in the configuration, which becomes a point with two 2’s in the central slice; that prevents the only realization of sixteen points from occurring since it has no points with two 2’s.  Further, from the Pareto optimal statistics for Moser sets for n=3 at the Moser wiki, we see its distribution must be (4,9,2,0). 
 
Slice the center cube along the second coordinate.  One outside slice, with the point 2122, must have that point at its center, and hence has a maximum of 5 points and at most two points with two twos.  The center slice 22xy has no center point and one point with three twos (2212). Because of this the center slice can have at most 4 points and it can contain at most three points with two twos.  So the remaining slice 23xy must have all four points with two twos.
 
The two side slices 1xyz and 3xyz, since they have thirteen points including the central point, must have statistics (3,6,3,1) or (4,6,2,1) each. So each of the diagonals connecting points with one two in the slice overall must have at least one point and that means that if we cut each of the side cubes along the same coordinate we cut the center cube we get there are a total four points with one two in the two side slices and if they are divided 2, 2. We can pick two pairs one point in a pair in each slice such there is a correspondence between the pairs of the points in that the coordinates j are equal. If they are divided 1,3 again there is a correspondence between the one point and one of the three such that the coordinates except for j are equal.
Now in the case of division 2-2 or 1-3 in the above we get a contradiction as follows be we have the above correspondences plus another one in the cube j=1 since it has its center spot occupied combined they give there are one or two points with the same center coordinates except for i in the cube j equals three but the center square of j=3 contains all its points with two two’s which block all lines between points with identical coordinates except for j and i equal to three and we get a line so we must have a four zero split, and since that split must have four points in each side cube and the center slice contains of j=3 contains all of it line so must have at most four of these point and the cube j=1 contains its center point and contains at most four of these points, these points must lie on either the squares i=1,j=3 and i=3,j=1 or i=1,j=1 and i=3,j=3 but then they will form a diagonal cube with i=2,j=2 which contains one point with three twos and this forms a line with one of the pairs of these four points on the diagonal cube and we are done.
<math>\square</math>
 
'''Lemma 3''' If a 4D Moser set has more than 40 points and 4 points with three
2’s it must have the following statistics:  (6,16,15,4,0) or (7,16,14,4,0).
 
'''Proof''' We have from Lemma 0(post 1113) that only the following statistics are possible:
(6,16,15,4,0), (7,16,14,4,0), (7,17,13,4,0), and (7,18,12,4,0).
and from Lemma 2
(If a Moser set has 4 points with 3 2’s and its size is 41 or more then it must not have any set of two points with three twos with the same c statistic. )
 
We look at the number of points with one two.  Each one must appear in exactly one of the four possible middle cubes from the four possible coordinate slices.  If the number of these points is greater than 16 then there must be one such middle cube with five of these points.
By Lemma 2 we know that there must be three points with three twos in the cube as well as otherwise there would be two with the same c statistic.  We check the pareto optimizers from the wiki and find there is only one satisfying (5,p,3,q) and that is (5,4,3,0).
So the center has 12 points and distribution (5,4,3,0).  The side cube with
the remaining point with three twos has thirteen points, and distribution (3,6,3,1) or (4,6,2,1).  The remaining side cube must have 41-12-13=16 points and hence distribution (4,12,0,0)
 
But this gives a total of 5 + 12+ 6 points with one two
which is too many for any of the possible sets of statistics.  So the only
distribution that is possible is the one with 16 points with one two
namely (6,16,15,4,0)or (7,16,14,4,0) and we are done.
<math>\square</math>
 
'''Lemma 4''' A 4D Moser set with 4 points with three threes has 40 points or less.
 
'''Proof'''By the reasoning of Lemma 3 each slice of a Moser set must have 4 points or less with one 2 in the center cube.  Since from the above we must have 16 of these points and each point only appears in one coordinate slice the division must be exactly 4 4 4 4.
 
No extremal slice can have 16 points; if so it has distribution (4,12,0,0) by the Pareto optimizers and hence since by the above the distribution of points with one two must include exactly 4 in the center slice we have a total of 16 and hence none in the other extremal set which contains its center point then by looking at the Pareto optimizers we see that we have to remove 6 points from a thirteen point or four points from a 11 point set in order to realize this and this gives at most 8 points then we have 8 + 16 points for the two side slices and we need 17 points in the center slice which cannot be realized.
 
So we have the side slice without the center point must have 15 points or less. Next we show that the center slice must have 14 points or less. By the above it must have 4 points with one two but this gives a distribution of (4 x y z) note the points with one two in this slice count as points with no 2 in the internal statistics of the cube. The center slice must have y = to three because we have already established that there are no two points with the same c-statistic so we must have statistics (4 x 3 0)
which looking at the Pareto optimizers must have 14 points or less.
 
Now we recall that now two points with three twos can have the same c-statistic then we can assume without loss of generality that all such points have the coordinate not equal to 2 equal to one. Then we look at the points
(1 1 3 2) (1 3 1 2) (3 1 1 2) Only one of these can be in the Moser set because otherwise a line will be formed with the points with three 2’s under the above assumption. Now that means that under one of the coordinate cuts must have a diagonal connecting two points with one two. empty and that means that it can have at most 5 points with one two since each of the other diagonals have at most one point. That implies that the there must be at most 12 points in this cube since the other points have at most 14 and 15 points we must have the distribution 12 14
15 or we will have less than 41 points. Then the statistics of the
cube must be (3 5 3 1) or ( 4 5 2 1) and the other side cube
must have statistics ( 3 9 3 1) (4 9 2 1) or (4 11 0 0)
or (3 12 0 0) but if we have the statistics (6 15 16 4 0) we can only have the choice (3 5 3 1) and the choices (3 9 3 1) and (3 12 0 0)
or we would have more than 6 points with no 2’s and we can discard
the possiblity (3 12 0 0) because it would give more than 16 points with one 2. So we must have (3 5 3 1) and (3 9 3 1) and this gives center slice
(2 9 3 0) but this has less than four points with two twos and will force another slice to have more than 4 and so we are done.
 
If we have the statistics:
(7,16,14,4,0) then recall we must have the distribution 12 14
15 or we will have less than 41 points. Also recall that the statistics of the side cube with its center point must be (3 5 3 1) or ( 4 5 2 1) then the statistics of the other side cube
must be ( 3 9 3 0) (4 9 2 0) or (4 11 0 0)
or (3 12 0 0)
Since the statistics are
(7,16,14,4,0) we must have one of the following four pairs of side cubes:
 
(3 5 3 1) and (4 9 2 0)
(3 5 3 1) and (4 11 0 0)
( 4 5 2 1) and (3 9 3 0)
( 4 5 2 1) and (3 12 0 0)
 
If we have (3 5 3 1) and (4 9 2 0)
forces the middle slice to have statistics (0 2 9 3)
which has less than 4 points with one two
hence forces another slice to have more than four which gives
a contradiction
 
If we have (3 5 3 1) and (4 11 0 0)
forces the middle slice to have statistics (0 0 11 3)
which has less than 4 points with one two
hence forces another slice to have more which gives
a contradiction
 
If we have ( 4 5 2 1) and (3 9 3 0)
forces the middle slice to have statistics (0 2 9 3)
which has less than 4 points with one two
hence forces another slice to have more which gives
a contradiction
 
If we have ( 4 5 2 1) and (3 12 0 0)
has 17 points with one two which contradicts the
statistics of the entire set.
So none of the cases work and we are done.
<math>\square</math>
 
===  If a Moser set for n=4 has 1 or more points with three 2’s it has less than 43 points. ===
 
Proof: Assume that such a set exists. We have already proved that it contains no point of type e. So we can assume that. This set does not contain such a point.
 
This set since it has 43 points must have at least 18 points of type c. See http://michaelnielsen.org/polymath1/index.php?title=Maple_calculations.
Since there is a point of type d we can slice the set so that one side cube has its center slot filled and so must have 13 points or less.
The other cubes must sum to 30. The other side cube must not have 16 points since then by the list of Pareto optimizers its distribution would be (4, 12, 0, 0) and it would contribute no points of type c to the Moser set. Then the other side cube could contribute at most 3 points of type c. So for there to be 18 the central cube must contribute 15 which is not possible.
 
This means the center cube must have at least 15 points for there to be a total of 43. Now we will show that the configuration has at most one point of type d.
 
Assume that there are more than one. Then no two can have the same c-statistic or we can slice and get two side cubes with center points filled which give each a total of at most 13 points which would force the center slice to have 17 points which is impossible.
 
So we can get a slice that has one point of type d in a side cube and the other in the center cube. That means the side cube must have its center slot filled and it must have 13 points, the center cube contains one point of type c(type d in the overall Moser set) and thus must have 15 points or less as the only Pareto optimal set with 16 points contains none of type c. The remaining side cube must have 15 points or more.
 
The only distribution which works is 13 points in one side cube and 15 in the other two. Now since there is no Moser three set with one point of type c and a total of fifteen points. There must be at least two points of type c in the center cube in giving at least 3 for the overall set.
From this and the Pareto optimizers we see that the distribution of the side slice with 13 points must be (3, 6,3,1) or (4,6,2,1) and of the center and side cubes (3,9,3,0) or (4,9,2,1) This means we have at least 17 points of type b. Every one of these points appears in the center cube in exactly one slice. There are 4 slices so there is one slice with 5 of these points in the center cube.
 
Now since we have at least three points of type d and we can’t have two of them in the side cubes we must have at least one in the center cube. This means that that cube must have at most 13 points. No if either of the side cubes has a point of type d its total will be at most 13 and the third cube must be 17 which gives a contradiction so all three center points must be in the center cube.
 
This lowers the total of the center cube to at most 12. This in fact forces the center cube to have distribution (5,4,3,0) or that distribution with one point removed.. This also forces the sides cubes to have total 31. This means that one will have 16 points and thus have statistics (4,12,0,0). The other will have 15 points and hence have 9 point s of type b giving a total of 25 of type b if the center cube has 12 points.
 
If it has 11 points then it will have the distribution (5, 3, 3 as that is the only subset of the Pareto optimizers satisfying the conditions. Then both side cubes will have 16 points which means that neither will contain points of type c which means that there must be 18 points of type c in the center cube which gives a contradiction.
 
So the center cube has 12 points and the total number of points of type b is 25 so since each point of type b occurs in one slice and there are four possible slices there must be one slice with 6 points of type b since we get a contradiction as above if there are less than 11 points. So there must be 12 points the only distribution that works is (6,6,0,0).
 
But then the middle slice contains none of the points of type d and one must be on a slide slice lowering the total of that slice to 13 or less forcing the other side slice to be above 18. So we have reached a contradiction in assuming that we have more than one point of type d the remaining case is that there is exactly one point of type d.
 
If there is exactly one slice so it is in one of the side cubes. That cube will have at most 13 points. The other side cube can have at most 15 points because if it has 16 it will have no points of type c and the other side cube will have at most 3 of type c and since the total size is 18 we must have 15 of type c in the center cube which gives a contradiction.
 
So the center cube must have at least 15 points. Furthermore since it has no points of type c since we have our single point of type d in one of the side cubes it must be a subset of (4,12,0,0) and must have at least 11 points of type b. To avoid forming a monochromatic line the points of type b of the side cubes must sum to 13 or less.
 
If the side cube without the center cube has 15 or more points it must have at least 9 points of type b forcing at most 4 of type be in the other side cube which forces its size to 11 or less which forces both of the other cubes to have more than 16 which contradicts the fact that no side cube can have more than 15 points proved above.
So the side cube without the center point must have at most 14 points. The other side cube can have at most 13 points so the center cube must have 16 points and since it cannot have 17 we have the distribution (13,16,14).
 
This forces the center cube to have all its points of type b there are 12 of these. From the Pareto optimizers the side cube with 13 points with the center spot filled must have at exactly 6 points of type b. We will get a line unless the remaining side cube has more than six points of type b. The only distributions with at least 14 points that satisfies this is (3,6,5,0) and (2,6,6,0). From the Pareto optimal statistics we can limit the possibilities for the other cubes of slice and get the following:


So one center cube has statistics (4,12,0,0) the side cube with thirteen points and the center filled has distribution (3,6,3,1) or (4,6,2,1) and final cube has statistics (3,6,5,0) and (2,6,6,0). So the statistics of the Moser set must be (6,16, 21,1,0), (7,16, 20,1,0), or (8,16, 19,1,0). So the exact number of points of type b must be 16.
See [[4D Moser sets with d at least 4 have at most 40 points]].


Now slice the set so that the point of type d is in the center slice. Then the center cube contains a point of type c and has at most 10 points of type b. It must have at most 14 points that means that the other two cubes must total at least 29. If one is 16 then it contains no points of type c and since the center cube contributes at most 10 the other side cube must have 8 such points. This gives a contradiction which means one side cube must be of size 15 and the other of size 14. The one of size 15 contains at most three of type c. The center contains at most 10 so the remaining cube must have 5 or more.
====  If a Moser set for n=4 has 1 or more points with three 2’s it has less than 43 points. ====


Again from the Pareto statistics we can limit the statistics of each of the cubes the side slice of size 15 must be (3,9,3,0) (4,9,2,0) otherwise it will have no points of type c and we will get a contradiction as above. The side slice must have at least 5 points of type c and at least 14 points so it must have statistics (2,6,6,0) or (3,6,5,0). The center slice must have 1 point of type c in its statistics and at least 9 points of type b in its statistics which are statistics of type in the whole Moser set. Thus it statistics are either (4,9,1,0) which is a Pareto optimal set with one point removed or (3,10,1,0). Then the distributions are either (5, 19,18,1), (5,18,19,1), (6,19,17,1,0),(6,18,18,1,0), (7,19,16,1,0) or (7,18,17,1,0). Since we must have 18 points of type c the only possible distributions are (5, 19,18,1), (5,18,19,1) or (5,18,19,1). But we have shown the exact number of points of type b must be 16 which is a contradiction and we are done. So every Moser set with d=4 cannot contain a point with three two’s.
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. ===
====  If a Moser set for n=4 has 3 or more points with three 2’s it has less than 42 points. ====


If a Moser set has 42 points it will have less than three points with three twos. Assume that there is a set with more than two such points. If it has 4 or more it will have two with the same c-statistic. We can slice along that coordinate and get two side cubes with the center cube occupied which implies they have 13 points or less. The center cube will have one such point and hence have 15 points or less. So the total number of points is 41 or less which is a contradiction. So we can assume we have exactly three such points.
See [[4D Moser sets with d at least 3 has at most 41 points]].
We can show no two of these points can have the same c-statistic. If they do again we can cut along the coordinate and the two side cubes will have their center slots occupied and will have 13 or less points and the center cube will have one such point and will have less than 16 points so the total will be less than 42. So we can assume that no two have the same c-statistic and without loss of generality we can assume that the points are (1,2,2,2), (2,1,2,2) and (2,2,1,2).


Look at the points (1,1,2,2), (2,1,1,2) and (1,2,1,2). No two of them can be in the Moser set because they would form a line with (1,2,2,2), (2,1,2,2) and (2,2,1,2). So one pair must be missing. That pair will have a one say in coordinate a in common and hence. Will be in one side cube of a side slice resulting from the cut along coordinate a that contains its center point. This will mean that the side slice has 5 points of type b and hence contains 12 or less points.
==== Brute-force calculations for <math>[3]{}^4</math> ====


If it contains 9 points then the other two slices must have at least 33 and that will result in one having 17 which leads to a contradiction. If it has 10 points the other two must have at least 32 which means that both must have 16 points which means that the center cube and the other side cube have no points with three 2’s which mean there are less than three such points which leads to a contradiction.
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.


If it has 11 points then the remaining two cubes must total 31. Then one must total 16 and the other 15. If the center cube totals 16 then there can be no points with three 2’s inside it and since only one such point can be in either of the side cubes we have at most 2 which gives a contradiction. If one of the side cubes totals 16 it must have 12 points with one two. The center cube if it totals 15 must contribute three such points and the side cube with 12 points must have statistics (4,4,3,1) or one of the following with two points removed: (3,6,3,1) or (4,6,2,1). In any of these cases it will have at least 4 points with one two. This gives at least 19 points with one 2 in the set.
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:


So we can assume the side cube with center spot occupied has exactly 12 points and it contain at least 5 points with one two..If the other side slice contains its center point the two side slices will total less than 26 and the total in the set will be less than 42 and we will have a contradiction. So the center cube must have two points with three 2’s in the set and hence it will have at most 15 points and it will have at least three points with one two. If it has 16 points it will contain no points with three 2’s and since the side slices can contain at most one we will have a contradiction. So it must contain exactly 15 points which implies the other side slice must have at least 15 and hence 9 points with one two. So we have at lest 5+9+3 points with one two in the set. In the case in the above paragraph we have at least 19 so we can assume at least 17.
* 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.


Now since each point with one two occurs in exactly one of the cuts along a coordinate in the center slice there must be one slice with 5 points in the center slice with exactly two 2’s and from the Pareto optimizers we see the center slice can have at most 14 points. If both side slices contain their center points then the total number of points would be less than 13+13+14 which is less than 42. So only one can have its center point and the center cube must have two such points and again by the Pareto optimizers it must have at most 13 points. Then if one of the side cube had its center spot occupied it would have at most 13 points and since the center cube has at most 13 points the other side cube must have 16 points. Then it would have no points of type c. The side cube could contribute at most 3 such points and the center cube at most 6 but we must have 12 such points see http://michaelnielsen.org/polymath1/index.php?title=Maple_calculations. So we have a contradiction so all three points with three 2’s must be in the center cube that means from the Pareto optimizers that the center must be a subset of (5,4,3,0) and have at most 12 points. That means that the total of the side cubes must be 30. If one is 16 it has no points with two 2’s in the set. The center has at most 4 such points that means since there are at least 12 the other cube must have at least 8 but by the Pareto statistics a 14 point set can have at most 6 such points. If both are fifteen they can contribute at most 6 such points the center cube can contribute at most 4 and we have a contradiction.
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 [http://spreadsheets.google.com/ccc?key=rwXB_Rn3Q1Zf5yaeMQL-RDw&hl=en this list of Pareto-optimals] and [http://spreadsheets.google.com/ccc?key=rD2Oc_wyheVOcmCyd-Drdgw&hl=en this list of extremals].


== Proof that <math>c'_5</math> = 124 ==
== Proof that <math>c'_5</math> = 124 ==
Line 589: Line 362:


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.
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>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), or equivalently
* The 22 a-points consisting of 111111, 111113, 113333 and permutations;
* The 66 b-points consisting of 111332, 333332 and permutations;
* The 165 c-points consisting of 111322, 113322, 333322 and permutations;
* The 100 d-points consisting of 111222, 133222, 333222 and permutations;
* No e, f, or g points.
'''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 [http://spreadsheets.google.com/ccc?key=rwXB_Rn3Q1Zf5yaeMQL-RDw&hl=en  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 of its "corner slices" - 11***** and permutations and reflections.  Define the ''defect'' of a slice to be 356 minus its score.  From [http://spreadsheets.google.com/ccc?key=rwXB_Rn3Q1Zf5yaeMQL-RDw&hl=en  the Pareto optimal list], the largest scores are
* 356 (defect 0) - attained by (6,12,18,4,0)
* 352 (defect 4)- attained by (5,12,18,4,0), (5,12,12,4,1), (6,8,12,8,0)
* 350 (defect 6)- attained by (6,11,18,4,0), (5,15,12,3,1), (6,11,12,7,0), (5,15,18,3,0)
* 348 (defect 8)- 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 (defect at least 10).
This establishes <math>c'_6 \leq 356</math>.
Call a corner slice "good" if it has score 356 (defect 0), i.e. has statistics (6,12,18,4,0), and "bad" otherwise (so has score at most 352, i.e. defect at least 4).  Thus:
* In a 356-point set, all 60 corner slices must be good.
* In a 355-point set, at most 15 corner slices can be bad.  (In fact, the total defect of all the slices is 60.)
* In a 354-point set, at most 30 corner slices can be bad. (In fact, the total defect of all the slices is 120.)
The (6,12,18,4,0) sets have been [[classification of (6,12,18,4,0) sets|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>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.  Call this set the (6,12,18,4,0) set of type xyzw.  It consists of
* The four "d" points x222, 2y22, 22z2, 222w;
* All 24 "c" points ''except'' for xy22, x2z2, x22w, 2yz2, 2y2w, 22zw;
* The 12 "b" points xYZ2, xY2W, x2ZW, XyZ2, Xy2W, 2yZW, XYz2, X2zW, 2YzW, XY2w, X2Zw, 2YZw, where X=4-x, Y=4-y, Z=4-z, W=4-w;
* The 6 "a" points xyzw, xyzW, xyZw, xYzw, Xyzw, XYZW.
In particular, the centre 3D slices of a good corner slice have statistics (3,9,3,0), and two opposing side slices have statistics (2,6,6,0) and (4,3,3,1).
'''Note''': in the 353-point example given above, the 11**** slices are good (and of type 1111), the 13**** slices have statistics (5,12,18,4,0) and consist of the type 3333 slice with the point 133333 removed, and the 33**** slices have statistics (6,8,12,8,0), with the slice consisting of the 6 a-points formed by permuting 1133, the 8 b-points formed by permuting 1112 and 3332, the 12 c-points formed by permuting 1122 and 3322, and all 8 d-points.
We now show that it is impossible to have a 356-point set, i.e. one in which all corner slices are good.  From the above discussion, we see that if the 111*** slice contains its center 111222, then the 113*** slice does not, and vice versa. 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.
Now we study what happens when two intersecting 4D corner slices of <math>[3]^6</math> are (6,12,18,4,0) sets.
'''Lemma 10'''.  Suppose that the 11**** slice is of type xyzw, and the 1*1*** slice is of type x'y'z'w'.  Then x' = x, and y'z'w' is equal to either yzw or YZW.  If x'=x=1, then y'z'w'=yzw. 
'''Proof''' Observe that the 11**** slice contains 111222 iff x=1, and the 1*1*** slice similarly contains 111222 iff x'=1.  This shows that x=x'.
Suppose now that x=x'=1.  Then the 111*** slice contains the three elements 111y22, 1112z2, 11122w, and excludes 111Y22, 1112Z2, 11122W, and similarly with the primes, which forces yzw=y'z'w' as claimed.
Now suppose that x=x'=3.  Then the 111*** slice contains the two elements 111yzw, 111YZW, but does not contain any of the other six "a" points in 111***, and similarly for the primes.  Thus y'z'w' is equal to either yzw or YZW as claimed.
One can reflect this to get
'''Corollary 11'''  Suppose that the pq**** slice is of type xyzw, and the p*r*** slice is of type x'y'z'w', where p,q,r,x,y,z,w,x',y',z',w' are in {1,3}.  Then x'=x iff q=r, and y'z'w' is equal to either yzw or YZW.  If x=r (or equivalently if x'=q), then y'z'w'=yzw.
Now we put some slices together:
'''Corollary 12''' Suppose that the 11**** slice is of type xyzw, and the 1*1*** and 13**** slices are both good.  Then the 13**** slice is of type Xyzw or XYZW.  If the 1**1** slice is also good, then the 13**** slice must be of type XYZW.
'''Proof''' From Lemma 10, the 1*1*** slice is of type xyzw or xYZW.  By Corollary 11, the 13**** slice is thus of type Xyzw or XYZW.  If the 1**1** slice is also good, then we similarly conclude that the 13**** slice is of type xYzw or XYZW.  The claim follows.
'''Corollary 13''' Suppose the 11**** and 13**** slices are good.  Then either they have opposite types (xyzw and XYZW) or else at least six of the eight slices beginning with 1* (i.e. 1*1***, 1*3***, 1**1**, 1**3**, 1***1*, 1***3*, 1****1, 1****3) are bad.
'''Lemma 14''' If the 11**** and 33**** slices are good and of the same type, then there are at most 350 points.
'''Proof'''  By symmetry we may assume that 11**** and 33**** are of type 1111.  This excludes a lot of points from 22****.  Indeed, the only points that can still survive in 22**** are 221133, 221333, 221132, 223332, and permutations of the last four indices.  Double counting the lines 22133* and permutations we see that there are at most 12 points one can place in the permutations of 221133, 221333, 221132, and so the 22**** slice has at most 16 points.  Meanwhile, the two 5D slices 1*****, 3***** have at most <math>c'_5=124</math> points, and the other two 4D slices 21****, 23**** slices have at most <math>c'_4=43</math> points, leading to <math>16+124*2+43*2 = 350</math> points in all.  The claim follows.
'''Corollary 15''' If the 11****, 13****, and 33**** slices of a 355-point set are all (6,12,18,4,0) sets, then either six of the eight slices beginning with 1* are bad, or six of the eight slices beginning with *3 are bad.
'''Proposition 16''' A 355-point set cannot have all four slices 11****, 13****, 31****, and 33**** slices be good.
'''Proof'''  Suppose not.  By Lemma 14, the 11**** and 33**** slices cannot be of the same type, and so they cannot both be of the opposite type to either 13**** or 31****.  From Corollary 15 we conclude that at least twelve of the sixteen slices beginning with 1*, 3*, *1, *3 are bad.  Since there are at most 15 bad slices, there are only three bad slices beginning with **.  By the pigeonhole principle, we may thus assume that **11**, **13**, **31**, **33** are good.  But now on applying Lemma 14 and Corollary 15 again we conclude that there are four more bad slices beginning with **, contradiction.
From this and the score analysis we see that
'''Corollary 17''' In a 355-point set, exactly three of the four slices 11****, 13****, 31****, and 33**** are good, and the bad slice is a 352-score set. 
In particular, one cannot have two parallel bad corner slices.  Combining this with Corollary 13, we see that two adjacent parallel good corner slices must necessarily have opposite types.  Combining this with Corollary 17, we obtain an opposing pair of parallel good corner slices of the same type, which is not possible by Lemma 14.  Thus a 355 point set cannot exist.
We now refine the analysis further, with the aim of eliminating 354-point sets.
'''Lemma 18'''  Suppose the 11**** and 13**** slices are good with types xyzw and x'y'z'w' respectively.  If x=x', then the 1*x*** slice has score at most 326 (defect at least 30), and the 1*X*** slice has score at most 348 (defect at least 8).  Also, the 1**1**, 1**3**, 1***1*, 1***3*, 1****1, 1****3 slices have score at most 350 (defect at least 6).  In particular, the total defect of slices beginning with 1* is at least 74.
'''Proof'''  The 1*x*** slice has eight "a" points, while the 1*X*** slice has only four.  The other six slices mentioned have six "a" points and at most seven "d" points, and cannot be good by Corollary 12.  The claim now follows from [http://spreadsheets.google.com/ccc?key=rwXB_Rn3Q1Zf5yaeMQL-RDw&hl=en  the Pareto optimal list].
'''Corollary 19''' A 354-point set cannot have all four slices 11****, 13****, 31****, and 33**** slices be good.
'''Proof''' Suppose not.  By Lemma 14, the 11**** and 33**** slices cannot be of the same type, and so they cannot both be of the opposite type to either 13**** or 31****.  If 13**** is not of the opposite type to 11****, then by (a permutation of) Lemma 18, the total defect of slices beginning with 1* is at least 74; otherwise, if 13**** is not of the opposite type to 33****, then by (a permutation and reflection of) Lemma 18, the total defect of slices beginning with *3 is at least 74.  Similarly, the total defect of slices beginning with 3* or *1 is at least 74, leading to a total defect of at least 148.  But a 354 point set has a total defect of 120, contradiction.
One can divide the 60 slices into fifteen families of four depending on their frozen coordinates, for instance one families of four is 11****, 13****, 31****, 33****.  We'll call this family the ab**** family, and similarly define the a*b*** family, etc.
'''Corollary 20''' A 354-point set can have at most one family with a total defect of at least 38.
'''Proof'''  Suppose there are two sets with defect at least 38.  The remaining thirteen sets have defect at least 4 by Corollary 19, leading to a net defect of 38*2+13*4=128.  But 354-point sets have a net defect of 120, a contradiction.
'''Proposition 21''' A 354-point set cannot have any family with a total defect of at least 38.
'''Proof''' Suppose for contradiction that the ab**** family (say) had a total defect of at least 38, then by Corollary 20 all other families have total defect at least 38.
We claim that the **ab** family can have at most two good slices.  Indeed, suppose the **ab** has three good slices, say **11**, **13**, **33**.  By Lemma 14, the **11** and **33** slices cannot be of the same type, and so cannot both be of opposite type to **13**.  Suppose **11** and **13** are not of opposite type.  Then by (a permutation of) Lemma 18, one of the families a*1***, *a1***, **1*a*, **1**a has a net defect of at least 38, contradicting the normalisation. 
Thus each of the six families **ab**, **a*b*, **a**b, ***ab*, ***a*b have at least two bad slices.  Meanwhile, the eight families a*b***, a**b**, a***b*, a****b, *ab***, *a*b**, *a**b*, *a***b have at least one bad slice by Corollary 19, leading to twenty bad slices in addition to the defect of at least 38 arising from the ab**** slice.  To add up to a total defect of 120, this means that all bad slices outside of the ab**** family have a defect of four, with at most one exception; but then by Lemma 18 this shows that (for instance) the 1*1*** and 1*3*** slices cannot be good unless they are of opposite type.  The previous argument then shows that the a*b*** slice cannot have three good slices, which increases the number of bad slices outside of ab**** to at least twenty-one, and now there is no way to add up to 120, a contradiction.
From Proposition 21 and Lemma 18 we conclude
'''Corollary 22''' In a 354-point set, the slices 11**** and 13**** can only be good if they have opposite type.
From this and Lemma 14 we conclude
'''Corollary 23''' In a 354-point set, every family can have at most two good slices, and thus have a defect of at least eight.
Since 120 = 15*8, we conclude
'''Corollary 23''' In a 354-point set, every family consists of ''exactly'' two good slices, plus two bad slices of defect exactly four.
Now we look at the statistics of center slices of 4D slices (e.g. the 112*** stats of the 11**** slice).  Computer search has revealed the following
* For a (6,12,18,4,0) slice, the central slice must be (3,9,3,0). [The other two slices are (4,3,3,1) and (2,6,6,0).]
* For a (5,12,18,4,0) slice, the central slice must be (3,9,3,0). [The other two slices must add up to (5,9,9,1).]
* For a (5,12,12,4,1) slice, the central slice must be (3,6,3,1). [The other two slices must add up to (5,9,6,1).]
* For a (6,8,12,8,0) slice, the central slice must be (2,6,6,0).  [The other two slices must add up to (6,6,6,2).]
Now we look at a side 3D slice, e.g. 111***.  Because at least two of 11****, 13****, 31****, 33**** must be of type (6,12,18,4,0), and such slices have 3D side slices of (4,3,3,1) and (2,6,6,0), we know that the 111*** slice must be adjacent to either a (4,3,3,1) slice or a (2,6,6,0) slice.  From the above list, we thus see that 111*** is one of the following possibilities:
# It is a slice of a (6,12,18,4,0) set, and is therefore either (4,3,3,1) or (2,6,6,0).
# It is a (3,3,3,1) slice of a (5,12,18,4,0) set, with the opposing slice being (2,6,6,0).
# It is a (1,6,6,0) slice of a (5,12,18,4,0) set, with the opposing slice being (4,3,3,1).
# It is a (3,3,0,1) slice of a (5,12,12,4,1) set, with the opposing slice being (2,6,6,0).
# It is a (1,6,3,0) slice of a (5,12,12,4,1) set, with the opposing slice being (4,3,3,1).
# It is a (2,3,3,1) slice of a (6,8,12,8,0) set, with the opposing slice being (4,3,3,1).
Furthermore, in all six cases, the opposing slice is a subslice of a (6,12,18,4,0) set.
Possibility 6 has been eliminated by computer, and possibilities 4,5 have been eliminated by hand.  As a consequence, the only possible 3D slices are (4,3,3,1), (2,6,6,0), (3,3,3,1), and (1,6,6,0).  This eliminates the (5,12,12,4,1) case.
The (6,8,12,8,0) case can also be eliminated: if (say) 11**** is (6,8,12,8,0), then 111*** and 113*** must now be (3,3,3,1), which forces the 1*1*** and 1*3*** slices to be bad, and hence the 3*1*** and 3*3*** slices are good, hence 311*** and 313*** must be (2,6,6,0) (note that we have no way of matching (3,3,3,1) to (4,3,3,1)), but then there is no consistent choice for the 31**** slice.
The only possible side slices of a (5,12,18,4,0) set are (4,3,3,1)+(1,6,6,0) and (3,3,3,1)+(2,6,6,0).  In particular, it contains exactly one of any opposing "d" points (e.g. 1222 and 3222).  Similarly for (6,12,18,4,0) sets.  We conclude that the same is true for the 6D set, e.g. exactly one of 111222 and 113222 lie in the set.
We can define the notion of the "type" of a (5,12,18,4,0) set just as with a (6,12,18,4,0) set.  The above observation forces any two adjacent slices (e.g. 11**** and 13****) to have opposing type, and thus any two diagonally opposite slices (e.g. 11**** and 33****) have identical type.  By Lemma 14, such slices cannot both be good.  Splitting each family into two pairs of diagonally opposing slices, we thus conclude
'''Proposition 24'''  In any two diagonally opposite slices of a 354-point set, one slice is (6,12,18,4,0) and the other is (5,12,18,4,0), and both slices have the same type.
On averaging, we see that the 354-point set has statistics (22,72,180,80,0,0,0).
'''Theorem 25''' <math>c'_6 = 353</math>.
'''Proof''' We repeat the previous argument that there is no 356-point set.  Suppose for contradiction that we have a 356-point set, i.e. one in which all corner slices are good.  From the above discussion, we see that if the 111*** slice contains its center 111222, then the 113*** slice does not, and vice versa. 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 (22,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.
== Connection with Fujimura's Problem ==
Recall the Gamma cells, where <math>\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> (a+r,b,c+s), (a,b+r+s,c), (a+s,b,c+r)</math> rather than equilateral triangles, and each point <math>(a,b,c)</math> is weighted by the cell cardinality <math>\frac{(a+b+c)!}{a!b!c!}</math>. (In particular, one has to exclude vertical line segments <math>(a+r,b,c+r),(a,b+2r,c)</math>, thus each value of <math>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.  More information on these results are stored [http://abel.math.umu.se/~klasm/Data/HJ/ here].  Note that the optimal values are found for n=1 to 4, but the value 122 is below the n=5 optimum value of 124.


== General n ==
== General n ==
Line 607: Line 547:
* <math>|A(m,3)| \le 2^m/(m+1)</math> because the size of a Hamming sphere is m+1.
* <math>|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>c'_6</math> and <math>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>c'_6 \le 361</math> and <math>c'_7 \le 1071</math>.
The integer programming routine from Maple 12 was used to obtain upper bounds for <math>c'_6</math> and <math>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>c'_6 \le 356</math> and <math>c'_7 \le 1041</math>.


A [[genetic algorithm]] has provided the following examples:
A [[genetic algorithm]] has provided the following examples:
Line 613: Line 553:
* <math>c'_6 \geq 353</math> (26 examples; [http://twofoldgaze.wordpress.com/2009/03/10/353-element-solution/ here is one])
* <math>c'_6 \geq 353</math> (26 examples; [http://twofoldgaze.wordpress.com/2009/03/10/353-element-solution/ here is one])
* <math>c'_7 \geq 988</math> [http://twofoldgaze.wordpress.com/2009/03/10/978-element-solution/ Here is the example]
* <math>c'_7 \geq 988</math> [http://twofoldgaze.wordpress.com/2009/03/10/978-element-solution/ Here is the example]
One 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, in the Fujimura-type problem described above.
For general N, the following collection of Gamma sets <math>\Gamma_{a,b,c}</math> is roughly one third better than the A sets described above when n is large:
* <math> \Gamma(a,q,N-a-q) </math> when <math>a\ne 2 (mod 3)</math>
* <math> \Gamma(a,q-1,N+1-a-q) </math> when <math>a\ne 1 (mod 3)</math>
* <math> \Gamma(a,q-2,N+2-a-q) </math> when <math>a = 0 (mod 3)</math>
* <math> \Gamma(a,q-3,N+3-a-q) </math> when <math>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) ==
== Larger sides (k>3) ==
Line 618: Line 573:
The following set gives a lower bound for Moser’s cube <math>[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
The following set gives a lower bound for Moser’s cube <math>[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>\binom{n}{n/2} 2^n + \binom{n}{n/2-1} 2^{n-1}</math>
<math>\binom{n}{\lfloor n/2\rfloor} 2^n + \binom{n}{\lfloor n/2\rfloor-1} 2^{n-1}</math>
 
The following set improves this bound to <math>(2+o(1))\binom{n}{\lfloor n/2\rfloor} 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>4^n/\sqrt{n}</math> by [[Stirling's formula]].
which is comparable to <math>\sqrt{\frac{8}{n\pi}}4^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>5^{n - O(\sqrt{\log n})}</math>.
For k=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>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>\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.
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>\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.

Latest revision as of 20:26, 29 September 2015

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; c'_6 = 353. }[/math]

Beyond this point, we only have some upper and lower bounds; 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:

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), or equivalently

  • The 22 a-points consisting of 111111, 111113, 113333 and permutations;
  • The 66 b-points consisting of 111332, 333332 and permutations;
  • The 165 c-points consisting of 111322, 113322, 333322 and permutations;
  • The 100 d-points consisting of 111222, 133222, 333222 and permutations;
  • No e, f, or g points.

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 of its "corner slices" - 11***** and permutations and reflections. Define the defect of a slice to be 356 minus its score. From the Pareto optimal list, the largest scores are

  • 356 (defect 0) - attained by (6,12,18,4,0)
  • 352 (defect 4)- attained by (5,12,18,4,0), (5,12,12,4,1), (6,8,12,8,0)
  • 350 (defect 6)- attained by (6,11,18,4,0), (5,15,12,3,1), (6,11,12,7,0), (5,15,18,3,0)
  • 348 (defect 8)- 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 (defect at least 10).

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

Call a corner slice "good" if it has score 356 (defect 0), i.e. has statistics (6,12,18,4,0), and "bad" otherwise (so has score at most 352, i.e. defect at least 4). Thus:

  • In a 356-point set, all 60 corner slices must be good.
  • In a 355-point set, at most 15 corner slices can be bad. (In fact, the total defect of all the slices is 60.)
  • In a 354-point set, at most 30 corner slices can be bad. (In fact, the total defect of all the slices is 120.)

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. Call this set the (6,12,18,4,0) set of type xyzw. It consists of

  • The four "d" points x222, 2y22, 22z2, 222w;
  • All 24 "c" points except for xy22, x2z2, x22w, 2yz2, 2y2w, 22zw;
  • The 12 "b" points xYZ2, xY2W, x2ZW, XyZ2, Xy2W, 2yZW, XYz2, X2zW, 2YzW, XY2w, X2Zw, 2YZw, where X=4-x, Y=4-y, Z=4-z, W=4-w;
  • The 6 "a" points xyzw, xyzW, xyZw, xYzw, Xyzw, XYZW.

In particular, the centre 3D slices of a good corner slice have statistics (3,9,3,0), and two opposing side slices have statistics (2,6,6,0) and (4,3,3,1).

Note: in the 353-point example given above, the 11**** slices are good (and of type 1111), the 13**** slices have statistics (5,12,18,4,0) and consist of the type 3333 slice with the point 133333 removed, and the 33**** slices have statistics (6,8,12,8,0), with the slice consisting of the 6 a-points formed by permuting 1133, the 8 b-points formed by permuting 1112 and 3332, the 12 c-points formed by permuting 1122 and 3322, and all 8 d-points.

We now show that it is impossible to have a 356-point set, i.e. one in which all corner slices are good. From the above discussion, we see that if the 111*** slice contains its center 111222, then the 113*** slice does not, and vice versa. 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.

Now we study what happens when two intersecting 4D corner slices of [math]\displaystyle{ [3]^6 }[/math] are (6,12,18,4,0) sets.

Lemma 10. Suppose that the 11**** slice is of type xyzw, and the 1*1*** slice is of type x'y'z'w'. Then x' = x, and y'z'w' is equal to either yzw or YZW. If x'=x=1, then y'z'w'=yzw.

Proof Observe that the 11**** slice contains 111222 iff x=1, and the 1*1*** slice similarly contains 111222 iff x'=1. This shows that x=x'.

Suppose now that x=x'=1. Then the 111*** slice contains the three elements 111y22, 1112z2, 11122w, and excludes 111Y22, 1112Z2, 11122W, and similarly with the primes, which forces yzw=y'z'w' as claimed.

Now suppose that x=x'=3. Then the 111*** slice contains the two elements 111yzw, 111YZW, but does not contain any of the other six "a" points in 111***, and similarly for the primes. Thus y'z'w' is equal to either yzw or YZW as claimed.

One can reflect this to get

Corollary 11 Suppose that the pq**** slice is of type xyzw, and the p*r*** slice is of type x'y'z'w', where p,q,r,x,y,z,w,x',y',z',w' are in {1,3}. Then x'=x iff q=r, and y'z'w' is equal to either yzw or YZW. If x=r (or equivalently if x'=q), then y'z'w'=yzw.

Now we put some slices together:

Corollary 12 Suppose that the 11**** slice is of type xyzw, and the 1*1*** and 13**** slices are both good. Then the 13**** slice is of type Xyzw or XYZW. If the 1**1** slice is also good, then the 13**** slice must be of type XYZW.

Proof From Lemma 10, the 1*1*** slice is of type xyzw or xYZW. By Corollary 11, the 13**** slice is thus of type Xyzw or XYZW. If the 1**1** slice is also good, then we similarly conclude that the 13**** slice is of type xYzw or XYZW. The claim follows.

Corollary 13 Suppose the 11**** and 13**** slices are good. Then either they have opposite types (xyzw and XYZW) or else at least six of the eight slices beginning with 1* (i.e. 1*1***, 1*3***, 1**1**, 1**3**, 1***1*, 1***3*, 1****1, 1****3) are bad.

Lemma 14 If the 11**** and 33**** slices are good and of the same type, then there are at most 350 points.

Proof By symmetry we may assume that 11**** and 33**** are of type 1111. This excludes a lot of points from 22****. Indeed, the only points that can still survive in 22**** are 221133, 221333, 221132, 223332, and permutations of the last four indices. Double counting the lines 22133* and permutations we see that there are at most 12 points one can place in the permutations of 221133, 221333, 221132, and so the 22**** slice has at most 16 points. Meanwhile, the two 5D slices 1*****, 3***** have at most [math]\displaystyle{ c'_5=124 }[/math] points, and the other two 4D slices 21****, 23**** slices have at most [math]\displaystyle{ c'_4=43 }[/math] points, leading to [math]\displaystyle{ 16+124*2+43*2 = 350 }[/math] points in all. The claim follows.

Corollary 15 If the 11****, 13****, and 33**** slices of a 355-point set are all (6,12,18,4,0) sets, then either six of the eight slices beginning with 1* are bad, or six of the eight slices beginning with *3 are bad.

Proposition 16 A 355-point set cannot have all four slices 11****, 13****, 31****, and 33**** slices be good.

Proof Suppose not. By Lemma 14, the 11**** and 33**** slices cannot be of the same type, and so they cannot both be of the opposite type to either 13**** or 31****. From Corollary 15 we conclude that at least twelve of the sixteen slices beginning with 1*, 3*, *1, *3 are bad. Since there are at most 15 bad slices, there are only three bad slices beginning with **. By the pigeonhole principle, we may thus assume that **11**, **13**, **31**, **33** are good. But now on applying Lemma 14 and Corollary 15 again we conclude that there are four more bad slices beginning with **, contradiction.

From this and the score analysis we see that

Corollary 17 In a 355-point set, exactly three of the four slices 11****, 13****, 31****, and 33**** are good, and the bad slice is a 352-score set.

In particular, one cannot have two parallel bad corner slices. Combining this with Corollary 13, we see that two adjacent parallel good corner slices must necessarily have opposite types. Combining this with Corollary 17, we obtain an opposing pair of parallel good corner slices of the same type, which is not possible by Lemma 14. Thus a 355 point set cannot exist.

We now refine the analysis further, with the aim of eliminating 354-point sets.

Lemma 18 Suppose the 11**** and 13**** slices are good with types xyzw and x'y'z'w' respectively. If x=x', then the 1*x*** slice has score at most 326 (defect at least 30), and the 1*X*** slice has score at most 348 (defect at least 8). Also, the 1**1**, 1**3**, 1***1*, 1***3*, 1****1, 1****3 slices have score at most 350 (defect at least 6). In particular, the total defect of slices beginning with 1* is at least 74.

Proof The 1*x*** slice has eight "a" points, while the 1*X*** slice has only four. The other six slices mentioned have six "a" points and at most seven "d" points, and cannot be good by Corollary 12. The claim now follows from the Pareto optimal list.

Corollary 19 A 354-point set cannot have all four slices 11****, 13****, 31****, and 33**** slices be good.

Proof Suppose not. By Lemma 14, the 11**** and 33**** slices cannot be of the same type, and so they cannot both be of the opposite type to either 13**** or 31****. If 13**** is not of the opposite type to 11****, then by (a permutation of) Lemma 18, the total defect of slices beginning with 1* is at least 74; otherwise, if 13**** is not of the opposite type to 33****, then by (a permutation and reflection of) Lemma 18, the total defect of slices beginning with *3 is at least 74. Similarly, the total defect of slices beginning with 3* or *1 is at least 74, leading to a total defect of at least 148. But a 354 point set has a total defect of 120, contradiction.

One can divide the 60 slices into fifteen families of four depending on their frozen coordinates, for instance one families of four is 11****, 13****, 31****, 33****. We'll call this family the ab**** family, and similarly define the a*b*** family, etc.

Corollary 20 A 354-point set can have at most one family with a total defect of at least 38.

Proof Suppose there are two sets with defect at least 38. The remaining thirteen sets have defect at least 4 by Corollary 19, leading to a net defect of 38*2+13*4=128. But 354-point sets have a net defect of 120, a contradiction.

Proposition 21 A 354-point set cannot have any family with a total defect of at least 38.

Proof Suppose for contradiction that the ab**** family (say) had a total defect of at least 38, then by Corollary 20 all other families have total defect at least 38.

We claim that the **ab** family can have at most two good slices. Indeed, suppose the **ab** has three good slices, say **11**, **13**, **33**. By Lemma 14, the **11** and **33** slices cannot be of the same type, and so cannot both be of opposite type to **13**. Suppose **11** and **13** are not of opposite type. Then by (a permutation of) Lemma 18, one of the families a*1***, *a1***, **1*a*, **1**a has a net defect of at least 38, contradicting the normalisation.

Thus each of the six families **ab**, **a*b*, **a**b, ***ab*, ***a*b have at least two bad slices. Meanwhile, the eight families a*b***, a**b**, a***b*, a****b, *ab***, *a*b**, *a**b*, *a***b have at least one bad slice by Corollary 19, leading to twenty bad slices in addition to the defect of at least 38 arising from the ab**** slice. To add up to a total defect of 120, this means that all bad slices outside of the ab**** family have a defect of four, with at most one exception; but then by Lemma 18 this shows that (for instance) the 1*1*** and 1*3*** slices cannot be good unless they are of opposite type. The previous argument then shows that the a*b*** slice cannot have three good slices, which increases the number of bad slices outside of ab**** to at least twenty-one, and now there is no way to add up to 120, a contradiction.

From Proposition 21 and Lemma 18 we conclude

Corollary 22 In a 354-point set, the slices 11**** and 13**** can only be good if they have opposite type.

From this and Lemma 14 we conclude

Corollary 23 In a 354-point set, every family can have at most two good slices, and thus have a defect of at least eight.

Since 120 = 15*8, we conclude

Corollary 23 In a 354-point set, every family consists of exactly two good slices, plus two bad slices of defect exactly four.

Now we look at the statistics of center slices of 4D slices (e.g. the 112*** stats of the 11**** slice). Computer search has revealed the following

  • For a (6,12,18,4,0) slice, the central slice must be (3,9,3,0). [The other two slices are (4,3,3,1) and (2,6,6,0).]
  • For a (5,12,18,4,0) slice, the central slice must be (3,9,3,0). [The other two slices must add up to (5,9,9,1).]
  • For a (5,12,12,4,1) slice, the central slice must be (3,6,3,1). [The other two slices must add up to (5,9,6,1).]
  • For a (6,8,12,8,0) slice, the central slice must be (2,6,6,0). [The other two slices must add up to (6,6,6,2).]

Now we look at a side 3D slice, e.g. 111***. Because at least two of 11****, 13****, 31****, 33**** must be of type (6,12,18,4,0), and such slices have 3D side slices of (4,3,3,1) and (2,6,6,0), we know that the 111*** slice must be adjacent to either a (4,3,3,1) slice or a (2,6,6,0) slice. From the above list, we thus see that 111*** is one of the following possibilities:

  1. It is a slice of a (6,12,18,4,0) set, and is therefore either (4,3,3,1) or (2,6,6,0).
  2. It is a (3,3,3,1) slice of a (5,12,18,4,0) set, with the opposing slice being (2,6,6,0).
  3. It is a (1,6,6,0) slice of a (5,12,18,4,0) set, with the opposing slice being (4,3,3,1).
  4. It is a (3,3,0,1) slice of a (5,12,12,4,1) set, with the opposing slice being (2,6,6,0).
  5. It is a (1,6,3,0) slice of a (5,12,12,4,1) set, with the opposing slice being (4,3,3,1).
  6. It is a (2,3,3,1) slice of a (6,8,12,8,0) set, with the opposing slice being (4,3,3,1).

Furthermore, in all six cases, the opposing slice is a subslice of a (6,12,18,4,0) set.

Possibility 6 has been eliminated by computer, and possibilities 4,5 have been eliminated by hand. As a consequence, the only possible 3D slices are (4,3,3,1), (2,6,6,0), (3,3,3,1), and (1,6,6,0). This eliminates the (5,12,12,4,1) case.

The (6,8,12,8,0) case can also be eliminated: if (say) 11**** is (6,8,12,8,0), then 111*** and 113*** must now be (3,3,3,1), which forces the 1*1*** and 1*3*** slices to be bad, and hence the 3*1*** and 3*3*** slices are good, hence 311*** and 313*** must be (2,6,6,0) (note that we have no way of matching (3,3,3,1) to (4,3,3,1)), but then there is no consistent choice for the 31**** slice.

The only possible side slices of a (5,12,18,4,0) set are (4,3,3,1)+(1,6,6,0) and (3,3,3,1)+(2,6,6,0). In particular, it contains exactly one of any opposing "d" points (e.g. 1222 and 3222). Similarly for (6,12,18,4,0) sets. We conclude that the same is true for the 6D set, e.g. exactly one of 111222 and 113222 lie in the set.

We can define the notion of the "type" of a (5,12,18,4,0) set just as with a (6,12,18,4,0) set. The above observation forces any two adjacent slices (e.g. 11**** and 13****) to have opposing type, and thus any two diagonally opposite slices (e.g. 11**** and 33****) have identical type. By Lemma 14, such slices cannot both be good. Splitting each family into two pairs of diagonally opposing slices, we thus conclude

Proposition 24 In any two diagonally opposite slices of a 354-point set, one slice is (6,12,18,4,0) and the other is (5,12,18,4,0), and both slices have the same type.

On averaging, we see that the 354-point set has statistics (22,72,180,80,0,0,0).

Theorem 25 [math]\displaystyle{ c'_6 = 353 }[/math].

Proof We repeat the previous argument that there is no 356-point set. Suppose for contradiction that we have a 356-point set, i.e. one in which all corner slices are good. From the above discussion, we see that if the 111*** slice contains its center 111222, then the 113*** slice does not, and vice versa. 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 (22,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.

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. More information on these results are stored here. Note that the optimal values are found for n=1 to 4, but the value 122 is below the n=5 optimum value of 124.

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:

One 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, in the Fujimura-type problem described above.

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}{\lfloor n/2\rfloor} 2^n + \binom{n}{\lfloor n/2\rfloor-1} 2^{n-1} }[/math]

The following set improves this bound to [math]\displaystyle{ (2+o(1))\binom{n}{\lfloor n/2\rfloor} 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{ \sqrt{\frac{8}{n\pi}}4^n }[/math] by Stirling's formula.

For k=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.

Retrieved from "https://michaelnielsen.org/polymath/index.php?title=Moser%27s_cube_problem&oldid=9743"