DHJ(3): 900-999 (Density Hales-Jewett type numbers)

4 March, 2009 in math.CO, polymath | Tags: density Hales-Jewett, Moser cube problem, polymath1

This is a continuation of the 700-799 thread of the polymath1 project, which is now full. During the course of that thread, we have made significant progress on the three problems being focused on:

1. Upper and lower bounds for $c_n$ for small n.

Let $c_n$ be the largest size of a set in $[3]^n$ without a combinatorial line. We now have both human and computer-assisted proofs of the first few values of this sequence:

$c_0=1; c_1=2; c_2=6; c_3=18; c_4=52; c_5 = 150; c_6 = 450$ .

The current best-known bounds for $c_7$ are $1302 \leq c_7 \leq 1348$ . Given the gap involved here, and the rate at which the complexity of the problem has increased with n, it seems unlikely that we will be able to compute $c_7$ exactly any time soon, but it is possible that some improvement can still be made here.

2. A hyper-optimistic conjecture

Consider a variant of the above problem in which each element of $[3]^n$ with a 1s, b 2s, and c 3s is weighted by the factor $\frac{a! b! c!}{n!}$ ; this gives $[3]^n$ a total weight of $\frac{(n+1)(n+2)}{2}$ . Let $c^\mu_n$ be the largest weight of a line-free set of $[3]^n$ , and let $\overline{c}^\mu_n$ be the largest size of a subset of

$\Delta_n := \{ (a,b,c) \in {\Bbb Z}_+^3: a+b+c=n \}$

which contains no upward-pointing equilateral triangles $(a+r,b,c), (a,b+r,c), (a,b,c+r)$ with r>0. It is known that $c^\mu_n \geq \overline{c}^\mu_n$ ; the “hyper-optimistic conjecture” is that one in fact has $c^\mu_n = \overline{c}^\mu_n$ . This would imply density Hales-Jewett for k=3.

Currently, the conjecture is verified for $n \leq 5$ , where the values of $c^\mu_n = \overline{c}^\mu_n$ for $n=0,1,2,3,4,5$ are 1,2,4,6,9,12 respectively; see this page and this page for details. It seems feasible to handle $n=6$ . Currently we know that $15 \leq \overline{c}^\mu_6 \leq 17$ and $\overline{c}^\mu_6 \leq c^\mu_6 \leq 28$ .

3. Asymptotics for Moser’s cube problem

Moser’s cube problem asks to compute the largest size $c'_n$ of a subset of the cube $[3]^n$ without geometric lines. The first few values of $c'_n$ are known:

$c'_0=1; c'_1 = 2; c'_2 = 6; c'_3 = 16; c'_4 = 43$ .

The best asymptotic lower bound known is still of the order of $3^n/\sqrt{n}$ . Improving this bound seems related to the well-known problem of improving the bounds in Behrend’s construction of an AP-3 free set of integers.

We are quite close now to pinning down $c'_5$ ; we know that it is equal to either 124 or 125, and it is looking increasingly unlikely that it is 125.

Comments on this thread should start at 900.

About these ads

110 comments

Comments feed for this article

4 March, 2009 at 1:38 pm

Kristal Cantwell

900. I have posted this to the old thread but in case I should
have put it in the new thread I am posting it here again.

We have already shown that if
The center slice is 42 or 43 and it has
17 or more points then there at most 124
Case 2
The center slice is 42 and c is less that 17
Then we must have c is 12
And we must have on of the 8
(6, 24, 12, 0, 0) sets.
Without less of generality
We can assume it to be $\Gamma _{220}+\Gamma _{202}+\Gamma _{022}+\Gamma _{112}+\Gamma _{211}$
In particular the middles slice
Contains the points
2122 21212 21221
23322 23232 23223 and the *1*** and *3*** slices
have a d value of at least three and so have at most
41 points now if the center slice is 42 we have 124 points
and we are done so it must be 43 but then it has value 18 or more
and and by case 1 we have 124 points or less so we are done.

4 March, 2009 at 6:12 pm

Terence Tao

901. Moser(3)

I think we are now quite close to classifying all the 125 point Moser sets (if any) and thus computing $c'_5$ precisely.

From Kristal’s lemma and the averaging argument from my 793, 795 comments, we now know that (after rotating a 125 point Moser set) that the 1****, 3**** slices have (a,b,c,d,e) distribution from the following four choices:

* (4,16,23,0,0) [score: 62 1/3]
* (3,16,24,0,0) [score: 63]
* (4,15,24,0,0) [score: 62 3/4]
* (2,16,24,0,0) [score: 62]

with total score at least 125. The maximal or near-maximal “c” values of these slices force the “c” value of the middle slice 2**** to be at most 1.

Now let A, B, C, D, E, F be the number of points in the Moser set with no 2s, one 2, …, five 2s respectively. We already know that E=F=0; the above discussion shows that D is at most 1, and also A is at most 4+4=8. Meanwhile, a double counting argument shows that 2B+C is at most 160 (details on the wiki). Since

$125 = A+B+C+D+E+F \leq A + \frac{1}{2} 160 + \frac{1}{2} C + D$

we thus have

$C \geq 90 - 2A - 2D$ . (1)

But this looks quite hard to satisfy; C can at most be 80! Furthermore, if D is 1 (e.g. if 11222 is in the set), then C can be at most 77, because of the three lines (e.g. 11×22, 112×2, 1122x) going through the D-point that have their other vertices as C-points. Also, as pointed out by Michael in 784, if C is 80, then A is at most 4. So it’s looking quite hard to actually satisfy the equation (1). Perhaps just a little more case analysis will finish the problem off for good… (and then we might look at how one can reduce the reliance on computer proofs, and perhaps even hope for a completely human proof).

4 March, 2009 at 6:22 pm

Terence Tao

902. Moser(3)

Actually, I think I can show that D=1. Suppose not (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 table at

http://spreadsheets.google.com/ccc?key=p5T0SktZY9DuqNcxJ171Bbw&hl=en

shows 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. So D=0.

4 March, 2009 at 7:32 pm

Jason Dyer

903. $\overline{c}^\mu_6 \neq 17$

(The solutions I-VI are defined as in my last proof.)

Here, “upper triangle” means the first four rows of the triangular lattice (with 060 at top) and “lower trapezoid” means the bottom three rows.

Suppose 11 removals leave a triangle-free set.

First, suppose that 5 removals come from the upper triangle and 6 come from the lower trapezoid.

Suppose the trapezoid 600-420-321-303 used solution IV. There are three disjoint triangles 402-222-204, 213-123-114, and 105-015-006. The remainder of the points in the lower trapezoid (420, 321, 510, 501, 402, 312, 024) must be left open. 024 being open forces either 114 or 015 to be removed.

Suppose 114 is removed. Then 213 is open, and with 312 open that forces 222 to be removed. Then 204 is open, and with 024 that forces 006 to be removed. So the bottom trapezoid is a removal configuration of 600-411-303-222-114-006, and the rest of the points in the bottom trapezoid are open. All 10 points in the upper triangle form equilateral triangles with bottom trapezoid points, hence 10 removals in the upper triangle would be needed, so 114 being removed doesn’t work.

Suppose 015 is removed. Then 006-024 forces 204 to be removed. Regardless of where the removal in 123-213-114, the points 420, 321, 222, 024, 510, 312, 501, 402, 105, and 006 must be open. This forces upper triangle removals at 330, 231, 042, 060, 051, 132, which is more than the 5 allowed, so 015 being removed doesn’t work, so the trapezoid 600-420-321-303 doesn’t use solution IV.

Suppose the trapezoid 600-420-321-303 uses solution VI. The trapezoid 303-123-024-006 can’t be IV (already eliminated by symmetry) or VI’ (leaves the triangle 402-222-204). Suppose the trapezoid 303-123-024-006 is solution VI. The removals from the lower trapezoid are then 420, 501, 312, 123, 204, and 015, leaving the remaining points in the lower trapezoid open. The remaining open points is forces 10 upper triangle removals, so the trapezoid 600-420-321-303 doesn’t use solution VI. Therefore the trapezoid 303-123-024-006 is solution V. The removals from the lower trapezoid are then 420, 510, 312, 204, 114, and 105. The remaining points in the lower trapezoid are open, and force 9 upper triangle removals, hence the trapezoid 303-123-024-006 can’t be V, and the solution for 600-420-321-303 can’t be VI.

The solution VI’ for the trapezoid 600-420-321-303 can be eliminated by the same logic by symmetry.

Therefore it is impossible for 5 removals come from the upper triangle and 6 come from the lower trapezoid.
Therefore 4 removals come from the upper triangle and 7 come from the lower trapezoid.

At this point note the triangle 141-411-141 must have one point removed, so let it be 141 and note that any logic that follows is also true for a removal of 411 and 141 by symmetry.

This implies the upper triangle must have either solution I or II.

Suppose it has solution II. Note there are five disjoint triangles 600-510-501, 411-321-312, 402-222-204, 213-123-114, and 105-015-006.

Suppose 420 and 024 are removed. Then, noting 303 must be open, 606 must be removed, leaving 510 open. 510-240 forces 213 to be removed, and 510-150 force 114 to be removed. 213 are 114 are in the same disjoint triangle. Hence both 420 and 024 both can’t be removed.

So at least either 420 or 024 is open. Let it be 420, noting by symmetry identical logic will apply if 024 is removed. Then 321, 222, and 123 are removed based on 420 and the open spaces in the upper triangle. This leaves four disjoint triangles 600-501-510, 402-303-312, 213-033-015, 204-114-105. So 411 and 420 are open, forcing the removal of 510. This leaves 501 open, and 501-411 forces the removal of 402. 600-303, and 330 are then open, forming an equilateral triangle. Therefore 420 isn’t open, therefore the upper triangle can’t have solution II.

Therefore the upper triangle has solution I.

Suppose 222 is open. 222 with open points in the upper triangle force 420, 321, 123, and 024 to be removed. This leaves four disjoint triangles 411-501-402, 213-303-204, 015-105-006, and 132-312-114. This would force 8 removals in the lower trapezoid, so 222 must be closed.

Therefore 222 is removed. There are six disjoint triangles 150-420-123, 051-321-024, 231-501-204, 132-402-105, 510-150-114, and 312-042-015. So 600, 411, 393, 114, and 006 are open. 600-240 open forces 204 to be removed and 600-150 open forces 105 to be removed. This forces 501 and 402 to be open, but 411 is open, so there is the equilateral triangle 501-411-402.

Therefore the solution of the upper triangle is not II, and we have a contradiction. So $\overline{c}^\mu_6 \neq 17$ .

4 March, 2009 at 9:43 pm

Kareem Carr

902. Terry had previously mentioned that a GA (Genetic Algorithm) based solution might be something to try so I implemented one. The best results were:

[3]^5, 150
[3]^6, 450
[3]^7, 1302
[3]^8, 3780
[3]^9, 11340

The GA fairly easily found the first three. It starts getting challenging around 8 and 9. I have run the program several times on each example and the results are replicable. I am having trouble with [3]^10. The best result so far is 32272. I feel some confidence in the results for 7,8 and 9 as I’ve attained them several times (the smaller ones more often than the large ones due to computational restraints).

At this point, it might be reasonable to conjecture that the procedure used to predict 1302, 3780 and 11340 will continue to be valid for larger n.

I will put the solutions on my blog.

4 March, 2009 at 10:54 pm

Terence Tao

903. Genetic algorithms

Kareem, this is very interesting! One is tempted to see how the algorithm would cope with the other three quantities $c'_n, c^\mu_n, \overline{c}^\mu_n$ we are studying (and in particular to see what it does with $c'_5$ ). One difficulty with the Moser problem is that there are substantially more lines (the cube $[3]^n$ has $4^n-3^n$ combinatorial lines, but $(5^n-3^n)/2$ geometric lines).

It would also be great to have some details on implementation and various statistics (e.g. population size, number of iterations needed to reach the solution, etc.).

5 March, 2009 at 7:37 am

Jason Dyer

Metacomment.

Someone (Marc again?) posted lower bound improvements to $\overline{c}^\mu_{8}$ and $\overline{c}^\mu_{9}$ . I have modified the spreadsheet to match.

Since the editor didn’t log in to the wiki, all we have is the IP address. This brings up the odd notion that someone could contribute to the project yet be entirely anonymous.

5 March, 2009 at 8:19 am

Michael Peake

904. Scores for $c'_6$

It might be possible to adapt Terry’s score to limit the possible values of $c'_6$ .

The following argument assumes f=g=0, which is likely to be correct.

Consider the sixty corners 11****, 13**** and so on.
Give the $c'_4$ arrangements the score $a/15+b/10+c/6+d/3+e$ . The total of the scores equals the number of points in the solution.

Of the 41-point, 42-point and 43-point solutions, the highest score is 5.833
If that were the highest possible score, $c'_6$ would be at most 350.

5 March, 2009 at 8:27 am

Kareem Carr

905. Genetic Algorithm Details

** Lookup Table **

I created a lookup table for each c_n on which I ran the genetic algorithm. This speeds up checking if a chromosome is line-free tremendously, making this tractable. (Any ideas about efficient ways to do this will have a very large effect on the speed of the algorithm).

** Encoding Solutions **

Chromosome structure: I code the solutions as a list of ones and zeros of length 3^n. The elements are ordered in this way 1…11, 1…12, 1…13, 1…21 and so on. A 0 in position 1 means element 1…11 is not in the set, otherwise it is.

** Making a new generation **

Selection: Any solutions below the mean of the population are completely ignored. The rest are selected with a probablity related to their score.

Crossover operator: I pick a random number, m between 2 and (3^n) – 1 and I make a new chromosome with the first m elements of a one chromosome and the last (3^n) – m elements of another chromosome.

Mutation operator: I pick a few points at random and flip them.

I check any new chromosomes to make sure they are valid. I do this by going through the chromosome elements in a random order (visiting each one) and removing points that conflict with other points.

** Population size **

I use elitism. (I keep the best 5 or sometimes 10 between generations.)

Population size: 60

I make more children than I can use (somewhere between 60-80) making the algorithm somewhat Malthusian. I take the best of the children and use them to replace the rest of the population.

** Non-standard addition **

An extremely effective trick has been to use a greedy algoritm on the list of all solutions to:

1. pick a small but fixed number of points in each chromosome and flip them if they improve the score.

2. run the greedy algorithm on the whole chromosome, going through all positions in a random order, and flipping any that make an improvement.

I vary the number of times I use 1 versus 2 in order to control the computational costs of this step.

I have found that without this step the algorithm is dramatically less good.

** Adaptive Elements **

The mutation rate is adaptive. I keep statistics on whether there are any repetitions in the chromosomes I generated and if there are, I increase the mutation rate until they disappear. Thus the mutation rate is just high enough to make sure a maximum number of novel solutions are being explored. If I have increased the rate twice in a row then I double the increment size and if I decrease the rate twice in the row then I half the increment size. (This allows quick changes in the rate if necessary.)

I also keep statistics on the probability that crossover and the probability that mutaton improve the score. I randomly choose one or the other in proportion to their effectiveness in the last generation.

** Cataloging solutions **

I set a criteria for when I think the genetic algorithm is stuck (200 generations with no change in the best performer). If there is no improvement then I restart the algorithm and I store the best solution.

** Final comments **

For n less than 8, this works very quickly. For n=5, a quick look at a few examples shows 150 is attained within 40 generations. This gets faster after the program has attained the solution once because a better mutation rate than my default guess is found.

5 March, 2009 at 8:46 am

Kareem Carr

906.

In a previous thread, I saw that 12 solutions were found for c_5. I was also able to find these solutions. In addition, I found 12 solutions for c_7. I only found a single solution for c_8 and c_9. Could this mean that if n is a prime larger than 3, there are 12 solutions?

I am not sure if this is already known but the 12 solutions for c_5 can be constructed from 9 smaller units: 6 of length 5 and 3 of length 70. Each solution contains four disjoint units: two of length 70 and two of length 5.

The 12 solutions for c_7 can be similarly constructed from 9 smaller units: 6 of length 21 and 3 of length 630. Each solution again contains four disjoint units: two of length 630 and two of length 21.

I will put the units used to make the solutions on my website along with the solutions as soon as soon as I have enough time to organize the data.

5 March, 2009 at 8:55 am

Terence Tao

906. Scores for $c'_6$

Michael: this is a nice observation! The proposed upper bound of 350 is close enough to the current lower bound of 344 that one can hope that $c'_6$ may actually be feasible to compute exactly. (It would be interesting to see how the genetic algorithm performs on this problem.)

There may be three ways to establish rigorously that 5.833 is the highest $c'_6$ -score of all four-dimensional Moser sets. Firstly, I would assume that Klas’s integer programming methods (which were able to find the maximal value of $a+b+c+d+e$ , namely 43) would also be able to find the maximal value of this score in a comparable amount of time (and even classify extremisers, etc.). Secondly, it may be that for 40-point sets and below one can use the inequalities that one already has on a,b,c,d,e (some are collected at the wiki page) together with the inequality $a+b+c+d+e \leq 40$ . A third way is to iterate the score strategy. One can presumably dispose of the e=1 case (we know already, for instance, that such sets have at most 39 points). Once e is gone, we can bound the score of a 4D Moser set by an average of a different type of score for 3D Moser sets. Now, the set of possibilities of statistics (a,b,c,d) of a 3D Moser set should be computable more or less exactly. [Actually, come to think of it, this is a worthwhile project to do anyway, as it may help us a lot in obtaining a human proof of Klas's very valuable computer-generated facts about 4D Moser statistics that we have been relying heavily on in our 5D analysis. I guess a warmup is to first completely understand the (a,b,c) statistics of a 2D Moser set.]

5 March, 2009 at 9:11 am

Kareem Carr

907.

I have noticed that each group of 70 seems to have two possible groups of 5 which are associated with it. Thus to construct a solution, we pick two groups of 70 (of the three possible) and then for each selected group of 70, we pick one of the two possible associated groups of 5. (Again, if this is repetition, I apologize.)

I think the same principle applies to the c_7 solutions.

5 March, 2009 at 9:15 am

Terence Tao

908. Moser statistics

I’ve started on the wiki a proposal to control the statistics (a,b,c,…) of Moser sets in low dimensions. Some definitions:

* A statistic (a,b,c,…) is attainable if there is a Moser set with that statistic. For instance, (2,4,0) is attainable due to the Moser set {11, 12, 21, 23, 32, 33}.

* An attainable statistic is Pareto-optimal if it is not pointwise dominated by another attainable statistic. For instance (2,4,0) is Pareto-optimal, but (2,3,0) is not.

* An attainable statistic is extremal if it is not the convex combination of other attainable statistics; this is stronger than Pareto-optimal. For instance (3,2,0) is Pareto-optimal but not extremal (it’s a convex combination of (2,4,0) and (4,0,0).

If one wants to maximise a linear score (or more generally, a convex score) over all statistics, it suffices to check it on extremal statistics. So it looks like a worthwhile task to classify extremal statistics for small n. So far I have

* n=0: The extremal statistics are (1).
* n=1: The extremal statistics are (2,0), (1,1).
* n=2: The extremal statistics are (4,0,0), (2,4,0), (2,2,1). There is also an additional Pareto-optimal statistic (3,2,0).

It looks like n=3 should be completely computable, and then (perhaps with the assistance of the known statistics for 41+ points) n=4 should be also.

5 March, 2009 at 9:18 am

Jason Dyer

909. Alternate cube problem type

Back in the other thread in the replies to O’Donnell .832 I mentioned using alternate wildcard types to produce variations of Moser’s.

In patricular consider one with two wildcards * and #, such that * gives 1, 2, 3 and # gives 2, 3, 1. (In other words, rather than the permutation between the wildcards being a 2-cycle, it’s a 3-cycle.) The leads to lines like for example **# which gives 112, 223, and 331.

I was curious how this looked so I tried a picture for [3]^3:

Picture of 3 cycle permutation of wildcards

I did not add in the standard combinatorial lines from having only a single wild card.

How many removals are needed so there are no more lines? Is this a known problem, or a new one?

And if it’s a new problem, what would it be called? “3-cycle cube problem” doesn’t make me entirely happy.

5 March, 2009 at 9:22 am

Terence Tao

910. Alternate cube problem

Dear Jason,

I haven’t seen this problem before, but if you allow six wildcards that encode all 3! permutations of 123, then this is basically the capset problem (i.e. computing $c''_n$ ).

Randall McCutcheon and Seva Lev independently proposed what we now call the “Strong Roth theorem” on the wiki, which corresponds to using the three wildcards 123, 231, 312 (i.e. cyclic permutations of 123). This problem, like the capset problem has the advantage of being translation-invariant with respect to the addition structure of $({\Bbb Z}/3{\Bbb Z})^n$ .

I’ll put something to this effect on the wiki.

5 March, 2009 at 11:40 am

Kristal Cantwell

911. If a Moser set has 124 points or less and its center slice is of side 41
It must have 11 points or less with two twos in its center slice.

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

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

5 March, 2009 at 12:20 pm

Kristal Cantwell

912. If the center slice of a Moser set is size 41 or more the set must have
124 or less points.

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

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

5 March, 2009 at 12:37 pm

Kristal Cantwell

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

5 March, 2009 at 10:06 pm

Michael Peake

914. Pareto set of ${}[3]^3$

There seem to be 22 Pareto-optimal statistics:

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

If I use the same argument as in 904, $c'_5$ is only restricted to 132 or below, which is not very effective. Even excluding points with three 2s, as Kristal has achieved, this argument only restricts $c'_5$ to 128 or below.

6 March, 2009 at 6:58 am

Hales-Jewett « The Twofold Gaze

[...] The problem is very well written up elsewhere. So without further ado here are the solutions for c_n for a few small [...]

6 March, 2009 at 7:03 am

Kareem Carr

915. Hi everyone,

Sorry about the delay. Judging from the traffic there has been a lot of interest. There is now a zip file on my website with the solutions that I have managed to compute so far. I tried to make it as complete as I could.

http://twofoldgaze.wordpress.com/2009/03/06/hales-jewett/

6 March, 2009 at 7:22 am

Kareem Carr

916. Just one warning, there is an error in the long form of the disjoint sets which generate the solutions for [3]^7. The elements listed are of length 5 and not the expected 7 (a consequence of not setting a parameter n=7 somewhere after I had finished doing the 12 solutions of n=5.) I will get it fixed.

6 March, 2009 at 7:49 am

Terence Tao

917.

I’m a bit busy today, so only some quick comments here:

Kristal: I haven’t had time to verify your results yet, but they look very interesting! If you have time you might want to merge them with the lemmas on the wiki page.

Michael: Nice! Your list shows, by the way, that the previous computation that a 3D Moser set with 222 has at most 13 points is sharp. (This is one of the reasons it’s nice to have a list of extremal triples).

Presumably if one reduces from Pareto-optimal triples to extremal triples then one should have a much smaller (and hence more tractable) set of triples to work with. Once one has those, one should be able to describe the sharp linear inequalities between a,b,c,d in 3D. For instance, in 2D, where the extremals are (4,0,0), (2,4,0), (2,2,1), there is only one non-trivial sharp linear inequality $2a+b + 2c \leq 8$ between the a,b,c, together of course with the trivial inequalities $a \geq 0$ , $0 \leq b \leq 4$ , $0 \leq c \leq 1$ .

Once we have the sharp linear inequalities in 3D, the averaging trick should then give us a bunch of useful linear inequalities in 4D. These are probably not optimal in themselves (in particular, they probably won’t be able to recover the sharp bound of 43, which still does not have a short human proof) but I’m hoping in conjunction with the data on 41, 42, and 43 point sets, we can do things like verify your conjecture that 4D Moser sets have a 5D score of at most 5.833.

Kareem: thanks for the data and the details of the GA!

6 March, 2009 at 9:50 am

Jason Dyer

918. $\overline{c}^\mu_7 \leq 22$

Finishing $\overline{c}^\mu_6$ will take some time, so here’s a quick chunk off of $\overline{c}^\mu_7$ .

I’m using the same eight extremal solutions to $\overline{c}^\mu_3$ as previous proofs:

Solution I: remove 300, 020, 111, 003
Solution II: remove 030, 111, 201, 102
Solution III (and 2 rotations): remove 030, 021, 210, 102
Solution III’ (and 2 rotations): remove 030, 120, 012, 201

Suppose the 8x8x8 lattice can be triangle-free with only 13 removals.

Slice the lattice into region A (070-340-043) region B (430-700-403) and region C (034-304-007). Each region must have at least 4 points removed. Note there is an additional disjoint triangle 232-322-223 that also must have a point removed. Therefore the points 331, 133, and 313 are open. 331-313 open means 511 must be removed, 331-133 open means 151 must be removed, and 133-313 open means 115 must be removed. Based on the three removals, the solutions for regions A, B, and C must be either I or II. All possible combinations for the solutions leave several triangles open (for example 160-520-124). So we have a contradiction, and $\overline{c}^\mu_7 \leq 22$ .

6 March, 2009 at 10:09 am

Jason Dyer

919. …and I completely blanked on the rotations of II (fixing 151 helps nullify the III cases, but allows II to be rotated), which means I need to go back and fix my previous proofs. The proof of 918 is still fine, although a complete listing of cases might be in order.

6 March, 2009 at 11:19 am

Kristal Cantwell

920. For n=6 a Moser set must contain 373 or less points.

We have from 912 that if n=5 a 125 point set must have its center slice
40 or less. Then slice arbitrarily call the coordinate i if the Moser set is 374
or more two of the slices must have 125 points and those slices must
have a center slice of 40 then if we slice again call that coordinate j so we have 9
sets of 81 points with each set representing one choice of two coordinates i, j
by the above For the two values of i with 125 points the center slices must be forty or less
which means the center slice of the set with respect to j has at most
40 + 40 + 43 points and by looking at the j slices we get 125 + 125 + 123 = 373 points or less.

6 March, 2009 at 12:26 pm

Kristal Cantwell

921. If a Moser set has 125 points then the number of points with
exactly two 2’s is either 78 or 79.

It must be less than 80
by lemma three in the section of the wiki dealing with Moser
sets for n=5.

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

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

6 March, 2009 at 1:06 pm

Kristal Cantwell

922. I am going to have to redo 912 I made a mistake in which I assumed their
had to be two side slices in one cut with 43 points or more.
However it can be easily fixed. Here is the corrected version:

If the center slice of a Moser set is size 41 or more the set must have
124 or less points.

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

6 March, 2009 at 2:04 pm

Klas Markström

923 Fujimura’s problem
Earlier today coded up Fujimura’s problem for integer programming. Here are the results

n=3, maximum 6 points, 10 solutions
n=4, maximum 9 points, 1 solution
n=5, maximum 12 points, 1 solution
n=6, maximum 15 points, 4 solutions
n=7, maximum 18 points, 85 solutions
n=8, maximum 22 points, 72 solutions
n=9, maximum 26 points, 183 solutions
n=10, maximum 31 points, 6 solutions
n=11, maximum 35 points, 576 solutions
n=12, maximum 40 points, 876 solutions

Here are the solutions for n=3
http://abel.math.umu.se/~klasm/solutions-n=3-k=3-FUJ

Here are the solutions for n=4
http://abel.math.umu.se/~klasm/solutions-n=3-k=3-FUJ

6 March, 2009 at 2:04 pm

Klas Markström

924.
Here are the solutions for n=5
http://abel.math.umu.se/~klasm/solutions-n=5-k=3-FUJ

Here are the solutions for n=6
http://abel.math.umu.se/~klasm/solutions-n=6-k=3-FUJ

6 March, 2009 at 2:05 pm

Klas Markström

925
Here are the solutions for n=7
http://abel.math.umu.se/~klasm/solutions-n=7-k=3-FUJ

Here are the solutions for n=8
http://abel.math.umu.se/~klasm/solutions-n=8-k=3-FUJ

6 March, 2009 at 2:05 pm

Klas Markström

926
Here are the solutions for n=9
http://abel.math.umu.se/~klasm/solutions-n=9-k=3-FUJ

Here are the solutions for n=10
http://abel.math.umu.se/~klasm/solutions-n=10-k=3-FUJ

6 March, 2009 at 2:06 pm

Klas Markström

927
Here are the solutions for n=11
http://abel.math.umu.se/~klasm/solutions-n=11-k=3-FUJ

Here are the solutions for n=12
http://abel.math.umu.se/~klasm/solutions-n=12-k=3-FUJ

6 March, 2009 at 3:58 pm

Kareem Carr

928.

Hi everyone,

I have been computing the first few c’_prime numbers and I got an extremal that was too large for n=3. Can someone help me find the geometric line in this solution?

{112, 113, 121, 123, 131, 132, 211, 213, 231, 233, 311, 312, 321, 323, 332, 333}

Thank you.

(I apologize if this is a repeated comment, something seems like it went wrong with my submission.)

6 March, 2009 at 4:02 pm

Terence Tao

929.

Oops, I think that was my fault; I wrote $c'_3 = 14$ on the blog post when it should be $c'_3=16$ . Corrected now…

6 March, 2009 at 6:35 pm

guest

930.

Kareem,

Have you tried a version of your genetic algorithm *without* crossover? In other words, a randomized version of hill-climbing based on your mutation operator? (run many times with different starting points.) I’ve heard several people who have worked with GAs report that sometimes switching to randomized hill-climbing, iterated with different initial conditions, gives results more efficiently.

(if nothing else, this is easy to test–just comment out the crossover step!)

7 March, 2009 at 4:10 am

Michael Peake

931 Details of Moser(3), 3-dim

Following on from 914. and 917., 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)

Their sharp linear bounds are :
2a+b+2c+4d <= 22
3a+2b+3c+6d <= 36
7a+2b+4c+8d <= 56
6a+2b+3c+6d <= 48

7 March, 2009 at 12:21 pm

Kristal Cantwell

932. If a Moser set has 125 points or more then it must have at least one cut where the center slice has 39 points or less.

If not all points must have center slice exactly equal to 40, Now one set of outside slices must have scores that sum to 125 or more then by the discussion following lemma 4 of the Wiki on Moser sets in the section devoted to n=5 and the slices must be chosen from the following
• (2,16,24,0,0) [42 points, score: 62]
• (4,16,23,0,0) [43 points, score: 62 1/3]
• (4,15,24,0,0) [43 points, score: 62 3/4]
• (3,16,24,0,0) [43 points, score: 63]

Now since the slice has 40 points the slice must
Contain the slice with 42 points and one of the slices
With 43 points however since the sum is 125 or more
It must contain the bottom slice thus the following is forced
As statistics of slices

(2,16,24,0,0) [42 points, score: 62]
(3,16,24,0,0) [43 points, score: 63]

Now the sum of these two slices is 125
Since the sum of all 5 sets of slices is 625
By lemma 4 of the section devoted to n=5
So we can subtract and get the sum of the
Four remaining slices is 500 but then we can repeat the
Process getting another cut with the same set of statistics of slices
And the three remaining sets of slices equal to 375 we can repeat
The process until we are done and get all 5 slices have the
Following statistics
(2,16,24,0,0) [42 points, score: 62]
(3,16,24,0,0) [43 points, score: 63]

The presence in the above of the 24 in the third position
means that the configuration must have all 80 points
with exactly two twos but by lemma 3 of the Wiki
in the section devoted to n=5 we have that implies
that the configuration has 124 points or less and we are done.

7 March, 2009 at 12:53 pm

Kristal Cantwell

933. If a configuration has 125 or more points
then it must have 6, 7 or 8 points with
no twos.

There must be a cut of the configuration whose outside slices sum to
125 or more.
If it has 40 points it must sum to exactly 125
and since we have the sum of all 5 sets of outside slices
is 125 we can subtract and get the remaining sets of slices
has sum 500 we keep repeating this step until a cut with
center slice 39 or less is chosen this must happen because
we will eventually run out of cuts with center slice 40.
We have shown that there is at least one cut
with center slice 39 or less. Then we will eventually get
a cut whose side slices sum to 125 or more whose
center slice is less than 40 then since we have the side slices
Must be

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]
The center slice must be of size 39 and the choice of the outside slice
with 42 points is not possible then since the values of the remaining
possible slices have a=3 or 4 we must have 6, 7 or 8 points with
no coordinates equal to 2 in the configuration and we are done.

7 March, 2009 at 2:20 pm

Kristal Cantwell

934. If a Moser set with exactly 125 points has exactly 78 points
with two 2’s it must have either 7 or 8 points
with no twos.

We know that it must have 6, 7 or 8 points with
no twos, if it has 6 then it must have 125 minus 78 minus 6
equals 41 points with exactly one two.

Then one of the center slices must contain 9 or more
points with exactly one two in the configuration. But that leads to
A contradiction since the slice is equal to 39 or 40
Take the case where it is equal to 39 We have 4a + b is less than or equal to 64 from the section of the wiki on Moser sets devoted to n = 4. so we have a + b is 39 and 4a + b is 64 or less we can subtract and get 3a is less than 25 so a is less than 9 and we have a contradiction so the center slice must have 40 points
Then again we have 4a + b is less than or equal to 64 from the section of the wiki on Moser sets devoted to n = 4. so we have a + b is 40 and 4a + b is 64 or less we can subtract and get 3a is less than 24 so a is less than 8 but that gives a contradiction so we are done.

7 March, 2009 at 3:47 pm

Terence Tao

935. Moser(3)

I reorganised the Moser wiki page a bit to incorporate the recent progress (and also simplified some of the arguments). It now seems that we have the distribution (A,B,C,D,E,F) of 125-point Moser sets in 5D pinned down to just three possibilities:

* (6,40,79,0,0,0)
* (7,40,78,0,0,0)
* (8,39,78,0,0,0)

It seems that we are reaching the limit of what we can do by analysing slices, and we will have to start understanding sphere packing better…

7 March, 2009 at 4:04 pm

Kareem Carr

guest: “Have you tried a version of your genetic algorithm *without* crossover?”

Thanks for the suggestion. This is only my second genetic algorithm project so I appreciate the input. I tried it without crossover and crossover does seem to help. In the beginning, I tried crossover on the chomosomes with regular crossover points at the one third and two thirds mark. That did seem to be disasterous, leading to very early convergence.

Do you happen to know why it was suggested that crossover not be used? I measure the probability that a particular operator can improve solutions so bad operators are not over used. However, if the issue is early convergence then I have no ideas on defending against that other than automated restarting of the algorithm.

7 March, 2009 at 8:06 pm

Jason Dyer

937. GA improvement

Could you go into detail about how you do this now?

7 March, 2009 at 9:58 pm

Kareem Carr

938. Jason Dyer:

For each element, I figured out the two other elements that are needed to make a line. For instance, 123 means that both 122 and 121 can’t be in the set. For each element, I have all possible pairs that would conflict if they were both elements of the set. If I do a simple transformation of 1->0,2->1 and 3->2 then I get numbers in base three which can then of course be representable as numbers in base 10. Thus I can represent each pair that I need to avoid as two numbers. (This is good as integers can be stored easily in a big table.) So that’s how I store them, I number everything from 0 to 3^n-1 and for each element I have a list of pairs that I have to check for. I store all this in an array where the nth row contains each pair in order.

The solutions are represented as binary numbers of length 3^n where if the mth element of [3]^n is a member of the set then the mth binary digit is set to 1 otherwise it is set to zero.

To check if a solution valid, for each position p, I check row p of my lookup table. I check pair by pair looking at the binary digits corresponding to each pair and making sure they aren’t both set to 1.

For example, my look up table for c_2 is the following:

1 2 3 6 4 8
0 2 4 7 -1 -1
0 1 5 8 -1 -1
0 6 4 5 -1 -1
0 8 1 7 3 5
2 8 3 4 -1 -1
0 3 7 8 -1 -1
1 4 6 8 -1 -1
0 4 2 5 6 7

The -1′s mark the end of the list so my program knows when the list of pairs has ended.

8 March, 2009 at 5:30 am

Michael Peake

939. $c'^6 \le 365$

Use the classification of 3-dim solutions.

The ${}[3]^6$ cube has 160 corner cubes, eg 111***,
240 edge cubes, eg. 112*** and 120 face cubes, 122***

Give the corner cubes a score $s_1 = 0.05a+0.026b + 0.05c + 0.1d$
Give the edge cubes a score $s_2 = 0.074b+0.0415c + 0.0714d+0.1429e$
Give the face cubes a score $s_3 = 0.0755c + 0.0286d + 0.0357e + 0.1f$

From the list of extremal solutions, $s_1 \le 0.556, s_2 \le 0.831, s_3 \le 0.645$

The total score is $a+b+c+d+e+f = 160s_1+240s_2 + 120s_3 < 365.8$

8 March, 2009 at 8:56 am

Kareem Carr

940. Possible lower bounds for c_6 and c_7

I just wanted to give a bit of an update concerning c’_n. My best solutions are:

c’_5: 124 (399 unique solutions – 3 million generations)
c’_6: 353 (26 unique solutions – 3 million generations)
c’_7: 978 (1 solution – 5.4 million generations)

I will put these on my website when I can so that the solutions can be doublechecked. At this point, I can say this is a much harder problem than c_n. I have included the amount of computation that I have thrown at each problem in order to indicate the diminishing returns with increasing n. I think it’s entirely possible that there are larger solutions.

(Sorry I keep forgetting to put the numbers, Terry.)

8 March, 2009 at 9:54 am

Terence Tao

941. $c'_6$

Kareem, it seems that your 6D and 7D solutions are better than those we already had, it will be interesting to analyse their structure. (It occurred to me that one might be able to “seed” a GA by throwing in some decent solutions that we already have and seeing whether evolution will improve it… so perhaps it’s still worth compiling a pool of reasonably good solutions here even if they are non-optimal.)

Incidentally, your 353-point example example shows that the conjecture in 904 is incorrect; either the score a/15+b/10+c/6+d/3+e for 4D sets can exceed 5.8333, or the 353-point example has a nonzero value of f or g. I guess what is going on here is that large values of d or e, which don’t show up in the 41+ point examples, can occur for smaller examples and result in a score larger than that for the big examples.

8 March, 2009 at 12:14 pm

Kristal Cantwell

If a Moser set for n=5 has 125 points
It must have the following statistics:
• (7,40,78,0,0,0) or
• (8,39,78,0,0,0)

Assume it has statistics (6,40,79,0,0,0),
the only remaining case
Now look at the 6 points with all coordinates not
equal to 2. Any set of 5 of these has one pair of
points that differ in exactly two coordinates
See the proof of lemma 3 in the Moser wiki
We start with 5 of these points and get at least one
pair that differs in exactly two coordinates if there is more than
one we choose a pair
Then we remove one of the points the pair and add the
additional point to replace then we have two pairs.

Then we note that each of these pairs of points
has the potential of forming a line with the
point p that has two twos in the coordinates i and j that the pair
of points differ and where the points of the pair have
the same coordinate p has that coordinate now
each such point p has the possibility of blocking two
such lines names those pairs nameless the pair
of points that has 11 and 33 in the coordinates where
p has two twos and the same coordinates as p elsewhere
and the points that have 13 and 31 in the points where
p has two 2’s and the same coordinates elsewhere

Now in the case of this Moser set with
Statistics (6,40,79,0,0,0)
We have two such pairs and since one of 80
Points with two twos is missing to avoid
A line the missing point must block both lines for the two
Pairs as above.

Now we have the from the above
four points which agree
On three coordinates and take on all
possible values on the remaining two coordinates.
They have the potential of forming lines
with those points with one two, namely those
points which agree which agree with the four
points on the the three coordinates mentioned
above and have one two and one arbitrary
value on the remaining two coordinates
there are four such points. The point p
mentoned earlier which agrees with the above
points in the three coordinates mentioned earlier
and has 2’s in the remaining coordinate
forms two lines with these points.
These lines are empty since p or any
of the other four points are in the Moser
set they form a a line with the points
in the two pairs.

The two lines were counted in the
Inequality 2B + C is less than or equal to
160 with weight one half. which is lemma three in the Wiki section n=5
we can remove these two lines and count over the remaining lines
since they are empty 2B +C will not be effected but the 160
will be reduced to 158 so then we will have
2B +C is less than or equal to 158
but 2B+C is 159 in the case with statistics
Statistics (6,40,79,0,0,0)
So only the remaining two statistics are possible and we are done.

8 March, 2009 at 3:29 pm

Terence Tao

943. An alternate proof of $c'_4 \leq 43$

Here is a relatively short, mostly human proof that $c'_4 \leq 43$ using the extremals from the 3D theory.

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 (see the spreadsheet

http://spreadsheets.google.com/ccc?key=p5T0SktZY9DuKZ2DyzO9EOg&hl=en#

) 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 16, a contradiction.

This argument also heuristically explains why the 43-point Moser sets have statistics close to (4,16,24,0,0).

8 March, 2009 at 5:32 pm

Terence Tao

944. $c'_6 \leq 364$

Michael’s method in 939 can be pushed a little bit. Given a Moser set in $[3]^n$ , let $\alpha_i$ denote the fraction of the points with i 2s in the cube that lie in the set; in terms of the (a,b,c,d,e) notation, we have $\alpha_0 = a/2^n, \alpha_1 = b/(n 2^{n-1})$ , etc.

The double counting argument applied to side slices of $[3]^{n+1}$ tells us that any linear inequality between the $\alpha_i$ that holds at dimension n, is also true at dimension n+1. Applying to middle slices instead, we see that any linear inequality between the $\alpha_i$ that holds at dimension n, is also true at dimension n+1 after replacing each $\alpha_i$ with $\alpha_{i+1}$ .

For instance, when n=3 a typical inequality is $2a+b+2c+4d \leq 22$ , which in normalized notation is $8\alpha_0+6\alpha_1+6\alpha_2+2\alpha_3 \leq 11$ . This inequality then holds for all higher n. For $n \geq 4$ we also get the shifted inequality $8\alpha_1+6\alpha_2+6\alpha_3+2\alpha_4 \leq 11$ , for $n \geq 5$ we get $8\alpha_2+6\alpha_3+6\alpha_4+2\alpha_5 \leq 11$ , etc.

Throwing all the inequalities descended from n=3 into a big list and using Maple’s linear programming routines, I can get an upper bound of 44 in four dimensions, 126 in five dimensions, and 364 in six dimensions. Here is the 6D code:

> with(simplex);

> X := [8*a+6*b+6*c+2*d<=11, 4*a+4*b+3*c+d<=6, 7*a+3*b+3*c+d <= 7, 4*b+2*c+d<=4, 4*a+6*c+2*d<=7, 6*a+3*c+d<=5, 2*a+d<=2, 2*b+d <= 2, 2*c+d <= 2, d <= 1, 8*b+6*c+6*d+2*e<=11, 4*b+4*c+3*d+e<=6, 7*b+3*c+3*d+e <= 7, 4*c+2*d+e<=4, 4*b+6*d+2*e<=7, 6*b+3*d+e<=5, 2*b+e<=2, 2*c+e <= 2, 2*d+e <= 2, e <= 1, 8*c+6*d+6*e+2*f<=11, 4*c+4*d+3*e+f<=6, 7*c+3*d+3*e+f <= 7, 4*d+2*e+f<=4, 4*c+6*e+2*f<=7, 6*c+3*e+f<=5, 2*c+f<=2, 2*d+f <= 2, 2*e+f <= 2, f <= 1, 8*d+6*e+6*f+2*g<=11, 4*d+4*e+3*f+g<=6, 7*d+3*e+3*f+g <= 7, 4*e+2*f+g<=4, 4*d+6*f+2*g<=7, 6*d+3*f+g<=5, 2*d+g<=2, 2*e+g <= 2, 2*f+g <= 2, g Z := 64*a+192*b+240*c+160*d+60*e+12*f+g;

> Z := 64*a+192*b+240*c+160*d+60*e+12*f+g;

> maximize(Z, X, NONNEGATIVE);

> evalf(subs(%,Z));

364.6984127

Incidentally, the statistics (a,b,c,d,e,f,g) of the maximiser are

[31.49206349, 94.98412698, 121.9047619, 83.80952381, 25.07936508, 7.428571429, 0.]

or in normalized form $(\alpha_0,\ldots,\alpha_6)$

[0.4920634921, 0.4947089947, 0.5079365079, 0.5238095238, 0.4179894180, 0.6190476190, 0.]

thus one is filling up about half of each Behrend sphere (except for the origin 222222), which seems to be different behaviour from lower dimensions. [Perhaps this is because 6D is the first place where we really have to deal with sets of density less than 1/2.]

Presumably one could use the 4D and 5D data to generate more inequalities to dump into the pot, which should shave this upper bound downwards a bit. (But I did try tossing in the fact that 4D sets have at most 43 points, and (optimistically) 5D sets have at most 124 points, but got no improvement in the 6D bound this way.)

9 March, 2009 at 11:14 am

gilang

Prof. Tao, I am very interested with your blog although i am not a talented in mathematic. But now i will not ask you all about the complexity or what you have posted. My question just simple and for long time with big patient i waiting for propose this quastion for one of the great mathematician. What you feel or crossed in your mind that you are one of the outstanding mathematician ? Can you imagine that when you at 7 years old you just a little boy study mathematic and now you take the control on mathematic, i mean You haved extended Mathematic standpoint not as a student of mathematic anymore? Maybe my question too laud/praise for you and i know you are a humble mathematician as I know. But this is my trully question from my mind with big curiosity to you? I will be glad when you respond my question

9 March, 2009 at 12:00 pm

Kristal Cantwell

945. Moser set n=5.

If a Moser set for n=5 has 125 points
It must have the following statistics:
• (8,39,78,0,0,0)

Assume it does not then the only remaining case
is that it must have these statistics:
• 7,40,78,0,0,0)

Now look at the 7 points with all coordinates not
equal to 2 Any set of 5 of these has one pair of
points that differ in exactly two coordinates
see the proof of lemma 3 in the Moser wiki.
We start with 5 of these points and get at least one
pair that differs in exactly two coordinates if there is more than
one we choose a pair
then we remove one of the points the pair and add the
additional point to replace then we have two pairs. We
keep doing this until we have three pairs.

If a line is to be avoided there must be a point with
two 2’s not in the in Moser set which has 2’s
where the points of the pair differ and for the
points where the pair agree it also agrees, if this
does not happen we will have a line.

Now we have the from the above
we have four points which agree
on three coordinates and take on all
possible values on the remaining two
coordinates.

They have the potential of forming lines
with those points with one two, namely those
points which agree which agree with the four
points on the the three coordinates mentioned
above and have one two and one arbitrary
value on the remaining two coordinates
there are four such points call the a, b,c,d. The point p
mentoned earlier which agrees with the above
points in the three coordinates mentioned earlier
and has 2’s in the remaining coordinate
forms two lines with these points.
these lines are empty since p or any
of the other four points are in the Moser
set they form a a line with the points
in the two pairs.

The two lines were counted in the
Inequality 2B + C is less than or equal to
160 with weight one half. which is lemma three
we can remove these two lines and count over the remaining lines
since they are empty 2B +C will not be effected but the 160
will be reduced to 158 so then we will have
2B +C is less than or equal to 158
but 2B+C is 158 in the case with statistics
Statistics (7,40,78,0,0,0)

Now this gives 2B+C for the remaining lines is less
Than or equal to 158 but 2B+C in this case = 158
Which means that every line must have exactly two points
We will use this fact in the proof that follows by starting
With empty points taking lines that aren’t the set that
Have the empty set and hence have to have the remaining
Point in the line we will use these points to force a line
In the set and thus get a contradiction.

For the empty set we start with the points a, b, c, d
Mentioned earlier have one two we are going
To force the existence of two sets of four points
Similar to a,b,c,d
They are identical to points of a, b, c,d except
In one coordinate.

Let us assume that the points
Of p have the following form 111xy where
The fixed coordinates are assumed to be 1
And in the first three places and x and y are
The moving coordinates. Then a b c d
Are of the form 11121, 11123, 11112, 11132.
The two new sets of similar to a b c d
Are 13121, 13123, 13112, 13132 and
11321, 11323, 11312, 11332 we get that
they must be in the Moser set by the above
and looking at lines 1×121, 1×123, 1×112, 1×132
and 11×21, 11×23, 11×12, 11×32
where x denotes a coordinate that may take
any of three values which are
not in the lines removed and hence by the above
must have 2 points and hence give us the 8 new
points mentioned above in the Moser set.
Now we note that the points
13121, 13123, 13112, 13132
together with 13122 forms a monochromatic line
in fact two monochromatic lines so the 13122
must not be in the set since we already have
11122 is not in the set all other points with
two twos must be in the set now
look at the points 11321, 11323, 11312, 11332
which must be in the set
together with 11322 which must be in the set they
form a monochromatic line in the set so we get
a contradiction.

Similarly we can form 8 such points
from the points p and a, b, c and d above
no matter what the value of the the fixed coordinates
and no matter the position of the fixed coordinates
and force a monochromatic line in the same way
and the get a contradiction so the only case remaining
is: that having statistics (8,39,78,0,0,0) and we are done.

9 March, 2009 at 12:33 pm

Kristal Cantwell

946. Note on 945

I should not have put the word monochromatic before line in several
cases in the second to last paragraph.

9 March, 2009 at 1:11 pm

Kristal Cantwell

947. Rewrite of 942

If a Moser set for n=5 has 125 points
It must have the following statistics:
• (7,40,78,0,0,0) or
• (8,39,78,0,0,0)

Assume it has statistics (6,40,79,0,0,0),
the only remaining case.
Now look at the 6 points with all coordinates not
equal to 2 in the set. Any set of 5 of these has one pair of
points that differ in exactly two coordinates
See the proof of lemma 3 in the Moser wiki.
We start with 5 of these points and get at least one
pair that differs in exactly two coordinates if there is more than
one we choose a pair
Then we remove one of the points the pair and add the
additional point to replace then we have two pairs.

Then we note that each of these pairs of points
has the potential of forming a line with the
point p that has two twos in the coordinates i and j that the pair of points differ and where the points of the pair have
the same coordinate p has that coordinate. So p must be absent from the Moser set. Now
each such point p has the possibility of blocking two
such lines. the pair of points that has 11 and 33 in the coordinates where
p has two twos and the same coordinates as p elsewhere
and the points that have 13 and 31 in the points where
p has two 2’s and the same coordinates elsewhere.

Now in the case of this Moser set with
statistics (6,40,79,0,0,0)
We have two such pairs and since only one of 80
points with two twos is missing to avoid
a line the missing point must block both lines for the two
pairs as above.

Now we have from the above
four points which agree
on three coordinates called fixed coordinates and take on all
possible values on the remaining two coordinates.
They have the potential of forming lines
with those points with one two, namely those
points which agree with the four
points on the three fixed coordinates mentioned
above and have one two and one arbitrary
value on the remaining two coordinates.
There are four such points.
They must be absent from the Moser set
to avoid formin a line.
The point p
mentioned earlier which agrees with the above
points in the three fixed coordinates
and has 2’s in the remaining coordinate
forms two lines with these points.
These two lines are empty since p or any
of the other four points are not in the Moser
set .

The two lines were counted in the
inequality 2B + C is less than or equal to
160 with weight one half. which is lemma three in the Wiki section n=5
we can remove these two lines and count over the remaining lines
since they are empty 2B +C will not be effected but the 160
will be reduced to 158 so then we will have
2B +C is less than or equal to 158
but 2B+C is 159 in the case with statistics
(6,40,79,0,0,0).

So only the remaining two statistics are possible and we are done.

9 March, 2009 at 1:30 pm

Kristal Cantwell

948. Rewrite of 945.

If a Moser set for n=5 has 125 points
It must have the following statistics:
• (8,39,78,0,0,0)

Assume it does not then the only remaining case
is that it must have these statistics:
• 7,40,78,0,0,0)

Now look at the 7 points in the set with all coordinates not
equal to 2 Any set of 5 of these has one pair of
points that differ in exactly two coordinates
see the proof of lemma 3 in the Moser wiki.
We start with 5 of these points and get at least one
pair that differs in exactly two coordinates if there is more than
one we choose a pair
then we remove one of the points the pair and add the
additional point to replace then we have two pairs. We
keep doing this until we have three pairs.
If a line is to be avoided there must be a point with
two 2’s not in the in Moser set which has 2’s
where the points of the pair differ and for the
points where the pair agree it also agrees, if this
does not happen we will have a line.

Now from the above
we have four points which agree
on three coordinates called fixed coordinates and take on all
possible values on the remaining two
coordinates.

They have the potential of forming lines
with those points with one two, namely those
points which agree with the four
points on the three fixed coordinates mentioned
above and have one two and one arbitrary
value on the remaining two coordinates
there are four such points call them a,b,c,d. The point p
mentioned earlier which agrees with the above
points in the three coordinates mentioned earlier
and has 2’s in the remaining coordinate
forms two lines with these points.
these lines are empty since if p or any
of the other four points are in the Moser
set they form a line with the points
in the two pairs.

The two lines were counted in the
Inequality 2B + C is less than or equal to
160 with weight one half. which is lemma three
we can remove these two lines and count over the remaining lines
since they are empty 2B +C will not be effected but the 160
will be reduced to 158. So then we will have
2B +C is less than or equal to 158
but 2B+C is 158 in the case with statistics
(7,40,78,0,0,0)

Now this gives 2B+C for the remaining lines is less
Than or equal to 158 but 2B+C in this case = 158.
Which means that every one of the remaining lines must have exactly two points.

We will use this fact in the proof that follows by starting
with the points a, b, c, d which as noted above are not in the Moser set. Taking lines from the remaining lines that
contain a, b, c or d and hence have to have the remaining
point in the line. We will use these points to force a line
In the set and thus get a contradiction.

We start with the points a, b, c, d
mentioned earlier. We are going
to force the existence of two sets of four points
similar to a,b,c,d
They are identical to points of a, b, c, d except
in one coordinate.

Let us assume that the points
Of p have the following form 111xy where
The fixed coordinates are assumed to be 1
And in the first three places and x and y are
The moving coordinates. Then a b c d
Are of the form 11121, 11123, 11112, 11132.
The two new sets of similar to a b c d
Are 13121, 13123, 13112, 13132 and
11321, 11323, 11312, 11332 we get that
they must be in the Moser set by the above
and looking at lines 1×121, 1×123, 1×112, 1×132
and 11×21, 11×23, 11×12, 11×32
where x denotes a coordinate that may take
any of three values which are
not in the lines removed and hence by the above
must have 2 points and hence give us the 8 new
points mentioned above are in the Moser set.
Now we note that the points
13121, 13123, 13112, 13132
which by the above must be in the Moser set
together with 13122 forms a monochromatic line
in fact two monochromatic lines so the 13122
must not be in the Moser set.

Since we already have
11122 is not in the set all other points with
two twos must be in the set now
look at the points 11321, 11323, 11312, 11332
which must be in the set
together with 11322 which must be in the Moser set by the above they
form a monochromatic line in the Moser set so we get
a contradiction.

9 March, 2009 at 3:36 pm

Kristal Cantwell

949. A Moser set for n=5 has 124 points

A Moser set for n=5 has 124 points.
If it doesn’t it must have 125 points since we have shown that a contradiction results if there are more than 126 points. Since it has 125 points
it must have the following statistics:
• (8,39,78,0,0,0)

Now look at the 8 points in the Moser set with all coordinates not
equal to 2 Any set of 5 of these has one pair of
points that differ in exactly two coordinates
see the proof of lemma 3 in the Moser wiki.
We start with 5 of these points and get at least one
pair that differs in exactly two coordinates if there is more than
one we choose a pair
then we remove one of the points the pair and add the
additional point to replace then we have two pairs. We
keep doing this until we have four pairs.

There must be points with exactly 2 coordinates equal to two for each of the coordinates where the pairs differ with coordinates. We have four pairs and only two possible points absent from the Moser set as we see by looking at the statistics. Now each of these points can block at most two of the lines formed by a pair. Since those coordinates constant in a pair must be constant in the point as well so only pairs which agree with the point on these constant coordinates can be blocked and there are only two such pairs for each set of three constant coordinates. They are the following points those which agree on the constant coordinates and have all 1’s or all 3’s on the remaining coordinates or the remaining two points which agree on the constant coordinates. Since we have four pairs and only two points with exactly two 2’s missing from the Moser set they must block the four lines formed by all four pairs. Each point blocks two lines.

Call these two points $p_1$ and $p_2$ .
Now from the above
we have two sets of four points. Each set agrees
on three coordinates called fixed coordinates and takes on all
possible values on the remaining two
coordinates.

Each set has the potential of forming lines
with those points with one two, namely those
points which agree with the four
points on the three fixed coordinates mentioned
above and have one two and one arbitrary
value on the remaining two coordinates
there are four such points for each set. The points $p_1$ and $p_2$ mentioned earlier
each form two lines with one set of four points mentioned above. So we have four such lines. These lines are empty since if $p_1$ or $p_2$ or any
of the either set of four points are in the Moser
set they form a line with the points
in the four pairs.

The four lines were counted in the
Inequality 2B + C is less than or equal to
160 with weight one half. which is lemma three
we can remove these four lines and count over the remaining lines
since they are empty 2B +C will not be effected but the 160
will be reduced to 156. So then we will have
2B +C is less than or equal to 156
but 2B+C is 156 in the case with statistics
(8,39,78,0,0,0)
Now this gives 2B+C for the remaining lines is less
Than or equal to 156 but 2B+C in this case = 156.
Which means that every one of the remaining lines must have exactly two points.
We will use this fact in the proof that follows by starting
with one set of four points with exactly one two which are associated with $p_1$ . Which as noted above are not in the Moser set. Taking lines from the remaining lines that
contain these and hence have to have the remaining
point in the line. We will use these points to force a line
n the set and thus get a contradiction. We will have to do this for two sets of four points because one of the sets formed might be the other set of four points associated with the other two pairs. However this can be dealt with because there are enough degrees of freedom to pick two and in fact three such sets of four points.
Let us assume that the points
Of two pairs forming one of the sets noted above have the following form 111xy where
The fixed coordinates are assumed to be 1
And in the first three places and x and y are
The moving coordinates. Then a b c d
Are of the form 11121, 11123, 11112, 11132.
The two new sets are
13121, 13123, 13112, 13132 and
11321, 11323, 11312, 11332 we get that
they must be in the Moser set by the above
and looking at lines 1×121, 1×123, 1×112, 1×132
and 11×21, 11×23, 11×12, 11×32
where x denotes a coordinate that may take
any of three values which are
not in the lines removed and hence by the above
must have 2 points and hence give us the 8 new
points mentioned above are in the Moser set unless the exception is as noted above that one of the two groups of 4 is the group of four points associated with the other set formed by the points of the other two pairs. In any case we will have one set of four points out of the two sets of four points that must be in the Moser set.
Now we note that these points without loss of generality can 13121, 13123, 13112, 13132. The proof is essentially the same for both cases.
These points by the above must be in the Moser set.
together with 13122 forms a line in fact two lines. Now if 13122 is not in the Moser set it must be one of $p_1$ or $p_2$ however by construction it cannot be $p_1$ and if it were $p_2$ then the set of four points 13121, 13123, 13112, 13132 would be the second set formed by the second set of two pairs associated with $platex p_2$ but we have chosen these points so that does not occur so it is in the Moser set.
So we have a line in the Moser set so we have a contradiction.

Similarly we can form 8 such points
from the four pairs above
no matter what the value of the fixed coordinates
and no matter the position of the fixed coordinates
and force a monochromatic line in the same way
and the get a contradiction so the only case remaining
is: that having statistics (8,39,78,0,0,0) and we are done.

9 March, 2009 at 6:01 pm

Terence Tao

950. Moser(3)

Kristal, this is great! I haven’t yet had time to go through the arguments and wikify them but I will get round to it at some point.

The next step will be to try to reduce the dependence on computer data. I think the classification of 3D extremals will help out a lot here. There are some very specific facts we need from the 4D data (e.g. no 41+ points sets with d >= 4, etc.) and it may well be that the inequalities coming from the 3D theory are enough for this. This should be checkable with Maple, and then a posteriori we can then write down a human proof.

Incidentally, I have submitted $c''_n$ to the OEIS at

http://www.research.att.com/~njas/sequences/A157795

9 March, 2009 at 7:40 pm

Terence Tao

951. Moser(3)

I’ve put Kristal’s arguments on the wiki. It would be good for others to go through the proof and keep an eye out for any corrections or simplifications. The points where the n=4 data is relied on should be inspected particularly carefully, to see if alternate arguments are available.

9 March, 2009 at 8:46 pm

Kareem Carr

c’_7
The 978 point solution:
http://twofoldgaze.wordpress.com/2009/03/10/978-element-solution/

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

9 March, 2009 at 8:50 pm

Kareem Carr

953.

My program is still running for the next few hours so I can’t access it yet but it seems I just found a 985 solution for c’_7.

9 March, 2009 at 10:13 pm

Kareem

954. (It’s hard to keep these posting numbers straight when sleep deprived.)

My largest solution for c_7 is 988. One more caveat, the algorithm I used to display the long form solutions has a bug in it. I will correct it soon.

9 March, 2009 at 10:14 pm

Kareem

955.

The term c_7 in my last comment should be c’_7.

9 March, 2009 at 10:34 pm

Kareem Carr

956.

The good news is that I corrected the bug and the solutions on my blog are correct now. I updated my 978 solution to a 988 solution. There is some bad news unfortunately. The long form solutions that I provided for c_n are probably all wrong in the same way. So stick with the short form solutions for now. For a quick fix, if things look wrong just shift the element to the one just below it so 113 -> 112 and so on. I will fix it as soon as I can.

9 March, 2009 at 10:55 pm

Kareem Carr

957.

Terry:

I thought your suggestion of solution seeding was a great idea so I implemented it using a stock of better than 972 solutions. Then I spent some time visualizing the solutions and I realize they have patterns. So I checked to see what parts of the chromosomes are conserved between solutions and that seems to be an effective form of solution seeding also.

http://twofoldgaze.files.wordpress.com/2009/03/visualization1.pdf

http://twofoldgaze.files.wordpress.com/2009/03/visualization2.pdf

guest: I thought a little more about your comment and decided to give it a more rigorous evaluation. I spent some time with a notepad and a pencil carefully noting the effectiveness of crossover. Paradoxically, without mutation crossover with a stocastic sort of greedy algorithm seemed to improve the solutions 5% of the time which was approximately the same as not doing crosover. However, when I implement crossover with mutation (with an underlying greedy algorithm to ensure no missed opportunities), 20% of the time crossover improves a solution versus 15% for mutation. Something about mutation seems to be boosting the effectiveness of crossover. (When I say it improves a solution, I mean a random solution in the population is improved, not necessarily the best solution.)

10 March, 2009 at 5:19 am

Michael Peake

958. Moser(3), dim-5

There is one step I am not sure of. The proof of Lemma 7 relies on slices with non-zero d having scores of 59 7/12 or below. But there are two examples in the list, with d=3 and d=2, with higher scores than that.

10 March, 2009 at 7:18 am

Terence Tao

959. 5D Moser(3)

Thanks Michael. Fortunately one can rule out the d>1 cases by observing from Lemma 7 that there is a way to cut the cube so that the side slices have at most one C-point missing (i.e. one side has c=24 and the other has c at least 23) and no D-points, and hence the middle slice has at most one D-point. I’ve updated the wiki appropriately.

There is also an alternate approach from Cantwell.912, Cantwell.913. Both approaches rely to some extent on the 4D statistics. It would be good to have an alternate proof of this fact which relied less on these statistics (e.g. relying more on the 3D inequalities, which are human-verifiable).

10 March, 2009 at 4:53 pm

Michael Peake

5D Moser(3)

Congratulations to Kristal on doing three quarters of the proof, and for completing the proof.

10 March, 2009 at 5:15 pm

Terence Tao

Yes, congratulations! It looks like this project is achieving many of its intended objectives; by a coincidence of timing, the same is true of the other half of the project at Gowers’ blog. There is now a retrospective discussion there at

http://gowers.wordpress.com/2009/03/10/polymath1-and-open-collaborative-mathematics

; I think some feedback from our side of the project would be valuable.

There are a few loose ends to tie up, I think: the proof of $c'_6=124$ could be simplified, with less of a dependence on computer data; and it would be interesting to see how the genetic algorithm performs for some other numbers, whether there are any cheap ways to improve its performance, and what an analysis of its solutions can tell us about what $c'_7$ (say) might look like. There’s also the hyperoptimistic conjecture to look at; we have some computer data now but our human-level understanding of the problem is fairly primitive still. But I think we are in general moving to the “endgame” and should begin thinking about issues such as how to write things up (I plan to comment on this over at Tim’s blog in a bit).

10 March, 2009 at 10:56 pm

Link Starbureiy

Congratulations to all of you on a job well done over the past weeks!

11 March, 2009 at 1:34 am

Klas Markström

961. HOC
I have done some more work on the weighted problem in the HOC and I found the results interesting.

I have not been able to prove that I have optimal values for n greater than 5, but for n=6 there is a unique solution of weight 15, which is the size of the optimal solution for Fujimura’s problem. Likewise there is a unique solution of weight 18 for n=7. The solutions are here
http://abel.math.umu.se/~klasm/solutions-n=6-k=3-HOC
http://abel.math.umu.se/~klasm/solutions-n=7-k=3-HOC
In order to find these solutions I have specified that the program should look for all solutions of this exact weight. For n=7 the program find a solution and then prove that it is the only one in 4 seconds. For n=8 the integer program suddenly gets a lot harder to solve and the program has not yet found a solution.

The tricky thing is that for this problem it is much harder to reduce the upper bound for the integer program ( I have multiplied all weight in the program by n! to get integer weights).
For n=6 I expect to soon have reduced the upper bound on the optimal solutions to strictly less than 16, again having to use a linux cluster. However, since we don’t know that the optimum for this problem is an integer the upper bound does not imply that the unique solution of weight 15 is the optimum, and reducing the bound to 15 seems too hard for my current program.

There is an interesting contrast here. For Fujimiura’s problem the number of optimal solutions seems to grow, on the average, with n, but if the solutions for n=6,7 for the weighted problem are optimal then this problem has a unique optimal solution for n=4,5,6,7

11 March, 2009 at 1:37 am

Klas Markström

And congratulations to Kristal for proving an upper bound which was too hard for my program!

11 March, 2009 at 2:35 am

Christian Elsholtz

962 Moser

Congratulations to Kristal!!

Here is a comment on the symmetry of the Moser sets.
The Moser sets in dimension 5, with 124 points:
The statistics of all 243 points is: (32,80,80,40,10,1)
The statistics of the known examples is: (4,40,80,0,0)

For each of the 40 and 80 points the antipodal point is included.
For the 4 points with no 2 there are example with no antipodal pairs, and there is
an example where 2 of the 4 points are antipodal, the other 2 are not.

To the best of my knowledge no symmetric solution (with regard to the
centre) is known to exist.
If the 124 solutions should all come from the same 40+80 points,
then there are no 4 symmetric points.

Those examples in dimension 6 (344 points) and 7 (960 points), that were
implicitly in Chvatal’s paper, Canadian Math Bulletin, Vol 15, 1972, 19-21.
“Remarks on a problem of Moser”, based on (elementary) bounds from coding
theory, contained some full Behrend spheres,
and some rather empty ones, so were in a similar spirit to the one above.

The better examples by Kareem Carr
353 points, have distribution
(22, 66, 165, 100, 0, 0 0)
out of
(64, 192, 240, 160, 60, 12, 1) for all 729 points, so have no almost full sphere.

The study of antipodal points of the 353 example on Kareems webpage gives
65 pairs of antipodal points
45 of these with two 2′s, and 20 with three 2′s.

For the 988 example in dimension 7 on Kareem’s webpage with distribution:
(36, 65, 336, 551, 0, 0, 0, 0)
compared to (for all 2187 points)
(128, 448, 672, 560, 280, 84, 14, 1)
let us make the following observations:
1) The sphere with three 2′s is quite full.
2) there are 272 antipodal pairs,
271 of these with three 2′s, and one pair with one 2.
(Of course there must be many antipodal pairs, if a sphere is almost
full).

Perhaps this gives a heuristical clue how good examples in some further
medium sized dimensions look like.
One almost full sphere, with (dimension/2) 2′s and in the other
partial spheres:
if point x occurs, then the antipodal does not occur.

Remarkably, the behaviour in dimension (2 to 5), 6 and now 7 are so
different…

In any case, perhaps this helps finding good “seeds” for the algorithm?

11 March, 2009 at 7:38 am

Kareem Carr

963. Christian Elsholtz:

If you will give me a few days to make them available, I have 25 other solutions of length 353 that might be interesting. Perhaps they have different properties.

11 March, 2009 at 7:47 am

Terence Tao

964. Dimension transition in Moser(3)

Two comments… it seems that the best solutions in 6D and 7D we have so far are avoiding all but the first four Behrend spheres (the strings with 0, 1, 2, or 3 twos). To speed up the GA, perhaps we could simply assume that all other spheres are empty and remove those chromosomes from the genotype. (I believe this will cut down the number of lines by a significant factor – quite a few lines pass through the inner spheres).

The second comment is that I think one reason for the transition is that in 5D and lower, the optimal solutions have density >1/2, and in 6D and higher, the optimal solutions have density <1/2. The thing is that the linear inequalities we have on sphere densities cannot rule out the possibility that every sphere has density 1/2 or less. Consider for instance the 3D case, in which the full set [3]^3 has statistics (8,12,6,1), so a mythical “half-density” Moser set would have statistics (4,6,3,0.5). Of course this is not possible, however the statistics (4,6,4,0) and (4,6,2,1) are possible, and so from the perspective of linear inequalities, nothing is preventing half-densities everywhere. I don’t know whether the same is true in 4D: half of (16,32,24,8,1) is (8,16,12,4,0.5), and I don’t know whether this is attainable as a convex combination of Moser 4D statistics. But this phenomenon may help explain the tendency for the higher D statistics to fill out about half of every sphere. (This also matches with the linear programming I did in 944.)

11 March, 2009 at 9:47 am

Jason Dyer

965. HOC

I checked the solution in Markström.961 of n=6, which is the same as the equal slice solution 510, 420, 330, 240, 150, 501, 402, 303, 204, 105, 015, 024, 033, 042, 051. (It’s all combinations of 1 & 2, 2 & 3, and 1 & 3.)

This is the same solution as the general bound for Fujimura of that size.

11 March, 2009 at 9:55 am

Jason Dyer

966. HOC

A quick scan indicates the same thing applies to n=7.

Klas, look for a solution of 21 on n=8 and see if you get one solution just like the general bound for Fujimura. If so I am guessing the HOC is false.

11 March, 2009 at 12:18 pm

Kristal Cantwell

Thank you to everyone for the congratulations! My congratulations to everyone here and also those who worked on the other half of this project. I will be working on proving there are no sets with 41 or more points with d greater than or equal to 4.

11 March, 2009 at 1:24 pm

Kareem Carr

967. Terry:

“Two comments… it seems that the best solutions in 6D and 7D we have so far are avoiding all but the first four Behrend spheres (the strings with 0, 1, 2, or 3 twos). ”

It turns out I had already been doing something like this when I tried to preserve the conserved regions between solutions. I had been looking at the conserved regions set to zero and the ones set to one both together and singly. I noticed that the conserved zero region (points consistently left out) turned out to be of length 379 (which I didn’t check by hand) but is the same size as the set of points with strings with four or more 2′s.

In the same spirit, I had a region of conserved one’s which turns out to contain 411 points. Perhaps someone else will see the pattern.

{13, 31, 37, 39, 41, 43, 49, 67, 85, 91, 93, 95, 97, 103, 111, 117, 119, 123, 125, 127, 133, 139, 145, 147, 149, 151, 157, 175, 193, 199, 201, 203, 211, 229, 247, 253, 255, 257, 259, 273, 275, 277, 281, 285, 287, 289, 291, 295, 301, 307, 311, 313, 319, 325, 327, 331, 333, 335, 339, 341, 343, 345, 347, 349, 353, 369, 371, 375, 379, 383, 385, 387, 389, 393, 395, 397, 399, 401, 409, 415, 417, 419, 421, 433, 437, 443, 447, 449, 451, 453, 455, 457, 469, 471, 473, 475, 481, 499, 517, 523, 525, 527, 535, 553, 571, 577, 579, 581, 583, 599, 601, 603, 605, 609, 611, 613, 615, 617, 619, 631, 635, 643, 661, 679, 685, 687, 689, 691, 697, 733, 739, 745, 751, 757, 761, 773, 775, 781, 787, 793, 797, 799, 805, 813, 815, 819, 825, 829, 833, 837, 839, 845, 855, 861, 865, 867, 869, 871, 873, 879, 881, 889, 903, 905, 907, 913, 921, 923, 925, 927, 933, 937, 939, 941, 949, 955, 957, 959, 961, 967, 981, 983, 987, 989, 991, 993, 995, 999, 1001, 1007, 1017, 1019, 1023, 1031, 1035, 1037, 1047, 1049, 1055, 1059, 1061, 1071, 1077, 1109, 1115, 1125, 1127, 1133, 1135, 1145, 1149, 1151, 1155, 1157, 1159, 1181, 1185, 1189, 1191, 1193, 1195, 1197, 1199, 1203, 1207, 1211, 1225, 1227, 1229, 1231, 1237, 1243, 1247, 1249, 1251, 1253, 1261, 1263, 1265, 1281, 1297, 1299, 1301, 1305, 1307, 1315, 1317, 1321, 1325, 1341, 1347, 1349, 1351, 1353, 1355, 1357, 1365, 1367, 1369, 1371, 1373, 1375, 1381, 1387, 1389, 1399, 1405, 1407, 1409, 1411, 1415, 1419, 1421, 1423, 1425, 1427, 1435, 1441, 1443, 1447, 1453, 1471, 1489, 1495, 1497, 1525, 1543, 1549, 1551, 1553, 1555, 1561, 1567, 1569, 1571, 1573, 1575, 1577, 1585, 1587, 1589, 1597, 1603, 1605, 1607, 1633, 1651, 1657, 1659, 1661, 1663, 1669, 1687, 1705, 1711, 1713, 1715, 1729, 1733, 1735, 1737, 1739, 1745, 1747, 1749, 1751, 1753, 1759, 1765, 1767, 1769, 1777, 1783, 1785, 1787, 1791, 1797, 1801, 1803, 1805, 1807, 1809, 1811, 1817, 1827, 1829, 1833, 1835, 1837, 1841, 1843, 1845, 1847, 1853, 1855, 1857, 1859, 1861, 1875, 1877, 1879, 1885, 1891, 1893, 1895, 1897, 1899, 1901, 1905, 1911, 1915, 1921, 1927, 1931, 1933, 1939, 1981, 1983, 1985, 1987, 1993, 2011, 2029, 2035, 2037, 2039, 2047, 2053, 2055, 2057, 2059, 2061, 2063, 2067, 2069, 2071, 2073, 2075, 2077, 2083, 2091, 2093, 2095, 2101, 2137, 2143, 2145, 2147, 2149, 2155, 2173}

11 March, 2009 at 2:53 pm

Christian Elsholtz

the 411 points above all have 3 two’s.
Otherwise coordinate stastistics alone will not help, since it contains for example the points
{2, 2, 2, 1, 1, 1, 3}, {2, 2, 2, 1, 1, 3, 1}, {2, 2, 2, 1, 1, 3, 3}, {2, 2, 2, 1, 3, 1, 1},
{2, 2, 2, 1, 3, 3, 1}, {2, 2, 2, 3, 1, 1, 3}, {2, 2, 2, 3, 1, 3, 3}, {2, 2, 2, 3, 3, 1, 1}, {2, 2, 2, 3, 3, 1, 3},
{2, 2, 2, 3, 3, 3, 3} etc.
that is some but not all permutations of 2221113.
It also pairs of points with Hamming distance 1.

11 March, 2009 at 4:14 pm

Terence Tao

969. Integer programming

I discovered an integer programming package (Optimization) on Maple 12, and gave it a whirl, see

http://michaelnielsen.org/polymath1/index.php?title=Maple_calculations

for details. I reconfirmed the fact that by throwing in all the linear inequalities we already know about, we can get $c'_6 \leq 364$ . The extremal statistics are

(31,94,126,83,23,7,0). (*)

[In comparison, Kareem's 353-point solution has statistics (22, 66, 165, 100, 0, 0 0).]

If we can find some reason why the statistics (*) are impossible, this should eventually be convertible to a linear inequality which I can then add to the integer program to improve the bound. Hopefully we can iterate this computer+human procedure to get the bounds to be closer to each other.

If I assume g=1 (i.e. the point 222222 is in the set), then the upper bound improves substantially to 355, with extremal (24,96,120,80,30,4,1). If instead I assume e=f=g=0 as in Kareem’s example, the upper bound similarly improves to 356, with extremal (24,72,180,80,0,0,0).

The 7D computations were disappointing; the best upper bound I could get was 1092, i.e. 3 times the current 6D bound.

11 March, 2009 at 5:09 pm

Terence Tao

770. Linear programming

There are some more inequalities available. For instance in 4D, we have $a+b+c+d+e \leq 43$ , but when e=1, we have the better estimate $a+b+c+d+e \leq 39$ (which I also verified by linear programming). Thus we in fact have $a+b+c+d+5e \leq 43$ . Similarly, the $c'_5=124$ result gives $a+b+c+d+e+f \leq 124$ in 5D, but when f=1 the linear inequalities improve this to 119, thus $a+b+c+d+e+6f \leq 124$ .

I inserted this into the integer program. Sadly, this did not improve the upper bound $c'_6 \leq 364$ , but it did give a prettier extremiser, namely (32,96,120,80,30,6,0), i.e. every Behrend sphere except for the last one is filled with density exactly 1/2. Also, this argument managed to improve the bound for $c'_7$ from 1092 to 1086.

The wiki page is adjusted to reflect these improvements, of course.

11 March, 2009 at 5:43 pm

Terence Tao

771. Linear programming

I found a 4D inequality which was inconsistent with the above 1/2-density scenario, and it gave some good results (basically it is useful for eliminating scenarios in which d, e, etc. are large).

It exploits the fact that the 41+ 4D solutions have small d and e. Indeed, the data shows that e=0 and a+b+c+d+e+d/2 <= 43 for such solutions. Meanwhile, linear programming shows that for 40- point solutions, one has a+b+c+d+e+d/2 <= 43, and furthermore a+b+c+d+e+d/2 <= 40.5 if e=0. We conclude that a+b+c+d+e+d/2+5e/2 <= 43. Inserting this into the integer programming machine gives significant improvements, namely $c'_6 \leq 360$ and $c'_7 \leq 1075$ .

To proceed further, one needs to find a reason why the $c'_6$ extremiser statistics, which happen to be (29,87,134,97,8,5,0), are not attainable. It may also be useful to figure out why the e=f=g=0 extremiser statistics (24, 72, 180, 80, 0, 0, 0) are not attainable; the densities here are quite clean, namely (3/8, 3/8, 3/4, 1/2, 0, 0, 0).

Wiki page updated as before.

11 March, 2009 at 5:53 pm

Kareem Carr

Christian Elsholtz:

Interesting points. The one thing I would add is that the 411 are probably not perfect as they are based on a guess of the better solutions found so far. Although, I realize I should have taken them more seriously as I was very surprised to see that the 379 zero points conserved matched so well with the Behrend spheres.

12 March, 2009 at 12:37 am

Klas Markström

972 HOC

Jason, I ran the program for n=8 and solutions of weight 21. The program quickly found a solution and in a few minuets proved that it is the unique solutions of that weight.
The solution is here
http://abel.math.umu.se/~klasm/solutions-n=8-k=3-HOC-21

12 March, 2009 at 5:49 am

Jason Dyer

973. A semi-optimist conjecture

Thanks Klas! Now I can say…

For $n > 2$ , $c^\mu_n = 3(n-1)$

This implies at least the optimist conjecture (if not the original version of the HOC, which I guess was an inequality?) which implies DHJ (3).

12 March, 2009 at 8:58 am

Terence Tao

974. Linear programming

I made a data entry error causing the bounds announced earlier to be off a little bit. Currently I can show $c'_6 \leq 361$ and $c'_7 \leq 1078$ , with the 361 bound improving just to 360 if one assumes e=f=g=0, and to 355 if one assumes g=1. The 361 extremiser is (28,80,160,80,10,3,0).

Jason, I am not sure I understand what you are getting at here. Every solution to Fujimura gives a solution to weighted DHJ, so $c^\mu_n$ always has to be at least as large as $\overline{c}^\mu_n$ ; in particular, $c^\mu_8$ has to be at least $\overline{c}^\mu_8=22$ .

Actually, this now confuses me quite a bit. Back in 923, 925, Klas found 72 22-point triangle-free sets in n=8. This will imply the existence of many 21-point triangle-free sets also, simply by removing one point from these examples. One can convert this to having many line-free sets with weight 21 in 8D, but the integer program tells us that there is only a unique solution… so something is strange somewhere.

12 March, 2009 at 10:29 am

Jason Dyer

975. HOC

Oh yes, even though the weights of the individual points represented by the edges of the lattice are larger, each complete slice has a weight that adds up to 1. This *is* really odd.

12 March, 2009 at 11:05 am

Kristal Cantwell

976. Moser set n=4

Here I am proving a partial result. Eventually I want to get the following:
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 six or more points with three 2’s it must have less than 41 points. We note that there cannot be a point with four 2’s as then we would have 39 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.

12 March, 2009 at 11:12 am

Klas Markström

977. HOC
This got me really worried too so I have been checking things and I think I have found the problem.

In order to get an integer problem with integer coefficients I multiplied all weights with n!. For small n this is perfectly fine but for the larger n this will actually cause the bound used to specify a solution of a given weight to be too large for the datatype the linear programing solver uses for coefficients.

So I created formally correct input files for the solver, but the weights are to large for the solver I have been using. This means that the claimed uniqueness in the weighted problem for n greater than 5 is meaningless.

For the other problems all weights and coefficients are 0/1 so they do not suffer from this.

12 March, 2009 at 6:29 pm

Jason Dyer

978. Making c^mu_n tractable

This is starting to get frustrating to work with in that we have no good way to approach c^mu_n by hand. Is there at least a conjecture we can make here that if true which might help us get a handle on it?

12 March, 2009 at 9:23 pm

Terence Tao

979. $c^\mu_n$

Well, we may have to go back to the very small values of n. For instance, I can work out $c^\mu_2 \leq 4$ by hand, but already $c^\mu_3 \leq 6$ is rather challenging. My guess is that we should be looking at the slice densities $\alpha_{a,b,c} := |A \cap \Gamma_{a,b,c}|/|\Gamma_{a,b,c}|$ of the line-free set A, and finding linear relations between them, perhaps to throw into an integer program to maximise $c^\mu_n$ , which is the maximal sum of all the $\alpha_{a,b,c}$ . (This of course sounds a lot like what Klas is doing, but this will be an integer program on $\binom{(n+1)(n+2)}{2}$ variables rather than $3^n$ variables, and so has a chance of being scaled up to reasonable values of n, such as 6 or 7.) We actually did a little bit of this way back in the 200 thread (see e.g. Jakobsen.210, Jakobsen.216, Tao.219, Peake.220).

We know that given any equilateral triangle, the sum of the $\alpha_{a,b,c}$ in that triangle adds up to at most 2. This should already give some bound; after finding that bound, we can see how to improve it.

13 March, 2009 at 7:11 am

Christian Elsholtz

980 Linear Programming.

In 770 Terry described that improvements on bounds of type
4D: $a+b+c+d+5e \leq 43$ etc help improving bounds in dimension 7.

I expect, that for In dimension 4, with e=1 a much better result holds.
In 778 KS Chua mentioned that the best example of this type he found had
36 points, (and his programme found a 124 point example in 5D).

Also, those programmes that classified the 43 extremisers could hopefully
be adapted to verify the maximum number of points in 4D.

If 36 is the maximum, this gives
$a+b+c+d+8e \leq 43$

Similar, for 5D I would expect a considerable gain over the currently used
$a+b+c+d+e+6f \leq 124$ .

13 March, 2009 at 8:28 am

Terence Tao

981 Linear programming

Christian: yes, that’s a great idea. Inserting the improvements to $a+b+c+d+e \leq 43$ that we already had were already instrumental in killing off the large e (or large f,g) counterexamples in 6D, 7D, and improved their bounds significantly (from 164 to 161 in 3D, and from 1092 to 1078 in 3D). Further such improved estimates would undoubtedly do better, and perhaps even eradicate e, f, g entirely in 6D (note that Kareem’s examples have e=f=g=0).

Another inequality that could stand improving is the inequality $a+b+c+d+e + d/2 + 5e/2 \leq 43$ in 4D. For e=0 this comes by inspection of the 41+ point data (in particular, the fact that d is so small in this regime) plus use of the existing 3D inequalities for 40- point data (somewhat analogous to Kristal’s 976). For e=1 I am relying purely on the linear programming from the 3D inequalities. Getting a better upper bound for a+b+c+d+e+d/2 in the e=1 case (currently it is 40.5) would help.

I quite like this approach as it wastes as little as possible: any “excess” estimate one gets in, say, 4D, can be recycled into improvements in 5D and higher.

This may well be the way to go for the HOC. For n=2, say, we should be able to classify the Pareto-optimal and extremal statistics for the slice densities $\alpha_{a,b,c}$ , giving linear inequalities. These inequalities then imply analogues in 3D, which we could then integer program and apply further combinatorial analysis to beget further linear inequalities to use in 4D, and so on and so forth.

13 March, 2009 at 10:32 am

Michael Peake

982 Moser(3) Diagonal cubes in 6D

The 6D cube contains 120 3D cubes of the form xxyyzz. The two xs take the values (11,22,33) or (13,22,31), and the same with the two ys and two zs.

Each point in the 3D cube contains 0,2,4 or 6 twos, so this introduces a set of new inequalities connecting a,c,e and g.

These inequalities are easiest to express in the density notation $\alpha_i$ . One of the inequalities for the simple 3D cube is $8\alpha_0 + 6\alpha_1 + 6\alpha_2 + 2\alpha_3 \le 11$ . The corresponding inequality for these diagonal cubes is $8\alpha_0 + 6\alpha_2 + 6\alpha_4 + 2\alpha_6 \le 11$ .

I don’t know whether these inequalities provide new information. Certainly the solution $\alpha_i = 1/2$ , which satisfies all the old 3D inequalities, satisfies the new ones too.

13 March, 2009 at 10:42 am

Terence Tao

983 6D Moser(3) diagonal cubes

Thanks Michael! Actually I had put those cubes in the linear program already (it’s the term op(subs([b=c,c=e,d=g],X3)) in the definition of X6) but I had forgotten to tell people about this. But yes, it does help. Without it, the bound on $c'_6$ stays where it as at 361, but the bound on $c'_6$ under the additional assumption g=1 worsens from 355 to 358. (It makes sense that this new inequality is really of use when g is non-zero.) This cuts down the inequality a+b+c+d+e+f+7g <= 361 to a+b+c+d+e+f+4g <= 361, which ends up worsening the $c'_7$ bound from 1078 to 1079.

There are also cubes in which each wildcard occurs a different number of times (e.g. 1xyy23) but I was unable to figure out how to use those “skew” cubes to generate more inequalities.

13 March, 2009 at 12:10 pm

Kevin O'Bryant

984. I don’t see anywhere anybody taking up question II.A: what exactly is the bound that comes out of the Behrend/Elkin construction?

Elkin’s bound is $r_3(n) > C n (\log n)^{1/4} 2^{-\sqrt{8 \log_2 n}}$ . He stated it just for n of a particular form, but it works for all n. The second ingredient is that $\binom{n}{a,b,c}$ , this size of $\Gamma_{a,b,c}$ is at least $C 3^n/n$ provided that all of a, b, c, are between $n/3- \sqrt n$ and $n/3+\sqrt n$ . The final ingredient is that if $x_i$ (with $1\leq i \leq 3$ ) are a line and $x_i$ is in $\Gamma_{a_i,b_i,c_i}$ , then $c_i-a_i$ are a (possibly constant) arithmetic progression of integers.

Now to put these together. Let R be a largest set of integers without 3-term APs that is contained in $(-\sqrt{n}/2,\sqrt{n}/2)$ . The set $A = \bigcup_{c-n/3 \in R} \Gamma_{n/3,b,c}$ has no lines, and has size at least $\sum_{c-n/3\in R} \binom{n}{n/3,b,c}$ . For each element r of R, we can take $c=r+n/3$ and $b=n/3-r$ , in which case $\binom{n}{n/3,b,c} > C 3^n /n$ . The size of A is then at least $C r_3(\sqrt{n}) \cdot C 3^n/n$ , which is at least $C (\log n)^{1/4} \exp_3(n- \alpha \sqrt{\log_3 n})$ , and $\alpha=2\sqrt{\log_3(2)}$ . Here, $\exp_3(x)$ is shorthand for $3^x$ .

As I write this, it doesn’t feel very optimal to set $a=n/3$ , instead of letting it vary at least a little. In particular, I am unpleased by the asymmetry.

13 March, 2009 at 12:51 pm

Kristal Cantwell

985. c^{\mu}_3=6

If we have all
Three points of the form aaa removed
Then the remaining points have value 7 and
We have covered all lines that have any set of moving coordinates
And all constant points equal to one value this leaves
The lines xab a,b not equal. Each point of the set
abc covers three of these lines the entire set covers each of these lines
there is no duplication the only alternative is to remove a point
abc and cover the lines with points of the form aab which have
a higher weight and only cover two lines each this would lower the weight
so the maximum weight occurs when all of abc is omitted along with
the three points aaa and that weight is 6.

If we have only two points removed of the form xxx then
The weight is at most 8 say the point not removed is 222
Then we must cover the lines xx2 and x22 we have three six such
Lines and all the xx2 must be covered one at a time by either 112
Or 332 the x22 must be covered one at a time by 322 or 122
These points must be removed and the that lowers the weight
To 8 – 3*(2/6) – 3*(2/6) = 6 again we have c^{\mu} must be less than 6

If we have one point removed say 111 then we must cover all lines of
The form xx2 xx3 and x22 and x33 the best we can do is to cover
Two of these at once as no point can cover x22 and x33 or xx2 and xx3
Only points of the form xxy can cover these lines and as we have 12 lines
Covering 2 at a times we must have 6 such lines which will have weight 3/6
So we will have removed one point with weight one and 6 more
With weight 1/2 giving remaining weight 6 or less for the remaining points.

Finally we have no points of the form xxx removed but then we will
have a line of the form xxx so we must have the earlier three cases and the weight of the points not removed can be at most 6.

13 March, 2009 at 1:25 pm

Kristal Cantwell

986. Second try at c^{\mu}_3=6

I don’t think the previous proof works I made some changes.

c^{\mu}_3=6
If we have all
Three points of the form xxx removed
Then the remaining points have value 7 and
We have covered all lines any set of moving coordinates
And all constant points equal to one value this leaves
The lines xab a,b not equal. Each point of the set
abc covers three of these lines the entire set covers each of these lines
there is no duplication the only alternative is to remove a point
abc and cover the lines with points of the form aab which have
a higher weight and only cover one line each this would lower the weight
so the maximum weight occurs when all of abc is omitted along with
the three points xxx and the weight is 6

If we have one point removed say 111 then we must cover all lines of
The form xx2 xx3 and x22 and x33 the best we can do is to cover these lines
Two of at once as no point can cover x22 and x33 or xx2 and xx3
And we have all points of the form aab when a = 2 and b =3
Or b=2 and a=3
Only points of the form xxy can cover these lines and as we have 12 lines
Cover 2 at a times we must have 6 such lines which will have weight 2/6
So we will have removed one point with weight one and six more
With weight 1/3 giving remaining weight 7 and we will have
Lines of the form x11 and xx1 to cover as well as x12 and x13
The lines of the form x11 will have to be covered by 3 lines with
Weight 1/3 however we are not done as we can split a point of the
Form 223 into 113 and 221 then we will cover the lines 22x and xx3
With two lines instead of one but we will cover one line of the
Form 11x however we due this we will either have to split
3 pairs and we will have weight 6 since 7-1=6 or split two
and use one point of the form 11x for the remaining line of the
form 11x or again the total is 6 or split one and use 2 and again
the remaining points total 6.

Finally we have no points of the form xxx removed but then we will
have a line of the form xxx

13 March, 2009 at 1:42 pm

Michael Peake

986. 4D Moser(3) Diagonal cube

There are 12 3D cubes that fit diagonally in 4D, with coordinates xxyz, where xx = (11,22,33) or (13,22,31), and y and z both range over (1,2,3).

Their points have (a,b,c,d,e) = (8,8,6,4,1)
So each a-point is in 6, each b-point in 3, c-pt in 3, d-pt in 6, e-pt in 12

Of the solutions without a coordinate line, there were 37 Pareto-optimal solutions and the following ten extremal solutions.

(34321),(42321),(44221),(44311),(24440), (42340),(44240),(44600),(48400),(80000).

These satisfy $2a+b+2c+2d+4e \le 24, 4a+b+2c+2c+4e \le 32$ and $a \le 8, b\le 8, c \le 6, d \le 4, e\le 1$

The inequality for the 4D set is 4A + B + 2C + 4D + 16E \le 96
8A + B + 2C + 4D + 16E \le 128

13 March, 2009 at 2:07 pm

Jason Dyer

987. c^{\mu}_3=6 (rephrased)

Just to make sure I understand I am rephrasing Kristal’s proof.

Consider the line 111, 222, 333. Either one is removed, two are removed, or three are removed. (It’s impossible to have zero removed — we are left with the line.)

Suppose all three are removed. Then we are left with 18 disjoint lines represented by a single wildcard. This can be done by removing all points on the slice \Gamma_{1,1,1}; each removal takes out 3 of the disjoint lines and we are left a weight of 6. Removing from the hexagon of slices 120-012-012-102-201-210 removes only 2 disjoint lines at a time with a higher weight, so the removal we’ve already found is optimal.

Suppose two are removed, leaving (suppose, noting symmetry) 222. Then we are left with disjoint lines **2, 2**, *2* (corresponding to the slices \Gamma_{2,1,0} and \Gamma_{0,1,2} and *22, 2*2, 22* (corresponding to the slices \Gamma_{1,2,0} and \Gamma{0,2,1}). There must be one removal for each of the six disjoint lines, removing a weight of 2 and leaving a weight of 6.

While I was typing Kristal changed her proof of one removed, so I’ll finish the rest later. :)

13 March, 2009 at 2:44 pm

Jason Dyer

988. c^{\mu}_3=6 question

Looking at your new one point proof: Kristal, are you sure we assume the slices $\Gamma{0,2,1}$ and $\Gamma{0,1,2}$ have to be removed? (It’s what you call “points of the form aab when a = 2 and b =3
Or b=2 and a=3″.) Even though it’s non optimal to pick two from one of the other slices it doesn’t put us quite over the weight limit (and shouldn’t be too hard to prove that it will) but since it’s not an immediate contradiction we can’t just assume we pick the locally optimal scenario.

13 March, 2009 at 2:49 pm

Michael Peake

989. 5D Moser(3) containing diagonal cubes xxyyz

Following on from 986. A 5D Moser cube contains 60 3D cubes diagonally, in the form xxyyz. Each contains points (a,b,c,d,e,f) = (8,4,8,4,2,1).

The sets without geometric lines have 42 Pareto maxima and the following 13 extrema:
(324211),(413211)(422211)(424111)(424201)(224420)(413320), (424220)(444020)(422410)(424400)(448000)(800000)
giving the following ten inequalities
$4\alpha + \beta+2\gamma +2\delta + \epsilon + \phi \le 5.5, 2\epsilon + \phi \le 2, 4\alpha+4\gamma+2\delta+\epsilon+\phi \le 6, 4\alpha+2\beta+2\gamma+2\delta+\epsilon+\phi \le 6, 7\alpha+\beta+2\gamma+2\delta+\epsilon+\phi\le 7, 4\alpha+2\epsilon+\phi\le 4, 8\alpha+4\gamma+2\delta+\epsilon+\phi \le 8, 8\alpha+2\beta+2\gamma+2\delta+\epsilon+\phi \le 8, 4\alpha+2\beta+2\delta+2\epsilon+\phi \le 6, 8\alpha+2\beta+2\delta+2\epsilon+\phi \le 8$

13 March, 2009 at 3:15 pm

Terence Tao

990. Diagonal Moser cubes

Michael, this is great! I of course plunked the inequalities into the linear program at

http://michaelnielsen.org/polymath1/index.php?title=Maple_calculations

to see what improves. The 4D bound for a+b+c+d+e+d/2 for e=1 improved from 41.5 to 40, giving a new inequality a+b+c+d+e+d/2 + 3e <= 43. The 5D bound a+b+c+d+e+f <= 119 for f=1 improved to 117, giving a new inequality a+b+c+d+e+f+7f <= 124. The $c'_6$ bound unfortunately did not budge at 361, but the extremal changed (e and f became even smaller), suggesting that at least some of the 361-point cases were eliminated. When g=1, the bound dropped from 355 to 352, which is below Kareem’s example and thus demonstrates for the first time that g=0 for the $c'_6$ extremiser.

In 7D, the bound for $c'_7$ improved from 1078 to 1073, and when h=1 there is a further improvement from 1071 to 1065. So the new inequalities are having an impact…

13 March, 2009 at 5:10 pm

Michael Peake

991. Diagonal Moser cubes

Inequalities arising from xxxyz diagonals:
Letters a to f are densities
8a+4b+2c+2d+4e+2f <=11
4a+2b+1c+2d+2e+1f <= 6
0a+0b+2c+0d+0e+1f <= 2
4a+4b+1c+0d+2e+1f <= 6
7a+2b+1c+1d+2e+1f <= 7
8a+2b+1c+2d+2e+1f <= 8
4a+0b+2c+0d+0e+1f <= 4
4a+0b+2c+2d+2e+1f <= 6
8a+0b+2c+2d+2e+1f <= 8
8a+4b+1c+0d+2e+1f <= 8

Inequalities arising from xxxxyz diagonals
a,b,c,e,f,g are densities. These cubes do not intersect the d slice
8a+4b+2c+2e+4f+2g <= 11
0a+0b+2c+0e+0f+1g <= 2
4a+2b+1c+2e+2f+1g <= 6
7a+2b+1c+1e+2f+1g <= 7
4a+0b+2c+0e+0f+1g <= 4
4a+0b+2c+2e+2f+1g <= 6
8a+0b+2c+2e+2f+1g <= 8
8a+2b+1c+2e+2f+1g <= 8
4a+4b+1c+0e+2f+1g <= 6
8a+4b+1c+0e+2f+1g <= 8

Inequalities from xxxyyz diagonals
Letters a to g are densities
4a+2b+0c+3d+1e+1f+1g <= 6
4a+0b+2c+3d+1e+1f+1g <= 6
8a+2b+0c+3d+1e+1f+1g <= 8
8a+0b+2c+3d+1e+1f+1g <= 8
0a+4b+0c+0d+2e+0f+1g <= 4
0a+0b+4c+0d+0e+2f+1g <= 4
8a+4b+0c+0d+2e+0f+1g <= 1
8a+0b+4c+0d+0e+2f+1g <= 1

13 March, 2009 at 8:39 pm

Terence Tao

992.

Michael, there seems to be something wrong with your third set of inequalities (xxxyyz), for instance they are inconsistent with the densities a=1, b=c=d=e=f=g=0, which is of course feasible. Perhaps the weighting is a bit off?

13 March, 2009 at 10:10 pm

Kevin O'Bryant

993. Question II.A revisited

Post 984 is a bit off, as I used $n$ in a place I should have had $\sqrt{n}$ . Here’s an improved construction, with corrected analysis of its size.

It comes down to this: $c_n > C 3^{n - 4\sqrt{\log 2}\sqrt{\log n}+\frac 12 \log \log n}$ for some absolute constant $C$ , and where all logarithms are base-3.

For convenience, let $n$ be a multiple of 3. Elkin’s bound gives $r_3(\sqrt{n}) > C \sqrt{n} (\log n)^{1/4} \exp_2(-2 \sqrt{\log_2 n})$ , and let $R$ be a subset of $(-3\sqrt{n}/2,3\sqrt{n}/2)$ without 3-term APs and with size $r_3(\sqrt{n})$ , and with all elements being integer multiples of 3 (again as a matter of convenience). For each $r,s\in R$ , let $a = (n-r-s)/3$ . The set $A$ is the union of all $\Gamma_{a,a+r,a+s}$ . Since all of $a, a+r,a+s$ are between $n/3-2\sqrt{n}$ and $n/3+2\sqrt{n}$ , the size of $\Gamma_{a,a+r,a+s}$ is at least $C 3^n / n$ . Since there are $r_3(\sqrt{n})^2$ choices for $r$ and $s$ , we have a set with size at least
$C (\sqrt{n} (\log n)^{1/4} \exp_2(-2 \sqrt{\log_2 n}))^2 3^n / n.$
This simplifies to $C \sqrt{\log n} \exp_3(n-\alpha \sqrt{\log_3(n)})$ , where $\alpha=4 \sqrt{\log_3(2)}$ , assuming my algebra holds this time.

Now suppose that $x_i\in \Gamma_{a_i,a_i+r_i,a_i+s_i}$ is a combinatorial line in the set $A$ . Then $(a_i+s_i)-(a_i)=s_i$ is a 3-term AP contained in $R$ , so the $s_i$ are all the same. Similarly, all of the $r_i$ are the same, and therefore all of the $a_i$ are the same, too. But this implies that the $x_i$ sequence is constant, which means the line is degenerate.

13 March, 2009 at 11:18 pm

Michael Peake

993. Moser’s diagonal cubes – correction

Hi Terry. Thanks for checking that.

The last two inequalities for xxxyyz should have 8 on the RHS.
8a+4b+0c+0d+2e+0f+1g <= 8
8a+0b+4c+0d+0e+2f+1g <= 8
The extremals for xxxyyz are
(4113111),(3223111),(2224220),(4113220),(4224200), (4223011),(4226000),(4222220),(4422020),(4224020), (4222111),(4223101),(4242200),(4444000),(8000000)

I checked the other inequalities, and I believe they are correct.
The density inequalities for xxyz, which I didn’t give above, are
4a+2b+3c+2d+e <= 6
8a+2b+3c+2d+e <= 8

14 March, 2009 at 6:04 am

Seva

994. While all the major players are (supposedly) still out there, I wonder whether anything intelligent can be said on the smallest possible size of a Kakeya set in ${\mathbb F}_3^r$ . Let’s denote it $k_r$ ; thus, $k_r$ is the smallest integer for which a set $K\subset {\mathbb F}_3^r$ exists such that $|K|=k_r$ and for every $d\in {\mathbb F}_3^r\setminus\{0\}$ , the set $K$ has a line in the direction $d$ . (A line in the direction $d$ is, of course, a three-element set of the form $\{a-d,a,a+d\}$ .)

Clearly, we have $k_1=3$ , and it is easy to see that $k_2=7$ . Using a computer, I also found $k_3=13$ and $k_4\le 27$ . I suspect that, indeed, $k_4=27$ holds (meaning that in ${\mathbb F}_3^4$ one cannot get away with just $26$ elements), and I am very curious to know whether $k_5=53$ : notice the pattern in

$3,7,13,27,53,\ldots$

As to the general estimates, we have

$k_r(k_r-1)\ge 3(3^r-1)$

and, on the other hand,

$k_r\le 2^{r+1}-1:$

the former since for each $d\in {\mathbb F}_3^r\setminus\{0\}$ there are at least three ordered pairs of elements of a Kakeya set with difference $d$ , the latter due to the fact that the set of all vectors in ${\mathbb F}_3^r$ such that at least one of the numbers $1$ and $2$ is missing among their coordinates is a Kakeya set. (I actually can improve the lower bound to something like $k_r\gg 3^{0.51r}$ .) Also, we have the trivial inequalities

$k_r\le k_{r+1}\le 3k_r;$

can the upper bound be strengthened to $k_{r+1}\le 2k_r+1$ ?

14 March, 2009 at 8:37 am

Terence Tao

995. Thread moving

As is now our tradition, I’m declaring this thread full and am moving to the 1100-1199 thread at

http://terrytao.wordpress.com/2009/03/14/dhj3-1100-1199-density-hales-jewett-type-numbers/

I’ll try to respond to several of the interesting new comments on this thread at the other thread.

14 March, 2009 at 8:37 am

DHJ(3): 1100-1199 (Density Hales-Jewett type numbers) « What’s new

[...] March, 2009 in math.CO | Tags: polymath1 | by Terence Tao This is a continuation of the 900-999 thread of the polymath1 project, which is now full. We’ve made quite a bit of progress so far on [...]

	Sandeep Murthy on An elementary non-commutative…
	Luqing Ye on 245A, Notes 2: The Lebesgue…
	Frank on Soft analysis, hard analysis,…
	andrescaicedo on Soft analysis, hard analysis,…
	Richard Palais on Pythagoras’ theorem
	The Coffee Stains in… on Does one have to be a genius t…
	Benoît Régent-Kloeck… on (Ingrid Daubechies) Planning f…
	Luqing Ye on 245B, Notes 7: Well-ordered se…
	Luqing Ye on 245B, Notes 7: Well-ordered se…
	Arjun Jain on 245B, Notes 7: Well-ordered se…
	Daniel on About
	%anchor_text% on Books
	Luqing Ye on 245B, Notes 7: Well-ordered se…
	Arjun Jain on 245B, Notes 7: Well-ordered se…
	Luqing Ye on 245A, Notes 2: The Lebesgue…

DHJ(3): 900-999 (Density Hales-Jewett type numbers)

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

Google+ feed

Tags

The Polymath Blog

Mathematics in Australia

110 comments

Leave a Reply Cancel reply

For commenters

Follow “What's new”

DHJ(3): 900-999 (Density Hales-Jewett type numbers)

Share this:

Like this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

Google+ feed

Tags

The Polymath Blog

Mathematics in Australia

110 comments

Leave a Reply Cancel reply

For commenters

Follow “What's new”