View source for Upper and lower bounds

<center>'''Upper and lower bounds for <math>c_n</math> for small values of n.'''</center>

<math>c_n</math> is the size of the largest subset of <math>[3]^n</math> that does not contain a combinatorial line.  A spreadsheet for all the latest bounds on <math>c_n</math> [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DsU-uZ1tK7VEg can be found here].  In this page we record the proofs justifying these bounds.


{|
| n || 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7
|-
| <math>c_n</math> || 1 || 2 || 6 || 18 || 52 || 150 || 450 || [1302,1350]
|}

== Basic constructions ==

For all <math>n \geq 1</math>, a basic example of a mostly line-free set is

:<math>D_n := \{ (x_1,\ldots,x_n) \in [3]^n: \sum_{i=1}^n x_i = 0 \ \operatorname{mod}\ 3 \}</math>.  (1)

This has cardinality <math>|D_n| = 2 \times 3^{n-1}</math>.  The only lines in <math>D_n</math> are those with

# A number of wildcards equal to a multiple of three;
# The number of 1s equal to the number of 2s modulo 3.

One way to construct line-free sets is to start with <math>D_n</math> and remove some additional points.  We also have the variants <math>D_{n,0}=D_n, D_{n,1}, D_{n,2}</math> defined as

:<math>D_{n,j} := \{ (x_1,\ldots,x_n) \in [3]^n: \sum_{i=1}^n x_i = j \ \operatorname{mod}\ 3 \}</math>.  (1')

When n is not a multiple of 3, then <math>D_{n,0}, D_{n,1}, D_{n,2}</math> are all cyclic permutations of each other; but when n is a multiple of 3, then <math>D_{n,0}</math> plays a special role (though <math>D_{n,1}, D_{n,2}</math> are still interchangeable).

Another useful construction proceeds by using the slices <math>\Gamma_{a,b,c} \subset [3]^n</math> for <math>(a,b,c)</math> in the triangular grid

:<math>\Delta_n := \{ (a,b,c) \in {\Bbb Z}_+^3: a+b+c = n \},</math>.  (2)

where <math>\Gamma_{a,b,c}</math> is defined as the strings in <math>[3]^n</math> with <math>a</math> 1s, <math>b</math> 2s, and <math>c</math> 3s.  Note that

:<math>|\Gamma_{a,b,c}| = \frac{n!}{a! b! c!}.</math> (3)

Given any set <math>B \subset \Delta_n</math> that avoids equilateral triangles <math> (a+r,b,c), (a,b+r,c), (a,b,c+r)</math>, the set

:<math>\Gamma_B := \bigcup_{(a,b,c) \in B} \Gamma_{a,b,c}</math> (4)

is line-free and has cardinality

:<math>|\Gamma_B| = \sum_{(a,b,c) \in B} \frac{n!}{a! b! c!},</math> (5)

and thus provides a lower bound for <math>c_n</math>:

:<math>c_n \geq \sum_{(a,b,c) \in B} \frac{n!}{a! b! c!}.</math> (6)

All lower bounds on <math>c_n</math> have proceeded so far by choosing a good set of B and applying (6).  Note that <math>D_n</math> is the same as <math>\Gamma_{B_n}</math>, where <math>B_n</math> consists of those triples <math>(a,b,c) \in \Delta_n</math> in which <math>a \neq b\ \operatorname{mod}\ 3</math>.

Note that if one takes a line-free set and permutes the alphabet <math>\{1,2,3\}</math> in any fashion (e.g. replacing all 1s by 2s and vice versa), one also gets a line-free set.  This potentially gives six examples from any given starting example of a line-free set, though in practice there is enough symmetry that the total number of examples produced this way is less than six.  (These six examples also correspond to the six symmetries of the triangular grid <math>\Delta_n</math> formed by rotation and reflection.)

Another symmetry comes from permuting the <math>n</math> indices in the strings of <math>[3]^n</math> (e.g. replacing every string by its reversal).  But the sets <math>\Gamma_B</math> are automatically invariant under such permutations and thus do not produce new line-free sets via this symmetry.

== The basic upper bound ==

Because <math>[3]^{n+1}</math> can be expressed as the union of three copies of <math>[3]^n</math>, we have the basic upper bound

:<math>c_{n+1} \leq 3 c_n.</math> (7)

Note that equality only occurs if one can find an <math>n+1</math>-dimensional line-free set such that every n-dimensional slice has the maximum possible cardinality of <math>c_n</math>.

== n=0 ==

:<math>c_0=1</math>:

This is clear.

== n=1 ==

:<math>c_1=2</math>:

The three sets <math>D_1 = \{1,2\}</math>, <math>D_{1,1} = \{2,3\}</math>, and <math>D_{1,2} = \{1,3\}</math> are the only two-element sets which are line-free in <math>[3]^1</math>, and there are no three-element sets.

== n=2 ==

:<math>c_2=6</math>:

There are four six-element sets in <math>[3]^2</math> which are line-free, which we denote <math>x = D_{2,2}</math>, <math>y=D_{2,1}</math>, <math>z=D_2</math>, and <math>w</math> and are displayed graphically as follows.

     13 .. 33       .. 23 33       13 23 ..       13 23 ..
 x = 12 22 ..   y = 12 .. 32   z = .. 22 32   w = 12 .. 32
     .. 21 31       11 21 ..       11 .. 31       .. 21 31

Combining this with the basic upper bound (7) we see that <math>c_2=6</math>.

== n=3 ==

:<math>c_3=18</math>:

We describe a subset <math>A</math> of <math>[3]^3</math> as a string <math>abc</math>, where <math>a, b, c \subset [3]^2</math> correspond to strings of the form <math>1**</math>, <math>2**</math>, <math>3**</math> in <math>[3]^3</math> respectively.  Thus for instance <math>D_3 = xyz</math>, and so from (7) we have <math>c_3=18</math>.

'''Lemma 1.'''
* The only 18-element line-free subset of <math>[3]^3</math> is <math>D_3 = xyz</math>.
* The only 17-element line-free subsets of <math>[3]^3</math> are formed by removing a point from <math>D_3=xyz</math>, or by removing either 111, 222, or 333 from <math>D_{3,2} = yzx</math> or <math>D_{3,3}=zxy</math>.

'''Proof'''.  We prove the second claim. As <math>17=6+6+5</math>, and <math>c_2=6</math>, at least two of the slices of a 17-element line-free set must be from x, y, z, w, with the third slice having 5 points.  If two of the slices are identical, the last slice can have only 3 points, a contradiction.  If one of the slices is a w, then the 5-point slice will contain a diagonal, contradiction.  By symmetry we may now assume that two of the slices are x and y, which force the last slice to be z with one point removed.  Now one sees that the slices must be in the order xyz, yzx, or zxy, because any other combination has too many lines that need to be removed.  The sets yzx, zxy contain the diagonal {111,222,333} and so one additional point needs to be removed. 

The first claim follows by a similar argument to the second.
<math>\Box</math>

== n=4 ==

:<math>c_4=52</math>:

Indeed, divide a line-free set in <math>[3]^4</math> into three blocks <math>1***, 2***, 3***</math> of <math>[3]^3</math>.  If two of them are of size 18, then they must both be xyz, and the third block can have at most 6 elements, leading to an inferior bound of 42.  So the best one can do is <math>18+17+17=52</math> which can be attained by deleting the diagonal {1111,2222,3333} from <math>D_{4,1} = xyz yzx xzy</math>, <math>D_4 = yzx zxy xyz</math>, or <math>D_{4,2} = zxy xyz yxz</math>.  In fact,

'''Lemma 2.'''

* The only 52-element line-free sets in <math>[3]^4</math> are formed by removing the diagonal {1111,2222,3333} from <math>D_{4,j}</math> for some j=0,1,2.
* The only 51-element line-free sets in <math>[3]^4</math> are formed by removing the diagonal and one further point from <math>D_{4,j}</math> for some j=0,1,2.

'''Proof''' It suffices to prove the second claim.  Suppose first that we can slice this set into three slices of 17 points.  Each of the slices is then formed by removing one point from xyz, yxz, and zxy.  Arguing as before we obtain the claim.
If one of the xyz, yzx, zyx patterns are used twice, then the third block can have at most 8 points, a contradiction, so each pattern must be used exactly once.  A pattern such as xyz zxy yzx (with three points removed) cannot occur since the columns xzy, yxz, zyx of this pattern can contain at most 16 points each.  So we must remove three points from <math>D_{4,1} = xyz yxz zyx</math> or a cyclic permutation thereof.  Let's say we are removing three points from <math>D_{4,1}</math>.  If 3333 is not removed, then we must remove one from each of the sets {1113,2223}, {1131,2232}, {1311,2322}, {3111,3222}, causing four points to be removed in all, a contradiction; thus 3333 must be removed, and similarly 2222, and the claim follows.

If there is no such slicing available, then every slicing of the 51-point set must slice into an 18-point set, an 17-point set, and a 16-point set.  By symmetry we may assume the 18-point slice is the first one, and the 17 point set is the next one:

xyz ??? ???

Looking at the vertical slices, we see that the first column must also be an xyz:

xyz y?? z??

this forces the second slice, which has 17 points, to be yzx with one point removed; in fact, the point removed must be either 2222 or 2333.  This forces the third slice to be contained in zxy.  Now we are back in the situation of <math>D_{4,1}</math> with three points removed, and the claim follows from the previous argument. <math>\Box</math>

It would be useful to have a classification of the 50-point line-free sets.

== n=5 ==

:<math>c_5=150</math>:

'''Lemma 3'''.  Any line-free subset of <math>D_{5,j}</math> can have at most 150 points.

'''Proof'''.  By rotation we may work with <math>D_5</math>.  This set has 162 points.  By looking at the triplets {10000, 11110, 12220} and cyclic permutations we must lose 5 points; similarly from the triplets {20000,22220, 21110} and cyclic permutations.  Finally from {11000,11111,11222} and {22000,22222,22111} we lose two more points. <math>\Box</math>

Equality can be attained by removing  <math>\Gamma_{0,4,1}, \Gamma_{0,5,0}, \Gamma_{4,0,1}, \Gamma_{5,0,0}</math> from <math>D_5</math>.  Thus <math>c_5 \geq 150</math>.

Another pattern of 150 points is this: Take the 450 points
in <math>{}[3]^6</math> which are (1,2,3), (0,2,4) and permutations,
then select the 150 whose final coordinate is 1. That gives
this many points in each cube:

17 18 17

17 17 18

12 17 17

'''Lemma 4'''.  A line-free subset of <math>[3]^5</math> with over 150 points cannot have two parallel <math>[3]^4</math> slices, each of which contain at least 51 points.

'''Proof'''.  Suppose not.  By symmetry, we may assume that the 1**** and 2**** slices have at least 51 points, and that the whole set has at least 151 points, which force the third slice to have at least <math>151-2c_4 = 47</math> points.

By Lemma 2, the 1**** slice takes the form <math>\{1\} \times D_{4,j}</math> for some <math>j=0,1,2</math> with the diagonal {11111,12222,13333} and possibly one more point removed, and similarly the 2**** slice takes the form <math>\{2\} \times D_{4,k}</math> for some <math>k=0,1,2</math> with the diagonal {21111,22222,23333} and possibly one more point removed.

Suppose first that j=k.  Then the 1-slice and 2-slice have at least 50 points in common, leaving at most 31 points for the 3-slice, a contradiction.  Next, suppose that jk=01.  Then observe that the *i*** slice cannot look like any of the configurations in Lemma 2 and so must have at most 50 points for i=1,2,3, leading to 150 points in all, a contradiction.  Similarly if jk=12 or 20.  Thus we must have jk equal to 10, 21, or 02.

Let's suppose first that jk=10.  The first slice then is equal to <math>\{1\} \times D_{4,1}</math> with the diagonal and possibly one more point removed, while the second slice is equal to <math>\{2\} \times D_{4,0}</math> with the diagonal and possibly one more point removed.  Superimposing these slices, we thus see that the third slice is contained in <math>\{3\} \times D_{4,2}</math> except possibly for two additional points, together with the one point 32222 of the diagonal that lies outside of <math>\{3\} \times D_{4,2}</math>.

The lines x12xx, x13xx (plus permutations of the last four digits) must each contain one point outside the set.  The first two slices can only absorb two of these, and so at least 14 of the 16 points formed by permuting the last four digits of 31233, 31333 must lie outside the set.  These points all lie in <math>\{3\} \times D_{4,2}</math>, and so the 3**** slice can have at most <math>|D_{4,2}|-14+3=43</math> points, a contradiction.

The case jk=02 is similar to the case jk=10 (indeed one can obtain one from the other by swapping 1 and 2).  Now we turn to the case jk=21.  Arguing as before we see that the third slice is contained in <math>\{3\} \times D_4</math> except possibly for two points, together with 33333.  

If 33333 was in the set, then each of the lines xx333, xxx33 (and permutations of the last four digits) must have a point missing from the first two slices, which cannot be absorbed by the two points we are permitted to remove; thus 33333 is not in the set.  For similar reasons, 33331 is not in the set, as can be seen by looking at xxx31 and permutations of the last four digits.  Indeed, any string containing four threes does not lie in the set; this means that at least 8 points are missing from <math>\{3\} \times D_4</math>, leaving only at most 46 points inside that set.  Furthermore, any point in the 3**** slice outside of <math>\{3\} \times D_4</math> can only be created by removing a point from the first two slices, so the total cardinality is at most <math>46+52+52 = 150</math>, a contradiction.<math>\Box</math>

'''Corollary'''. <math>c_5 \leq 152</math>

'''Proof'''.  By Lemma 4 and the bound <math>c_4=52</math>, any line-free set with over 150 points can have one slice of cardinality 52, but then the other two slices can have at most 50 points. <math>\Box</math>


An integer programming method has established the upper bound <math>c_5\leq 150</math>, with 12 extremal solutions.

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

[http://abel.math.umu.se/~klasm/linprog-d=5-t=3.lpt This is the linear program], readable by Gnu’s glpsol linear programing solver, which also quickly proves that 150 is the optimum.

Each variable corresponds to a point in the cube, numbered according to their lexicografic ordering. If a variable is 1 then the point is in the set, if it is 0 then it is not in the set.
There is one linear inequality for each combinatorial line, stating that at least one point must be missing from the line.

== n=6 ==

:<math>c_6=450</math>:

The upper bound follows since <math>c_6 \leq 3 c_5</math>.   The lower bound can be formed by gluing together all the [[slice]]s <math>\Gamma_{a,b,c}</math> where (a,b,c) is a permutation of (0,2,4) or (1,2,3).

== n=7 ==

:<math>1302 \leq c_7 \leq 1350</math>:

The upper bound follows since <math>c_7 \leq 3 c_6</math>. The lower bound can be formed by removing 016,106,052,502,151,511,160,610 from <math>D_7</math>.

== Larger n ==

The following construction gives lower bounds for the number of triangle-free points, 
There are of the order <math>2.7 \sqrt{log(N)/N}3^N</math> points for large N (N ~ 5000)

It applies when N is a multiple of 3. 
* For N=3M-1, restrict the first digit of a 3M sequence to be 1.  So this construction has exactly one-third as many points for N=3M-1 as it has for N=3M. 
* For N=3M-2, restrict the first two digits of a 3M sequence to be 12.  This leaves roughly one ninth of the points for N=3M-2 as for N=3M.

The current lower bounds for <math>c_{3m}</math> are built like this, with abc being shorthand for <math>\Gamma_{a,b,c}</math>:

* <math>c_3</math> from (012) and permutations
* <math>c_6</math> from (123,024) and perms
* <math>c_9</math> from (234,135,045) and perms
* <math>c_{12}</math> from (345,246,156,02A,057) and perms (A=10)
* <math>c_{15}</math> from (456,357,267,13B,168,04B,078) and perms (B=11)

To get the triples in each row, add 1 to the triples in the previous row; then include new triples that have a zero.

A general formula for these points is given below.  I think that they are triangle-free.  (For N<21, ignore any triple with a negative entry.)

* There are thirteen groups of points in the centre, that are the same for all N=3M:
** (M-7, M-3, M+10) and perms
** (M-7, M,   M+7) and perms
** (M-7, M+3, M+4) and perms
** (M-6, M-4, M+10) and perms
** (M-6, M-1, M+7) and perms
** (M-6, M+2, M+4) and perms
** (M-5, M-1, M+6) and perms
** (M-5, M+2, M+3) and perms
** (M-4, M-2, M+6) and perms
** (M-4, M+1, M+3) and perms
** (M-3, M+1, M+2) and perms
** (M-2, M,   M+2) and perms
** (M-1, M,   M+1) and perms
* There is also a string of points, that is slightly different for odd and even N:
** For N=6K:
*** (2x, 2x+2, N-4x-2) and permutations (x=0..K-4)
*** (2x, 2x+5, N-4x-5) and perms (x=0..K-4)
*** (2x, 3K-x-4, 3K+x+4) and perms (x=0..K-4)
*** (2x, 3K-x-1, 3K+x+1) and perms (x=0..K-4)
*** (2x+1, 2x+5, N-4x-6) and perms (x=0..K-5)
*** (2x+1, 2x+8, N-4x-9) and perms (x=0..K-5)
*** (2x+1, 3K-x-1, 3K-x) and perms (x=0..K-5)
*** (2x+1, 3K-x-4, 3K-x+3) and perms (x=0..K-5)
** For N=6K+3: the thirteen points mentioned above, and:
*** (2x, 2x+4, N-4x-4) and perms, x=0..K-4
*** (2x, 2x+7, N-4x-7) and perms, x=0..K-4
*** (2x, 3K+1-x, 3K+2-x) and perms, x=0..K-4
*** (2x, 3K-2-x, 3K+5-x) and perms, x=0..K-4
*** (2x+1, 2x+3, N-4x-4) and perms, x=0..K-4
*** (2x+1, 2x+6, N-4x-7) and perms, x=0..K-4
*** (2x+1, 3K-x, 3K-x+2) and perms, x=0..K-4
*** (2x+1, 3K-x-3, 3K-x+5) and perms, x=0..K-4

An alternate construction:

First define a sequence, of all positive numbers which, in base 3, do not contain a 1. Add 1 to all multiples of 3 in this sequence. This sequence does not contain a length-3 arithmetic progression.

It starts 1,2,7,8,19,20,25,26,55, …

Second, list all the (abc) triples for which the larger two differ by a number
from the sequence, excluding the case when the smaller two differ by 1, but then including the case when (a,b,c) is a permutation of N/3+(-1,0,1)

== Asymptotics ==

DHJ(3) is equivalent to the upper bound

:<math>c_n \leq o(3^n)</math>

In the opposite direction, observe that if we take a set <math>S \subset [3n]</math> that contains no 3-term arithmetic progressions, then the set <math>\bigcup_{(a,b,c) \in \Delta_n: a+2b \in S} \Gamma_{a,b,c}</math> is line-free.  From this and the Behrend construction it appears that we have the lower bound

:<math>c_n \geq 3^{n-O(\sqrt{\log n})}</math>

though this has to be checked.

[http://terrytao.wordpress.com/2009/02/05/upper-and-lower-bounds-for-the-density-hales-jewett-problem/#comment-35652 Numerics suggest] that the first large n construction given above above give a lower bound of roughly <math>2.7 \sqrt{\log(n)/n} \times 3^n</math>, which would asymptotically be inferior to the Behrend bound.

The second large n construction had numerical asymptotics for \log(c_n/3^n) close to <math>1.2-\sqrt{\log(n)}</math> between n=1000 and n=10000, consistent with the Behrend bound.

== Numerical methods ==

A greedy algorithm [http://thetangentspace.com/wiki/Hales-Jewett_Theorem was implemented here].  The results were sharp for <math>n \leq 3</math> but were slightly inferior to the constructions above for larger n.