Bounds for the first few density Hales-Jewett numbers, and related quantities

13 February, 2009 in math.CO, polymath | Tags: polymath1

This thread is a continuation of the previous thread here on the polymath1 project. Currently, activity is focusing on the following problems:

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. Thanks to efforts from previous threads, we have the first five values of $c_n$ :

$c_0=1; c_1=2; c_2=6; c_3=18; c_4=52$ .

We also know that $150 \leq c_5 \leq 154$ , and are working to narrow this further. The arguments justifying these bounds can be found here. The latest bounds for the next few values of $c_n$ can be found 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, we know the following values for these sequences:

$c^\mu_0 = 1; c^\mu_1 = 2; c^\mu_2 = 4$

and

$\overline{c}^\mu_0 = 1; \overline{c}^\mu_1 = 2; \overline{c}^\mu_2 = 4; \overline{c}^\mu_3 = 6; \overline{c}^\mu_4 = 9; \overline{c}^\mu_5 = 12$ .

There are also some further upper and lower bounds known; see this spreadsheet for the latest bounds, and this page for proofs of the bounds. The data so far is consistent with the conjecture, but more work would be needed to obtain a more convincing case for it.

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 = 14; c'_4 = 43$ .

The best asymptotic lower bound known is $c'_n \gg 3^n/\sqrt{n}$ . Given that we have a significantly superior lower bound of $c_n \geq 3^{n-O(\sqrt{\log n})}$ for $c_n$ , one might hope to similarly improve the lower bound for Moser’s problem. But there seems to be a technical snag, based on the observation that between two slices $\Gamma_{a,b,c}$ and $\Gamma_{a',b',c'}$ with the $c-a=c'-a'$ , there are in fact quite a few combinatorial lines connecting them, and so it is not obvious how to create a geometric line-free set that involves more than one slice per value of c-a.

It is also of interest to work out what asymptotic lower bound for $c_n$ one can get for larger values of k than 3.

Comments on this thread should start at 700. We will also try to record progress made at the polymath1 wiki and at the polymath1 spreadsheet, as appropriate.

About these ads

103 comments

Comments feed for this article

14 February, 2009 at 7:02 am

Thomas Sauvaget

700. bound on $c_5$ , then on $c_n$

in order not to burden this thread I’m inviting any other attempts along the lines of 275 to be discussed at:

http://thomas1111.wordpress.com/2009/02/14/a-proof-that-c_5154/

and if things work out we’ll report a brief summary back here and in the wiki, after the (possibly longish) trial/error period. Currently I’ve found a new pattern for $c_5$ which requires independent confirmation/infirmation.

14 February, 2009 at 8:03 am

Terence Tao

701. bound on $c_5$ .

By the way, one cautionary note: I think any line-free subset of the 162-element set $D_5 = \{ x_1 x_2 x_3 x_4 x_5: x_1+\ldots+x_5 \neq 0 \hbox{ mod } 3 \}$ must have at most 150 points. Proof: one can view $D_5$ as ${}[3]^5$ with $\Gamma_{(a,b,c)}$ deleted for the triples $(a,b,c) = (0,0,5), (1,1,3), (2,2,1), (0,3,2), (1,4,0), (3,0,2), (4,1,0)$ . From the triples $(5,0,0), (2,0,3), (2,3,0)$ one more point needs to be deleted, and similarly for $(0,5,0), (2,0,3), (0,3,2)$ . Meanwhile, from the triples $(4,0,1), (1,0,4), (1,3,1)$ five more points need to be deleted, and similarly for $(0,4,1), (0,1,4), (3,1,1)$ , leading to at most 150 points overall.

at least one point needs to be deleted from

14 February, 2009 at 10:02 pm

Michael Peake

702. Lower bound for Moser’s cube

The following set gives a lower bound of $n(n+1)2^{n-3}$ points for Moser’s cube:

Take all points with two 2s, and all those with one 2 and an odd number of 1s.

14 February, 2009 at 10:31 pm

Michael Peake

703. Lower bound for Moser’s cube

Should the asymptotic lower bound for Moser’s cube be $12^{n/3}/\sqrt{n}$ ?

Now that I’ve read the page on Moser’s cube, you can take all points with q 2s, and all those with q-1 2s and an odd number of 1s, to give $\binom{N+1}{q}2^{N-q}$ points, where q is the nearest integer to N/3

14 February, 2009 at 10:47 pm

Terence Tao

704. Lower bound for Moser’s cube

Dear Michael, I think Stirling’s formula will show that $\binom{N+1}{q} 2^{N-q}$ is roughly $3^N / \sqrt{N}$ . (One can also see this from the binomial formula $3^{N+1} = \sum_{q=0}^{N+1} \binom{N+1}{q} 2^{N-q+1}$ and the law of large numbers, which shows that the bulk of the sum comes from the region $q = N/3 + O(\sqrt{N})$ .)

15 February, 2009 at 12:08 am

Michael Peake

705. Bounds for $c'_n$

Oh, I see. Thanks.

I think I can squeeze in some more points with N/6-1 1s, and N/6 2s,
but they will be relatively few.

BTW it must be a quarter century since we last met, at Vern’s classes.
I’m delighted to be in this, which is sort of one of your classes.

15 February, 2009 at 7:44 am

Klas Markström

706. The value of c_5 is 150

I formulated the problem as an integer programing instance and solved it using some of my linear programming tools. The program quickly finds a solutions with 150 points and then reduces the upper bound to 150 in less than 2 minutes

My program correctly gives the known values for the lower c_n and the correct number of solutions for them as well.

There are 12 different extremal configurations for c_5.

I have started a run for c_6

15 February, 2009 at 9:05 am

Terence Tao

707. $c_5$

Klas, that’s quite impressive! (For comparison, the fact that $c''_6 = 112$ took some time to be done by hand.) It would be great if some data or source code for the run could be made available somewhere (e.g. on the wiki).

The Moser number c’_5 might also be in reach now (it is somewhere between 120 and 129, according to the spreadsheet). [By the way, to the anonymous contributor of the lower bounds for the Moser problem: if you could describe the examples either here or on the wiki page for the Moser problem, that would be great!]

15 February, 2009 at 11:18 am

Kristal Cantwell

708. If c_5 is 150 than if the spreadsheet is correct c_6 is 450. Clearly
c_6 is less than or equal to 3 times c_5 and we have a lower bound
of 450 so that forces c_6 to be 450. c_7 is between 1302 and 1350 since we have a lower bound of 1302 and by the same reasoning 3 times 450 is
1350.

15 February, 2009 at 11:48 am

Kristal Cantwell

709. A052979 was the last sequence in the OEIS which might have been equal to the sequence c_n but the two sequences diverge if c_5 equals 150.

15 February, 2009 at 1:48 pm

Terence Tao

710. I’ve provisionally updated the spreadsheet to reflect the upper bound for $c_5$ . (It seems consistent with the difficulties Thomas has been experiencing in trying to improve the lower bound below 150.) If we have a complete list of all the extremisers for $c_5$ , then it looks likely that one will be able to shave a couple points off of the upper bound 1350 from $c_7$ , though it seems rather unlikely that we will be able to close the gap with the lower bound of $1302$ without a massive computational effort. Still, this is much more of the sequence $c_n$ computed than I would have initially thought possible, if it all checks out…

15 February, 2009 at 2:04 pm

Klas Markström

711. c_5

Terry, I can upload the file with the linear program in a standard format which can be read by e.g. the open source linear programing solver glpk from gnu.
The integer programing formulation is quite simple. One 0/1-variable for each point in the cube, and one linear inequality for each combinatorial line.

I have a file with the 12 extremal sets for c_5 which I can also upload.

I am running the c_6 case to see if I can find the extremal sets there too, but it is considerably harder and I have moved it to a linux cluster where it will run over night. (It’s now late in the evening in Sweden)

I did a quick check for the Moser-problem and it seem less well suited for integer programing. I could quickly verify the value of 43 for n=4, but for n=5 the integer gap is much larger than it was for c_5, and that means that it will take a lot longer to run. But I can give it a try later.

15 February, 2009 at 2:43 pm

Terence Tao

712. $c_6$

If $c_5 = 150$ , then as noted in 708, $c_6=450$ and so every $c_6$ extremiser is formed from three $c_5$ extremisers. If there are only 12 $c_5$ extremisers, then one should be able to fairly quickly exhaust the $12^3=1728$ combinations to find all the $c_6$ extremisers. (There are also some symmetries of the problem that might be deployable to cut down the search space by a factor of 6 or so.)

It may also be possible to get the computer to classify near-extremisers, e.g. 149-element line-free subsets of $[3]^5$ . This may then be able to lower the upper bound of $c_7 \leq 1350$ somewhat.

15 February, 2009 at 4:48 pm

Michael Peake

713. Lower bounds for Moser cubes

Dear Terry.707,

I am sorry, that was me who entered the lower bounds. I forgot to log into Google before I did so.

My logic was as I described in 702 and 703. You can include all points with q 2s and half of those with q-1 2s.

Any combinatorial line can only have one entry vary. In one of the endpoints, it has an odd number of 1s. So all combinatorial lines are excluded.

15 February, 2009 at 5:29 pm

jozsef

714. Lower bound for Moser’s cube

We would like to find some restriction on the number of 0-s, 1-s, and 2-s that makes the appearance of a geometric line impossible, but still allows many points. If $a$ denotes the number of 0-s and $c$ denotes the number of 2-s, then fixing the number of 1-s means that we select a,b pairs that a+c = constant. (this is our best solution so far) There is another way to avoid lines; If A and C denote the sets of a-s and c-s, then if the difference set of A, A-A , and the difference set C-C are disjoint then triples (a,*,c) won’t form geometric lines. Now, if $A , C \subset [m]$ then it is easy to choose them being “difference-disjoint” and that the product |A||C| is about m. This gives the same bound as the a+c=constant trick. But I’m not sure that one can’t find two larger difference-disjoint sets A and C. That would improve our lower bound instantly.

15 February, 2009 at 5:43 pm

Terence Tao

715. Lower bound for Moser’s problem

Dear Jozsef, if $A, C \subset [m]$ are such that $|A| |C| > 2m$ , then by the pigeonhole principle there must be a collision in the sumset A+C, i.e. a non-trivial solution to a+c=a’+c’ with $a,a' \in A$ and $c,c' \in C$ . Then a-a’=c’-c, and so A-A and C-C have non-trivial intersection. So I think this method may not give a substantial improvement over the current example.

15 February, 2009 at 5:49 pm

Terence Tao

716. Genetic algorithms

This is perhaps not something to pursue too seriously here (it would take a non-trivial programming effort, unless someone just happens to have an off-the-shelf piece of GA software lying around), but it would be amusing to see how well a genetic algorithm would fare with trying to maximise the size of a line-free set. It’s tempting to use blocks of, say, $[3]^2$ as “genes” that can be swapped around between competitor sets, possibly with some transposon genes to mix the blocks up a little. (The evolution of the “phenotype” in Thomas’s blog post might give an illustration of how such an algorithm would develop, sans the “intelligent designer” of course ;-) .)

More generally, this problem might serve as a reasonable one for benchmarking a number of standard algorithms (we’ve discussed greedy algorithms, integer programming, genetic algorithms, SAT solvers, and quadratic programming in previous comments).

15 February, 2009 at 6:00 pm

jozsef

717. Lower bound

Terry, re. 715, yes you are right, however we might handle such cases by considering only some a, c pairs. In general, we can ask what is the max number of edges in a bipartite graph between A and B which still avoids lines. (i.e. by taking (a,*,c) points only where a,c is an edge can’t form lines) If it true that the number of edges of such graph is always at most m?

15 February, 2009 at 6:33 pm

jozsef

718. Lower bound

Well, it seems that any bipartite graph between $A\subset [m]$ and $C\subset [m]$ which avoids lines has at most m edges. A graph avoids lines iff there are no parallel edges; one edge between a and c and another connecting a+d and c+d. This shows that simply considering the number of 0-s, 1-s, and 2-s can’t give us a better bound than what we have.

16 February, 2009 at 4:00 am

Michael Peake

719. Lower bound for Moser, k=4

A straightforward lower bound for Moser’s cube k=4 (values 0,1,2,3) is:
q entries are 1 or 2; or q-1 entries are 1 or 2 and an odd number of entries are 0.

$\binom{N}{N/2}2^N + \binom{N}{N/2-1}2^{N-1}$

I think this is $O(4^N/\sqrt{N})$

16 February, 2009 at 5:48 am

Jason Dyer

720. Multi-dimensional tic-tac-toe

Busy weekend! Are we ready for the OEIS, or should we try a proof by hand that c_5 = 150 first?

I haven’t done much other than realize there might be something about our problem in the literature relating to multi-dimensional tic-tac-toe, and indeed the very first to explore it were Hales and Jewett. (Was this how DHJ was started, or did this occur later?)

This article from Contemporary Combinatorics seems to be the most recent treatment.

16 February, 2009 at 9:03 am

jozsef

721. Lower bound for Moser, k=4

Michael, re. 719, you have a better bound by selecting elements where the total number of 1-s and 2-s is n/2. Similar to the k=3 case, one can argue that this is the best possible bound if you only consider the numbers of 0-s,1-s,2-s, and 3-s. For k=5 the situation is better, there we have an arithmetic progression-like sequence just by considering the sizes of digits.

16 February, 2009 at 9:09 am

jozsef

722. Lower bound for Moser, k=4

contd. It seems that this is practically the same bound as yours, Michael. Sorry for not noticing. I’ll have a morning coffee before writing anything more …

16 February, 2009 at 9:33 am

jozsef

723. Lower bound for Moser, k=5

If A, B, C, D, and E denote the numbers of 0-s, 1-s, 2-s, 3-s, and 4-s then the first three points of a geometric line form a 3-term arithmetic progression in A+E+2(B+D)+3C. So, for k=5 we have a similar lower bound for the Moser’s problem as for DHJ k=3.

16 February, 2009 at 9:45 am

Klas Markström

721. Files for c_5=150
I’m a bit short on time today but I want to make the data for c_5 available. I have put the two files on my webserver, temporarily.
If someone is willing to put them in a suitable place in the wiki then that would be great.

This file contains the extermisers. One point per line and different extermisers separated by a line with “—”
http://abel.math.umu.se/~klasm/extremal-c5

This is the linear program, readable by Gnu’s glpsol linear programing solver, which also quickly proves that 150 is the optimum.
http://abel.math.umu.se/~klasm/linprog-d=5-t=3.lpt
Each variable corresponds to a point in the cube, numbered according to their lexicografic ordering. If a variable is 1 then the point is in the set, if it is 0 then it is not in the set.
There is one linear inequality for each combinatorial line, stating that at least one point must be missing from the line.

16 February, 2009 at 9:52 am

Klas Markström

725. c_6
I’m aware that the value of c_6 follows from c_5 and that the extermisers can be constructed from the c_5 extermisers. However when doing computer work for these kinds of things I try to follow the cautious strategy that if one can get the same answer in two different ways then it is best to try them both. This gives a good insurance against mistakes and other errors.

It would be good if someone else would be willing to combine the c_5 extermisers into c_6 extermisers. That way we would have an independent construction by that method as well as the pure integer programming run I am doing for the problem now.

16 February, 2009 at 10:40 am

Terence Tao

726.

I’ve put the recent progress on c_n and Moser’s problem on the wiki. Please feel free to edit.

I think as soon as we have a second confirmation of the 150 result (either by hand or by computer) we can send the sequence (up to 450) to the OEIS. I doubt we will pin down $1302 \leq c_7 \leq 1350$ exactly any time soon, though we may be able to narrow the bounds by a bit.

16 February, 2009 at 12:58 pm

Sune Kristian Jakobsen

727.

Have anyone tried to generalize the construction in 220? (Michael’s answer to Terry.219)
Do there exist similar examples when a, b and c are not equal? or when r>1?

16 February, 2009 at 2:06 pm

Jason Dyer

728. Fujimura’s problem

Thinking about the multi-dimensional tic-tac-toe led to attempting this problem as an n-queens variant.

Imagine each removed point as a “queen” that attacks in all six possible directions (and is able to pass over other queens).

For there to be no equilateral triangles, it is necessary but not sufficient for each point without a queen to be attacked by at least n queens. This corresponds with the removal of all n triangles from that point.

To be a sufficient condition, each available distance and direction must contain at least one queen. (The three directions are (a+k,b,c) (a,b+k,c) (a,b,c+k) with k>0.)

There is also a limit to how many queens any individual queen may be attacked by, but I haven’t gone through the calculations yet.

16 February, 2009 at 6:37 pm

Dima

729.Geometric hyperplanes.

(studied mostly in a different context, for geometries related to finite simple groups, buildings, etc)

As the name suggests, a geometric hyperplane is a subset such that every line (combinatorial line, that is, in our case) either lies in it, or intersects it in a point (i.e. an $n-$ word over {1,2,3}, in our case). So the complement of a geometric hyperplane does not contain a combinatorial line. The opposite need not be true, as a combinatorial line can intersect the complement of a line-free set in 2 points (the latter looks like a “waste of lines”, though, and one would hope (too optimistically, perhaps) that in the extremal examples of line-free sets this does not happen)

A geometric hyperplane of any “partial linear space with line size 3″ (we have our combinatorial lines as an example) is obtained from a so-called universal embedding into $\mathbb{F}_2 P^{N-1},$ where $N$ is the number of points, $\mathbb{F}_2$ are integers mod 2, and in our case $N=3^n,$ provided certain natural condition is satisfied. This is a result due to M.Ronan (“Embeddings and hyperplanes of discrete geometries”, Europ. J. Combin. 8 (1987), 179–185.)
As far as I can recall (I can’t easily lay my hands on this text here), for our examples this condition trivially holds.

The universal embedding is the following natural contruction: take the vectorspace $\mathbb{F}_2^N$ modulo the relations $x_i+x_j+x_k=0,$ for each line $\{i,j,k\}.$ This maps each point the geometry to a nonzero vector of $\mathbb{F}_2^M,$ and each line to a 2-space of $\mathbb{F}_2^M$ (here $M$ is the dimension of the quotient space).
The geometric hyperplanes then are just hyperplanes of the space $\mathbb{F}_2^M.$

One way or another, this is a nice and sometimes useful construction, although I am not too optimistic for it being useful here. Perhaps it would lead to better understanding of construtions of particular line-free sets.

16 February, 2009 at 6:40 pm

Michael Peake

730. List of $c_5$ solutions

The twelve solutions are in three types.

In the notation of Kristal.247 and Terry.248, all twelve can be formed by removing points from

yzx zxy xyz
xyz yzx zxy
zxy xyz yzx

or a cyclic permutation of that.

The number of points remaining in each cube is either

3 solutions from permutations of this
17 17 18
18 14 17
14 18 17

6 solutions from permutations of this
17 17 15
18 14 17
17 18 17

3 solutions from permutations of this
17 17 12
18 17 17
17 18 17

In each solution, one number on the rising diagonal is a multiple of 3;
that cube was xyz before the removal of points.

All twelve solutions are formed from complete $\Gamma_{a,b,c}$ slices.

If my program is right, there is only one $c_6$ solution, the one we know, and it is built from the last three solutions above.

16 February, 2009 at 6:57 pm

Terence Tao

731. $c_5 \leq 152$

I was able to show by hand that $c_5 \leq 152$ , basically by using a precise description of the 52 and 51-point line-free sets in $[3]^4$ , followed by a rather tedious case analysis. See

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

The key point seems to be that extremal sets have a very strong tendency to be trapped in one of the sets

$D_{n,j} := \{ (x_1,\ldots,x_n): x_1+\ldots+x_n = j \hbox{ mod } 3 \}$

for j=0,1,2, and any attempt to deviate from these sets by adding a point or two outside of the set tends to be “punished” by the forcible removal of many points from inside that set.

Much of the analysis seems like it can be pushed to 150. For instance, I know that if two parallel slices of the set have 51 points or more, then the set as a whole can have at most 150 points. One still has to rule out 52-50-49 and 51-50-50 slice patterns, though, if one is to get all the way to 150.

Michael: If there is only one $c_6$ solution, then we have $c_7 \leq 3c_6 - 2 = 1348$ , by the same argument that gave us $c_4 \leq 3 c_3 - 2 = 52$ .

16 February, 2009 at 7:03 pm

Dima

732. Symmetries.

Klas, Terence,
when you talk about cutting down the search space, it can be cut down by the full automorphism group of the set of combinatorial lines, that is by the direct product of $\mathbb{Z}_3$ and $S_n,$ the symmetric group on $n$ letters. (It is easy to see that adding 1 to each coordinate, thinking of coordinates being in $\mathbb{Z}_3,$ maps a combinatorial line to a combinatorial line, and gives $\mathbb{Z}_3,$ whereas permuting the coordinates gives $S_n.$ That there are no more symmetries, can be seen by observing that there are different numbers of combinatorial lines on points with different numbers of symbols equal to each other.)

16 February, 2009 at 9:54 pm

Michael Peake

733. Moser, k=5, equals DHJ, k=3

joszef.723 noted that we get the same density for the Moser cube with k=5 as we got for DHJ with k=3. That is because the restriction of the k=5 Moser’s cube to ${}[0,1,2]^N$ is the same problem as DHJ. It also explains why Moser’s k=3 cube gets the same density as Spurner’s lemma.

16 February, 2009 at 10:43 pm

Michael Peake

734. Moser, k=5 doesn’t equal DHJ, k=3

No, I don’t think my previous comment is correct, although the densities do match.

17 February, 2009 at 8:18 am

jozsef

735. Re:734. Moser, k=5 doesn’t equal DHJ, k=3

Michael, the k=6 case is the first one where I see some simple correlation between the Moser and DHJ problems. By the map P: P(0)=P(5)=0, P(1)=P(4)=1, P(2)=P(3)=2 a line-free grid maps to a combinatorial-line-free cube. So, Moser k=6 is at least $2^n$ times DHJ k=3. For k=5 we would need an asymmetric map, I’m not sure if one can get a relation between the two problems similar to the k=6 case.

17 February, 2009 at 3:31 pm

KS Chua

736. $c'_5 \ge 124$

Using the optimization method described in 229. I found a geometric line free set of size 124. ( $k=3,n=5$ ). The program is implemented in MATLAB using the builtin minimization routine (which does not use the fact that the objective function is a cubic polynomial). Because there is no apparent structure to the set found, I list the 124 integers below (whose ternary expansions give the set) so that it may be checked independently.

1 , 4 , 5 , 9 , 10 , 12 , 14 , 16 , 17 , 21 , 22 , 25 , 28 , 29 , 30 , 32 , 33 , 34 , 36 , 38 , 42 , 44 , 45 , 46 , 48 , 50 , 52 , 53 , 57 , 58 , 61 , 62 , 64 , 65 , 66 , 68 , 69 , 70 , 73 , 76 , 77 , 80 , 81 , 82, 84 , 86 , 88 , 89 , 90 , 92 , 96 , 98 , 100 , 101 , 102 , 104 , 105 , 106 , 108 , 110 , 114 , 116 , 126 , 128 , 132 , 134, 136 , 137 , 138 , 140 , 141 , 142 , 144 , 146 ,150 , 152 , 153 , 154 , 156 , 158 , 160 , 161 , 164 , 165 , 166 , 169 , 172 , 173,
174 , 176 , 177 , 178 , 181 , 184 , 185 , 186 , 189 , 190 , 192 , 194 , 196 , 197, 198 , 200, 204 , 206 , 208 , 209 , 210 , 212,
213 , 214 , 217 , 220 , 221 , 225 , 226 , 228 , 230 , 232 , 233 , 237, 238 , 241.

17 February, 2009 at 6:18 pm

Michael Peake

737. c5′

Chua.736′s solution contains all points with two 1s, or one 1 and an even number of 0s.
It also contains four points with no 1s and two or three 0s. Any two of these four points differ in three places, except for one pair of points that differ in one place.
For these reasons, I agree that this is a solution to Moser’s problem.

17 February, 2009 at 8:45 pm

Michael Pea

738. Moser’s cube, k=3

This suggests further solutions for $c'_N$

q 1s, all points from $A(N-q,1)$
q-1 1s, points from $A(N-q+1,2)$
q-2 1s, points from $A(N-q+2,3)$
etc.

where $A(m,d)$ is a subset of $[0,2]^m$ for which any two points differ from each other in at least d places.

Mathworld’s entry on error-correcting codes suggests it might be NP-complete to find the size of A(m,d) in general.

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

18 February, 2009 at 1:29 am

Klas Markström

739. c_6
My integer programing run has now finished and as expected it found the optimum to be c_6=450 and found a unique one solution.

This case required a lot more CPU-time than c_5. I had to split the problem into many subcases and ran them in parallell ona linux cluster. My guess would that it used around 1000 CPU-hours.

18 February, 2009 at 10:15 pm

Michael Peake

740.

That’s a huge effort, and I’m guessing we won’t be able to find $c_7$ by this method.

In 738, I can at least estimate the size of A(m,d) by sphere packing.

In A(m,3), each selected point and its m immediate neighbours form disjoint sets, so $|A(m,3)| <= \frac{2^m}{m+1}$
Also $|A(m,4)| <= \frac{2^m}{m+1}$

In A(m,5) and A(m,6), each selected point and two layers of neighbours form disjoint sets, so $|A(m,5)|(1+m+\binom{m}{2}) \leq 2^m$ .

Using these inequalities, it seems that only a tiny fraction of points from lower layers are included in the method described in 738. So this method still only has $O(3^N/\sqrt{N})$ points.

19 February, 2009 at 9:31 am

Terence Tao

741. Moser

It occurs to me that if we have a good enough understanding of the $c'_4=43$ result, and in particular we can classify 43-point Moser sets, then we may be able to improve the upper bound on $c'_5$ from 129 to $127 = 43 + 42 + 42$ as was done for the $c_4$ and $c_7$ upper bounds, bringing us closer to the lower bound of 124. If we also can classify the 42-point Moser sets then in principle we can hit $124 = 42 + 41 + 41$ exactly.

(Similarly, if we get a good classification of 50-point line-free subsets of $[3]^4$ , then we should be able to finish off a non-computer-assisted proof that c_5 = 150.)

19 February, 2009 at 2:00 pm

Klas Markström

742. Moser.
I ran my program for the Moser problem. For n=4 I get 43 as the optimum and the program found 1552 extremisers. However a quick heuristic test suggest that most might be isomorphic.
The solutions can be found here
http://abel.math.umu.se/~klasm/extremal-moser-n=5-t=3
The file format is the same as before.

19 February, 2009 at 6:50 pm

Michael Peake

743. Moser

At a first glance, there are four types of solution

512 solutions: 24 points contain two 2s, 16 contain one 2, 3 contain no 2s
768 solutions: 23 points contain two 2s, 16 contain one 2, 4 contain no 2s
256 solutions: 24 points contain two 2s, 15 contain one 2, 4 contain no 2s
16 solutions: 18 points contain two 2s, 20 contain one 2, 5 contain no 2s

19 February, 2009 at 8:08 pm

Kristal Cantwell

744. If the following:

are the only possible values for c_4′ = 43. Then I think that c_5′
must be 128 or less. There are only 24 points possible with two 2′s
so if there are three in a row the first one must have at least 18 of these
points the second cube must also have at least 18 so there must be at least
12 in both final the third must have at least 18 so there must be
at least 6 in all three which results in a line. So the maximum value for
c_5′ is 128 or less.

19 February, 2009 at 10:22 pm

Terence Tao

745. $c_4$

I’ve managed to classify all 52-point, 51-point, and 50-point line-free subsets of $[3]^4$ ; the details are somewhat tedious but they are on the wiki, see Lemma 2 of

http://michaelnielsen.org/polymath1/index.php?title=Upper_and_lower_bounds#n.3D4

At the 50-point level we see for the first time a set which is not contained in one of the $D_{4,j}$ sets, which I have called X.

In principle, it should now be possible to establish the upper bound $c_5 \leq 150$ , using Lemmas 2, 3, 4 on the wiki, though I will not have the time to verify this in the near future.

20 February, 2009 at 4:41 am

Christian Elsholtz

746, Mosers problem in dimension 4 and 5.

From Klas’ list in 742 it appears to me (just by a visual inspection, not by computer count) that possibly the distributions of the 43 vectors in the 3 planes are like
(13, 16,14) and (14,15,14) (only?)
This would mean that the middle layer is quite full,
so, when constructing a 5 dimensional array out of the 4 dimensional configurations,
like
(a b c)
(d e f)
(g h i), where $a+b+c \leq 43$ , etc, and also
$b +e+h \leq 43$
one should indeed be able to get a better upper bound.
Perhaps one of you can count the number of ones, twos and threes in the first column, for each solution and report the distributions?

Given that for dimension 3 the extremal example is of type (6,4,6), i.e. middle layer is not dense, in dimension 4 we have (possibly) the opposite, so that for dimension 5 one could expect again the middle layer is less dense,
The example by KS Chua in 736 has a distribution of
{{42, 40, 42}, {42, 40, 42}, {42, 40, 42}, {41, 40, 43}, {41, 40, 43}}
in the 5 parallel layers, so is in the spirit of this philosophy.

20 February, 2009 at 5:22 am

Klas Markström

747. Moser n=4

Over night I ran the program to find all solutions for Moser’s problem for n=4 and 42 points.
The solutions can be found here
http://abel.math.umu.se/~klasm/moser-n=4-t=3-p=42.gz
There are of course a large number of solutions, 86232, but again it seems that the number of non-isomorphic solutions might be quite small.

A question for those analysing the solutions. Are all the 42 point solutions subsets of the 43 point extremisers or are there other maximal solutions as well?

20 February, 2009 at 8:29 am

Christian Elsholtz

748 Moser
The observation made by Michael, in 738 and 740 has also been made
by V Chvatal, Canadian Math Bulletin, Vol 15, 1972, 19-21. “Remarks on a problem of Moser”.
That paper, however, is more difficult to read, and rewriting that observation in modern notation, as done by Michael, was certainly useful.

That paper also comments that the construction only gives $O( \frac{3^n}{\sqrt{n}})$ , the reason being indeed that $A(n,d)\leq 2^{n-d+1}$

It can also be observed that the method gives for dimension 4 only 42 points, so that one should not expect that construction to be optimal, since $c_4'=43$ .

20 February, 2009 at 8:35 am

KS Chua

749. $c_n^{\mu}$ by optimization and LYM

The optimization approach can be applied to the weighted version
$c_n^{\mu}$ . The argument in 229 (minus the confusing
indexing) is :

Let $G$ be a uniform k graph with vertex set $V=\{v_1,...,v_m\}$ and edge set $E_k$ together with a weight
function $0 \le w_i \le 1$ for each vertex $v_i$ and set

$f(x)= \sum_{i=1}^m x_i w_i-\sum_{(i_1,...,i_k) \in E_k} x_{i_1}...x_{i_k} .$

Then the maximal total weight $\alpha$ of an independent set
of vertices (no k of which is an edge) in $G$ is given by

$\alpha=MAX_{x \in \{0,1\}^n}f(x)=MAX_{x \in [0,1]^n}f(x).$

Applied to subset relation , with variables $x_I, I \subset [n]$ weighted by $1/\begin{pmatrix} n \cr |I| \end{pmatrix}$ and the known $c_n^{\mu}=1$ for $k=2$ , it gives the
following interpolation of the LYM equality. For all $x \in [0,1]^{2^n}$ ,

$\sum_{I \subset [n]} \frac{x_I}{\begin{pmatrix} n \cr |I| \end{pmatrix}}-\sum_{I \subset J \;\; or \;\; J \subset I} x_I x_J \le 1.$

Choosing a 0-1 $x$ corresponding to an antchain gives the usual LYM.

20 February, 2009 at 12:13 pm

Kristal Cantwell

750. If there are 1552 43-point solutions and 86232 42-point solutions
then there must be one 42-point solution which is not a subset of any of the 43-point solutions, since each 43-point solution has 43 42-point subsets and 43*1552 is less than 86232.

20 February, 2009 at 8:54 pm

Michael Peake

751. $c_5 \leq 151$ by hand

I used Terry’s classification, in comment 745, of 50pt, 51pt and 52pt subsets of ${}[3]^4$ to show $c_5 \leq 151$ . My proof
is in the wiki.

In 743, one group of 16 solutions had five points with no 2s.
One of these solutions is the union of the following, and the other fifteen are reflections of it in one or more of the axes.

$\Gamma_{0,0,4} + \Gamma_{0,1,3} + \Gamma_{0,2,2} + \Gamma_{1,2,1} + \Gamma_{2,1,1} + \Gamma_{3,0,1} + \Gamma_{3,1,0}$

21 February, 2009 at 5:30 am

Seva

752. An algebraic DHJ(3)

Not quite following the mainstream of this thread, and perhaps already discussed elsewhere — but anyway. There seems to be a nice version of the DHJ(3), which may be easier to attack and which looks (almost) equally exciting to me.

Let’s say that a vector in $F_3^r$ is simple if either $1$ , or $2$ does not appear among its coordinates; say, $(1,0,0,1,0)$ and $(2,2,2,0,2)$ are simple vectors, while $(1,2,1,1,1)$ is not. Furthermore, call a three-term progression in $F_3^r$ simple if its difference is simple. Thus, a simple progression is a triple $a,b,c$ of distinct elements of $F_3^r$ with $a+b+c=0$ and $a-b,b-c,c-a$ all simple. The DHJ(3) implies that any positive density subset of $F_3^r$ contains a simple progression. Is there any combinatorial or Fourier-theoretic proof of this fact?

Notice that by the integer Roth theorem, any set $A\subseteq[N]$ of positive density contains a three-term progression with the difference, say, at most $N^{0.1}$ ; however, the corresponding argument does not seem to extend onto simple progressions in $F_3^r$ .

21 February, 2009 at 5:34 am

Michael Peake

752. $c_5 \leq 150$ by hand

I think I have finished the long-winded proof that $c_5 \leq 150$ , in the wiki.

21 February, 2009 at 8:51 am

Terence Tao

753.

Michael: Excellent! Now we have two independent confirmations that $c_5=150$ and thus $c_6=450$ , and also quite a good understanding of the extremisers and near-extremisers (though probably not enough to completely close the gaps in the bounds $1302 \leq c_7 \leq 1348$ ). Incidentally, I placed this sequence on the OEIS at

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

and c”_n at

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

Seva: Thanks for the question, which I have added to the wiki. The same question was also posed, incidentally, by Randall in 480. I think the problem is similar to that of finding arithmetic progressions of length three in dense sets of [N] whose difference is a square. Ben observed once that such a result could be deduced from known results in “quadratic Fourier analysis” (in particular, the U^3 inverse theorem) and so there is a chance that something similar can be done here.

Re: Moser: it may be helpful to try to find a non-computer-assisted proof of the upper bound $c'_4 \leq 43$ , as this may help us understand the structure of the extremisers and near-extremisers better (given that this strategy seems to have been quite successful for $c_n$ ). Actually, do we even have a human proof of $c'_3 \leq 16$ ?

21 February, 2009 at 10:21 am

Christian Elsholtz

754 Human proofs of Moser’s problem in dimension 3 and 4
(with regard to terry’s question in 753)

1) L. Moser, Problem P.170 in Canad. Math. Bull. 13 (1970), 268.
Origin of problem.

2) Komlos, solution to problem P.170 by Leo Moser,
Canad. Math.. Bull. vol (??check) (1972), 312-313, 1970.

gives a solution like fixing n/3 coefficients, i.e. a lower bound of $\frac{3^n}{\sqrt{n}}$ .

3) V. Chvatal, Remarks on a problem of Moser, Canad. Math. Bull. 15 (1972),
19-21.

improves the constant in Komlos construction, essentially taking a union of slices,
gives a lower bound of $c'_4\geq 42$ and implicitly $c’_5\geq 124$ etc,
by. relating the problem to a coding theory problem.
but is aware of the solution with 43 points in dimension 4.

4) V. Chvatal,
Edmonds polytopes and a hierarchy of combinatorial problems
Discrete Math. 4 (1973) 305-337.
Reprinted: Discrete Mathematics, 306, 2006, 886-904.

gives a human proof of $c'_3=16$ , it’s actually a linear programming method, with some geometrically motivated clever scalings. perhaps this can be generalized.

5) A.K. Chandra, On the solution of Moser’s problem in four dimensions,
Canad. Math. Bull. 16 (1973), 507-511.

gives a human proof of $c'_4=43$ with some useful info on number of points in certain sub-configurations.

21 February, 2009 at 10:33 am

jozsef

754. Exact bounds

It is great that you find the exact values of $c_5$ and $c_6$ !
I was wondering if you could check if the extremal configurations are “corner-free” or not. By corner-free I meant that if for every point you assign a 3-dimensional point (a,b,c) where a is the number of 0-s, b is the number of 1-s, and c is the number of c-s then there is no triple of the form (x+d,y,z), (x,y+d,z),(x,y,z+d). It would be also interesting to know if there is at least one such extremal configuration exists for k=6. It is for checking if our present lower bound strategy is optimal or not. (Probably not)

21 February, 2009 at 12:05 pm

Kristal Cantwell

I tried these two links

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

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

and the I didn’t get a sequence for the second one which
I think is for $c''_n$ even though I tried it twice.

21 February, 2009 at 1:16 pm

Christian Elsholtz

757 Moser, n=5

Comment on the example that shows $c'_5 \geq 154$ :

If one shifts the digits from {1,2,3} to {-1,0,1}, then one observes that
the example has all 80 vectors with “sum of coordinate entry squares=3,
i.e. two zeros and three times $\pm 1$
all 40 vectors with sum of entry squares=4, i.e. one zeros and four $\pm 1$ entries, and four more vectors with all entries being $\pm 1$ .

In other words, this is a union of two Behrend spheres and a third partial sphere.

21 February, 2009 at 1:27 pm

Terence Tao

Dear Kristal, the sequence got moved to

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

because of a duplication.

22 February, 2009 at 11:49 am

Sune Kristian Jakobsen

758. Contains on $(|A|, |B|, |C|)$ .
Let $S := \Gamma_{a+r,b,c} \cup \Gamma_{a,b+r,c} \cup \Gamma_{a,b,c+r} \subset [3]^n$ , where $r>0$ , and let $A \cup B \cup C$ be a (combinatorial-)line-free subset of $S$ , such that $A \subset \Gamma_{a+r,b,c}, B \subset \Gamma_{a,b+r,c}, C \subset \Gamma_{a,b,c+r}$ . Now we want to find the contains on $(|A|, |B|, |C|)$ .

It is possible to show that $\frac{|A|}{\binom n{a+r,b,c}}+\frac{|B|}{\binom n{a,b+r,c}}+\frac{|C|}{\binom n{a,b,c+r}}\leq 2$ (216). That is: The equal-slice measure of $A \cup B \cup C$ is at most $2$ . I thought this inequality was sharp when none of A, B, and C are empty, but this was disproved in Michael.220 in the case $a=b=c=r=1$ . The following is a general counterexample except for the case where $a=b=c=0$ where it is trivially true. Assume WLOG that $c \neq 0$ , and let M be a proper non-empty subset of $\binom {[n]}{c}$ (such a set M exist since $n\geq 2$ , because $c,r>0$ ). Now let $C=\Gamma_{a,b,c+r}$ , let A be the set of elements $x\in\Gamma_{a+r,b,c}$ where the set of i’s such that $x_i=3$ is an element in M, and let B be the set of elements $x\in\Gamma_{a,b+r,c}$ where the set of i’s such that $x_i=3$ is _not_ an element in M. Now $A \cup B \cup C$ contains 2 elements of every line, and thus $\frac{|A|}{\binom n{a+r,b,c}}+\frac{|B|}{\binom n{a,b+r,c}}+\frac{|C|}{\binom n{a,b,c+r}}= 2$ .

Notice that the example in 220 is not a special case of the above example.

22 February, 2009 at 1:55 pm

Terence Tao

759. Moser(3)

I found the $c'_4 = 43$ paper online at

ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/72/286/CS-TR-72-286.pdf

I also reconstructed the $c'_3 \leq 16$ argument as follows. For every $0 \leq m \leq n$ , let $\alpha_m$ be the density of A inside the set of points with exactly m 2s. Thus for instance when n=3 we have $|A| = 8 \alpha_0 + 12 \alpha_1 + 6 \alpha_2 + \alpha_3$ . We also have the linear inequalities $2\alpha_i + \alpha_j \leq 2$ for $i < j$ , as can be seen by double-counting those geometric lines with j-i wildcards and i fixed 2s. There is also the refinement $2 \alpha_0 + \alpha_1 + \alpha_2/2 \leq 2$ , formed by checking this inequality by hand in the two-dimensional case, which then implies the general case by an averaging argument. In three dimensions, one can get $|A| \leq 16$ by a suitable linear combination of these inequalities.

The same argument only seems to give $c'_4 \leq 48$ in four dimensions. I haven’t yet digested the paper above to see how to do better.

22 February, 2009 at 2:47 pm

Terence Tao

760. Moser(3)

There is an additional inequality in 3 and higher dimensions, namely $\alpha_0 + \alpha_2 \leq 4/3$ . This can be proven by first verifying it inside the six-element set {333, 322, 311, 223, 113, 212} and then averaging over all the symmetries of the Moser cube. This seems to lower the upper bound for $c'_4$ to 46 2/3 (and hence to 46, by integrality).

22 February, 2009 at 7:54 pm

Terence Tao

761. Moser(3)

In 743 it was remarked that the $c'_4 = 43$ extremisers were distributed in the patterns (3,16,24,0,0), (4,15,24,0,0), (4,16,23,0,0), or (5,20,18,0,0), where (a,b,c,d,e) means that there are a numbers with 0 2s, b numbers with 1 2, etc. (For comparison, the entire cube $[3]^4$ has distribution (16,32,24,8,1)). It is not so surprising that the d and e slots are empty (putting a point in there tends to be very expensive with regard to the higher slices), but it is interesting that there is such a huge bulge in the c position; as noted in 744, this already shows that one cannot have three parallel slices of 43-point sets, leading to the bound $c'_5 \leq 3 c'_4 - 1 = 128$ .

It should be straightforward to compute the distributions of the 42-point sets provided in 747. If the bulge persists,then there should not be any parallel slices of three 42-point sets either, which would let us shave the upper bound from 128 to 127 and put significant constraints on any 126-point set.

Eventually, one may want to work in (a,b,c,d,e) space. Let $\Omega$ be the convex hull of all (a,b,c,d,e) that are attainable from Moser sets in $[3]^4$ , then the cardinality of a Moser set A in $[3]^5$ is equal to $3(a'+b'+c'+d'+e')$ , where $(a',b',c',d',e')$ is the average of three points $(a_1,\ldots,e_1), (a_2,\ldots,e_2), (a_3,\ldots,e_3)$ in $\Omega$ (corresponding to the 3 slices of $A$ ) and thus also lies in $\Omega$ . On the other hand, by considering vertical lines (which can each intersect at most two of the three slices of A) we see that $(a',b',c',d',e') \leq \frac{2}{3} (16,32,24,8,1)$ , in the sense that each component on the left is less than the corresponding component on the right. Linear programming should then give us some bound on $3(a'+b'+c'+d'+e')$ , but first we need to understand the shape of $\Omega$ . As a first approximation we might make the simplifying assumption that d=e=0 (so that $\Omega$ is some three-dimensional polyhedron), given that this is what happens in the 43-point extremisers.

23 February, 2009 at 1:52 am

Christian Elsholtz

762 Moser, in dimension 2,3,4,5
We can assume that e=0 (in Terry’s notation in 761) for a very simple reason:
Suppose that e=1, meaning the central points is used, then there can be at most
$\frac{3^n-1}{2}+1$ points in the set, since for each non-central point there is a forbidden point by symmetry.
In dimension 2,3,4,5 the lower bounds are larger than the bound above, so that the central point is not used.

23 February, 2009 at 1:58 am

Klas Markström

763. Moser(3)
The statistics for the number of 2s in the point of the 42 point sets can be found here
http://abel.math.umu.se/~klasm/Moser-42-stat.pdf

As you can see there is a small group of solutions with only 12 2s, but the rest have at least 17. There is also a group of solutions with 2 in the d slot.

The solutions with 12 2s can be found here
http://abel.math.umu.se/~klasm/moser-n=4-42-12
and the solutions with non-zero d slot here
http://abel.math.umu.se/~klasm/moser-n=4-42-e=2

["e" corrected to "d" - T.]

23 February, 2009 at 9:28 am

Terence Tao

764: Moser(3)

Klas: thanks, this is very interesting! It means in particular that the only 43+43+42 = 128 point solutions in $[3]^5$ can come when the 42-point slice is one of the eight c=12 solutions, and one of the 42-point slices is one of the six c=18 point solutions. This looks like enough reduction in the entropy to eliminate this case by computer search, and maybe even by hand if one is clever enough. (It also suggests that we should understand the structure of these anomalously low-c solutions better. Given how few they are, it is likely that there is just one solution up to isomorphism in both cases). That should lower the upper bound for $124 \leq c'_5 \leq 128$ to 127.

Presumably the number of 41-point solutions is too enormous to list explicitly… but perhaps the number of low-c solutions is small, and could be worth searching for by an integer program. Note for instance in a 42+42+41=125 type solution, if the 42-point solutions are not from the c=12 class, then they each have c >= 17, and so the 41 point solution has c <= 14. So perhaps it is worth trying to enumerate the 41-point solutions with c <=14? From the 42-point and 43-point data one may hope that there are relatively few of these. [It would be good, though, to have some explanation of why c tends to be high. Note that there is a 40-point solution with (a,b,c,d,e) = (8,32,0,0,0), so this phenomenon may well be very transient.]

Christian: It is true that if one has e=1 in a Moser set in $[3]^4$ then the number of points is at most $\frac{3^4-1}{2}+1 = 41$ , which is less than $c_4 = 43$ . But this does not yet rule out the possibility that one of the 3-slices of, say, a 125-point Moser set in $[3]^5$ could have e=1, since the distribution could be (say) 42+42+41 or 43+43+39. (The argument does tell us, though, that the middle slice has e=0). But presumably we can improve on the upper bound, which leads to a subquestion: what’s the largest size of a Moser set in $[3]^4$ that contains the centre 2222? If we can improve the easy upper bound 41 to 38 then we can rule out this case completely, or failing that if we get a reasonable description of the 39+ point sets with the centre then we should be able to eliminate it by hand. [Also, if we know that every slice of a Moser set has e=0, this implies after rotation of the cube that the middle slice of the Moser set has d=0. Similarly, if we learn that every slice of a Moser set has to have small d, then this should imply that at least one middle slice has small c, which by the previous discussion should be helpful in limiting the number of possibilities.]

23 February, 2009 at 9:42 am

Terence Tao

765. Moser(3)

In fact, I can now rule out 128-point sets as follows. If one had a 128-point set, then the set must slice as 43+43+42 (or a permutation thereof) in every direction. But all 43-point slices have d=0 and all 42-point slices have d <= 2. Thus, there are at most two points amongst the sixteen points x222y, x22y2, x2y22, xy222 with x,y = 1,3 that lie in the set. Averaging this over all orientations we see that at most one eighth of all points with exactly 3 2s lie in the set. Thus, by the pigeonhole principle and a double counting argument, there exists a middle slice of the set with this property, i.e. a slice with c <= 24/8 = 3, but we know from the 43-point and 42-point distribution data that this is impossible.

To push this argument further, it would be helpful to classify the large-d 41-point solutions (as well as the large-e and low-c); presumably there are not very many of these.

23 February, 2009 at 5:48 pm

KS Chua

766 Moser(3)

From 762, there are at most 2^13=8192 subsets of size 14 in [3]^3 containing (222) which may be line free. This can be checked and they all contain at least 2 lines. So all such set has size <=13. Doing the n=4 case this way requires checking 2^41.

23 February, 2009 at 6:03 pm

Terence Tao

767 Moser(3)

Dear KS: Thanks! Actually, knowing that 3-dimensional Moser sets with 222 have at most 13 points automatically implies that 4-dimensional Moser sets with 2222 have at most 40 points, because if they had 41 points, then every pair of antipodal points in the cube have exactly one representative in the set, which implies that every middle slice of the set has 14 points, which you have just ruled out.

In fact, if a 4D Moser set contains 2222, we now know that every middle slice must be missing at least one antipodal pair of points. There are four middle slices, and every antipodal pair belongs to at most three of them, so we must miss at least two antipodal pairs and so Moser sets with 2222 can have at most 39 points. This is right on the edge of what we need to rule them out for 125 = 43 + 43 + 39-point 5D Moser sets; perhaps a slightly more sophisticated analysis can eliminate them completely. If so, this would imply that a 125-point 5D Moser set cannot contain any point with 4 or 5 2s. In any event, we have already established this for 126-point sets.

25 February, 2009 at 9:47 am

Terence Tao

768 Moser(3)

I can almost eliminate points with four 2s completely from the 5D Moser problem.

By 767, we know that any 4D Moser set with 2222 has at most 39 points. Hence, the only way a 5D Moser can have a point (say 12222) with four 2s is if the 1****, 2****, 3**** slices have 39+43+43=125 points between them. But by 743, the 43-point slices have c = 24, 23, or 18. Meanwhile, the 39-point slice must have c at least 10, because it is allowed to miss at most two of the 12 antipodal pairs in c (and all antipodal pairs have at most one point in the set). Looking at vertical lines, we see that the total of the three c’s from the three slices is at most 2*24. This is only possible if the two 43-point slices have c=18.

So we are now in a position where the 2**** and 3**** slices are one of the 16 solutions with (a,b,c,d,e) = (5,20,18,0,0). This looks like a lot of information available, but to proceed further we would need to understand the structure of these 16 exceptional solutions (presumably they are all isomorphic to each other).

25 February, 2009 at 9:50 am

Jason Dyer

768. Counting problems

There are $4^n-3^n$ sets of 3 distinct points x, y, z in $[3]^n$ such that they form a combinatorial line.

Therefore there are $3^n(3^n-1)(3^n-2)-4^n+3^n$ sets that do not form a combinatorial line. Take those sets, and consider the pairs x and y, y and z, and x and z.

Counting Problem A: How many of those sets have all three pairs form partial combinatorial lines? (I’m using “partial combinatorial line” to mean given a pair there’s a third point in $[3]^n$ that will make it a combinatorial line.)

Counting Problem B: How many of those sets have exactly two pairs form partial combinatorial lines?

Counting Problem C: How many of those sets have exactly one pair form a partial combinatorial line?

Counting Problem D: How many of those sets have no pairs form a partial combinatorial line?

I have made progress on B by making a “fake wildcard” (using the symbol #). For example, take a sequence like *#212. Given x = both wildcards set at 1 (11212) then y = 21312 or 31312 and z = 12312 or 13312. Repeat this for all possible wildcard settings, remove all duplicates, and all sequences ..212 are accounted for.

Then it just is a matter of counting how many possible settings it is with both * and # wildcards and removing duplicates from there (*#212 will yield the same results as #*212), and problem B is solved. But that’s a messy calculation so I wanted to share here my current progress before I went any farther. (Also someone might point out where we have the solution to this already 600 posts back.)

25 February, 2009 at 2:35 pm

Kristal Cantwell

769. The 18 points with 2 2′s in the 2**** slot will produce 18 points
with 3 2′s in the total configuration moreover they will all have
2′s in one coordinate x(the one in which the point with 4 2′s has
a coordinate not equal to 2. These 18 points will have 36
coordinates not equal to 2 among the four coordinates not equal
to x but that means there must be at least 9 coordinates
not equal to 2 at one of these coordinates. A majority of these coordinates
must be equal to a value not equal to 2 without loss of generality say 1
then at most six of these points can be equal to 1 since the ramaining
coordinate not equal to 2 can take one of two values at the remaining
3 coordinates giving a total of 6. thus we have one coordinate with
three 1′s and three 3′s among the 18 triples. Then we slice at this coordinate
the 3 triples of two in the one and three block makes these slices have
size 41 the point with four twos becomes a point with three twos in
the 2 slice thus forcing it to have value 42 or less so the sum is 124.
Thus if there is one point with four 2′s the value is 124 or less.

25 February, 2009 at 3:12 pm

Terence Tao

770. Moser(3)

Kristal: thanks! I wrote up your argument on the wiki page. In fact the argument shows that any 125-point Moser set cannot have 43 points in its 2**** slice, and in fact cannot have 42 points either unless it is one of the eight anomalous (a,b,c,d,e) = (6,24,12,0,0) solutions at that level.

If we can eliminate those anomalous solutions, it implies that 125-point Moser sets must always have their thin slice in the middle, i.e. they must slice as 43+39+43, 43+40+42, 42+40+43, or 42+41+42.

25 February, 2009 at 6:57 pm

Michael Peake

771. Moser(3)

One solution of the (6,24,12,0,0) set is made of the following slices.
the other solutions would be reflections in one or more axes

$\Gamma_{220}+\Gamma_{202}+\Gamma_{022}+\Gamma_{112}+\Gamma_{211}$

26 February, 2009 at 1:34 am

Michael Peake

772. Moser(3)

Terry, in your writeup of Kristal’s proof, you said that any solution with d>2 had at most 40 points. From reading this blog and the wiki, I can only tell that such a solution has at most 41 points. What have I missed?

26 February, 2009 at 7:45 am

Terence Tao

773. Oops, you’re right, which means that my strengthening of Kristal’s argument doesn’t quite work (at least for the problem of getting the bound 124 on the nose; it still works if one just wants to prove $c'_5 \leq 125$ ). I’ve readjusted the wiki appropriately.

26 February, 2009 at 2:30 pm

Terence Tao

774. Strategy for Moser(3)

I think we have a decent shot at pushing the upper bound for $c'_5$ (currently at 127) all the way down to the lower bound of 124. The idea is to exploit the numerically observed phenomenon that large four-dimensional slices (particularly those with 42 and 43 points) tend to have very large “c” values (points with two 2s) but very low “d” values (points with three 2s). In particular, middle slices such as 2**** (if large) tend to have large “c”, and side slices such as 1**** or 3**** tend to have small “d”.

But (as implicitly observed in Kristal’s argument) one middle slice’s “c” is another side slice’s “d”. For instance, if the 2xxxx slice contains an element with two additional 2s, e.g. 21223, then this contributes a “d” point to the side slices *1*** and ****3. More generally, double counting tells us that the total “c”‘s of all the five middle slices put together, is equal to 3/2 times the total “d”s of all the ten side slices put together. By the pigeonhole principle, there must therefore exist one coordinate such that the “c” of the middle slice of that coordinate is at most 3/2 the sum of the “d” of the two side slices of that coordinate. Without loss of generality we may assume this is the first coordinate; thus

c(2****) <= 3/2 [ d(1****) + d(3****) ] (1)

where I use c(2****) to denote the “c” count of the 2**** slice (i.e. the number of points in this slice with two additional 2s), etc.

The listing of 43 and 42-point slices tells us that for such slices, c is at least 12 and d is at most 2. Comparing this with (1) we already see that not all slices can have 42 or more points, which already recovers our existing upper bound of 127=43+43+41. But I think we can do better. Firstly, it seems that having a lot of “d”s really does push down the total size of a slice. In the extreme case, if d is equal to its maximal value of 8, then it is easy to see that c is at most 12, b is at most 8 (note for instance that at most one of 2111, 2133, 2313, 2331 can lie in the set if every point with 3 2s lie in the set), and a is at most 8, leading to only 36 points.

Conversely, if c is really small (and d=e=0, which we know to be true for the middle slice), this also pushes down the size of a slice. For instance, in the extreme case when c=0, the bound b+4a <= 64 (coming from double counting lines such as 1111, 1112, 1113) and the trivial bound b <= 32 gives at most 40 points in the slice.

I’m hopeful that if we get good enough upper bounds on the size of slices for various small values of c or large values of d, we should be able to solve the problem. (For comparison, in the 124-point examples given in 736, the middle slice is (8,32,0,0,0) (thus c=0) and the side slices are (1,16,24,0,0), (2,16,24,0,0) or (3,16,24,0,0) (thus d=0).)

27 February, 2009 at 7:59 am

Christian Elsholtz

775 Moser:
I have typed some notes (to use Latex) and have put them here:
http://www.ma.rhul.ac.uk/~elsholtz/WWW/blog/mosertablogv01.pdf

This contains two parts:
1) A human proof that a Moser set in dimension 3 with centre point 222 contains at most 13 points. Earlier proved by KS Chua 766 (by computer).

2) A sketch to prove that in dimension 4 a Moser set with centre 2222 contains at most 39 points. Proved earlier by Terry in 767.
Essentially I proved that the two missing pairs of antipodal points must be included
in sets of the form 22xy or xy22, which means I have localized them somewhat. possibly one can squeeze more of the argument.

Is there actually a set with 39 points? (those computer programmes that classified the
Moser sets with 43 points can possibly be adapted).

Perhaps the arguments prove useful for the discussions on dimension 5.

27 February, 2009 at 1:55 pm

Kristal Cantwell

We can show that any line free configuration
Has 126 or less points

If there is a 42 or 43 in the center
Then the value is 125
Case 1
There are 17 or more points with 3 2’s and two 1 or 3’s one coordinate has all
2’s the 34 or more non two coordinates are divided among
four coordinates one must contain 9 or more but at most six can have
the one value so there will be at least three points with value one and
three with value 3 at that coordinate we slice at that coordinate
and get the slices associated with one and three
having three or more points with three 2’s and hence
having 41 points or less thus the value is 41 + 41 +43
Case 2 there is one remaining anamolous case which from
Note 771 contains
all points with two coordinates equal to
2 and two points equal to one of the values 1 or three
then the set of points 1122 1212 1221 3322 3232 3223 which is in every configuration of this case has three points
with value 1 and three with value 2 which have two twos in the center slice
and hence three 2’s overall we can slice at this coordinate and get by similar reasoning
to the above the two noncenter cubes having 41 points or less and hence
the entire configuration having 125 points or less

Now we assume we have a line free configuration with 127 points
Center must be 41
Then other two edges must be 43
Next we note that if the center slice
contains no point with 2 or more 2′s it must have 40
points or less and we are done
we use the inequality
$2\alpha_i + \alpha_j \leq 2$
for i less than j
mentioned in 759 for the center cube for i = 0
and j =1. Then it implies that a center slice
with no points with 2 or more twos can have at most
40 points. Now using the above
any configuration with 127 or more points
must have a slice in the center with 41 points or less
and also its center slice must contain at least one point with
two twos in the coordinates of the slice and three overall
(or else we have 43 + 43 +40 points and that is less than 127
and we are done) that slice must have one coordinate not equal
to 2 or else the configuration will have less than 127 points
we can slice along that coordinate and get one of the non-center
slices having a point with three coordinates equal to 2 and thus
having value less than or equal 42 now by the above the center slice
is 41 or less and we have less than 127 points at most 41 + 42
+43 is 126 points

27 February, 2009 at 8:49 pm

Terence Tao

777. Moser(3)

Thanks, Kristal! Now we are down to $124 \leq c'_5 \leq 126$ . I’ve written up your proof on the wiki.

Christian: Thanks for the human proof of these facts; it is good to have independent confirmation of these things. I’ve also linked your notes to the wiki.

28 February, 2009 at 12:50 am

KS Chua

778 Moser(3)

Here is a Moser set containing (2222) of size 36.
0,2,3,5,7,9,11,15,17,19,21,23,24,26,27,29,33,35,36,38,40,
41,46,48,50,52,55,58,60,62,64,66,68,70,76,79

It seems the upper bound of 39 is too high.
One can classify 13-point Moser containg (222) and 12 points.
Call a point odd if the sum of coordinates in (123-form) is odd and even
otherwise. Then the omitted antipodal must be odd ie. the omitted point is
either the corner or center of a side slice or the complement of this in the
middle slice.

If there are only 2 omitted points in [3]^4 Moser with center. They must together account for the four 2 in the center slices. The above rule out
the case when both have two 2.

28 February, 2009 at 11:50 am

Klas Markström

779. Moser(3)
After waiting for some fre time on a Linux-cluster I have now constructed the 41 point solutions. There are quite a few of them, 2 765 200.
Here are the statistics for the number of 2:s
http://abel.math.umu.se/~klasm/Moser-41-stat.pdf
and here are the solutions.
http://abel.math.umu.se/~klasm/solutions-4-t=3-41-moser.gz
In order to make thing more compact each point is now given by its number in the lexicografic ordering and solutions are separated by a line with a single “Y”.

28 February, 2009 at 1:09 pm

Terence Tao

780 Moser (3).

Thanks Klas! Scanning through the statistics, I see two things which look quite encouraging:

1. d is always small; the largest value of d among any 41-point set is at most 3 (and in fact is at most 2, with just one family of 256 exceptions).

2. c is usually large. There are 16 anomalous solutions with c=6 (which are worth taking a closer look at), but everyone else has c at least 11.

Inserting this into my equation (1) from 774, we see that not all of the three slices here can have 41 or more points, unless the middle slice is one of the 16 anomalous c=6 solutions, and in the latter case the other two slices can’t have 43 points (because then they won’t contribute enough d’s to (1)). Unfortunately this is not enough to improve the 126 upper bound because of the 43+40+43 and 40+43+43 cases, but we understand the 43 point slices pretty well and so perhaps we can do something else to eliminate these cases also. For instance, if (1) holds and we are in the 43+40+43 case then d(1****)=d(3****)=0 and so c(2****)=0, which forces b(2****)=32 and a(2****)=8, which is looking pretty incompatible with the 43-point slices, though I cannot rule them out completely yet.

28 February, 2009 at 3:38 pm

Klas Markström

781. Moser(3)
I let a script run during the evening to pick out some of the more interesting solutions. The flies are in the original format.

Here are the solutions with c=6
http://abel.math.umu.se/~klasm/moser-n=3-t=3-41-c=6.gz

Here are the solutions with d=1
http://abel.math.umu.se/~klasm/moser-n=3-t=3-41-d=1.gz
the solutions with d=2
http://abel.math.umu.se/~klasm/moser-n=3-t=3-41-d=2.gz
the solutions with d=3
http://abel.math.umu.se/~klasm/moser-n=3-t=3-41-d=3.gz

1 March, 2009 at 10:09 am

Klas Markström

Did my posting of the low-c solutions just get stuck in the spam filter or did it disappear? [It got stuck in the spam filter - I think any comment which has too many hyperlinks in it gets flagged as spam. I've fished it out. -T.]

1 March, 2009 at 1:29 pm

Kristal Cantwell

782. Any line free configuration has 125 or less points.

The center slice is less than 42 because we have shown that a center slice of 42 or more means a total of 125 points or less.

The center slice is 40 or more since if it is 39 or less the total is at most 125.

Then the center is 40 or 41 and we have two cases with the center 40 or 41 and the sum 125
43 40 43
43 41 42
let us first look at the case in which the center is 41.

Now this must have a point p with 3 2’s in the center slice since 4a + b must be less than
64 and b must be 32 or less so if it is not then there are only 40 points in the center
slice. Then we can slice on one of the coordinates of p not equal to two
and get a non-center cube with 42 points with a point with with three twos or a point a non-center
cube with 41 points which together with the center cube in the new slice
which must have 41 points gives a total of 125 or less 41 43 or 41 41 43 but this 125 and we are done.
So we must have a side cube with 42 points and two points with three two’s
and I have checked all cases of these 42 point configurations
they are available at http://abel.math.umu.se/~klasm/moser-n=4-42-e=2
and in each case the two points with three twos have a coordinate at which one point has a one and the other a three
so we can slice at this coordinate and we get two noncenter cubes that must have at least one point with
three coordinates equal to 2 and hence the these two cubes
must have value 42 or less and since the center cube has value
41 we have a total of 125 and we are done with this case.

the only case left is one in which the center is 40 and the remaining cubes
are 43 now we divide this into two cases
first the center contains a point with two threes
then we can cut at a coordinate at which this point is not two
and force the case 43 41 42 which we have just done.

now it must a 43 40 43 division must occur in every slice
or we are back to the previous case
since 4a + b must be less than
64 and b must be 32 or less
we must have all 32 points with one two must be in the center slice
and all 32 points must be in all center slices so
we must have all points with exactly two coordinates equal to 2 in the configuration.

Now we note that in the division of the configuration into cubes with each cube corresponding to a fixed choice
of the first two coordinates we have the following all the points with first two coordinates equal to
one of 1 or 3( there are four of these) must have the center cube occupied hand hence by must have 13 or less see post 775
points the center cube can only have 8 points as the remaining points have 3 or more twos, the remaining cubes
can have at most 16 points this gives a total of 4*13 + 8 +4*16 = 124 and we are done.

1 March, 2009 at 4:11 pm

Terence Tao

783. Moser(3)

Kristal, I’ve written up most of your proof on the wiki, but I had trouble with the last paragraph. I agree that the only case left is when all slices are 43+40+43, and that the 126-point set contains every point with two 2s, and no point with three or more 2s. But I don’t think that this implies that the corner slices 11***, 13***, 31***, 33*** contain their center. Instead, they seem to contain all six points with two 2s, and perhaps half of the 12 points with one 2 and at most 2 of the 8 points with no 2s (because we can divide these 8 points into two quadruplets ***=111,133,313,331 and ***=333,311,131,113, each of which can have at most one point), leading to as many as 14 points which is not quite good enough.

We are beginning to brush up against the sphere packing problem that Michael observed back in 737, 738. Once we have all of the 80 points in $[3]^5$ with exactly two 2s, we have at most 40 of the 80 points with one 2, and we have to show that there are at most 4 points (or 5 points, if one is willing to settle for the 125 upper bound) remaining amongst the 32 points with no 2s. Note that any two points in this final component cannot differ in exactly two positions, but they may possibly differ in one position, so it isn’t quite a classical sphere packing problem here.

1 March, 2009 at 6:19 pm

Michael Peake

784. Moser(3)

If all 80 points with two 2s are included, then at most 4 points from ${}[1,3]^5$ can be chosen.
Two of these have an even number of 1s, and two have an odd number.

Suppose 11111 is one of the points. All points with two 3s are excluded, so the only points allowed with an odd number of 1s are those with four 3s. But all those points differ from each other in two positions, so at most
one of them is allowed.

1 March, 2009 at 7:45 pm

Terence Tao

785. Moser(3)

Thanks Michael! I’ve completed the proof of the 125 upper bound on the wiki. Only one more improvement left before we pin down $c'_5$ exactly…

3 March, 2009 at 8:10 am

Jason Dyer

786. $\overline{c}^\mu_6 < 18$

First note that there are eight extremal solutions to $\overline{c}^\mu_3$ :

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

Also consider the same triangular lattice with the point 020 removed, making a trapezoid. Solutions based on I-III are
Solution IV: remove 300, 111, 003
Solution V: remove 201, 111, 102
Solution VI: remove 210, 021, 102
Soltuion VI’: remove 120, 012, 201

Suppose we can remove all equilateral triangles on our 7x7x7 triangular lattice with only 10 removals.

The triangle 141-411-114 must have at least one point removed. Remove 141, and note because of symmetry any logic that follows also applies to 411 and 114. (1 removal total)

There are three disjoint triangles 060-150-051, 240-231-330, 042-132-033, so each must have a point removed.

(Now only six removals remaining.)

The remainder of the triangle includes the overlapping trapezoids 600-420-321-303 and 303-123-024-006.
If the solutions of these trapezoids come from V, VI, or VI’, then 6 points have been removed.
Suppose the trapezoid 600-420-321-303 uses the solution IV (by symmetry the same logic will work with the other trapezoid). Then there are 3 disjoint triangles 402-222-204, 213-123-114, and 105-015-006. Then 6 points have been removed.
Therefore the remaining six removals must all come from the bottom three rows of the lattice.

Note this means the “top triangle” 060-330-033 must have only four points removed so it must conform to solution either I or II, because of the removal of 141.

Suppose the solution of the trapezoid 600-420-321-303 is VI or VI’. Both solutions I and II on the “top triangle” leave 240 open, and hence the equilateral triangle 240-420-222 remains. So the trapezoid can’t be VI or VI’.

Suppose the solution of the trapezoid 600-420-321-303 is V. This leaves an equilateral triangle 420-321-330 which forces the “top triangle” to be solution I. This leaves the equilateral triangle 201-321-222. So the trapezoid can’t be V.

Therefore the solution of the trapezoid 600-420-321-303 is IV.

Since the disjoint triangles 402-222-204, 213-123-114, and 105-015-006 must all have points removed, that means the remaining points in the bottom three rows (420, 321, 510, 501, 312, 024) must be left open. 420 and 321 force 330 to be removed, so the “top triangle” is solution I. This leaves triangle 321-024-051 open, and we have reached a contradiction.

3 March, 2009 at 1:42 pm

Kristal Cantwell

787. Any Moser set with at least 42 points in the middle slice has at most 124 points.

There are two cases one the c value of the middle slice is 17 or more.
Then these points have 34 or more coordinate values not equal to 2 divided
among four coordinates one of these must have 9 of these coordinates
at most six of these can have value 1 or 3 thus at least 3 must be 3 and three must be one and also there must be more than 5 of either one or three. Now we slice at this coordinate then both slices have three points with three coordinates equal to 2. Then they must have at most 41 points.
Now since the most points with three coordinates equal to 2 in a slice
of 41 is 4 and we have one slice with 5 or more of these points that slice
must have at most 40 points. Now since one slice is of size 40 or less the other
41 or less and the remain slice trivially has 43 or less we have at most 124 points.

4 March, 2009 at 3:28 am

Klas Markström

788. HOC(3)
I have now found the extremal solutions for the weighted problem in the hyper-optimistic conjecture, again using integer programming.
The first few values are
c^{\mu}_2=4 with 3 solutions
c^{\mu}_3=6 with 9 solutions
c^{\mu}_4=9 with 1 solution
c^{\mu}_5=12 with 1 solution

The solution for n=5 is here
http://abel.math.umu.se/~klasm/solutions-n=5-k=3-HOC

The solution for n=4 is here
http://abel.math.umu.se/~klasm/solutions-n=4-k=3-HOC

I’ll see if I can do n=6 as well.

4 March, 2009 at 3:29 am

Klas Markström

789 HOC(3)

The solutions for n=3 are here
http://abel.math.umu.se/~klasm/solutions-n=3-k=3-HOC

The solutions for n=2 are here
http://abel.math.umu.se/~klasm/solutions-n=2-k=3-HOC

4 March, 2009 at 6:42 am

Jason Dyer

790. A super-optimist conjecture

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

4 March, 2009 at 8:24 am

Marc

791. $\bar{c}^\mu_{10} \ge 29$

028,046,055,064,073,118,172,181,190,208,217,235,262,
316,334,352,361,406,433,442,541,550,604,613,622,
721,730,901,1000

4 March, 2009 at 9:20 am

Jason Dyer

792. $\bar{c}^\mu_10$

Well, *that* was a short-lived conjecture. (re: Marc.791 in response to Dyer.790 — I just confirmed, and changed the spreadsheet) Was that done with random fiddling or was there a method?

Also I would like to remind people of the optimist conjecture in Jakobsen.813, which seems quite (well, moreso than other things) reasonable to prove.

4 March, 2009 at 9:35 am

Terence Tao

793. Various

A lot of progress! I will have to start a new thread soon, this one is being used up.

Kristal: it seems the second case (when c(2****) < 17) is missing from your 787. I’ve tentatively updated Lemma 2 on the wiki to reflect this improved bound, but we’ll need to check that second case.

Assuming this improvement, it means that 125-point Moser sets have at most 41 points in the middle slice, which forces them to have at least 41 points in the side slices. This is good news, because we’ve got a computer list of all of these points. In fact I have the following strategy to propose. We know that a 125-point Moser set does not contain 22222, and so all the points in the Moser set are contained in at least one side slice. More precisely, points with four 2s are contained in one side slice, points with three 2s are contained in two side slices, and so forth up to points with no 2s, which are contained in five side slices. Double-counting this fact, we see that

125 = sum_S a(S)/5 + b(S)/4 + c(S)/3 + d(S)/2 + e(S)

where S ranges over the 10 side slices. Dividing the side slices into five pairs (1****,3****), etc., and using the pigeonhole principle, we may thus assume without loss of generality that

a(1****) + 5 b(1****)/4 + 5 c(1****) / 3 + 5 d(1****) / 2 + 5 e(1*****)

and

a(3****) + 5 b(3****)/4 + 5 c(3****) / 3 + 5 d(3****) / 2 + 5 e(3*****)

sum to at least 125.

Now, we know (contingent on Kristal’s lemma) that the 1**** and 3**** slices have at least 41 points. On the spreadsheet

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

I’ve computed a+5b/4+5c/3+5d/2+5e for the 43 and 42-point solutions. Encouragingly, the largest this quantity is is 63, and almost all of these numbers are less than 62; only the (4,16,23,0,0), (3,16,24,0,0), (4,15,24,0,0), (2,16,24,0,0) configurations are 62 or higher. I haven’t entered in the 41-point data but I would assume the quantity is smaller than 62 in all those cases. If so, that pins down the 1**** and 3**** slices quite precisely, and I would hope that this gets us close to finishing off the problem.

Klas: Great! I’ve updated the hyper-optimistic conjecture page and the spreadsheet to reflect your new data. Thus far the HOC is holding up very nicely, we’ve verified it up to n=5. If we get n=6 for either c^\mu_n or \overline{c}^\mu_n then it might be time to send this sequence to the OEIS also. (The latter sequence is an integer sequence, and if HOC is true, the former is also.)

Marc: I’ve added your example to the wiki and spreadsheet too. Looks like Jason’s super-optimistic conjecture didn’t make it, unfortunately.

4 March, 2009 at 9:46 am

Klas Markström

794. HOC
From the comment in the wiki on using Behrend sets we have a super-linear lower bound for Fujimuras problem. So the nice pattern behind the super-optimistic conjecture is a small n effect.

The HOC for n=6 seems a lot harder than the previous cases but I’ll see what I can do.

4 March, 2009 at 9:49 am

Terence Tao

795. Moser(3)

I’ve updated the Moser spreadsheet,

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

to input the 41-point data, and as expected the “score” a+5b/4+5c/3+5d/2+5e never reached 62 (though the anomalous d=3 solution got close, at 61.5). Assuming Kristal’s lemma, this implies that there is a coordinate whose two side slices have one of the following statistics:

* (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]

and furthermore the total score must add up to at least 125. (For comparison, in the known 124 point example, the side slices have statistics (3,16,24,0,0), (2,16,24,0,0), or (1,16,24,0,0), with scores 63, 62, and 61 respectively.) This looks like quite a bit of information with which one can work with.

4 March, 2009 at 12:05 pm

Kristal Cantwell

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 c 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 middle 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 1:29 pm

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

[...] Hales-Jewett, Moser cube problem, polymath1 | by Terence Tao 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 [...]

4 March, 2009 at 1:33 pm

Terence Tao

796. Moser(3)

Thanks Kristal! Looks like we are in very good shape now. In particular we now have the situation described in 795; I’ll put that argument on the wiki now.

As this thread is now basically full, I am closing it and we will be moving to the 900 thread at

http://terrytao.wordpress.com/2009/03/04/dhj3-900-999-density-hales-jewett-type-numbers/

	Anonymous on Don’t base career decisions on…
	Terence Tao on A mathematical formalisation o…
	Mauricio Calvao on A mathematical formalisation o…
	Luqing Ye on 245A, Notes 2: The Lebesgue…
	Think ahead \| Planti… on Create lemmas
	Think ahead \| Planti… on Think ahead
	Dan Shved on 245B notes 4: The Stone and Lo…
	Anonymous on (Ingrid Daubechies) Planning f…
	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…

Bounds for the first few density Hales-Jewett numbers, and related quantities

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

103 comments

Leave a Reply Cancel reply

For commenters

Follow “What's new”

Bounds for the first few density Hales-Jewett numbers, and related quantities

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

103 comments

Leave a Reply Cancel reply

For commenters

Follow “What's new”