DHJ(3): 1100-1199 (Density Hales-Jewett type&nbsp;numbers)

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

1100. Moser & Elkin

Michael, thanks for the corrected inequalities at 993. I plugged them into the linear program, of course, but unfortunately the bounds did not budge, only the extremisers, which means that we chipped away a little bit but not as much as before. I can imagine that there is a law of diminishing returns in play here.

Kevin: thanks very much for the precise computation! I put it on the wiki at

but I suppose it could be cleaned up more. (Actually, the same holds for just about everything else on the wiki.)

14 March, 2009 at 9:15 am

http://michaelnielsen.org/polymath1/index.php?title=Hyper-optimistic_conjecture

1101. Hyper-optimistic conjecture

Kristal and Jason: looks like we’re off to a good start with the human proof of $c^\mu_3=6$ . I copied Kristal’s text to the wiki at

but presumably we could develop it further.

Given how successful the linear programming method based on sphere densities has been for Moser, I think it is worth a shot at working out linear inequalities for slice densities for the HOC; indeed one can view Kristal’s argument as implicitly using these slice densities.

14 March, 2009 at 9:27 am

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

1102. Genetic algorithm

Kareem, I put some of the description of your GA on the wiki at

If you had any further commentary (e.g. on the performance of the algorithm, and links to data) that would be great. Do you still think that verification of the line-free property is the bottleneck? One thought I had on this was to break up the lookup table into pieces, and only apply a piece of the table to each organism. The problem with this though is that it may allow organisms with one or two lines to survive for a bit longer than they should.

14 March, 2009 at 9:45 am

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

1103. Kakeya

Seva, this is a great suggestion! I transcribed your post to the wiki at

A recent result of Dvir, Kopparty, Saraf, and Sudan show that a Kakeya set in $F_q^n$ has size at least $q^n/2^n$ , while an earlier example of Dvir (and reproduced in an appendix of a paper by Saraf and Sudan) constructs a Kakeya set of size $2^{n-1} q^n + O(q^{n-1})$ . These are asymptotically tight to within a factor of 2 when q is large, but it doesn’t look like it works all that well for small q.

So, we have a new low-dimensional problem to chew on: is $k_4=27$ (i.e. is it impossible to have a 26-point set in [3]^4 that contains a line in every direction)? I guess a starting point would be to get a human proof of $k_3=13$ .

14 March, 2009 at 10:30 am

14 March, 2009 at 10:40 am

1104.

Thanks Terry. I don’t have a lot of time right now but I will add any extra commentary in a few days.

I am not completely sure that the line-free property is the bottleneck with respect to the speed of the program but it is probably a big contributor. I will have to do some experimenting. The line-free property causes limitations in several senses. It grows exponentially with n. The largest lookup table I have made is about half a gigabyte. It takes a long time to read into memory. If I only take part of it then I do think that could speed things up tremendously. One could squeeze some more speed up out of this idea by picking a random selection of lines in the lookup table and evaluating a whole generation with the same lines. This reduces cache misses. If it’s not the same group of lines each time then maybe this won’t hurt us too much.

Kristal Cantwell

1105. c^{\mu}_3=6

I have made some changes to one of the cases, that case is
where there is one point removed of the form aaa

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 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 111 is removed
then we must cover all lines of
the form xx2 xx3 and x22 and x33

Look at the pairs of lines such as xx2 and 33x
one with moving coordinates in two positions and
a fixed coordinate equal to 2 or 3 say 2
the other with fixed coordinates equal to the other
value which in this case is 2 so if the fixed coordinate(s)
in one point of the pair is 2 in the other they or it will
Then we must have one of the points 222
112 332 removed to block the first line of the pair
and for the second line we can use 333
332 331. However we do not have the points
222 or 333 removed in this case so we must have
either 332 or the pair 112 or 331.
For every one of the six point 332 or 223
we will have a similar choice forcing either
the removal of the point itself or the associated
pair. After these choices have been made more points
of the form aab can be added but there must be
a subset corresponding to one set of the above six choices
since in each case there are only two ways to cover the lines noted.
If we start with the configuration 111 removed all six points with
two 2’s and one three and two 3’s and one two removed and all points of
the form abc removed then this configuration has weight 6
then we can perform a series of steps which will
reach all combinatorial line free configurations.

These steps are as follows:

1 Making choices as above and allowing the addition
Of all possible abcs

2.Removal of points of the form aab and addition of all possible abc’s

3.Removal of abc

It will be shown that with each step the weight decreases or remains the same
so the weight is 6 or less
This will give all line free configurations as we must have sub configuration
corresponding to one of the six choices and all we can do is add points
of the form aab and take the resulting set with the most possible
Abc’s and them remove any arbitrary abcs that we wish to remove.

Are the making of the six choices noted above and the addition of
any points of the form abc where possible without forming a combinatorial line.
At the start each point of the form abc cannot be added because it has
two lines which are some permutations of x12 and x13 now
look at the points possibly blocking x12 they are 112 212 and 312 initially
point 312 which is removed could not be added because the two points
112 and 212 are not removed as each choice is moved then each of the
removed lines of type 113 covers two lines of the form permutations of x13
similarly lines of type 133 covers two lines of the form permutations of x13
now each choice to replace a line of the form 332 increase the number of
points removed with two coordinates the same by one thus lowers the weight
by one third and blocks four lines of the form x13 or x12 thus after
n such choices we have reduced the weight by n/3 and covered 4n such
lines since every point of the of the form permutations of 123
starts out with 2 such lines which it is blocking and can only be added
when they are filled we can only add at most 2n such points which
since they have weight 1/6 at the end of n such steps the weight
is unchanged now afterwards if we remove more points of the form
aab they cover at most two lines of the form xab and thus allow
at most two points of the form abc to be added thus the change in weight
is at most -1/3 +1/6 +1/6=0 finally afterwards we can remove points
of the form abc but that will only lower the weight.

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

14 March, 2009 at 12:13 pm

A tongue-in-cheek suggestion.

Metacomment: Logo

14 March, 2009 at 12:37 pm

Seva

1106. Here is a sketch of what, hopefully, can be developed into a human proof of $k_3\ge 13$ . The argument depends heavily on the fact that, applying a non-degenerate affine transformation to a Kakeya set, we get a Kakeya set. Let $e_1=(1,0,0),e_2=(0,1,0),e_3=(0,0,1)$ be the standard basis of ${\mathbb F}_3^3$ .

Suppose that $K\subset{\mathbb F}_3^3$ is a Kakeya set with $|K|=12$ . For each of the $(3^3-1)/2=13$ directions in ${\mathbb F}_3^3$ fix a line in this direction inside $K$ . We thus have $13$ lines, with $3$ points on each line, resulting in $39$ point-line incidences — and just $12$ points; therefore, there is a point in $K$ , incident with (at least) four lines. Shifting $K$ suitably, we assume that $0\in K$ and $K$ contains four lines through $0$ .

If all lines through $0$ in $K$ are contained in a subspace of dimension $2$ , then $K$ actually contains this subspace, and without loss of generality we can assume that the subspace is ${\rm Sp}\{e_1,e_2\}$ . Fix a vector in $K$ outside this subspace; WLOG, this vector is $e_3$ . Thus, $K$ consists of ${\rm Sp}\{e_1,e_2\}$ , $e_3$ , and two more vectors, and the proof is easy to complete in this case showing that such a set cannot contain a line in every direction.

Therefore, the four lines through $0$ are not contained in a proper subspace. Hence, applying a suitable linear transformation, we can assume that the directions, determined by these lines, are $e_1,e_2,e_3$ , and $b$ , with some vector $b\in{\mathbb F}_3^3$ of weight at least $2$ . (The weight of a vector for this purpose is the number of non-zero coordinates in its expansion in the standard basis.) That is, $\{0,\pm e_1,\pm e_2,\pm e_3,\pm b\}\subset K$ . If the weight of $b$ is $3$ , then, changing the signs of the vectors of the standard basis as needed (which is a linear transformation, of course), we can assume $b=e_1+e_2+e_3$ ; similarly, if the weight of $b$ is $2$ , then we can assume $b=e_1+e_2$ .

We thus are left with two cases to consider, as follows. Case (A): $K$ consists of $0,\pm e_1,\pm e_2,\pm e_3, \pm(e_1+e_2+e_3)$ , and three more vectors. Case (B): $K$ consists of $0,\pm e_1,\pm e_2,\pm e_3,\pm(e_1+e_2)$ , and three more vectors. Hopefully, both these cases can be completed with some moderate effort.

14 March, 2009 at 2:25 pm

15 March, 2009 at 5:20 am

1107. Kakeya

I realised that I can import some existing arguments in the literature to get some better lower bounds on Kakeya in this low characteristic, high dimensional regime than the (3/2)^n bound from Dvir-Kopparty-Saraf-Sudan.

For instance, we can use the “bush” argument. There are $N := (3^n-1)/2$ different directions. Take a line in every direction, let E be the union of these lines, and let $\mu$ be the maximum multiplicity of these lines (i.e. the largest number of lines that are concurrent at a point). On the one hand, from double counting we see that E has cardinality at least $3N/\mu$ . On the other hand, by considering the “bush” of lines emanating from a point with multiplicity $\mu$ , we see that E has cardinality at least $2\mu+1$ . If we minimise $\max(3N/\mu, 2\mu+1)$ over all possible values of $\mu$ one obtains approximately $\sqrt{6N} \approx 3^{(n+1)/2}$ as a lower bound of |E|, which is asymptotically better than $(3/2)^n$ .

Or, we can use the “slices” argument. Let $A, B, C \subset ({\Bbb Z}/3{\Bbb Z})^{n-1}$ be the three slices of a Kakeya set E. We can form a graph G between A and B by connecting A and B by an edge if there is a line in E joining A and B. The restricted sumset $\{a+b: (a,b) \in G \}$ is essentially C, while the difference set $\{a-b: (a-b) \in G \}$ is all of $({\Bbb Z}/3{\Bbb Z})^{n-1}$ . Using an estimate from my paper with Nets Katz, we conclude that $3^{n-1} \leq \max(|A|,|B|,|C|)^{11/6}$ , leading to the bound $|E| \geq 3^{6(n-1)/11}$ , which is asymptotically better still.

For an upper bound, I can invert the “slices” idea and use a construction of Imre Ruzsa. Let $A, B \subset [3]^n$ be the set of strings with $n/3+O(\sqrt{n})$ 1’s, $2n/3+O(\sqrt{n})$ 0’s, and no 2’s; let $C \subset [3]^n$ be the set of strings with $2n/3+O(\sqrt{n})$ 2’s, $n/3+O(\sqrt{n})$ 0’s, and no 1’s, and let $E = \{0\} \times A \cup \{1\} \times B \cup \{2\} \times C$ . From Stirling’s formula we have $|E| = (27/4 + o(1))^{n/3}$ . Now I claim that for most $t \in [3]^{n-1}$ , there exists an algebraic line in the direction (1,t). Indeed, typically t will have $n/3+O(\sqrt{n})$ 0s, $n/3+O(\sqrt{n})$ 1s, and $n/3+O(\sqrt{n})$ 2s, thus $t = e + 2f$ where e and f are strings with $n/3 + O(\sqrt{n})$ 1s and no 2s, with the 1-sets of e and f being disjoint. One then checks that the line $(0,f), (1,e), (2,2e+2f)$ lies in E.

This is already a positive fraction of directions in E. One can use the random rotations trick to get the rest of the directions in E (losing a polynomial factor in n).

Putting all this together, I think we have

$(3^{6/11} + o(1))^n \leq k_n \leq ( (27/4)^{1/3} + o(1))^n$

$(1.8207\ldots+o(1))^n \leq k_n \leq (1.88988+o(1))^n$

This seems consistent with your conjecture $k_{n+1} \leq 2k_n + 1$ .

Seva

1108. Kakeya in $F_3^r$

Dear Terry,

As I see it, your 1107 post essentially solves the problem: the gap between the lower and upper bounds is not that large now, and narrowing it further may be both pointless and tedious (while finding a sharp asymptotic may be hopeless). I would also say that the values of $k_r$ for small $r$ are not of much interest now that $\limsup(\ln k_r)/r<2$ is known to hold.

A couple of minor remarks.

The “bush argument” gives the very same estimate as that indicated in my original post. Since this estimates supersedes the Dvir-Kopparty-Saraf-Sudan bound, I have not mentioned the latter.

For the estimate $k_r\gg 3^{0.51r}$ mentioned in my post I used restricted addition and Balog-Szemeredi; so, the “slices argument” is kind of an improvement of what I did.

Also, for the slices argument: I don’t quite see why “the restricted sumset is essentially $C$ “, but it is contained in $-C$ , which is just fine for our purposes; correct?

15 March, 2009 at 8:11 am

http://www.ams.org/mathscinet-getitem?mr=1692486

1109. Kakeya in $F_3^r$

Fair enough. It may still be interesting to know the dependence on the field size though. For each prime power q, let $k_{q,r}$ be the minimal size of a Kakeya set in $F_q^r$ , then we know from submultiplicativity $k_{q,r+s} \leq k_{q,r} k_{q,s}$ that $k_{q,r}^{1/r}$ converges to a limit $\kappa_q$ . For instance I think one can show that $\kappa_q = \sqrt{2}$ , and we now know that $1.82\ldots \leq \kappa_3 \leq 1.88\ldots$ . What happens for other values of q? Dvir et al. show that $\kappa_q \geq q/2$ for all q, and of course $\kappa_q \leq q$ . I don’t know which bound is closer to the truth.

Your Balog-Szemeredi argument, by the way, sounds very similar to the original slices argument of Bourgain in which my paper with Nets was based (and the Bourgain paper was in turn inspired by Tim Gowers’ paper on Szemeredi’s theorem, and in particular on his version of the Balog-Szemeredi lemma):

In our language, the Bourgain argument would give $k_r \gg 3^{13r/25} = 3^{0.52 r}$ .

p.s. Yes, “contained in -C” is what I meant by “essentially C”. I got lazy and didn’t want to work out the exact relationship :)

15 March, 2009 at 11:03 am

Seva

1110. Kakeya in ${\mathbb F}_3^r$ (in reply to 1109)

> Your Balog-Szemeredi argument, by the way, sounds
> very similar to the original slices argument of Bourgain

Not surprising: the idea to use this approach was actually suggested to me by Bourgain!

Also, upon some thinking. It seems that Ruzsa’s argument that you mention is not really about slices; it is about a clever modification of the construction from my initial post. Namely, instead of the set $K$ of all vectors in ${\mathbb F}_3^r$ with either $1$ , or $2$ missing among their coordinates, consider its subset $K_0:=A\cup B$ , where $A$ is the set of all those vectors with $r/3+O(\sqrt r)$ coordinates equal to $1$ and the rest equal to $0$ , and $B$ is the set of all those vectors with $2r/3+O(\sqrt r)$ coordinates equal to $2$ and the rest equal to $0$ . Then $K_0$ , being of size just about $(27/4)^{r/3}$ , contains lines in positive proportion of directions. No slices!

15 March, 2009 at 1:10 pm

Kristal Cantwell

1111. Moser sets n=4

If a Moser set for n=4 has 5 or more points with three 2’s it must have less than 41 points it must have the following statistics:
(7, 15, 14, 5,0), (6, 15, 15, 5,0)

I have already proved the case with 6 or more points cannot occur so all I need to do here is get the case n=5. 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 5 points with three 2’s the center slice must have the remaining three. 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 15. Further it must have the statistics (3,9,3,0) The two side cubes must have statistics 3,6,3,1) or (4,6,2,1) this gives three possible combinations which give the following possible sets of statsitcs:

(8, 15, 13, 5,0), (7, 15, 14, 5,0), (6, 15, 15, 5,0)
Now the statistics (8, 15, 13, 5,0) violate the following inequality from the section n=4 of the wiki
4a + b + c + d is less than or equal to 64 as it equals 65. So we are left with:
(7, 15, 14, 5,0), (6, 15, 15, 5,0) and we are done.

15 March, 2009 at 2:02 pm

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

1112. Terry suggested that these types of visualizations might be more useful. I have made a few.

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

15 March, 2009 at 4:13 pm

15 March, 2009 at 4:47 pm

1113. 4D Moser

Kristal, I played around with Michael’s linear inequalities using maple and I think I can rule out d=5 completely for the 41+ point sets using them via a purely human proof (which was found, of course, using maple). On the 3D section of the Wiki, we have the inequalities

$4\alpha_0+4\alpha_1+3\alpha_2+\alpha_3 \leq 6$ (1)

$7\alpha_0+3\alpha_1+3\alpha_2+\alpha_3 \leq 7$ (2)

which when averaged on middle slices gives the 4D inequalities

$b/8 + c/6 + 3d/8 + e \leq 6$ (3)

$7b/32 + c/8 + 3d/8 + e \leq 7$ . (4)

Averaging (1) on side slices similarly gives

$a/4 + b/8 + c/8 + d/8 \leq 6$ . (5)

Computing 9/4 *(3) + (4) + 4*(5) gives

$a+b+c+d+e \leq 89/2 - 23 d / 32 - 9 e / 4$

and so if $a+b+c+d+e \geq 41$ then we must have $d \leq 4$ .

I got maple to find the integer solutions to $d=4, a+b+c+d+e \geq 41$ that were consistent with all known inequalities. They are: (6,16,15,4,0,0), (7,16,14,4,0,0), (7,17,13,4,0,0), and (7,18,12,4,0,0).

http://twofoldgaze.wordpress.com/2009/03/16/visualizations-iii/

1114. An animation of extremals of type c’_5:

16 March, 2009 at 7:58 am

(Text)
http://twofoldgaze.wordpress.com/2009/03/16/solution-of-size-989-text/

1115.

I found a new largest solution for c’_7:

(Image)
http://twofoldgaze.wordpress.com/2009/03/16/solution-of-size-989-image/

16 March, 2009 at 2:17 pm

Christian Elsholtz

1116. Kareem’s 989 Moser-example in dimension 7.

here is an analysis which perhaps helps improving your programme:
I do not exactly know how your programme works, so the analysis is how a programme could have found the 989 set from the 988 set.

The 988 solution and the new 989 solution do not differ very much.
Start with the 988 solution.
Delete {1112223, 1311231}
and add {1111233, 1112333, 2312231}
and you have the 989 solution.

While a complete search to find such an exchange might need about
988 times 987/2 steps for the deletion, multiplied with
(2187-988)times (2187-989) times (2187-990)/6 steps for the
addition, the following speeds it up considerably:

Start with a progression-free set.
Take a loop over one element to be added. (Here say 988 steps).
Write down all clashes. (those must include of course the new element, so the search may be efficient).
If there are many forget about this case,
if there are very few, delete some of them.
Check if all clashes are avoided, and for any pair of two
elements list those elements that extend the two to a progression.

In this example this works extremely well.

Start with the 988 set.
add {1111233}, giving 989 elements.
The set of clashes is built by the five elements.
{1111233, 1112223, 1113213, 1211232, 1311231}

Choose subsets of 2 of the 4 elements. (of course avoid 1111233 which we
just added).

If in this way you delete for example {1112223,1311231}, and check for elements which
are now not the last point of an arithmetic progression, then you find
{1112333, 2312231}.

(Well, I may have been lucky with this choice, but the point is that there are not so many cases.)

More generally, it seems one can iterate this:
instead of deleting k and adding k+1 elements, which seems to produce many
cases, proceed in the above balanced way:
add one, and only use those cases with very few clashes.
Choose from these few clashes two (or more) elements to delete,
and check which elements can then be added etc.

16 March, 2009 at 3:41 pm

16 March, 2009 at 4:00 pm

1117. Christian’s idea sounds like a great idea for a mutation operator. The current one is somewhat dumb, it adds one where it can and doesn’t do any global considerations of the whole solution. I ruled out any kind of global examination of the solution as too slow but now that more computations aren’t yielding dramatically better results, a slow operator doesn’t seem as expensive as it did before.

I had been intending to solicit advice on small tricks that people have found useful in generating new solutions. (If Christian or any one else has any ideas please let me know.)

Thanks for the idea, Christian. There are an ever growing list of things that need to be done with this project but I will implement this one as soon as I can.

Micahael Bacon

I can’t contribute directly to these types of developments, but I would be interested in Mr. Tao’s thoughts regarding what I think is the amazing ability of web-based approaches to these and many other math and physics issues. Does this new rapid and multi-personal addressing of issues offer hope that much more rapid progress will be made?

16 March, 2009 at 4:14 pm

16 March, 2009 at 4:27 pm

1118. 4D Moser extremals

The 3D Moser extremals that Michael found (by computer exhaustion of the 2^{27} cases, though I would imagine that we could also verify the resulting linear inequalities by hand if needed) have been very useful in higher D. It would thus be nice to obtain a list of 4D Moser extremals. Even just knowing the e=1 extremals would presumably improve our inequalities somewhat.

Unfortunately, direct exhaustion requires 2^{81} cases to check, which is too huge. There is a symmetry group of size $4! \times 2^4 \approx 2^9$ to cut things down a little bit, and we can of course close off any branch of the exhaustion that contains a line, but this is still not feasible.

On the other hand, by collapsing the 81 points of $[3]^4$ into the five classes a,b,c,d,e (with 16, 32, 24, 8, 1 points in each) we get a much more tractable integer program, and we can already get quite far just from using the linear inequalities inherited from 3 and lower dimensions. But it doesn’t quite give us everything we need, e.g. it gives an upper bound of 44 off the bat, and additional work is needed to get 43, and we still can’t rule out d=4 41-point sets other than via Klas’s data.

So I propose an intermediate regime, in which we identify 1s and 3s but leave the 2s intact. Let’s use x to denote letters that are either 1 or 3, then the 81 points get split up into 16 groups: 2222 (1 point), 222x, 22×2, 2×22, x222 (two points each), 22xx, 2x2x, x22x, 2xx2, x2x2, xx22 (four points each), 2xxx, x2xx, xx2x, xxx2 (eight points each), xxxx (sixteen points). Let c(w) denote the number of points inside a group w, e.g. c(xx22) is the number of points of the form xx22 inside the set, and is thus an integer from 0 to 4.

Every combinatorial line in $\{2,x\}^4$ gives rise to an inequality between the corresponding c’s. For instance, the line $\{222x, 2xxx\}$ gives rise to the inequality $c(222x)/2 + c(2xxx)/4 \leq 2$ (as can be seen by considering the four lines connecting a 222x point to two 2xxxx points) and more generally we have $c(u)/2^a + c(v)/2^{b-1} \leq 2$ whenever $\{u,v\}$ is a line where u has a 2’s and v has b 2’s with $b > a$ .

This is an integer program on 16 variables and 80 line inequalities (plus the upper bound $c(2222) \leq 1$ and the 16 inequalities asserting that all c(w) are non-negative), which looks tractable. One should be able to get a list of Pareto-optimal and extremal c-statistics either by integer-programming or by brute force. (The total number of possible c-statistics is $2 \times 3^4 \times 5^6 \times 9^4 \times 17 \approx 2.8 \times 10^{11}$ , which is at the edge of what brute force can deal with, but presumably one can use symmetries to cut things down a bit (e.g. assuming $c(2xxx) \leq c(x2xx) \leq c(xx2x) \leq c(xxx2)$ cuts things down by a factor of 13 or so; also, c(xxxx) can be easily maximised after making all the other choices, potentially saving a factor of 17). The e=1 case (when c(2222)=1) should be particularly doable (the total number of possibilities here is now $2^4 \times 3^6 \times 5^4 \times 9 \approx 6.5 \times 10^8$ , and after using symmetries this should be quite manageable). Once the possible c-statistics are known, the (a,b,c,d,e) statistics can then be recovered (for instance, we may be able to improve the current upper bound of 39 for the size of e=1 4D Moser sets). (Also, the c-statistics also reveal the (a,b,c,d,e) statistics of 4D diagonal cubes in higher dimensions, e.g. xxyyzw, which could lead to further improvement in the 6D and 7D bounds.)

Of course, just as the a,b,c,d,e inequalities didn’t fully recover all possible statistics of Moser sets, it could be that the c-inequalities (which are only “averaged” versions of the property of having no combinatorial lines) don’t quite capture the full truth of the situation. But they should do better than the (a,b,c,d,e) inequalities method, and seem within range of a reasonable computer search.

http://twofoldgaze.wordpress.com/2009/03/16/the-structure-of-the-extremal-1302/

1119. I thought this analysis of the solutions of c_7 might be of interest:

http://twofoldgaze.wordpress.com/2009/03/16/the-structure-of-the-extremals-of-1302-ii/

16 March, 2009 at 4:28 pm

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

1120. c-statistics

I should say that perhaps it would be wise to first see if this method can already recover the known extremals in 3D. I can at least do 2D by hand: here we have four integers $0 \leq c(22) \leq 1$ , $0 \leq c(2x), c(x2) \leq 2$ , $0 \leq c(xx) \leq 4$ obeying the inequalities

$c(22) + c(2x), c(22) + c(x2) \leq 2; c(2x)+c(xx), c(x2)+c(xx) \leq 4; 2c(22) + c(xx) \leq 4$ .

By symmetry we may also impose (say) $c(2x) \leq c(x2)$ . The extremals for $(c(22), c(2x), c(x2), c(xx))$ are then (0,0,0,4), (0,2,2,2), (1,1,1,2), which correspond exactly to the (a,b,c) extremals (0,0,4), (0,4,2), (1,2,2).

Also, every linear c-inequality at a given dimension implies further linear c-inequalities at higher dimensions by suitable averaging over cubes (but we don’t average as much as in the (a,b,c,d,e) case, we only average over permutations of 1 and 3). One could imagine iteratively building up the c-inequalities much as we have been doing for the coarser (a,b,c,d,e) type inequalities. For instance the above 2D extremals show that $c(22) + c(2x) + c(xx), c(22)+c(x2)+c(xx) \leq 4$ , which can be leveraged to higher dimensions (e.g. the first inequality implies that $c(222)+c(2x2)+c(xx2) \leq 4$ and $c(22x)/2+c(2xx)/2+c(xxx)/2 \leq 4$ , and also $c(22)+c(22x)+c(xxx)/2 \leq 4$ , by looking at yz2, yzx, and yyz cubes respectively, where the wildcard x is understood to be 1 or 3 but the other wildcards are unrestricted.)

Dear Micahael: these issues are being discussed over at Gowers’ blog at

16 March, 2009 at 5:26 pm

Kristal Cantwell

1121. Alternative to c-statistics

One alternative is breaking up points according to their number of 1’s, 2’s and 3’s this would grow as $n^3$ as opposed to c-statistics which might be exponential. Also both could be combined in order to get more information.

17 March, 2009 at 9:57 am

Michael Peake

1122. Alternative to c-statistics

Kristal, isn’t that just the $\Gamma$ slices we have been using? It only grows as $n^2$ because the total number of 1s, 2s and 3s is constant.

I am running Terry’s idea for ${}[3]^4$ at home, and it looks like it will take a day or two.

17 March, 2009 at 10:06 am

Kristal Cantwell

1123. Alternative to c-statistics

Yes I think these are the slices we have been using and I agree they are quadratic, $(n^2 + n)/2$ .

17 March, 2009 at 4:12 pm

http://twofoldgaze.wordpress.com/2009/03/17/the-structure-of-the-extremals-of-1302-iii/

1124. The next installment in my new series ‘Better know an extremal …’:

18 March, 2009 at 2:05 am

Michael Peake

1125. c-statistics

I ran a search for the sixteen c-statistics (2×22, 22×2, etc)
I could only find 65 rules, from the 65 combinatorial lines.

My results limit the total possible points for 4D Moser below 73, which is higher than 43. Either I have a bug, or there was too little connection between the various c statistics.

For the record, the Pareto extremals it found were
16,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
8,8,8,8,8,4,4,4,4,4,4,2,2,2,2,1
12,4,4,4,4,2,2,2,2,2,2,1,1,1,1,0
14,2,2,2,2,1,1,1,1,1,1,0,0,0,0,0
10,6,6,6,6,3,3,3,3,3,3,1,1,1,1,0
15,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0
13,3,3,3,3,1,1,1,1,1,1,0,0,0,0,0
11,5,5,5,5,2,2,2,2,2,2,1,1,1,1,0
9,7,7,7,7,3,3,3,3,3,3,1,1,1,1,0

18 March, 2009 at 4:14 am

Michael Peake

1126. c-statistics

I ran through the 2^27 subsets of the 3D cube, looking for Moser sets. I classified them with the c-statistics. I collected Pareto optimal points. Then, from the extremal points I found a set of twenty linear inequalities satisfied by all Moser sets. They are the same linear inequalities found earlier for the ‘xxxxyyz diagonals’. They are on Sheet 8 of a spreadsheet in the Moser section of the wiki.

I don’t yet know their effects in 4D

18 March, 2009 at 9:52 am

18 March, 2009 at 10:57 am

1127. Progress on $\overline{c}^\mu_6 = 15$

What I have typed so far is at the talk page about Fujimura’s on the wiki. My time is limited (my wife is close to giving birth to our first child) so it may be a while before I can finish all the cases.

Kristal Cantwell

1128. Progress on \overline{c}^\mu_6 = 15

“My time is limited (my wife is close to giving birth to our first child)”

Congratulations!

18 March, 2009 at 11:12 am

Kristal Cantwell

1129. c^{\mu}_4=9

If c^{\mu}_4 is greater than 9 then the counterexample must occur
when there is exactly one point of the form aaaa removed. The other three cases are below.

If we have all
three points of the form aaaa removed
then the remaining points have value 12 and
we have covered all lines any set of moving coordinates
with all constant points equal to one value this leaves
the lines xxab, xabc and xaab. let us also remove the three sets of the form aabc, a, b, c not equal. These block the remaining lines and the size is now 9.

Now suppose we try to replace the removed points of the form aabc by points of the form aaab or aabb. Now we must cover the lines of the form xaab each point of the form aabc covers two and has a weight 1/12 each point of the form aabb covers 4 and has a weight 1/6 each point of the form aaab covers three and has a weight of 1/3 and since each element of the form covers two elements of the form xaab that no other element of the set aabc covers and as noted above all lines of the form xaab are covered by the the elements of the three sets of the form aabc we cannot improve on the weight as we can only cover the xaab’s by the same or higher weight lowering the total from 9 so for this case the value is 9.

If we have two points removed of the form aaaa then
the weight is at most 13 say the point not removed is 2222
then we must cover the lines xxx2 and x222 we have eight such
lines and all six xx22 must be covered one at a time by either 1122
or 3322 the four x222 must be covered one at a time by 3222 or 1222
the four xxx2 must be covered by 3332 or 1112
these points must be removed and the that lowers the weight
To 13 – 4*(6/24) – 6*(1/6) – 4(6/24) = 10.
We also have 24 lines of the form xabc which can only be covered
two at a time by the aabc which have weight 1/12 so we need to cover
these with at least 12 of these which we can do by choosing all points which are permutations of
1123 this reduces the number to 9 and
again we have c^{\mu} must be 9.

Finally we have no points of the form aaaa removed but then we will
have a line of the form xxxx.

19 March, 2009 at 3:25 pm

19 March, 2009 at 3:30 pm

1130 $\overline{c}^\mu_6 = 15$

$\overline{c}^\mu_6 \geq 15$ from the bound for general n.

Note that there are ten extremal solutions to $\overline{c}^\mu_3$ :

Solution I: remove 300, 020, 111, 003
Solution II (and 2 rotations): 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
Solution VI’: remove 120, 012, 201

The on the 7x7x7 triangular lattice triangle 141-411-114 must have at least one point removed. Remove 141, noting by symmetry any logic that follows will also work for either of the other two points.

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

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

At least 4 of those removals must come from the top triangle (the solutions of $\overline{c}^\mu_3$ mentioned above).

The bottom trapezoid 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 at least six removals must come from the bottom trapezoid.

To make a total of 12 removals there must be either:
Case A: 4 removals from the top triangle and 8 from the bottom trapezoid.
Case B: 5 removals from the top triangle and 7 from the bottom trapezoid.
Case C: 6 removals from the top triangle and 6 from the bottom trapezoid.

* Suppose case A is true.

Because 141 is already removed, the solution to the upper triangle must remove either solution I (remove 060, 330, 033), solution II (remove 060, 231, 132), solution IIb (remove 033, 150, 240) or solution IIc (remove 330, 051, 042)

Suppose I is the solution for the upper triangle.

Suppose 222 is open. Then 420, 321, 123, and 024 must all be removed. This leaves five disjoint triangles which require removals in the bottom trapezoid (150-600-105, 051-501-006, 222-402-204, 231-411-213, 132-312-114); therefore the bottom trapezoid needs at least 9 removals, but we can only make 8, therefore 222 is closed.

Suppose 411 is open. Then 213 and 015 must be removed. This leaves five disjoint triangles such that each triangle must have exactly one removal (420-150-123, 321-051,024, 600-510-501, 402-312-303, 204-114-105), so the remaining point (006) must be open, forcing 501 to be removed. This makes 600 and 510 open, and based on the triangles 600-240-204 and 510-150-114 both 204 and 114 must both be removed, but 204 and 114 are on the same disjoint triangle, contradicting the statement that each triangle must have exactly one removal. So 411 is closed.

This leaves six disjoint triangles each which must have at least one removal (420-123-150, 321-024-051, 510-213-240, 312-015-042, 501-204-231, 402-105-132). This forces 600 and 006 to be open. Based on the triangles 006-501-051 and 600-204-240, this forces 501 and 204 to be open. But then there are no removals from the triangle 501-204-231, which is a contradiction. Therefore the solution of the upper triangle cannot be I.

Suppose II is the solution for the upper triangle.

There are seven disjoint triangles (150-600-105, 051-501-006, 222-402-204, 240-510-213, 042-312-015, 330-420-321, 033-123-024), therefore of the three points remaining in the bottom trapezoid (411, 303, 114) exactly one must be removed.

Suppose 411 is removed. Then 114 and 303 are open; 114 open forces 510 to be removed, forcing 213 to be open. 114 and 213 open force 123 to be closed, forcing 024 to be open. 024 open forces 222 to be closed, which forces 204 to be open, which leaves the triangle 213-303-204 open so we have a contradiction.

By symmetry 114 also can’t be removed. Therefore we must remove 303. This leaves 411 and 114 open, forcing 510 and 015 closed. 510 and 015 closed forces 312 and 213 open, forcing 222 closed. 222 closed forces 402 and 204 open. 402 and 204 open force 501 and 105 closed. 510 and 105 closed force 600 and 006 open, leaving equilateral triangles 600-204-240 and 402-006-042 open. Therefore 303 can’t be removed, and so the solution of the upper triangle can’t be II.

Suppose IIb is the solution for the upper triangle.

Suppose 024 is open. This forces 420, 321, and 222 closed. Five disjoint triangles remain (510-600-501, 231-411-213, 132-312-114, 123-303-105, 024-204-006) so each must have exactly one point removed, and the remaining points in the lower trapezoid (402, 015) must be open. This forces 312, 411, 510, and 006 closed, which then force the the other points in their disjoint triangles open (600, 501, 231, 213, 132, 114, 204). The triangle 501-231-204 is therefore open, so we have a contradiction, therefore 024 is closed.

Suppose 006 is open. This forces 600, 501 and 402 to be closed, and leaves five disjoint triangles (510-420-411, 321-231-222, 312-132-114, 303-213-204, 105-015-006) and so 123 must be open. This forces 222 closed, which forces 321 open, which forces 420 closed, which forced 510 and 411 open, which forces 213 closed, which forces 303 and 204 open, which forces 105 closed, which forces 015 and 006 to be open, leaving an open triangle at 411-015-051. Therefore we have a contradiction, so 006 is closed.

Given 024 and 006 closed, now note there are six disjoint triangles (600-510-501, 402-312-303, 204-114-105, 420-330-321, 222-132-123, 411-231-213). Therefore the remaining point in the lower trapezoid 015 must be open, forcing 510, 411, and 312 to be closed. Using the disjoint triangles this forces 600, 501, 402, 303 and 213 to be open, which then forces 420 and 321 to be closed. Both 420 and 321 are on the same disjoint triangle, therefore we have a contradiction, so IIb can’t be solution.

Note by symmetry, the same logic for IIb will apply for IIc. Therefore case A isn’t true.

* Suppose case B is true.

The row 330-231-132-033 has ten possible solutions (excluding reflections, which by symmetry will be handled by the same logic):

Case Q: open-open-open-open
Case R: closed-closed-closed-closed
Case S: closed-open-open-open
Case T: closed-open-closed-closed
Case U: open-closed-closed-closed
Case V: closed-open-closed-closed
Case W: closed-closed-open-open
Case X: closed-open-closed-open
Case Y: open-closed-closed-open
Case Z: closed-open-open-closed

Consider all 10 cases. Note in all these cases we are still assuming 141 is removed.

(Case Q) 330, 231, 132, 033 open forces 060, 150, 051, 240, 141, 042 closed, but the upper triangle only allows 5 removals, so case Q forms a contradiction.

(Case R) 060-240-042 is left open, so case R forms a contradiction.

(Case S) 231, 132, and 033 open force 031 and 042 removed, which means from 240, 150, 061 there must be exactly one removal.

Suppose 213 is open. Then 411 and 015 are closed, and five disjoint triangles are left where each triangle must have exactly one removal (600-420-402, 501-321-303, 312-222-213, 204-105-114, 123-024-033). So the two remaining points in the lower trapezoid (510 and 006) must be open. 510 and 006 open force 303 closed, which forces 321 and 501 open, which forces 204 closed, which forces 114 and 103 open, which forces 402 and 312 closed, forcing 222 open, leaving 321-231-222 as an open triangle, so we have a contradiction.

Therefore 213 is closed. This leaves six disjoint triangles (600-420-402, 501-231-204, 303-033-006, 411-321-312, 222-132-123, 114-024-015) which each have exactly one removal. Therefore 510 from the lower trapezoid is open. Note since one of 150 and 060 must be open, then one of 114 or 015 must be closed; therefore 024 is open. This forces 123 closed, forcing 222 to be open, forcing 321 to be closed, forcing 411 and 312 open, forcing 421 closed, forcing 600 and 402 open, forcing 303 closed, forcing 006 open, forcing 204 closed, forcing 501 open, leaving the triangle 600-510-501 open and a contradiction.

(Case T) 231 is closed, and 330, 132, and 033 open force 060, 150, and 042 closed. Since 141 is already closed we have five removals from the top triangle, so 240 and 051 are open.

Suppose 024 is open. This forces 321 and 123 closed, leaving five disjoint triangles (600-510-501, 402-312-303, 204-114-105, 420-240-222, 213-033-015). Therefore 006 and 411 remaining in the lower trapezoid are open, forcing 501, 303 and 015 closed, forcing 600, 510, 312, 402, and 213 open, forcing 222 closed, forcing 420 open, leaving the open triangle 420-510-411, so we have a contradiction.

Therefore 024 is closed. There are now six disjoint triangles (510-600-501, 330-420-321, 312-402-303, 132-222-123, 033-213-015, 114-204-105). This leaves 411 and 006 open, which forces 015 and 501 closed, which forces 510 and 213 open, leaving the triangle 240-510-213 open, so we have a contradiction.

(Case U) Given the removals 231, 132, 033, and 141, the only possible removal to not leave any equilateral triangles in the upper triangle is 060. So 330, 240, 150, 051, and 042 are open.

Suppose 420 is open. This forces 321, 222, and 123 closed. This leaves five disjoint triangles (600-330-303, 510-420-411, 204-105-114, 501-051-006, and 312-042-015), so we have a contradiction.

Therefore 420 is closed. This leaves six disjoint triangles (600-330-303, 501-051-006, 204-114-105, 510-240-213, 411-321-312, 222-042-024). 015 in the lower trapezoid is therefore open, forcing 312 and 411 closed, but 312 and 411 are on the same disjoint triangle, so we have a contradiction.

(Case V) Given the removals 330, 132, and 033, the only possible removal to not leave any equilateral triangles in the upper triangle is 060. So 150, 051, 240, 042, and 231 are open.

Suppose 420 is open. Then 222 and 123 are closed, and we are left with 6 disjoint triangles (150-600-105, 240-510-213, 231-501-204, 024-114-015, 042-402-006, 411-321-312). This exceeds our limit of 7 removals in the bottom trapezoid, so we have a contradiction.

Therefore 420 is closed. Again we are left with the same 6 disjoint triangles (150-600-105, 240-510-213, 231-501-204, 024-114-015, 042-402-006, 411-321-312). Therefore 222, 123, and 303 are open. This forces 321, 024, and 105 to be closed, which then forces 411 and 015 to be open, forming an open triangle at 051-411-015, so we have a contradiction.

(Case W) Given the removals 330 and 231 with 132 and 033 open, 132 and 033 open force 042 closed. Given 141 is already closed, that leaves one more removal on the upper triangle, which must be one of 060-150-051, so 240 must be open.

Suppose 024 is open. This forces 123 to be closed, and leaves 6 disjoint triangles (600-510-501, 420-240-222, 411-321-312, 402-132-105, 213-033-015, 204-024-006). So 303 and 114 in the lower trapezoid are left open, forcing 312 and 005 to be closed, forcing 204 and 321 to be open, forcing 600 and 501 to be closed. 600 and 501 are on the same disjoint triangle so we have a contradiction.

Therefore 024 is closed. Suppose 312 is open. This forces 114 to be closed, and leaevs 5 disjoint triangles (600-510-501, 411-321-312, 303-213-204, 222-132-123, 105-015-006). Therefore 402 in the lower trapezoid is open, which forces 105 to be closed, which forces 015 and 006 to be open, which forces 213 and 303 to be closed, which are on the same disjoint triangle, so we have a contradiction.

Therefore 312 is closed. This leaves five disjoint triangles (510-240-213, 501-411-402, 222-132-123, 204-114-105, 303-033-006), and leaves 600, 420, 321, and 015 in the lower trapezoid open. This forces 402 and 213 to be closed, which forces 510 and 411 to be open, leaving an open triangle at 510-420-411, so we have a contradiction.

(Case X) 330 and 132 closed and 231 and 033 open imply 051 is closed, and since 141 is closed and we have only one more removal in the upper triangle it must be one of 240, 042, or 060. This leaves 150 open.

Suppose 321 is open. This forces 222 to be closed and leaves six disjoint triangles (600-420-402, 510-150-114, 411-321-312, 303-213-204, 105-015-006, 123-033-024), leaving 501 in the lower trapezoid open. This forces 204 to be closed, which forces 303 to be open, leaving an open triangle at 501-321-303.

So 321 is closed. This leaves six disjoint triangles (600-420-402, 510-150-114, 501-231-204, 312-222-213, 123-033-024, 105-015-006) and leaves 303 and 411 in the lower trapezoid open. This forces 213 and 006 to be closed, and forces 312, 222, 105, and 015 to be open. This forces 600 to be closed and 402 to be open, leaving an open triangle at 402-312-303. So we have a contradiction.

(Case Y) 330 and 033 are open, 330 and 033 open force 060 to be closed. With 141 closed there can be only one more removal, so suppose 150 is open (and note that if 150 was closed, we can use symmetry considering 051 to be open).

Suppose 600 is open. This forces 303 to be closed, and leaves six disjoint triangles (510-150-114, 420-330-321, 411-501-402, 222-312-213, 033-123-024, 015-105-006). So 204 in the lower trapezoid is left open. 600 and 150 open implies 105 is closed, forcing 015 and 006 to be open, forcing 024 and 213 to be closed, forcing 312, 222, and 123 to be open, forcing 042 in the upper triangle to be closed (so 051 and 240 are open). 051 and 015 open force 411 to be closed, which forces 501 to be open and leaves the open triangle 051-501-006.

So 600 is closed. This leaves six disjoint triangles (510-150-114, 420-330-321, 411-501-402, 222-312-213, 033-123-024, 015-105-006). 015 is the lower trapezoid is then left open, forcing 312 and 411 to be closed. However, 312 and 411 are on the same disjoint triangle, so we have a contradiction.

(Case Z) 330, 141, and 033 are closed, and 231 and 132 are open. Suppose 051 is open (note that if this forms a contradiction, by symmetrical argument we can say both 150 and 051 are closed).

Suppose 114 is closed. This leaves six disjoint triangles (600-510-501, 402-312-303, 105-015-006, 411-231-213, 222-132-123, 321-051-024) and so 420 and 204 are open. This forces 501 to be closed, which forces 510 and 600 to be open, which forces 411 and 402 to be closed, which forces 213 and 303 to be open, leaving an open triangle at 213-303-204.

So 114 is open. Suppose 213 is closed. This leaves five disjoint triangles (600-420-402, 501-321-303, 411-051-015, 222-132-123, 204-024-006) and in the lower trapezoid 510 and 105 are open. This forces 204 to be closed, forcing 024 and 006 to be open, forcing 015 to be closed, forcing 411 to be open, forcing 420 to be closed, forcing 402 to be open, leaving the open triangle 402-132-105.

So both 114 and 213 are open. Therefore 411 and 312 are closed. This leaves five disjoint triangles (600-510-501, 303-213-204, 105-015-006, 222-132-123, 321-051-024). The remaining points in the lower trapezoid (420, 402) are then open, forcing 105 to be closed, forcing 015 and 006 to be open, forcing 024 to be closed. Also note 114 and 213 open force 123 to be closed, which forces 222 to be open, which forces 321 to be closed. 321 and 024 are on the same disjoint triangle, so we have a contradiction.

So 150 and 051 are both closed. However, this leaves the triangle 240-042-060 open, so case Z is impossible.

Since all ten solutions have been eliminated, case B is impossible.

* Suppose case C is true.

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 (more than the 6 allowed), 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, our remaining 6 removals on the top triangle. However, we have already removed 141, forcing one removal too many, 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 the bottom trapezoid to use only 6 removals.

We have determined cases A, B, and C to be impossible, therefore it impossible to form a triangle free configuration on the 7x7x7 lattice with only 12 removals. Therefore $\overline{c}^\mu_6 = 15$ .

20 March, 2009 at 5:44 am

1130. $\overline{c}^\mu_6 = 15$

The proof is complete.

I tried to post it here but I guess it was too large and got caught by the spam filter? It’s definitely a level of complexity over latex \overline{c}^\mu_5$.

Michael Peake

1131 c-statistics

The 3D cube has 14 ways to fit in the 4D cube: 4 side-slices 2yzw, 4 middle slices xyzw, and six diagonal slices wwyz. So twenty inequalities for the cube become 280 inequalities for the 4D cube. There is some repetition, so there are only 239 different inequalities. One solution of these inequalities has 44 points: $cxxxx = cxxx2 = cxx22 = 4$ and permutations.

There were 2150 inequalities for the 5D cube with c-statistics; I have not yet found the maximum for that.

20 March, 2009 at 8:30 am

21 March, 2009 at 8:22 am

1132. Commentary on $\overline{c}^\mu_6 = 15$ .

The basic proof strategy was to set up removals such that there would be enough disjoint triangles to say that each triangle needed to have one removal. Then any points not in the union of disjoint triangles were forced to be in $\overline{c}^\mu_6$ , and those points could be used to force a chain of removals leading to an impossibility.

Unfortunately the process was not very mechanical, so it’d be hard to come up with a mathematical generalization. Each case was like its own individual puzzle, and I often had to go through multiple bad attempts before I found a set that broke things open.

However, there was a technique I used in making solution sketches which may have some useful general properties — look for all the possible disjoint triangle sets on a possible configuration, then pick the “overlay pattern” that was the most useful (possibly switching patterns mid-problem).

For example, here’s a simple mathematical property:

Suppose some set of points $Q$ on the triangular lattice that has a maximal number of disjoint triangles $m$ where $m$ removals are also sufficient to produce a triangle-free set. Let $F_1,\dots,F_j$ be the triangle-free sets of $Q$ (if the solution is unique, $j = 1$ ).

Consider all sets $T_1,\dots,T_k$ where $k$ is the number of possible configurations of $m$ disjoint triangles in the set $Q$ .

Then for each $1 \leq i \leq k$ , $Q \setminus T_i$ must be a subset of $F_1\cap\dots\cap F_j$ .

(In other words, any points remaining after locating disjoint triangles must be open, considering all of the possible disjoint triangle configurations.)

It’s also possible to set up a graph representing where the disjoint triangles overlap.

Let me take the case of $\overline{c}^\mu_3$ . There are two disjoint triangle configurations: A = 030-120-021, B = 210-300-201, C = 012, 102, 003 and D = 030-210-012, E = 120-300-102, F=021-201-003. Any removal from A has to remove also remove from either D, E, or F; any removal from B has to remove from either D, E, or F, and any removal from C has to remove from either D, E, or F. This can be represented as a complete bipartite graph between A, B, C and D, E, F.

I’m not sure if anything in this will be useful for solving general n, but it might be possible to scrounge some tools to work on low-n cases.

Michael Peake

1132 Kakeya k_3 > 12

We try to find a set A containing twelve points in F_3^3 that form a Kakeya set.

Seva showed in 1106 that we can assume A contains four lines through the origin, including the three axes. (000),(001),(002),(010),(020),(100),(200)

Case A: The fourth line is in the xy plane z=0. Then seven points are in this plane, leaving five points in the two planes z=1, z=2. There are nine directions not parallel to the xy plane; each direction must contain two of the five points, one in the z=1 plane and one in the z=2 plane. This is impossible.

Case B: The fourth line is (000),(111),(222)
If there is a sixth point in the z=0 plane, there are only six points left in z=1 and z=2. To form nine directions out of the xy plane, we need three points in z=1 and three in z=2. We also need none of the nine directions parallel to each other. But (002)-(111) is parallel to (222)-(001), so we can’t get nine non-parallel directions out of the plane.

So the z=0 plane only contains points along the axes. Likewise the x=0 and y=0 planes. There are three points left to place, and they all lie in the cube [1,2]^3.

To form a (120) line, we need to include (121) and (211). Then, to form a (110) line, we need to include either (112) or (221)

Case B1: the extra three points are (121),(211),(112). There is no (112) line.

Case B2: the extra three points are (121),(211),(221). There is no (102) or (012) line.

21 March, 2009 at 11:43 am

Kristal Cantwell

1133. c^{\mu}_4=9

This is the final case of the partial proof in 1129.

If one point of the form aaaa is removed say 1111
then we must cover all lines of
the form xxx2 xxx3 and xx22 and xx33 and x222 and x333
Look at the pairs of lines such as xxx2 and 333x
one with moving coordinates in three positions and
a fixed coordinate equal to 2 or 3 say 2
the other with fixed coordinates equal to the other
value which in this case is 3.

Then we must have one of the points 2222
1112 3332 removed to block the first line of the pair
and for the second line we can use 3333
3332 3331. However we do not have the points
2222 or 3333 removed in this case so we must have
either 3332 or the pair 1112 or 3331.
For every one of the eight points 3332 or 2223
we will have a similar choice forcing either
the removal of the point itself or the associated
pair. After these choices have been made more points
of the form aaab can be added but there must be
a subset corresponding to one set of the above eight choices
since in each case there are only two ways to cover the lines noted.
Look at the pairs of lines such as 22xx and xx33
one with moving coordinates in two positions and
a two fixed coordinates equal to 2 or 3 say 2
the other with two fixed coordinates equal to the other
value which in this case is 2 so if the fixed coordinate(s)
in one point of the pair is 2 in the other they or it will
Then we must have one of the points 2211
2222 2233 removed to block the first line of the pair
and for the second line we can use 3333
2233 1133. However we do not have the points
2222 or 3333 removed in this case so we must have
either 2233 or the pair 1133 or 2211.
For every one of the six points with two threes and two twos
we will have a similar choice forcing either
the removal of the point itself or the associated
pair. After these choices have been made more points
of the form aabb can be added but there must be
a subset corresponding to one set of the above six choices

If we start with the configuration 1111 removed all eight points with three 2’s and one three and three 3’s and one two removed and all points with two 3’s and two 2’s removed and all points of the form aabc removed then this configuration has weight 8
then we can perform a series of steps in order which will
reach all combinatorial line free configurations.
These steps are as follows:

1 Making choices as above for elements of the form aaab and allowing the addition
of all possible aabc’ss.

2 Making choices as above for elements of the form aabb and allowing the addition
of all possible aabc’ss.

3.Removal of points of the form aabb or aaab and addition of all possible aabc’s.

4.Removal of aabc’s.

At present none of the aabc can be added
there are lines of the form xx12 and xx13 and x113 and x112
which each have to blocked to allow their addition

What we are going to do is perform the previous steps in order.
we will show that each step eliminates twice as much in weight
of elements of the form aabc as it adds of all other forms. To facilitate the proof
we will have to perform the operations in the order listed. However we will
be able to reach every possible configuration. We must have a subconfiguration
corresponding to one set of choices above then we can delete various elements
of the form aabb and aaab to get all possible line free sets of the elements of
the form aabb and aaab and then for each set we add the maximum possible number
of elements of the form aabc.

The point is doing this is that we can only add two units in weight
of the form aabc as the lines of the form xabc must be covered and they
Can only be covered by one unit in weight of elements of the form abc
So if we have the two to one ratio or better and have to stop at two we will
End up with a net change of 2-1 which will raise the weight to 9 or less
And we still have the maximum weight of is 9.

When we make a choice deleting a pair and adding say
2223 which will give 1113 and 2221 we block three lines
of the form xx13 and three of the form xx12 thus allowing
the addition of 6 points of weight 1/12 which give a total
change of weight 1/2 which is exactly twice the net change in
weight caused by the addition of 2223 and the removal of 1113
of 2221

Now with each substitution there will also be the blocking of lines
of the form x113 or x112 however to allow the point say 2113
To be added we must block both x113 and 211x and to do this
We must make choices adding both 2223 and 2333 which unblocks
The line 2xx1 and forbids the addition of the point 2113 thus the increase in
material of the form aabc is twice the net change in weight of the other types

1122 can block the 11×2 two at a time but their
weight is 1/6 so even if they block two of the 11×2
and allow the addition of two 1132’s the weight will
remain the same and since each replacement of 2233
by 1133 and 2211 has only one element of the form
2211 we are done with step one.

For the choices of elements
of the form aabb if we replace an element of the form
2223 by 1113 and 2221 we will be able to block three lines
of the form x113 which gets rid of 3 elements of the form
2113 but the weight of the addional aaab element created is 1/4 and the weight of the removed elements is the same. So step
two can not improve the weight. So we are done with the choices mentioned above and move on two steps 3 and 4 deleting individual elements.

If we add an element of the form 2233 and delete 1133 and 2211 then it can unblock two lines of the form x113 and two of the form x112 thus allowing the addition of at most 4 points of the form
3112 thus giving a net change of -1/4 +4/12 and again the ratio is 2 to one.

Then after all the above choices have been made we can delete elements of the form 2223 which will block at most three lines
Of the form 2xx3 if created by the above choices
And the ratio of points added to points deleted is at most one
And so is less than 1/2 and we are done. The case 3332
is handled the same way.

If we delete an element of the form 1112 we unblock three lines
Of the form xx12 and three of x112 we free at most 6 points with
Weight 1/12 giving a total weight of 1/2 the point removed is weight 1/4 so the ratio is 2 to 1 and we are done the case of
1113 is similar.

If we delete an element of the form 3331 it can unblock three lines
of the form xx31 and we free three points for possible addition
The have total weight equal to the weight of 3331 so the ratio is
less than 2 to 1. The case of an element of the form 2221 is similar.

If we delete a point of the form 2233
We don’t unblock any lines so we can’t
Add any points of the form aabc.

If we delete a point of the form 1133 we unblock two lines
Of the form xx13 and two of x113 and so can add four points
With weight 1/12 which has total 1/3 which is twice the weight
Of the point 1133 so the ratio is less than or equal to 2 and we are
Done. The case of deleting a point of the form 1122 is handled similarly.
So we are done with step three.

If we delete a point of the form aabc the weight is less. So we have gone through all steps and the ratio in them 2 or less and thus in this case the weight is 9 or less and we are done. Since this is the final case we have proved the theorem and the weight is 9.

21 March, 2009 at 11:48 am

Kristal Cantwell

1133. c^{\mu}_4=9

This is the final case of the partial proof in 1129. It is divided
into two parts. Here is part one:

1 Making choices as above for elements of the form aaab and allowing the addition
of all possible aabc’ss.

2 Making choices as above for elements of the form aabb and allowing the addition
of all possible aabc’ss.

3.Removal of points of the form aabb or aaab and addition of all possible aabc’s.

4.Removal of aabc’s.

21 March, 2009 at 11:50 am

Kristal Cantwell

1134. c^{\mu}_4=9

Part 2 continued form 1133:

At present none of the aabc can be added
there are lines of the form xx12 and xx13 and x113 and x112
which each have to blocked to allow their addition

Now with each substitution there will also be the blocking of lines
of the form x113 or x112 however to allow the point say 2113
To be added we must block both x113 and 211x and to do this
We must make choices adding both 2223 and 2333 which unblocks
The line 2xx1 and forbids the addition of the point 2113 thus the increase in
Material of the form aabc is twice the net change in weight of the other types

If we delete a point of the form 2233
We don’t unblock any lines so we can’t
Add any points of the form aabc.

23 March, 2009 at 5:27 am

23 March, 2009 at 9:25 am

1135. Other values of k
I have been busy the last few days, with both work and more everyday things like having a cold, but I decided to let the computers to do some new work by expandingto new values of k.

Here
http://abel.math.umu.se/~klasm/Data/HJ/
is a table with the optimum sizes for subsets of [k]^n without combinatorial lines, and the optimal solutions for some cases. (Anyone who can edit the wiki is welcome to add it there)

One natural question here is; For which values of n and k is the optimum size (k-1)k^n ?

Kareem, maybe your program can improve the lower bounds for the values my program could not determine?

Kristal Cantwell

1136. c^{\mu}_4=9

Sorry about the duplication I put the proof for the final case in and it did not go through then I split it in half and it went through later the original finally went through. I have put the cases 3 and 4 in the wiki at

http://michaelnielsen.org/polymath1/index.php?title=Hyper-optimistic_conjecture

23 March, 2009 at 7:07 pm

23 March, 2009 at 11:07 pm

1137. Dimension 2, any k

Regarding the data in Markström.1135, it is simple to show when restricting to dimension two the maximal set size has to be k(k-1). This can be done by removing the diagonal values 11, 22, 33, …, kk. Since they are in disjoint lines this removal is minimal.

Michael Peake

1138. Dimension 2, any k

The k missing points are one per line and one per column.
So their y-coordinates are a shuffle of their x-coordinates.
There are k! rearrangements of the numbers 1 to k.
The k points include a point on the diagonal, so this shuffle is not a derangement. There are k!/e derangements of the numbers 1 to k, so k!(1-1/e) optimal solutions

24 March, 2009 at 1:03 am

24 March, 2009 at 5:26 am

1139. Dimension 3, k at least 3
Let S be a latin square of side k on the symbols 1…k, with colour i in position (i,i) ( This is not possible for k=2 )

Let axis one in S correspond to coordinate 1 in [k]^3, axis two to coordinate 2 and interpret the colour in position (i,j) as the third coordinate. Delete the points so defined.

The line with three wild cards has now been removed.
A line with two wildcards will be missing the point corresponding to the diagonal in S.
A line with a single wildcard will be missing a point corresponding to an off diagonal point in S.

Something similar should work in higher dimensions if one can find latin cubes etc with the right diagonal properties.

Michael Peake

1140. $k \ge d$ , k prime

Delete those points whose coordinates add up to a multiple of k.
Every combinatorial line has one point deleted, except for the major diagonal of d=k, which has all points deleted.

24 March, 2009 at 8:34 am

Kristal Cantwell

1141. Values near primes

Could we extend 1140 to values near primes with only a slight loss? For instance for 100 we delete all values equal to zero mod 101 and 1 mod 101 then all combinatorial lines with d less than 101 will have 100 different values mod 101 and hence will have one deleted value. So we will have a line free set for d equal to 101 or less with density 99/101 or more.

24 March, 2009 at 8:51 am

Kristal Cantwell

1142. All values

I am looking for a further extension of 1141 according to

R. C. Baker and G. Harman, “The difference between consecutive primes,” Proc. Lond. Math. Soc., series 3, 72 (1996) 261–280. MR 96k:11111

Abstract: The main result of the paper is that for all large x, the interval A=[x-x^0.535,x] contains prime numbers.

This is from the abstract at

http://primes.utm.edu/references/refs.cgi?long=BH96

I found it using:

http://primes.utm.edu/notes/gaps.html

So for any number n there is a nearby prime p whose difference from
n is x^.535 so then we remove x^.535 +1 values mod p and for those values the density will be (p-x^.535-1)/p
of d less than p we will have no combinatorial lines.

24 March, 2009 at 9:12 am

Kristal Cantwell

1142. lower bounds on line free sets

I think the results of 1141 can be used to get lower bounds on lines free sets for large n for all values of k. For any k and any n we can find a prime prelatively close to k^n then we remove the first k+1 values mod p then we pick a value then we remove the must k+1 so we only have k+2, 2k+3, etch
the idea is to prevent any two values on a line because two points on a combinatorial line increase by at most k. This has density 1/k so we have
a line free density of 1/(k+1).

24 March, 2009 at 9:34 am

Kristal Cantwell

1143. I think the bound in 1142 could possibly be improved. First by getting most of the set concentrated around the point with equal numbers of ones twos and threes or the point with values closes to equality the standard deviation should be something like the square root of n. Then we could apply the near prime with sets c(k^.5 + 1) and get a density of roughly c/k^.5
which I think will be better than the Behrend-Elkin construction as e^-x will eventually be less than 1/x as x increases without limit and the square root of k will increase without limit.

24 March, 2009 at 2:09 pm

24 March, 2009 at 3:36 pm

Just a quick note to say that I’m traveling at present and have not been able to reply to all the interesting progress made in the last week or so, but it looks like the project is humming along nicely without my assistance anyway! I’ll try to say something more constructive when I return next week.

Kevin O'Bryant

1144. Implication of Behrend/Elkin for $c_n^{\mu}$ .

If $n$ is sufficiently large, then $c_n^\mu > n^2 2^{-4\sqrt{2}\sqrt{\log n}+1/2 \log \log n -2}$ , where the $log$ ‘s are base 2.

I’ve posted the details to the wiki under “Hyper-optimistic conjecture” (http://michaelnielsen.org/polymath1/index.php?title=Hyper-optimistic_conjecture).

24 March, 2009 at 3:39 pm

Kevin O'Bryant

1145. Gaps between primes

If I recall correctly, then the Riemann hypothesis implies that there is always a prime between $n$ and $n^{1/2+\epsilon}$ (provided of course that $n$ is large enough, while the truth is believed to be that there is a prime between $n$ and $n + C (\log n)^2$ , and some people have guessed $C=1$ .

24 March, 2009 at 4:23 pm

Anonymous

1146. Hyper-optimistic conjecture extended beyond 3

If the Hyper-optimistic conjecture is extended to 4, 5 etc I can prove it for some specific values.

Specifically I think I can prove it Hyper-optimistic conjecture for all the values k greater than d where k is prime as in 1140, the key is every incidence is exactly one and every incidence is of minimum weight on the lines consisting of x repeated d times x followed by d-1 a’s not divisible by the prime k, x followed by d-2 a’s not divisible by the prime k etc these lines will have to be blocked somehow and this can only be done at greater or equal cost. So for the extension of this conjecture beyond 3 we have that it holds true for primes p for values less than or equal to p.

24 March, 2009 at 4:25 pm

Kristal Cantwell

1147. Hyper-optimistic conjecture extended beyond 3

The previous anonymous comment was by me, I forgot to include my information.

24 March, 2009 at 7:23 pm

Kristal Cantwell

1148. Extending Hyper-optimistic conjecture

To extend this conjecture we need to define a weight beyond 3
we do this by letting the weight of a point with a ones b twos c threes
and d fours to be a!b!c!d!/a+b+c+d! Similarly we can add e for 5 f for6
the general pattern should be clear.
We also need to extend slices thus in the case of k=4 we add a d which is the number of 4’s in the slice similarly we add an e in the case of k=5. The extension of the conjecture would that the maximal weight is realized by a set of slices.

24 March, 2009 at 7:38 pm

24 March, 2009 at 7:47 pm

1149.

Klas,

I will look into it. I did not have much time last week but things are opening up now.

Kareem

Kristal Cantwell

1148. Extending Hyper-optimistic conjecture

I am going to try to prove part of the result I tried to prove in 1146, there is at least one mistake.

I want to prove that if p is a prime and d is a dimension less than p and the Hyper-optimistic conjecture is extended as in 1148 for p then for the specific values of d
less than p the Hyper-optimistic conjecture is true.

To try to prove this try we remove all points whose sum is divisible by p, then since permuting the coordinates will not change the sum this is a set of slices we only need to prove it is minimal in weight and it covers all combinatorial lines. So I have it is a set of slices.

It covers all combinatorial lines because the line since d is less than p must increase by a number less than p hence all values modulo p will be realized including p and we are done. So I have it covers all combinatorial lines.

I still need to prove the weight is minimal though to get the result I want.
I thought I could do this in 1146 but what I wrote did not work.

24 March, 2009 at 11:50 pm

25 March, 2009 at 7:06 am

1149. Gaps between primes.

There is a later improvement of the gap result.

Baker, R. C.(1-BYU); Harman, G.(4-LNDHB); Pintz, J.(H-AOS)
The difference between consecutive primes. II.
Proc. London Math. Soc. (3) 83 (2001), no. 3, 532–562.

Here they find a prime in [x-x^{0.525},x]

25 March, 2009 at 11:57 am

1150. Dimension 2, any k

The number of optimal solutions is this sequence.

26 March, 2009 at 12:56 pm

1151. Bounds on c_n from Fujmura.

Has anyone calculated which lower bounds for c_n we get from the optimal solutions to Fujimura’s problem I constructed a while ago?

Kristal Cantwell

1152. Bounds on c_n from Fujmura.

I have gone back to the posts 923 through 927 where you gave some of these solutions. I didn’t find any improvement to our current bounds. I think to go over some of these solutions the process will have to be automated since there are a lot of solutions in some cases. Possibly we might be able to improve some of the bounds at higher levels by going through all the cases.

26 March, 2009 at 1:09 pm

26 March, 2009 at 1:14 pm

1153. Bounds on c_n from Fujmura.

Yes for the smaller n we might actually already have the optimal values, but for higher n we could possibly get better bounds than we get from the bounds for general n.

Does anyone want to volunteer to automate this?

I can probably find the full set of optimal solutions to Fujimura’s problem for a few more values of n too.

26 March, 2009 at 4:42 pm

1154.

Do we have any “hand made” values for small n for the quadruple version of Fujimura’s problem Kristal suggested?

26 March, 2009 at 4:44 pm

1156. Higher-dimensional Fujimura

for k=4:

When n=2, the largest triangle-free set is trivially 2 (remove for example 1000 and 0100).

When n=3, the largest triangle-free set is 6 (remove 0200, 1010, 1001, 0011). Proof: One of 2000, 0200, 0020 must be removed — say it is 0200, and note by symmetry the logic that follows will apply if 2000 or 0020 is removed. There are three disjoint triangles (1010-0110-0020, 2000-1100-1001, 0002-0101-0011) which must all have at least one removal, so the minimal number of removals is 4, so we have proven our solution to be optimal.

26 March, 2009 at 4:49 pm

1157. Higher-dimensional Fujimura

Oops, my n=3 is wrong. Higher dimensions are tricky: I left 2000-0020-0002 open. Let me fiddle and come back.

26 March, 2009 at 7:43 pm

1158. Higher-dimensional Fujimura

Do over!

When n=3, the largest triangle-free set is 6 (remove 2000, 0200, 0020, 0002). Proof: One of 2000, 0200, 0020 must be removed — say it is 0200, and note by symmetry the logic that follows will apply if 2000 or 0020 is removed. There are three disjoint triangles (1010-0110-0020, 2000-1100-1001, 0002-0101-0011) which must all have at least one removal, so the minimal number of removals is 4, so we have proven our solution to be optimal.

Note this not only leaves “upside down” triangles but “lateral” triangles like 1100-1010-0010, but none seem to form a combinatoric line.

26 March, 2009 at 8:12 pm

1159. Higher-dimensional Fujimura

My n are one off from our convention, I of course mean:

When k=4 and n=1, the largest triangle-free set is 2.
When k=4 and n=2, the largest triangle-free set is 6.

I believe that when k=4 and n=3, the largest triangle free set is 12, but I do not have a proof yet.

The lower bound is 6(n-1), using the exact same pattern on each face of the tetrahedron as general n bound with the k=3 case.

We also need a symbol to represent the problem. It’s tempting to use $\overline{\overline{c}}^\mu_n$ for k=4 but we might be working with larger k (making the stack rather large).

Michael Peake

1160. Lower bounds on line-free sets

There are $k^{n-1}$ disjoint lines *abcd..m, so the density of removed points must be at least 1/k, and retained points at most (k-1)/k.
If $n \le p \le k$ then one can get a density of (p-1)/p by deleting points whose coordinates sum to a multiple of p.
The lower bound (p-1)/p approaches (k-1)/k as $k\rightarrow \infty$ .

26 March, 2009 at 9:05 pm

26 March, 2009 at 10:59 pm

1161. Tetrahedron geometry

In the k = 3 case of Fujimura things get tricky when n >= 3 because the internal points in the tetrahedral lattice must be considered. I believe my early lower bound was too hasty.

26 March, 2009 at 11:09 pm

1162. k=4 Fujimura

Now I see where my problem has been, we need the tetrahedron-free set to match combinatoric lines, not the triangle-free set.

So n=1 would just be one removal and a set size of 3.
and n=2 would be two removals (say, 1100 and 0002) and a set size of 8.

26 March, 2009 at 11:11 pm

1162. Higher-dimensional Fujimura

Jason, are you considering triangles or squares? I’m just wondering if you are looking at the problem Kristal posted at Tim’s blog or a different version?

27 March, 2009 at 11:50 am

It seems you answered my question while I was writing it.

27 March, 2009 at 12:27 pm

1163. Fixing k=4 Fujimura

Just in case I make any more mistakes I will putting current progress for now on the talk page of the Wiki.

The current values I have now (barring any further mistakes *cough*) are:

n = 0, largest set of 1
n = 1, largest set of 3
n = 2, largest set of 7

I’m using $\overline{\overline{c}}^\mu_n$ for now (until we decide on a better notation).

Kristal Cantwell

1164. HJ(3,3) is greater than 7

For a fixed r and k, the least n needed for the Hales-Jewett theorem to apply is denoted HJ(k,r).
See http://michaelnielsen.org/polymath1/index.php?title=Coloring_Hales-Jewett_theorem
Currently we have:

HJ(3,1) = 1
HJ(3,2) = 4
HJ(3,3) > 6

We start with the set formed by removing (0,1,6), (1,0,6), (0,5,2), (5,0,2) , (1,5,1), (5,1,1),(1,6,0), (6,1,0) from D_7.
Note that none of (0,1,6), (1,0,6), (0,5,2), (5,0,2) , (1,5,1), (5,1,1),(1,6,0), (6,1,0)contains a point whose coordinate sum is divisible by three we give it color 1
where (a,b,c) is shorthand for the slice Γ_a,b,c.
It is combinatorial line free from the n=7 section of the upper and lower bounds wiki at
http://michaelnielsen.org/polymath1/index.php?title=Upper_and_lower_bounds#n.3D7

then we divide the remaining points into all points whose coordinate sum is not equal to 0 mod 9 and
all points of (0,1,6), (1,0,6), (0,5,2), (5,0,2) , (1,5,1), (5,1,1),(1,6,0), (6,1,0)whose coordinate sum is equal to 1 mod 3 We give these color 2

then we take all points of (0,1,6), (1,0,6), (0,5,2), (5,0,2) , (1,5,1), (5,1,1),(1,6,0), (6,1,0)whose coordinate sum equal to 2 mod 3 and those points
whose sum is equal to 0 mod 9. We give these color 3.

Then with this coloring there are nor monochromatic lines. If there are any monochromatic
Lines with number of moving coordinates not divisible by three in color 2 they must contain point whose coordinate sum is equal to 2 mod three
But there are no such points with color 2. If there are any monochromatic lines whose coordinate sum is divisible by three
Than they must contain points whose coordinate sum is 0 mod 9 but there are no such points with color 2. So there
Are no monochromatic combinatorial lines with color 2.

If there are any monochromatic
Lines with number of moving coordinates not divisible by three in color 3 they must contain point whose coordinate sum is equal to 1 mod three
But there are no such points with color 3. If there are any monochromatic lines whose coordinate sum is divisible by three
Than they must contain points whose coordinate sum is not 0 mod 9 but there are no such points with color 3.

As already noted color 1 is combinatorial line free and we are done.

27 March, 2009 at 12:32 pm

Kristal Cantwell

1165. Bounds on c_n from Fujmura.

I have been looking at the upper bounds that we have and I think some of them come from lower bounds from Fujimura problem so I think that improvements to this problem could give better bounds.

28 March, 2009 at 1:35 am

28 March, 2009 at 5:36 am

1166. Higher-dimensional Fujimura

Jason, how about using $\bar{c}^{\mu}_{n,k}$ where k is the size of the tuples, or the dimension of the Z^k used?
The original Fujimura problem would correpspond to $\bar{c}^{\mu}_{n,3}$ and the quadruple version to $\bar{c}^{\mu}_{n,4}$

You get a non-constructive quadratic lower bound for the quadruple problem by taking a random subset of size $c n^2$ . If c is not too large the linearity of expectation shows that the expected number of tetrahedrons in such a set is less than one, and so there must be a set of that size with no tetrahedrons.

28 March, 2009 at 10:08 am

1167. $\overline{c}^\mu_{n,4}$

Klas, I have adopted your notation and added your non-constructive bound to the talk page.

Should this be merged into the regular page or should we be making a separate one for the k > 3 cases?

Michael Peake

1168. $\overline{c}^\mu_{n,4}$

if the coordinates of points (a,b,c,d), then a+2b+3c is a four-term arithmetic progression for any of these tetrahedrons.
We include slices a+2b+3c = constant.
http://arxiv.org/PS_cache/arxiv/pdf/0811/0811.3057v2.pdf this paper shows that the proportion of slices included can be at least
$C\frac{(log N)^{1/4}}{2^{2\sqrt{2 log N}}}$ for some constant C.

28 March, 2009 at 10:54 am

28 March, 2009 at 12:56 pm

1169. $\overline{c}^{\mu}_{n,k}$

Michael, this should give a lower bound for general k as well.
Likewise the counting argument gives an upper bound for general k too.

It is also possible to use a triangle-free set to build a tetrahedron-free set for a larger value of n, but I’m not sure how efficient such constructions can be made.

Kristal Cantwell

1170. $\overline{c}^{\mu}_{n,k}$

In general for $\overline{c}^{\mu}_{n,k}$ the series a + 2b + 3c+…
continued to k-1 terms will be a k-term arithmetic progression for
the points of any configuration (a+r, b,..), (a,b+r .. which is the generalization
of an upward triangle, an upward k-1 dimensional simplex. So as in 1160
for the case k=4
we can get a formula in this case the general formula from the paper
http://arxiv.org/PS_cache/arxiv/pdf/0811/0811.3057v2.pdf
and we get if k is greater than 2^n +1
$C\frac{\sqrt[2n]{log N}}{2^{n2^{(n-1)/2}\sqrt[2n]{log N}}}$
This is actually a set of formulas as n will have to be chosen given k
it is the greatest integer less than log base 2 of k-1.

29 March, 2009 at 10:53 am

Kristal Cantwell

1171. 4D Moser

If a Moser set has 4 points with 3 2’s and its size is 41
or more then it must not have two sets of two points with three twos with
the same c statistic.

To prove this assume that it is true then we must have two
points without lost of generality of the form x222 then
one must have one in the first position the other must
have 3 we can then cut at the first coordinate and get
the side slices must have 13 or less points which means
that the center slice must have 15 or more points and
the remaining two points of the form say 2×22 are in the
center cube so we can slice and the side squares have
The center spot occupied that means that total number
of points in the center cube with one coordinate equal
to 2 in the cube and two in the configuration must be
At most 8 two each from the side squares since the center
spot is occupied and possibly all 4 from the center square.

Then form the Pareto optimal statistics in section n=3
of the Moser wiki
and the fact the center cube has 15 points and has c=2
we have the statistics of the center
slice must be (4,9,2,0) but from the above we have
At most 8 points with one coordinate equal to 2 so we are done.

29 March, 2009 at 2:22 pm

29 March, 2009 at 2:30 pm

1172. $c_{n,k}$

I suppose it is reasonable to call $c_{n,k}$ the size of the largest line-free subset of $[k]^n$ . Thus $c_n = c_{n,3}$ .

Sperner’s theorem tells us that $c_{n,2} = \binom{n}{\lfloor n/2\rfloor}$ . We have $c_{n,1}=0$ so let’s forget about the k=1 case.

Dyer.1137, Markstrom.1139 show that $c_{n,k} = (k-1) k^{n-1}$ for n=1,2,3 (one needs k at least 3 when n=3), while Peake.1140 shows that this is also the case for n up to k if k is prime. Kristal has various modifications of this in the non-prime case.

Here is a naive conjecture: the above are the only values of (n,k) for which one has $c_{n,k} = (k-1) k^{n-1}$ (i.e. exactly one point deleted from each row or column), thus if n is at least 4 and k is composite then $c_{n,k}$ has to be strictly less than $(k-1) k^{n-1}$ . Actually it suffices to check this claim for n=4 since $c_{n+1,k} \leq k c_{n,k}$ .

Klas’s tables at http://abel.math.umu.se/~klasm/Data/HJ/ indeed show that $c_{4,k} < (k-1) k^3$ for k=4,6.

When k=3 we obtained this inequality by exploiting the fact that there was a unique 3D line-free set with $(k-1) k^2$ points. Unfortunately, as Klas’s tables show, this is no longer the case in higher D, but perhaps we can still understand the 3D extremisers well enough to settle this conjecture (e.g. do they all correspond to Latin squares as in Markstrom.1139?)

29 March, 2009 at 3:53 pm

1173. HJ(k,r)

Kristal, that’s a nice lower bound construction for HJ(3,3), which is better than the existing bound in the literature; I put it on the wiki. One may hope to get some better asymptotic bounds for HJ(n,k) too, by leveraging Behrend sets or something. There is a way to use the Behrend construction to colour [n] with relatively few colours in such a way that there are no monochromatic arithmetic progressions, which should then lift to HJ by the same sorts of methods as in, say, 1170. There should also be some existing lower bounds on HJ(n,k) in the literature, though I don’t have them on hand right now…

29 March, 2009 at 4:17 pm

1174. $c_{n,k}$

In between baby holdings, so I don’t have time to check the lemma on this, but:

For proving the n=4 case you cite for all k, wouldn’t it suffice to form some sort of controlled exchange between coordinate positions such that the number of combinatorial lines is never increased? Therefore any configuration hopeful of finding $c_{4,k} = (k-1)k^3$ can be shuffled to the diagonal, which is clearly not a line-free set?

Kristal Cantwell

1175. HJ(k,r)

I found this pre-print:

http://www.math.ucsd.edu/~etressle/hj32.pdf

29 March, 2009 at 4:29 pm

29 March, 2009 at 4:58 pm

1176. $c_{n,k}$

Wait, can’t we just immediately shift all the points to the diagonal and claim that for each point the number of intersecting combinatorial lines has to either stay the same or increase? The maximal intersections are clearly where you have a maximal number of possible wildcards, that is, the largest number of identical coordinates that can be substituted by the * wildcard. Shifting everything immediately to the diagonal does not necessarily cause an increase of intersections in a particular point (since now the blocking of the diagonal is duplicated in every point) but it can’t cause a decrease, either, since the highest possible duplication for each point is 1 line.

Kristal Cantwell

1175. k=4 Fujimura

I think this is 12. Taking all slices for which a +2b+3b is one of three different values mod 5 gives this as any arithmetic progression a +kr in this set must have r less than 4, so the four values in the arithmetic progression will have four different values mod 5 so this set of slices will not contain any tetrahedrons and 3/5 of 20 is 12 so we have 12 works.

29 March, 2009 at 6:01 pm

29 March, 2009 at 6:47 pm

Metacomment.

I have made a new page for higher-dimensional Fujimura and moved the content from the talk page (although not deleted it yet).

Kristal Cantwell

1177. k=4 Fujimura

I think this is 12 for k=4, n=3. I didn’t give the value of n in the previous post.

29 March, 2009 at 7:49 pm

Kristal Cantwell

1178. HJ(p,2)

Let p be prime then HJ(p,2) is greater than p-1.
We take p-1 values mod p and let them be one color
and let the remaining value take the other color, then
each combinatorial line with less than p moving coordinates
will run through all values mod p and hence will not be monochromatic
so we are done.

29 March, 2009 at 7:55 pm

Kristal Cantwell

1179. HJ(n,2)

From post 1149 we get this reference
Baker, R. C.(1-BYU); Harman, G.(4-LNDHB); Pintz, J.(H-AOS)
The difference between consecutive primes. II.
Proc. London Math. Soc. (3) 83 (2001), no. 3, 532–562.

Here they find a prime in [x-x^{0.525},x]
so HJ(n,2) will be greater than n-n^.525-1 as we can find a prime and
use the above argument namely take p-1 values of the prime in color
and the remaining value in a second color and as long as the number
of moving coordinates in the combinatorial line is less than p all values
will be realized mod p and we will have the combinatorial line not monochromatic.

29 March, 2009 at 8:15 pm

Kristal Cantwell

1180. HJ(n,2)

HJ(n,2) is greater than 2n-(2n)^{0.525}.

We can find a prime less than 2n greater than 2n-(2n)^{0.525}
as in the previous post
then we divide the classes modulo this prime into two nearly equal classes
there may be a disparity of one between them both classes will have
cardinality less than n we give color 1 to one class and two to the other, the combinatorial lines smaller than or equal to 2n-(2n)^{0.525}
will realize different values modulo that prime for each point there are n points in a combinatorial line so we must have members of both classes and we are done.

29 March, 2009 at 8:21 pm

Kristal Cantwell

1181. HJ(n,m)

HJ(n,m) is greater than mn-(mn)^{0.525}

We can find a prime less than mn greater than mn-(mn)^{0.525}
as in 1179
then we divide the classes modulo this prime into m nearly equal classes
there may be a disparity of one between them All classes will have
cardinality less than n we give one color to each class, the combinatorial lines smaller than or equal to mn-(mn)^{0.525}
will realize different values modulo that prime for each point, there are n points in a combinatorial line so we must have members of more than one class and we are done.

29 March, 2009 at 10:08 pm

Kristal Cantwell

1182. $c_{n,k} = (k-1) k^{n-1}$

For n= 35 $c_{35,4} = 34 \times 35^{3}$
To see this select one value modulo 35 and eliminate it.
Combinatorial lines with one, two, three or four moving coordinates will
realize all values modulo 35 as one, two, three, or four are units modulo 35.
This generalizes in the following way:
$c_{n,k} = (k-1) k^{n-1}$
if k is less than all divisors of n.

29 March, 2009 at 10:10 pm

Kristal Cantwell

1183. $c_{n,k} = (k-1) k^{n-1}$

That should be for n= 35 c_{35,4} = 34*35^{3} [Corrected – T.]

29 March, 2009 at 10:39 pm

30 March, 2009 at 1:03 am

1182. Fujimura k=4

I’ve had my program running during the weekend and it reports the following values for Fujimura’s problem with k=4

d=2 size 7
d=3 size 14
d=4 size 24
d=5 size 37
d=6 size 55
Right now it has a lower bound of 78 for d=7

I’ll update my table page and put the solutions there too.

Jason, congratulations on your baby!

30 March, 2009 at 4:01 am

1185. HOC k=4

Unless I have messed something up this is a line free set with weight 7.5 in the n=2, k=4 version of the HOC

{{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 3}, {2, 4}, {3, 2}, {3, 3}, {3,
4}, {4, 1}, {4, 2}, {4, 4}}

1186 HOC: $c_{n,k} \ge \bar{c}_{n,k}$

I agree with 1185. One can still considers the alternate HOC. In the
original $k=3$ case, let $\bar{c}_n$ be the maximal
weighted triangle-free subset of $\Delta_{n}$ with $(a,b,c)$ weighted by $n!/(a!b!c!)$ . Then we have $c_n \ge \bar{c}_n$ and equality holds for $n \le 6$ (when $c_n$ is known). The more natural HOC is perhaps $c_n=\bar{c}_n$ i.e. the optimal line free sets are union of slices
(both sides are integers now). For $k=4$ , by 1182,1185 we have
$c^\mu_{2,4}=7.5> \bar{c}^\mu_{2,4}=7$ but we still have
$c_{2,4}=\bar{c}_{2,4}=12$ by Klas’s example in 1185 and
Jason’s example $\Delta_n-\{0002,0020,1100\}$ .

30 March, 2009 at 4:23 am

http://michaelnielsen.org/polymath1/index.php?title=Higher-dimensional_DHJ_numbers

1187. $c_{n,k}$

Well, so much for the naive conjecture… but it does make me curious now to figure out exactly what pairs of n,k admit “saturated” configurations, i.e. line-free sets of size $(k-1) k^n$ . Right now the set of such “saturated” pairs includes

* (n,1) for all n [this is trivial]
* (1,k) for all k >= 1
* (2,k) for all k >= 1
* (3,k) for all k >= 3
* (n,k) whenever n is less than all divisors of k [note there is a notational mismatch in 1182]
* not (4,4) or (4,6)

So I guess the first unknown cases are (4,8) and then (4,9).

I’ve moved the higher-d DHJ numbers data to their own page on the wiki at

it could still do with some editing.

30 March, 2009 at 5:56 am

Michael Peake

1188. Regarding $c_{4,k}$

I split the $k^4$ points into five sorts of points: xyzw, xxyz, xxyy, xxxy and xxxx, where different letters represent different digits.

Then there are seven sorts of lines: *xyz, *xxy,*xxx, **xy, **xx, ***x, ****.

Linear inequalities connect the number of each type of point to each type of line. For example, each xxyz point covers two *xyz lines, two *xxy lines and one **xy line. The maximum number of *xyz lines removed is 4*number of xyzw points + 2*number of xxyz points.

If there is a solution with $k^3$ missing points, there must be
*(k-1)(k-2)(k-3) missing xyzw points
*6(k-1)(k-2) missing xxyz points
*3(k-1) missing xxyy points
*4(k-1) missing xxxy points
*1 missing xxxx point.

30 March, 2009 at 7:25 am

Michael Peake

1189. Regarding $c_{4,k}$

There is another possible solution to the linear inequalities
* k(k-1)(k-5) missing xyzw points
* 6k(k-1) missing xxyz points
* k missing xxxx points

and probably other solutions with values intermediate between this post and the previous post. The difference between the new and old solutions is
* 6(k-1) fewer xyzw points
* 12(k-1) extra xxyz points
* 3(k-1) fewer xxyy points
* 4(k-1) fewer xxxy points
* k-1 extra xxxx points

which hints at k different solutions altogether.

30 March, 2009 at 10:49 am

Kristal Cantwell

1190. H(4,2) is greater than 11

We take the slices of the eleven dimensional hypercube
of side four in the following way:
We start with the Van der Warden number W(4,2) for which
we have an exact value:
W(4,2) =35
from the Ramsey theory book by Graham Rothschild and Spencer
second addition
We give the slice (a,b,c,d) the color associated
with a + 2b + 3b+1 then the maximum value is 34
We add one because the coloring in W(4,2) starts with one
and we have zero values in our slices.
Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
tetrahedron (a+r,b,c,d) (a,b+r,c,d) etc. so we are done.
This is an improvement in the old value of HJ(4,2) is greater than 6.

30 March, 2009 at 10:55 am

Kristal Cantwell

1191. H(3,3) is greater than 13

We take the slices of the eleven dimensional hypercube
of side four in the following way:
We start with the Van der Warden number W(3,3) for which
we have an exact value:
W(3,3) =27
same source as 1190
We give the slice (a,b,c,) the color associated
with a + 2b +1 then the maximum value is 27
We add one because the coloring in W(3,3) starts with one
and we have zero values in our slices.
Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
triangle and a monochromatic upward triangle would lead to
an arithmetic progression of lenght three but we have forbidden such a progression by our choice of coloring so we are done.
This is an improvement in the old value of HJ(3,3) is my value of 7 before that there was a computer generated value of 6 in the paper I cited in 1175.

30 March, 2009 at 10:59 am

Kristal Cantwell

1192. H(4,2) is greater than 11 redo

I am redoing this because I omitted part of the proof:
We take the slices of the eleven dimensional hypercube
of side four in the following way:
We start with the Van der Warden number W(4,2) for which
we have an exact value:
W(4,2) =35
from the Ramsey theory book by Graham Rothschild and Spencer
second addition
We give the slice (a,b,c,d) the color associated
with a + 2b + 3b+1 then the maximum value is 34
We add one because the coloring in W(4,2) starts with one
and we have zero values in our slices.
Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
tetrahedron (a+r,b,c,d) (a,b+r,c,d) etc. and a monochromatic upward tetrahedron would lead to
an arithmetic progression of length four but we have forbidden such a progression by our choice of coloring so we are done.
This is an improvement in the old value of HJ(4,2) is greater than 6.

30 March, 2009 at 11:04 am

Kristal Cantwell

1193. H(5,2) is greater than 59

We color the slices of the 59 dimensional hypercube
of side four in the following way:
We start with the Van der Warden number W(5,2) for which
we have an exact value:
W(5,2) =178
from the Ramsey theory book by Graham Rothschild and Spencer
second addition
We give the slice (a,b,c,d) the color associated
with a + 2b + 3b+1 then the maximum value is 178
We add one because the coloring in W(5,2) starts with one
and we have zero values in our slices.
Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
tetrahedron (a+r,b,c,d) (a,b+r,c,d) etc. and a monochromatic upward tetrahedron would lead to
an arithmetic progression of length four but we have forbidden such a progression by our choice of coloring so we are done.

30 March, 2009 at 11:10 am

Kristal Cantwell

1194. H(3,4) is greater than 37

We color the slices of the 37 dimensional hypercube
of side three in the following way:
We start with the Van der Warden number W(3,4) for which
we have an exact value:
W(3,4) =76
from the Ramsey theory book by Graham Rothschild and Spencer
second addition
We give the slice (a,b,c,d) the color associated
with a + 2b + 1 then the maximum value is 75
We add one because the coloring in W(5,2) starts with one
and we have zero values in our slices.
Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
triangle and a monochromatic upward triangle would lead to
an arithmetic progression of length three but we have forbidden such a progression by our choice of coloring so we are done.

30 March, 2009 at 11:18 am

30 March, 2009 at 11:26 am

1195. HOC k=4

After finding the example for HOC k=4 I decided to modify my program to work for this case too. The example is optimal and I get the values.

d=2 weight 7.5 points 12 solutions 8
d=3 weight 14.5 points 45 solutions 112
d=4 weight 25 points 180 solutions 24

The solutions are here
http://abel.math.umu.se/~klasm/Data/HJ/HOC/

Kristal Cantwell

1195. H(n,2)

We start with the fact W(p+1, 2) is greater than or equal to p*2^p
From the book mentioned above
then for any n we an find a prime p less than n greater than n-n^.525
then we get a sequence of length p*2^p free of progressions of length
p and hence of length progressions of length n we look at the largest integer
less than or equal to p*2p/n-1 then subtract one from it that will be the dimension of our slice space we give each slice the coloring associated with
the p*2^p for a + 2b+ 3c .. continued for n terms the maximum value will be less than or equal to p*2^p we will not have an upward n-1 dimensional simplex hence avoid combinatorial lines because if we did we would have a monochromatic arithmetic progression of length p which we have forbidden thus we get a bound H(n,2) is greater than ((n-n^5.35)*2^(n-n.535)/n-1)-2 (the two comes from possible rounding in taking the greatest integer and th subtraction of one).

30 March, 2009 at 12:22 pm

Kristal Cantwell

1196. H(n,r)

We start with the bound W(n,r) is greater than r^n/erk(1+o(1))
which is from the website

http://mathworld.wolfram.com/vanderWaerdenNumber.html

which gives the reference
Heule, M. J. H. “Improving the Odds: New Lower Bounds for Van der Waerden Numbers.” March 4, 2008. http://www.st.ewi.tudelft.nl/sat/slides/waerden.pdf.

then we take that coloring and give it to a +2b+.. continued n-1 times
we can do this if the dimension is less than ((n^r/ern(1+o(1)))/n-1) -2
we then will get no n-1 dimensional upward simplex as then we would
have a monochromatic arithmetic progression which we have forbidden but since we have no monochromatic upward n-1 dimensional simplex we will have no combinatorial lines and so we are done and we have

H(n,r) is greater than ((n^r/ern(1+o(1)))/n-1) -2

30 March, 2009 at 12:29 pm

Kristal Cantwell

1196. HJ(n,r)

I should have written that not H(n,r) in 1190-1194 and in 1195-6 thus the above should be:

HJ(n,r) is greater than ((n^r/ern(1+o(1)))/n-1) -2

HJ(n,2) is greater than ((n-n^5.35)*2^(n-n.535)/n-1)-2

HJ(3,4) is greater than 37

HJ(5,2) is greater than 59

HJ(3,4) is greater than 37

HJ(4,2) is greater than 11

HJ(3,3) is greater than 13

30 March, 2009 at 12:38 pm

30 March, 2009 at 1:10 pm

1197. Fujimura k=3 n= 13

The computation for k=3 n=13 has finished. The optimal size is 46 and I have added the solutions to my table page.

This required some spare time from a linux cluster to be possible so I will not try to extend Fujimura for k=3 unless it turns out to be needed for something specific.

Kristal Cantwell

1198. $c_n$ and generalization beyond 3

We have HJ(3,r) is greater than ((3^r/er3(1+o(1)))/2) -2
so we c_n greater than 3^n/r for n is less than ((3^r/er3(1+o(1)))/2) -2
and we get c_n is is greater than 3^n/(logn-log (log n) -log 3e(1+(o)1))
similarly we get in general the maximal number of points in a combinatorial line free cube of side m and dimension n is m^n/(logn-log (log n) -log (me(1+o1))

30 March, 2009 at 1:12 pm

Kristal Cantwell

1198. correction

imilarly we get in general the maximal number of points in a combinatorial line free cube of side m and dimension n is m^n/(logn-log (log n) -log (me(1+o1)) should be

imilarly we get in general the maximal number of points in a combinatorial line free cube of side m and dimension n is greater than m^n/(logn-log (log n) -log (me(1+o1))

30 March, 2009 at 1:26 pm

DHJ(k): 1200-1299 (Density Hales-Jewett type numbers) « What’s new

[…] March, 2009 in math.CO | Tags: polymath1 | by Terence Tao This is a continuation of the 1100-1199 thread of the polymath1 project, which is now full. The focus has now mostly shifted on generalisations […]

30 March, 2009 at 1:30 pm

Kristal Cantwell

1199. More HJ numbers

We have from
http://www.st.ewi.tudelft.nl/sat/waerden.php
W(3,5) is greater than 170 from this we get
using methods similar to the above HJ(3,5) is
greater than 84 this actually makes a difference for values of
82,83 and 84 for c_n in the table at http://spreadsheets.google.com/ccc?key=p5T0SktZY9DsU-uZ1tK7VEg as the maximal density must be greater than
.2

We have from
the same source
W(3,6) is greater than 207
so by similar method as above we have
HJ(3,6) is greater than 103 again this makes a difference in
the table starting at 82 and continuing through 98 as the maximal density must be greater than 1/6

30 March, 2009 at 3:23 pm