Difference between revisions of "Fujimura.tex"

From Polymath1Wiki
Jump to: navigation, search
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
\section{Fujimura's problem}\label{fujimura-sec}
 
\section{Fujimura's problem}\label{fujimura-sec}
 +
 
Let $\overline{c}^\mu_n$ be the size of the largest subset of the trianglular grid  
 
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\}$$
+
$$\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'.
 
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 [http://www.puzzles.com/PuzzlePlayground/CoinsAndTriangles/CoinsAndTriangles.htm this] puzzle asked the related question of eliminating all equilateral triangles.)
 
(Kobon Fujimura is a prolific inventor of puzzles, and in [http://www.puzzles.com/PuzzlePlayground/CoinsAndTriangles/CoinsAndTriangles.htm 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 [http://michaelnielsen.org/polymath1/index.php?title=Fujimura's_problem here]).
+
The table in Figure \ref{lowFujimura} was formed mostly by computer searches for optimal solutions. We also found human proofs for most of them (see {\tt http://michaelnielsen.org/polymath1/index.php?title=Fujimura's\_problem}).
 +
 
 +
\begin{figure}
 +
\centerline{
 +
\begin{tabular}{l|llllllllllllll}
 +
$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}
 +
\end{figure}
 +
 
 +
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 {\tt http://arxiv.org/PS\_cache/arxiv/pdf/0811/0811.3057v2.pdf}). 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}))$.
  
\begin{figure}\centerline{
+
It can be shown by a `corners theorem' of Ajtai and Szemeredi \cite{ajtai} that $\overline{c}^\mu_n = o(n^2)$ as $n \rightarrow \infty$.
\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 [http://arxiv.org/PS_cache/arxiv/pdf/0811/0811.3057v2.pdf 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}))$.
+
An explicit lower bound is $3(n-1)$, made of all points in $\Delta_n$ with exactly one coordinate equal to zero.
  
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.
+
An explicit upper bound comes from counting the triangles. There are $\binom{n+2}{3}$ 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 $\overline{c}^\mu_n$.

Latest revision as of 06:46, 27 July 2009

\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 table in Figure \ref{lowFujimura} was formed mostly by computer searches for optimal solutions. We also found human proofs for most of them (see {\tt http://michaelnielsen.org/polymath1/index.php?title=Fujimura's\_problem}).

\begin{figure} \centerline{ \begin{tabular}{l|llllllllllllll} $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} \end{figure}

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 {\tt http://arxiv.org/PS\_cache/arxiv/pdf/0811/0811.3057v2.pdf}). 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 by a `corners theorem' of Ajtai and Szemeredi \cite{ajtai} that $\overline{c}^\mu_n = o(n^2)$ as $n \rightarrow \infty$.

An explicit lower bound is $3(n-1)$, made of all points in $\Delta_n$ with exactly one coordinate equal to zero.

An explicit upper bound comes from counting the triangles. There are $\binom{n+2}{3}$ 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 $\overline{c}^\mu_n$.