Upper and lower bounds
[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.
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| [math]\displaystyle{ c_n }[/math] | 1 | 2 | 6 | 18 | 52 | 150 | 450 | [1302,1350] |
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
- 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]\displaystyle{ D_n }[/math] and remove some additional points. We also have the variants [math]\displaystyle{ D_{n,0}=D_n, D_{n,1}, D_{n,2} }[/math] defined as
- [math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ D_{n,0} }[/math] plays a special role (though [math]\displaystyle{ D_{n,1}, D_{n,2} }[/math] are still interchangeable).
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
- [math]\displaystyle{ c_0=1 }[/math]:
This is clear.
n=1
- [math]\displaystyle{ c_1=2 }[/math]:
The three sets [math]\displaystyle{ D_1 = \{1,2\} }[/math], [math]\displaystyle{ D_{1,1} = \{2,3\} }[/math], and [math]\displaystyle{ D_{1,2} = \{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.
n=2
- [math]\displaystyle{ c_2=6 }[/math]:
There are four six-element sets in [math]\displaystyle{ [3]^2 }[/math] which are line-free, which we denote [math]\displaystyle{ x = D_{2,2} }[/math], [math]\displaystyle{ y=D_{2,1} }[/math], [math]\displaystyle{ z=D_2 }[/math], and [math]\displaystyle{ 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]\displaystyle{ c_2=6 }[/math].
n=3
- [math]\displaystyle{ c_3=18 }[/math]:
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].
Lemma 1.
- The only 18-element line-free subset of [math]\displaystyle{ [3]^3 }[/math] is [math]\displaystyle{ D_3 = xyz }[/math].
- The only 17-element line-free subsets of [math]\displaystyle{ [3]^3 }[/math] are formed by removing a point from [math]\displaystyle{ D_3=xyz }[/math], or by removing either 111, 222, or 333 from [math]\displaystyle{ D_{3,2} = yzx }[/math] or [math]\displaystyle{ D_{3,3}=zxy }[/math].
Proof. We prove the second claim. As [math]\displaystyle{ 17=6+6+5 }[/math], and [math]\displaystyle{ 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]\displaystyle{ \Box }[/math]
n=4
- [math]\displaystyle{ c_4=52 }[/math]:
Indeed, divide a line-free set in [math]\displaystyle{ [3]^4 }[/math] into three blocks [math]\displaystyle{ 1***, 2***, 3*** }[/math] 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] which can be attained by deleting the diagonal {1111,2222,3333} from [math]\displaystyle{ D_{4,1} = xyz yzx xzy }[/math], [math]\displaystyle{ D_4 = yzx zxy xyz }[/math], or [math]\displaystyle{ D_{4,2} = zxy xyz yxz }[/math]. In fact,
Lemma 2.
- The only 52-element line-free sets in [math]\displaystyle{ [3]^4 }[/math] are formed by removing the diagonal {1111,2222,3333} from [math]\displaystyle{ D_{4,j} }[/math] for some j=0,1,2.
- The only 51-element line-free sets in [math]\displaystyle{ [3]^4 }[/math] are formed by removing the diagonal and one further point from [math]\displaystyle{ 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]\displaystyle{ D_{4,1} = xyz yxz zyx }[/math] or a cyclic permutation thereof. Let's say we are removing three points from [math]\displaystyle{ 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]\displaystyle{ D_{4,1} }[/math] with three points removed, and the claim follows from the previous argument. [math]\displaystyle{ \Box }[/math]
n=5
- [math]\displaystyle{ c_5=150 }[/math]:
We have the upper bound [math]\displaystyle{ c_5 \leq 154 }[/math]
Suppose for contradiction that we had a pattern with [math]\displaystyle{ 155 = 3 \times 52 - 1 }[/math] points, then two of the [math]\displaystyle{ [3]^3 }[/math] slices must have 52 points and the third has 51, no matter how one slices. Using the previous theorem, we see up to permutation that one is now removing seven 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_5 \geq 150 }[/math]
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
An integer programming method has established the upper bound [math]\displaystyle{ c_5\leq 150 }[/math], with 12 extremal solutions.
This file contains the extermisers. One point per line and different extermisers separated by a line with “—”
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]\displaystyle{ c_6=450 }[/math]:
The upper bound follows since [math]\displaystyle{ c_6 \leq 3 c_5 }[/math]. The lower bound can be formed by gluing together all the slices [math]\displaystyle{ \Gamma_{a,b,c} }[/math] where (a,b,c) is a permutation of (0,2,4) or (1,2,3).
n=7
- [math]\displaystyle{ 1302 \leq c_7 \leq 1350 }[/math]:
The upper bound follows since [math]\displaystyle{ 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]\displaystyle{ D_7 }[/math].
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, with abc being shorthand for [math]\displaystyle{ \Gamma_{a,b,c} }[/math]:
- [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
- For N=6K:
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]\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} }[/math] is line-free. From this and the Behrend construction it appears that we have the lower bound
- [math]\displaystyle{ c_n \geq 3^{n-O(\sqrt{\log n})} }[/math]
though this has to be checked.
Numerics suggest that the first large n construction given above 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.
The second large n construction had numerical asymptotics for \log(c_n/3^n) close to [math]\displaystyle{ 1.2-\sqrt{\log(n)} }[/math] between n=1000 and n=10000, consistent with the Behrend bound.
Numerical methods
A greedy algorithm was implemented here. The results were sharp for [math]\displaystyle{ n \leq 3 }[/math] but were slightly inferior to the constructions above for larger n.
