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].
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. Proof: 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.
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]. In fact, there are exactly three ways to get to 52, namely
- xyz yz’x zxy’
- y’zx zx’y xyz
- z’xy xyz yzx’
where
- x' is x with either 2222 or 3333 removed (depending on whether the x' appears in the second block or the third)
- y' is y with either 1111 or 3333 removed
- 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.
Indeed, given a 52-point line-free set, one of the blocks must be xyz and the others must be xyz, yzx, zyx with one point removed. 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 cannot occur since the columns xzy, yxz, zyx of this pattern can contain at most 16 points each. So we must remove two points from xyz zyx yxz or a cyclic permutation thereof, and we can then easily reduce to the above classification.
The same logic can classify 51-point line-free sets.
Theorem: a 51-point set is formed by removing three points from xyz yzx zxy, yzx zxy xyz, or zxy xyz yzx.
Proof. 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 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, and the claim follows.
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.
