Fujimura's problem

Let [math]\displaystyle{ \overline{c}^\mu_n }[/math] the largest subset of the triangular grid

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

which contains no equilateral triangles [math]\displaystyle{ (a+r,b,c), (a,b+r,c), (a,b,c+r) }[/math] with [math]\displaystyle{ r \gt 0 }[/math]; call such sets triangle-free. (It is an interesting variant to also allow negative r, thus allowing "upside-down" triangles, but this does not seem to be as closely connected to DHJ(3).) Fujimura's problem is to compute [math]\displaystyle{ \overline{c}^\mu_n }[/math]. This quantity is relevant to a certain hyper-optimistic conjecture.

n	0	1	2	3	4	5
[math]\displaystyle{ \overline{c}^\mu_n }[/math]	1	2	4	6	9	12

n=0

[math]\displaystyle{ \overline{c}^\mu_0 = 1 }[/math]:

This is clear.

n=1

[math]\displaystyle{ \overline{c}^\mu_1 = 2 }[/math]:

This is clear.

n=2

[math]\displaystyle{ \overline{c}^\mu_2 = 4 }[/math]:

This is clear (e.g. remove (0,2,0) and (1,0,1) from [math]\displaystyle{ \Delta_2 }[/math]).

n=3

[math]\displaystyle{ \overline{c}^\mu_3 = 6 }[/math]:

For the lower bound, delete (0,3,0), (0,2,1), (2,1,0), (1,0,2) from [math]\displaystyle{ \Delta_3 }[/math].

For the upper bound: observe that with only three removals each of these (non-overlapping) triangles must have one removal:

• set A: (0,3,0) (0,2,1) (1,2,0)
• set B: (0,1,2) (0,0,3) (1,0,2)
• set C: (2,1,0) (2,0,1) (3,0,0)

Consider choices from set A:

• (0,3,0) leaves triangle (0,2,1) (1,2,0) (1,1,1)
• (0,2,1) forces a second removal at (2,1,0) [otherwise there is triangle at (1,2,0) (1,1,1) (2,1,0)] but then none of the choices for third removal work
• (1,2,0) is symmetrical with (0,2,1)

n=4

[math]\displaystyle{ \overline{c}^\mu_4=9 }[/math]:

The set of all [math]\displaystyle{ (a,b,c) }[/math] in [math]\displaystyle{ \Delta_4 }[/math] with exactly one of a,b,c =0, has 9 elements and is triangle-free. (Note that it does contain the equilateral triangle (2,2,0),(2,0,2),(0,2,2), so would not qualify for the generalised version of Fujimura's problem in which [math]\displaystyle{ r }[/math] is allowed to be negative.)

Let [math]\displaystyle{ S\subset \Delta_4 }[/math] be a set without equilateral triangles. If [math]\displaystyle{ (0,0,4)\in S }[/math], there can only be one of [math]\displaystyle{ (0,x,4-x) }[/math] and [math]\displaystyle{ (x,0,4-x) }[/math] in S for [math]\displaystyle{ x=1,2,3,4 }[/math]. Thus there can only be 5 elements in S with [math]\displaystyle{ a=0 }[/math] or [math]\displaystyle{ b=0 }[/math]. The set of elements with [math]\displaystyle{ a,b\gt 0 }[/math] is isomorphic to [math]\displaystyle{ \Delta_2 }[/math], so S can at most have 4 elements in this set. So [math]\displaystyle{ |S|\leq 4+5=9 }[/math]. Similar if S contain (0,4,0) or (4,0,0). So if [math]\displaystyle{ |S|\gt 9 }[/math] S doesn’t contain any of these. Also, S can’t contain all of [math]\displaystyle{ (0,1,3), (0,3,1), (2,1,1) }[/math]. Similar for [math]\displaystyle{ (3,0,1), (1,0,3),(1,2,1) }[/math] and [math]\displaystyle{ (1,3,0), (3,1,0), (1,1,2) }[/math]. So now we have found 6 elements not in S, but [math]\displaystyle{ |\Delta_4|=15 }[/math], so [math]\displaystyle{ S\leq 15-6=9 }[/math].

Remark: curiously, the best constructions for [math]\displaystyle{ c_4 }[/math] uses only 7 points instead of 9.

n=5

[math]\displaystyle{ \overline{c}^\mu_5=12 }[/math]:

The set of all (a,b,c) in [math]\displaystyle{ \Delta_5 }[/math] with exactly one of a,b,c=0 has 12 elements and doesn’t contain any equilateral triangles.

Let [math]\displaystyle{ S\subset \Delta_5 }[/math] be a set without equilateral triangles. If [math]\displaystyle{ (0,0,5)\in S }[/math], there can only be one of (0,x,5-x) and (x,0,5-x) in S for x=1,2,3,4,5. Thus there can only be 6 elements in S with a=0 or b=0. The set of element with a,b>0 is isomorphic to [math]\displaystyle{ \Delta_3 }[/math], so S can at most have 6 elements in this set. So [math]\displaystyle{ |S|\leq 6+6=12 }[/math]. Similar if S contain (0,5,0) or (5,0,0). So if |S| >12 S doesn’t contain any of these. S can only contain 2 point in each of the following equilateral triangles:

(3,1,1),(0,4,1),(0,1,4)

(4,1,0),(1,4,0),(1,1,3)

(4,0,1),(1,3,1),(1,0,4)

(1,2,2),(0,3,2),(0,2,3)

(3,2,0),(2,3,0),(2,2,1)

(3,0,2),(2,1,2),(2,0,3)

So now we have found 9 elements not in S, but [math]\displaystyle{ |\Delta_5|=21 }[/math], so [math]\displaystyle{ S\leq 21-9=12 }[/math].

n=6

[math]\displaystyle{ 15 \leq \overline{c}^\mu_6 \leq 17 }[/math]:

[math]\displaystyle{ 15 \leq \overline{c}^\mu_6 }[/math] from the bound for general n.

Note that there are eight extremal solutions to [math]\displaystyle{ \overline{c}^\mu_3 }[/math]:

Solution I: remove 300, 020, 111, 003
Solution II: remove 030, 111, 201, 102
Solution III (and 2 rotations): remove 030, 021, 210, 102
Solution III' (and 2 rotations): remove 030, 120, 012, 201

Also consider the same triangular lattice with the point 020 removed, making a trapezoid. Solutions based on I-III are:

Solution IV: remove 300, 111, 003
Solution V: remove 201, 111, 102
Solution VI: remove 210, 021, 102
Solution VI': remove 120, 012, 201

Suppose we can remove all equilateral triangles on our 7×7x7 triangular lattice with only 10 removals.

The triangle 141-411-114 must have at least one point removed. Remove 141, and note because of symmetry any logic that follows also applies to 411 and 114.

There are three disjoint triangles 060-150-051, 240-231-330, 042-132-033, so each must have a point removed.

(Now only six removals remaining.)

The remainder of the triangle includes the overlapping trapezoids 600-420-321-303 and 303-123-024-006. If the solutions of these trapezoids come from V, VI, or VI', then 6 points have been removed. Suppose the trapezoid 600-420-321-303 uses the solution IV (by symmetry the same logic will work with the other trapezoid). Then there are 3 disjoint triangles 402-222-204, 213-123-114, and 105-015-006. Then 6 points have been removed. Therefore the remaining six removals must all come from the bottom three rows of the lattice.

Note this means the "top triangle" 060-330-033 must have only four points removed so it must conform to solution either I or II, because of the removal of 141.

Suppose the solution of the trapezoid 600-420-321-303 is VI or VI'. Both solutions I and II on the "top triangle" leave 240 open, and hence the equilateral triangle 240-420-222 remains. So the trapezoid can't be VI or VI'.

Suppose the solution of the trapezoid 600-420-321-303 is V. This leaves an equilateral triangle 420-321-330 which forces the "top triangle" to be solution I. This leaves the equilateral triangle 201-321-222. So the trapezoid can't be V.

Therefore the solution of the trapezoid 600-420-321-303 is IV. Since the disjoint triangles 402-222-204, 213-123-114, and 105-015-006 must all have points removed, that means the remaining points in the bottom three rows (420, 321, 510, 501, 312, 024) must be left open. 420 and 321 force 330 to be removed, so the "top triangle" is solution I. This leaves triangle 321-024-051 open, and we have reached a contradiction.

[math]\displaystyle{ 15 \leq \overline{c}^\mu_6 \leq 16 }[/math]:

Here, "upper triangle" means the first four rows (with 060 at top) and "lower trapezoid" means the bottom three rows.

Suppose 11 removals leave a triangle-free set.

First, suppose that 5 removals come from the upper triangle and 6 come from the lower trapezoid.

Suppose the trapezoid 600-420-321-303 used solution IV. There are three disjoint triangles 402-222-204, 213-123-114, and 105-015-006. The remainder of the points in the lower trapezoid (420, 321, 510, 501, 402, 312, 024) must be left open. 024 being open forces either 114 or 015 to be removed.

Suppose 114 is removed. Then 213 is open, and with 312 open that forces 222 to be removed. Then 204 is open, and with 024 that forces 006 to be removed. So the bottom trapezoid is a removal configuration of 600-411-303-222-114-006, and the rest of the points in the bottom trapezoid are open. All 10 points in the upper triangle form equilateral triangles with bottom trapezoid points, hence 10 removals in the upper triangle would be needed, so 114 being removed doesn't work.

Suppose 015 is removed. Then 006-024 forces 204 to be removed. Regardless of where the removal in 123-213-114, the points 420, 321, 222, 024, 510, 312, 501, 402, 105, and 006 must be open. This forces upper triangle removals at 330, 231, 042, 060, 051, 132, which is more than the 5 allowed, so 015 being removed doesn't work, so the trapezoid 600-420-321-303 doesn't use solution IV.

Suppose the trapezoid 600-420-321-303 uses solution VI. The trapezoid 303-123-024-006 can't be IV (already eliminated by symmetry) or VI' (leaves the triangle 402-222-204). Suppose the trapezoid 303-123-024-006 is solution VI. The removals from the lower trapezoid are then 420, 501, 312, 123, 204, and 015, leaving the remaining points in the lower trapezoid open. The remaining open points is forces 10 upper triangle removals, so the trapezoid 600-420-321-303 doesn't use solution VI. Therefore the trapezoid 303-123-024-006 is solution V. The removals from the lower trapezoid are then 420, 510, 312, 204, 114, and 105. The remaining points in the lower trapezoid are open, and force 9 upper triangle removals, hence the trapezoid 303-123-024-006 can't be V, and the solution for 600-420-321-303 can't be VI.

The solution VI' for the trapezoid 600-420-321-303 can be eliminated by the same logic by symmetry.

Therefore it is impossible for 5 removals come from the upper triangle and 6 come from the lower trapezoid. Therefore 4 removals come from the upper triangle and 7 come from the lower trapezoid.

At this point note the triangle 141-411-141 must have one point removed, so let it be 141 and note that any logic that follows is also true for a removal of 411 and 141 by symmetry.

This implies the upper triangle must have either solution I or II.

Suppose it has solution II. Note there are five disjoint triangles 600-510-501, 411-321-312, 402-222-204, 213-123-114, and 105-015-006.

Suppose 420 and 024 are removed. Then, noting 303 must be open, 606 must be removed, leaving 510 open. 510-240 forces 213 to be removed, and 510-150 force 114 to be removed. 213 are 114 are in the same disjoint triangle. Hence both 420 and 024 both can't be removed.

So at least either 420 or 024 is open. Let it be 420, noting by symmetry identical logic will apply if 024 is removed. Then 321, 222, and 123 are removed based on 420 and the open spaces in the upper triangle. This leaves four disjoint triangles 600-501-510, 402-303-312, 213-033-015, 204-114-105. So 411 and 420 are open, forcing the removal of 510. This leaves 501 open, and 501-411 forces the removal of 402. 600-303, and 330 are then open, forming an equilateral triangle. Therefore 420 isn't open, therefore the upper triangle can't have solution II.

Therefore the upper triangle has solution I.

Suppose 222 is open. 222 with open points in the upper triangle force 420, 321, 123, and 024 to be removed. This leaves four disjoint triangles 411-501-402, 213-303-204, 015-105-006, and 132-312-114. This would force 8 removals in the lower trapezoid, so 222 must be closed.

Therefore 222 is removed. There are six disjoint triangles 150-420-123, 051-321-024, 231-501-204, 132-402-105, 510-150-114, and 312-042-015. So 600, 411, 393, 114, and 006 are open. 600-240 open forces 204 to be removed and 600-150 open forces 105 to be removed. This forces 501 and 402 to be open, but 411 is open, so there is the equilateral triangle 501-411-402.

Therefore the solution of the upper triangle is not I, and we have a contradiction. So [math]\displaystyle{ \overline{c}^\mu_6 \neq 17 }[/math].

n = 7

[math]\displaystyle{ \overline{c}^\mu_{7} \leq 22 }[/math]:

Using the same eight extremal solutions to [math]\displaystyle{ \overline{c}^\mu_3 }[/math] as previous proofs:

Solution I: remove 300, 020, 111, 003
Solution II: remove 030, 111, 201, 102
Solution III (and 2 rotations): remove 030, 021, 210, 102
Solution III' (and 2 rotations): remove 030, 120, 012, 201

Suppose the 8x8x8 lattice can be triangle-free with only 13 removals.

Slice the lattice into region A (070-340-043) region B (430-700-403) and region C (034-304-007). Each region must have at least 4 points removed. Note there is an additional disjoint triangle 232-322-223 that also must have a point removed. Therefore the points 331, 133, and 313 are open. 331-313 open means 511 must be removed, 331-133 open means 151 must be removed, and 133-313 open means 115 must be removed. Based on the three removals, the solutions for regions A, B, and C must be either I or II. All possible combinations for the solutions leave several triangles open (for example 160-520-124). So we have a contradiction, and [math]\displaystyle{ \overline{c}^\mu_7 \leq 22 }[/math].

n = 8

[math]\displaystyle{ \overline{c}^\mu_{8} \geq 22 }[/math]:

008,026,044,062,107,125,134,143,152,215,251,260,314,341,413,431,440,512,521,620,701,800

n = 9

[math]\displaystyle{ \overline{c}^\mu_{9} \geq 26 }[/math]:

027,045,063,081,126,135,144,153,207,216,252,270,315,342,351,360,405,414,432,513,522,531,603,630,720,801

n = 10

[math]\displaystyle{ \overline{c}^\mu_{10} \geq 29 }[/math]:

028,046,055,064,073,118,172,181,190,208,217,235,262, 316,334,352,361,406,433,442,541,550,604,613,622, 721,730,901,1000

General n

A lower bound for [math]\displaystyle{ \overline{c}^\mu_n }[/math] is 2n for [math]\displaystyle{ n \geq 1 }[/math], by removing (n,0,0), the triangle (n-2,1,1) (0,n-1,1) (0,1,n-1), and all points on the edges of and inside the same triangle. In a similar spirit, we have the lower bound

[math]\displaystyle{ \overline{c}^\mu_{n+1} \geq \overline{c}^\mu_n + 2 }[/math]

for [math]\displaystyle{ n \geq 1 }[/math], because we can take an example for [math]\displaystyle{ \overline{c}^\mu_n }[/math] (which cannot be all of [math]\displaystyle{ \Delta_n }[/math]) and add two points on the bottom row, chosen so that the triangle they form has third vertex outside of the original example.

An asymptotically superior lower bound for [math]\displaystyle{ \overline{c}^\mu_n }[/math] is 3(n-1), made of all points in [math]\displaystyle{ \Delta_n }[/math] with exactly one coordinate equal to zero.

A trivial upper bound is

[math]\displaystyle{ \overline{c}^\mu_{n+1} \leq \overline{c}^\mu_n + n+2 }[/math]

since deleting the bottom row of a equilateral-triangle-free-set gives another equilateral-triangle-free-set. We also have the asymptotically superior bound

[math]\displaystyle{ \overline{c}^\mu_{n+2} \leq \overline{c}^\mu_n + \frac{3n+2}{2} }[/math]

which comes from deleting two bottom rows of a triangle-free set and counting how many vertices are possible in those rows.

Another upper bound comes from counting the triangles. There are [math]\displaystyle{ \binom{n+2}{3} }[/math] triangles, and each point belongs to n of them. So you must remove at least (n+2)(n+1)/6 points to remove all triangles, leaving (n+2)(n+1)/3 points as an upper bound for [math]\displaystyle{ \overline{c}^\mu_n }[/math].

Asymptotics

The corners theorem tells us that [math]\displaystyle{ \overline{c}^\mu_n = o(n^2) }[/math] as [math]\displaystyle{ n \to \infty }[/math].

By looking at those triples (a,b,c) with a+2b inside a Behrend set, one can obtain the lower bound [math]\displaystyle{ \overline{c}^\mu_n \geq n^2 \exp(-O(\sqrt{\log n})) }[/math].