DHJ(k): 1200-1299 (Density Hales-Jewett type&nbsp;numbers)

31 March, 2009 at 1:27 am

1203. Fujimura k=4 n=7

This night my program finished the computation for Fujimur’as problem with k=4 n=7. The optimum size is 78, and there are only 48 solutions.
I have updated my table page and put the solutions there.

I do not plan to extend the k=4 case further unless further values are needed.

Michael Peake

1204. Query on HJ(k,r)

Kristal,

I am having trouble with the limit for $c_n$ .
The formula given for the van der Waerden number W(r,k) is $\frac{r^k}{erk}(1+o(1))$ , where r is the number of colours and k the size of the cube. k is also the length of the arithmetic progression. For DHJ(3), k=3, so $W(r,3) = \frac{r^2}{3e}(1+o(1))$. Then we can set the dimension to be $n = r^2/6e + o(r^2)$ and keep 1/r of the points. The total number of points kept is $3^n/r$ , which is $O(3^n/\sqrt{n})$ or $3^{n-log(n)/2}$ . This is smaller than the old limit of $3^{n-\sqrt{log(n)}}$ .

31 March, 2009 at 12:13 pm

31 March, 2009 at 12:23 pm

1205. HOC

Is there some viable alternative to the HOC?

For k=2 to original HOC is true.
For k=3 it holds for the few values of n where we know the involved values.

For k=4 it fails for n=2, weight 7.5 and Fujimura has has 7 points, but the number of points in the weighted problem is the same as in the unweighted maximum

For k=4 and n=3 the weight is greater than the size of Fujimura solution, and the number of points is smaller than in the maximum unweighted set.
The same things holds for n=4

Kristal Cantwell

1206. HJ(k,r)

I made a mistake in this section of the wiki, I switched r and k
in the exponent I have repaired this I no longer can improve the
existing asymptotic to c_n so I have deleted that material.

31 March, 2009 at 12:34 pm

Kristal Cantwell

1207. HOC

If the in the HOC equality is replaced a bounding constant factor then I think you can still get DHJ(k) from the weakened HOC The corners theorem and the combinatorial line free state forces the number of slices to be small
the constant factor forces the set in equal slices measure to be small and then equivalence of measures makes the density of the points with ordinary weighting small and we are done.

31 March, 2009 at 1:09 pm

31 March, 2009 at 2:51 pm

I’m coming to this very late, and probably this is overly naive and already long since considered and discarded, but: a permutation can be thought of as a machine for turning slices into {0,1}-colorings of [n]: the coloring is formed by coloring a prefix of the permutation with 0 and a suffix with 1, and the slice tells you how long to make the prefix and suffix. This machine has the property that any two colorings picked out by the same permutation form a combinatorial line in [2]^n. And the equal-slices measure of a set of colorings is just the expected number of colorings picked out by a random permutation.

So I was wondering, in connection with the hyper-optimistic conjecture, whether one could define some sort of combinatorial machine for turning slices into {0,1,2}-colorings of [n], with the property that for any three slices forming an equilateral triangle, the three colorings picked out by the machine for those slices form a combinatorial line. If such machines existed, we could hope for a proof of the hyperoptimistic conjecture in which the equal-slices measure is the expected number of colorings picked out by a random machine.

Sadly, machines of this type do not seem to exist. At least, I tried placing {0,1,2}-colorings of a two-element set into a triangle of the six possible slices a two-element set, and the constraint that equilateral triangles form lines quickly led to inconsistencies.

With this avenue of attack on the hyper-optimistic conjecture blocked off, I’m wondering what other approaches might seem more promising. I looked on the wiki but all I saw were computer calculations; I can imagine a counterexample to the hyper-optimistic conjecture being found in this way but that seems unlikely to lead to a proof.

31 March, 2009 at 4:22 pm

1209. Coloring machine

David, welcome!

I vaguely considered what you are speaking of at this comment. I haven’t had time to think about it further, though. There’s a definite feel of some sort of “automatic chain” going on based on disjoint triangles that could be used to formulate a sensible coloring.

31 March, 2009 at 5:07 pm

1210. Coloring machine

Hi David!

What you propose sounds similar to what Gowers proposed back in 331 and then discounted in 332 for more or less the same reason you did. However, this approach did lead to what I called “Cartesian semi-products”, which were basically upper triangular grids in the cube such that any triangle with one edge on the diagonal formed a combinatorial line; see e.g. my comment 451. Some vestige of this idea eventually got incorporated into the crucial observation “if a set has no combinatorial lines, then it correlates with a local complexity 1 set” which was finally proven in Gowers’ comment 820. And this is a cornerstone of one of our current proofs of DHJ. So, basically, your idea is what did lead (after about four weeks of work, and many twists and turns) to a full solution of the problem :-)

The breakdown of the hyper-optimistic conjecture in k=4 does strongly suggest that the k=3 HOC, if true, is going to be true for “fluky” reasons rather than because there is an elegant proof of the fact. The version of HOC with a constant loss may of course still be true, but cannot be proven or disproven numerically, and I’m not sure there is much more one can say about that version of the conjecture at this stage.

31 March, 2009 at 8:48 pm

1211. Coloring machine

Ok, define a “coloring machine” to be a function M that maps slices in Δn to colorings in [3]^n, but now rather than requiring that all equilateral triangles are mapped by M to lines, we only hope that many of them are. Let a(M) be the cardinality of the largest subset of Δn that avoids all of the triangles mapped by M to lines (obviously this is greater than or equal to the largest triangle-free set).

Then the equal-slices measure of any line-free set must be at most a(M). The proof idea is pretty much the same as for Lubell’s proof of Sperner. The equal-slices measure is the expected number of elements of the line-free set that are picked out by a machine M’ formed by applying a random permutation to M, but any individual one of these machines can only pick out a(M) of these elements else the elements it picks out would include a line.

That is, even if this idea is hopeless for getting to the hyper-optimistic conjecture, maybe it can at least give a nontrivial upper bound on equal-slices measure, if only we could find an infinite family of M’s with small a’s. Of course, you do already have a nontrivial upper bound on equal-slices measure: it is o(|Δn|) because (the Wiki says) that statement is the same as DHJ(3).

Kristal Cantwell

1212. HJ(3,r)

I have added the new bound:

HJ(3,r) is greater than r^{clnr}/2-1

to the wiki at
http://michaelnielsen.org/polymath1/index.php?title=Coloring_Hales-Jewett_theorem#Improved_bounds_on_HJ.283.2Cr.29
more is on it there.

As far as I know this is the first greater than polynomial bound for
HJ(3,r)

1 April, 2009 at 12:16 am

Gil Kalai

1213. all sort of things

Let me repeat some little comments (from the 1000 thread) which are perhaps more appropriate on this thread. The first is that it can be fruitful to examine slightly finer slice structures (perhaps in order to eliminate the hyper optimistic conj already for k=3). For example: Let $\Gamma_{a,b,c; x,y,z}$ be all 0-1-2 vectors with a 0′s b 1′s and c 2′s where x is the sum of indices of the 0 entries y the sum of indices of 1 entries and z the sum of entriez of z vectors. (Such slices are of interest for binary vectors; you can have further refinements by presecribing the sum of squares of 0-indices etc;) union of slices where the sets of vectors (b+2x,y+2z) avoides 3-term AP look like avoiding combinatorial lines. But I do not know if such examples are potentially useful.

The other comment related to David’s is that in the DHJ(2) case (it is still an interesting issue if DHJ(2) is a good analog for DHJ(3)) there are sets which are line-ample – with a lot of lines. Namely, the chains. Now for DHJ(3) I am not aware of sets which have a “lot of lines” (by a lot we really want more than for combinatorial subspaces).

A concrete problem is this: for Sperner a maximal chain is a subset on which the density of a line-free subsubset is at most 1/(n+1). (And of course, there is no subset which is better).

For ${0,1,2}^n$ what is the subset X so that the maximum density $c_X$ in X of a line avoiding subsubset Y is minimum. Are there such X for which $c_X$ is smaller or even substantially smaller than for $X= \{0,1,2\}^n?$ .

1 April, 2009 at 8:59 am

jozsef

1214. HJ(3,r)

re. 1212. Kristal, I think that this is a standard argument. If one can r-colour the integers from 0 to 2d avoiding monochromatic 3-term arithmetic progressions, then it implies HJ(3.r)>d; just colour every point of $\{0,1,2\}^d$ with the colour assigned to the sum of its coordinates. So, $HJ(3,r)\geq W(3,r)/2$ . You used a+2b+1, but it is the same.

1 April, 2009 at 9:13 am

jozsef

1214. HJ(3,r) (contd.)

Maybe one can use a 1-1 map between $[3]^n$ and a subset of integers to get a new bound on HJ(3,r) or DHJ3. We can consider the coordinates of points in $[3]^n$ as exponents of the prime factorization of an integer. If we can find a large set of integers without a 3-term GEOMETRIC progression, that would give a line-free subset in $[3]^n$ . It is different from Kristal’s construction and it might give a better bound (but I’m not sure).

1 April, 2009 at 9:52 am

Michael Peake

1215. Regarding $c_{5,k}$

Following from 1188 and 1189, any coordinate-line-free solution of the five-dimensional k-cube, with $k^4$ missing points, must have the following missing points of each type.

p(vwxyz) = 24a + (k-1)(k-2)(k-3)(k-4)
p(wwxyz) = -60a + 10(k-1)(k-2)(k-3)
p(xxyyz) = 30a + 15(k-1)(k-2)
p(xxxyz) = 20a + 10(k-1)(k-2)
p(xxxyy) = -10a + 10(k-1)
p(xxxxy) = -5a + 5(k-1)
p(xxxxx) = a+1
(a=0..k-1)

Again, the number of missing points on the main diagonal (xxxxx) can be anything from 1 to k, but then the number of each other type is fixed. I don’t know why the formulae are so neat; the theory of Young tableaux and Schur polynomials must have something to do with it.

1 April, 2009 at 10:37 am

Gil

1216. re 1214 part B
Dear Jozsef, This looks very interesting! but are there any bounds known on the density of sets avoiding 3-terms geometric progression? (also when you say it is different than Krystal’s example which example do you refer to?)

1 April, 2009 at 10:44 am

1 April, 2009 at 11:00 am

1217. Coloring machines

I tried playing around a bit with David’s suggestion to find maps $\phi: \Delta_r \to [3]^n$ from a triangle $\Delta_r := \{ (a,b,c) \in {\Bbb Z}_+^3: a+b+c=r\}$ into $[3]^n$ which map as many equilateral triangles into $[3]^n$ as possible.

Currently, we are using embeddings such as $\phi( a,b,c ) = 0^a 1^b 2^c$ (taking r=n, say); this maps (a+r,b,c), (a,b+r,c), (a,b,c+r) to a line as long as b=0 (thus the equilateral triangle has to have one side on the boundary of $\Delta_r$ ).

Another thing to do is to take $r = 2^n-1$ , and map $\phi(a,b,c) = w$ whenever a (resp. b, c) is the n-bit binary string which has 1s at the places where w is 0 (resp. 1, 2) and 0s elsewhere. This map is not defined on all of $\Delta_r$ , but only maps a sort of Sierpinski triangle in $\Delta_r$ to $[3]^n$ , in which exactly one of the i^th bits of a, b, c is one for each i. Any line in $[3]^n$ maps back to an equilateral triangle in $\Delta_r$ . But this basically is just reformulating DHJ(3) as a problem about avoiding a sort of Sierpinski gasket of equilateral triangles (a little reminiscent of the IP-Szemeredi theorem or strong Roth theorem).

1 April, 2009 at 11:46 am

1218. Ternary error correction

While thinking more about what kinds of bounds the coloring machine idea might be able to prove, I ran into a different question that may be heading a bit too far off-topic, but I thought I’d mention it here anyway.

A ternary error-correcting code is just a subset of [3]^n such that no two colorings differ only in a single position. The maximum size of an error correcting code is just [3]^{n-1}, or equivalently the maximum density is 1/3 — just take all colorings whose sum is 0 mod 3. But what is the maximum equal-slices density?

A lower bound of 1/3 on maximum equal-slices density is trivial: take the three sets of colorings whose sum is i mod 3 for i=0,1,2, and choose whichever of them has largest density. But this is not in general optimal. A better lower bound for some n is to take a maximum independent set in Δ_n and use all colorings within those slices. For n=2 this gives equal-slices density 1/2, and for n=4 it gives 2/5, but for n=3 it doesn’t do any better than the trivial 1/3 lower bound.

An upper bound on the maximum equal-slices density is the value of a fractional relaxation of the maximum independent set: assign real numbers to Δ_n such that no two adjacent numbers add to more than one, and take the average of these numbers. I think the optimal solution is the assignment of 1/2 to each slice, so the maximum equal-slices density should be at most 1/2. For n=2 this matches the lower bound but for higher n it is different.

My suspicion is that the lower bound is tight and the upper bound isn’t. Is this known? Any hope of a proof?

jozsef

129. Re 126. Geometric progressions

Dear Gil, I was thinking about how to get a lower bound on HJ(3,r) which is different from Kristal’s in post 1212. I don’t know good lower bounds on monochromatic-3-term-geometric-progression (3GP) avoiding colourings, but I will think about it. In fact, we don’t need to avoid all geometric progressions, just the ones where $a$ and $d$ are relative primes where the 3GP is written as $a, ad, ad^2$ .

1 April, 2009 at 12:46 pm

1219. Fujimura and divisibility

I was working on k=3 Fujimura a little, and while I haven’t had much luck, I wanted to note the divisibility of n seems to be a major factor in the layout of any potential disjoint triangles.

For example, when n mod 2 = 1, one can lay out triangles of side length 1 all the way to the edges of the lattice (for example when n = 3, the triangles 030-120-021, 210-300-201, 012-102-003) whereas when n mod 2 = 0 there is an “extra row”. This means the increase in disjoint triangles to a n mod 2 = 1 case is larger than to a n mod 2 = 0 case.

1 April, 2009 at 2:01 pm

Minor bugfix: that should be “error detection” and “error-detecting code” not “error correction” etc — correction requires greater Hamming distance than two.

1 April, 2009 at 2:52 pm

1220. Fujimura disjoint triangle cover

The triangular lattice of Fujimura’s problem can be covered by disjoint triangles as long as n=2*3^(i-1)-1 (where i >= 1).

Esentially, 6 copies of the previous cover are arranged to make the new cover, and the points not included can then be covered. It’s somewhat Sierpinski-ish.

1 April, 2009 at 3:41 pm

1221. Fujimura disjoint triangle cover.

Jason: see my C++ code for finding covers by disjoint triangles. Obvious necessary conditions for a cover to exist are that the triangular lattice have a number of points divisible by three, and that the bottom edge of the triangle have evenly many points. That is, the number of points on the bottom edge must be 0 or 2 (mod 6). My code finds solutions for all small n satisfying those conditions, with numbers of points on the bottom edge equal to 2, 6, 8, 12, 14, and after that I got tired of waiting for an answer. Your construction allows any solution to be tripled, so 18 and 24 are also solvable; the next unknown case is 20.

1 April, 2009 at 5:21 pm

1222. Fujimura disjoint triangle cover.

If you have a solution with a triangle with n points on the bottom edge, and in addition your solution has the property that it uses the three side-length-1 triangles from the three corners, then Jason’s idea of arranging 6 copies and then covering the remaining points can be used in such a way that the 6 copies overlap only on these side-length-1 triangles. The resulting cover has 3n-4 points on the bottom edge (and again uses three side-length-1 corner triangles).

The solutions for 6 and 8 do have this property of using the three small corner triangles, and lead to solutions for 14 and 20. As I said, 18 and 24 are solvable using Jason’s version of the tripling construction. The same idea with order-6 overlapping corner regions allows the side-length-14 solution to turned into a solution with side length 3*14 – 2*6 = 30. So the next unknown case is 26.

2 April, 2009 at 6:55 am

1223. Alternate slice notation

Kalai.1213 discusses an alternate slice notation $\Gamma_{a,b,c;x,y,z}$ . To begin with, Gil, are you really meaning this?

x is the sum of indices of the 1 entries
y is the sum of indices of the 2 entries
z is the sum of indices of the 3 entries

So for example the string 321 would have x = 2, y = 1, and z = 0. Equal slice notation would have a = 1, b = 1, and c = 1.

Given that, I’m not sure how useful it is combining the equal-slice and index-slice together; on $c_3$ for example it gives one point for each slice, which isn’t terribly useful. It seems better to form a separate slice type notation, say, $\Psi_{x,y,z}$ , and then if at any point we need equal-slice and index-slice together we can use intersection etc. as needed.

With $c_3$ then each $\Psi_{x,y,z}$ is a combinatorial line. For example $\Psi_{2,1,0}$ is the line 121-221-321 intersecting the equal slices $\Gamma_{2,1,0}$ , $\Gamma_{1,2,0}$ , and $\Gamma_{1,1,1}$ .

2 April, 2009 at 8:20 am

1224. Alternate slice notation

The $\Psi_{x,y,z}$ I just mentioned gives combinatorial lines with a single wildcard in the first position; it is therefore useful to be able to number indices arbitrarily, so for example $\Psi^{[2,0,1]}_{x,y,z}$ would give a single wildcard in the second position.

Note also $\Psi^{[1,1,1]}_{x,y,z}$ is then simply equal slices, so it’s probably best to keep with our original notation of Gamma, so the original index-slice notation would be $\Gamma^{[0,1,2]}_{x,y,z}$

(Or whatever alternate way other than my bracket-thing people want to do this.)

2 April, 2009 at 9:02 am

Gil Kalai

1225.
Dear Jason, I suppose this is what I meant; It is ok to think separately on slices of various types. (I did not understand your notation $\Gamma_{x,y,x}^{a,b,c}$ .)

I did not understand what is $\Psi_{x,y,z}$ in 1223.
if the sum of indices of the locations for ’1′ is ’2′ why do you get there 121 and 221?

2 April, 2009 at 9:31 am

2 April, 2009 at 10:49 am

1226. Alternate slice notation

Maybe I’m misunderstanding, but:

121 (in equal slices it would be a = 2, b = 1, c = 0)
1s: 0 + 2 = 2 = x
2s: 1 = 1 = y
3s: 0 = z

221 (in equal slices a = 1, b = 2, c = 0)
1s: 2 = 2 = x
2s: 0 + 1 = 1 = y
3s: 0 = z

321 (in equal slices a = 1, b = 1, c = 1)
1s: 2 = 2 = x
2s: 1 = 1 = y
3s: 0 = z

Gil Kalai

Ok, i suppose I started with 1 (not with 0) it makes no difference if you insist your sets will be from the same slice with the two definitions together. But starting with ’1′ will not allow even the coarse slices to have lines.

Now the individual slices in the index sum definitions are smaller.
(Actually a single slice in the ususal sense is at most $3^n/n$ and not $3^n/\sqrt n$ as the wiki suggests, right?)
Each slice in the new sense have $3^n/n^3$ (when you just take the sum of indices) and if you insist on a slice both in terms of the sums of indices and in terms of number of coordinates of each type (and then you can start with 0) you get slices of at most $3^n/n^4$ .

Now we want to gather many such slices to avoid a combinatorial line. So it looks that if the indices of the slices are (a,b,c,x,y,z,) we should not include 6-tuples avoiding 3 term a. p. simultaniusly in both b+2c and x+2y

The tragedy is that it seems that unions of such slices will give you examples in the same ball park as the examples we already have. but I am not sure about it. Also if it is in the same ball park asymptotically it can lead to better examples than the hyper optimistic ones. We may be able to explore the situation for union of slices in the different sense and in the refined sense for small but not terribly small n’s.

the question is related to the maximum sizes of subsets of a rectangle {1,2,…,a} times {1,2,…,b} not having a 3-term A.P. I suppose the asnwer is in the same ball park as for {1,2,…,ab} but I am not sure about it and I suppose experts would know.

2 April, 2009 at 1:01 pm

3 April, 2009 at 12:38 am

1128. Alternate slice notation

Just to clarify on my notation, $\Gamma^{0,1,2}$ would mean the index starts at 0, and $\Gamma^{1,2,3}$ would mean the index starts at 1.

So to compare:

221 with $\Gamma^{0,1,2}$ :

1s: 2 = x
2s: 0 + 1 = 1 = y
3s: 0 = z

221 with $\Gamma^{1,2,3}$ :

1s: 3 = x
2s: 1 + 2 = 3 = y
3s: 0 = x

Equal slices is $\Gamma^{1,1,1}$ , giving equal weight to each position in the string.

I think it worthwhile to compare the different possible slices using this notation.

2 April, 2009 at 2:05 pm

Kristal Cantwell

1228. Maximal single slice

I think that the maximal single slice is one with all coordinates equal if the dimension is divisible by three, or one of three slices of the same size
using stirling’s approximation
http://mathworld.wolfram.com/StirlingsApproximation.html gives roughly
3^n/n. Apparently the division is by a power approximately one factor of square root of n greater each time we increase k by one and look for the maximum center slice of a cube of dimension n and side k.

1229. HOC k=3

I have now used a different integer programming solver, the cplex solver, in order to determine the value of $c_{6,3}^{\mu}$ .
The program found a solutions quite quickly and after a bit over twelve hours the program had reduced the upper bound to the same value.

The result is $c_{n,3}^{\mu}=15$ .

With this program I can currently not get complete sets of solutions but the solution the program did find is here
http://abel.math.umu.se/~klasm/solutions-n=6-k=3-HOC-6

3 April, 2009 at 5:48 am

3 April, 2009 at 10:36 am

1230. Alternate slice notation

Quick note: when strings get larger the above notation is obviously impractical and not very general, so it’s probably best to have $Gamma^1$ mean Gil’s indexing starting at 1 and $Gamma^0$ be my own starting at 0.

http://numberwarrior.files.wordpress.com/2009/04/sampleslice.gif

1231. Alternate slice notation visual comparison

Just for fun, here’s [3]^2 with four different slice types:

3 April, 2009 at 7:31 pm

Kareem Carr

1232.

I wanted to mentioned before it slips my mind that I expanded my GA to strings in [4]^n, [5]^n, [6]^n and [7]^n. I haven’t had the time to try very hard but I did make an improvement in the lowerbound of [6]^3 of 1031. Things keep coming up but I will try to remember to exhibit the solution. If I don’t and someone is curious about this, please make a post on my blog and remind me or something like that.

Cheers.

3 April, 2009 at 7:50 pm

Kristal Cantwell

1233. GA lower bound 1031

Possibly could that be the Moser set 6^4 has a lower bound of 1031? 6^3 is 216.

4 April, 2009 at 8:03 am

Mats Granvik

1234.

Dear Terence Tao,

It appears that except for the first term, sequence A156989 in the oeis
is given by the expression A105659(A101976) + A000027 – 2.
That is: 0, 2, 6, 18, 52, 150, 450

4 April, 2009 at 8:52 am

Kareem Carr

1235.

Thanks Kristal. Yes I meant [6]^4.

4 April, 2009 at 9:17 am

1236. OEIS sequence

Mats, I get a sequence starting 0, 4, 17, 42, 123 . . .

1*1+1-2 = 0
2*2+2-2 = 4
4*4+3-2 = 17
5*8+4-2 = 42

Am I reading your expression wrong?

4 April, 2009 at 9:23 am

4 April, 2009 at 12:52 pm

1237. Fujimura disjoint triangle cover

David, it might also be useful to have the same information about near-covers, that is, covering $|\Delta_n|-1$ and $|\Delta_n|-2$ .

At the least constructive proofs of the covers seem to leave the door open for upper bound improvement, although I’m still noodling with that.

Kristal Cantwell

1238. Colorings avoiding geometric lines

Let M(n,r) be defined as the least dimension of an n-cube such that any r-coloring of it has a monochromatic line. We will show M(3,2) =3.
It is greater than 2 since we can color the square of side three as follows

221
112
212

To see that it is three must show that every two coloring of the three dimensional cube of side 3 must have a monochromatic geometric line. We start by noting that one of the colors must have the center point then we subtract the Pareto optimal statistics from the total number of points in each class then we get a set of possible statistics that are the only statistics except for those which we get by adding points which correspond to the original statistics with one central point with points removed.

We start with (8,12,6,1) and subtract (3,6,3,1), (4,4,3,1) and (4,6,2,1) getting (5,6,3,0), (4,8,3,0) and (4,6,4,0). Of these only (4,6,4,0) is an extremiser. Now it has two four points with two 2’s. So it must have a pair with the same c-statistic slice on the coordinate of this pair which is not equal to two and we get two side slices which are squares with the central spot occupied. Without loss of generality let the first coordinate be the one with two points with the same c-statistic.

No suppose that there is a second pair of points with two 2’s with the same c-statistic then in the center slice the center and the two points with two 2’s will be empty and hence form a line in the other color and this gives a contradiction so we must have the two remaining points having different c-statistics.

Now without loss of generality let the two remaining points with two twos that are in the center slice be (2,2,1) and (2,1,2).
Then look at the points (1,1,1), (3,1,3), and (3,3,1) only one can be in the set because of possible monochromatic lines formed by (2,2,1), (2,1,1) and (3,2,2). Similarly of the points (3,1,1), (1,1,3) and (1,3,1) can contain only one element in the set because of possible monochromatic lines formed by (2,2,1), (2,1,1) and (1,2,2).

Since we must have four points with no twos by the above we must have the points (1,3,3) and (3,3,3) in the set. This will exclude the point (2,3,3).
Since the point (2,3,3) is excluded and the center slice must contain 4 points the point (2,1,1) must be excluded or it will eliminate all possible remaining points due to possible lines.

Because of a possible line with (1,3,3) and (1,2,2) the point (1,1,1) must be excluded. Similarly because of a possible line with (3,3,3) and (3,2,2) the point (3,1,1) must be excluded.

But now with (1,1,1), (2,1,1) and (3,1,1) excluded by the above they must be in the other color where they form a monochromatic line and we are done and M(3,2) =3.

4 April, 2009 at 10:04 pm

Mats Granvik

1239. Re:1236.

Jason, the expression with the parentheses means that A101976 is used as an index to A105659. In other words lookup the A101976:th number in sequence A105659, then add A000027 and subtract two.

Doing it backwards as I originally did it, you can lookup 2 5 16 49 146 445 without separating commas in the search.

The position of those numbers are given by sequence A101976.

4 April, 2009 at 11:28 pm

Gil Kalai

1240. re: David’s 1218
There are some studies of the “diatance distribution” for error correcting codes, and for linear codes this is equivalent to asking about the densities in every slice. (In particular, about the equal slice measure.) In fact, the linear programming method is based on solving linear programs for the entire distance distribution. (I am not so sure if talking about slices is so natural in the non linear case.)

For example, the conjecture that for (say linear) error-correcting codes that correct a linear number of errors the Gilbert-Varshamov bound is asymptotically optimal, can be strenghtened to Gilbert Varshamov being asymptotically optimal for every slice (and the density in a slice with $bn$ ’1′s will thus be $2^{-H(a)n}$ where $an$ is the minimal distance. (Nati linial and I studied such distance distributions in an old paper of ours.) Anyway, I think trying to relate questions discussed here with error-correcting codes would be very nice. But such a connection is, so far, far.

Also it is worth mentioning that for Sperner’s theorem there is a complete description (sharper than the LYM inequalities) of the possible “f-vectors” namely the number of sets of every possible size. (and this follows from the Kruskal-Katona’s theorem). But it would be ultra optimistic to hope for something like this in DHJ(3).

5 April, 2009 at 12:15 pm

Kristal Cantwell

1241. 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 any set of two points with three twos with
the same c statistic. We have already shown that 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. See post 1171 in http://terrytao.wordpress.com/2009/03/14/dhj3-1100-1199-density-hales-jewett-type-numbers/

We start by assuming we have such a pair and as noted above only one pair the we slice on that the coordinate of that pair say i getting two slide slices with 13 or less points that means that the center slice must have 15 point or more it cannot have sixteen as it has at least one point with three twos in the configuration which becomes a point with two 2’s in the central slice and prevents the only realization of sixteen points from occurring since it has no points with two 2’s. Further we see from the Pareto optimal statistics for Moser sets for n=3 at the Moser wiki we see its distribution must be (4,9,2) we slice the center cube along one of the coordinates j in which there is a point with three twos then one outside slice without loss of generality say j=1 with the point with three twos must have that point at its center and hence have a maximum of 5 points and at most two points with three twos. the center slice has no center point and one point with three twos(we know it is not in the other outside slice because we have only one set of two points with the same c statistic and they are outside the center cube. Because of this the center slice can have at most 4 and it can contain at most three points with two twos, so the remaining slice j =3 must have all four points with two twos.

Now the two side slices since they have thirteen points must have statistics (3,6,3,1) or (4,6,2,1) each. So each of the diagonals connecting points with one two in the slice overall must have at least one point and that means that if we cut each of the side cubes along the same coordinate we cut the center cube we get there are a total four points with one two in the two side slices and if they are divided 2, 2. We can pick two pairs one point in a pair in each slice such there is a correspondence between the pairs of the points in that the coordinates j are equal. If they are divided 1,3 again there is a correspondence between the one point and one of the three such that the coordinates except for j are equal.

Now in the case of division 2-2 or 1-3 in the above we get a contradiction as follows be we have the above correspondences plus another one in the cube j=1 since it has its center spot occupied combined they give there are one or two points with the same center coordinates except for i in the cube j equals three but the center square of j=3 contains all its points with two two’s which block all lines between points with identical coordinates except for j and i equal to three and we get a line so we must have a four zero split, and since that split must have four points in each side cube and the center slice contains of j=3 contains all of it line so must have at most four of these point and the cube j=1 contains its center point and contains at most four of these points, these points must lie on either the squares i=1,j=3 and i=3,j=1 or i=1,j=1 and i=3,j=3 but then they will form a diagonal cube with i=2,j=2 which contains one point with three twos and this forms a line with one of the pairs of these four points on the diagonal cube and we are done.

5 April, 2009 at 1:57 pm

1242. Fujimura disjoint triangle cover

Ok, let P(k,S) denote the statement “the triangular lattice with k points per side admits a partition into disjoint equilateral triangles, such that, for each number k’ in set S, the three corner sublattices with k’ points per side are also partitioned into equilateral triangles”.

We’ve seen
(1) P(k,S) => P(3k,S u {k}) [Jason Dyer 1220] and
(2) P(k,S) and j in S => P(3k-2j,S u {k}) [me 1222].

But we also have
(3) P(k,S) => P(3k+2,S u {k}).
To see this, in a (3k+2)-lattice, place six copies of the P(k,S) partition, three in each corner and three centered on each side. There are two points left over on each side edge of the (3k+2)-lattice that form an equilateral triangle with a point near the middle of the lattice. The remaining points form three regions that are translates of each other in an equilateral pattern and can be covered with congruent equilateral triangles having one point per region. The cover for the 8-lattice is an example of this construction.

So we have
P(2,Ø) — obvious
P(6,{2}) — by (1) from P(2,Ø)
P(8,{2}) — by (3) from P(2,Ø)
P(14,{2,6}) — by (2) from P(6,{2})
P(20,{2,6}) — by (3) from P(6,{2})
P(20,{2,8}) — by (2) from P(8,{2})
P(24,{2,8}) — by (1) from P(8,{2})
P(26,{2,8}) — by (3) from P(8,{2})
P(30,{2,6,14}) — by (2) from P(14,{2,6})
36: NO SOLUTION KNOWN
P(38,{2,6,14}) — by (2) from P(14,{2,6})
P(42,{2,6,14}) — by (1) from P(14,{2,6})
P(44,{2,6,14}) — by (3) from P(14,{2,6})
P(44,{2,8,20}) — by (2) from P(20,{2,8})
P(48,{2,6,20}) — by (2) from P(20,{2,6})
50: NO SOLUTION KNOWN
54: NO SOLUTION KNOWN
P(56,{2,6,20}) — by (2) from P(20,{2,6})
P(56,{2,8,20}) — by (2) from P(20,{2,8})
P(60,{2,6,20}) — by (1) from P(20,{2,6})
P(60,{2,8,20}) — by (1) from P(20,{2,8})
P(62,{2,6,20}) — by (3) from P(20,{2,6})
P(62,{2,8,20}) — by (3) from P(20,{2,8})

It’s starting to look likely that there’s a solution whenever the side length is 0 or 2 mod 6.

5 April, 2009 at 4:32 pm

1243. Fujimura disjoint triangle cover

I forgot that my program had already found a solution for 12. Tripling that gives 36. So the first unknown sizes are 50 and 56.

Also, in the 3n+2 construction, there’s no need to treat the six leftover side points and the three center points as distinct from the three congruent regions. It’s simpler just to think of this as a partition of the (3n+2)-triangular lattice into six n-lattices and three upside-down (n+1)-lattices.

5 April, 2009 at 4:50 pm

1244. Fujimura disjoint triangle cover

Ok, after noticing several more erroneous omissions in the list above, I wrote a program to run the various lattice-tripling patterns for me. Among the possible triangular lattice sizes (congruent to 0 or 2 mod 6) up to 1000, it only fails to find a solution for 32, 66, 96, 192, 288, 572, and 578.

If the size-12 solution can have size-1 equilateral triangles in all four of its corners (that is, in the previous notation, P(12,{2}) — I haven’t checked, but this should be within reach of hand search or the search algorithm I posted earlier), then the only size without a known solution up to 5000 would be 66. So it seems that these tripling rules are almost enough to solve all possible lattice sizes.

6 April, 2009 at 1:53 am

1245. HJ k>3

I have had the programs running during the weekend and they have improved the bounds for two pairs of values.

$c_{4,6}\geq 1051$
$c_{5,4}\geq 708$

I have updated my table page and the solutions are available there too.

6 April, 2009 at 7:50 am

6 April, 2009 at 11:07 am

Metacomment.

The sequence primary to Granvik.1234 is A105659, which was sent in to the OEIS by Sascha Kurz.

Sascha Kurz’s research page has quite a few papers about integral point sets, although I haven’t found the sequence in question. I have emailed the author to hopefully get further info.

I have no idea why integral triangles would be linked to combinatorial lines in such a manner.

Jonathan Vos Post

I withdrew my submission 24 hours earlier of A156989 in favor of Terry Tao’s submission, because I have 2130 sequences there already, and the world of mathematics would benefit from more directly from Dr. Tao. OEIS is a tremendously valuable collaborationware. I now consider it, among other things, a kind of alpha test of Polymath1.

6 April, 2009 at 11:27 am

6 April, 2009 at 11:35 am

1246. Fujimura disjoint triangle cover

Theorem: for all n congruent to 0 or 2 mod 6, the triangular lattice with n points per side can be partitioned into (upwards oriented) triples of points forming the vertices of equilateral triangles.

Proof: We show more strongly by induction that such a partition exists in which the outer three points in each corner of the lattice are each covered by triangles of the partition. As a base case, it’s trivial for n=2.

When n=0 or 6 mod 18, the result follows by partitioning the lattice into six upwards-oriented sublattices of size n/3 and three downwards-oriented sublattices of size n/3 – 1, per [1220]. The upwards sublattices can be partitioned by induction and the downwards sublattices are translates of each other in an equilateral triangle and together can be partitioned into congruent triangles with one vertex per downwards sublattice.

Similarly, when n = 2 or 8 mod 18, the result follows by partitioning the lattice into six upwards-oriented sublattices of size n/3 and three downwards-oriented sublattices of size n/3 + 1, per [1242].

When n = 14 mod 18, the result follows by covering the lattice by six upwards-oriented sublattices of size (n+4)/3 that overlap only on their corners, with six downwards-oriented sublatices of size (n+4)/3 – 5 in an equilateral triangle pattern, per [1222].

When n = 12 mod 18, the result follows by placing three upwards-oriented sublattices of size (n+6)/3 centered on each side of the lattice, overlapping in a size-2 sublattice in the center of the lattice, and placing three upwards-oriented sublattices of size (n+6)/3 – 4 in the corners of the lattice, leaving three downwards-oriented sublattices of size (n+6)/3 – 3 in an equilateral triangle pattern.

This covers all possible values mod 18, so the result is proven.

6 April, 2009 at 10:36 pm

Follow-up to previous comment: there’s a gap in the proof. The claimed decomposition for 12 mod 18 actually works for 14 mod 18. If you try it for 12 mod 18 the three side-centered sublattices will have too large an area of overlap.

Michael Peake

1248: Fujimura triangles

If you have a solution for n, you can get a solution for 2n+2.
First cover the 2n+2 grid with the smallest triangles.
That leaves an n grid of twice the size.

That together with the previous post gives a solution for 30 mod 36.

7 April, 2009 at 7:56 am

Mats Granvik

1249.

What I said here in 1234 and 1239 does not hold. The next term with this method would have been 1473 which is outside the bounds for $latex $.

7 April, 2009 at 7:58 am

Mats Granvik

1249.
Oops, I got the latex wrong I meant c7.

7 April, 2009 at 12:16 pm

Kristal Cantwell

1250. Density Moser theorems implies DH(k) for all k

If we take a point from n^k and map it to 2^k points in 2n^k as follows f(p) is the set of points such that the ith coordinate value is either the ith value of p or 2k-p. This will give 2^k possible points for each point p and thus preserve density.

If there is a geometric line in the 2k set it corresponds to a combinatorial line in the k set as pairs of the form 2k-i and i which are the two possible ith points of a geometric line are images of i and so from a geometric line we get a combinatorial line in the original. This is a generalization for a specific result involving 3 and 6 already known.

We can use this as follows if we have a proof that if a cube of side n has density epsilon and there is a dimension high enough that it has a geometric line and this is true for all n Call this DM(n), we can get DHJ(n) for all n. To see this suppose we do not have DHJ(k) for a specific k then we can use the above mapping which preserves density to get a Moser set with side 2k with epsilon for all dimensions n such that there is no geometric line and this contradicts DM(n) for the specific values epsilon and 2k. This could be used to possibly simplify proofs of DHJ(k) and its consequences.

8 April, 2009 at 5:27 am

Michael Peake

1251: Fujimura, size 12

Referring to 1244, here is a solution to size 12 with a small triangle in each corner:
a,
aa,
bhj,
bbjj,
chlhq,
cckorv,
dglnlvv,
eggoqotq,
eekprkurx,
dimdswuuxx,
fiinsstnytz,
ffmpmwpwyyzz.

8 April, 2009 at 8:25 am

Michael Peake

1252. Fujimura, disjoint triangles

Proof that an equilateral triangle of sides 6n, 6n+2 can be split into equilateral triangles.

Further, they can be covered so that the three corners contain length-2 triangles.

Further, if the side is more than 204, they can be covered so the three corners contain separate length-6 triangles.

Take David’s three rules from 1242.
(1) P(k,S) => P(3k,S u {k})
(2) P(k,S) and j in S => P(3k-2j,S u {k})
(3) P(k,S) => P(3k+2,S u {k}).
Add a fourth rule from 1248:
(4) P(k,S) => P(2k+2, 2 U (2S+2) )

Let Q(k) be the property P(k,{2,6}).
We can do induction if n >34.
Suppose Q(6n) and Q(6n+2) are true
then Q(6n) -> Q(18n-4),Q(18n-12),Q(18n),Q(18n+2)
and Q(6n+2) -> Q(18n+2),Q(18n-6),Q(18n+6),Q(18n+8)
-> Q(18n+m) for m=-6,-4,0,2,6,8
-> Q(6p) and Q(6p+2) are true for p=3n-1, 3n, 3n+1

All that remains now is to establish P(k,S) for k below 204, and Q(6k),Q(6k+2) for k between 35 and 104. My Matlab routine, based on the four rules, said it was true.

8 April, 2009 at 9:28 am

9 April, 2009 at 11:57 am

1253. HJ

I decided try out a variation of the earlier constructions for large sets without combinatorial lines. Consider all sets of the following type: A point $x$ is in $S_A$ if the sum of the coordinates of $x$ belongs to $A$ .
The construction considering the divisors of k is a special case of this kind of set.

It is easy to modify the integer programs to sets of this kind. The results are here
http://abel.math.umu.se/~klasm/Data/HJ/
The numbers of optimal solutions are quite small.

The optimal set of this type for (5,4) actually improved the lower bound for $c_{5,4}$ from 708 to 712.

8 April, 2009 at 1:12 pm

Kristal Cantwell

1254. Colorings avoiding geometric lines

Let M(n,r) be defined as the least dimension of an n-cube such that any r-coloring of it has a monochromatic line.
We will show:

M(2k,r) is greater than or equal to HJ(k,r) and
M(2k+1,r) is greater than or equal to HJ(k,r).

If we have a r-coloring of k^n
which is combinatorial line free then
we give the color each point of 2k (a,b,c..
to each point (a or 2k-a, b or 2k-b and
get a geometric line free coloring as a geometric
line would force a combinatorial line in the orginal coloring
so M(2k,r) is greater than or equal to HJ(k,r).

Similarly
if we have a r-coloring of k^n
which is combinatorial line free then
we give the color each point of 2k (a,b,c..
to each point (a or 2k-a+1, b or 2k-b+1 and
get a geometric line free coloring as a geometric
line would force a combinatorial line in the orginal coloring
so M(2k+1,r) is greater than or equal to HJ(k,r).

Kristal Cantwell

1255. Hyper-optimistic conjecture for Moser sets

If we look at the question of whether the weight of a set that is geometric line free is equal to
the greatest number of slices in a geometric line free set we get
the hyper-optimistic conjecture for Moser sets. For 2 the question is trivially true
since we are allowed only one point and there are single points that are slices.

For 3 and 4 since there are two slice sets that contain geometric lines the number
of slices in a geometric set is linear and quadratic respectively for a density of c/n
in the slice space and this will transfer over to a maximum density of all sets composed of slices of I think
1/n^.5 and this in turn should I think give colorings of less than 1/n^.5 must have a monochromatic line.
Beyond 3 and 4 the colorings start getting better at 5. Can these numbers
be improved by some sort of nonslice division of points. Or for that matter is there a conterexample to the this conjecture for Moser sets.

9 April, 2009 at 9:13 pm

Kristal Cantwell

1255. Hyper-optimistic conjecture for Moser sets correction

In the above the lower bound for the density for moser sets n=3 and 4 deri ed from slices should be something like
1/n^5 but with a factor of log n as well. That will also affect the colorings by a factor of log n as well.

12 April, 2009 at 3:49 am

Michael Peake

1256. Regarding $c_{4,5}$

Following my 1189, I have found a saturated solution of $c_{4,5}$ in which all five points of the major diagonal are among the 125 deleted points. I think that makes it different from the other solutions. I have put it in the wiki. I can’t see how to generalize it yet.

Also, regarding the dissection of the Fujimura triangle into disjoint triangles, there are 118 solutions when n=8, and millions when n=12. So my proof that involved triangles with n>600 was probably overkill.

12 April, 2009 at 4:15 am

Michael Peake

1257.

The solution for $c_{4,5}$ that I put in the wiki was just a disguised version of the solution we already have: Replace the digits (0,1,2,3,4) by (3,4,0,2,1), then for all 125 points (x,y,z,w), x+y+z+2w is a multiple of 5.

14 April, 2009 at 11:05 am

Kristal Cantwell

1258. Lower bound for density of combinatorial line free k cube of side n

From 1170 we get a formula for slice desity based on
lower bounds for sets without k term geometric progressions
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}}}

Now if we restrict ourselves to several standard deviations from the mean
then all the slices will be roughly the same size
as the limit of (1+1/c(n^.5))^c(n^.5) is roughly e^-c
the density is roughly the same there will be a factor of 1/2^5 on the constant multiplying the exponent 2^c(log n)^.5
also in the original I think N had to be k*n+1 since the values for which the arithmetic series are excluded go from 0 to kn and here that range would be roughly c(n^.5)

14 April, 2009 at 12:03 pm

Kristal Cantwell

1258. Correction and further remarks

It should be side k and dimension N
n is used in the formula
the argument has already been used in the wiki to
get the asymptote for c_n based on a set of slices
close to even distribution by a multiple of square root
of n so here I am extending this argument for cases greater than three
using the most recent bound for k arithmetic progression free sets
from

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 k(cN^.5)+1}}{2^{n2^{(n-1)/2}\sqrt[2n]{log K(cN^5}+1}

where here capital N is dimension and n is an integer entirely separate
from N dependent of k

15 April, 2009 at 11:43 am

Kristal Cantwell

1259. 4D Moser

If a 4D Moser set has more than 40 points and 4 points with three
2′s it must have the following statistics:

(6,16,15,4,0,0)

We have from post 1113 that only the following statistics are possible:

(6,16,15,4,0), (7,16,14,4,0), (7,17,13,4,0), and (7,18,12,4,0).

and from post 1241

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

We look at the number of points with one two each one must appear in exactly one of the four possible middles cubes from the four possible coordinate slices, hence if the number of these points is greater than 16 then there must be one such middle cube with five of these points
then by 1241 we know that there must be three points with three twos in the cube as well as otherwise there would be two with the same c statistic so we check the pareto optimizers from the wiki and find there is only one satisfying 5 something 3 something and that is (5,4,3,0)
so the center has 12 points and distribution (5,4,3,0) and the cube with
the remaining point with three twos has thirteen points so the remaining cube must have 16 points and hence distribution (4,12,0,0) and the distribution of the other side cube since has thirteen points must be
(3,6,3,1) or (4,6,2,1) but this gives a total of 5 + 12+ 6 points with one two
which is two many for any of the possible sets of statistics so the only
distribution that is possible is the one with 16 points with one two
namely (6,16,15,4,0) and we are done.

20 April, 2009 at 11:50 am

Kristal Cantwell

1260. 4D Moser

A 4D Moser set with 4 points with three threes has 40 points or less.
By the reasoning of the above post each slice of a Moser set must have 4 points or less with one 2in the center cube. Since from the above we must have 16 of these points and each point only appears in one coordinate slice the division must be exactly 4 4 4 4.

No extremal slice can be 16 if so it has distribution (4,12,0,0) by the Pareto optimizers and hence since by the above the distribution of points with one two must include exactly 4 in the center slice we have a total of 16 and hence none in the other extremal set which contains its center point then by looking at the Pareto optimizers we see that we have to remove 6 points from a thirteen point or four points from a 11 point set in order to realize this and this gives at most 8 points then we have 8 + 16 points for the two side slices and we need 17 points in the center slice which cannot be realized.

So we have the side slice without the center point must have 15 points or less. Next we show that the center slice must have 14 points or less. By the above it must have 4 points with one two but this gives a distribution
of (4 x y z) note the points with one two in this slice count as points with no 2 in the internal statistics of the cube. The center slice must have y = to three because we have already established that there are no two points with the same c-statistic so we must have statistics (4 x 3 0)
which looking at the Pareto optimizers must have 14 points or less.
(I will continue this in the next post .)

20 April, 2009 at 12:08 pm

Kristal Cantwell

1261. 4D Moser set

Continued from 1260:

Now we recall that now two points with three twos can have the same c-statistic then we can assume without loss of generality that all such points have the coordinate not equal to 2 equal to one. Then we look at the points
(1 1 3 2) (1 3 1 2) (3 1 1 2) Only one of these can be in the Moser set because otherwise a line will be formed with the points with three 2′s under the above assumption. Now that means that under one of the coordinate cuts must have a diagonal connecting two points with one two. empty and that means that it can have at most 5 points with one two since each of the other diagonals have at most one point. That implies that the there must be at most 12 points in this cube since the other points have at most 14 and 15 points we must have the distribution 12 14
15 or we will have less than 41 points. Then the statistics of the
cube must be (3 5 3 1) or ( 4 5 2 1) and the other side cube
must have statistics ( 3 9 3 1) (4 9 2 1) or (4 11 0 0)
or (3 12 0 0) but since we have the statistics (6 15 16 4 0) we can only have the choice (3 5 3 1) and the choices (3 9 3 1) and (3 12 0 0)
or we would have more than 6 points with no 2′s and we can discard
the possiblity (3 12 0 0) because it would give more than 16 points with one 2. So we must have (3 5 3 1) and (3 9 3 1) and this gives center slice
(2 9 3 0) but this has less than four points with two twos and will force another slice to have more than 4 and so we are done.

20 April, 2009 at 12:12 pm

Kristal Cantwell

1261. Correction

The first sentence should read recall that no two points with three twos can have the same c-statistic.

20 April, 2009 at 2:22 pm

20 April, 2009 at 5:00 pm

1262.

Kristal, this is great! Looks like we are on track to produce a human proof of the $c'_5=124$ theorem, though if I recall correctly we used Klas’s data in other places as well than the $d \leq 3$ bound for 41+ Moser sets. Also, my reduction of the statistics used Michael’s data for the n=3 Moser sets, which was a brute force search over the $2^{27}$ possibilities if I recall correctly. But that is at least a computation that is easily reproduced, and can probably be proven by human methods also.

23 April, 2009 at 11:06 am

p.s. if you could transcribe the argument to the wiki, that would be great also. At some point I’ll also describe the argument in 1113 in more detail, to help complete the proof.

Kristal Cantwell

1263. 4D Moser set

I put all my posts and 1113 on the Moser wiki at the end of the section n=4.

24 April, 2009 at 8:50 pm

25 April, 2009 at 9:18 am

1264. Limited HOC

Do we need the complete HOC to get DHJ(3)? I haven’t had much time still but I’ve been fiddling with the disjoint triangle proofs and it seems like configurations can get quite different depending on the divisibility of the side length. I theorize it might be possible to find an extremely specific case (to generate a random and non-serious example, where (n+1) mod 128 = 41) where Fujimura is not only tractable but constructible, and the construction can then be used to resolve both ends of the equation.

Kristal Cantwell

1265. Limited HOC

As I understand it we do not need equality but bounding by a constant factor would be enough for the cases n=3 and higher.

28 April, 2009 at 5:22 pm

Michael Peake

1266. 4D Moser set

Kristal, I was going through your proof of the 4D Moser set, and I don’t think you have eliminated the statistic (7,16,14,4,0). In 1259 you show that b=16, and in 1261 you use that a=6.

I have edited your proof a little in the Wiki; I hope you don’t mind.

29 April, 2009 at 10:12 am

Kristal Cantwell

1267. 4D Moser set

It looks like I made a mistake hear and I need to
do case (7 16 14 4 0)
Here it is:

Recall we must have the distribution 12 14
15 or we will have less than 41 points. Also recall that the statistics of the side cube with its center point must be (3 5 3 1) or ( 4 5 2 1) then the statistics of the other side cube
must be ( 3 9 3 0) (4 9 2 0) or (4 11 0 0)
or (3 12 0 0)
Since the statistics are
(7,16,14,4,0) we must have one of the following four pairs
(3 5 3 1) and (4 9 2 0)
(3 5 3 1) and (4 11 0 0)
( 4 5 2 1) and (3 9 3 0)
( 4 5 2 1) and (3 12 0 0)

(3 5 3 1) and (4 9 2 0)
forces the middle slice to have statistics (0 2 9 3)
which has less than 4 points with one two
hence forces another slice to have more than four which gives
a contradiction

(3 5 3 1) and (4 11 0 0)
forces the middle slice to have statistics (0 0 11 3)
which has less than 4 points with one two
hence forces another slice to have more which gives
a contradiction

( 4 5 2 1) and (3 9 3 0)
forces the middle slice to have statistics (0 2 9 3)
which has less than 4 points with one two
hence forces another slice to have more which gives
a contradiction

( 4 5 2 1) and (3 12 0 0)
has 17 points with one two which contradicts the
statistics of the entire set.
So none of the cases work and we are done.

1 May, 2009 at 1:34 pm

Kristal Cantwell

1268. 4D Moser Set

I have added 1267 to the wiki at

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

at the end of the section n=4

Thank you to Michael Peake for finding the error and editing
the proof.

15 May, 2009 at 6:06 am

Metacomment:
Given that we have not added much new material for the last month or so I have a metaquestion:

What are the current plans for writing something up based on the threads here? Will it be part of the paper already being written or a second one?

We have a number of results on both asymptotics and small (n,k). In the outline for the write up that has begun at the wiki, bounds are mentioned as a possible part of the Discussion section.

15 May, 2009 at 8:42 am

Ah, yes, I should be getting back to this project at some point. I was kind of delaying things hoping for the paper writing project on the other side to advance a bit first, but that seems to be slow also.

Right now, it looks like the plan is to have two papers – one for the new proofs of DHJ(3), and the other for the small (n,k) results. My feeling is that we don’t need to put every single result we’ve established into the small(n,k) paper; there are some which definitely have a preliminary feel to them, and in any case there’s no reason why we can’t write a subsequent paper should there be further significant advances, and in the meantime we have the wiki.

The obvious things to put in, I think, are the c_6 and c’_5 computations, the numerics for higher n, the asymptotic counterexamples we have, and the results we have for the n,k DHJ numbers, including the breakdown of the HOC. It looks like we’re close to a human proof of c’_5; it would be nice to have both in there. That would already be a reasonably-sized paper with a number of non-trivial results, I think.

Once we get some consensus on what to put in, I can try to draft an outline of the paper similar to what one has for the other paper, and then we can discuss individual sections, standardise the notation (e.g. is [3] equal to {0,1,2} or {1,2,3}? Not a life-or-death issue, but one which needs to be settled at some point.)

15 May, 2009 at 5:23 pm

I think the suggested material should make a good paper. This will be emphasising the original “growing n” direction of the problem.

I am away for about a week now but once I get back home I should have some time to devote to this project again.

17 May, 2009 at 10:58 am

Kristal Cantwell

I also agree that the suggested material looks good for a paper. I would prefer {1,2,3} as I am used to seeing 2 as the center point. I will be looking at the problem of making the proof of c_5′ a human proof.

18 May, 2009 at 6:43 am

I also vote for {1,2,3}.

I think Fujimura deserves a paper on its own but we don’t know enough about it yet to consider one. Separated from DHJ, allowing r < 0 should be considered, and I think it’d be productive to study all the various restrictions on r (only r = 1, 0 < r < 3, etc.)

I also now believe the HOC is false for even DHJ(3), and it’d be great if we could find a counterexample before the paper goes up, but that might be out of our computational reach.

18 May, 2009 at 6:50 am

Second thought: would it be productive to make a “spin-off” thread for a Fujimura-only polymath? (I’d be happy to make one but my blog traffic is about 30 times less than here, so I doubt we’d get much of the same cross-interaction we’ve had.)

18 May, 2009 at 11:07 am

1269. Fujimura when r can only equal 1

r=1 is the case of considering only the triangles of sidelength 1.

Consider each row r of the triangular lattice. Let the terms of a particular row be i_0, i_1, …. , i_r.
When r mod 3 = 0, then the terms i_k where k mod 3 = 1 should be removed.
When r mod 3 = 1, then the terms i_k where k mod 3 = 0 should be removed.
When r mod 3 = 2, then the terms i_k where k mod 3 = 2 should be removed.

This leaves maximal sets of 0, 2, 4, 6, 10, 14, 18, 24, … which curiously enough matches with A128422 which is the projective plane crossing number of $K_{4,n}$ .

There’s a closed form of $f(n) = \lfloor \frac{n}{3} \rfloor(2n-3(1+\lfloor \frac{n}{3} \rfloor))$ for A128422 which means the closed form for the sequence above is just $f(n+3)$ of the same.

18 May, 2009 at 11:15 am