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.
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{ \{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.
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 }[/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
- [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.
n=4
- [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
- 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.
n=5
- [math]\displaystyle{ c_5=150 }[/math]:
We have the upper bound [math]\displaystyle{ c_5 \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_5 \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
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.
