Upper and lower bounds

Upper and lower bounds for [math]\displaystyle{ c_n }[/math] for small values of n.

[math]\displaystyle{ c_n }[/math] is the size of the largest subset of [math]\displaystyle{ [3]^n }[/math] that does not contain a combinatorial line. A spreadsheet for all the latest bounds on [math]\displaystyle{ c_n }[/math] can be found here. In this page we record the proofs justifying these bounds.

Basic constructions

For all [math]\displaystyle{ n \geq 1 }[/math], a basic example of a mostly line-free set is

[math]\displaystyle{ 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]\displaystyle{ |D_n| = 2 \times 3^{n-1} }[/math]. The only lines in [math]\displaystyle{ D_n }[/math] are those with

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

One way to construct line-free sets is to start with [math]\displaystyle{ D_n }[/math] and remove some additional points.

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

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

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

[math]\displaystyle{ |\Gamma_{a,b,c}| = \frac{n!}{a! b! c!}. }[/math] (3)

Given any set [math]\displaystyle{ B \subset \Delta_n }[/math] that avoids equilateral triangles [math]\displaystyle{ (a+r,b,c), (a,b+r,c), (a,b,c+r) }[/math], the set

[math]\displaystyle{ \Gamma_B := \bigcup_{(a,b,c) \in B} \Gamma_{a,b,c} }[/math] (4)

is line-free and has cardinality

[math]\displaystyle{ |\Gamma_B| = \sum_{(a,b,c) \in B} \frac{n!}{a! b! c!}, }[/math] (5)

and thus provides a lower bound for [math]\displaystyle{ c_n }[/math]:

[math]\displaystyle{ c_n \geq \sum_{(a,b,c) \in B} \frac{n!}{a! b! c!}. }[/math] (6)

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

Note that if one takes a line-free set and permutes the alphabet [math]\displaystyle{ \{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]\displaystyle{ \Delta_n }[/math] formed by rotation and reflection.)

Another symmetry comes from permuting the [math]\displaystyle{ n }[/math] indices in the strings of [math]\displaystyle{ [3]^n }[/math] (e.g. replacing every string by its reversal). But the sets [math]\displaystyle{ \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]\displaystyle{ [3]^{n+1} }[/math] can be expressed as the union of three copies of [math]\displaystyle{ [3]^n }[/math], we have the basic upper bound

[math]\displaystyle{ c_{n+1} \leq 3 c_n. }[/math] (7)

Note that equality only occurs if one can find an [math]\displaystyle{ n+1 }[/math]-dimensional line-free set such that every n-dimensional slice has the maximum possible cardinality of [math]\displaystyle{ c_n }[/math].

n=0

Clearly [math]\displaystyle{ c_0=1 }[/math].

n=1

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

n=2

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

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

[math]\displaystyle{ z }[/math] is also the same as [math]\displaystyle{ D_2 }[/math]. Combining this with the basic upper bound (7) we see that [math]\displaystyle{ c_2=6 }[/math].

n=3

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

It turns out that [math]\displaystyle{ D_3 = xyz }[/math] is the only 18-element line-free subset of [math]\displaystyle{ [3]^3 }[/math]. To create an 17-element set, the only way is to remove a single element from one of xyz, yzx, or zxy.

n=4

We have [math]\displaystyle{ c_4=52 }[/math]. Indeed, divide a line-free set in [math]\displaystyle{ [3]^4 }[/math] into three blocks of [math]\displaystyle{ [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]\displaystyle{ 18+17+17=52 }[/math]. In fact, there are exactly three ways to get to 52, namely

1. xyz yz’x zxy’

1. y’zx zx’y xyz

1. z’xy xyz yzx’

where

1. x' is x with either 2222 or 3333 removed (depending on whether the x' appears in the second block or the third)
2. y' is y with either 1111 or 3333 removed
3. z' is z with either 1111 or 2222 removed

The second example here can also be described as [math]\displaystyle{ D_4 }[/math] with 1111 and 2222 removed.

n=5

We have the upper bound [math]\displaystyle{ c_4 \leq 154 }[/math]

[The following needs to be formatted etc.] Recall that there is just one pattern to fit 18 points in a cube; the three square slices of this pattern (along any axis) are x, y and z.

To fit 17 points in a cube, the only way is to remove one point from either xyz, yzx or zxy.

This makes the proof in 243. easier because the slices are formed by removing points from

yzx zxy xyz

zxy xyz yzx

xyz yzx zxy

Now the major diagonal of the cube is yyy, and six points must be removed from that. Four of the off-diagonal cubes must also lose points. That leaves 152 points, which contradicts the 155 points we started with.

We have the lower bound [math]\displaystyle{ c_4 \geq 150 }[/math]

[The following needs to be formatted also.]

One way to get 150 is to start with [math]\displaystyle{ D_5 }[/math] and remove the slices [math]\displaystyle{ \Gamma_{0,4,1}, \Gamma_{0,5,0}, \Gamma_{4,0,1}, \Gamma_{5,0,0} }[/math].

Another pattern of 150 points is this: Take the 450 points in [math]\displaystyle{ {}[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

Larger n

The following construction gives lower bounds for the number of triangle-free points, There are of the order [math]\displaystyle{ 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]\displaystyle{ c_{3m} }[/math] are built like this, written in terms of Tao.206’s (a,b,c):

[math]\displaystyle{ c_3 }[/math] from (012) and permutations

[math]\displaystyle{ c_6 }[/math] from (123,024) and perms

[math]\displaystyle{ c_9 }[/math] from (234,135,045) and perms

[math]\displaystyle{ c_{12} }[/math] from (345,246,156,02A,057) and perms (A=10)

[math]\displaystyle{ 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

Asymptotics

DHJ(3) is equivalent to the upper bound

[math]\displaystyle{ c_n \leq o(3^n) }[/math]

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

though this has to be checked.

Numerics suggest that the lower bound constructions above give a lower bound of roughly [math]\displaystyle{ 2.7 \sqrt{\log(n)/n} \times 3^n }[/math], which would asymptotically be inferior to the Behrend bound.