# Difference between revisions of "Fujimura's problem"

Line 3: | Line 3: | ||

:<math>\Delta_n := \{ (a,b,c) \in {\Bbb Z}_+^3: a+b+c=n \}</math> | :<math>\Delta_n := \{ (a,b,c) \in {\Bbb Z}_+^3: a+b+c=n \}</math> | ||

− | which contains no equilateral triangles <math>(a+r,b,c), (a,b+r,c), (a,b,c+r)</math> with <math>r > 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>\overline{c}^\mu_n</math>. This quantity is relevant to a certain | + | which contains no equilateral triangles <math>(a+r,b,c), (a,b+r,c), (a,b,c+r)</math> with <math>r > 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>\overline{c}^\mu_n</math>. This quantity is relevant to a certain [[hyper-optimistic conjecture]]. |

== n=0 == | == n=0 == | ||

− | + | <math>\overline{c}^\mu_0 = 1</math>: | |

+ | |||

+ | This is clear. | ||

== n=1 == | == n=1 == | ||

− | + | <math>\overline{c}^\mu_1 = 2</math>: | |

+ | |||

+ | This is clear. | ||

== n=2 == | == n=2 == | ||

− | + | <math>\overline{c}^\mu_2 = 4</math>: | |

+ | |||

+ | This is clear (e.g. remove (0,2,0) and (1,0,1) from <math>\Delta_2</math>). | ||

== n=3 == | == n=3 == | ||

− | + | <math>\overline{c}^\mu_3 \geq 6</math>: | |

− | + | For the lower bound, delete (0,3,0), (0,2,1), (2,1,0), (1,0,2) from <math>\Delta_3</math>. | |

− | + | ||

− | set A: (0,3,0) (0,2,1) (1,2,0) | + | For the upper bound: observe that with only three removals each of these (non-overlapping) triangles must have one removal: |

− | set B: (0,1,2) (0,0,3) (1,0,2) | + | |

− | set C: (2,1,0) (2,0,1) (3,0,0) | + | * 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: | 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 | + | * (0,3,0) leaves triangle (0,2,1) (1,2,0) (1,1,1) |

− | (1,2,0) is symmetrical with (0,2,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 == | == n=4 == | ||

− | :<math>\overline{c}^\mu_4=9 | + | :<math>\overline{c}^\mu_4=9</math>: |

The set of all <math>(a,b,c)</math> in <math>\Delta_4</math> with exactly one of a,b,c =0, has 9 elements and is triangle-free. | The set of all <math>(a,b,c)</math> in <math>\Delta_4</math> with exactly one of a,b,c =0, has 9 elements and is triangle-free. | ||

Line 43: | Line 52: | ||

== n=5 == | == n=5 == | ||

− | :<math>\overline{c}^\mu_5=12</math> | + | :<math>\overline{c}^\mu_5=12</math>: |

+ | |||

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

Line 83: | Line 93: | ||

Another upper bound comes from counting the triangles. There are <math>\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>\overline{c}^\mu_n</math>. | Another upper bound comes from counting the triangles. There are <math>\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>\overline{c}^\mu_n</math>. | ||

+ | |||

+ | == Asymptotics == | ||

+ | |||

+ | The corners theorem tells us that <math>\overline{c}^\mu_n = o(n^2)</math> as <math>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>\overline{c}^\mu_n \geq n^2 \exp(-O(\sqrt{\log n}))</math>. |

## Revision as of 18:23, 13 February 2009

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

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

which contains no equilateral triangles [math](a+r,b,c), (a,b+r,c), (a,b,c+r)[/math] with [math]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]\overline{c}^\mu_n[/math]. This quantity is relevant to a certain hyper-optimistic conjecture.

## Contents

## n=0

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

This is clear.

## n=1

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

This is clear.

## n=2

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

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

## n=3

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

For the lower bound, delete (0,3,0), (0,2,1), (2,1,0), (1,0,2) from [math]\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]\overline{c}^\mu_4=9[/math]:

The set of all [math](a,b,c)[/math] in [math]\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]r[/math] is allowed to be negative.)

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

## n=5

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

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

Let [math]S\subset \Delta_5[/math] be a set without equilateral triangles. If [math](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]\Delta_3[/math], so S can at most have 6 elements in this set. So [math]|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]|\Delta_5|=21[/math], so [math]S\leq 21-9=12[/math].

## General n

A lower bound for [math]\overline{c}^\mu_n[/math] is 2n for [math]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]\overline{c}^\mu_{n+1} \geq \overline{c}^\mu_n + 2[/math]

for [math]n \geq 1[/math], because we can take an example for [math]\overline{c}^\mu_n[/math] (which cannot be all of [math]\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]\overline{c}^\mu_n[/math] is 3(n-1), made of all points in [math]\Delta_n[/math] with exactly one coordinate equal to zero.

A trivial upper bound is

- [math]\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]\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]\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]\overline{c}^\mu_n[/math].

## Asymptotics

The corners theorem tells us that [math]\overline{c}^\mu_n = o(n^2)[/math] as [math]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]\overline{c}^\mu_n \geq n^2 \exp(-O(\sqrt{\log n}))[/math].