Human proof of the 3D Pareto-optimal Moser statistics

From Polymath1Wiki
Jump to: navigation, search


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

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

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.

A Moser set with statistics (5,5,3,0) cannot be realized. First we note that two of the points of type c cannot have the same c-statistic. If they did then we could slice on the coordinate where the two points do not equal 2. Then both side squares would have their center points and the number of points of type a on both would be limited to 2 which is less than 5. So without loss of generality we can assume the three points of type c are (1,2,2), (2,1,2) and (2,2,1). We cut along the first coordinate. If the the square with first coordinate equal to three has four points of type a then these points will block all the points of type b in the square and since the other side square has its center point it can only have two points of type b there must be three points of type b in the center square of the slice. But since that square contains (2,1,2) and (2,2,1) it cannot contain (2,1,1) as then it would block two points of type a and we need three of these in the center slice. So the points in the center slice of type a must be the other three besides (2,1,1) and in combination with the four points of type a in the square with first coordinate equal to three they block all points in the square with first coordinate equal to one except (1,1,1). But one together with the points (2,1,2) and (2,2,1) it blocks two points of type a in the square with first coordinate equal to three but that square must have all of its points of type a and we get a contradiction and we are done.

Then since the square with first coordinate equal to one has its center point and only contains at most two points of type a the other side slice must have at least three points of this type. But since we have ruled out four of these points above the only distribution left is 2 points of type a in the square with first coordinate equal to 1 and three of this type in the other side slice. If the square with first coordinate equal to one has contains the point (1,1,1) the with (2,1,2) and (2,2,1) it will block two points of type a in the other side slice which gives a contradiction.

Since the square with first coordinate equal to 1 must have two points of type a it must have at least one on each diagonal so it must have the point (1,3,3). Now if the square with first coordinate equal to three contains (3,1,1) then with the points (2,1,2) and (2,2,1) it will block two points of type a in a diagonal on the other side cube but that will limit the number of points of type a in that cube to one which gives a contradiction so it cannot contain the point (3,1,1) and so it must contain all other points of type a. These include (3,3,3) which together with (1,3,3) which we have also shown to be in the Moser set blocks (2,3,3). Now if the center slice contains (1,2,2) it will block all points except (2,3,3) which is already blocked so the only way the center slice can have two points with one 2's is if has (2,1,3) and (2,3,1) but these together with (3,1,3) and (3,3,1) block all the points of type a in a diagonal in the square with coordinate one. This forces two points in the other diagonal in order to have two points of type a but this forms a line with the center point of that square. So there is only one point of type b in the center slice.

The square with coordinate 1 can only have at most two points of type b since it has its center point. The other side slice can only have two as we know what the points of type a in that square are and the block two points of type b. The center square can only have one point of type b. Given the above the only way 5 points of type b can be reached is for each of the side slices to have two such points and the center slice to have one. The square with first coordinate three must have the points (3,1,2) and (3,2,1) as all the others are blocked by points of type a. These with the points (2,1,2) and (2,2,1) block the points (1,1,2) and (1,2,1). For the square with first coordinate one to have two points of type b it must contain (1,3,2) and (1,2,3) which together with the point (1,3,3) block the points (1,3,1) and (1,1,3) which together with the fact already shown that (1,1,1) cannot be in the set limits the number of points of type a in the square with first coordinate equal to one to one which eliminates the last case and we are done.

A Moser set with statistics (6,0,3,0) cannot be realized. First we note that two points of type c cannot have the same c-statistic. If they did we could slice along the coordinate not equal to 2 in both points and get two side slices with their center points both would have two or less points of type a but we must have six such points contradiction. So without loss of generality we can take these points to be (1,2,2), (2,1,2) and (2,2,1). We slice along the first coordinate. If the square with first coordinate equal to three has four points of type a then it must contain (3,1,1) this with (2,1,2) and (2,2,1) blocks (1,1,3) and (1,3,1) but this forces the points of type a in the square with first coordinate equal to one to lie and a diagonal and due to the presence of the center point limits there number to one and the total number of such points to 5 but we must have six so we have a contradiction, so the square of side three must have three or less such points but the other side square is limited to two such points due to the presence of its center point. This limits the number of points of type a to 5 but we need six so we have disposed of all cases and this set cannot be realized.

A Moser set with statistics (3,8,4,0) cannot be realized. Since there are 4 points of type c two must have the same c-statistic. Without loss of generality say these points are (1,2,2) and (3,2,2). Slice along the first coordinate. The two side squares can only have two points of type b each since they both have their center points. To have 8 points of type b the center slice must have all four of its corner points but these block all points of type c in the center slice and since there are a maximum of two such points in the side slices we have less than four and we are done.

A Moser set with statistics (4,7,4,0) cannot be realized. Since there are 4 types of type c two must have the same c-statistics. Without loss of generality say these points are (1,2,2) and (3,2,2). Slice along the first coordinate. There are at most two points of type b in both side slices for a maximum total of four. Thus there must be three points of this type in the center slice which means that it must have three of its corner points in the set. The only possible spots for points of type c in the central slice are the two spots adjacent to the missing corner point of the center slice. These must be filled as we have 4 points of type c and only two in the side slices. Without loss of generality say the missing corner point is (2,1,1) and the two adjacent points of type c are (2,2,1) and (2,1,2). Then of the pairs (3,1,3) and (1,1,3), (3,1,3) and (1,1,3), (1,3,1) and (3,3,1) the set can have only one point in each pair because the three corners in the center slice would form a line with any complete pair. Thus the set must have one of the two points (1,1,1) or (3,1,1). If it has (1,1,1) with (2,2,1) and (2,1,2) it would block all the points of type a in a diagonal in the square with first coordinate equal to 3. But that would force points of type a in that square to a diagonal and limit there number to one limiting the total number of such points in the set to three giving a contradiction. If it has (3,1,1) with (2,2,1) and (2,1,2) it would block all the points of type a in a diagonal in the square with first coordinate equal to 1. But that would force points of type a in that square to a diagonal and limit there number to one limiting the total number of such points in the set to three giving a contradiction. So we have exhausted all cases and we are done.

A Moser set with statistics (5,0,4,0) cannot be realized. Since there are 4 points of type c two must have the same c-statistic. Without loss of generality we can say these points are (1,2,2) and (3,2,2). Slice along the first coordinate then the two side slices have their center points and hence have at most 2 points of type a each but we need five such points so have a contradiction and we are done.

A Moser set with statistics (3,7,5,0) cannot be realized. Since there are 5 points of type c two must have the same c-statistic. Without loss of generality let them be (1,2,2) and (3,2,2). Slice on the first coordinate. Then both side squares have their center points and hence must have at most two points of type a and three must be in the center slice. Also since only two of the points of type c are on the side slices three must be in the center slice. However if three of the points of type a are in the center slice they fill three of the four corners and block two of the points of type c. So there are at most two points of type c in the center slice but we must have three and so we have a contradiction and we are done.

A Moser set with statistics (4,5,5,0) cannot be realized. Since there are 5 points of type c two must have the same c-statistic. There must be one other such pair and one unpaired point. Without loss of generality we can say the five points are (1,2,2),(3,2,2),(2,1,2),(2,3,2), (2,2,1) with (2,2,3) the missing point of type c. We slice on the first coordinate. Each side slice gets its center point and hence can have at most two points of type a one on each diagonal. Now the points (1,1,1) combines with (2,2,1) and (2,1,2) to block (3,3,1) and (3,1,3) but that combined with the fact that these points are on a diagonal and we must have at least one point in each diagonal of type a gives a contradiction. By the same method the points (1,1,3),(3,1,1), and (3,1,3) are forbidden. This and fact that we must have four ponts of type a means we must have the points (1,3,1),(1,3,3),(3,3,1) and (3,3,3).

These points block the points (2,3,1) and (2,3,3) in the center slice. Only one of the remaining points of type a can be in the set since if both are in the set the point (2,2,3) would form a line with them. So the the center set there is at most one point of type b. To get five we must have two on each side slice. The points of type b on the side slices lie on pairs on two lines with the center. There must be one in each line for there to be two such points. In particular there must be one on the lines (1,1,2), (1,2,2), and (1,3,2) and (3,1,2), (3,2,2), and (3,3,2). But the points (1,3,2) and (3,3,2) are blocked by the points of type a in each slice. So we must have the points (1,1,2) and (1,3,2) but we cannot have these ponts because they form a line with the point (1,2,2). So we have a contradiction and we are done.

A Moser set with statistics (3,6,6) cannot be realized. We slice on the first coordinate. Both center points will be in both side slices because we have all points of type c. Because of this both side slices must have two or less points of type a. One must have only one such point. Without loss of generality say this slice is the square with coordinate one and the point is (1,1,1). Then with the points (2,1,2) and (2,2,1) it blocks the points (3,1,3) and (3,3,1) but that means that the square with side three which must have two points of type a must have them both on the diagonal (3,1,1),(3,2,2) and (3,3,3) but then they will form a line with the center point. So we have a contradiction and we are done.