Fujimura.tex

\section{Fujimura's problem}\label{fujimura-sec} Let $\overline{c}^\mu_n$ be the size of the largest subset of the trianglular grid $$\Delta_n := \{(a,b,c)\in \mathbb{Z}^3_+ : a+b+c = n\}$$ which contains no equilateral triangles $(a+r,b,c), (a,b+r,c), (a,b,c+r)$ with $r>0$. These are upward-pointing equilateral triangles. We shall refer to such sets as 'triangle-free'. (Kobon Fujimura is a prolific inventor of puzzles, and in this puzzle asked the related question of eliminating all equilateral triangles.)

The following table was formed mostly by computer searches for optimal solutions. We also found human proofs for most of them (see here).

\begin{figure}\centerline{ \begin{tabular}[l|lllllllllllll] $n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13\\ \hline $\overline{c}^\mu_n$ & 1 & 2 & 4 & 6 & 9 & 12 & 15 & 18 & 22 & 26 & 31 & 35 & 40 & 46 \end{tabular}\label{lowFujimura}\caption{Fujimura numbers}}

For any equilateral triangle $(a+r,b,c)$,$(a,b+r,c)$ and $(a,b,c+r)$, the value $y+2z$ forms an arithmetic progression of length 3. A Behrend set is a finite set of integers with no arithmetic progression of length 3 (see this paper). By looking at those triples (a,b,c) with a+2b inside a Behrend set, one can obtain the lower bound of $\overline{c}^\mu_n \geq n^2 exp(-O(\sqrt{\log n}))$.

It can be shown that $\overline{c}^\mu_n = o(n^2)$ as $n \rightarrow \infty$, but the details are outside the scope of this paper.