%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-41/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}

%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}

\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}


%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
  \gdef\@thm@name{#3}%
  \@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
   \edef\@currentlabel{\@thm@name}%
   \label{#1}\endgroup
}
\makeatother
% end lift

\newtheoremstyle{namedthrm}
  {}{}{}{}{}{}{ }  % This last space needs to be there
  {\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack


%% Document start
\date{}
\begin{document}

%% Content start


\newtheorem{cor}{Corollary}
\newtheorem*{lemma}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{fact}{Fact}
\newtheorem{q}{Problem}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem*{remark}{Remark}
\newtheorem*{ack}{Acknowledgements}


\title{Monochromatic Affine Lines in Finite Vector Spaces}
\author{T. C. Brown}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{Monochromatic affine lines in finite vector spaces}, J. Combin.
  Theory Ser. A \textbf{38} (1985), 35--41.}\bigskip\end{center}

\begin{abstract}
Let $d(k,q)$ be the smallest positive integer $d$ such that if the $d$-dimensional vector space over the $q$-element field is $k$-colored, there exists a monochromatic affine line. It is shown that $d(2,4) = 3$ and $d(3,3) = 4$.
\end{abstract}

\section{Introduction} \label{sec: 1} 

Let $F_q$ denote the $q$-element field and let $F_q(d)$ denote the $d$-dimensional vector space over $F_q$. We will take $F_q(d) = \{(x_1,\dots,x_d): x_i \in F_q, 1 \leq i \leq d\}$. For any $k \geq 1$ and prime power $q$, let $d(k,q)$ denote the smallest integer $d$ such that if $F_q(d)$ is $k$-colored, there exists a monochromatic affine line.

(In other words, if
\[ F_q(d) = A_1 \cup A_2 \cup \cdots \cup A_k, \]
then some $A_i$ contains an affine line. An affine line is any translate (coset) of a $1$-dimensional vector subspace.)

The existence of the numbers $d(k,q)$ is guaranteed by the Hales-Jewett theorem~\cite{hales+jewett1963}. However, no ``reasonable" (for example, primitive recursive) upper bound is known for these numbers.

Similarly, no ``reasonable" upper bound is known for the van der Waerden numbers $w(k,t)$, where, for any $k \geq 1$, $t \geq q$, $w(k,t)$ is the smallest positive integer $w$ such that if $\{1,2,\dots,w\}$ is $k$-colored, there exists a monochromatic $t$-term arithmetic progression~\cite{vanderwaerden1927}.

In this note we show that $d(2,4) = 3$ and $d(3,3) = 4$.

(The only known non-trivial values for the van der Waerden numbers are $w(2,3) = 9$, $w(3,3) = 27$, $w(2,4) = 35$, $w(3,4) = 76$, $w(2,5) = 178$~\cite{bernoulli1772}.)

In the case of $d(3,3) = 4$, (or of $d(2,3) = 2$) we are dealing with affine lines over the field $F_3$, and these are precisely the sets of the form 
\[ \{x, x + y, x + 2y\}, \quad y \ne 0. \]
That is, the affine lines are $3$-term arithmetic progressions in $F_3(4)$ (or $F_3(2)$). 

The only known way to show that $w(3,3) = 27$ is to verify (by computer) that each of the $3^{27}$ 3-colorings of $\{1,2,\dots,27\}$ has a monochromatic $3$-term arithmetic progression. It is interesting that the algebraic and geometric structure carried by $F_3(4)$ allows one to show in a few pages that each of the $3^{81}$ 3-colorings of $F_3(4)$ has a monochromatic $3$-term arithmetic progression. Perhaps this method can be extended to give upper bounds for $d(k,3)$, $k > 3$.

\section{Exact values for $d(k,q)$} \label{sec: 2}

Throughout, by ``line" we mean ``affine line."

\begin{fact} \label{fact: 1}
$d(k,2) = \lfloor \log_2k \rfloor + 1$, $k \geq 1$.
\end{fact}

\begin{proof} Any 2-element subset of $F_2(d)$ is a line, hence if $2^d>k$ and $F_2(d)$ is $k$-colored, there will be a monochromatic line, and therefore $d(k,2) \leq \lfloor log_2k\rfloor + 1$. It is clear that $d(k,2) > \lfloor \log_2 k \rfloor$.
\end{proof}

\begin{fact} \label{fact: 2}
$d(2,3) = 2$.
\end{fact}

\begin{proof}
Clearly $d(2,3) > 1$. Examination of a few cases shows that $d(2,3) \leq 2$.
\end{proof}

\begin{fact} \label{fact: 3}
d(2,4) = 3.
\end{fact}

\begin{proof} It is not difficult to find a 2-coloring of $F_4(2)$ for which there does not exist any monochromatic line. (Note that $F_4(2)$ has 20 lines, 4 translates of each of the 5 1-dimensional vector subspaces.) For example, with $F_4 = \{0,1, s, 1 + s\}$ (where $s^2 = 1 + s$), color the points $(0,0), (0,s), (0,1 + s), (1,1), (s,1), (1 + s,0), (1 + s,s), (1 + s, 1 + s)$ with one color, and the remaining points of $F_4(2)$ with the other color. This shows that $d(2,4) > 2$.

To show that $d(2,4) \leq 3$, we suppose that a 2-coloring of $F_4(3)$ is given, say, using the colors Red and Blue, and we assume that there does not exist any monochromatic line.

Let $A$ be the set of Red points. Then $A$ meets every line, and contains no line. Let $|A| = t$, and for each $x$ in $A$, let $A_x$ denote the set of lines in $F_4(3)$ which contain $x$.

Let $a_i$ be the number of lines in $F_4(3)$ which contain exactly $i$ points of $A$, for $i = 1,2,3$. Note that in $F_4(3)$ there are $(4^3 - 1)/(4 - 1) = 21$ lines containing a given point, and $21 \cdot 4^3/4 = 336$ lines altogether.

Now let $S$ denote the sum $\sum |A_x| \: (x \in A)$ and let $T$ denote the sum $\sum |A_x \cap A_y| \: (x,y \in A, x \ne y)$. Then a line which contains exactly one point of $A$ contributes 1 to $S$ and 0 to $T$. Similarly, a line containing exactly two points of $A$ contributes 2 to $S$ and 1 to $T$, and line containing three points of $A$ contributes 3 to $S$ and 3 to $T$. Noting that $|A_x| = 21$ and $|A_x \cap A_y| = 1$ for all $x,y \in A$, $x \ne y$, we obtain
\begin{align*} a_1 + a_2 + a_3 &= 336, \\
a_1 + 2a_2 + 3a_3 &= \sum |A_x| = 21t, \\
a_2 + 3a_3 &= \sum |A_x \cap A_y| = \frac{1}{2} t(t - 1).
\end{align*}

Solving gives
\begin{align*} 
a_1 &= \frac{1}{2}[t^2 - 85t + 2016], \\
a_2 &= -[t^2 - 64t + 1008], \\
a_3 &= \frac{1}{2}[t^2 - 43t + 672]. \end{align*}

The number $a_2$ is non-negative only when $28 \leq t \leq 36$, and for each of these values of $t$, either $a_1 \geq 160$ or $a_3 \geq 160$.

Therefore we may assume without loss of generality that there are 160 lines containing three Red points and one Blue point each. (In short, we have 160 RRRB lines.)

From this point on it will be convenient to perform various invertible affine transformations (an invertible linear transformation followed by a translation) on the vector space $F_4(3)$. Each time we do this, we actually shift to a new coloring, but if we find a monochromatic line relative to the new coloring, there must be a monochromatic line relative to the old coloring. Indeed, if $c: F_4(3) \mapsto \{R,B\}$ is any coloring and $f$ is any invertible affine transformation, then the new coloring $c'$ is defined by 
\[ c'(x) = c(f^{-1}(x)), \quad x \in F_4(3), \]
and there is a $c$-monochromatic line $L$ if and only if there is a $c'$-monochromatic line $f(L)$.

Returning to the argument, note that the set of all lines in $F_4(3)$ is the disjoint union of 21 sets of 16 lines each, where each set is a ``parallel class of lines," that is, within each set the 16 lines are all parallel. (Two lines are parallel if each is a translate of the other.) Since $7 \cdot 21 < 160$, some parallel class must contain at least 8 RRRB lines.

Thus there is a line $L$ and points $a_1',\dots,a_8'$ such that 
\[ a_1' + L, \dots, a_8' + L \]
are all RRRB lines.

By means of affine transformations we can assume that 
\[ L = F_4v, \quad v = (1,0,0), \]
so that if $a' = (x,y,z)$ then $a' + L = \{(x + a, y, z): a \in F_4\}$. In particular, each line $a_i' + L$ intersects the plane
\[ P = \{(0,y,z): y,z \in F_4\} \]
in a point $a_i$. Since $a_i' + L = a_i + L$, we have that $a_1 + L, \dots, a_8 + L$ are all RRRB lines and that $a_1,\dots,a_8 \in P$.

Now in $P$, some three of $a_1,\dots,a_8$ are collinear, say, on the line $L_1$. (For in $P$ there are exactly 5 lines through $a_1$. At least 2 of the remaining 7 points $a_2,\dots,a_8$ must lie on one of these lines.)

Assume that $\{a_1,a_2,a_3,b\} = L_1$. Since $L_1 \subset P$, $L_1$ and $L$ are not parallel, so the lines $a_1 + L$, $a_2 + L$, $a_3 + L$, $b + L$ are parallel and their union is a plane $P_1$. Since the first 3 of these lines are RRRB lines, their union contains only 3 Blue points.

We can assume that the line $b + L$ contains a Red point $u_0$. (Otherwise, the line $b + L$ is monochromatic in the color Blue.) Through $u_0$ in the plane $P_1$ there are 5 lines: the line $b + L$, and four more lines. Each of the three Blue points in $(a_1 + L) \cup (a_2 + L) \cup (a_3 + L)$ belongs to exactly one of these four lines. Hence there is a line through $u_0$ in $P_1$ which is monochromatic in the color Red.

This contradiction finishes the proof that $d(2,4) \leq 3$, and hence $d(2,4) = 3$. 
\end{proof}

\begin{fact} \label{fact: 4}
$d(3,3) = 4$.
\end{fact}

\begin{proof}
To see that $d(3,3) > 3$, consider the following coloring of $F_3(3)$, using the colors $1,2,3$.
\[ \begin{matrix} 1 & 1 & 2 \\ 1 & 1 & 2 \\ 2 & 2 & 3 \end{matrix} \qquad \begin{matrix} 2 & 2 & 3 \\ 2 & 2 & 3 \\ 3 & 3 & 1 \end{matrix} \qquad
\begin{matrix} 3 & 3 & 1 \\ 3 & 3 & 1 \\ 1 & 1 & 2 \end{matrix} \]
It is easy to check that there is no monochromatic line.

To see that $d(3,3) \leq 4$, we argue along the lines of the proof of Fact~\ref{fact: 3}, except that now the equations are obtained from incidence relations involving points and planes (by ``plane" we mean ``affine plane," that is, a translate of a 2-dimensional vector subspace) rather than points and lines.
Let a 3-coloring of $F_3(4)$ be given, say, using the colors Red, Blue, and Green, and assume that there does not exist any monochromatic line. As before, we shall show that under this assumption there must be a monochromatic line.

Let $A$ be the set of Red points, and let $|A| = t$. According to Fact~\ref{fact: 2}, every plane $P$ in $F_3(4)$ has $|P \cap A| \geq 1$. Also, it is not difficult to see that if $|P \cap A| \geq 5$, then $P$ contains a monochromatic line in the color Red. Hence every plane in $F_3(4)$ meets $A$ in either $1,2,3$ or 4 points. 

Let $a_i$ be the number of planes in $F_3(4)$ which meet $A$ in exactly $i$ points, and for each $x$ in $A$ let $A_x$ denote the set of planes in $F_3(4)$ which contain $x$.

In $F_3(4)$ there are $(3^4 - 1)(3^4 - 3)/(3^2 - 1)(3^2 - 3) = 130$ 2-dimensional vector subspaces and hence 130 (affine) planes through each point. The total number of planes is $130 \cdot 3^4/3^2 = 1170$. We also use the fact that since $A$ contains no line, there is exactly one plane through any three points of $A$; also there are $(3^4 - 3)/(3^2 - 3) = 13$ planes through each pair of points. 

Putting all this information together (and counting the contribution of each type of plane to the various sums) we obtain the following equations.
\begin{align*} 
a_1 + a_2 + a_3 + a_4 &= 1170, \\
a_1 + 2a_2 + 3a_3 + 4a_4 &= \sum |A_x| = 130t, \\
a_2 + 3a_3 + 6a_4 &= \sum |A_x \cap A_y| = 13 \binom{t}{2}, \\
a_3 + 4a_4 &= \sum |A_x \cap A_y \cap A_z| = \binom{t}{3}. \end{align*}
Solving gives 
\begin{align*}
a_1 &= 4 \cdot 1170 - 3 \cdot 130 t + 2 \cdot 13 \binom{t}{2} - \binom{t}{3}, \\
a_2 &= -6 \cdot 1170 + 6 \cdot 130 t - 5 \cdot 13 \binom{t}{2} + 3\binom{t}{3}, \\
a_3 &= 4 \cdot 1170 - 4 \cdot 130 t + 4 \cdot 13\binom{t}{2} - 3\binom{t}{3}, \\
a_4 &= -1170 + 130t - 13\binom{t}{2} + \binom{t}{3}.
\end{align*}

When $t = 27$, $a_3 = 117$. For all larger values of $t$, $a_3$ is negative. Since at least one of the colors must occur at least $27$ times (and the same set of equations hold when $A$ is replaced by the set of Blue points or the set of Green points), it follows that $t = 27$ and 
\[ a_1 = 351, \qquad a_2 = 0, \qquad a_3 = 117, \qquad a_4 = 704. \]

The same conclusions hold for the Blue points and the Green points. Therefore there are exactly 351 $(4,4,1)$-planes, 351 $(4,1,4)$-planes, 351 $(1,4,4)$-planes, and 117 $(3,3,3)$-planes, where an $(r,b,g)$-plane is one which has $r$ Red points, $b$ Blue points, and $g$ Green points.

Consider the $(4,4,1)$-planes and $(4,1,4)$-planes. There are 702 of these planes, and 130 parallel classes of planes in $F_3(4)$, hence some 6 of these planes lie in the same parallel class. We may assume by an affine transformation that these 6 planes are all parallel to the plane
\[ P_1 = \{(0,0,x,y): x,y \in F_3\}. \]

Each of the 6 planes intersects the plane
\[ P_0 = \{(x,y,0,0): x,y \in F_3\} \]
in one point. Let the 6 planes be $a_1 + P_1, \dots, a_6 + P_1$, where $a_1,\dots,a_6$ are in $P_0$.

Some three of the six points $a_1,\dots,a_6$ are collinear in $P_0$, say $a_1,a_2,a_3$. Of the three planes $a_1 + P_1, a_2 + P_1, a_3 + P_1$, at least two are of the same type (both $(4,4,1)$-planes or both $(4,1,4)$-planes). Assume without loss of generality that two of them are $(4,4,1)$-planes. Then the union
\[ (a_1 + P_1) \cup (a_2 + P_1) \cup (a_3 + P_1) \]
is a 3-space, in which the color Green appears at most 6 times. 

In this 3-space, there are $(3^3 - 1)(3^3 - 3)/(3^2 - 1)(3^2 - 3) = 13$ planes through each point, $(3^3 - 3)/(3^2 - 3) = 4$ planes through each pair of points, one plane through each triple of Green points (since we are assuming no monochromatic line) and $13 \cdot 3^3/3^2 = 39$ planes altogether.

Let $G$ be the set of 6 Green points in this 3-space, and for $x$ in $G$ let $G_x$ be the set of planes containing $x$. Then 
\begin{align*}
\left| \bigcup G_x \right| &\leq \sum |G_x| - \sum |G_x \cap G_y| + \sum |G_x \cap G_y \cap G_z| \\
&= 6 \cdot 13 - 15 \cdot 4 + 20 \\
&= 38 < 39. 
\end{align*}

Therefore there is a plane with no Green point, and hence a monochromatic Red or Blue line. This shows that $d(3,3) \leq 4$, and hence $d(3,3) = 4$.
\end{proof}

\section{Concluding remarks} \label{sec: 3}

One would like to have upper and lower bounds for $d(k,3)$, $k \geq 1$. Perhaps the correct order of magnitude for an upper bound for $d(k,3)$ is $2^{k - 1}$, as is suggested by $d(1,3) = 1$, $d(2,3) = 2$, $d(3,3) = 4$. Perhaps the coloring of $F_3(3)$ which was used to show $d(3,3) > 3$ has a generalization to $F_3(d)$, for $d >3$. 

The best-known bounds for the van der Waerden numbers $w(k,3)$ are 
\[ k^{c \log k} < w(k,3) < 2^{2^{dk}}, \quad k \geq 1, \]
where $c,d$ are constants~\cite{bernoulli1772}.



\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}