DHJ: Still writing the second&nbsp;paper

14 June, 2009 at 12:31 pm

A set with statistics. (6,12,18,4,0) cannot have two points of type d with the same c-statistic. If it does say the coordinate of both points which is not equal to 2 is one then slice on that coordinate there result will be that both side slices will have their center point and can have at most three points of type c. So the remaining 12 must be in the center slice. But there they will block all points of type d but the only remaining spaces for these points are the outside slices and there are only two such spaces there and we need two so there is a contradiction.

Now without loss of generality taking in account the above we can take the points of type d to be (1,2,2,2), (2,1,2,2),(2,2,1,2) and (2,2,2,1) . We slice on the first coordinate. Then the cube with first coordinate equal to one contains its center point and can only have three points of type c. The center cube contains the remaining points of type d and hence can contain 9 of the remaining points of type d. The rest must be in the remaining slice. It must contain all its points of type c. But we could have cut along any coordinate thus the set contains all points of type c with one coordinate equal to 3. This accounts for all 18 of its points.

With this I think we can show that four dimensional slice of a six dimensional Moser set with its coordinates equal to 1 or three cannot be equal to this set. If this occurs then when two slices differ by cooridinate not equal to 2 and intersect in a cube that has all of its points of type c the other side cube in both sets will have its center point and three such points. If they intersect in a slice that does not have all of its points of type the other side cube of both sets will have all of its points of this type. In this all cubes which have the same two coordinates equal to two that the original two intersecting slices will have either all of their points of type c or one depending on the parity of the difference from the orginal cube formed by the intersection of the original 4 dimensional slices. But we can get a contradiction because we can find a set that contains all of the points of type d as the extra 2’s wipe out the parity difference. Then we can find two that have the same c-statistic and get a contradiction as above.

I originally looked at this to try to find the above proof but I ought to be able to use the above information to find out more about the sets with statistics (6,12,18,4,0).

I have looked at the (6,18,24,0,0) slices mentioned at the end of the previous thread and I don’t think that they can be realized as 4 dimensional Moser sets. They are not listed in the table of Pareto extremizers and it looks like the density of points of type b is over 1/2 while the density of points of type c is 1 which would seem to give a contradiction.

14 June, 2009 at 3:14 pm

Sorry, that was a typo: I meant (6,12,18,4,0) instead of (6,18,24,0,0). Thus:

The score 4a+6b+10c+20d+60e is maximised at 356 at (6,12,18,4,0), and equals 352 for (5,12,18,4,0), (5,12,12,4,1), and (6,8,12,8,0). All other feasible statistics have score at most 350.

One example of a (6,12,18,4,0) set comes from taking the strings 1111, 1113, 3333, 1332, 1322, 1222 and all permutations. I am tentatively conjecturing that, up to symmetries, this is the only such set.

14 June, 2009 at 4:12 pm

Kristal Cantwell

Shouldn’t that be 1111, 1113, 3333, 1332, 1322, 1222 with the addition of 3322 with all permutations? I think the addition of the 3322 term is needed to make it (6,12,18,4) otherwise it would be (6,12,12,4,0). In any case I will be looking at these sets and your conjecture.

14 June, 2009 at 4:47 pm

Yes, this is what I meant. From the scanning code (which only detected the (6,12,18,4,0) statistic once, in the scan region 249) it does seem that this particular statistic is extremely rare, but I think one should be able to obtain a human proof of this fact fairly easily, without reliance on computer data.

14 June, 2009 at 5:42 pm

Kristal Cantwell

I think I will be able to get all instances of this soon. I think I can force all points of type c, d and a into a certain pattern. I am still working on the points of type b I suspect I will be done soon. I think a human proof is doable.

14 June, 2009 at 7:12 pm

Michael Peake

A long time ago, Kristal suggested a middle ground between (a,b,c,d) statistics and c-statistics, where you count the points with the same number of 1s, same number of 2s and same number of 3s. However I jumped up and down on the idea. I was wrong to do that, firstly because it was an idea and secondly because it was a good idea that I didn’t follow. I am sorry Kristal. Would these statistics help now?

14 June, 2009 at 9:30 pm

http://twofoldgaze.wordpress.com/2009/03/10/353-element-solution/

Speaking of ideas from long ago, I just now realised that the score argument I mentioned at the end of the last thread was in fact proposed by Michael way back in 904! But we only had the 41, 42, 43 point data then, and couldn’t push it through…

I crunched the numbers on Kareem’s example at

The stats are (22, 66, 165, 100, 0, 0 0). If we look at 11xxxx, 13xxxx, 31xxxx, 33xxxx slices, they split as (6,8,12,8,0,0), (5,12,18,4,0), (5,12,18,4,0), (6,12,18,4,0). In fact all of the $\binom{5}{2}=20$ different ways to slice the set give exactly the same four statistics; one slice is always the 356-score statistic (6,12,18,4,0) and the other three are 352-score statistics, for a net average of 353, which unsurprisingly is the cardinality of the example.

If the putative 354 and 355 point Moser sets can be proven to exhibit similar behaviour, then perhaps the way to proceed is to classify all the 352 and 356 score sets in 4D, and then do a brute force computer search over all possibilities of the 11xxxx, 13xxxx, 31xxxx, 33xxxx slices.

15 June, 2009 at 12:11 pm

15 June, 2009 at 12:13 pm

I think I can show that there is only one set of type (6,12,18,4,0) up to the various permutations.

end of part 1

15 June, 2009 at 12:14 pm

Part 2 of proof that there is only one set of type (6,12,18,4,0) up to the various permutations:

Now for the points of type a. There can only be two points of type a in the slice with first coordinate equal to three as any two points that don’t block a line block the remaining points. So there must be four in the other side slice. Now if the point (1,1,3,3) is in the set then it will block all points except (1,1,1,1), (1,1,3,1), (1,1,1,3) and (1,3,3,3) and (3,1,1,1), (3,1,3,1) and (3,1,1,3) and (3,3,3,3). To have four points in the slice with first coordinate equal to one it must contain one of (1,1,3,1) and (1,1,1,3)
But either of these together with (1,1,3,3) will block all but one of the points in the slice with first coordinate equal to three but we need to so we have a contradiction. And by a similar argument we can deal with all points of the which are permutations of (1,1,3,3).

If the point (1,3,3,3) is in the set it will block all points which are permutations of (1,1,1,3) and (1,1,1,1) and to get four points in the slice with first coordinate equal to one we will need points which are permutations of (1,1,3,3) but that leads to contradictions as noted above.

So the only way to have four points in the side slice with first coordinate equal to one is to have the points (1,1,1,1), (1,1,1,3), (1,1,3,1) and (1,1,1,3).

These points block all but he points (3,1,1,1) and (3,3,3,3) these can be included and we need them to have six points so we add them and we have our six points of type a.

15 June, 2009 at 12:33 pm

Part 3 of proof that there is only one set of type (6,12,18,4,0) up to the various permutations:

Now we need to get the points of type b. We can include all points which are permutations of (1,3,3,2) and get 12 points so we need to show that any deviation from this leads to less points. Let us look at the 8 points of type a which have the first coordinate equal to 2 we will show that the only way to have three points in that set is if they all are permutations of (1,3,3,2). Assume we have a point with two ones say (2,1,1,3) we will have the points (2,2,1,3) and (2,1,2,3) in the set from the above result on points of type b. They will block (2,3,1,3) and (2,1,3,3). The points (2,1,2,2) and (2,2,1,2) will be in the set from our discussion of points of type d. They will block (2,1,3,1) and (2,3,1,1). So the only points left are (2,3,3,1), (2,3,3,3)
And (2,1,1,1) but (2,1,1,1) is blocked by (1,1,1,1) and (3,1,1,1).
So we must have both of (2,3,3,1) and (2,3,3,3) but (2,3,3,2) is in our set as noted in our discussion of points of type c. So we can have only one of the two. So the only way we can have three points in the set is if we have the three permutations of (1,3,3,2) in the set.
Similar arguments apply to the other sets with one fixed coordinate equal to two and the rest not equal to two. Thus the only set of points of type b that works is the permutations of the points (1,3,3,2) and we are done.

15 June, 2009 at 10:34 pm

Kristal, this morning I started up an integer programming run for n=6 where I have added the condition that the statistics must be (6,12,18,4,0). So far it has eliminated a large number of subcases, and I hope it will finish the rest during the night, but only found one solution.

15 June, 2009 at 9:24 pm

Mohammad

that make me confiused :S

i’ll try to find solution

thanks :)

Dear Kareem and Klas,

Thanks! It looks like the (6,12,18,4,0) solutions will be classified by two independent means.

I’ve been looking a bit at what 355-point Moser sets would look like. The average score 4a+6b+10c+20d+60e of the 60 slices of 11**** type is 355, which means (from the Pareto statistics) that at least 45 of these slices have to be of the (6,12,18,4,0) type (which have score 356), with all other slices having score 352 or less. This means that one of two possibilities holds:

1. There exists four parallel slices of 11**** type (e.g. 11****, 13****, 31****, 33****) which all have statistics (6,12,18,4,0). [In particular this forces a=24.]

2. For each of the 10 ways to create four parallel slices of 11**** type, three of those slices have statistics (6,12,18,4,0), while the last slice has score 352 (and thus has statistics (5,12,18,4,0), (5,12,12,4,1), or (6,8,12,8,0)). [In particular this forces a=24 or a=23.]

Presumably the classification of (6,12,18,4,0) slices will help in analysing these two cases further. Note that the (6,12,18,4,0) slice has 40 points, and the (5,12,18,4,0) slice has 39 points, but the (5,12,12,4,1) and (6,8,12,8,0) only have 34, so it may be relatively easily to eliminate the latter. (It also seems desirable to eliminate the “e” points once and for all. The linear inequalities are only able to establish the bound $e \leq 2$ for 355-point Moser sets.)

I also looked at the 12**** slices. The analogous score here, let’s call it 12****-score, is 12a+15b/2+20c/3 + 15d/2; the average 12**** score of a 6D Moser set is its cardinality minus the “a”-points, which in the case of 355-point sets is either 331 or 332.

Unfortunately the scoring isn’t quite as favourable here. The largest 12**** score is 336 (attained at (8,32,0,0,0)), followed by 334 (attained by (7,28,6,0,0), 332 (attained by (6,24,12,0,0)), and 330 (attained by (5,20,18,0,0)), and then they start piling on quickly after that. The (8,32,0,0,0) slice looks rather unlikely, but the other ones look like real possibilities.

For comparison, with Kareem’s 353-point example, the ab**** slice statistics are

(5,12,18,4,0) (6,24,12,0,0) (6,12,18,4,0)
(5,20,18,0,0) (11,20,0,0,0) (6,24,12,0,0)
(6,8,12,8,0) (5,20,18,0,0) (5,12,18,4,0)

in fact all ten ways of slicing the example give some reflection or rotation of these statistics, so Kareem’s example is actually rather symmetric. (It might be illuminating to find a good description of this example.)

16 June, 2009 at 1:23 am

http://twofoldgaze.wordpress.com/2009/03/15/visualizing-solutions-i/

My integer program finished during the night. The program looked for solutions for n=6 with size at least 353, where each slice with two coordinates fixed to 1 has the right statistics. It found that there is just one such solution, which has size 353,
The solution is here
http://abel.math.umu.se/~klasm/Data/HJ/solution-n=6-k=3-moser-6_12_18_4_0

However, in this solution the 33**** slices do not have the right statistics

16 June, 2009 at 2:19 am

Michael Peake

So putting the last two posts together, it follows that c’_6 = 353. To get a score above 352, at least one corner is (6,12,18,4,0), and Klas shows there is therefore just one solution

16 June, 2009 at 3:08 am

Michael Peake

The 353-point solution is 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)

16 June, 2009 at 4:15 am

Thomas Sauvaget

Here is a picture of this 353-point solution
http://thomas1111.files.wordpress.com/2009/06/moser353new.png

It has indeed some symmetry in it, more precisely it is of the form
A B C
B D E
C E F
where each letter represents a pattern (subset of $[3]^4$ ) and where both patterns B and F have invertion symmetry throught their center, while A, C, D and E are symmetric wrt their first diagonal.

16 June, 2009 at 6:23 am

Kareem Carr

I had actually produced several examples of size, 353. The above link gives images of three of them. It had slipped my mind but I should have them on my drive somewhere. I will make them available shortly.

16 June, 2009 at 6:34 am

Hmm, it is interesting to see the Gamma cells emerge for the Moser problem at last; they have of course been of major importance in the DHJ problem but had not been so useful for Moser (in large part because they don’t respect the symmetries of the cube). I wonder if we can improve the $n=7$ lower bound of 988 using Gamma cells?

Unfortunately we are not yet done in showing $c'_6=353$ , although given how pretty and symmetric the 353-point example, one can begin to conjecture that this is the case. The score argument tells us that there are many 11***-type slices of statistic (6,12,18,4,0) (in fact, for 355-point sets, at least 45 of the 60 such slices must have this statistic, and for 354-point sets, at least 30 must), but this does not quite put us in the situation assumed in Klas’s program (in which the ten slices 11***, 1*1**, 1**1*, 1***1, *11**, *1*1*, *1**1, **11*, **1*1, ***11 are all assumed to have statistic (6,12,18,4,0)), at least if I understand Klas’s description correctly.)

But perhaps we can get by with less. For instance, suppose we assume that the 11*** and 33*** slices are both (6,12,18,4,0), and that there are at least 354 points (or, if we are feeling less ambitious, assume there are exactly 355 points). Can we get the integer program to get a contradiction? I’m guessing that these are too few constraints for the program to run in a reasonable amount of time, but we can reduce the amount of work by using the classification of (6,12,18,4,0)-sets. Kristal showed that there is exactly one such set with d-points 1222, 2122, 2212, 2221; more generally, by reflection symmetry, given $x,y,z,w \in \{1,3\}$ , there is exactly one (6,12,18,4,0) point with d-points x222, 2y22, 22z2, 222w. Let’s call this the [xyzw] (6,12,18,4,0)-set; this describes all 16 such [xyzw] (6,12,18,4,0)-sets. If we are assuming that the 11*** and 33*** slices are both (6,12,18,4,0) sets, then by all the symmetries we may assume that the 11*** slice is the [1111] (6,12,18,4,0) set, and the 33*** slice is either the [1111], [1113], [1133], [1333], or [3333] (6,12,18,4,0)-set. So we have five cases to check, and in each of which we have pinned down $2 \times 3^4 = 162$ of the $3^9 = 729$ cells completely, which should help. We also already know that f=g=0, which eliminates 13 more cells. (It would definitely help if we could show e=0, as is the case with the known 353-point examples; this would eliminate 58 more cells.)

If we can eliminate this case when two diagonally opposite slices are both (6,12,18,4,0), then this kills off the 355-point case, and puts severe restrictions on the 354-point case (every antipodal pair of slices must have exactly one (6,12,18,4,0) slice). If one can eliminate this case under the additional hypothesis that the 13**** slice is also (6,12,18,4,0), then this disposes of the 355-point case at least, and puts non-trivial restrictions on the 354-point case. If one can eliminate under the additional hypotheses that 13**** and 31**** are all (6,12,18,4,0), then this is a significant advance on the 355-point problem (it forces us into Case 2 of my 15 June 10:34pm comment).

16 June, 2009 at 6:41 am

It may also be better to work with transverse slices rather than parallel ones. For instance, suppose we assume that 11****, 1*1***, and *11*** are all (6,12,18,4,0); by symmetry we can reduce to this situation in the 355-point case by the pigeonhole principle, and one can almost reduce to this situation in the 354-point case (because a triangle-free graph cannot have more than half of the edges, by Turan’s theorem). These 16-point slices intersect each other in 8-point subspaces, and so there should be a lot of compatibility conditions between the [xyzw] types of these three slices in order for them to fit together properly. Furthermore, the lines between these three slices then put constraints on several other parts of the cube $[3]^6$ . So this may be another way to proceed.

16 June, 2009 at 6:54 am

It occurs to me that the Moser problem, when specialised to unions of $\Gamma_{a,b,c}$ cells, becomes a Fujimura-type problem but in which one has to forbid isosceles triangles $(a+r,b,c+s), (a,b+r+s,c), (a+s,b,c+r)$ rather than equilateral triangles, and each point $(a,b,c)$ is weighted by the cell cardinality $\frac{n!}{a!b!c!}$ . (In particular, one has to exclude vertical line segments $(a+r,b,c+r), (a,b+2r,c)$ , thus each value of $c-a$ can have at most one cell. It may thus be quite computable, even by hand, to work out what the best 7D construction is by this method, especially since some of us have some Fujimura practice already…

16 June, 2009 at 8:03 am

http://twofoldgaze.wordpress.com/files/2009/06/353-examples.pdf

My program assumed that each slice of the form 11**** and permutations thereof had the given statistics. This gives 15 different slices and an indentify for the statistics vector for each of them.

It is fairly easy to change these conditions in the integer program, but as always it is hard to say how the running time will be affected.

16 June, 2009 at 8:32 am

Kareem Carr

Here are the additional sets of size 353 that I promised. There are 26.

16 June, 2009 at 10:28 am

Michael Peake

I think the following Gamma sets work to give a set of 1008 points for c’_7
(610),(520),(430),(502),(331),(322),(313),(223),(133),(205),(034),(025),(016)

16 June, 2009 at 11:29 am

Michael Peake

The following pattern of Gamma sets will give a one-third improvement over the bound $\binom{n+1}{q}2^{n-q}$ when n is large.
Take two cells in every three from the #2=q and #2=q-1 layers, and one cell in every three from the #2=q-2 and #2=q-3 layers. The Gamma cells in the #2=q-2 layer match the gaps in the q layer, and the cells in the q-3 layer match the gaps in the q-1 layer.
You get to pick q so, for large n, you get roughly twice the sum of the largest layer.

16 June, 2009 at 11:45 am

16 June, 2009 at 11:49 am

Dear Michael: nice! This may well be close to the limit of the Gamma method for Moser sets. One can’t pick two cells $(a+r,b,c+r), (a,b+2r,c)$ on the same vertical line, so it seems one can’t hope to do any better than two rows worth of Gamma’s, i.e. roughly twice the size of the largest layer. It should be possible to make this rigorous using Stirling’s formula; that would be a nice addition to the paper. (On the other hand, it looks like the Gamma method is unable to reproduce the 124-point 5D Moser set example, though this should be checked. It may be that the correct optimum is some combination of Gammas plus a sphere packing of an outer layer or two, a little bit like a layer cake with frosting.)

A side remark: computing slices of a union of Gamma sets (e.g. the 12**** slice of a 6D set) can be done easily: plot the points on the triangle $\Delta_n = \{(a,b,c): a+b+c=n\}$ corresponding to the occupied Gamma sets, and then pass to a subtriangle. In particular, slices of Gamma sets are again Gamma sets.

By the way: Jozsef Solymosi just contacted me and invited us to submit this paper to the proceedings of a conference next year in honour of Endre Szemeredi’s 70th birthday. I think this would be quite suitable and am in favour of this. (The deadline for submission would be April 2010; given our current rate of progress in writing up, I don’t believe that we will have difficulty making this deadline.)

16 June, 2009 at 12:05 pm

Dear Kareem: thanks for the stats! (I guess wordpress does not support uploading of raw txt files, which is a pity, but the files should still be scrapeable, I think.) It seems that none of the examples have any e-points (I searched for 2222 and came up empty), and so perhaps a key step trying to show that no 354 or 355 point Moser sets exist is to show that e=0. (A sub-problem would be to get a human proof that f=0; currently the only proof I know is through the Maple calculations. I managed at least to show that g=0 by human means, the proof is on the wiki at http://michaelnielsen.org/polymath1/index.php?title=Moser%27s_cube_problem ). Perhaps some further playing around with various scores of slices will settle this issue.

16 June, 2009 at 12:19 pm

Tomorrow I will try to adapt my program for Fujimura to the Moser-Fujimura version as well. It should not be too much work but its probably best if I don’t try do it now in the evening when I’m tired.

The proceedings volume sounds like a suitable place for this paper, so I too am in favour of that.

http://cid-b28d4245e5fea70c.skydrive.live.com/self.aspx/.Public/353%20Examples.txt

I am also in favor of submission to the proceedings volume.

16 June, 2009 at 2:15 pm

Kareem Carr

Hi Terry,

It took some digging around but I found a place to store the text file. I put the file here:

17 June, 2009 at 1:07 am

Could someone try to do the first few values for the Moser-Fujimura problem by hand?

I have a program for this problem now but I am getting oddly low values and a few independently generated values would be good in order to help track down the bug I suspect I have.

17 June, 2009 at 1:55 am

Michael Peake

Here are my results by hand
d N
1 2 = (100),(010)
2 6 = (011),(101),(110)
3 16 = (111),(201),(210),(012),(003)
4 42 = (004),(013),(022),(121),(211),(220),(400)
5 122 = (500),(401),(104),(005),(212),(221),(122),(230),(032)
6 355 = (610),(520),(430),(502),(331),(322), (313),(223),(133),(205),(034),(025),(016)

17 June, 2009 at 3:38 am

I fixed the problem, which was an incorrect bound for the new linear inequalites. The values are

n size
2 6
3 16
4 43
5 122
6 353
7 1017
8 2902
9 8622
10 24786
11 71766
12 212423
13 614875

I will post complete solution sets later.

17 June, 2009 at 5:37 am

Michael Peake

For what it’s worth, the ratio between this list and 3^n is close to 0.25+n^{1/3}

17 June, 2009 at 9:00 am

I have now computed the full solution sets, and the size for a few more values of n. I have added them to my table page here
http://abel.math.umu.se/~klasm/Data/HJ/

As you can see the number or optimal solutions is very small. I have not had time to look at the structure of the optima solutions but given the small number one could even hope that there is an extremal family with a nice description.

17 June, 2009 at 9:43 am

Klas and Michael: Thanks for the quick work!

It may be that, as I mentioned previously, one can squeeze a little bit more out of the Gamma cell method by using sphere packing. Consider one of Klas’s optimal configurations of Gamma cells $\Gamma_{a,b,c}$ . Being optimal, no further cell $\Gamma_{a,b,c}$ can be added, so any such cell must form an isosceles triangle with two existing cells.

If that triangle is non-degenerate, or if the new cell sits at the top (a,b+2r,c) of a degenerate isosceles triangle rather than at the bottom (a+r,b,c+r), then one cannot even add a single point from that cell without creating a line. But 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 $\Gamma_{a+r,b,c+r}$ 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.

It may be that this observation could explain the discrepancy between the 122 bound for 5D Gamma cell Moser sets, and the truth of 124. If we’re really lucky, it might also nudge up the 353 and 1017 lower bounds, which may make our work for computing $c'_6$ a bit easier.

18 June, 2009 at 2:37 am

Michael Peake

One can push up the number of points in $c'_8$ by four points, namely 11333333, 33113333, 33331133, 33333311.

18 June, 2009 at 3:35 am

Michael, that is interesting to see. Did you find this by hand or have you tested all possible additional points for n=8? Does this work for both of the n=8 Fujimura type solutions?

The integer program for the Moser-Fujimura problem was fairly simple to solve so I can push through a few more values of n.

18 June, 2009 at 3:58 am

I added the values for n=17…20, using the stable MIP-solver I have.
My current complete solver can not generate complete solution sets for these sizes.

18 June, 2009 at 4:32 am

The discussion just made me realise that there is one thing that I have forgotten to post here relating to older posts.
A while back I made a program which converts solutions for Fujimura’s problem into line free subsets of the cube. The bound this gae did not beat any of the bounds we already had for small values of n. Furthermore the different optimal Fujimura solutions for a given n gave a quite large span of different size for the line free sets, despite having the same equal-slices measure.

Now if one wants to use Fujimura type sets to construct large sets without combinatorial lines one should of course use a version where a point (a,b,c) is weighted according to the size of the cell it corresponds to, just as we have done for Moser sets.

I just implemented this modification and the first few values are

n weight #solutions

3 18 1
4 52 3
5 150 12
6 450 1
7 1302 12
8 3780 12
9 11340 1
10 32864 12

I will compute a few more and post a table and the solution sets.

18 June, 2009 at 4:55 am

18 June, 2009 at 10:46 am

I have now computed the optimal values for n up to 20 and the solution sets for n up to 10. I have added a new table for this problem and posted the solutions.
http://abel.math.umu.se/~klasm/Data/HJ/

18 June, 2009 at 8:47 am

Michael Peake

Klas,
I haven’t checked the full set of possibilities.
For the four extra points, I just noticed that (2,0,6) satisfied Terry’s suggestion. Any two points in the set are not allowed to differ in two places, so their 1s must be in disjoint places.
In the other pattern, (6,0,2) gives a similar set of four extra points.

Michael Peake

Your update of the Moser section for the paper looks good; however, the four extra points that I found are for $c'_8$ rather than $c'_7$ .

18 June, 2009 at 10:57 am

http://terrytao.wordpress.com/files/2009/06/polymath2.pdf

Oops! I think it is fixed now.

A new version of the PDF of the paper is at

incorporating much of the recent lower bound discussion; I haven’t touched the upper bound stuff yet given that it is likely to improve further. I also added Thomas’ picture, and a new argument showing that by using Gamma-cells one cannot asymptotically do much better than Michael’s construction which is approximately two slices thick.

NB The precise value of the set B in the 8D example is slightly off in the PDF draft, but I think I have reverted it on the wiki version to Michael’s values.

19 June, 2009 at 2:46 am

Michael Peake

A similar pattern would give an improved solution to the DHJ([4]^n) problem:
Gamma(a,b,c,d) cells with:
a = q, b+c != 2 mod 3
a = q-1, b+c != 1 mod 3
a = q-2, b+c != 0 mod 3
a = q-3, b+c = 2 mod 3
a = q-4, b+c = 1 mod 3
a = q-5, b+c = 0 mod 3

19 June, 2009 at 3:09 am

This morning I modified my integer program for Moser sets so that it can begin with an initial set and find the optimal way of adding additional points to the set.

For n=5 it found that one of the five solutions coming from the Fujimura problem can be extended to a set of size 124 in 25 different ways. The 124 point sets are here
http://abel.math.umu.se/~klasm/Data/HJ/solutions-n=5-k=3-Moser-ext

However according to this program the Fujimura based sets for n=6…9 can not be extended at all. So either there is a bug in my program or there is a line hiding in Michael’s proposed extension for n=8.

This Friday is a holiday in Sweden, Midsummer, so I probably wont do any more work on this until tomorrow.

19 June, 2009 at 3:12 am

Michael Peake

No, that’s not an improvement :(

19 June, 2009 at 3:24 am

Michael Peake

Sorry, I missed the isosceles triangle (1 0 7),(0 3 5),(2 0 6)

19 June, 2009 at 3:43 am

Michael Peake

I think that twelve points from (5,0,5) can be added to Klas’ first n=10 solution. That number 12 is A(10,5) on page 22 of the Jun18 version of our paper.

19 June, 2009 at 7:19 am

19 June, 2009 at 10:46 am

Well, I’m glad at least we have both human and computer approaches to these problems, as the redundancy seems to be quite helpful in cutting down errors.

Michael, can you edit the paper (and the spreadsheet) accordingly to reflect the corrections? I’m beginning to get a little confused as to what is proven and what is not…

19 June, 2009 at 7:40 am

Michael Peake

To the best of my knowledge, both the paper’s wiki and the spreadsheet are now correct.

The point (5,0,5) is directly below (3,4,3) which is in Klas’ solution.

An example of twelve points, no two of which differ in exactly four places, is the following.
1113313313
1331333111
1331133113
1133311313
3133113131
3133131131
3311311331
3113133131
3311111333
1331133311
1113331313
3311311133

Michael Peake

I don’t know how to show there are only twelve points of Gamma(5,0,5) that are not distance 4 from each other. I think A(10,5) in the paper is something else. It doesn’t matter too much because we only want to show that some such points exist.

Since our results are now better than Chvatel’s, do we need to describe the latter in the paper?

20 June, 2009 at 4:22 am

This morning I modified my program for creating the integer program input files to make it use less RAM, at the cost of begin a little bit slower. The input file for extending the n=10 Fujimura/moser sets is about 460Mb.

The program verifies that the optimal extension for n=10 is to a set of 24798 points, just as for the one Michael has found, and that both n=10 solution can be extended to that size. However because of the RAM requirements I cannot find the full set of extensions for n=10.

In order to be able to do the extension step for n=11 with my current programs I would have to install more RAM in the machine with the more advanced MIP-solver.

20 June, 2009 at 8:57 am

Michael Peake

I think you can get eighteen more points for n=11, from either Gamma(4,0,7) or Gamma(5,0,6). I did the following random search: First, shuffle the 330 points of Gamma(4,0,7). Then, greedily, collect points that are not a distance four from each other. Shuffle and repeat, a thousand times.

This problem is like coding theory, except that adjacent points are allowed. Here, a distance 4 is not allowed because of the degenerate triangles (4,0,7),(2,4,5),(4,0,7) and (5,0,6),(3,4,4),(5,0,6).

The points from Gamma(4,0,7) can be found from the binary representations of these eighteen numbers:
15, 23, 27, 29, 30, 240, 232, 228, 226, 225, 1920, 1856, 1824, 1808, 1800, 1796, 1794, 1793.
The eighteen points from Gamma(5,0,6) can be found from the binary representations of these numbers, no two of which differ in exactly four places: 31,47, 55, 59, 61, 62, 713, 714, 716, 944, 1347, 1349, 1350, 1456, 1712, 1840, 1936, 1952

20 June, 2009 at 3:16 pm

Michael Peake

There is an analogy for this problem in k=4. Isosceles triangles are replaced by isosceles tetrahedra. Again, there will be a limit of two layers’ worth of points, spread over four layers. This time, each layer will have a density of 50 percent.

The set of possible (a,b,c,d) form a tetrahedron, with vertices (n,0,0,0),(0,n,0,0),etc. Sit this tetrahedron on its (0,b,c,0) edge, with that edge pointing north-south. The (a,0,0,d) edge is on top, pointing east-west. Each layer of cells has constant a+d, or equivalently constant b+c. Each layer is a rectangle. The cells in one layer are offset from the layer below, but directly above the cells in the layer two down.

A geometric line has points from the four cells (a+r,b,c,d+s), (a,b+r,c+s,d), (a,b+s,c+r,d), (a+s,b,c,d+r). These form an isosceles tetrahedron with its upper edge pointing east-west and its lower edge north-south. Degenerate tetrahedra exist, with (a+r,b,c,d+r) directly above (a,b+r,c+r,d).

So one can’t include two whole cells when one is directly above another. One expects one layer’s worth of cells from the even layers, and one layer’s worth from the odd layers.

Give each layer a checkerboard colouring, with each layer matching the layer two levels down. Even layers have one colouring; odd layers have their own colouring.

Select dark cells in layers q and q-1, and light cells in layers q-2 and q-3. This gives four half-layers of cells. No isosceles tetrahedrons form from these cells. One expects at most two layers worth of cells, so this is best possible.

It is still possible to include a subset of lower cells, with degenerate tetrahedrons, so long as geometric lines are avoided.

20 June, 2009 at 9:35 pm

Michael Peake

Klas,
Is it possible to run your routine, looking just for points from Gamma(7,0,5) that are not a distance 4 from each other? I think they may be added to the first solution for n=12 without adding geometric lines. Also, I think points from Gamma(3,0,9) that are not 4 from each other may be added; unlike my solution for n=11 above, those two sets can both be added to the n=12 mix.

21 June, 2009 at 5:36 am

21 June, 2009 at 10:38 am

Michael, it doesn’t sound too hard to make a program for that. I’ll look into it.

I have written the program for maximum sets with no points at distance exactly 4. The program finds good solutions fairly quickly but it is slow at reducing the upper bounds. The values so far are

Cell best found upper bound
n=11
(4,0,7) 18 28
(5,0,6) 18 57
n=12
(3,0,9) 12 optimal
(7,0,5) 25 112

I have the programs running on three machines trying to close the gap but I think they will run out of RAM sometime this night before finishing.

21 June, 2009 at 7:05 pm

21 June, 2009 at 11:20 pm

Klas,

Could you look for the number of points without distance 4 in (5,0,5)? It looks like it may be more than 12, possibly taking an example in (5,0,6) that has 18 such points and modifying it may give more than 12.

23 June, 2009 at 10:17 pm

Kristal, it follows from my earlier post about the best possible extension for n=10 that there cannot be a set with more than 12 points in (5,0,5)

The programs have been running over night and the best new upper bounds are now
(4,0,7) 22

(7,0,5) 111

22 June, 2009 at 3:26 am

Michael Peake

For n=12, I think you can have points from (5,1,6) so long as no two points have the 2 in the same place and four 1s or 3s different. That would be 12*18 = 216 extra points.

23 June, 2009 at 2:56 pm

Michael Peake

I went looking for points that are not a distance 4 from each other.

I expect to find the most ‘extra’ points in the q-4 layer, and the connection between the q’th layer and the q-4′th layer causes that restriction.

The following is the results of random searches. For Gamma(a,0,c), the row is a+c, the column is a or c, and the entry is the number of points I could find that are not a distance 4 from each other.

For Gamma(a,b,c), I think you multiply that number of points by binom(a+b+c,b), because the two ends of a geometric line have 2s in the same places.

1 0 0 0 0 0 0 0 0 0
2 1 0 0 0 0 0 0 0 0
3 3 1 0 0 0 0 0 0 0
4 3 4 1 0 0 0 0 0 0
5 4 4 5 1 0 0 0 0 0
6 5 4 5 6 1 0 0 0 0
7 6 5 5 6 7 1 0 0 0
8 7 8 10 8 7 8 1 0 0
9 8 8 11 11 8 8 9 1 0
10 9 8 12 12 12 8 9 10 1
11 10 9 18 18 18 18 9 10 11
12 11 12 20 25 28 25 20 12 11
13 12 12 22 29 34 34 29 22 12
14 13 12 29 37 42 43 42 37 29
15 14 13 32 43 52 59 59 52 43
16 15 16 35 49 68 79 86 79 68
17 16 16 43 55 82 107 123 123 107
18 17 16 47 63 100 137 167 177 167
19 18 17 51 75 121 174 228 256 256
20 19 20 60 83 144 220 299 359 380

Michael Peake

For the n=10 case, I think I can get 36 extra points, rather than twelve:

Delete the Gamma(0,0,10) set
Add one point from Gamma(1,0,9),
23 points from Gamma(4,0,6) that are not 2 from each other, and
13 points from Gamma(7,0,3) that are not 2 from each other.

24 June, 2009 at 12:36 pm

I have been wondering a bit about the tentive title for the second paper. Now it is “Density Hales-Jewett and Moser numbers in low dimensions”. However, quite a lot of the material is really about giving constructions which give lower bounds for all values of n. Should we update the title to reflect this?

25 June, 2009 at 6:38 am

Michael Peake

A general form for extra points is to include these whole Gamma sets:

Γ(a,q,N − a − q) when a\neq 2(mod 3)
Γ(a,q − 1,N + 1 − a − q) when a\neq 1(mod 3)
Γ(a,q − 2,N + 2 − a − q) when a = 0(mod3)
Γ(a,q − 3,N + 3 − a − q) when a = 2(mod3)

and some extra points from the following Gamma sets:
Γ(a,q-4,N + 4 − a − q) when a = 1 (mod 3)
Points within these Gamma sets must not be connected by swapping a 1 and a 3. So one can have points with coordinates (1,2,3) and (2,1,3), but not both (1,2,3) and (3,2,1).

The proportion of extra points one can keep from Gamma(a,0,c) is 1/(1+max(a,c)), for the following reason. For each included point, there are ac excluded points which are all its nearest neighbours. For each excluded point, there are ac nearest neighbours, but only min(a,c) of them may be included. So each included point has on average ac/min(a,c) = max(a,c) excluded points. So the proportion of included points is at most one in 1+max(a,c).

The proportion of extra points one can keep from Gamma(a,q-4,c) is also at most 1/(1+max(a,c)) < 2/(N-q+6). Since we keep these points from one cell in three of the q-4 layer, one can expect a proportion 2/3(N-q+6) of extra points from this layer

25 June, 2009 at 9:05 am

25 June, 2009 at 12:39 pm

We could change “Density Hales-Jewett and Moser numbers in low dimensions” to “Density Hales-Jewett and Moser numbers.” I think that would include lower bounds that work for all values of n.

25 June, 2009 at 11:26 pm

Such a name change seems fine with me. (I’m busy with other things at the moment, but hope to have some time to devote to this project again in the near future.)

Matemáticos colaboram num projecto aberto de investigação conjunta através do blogue do Professor Timothy Gowers « problemas | teoremas

That looks like a good name.

26 June, 2009 at 1:46 am

[...] Tao, sabe quem acompanha o seu blogue que está igualmente envolvido no projecto. O artigo DHJ: Still writing the second paper, de 14.06.09, é o último sobre o [...]

26 June, 2009 at 10:54 pm

Michael Peake

I have forgotten how to get some of the c_n numbers in the spreadsheet, specifically from c_13 on, so I have added column AC which is the best values I can get now. They are the first general form given in the paper and the wiki. Does someone else remember how the values in Column A were found?

2 July, 2009 at 12:03 am

Michael Peake

Ah. The numbers from 13 to 20 were found by Klas, as he gives in
http://abel.math.umu.se/~klasm/Data/HJ/
The numbers from 21 to 100 are given by my general form.

2 July, 2009 at 3:53 pm

http://michaelnielsen.org/polymath1/index.php?title=Moser%27s_cube_problem#n.3D6

I managed to eliminate 355-point Moser sets in 6 dimensions by a rather complicated analysis, based on seeing how (6,12,18,4,0) sets can fit with each other, see

It may be possible to extend the analysis to eliminate 354-point Moser sets also, but this looks somewhat tricky, as now up to half of the 11**** type slices can fail to be of the (6,12,18,4,0) configuration. One may have to understand (i.e. to classify) the (5,12,18,4,0), (5,12,12,4,1), (6,8,12,8,0) configurations to do this. (But it should be possible, I think, to show that e=0, which would at least kill off the (5,12,12,4,1) case.)

3 July, 2009 at 9:39 am

I am looking at (5,12,18,4,0), (5,12,12,4,1), and (6,8,12,8,0). It looks like (5,12,18,4,0) has at least 3 different representations as one can remove a point without 2′s three different ways from (6,12,18,4,0).

3 July, 2009 at 3:26 pm

Kristal Cantwell

Since in the proof of the uniqueness of (6,12,18,4,0) The c’s and d’s are fixed in a pattern before the a’s or b’s positions are known they will also be forced to take the same positions in (5,12,18,4,0) only the positions of the a’s and b’s can vary.

3 July, 2009 at 4:02 pm

Thanks Kristal. The analysis on the blog doesn’t use the a-points much, so if the (5,12,18,4,0) sets are indeed just the same as the (6,12,18,4,0) sets modulo a points then the analysis should carry over to this case.

The problem resembles a sort of six-dimensional jigsaw puzzle where one has 60 four-dimensional faces to slot together. I’m hoping that the (5,12,12,4,1) piece doesn’t fit with any of the other high-score pieces, in which case it can hopefully be ignored. From the 353 point examples I know that the (6,8,12,8,0) piece can fit with the remaining two high-score pieces, but hopefully the exact nature of that fitting can be quantified precisely. Then there are the lower score pieces – unfortunately, there can be as many as 20 slices with a score of 350 or lower, but hopefully the 40+ high-score pieces will already give enough information to conclude. (Another useful piece of information is that the total “a” count of four parallel slices, e.g. 11****, 13****, 31****, 33****, must equal the total “a” count of the 6D set. This already tells us that a must be either 22, 23, or 24, and any of these three already constrains the configurations of ways to fill out the various 4D faces a fair bit.)

3 July, 2009 at 6:02 pm

Kristal Cantwell

“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. Tthus 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.”

The above is true for not just just for (6,12,18,4,0) but also for(5,12,12,4,1) and (5,12,18,4,0). For (5,12,12,4,1) it is true because of the presence of the center point. For (5,12,18,4,0) it is true because it has the same possible pattern of d points as (6,12,18,4,0).

Also for (6,8,12,8,0) both side slices contain their center points for any cut.
Perhaps that could eliminate some combinations.

4 July, 2009 at 8:41 am

That’s a good observation! I checked it against the symmetric 353-point example described on the wiki to see what happens (I added more detail on the wiki page to reflect this discussion). The 11**** slices of this example are of the (6,12,18,4,0) type, while the 13**** slices are of the (5,12,18,4,0) type and are just a (6,12,18,4,0) set with one a-point removed. The 33**** slices are of the (6,8,12,8,0) type (consisting of 1133, 1112, 3332, 1122, 3322, 1222, 3222 and permutations). There are five “d” points of type ***222, namely 111222, 333222, 113222, 131222, and 311222. They obey the alternating pattern except for 333222, which is consistent with the fact that the three (6,8,12,8,0) slices 33****, 3*3***, *33*** pass through this point.

6 July, 2009 at 10:39 am

The spam problem at the wiki seems to be increasing. Take a look at the discussion for the main page where Michael Nielsen has asked question about completely blocking anonymous users from editing the wiki.

6 July, 2009 at 12:56 pm

Klas: thanks for the heads up! I’ve put in my vote. Thanks for all your spam-fighting efforts!

On the 6D Moser problem, I’ve made a partial breakthrough: I now know that the only way one can make a 354 set is if, among the 11****, 13****, 31****, 33**** slices, two of them have statistic (6,12,18,4,0) and the other two have statistics from (5,12,18,4,0), (5,12,12,4,1), (6,8,12,8,0), so hopefully once we classify all the sets with these statistics we will be close to finally eliminating this case and establishing $c'_6=353$ . Details are on the wiki. The key new observation, which came from the list of Pareto-optimal 4D statistics, is that any 4D slice with a=8 had to have an extremely low score (at most 326), which made such slices extremely rare (and in fact I could eventually eliminate them altogether). Also, a 4D slice with a=4 also has to have a moderately low score (at most 350). On the other hand, the side 4D slices of a (6,12,18,4,0) set alternate between (4,3,3,1) and (2,6,6,0). But it is difficult for two (4,3,3,1) slices to be adjacent because this would create a 4D slice with a=8; it is also difficult for two (2,6,6,0) slices to be adjacent. It turns out that one can leverage this to show that one can’t have too many (6,12,18,4,0) slices that are adjacent, in particular one cannot have the 11****, 13****, 33**** slices all of this form.

6 July, 2009 at 7:57 pm

I have been looking at the ways (5,12,12,4,1), and (6,12,18,4,0) slices can have points in common and I think I have an example in which they can share a (2,6,6,0) slice and the example can be modified so that (5,12,12,4,1), and (5,12,18,4,0) can share the same slice. I was trying to prove that this was not possible and ended up constructing an example. I will be posting it tomorrow. I am still looking at these sets

6 July, 2009 at 8:52 pm

It looks like every family consists of two (6,12,18,4,0) and two of (5,12,18,4,0), (5,12,12,4,1), (6,8,12,8,0) so we don’t have to look at any four dimensional sets but these. Is there any information about these sets from the search for Pareto optimizers? If you have one (6,8,12,8,0) set in a family I think there have to be two which have to be adjacent. I might be able to prove the same for (5,12,12,4,1) since if one is adjacent to a (6,12,18,4,0) one of its side slices has a low number of points I think seven. Could we do a computer search for all examples of the four types, then search for all possible families having the desired characteristics and then try for all possible combinations of families? Perhaps less than 15 families would determine a set and that could narrow the final search.

6 July, 2009 at 9:39 pm

Dear Kristal,

I have the a-set data for the Pareto optimisers, but not the other data (though I suppose I could modify the code to hunt for these if necessary). [If you'll recall, the search was conducted by looping over all possible a-sets (modulo symmetries), filling in the top and bottom 3D layers with Moser sets, finding the forbidden points on the middle layer, then looking up the Pareto optimal statistics for that layer.]

For (5,12,12,4,1), it looks from the data that the a-set must be some permutation of one of the following three possibilities:

* 1111, 1113, 1131, 1311, 3111
* 3333, 1113, 1131, 1311, 3111
* 1111, 1113, 1133, 1333, 3333

For (6,8,12,6,0), it looks like the a-set must be a permutation of 1133, 1313, 1331, 3113, 3131, 3311.

For the (5,12,18,4,0) guy, the situation is a bit more complicated because it isn’t a Pareto optimal set (being shadowed by (6,12,18,4,0)). But if I am reading the data correctly, the a-set must (up to symmetries) be formed by removing one point from 1111, 1113, 1131, 1311, 3111, 3333, which is consistent with the conjecture that the (5,12,18,4,0) sets are all formed by removing one point from a (6,12,18,4,0) set.

I am only about 75% confident in these above statements; it would be good to have an independent means of confirming these claims.

It does seem that once we have a good list of all the possible (5,12,18,4,0), (5,12,12,4,1), and (6,8,12,8,0) sets, and how they can fit with each other, one should be well on the way to doing a computer search to exhaust the remaining possibilities, but I guess we will have to first see the list before it becomes clear how feasible this would be and what the best algorithm would be.

7 July, 2009 at 7:51 am

Michael Peake

My computer found 10000 solutions for (6,8,12,8,0), assuming the 12 c-points are Gamma(2,2,0) and Gamma(0,2,2). There would be more solutions by symmetry.
The six a-points were Gamma(2,0,2)
The eight b-points included two from the c-statistic c2xxx, two from cx2xx, two from cxx2x and two from cxxx2. The two from c2xxx included three 1s and three 3s in their coordinates, and so for cx2xx, cxx2x and cxxx2. There are ten choices for c2xxx, and 10^4 choices altogether.

7 July, 2009 at 8:38 am

I think I can get rid of a lot of cases of 354 and get close to proving that the answer is 353. I am going to be working on this and hopefully I should have some cases eliminated soon. The idea is that when (5,12,12,4,1), and (5,12,18,4,0) share the same (2,6,6,0) slice I can get the number of points is 353 or less and I hope to extend this to other sets as well and narrow the possibilities.

7 July, 2009 at 9:06 am

Michael Peake

My computer found 1720 solutions for (5,12,12,4,1) when 1222,2122,2212 and 2221 were included.

If I have read the results correctly, there were
608 solutions with (3333,3111,1311,1131,1113)
608 solutions with (1111,3111,1311,1131,1113)
112 solutions with (3333,1333,1311,1131,1113)
112 solutions with (3333,3111,3133,1131,1113)
112 solutions with (3333,3111,1311,3313,1113)
112 solutions with (3333,3111,1311,1131,3331)
14 solutions with (1111,3111,3311,3131,3113)
14 solutions with (1111,1311,3311,1331,1313)
14 solutions with (1111,1131,3131,1331,1133)
14 solutions with (1111,1113,3113,1313,1133)

None had any points from Gamma(3,1,0) or Gamma(0,1,3), I don’t know why.

7 July, 2009 at 9:38 am

Thanks Michael! I made an error in my earlier post; the (5,12,12,4,1) sets were picked up in the 16, 214, and 30 scans, which correspond to (permutations of) (1111,3111,1311,1113,1113), (3333,3111,1311,1131,3331), and (3333,3111,1311,1131,1113) respectively (I didn’t expand out the binary code for the 214 scan properly before). This is consistent with your statistics; the 16 scan corresponds to your second set of 608 solutions and all four sets of 14 solutions, the 214 scan corresponds to the four sets of 112 solutions, and the 30 scan corresponds to the first set of 608 solutions. So the data appears to be consistent, which is reassuring.

Kristal: sounds promising! The (5,12,12,4,1) slice does seem to be the “odd one out”; it doesn’t show up in the 353-point example (whereas the other four types do) and it does seem like it shouldn’t fit very well with the other three puzzle pieces.

The families in the 353-point example consists of a (6,12,18,4,0) slice adjacent to two (5,12,18,4,0) slices, while being diagonally opposite a (6,8,12,8,0) slice. Based on this, my guess is that any putative 354-point example should eventually have a family consisting of a (6,12,18,4,0) slice adjacent to a (6,12,18,4,0) and a (5,12,18,4,0) slice while being diagonally opposite a (6,8,12,8,0) slice. Based on the 355 point theory, I would imagine that the diagonally opposite (6,12,8,4,0) and (5,12,18,4,0) points would be forced to be of the same type and thus eliminate a lot of points in the center slice 22****, perhaps enough to get to 353 or below.

The number of possibilities coming up in Michael’s search are unfortunately looking a bit big for a computer search to be really feasible, though clearly symmetry is going to help a bit. I guess at this point it is better to use the human methods to keep cutting down the possibilities before we resort to computer methods.

7 July, 2009 at 9:41 am

Michael, is it possible to work out what the 3D side slice statistics of your (6,8,12,8,0) and (5,12,12,4,1) sets can look like? For instance, I know that the 3D side slices of a (6,12,18,4,0) set are all either (4,3,3,1) or (2,6,6,0), and this is very useful in fitting these 4D slices together with each other and with the other 4D slices (e.g. one can relate the 11**** slice to the 1*1*** slice by studying the common side slice 111***).

7 July, 2009 at 10:12 am

Michael Peake

My computer found solutions for (5,12,18,4,0), with 1222,2122,2212,2221 included:
* The (6,12,8,4,0) solution with one a-point removed; (six solutions)
* Remove 3111,2133,2313,2331, but add 2111,2311,2333 (twelve more solutions)
* Remove 1111, get a different set of b-points, (255 more solutions)
The c-points were all determined by the d-points, and the a-points were always five of the six a-points from the (6,12,18,4,0) solution.

7 July, 2009 at 10:39 am

Michael Peake

The 256 solutions you get from (5,12,18,4,0) from deleting (1111) is by adding three points from each of c2xxx, cx2xx, cxx2x and cxxx2. The three points from c2xxx are either 2111,2113,2333; 2111,2131,2333; 2111,2311,2333 or 2133,2313,2331. There are four similar choices for each of c2xxx, cx2xx, cxx2x and cxxx2, so 4^4 = 256 solutions in all.

7 July, 2009 at 11:47 am

Michael Peake

The side statistics for (5,12,18,4,0) are as follows.

The side statistics for the 256 solutions are (3,x,3,1,0) and (2,9-x,6,0,0) for x between 3 and 6.
The stats for the twelve solutions are either 34310,25600 or 33310,26600.
The stats for the (6,12,18,4,0) solution missing 3333 are (43310) and (16600)
The centre slice is always (3930)

The side stats for (6,8,12,8,0) are (3×31) and (3,6-x,3,1) for x between 0 and 3. The centre slice is always (2,6,6,0)

The centre slice for (5,12,12,4,1) is always (3,6,3,1).
The side slices for (5,12,12,4,1) have from 6 to 12 points. They have 45 different statistics:
(3-4,3-6,0,1), (2-4,3-6,1,1),(2-4,2-5,2,1),(2-4,0-3,3,1),(1,3,3,1)

7 July, 2009 at 1:01 pm

Thanks Michael! I’m a bit puzzled though as to why the side slices for (5,12,12,4,1) always have d=1, I would have thought they would come in pairs, one with d=1, and the opposite slice with d=0.

It does seem to support the claim that the (5,12,12,4,1) slice is hard to fit with the other slices… it seems that only the (3,*,3,1) slices (and the (4,3,3,1) slice) are in common with other 4D slices, if I’m reading the data correctly.

7 July, 2009 at 1:20 pm

Ah, I guess you are omitting the d=0 slices from the (5,12,12,4,1) data as they can be inferred from the d=1 slice and the fact that the center slice is always (3,6,3,1), is that correct?

If I am understanding the data correctly, then there is actually quite a severe limitation on what the 3D slices can be. We have to have at least one (in fact we have two) (6,12,18,4,0) set in every family, which has slices (2,6,6,0) and (4,3,3,1). On the other hand, the data seems to assert that

* a (2,6,6,0) slice can only be adjacent to either a (4,3,3,1) slice, a (3,3,0,1) slice, or a (3,3,3,1) slice. [Two 3D slices are adjacent if they are side slices of the same 4D slice, e.g. 111*** and 113*** are adjacent.]

* A (4,3,3,1) slice can only be adjacent to a (2,6,6,0), (1,6,6,0) or a (1,6,3,0) slice.

* A (3,3,3,1) slice can only be adjacent to a (2,6,6,0), (3,3,3,1), or (2,6,3,0) slice.

* A (1,6,6,0) slice can only be adjacent to a (4,3,3,1) or (4,3,0,1) slice.

* A (1,6,3,0) slice can only be adjacent to a (4,3,3,1) slice.

* A (4,3,0,1) slice can only be adjacent to a (1,6,6,0) slice.

* A (2,6,3,0) slice can only be adjacent to a (3,3,3,1) slice.

* A (3,3,0,1) slice can only be adjacent to a (2,6,6,0) slice.

If all this is true, then the only possible 3D slice statistics are (4,3,3,1), (2,6,6,0), (1,6,3,0), (3,3,3,1), (1,6,6,0), (4,3,0,1), (3,3,0,1), and (2,6,3,0). This should severely cut down on the possible 4D slices and move us closer to the point where we can exhaust the remaining cases by computer or even by hand.

7 July, 2009 at 1:34 pm

Actually, the situation seems to be even better than this. On the wiki it is shown that in every family of 4D slices, two of the slices are good (i.e. of (6,12,18,4,0) type). This implies that every 3D slice is adjacent to a 3D slice of a (6,12,18,4,0) set, i.e. adjacent to either a (4,3,3,1) slice or a (2,6,6,0) slice. This eliminates the (4,3,0,1) and (2,6,3,0) possibilities, thus every 3D slice must be either (4,3,3,1), (2,6,6,0), (1,6,3,0), (3,3,0,1), (1,6,6,0), or (3,3,3,1).

It looks like one could eliminate more possibilities with a bit more effort…

7 July, 2009 at 1:40 pm

Ah, it looks like one can now fully eliminate the (6,8,12,8,0) slices (but this needs to be double-checked).

Suppose for instance that the 11**** slice was of type (6,8,12,8,0). Then by Michael’s stats, the 111*** and 113*** slices are of type (3,*,3,1) (in fact they have to be (3,3,3,1), in order to be adjacent to either (4,3,3,1) or (2,6,6,0)). This implies that the 1*1*** and 1*3*** slices can’t be of the form (6,12,18,4,0), which implies that the 3*1*** and 3*3*** slices must be of the form (6,12,18,4,0). In particular, the 311*** and 333*** slices must be either (4,3,3,1) or (2,6,6,0). But these slices are adjacent to the (3,*,3,1) slices at 111*** and 113***, and must therefore be of type (2,6,6,0). But then we have two adjacent (2,6,6,0) slices, which is not possible with this data (actually Kristal observed earlier that we can’t have any two d=0 slices adjacent to each other).

8 July, 2009 at 6:01 am

Michael Peake

That looks right, although I think you meant 313*** instead of 333***.
I am afraid I omitted half the (5,12,12,4,1) slices because it was getting a bit late. The fact that centre slices were (3,6,3,1) was intended as a check, rather than a cryptic clue.
Another thing from yesterday was the (6,8,12,8,0) data, where I assumed the c-points were Gamma(2,2,0) and Gamma(0,2,2). I have run it again, without that assumption, and the only extra solutions I got were indeed from symmetries of the cube.

8 July, 2009 at 10:37 am

Let us assume that a (6,12,18,4,0) set and a (5,12,12,4,1) are in the same family and they share a (2,6,6,0) slice we will show that we can get a contradiction. We will later have to deal with the other possible slice of the (6,12,18,4) as well.

The coordinates of the (2,6,6,0) slice can be assumed to be without loss of generality: (3,3,3,3), (3,3,3,2), (3,3,2,1), (3,3,1,2), (3,2,3,2), 3,2,3,1),(3,2,1,2), (3,2,2,3), (3,2,2,1), (3,2,1,3), (3,1,1,1), (3,1,2,2), (3,1,2,3) and (3,1,3,2).

We can assume the presence of points (2,2,2,2) and (1,2,2,2).

Now the points of the (2,6,6,0) reflected by (2,2,2,2) block all but the center spot and 6 pairs of points which are symmetric about (1,2,2,2) this means that there are at most 7 points but there are at most 13 points in the center slice and exactly 14 in the (2,6,6,0) slice and since there are 34 in the overall set there must be exactly 7 in the slice with first coordinate equal to one and exactly 13 in the center slice.

Frome this we see that there must be exactly one of the following pairs in the set: 2212 and 2223,2223 and 2232, 2232 and 2221, and 2221 and 2212. We will look at each of these four cases.

to be continued

8 July, 2009 at 10:46 am

continued from my previous post:

assume 2212 and 2223 are in the set
then with 3213, 2212 blocks 1211 and with
3213 2223 blocks 1233 but this means the diagonal
1211 1222 and 1233 contains only one point and by the previous discussion
the slice with first coordinate equal to one has less than 7 points which means the total set size is less than 34 which gives a contradiction.
The case of 2232 and 2221 is symmetric to this so the only remaining cases are the pair 2221 and 2212 and the pair 2223 and 2232.

to be continued

8 July, 2009 at 11:18 am

It looks like we are rapidly narrowing down the number of possible 4D corner slices (such as 11****) and 3D side slices (such as 111***) of a 354-point 6D Moser set.

To summarise so far, it now looks (though it would be good to recheck) that the only possible 4D corner slices are (6,12,18,4,0), (5,12,18,4,0), and (5,12,12,4,1). The only possible 3D side slices are (4,3,3,1), (2,6,6,0), (1,6,3,0), (3,3,0,1), (1,6,6,0), and (3,3,3,1).

In any family of four parallel 4D slices (e.g. 11****, 13****, 31****, 33****) we have two (6,12,18,4,0) slices, and two slices which are either (5,12,18,4,0) or (5,12,12,4,1).

Any two opposing side slices of a (6,12,18,4,0) slice (e.g. 111*** and 113*** of 11****) has statistics (4,3,3,1) and (2,6,6,0).

Any two opposing side slices of a (5,12,18,4,0) slice come in the pairs (3,3,3,1)+(2,6,6,0) or (4,3,3,1)+(1,6,6,0).

Any two opposing side slices of a (5,12,12,4,1) slice comes in the pairs (4,3,3,1)+(1,6,3,0) or (3,3,0,1)+(2,6,6,0).

Furthermore, if I understand Kristal’s most recent comments correctly, the (2,6,6,0) slice of (5,12,12,4,1) is not compatible with the (2,6,6,0) slice of a (6,12,18,4,0) set. If so, it appears that the (3,3,0,1) slice cannot occur, because every 3D slice has to be adjacent to a 3D slice of a (6,12,18,4,0) set as I mentioned in my 7 July 1:34pm comment. So the (5,12,12,4,1) slice must have the property that every opposing pair of side slices take the form (4,3,3,1)+(1,6,3,0). There shouldn’t be too many such slices with that property (and if the (4,3,3,1) slices are not compatible with the (4,3,3,1) slice of the (6,12,18,4,0) set, then we should be able to eliminate (5,12,12,4,1) entirely, which would be a huge advance).

8 July, 2009 at 11:27 am

Continued from my previous post:

Assume the set contains the points 2221 and 2212
then the points 3312 and 3321 together with the above points block
1121 and 1112. Since the slice with first coordinate one must have seven points the diagonals 1121 1222 1323 and 1112 1222 1332 must have two points and so the set must contain the points 1323 1332

Now the points 3213 2212 block 1211 since the diagonal 1211 1222 1233 must contain two points the set must contain 1233

Now on the five remaining diagonals on which points can possibly lie in the slice with first coordinate 1 the points of the (2,6,6,0) set block one point each for four of these diagonals for the slice to have 7 points and the configuration to have 34 the remaining spaces must be filled thus the set must have the points 1332, 1323, 1311, and 1133.

The points 1311 and 3333 block 2322 and since the center slice must have 13 points the point 2122 must be in the set.

to be continued.

8 July, 2009 at 11:55 am